Julia: Unreachable reached

[alyst]

I hit "Unreachable reached" error with Julia 1.0.2 on Archlinux, then I tried backports-1.0.3 branch, assuming that #29986 will fix the problem, but it's still there.
Unfortunately, I don't have a small reproducible test case: it happens when I try to run the ]test BlackBoxOptim using pareto_rtree branch, which requires SpatialIndexing master (not yet in Julia registry).

Here's the log:

              _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.0.3-pre.29 (2018-11-19)
 _/ |\__'_|_|_|\__'_|  |  makepkg/33a5d6a2d9* (fork: 316 commits, 105 days)
|__/                   |

julia> versioninfo()
Julia Version 1.0.3-pre.29
Commit 33a5d6a2d9* (2018-11-19 15:19 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i7-7600U CPU @ 2.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.0 (ORCJIT, skylake)

(v1.0) pkg> test BlackBoxOptim
   Testing BlackBoxOptim
 Resolving package versions...
    Status `/tmp/tmpZWmfd8/Manifest.toml`
....

[ Info: subtract!(): region=BlackBoxOptim.DominanceCone{Int64,2,true}((22, 11))
[ Info: subtract!(): region=BlackBoxOptim.DominanceCone{Int64,2,true}((32, 11))
[ Info: _subtract!(): lev=0 i=0 len=1
[ Info: _subtract!(): delete subtree lev=0 i=0 len=1
[ Info: delete_subtree(): lev=0
[ Info: _delete_subtree(): empty children (1 objs) of node lev=0 parent=false
[ Info: _delete_subtree(): done node lev=0 parent=false
[ Info: _subtract!(): delete subtree done lev=0 i=0 len=0, returning 1
Unreachable reached at 0x7f8e4dabf335

signal (4): Illegal instruction
in expression starting at /home/ge68wan/.julia/dev/BlackBoxOptim/test/test_epsbox_archive.jl:1
subtract! at /home/ge68wan/.julia/dev/SpatialIndexing/src/rtree/delete.jl:65
add_candidate! at /home/ge68wan/.julia/dev/BlackBoxOptim/src/archives/epsbox_archive.jl:235
add_candidate! at /home/ge68wan/.julia/dev/BlackBoxOptim/src/archives/epsbox_archive.jl:262 [inlined]
add_candidate! at /home/ge68wan/.julia/dev/BlackBoxOptim/src/archives/epsbox_archive.jl:262
unknown function (ip: 0x7f8e4dad9d35)
jl_fptr_trampoline at /usr/bin/../lib/libjulia.so.1 (unknown line)
jl_apply_generic at /usr/bin/../lib/libjulia.so.1 (unknown line)
macro expansion at /home/ge68wan/.julia/dev/BlackBoxOptim/test/test_epsbox_archive.jl:50 [inlined]
macro expansion at /home/ge68wan/aur/julia-git/src/julia/usr/share/julia/stdlib/v1.0/Test/src/Test.jl:1083 [inlined]
macro expansion at /home/ge68wan/.julia/dev/BlackBoxOptim/test/test_epsbox_archive.jl:32 [inlined]
macro expansion at /home/ge68wan/aur/julia-git/src/julia/usr/share/julia/stdlib/v1.0/Test/src/Test.jl:1083 [inlined]
top-level scope at /home/ge68wan/.julia/dev/BlackBoxOptim/test/test_epsbox_archive.jl:4
jl_fptr_trampoline at /usr/bin/../lib/libjulia.so.1 (unknown line)
....

Here's the code in question:

function subtract!(tree::RTree{T,N}, reg::Region{T,N}) where {T,N}
    @info "subtract!(): region=$(reg)"
    isempty(tree) && return tree

    tmpdetached = Vector{nodetype(tree)}()
    status = _subtract!(tree.root, 0, reg, tree, tmpdetached)
    @info "_subtract!(root) done"
    @show status
    @show typeof(tmpdetached) length(tmpdetached)
    @info "subtract!(): status=$(status) tmpdetached=$(length(tmpdetached))"
    if status == 1 # tree changed, but not removed
        _condense!(tree.root, tree, tmpdetached) # try to condense the root
    elseif status == 2 # whole tree removed
        @assert isempty(tree)
        @assert isempty(tmpdetached)
    end
    _reinsert!(tree, tmpdetached)
    return tree
end

function _subtract!(node::Node, node_ix::Int, reg::Region, tree::RTree,
                    tmpdetached::AbstractVector{<:Node})
    nodembr = mbr(node)
    @info "_subtract!(): lev=$(level(node)) i=$node_ix len=$(length(node))"
    # FIXME juxtaposition() method that combines in() and intersects()?
    if in(nodembr, reg)
        @info "_subtract!(): delete subtree lev=$(level(node)) i=$node_ix len=$(length(node))"
        delete_subtree!(tree, node)
        @info "_subtract!(): delete subtree done lev=$(level(node)) i=$node_ix len=$(length(node)), returning 1"
        return 2 # node removed
    elseif intersects(nodembr, reg)
        mbr_dirty = false
        i = 1
        while i <= length(node)
            #@debug "1: lev=$(level(node)) i=$i len=$(length(node))"
            child = node[i]
            oldmbr = mbr(child)
            if node isa Branch
                child_res = _subtract!(child, i, reg, tree, tmpdetached)
            else
                @assert node isa Leaf
                if in(oldmbr, reg)
                    @info "_subtract!(): detach elem lev=$(level(node)) i=$i len=$(length(node))"
                    _detach!(node, i, tree, updatembr = false) # don't update MBR, we do it later
                    tree.nelems -= 1
                    tree.nelem_deletions += 1
                    child_res = 2
                    # FIXME intersect is not considered (would be important if elem mbr is not a point), should be handled by `filter`
                else
                    child_res = 0
                end
            end
            if !mbr_dirty && (child_res != 0) && tree.tight_mbrs
                mbr_dirty = touches(nodembr, oldmbr)
            end
            if child_res != 2 # don't increment if i-th node removed
                i += 1
            end
        end
        if hasparent(node) && length(node) < floor(Int, tree.reinsert_factor * capacity(node, tree))
            _detach!(parent(node), node_ix, tree)
            tree.nnodes_perlevel[level(node)+1] -= 1
            push!(tmpdetached, node)
            return 2 # node removed
        elseif mbr_dirty
            syncmbr!(node)
            return 1 # mbr changed
        else
            return 0 # no mbr change
        end
    else
        return 0 # no change
    end
end

It looks like the error happens immediately before/after _subtract!() returns to subtract!().

I think it's related to the concrete types of the RTree and Node, because this code runs fine in SpatialIndexing tests (nodetype(tree) = SpatialIndexing.Node{Float64,3,SpatialElem{Float64,3,Int64,String}}), but fails when (nodetype(tree) = SpatialIndexing.Node{Int64,2,BlackBoxOptim.FrontierIndividual{BlackBoxOptim.IndexedTupleFitness{2,Float64}}}).
Since it looks like it's type-related, I thought that it might be similar to #30067.

[Keno]

Looks like the _subtract! was inferred as not returning, but then returned anyway:

(SpatialIndexing._subtract!)(%154, 0, %148, %147, %153)::Union{}

in particular because of this:

julia> code_typed(SpatialIndexing._subtract!, AT)[1][2]
Union{}

julia> code_typed(SpatialIndexing._subtract!, TT)[1][2]
Int64

julia> TT <: AT
true

julia> TT
Tuple{SpatialIndexing.Leaf{Int64,2,FrontierIndividual{IndexedTupleFitness{2,Float64}}},Int64,DominanceCone{Int64,2,true},RTree{Int64,2,FrontierIndividual{IndexedTupleFitness{2,Float64}}},Array{Node{Int64,2,FrontierIndividual{IndexedTupleFitness{2,Float64}}},1}}

julia> AT
Tuple{Node{Int64,2,V} where V,Int64,DominanceCone{Int64,2,true},RTree{Int64,2,FrontierIndividual{IndexedTupleFitness{2,Float64}}},Array{Node{Int64,2,FrontierIndividual{IndexedTupleFitness{2,Float64}}},1}}

[Keno]

Reduced:

struct Foo{F,N}; end
f(a::Foo{F,N}, b::Tuple{Vararg{F,N}}) where {F,N} = nothing
Base._methods_by_ftype(Tuple{typeof(f), Foo{Int64,2}, NTuple}, 1, typemax(UInt))

gives zero matches, despite:

S = Tuple{typeof(f), Foo{Int64,2}, NTuple{2, Int64}}
@assert S <: Tuple{typeof(f), Foo{Int64,2}, NTuple}
length(Base._methods_by_ftype(S, 1, typemax(UInt))) # 1

[Keno]

Or even simpler:

struct Foo{F,N}; end
typeintersect(Tuple{Foo{Int64,2}, NTuple}, Tuple{Foo{F,N},Tuple{Vararg{F,N}}} where N where F)

is giving the wrong answer.

[alyst]

Thanks for the amazing work of tracking it down! I wonder whether it's possible to detect issues like that earlier (during type inference or compilation).

[Keno]

Not really, what you're seeing is already the result of extra code inserted to make these sorts of issues obvious. The compiler thought one thing was gonna happen, but another thing did.

[alyst]

I'm very sorry for pinging this issue: I know/see you are very busy improving various aspects of Julia.
It's just that I hoped the code in question would be working, and I can use it for my projects.
Is the issue something that could be easily fixed in the near future or I'd better devise a workaround?
I'm only asking because it was stated that compiler correctness has top priority.

[JeffBezanson]

I'm looking at it now. Ok to ping issues to gently remind us; thanks for your patience.