search

JuliaLang / julia

The Julia Programming Language
https://julialang.org/
MIT License
45.47k stars 5.46k forks source link

Collecting a `StepRange` can crash julia if equality isn't defined for custom number types #50057

Open jishnub opened 1 year ago

jishnub commented 1 year ago

This happens because of an @inbounds annotation in the collect. Consider the following code:

module MyInts

import Base: +, -, <, div, rem, Int, BigInt

export MyInt

struct MyInt{T<:Integer} <: Integer
    x :: T
end

MyInt{T}(x::MyInt{T}) where {T<:Integer} = x
MyInt{T}(x::MyInt) where {T<:Integer} = MyInt{T}(T(x))

for f in (:+, :-, :rem, :div)
    @eval $f(a::MyInt, b::MyInt) = MyInt($f(a.x, b.x))
end

for f in (:<,)
    @eval $f(a::MyInt, b::MyInt) = $f(a.x, b.x)
end

for f in (:Int, :BigInt)
    @eval $f(a::MyInt) = $f(a.x)
end

Base.promote_rule(::Type{MyInt{A}}, ::Type{MyInt{B}}) where {A<:Integer,B<:Integer} = MyInt{promote_type(A,B)}
Base.promote_rule(::Type{MyInt{A}}, ::Type{B}) where {A<:Integer,B<:Integer} = promote_type(A,B)

end

In this, the user hasn't defined Base.:(==)(a::MyInt, b::MyInt) yet, presumably because 

julia> using .MyInts

julia> MyInt(2) == MyInt(2)
true

But if they try collecting a BigInt StepRange, it'll lead to a segfault:

julia> StepRange(MyInt(big(1)), MyInt(big(1)), MyInt(big(2))) |> collect

[19373] signal (11.1): Segmentation fault
in expression starting at REPL[4]:1
jl_gc_pool_alloc_inner at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/gc.c:1451 [inlined]
ijl_gc_pool_alloc at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/gc.c:1494
_#1 at ./gmp.jl:64 [inlined]
BigInt at ./gmp.jl:63 [inlined]
add at ./gmp.jl:166
+ at ./gmp.jl:490 [inlined]
+ at ./REPL[1]:15 [inlined]
iterate at ./range.jl:892 [inlined]
vcat at ./range.jl:1362
collect at ./range.jl:1367 [inlined]
|> at ./operators.jl:907
unknown function (ip: 0x7fcd365063f2)
_jl_invoke at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/gf.c:2758 [inlined]
ijl_apply_generic at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/gf.c:2940
jl_apply at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/julia.h:1879 [inlined]
do_call at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/interpreter.c:126
eval_value at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/interpreter.c:226
eval_stmt_value at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/interpreter.c:177 [inlined]
eval_body at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/interpreter.c:624
jl_interpret_toplevel_thunk at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/interpreter.c:762
jl_toplevel_eval_flex at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/toplevel.c:912
jl_toplevel_eval_flex at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/toplevel.c:856
jl_toplevel_eval_flex at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/toplevel.c:856
jl_toplevel_eval_flex at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/toplevel.c:856
ijl_toplevel_eval_in at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/toplevel.c:971
eval at ./boot.jl:370 [inlined]
eval_user_input at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/usr/share/julia/stdlib/v1.9/REPL/src/REPL.jl:153
repl_backend_loop at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/usr/share/julia/stdlib/v1.9/REPL/src/REPL.jl:249
#start_repl_backend#46 at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/usr/share/julia/stdlib/v1.9/REPL/src/REPL.jl:234
start_repl_backend at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/usr/share/julia/stdlib/v1.9/REPL/src/REPL.jl:231
_jl_invoke at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/gf.c:2758 [inlined]
ijl_apply_generic at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/gf.c:2940
#run_repl#59 at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/usr/share/julia/stdlib/v1.9/REPL/src/REPL.jl:379
run_repl at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/usr/share/julia/stdlib/v1.9/REPL/src/REPL.jl:365
jfptr_run_repl_60276.clone_1 at /home/jishnu/packages/julias/julia-1.9/lib/julia/sys.so (unknown line)
_jl_invoke at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/gf.c:2758 [inlined]
ijl_apply_generic at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/gf.c:2940
#1017 at ./client.jl:421
jfptr_YY.1017_32248.clone_1 at /home/jishnu/packages/julias/julia-1.9/lib/julia/sys.so (unknown line)
_jl_invoke at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/gf.c:2758 [inlined]
ijl_apply_generic at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/gf.c:2940
jl_apply at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/julia.h:1879 [inlined]
jl_f__call_latest at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/builtins.c:774
#invokelatest#2 at ./essentials.jl:816 [inlined]
invokelatest at ./essentials.jl:813 [inlined]
run_main_repl at ./client.jl:405
exec_options at ./client.jl:322
_start at ./client.jl:522
jfptr__start_37386.clone_1 at /home/jishnu/packages/julias/julia-1.9/lib/julia/sys.so (unknown line)
_jl_invoke at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/gf.c:2758 [inlined]
ijl_apply_generic at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/gf.c:2940
jl_apply at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/julia.h:1879 [inlined]
true_main at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/jlapi.c:573
jl_repl_entrypoint at /cache/build/default-amdci4-0/julialang/julia-release-1-dot-9/src/jlapi.c:717
main at julia (unknown line)
unknown function (ip: 0x7fcd4db8250f)
__libc_start_main at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
unknown function (ip: 0x401098)
Allocations: 1437462 (Pool: 1436301; Big: 1161); GC: 2
[1]    19373 segmentation fault (core dumped)  julia

This seems to happen because of the inbounds annotation in vcat:

https://github.com/JuliaLang/julia/blob/f407a4cac3d1c660d1f8f1a9b367eec108d98178/base/range.jl#L1358-L1370

and because

julia> r = StepRange(MyInt(big(1)), MyInt(big(1)), MyInt(big(2)));

julia> last(r) == MyInt(big(2))
false

Ideally, the user should receive a helpful error message (although I'm not certain what that should be in this case)

Edit: as discussed below, I've removed the <= definition, as this wasn't necessary to reproduce the issue.

LilithHafner commented 1 year ago

We can fix this with

diff --git a/base/range.jl b/base/range.jl
index f0bcc0dd20..e58f1d8299 100644
--- a/base/range.jl
+++ b/base/range.jl
@@ -894,7 +894,7 @@ iterate(r::OrdinalRange) = isempty(r) ? nothing : (first(r), first(r))

 function iterate(r::OrdinalRange{T}, i) where {T}
     @inline
-    i == last(r) && return nothing
+    (step(r) < zero(step(r)) ? i > last(r) : i < last(r)) || return nothing
     next = convert(T, i + step(r))
     (next, next)
 end

But this begs the question: which operations are required on a number to support ranges?

EDIT to replace <= with <

Seelengrab commented 1 year ago

It's a bit odd to implement < and <=, instead of < and ==, since <= is defined to fall back on those. < should have some mention of == in its docstring though.

EDIT: disregard the below - the segfault happens when it tries to write the result, which is then undersized :facepalm:

I wonder why exactly this segfaults in the first place :thinking: The stacktrace suggests this is due to the +, not ==:

BigInt at ./gmp.jl:63 [inlined]
add at ./gmp.jl:166
+ at ./gmp.jl:490 [inlined]
+ at ./REPL[1]:15 [inlined]
iterate at ./range.jl:892 [inlined]
vcat at ./range.jl:1362
collect at ./range.jl:1367 [inlined]
|> at ./operators.jl:907
unknown function (ip: 0x7fcd365063f2)

EDIT: Ah, == is false, so shouldn't this lead to a stackoverflow, rather than a segfault?

LilithHafner commented 1 year ago

Oops, there was no need for me to use <= above.

jishnub commented 1 year ago

It's a bit odd to implement < and <=, instead of < and ==, since <= is defined to fall back on those.

Fair enough, the <= definition is redundant in this example

jishnub commented 1 year ago

This seems to be a duplicate of https://github.com/JuliaLang/julia/issues/42483#issuecomment-932949350, albeit for integer ranges rather than floating-point ones. I'm leaving this open for now, as this is more about equality being required for ranges, rather than being able to compare the values exactly. In this case, the comparison is possible