Determining if UnionAll corresponds to a single type + Union{}

Internals & Design
1

A UnionAll such as Type{T} where {T<:Tuple{typeof(sin),Float64}} is a union containing a single type: Type{Tuple{typeof(sin),Float64}}

On the other hand, Type{T} where {T<:Tuple{typeof(sin),Real}} is a union over many types.

Is there a in way general to programmatically determine whether, for a given UnionAll, it contains only a single type?

2

Your first example contains two types because it also has the empty type Union{}.

So I guess you’re asking about a single concrete type?

Is this sufficient?

  1. Check if all the bounds have a concrete upper bound.
  2. Substitute these upper bounds in.
  3. See if the resulting type is concrete.

Edit: step 1 should recurse because the upper bound can also be a union-all containing one concrete type.

2 Likes
3

Shouldn’t this be the same as that UnionAll being a subtype of a given concrete type? I’m just not sure whether our subtyping handles this case.

1 Like
4

Your first example contains two types because it also has the empty type Union{}.

Good point @cjdoris

Is this sufficient?

Sorry, I’m not quite able to follow your steps here – would you be able to give an example?

Shouldn’t this be the same as that UnionAll being a subtype of a given concrete type? I’m just not sure whether our subtyping handles this case.

@Sukera ooo interesting. The below doesn’t seem to give the answer we want, but I may have misunderstood you:

julia> sig = Tuple{typeof(sin),Float64}
Tuple{typeof(sin), Float64}

julia> Type{<:sig} <: Type{sig}
false

julia> Type{<:sig} <: Union{Type{sig},Type{Union{}}}
false
5

I think my earlier method was false because you can (almost?) always substitute Union{} for the type parameter and get a concrete type.

I think this means that (almost?) all UnionAlls have multiple concrete subtypes.

For example your example Type{<:sig} <: Type{sig} is false because Type{<:sig} is equivalent to Union{Type{sig},Type{Union{}}}.

6

== seems to work given the one type, though I don’t see this documented for iterated unions in particular.

julia> let sig = Tuple{typeof(sin),Float64}, T = Type
         (T{sig} == T{S} where {S<:sig},
         T{sig} == T{S} where {sig<:S<:sig}) # force S == sig
       end
(false, true)

It’s not, one strictly subtypes the other:

julia> let sig = Tuple{typeof(sin),Float64}, T = Type
         (Union{T{sig}, T{Union{}}} == T{<:sig},
         Union{T{sig}, T{Union{}}} <: T{<:sig},
                          T{<:sig} <: Union{T{sig}, T{Union{}}})
       end
(false, true, false)

Can’t imagine what else could be in T{<:sig} though. Results are the same for sig = Int, T = Vector so it’s not an artifact of Tuple or Type.

7

Indeed, I just meant that they have the same two subtypes, not that they are equal types.

8

Thanks for your thoughts on this.

I wonder if the question is easier for us to answer if we restrict ourselves to a subset of possible Tuples? For context: in my particular use case, there’s a performance optimisation that I can perform if I know that Type{T} where T<:Tuple{...} contains only Type{Tuple{...}} and Type{Union{}}, so I’m quite happy if we’re able to determine if this is the case for a large-ish family of Tuple{...}s, as opposed to all possible Tuple{...}s.

For example, given Tuple{P_1,P_2,P_3...} where each P_n is not a subtype of Type (because this contains some edge cases that I find hard to reason about), is it enough to check that all P_n are concrete?

9

Tuples are special because they are invariant covariant. In particular a tuple type is concrete if and only if all its parameters are concrete.

I think this means that a <:Tuple bound can only have one concrete tuple if and only if:

  • it’s not Vararg (so the number of parameters is known); and
  • each parameter bound only has one concrete subtype, so either:
    • it’s a concrete type, or
    • it’s bounded above by a concrete type, or
    • it’s bounded above by a type that only has one concrete subtype (and you can recurse on this condition if you like).

In practice you probably catch most cases without needing to recurse.

1 Like
10

This makes sense. There’s still the edge case involving something like Tuple{Type{F}} for some type F to deal with, so perhaps something like this would work?

function is_safe_to_optimise(x::Type{<:Tuple})
    # Exclude `UnionAll`s, `Union`s, and `Core.TypeofBottom`.
    x isa DataType || return false

    try
        # Exclude eg. `Tuple{DataType}` because `DataType` is concrete, but `Type{F} <: DataType`.
        any(T -> T <: Type, fieldtypes(x)) && return false

        # It's now enough to know that everything is concrete?
        return isconcretetype(x)
    catch
        # If contains a `Vararg`, the fieldcount will not be defined, and an `ArgumentError` thrown.
        return false
    end
end
11

I think your function is equivalent to just isconcretetype.

12

Not quite:

julia> isconcretetype(Tuple{DataType})
true

julia> is_safe_to_optimise(Tuple{DataType})
false

I think (hope) you’re correct about every other concrete Tuple type though.

edit: note that this is an especially odd edge case:

julia> Tuple{Type{Float64}} <: Tuple{DataType}
true

despite the fact that DataType is concrete.

edit2: which I guess is true because

julia> Type{Float64} <: DataType
true
1 Like
13

This seems to be a typo.

Invariant type parameters are in fact the default in julia

julia> Int <: Integer
true

julia> Vector{Int} <: Vector{Integer}
false

and Tuple types are special because they are covariant.

julia> Tuple{Int} <: Tuple{Integer}
true

Julia Manual - parametric types
Julia Manual - Tuple types

3 Likes
14

Thanks, corrected.

1 Like
15

Thanks again everyone for your thoughts on this, I greatly appreciate you all taking the time to respond.

I don’t think that we’ve landed on a completely satisfying solution (although I suspect that is_safe_to_optimise is fairly close), so I’m not going to give anything the green tick at this point, in case someone knows something we don’t and stumbles across this in the future!

1 Like