Julia: Unreachable reached at 0000000015349AF1

[mohamed82008]

I was running the following code, when Julia crashed and I got the following error:

julia> struct FunctorArgTrait{T<:Tuple} end

julia> struct FunctorRetTrait{S} end

julia> f(x, y) =  x+y
f (generic function with 1 method)

julia> get_ret_trait(::Type{typeof(f)}, input_types::Type{<:Tuple}) = FunctorRetTrait{promote_type(input_types.parameters...)}()
get_ret_trait (generic function with 1 method)

julia> get_arg_trait(::Type{typeof(f)}) = FunctorArgTrait{Tuple{Any,Any}}()
get_arg_trait (generic function with 1 method)

julia> g(f::F, x, y) where {F<:Function, T1, T2} = g(f, x, y, get_arg_trait(F), get_ret_trait(F, Tuple{Int,Int}))
g (generic function with 1 method)

julia> g(f::F, x, y, ::FunctorArgTrait{Tuple{>:Int, >:Int}}, ::FunctorRetTrait{S}) where {F<:Function, S<:Int} = f(x,y)::S
g (generic function with 2 methods)

julia> g(f, 1, 2)

Unreachable reached at 0000000015349AF1

Please submit a bug report with steps to reproduce this fault, and any error messages that follow (in their entirety). Thanks.
Exception: EXCEPTION_ILLEGAL_INSTRUCTION at 0x15349af1 -- g at .\REPL[8]:1
in expression starting at no file:0
g at .\REPL[8]:1
jl_call_fptr_internal at /home/Administrator/buildbot/worker/package_win64/build/src\julia_internal.h:384 [inlined]
jl_call_method_internal at /home/Administrator/buildbot/worker/package_win64/build/src\julia_internal.h:399 [inlined]
jl_apply_generic at /home/Administrator/buildbot/worker/package_win64/build/src\gf.c:2082
do_call at /home/Administrator/buildbot/worker/package_win64/build/src\interpreter.c:323
eval_value at /home/Administrator/buildbot/worker/package_win64/build/src\interpreter.c:395
eval_body at /home/Administrator/buildbot/worker/package_win64/build/src\interpreter.c:509
jl_interpret_toplevel_thunk_callback at /home/Administrator/buildbot/worker/package_win64/build/src\interpreter.c:720
unknown function (ip: FFFFFFFFFFFFFFFE)
unknown function (ip: 000000001161720F)
unknown function (ip: FFFFFFFFFFFFFFFF)
jl_toplevel_eval_flex at /home/Administrator/buildbot/worker/package_win64/build/src\toplevel.c:798
jl_toplevel_eval_in at /home/Administrator/buildbot/worker/package_win64/build/src\builtins.c:626
eval at .\boot.jl:298 [inlined]
eval at .\repl\REPL.jl:3
jl_call_fptr_internal at /home/Administrator/buildbot/worker/package_win64/build/src\julia_internal.h:380 [inlined]
jl_call_method_internal at /home/Administrator/buildbot/worker/package_win64/build/src\julia_internal.h:399 [inlined]
jl_apply_generic at /home/Administrator/buildbot/worker/package_win64/build/src\gf.c:2082
eval_user_input at .\repl\REPL.jl:70
jl_call_fptr_internal at /home/Administrator/buildbot/worker/package_win64/build/src\julia_internal.h:380 [inlined]
jl_call_method_internal at /home/Administrator/buildbot/worker/package_win64/build/src\julia_internal.h:399 [inlined]
jl_apply_generic at /home/Administrator/buildbot/worker/package_win64/build/src\gf.c:2082
macro expansion at .\repl\REPL.jl:101 [inlined]
#1 at .\event.jl:92
jl_call_fptr_internal at /home/Administrator/buildbot/worker/package_win64/build/src\julia_internal.h:380 [inlined]
jl_call_method_internal at /home/Administrator/buildbot/worker/package_win64/build/src\julia_internal.h:399 [inlined]
jl_apply_generic at /home/Administrator/buildbot/worker/package_win64/build/src\gf.c:2082
jl_apply at /home/Administrator/buildbot/worker/package_win64/build/src\julia.h:1473 [inlined]
start_task at /home/Administrator/buildbot/worker/package_win64/build/src\task.c:268
Allocations: 2506350 (Pool: 2505097; Big: 1253); GC: 5

[garrison]

Thank you for the report. This resulted in a MethodError for me on julia 0.6.2. Is this error reproducible for you? What is the output of versioninfo()?

[mohamed82008]

Oh sorry, forgot to include that:

julia> versioninfo()
Julia Version 0.7.0-DEV.3234
Commit 2cc82d29e1* (2018-01-02 11:44 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Haswell)
  LAPACK: libopenblas64_
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, skylake)

[mohamed82008]

It is reproducible yes.

[mohamed82008]

Works fine when I take the >: Int in the first method of g to the where clause and remove T1 and T2 (typo) from the first method of g:

julia> struct FunctorArgTrait{T<:Tuple} end

julia>  struct FunctorRetTrait{S} end

julia>  f(x, y) =  x+y
f (generic function with 1 method)

julia>  get_ret_trait(::Type{typeof(f)}, input_types::Type{<:Tuple}) = FunctorRetTrait{promote_type(input_types.parameters...)}()
get_ret_trait (generic function with 1 method)

julia> get_arg_trait(::Type{typeof(f)}) = FunctorArgTrait{Tuple{Any,Any}}()
get_arg_trait (generic function with 1 method)

julia> g(f::F, x, y, ::FunctorArgTrait{Tuple{T1, T2}}, ::FunctorRetTrait{S}) where {F<:Function, S<:Int, T1 >: Int, T2 >: Int} = f(x,y)::S
g (generic function with 1 method)

julia> g(f::F, x, y) where {F<:Function} = g(f, x, y, get_arg_trait(F), get_ret_trait(F, Tuple{Int,Int}))
g (generic function with 2 methods)

julia>  g(f, 1, 2)
3

[martinholters]

AFAIK the two function signatures are different as
FunctorArgTrait{Tuple{>:Int, >:Int}} == FunctorArgTrait{Tuple{T1, T2} where {T1 >: Int, T2 >: Int}} != FunctorArgTrait{Tuple{T1, T2}} where {T1 >: Int, T2 >: Int}. So the OP example should give a method error as FunctorArgTrait{Tuple{Any,Any}} is not a subtype of the former. And indeed inference determined Union{} as the return type of f(g, 1, 2).

[martinholters]

There is something funny about dispatch/subtyping here. Reduced example:

julia> f(t::Vector{Tuple{>:Int}}) where T = @assert t isa Vector{Tuple{>:Int}}
f (generic function with 1 method)

julia> f(Vector{Tuple{Any}}())
ERROR: AssertionError: t isa Vector{Tuple{>:Int}}
Stacktrace:
 [1] f(::Array{Tuple{Any},1}) at ./REPL[1]:1
 [2] top-level scope

The assertion fails as

julia> Vector{Tuple{Any}}() isa Vector{Tuple{>:Int}}
false

while the method is dispatched to because

julia> typeof(Vector{Tuple{Any}}()) <: Vector{Tuple{>:Int}}
true

where the latter looks bogus to me.

[martinholters]

After some more thought, Tuple{>:Int} == (Tuple{T} where T>:Int64) == Union{Tuple{Int64},Tuple{Signed},Tuple{Integer},...,Tuple{Any}} == Tuple{Any}, and from Tuple{>:Int} == Tuple{Any} follows Vector{Tuple{Any}} == Vector{Tuple{>:Integer}}, but then the isa above looks wrong.

Also

julia> g(t::Vector{Tuple{>:Int}}) = @assert t isa Vector{Tuple{>:Int}} # no where {T} here
g (generic function with 1 method)

julia> g(Vector{Tuple{Any}}())
ERROR: MethodError: no method matching g(::Array{Tuple{Any},1})
Closest candidates are:
  g(::Array{Tuple{#s1} where #s1>:Int64,1}) at REPL[23]:1

then looks wrong.

[martinholters]

I think I've pinned down the problem here: The code in subtype.c assumes that concrete/leaf types are identical if they are type-equal. However, e.g. Vector{Tuple{>:Int}} and Vector{Tuple{Any}} violate this:

julia> T1, T2 = Vector{Tuple{>:Int}}, Vector{Tuple{Any}}
(Array{Tuple{#s1} where #s1>:Int64,1}, Array{Tuple{Any},1})

julia> T1 == T2
true

julia> T1 === T2
false

What trips off inference in the OPs example is that

julia> typeintersect(T1, T2)
Union{}

Simply removing the following lines resolves the problems reported in this issue:
https://github.com/JuliaLang/julia/blob/11dcd63b0fe874eefdcb07a66f05880d78b429ba/src/subtype.c#L209-L212
https://github.com/JuliaLang/julia/blob/11dcd63b0fe874eefdcb07a66f05880d78b429ba/src/subtype.c#L253-L258
https://github.com/JuliaLang/julia/blob/11dcd63b0fe874eefdcb07a66f05880d78b429ba/src/subtype.c#L1210-L1211

However, I'm a bit afraid that these constitute valuable fast paths and it would probably be beneficial to just limit them down a bit further instead of removing them altogether. I'm thinking of replacing the jl_is_leaf_type condition with something like is_simple_type which is true for leaf types that fulfill additional properties, e.g. should not contain Union or UnionAll anywhere. But I'm not sure

• which conditions would be sufficient
• whether it's really worth it
• whether to add a flag to the type that is filled when the type is constructed or to check the conditions on the fly.

The other option would be to ensure that leaf types are always normalized. I think this is what we've been trying to achieve. But I'm wondering whether that is achievable in general. As e.g. Vector{T} is always a leaf type (unless T contains unbound typevars), wouldn't that mean we would have to be able to normalize any type such that type-equality becomes identity?

Any insights to share, @JeffBezanson?

[JeffBezanson]

Excellent investigation, @martinholters ! The is_simple_type solution sounds worth trying at least.

[vtjnash]

wouldn't that mean we would have to be able to normalize any type such that type-equality becomes identity?

Yes, but we should definitely be able do that – there's a linear-scan cache in datatype instantiation for this purpose. (I've been trying to find an old commit where I had started working on this, but I'm pretty sure at this point that I've lost it and will need to recreate that).

[martinholters]

Ah, thanks for the pointer, @vtjnash! The problem here is that Vector{Tuple{Any}} is stored in the ordered cache, but Vector{Tuple{>:Int}} is only searched for in the linear cache. Should we have to put all types in the linear cache?

[martinholters]

I've tried this:

--- a/src/jltypes.c
+++ b/src/jltypes.c
@@ -725,6 +725,10 @@ static jl_value_t *lookup_type(jl_typename_t *tn, jl_value_t **key, size_t n)
     JL_TIMING(TYPE_CACHE_LOOKUP);
     int ord = is_typekey_ordered(key, n);
     ssize_t idx = lookup_type_idx(tn, key, n, ord);
+    if (ord && idx < 0) { // also search in linear cache
+        ord = !ord;
+        idx = lookup_type_idx(tn, key, n, ord);
+    }
     jl_value_t *t = (idx < 0) ? NULL : jl_svecref(ord ? tn->cache : tn->linearcache, idx);
     return t;
 }
@@ -802,6 +806,12 @@ jl_value_t *jl_cache_type_(jl_datatype_t *type)
             type = (jl_datatype_t*)jl_svecref(ord ? type->name->cache : type->name->linearcache, idx);
         else
             cache_insert_type((jl_value_t*)type, ~idx, ord);
+        if (ord) { // also store in linear cache
+            ssize_t idx = lookup_type_idx(type->name, jl_svec_data(type->parameters),
+                                          jl_svec_len(type->parameters), 0);
+            if (idx < 0)
+                cache_insert_type((jl_value_t*)type, ~idx, 0);
+       }
     }
     return (jl_value_t*)type;
 }

And it solves this issue. Yay! But... It may of course lead to unexpected normalization:

julia> Vector{Tuple{Any}}
Array{Tuple{#s2} where #s2>:Int64,1}

because it just so happened that I had instantiated the latter first. Also
https://github.com/JuliaLang/julia/blob/7d3991f7844adadab51c864e2f36c9bb9d3e06ee/test/core.jl#L172
results in a StackOverflowError. I had seen that before, though, when just disabling the fastpaths discussed above---maybe it is just accidentally working at the moment?

I tend to try the following:

• Leave the caches as they are.
• In the subtyping code, tighten the condition for assuming T1===T2 is equivalent to T1==T2. Instead of just checking that (at least) one of them is a leaf-type, if they are both leaf-types, they also have to belong to same cache (ordered/linear).

Does that sound reasonable?

[martinholters]

I'm a bit confused by the ordered cache. Shouldn't the entries be mutually type-unequal? Because:

julia> Vector{Vector{Tuple{Any}}} # this goes into the ordered cache
Array{Array{Tuple{Any},1},1}

julia> Vector{Vector{Tuple{>:Int}}} # this too - but should it?
Array{Array{Tuple{#s1} where #s1>:Int64,1},1}

julia> Vector.body.name.cache[203]
Array{Array{Tuple{Any},1},1}

julia> Vector.body.name.cache[204]
Array{Array{Tuple{#s1} where #s1>:Int64,1},1}

julia> Vector.body.name.cache[203] == Vector.body.name.cache[204]
true

Should is_typekey_ordered be stricter (probably by recursing)?