Ranges longer than size_t.max

[Simen Kjaeraas]

On 2012-18-29 02:12, Peter Alexander <peter.alexander.au at gmail.com> wrote:

> There was a discussion a while ago about the type returned by .length  
> for ranges. I believe the conclusion was that it should always be size_t.
>
> My question now is what to do with really large ranges? For example, if  
> we have a range of permutations of the elements in a set, when the set  
> is larger than 21 the number of permutations is 21 factorial, which is  
> over 2^64. As far as I see, there are three options:
>
> 1. Allow ranges to return BigInt for length.
> 2. Allow ranges like this but assert when .length overflows.
> 3. Allow ranges like this and just allow .length to overflow dangerously.
> 4. Do not allow ranges like this.
>
> Option 1 solves the problem, but significantly complicates Phobos  
> development for the rare case.
>
> Option 2 works, and is practical, although runtime asserts are  
> undesirable.
>
> Option 3 is current Phobos practice (presumably because overflow is  
> unlikely). See example below. This may be acceptable currently, but  
> perhaps less so when overflow is more likely.
> --------------------------------
> auto a = iota(size_t.max / 2 + 1);	
> auto b = chain(a, a);
> writeln(a.length); // 9223372036854775808
> writeln(b.length); // 0
> --------------------------------
>
> Option 4 works, but it would be a shame to lose these ranges.
>
> Thoughts?

64 bits ought to be enough for anyone. :p

This is a bit of a tough one, and I believe the root problem is that
user-defined types are second-class citizens. Specifically, CommonType
is incapable of finding the common type of BigInt and int. This makes
it hard to find the correct return type for e.g. chain. Behind the
scenes, CommonType is using ?: to figure out the correct type. If D
supported opImplicitCastFrom (as suggested in WalterAndrei.pdf), ?:
could figure out the correct type, and chain's .length could be:

   private template LengthType(Range)
   {
       alias typeof(Range.length) LengthType;
   }

   @property auto length()
   {
       CommonType!(staticMap!(LengthType, R)) result = 0;
       foreach (i, Unused; R)
       {
           result += source[i].length;
       }
       return result;
   }

This would thus support BigInt .length just as well as size_t, byte,
or whatever.

-- 
Simen