Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Unreachable reached at 0000000015349AF1 #25430

Closed
mohamed82008 opened this issue Jan 6, 2018 · 13 comments · Fixed by #25796
Closed

Unreachable reached at 0000000015349AF1 #25430

mohamed82008 opened this issue Jan 6, 2018 · 13 comments · Fixed by #25796
Labels
bug Indicates an unexpected problem or unintended behavior types and dispatch Types, subtyping and method dispatch

Comments

@mohamed82008
Copy link
Contributor

mohamed82008 commented Jan 6, 2018

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
Copy link
Member

garrison commented Jan 6, 2018

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
Copy link
Contributor Author

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
Copy link
Contributor Author

It is reproducible yes.

@mohamed82008
Copy link
Contributor Author

mohamed82008 commented Jan 6, 2018

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

@garrison garrison added the bug Indicates an unexpected problem or unintended behavior label Jan 6, 2018
@martinholters
Copy link
Member

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
Copy link
Member

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 martinholters added the types and dispatch Types, subtyping and method dispatch label Jan 12, 2018
@martinholters
Copy link
Member

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
Copy link
Member

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:

julia/src/subtype.c

Lines 209 to 212 in 11dcd63

if (jl_is_leaf_type(a) && !((jl_datatype_t*)a)->abstract)
return 1;
if (jl_is_leaf_type(b) && !((jl_datatype_t*)b)->abstract)
return 1;

julia/src/subtype.c

Lines 253 to 258 in 11dcd63

if (jl_is_leaf_type(a) && !((jl_datatype_t*)a)->abstract &&
jl_is_leaf_type(b) && !((jl_datatype_t*)b)->abstract &&
// TODO: remove these 2 lines if and when Tuple{Union{}} === Union{}
(((jl_datatype_t*)a)->name != jl_tuple_typename ||
((jl_datatype_t*)b)->name != jl_tuple_typename))
return 1;

julia/src/subtype.c

Lines 1210 to 1211 in 11dcd63

if (jl_is_leaf_type(t))
return 0;

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
Copy link
Member

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

@vtjnash
Copy link
Member

vtjnash commented Jan 25, 2018

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
Copy link
Member

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
Copy link
Member

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

struct T22624{A,B,C}; v::Vector{T22624{Int64,A}}; end

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
Copy link
Member

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)?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Indicates an unexpected problem or unintended behavior types and dispatch Types, subtyping and method dispatch
Projects
None yet
Development

Successfully merging a pull request may close this issue.

5 participants