Hang in subtyping with sufficiently-complex `Union`

[timholy]

If I have time I'll see if I can simplify this further, but this is already greatly simplified from the original. Define this file:

import Base: map, convert
using Base.Broadcast: BroadcastStyle, Unknown, combine_styles, result_style

## Linked-list representation of a tuple. Inferrable even for Type elements.

struct TupleLL{T, Rest}
    head::T    # car
    rest::Rest # cdr
    TupleLL(x, rest::TupleLL) where {} = new{Core.Typeof(x), typeof(rest)}(x, rest) # (cons x rest)
    TupleLL(x, rest::Nothing) where {} = new{Core.Typeof(x), typeof(rest)}(x, rest) # (cons x nil)
    TupleLL(x) where {} = new{Core.Typeof(x), Nothing}(x, nothing) # (list x)
    TupleLL() where {} = new{Nothing, Nothing}(nothing, nothing)
end
# (apply list a)
make_TupleLL() = TupleLL()
make_TupleLL(a) = TupleLL(a)
make_TupleLL(a, args...) = TupleLL(a, make_TupleLL(args...))


struct Broadcasted{Style<:Union{Nothing,BroadcastStyle}, ElType, Axes, Indexing<:Union{Nothing,TupleLL}, F, Args<:TupleLL}
    f::F
    args::Args
    axes::Axes          # the axes of the resulting object (may be bigger than implied by `args` if this is nested inside a larger `Broadcasted`)
    indexing::Indexing  # index-replacement info computed from `newindexer` below
end

function Broadcasted(f::F, args::Args) where {F, Args<:TupleLL}
    style = _combine_styles(args)
    Broadcasted{typeof(style), Unknown, Nothing, Nothing, Core.Typeof(f), Args}(f, args, nothing, nothing)
     # Unknown is a flag indicating the ElType has not been set
     # using Core.Typeof rather than F preserves inferrability when f is a type
end

_combine_styles(args::TupleLL{Nothing,Nothing}) = Scalar()
_combine_styles(args::TupleLL{T,Nothing}) where T = combine_styles(args.head)
@inline _combine_styles(args::TupleLL) = result_style(combine_styles(args.head), _combine_styles(args.rest))

## Instantiation fills in the "missing" fields in Broadcasted.

@inline instantiate(bc::Broadcasted{Style,Unknown,Nothing,Nothing}) where {Style} = 1

@inline instantiate(bc::Broadcasted{Style,Unknown,Nothing,Nothing}, axes) where {Style} = 2

@inline function instantiate(bc::Broadcasted{Style,ElType,Nothing,Nothing}) where {Style,ElType} return 3 end

@inline instantiate(bc::Broadcasted{Style,ElType,Nothing,Nothing}, axes) where {Style,ElType} = 4

@inline function instantiate(bc::Broadcasted{Style,ElType,Axes,Nothing}) where {Style,ElType,Axes} return 5 end

instantiate(bc::Broadcasted{Style,ElType,Axes,Indexing}) where {Style,ElType,Axes,Indexing<:Tuple} = 6

Then include it and do this:

a = Vector{Union{Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8}}(uninitialized, 8); fill!(a, 1)
c = [1]
bc = Broadcasted(==, make_TupleLL(a, c));
@which instantiate(bc)

and you should see a hang on the @which. Reducing the complexity of the Union used in eltype(a) lets the method finish.

One curiosity is that if you hit Ctrl-C enough times then it returns the correct value immediately.

The reason I say this is in subtyping is that sometimes I get a backtrace from Ctrl-C, and most often it breaks in subtype at /home/tim/src/julia-1.0/src/subtype.c:856 or nearby lines.

[gbaraldi]

This does not hang for me anymore!