incorrect type intersection in tuples of types

[schlichtanders]

Dear Core Team,

I was motivated to raise a Bug report by the small discourse discussion about the same Unreachable Reached.

I can share reproducible piece of code, but please bear with me that it reproduces my current development setup and is not minified yet (I expect it to be quite hard to minify it actually). Still, at least you can trigger it now yourself:

using Pkg
pkg"registry add https://github.com/JuliaRegistries/General"
pkg"registry add https://github.com/schlichtanders/SchlichtandersJuliaRegistry.jl"
pkg"add Traits#unreachable_reached_2020_05_01"

using Traits

@traits f1(a::Vector) where {!isempty(a)} = a[1]
# the second call will trigger Unreachable Reached,
# actually you can switch both lines, and it is still the second call
@traits f2(a::Vector{A}) where {A, Base.isconcretetype(A)} = length(a)

The second @traits line will trigger the Unreachable Reached. You can also execute f2 before f1, and then, surprisingly, f1 will trigger the Unreachable Reached. This indicates that some state-keeping is not working correctly within Julia.

Good thing is that this way one can actually inspect both macros using macroexpand.

@traits itself also has a state, however each function has its own state (at least this is the intention, I am not yet 100% sure that it currently is still the case, as this hit me in the middle of some refactoring). So my best guess is that it is some julia internal state-keeping.

Here the unreachable reached error:

Unreachable reached at 0x1169e89d5

signal (4): Illegal instruction: 4
in expression starting at REPL[3]:1
Type##kw at ./util.jl:753
normalize_func at /Users/s.sahm/.julia/packages/Traits/Ft0sy/src/Syntax/Parsing.jl:203
#parse_traitsfunction#2 at /Users/s.sahm/.julia/packages/Traits/Ft0sy/src/Syntax/Parsing.jl:106
parse_traitsfunction at /Users/s.sahm/.julia/packages/Traits/Ft0sy/src/Syntax/Parsing.jl:16 [inlined]
_traits_parsed at /Users/s.sahm/.julia/packages/Traits/Ft0sy/src/Syntax/Syntax.jl:38
_traits at /Users/s.sahm/.julia/packages/Traits/Ft0sy/src/Syntax/Syntax.jl:32
@traits at /Users/s.sahm/.julia/packages/Traits/Ft0sy/src/Syntax/Syntax.jl:22
jl_invoke_julia_macro at /Users/julia/buildbot/worker/package_macos64/build/src/ast.c:1039
jl_expand_macros at /Users/julia/buildbot/worker/package_macos64/build/src/ast.c:1101
jl_expand_with_loc at /Users/julia/buildbot/worker/package_macos64/build/src/ast.c:1179
jl_toplevel_eval_flex at /Users/julia/buildbot/worker/package_macos64/build/src/toplevel.c:634
jl_toplevel_eval_flex at /Users/julia/buildbot/worker/package_macos64/build/src/toplevel.c:764
jl_toplevel_eval at /Users/julia/buildbot/worker/package_macos64/build/src/toplevel.c:823 [inlined]
jl_toplevel_eval_in at /Users/julia/buildbot/worker/package_macos64/build/src/toplevel.c:843
eval at ./boot.jl:331
eval_user_input at /Users/julia/buildbot/worker/package_macos64/build/usr/share/julia/stdlib/v1.4/REPL/src/REPL.jl:86
macro expansion at /Users/julia/buildbot/worker/package_macos64/build/usr/share/julia/stdlib/v1.4/REPL/src/REPL.jl:118 [inlined]
#26 at ./task.jl:358
jl_apply at /Users/julia/buildbot/worker/package_macos64/build/src/./julia.h:1700 [inlined]
start_task at /Users/julia/buildbot/worker/package_macos64/build/src/task.c:687
Allocations: 21909506 (Pool: 21906518; Big: 2988); GC: 25

julia> versioninfo()
Julia Version 1.4.1
Commit 381693d3df* (2020-04-14 17:20 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin18.7.0)
  CPU: Intel(R) Core(TM) i9-9980HK CPU @ 2.40GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-8.0.1 (ORCJIT, skylake)

I hope this can already enable some others to help inspecting the issue further.
With best wishes

[maleadt]

julia> pkg"add Traits#unreachable_reached_2020_05_01"
    Cloning git-repo `https://github.com/schlichtanders/Traits.jl/`
   Updating git-repo `https://github.com/schlichtanders/Traits.jl/`
   Updating registry at `~/Julia/tools/creduce/depot/registries/General`
   Updating git-repo `https://github.com/JuliaRegistries/General`
   Updating registry at `~/Julia/tools/creduce/depot/registries/SchlichtandersJuliaRegistry`
   Updating git-repo `https://github.com/schlichtanders/SchlichtandersJuliaRegistry.jl`
  Resolving package versions...
  Installed Requires ───────── v1.0.1
  Installed ConstructionBase ─ v1.0.0
  Installed Suppressor ─────── v0.2.0
  Installed MacroTools ─────── v0.5.5
  Installed Setfield ───────── v0.6.0
    Cloning [83eed652-29e8-11e9-12da-a7c29d64ffc9] DataTypesBasic from https://github.com/schlichtanders/DataTypesBasic.jl
   Updating git-repo `https://github.com/schlichtanders/DataTypesBasic.jl`
ERROR: DataTypesBasic: git object 9b34765f66b3b93240fed1f80afb476afc61dea5 could not be found

[schlichtanders]

thank you @maleadt for trying it out
it worked for me on a fresh Julia 1.4.1 installation...

I pushed now DataTypesBasic - there have been some local changes which are now upstream too.
I hope that solves the ERROR

[schlichtanders]

I successfully minimized the example, now it no longer includes any of my packages and is only about 10 lines long. :)

Happy inspecting!

Base.@kwdef struct UnreachableReached{T}
    type::Type{T}
end

type1 = Tuple{Array{T1,1} where T1}
UnreachableReached{type1}(type = type1)

type2 = Tuple{Array{T2,1}} where T2
UnreachableReached{type2}(type = type2)

again, you can actually reverse the order of type2 and type1 and the error will still be thrown at the very end, indicating that some internal state is not handled correctly.

The unreachable is reached for both Julia 1.4.1 and Julia 1.3.1 for me

Unreachable reached at 0x11c462ada

signal (4): Illegal instruction: 4
in expression starting at REPL[5]:1
Type##kw at ./util.jl:753
jl_apply at /Users/julia/buildbot/worker/package_macos64/build/src/./julia.h:1700 [inlined]
do_call at /Users/julia/buildbot/worker/package_macos64/build/src/interpreter.c:369
eval_body at /Users/julia/buildbot/worker/package_macos64/build/src/interpreter.c:0
jl_interpret_toplevel_thunk at /Users/julia/buildbot/worker/package_macos64/build/src/interpreter.c:911
jl_toplevel_eval_flex at /Users/julia/buildbot/worker/package_macos64/build/src/toplevel.c:814
jl_toplevel_eval_flex at /Users/julia/buildbot/worker/package_macos64/build/src/toplevel.c:764
jl_toplevel_eval at /Users/julia/buildbot/worker/package_macos64/build/src/toplevel.c:823 [inlined]
jl_toplevel_eval_in at /Users/julia/buildbot/worker/package_macos64/build/src/toplevel.c:843
eval at ./boot.jl:331
eval_user_input at /Users/julia/buildbot/worker/package_macos64/build/usr/share/julia/stdlib/v1.4/REPL/src/REPL.jl:86
macro expansion at /Users/julia/buildbot/worker/package_macos64/build/usr/share/julia/stdlib/v1.4/REPL/src/REPL.jl:118 [inlined]
#26 at ./task.jl:358
jl_apply at /Users/julia/buildbot/worker/package_macos64/build/src/./julia.h:1700 [inlined]
start_task at /Users/julia/buildbot/worker/package_macos64/build/src/task.c:687
Allocations: 950101 (Pool: 949867; Big: 234); GC: 1

---

Actually this also indicated a workaround - instead of using keyword arguments, you can use positional arguments and it will just work.

[JeffBezanson]

Thanks for reducing, that's very helpful. Looks like another relative of #35130.

[martinholters]

Interestingly, normalization does work in this case:

julia> UnreachableReached{type1}
UnreachableReached{Tuple{Array{T1,1} where T1}}

julia> UnreachableReached{type2}
UnreachableReached{Tuple{Array{T1,1} where T1}}

From what it is not surprising that when changing the second constructor call to UnreachableReached{type1}(type = type2) it crashes all the same. In fact, it's not even necessary to call the first constructor, just to construct the type itself. It follows a slight further reduction:

Base.@kwdef struct UnreachableReached{T}
    type::Type{T}
end

type1 = Tuple{Array{T1,1} where T1}
type2 = Tuple{Array{T2,1}} where T2

UnreachableReached{type1}(type = type2)

So let's look at

julia> @code_typed UnreachableReached{type1}(type = type2)
CodeInfo(
1 ── %1 = Base.getfield(@_2, :type)::UnionAll
│    %2 = Base.sle_int(1, 1)::Bool
└───      goto #3 if not %2
2 ── %4 = Base.sle_int(1, 0)::Bool
└───      goto #4
3 ──      nothing::Nothing
4 ┄─ %7 = φ (#2 => %4, #3 => false)::Bool
└───      goto #6 if not %7
5 ──      invoke Base.getindex(()::Tuple, 1::Int64)::Union{}
└───      $(Expr(:unreachable))::Union{}
6 ┄─      goto #7
7 ──      goto #8
8 ──      goto #9
9 ──      goto #10
10 ─      nothing::Nothing
│         invoke Main.:(var"#_#1")(%1::Type{T} where T, _3::Type{UnreachableReached{Tuple{Array{T1,1} where T1}}})::Union{}
└───      $(Expr(:unreachable))::Union{}
) => Union{}

Hm, why does the invoke in block 10 give Union{}? Let's see:

julia> code_typed(var"#_#1", Tuple{Type{T} where T, Type{UnreachableReached{Tuple{Array{T1,1} where T1}}}})
1-element Array{Any,1}:
 CodeInfo(
1 ─ %1 = invoke UnreachableReached{Tuple{Array{T1,1} where T1}}(_2::Type{T} where T)::UnreachableReached{Tuple{Array{T1,1} where T1}}
└──      return %1
) => UnreachableReached{Tuple{Array{T1,1} where T1}}

Um?

[martinholters]

Ah, I should have known better: The argument type is UnionAll, and indeed:

julia> code_typed(var"#_#1", Tuple{UnionAll, Type{UnreachableReached{Tuple{Array{T1,1} where T1}}}})
1-element Array{Any,1}:
 CodeInfo(
1 ─     invoke UnreachableReached{Tuple{Array{T1,1} where T1}}(_2::Type{T} where T)::Union{}
└──     $(Expr(:unreachable))::Union{}
) => Union{}

From there:

julia> code_typed(UnreachableReached{Tuple{Array{T1,1} where T1}}, Tuple{UnionAll})
1-element Array{Any,1}:
 CodeInfo(
1 ─ %1 = Core.fieldtype(UnreachableReached{Tuple{Array{T1,1} where T1}}, 1)::Type{Type{Tuple{Array{T1,1} where T1}}}
│        Base.convert(%1, type)::Union{}
└──      $(Expr(:unreachable))::Union{}
) => Union{}

Aha, it's the convert! That leads to a further reduction:

foo() = convert(Type{Tuple{Array{T1,1} where T1}}, UnionAll[Tuple{Array{T2,1}} where T2][1])
foo()

And we may note the following:

julia> methods(convert, Tuple{Type{Type{Tuple{Array{T,1} where T}}}, UnionAll})
# 0 methods for generic function "convert":

julia> methods(convert, Tuple{Type{Type{Tuple{Array{T,1} where T}}}, Type{Tuple{Array{T2,1}} where T2}})
# 1 method for generic function "convert":
[1] convert(::Type{T}, x::T) where T in Base at essentials.jl:171

julia> Type{Tuple{Array{T2,1}} where T2} <: UnionAll
true

So it boils down to this tircky type intersection problem:

julia> typeintersect(Tuple{Type{T}, T} where T, Tuple{Type{Type{Tuple{Array{T,1} where T}}}, UnionAll})
Union{}

Which shoud give Tuple{Type{Type{Tuple{Array{T,1} where T}}},Type{Tuple{Array{T2,1}} where T2}}.

[martinholters]

Or a simplified version of the type intersection problem:

julia> T = Type{Tuple{Array{T,1} where T}}
Type{Tuple{Array{T,1} where T}}

julia> typeintersect(T, UnionAll)
Union{}

julia> R = Type{Tuple{Array{T,1}} where T}
Type{Tuple{Array{T2,1}} where T2}

julia> R <: T && R <: UnionAll
true

[fingolfin]

Just to say, this crash is (unsurprisingly) still present in Julia 1.5.2 and 1.6.0-DEV.1399.

[ViralBShah]

Still present on 1.9-dev.