Unreachable reached and Illegal Instruction in v1.10+

[AntonReinhard]

I had a working implementation of a Trie structure in Julia 1.8 and 1.9 which broke with 1.10+. I have managed to reduce it to the following MWE:

abstract type AbstractT end
abstract type AT1 <: AbstractT end
abstract type AT2 <: AbstractT end
struct T1 <: AT1 end
struct T2 <: AT2 end

struct N1{TaskType <: AT1} end
struct N2{TaskType <: AT2} end

struct NodeIdTrie{NodeType} end

function insert_helper!(
    trie::NodeIdTrie{NodeType},
    node::NodeType,
) where {TaskType <: AbstractT, NodeType <: Union{N1{TaskType}, N2{TaskType}}}
    return nothing
end

function insert!(node::NodeType) where {TaskType <: AbstractT, NodeType <: Union{N1{TaskType}, N2{TaskType}}}
    children = Dict{DataType, NodeIdTrie}()
    children[NodeType] = NodeIdTrie{NodeType}()
    return insert_helper!(children[NodeType], node)
end

insert!(N1{T1}())

This works in version 1.6.7 and 1.9.4, but breaks in 1.10.3 and 1.11.0-beta1 (all installed via juliaup):

[132489] signal (4.2): Illegal instruction
in expression starting at /.../src/mwe_illegal.jl:25
insert! at /.../src/mwe_illegal.jl:22
unknown function (ip: 0x7beba9080262)
_jl_invoke at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/gf.c:2895 [inlined]
ijl_apply_generic at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/gf.c:3077
jl_apply at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/julia.h:1982 [inlined]
do_call at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/interpreter.c:126
eval_value at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/interpreter.c:223
eval_stmt_value at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/interpreter.c:174 [inlined]
eval_body at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/interpreter.c:617
jl_interpret_toplevel_thunk at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/interpreter.c:775
jl_toplevel_eval_flex at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/toplevel.c:934
jl_toplevel_eval_flex at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/toplevel.c:877
ijl_toplevel_eval_in at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/toplevel.c:985
eval at ./boot.jl:385 [inlined]
include_string at ./loading.jl:2076
_jl_invoke at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/gf.c:2895 [inlined]
ijl_apply_generic at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/gf.c:3077
_include at ./loading.jl:2136
include at ./Base.jl:495
jfptr_include_46394.1 at /home/user/.julia/juliaup/julia-1.10.3+0.x64.linux.gnu/lib/julia/sys.so (unknown line)
_jl_invoke at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/gf.c:2895 [inlined]
ijl_apply_generic at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/gf.c:3077
exec_options at ./client.jl:318
_start at ./client.jl:552
jfptr__start_82726.1 at /home/user/.julia/juliaup/julia-1.10.3+0.x64.linux.gnu/lib/julia/sys.so (unknown line)
_jl_invoke at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/gf.c:2895 [inlined]
ijl_apply_generic at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/gf.c:3077
jl_apply at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/julia.h:1982 [inlined]
true_main at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/jlapi.c:582
jl_repl_entrypoint at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/src/jlapi.c:731
main at /cache/build/builder-amdci4-2/julialang/julia-release-1-dot-10/cli/loader_exe.c:58
unknown function (ip: 0x7bebaa241d49)
__libc_start_main at /usr/lib/libc.so.6 (unknown line)
unknown function (ip: 0x4010b8)
Allocations: 2908 (Pool: 2898; Big: 10); GC: 0
fish: Job 1, 'julia --project=. src/mwe_illeg…' terminated by signal SIGILL (Illegal instruction)

Versioninfo:

julia> versioninfo()
Julia Version 1.10.3
Commit 0b4590a5507 (2024-04-30 10:59 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 24 × AMD Ryzen 9 7900X3D 12-Core Processor
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-15.0.7 (ORCJIT, znver3)
Threads: 1 default, 0 interactive, 1 GC (on 24 virtual cores)

The problem seems to be caused by some combination of the abstraction layer introduced by AT1 and AT2 (removing those removes the error), and the Union{} in line 15. Also, calling insert_helper! at line 22 directly on NodeIdTrie{NodeType}() also works. It also runs fine using the VSCode Julia Debugger.

[nsajko]

Reproduces on master.

[N5N3]

Type intersect MWE

julia> struct Val2{T <: Number} end

julia> S = Tuple{Val, Val{Nothing}}
Tuple{Val, Val{Nothing}}

julia> T = Tuple{Val{A}, A} where {B, A<:Union{Val{B}, Val2{B}}}
Tuple{Val{A}, A} where {B, A<:Union{Val{B}, Val2{B}}}

julia> typeintersect(S, T)
Union{}

The reason seems clear:
A's bounds is frozen as Val{Nothing} <: A <: Union{Val{B}, Val2{B}} before we finish the intersection of B (see #49591).
Our intersection algorithm is clever enough to prove B == Nothing, thus we would try to construct Val{Nothing} <: A <: Union{Val{Nothing}, Val2{Nothing}} and fail at Val2{Nothing}'s check.

[ViralBShah]

Should probably add a testcase.

[AntonReinhard]

Thanks a lot for the quick solution!