Find most specific type

given a collection of type tupels.
Like [Tuple{Int, Int}, Tuple{Integer, Integer}, Tuple{T, T} where T<: Real]
how can I find which is the most specific?

I assume julia has a fast way of doing this since this is what dispatch needs to do.
An abusive way might be to generate a bunch of methods, and then use @which, and then pull off the sig from the method object.
but that seems gross.

julia> type_morespecific(a, b) = ccall(:jl_type_morespecific, Cint, (Any,Any), a, b)
type_morespecific (generic function with 1 method)

julia> types = [Tuple{Int, Int}, Tuple{Integer, Integer}, Tuple{T, T} where T<: Real, Tuple{Int, Integer}];

julia> sort(types, lt = Bool∘type_morespecific)
4-element Vector{Type}:
 Tuple{Int64, Int64}
 Tuple{Int64, Integer}
 Tuple{Integer, Integer}
 Tuple{T, T} where T<:Real

(thanks to @jakobnissen for linking More about types · The Julia Language) but that doesn’t necessarily give an answer to which method your input tuple would be dispatched to (e.g. consider Tuple{Int64, Float64}).

6 Likes

Since we don’t actually need to the fully ordered list of specificity,
just the most specific,
I think we can maybe use the subtype operator <:.
I think this is only correct because we want just the most specific, the others might be in another order,
since <: only is a partial ordering. Because there are types that are neither a<:b nor b<:a.
But anything at the bottom must not be >: of anything else in the list.
Which is still not enough to to give us a unique most specific.
But if we add the additional restriction that these are all answers to T in a isa T for some specific a, which is true in my case, then I think now it is enough to find use a unique most specific type, modulo ambiguity.

And that is a fair bit faster

julia> using BenchmarkTools

julia> type_morespecific(a, b) = Bool(ccall(:jl_type_morespecific, Cint, (Any,Any), a, b))
type_morespecific (generic function with 1 method)

julia> is_subtype_vs(a, b) = a <: b
is_subtype_vs (generic function with 1 method)

julia> is_subtype_ts(::Type{a}, ::Type{b}) where {a,b} = a <: b
is_subtype_ts (generic function with 1 method)

julia> const types = [Tuple{Int, Int}, Tuple{Integer, Integer}, Tuple{T, T} where T<: Real, Tuple{Int, Integer}];

julia> @btime partialsort(types, 1; lt=type_morespecific)
  1.304 μs (5 allocations: 304 bytes)
Tuple{Int64, Int64}

julia> @btime partialsort(types, 1; lt=is_subtype_vs)
  495.861 ns (3 allocations: 208 bytes)
Tuple{Int64, Int64}

julia> @btime partialsort(types, 1; lt=is_subtype_ts)
  212.740 ns (1 allocation: 112 bytes)
Tuple{Int64, Int64}

However, as I said this doesn’t overall give a correct ordering.

julia> @btime sort(types, lt=type_morespecific)
  1.326 μs (6 allocations: 384 bytes)
4-element Vector{Type}:
 Tuple{Int64, Int64}
 Tuple{Int64, Integer}
 Tuple{Integer, Integer}
 Tuple{T, T} where T<:Real

julia> @btime sort(types, lt=is_subtype_vs)
  515.120 ns (4 allocations: 288 bytes)
4-element Vector{Type}:
 Tuple{Int64, Int64}
 Tuple{Integer, Integer}
 Tuple{T, T} where T<:Real
 Tuple{Int64, Integer}

julia> @btime sort(types, lt=is_subtype_ts)
  225.705 ns (2 allocations: 192 bytes)
4-element Vector{Type}:
 Tuple{Int64, Int64}
 Tuple{Integer, Integer}
 Tuple{T, T} where T<:Real
 Tuple{Int64, Integer}

That’s what I tried to use initially, but:

julia> Tuple{Integer, Integer} <: Tuple{T, T} where T<: Real
false

julia> type_morespecific(Tuple{Integer, Integer}, Tuple{T, T} where T<: Real)
true
1 Like

Ah i see, yeah.

That is still a problem even for a set of methods that follow my

But if we add the additional restriction that these are all answers to T in a isa T for some specific a , which is true in my case, then I think now it is enough to find use a unique most specific type, modulo ambiguity.