#38002

Committed 06 Feb 2025 06:14AM UTC coverage: 20.322% (-2.4%) from 22.722%

Build # #38002

Build Type

push

local

Committed by

web-flow

Commit Message

bpart: Fully switch to partitioned semantics (#57253)

This is the final PR in the binding partitions series (modulo bugs and
tweaks), i.e. it closes #54654 and thus closes #40399, which was the
original design sketch.

This thus activates the full designed semantics for binding partitions,
in particular allowing safe replacement of const bindings. It in
particular allows struct redefinitions. This thus closes
timholy/Revise.jl#18 and also closes #38584.

The biggest semantic change here is probably that this gets rid of the
notion of "resolvedness" of a binding. Previously, a lot of the behavior
of our implementation depended on when bindings were "resolved", which
could happen at basically an arbitrary point (in the compiler, in REPL
completion, in a different thread), making a lot of the semantics around
bindings ill- or at least implementation-defined. There are several
related issues in the bugtracker, so this closes #14055 closes #44604
closes #46354 closes #30277

It is also the last step to close #24569.
It also supports bindings for undef->defined transitions and thus closes
#53958 closes #54733 - however, this is not activated yet for
performance reasons and may need some further optimization.

Since resolvedness no longer exists, we need to replace it with some
hopefully more well-defined semantics. I will describe the semantics
below, but before I do I will make two notes:

1. There are a number of cases where these semantics will behave
slightly differently than the old semantics absent some other task going
around resolving random bindings.
2. The new behavior (except for the replacement stuff) was generally
permissible under the old semantics if the bindings happened to be
resolved at the right time.

With all that said, there are essentially three "strengths" of bindings:

1. Implicit Bindings: Anything implicitly obtained from `using Mod`, "no
binding", plus slightly more exotic corner cases around conflicts

2. Weakly declared bindin... (continued)

Run Details

11 of 111 new or added lines in 7 files covered. (9.91%)

1273 existing lines in 68 files now uncovered.

9908 of 48755 relevant lines covered (20.32%)

105126.48 hits per line

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

4.83

/base/invalidation.jl

# This file is a part of Julia. License is MIT: https://julialang.org/license

struct GlobalRefIterator
    mod::Module
end
IteratorSize(::Type{GlobalRefIterator}) = SizeUnknown()
globalrefs(mod::Module) = GlobalRefIterator(mod)

function iterate(gri::GlobalRefIterator, i = 1)
    m = gri.mod
    table = ccall(:jl_module_get_bindings, Ref{SimpleVector}, (Any,), m)
    i > length(table) && return nothing
    b = table[i]
    b === nothing && return iterate(gri, i+1)
    return ((b::Core.Binding).globalref, i+1)
end

const TYPE_TYPE_MT = Type.body.name.mt
const NONFUNCTION_MT = Core.MethodTable.name.mt
function foreach_module_mtable(visit, m::Module, world::UInt)
    for gb in globalrefs(m)
        binding = gb.binding
        bpart = lookup_binding_partition(world, binding)
        if is_defined_const_binding(binding_kind(bpart))
            v = partition_restriction(bpart)
            uw = unwrap_unionall(v)
            name = gb.name
            if isa(uw, DataType)
                tn = uw.name
                if tn.module === m && tn.name === name && tn.wrapper === v && isdefined(tn, :mt)
                    # this is the original/primary binding for the type (name/wrapper)
                    mt = tn.mt
                    if mt !== nothing && mt !== TYPE_TYPE_MT && mt !== NONFUNCTION_MT
                        @assert mt.module === m
                        visit(mt) || return false
                    end
                end
            elseif isa(v, Core.MethodTable) && v.module === m && v.name === name
                # this is probably an external method table here, so let's
                # assume so as there is no way to precisely distinguish them
                visit(v) || return false
            end
        end
    end
    return true
end

function foreachgr(visit, src::CodeInfo)
    stmts = src.code
    for i = 1:length(stmts)
        stmt = stmts[i]
        isa(stmt, GlobalRef) && visit(stmt)
        for ur in Compiler.userefs(stmt)
            arg = ur[]
            isa(arg, GlobalRef) && visit(arg)
        end
    end
end

function anygr(visit, src::CodeInfo)
    stmts = src.code
    for i = 1:length(stmts)
        stmt = stmts[i]
        if isa(stmt, GlobalRef)
            visit(stmt) && return true
            continue
        end
        for ur in Compiler.userefs(stmt)
            arg = ur[]
            isa(arg, GlobalRef) && visit(arg) && return true
        end
    end
    return false
end

function should_invalidate_code_for_globalref(gr::GlobalRef, src::CodeInfo)
    isgr(g::GlobalRef) = gr.mod == g.mod && gr.name === g.name
    isgr(g) = false
    return anygr(isgr, src)
end

function scan_edge_list(ci::Core.CodeInstance, binding::Core.Binding)
    isdefined(ci, :edges) || return false
    edges = ci.edges
    i = 1
    while i <= length(edges)
        if isassigned(edges, i) && edges[i] === binding
            return true
        end
        i += 1
    end
    return false
end

function invalidate_method_for_globalref!(gr::GlobalRef, method::Method, invalidated_bpart::Core.BindingPartition, new_max_world::UInt)
    invalidate_all = false
    binding = convert(Core.Binding, gr)
    if isdefined(method, :source)
        src = _uncompressed_ir(method)
        old_stmts = src.code
        invalidate_all = should_invalidate_code_for_globalref(gr, src)
    end
    for mi in specializations(method)
        isdefined(mi, :cache) || continue
        ci = mi.cache
        while true
            if ci.max_world > new_max_world && (invalidate_all || scan_edge_list(ci, binding))
                ccall(:jl_invalidate_code_instance, Cvoid, (Any, UInt), ci, new_max_world)
            end
            isdefined(ci, :next) || break
            ci = ci.next
        end
    end
end

const BINDING_FLAG_EXPORTP = 0x2

function invalidate_code_for_globalref!(b::Core.Binding, invalidated_bpart::Core.BindingPartition, new_bpart::Union{Core.BindingPartition, Nothing}, new_max_world::UInt)
    gr = b.globalref
    if is_some_guard(binding_kind(invalidated_bpart))
        # TODO: We may want to invalidate for these anyway, since they have performance implications
        return
    end
    foreach_module_mtable(gr.mod, new_max_world) do mt::Core.MethodTable
        for method in MethodList(mt)
            invalidate_method_for_globalref!(gr, method, invalidated_bpart, new_max_world)
        end
        return true
    end
    if isdefined(b, :backedges)
        for edge in b.backedges
            if isa(edge, CodeInstance)
                ccall(:jl_invalidate_code_instance, Cvoid, (Any, UInt), edge, new_max_world)
            elseif isa(edge, Core.Binding)
                isdefined(edge, :partitions) || continue
                latest_bpart = edge.partitions
                latest_bpart.max_world == typemax(UInt) || continue
                is_some_imported(binding_kind(latest_bpart)) || continue
                partition_restriction(latest_bpart) === b || continue
                invalidate_code_for_globalref!(edge, latest_bpart, nothing, new_max_world)
            else
                invalidate_method_for_globalref!(gr, edge::Method, invalidated_bpart, new_max_world)
            end
        end
    end
    if (b.flags & BINDING_FLAG_EXPORTP) != 0
        # This binding was exported - we need to check all modules that `using` us to see if they
        # have an implicit binding to us.
        usings_backedges = ccall(:jl_get_module_usings_backedges, Any, (Any,), gr.mod)
        if usings_backedges !== nothing
            for user in usings_backedges::Vector{Any}
                user_binding = ccall(:jl_get_module_binding_or_nothing, Any, (Any, Any), user, gr.name)
                user_binding === nothing && continue
                isdefined(user_binding, :partitions) || continue
                latest_bpart = user_binding.partitions
                latest_bpart.max_world == typemax(UInt) || continue
                is_some_imported(binding_kind(latest_bpart)) || continue
                partition_restriction(latest_bpart) === b || continue
                invalidate_code_for_globalref!(convert(Core.Binding, user_binding), latest_bpart, nothing, new_max_world)
            end
        end
    end
end
invalidate_code_for_globalref!(gr::GlobalRef, invalidated_bpart::Core.BindingPartition, new_bpart::Core.BindingPartition, new_max_world::UInt) =
    invalidate_code_for_globalref!(convert(Core.Binding, gr), invalidated_bpart, new_bpart, new_max_world)

gr_needs_backedge_in_module(gr::GlobalRef, mod::Module) = gr.mod !== mod

# N.B.: This needs to match jl_maybe_add_binding_backedge
function maybe_add_binding_backedge!(b::Core.Binding, edge::Union{Method, CodeInstance})
    method = isa(edge, Method) ? edge : edge.def.def::Method
    gr_needs_backedge_in_module(b.globalref, method.module) || return
    if !isdefined(b, :backedges)
        b.backedges = Any[]
    end
    !isempty(b.backedges) && b.backedges[end] === edge && return
    push!(b.backedges, edge)
end

function binding_was_invalidated(b::Core.Binding)
    # At least one partition is required for invalidation
    !isdefined(b, :partitions) && return false
    b.partitions.min_world > unsafe_load(cglobal(:jl_require_world, UInt))
end

function scan_new_method!(methods_with_invalidated_source::IdSet{Method}, method::Method)
    isdefined(method, :source) || return
    src = _uncompressed_ir(method)
    mod = method.module
    foreachgr(src) do gr::GlobalRef
        b = convert(Core.Binding, gr)
        binding_was_invalidated(b) && push!(methods_with_invalidated_source, method)
        maybe_add_binding_backedge!(b, method)
    end
end

function scan_new_methods(extext_methods::Vector{Any}, internal_methods::Vector{Any})
    methods_with_invalidated_source = IdSet{Method}()
    for method in internal_methods
        if isa(method, Method)
           scan_new_method!(methods_with_invalidated_source, method)
        end
    end
    for tme::Core.TypeMapEntry in extext_methods
        scan_new_method!(methods_with_invalidated_source, tme.func::Method)
    end
    return methods_with_invalidated_source
end

1	# This file is a part of Julia. License is MIT: https://julialang.org/license
2
3	struct GlobalRefIterator
4	mod::Module
5	end
6	IteratorSize(::Type{GlobalRefIterator}) = SizeUnknown()	×
7	globalrefs(mod::Module) = GlobalRefIterator(mod)	×
8
9	function iterate(gri::GlobalRefIterator, i = 1)	×
10	m = gri.mod	×
11	table = ccall(:jl_module_get_bindings, Ref{SimpleVector}, (Any,), m)	×
12	i > length(table) && return nothing	×
13	b = table[i]	×
14	b === nothing && return iterate(gri, i+1)	×
15	return ((b::Core.Binding).globalref, i+1)	×
16	end
17
18	const TYPE_TYPE_MT = Type.body.name.mt
19	const NONFUNCTION_MT = Core.MethodTable.name.mt
20	function foreach_module_mtable(visit, m::Module, world::UInt)	×
21	for gb in globalrefs(m)	×
22	binding = gb.binding	×
23	bpart = lookup_binding_partition(world, binding)	×
24	if is_defined_const_binding(binding_kind(bpart))	×
25	v = partition_restriction(bpart)	×
26	uw = unwrap_unionall(v)	×
27	name = gb.name	×
28	if isa(uw, DataType)	×
29	tn = uw.name	×
30	if tn.module === m && tn.name === name && tn.wrapper === v && isdefined(tn, :mt)	×
31	# this is the original/primary binding for the type (name/wrapper)
32	mt = tn.mt	×
33	if mt !== nothing && mt !== TYPE_TYPE_MT && mt !== NONFUNCTION_MT	×
34	@assert mt.module === m	×
35	visit(mt) \|\| return false	×
36	end
37	end
38	elseif isa(v, Core.MethodTable) && v.module === m && v.name === name	×
39	# this is probably an external method table here, so let's
40	# assume so as there is no way to precisely distinguish them
41	visit(v) \|\| return false	×
42	end
43	end
44	end	×
45	return true	×
46	end
47
UNCOV 48	function foreachgr(visit, src::CodeInfo)	×
UNCOV 49	stmts = src.code	×
UNCOV 50	for i = 1:length(stmts)	×
UNCOV 51	stmt = stmts[i]	×
UNCOV 52	isa(stmt, GlobalRef) && visit(stmt)	×
UNCOV 53	for ur in Compiler.userefs(stmt)	×
UNCOV 54	arg = ur[]	×
UNCOV 55	isa(arg, GlobalRef) && visit(arg)	×
UNCOV 56	end	×
UNCOV 57	end	×
58	end
59
60	function anygr(visit, src::CodeInfo)	×
61	stmts = src.code	×
62	for i = 1:length(stmts)	×
63	stmt = stmts[i]	×
64	if isa(stmt, GlobalRef)	×
65	visit(stmt) && return true	×
66	continue	×
67	end
68	for ur in Compiler.userefs(stmt)	×
69	arg = ur[]	×
70	isa(arg, GlobalRef) && visit(arg) && return true	×
71	end	×
72	end	×
73	return false	×
74	end
75
76	function should_invalidate_code_for_globalref(gr::GlobalRef, src::CodeInfo)	×
77	isgr(g::GlobalRef) = gr.mod == g.mod && gr.name === g.name	×
78	isgr(g) = false	×
79	return anygr(isgr, src)	×
80	end
81
82	function scan_edge_list(ci::Core.CodeInstance, binding::Core.Binding)	×
83	isdefined(ci, :edges) \|\| return false	×
84	edges = ci.edges	×
85	i = 1	×
86	while i <= length(edges)	×
87	if isassigned(edges, i) && edges[i] === binding	×
88	return true	×
89	end
90	i += 1	×
91	end	×
92	return false	×
93	end
94
95	function invalidate_method_for_globalref!(gr::GlobalRef, method::Method, invalidated_bpart::Core.BindingPartition, new_max_world::UInt)	×
96	invalidate_all = false	×
97	binding = convert(Core.Binding, gr)	×
98	if isdefined(method, :source)	×
99	src = _uncompressed_ir(method)	×
100	old_stmts = src.code	×
101	invalidate_all = should_invalidate_code_for_globalref(gr, src)	×
102	end
103	for mi in specializations(method)	×
104	isdefined(mi, :cache) \|\| continue	×
105	ci = mi.cache	×
106	while true	×
107	if ci.max_world > new_max_world && (invalidate_all \|\| scan_edge_list(ci, binding))	×
108	ccall(:jl_invalidate_code_instance, Cvoid, (Any, UInt), ci, new_max_world)	×
109	end
110	isdefined(ci, :next) \|\| break	×
111	ci = ci.next	×
112	end	×
113	end	×
114	end
115
116	const BINDING_FLAG_EXPORTP = 0x2
117
NEW 118	function invalidate_code_for_globalref!(b::Core.Binding, invalidated_bpart::Core.BindingPartition, new_bpart::Union{Core.BindingPartition, Nothing}, new_max_world::UInt)	×
NEW 119	gr = b.globalref	×
NEW 120	if is_some_guard(binding_kind(invalidated_bpart))	×
121	# TODO: We may want to invalidate for these anyway, since they have performance implications
NEW 122	return	×
123	end
NEW 124	foreach_module_mtable(gr.mod, new_max_world) do mt::Core.MethodTable	×
NEW 125	for method in MethodList(mt)	×
NEW 126	invalidate_method_for_globalref!(gr, method, invalidated_bpart, new_max_world)	×
NEW 127	end	×
NEW 128	return true	×
129	end
NEW 130	if isdefined(b, :backedges)	×
NEW 131	for edge in b.backedges	×
NEW 132	if isa(edge, CodeInstance)	×
NEW 133	ccall(:jl_invalidate_code_instance, Cvoid, (Any, UInt), edge, new_max_world)	×
NEW 134	elseif isa(edge, Core.Binding)	×
NEW 135	isdefined(edge, :partitions) \|\| continue	×
NEW 136	latest_bpart = edge.partitions	×
NEW 137	latest_bpart.max_world == typemax(UInt) \|\| continue	×
NEW 138	is_some_imported(binding_kind(latest_bpart)) \|\| continue	×
NEW 139	partition_restriction(latest_bpart) === b \|\| continue	×
NEW 140	invalidate_code_for_globalref!(edge, latest_bpart, nothing, new_max_world)	×
141	else
NEW 142	invalidate_method_for_globalref!(gr, edge::Method, invalidated_bpart, new_max_world)	×
143	end
144	end	×
145	end
NEW 146	if (b.flags & BINDING_FLAG_EXPORTP) != 0	×
147	# This binding was exported - we need to check all modules that `using` us to see if they
148	# have an implicit binding to us.
NEW 149	usings_backedges = ccall(:jl_get_module_usings_backedges, Any, (Any,), gr.mod)	×
NEW 150	if usings_backedges !== nothing	×
NEW 151	for user in usings_backedges::Vector{Any}	×
NEW 152	user_binding = ccall(:jl_get_module_binding_or_nothing, Any, (Any, Any), user, gr.name)	×
NEW 153	user_binding === nothing && continue	×
NEW 154	isdefined(user_binding, :partitions) \|\| continue	×
NEW 155	latest_bpart = user_binding.partitions	×
NEW 156	latest_bpart.max_world == typemax(UInt) \|\| continue	×
NEW 157	is_some_imported(binding_kind(latest_bpart)) \|\| continue	×
NEW 158	partition_restriction(latest_bpart) === b \|\| continue	×
NEW 159	invalidate_code_for_globalref!(convert(Core.Binding, user_binding), latest_bpart, nothing, new_max_world)	×
UNCOV 160	end	×
161	end
162	end
163	end
NEW 164	invalidate_code_for_globalref!(gr::GlobalRef, invalidated_bpart::Core.BindingPartition, new_bpart::Core.BindingPartition, new_max_world::UInt) =	×
165	invalidate_code_for_globalref!(convert(Core.Binding, gr), invalidated_bpart, new_bpart, new_max_world)
166
167	gr_needs_backedge_in_module(gr::GlobalRef, mod::Module) = gr.mod !== mod	116✔
168
169	# N.B.: This needs to match jl_maybe_add_binding_backedge
170	function maybe_add_binding_backedge!(b::Core.Binding, edge::Union{Method, CodeInstance})	116✔
171	method = isa(edge, Method) ? edge : edge.def.def::Method	232✔
172	gr_needs_backedge_in_module(b.globalref, method.module) \|\| return	168✔
173	if !isdefined(b, :backedges)	64✔
UNCOV 174	b.backedges = Any[]	×
175	end
176	!isempty(b.backedges) && b.backedges[end] === edge && return	64✔
177	push!(b.backedges, edge)	64✔
178	end
179
180	function binding_was_invalidated(b::Core.Binding)
181	# At least one partition is required for invalidation
UNCOV 182	!isdefined(b, :partitions) && return false	×
UNCOV 183	b.partitions.min_world > unsafe_load(cglobal(:jl_require_world, UInt))	×
184	end
185
186	function scan_new_method!(methods_with_invalidated_source::IdSet{Method}, method::Method)
UNCOV 187	isdefined(method, :source) \|\| return	×
UNCOV 188	src = _uncompressed_ir(method)	×
189	mod = method.module	×
UNCOV 190	foreachgr(src) do gr::GlobalRef	×
UNCOV 191	b = convert(Core.Binding, gr)	×
UNCOV 192	binding_was_invalidated(b) && push!(methods_with_invalidated_source, method)	×
UNCOV 193	maybe_add_binding_backedge!(b, method)	×
194	end
195	end
196
UNCOV 197	function scan_new_methods(extext_methods::Vector{Any}, internal_methods::Vector{Any})	×
UNCOV 198	methods_with_invalidated_source = IdSet{Method}()	×
UNCOV 199	for method in internal_methods	×
UNCOV 200	if isa(method, Method)	×
UNCOV 201	scan_new_method!(methods_with_invalidated_source, method)	×
202	end
UNCOV 203	end	×
UNCOV 204	for tme::Core.TypeMapEntry in extext_methods	×
UNCOV 205	scan_new_method!(methods_with_invalidated_source, tme.func::Method)	×
UNCOV 206	end	×
UNCOV 207	return methods_with_invalidated_source	×
208	end

JuliaLang / julia / #38002

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