Integer range overflows

[andrioni]

As the length of a range is stored as an Int, it is possible to overflow it using Uint:

julia> 0x1:0x7fffffffffffffff
0x0000000000000001:0x7fffffffffffffff

julia> 0x1:0x8000000000000000
ERROR: Range: length must be non-negative
 in Range1 at range.jl:27
 in colon at range.jl:86

Another problem caused by this is that BigInt ranges are also limited, which is how I discovered the problem, via #3077:

julia> BigInt(1):BigInt("9223372036854775807")
1:9223372036854775807

julia> BigInt(1):BigInt("9223372036854775808")
ERROR: InexactError()
 in convert at gmp.jl:67
 in colon at range.jl:38

[StefanKarpinski]

Yikes. This is going to be tough to solve cleanly.

[JeffBezanson]

The only hope may be to add BigRange.

[andrioni]

That's what I was thinking, changing only colon would allow it. (and the Uint side of the bug isn't as relevant and can be solved by making the default length a Uint instead of a Int, no?)

[JeffBezanson]

We use Int as the default type for everything, including lengths, to avoid worrying about signed vs. unsigned arithmetic. Unsigned makes it too easy to get subtle bugs.

[GunnarFarneback]

Int ranges overflow as easily as unsigned ranges.

julia> r=0:typemax(Int)
0:-1

julia> r[end]
ERROR: BoundsError()
 in getindex at range.jl:109

Naturally Int128/Uint128 ranges also have the same problem.

[ggggggggg]

function better_range(start,stop,step)
    a,b = divrem(start,step)
    c,d = divrem(stop,step)
    len = c-a+div(d-b+step,step)
    Range(start, step, len)
end
julia> 1:3:typemax(Int)
1:3:-2
julia> better_range(1,typemax(Int),3)
1:3:9223372036854775807

I think if you calculate the length slightly differently you can avoid most of the overflow issues.

[quinnj]

I believe this can be closed. It seems we've fixed or give an appropriate OverflowError in all the cases above:

In  [29]:  0x1:0x7fffffffffffffff

Out [29]: 0x0000000000000001:0x7fffffffffffffff

In  [30]: 0x1:0x8000000000000000

Out [30]: 0x0000000000000001:0x8000000000000000

In  [31]: BigInt(1):BigInt("9223372036854775807")

Out [31]: 1:9223372036854775807

In  [32]: BigInt(1):BigInt("9223372036854775808")

Out [32]: 1:9223372036854775808

In  [33]:  r=0:typemax(Int)

Out [33]: 0:9223372036854775807

In  [34]: r[end]

Out [34]: ERROR: OverflowError()
while loading In[34], in expression starting on line 1
 in endof at abstractarray.jl:24

[JeffBezanson]

Thanks for finding these issues.
I wonder if we should provide endof for ranges so r[end] can work.

[quinnj]

It seems to work to work already.....

In  [103]: t = 1:2

Out [103]: 1:2

In  [104]: t[end]


Out [104]: 2

In  [105]: r = 1:3:30

Out [105]: 1:3:28

In  [106]: r[end]

Out [106]: 28

In  [107]: using Dates

In  [108]: f = Date(2013):Date(2014)

Out [108]: 2013-01-01:1 day:2014-01-01

In  [109]: f[end]

Out [109]: 2014-01-01

In  [110]: v = 1.0:2.0:12.0

Out [110]: 1.0:2.0:11.0

In  [111]: v[end]

Out [111]: 11.0

[JeffBezanson]

It works but it uses a definition that relies on length.