Hang in inference, during subtyping, on 1.10.9

[Drvi]

The following code hangs:

reproducer

abstract type AbstractTypeDescriptor <: Base.Order.Ordering end
struct MyOrdering <: AbstractTypeDescriptor
end
struct KVTypeDescriptor{K,V} <: AbstractTypeDescriptor
    denormalized_type::Type
end
key_td(x) = x
value_td(x) = x
normalize_values_tuple(x) = x

activated() = true
has_var_strings(::Type) = false
has_var_strings(::Type{String}) = true
has_var_strings(::Type{Regex}) = true
has_var_strings(::Type{Tuple{}}) = false
has_var_strings(::Type{Union{}}) = false
function has_var_strings(T::Type{<:Tuple})
    has_var_strings(Base.tuple_type_head(T)) && return true
    return has_var_strings(Base.tuple_type_tail(T))
end

function denormalize_values_tuple(::Type{V}, values::Tuple) where {V<:Tuple}
    if activated() && !has_var_strings(V)
        # return fast_reinterpret(V, values)
        return denormalize_tuple(V, values)
    else
        return values
    end
end

@inline flatten_tuple(t::Tuple) = _flatten_tuple(t)
_flatten_tuple(::Tuple{}) = ()
_flatten_tuple(v) = (v,)
function _flatten_tuple(t::Tuple)
    head = first(t)
    # This is necessary because we need to distinguish between empty tuples
    # in the input (to keep them) and the stopping condition.
    if typeof(head) == Tuple{}
        ((), _flatten_tuple(Base.tail(t))...)
    else
        (_flatten_tuple(head)..., _flatten_tuple(Base.tail(t))...)
    end
end


@inline flatten_tuple_type(::Type{T}) where {T<:Tuple} = _flatten_tuple_type(T)
_flatten_tuple_type(::Type{T}) where T = Tuple{T}
_flatten_tuple_type(::Type{Tuple{}}) = Tuple{}
function _flatten_tuple_type(::Type{T}) where {T <: Tuple}
    HeadType = Base.tuple_type_head(T)
    if HeadType == Tuple{}
        return Tuple{
            Tuple{},
            fieldtypes(_flatten_tuple_type(Base.tuple_type_tail(T)))...
        }
    else
        return Tuple{
            fieldtypes(_flatten_tuple_type(HeadType))...,
            fieldtypes(_flatten_tuple_type(Base.tuple_type_tail(T)))...
        }
    end
end

@inline function unflatten_tuple(::Type{T}, t::Tuple) where {T <: Tuple}
    result, rest = _unflatten_tuple(T, t)
    return result
end

_unflatten_tuple(::Type{Tuple{}}, t::Tuple) = ((), t)
function _unflatten_tuple(::Type{T}, t::Tuple) where {T <: Tuple}
    HeadType = Base.tuple_type_head(T)
    # This is necessary because we need to distinguish between empty tuples
    # in the input (to keep them) and the stopping condition.
    if HeadType == Tuple{}
        head = first(t)
        tail, rest = _unflatten_tuple(Base.tuple_type_tail(T), Base.tail(t))
        return ((head, tail...), rest)
    elseif HeadType <: Tuple
        head, tail = _unflatten_tuple(HeadType, t)
        tail2, rest = _unflatten_tuple(Base.tuple_type_tail(T), tail)
        return ((head, tail2...), rest)
    else
        head = first(t)
        tail, rest = _unflatten_tuple(Base.tuple_type_tail(T), Base.tail(t))
        return ((head, tail...), rest)
    end
end

denormalize_tuple(::Type{K}, t::K) where {K<:Tuple} = return t

function denormalize_tuple(::Type{K}, t::Tuple) where {K}
    FlatK = flatten_tuple_type(K)
    flat = _deconstruct_tuple(FlatK, t)
    return unflatten_tuple(K, flat)
end

is_normalizable_type(::Type{T}) where {T} = isabstracttype(T) || T <: Tuple

@inline _deconstruct_tuple(::Type{K}, ::Tuple{}) where K = ()
@inline function _deconstruct_tuple(::Type{K}, t::Tuple) where {K}
    head = first(t)
    tail = Base.tail(t)

    if is_normalizable_type(first(fieldtypes(K)))
        return t
    else
        return (head, _deconstruct_tuple(Base.tuple_type_tail(K), tail)...)
    end
end

const DEFAULT_SORTING_ALG = Base.Sort.Small{10}(Base.Sort.CheckSorted(QuickSort))
const Option{T} = Union{Nothing, T}

struct AggregationSpec
    reduce_op::Option{Function}
    filter_op::Option{Function}
end

function sort_and_aggregate!(
    agg_spec::AggregationSpec,
    records::Vector{Tuple{K,V}},
    td::AbstractTypeDescriptor,
) where {K,V}
    aggregate!(agg_spec.reduce_op, agg_spec.filter_op, records, td)
    return nothing
end


function aggregate!(
    op, filter_op, records::Vector{Tuple{K,V}}, td::AbstractTypeDescriptor, lo::Int = 1, hi::Int = length(records)
) where {K,V}
    return _aggregate!(op, filter_op, records, td, td.denormalized_type, lo, hi)
end
function aggregate!(
    op, filter_op, records::Vector{Tuple{K,V}}, td::MyOrdering, lo::Int = 1, hi::Int = length(records)
) where {K,V}
    return _aggregate!(op, filter_op, records, td, V, lo, hi)
end

function _aggregate!(
    reduce_op::OP,
    filter_op::Option{Function},
    records::Vector{Tuple{K,V}},
    td::AbstractTypeDescriptor,
    ::Type{VDenorm},
    lo::Int,
    hi::Int,
) where {OP<:Function,K,V<:Tuple,VDenorm}
    _denormalize_value(VDenorm, records[lo+1][2])::VDenorm
    return lo-1
end
function _aggregate!(
    ::Nothing,
    ::Nothing,
    records::Vector{Tuple{K,V}},
    td::AbstractTypeDescriptor,
    ::Type,
    lo::Int,
    hi::Int,
) where {K,V}
    return lo
end

_denormalize_value(::Type{V}, value::V) where {V} = value
_denormalize_value(::Type{V}, value::VNorm) where {V,VNorm} = denormalize_values_tuple(V, value)

# hangs
sort_and_aggregate!(AggregationSpec((a,b,c)->true, nothing), Tuple{Tuple{Int},Tuple{Int}}[((1,),(2,))], KVTypeDescriptor{Tuple{Int},Tuple{Int}}(Tuple{Int}))

When interrupted, the stack trace points to subtyping:

subtype_tuple at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:1299
subtype_tuple_varargs at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:1111 [inlined]
subtype_tuple_tail at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:1232 [inlined]
subtype_tuple at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:1340
subtype_tuple_varargs at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:1111 [inlined]
subtype_tuple_tail at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:1232 [inlined]
subtype_tuple at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:1340
subtype_tuple_varargs at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:1111 [inlined]
subtype_tuple_tail at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:1232 [inlined]
subtype_tuple at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:1340
exists_subtype at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:1716 [inlined]
forall_exists_subtype at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:1745 [inlined]
ijl_subtype_env at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:2204
ijl_subtype at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:2241 [inlined]
subtype_tuple_tail at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:1258 [inlined]
subtype_tuple at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:1340
exists_subtype at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:1716 [inlined]
forall_exists_subtype at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:1745 [inlined]
ijl_subtype_env at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/subtype.c:2204
jl_f_issubtype at /Users/julia/.julia/scratchspaces/a66863c6-20e8-4ff4-8a62-49f30b1f605e/agent-cache/default-honeycrisp-HL2F7YQ3XH.0/build/default-honeycrisp-HL2F7YQ3XH-0/julialang/julia-release-1-dot-10/src/builtins.c:547
⊑ at ./compiler/abstractlattice.jl:153 [inlined]
⊑ at ./compiler/typelattice.jl:530
⊑ at ./compiler/typelattice.jl:508
⊑ at ./compiler/typelattice.jl:432 [inlined]
⊑ at ./compiler/typelattice.jl:397
tmerge_limited at ./compiler/typelimits.jl:408
tmerge at ./compiler/typelimits.jl:450 [inlined]
record_ssa_assign! at ./compiler/inferencestate.jl:583
...

julia> versioninfo()
Julia Version 1.10.9
Commit 5595d20a287 (2025-03-10 12:51 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: macOS (arm64-apple-darwin24.0.0)
  CPU: 10 × Apple M1 Max
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-15.0.7 (ORCJIT, apple-m1)
Threads: 1 default, 0 interactive, 1 GC (on 8 virtual cores)

The issue doesn't seem to reproduce on 1.11 and recent nightly (the code runs and throws an exception -- this is expected, it's a minified example).

Could you please have a look? Thanks!

[vtjnash]

Have you tried it without Base.@assume_effects :foldable? That annotation appears to be factually wrong, so it might be relevant to any spurious problems you get with this code

[NHDaly]

I have confirmed it still hangs without it, thanks for the recommendation.
I'll ask you about the annotation on slack, so as not to distract from the discussion here.

[NHDaly]

I've edited the reproducer at the top of the issue to remove the annotation, since it reproduces without it, for both me and Tomas. Thanks all!

[KristofferC]

Fix bisected to #50927.

[NHDaly]

Next steps for Kristoffer:

• Use debugger to find out what it was inferring / what subtyping problem it was solving
• Ask around to see if there's a fix for this specific issue.

[KristofferC]

The subtype query that seems to get stuck from the MWE on 1.10 is:

a = Tuple{Tuple{Vararg{Tuple{Vararg{Tuple{Vararg{Tuple{Vararg{Tuple{Vararg{             Union{Tuple{}, Tuple{Tuple{}}}}}}}}}}}}}  , Tuple{}}
b = Tuple{Tuple{Vararg{Tuple{Vararg{Tuple{Vararg{Tuple{Vararg{Tuple{Vararg{Tuple{Vararg{Union{Tuple{}, Tuple{Tuple{}}}}}}}}}}}}}}}, Tuple{}}
a <: b

This specific query also hangs on nightly (although the MWE does no longer reproduce).

@N5N3 or @vtjnash, any chance you could give some extra info on the possibility of fixing this?

[N5N3]

Looks like a ∀ union explosion caused by Union inside nested Vararg.
This specific query should be fixable, we just need some fast path like https://github.com/JuliaLang/julia/blob/master/src/subtype.c#L1265-L1274