vcat(::AbstractRange...) can do an out of bounds access inside an @inbounds block

[KristofferC]

The repro below requires ForwardDiff 0.10.19 or earlier.

ForwardDiff breaks some assumptions made by the range framework which causes it to compute the length wrong which leads to an out of bounds access:

❯ julia -q --check-bounds=yes

julia> using ForwardDiff:Dual

julia> r = Dual(0.0):Dual(0.2):Dual(25.0)

julia> collect(r)
ERROR: BoundsError: attempt to access 124-element Vector{Dual{Nothing, Float64, 0}} at index [125]
Stacktrace:
 [1] setindex!
   @ ./array.jl:839 [inlined]
 [2] vcat(rs::StepRange{Dual{Nothing, Float64, 0}, Dual{Nothing, Float64, 0}})
   @ Base ./range.jl:1036
 [3] collect(r::StepRange{Dual{Nothing, Float64, 0}, Dual{Nothing, Float64, 0}})
   @ Base ./range.jl:1043
 [4] top-level scope
   @ REPL[4]:1

However, this part of the code has an @inbounds which thus gives memory corruption unless bounds checking is enforced:

julia/base/range.jl

Lines 1320 to 1332 in be28eb3

	function vcat(rs::AbstractRange{T}...) where T
	n::Int = 0
	for ra in rs
	n += length(ra)
	end
	a = Vector{T}(undef, n)
	i = 1
	for ra in rs, x in ra
	@inbounds a[i] = x
	i += 1
	end
	return a
	end

The core problem is that iterating the range never terminates:

julia> for x in r
           println(x)
       end
Dual{Nothing}(0.0)
Dual{Nothing}(0.2)
Dual{Nothing}(0.4)
Dual{Nothing}(0.6000000000000001)
Dual{Nothing}(0.8)
Dual{Nothing}(1.0)
Dual{Nothing}(1.2)
Dual{Nothing}(1.4)
Dual{Nothing}(1.5999999999999999)
Dual{Nothing}(1.7999999999999998)
Dual{Nothing}(1.9999999999999998)
Dual{Nothing}(2.1999999999999997)
Dual{Nothing}(2.4)
Dual{Nothing}(2.6)
Dual{Nothing}(2.8000000000000003)
Dual{Nothing}(3.0000000000000004)
# never ends

Perhaps this is a bug with the range framework more than the vcat method:

julia> Dual(0.0):Dual(0.2):Dual(25.0) |> last
Dual{Nothing}(24.8)

julia> 0.0:0.2:25.0 |> last
25.0

Also note:

julia> Dual(0.0):Dual(0.2):Dual(25.0) |> typeof
StepRange{Dual{Nothing, Float64, 0}, Dual{Nothing, Float64, 0}}

julia> 0.0:0.2:25.0 |> typeof
StepRangeLen{Float64, Base.TwicePrecision{Float64}, Base.TwicePrecision{Float64}, Int64}

Downstream issue: JuliaDiff/ForwardDiff.jl#548

[vtjnash]

While we often do depend on length being correct, perhaps we could add a boundscheck at the end, so we can be more confident it will crash quickly?

[KristofferC]

Why can we assume length is correct in user code but at the same time reject PRs like #40397 because they are too unsafe?

[KristofferC]

Here is a MWE that causes the out of bounds access:

struct W{T} <: Number
    n::T
end

for op in (:+, :-)
    @eval Base.$op(a::W, b::W) = W($op(a.n, b.n))
end
Base.isless(a::W, b::W) = isless(a.n, b.n)
Base.rem(a::W, b::W) = rem(a.n, b.n)
Base.promote_rule(::Type{W{Float64}}, ::Type{Float64}) = W{Float64}
Base.div(a::W, b::W, c) = div(a.n, b.n, c)

collect(W(0.0):W(0.2):W(25.0)) # boom

It doesn't feel like W has done anything very wrong here that would deserve potential memory corruption.

[vtjnash]

We probably also should not.

Can we improve the range iterator for that case.

[mcabbott]

Probably you know this, but iterate(::OrdinalRange) seems to assume exact equality in order to stop:

julia> r = W(0.0):W(0.2):W(25.0)
W{Float64}(0.0):W{Float64}(0.2):W{Float64}(24.8)

julia> typeof(r)
StepRange{W{Float64}, W{Float64}}

julia> length(r)
124

julia> last(r)
W{Float64}(24.8)

julia> for x in Iterators.take(Iterators.drop(r, 120), 7)
        @show x
       end
x = W{Float64}(23.999999999999947)
x = W{Float64}(24.199999999999946)
x = W{Float64}(24.399999999999945)
x = W{Float64}(24.599999999999945)
x = W{Float64}(24.799999999999944)
x = W{Float64}(24.999999999999943)
x = W{Float64}(25.199999999999942)

julia> @which iterate(r, first(r))   # i == last(r) && return nothing
iterate(r::OrdinalRange{T}, i) where T in Base at range.jl:868

That's fine for UnitRange of course. The method for Union{StepRangeLen,LinRange} checks the index against the length instead.