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

1 Like
14

Thanks, corrected.

1 Like