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 #30122

Closed
alyst opened this issue Nov 22, 2018 · 7 comments
Closed

Unreachable reached #30122

alyst opened this issue Nov 22, 2018 · 7 comments
Assignees
Labels
bug Indicates an unexpected problem or unintended behavior types and dispatch Types, subtyping and method dispatch

Comments

@alyst
Copy link
Contributor

alyst commented Nov 22, 2018

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

Keno commented Nov 22, 2018

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

Keno commented Nov 22, 2018

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

Keno commented Nov 22, 2018

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.

@Keno Keno added bug Indicates an unexpected problem or unintended behavior types and dispatch Types, subtyping and method dispatch labels Nov 22, 2018
@alyst
Copy link
Contributor Author

alyst commented Nov 26, 2018

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

Keno commented Nov 26, 2018

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

alyst commented Dec 1, 2018

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

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

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

No branches or pull requests

3 participants