Bounds-checking failure while indexing an empty UnitRange if there's an overflow

[jishnub]

julia> r = Base.OneTo(0) .+ typemax(Int)
-9223372036854775808:9223372036854775807

julia> length(r)
0

julia> axes(r,1)
Base.OneTo(0)

julia> r[1]
-9223372036854775808

julia> r[1000]
-9223372036854774809

Related:

julia> r2 = typemin(Int):typemax(Int)
-9223372036854775808:9223372036854775807

julia> length(r2)
0

[Seelengrab]

I don't think either of these are realistically fixable. The length one can only ever be accurate for overflowing ranges if a larger datatype is returned.

The indexing one is a result of the overflow that happened in 1 + typemax(Int) - the result is otherwise correct:

julia> typemin(Int) + 1000 - 1
-9223372036854774809

[vtjnash]

julia> Base.checked_length(r)
ERROR: OverflowError: 9223372036854775807 - -9223372036854775808 overflowed for type Int64
Stacktrace:
 [1] throw_overflowerr_binaryop(op::Symbol, x::Int64, y::Int64)
   @ Base.Checked ./checked.jl:163
 [2] checked_sub
   @ ./checked.jl:232 [inlined]
 [3] checked_length(r::UnitRange{Int64})
   @ Base ./range.jl:714
 [4] top-level scope
   @ REPL[2]:1


julia> Base.checked_length(r2)
ERROR: OverflowError: 9223372036854775807 - -9223372036854775808 overflowed for type Int64
Stacktrace:
 [1] throw_overflowerr_binaryop(op::Symbol, x::Int64, y::Int64)
   @ Base.Checked ./checked.jl:163
 [2] checked_sub
   @ ./checked.jl:232 [inlined]
 [3] checked_length(r::UnitRange{Int64})
   @ Base ./range.jl:714
 [4] top-level scope
   @ REPL[9]:1

[johnnychen94]

If there's nothing that needs to change to the current overflow behavior, should we close this?

[jishnub]

One option is to change the indexing behavior to use

_in_unit_range(v::UnitRange, val, i::Integer) = 0 < i <= v.stop - v.start + 1

but this will add an overhead to address somewhat uncommon use cases.

[jishnub]

This behavior is somewhat interesting

julia> r = typemin(Int):typemax(Int)
-9223372036854775808:9223372036854775807

julia> length(r)
0

julia> isempty(r)
false

Ideally this should be consistent, overflow or not

[cmcaine]

What do you think length(typemin(Int):typemax(Int)) should return? The numeric answer is equal to typemax(UInt64), but length returns a signed value. So there are three options to "fix" this, all of which are breaking changes:

• Have length throw an error if length > typemax(Int) (this is the behaviour of Base.checked_length)
• Have the range constructor throw an error if the length would be > typemax(Int)
• Have length return a UInt64 (makes finding the difference between lengths difficult) or an Int128 (slow)

Personally, the behaviour of Base.checked_length seems fine to me as the default, so long as it got a nice error message.

As a related issue, because an empty range is indicated by stop < start, if you start a range at the typemin then you get wacky behaviour if length is 0:

# length == 0; !isempty
julia> range(typemin(Int); length=0)
-9223372036854775808:9223372036854775807

# Gets promoted to UnitRange{Int64} and is fine.
julia> range(typemin(Int8); length=0)
-128:-129

# But if we construct a UnitRange{Int8} then `range` is lying to us again:
# length == 256; !isempty
julia> range(typemin(Int8), length=zero(Int8)) |> length
256

# length and isempty are correct for this one, but you'll get an `InexactError` if you try to access the `last` value of the range
julia> range(typemin(UInt8), length=zero(UInt8)) |> length
0

# with a UInt range, the `last` value is wrong, but isempty and length are still correct.
julia> range(typemin(UInt); length=zero(UInt)) |> last
0xffffffffffffffff

I think defining last(1:0) == 0 makes it difficult to fix this. If we could forbid reading the stop-point of an empty range then we wouldn't have to define what the stop point of a range starting at typemin(Int) was. Or if we had half-open ranges then we wouldn't have a problem because then the empty range would have start==stop and we could define stop < start as an illegal range.

Here are some possible improvements:

1. Make range(start; length=0) throw an error when length=0 and stop > start.
2. Make range(start; length=n) return a different kind of range object that's defined by start and length, not start and stop and define consistent isempty, length and last functions for it. If we consistently allow last to throw errors (as it does already for range(typemin(UInt8), length=zero(UInt8)) |> last), then we could have consistent behaviour for all three functions across ranges of any type of integer.
3. Do 2 and also define the regular ranges in (start, len) form.