Inconsistent StackOverflowError with recursive parametric dynamic types

General Usage
,
1

I think I stumbled upon a bug in the Julia, but I am not sure what kind of issue is this.

The code is the following:

using Graphs

abstract type MyAbstract end

struct Composite{T <: MyAbstract,R <: MyAbstract} <: MyAbstract
    a::T
    av::Vector{Union{T,R}}
end

struct Leaf <: MyAbstract
    b
end
Leaf() = Leaf(1)

Composite{T,R}() where {T<:MyAbstract,R<:MyAbstract} = Composite{T,R}(T(),Vector{Union{T,R}}([T()]))

randcomp1(firsttype::Type) = randn() > 0.5 ? Composite{firsttype, firsttype}() : Composite{firsttype, Composite}()

and then I get

julia> randcomp1(Leaf)
Internal error: encountered unexpected error in runtime:
StackOverflowError()
jl_has_free_typevars at /buildworker/worker/package_linux64/build/src/jltypes.c:114
intersect_union at /buildworker/worker/package_linux64/build/src/subtype.c:2141
intersect at /buildworker/worker/package_linux64/build/src/subtype.c:3073
intersect_all at /buildworker/worker/package_linux64/build/src/subtype.c:3175
intersect_aside at /buildworker/worker/package_linux64/build/src/subtype.c:2131
intersect_var at /buildworker/worker/package_linux64/build/src/subtype.c:2334
intersect at /buildworker/worker/package_linux64/build/src/subtype.c:3057
intersect_union at /buildworker/worker/package_linux64/build/src/subtype.c:2154
intersect at /buildworker/worker/package_linux64/build/src/subtype.c:3073
intersect_all at /buildworker/worker/package_linux64/build/src/subtype.c:3175
intersect_aside at /buildworker/worker/package_linux64/build/src/subtype.c:2131
intersect_var at /buildworker/worker/package_linux64/build/src/subtype.c:2334
intersect at /buildworker/worker/package_linux64/build/src/subtype.c:3057
intersect_union at /buildworker/worker/package_linux64/build/src/subtype.c:2154
intersect at /buildworker/worker/package_linux64/build/src/subtype.c:3073
intersect_all at /buildworker/worker/package_linux64/build/src/subtype.c:3175
^CWARNING: Force throwing a SIGINT
ERROR: ^CInterruptException:
Stacktrace:
 [1] top-level scope
   @ REPL[2]:1

caused by: StackOverflowError:
Stacktrace:
  [1] _methods_by_ftype
    @ ./reflection.jl:908 [inlined]
  [2] #findall#246
    @ ./compiler/methodtable.jl:68 [inlined]
  [3] (::Core.Compiler.var"#249#250"{Int64, Core.Compiler.CachedMethodTable{Core.Compiler.InternalMethodTable}, Core.Box})()
    @ Core.Compiler ./compiler/methodtable.jl:97
  [4] get!
    @ ./iddict.jl:178 [inlined]
  [5] #findall#248
    @ ./compiler/methodtable.jl:96 [inlined]
  [6] find_matching_methods(argtypes::Vector{Any}, atype::Any, method_table::Core.Compiler.CachedMethodTable{Core.Compiler.InternalMethodTable}, union_split::Int64, max_methods::Int64)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:308
  [7] abstract_call_gf_by_type(interp::Core.Compiler.NativeInterpreter, f::Any, fargs::Vector{Any}, argtypes::Vector{Any}, atype::Any, sv::Core.Compiler.InferenceState, max_methods::Int64)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:39
  [8] abstract_call_known(interp::Core.Compiler.NativeInterpreter, f::Any, fargs::Vector{Any}, argtypes::Vector{Any}, sv::Core.Compiler.InferenceState, max_methods::Int64)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:1342
  [9] abstract_call(interp::Core.Compiler.NativeInterpreter, fargs::Vector{Any}, argtypes::Vector{Any}, sv::Core.Compiler.InferenceState, max_methods::Int64)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:1397
 [10] abstract_call(interp::Core.Compiler.NativeInterpreter, fargs::Vector{Any}, argtypes::Vector{Any}, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:1382
 [11] abstract_eval_statement(interp::Core.Compiler.NativeInterpreter, e::Any, vtypes::Vector{Any}, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:1534
 [12] typeinf_local(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:1918
 [13] typeinf_nocycle(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:2014
 [14] _typeinf(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/typeinfer.jl:226
 [15] typeinf(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/typeinfer.jl:209
 [16] typeinf_edge
    @ ./compiler/typeinfer.jl:823 [inlined]
 [17] abstract_call_method(interp::Core.Compiler.NativeInterpreter, method::Method, sig::Any, sparams::Core.SimpleVector, hardlimit::Bool, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:504
 [18] abstract_call_gf_by_type(interp::Core.Compiler.NativeInterpreter, f::Any, fargs::Vector{Any}, argtypes::Vector{Any}, atype::Any, sv::Core.Compiler.InferenceState, max_methods::Int64)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:105
 [19] abstract_call(interp::Core.Compiler.NativeInterpreter, fargs::Vector{Any}, argtypes::Vector{Any}, sv::Core.Compiler.InferenceState, max_methods::Int64)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:1395
 [20] abstract_call(interp::Core.Compiler.NativeInterpreter, fargs::Vector{Any}, argtypes::Vector{Any}, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:1382
 [21] abstract_eval_statement(interp::Core.Compiler.NativeInterpreter, e::Any, vtypes::Vector{Any}, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:1534
 [22] typeinf_local(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:1918
 [23] typeinf_nocycle(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:2014
 [24] _typeinf(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/typeinfer.jl:226
 [25] typeinf(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/typeinfer.jl:209
 [26] typeinf_edge
    @ ./compiler/typeinfer.jl:823 [inlined]
 [27] abstract_call_method(interp::Core.Compiler.NativeInterpreter, method::Method, sig::Any, sparams::Core.SimpleVector, hardlimit::Bool, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:504
 [28] abstract_call_gf_by_type(interp::Core.Compiler.NativeInterpreter, f::Any, fargs::Vector{Any}, argtypes::Vector{Any}, atype::Any, sv::Core.Compiler.InferenceState, max_methods::Int64)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:105
 [29] abstract_call(interp::Core.Compiler.NativeInterpreter, fargs::Vector{Any}, argtypes::Vector{Any}, sv::Core.Compiler.InferenceState, max_methods::Int64)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:1395
 [30] abstract_call(interp::Core.Compiler.NativeInterpreter, fargs::Vector{Any}, argtypes::Vector{Any}, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:1382
 [31] abstract_eval_statement(interp::Core.Compiler.NativeInterpreter, e::Any, vtypes::Vector{Any}, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:1534
 [32] typeinf_local(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:1918
 [33] typeinf_nocycle(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:2014
 [34] _typeinf(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/typeinfer.jl:226
 [35] typeinf(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/typeinfer.jl:209
 [36] typeinf_edge
    @ ./compiler/typeinfer.jl:823 [inlined]
 [37] abstract_call_method(interp::Core.Compiler.NativeInterpreter, method::Method, sig::Any, sparams::Core.SimpleVector, hardlimit::Bool, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:504
 [38] abstract_call_gf_by_type(interp::Core.Compiler.NativeInterpreter, f::Any, fargs::Vector{Any}, argtypes::Vector{Any}, atype::Any, sv::Core.Compiler.InferenceState, max_methods::Int64)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:105
 [39] abstract_call(interp::Core.Compiler.NativeInterpreter, fargs::Vector{Any}, argtypes::Vector{Any}, sv::Core.Compiler.InferenceState, max_methods::Int64)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:1395
 [40] abstract_call(interp::Core.Compiler.NativeInterpreter, fargs::Vector{Any}, argtypes::Vector{Any}, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:1382
 [41] abstract_eval_statement(interp::Core.Compiler.NativeInterpreter, e::Any, vtypes::Vector{Any}, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:1534
 [42] typeinf_local(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:1918
 [43] typeinf_nocycle(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:2014
 [44] _typeinf(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/typeinfer.jl:226
 [45] typeinf(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/typeinfer.jl:209
 [46] typeinf_ext(interp::Core.Compiler.NativeInterpreter, mi::Core.MethodInstance)
    @ Core.Compiler ./compiler/typeinfer.jl:909
 [47] typeinf_ext_toplevel(interp::Core.Compiler.NativeInterpreter, linfo::Core.MethodInstance)
    @ Core.Compiler ./compiler/typeinfer.jl:942
 [48] typeinf_ext_toplevel(mi::Core.MethodInstance, world::UInt64)
    @ Core.Compiler ./compiler/typeinfer.jl:938
 [49] top-level scope
    @ REPL[2]:1

if I try again, the second time it will work normally:

julia> randcomp2(Leaf)
Composite{Leaf, Composite}(Leaf(1), Union{Leaf, Composite}[Leaf(1)])

If I remove using Graphs on the above code everything will run normally directly with the first try.
The problem is not particular to Graphs. I also tried other libraries like JuMP. It seems that just having an environment “loaded” with a package does some hurm.

Also if I define and call a function like the following with more concrete type allowance, it will work again without problems:

randcomp2(firsttype::Type{Leaf}) = randn() > 0.5 ? Composite{firsttype, firsttype}() : Composite{firsttype, Composite}()

Finally, if I substitute the general constructor with more concrete cases, it will again work without problems:

Composite{Leaf,Composite}() = Composite{Leaf,Composite}(Leaf(),Vector{Union{Leaf,Composite}}([Leaf()]))
Composite{Leaf,Leaf}() = Composite{Leaf,Leaf}(Leaf(),Vector{Union{Leaf,Leaf}}([Leaf()]))

tested on a julia version version 1.7.2.

could someone confirm this behavior ?

2

Not yet confirmed on versioninfo()

Julia Version 1.9.0-DEV.81
Commit 8ae9dd5c5b (2022-02-24 19:13 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 12 Ă— Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-13.0.1 (ORCJIT, skylake)
  Threads: 5 on 12 virtual cores
Environment:
  JULIA_EDITOR = code
  JULIA_NUM_THREADS = 5
3

I am on a Debian 11

Julia Version 1.7.2
Commit bf53498635 (2022-02-06 15:21 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, skylake)
4

Confirmed on

Julia Version 1.7.2
Commit bf53498635 (2022-02-06 15:21 UTC)        
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
  WORD_SIZE: 64    
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, skylake)
Environment:
  JULIA_EDITOR = code
  JULIA_NUM_THREADS = 5

This is probably worth an issue.

Edit: on second thought, it could be a Graphs issue, but nevertheless the compiler accepts the code in newer versions…

5

It’s not a Graphs issue. Graphs is not used at all in this example. It is just loaded. I also tried the same with other packages like JuMP instead of Graphs and the behavior is the same.

Which versions do you mean?

6

Development versions

7

Glad to also confirm that it works in the nightly build. So I assumed that whatever the error is, it is already fixed for the future julia versions.

8

Issue filed.