"Unreachable reached" caused by for loop during testing

[jcampolongo]

versions 1.5.3/1.5.2/1.5.1/Win10 & 1.5.3/OSX & 1.5.3/WSL(Ubuntu)

The following code (the full code is in the following comment) causes an "Unreachable reached" error under the above Julia versions.

@testset "DiscreteCPT operations" begin
    cpd = Dict((1,1) => [0.3, 0.7], (1,2) => [0.6, 0.4], (2,1) => [0.4, 0.6], (2,2) => [0.7, 0.3], (3,1) => [0.5, 0.5], (3,2) => [0.8, 0.2])
    x = DiscreteCPT([1,2], cpd)

    @testset "expected_stats " begin
        parpi1 = [0.2, 0.3, 0.5]
        parpi2 = [0.9, 0.1]
        lam = [0.1, 0.4]
        
        expected_stats(x, [1,2], [[1,2,3], [1,2]], [parpi1, parpi2], lam)
        
        # [k for k in 1:10]
        for k in 1:10
        end
        @test true
    end
end

If the for k in 1:10 is removed, the code does not crash. If for k in 1:10 is replaced with [k for k in 1:10], the code does not crash. If the outer or inner @testset is removed, the code does not crash. If julia is run with the --compiler=no flag, it does not crash.

The error is, under WSL,

Unreachable reached at 0x7f7f08871638

signal (4): Illegal instruction
in expression starting at /mnt/c/Users/jcampolongo/test/test_exception.jl:178
macro expansion at /mnt/c/Users/jcampolongo/test/test_exception.jl:187 [inlined]
macro expansion at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.5/Test/src/Test.jl:1115 [inlined]
macro expansion at /mnt/c/Users/jcampolongo/test/test_exception.jl:183 [inlined]
macro expansion at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.5/Test/src/Test.jl:1115 [inlined]
top-level scope at /mnt/c/Users/jcampolongo/test/test_exception.jl:179
jl_toplevel_eval_flex at /buildworker/worker/package_linux64/build/src/toplevel.c:834
jl_parse_eval_all at /buildworker/worker/package_linux64/build/src/ast.c:913
jl_load_rewrite at /buildworker/worker/package_linux64/build/src/toplevel.c:914
include at ./client.jl:457
_jl_invoke at /buildworker/worker/package_linux64/build/src/gf.c:2231 [inlined]
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2398
jl_apply at /buildworker/worker/package_linux64/build/src/julia.h:1690 [inlined]
do_call at /buildworker/worker/package_linux64/build/src/interpreter.c:117
eval_value at /buildworker/worker/package_linux64/build/src/interpreter.c:206
eval_stmt_value at /buildworker/worker/package_linux64/build/src/interpreter.c:157 [inlined]
eval_body at /buildworker/worker/package_linux64/build/src/interpreter.c:566
jl_interpret_toplevel_thunk at /buildworker/worker/package_linux64/build/src/interpreter.c:660
jl_toplevel_eval_flex at /buildworker/worker/package_linux64/build/src/toplevel.c:840
jl_toplevel_eval_flex at /buildworker/worker/package_linux64/build/src/toplevel.c:790
jl_toplevel_eval_in at /buildworker/worker/package_linux64/build/src/toplevel.c:883
eval at ./boot.jl:331
_jl_invoke at /buildworker/worker/package_linux64/build/src/gf.c:2214 [inlined]
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2398
eval_user_input at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.5/REPL/src/REPL.jl:134
repl_backend_loop at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.5/REPL/src/REPL.jl:195
start_repl_backend at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.5/REPL/src/REPL.jl:180
#run_repl#37 at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.5/REPL/src/REPL.jl:292
run_repl at /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.5/REPL/src/REPL.jl:288
_jl_invoke at /buildworker/worker/package_linux64/build/src/gf.c:2231 [inlined]
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2398
#806 at ./client.jl:399
jfptr_YY.806_52378.clone_1 at /home/jcampolongo/programs/julia/julia-1.5.0/lib/julia/sys.so (unknown line)
_jl_invoke at /buildworker/worker/package_linux64/build/src/gf.c:2214 [inlined]
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2398
jl_apply at /buildworker/worker/package_linux64/build/src/julia.h:1690 [inlined]
do_apply at /buildworker/worker/package_linux64/build/src/builtins.c:655
jl_f__apply_latest at /buildworker/worker/package_linux64/build/src/builtins.c:705
#invokelatest#1 at ./essentials.jl:710 [inlined]
invokelatest at ./essentials.jl:709 [inlined]
run_main_repl at ./client.jl:383
exec_options at ./client.jl:313
_start at ./client.jl:506
jfptr__start_43701.clone_1 at /home/jcampolongo/programs/julia/julia-1.5.0/lib/julia/sys.so (unknown line)
_jl_invoke at /buildworker/worker/package_linux64/build/src/gf.c:2214 [inlined]
jl_apply_generic at /buildworker/worker/package_linux64/build/src/gf.c:2398
unknown function (ip: 0x401931)
unknown function (ip: 0x401533)
__libc_start_main at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
unknown function (ip: 0x4015d4)
Allocations: 4234161 (Pool: 4233195; Big: 966); GC: 4
Illegal instruction (core dumped)

[jcampolongo]

I cannot attach the reproducible file, so I'm copying it into this comment.

using Test
using Base.Filesystem
using Random

cartesian_product(xs :: Tuple) = cartesian_product([x for x in xs])

# function cartesian_product(xs :: Array{Array{T, 1}, 1}) where T
function cartesian_product(xs :: Array)
    if isempty(xs)
        result = Array{Any, 1}[[]]
    else
        yss = cartesian_product(xs[2:length(xs)])
        result = Array{Any, 1}[]
        for x in xs[1]
            for ys in yss
                zs = copy(ys)
                pushfirst!(zs, x)
                push!(result, zs)
            end
        end
    end
    return result
end

abstract type ValueTyped{O} end

abstract type SFunc{I <: Tuple, O, P} <: ValueTyped{O} end

abstract type Conditional{I <: Tuple, J <: Tuple, K <: Tuple, O, P, Q, S <: SFunc{J, O, Q}} <: SFunc{K, O, P}
end

get_params(c::Conditional) = c.params

set_params!(c::Conditional, pms) = c.params = pms

abstract type ParamGen{I <: Tuple, J <: Tuple, K <: Tuple, O, P, Q, S <: SFunc{J, O, Q}} <: Conditional{I,J,K,O,P,Q,S}
end

function extend_tuple_type(T1, T2)
    n1 = length(fieldnames(T1))
    n2 = length(fieldnames(T2))
    ts = []
    for i = 1:n1
        push!(ts, fieldtype(T1, i))
    end
    for i = 1:n2
        push!(ts, fieldtype(T2, i))
    end
    return Tuple{ts...}
end

function gensf(p::ParamGen{I,J,K,O,P,Q,S}, i::I)::S where {I <: Tuple, J, K, O, P, Q, S}
    set_params!(p.sf, setq(p, i))
    return p.sf
end

mutable struct Table{NumInputs, I <: NTuple{NumInputs, Any}, J, K, O, Q, S <: SFunc{J,O,Q}} <: ParamGen{I, J, K, O, Array{Q,NumInputs}, Q, S} 
    icombos :: Vector{I}
    iranges :: NTuple{NumInputs, Array{Any, 1}}
    isizes :: NTuple{NumInputs, Int}
    imults :: NTuple{NumInputs, Int}
    inversemaps :: NTuple{NumInputs, Dict{Any, Int}}
    params :: Array{Q, NumInputs}
    sf :: S
    default :: Q # used for estimating parameters when no data available; 
                 # these are the parameters of the sf with which the table is created
    function Table(NumInputs::Int, paramdict, sf::S) where {J,O,Q, S <: SFunc{J,O,Q}}
        k1 = collect(keys(paramdict))[1]
        I = typeof(k1)
        @assert NumInputs == length(k1)
        K = extend_tuple_type(I,J)
        default = sf.params
        icombos = keys(paramdict)
        iranges :: Array{Array{Any,1}} = [unique(collect([combo[k] for combo in icombos])) for k in 1:NumInputs]
        isizes = tuple([length(irange) for irange in iranges]...)
        m = 1
        ims = zeros(Int, NumInputs)
        for k in NumInputs:-1:1
            ims[k] = m
            m *= isizes[k]
        end
        imults = tuple(ims...)
        # TODO: Fix ordering of Dict
        inversemaps = tuple([Dict([x => i for (i,x) in enumerate(irange)]) for irange in iranges]...)
        sortedcombos = [tuple(p...) for p in cartesian_product(iranges)]   
        params = Array{Q, NumInputs}(undef, isizes)
        for k in 1:length(sortedcombos)
            is = sortedcombos[k]
            params[k] = get(paramdict, is, default) # The input dict does not have to have all combos
        end
        new{NumInputs, I, J, K, O, Q, S}(sortedcombos, tuple(iranges...), isizes, imults, inversemaps, params, sf, default)
    end
end

abstract type Unconditional{T,P} <: SFunc{Tuple{}, T, P} end

function get_params(u::Unconditional{T,P}) :: P where {T,P} 
    return u.params
end

function set_params!(u::Unconditional{T,P}, ps::P) where {T,P}
    u.params = ps
end

mutable struct Cat{T} <: Unconditional{T, Vector{Float64}}
    range :: Vector{T}
    inversemap :: Dict{T, Int}
    params :: Vector{Float64}
    Cat(r::Vector{T}, ps::Vector{Float64}) where T = begin
        @assert length(r) == length(ps)
        inversemap = Dict([x => i for (i,x) in enumerate(r)]) 
        new{T}(r,inversemap,ps)
    end
    Cat(rps::Vector{Pair{T,Float64}}) where T = begin
        range = first.(rps)
        probs = last.(rps)
        inversemap = Dict([x => i for (i,x) in enumerate(range)]) 
        new{T}(range, inversemap, probs)
    end
end

function setq(t::Table{N,I,J,K,O,Q,S}, i::NTuple{N,Any}) where {N,I,J,K,O,Q,S}
    inds = tuple([t.inversemaps[k][i[k]] for k in 1:length(i)]...)
    i = 1
    for k in 1:N
        i += (inds[k] - 1) * t.imults[k]
    end
    return t.params[i]
end

function split_pars(::Conditional{I,J,K,O,P,Q,S}, pars) where {I,J,K,O,P,Q,S}
    n1 = length(fieldnames(I))
    if n1 == 0
        return (tuple(), pars)
    elseif n1 == 1
        is = [pars[1]]
    else
        is = pars[1:n1]
    end
    js = pars[n1+1:length(pars)]
    return (tuple(is...), tuple(js...))
end

function expected_stats(c::Cat, range, child_λ) 
    ps = [c.range[i] in range ? c.params[i] : 0.0 for i in 1:length(c.range)]
    return ps .* child_λ
end


expected_stats(u::Unconditional, range, parranges, incoming_πs, child_λ) =
    expected_stats(u, range, child_λ)


function expected_stats(pg::ParamGen, range, parranges, parent_πs, child_λ) 
    (iranges, jranges) = split_pars(pg, parranges)
    iinds = cartesian_product(collect(map(r -> collect(1:length(r)), iranges)))
    (ipis, jpis) = split_pars(pg, parent_πs)
    result = Dict()
    for iind in iinds
        ival = [iranges[r][iind[r]] for r in 1:length(iranges)]
        sf = gensf(pg, tuple(ival...))
        ipi = reduce(*, (ipis[r][iind[r]] for r in 1:length(iranges)))
        innerstat = expected_stats(sf, range, jranges, jpis, child_λ)
        result[tuple(ival...)] = [x*y for (x,y) in zip(innerstat,ipi)]
    end
    return result
end

# A DiscreteCPT is a Table in which the embedded SFunc is a Cat.
function DiscreteCPT(range::Vector{O}, paramdict::Dict{I, Vector{Float64}}) where {I <: Tuple, O}
    sf = Cat(range, ones(length(range)))
    NumInputs = length(collect(keys(paramdict))[1])
    return Table(NumInputs, paramdict, sf)
end



@testset "DiscreteCPT operations" begin
    cpd = Dict((1,1) => [0.3, 0.7], (1,2) => [0.6, 0.4], (2,1) => [0.4, 0.6], (2,2) => [0.7, 0.3], (3,1) => [0.5, 0.5], (3,2) => [0.8, 0.2])
    x = DiscreteCPT([1,2], cpd)

    @testset "expected_stats " begin
        parpi1 = [0.2, 0.3, 0.5]
        parpi2 = [0.9, 0.1]
        lam = [0.1, 0.4]
        
        expected_stats(x, [1,2], [[1,2,3], [1,2]], [parpi1, parpi2], lam)
        
        # [k for k in 1:10]
        for k in 1:10
        end
        @test true
    end
end

[JeffBezanson]

Thanks for the test case. Still happens on 1.6. I already have a clue/workaround, which is to change the constraint I <: NTuple{NumInputs, Any} to I <: Tuple.

[maleadt]

Reduced it a little further:

macro a(ae)
    af = ae
    quote
        try
            $af
        catch
        end
    end
end
abstract type c{e,d,g<:Tuple,f,i,h,l} end
function j(n, m)
    p = []
    Tuple{p...}
end
struct q{o,e<:NTuple{o},d,g,b,h,l} <: c{e,0,g,0,Array{o},0,0}
    function q(o, aa, :)
        r = collect(keys(aa))[]
        e = typeof(r)
        g = j(0, 0)
        new{o,e,0,g,0,0,0}()
    end
end
function s(::c, b, d, π, λ) end
function t(b, aa)
    o = length(collect(aa)[])
    q(o, aa, 0)
end
@a begin
    ad = Dict((0, 0) => 0)
    u = t([], ad)
    s(u, [], [], [], 0)
    for k in 0
    end
end

How can i send bug to Julia. Any Email? Actually I found the logical error vulnerability in Julian language. Tell me how can i contact with you?

[StefanKarpinski]

If you have found a security vulnerability, you can privately send information about it to security@julialang.org. If you have found some other kind of issue, you can open a new GitHub issue or ask questions on discourse.

[NHDaly]

+1 I think we've seen an error similar to this as well. For us, the stacktrace came from Generator, in case that's helpful:

      From worker 2:    Unreachable reached at 0x7fffca9b6d73
      From worker 2:    
      From worker 2:    signal (4): Illegal instruction
      From worker 2:    in expression starting at /tmp/nix-build-delve-packages.drv-0/delve-source/packages/Serde/test/model.jl:544
      From worker 2:    Generator at ./generator.jl:32 [inlined]
      From worker 2:    Generator at ./generator.jl:32 [inlined]
      From worker 2:    _deserialize_vector at /tmp/nix-build-delve-packages.drv-0/delve-source/packages/Serde/src/Serde.jl:480
          [...]

[mharradon]

I have reduced this example significantly:

abstract type c{e,g<:Tuple,i} end
struct q{o,e<:NTuple{o},g} <: c{e,g,Array{o}}
    function q(oo, :)
        aa = Dict(nothing=>nothing)
        new{oo,
            Tuple{Int64},
            Tuple{[]...}}()
    end
end
s(::c) = nothing
fault() = s(q(1, Dict()))
fault()

I get Illegal Instruction from this on my Mac with Julia 1.6.0:

signal (4): Illegal instruction: 4
in expression starting at /Users/mharradon/tmp/illegal.jl:12
fault at /Users/mharradon/tmp/illegal.jl:11
unknown function (ip: 0x15acd92ec)
jl_apply_generic at /Users/mharradon/Applications/Julia-1.6.app/Contents/Resources/julia/lib/julia/libjulia-internal.1.dylib (unknown line)
do_call at /Users/mharradon/Applications/Julia-1.6.app/Contents/Resources/julia/lib/julia/libjulia-internal.1.dylib (unknown line)
eval_body at /Users/mharradon/Applications/Julia-1.6.app/Contents/Resources/julia/lib/julia/libjulia-internal.1.dylib (unknown line)
jl_interpret_toplevel_thunk at /Users/mharradon/Applications/Julia-1.6.app/Contents/Resources/julia/lib/julia/libjulia-internal.1.dylib (unknown line)
jl_toplevel_eval_flex at /Users/mharradon/Applications/Julia-1.6.app/Contents/Resources/julia/lib/julia/libjulia-internal.1.dylib (unknown line)
jl_toplevel_eval_flex at /Users/mharradon/Applications/Julia-1.6.app/Contents/Resources/julia/lib/julia/libjulia-internal.1.dylib (unknown line)
jl_toplevel_eval_in at /Users/mharradon/Applications/Julia-1.6.app/Contents/Resources/julia/lib/julia/libjulia-internal.1.dylib (unknown line)
eval at ./boot.jl:360 [inlined]
include_string at ./loading.jl:1094
jl_apply_generic at /Users/mharradon/Applications/Julia-1.6.app/Contents/Resources/julia/lib/julia/libjulia-internal.1.dylib (unknown line)
_include at ./loading.jl:1148
include at ./Base.jl:386
jl_apply_generic at /Users/mharradon/Applications/Julia-1.6.app/Contents/Resources/julia/lib/julia/libjulia-internal.1.dylib (unknown line)
exec_options at ./client.jl:285
_start at ./client.jl:485
jfptr__start_32776.clone_1 at /Users/mharradon/Applications/Julia-1.6.app/Contents/Resources/julia/lib/julia/sys.dylib (unknown line)
jl_apply_generic at /Users/mharradon/Applications/Julia-1.6.app/Contents/Resources/julia/lib/julia/libjulia-internal.1.dylib (unknown line)
true_main at /Users/mharradon/Applications/Julia-1.6.app/Contents/Resources/julia/lib/julia/libjulia-internal.1.dylib (unknown line)
repl_entrypoint at /Users/mharradon/Applications/Julia-1.6.app/Contents/Resources/julia/lib/julia/libjulia-internal.1.dylib (unknown line)
Allocations: 2650 (Pool: 2641; Big: 9); GC: 0
[1]    59915 illegal hardware instruction  julia illegal.jl

Also confirmed on Julia 1.6.3

[vtjnash]

That is rather interesting to look at the specific failure (from Cthulhu.descend):

julia> typeintersect(q{<:Any, Tuple{Int}}, c)
Union{}

julia> typeintersect(q{1, Tuple{Int}}, c)
q{1, Tuple{Int64}, g} where g<:Tuple

julia> typeintersect(q{<:Any, Tuple{Int}, Tuple}, c)
q{_A, Tuple{Int}, Tuple} where _A

Possibly the same as #39098?

[mharradon]

It's worth noting that even nonsense changes to this code resolve the segfault. E.g. dropping the aa = line (which should do nothing) results in code that runs without exception. For that reason I haven't been able to simplify further even with significant effort.

Looking at the IR as I change the code indicates this does result in significant compilation changes, so it appears there's some specific code generation / optimization paths that must be followed to trigger the segfault.