1508

Committed 18 Apr 2026 06:48AM UTC coverage: 77.696% (-0.2%) from 77.907%

Build # 1508

Build Type

push

buildkite

Committed by

web-flow

Commit Message

compiler: Filter dominated original methods in overlay matching (#61581)

When merging overlay and base method match results in `findall(sig,
::OverlayMethodTable)`, base methods whose signature is fully covered by
any of matching overlay methods' signatures are now filtered out.

Previously, both the overlay and base methods with the same signature
appeared in the results. This caused type inference to union their
return types even though the overlay should take dispatch priority.

While this is a general inference correctness improvement that makes
inference's emulation of overlay method selection at runtime more
"correct", it might be worth explaining the concrete need that motivates
this change:

Currently, inference for code like `[(x::Vector{Vector{Int}})...;]`
unexpectedly infers `Union{Vector{Int},Vector{Any}}` instead of
`Vector{Int}`, causing type instability isseus as reported in
aviatesk/JET.jl#413.
The root cause of this type instability is the existence of the fallback
method `vcat() = Any[]`.
To fix this, I initially attempted to remove the `vcat()` method
(JuliaLang/julia#47628), but that turned out to be a considerably
breaking change, so I concluded it was not viable to proceed in that
direction as of Julia v1 time.
I also considered alternative approaches: 1.) changing the lowering of
`[x...;]` to produce a primitive for `vcat` that would allow inference
to work correctly in such cases, and 2.) adding a typed required 1st
argument to other `vcat` methods so that dispatch to `vcat()` would not
be considered — but both of those also proved impractical for various
reasons (primarily because the complexity they introduce is too high).
Removing the fallback method definitions for `vcat()` and `hcat()`
themselves would be the simplest and most elegant fix, but that would
have to wait for the release of Julia v2.

Therefore, rather than fixing this type instability on the Julia base
side, I believe the least invasive solution is to define,... (continued)

Coverage Stats

0 of 5 new or added lines in 1 file covered. (0.0%)

471 existing lines in 19 files now uncovered.

65259 of 83993 relevant lines covered (77.7%)

23119906.18 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

73.58

/Compiler/src/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

abstract type MethodTableView end

"""
    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,
    # filtering out base methods that are fully covered by overlay methods
    overlay_matches = result.matches
    filtered = filter(fallback_result.matches) do base_match::MethodMatch
        dominated = any(overlay_matches) do overlay_match::MethodMatch
            base_match.method.sig <: overlay_match.method.sig
        end
        return !dominated
    end
    return MethodLookupResult(
        vcat(overlay_matches, filtered),
        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)

1	# This file is a part of Julia. License is MIT: https://julialang.org/license
2
3	struct MethodLookupResult
4	# Really Vector{Core.MethodMatch}, but it's easier to represent this as
5	# and work with Vector{Any} on the C side.
6	matches::Vector{Any}	1,172,028✔
7	valid_worlds::WorldRange
8	ambig::Bool
9	end
10	length(result::MethodLookupResult) = length(result.matches)	1,924,861✔
11	function iterate(result::MethodLookupResult, args...)
12	r = iterate(result.matches, args...)	2,247,984✔
13	r === nothing && return nothing	2,247,984✔
14	match, state = r	453,932✔
15	return (match::MethodMatch, state)	1,739,928✔
16	end
17	getindex(result::MethodLookupResult, idx::Int) = getindex(result.matches, idx)::MethodMatch	1,460,697✔
18
19	abstract type MethodTableView end
20
21	"""
22	struct InternalMethodTable <: MethodTableView
23
24	A struct representing the state of the internal method table at a
25	particular world age.
26	"""
27	struct InternalMethodTable <: MethodTableView
28	world::UInt	954,978✔
29	end
30
31	"""
32	struct OverlayMethodTable <: MethodTableView
33
34	Overlays the internal method table such that specific queries can be redirected to an
35	external table, e.g., to override existing method.
36	"""
37	struct OverlayMethodTable <: MethodTableView
38	world::UInt	13,560✔
39	mt::MethodTable
40	end
41
42	struct MethodMatchKey
43	sig # ::Type
44	limit::Int
45	MethodMatchKey(@nospecialize(sig), limit::Int) = new(sig, limit)	85,969✔
46	end
47
48	"""
49	struct CachedMethodTable <: MethodTableView
50
51	Overlays another method table view with an additional local fast path cache that
52	can respond to repeated, identical queries faster than the original method table.
53	"""
54	struct CachedMethodTable{T<:MethodTableView} <: MethodTableView
55	cache::IdDict{MethodMatchKey, Union{Nothing,MethodLookupResult}}	2,454✔
56	table::T
57	end
58	CachedMethodTable(table::T) where T = CachedMethodTable{T}(IdDict{MethodMatchKey, Union{Nothing,MethodLookupResult}}(), table)	2,454✔
59
60	"""
61	findall(sig::Type, view::MethodTableView; limit::Int=-1) ->
62	matches::MethodLookupResult or nothing
63
64	Find all methods in the given method table `view` that are applicable to the given signature `sig`.
65	If no applicable methods are found, an empty result is returned.
66	If the number of applicable methods exceeded the specified `limit`, `nothing` is returned.
67	Note that the default setting `limit=-1` does not limit the number of applicable methods.
68	`overlayed` indicates if any of the matching methods comes from an overlayed method table.
69	"""
70	findall(@nospecialize(sig::Type), table::InternalMethodTable; limit::Int=-1) =	2,381,048✔
71	_findall(sig, nothing, table.world, limit)
72
73	function findall(@nospecialize(sig::Type), table::OverlayMethodTable; limit::Int=-1)	13,470✔
74	result = _findall(sig, table.mt, table.world, limit)	×
75	result === nothing && return nothing	×
76	nr = length(result)	×
77	if nr ≥ 1 && result[nr].fully_covers	×
78	# no need to fall back to the internal method table
79	return result	×
80	end
81	# fall back to the internal method table
82	fallback_result = _findall(sig, nothing, table.world, limit)	×
83	fallback_result === nothing && return nothing	×
84	# merge the fallback match results with the internal method table,
85	# filtering out base methods that are fully covered by overlay methods
NEW 86	overlay_matches = result.matches	×
NEW 87	filtered = filter(fallback_result.matches) do base_match::MethodMatch	×
NEW 88	dominated = any(overlay_matches) do overlay_match::MethodMatch	×
NEW 89	base_match.method.sig <: overlay_match.method.sig	×
90	end
NEW 91	return !dominated	×
92	end
UNCOV 93	return MethodLookupResult(	×
94	vcat(overlay_matches, filtered),
95	WorldRange(
96	max(result.valid_worlds.min_world, fallback_result.valid_worlds.min_world),
97	min(result.valid_worlds.max_world, fallback_result.valid_worlds.max_world)),
98	result.ambig \| fallback_result.ambig)
99	end
100
101	function _findall(@nospecialize(sig::Type), mt::Union{Nothing,MethodTable}, world::UInt, limit::Int)
102	_min_val = RefValue{UInt}(typemin(UInt))	1,181,261✔
103	_max_val = RefValue{UInt}(typemax(UInt))	1,181,261✔
104	_ambig = RefValue{Int32}(0)	1,181,261✔
105	ms = _methods_by_ftype(sig, mt, limit, world, false, _min_val, _max_val, _ambig)	1,181,261✔
106	isa(ms, Vector) \|\| return nothing	1,190,524✔
107	return MethodLookupResult(ms, WorldRange(_min_val[], _max_val[]), _ambig[] != 0)	1,171,998✔
108	end
109
110	function findall(@nospecialize(sig::Type), table::CachedMethodTable; limit::Int=-1)	1,125,001✔
111	if isconcretetype(sig)	237,389✔
112	# as for concrete types, we cache result at on the next level
113	return findall(sig, table.table; limit)	151,420✔
114	end
115	key = MethodMatchKey(sig, limit)	85,969✔
116	if haskey(table.cache, key)	128,525✔
117	return table.cache[key]	42,556✔
118	else
119	return table.cache[key] = findall(sig, table.table; limit)	43,413✔
120	end
121	end
122
123	"""
124	findsup(sig::Type, view::MethodTableView) ->
125	(match::Union{MethodMatch,Nothing}, valid_worlds::WorldRange, overlayed::Bool)
126
127	Find the (unique) method such that `sig <: match.method.sig`, while being more
128	specific than any other method with the same property. In other words, find the method
129	which is the least upper bound (supremum) under the specificity/subtype relation of
130	the queried `sig`nature. If `sig` is concrete, this is equivalent to asking for the method
131	that will be called given arguments whose types match the given signature.
132	Note that this query is also used to implement `invoke`.
133
134	Such a matching method `match` doesn't necessarily exist.
135	It is possible that no method is an upper bound of `sig`, or
136	it is possible that among the upper bounds, there is no least element.
137	In both cases `nothing` is returned.
138
139	`overlayed` indicates if any of the matching methods comes from an overlayed method table.
140	"""
141	findsup(@nospecialize(sig::Type), table::InternalMethodTable) =	2,332✔
142	_findsup(sig, nothing, table.world)
143
144	function findsup(@nospecialize(sig::Type), table::OverlayMethodTable)	×
145	match, valid_worlds = _findsup(sig, table.mt, table.world)	51✔
146	match !== nothing && return match, valid_worlds	51✔
147	# fall back to the internal method table
148	fallback_match, fallback_valid_worlds = _findsup(sig, nothing, table.world)	45✔
149	return (	45✔
150	fallback_match,
151	WorldRange(
152	max(valid_worlds.min_world, fallback_valid_worlds.min_world),
153	min(valid_worlds.max_world, fallback_valid_worlds.max_world)))
154	end
155
156	function _findsup(@nospecialize(sig::Type), mt::Union{Nothing,MethodTable}, world::UInt)	169✔
157	min_valid = RefValue{UInt}(typemin(UInt))	2,666✔
158	max_valid = RefValue{UInt}(typemax(UInt))	2,666✔
159	match = ccall(:jl_gf_invoke_lookup_worlds, Any, (Any, Any, UInt, Ptr{Csize_t}, Ptr{Csize_t}),	2,666✔
160	sig, mt, world, min_valid, max_valid)::Union{MethodMatch, Nothing}
161	valid_worlds = WorldRange(min_valid[], max_valid[])	2,666✔
162	return match, valid_worlds	2,203✔
163	end
164
165	# This query is not cached
166	findsup(@nospecialize(sig::Type), table::CachedMethodTable) = findsup(sig, table.table)	28✔

JuliaLang / julia / 1508

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous