1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
//! Graph-agnostic keyed bookkeeping core for the reactive map family.
//!
//! The three `ReactiveMap` flavors ([`ReactiveMap`](crate::ReactiveMap),
//! [`ThreadSafeReactiveMap`](crate::ThreadSafeReactiveMap),
//! [`AsyncReactiveMap`](crate::AsyncReactiveMap)) differ in exactly two places:
//! which interior-mutability wrapper guards their state, and which graph they
//! mint entry nodes and signal cells on. Everything *between* those — the
//! present set, the authoritative key order, `position`, and the atomic-move
//! algebra — is the same code three times over.
//!
//! [`KeyedOrder`] is that middle. It is the same "pure core split from the
//! reactive cell" seam the rest of the crate uses (`MembershipCore`,
//! `LeaseCore`, `CircuitBreakerCore`, …), applied to the map family:
//!
//! - **no context** — it never mints, reads, or writes a reactive node;
//! - **no closure** — it stores handles, not factories, so it needs no
//! `Send + Sync` bound and cannot inherit one from a graph trait;
//! - **no interior mutability** — each flavor wraps it in its own `RefCell`
//! (single-threaded) or `Mutex` (`Send + Sync`).
//!
//! What it deliberately does *not* own is **reactivity** over that bookkeeping.
//! Membership and order invalidation is `ctx.set` on a flavor's own signal
//! cells, which is context-typed and therefore stays in each shell. A core that
//! owned reactivity too would have to fake it with polled version counters —
//! which is precisely the shape lazily-zig's map has, and precisely why its
//! `keys()`/`len()` register no dependency edge. So the mutators here **report
//! what changed** ([`Mutation`], [`Move`]) and let the shell decide which
//! signals to bump.
use std::collections::HashMap;
use std::hash::Hash;
/// What an insert/remove did to the key set, so the caller knows whether to bump
/// its membership + order signals.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum Mutation {
/// The key set changed (a key was added or removed). Bump membership *and*
/// order — an add/remove changes the ordered key list too.
Changed,
/// Nothing changed (insert of a present key, remove of an absent one). Bump
/// nothing: invalidating readers here would be a spurious wakeup.
Unchanged,
}
/// The outcome of an atomic ordered move.
///
/// Split three ways rather than two because "the key was present" and "the order
/// actually changed" are different questions: the public `move_*` methods return
/// the former, while only the latter may bump the order signal.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum Move {
/// The key (or the anchor) is not in the order — nothing to move.
Absent,
/// The key is already at the requested position. A no-op: do **not**
/// invalidate order readers.
Unchanged,
/// The key changed position. Bump the order signal — once. Membership is
/// untouched: a reorder does not change set identity, so `len` /
/// `contains_key` readers must stay cached.
Reordered,
}
impl Move {
/// Whether the move could be expressed at all — the `bool` the public
/// `move_to` / `move_before` / `move_after` return.
pub(crate) fn is_present(self) -> bool {
!matches!(self, Move::Absent)
}
/// Whether the order actually changed, i.e. whether to bump the order signal.
pub(crate) fn changed(self) -> bool {
matches!(self, Move::Reordered)
}
}
/// The present set plus its authoritative key order, with the move algebra.
///
/// `entries` and `order` are kept in lockstep: every key in `entries` appears
/// exactly once in `order` and vice versa. All mutators preserve that, including
/// on their failure paths — a partially-applied move that left a key in one and
/// not the other is the desync lazily-zig's `moveTo` can hit on allocator
/// failure.
pub(crate) struct KeyedOrder<K, H> {
/// Per-key node handles. Each entry is its own reactive node in the owning
/// graph; this core only stores the (`Copy`) handle.
entries: HashMap<K, H>,
/// Authoritative key list. Insertion-ordered until an atomic move reorders
/// it; the snapshot returned by `keys`.
order: Vec<K>,
}
impl<K, H> Default for KeyedOrder<K, H> {
fn default() -> Self {
Self {
entries: HashMap::new(),
order: Vec::new(),
}
}
}
impl<K, H> KeyedOrder<K, H>
where
K: Eq + Hash + Clone,
H: Copy,
{
/// An empty core.
pub(crate) fn new() -> Self {
Self::default()
}
/// The handle for `key`, if present.
pub(crate) fn get(&self, key: &K) -> Option<H> {
self.entries.get(key).copied()
}
/// Whether `key` is in the present set.
pub(crate) fn contains(&self, key: &K) -> bool {
self.entries.contains_key(key)
}
/// Insert `handle` at `key`, appending to the order. If `key` is already
/// present the existing handle is **kept** (first writer wins, so a key keeps
/// a stable node identity) and the caller's `handle` is discarded.
///
/// Returns the handle now bound to `key` and whether the key set grew.
pub(crate) fn insert(&mut self, key: K, handle: H) -> (H, Mutation) {
if let Some(existing) = self.entries.get(&key) {
return (*existing, Mutation::Unchanged);
}
self.entries.insert(key.clone(), handle);
self.order.push(key);
(handle, Mutation::Changed)
}
/// Remove `key` from both planes, returning its handle if it was present.
/// The caller is responsible for tearing the node down on its own graph.
pub(crate) fn remove(&mut self, key: &K) -> (Option<H>, Mutation) {
let Some(handle) = self.entries.remove(key) else {
return (None, Mutation::Unchanged);
};
self.order.retain(|k| k != key);
(Some(handle), Mutation::Changed)
}
/// Snapshot of the keys in their current order.
pub(crate) fn keys(&self) -> Vec<K> {
self.order.clone()
}
/// Number of present entries.
pub(crate) fn len(&self) -> usize {
self.order.len()
}
/// Current 0-based position of `key` in the order, or `None` if absent.
pub(crate) fn position(&self, key: &K) -> Option<usize> {
self.order.iter().position(|k| k == key)
}
/// Atomically move `key` to `index`.
///
/// The entry keeps the **same** handle, dependents, and lineage — unlike a
/// naive remove + re-mint, which reallocates the node and bumps membership
/// twice. `index` is clamped to `[0, len)`.
pub(crate) fn move_to(&mut self, key: &K, index: usize) -> Move {
let Some(from) = self.position(key) else {
return Move::Absent;
};
let to = index.min(self.order.len().saturating_sub(1));
if from == to {
return Move::Unchanged;
}
let k = self.order.remove(from);
self.order.insert(to, k);
Move::Reordered
}
/// Atomically move `key` to just before `anchor`. `Absent` if either key is
/// missing.
pub(crate) fn move_before(&mut self, key: &K, anchor: &K) -> Move {
let (Some(anchor_idx), Some(from)) = (self.position(anchor), self.position(key)) else {
return Move::Absent;
};
// Removing `key` first shifts `anchor` left by one when key precedes it.
let target = if from < anchor_idx {
anchor_idx - 1
} else {
anchor_idx
};
self.move_to(key, target)
}
/// Atomically move `key` to just after `anchor`. `Absent` if either key is
/// missing.
pub(crate) fn move_after(&mut self, key: &K, anchor: &K) -> Move {
let (Some(anchor_idx), Some(from)) = (self.position(anchor), self.position(key)) else {
return Move::Absent;
};
let target = if from <= anchor_idx {
anchor_idx
} else {
anchor_idx + 1
};
self.move_to(key, target)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn seeded(keys: &[&str]) -> KeyedOrder<String, u32> {
let mut core = KeyedOrder::new();
for (i, key) in keys.iter().enumerate() {
core.insert((*key).to_string(), i as u32);
}
core
}
fn k(s: &str) -> String {
s.to_string()
}
#[test]
fn insert_appends_and_reports_growth() {
let mut core = KeyedOrder::new();
assert_eq!(core.insert(k("a"), 1), (1, Mutation::Changed));
assert_eq!(core.insert(k("b"), 2), (2, Mutation::Changed));
assert_eq!(core.keys(), vec![k("a"), k("b")]);
assert_eq!(core.len(), 2);
}
#[test]
fn reinsert_keeps_the_original_handle_and_reports_no_change() {
let mut core = seeded(&["a"]);
// First writer wins: the key keeps a stable node identity, and the caller
// learns not to bump membership.
assert_eq!(core.insert(k("a"), 99), (0, Mutation::Unchanged));
assert_eq!(core.get(&k("a")), Some(0));
assert_eq!(core.keys(), vec![k("a")]);
}
#[test]
fn remove_clears_both_planes() {
let mut core = seeded(&["a", "b", "c"]);
let (handle, mutation) = core.remove(&k("b"));
assert_eq!((handle, mutation), (Some(1), Mutation::Changed));
assert_eq!(core.keys(), vec![k("a"), k("c")]);
assert!(!core.contains(&k("b")));
assert_eq!(core.position(&k("b")), None);
// Absent remove is inert.
assert_eq!(core.remove(&k("b")), (None, Mutation::Unchanged));
}
#[test]
fn move_to_reorders_and_clamps() {
let mut core = seeded(&["a", "b", "c", "d"]);
assert_eq!(core.move_to(&k("b"), 3), Move::Reordered);
assert_eq!(core.keys(), vec![k("a"), k("c"), k("d"), k("b")]);
// Out-of-range index clamps to the last slot rather than panicking.
assert_eq!(core.move_to(&k("a"), 99), Move::Reordered);
assert_eq!(core.keys(), vec![k("c"), k("d"), k("b"), k("a")]);
}
#[test]
fn move_to_same_position_is_unchanged_not_reordered() {
let mut core = seeded(&["a", "b", "c"]);
// The distinction the order signal depends on: a no-op move must not
// invalidate order readers.
assert_eq!(core.move_to(&k("b"), 1), Move::Unchanged);
assert!(core.move_to(&k("b"), 1).is_present());
assert!(!core.move_to(&k("b"), 1).changed());
assert_eq!(core.keys(), vec![k("a"), k("b"), k("c")]);
}
#[test]
fn move_absent_key_is_absent() {
let mut core = seeded(&["a"]);
assert_eq!(core.move_to(&k("zz"), 0), Move::Absent);
assert!(!core.move_to(&k("zz"), 0).is_present());
assert_eq!(core.move_before(&k("zz"), &k("a")), Move::Absent);
assert_eq!(core.move_before(&k("a"), &k("zz")), Move::Absent);
assert_eq!(core.move_after(&k("a"), &k("zz")), Move::Absent);
}
#[test]
fn move_before_lands_immediately_ahead_of_the_anchor_from_either_side() {
// Moving rightwards past the anchor.
let mut core = seeded(&["a", "b", "c", "d"]);
assert_eq!(core.move_before(&k("a"), &k("d")), Move::Reordered);
assert_eq!(core.keys(), vec![k("b"), k("c"), k("a"), k("d")]);
// Moving leftwards ahead of the anchor.
let mut core = seeded(&["a", "b", "c", "d"]);
assert_eq!(core.move_before(&k("d"), &k("a")), Move::Reordered);
assert_eq!(core.keys(), vec![k("d"), k("a"), k("b"), k("c")]);
}
#[test]
fn move_after_lands_immediately_behind_the_anchor_from_either_side() {
let mut core = seeded(&["a", "b", "c", "d"]);
assert_eq!(core.move_after(&k("a"), &k("c")), Move::Reordered);
assert_eq!(core.keys(), vec![k("b"), k("c"), k("a"), k("d")]);
let mut core = seeded(&["a", "b", "c", "d"]);
assert_eq!(core.move_after(&k("d"), &k("a")), Move::Reordered);
assert_eq!(core.keys(), vec![k("a"), k("d"), k("b"), k("c")]);
}
#[test]
fn move_relative_to_an_adjacent_anchor_is_a_no_op() {
let mut core = seeded(&["a", "b", "c"]);
assert_eq!(core.move_before(&k("a"), &k("b")), Move::Unchanged);
assert_eq!(core.move_after(&k("c"), &k("b")), Move::Unchanged);
assert_eq!(core.keys(), vec![k("a"), k("b"), k("c")]);
}
#[test]
fn entries_and_order_never_desync() {
let mut core = seeded(&["a", "b", "c", "d", "e"]);
core.move_to(&k("e"), 0);
core.remove(&k("c"));
core.move_before(&k("a"), &k("e"));
core.insert(k("f"), 5);
core.move_after(&k("b"), &k("f"));
let keys = core.keys();
assert_eq!(keys.len(), core.len());
for key in &keys {
assert!(core.contains(key), "`{key}` in order but not in entries");
assert!(core.position(key).is_some());
}
// And nothing in `entries` is missing from `order`.
for key in ["a", "b", "d", "e", "f"] {
assert!(
keys.contains(&k(key)),
"`{key}` in entries but not in order"
);
}
assert!(!core.contains(&k("c")));
}
}