search

JuliaLang / julia

The Julia Programming Language
https://julialang.org/
MIT License
44.95k stars 5.42k forks source link

return type inference, given abstract argument type, takes a long, maybe unbounded, time #54886

Open nsajko opened 1 week ago

nsajko commented 1 week ago

Not a regression. Reproducer:

module HeterogeneousLists

module Internals

export Internal

struct Internal end

end

module TupleTail

export tuple_tail

function vararg_tail((@nospecialize ::Any), @nospecialize r...)
    r
end

function tuple_tail(@nospecialize t::Tuple{Any,Vararg})
    vararg_tail(t...)::Tuple
end

end

module TypeDomainNaturalNumbers

export NonnegativeInteger, PositiveInteger, natural_successor, natural_predecessor, natural_tuple_length

using ..Internals, ..TupleTail

abstract type AbstractNonnegativeInteger end

struct NonnegativeInteger{
    Predecessor<:Union{Nothing,AbstractNonnegativeInteger},
} <: AbstractNonnegativeInteger
    predecessor::Predecessor
    function NonnegativeInteger{P}(::Internal, p::P) where {P}
        new{P}(p)
    end
end

const PositiveInteger = let t = NonnegativeInteger
    t{<:t}
end::Type{<:NonnegativeInteger}

function natural_successor(o::NonnegativeInteger)
    NonnegativeInteger{typeof(o)}(Internal(), o)::PositiveInteger
end

function natural_predecessor(o::PositiveInteger)
    o.predecessor::NonnegativeInteger
end

function (::Type{NonnegativeInteger})()
    # canonical zero
    NonnegativeInteger{Nothing}(Internal(), nothing)
end

function Base.zero(::Type{NonnegativeInteger})
    NonnegativeInteger()
end

function to_int(@nospecialize o::NonnegativeInteger)
    if o isa PositiveInteger
        let p = natural_predecessor(o), t = @inline to_int(p)
            t::Int + 1
        end
    else
        0
    end::Int
end

function Base.convert(::Type{Int}, o::NonnegativeInteger)
    to_int(o)
end

function from_val(::Val{N}) where {N}
    Vararg{Any,N}
    if N === 0
        NonnegativeInteger()
    else
        let v = Val{N - 1}(), p = @inline from_val(v)
            natural_successor(p::NonnegativeInteger)
        end::PositiveInteger
    end::NonnegativeInteger
end

function from_int(n::Int)
    Vararg{Any,n}
    if n === 0
        NonnegativeInteger()
    else
        from_val(Val{n}())
    end::NonnegativeInteger
end

function Base.convert(::Type{NonnegativeInteger}, n::Int)
    from_int(n)
end

function natural_tuple_length(@nospecialize t::Tuple)
    if t === ()
        NonnegativeInteger()
    else
        let a = tuple_tail(t), b = @inline natural_tuple_length(a)
            natural_successor(b::NonnegativeInteger)
        end::PositiveInteger
    end::NonnegativeInteger
end

end

module TupleUtils

using ..TupleTail, ..TypeDomainNaturalNumbers

export tail_is_ntuple, single_from

function tuple_is_of_length((@nospecialize t::Tuple), @nospecialize l::NonnegativeInteger)
    length(t) == convert(Int, l)
end

function tail_is_ntuple((@nospecialize t::Tuple), @nospecialize l::NonnegativeInteger)
    if tuple_is_of_length(t, l)
        t isa NTuple
    else
        let s = tuple_tail(t)
            @inline tail_is_ntuple(s, l)
        end::Bool
    end
end

function single_from(t::Tuple, @nospecialize l::PositiveInteger)
    i = length(t) - convert(Int, l) + 1
    t[i]
end

end

using .TypeDomainNaturalNumbers, .TupleUtils

struct EmptyList end

abstract type AbstractNonemptyHomogeneousList{ElementType} end

struct HomogeneousListNonempty{
    ElementType,
    Linked<:Union{EmptyList,AbstractNonemptyHomogeneousList{ElementType}},
} <: AbstractNonemptyHomogeneousList{ElementType}
    value::ElementType
    linked::Linked
    function HomogeneousListNonempty{E,L}(e::E, l::L) where {
        E,
        L<:Union{EmptyList,HomogeneousListNonempty{E}},
    }
        new{E,L}(e, l)
    end
end

function HomogeneousListNonempty{E}(e::E, l::Union{EmptyList,HomogeneousListNonempty{E}}) where {E}
    HomogeneousListNonempty{E,typeof(l)}(e, l)
end

function HomogeneousListNonempty(e::E, l::Union{EmptyList,HomogeneousListNonempty{E}}) where {E}
    HomogeneousListNonempty{E}(e, l)
end

abstract type AbstractNonemptyHeterogeneousList end

struct HeterogeneousListNonemptyProper{
    ElementType,
    Linked<:Union{EmptyList,HomogeneousListNonempty,AbstractNonemptyHeterogeneousList},
} <: AbstractNonemptyHeterogeneousList
    value::ElementType
    linked::Linked
    function HeterogeneousListNonemptyProper{E,L}(e::E, l::L) where {
        E,
        L<:Union{EmptyList,HomogeneousListNonempty,HeterogeneousListNonemptyProper},
    }
        new{E,L}(e, l)
    end
end

function HeterogeneousListNonemptyProper{E}(e::E, l::Union{EmptyList,HomogeneousListNonempty,HeterogeneousListNonemptyProper}) where {E}
    HeterogeneousListNonemptyProper{E,typeof(l)}(e, l)
end

function HeterogeneousListNonemptyProper(e::E, l::Union{EmptyList,HomogeneousListNonempty,HeterogeneousListNonemptyProper}) where {E}
    HeterogeneousListNonemptyProper{E}(e, l)
end

const HeterogeneousListNonempty = Union{HomogeneousListNonempty,HeterogeneousListNonemptyProper}

const HeterogeneousList = Union{EmptyList,HeterogeneousListNonempty}

function from_tuple_view(t::Tuple, @nospecialize l::NonnegativeInteger)
    if l isa PositiveInteger
        let p = natural_predecessor(l),
            e = single_from(t, l),
            r = @inline from_tuple_view(t, p)
            if tail_is_ntuple(t, l)
                HomogeneousListNonempty(e, r)
            else
                HeterogeneousListNonemptyProper(e, r)
            end
        end::HeterogeneousListNonempty
    else
        EmptyList()
    end::HeterogeneousList
end

function from_tuple(t::Tuple)
    l = natural_tuple_length(t)
    from_tuple_view(t, l)
end

end

(v -> HeterogeneousLists.from_tuple(v[1]))(Tuple{Vararg{Int}}[()])

Output when interrupted:

julia> (v -> HeterogeneousLists.from_tuple(v[1]))(Tuple{Vararg{Int}}[()])
^CInternal error: during type inference of
var"#1"(Array{Tuple{Vararg{Int64}}, 1})
Encountered unexpected error in runtime:
InterruptException()
jl_gc_state_set at /cache/build/builder-amdci5-5/julialang/julia-master/src/julia_threads.h:345 [inlined]
maybe_collect at /cache/build/builder-amdci5-5/julialang/julia-master/src/julia_threads.h:340 [inlined]
jl_gc_pool_alloc_inner at /cache/build/builder-amdci5-5/julialang/julia-master/src/gc.c:1325
jl_gc_alloc_ at /cache/build/builder-amdci5-5/julialang/julia-master/src/julia_internal.h:509 [inlined]
ijl_new_typevar at /cache/build/builder-amdci5-5/julialang/julia-master/src/builtins.c:1652
jl_rename_unionall at /cache/build/builder-amdci5-5/julialang/julia-master/src/jltypes.c:1492
unalias_unionall at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:906
subtype_unionall at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:917
subtype at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:1423
exists_subtype at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:1651
_forall_exists_subtype at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:1682
local_forall_exists_subtype at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:1570
subtype_ccheck at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:656
var_gt at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:772
subtype at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:1377
exists_subtype at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:1651
_forall_exists_subtype at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:1682
local_forall_exists_subtype at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:1570
forall_exists_equal at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:1633
subtype at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:1466
subtype_unionall at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:925
subtype at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:1423
subtype_unionall at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:932
subtype at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:1420
exists_subtype at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:1651
_forall_exists_subtype at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:1682
forall_exists_subtype at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:1696 [inlined]
ijl_types_equal at /cache/build/builder-amdci5-5/julialang/julia-master/src/subtype.c:2254
inst_datatype_inner at /cache/build/builder-amdci5-5/julialang/julia-master/src/jltypes.c:2000
jl_apply_tuple_type_v_ at /cache/build/builder-amdci5-5/julialang/julia-master/src/jltypes.c:2299 [inlined]
ijl_apply_tuple_type_v at /cache/build/builder-amdci5-5/julialang/julia-master/src/jltypes.c:2309
_jl_invoke at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3081 [inlined]
ijl_apply_generic at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3258
jl_apply at /cache/build/builder-amdci5-5/julialang/julia-master/src/julia.h:2185 [inlined]
do_apply at /cache/build/builder-amdci5-5/julialang/julia-master/src/builtins.c:831
argtypes_to_type at ./compiler/typeutils.jl:57
abstract_call_known at ./compiler/abstractinterpretation.jl:2206
abstract_call at ./compiler/abstractinterpretation.jl:2289
abstract_call at ./compiler/abstractinterpretation.jl:2282
abstract_call at ./compiler/abstractinterpretation.jl:2432
abstract_eval_call at ./compiler/abstractinterpretation.jl:2445
abstract_eval_statement_expr at ./compiler/abstractinterpretation.jl:2680
abstract_eval_statement at ./compiler/abstractinterpretation.jl:2788
abstract_eval_basic_statement at ./compiler/abstractinterpretation.jl:3082
typeinf_local at ./compiler/abstractinterpretation.jl:3359
typeinf_nocycle at ./compiler/abstractinterpretation.jl:3441
_typeinf at ./compiler/typeinfer.jl:273
typeinf at ./compiler/typeinfer.jl:215
jfptr_typeinf_37992.1 at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/lib/julia/sys.so (unknown line)
_jl_invoke at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3081 [inlined]
ijl_invoke at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3088
typeinf_edge at ./compiler/typeinfer.jl:923
abstract_call_method at ./compiler/abstractinterpretation.jl:660
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:101
abstract_call_known at ./compiler/abstractinterpretation.jl:2207
abstract_call at ./compiler/abstractinterpretation.jl:2289
abstract_call at ./compiler/abstractinterpretation.jl:2282
abstract_call at ./compiler/abstractinterpretation.jl:2432
abstract_eval_call at ./compiler/abstractinterpretation.jl:2445
abstract_eval_statement_expr at ./compiler/abstractinterpretation.jl:2680
abstract_eval_statement at ./compiler/abstractinterpretation.jl:2788
abstract_eval_basic_statement at ./compiler/abstractinterpretation.jl:3106
typeinf_local at ./compiler/abstractinterpretation.jl:3359
typeinf_nocycle at ./compiler/abstractinterpretation.jl:3441
_typeinf at ./compiler/typeinfer.jl:273
typeinf at ./compiler/typeinfer.jl:215
jfptr_typeinf_37992.1 at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/lib/julia/sys.so (unknown line)
_jl_invoke at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3081 [inlined]
ijl_invoke at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3088
typeinf_edge at ./compiler/typeinfer.jl:923
abstract_call_method at ./compiler/abstractinterpretation.jl:660
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:101
abstract_call_known at ./compiler/abstractinterpretation.jl:2207
abstract_call at ./compiler/abstractinterpretation.jl:2289
abstract_call at ./compiler/abstractinterpretation.jl:2282
abstract_call at ./compiler/abstractinterpretation.jl:2432
abstract_eval_call at ./compiler/abstractinterpretation.jl:2445
abstract_eval_statement_expr at ./compiler/abstractinterpretation.jl:2680
abstract_eval_statement at ./compiler/abstractinterpretation.jl:2788
abstract_eval_basic_statement at ./compiler/abstractinterpretation.jl:3106
typeinf_local at ./compiler/abstractinterpretation.jl:3359
typeinf_nocycle at ./compiler/abstractinterpretation.jl:3441
_typeinf at ./compiler/typeinfer.jl:273
typeinf at ./compiler/typeinfer.jl:215
jfptr_typeinf_37992.1 at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/lib/julia/sys.so (unknown line)
_jl_invoke at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3081 [inlined]
ijl_invoke at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3088
typeinf_edge at ./compiler/typeinfer.jl:923
abstract_call_method at ./compiler/abstractinterpretation.jl:660
abstract_call_gf_by_type at ./compiler/abstractinterpretation.jl:101
abstract_call_known at ./compiler/abstractinterpretation.jl:2207
abstract_call at ./compiler/abstractinterpretation.jl:2289
abstract_call at ./compiler/abstractinterpretation.jl:2282
abstract_call at ./compiler/abstractinterpretation.jl:2432
abstract_eval_call at ./compiler/abstractinterpretation.jl:2445
abstract_eval_statement_expr at ./compiler/abstractinterpretation.jl:2680
abstract_eval_statement at ./compiler/abstractinterpretation.jl:2788
abstract_eval_basic_statement at ./compiler/abstractinterpretation.jl:3106
typeinf_local at ./compiler/abstractinterpretation.jl:3359
typeinf_nocycle at ./compiler/abstractinterpretation.jl:3441
_typeinf at ./compiler/typeinfer.jl:273
typeinf at ./compiler/typeinfer.jl:215
typeinf_ext at ./compiler/typeinfer.jl:1176
typeinf_ext_toplevel at ./compiler/typeinfer.jl:1239 [inlined]
typeinf_ext_toplevel at ./compiler/typeinfer.jl:1237
jfptr_typeinf_ext_toplevel_38275.1 at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/lib/julia/sys.so (unknown line)
_jl_invoke at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3081 [inlined]
ijl_apply_generic at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3258
jl_apply at /cache/build/builder-amdci5-5/julialang/julia-master/src/julia.h:2185 [inlined]
jl_type_infer at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:395
jl_compile_method_internal at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:2645
_jl_invoke at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3073 [inlined]
ijl_apply_generic at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3258
jl_apply at /cache/build/builder-amdci5-5/julialang/julia-master/src/julia.h:2185 [inlined]
do_call at /cache/build/builder-amdci5-5/julialang/julia-master/src/interpreter.c:127
eval_value at /cache/build/builder-amdci5-5/julialang/julia-master/src/interpreter.c:224
eval_stmt_value at /cache/build/builder-amdci5-5/julialang/julia-master/src/interpreter.c:175 [inlined]
eval_body at /cache/build/builder-amdci5-5/julialang/julia-master/src/interpreter.c:670
jl_interpret_toplevel_thunk at /cache/build/builder-amdci5-5/julialang/julia-master/src/interpreter.c:877
top-level scope at REPL[2]:1
jl_toplevel_eval_flex at /cache/build/builder-amdci5-5/julialang/julia-master/src/toplevel.c:969
__repl_entry_eval_expanded_with_loc at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:222
toplevel_eval_with_hooks at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:229
toplevel_eval_with_hooks at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:233
toplevel_eval_with_hooks at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:226 [inlined]
eval_user_input at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:251
repl_backend_loop at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:360
#start_repl_backend#55 at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:345
start_repl_backend at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:342
_jl_invoke at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3081 [inlined]
ijl_apply_generic at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3258
#run_repl#68 at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:501
run_repl at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:487
jfptr_run_repl_12585 at /home/nsajko/.julia/compiled/v1.12/REPL/u0gqU_umh3X.so (unknown line)
_jl_invoke at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3081 [inlined]
ijl_apply_generic at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3258
#1157 at ./client.jl:447
jfptr_YY.1157_17222 at /home/nsajko/.julia/compiled/v1.12/REPL/u0gqU_umh3X.so (unknown line)
_jl_invoke at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3081 [inlined]
ijl_apply_generic at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3258
jl_apply at /cache/build/builder-amdci5-5/julialang/julia-master/src/julia.h:2185 [inlined]
jl_f__call_latest at /cache/build/builder-amdci5-5/julialang/julia-master/src/builtins.c:875
#invokelatest#2 at ./essentials.jl:1045 [inlined]
invokelatest at ./essentials.jl:1042 [inlined]
run_main_repl at ./client.jl:431
repl_main at ./client.jl:567 [inlined]
_start at ./client.jl:542
jfptr__start_71268.1 at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/lib/julia/sys.so (unknown line)
_jl_invoke at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3081 [inlined]
ijl_apply_generic at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3258
jl_apply at /cache/build/builder-amdci5-5/julialang/julia-master/src/julia.h:2185 [inlined]
true_main at /cache/build/builder-amdci5-5/julialang/julia-master/src/jlapi.c:900
jl_repl_entrypoint at /cache/build/builder-amdci5-5/julialang/julia-master/src/jlapi.c:1059
main at /cache/build/builder-amdci5-5/julialang/julia-master/cli/loader_exe.c:58
unknown function (ip: 0x773b02cbdc87)
__libc_start_main at /usr/lib/libc.so.6 (unknown line)
unknown function (ip: 0x4010b8)

[227276] signal 6 (-6): Aborted
in expression starting at REPL[2]:1
unknown function (ip: 0x773b02d2ce44)
gsignal at /usr/lib/libc.so.6 (unknown line)
abort at /usr/lib/libc.so.6 (unknown line)
jl_type_infer at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:414
jl_compile_method_internal at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:2645
_jl_invoke at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3073 [inlined]
ijl_apply_generic at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3258
jl_apply at /cache/build/builder-amdci5-5/julialang/julia-master/src/julia.h:2185 [inlined]
do_call at /cache/build/builder-amdci5-5/julialang/julia-master/src/interpreter.c:127
eval_value at /cache/build/builder-amdci5-5/julialang/julia-master/src/interpreter.c:224
eval_stmt_value at /cache/build/builder-amdci5-5/julialang/julia-master/src/interpreter.c:175 [inlined]
eval_body at /cache/build/builder-amdci5-5/julialang/julia-master/src/interpreter.c:670
jl_interpret_toplevel_thunk at /cache/build/builder-amdci5-5/julialang/julia-master/src/interpreter.c:877
jl_toplevel_eval_flex at /cache/build/builder-amdci5-5/julialang/julia-master/src/toplevel.c:969
__repl_entry_eval_expanded_with_loc at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:222
toplevel_eval_with_hooks at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:229
toplevel_eval_with_hooks at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:233
toplevel_eval_with_hooks at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:226 [inlined]
eval_user_input at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:251
repl_backend_loop at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:360
#start_repl_backend#55 at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:345
start_repl_backend at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:342
_jl_invoke at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3081 [inlined]
ijl_apply_generic at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3258
#run_repl#68 at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:501
run_repl at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/share/julia/stdlib/v1.12/REPL/src/REPL.jl:487
jfptr_run_repl_12585 at /home/nsajko/.julia/compiled/v1.12/REPL/u0gqU_umh3X.so (unknown line)
_jl_invoke at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3081 [inlined]
ijl_apply_generic at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3258
#1157 at ./client.jl:447
jfptr_YY.1157_17222 at /home/nsajko/.julia/compiled/v1.12/REPL/u0gqU_umh3X.so (unknown line)
_jl_invoke at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3081 [inlined]
ijl_apply_generic at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3258
jl_apply at /cache/build/builder-amdci5-5/julialang/julia-master/src/julia.h:2185 [inlined]
jl_f__call_latest at /cache/build/builder-amdci5-5/julialang/julia-master/src/builtins.c:875
#invokelatest#2 at ./essentials.jl:1045 [inlined]
invokelatest at ./essentials.jl:1042 [inlined]
run_main_repl at ./client.jl:431
repl_main at ./client.jl:567 [inlined]
_start at ./client.jl:542
jfptr__start_71268.1 at /home/nsajko/tmp/jl/jl/assert/julia-9d8ecaa899/lib/julia/sys.so (unknown line)
_jl_invoke at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3081 [inlined]
ijl_apply_generic at /cache/build/builder-amdci5-5/julialang/julia-master/src/gf.c:3258
jl_apply at /cache/build/builder-amdci5-5/julialang/julia-master/src/julia.h:2185 [inlined]
true_main at /cache/build/builder-amdci5-5/julialang/julia-master/src/jlapi.c:900
jl_repl_entrypoint at /cache/build/builder-amdci5-5/julialang/julia-master/src/jlapi.c:1059
main at /cache/build/builder-amdci5-5/julialang/julia-master/cli/loader_exe.c:58
unknown function (ip: 0x773b02cbdc87)
__libc_start_main at /usr/lib/libc.so.6 (unknown line)
unknown function (ip: 0x4010b8)
Allocations: 121250751 (Pool: 121250645; Big: 106); GC: 130
Aborted (core dumped)

Alternatively, may also be reproduced with Core.Compiler.return_type(HeterogeneousLists.from_tuple, Tuple{Tuple{Vararg{Int}}}):

julia> Core.Compiler.return_type(HeterogeneousLists.from_tuple, Tuple{Tuple{Vararg{Int}}})
^CERROR: InterruptException:
Stacktrace:
  [1] getindex
    @ ./iddict.jl:97 [inlined]
  [2] findall(sig::Type, table::Core.Compiler.CachedMethodTable{Core.Compiler.InternalMethodTable}; limit::Int64)
    @ Core.Compiler ./compiler/methodtable.jl:107
  [3] findall
    @ ./compiler/methodtable.jl:100 [inlined]
  [4] find_simple_method_matches(interp::Core.Compiler.NativeInterpreter, atype::Any, max_methods::Int64)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:320
  [5] find_method_matches(interp::Core.Compiler.NativeInterpreter, argtypes::Vector{Any}, atype::Any; max_union_splitting::Int64, max_methods::Int64)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:263
  [6] find_method_matches
    @ ./compiler/abstractinterpretation.jl:257 [inlined]
  [7] abstract_call_gf_by_type(interp::Core.Compiler.NativeInterpreter, f::Any, arginfo::Core.Compiler.ArgInfo, si::Core.Compiler.StmtInfo, atype::Any, sv::Core.Compiler.InferenceState, max_methods::Int64)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:25
  [8] abstract_call_known(interp::Core.Compiler.NativeInterpreter, f::Any, arginfo::Core.Compiler.ArgInfo, si::Core.Compiler.StmtInfo, sv::Core.Compiler.InferenceState, max_methods::Int64)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:2207
  [9] abstract_call(interp::Core.Compiler.NativeInterpreter, arginfo::Core.Compiler.ArgInfo, si::Core.Compiler.StmtInfo, sv::Core.Compiler.InferenceState, max_methods::Int64)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:2289
 [10] abstract_call(interp::Core.Compiler.NativeInterpreter, arginfo::Core.Compiler.ArgInfo, si::Core.Compiler.StmtInfo, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:2282
 [11] abstract_call(interp::Core.Compiler.NativeInterpreter, arginfo::Core.Compiler.ArgInfo, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:2432
 [12] abstract_eval_call(interp::Core.Compiler.NativeInterpreter, e::Expr, vtypes::Vector{Core.Compiler.VarState}, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:2445
 [13] abstract_eval_statement_expr(interp::Core.Compiler.NativeInterpreter, e::Expr, vtypes::Vector{Core.Compiler.VarState}, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:2680
 [14] abstract_eval_statement(interp::Core.Compiler.NativeInterpreter, e::Any, vtypes::Vector{Core.Compiler.VarState}, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:2788
 [15] abstract_eval_basic_statement(interp::Core.Compiler.NativeInterpreter, stmt::Any, pc_vartable::Vector{Core.Compiler.VarState}, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:3106
 [16] typeinf_local(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:3359
 [17] typeinf_nocycle(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:3441
 [18] _typeinf(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/typeinfer.jl:273
 [19] typeinf(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/typeinfer.jl:215
 [20] typeinf_edge(interp::Core.Compiler.NativeInterpreter, method::Method, atype::Any, sparams::Core.SimpleVector, caller::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/typeinfer.jl:923
 [21] abstract_call_method(interp::Core.Compiler.NativeInterpreter, method::Method, sig::Any, sparams::Core.SimpleVector, hardlimit::Bool, si::Core.Compiler.StmtInfo, sv::Core.Compiler.Inferen
    @ Core.Compiler ./compiler/abstractinterpretation.jl:660
 [22] abstract_call_gf_by_type(interp::Core.Compiler.NativeInterpreter, f::Any, arginfo::Core.Compiler.ArgInfo, si::Core.Compiler.StmtInfo, atype::Any, sv::Core.Compiler.InferenceState, max_me
    @ Core.Compiler ./compiler/abstractinterpretation.jl:101
--- the above 15 lines are repeated 1 more time ---
 [38] abstract_call_known(interp::Core.Compiler.NativeInterpreter, f::Any, arginfo::Core.Compiler.ArgInfo, si::Core.Compiler.StmtInfo, sv::Core.Compiler.InferenceState, max_methods::Int64)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:2207
 [39] abstract_call(interp::Core.Compiler.NativeInterpreter, arginfo::Core.Compiler.ArgInfo, si::Core.Compiler.StmtInfo, sv::Core.Compiler.InferenceState, max_methods::Int64)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:2289
 [40] abstract_call(interp::Core.Compiler.NativeInterpreter, arginfo::Core.Compiler.ArgInfo, si::Core.Compiler.StmtInfo, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:2282
 [41] abstract_call(interp::Core.Compiler.NativeInterpreter, arginfo::Core.Compiler.ArgInfo, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:2432
 [42] abstract_eval_call(interp::Core.Compiler.NativeInterpreter, e::Expr, vtypes::Vector{Core.Compiler.VarState}, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:2445
 [43] abstract_eval_statement_expr(interp::Core.Compiler.NativeInterpreter, e::Expr, vtypes::Vector{Core.Compiler.VarState}, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:2680
 [44] abstract_eval_statement(interp::Core.Compiler.NativeInterpreter, e::Any, vtypes::Vector{Core.Compiler.VarState}, sv::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:2788
 [45] abstract_eval_basic_statement(interp::Core.Compiler.NativeInterpreter, stmt::Any, pc_vartable::Vector{Core.Compiler.VarState}, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:3106
 [46] typeinf_local(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:3359
 [47] typeinf_nocycle(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/abstractinterpretation.jl:3441
 [48] _typeinf(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/typeinfer.jl:273
 [49] typeinf(interp::Core.Compiler.NativeInterpreter, frame::Core.Compiler.InferenceState)
    @ Core.Compiler ./compiler/typeinfer.jl:215
 [50] typeinf
    @ ./compiler/typeinfer.jl:12 [inlined]
 [51] typeinf_type(interp::Core.Compiler.NativeInterpreter, mi::Core.MethodInstance)
    @ Core.Compiler ./compiler/typeinfer.jl:1230
 [52] typeinf_type(interp::Core.Compiler.NativeInterpreter, match::Core.MethodMatch)
    @ Core.Compiler ./compiler/typeinfer.jl:1219
 [53] return_type(interp::Core.Compiler.NativeInterpreter, t::DataType)
    @ Core.Compiler ./compiler/typeinfer.jl:1272
 [54] return_type(f::Any, t::DataType)
    @ Core.Compiler ./compiler/typeinfer.jl:1245
nsajko commented 1 week ago 
Julia Version 1.12.0-DEV.766
Commit 9d8ecaa899d (2024-06-21 17:00 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 8 × AMD Ryzen 3 5300U with Radeon Graphics
  WORD_SIZE: 64
  LLVM: libLLVM-17.0.6 (ORCJIT, znver2)
Threads: 1 default, 0 interactive, 1 GC (on 8 virtual cores)
vtjnash commented 1 week ago

Taking effectively unbounded time on badly designed code patterns is not a bug, unless you can show it is generating an ever growing list of candidates

vtjnash commented 1 week ago

Looks like a tmerge / lattice convergence issue with the constant Conditional (t isa Tuple resolves to Core.Compiler.Conditional(slot=2, thentype=Tuple{Vararg{Int64}}, elsetype=Union{}) which is a refinement of Const(true)) interacting badly with the recursion call

MWE

julia> function tail_is_ntuple((@nospecialize t::Tuple))
           if unknown
               t isa Tuple
           else
               tail_is_ntuple(t) # alternatively `Base.tail(t)` here
           end
       end;

julia> Base.return_types(tail_is_ntuple, Tuple{Tuple{Vararg{Int}}}) # hangs

(tested to be last-working in v1.9)