Crash in subtype_unionall()

nalimilan commented 7 years ago

With the nl/crash branch of CategoricalArrays, I get a crash in subtype_unionall with Julia from a recent git master:

julia> using CategoricalArrays

julia> NullableCategoricalVector(2)

signal (11): Segmentation fault
while loading no file, in expression starting on line 0
subtype_unionall at /home/milan/Dev/julia/src/subtype.c:590
subtype_unionall at /home/milan/Dev/julia/src/subtype.c:570
subtype_unionall at /home/milan/Dev/julia/src/subtype.c:599
subtype_unionall at /home/milan/Dev/julia/src/subtype.c:599
forall_exists_equal at /home/milan/Dev/julia/src/subtype.c:950
subtype at /home/milan/Dev/julia/src/subtype.c:929
subtype_tuple at /home/milan/Dev/julia/src/subtype.c:765 [inlined]
subtype at /home/milan/Dev/julia/src/subtype.c:909
subtype_unionall at /home/milan/Dev/julia/src/subtype.c:570
exists_subtype at /home/milan/Dev/julia/src/subtype.c:972 [inlined]
forall_exists_subtype at /home/milan/Dev/julia/src/subtype.c:1000
jl_subtype_env at /home/milan/Dev/julia/src/subtype.c:1054
jl_f_issubtype at /home/milan/Dev/julia/src/builtins.c:286
abstract_call_gf_by_type at ./inference.jl:1299
unknown function (ip: 0x7ffa2fe40c36)
jl_call_fptr_internal at /home/milan/Dev/julia/src/julia_internal.h:353 [inlined]
jl_call_method_internal at /home/milan/Dev/julia/src/julia_internal.h:372 [inlined]
jl_apply_generic at /home/milan/Dev/julia/src/gf.c:1923
abstract_call at ./inference.jl:1888
unknown function (ip: 0x7ffa2fe3cb8e)
jl_call_fptr_internal at /home/milan/Dev/julia/src/julia_internal.h:353 [inlined]
jl_call_method_internal at /home/milan/Dev/julia/src/julia_internal.h:372 [inlined]
jl_apply_generic at /home/milan/Dev/julia/src/gf.c:1923
abstract_eval_call at ./inference.jl:1918
abstract_eval at ./inference.jl:1941
unknown function (ip: 0x7ffa2fe37c46)
jl_call_fptr_internal at /home/milan/Dev/julia/src/julia_internal.h:353 [inlined]
jl_call_method_internal at /home/milan/Dev/julia/src/julia_internal.h:372 [inlined]
jl_apply_generic at /home/milan/Dev/julia/src/gf.c:1923
typeinf_work at ./inference.jl:2715
typeinf at ./inference.jl:2780
typeinf_frame at ./inference.jl:2495
typeinf_code at ./inference.jl:2576
unknown function (ip: 0x7ffa2fe53ead)
jl_call_fptr_internal at /home/milan/Dev/julia/src/julia_internal.h:353 [inlined]
jl_call_method_internal at /home/milan/Dev/julia/src/julia_internal.h:372 [inlined]
jl_apply_generic at /home/milan/Dev/julia/src/gf.c:1923
typeinf_ext at ./inference.jl:2615
unknown function (ip: 0x7ffa2fe32512)
jl_call_fptr_internal at /home/milan/Dev/julia/src/julia_internal.h:353 [inlined]
jl_call_method_internal at /home/milan/Dev/julia/src/julia_internal.h:372 [inlined]
jl_apply_generic at /home/milan/Dev/julia/src/gf.c:1923
jl_apply at /home/milan/Dev/julia/src/julia.h:1424 [inlined]
jl_apply_with_saved_exception_state at /home/milan/Dev/julia/src/rtutils.c:257
jl_type_infer at /home/milan/Dev/julia/src/gf.c:262
jl_compile_for_dispatch at /home/milan/Dev/julia/src/gf.c:1658
jl_compile_method_internal at /home/milan/Dev/julia/src/julia_internal.h:321 [inlined]
jl_call_method_internal at /home/milan/Dev/julia/src/julia_internal.h:368 [inlined]
jl_apply_generic at /home/milan/Dev/julia/src/gf.c:1923
do_call at /home/milan/Dev/julia/src/interpreter.c:75
eval at /home/milan/Dev/julia/src/interpreter.c:242
jl_interpret_toplevel_expr at /home/milan/Dev/julia/src/interpreter.c:34
jl_toplevel_eval_flex at /home/milan/Dev/julia/src/toplevel.c:575
jl_toplevel_eval_in at /home/milan/Dev/julia/src/builtins.c:496
eval at ./boot.jl:236
unknown function (ip: 0x7ffa2ff917af)
jl_call_fptr_internal at /home/milan/Dev/julia/src/julia_internal.h:353 [inlined]
jl_call_method_internal at /home/milan/Dev/julia/src/julia_internal.h:372 [inlined]
jl_apply_generic at /home/milan/Dev/julia/src/gf.c:1923
eval_user_input at ./REPL.jl:66
unknown function (ip: 0x7ffa30018d8f)
jl_call_fptr_internal at /home/milan/Dev/julia/src/julia_internal.h:353 [inlined]
jl_call_method_internal at /home/milan/Dev/julia/src/julia_internal.h:372 [inlined]
jl_apply_generic at /home/milan/Dev/julia/src/gf.c:1923
macro expansion at ./REPL.jl:97 [inlined]
#1 at ./event.jl:73
unknown function (ip: 0x7ffa1d7db32f)
jl_call_fptr_internal at /home/milan/Dev/julia/src/julia_internal.h:353 [inlined]
jl_call_method_internal at /home/milan/Dev/julia/src/julia_internal.h:372 [inlined]
jl_apply_generic at /home/milan/Dev/julia/src/gf.c:1923
jl_apply at /home/milan/Dev/julia/src/julia.h:1424 [inlined]
start_task at /home/milan/Dev/julia/src/task.c:267
unknown function (ip: 0xffffffffffffffff)
Allocations: 11023194 (Pool: 11021512; Big: 1682); GC: 5
Segmentation fault (core dumped)

(The codebase is in an inconsistent state which isn't supposed to work, but for this reason it's a good test for inference.)

martinholters commented 7 years ago

With assertions enabled, this hits this assertion after recursing quasi-infinitely. Simpler repro (with assertions on/debug build):

struct Null end
struct CategoricalArray{T, V} end
t1=Type{CategoricalArray{Union{T, Null}, T} where T}
t2=Type{CategoricalArray{Union{T, Null}, V2} where V2} where T
typeintersect(t1,t2)

Might be related to #21332, although there the recursion went through var_lt, while here it goes through var_gt.

JeffBezanson commented 7 years ago

Just t1 <: t2 also seems to reproduce the problem.

ulysses4ever commented 6 years ago

Is there any updates on the status of this? Is it going to be handled for 0.7/1.0? Is there something fundamental behind this that doesn't allow fixing? (Like simple stack size increase is not feasible or something anymore.) @JeffBezanson (It is still reproducible on master.)

ulysses4ever commented 6 years ago

One more example which seems similar and doesn't require external packages to reproduce:

julia> t1 = Ref{Ref{Ref{Union{Int64, T}}} where T}; t2 = Ref{Ref{Ref{Union{T, S}}} where T} where S
julia> t1 <: t2
ERROR: StackOverflowError:

This is on master.

vtjnash commented 2 years ago

Why closing? The example above still reproduces

JuliaLang / julia

Crash in subtype_unionall() #22123