Revision f442e4230a41d0d40f81346c1707f946f743cbcf authored by Jeff Bezanson on 09 June 2021, 02:51:34 UTC, committed by GitHub on 09 June 2021, 02:51:34 UTC
This PR implements a way to keep tables of methods that are not part of the internal method table, but still participate in the special support we have for keeping tables of methods, in particular unification through precompilation and efficient lookup. The intended design use case is to allow for method overlay tables for various non-CPU backends (e.g. GPU and TPU). These backends would like to modify basic function like `sin` to perform better on the device in question (or in the case of TPU to define them over non-LLVM intrinsics). It is worth noting that this PR only gives the ability to keep these tables of methods. It assigns no particular meaning to them and the runtime (and regular inference) do not look at them. They are designed as an implementation detail for external compilers and similar tools. # Demo ```julia julia> using Base.Experimental: @overlay, @MethodTable julia> @MethodTable(mt) # 0 methods: julia> @overlay mt function sin(x::Float64) 1 end julia> @overlay mt function cos(x::Float64) 1 end julia> mt # 2 methods: [1] cos(x::Float64) in Main at REPL[5]:1 [2] sin(x::Float64) in Main at REPL[4]:1 julia> Base._methods_by_ftype(Tuple{typeof(sin), Float64}, mt, 1, typemax(UInt)) 1-element Vector{Any}: Core.MethodMatch(Tuple{typeof(sin), Float64}, svec(), sin(x::Float64) in Main at REPL[4]:1, true) julia> Base._methods_by_ftype(Tuple{typeof(sin), Float64}, 1, typemax(UInt)) 1-element Vector{Any}: Core.MethodMatch(Tuple{typeof(sin), Float64}, svec(Float64), sin(x::T) where T<:Union{Float32, Float64} in Base.Math at special/trig.jl:29, true) ``` Co-authored-by: Tim Besard <tim.besard@gmail.com> Co-authored-by: Julian P Samaroo <jpsamaroo@jpsamaroo.me> Co-authored-by: Keno Fischer <keno@juliacomputing.com>
1 parent 0e3276c
specificity.jl
# This file is a part of Julia. License is MIT: https://julialang.org/license
function args_morespecific(a, b)
sp = (ccall(:jl_type_morespecific, Cint, (Any,Any), a, b) != 0)
if sp # make sure morespecific(a,b) implies !morespecific(b,a)
@test ccall(:jl_type_morespecific, Cint, (Any,Any), b, a) == 0
end
return sp
end
# issue #8652
let
a = Tuple{Type{T1}, T1} where T1<:Integer
b2 = Tuple{Type{T2}, Integer} where T2<:Integer
@test args_morespecific(a, b2)
@test !args_morespecific(b2, a)
a = Tuple{Type{T1}, Ptr{T1}} where T1<:Integer
b2 = Tuple{Type{T2}, Ptr{Integer}} where T2<:Integer
@test !args_morespecific(a, b2)
@test args_morespecific(b2, a)
end
# issue #11534
let
t1 = Tuple{AbstractArray, Tuple{Vararg{Base.RangeIndex}}}
t2 = Tuple{Array, T} where T<:Tuple{Vararg{Base.RangeIndex}}
@test !args_morespecific(t1, t2)
@test args_morespecific(t2, t1)
end
let
a = Tuple{Array{T,N}, Vararg{Int,N}} where T where N
b = Tuple{Array,Int}
@test args_morespecific(a, b)
@test !args_morespecific(b, a)
a = Tuple{Array, Vararg{Int,N}} where N
@test !args_morespecific(a, b)
@test args_morespecific(b, a)
end
# another specificity issue
_z_z_z_(x, y) = 1
_z_z_z_(::Int, ::Int, ::Vector) = 2
_z_z_z_(::Int, c...) = 3
@test _z_z_z_(1, 1, []) == 2
@test args_morespecific(Tuple{T,Vararg{T}} where T<:Number, Tuple{Number,Number,Vararg{Number}})
@test !args_morespecific(Tuple{Number,Number,Vararg{Number}}, Tuple{T,Vararg{T}} where T<:Number)
@test args_morespecific(Tuple{Array{T} where T<:Union{Float32,Float64,ComplexF32,ComplexF64}, Any},
Tuple{Array{T} where T<:Real, Any})
@test args_morespecific(Tuple{1,T} where T, Tuple{Any})
@test args_morespecific(Tuple{T} where T, Tuple{T,T} where T)
@test !args_morespecific(Type{T} where T<:Integer, Type{Any})
# issue #21016
@test args_morespecific(Tuple{IO, Core.TypeofBottom}, Tuple{IO, Type{T}} where T<:Number)
# issue #21382
@test args_morespecific(Tuple{Type{Pair{A,B} where B}} where A, Tuple{DataType})
@test args_morespecific(Tuple{Union{Int,String},Type{Pair{A,B} where B}} where A, Tuple{Integer,UnionAll})
# PR #21750
let A = Tuple{Any, Tuple{Vararg{Integer}}},
B = Tuple{Any, Tuple{Any}},
C = Tuple{Any, Tuple{}}
@test args_morespecific(A, B)
@test args_morespecific(C, A)
@test args_morespecific(C, B)
end
# with bound varargs
_bound_vararg_specificity_1(::Type{Array{T,N}}, d::Vararg{Int, N}) where {T,N} = 0
_bound_vararg_specificity_1(::Type{Array{T,1}}, d::Int) where {T} = 1
@test _bound_vararg_specificity_1(Array{Int,1}, 1) == 1
@test _bound_vararg_specificity_1(Array{Int,2}, 1, 1) == 0
# issue #21710
@test args_morespecific(Tuple{Array}, Tuple{AbstractVector})
@test args_morespecific(Tuple{Matrix}, Tuple{AbstractVector})
# Method specificity
begin
local f, A
f(dims::Tuple{}, A::AbstractArray{T,0}) where {T} = 1
f(dims::NTuple{N,Int}, A::AbstractArray{T,N}) where {T,N} = 2
f(dims::NTuple{M,Int}, A::AbstractArray{T,N}) where {T,M,N} = 3
A = zeros(2,2)
@test f((1,2,3), A) == 3
@test f((1,2), A) == 2
@test f((), reshape([1])) == 1
f(dims::NTuple{N,Int}, A::AbstractArray{T,N}) where {T,N} = 4
@test f((1,2), A) == 4
@test f((1,2,3), A) == 3
end
# a method specificity issue
c99991(::Type{T},x::T) where {T} = 0
c99991(::Type{UnitRange{T}},x::StepRangeLen{T}) where {T} = 1
c99991(::Type{UnitRange{T}},x::AbstractRange{T}) where {T} = 2
@test c99991(UnitRange{Float64}, 1.0:2.0) == 1
@test c99991(UnitRange{Int}, 1:2) == 2
# issue #17016, method specificity involving vararg tuples
T_17016{N} = Tuple{Any,Any,Vararg{Any,N}}
f17016(f, t::T_17016) = 0
f17016(f, t1::Tuple) = 1
@test f17016(0, (1,2,3)) == 0
@test !args_morespecific(Tuple{Type{Any}, Any}, Tuple{Type{T}, Any} where T<:VecElement)
@test !args_morespecific((Tuple{Type{T}, Any} where T<:VecElement), Tuple{Type{Any}, Any})
@test !args_morespecific(Tuple{Type{T}, Tuple{Any, Vararg{Any}}} where T<:Tuple{Any, Vararg{Any}},
Tuple{Type{Any}, Any})
@test !args_morespecific(Tuple{Type{T}, Tuple{Any, Vararg{Any}}} where T<:Tuple{Any, Vararg{Any}},
Tuple{Type{Tuple}, Tuple})
@test !args_morespecific(Tuple{Type{T}, T} where T<:Tuple{Any, Vararg{Any}},
Tuple{Type{T}, Any} where T<:VecElement)
@test args_morespecific(Tuple{Any, Tuple{}, Tuple{}}, Tuple{Any, Tuple{Any}})
@test args_morespecific(Tuple{Any, Tuple{Any}, Tuple{Any}}, Tuple{Any, Tuple{Any, Any}})
@test args_morespecific(Tuple{Any, Vararg{Tuple{}}}, Tuple{Any, Tuple{Any}})
@test args_morespecific(Tuple{T, T} where T<:AbstractFloat, Tuple{T, T, T} where T<:AbstractFloat)
@test args_morespecific(Tuple{T, Real, T} where T<:AbstractFloat, Tuple{T, T} where T<:Real)
@test args_morespecific(Tuple{Real, Real}, Tuple{T, T, T} where T <: Real)
@test !args_morespecific(Tuple{Real, Real, Real}, Tuple{T, T, T} where T <: Real)
@test !args_morespecific(Tuple{Real, Real, Vararg{Real}}, Tuple{T, T, T} where T <: Real)
@test args_morespecific(Tuple{Real, Real, Vararg{Int}}, Tuple{T, T, T} where T <: Real)
@test args_morespecific(Tuple{Type{Base.Some{T}}} where T, Tuple{Type{T}, Any} where T)
@test !args_morespecific(Tuple{Type{Base.Some{T}}, T} where T, Tuple{Type{Base.Some{T}}} where T)
@test args_morespecific(Tuple{Union{Base.StepRange{T, S} where S, Base.StepRangeLen{T, T, S} where S},
Union{Base.StepRange{T, S} where S, Base.StepRangeLen{T, T, S} where S}} where T,
Tuple{T, T} where T<:Union{Base.StepRangeLen, Base.LinRange})
@test args_morespecific(Tuple{Type{Tuple}, Any, Any},
Tuple{Type{Tuple{Vararg{E}}}, Any, Any} where E)
@test args_morespecific(Tuple{Type{Tuple{}}, Tuple{}},
Tuple{Type{T}, T} where T<:Tuple{Any, Vararg{Any}})
@test args_morespecific(Tuple{Type{CartesianIndex{N}}} where N,
Tuple{Type{CartesianIndex{N}},Vararg{Int,N}} where N)
# issue #22164
let A = Tuple{Type{D},D} where D<:Pair,
B = Tuple{Type{Any}, Any},
C = Tuple{Type{Pair}, Pair}
@test args_morespecific(C, A)
@test !args_morespecific(A, B)
@test !args_morespecific(C, B)
end
# issue #22338
let A = Tuple{Ref, Tuple{T}} where T,
B = Tuple{Ref{T}, Tuple{Vararg{T}}} where T,
C = Tuple{Ref{T}, Tuple{T}} where T
@test args_morespecific(C, A)
@test args_morespecific(C, B)
@test !args_morespecific(A, B)
@test !args_morespecific(B, A)
end
# issue #22339
let A = Tuple{T, Array{T, 1}} where T,
B = Tuple{T} where T,
C = Tuple{T} where T<:AbstractFloat
@test args_morespecific(B, A)
@test args_morespecific(C, B)
@test args_morespecific(C, A)
end
# issue #22908
f22908(::Union) = 2
f22908(::Type{Union{Int, Float32}}) = 1
@test f22908(Union{Int, Float32}) == 1
let x = Type{Union{Tuple{T}, Tuple{Ptr{T}, Ptr{T}, Any}} where T},
y = Type{Union{Tuple{T}, Tuple{Array{T, N} where N, Any, Array{T, N} where N, Any, Any}} where T}
@test !args_morespecific(x, y)
@test !args_morespecific(y, x)
@test !args_morespecific(x.parameters[1], y.parameters[1])
@test !args_morespecific(y.parameters[1], x.parameters[1])
end
let A = Tuple{Array{T,N}, Vararg{Int,N}} where {T,N},
B = Tuple{Array, Int},
C = Tuple{AbstractArray, Int, Array}
@test args_morespecific(A, B)
@test args_morespecific(B, C)
@test args_morespecific(A, C)
end
# transitivity issue found in #26915
let A = Tuple{Vector, AbstractVector},
B = Tuple{AbstractVecOrMat{T}, AbstractVector{T}} where T,
C = Tuple{AbstractVecOrMat{T}, AbstractVecOrMat{T}} where T
@test args_morespecific(A, B)
@test args_morespecific(B, C)
@test args_morespecific(A, C)
end
# issue #27361
f27361(::M) where M <: Tuple{2} = nothing
f27361(::M) where M <: Tuple{3} = nothing
@test length(methods(f27361)) == 2
# specificity of TypeofBottom
@test args_morespecific(Tuple{Core.TypeofBottom}, Tuple{DataType})
@test args_morespecific(Tuple{Core.TypeofBottom}, Tuple{Type{<:Tuple}})
@test args_morespecific(Tuple{Type{Any}, Type}, Tuple{Type{T}, Type{T}} where T)
@test !args_morespecific(Tuple{Type{Any}, Type}, Tuple{Type{T}, Type{T}} where T<:Union{})
# issue #22592
abstract type Colorant22592{T,N} end
abstract type Color22592{T, N} <: Colorant22592{T,N} end
abstract type AbstractRGB22592{T} <: Color22592{T,3} end
AbstractGray22592{T} = Color22592{T,1}
MathTypes22592{T,C} = Union{AbstractRGB22592{T},AbstractGray22592{T}}
@test !args_morespecific(Tuple{MathTypes22592}, Tuple{AbstractGray22592})
@test !args_morespecific(Tuple{MathTypes22592, MathTypes22592}, Tuple{AbstractGray22592})
@test args_morespecific(Union{Set,Dict,Vector}, Union{Vector,AbstractSet})
let N = Tuple{Type{Union{Nothing, T}}, Union{Nothing, T}} where T,
LI = Tuple{Type{LinearIndices{N,R}}, LinearIndices{N}} where {N,R},
A = Tuple{Type{T},T} where T<:AbstractArray
@test args_morespecific(LI, A)
@test args_morespecific(A, N)
@test args_morespecific(LI, N)
end
# issue #29528
@test !args_morespecific(Tuple{Array,Vararg{Int64}}, Tuple{AbstractArray, Array})
@test !args_morespecific(Tuple{Array,Vararg{Int64,N}} where N, Tuple{AbstractArray, Array})
@test args_morespecific(Tuple{Array,Int64}, Tuple{Array,Vararg{Int64,N}} where N)
@test args_morespecific(Tuple{Array,Int64}, Tuple{Array,Vararg{Int64}})
@test !args_morespecific(Tuple{Array,Int64}, Tuple{AbstractArray, Array})
# issue #30114
let T1 = Tuple{Type{Tuple{Vararg{AbstractUnitRange{Int64}}}},CartesianIndices{N,R} where R<:Tuple{Vararg{AbstractUnitRange{Int64},N}}} where N
T2 = Tuple{Type{T},T} where T<:AbstractArray
T3 = Tuple{Type{AbstractArray{T,N} where N},AbstractArray} where T
T4 = Tuple{Type{AbstractArray{T,N}},AbstractArray{s57,N} where s57} where N where T
@test !args_morespecific(T1, T2)
@test !args_morespecific(T1, T3)
@test !args_morespecific(T1, T4)
@test args_morespecific(T2, T3)
@test args_morespecific(T2, T4)
end
@test !args_morespecific(Tuple{Type{Tuple{Vararg{AbstractUnitRange{Int64},N}}},} where N,
Tuple{Type{Tuple{Vararg{AbstractUnitRange}}},})
@test args_morespecific(Tuple{Type{SubArray{T,2,P} where T}, Array{T}} where T where P,
Tuple{Type{AbstractArray{T,N} where N},AbstractArray} where T)
# these are ambiguous
@test !args_morespecific(Tuple{Type{T},T} where T<:BitArray,
Tuple{Type{BitArray},Any})
@test !args_morespecific(Tuple{Type{BitArray},Any},
Tuple{Type{T},T} where T<:BitArray)
abstract type Domain{T} end
abstract type AbstractInterval{T} <: Domain{T} end
struct Interval{L,R,T} <: AbstractInterval{T}
end
let A = Tuple{Type{Interval{:closed,:closed,T} where T}, Interval{:closed,:closed,T} where T},
B = Tuple{Type{II}, AbstractInterval} where II<:(Interval{:closed,:closed,T} where T),
C = Tuple{Type{AbstractInterval}, AbstractInterval}
@test args_morespecific(A, B)
@test !args_morespecific(B, C)
@test !args_morespecific(A, C)
end
let A = Tuple{Type{Domain}, Interval{L,R,T} where T} where R where L,
B = Tuple{Type{II}, AbstractInterval} where II<:(Interval{:closed,:closed,T} where T),
C = Tuple{Type{AbstractInterval{T}}, AbstractInterval{T}} where T
@test !args_morespecific(A, B)
@test args_morespecific(B, C)
@test !args_morespecific(A, C)
end
let A = Tuple{Type{AbstractInterval}, Interval{L,R,T} where T} where R where L,
B = Tuple{Type{II}, AbstractInterval} where II<:(Interval{:closed,:closed,T} where T),
C = Tuple{Type{AbstractInterval{T}}, AbstractInterval{T}} where T
@test !args_morespecific(A, B)
@test args_morespecific(B, C)
@test args_morespecific(A, C)
end
@test args_morespecific(Tuple{Type{Missing},Any},
Tuple{Type{Union{Nothing, T}},Any} where T)
let A = Tuple{Type{SubString{S}},AbstractString} where S<:AbstractString,
B = Tuple{Type{T},AbstractString} where T<:AbstractString,
C = Tuple{Type{Union{Missing, Nothing, T}},Union{Missing, Nothing, T}} where T
@test args_morespecific(A, B)
@test args_morespecific(B, C)
@test args_morespecific(A, C)
end
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...