https://github.com/JuliaLang/julia
Tip revision: 4ba81cb96264e4ae9202aad108bdbc86581a9d51 authored by Gabriel Baraldi on 26 October 2023, 15:04:29 UTC
Require patchelf to install llvm tools
Require patchelf to install llvm tools
Tip revision: 4ba81cb
methodtable.jl
# This file is a part of Julia. License is MIT: https://julialang.org/license
struct MethodLookupResult
# Really Vector{Core.MethodMatch}, but it's easier to represent this as
# and work with Vector{Any} on the C side.
matches::Vector{Any}
valid_worlds::WorldRange
ambig::Bool
end
length(result::MethodLookupResult) = length(result.matches)
function iterate(result::MethodLookupResult, args...)
r = iterate(result.matches, args...)
r === nothing && return nothing
match, state = r
return (match::MethodMatch, state)
end
getindex(result::MethodLookupResult, idx::Int) = getindex(result.matches, idx)::MethodMatch
"""
struct InternalMethodTable <: MethodTableView
A struct representing the state of the internal method table at a
particular world age.
"""
struct InternalMethodTable <: MethodTableView
world::UInt
end
"""
struct OverlayMethodTable <: MethodTableView
Overlays the internal method table such that specific queries can be redirected to an
external table, e.g., to override existing method.
"""
struct OverlayMethodTable <: MethodTableView
world::UInt
mt::MethodTable
end
struct MethodMatchKey
sig # ::Type
limit::Int
MethodMatchKey(@nospecialize(sig), limit::Int) = new(sig, limit)
end
"""
struct CachedMethodTable <: MethodTableView
Overlays another method table view with an additional local fast path cache that
can respond to repeated, identical queries faster than the original method table.
"""
struct CachedMethodTable{T<:MethodTableView} <: MethodTableView
cache::IdDict{MethodMatchKey, Union{Nothing,MethodLookupResult}}
table::T
end
CachedMethodTable(table::T) where T = CachedMethodTable{T}(IdDict{MethodMatchKey, Union{Nothing,MethodLookupResult}}(), table)
"""
findall(sig::Type, view::MethodTableView; limit::Int=-1) ->
matches::MethodLookupResult or nothing
Find all methods in the given method table `view` that are applicable to the given signature `sig`.
If no applicable methods are found, an empty result is returned.
If the number of applicable methods exceeded the specified `limit`, `nothing` is returned.
Note that the default setting `limit=-1` does not limit the number of applicable methods.
`overlayed` indicates if any of the matching methods comes from an overlayed method table.
"""
findall(@nospecialize(sig::Type), table::InternalMethodTable; limit::Int=-1) =
_findall(sig, nothing, table.world, limit)
function findall(@nospecialize(sig::Type), table::OverlayMethodTable; limit::Int=-1)
result = _findall(sig, table.mt, table.world, limit)
result === nothing && return nothing
nr = length(result)
if nr ≥ 1 && result[nr].fully_covers
# no need to fall back to the internal method table
return result
end
# fall back to the internal method table
fallback_result = _findall(sig, nothing, table.world, limit)
fallback_result === nothing && return nothing
# merge the fallback match results with the internal method table
return MethodLookupResult(
vcat(result.matches, fallback_result.matches),
WorldRange(
max(result.valid_worlds.min_world, fallback_result.valid_worlds.min_world),
min(result.valid_worlds.max_world, fallback_result.valid_worlds.max_world)),
result.ambig | fallback_result.ambig)
end
function _findall(@nospecialize(sig::Type), mt::Union{Nothing,MethodTable}, world::UInt, limit::Int)
_min_val = RefValue{UInt}(typemin(UInt))
_max_val = RefValue{UInt}(typemax(UInt))
_ambig = RefValue{Int32}(0)
ms = _methods_by_ftype(sig, mt, limit, world, false, _min_val, _max_val, _ambig)
isa(ms, Vector) || return nothing
return MethodLookupResult(ms, WorldRange(_min_val[], _max_val[]), _ambig[] != 0)
end
function findall(@nospecialize(sig::Type), table::CachedMethodTable; limit::Int=-1)
if isconcretetype(sig)
# as for concrete types, we cache result at on the next level
return findall(sig, table.table; limit)
end
key = MethodMatchKey(sig, limit)
if haskey(table.cache, key)
return table.cache[key]
else
return table.cache[key] = findall(sig, table.table; limit)
end
end
"""
findsup(sig::Type, view::MethodTableView) ->
(match::Union{MethodMatch,Nothing}, valid_worlds::WorldRange, overlayed::Bool)
Find the (unique) method such that `sig <: match.method.sig`, while being more
specific than any other method with the same property. In other words, find the method
which is the least upper bound (supremum) under the specificity/subtype relation of
the queried `sig`nature. If `sig` is concrete, this is equivalent to asking for the method
that will be called given arguments whose types match the given signature.
Note that this query is also used to implement `invoke`.
Such a matching method `match` doesn't necessarily exist.
It is possible that no method is an upper bound of `sig`, or
it is possible that among the upper bounds, there is no least element.
In both cases `nothing` is returned.
`overlayed` indicates if any of the matching methods comes from an overlayed method table.
"""
findsup(@nospecialize(sig::Type), table::InternalMethodTable) =
_findsup(sig, nothing, table.world)
function findsup(@nospecialize(sig::Type), table::OverlayMethodTable)
match, valid_worlds = _findsup(sig, table.mt, table.world)
match !== nothing && return match, valid_worlds
# fall back to the internal method table
fallback_match, fallback_valid_worlds = _findsup(sig, nothing, table.world)
return (
fallback_match,
WorldRange(
max(valid_worlds.min_world, fallback_valid_worlds.min_world),
min(valid_worlds.max_world, fallback_valid_worlds.max_world)))
end
function _findsup(@nospecialize(sig::Type), mt::Union{Nothing,MethodTable}, world::UInt)
min_valid = RefValue{UInt}(typemin(UInt))
max_valid = RefValue{UInt}(typemax(UInt))
match = ccall(:jl_gf_invoke_lookup_worlds, Any, (Any, Any, UInt, Ptr{Csize_t}, Ptr{Csize_t}),
sig, mt, world, min_valid, max_valid)::Union{MethodMatch, Nothing}
valid_worlds = WorldRange(min_valid[], max_valid[])
return match, valid_worlds
end
# This query is not cached
findsup(@nospecialize(sig::Type), table::CachedMethodTable) = findsup(sig, table.table)