#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

40.63

/base/ordering.jl

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

module Order


import ..@__MODULE__, ..parentmodule
const Base = parentmodule(@__MODULE__)
import .Base:
    AbstractVector, @propagate_inbounds, isless, identity, getindex, reverse,
    +, -, !, &, <, |

## notions of element ordering ##

export # not exported by Base
    Ordering, Forward, Reverse,
    By, Lt, Perm,
    ReverseOrdering, ForwardOrdering,
    DirectOrdering,
    lt, ord, ordtype

"""
    Base.Order.Ordering

Abstract type which represents a strict weak order on some set of elements. See
[`sort!`](@ref) for more.

Use [`Base.Order.lt`](@ref) to compare two elements according to the ordering.
"""
abstract type Ordering end

struct ForwardOrdering <: Ordering end

"""
    ReverseOrdering(fwd::Ordering=Forward)

A wrapper which reverses an ordering.

For a given `Ordering` `o`, the following holds for all  `a`, `b`:

    lt(ReverseOrdering(o), a, b) == lt(o, b, a)
"""
struct ReverseOrdering{Fwd<:Ordering} <: Ordering
    fwd::Fwd
end

ReverseOrdering(rev::ReverseOrdering) = rev.fwd
ReverseOrdering(fwd::Fwd) where {Fwd} = ReverseOrdering{Fwd}(fwd)
ReverseOrdering() = ReverseOrdering(ForwardOrdering())

"""
    reverse(o::Base.Ordering)

reverses ordering specified by `o`.

"""
reverse(o::Ordering) = ReverseOrdering(o)

const DirectOrdering = Union{ForwardOrdering,ReverseOrdering{ForwardOrdering}}

"""
    Base.Order.Forward

Default ordering according to [`isless`](@ref).
"""
const Forward = ForwardOrdering()

"""
    Base.Order.Reverse

Reverse ordering according to [`isless`](@ref).
"""
const Reverse = ReverseOrdering()

"""
    By(by, order::Ordering=Forward)

`Ordering` which applies `order` to elements after they have been transformed
by the function `by`.
"""
struct By{T, O} <: Ordering
    by::T
    order::O
end

# backwards compatibility with VERSION < v"1.5-"
By(by) = By(by, Forward)

"""
    Lt(lt)

`Ordering` that calls `lt(a, b)` to compare elements. `lt` must
obey the same rules as the `lt` parameter of [`sort!`](@ref).
"""
struct Lt{T} <: Ordering
    lt::T
end

"""
    Perm(order::Ordering, data::AbstractVector)

`Ordering` on the indices of `data` where `i` is less than `j` if `data[i]` is
less than `data[j]` according to `order`. In the case that `data[i]` and
`data[j]` are equal, `i` and `j` are compared by numeric value.
"""
struct Perm{O<:Ordering,V<:AbstractVector} <: Ordering
    order::O
    data::V
end

ReverseOrdering(by::By) = By(by.by, ReverseOrdering(by.order))
ReverseOrdering(perm::Perm) = Perm(ReverseOrdering(perm.order), perm.data)

"""
    lt(o::Ordering, a, b) -> Bool

Test whether `a` is less than `b` according to the ordering `o`.
"""
lt(o::ForwardOrdering,       a, b) = isless(a,b)
lt(o::ReverseOrdering,       a, b) = lt(o.fwd,b,a)
lt(o::By,                    a, b) = lt(o.order,o.by(a),o.by(b))
lt(o::Lt,                    a, b) = o.lt(a,b)

@propagate_inbounds function lt(p::Perm, a::Integer, b::Integer)
    da = p.data[a]
    db = p.data[b]
    (lt(p.order, da, db)::Bool) | (!(lt(p.order, db, da)::Bool) & (a < b))
end


_ord(lt::typeof(isless), by, order::Ordering)                         = _by(by, order)
_ord(lt::typeof(isless), by, order::ForwardOrdering)                  = _by(by, order)  # disambiguation
_ord(lt::typeof(isless), by, order::ReverseOrdering{ForwardOrdering}) = _by(by, order)  # disambiguation
_ord(lt,                 by, order::ForwardOrdering)                  = _by(by, Lt(lt))
_ord(lt,                 by, order::ReverseOrdering{ForwardOrdering}) = reverse(_by(by, Lt(lt)))
_ord(lt,                 by, order::Ordering) = error("Passing both lt= and order= arguments is ambiguous; please pass order=Forward or order=Reverse (or leave default)")
_by(by, order::Ordering) = By(by, order)
_by(::typeof(identity), order::Ordering) = order

"""
    ord(lt, by, rev::Union{Bool, Nothing}, order::Ordering=Forward)

Construct an [`Ordering`](@ref) object from the same arguments used by
[`sort!`](@ref).
Elements are first transformed by the function `by` (which may be
[`identity`](@ref)) and are then compared according to either the function `lt`
or an existing ordering `order`. `lt` should be [`isless`](@ref) or a function
that obeys the same rules as the `lt` parameter of [`sort!`](@ref). Finally,
the resulting order is reversed if `rev=true`.

Passing an `lt` other than `isless` along with an `order` other than
[`Base.Order.Forward`](@ref) or [`Base.Order.Reverse`](@ref) is not permitted,
otherwise all options are independent and can be used together in all possible
combinations.
"""
ord(lt, by, rev::Nothing, order::Ordering=Forward) = _ord(lt, by, order)

function ord(lt, by, rev::Bool, order::Ordering=Forward)
    o = _ord(lt, by, order)
    return rev ? ReverseOrdering(o) : o
end


# This function is not in use anywhere in Base but we observed
# use in sorting-related packages (#34719). It's probably best to move
# this functionality to those packages in the future; let's remind/force
# ourselves to deprecate this in v2.0.
# The following clause means `if VERSION < v"2.0-"` but it also works during
# bootstrap. For the same reason, we need to write `Int32` instead of `Cint`.
if ccall(:jl_ver_major, Int32, ()) < 2
    ordtype(o::ReverseOrdering, vs::AbstractArray) = ordtype(o.fwd, vs)
    ordtype(o::Perm,            vs::AbstractArray) = ordtype(o.order, o.data)
    # TODO: here, we really want the return type of o.by, without calling it
    ordtype(o::By,              vs::AbstractArray) = try typeof(o.by(vs[1])) catch; Any end
    ordtype(o::Ordering,        vs::AbstractArray) = eltype(vs)
end

end

1	# This file is a part of Julia. License is MIT: https://julialang.org/license
2
3	module Order
4
5
6	import ..@__MODULE__, ..parentmodule
7	const Base = parentmodule(@__MODULE__)
8	import .Base:
9	AbstractVector, @propagate_inbounds, isless, identity, getindex, reverse,
10	+, -, !, &, <, \|
11
12	## notions of element ordering ##
13
14	export # not exported by Base
15	Ordering, Forward, Reverse,
16	By, Lt, Perm,
17	ReverseOrdering, ForwardOrdering,
18	DirectOrdering,
19	lt, ord, ordtype
20
21	"""
22	Base.Order.Ordering
23
24	Abstract type which represents a strict weak order on some set of elements. See
25	[`sort!`](@ref) for more.
26
27	Use [`Base.Order.lt`](@ref) to compare two elements according to the ordering.
28	"""
29	abstract type Ordering end
30
31	struct ForwardOrdering <: Ordering end
32
33	"""
34	ReverseOrdering(fwd::Ordering=Forward)
35
36	A wrapper which reverses an ordering.
37
38	For a given `Ordering` `o`, the following holds for all `a`, `b`:
39
40	lt(ReverseOrdering(o), a, b) == lt(o, b, a)
41	"""
42	struct ReverseOrdering{Fwd<:Ordering} <: Ordering
43	fwd::Fwd
44	end
45
46	ReverseOrdering(rev::ReverseOrdering) = rev.fwd	×
47	ReverseOrdering(fwd::Fwd) where {Fwd} = ReverseOrdering{Fwd}(fwd)	×
48	ReverseOrdering() = ReverseOrdering(ForwardOrdering())	×
49
50	"""
51	reverse(o::Base.Ordering)
52
53	reverses ordering specified by `o`.
54
55	"""
56	reverse(o::Ordering) = ReverseOrdering(o)	×
57
58	const DirectOrdering = Union{ForwardOrdering,ReverseOrdering{ForwardOrdering}}
59
60	"""
61	Base.Order.Forward
62
63	Default ordering according to [`isless`](@ref).
64	"""
65	const Forward = ForwardOrdering()
66
67	"""
68	Base.Order.Reverse
69
70	Reverse ordering according to [`isless`](@ref).
71	"""
72	const Reverse = ReverseOrdering()
73
74	"""
75	By(by, order::Ordering=Forward)
76
77	`Ordering` which applies `order` to elements after they have been transformed
78	by the function `by`.
79	"""
80	struct By{T, O} <: Ordering
81	by::T	12,636✔
82	order::O
83	end
84
85	# backwards compatibility with VERSION < v"1.5-"
86	By(by) = By(by, Forward)	708✔
87
88	"""
89	Lt(lt)
90
91	`Ordering` that calls `lt(a, b)` to compare elements. `lt` must
92	obey the same rules as the `lt` parameter of [`sort!`](@ref).
93	"""
94	struct Lt{T} <: Ordering
95	lt::T	55✔
96	end
97
98	"""
99	Perm(order::Ordering, data::AbstractVector)
100
101	`Ordering` on the indices of `data` where `i` is less than `j` if `data[i]` is
102	less than `data[j]` according to `order`. In the case that `data[i]` and
103	`data[j]` are equal, `i` and `j` are compared by numeric value.
104	"""
105	struct Perm{O<:Ordering,V<:AbstractVector} <: Ordering
UNCOV 106	order::O	×
107	data::V
108	end
109
110	ReverseOrdering(by::By) = By(by.by, ReverseOrdering(by.order))	1✔
111	ReverseOrdering(perm::Perm) = Perm(ReverseOrdering(perm.order), perm.data)	×
112
113	"""
114	lt(o::Ordering, a, b) -> Bool
115
116	Test whether `a` is less than `b` according to the ordering `o`.
117	"""
118	lt(o::ForwardOrdering, a, b) = isless(a,b)	282,264✔
119	lt(o::ReverseOrdering, a, b) = lt(o.fwd,b,a)	3,000✔
120	lt(o::By, a, b) = lt(o.order,o.by(a),o.by(b))	199,146✔
121	lt(o::Lt, a, b) = o.lt(a,b)	419,760✔
122
123	@propagate_inbounds function lt(p::Perm, a::Integer, b::Integer)
UNCOV 124	da = p.data[a]	×
UNCOV 125	db = p.data[b]	×
UNCOV 126	(lt(p.order, da, db)::Bool) \| (!(lt(p.order, db, da)::Bool) & (a < b))	×
127	end
128
129
130	_ord(lt::typeof(isless), by, order::Ordering) = _by(by, order)	×
131	_ord(lt::typeof(isless), by, order::ForwardOrdering) = _by(by, order) # disambiguation	12,033✔
132	_ord(lt::typeof(isless), by, order::ReverseOrdering{ForwardOrdering}) = _by(by, order) # disambiguation	×
133	_ord(lt, by, order::ForwardOrdering) = _by(by, Lt(lt))	×
134	_ord(lt, by, order::ReverseOrdering{ForwardOrdering}) = reverse(_by(by, Lt(lt)))	×
135	_ord(lt, by, order::Ordering) = error("Passing both lt= and order= arguments is ambiguous; please pass order=Forward or order=Reverse (or leave default)")	×
136	_by(by, order::Ordering) = By(by, order)	11,927✔
137	_by(::typeof(identity), order::Ordering) = order	×
138
139	"""
140	ord(lt, by, rev::Union{Bool, Nothing}, order::Ordering=Forward)
141
142	Construct an [`Ordering`](@ref) object from the same arguments used by
143	[`sort!`](@ref).
144	Elements are first transformed by the function `by` (which may be
145	[`identity`](@ref)) and are then compared according to either the function `lt`
146	or an existing ordering `order`. `lt` should be [`isless`](@ref) or a function
147	that obeys the same rules as the `lt` parameter of [`sort!`](@ref). Finally,
148	the resulting order is reversed if `rev=true`.
149
150	Passing an `lt` other than `isless` along with an `order` other than
151	[`Base.Order.Forward`](@ref) or [`Base.Order.Reverse`](@ref) is not permitted,
152	otherwise all options are independent and can be used together in all possible
153	combinations.
154	"""
155	ord(lt, by, rev::Nothing, order::Ordering=Forward) = _ord(lt, by, order)	12,033✔
156
157	function ord(lt, by, rev::Bool, order::Ordering=Forward)
158	o = _ord(lt, by, order)	1✔
159	return rev ? ReverseOrdering(o) : o	1✔
160	end
161
162
163	# This function is not in use anywhere in Base but we observed
164	# use in sorting-related packages (#34719). It's probably best to move
165	# this functionality to those packages in the future; let's remind/force
166	# ourselves to deprecate this in v2.0.
167	# The following clause means `if VERSION < v"2.0-"` but it also works during
168	# bootstrap. For the same reason, we need to write `Int32` instead of `Cint`.
169	if ccall(:jl_ver_major, Int32, ()) < 2
170	ordtype(o::ReverseOrdering, vs::AbstractArray) = ordtype(o.fwd, vs)	×
171	ordtype(o::Perm, vs::AbstractArray) = ordtype(o.order, o.data)	×
172	# TODO: here, we really want the return type of o.by, without calling it
173	ordtype(o::By, vs::AbstractArray) = try typeof(o.by(vs[1])) catch; Any end	×
174	ordtype(o::Ordering, vs::AbstractArray) = eltype(vs)	×
175	end
176
177	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