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
//! Movement re-parenting over Rhapsody's derived coordinates.
extern crate alloc;
use alloc::vec::Vec;
use super::children;
use super::maintenance::placed_anchor;
use super::placement::Dot;
use super::{Anchor, Locus, Rhapsody};
use crate::metis::dot::RawDot;
pub(in crate::metis::rhapsody) enum PlacementEffect {
Unchanged,
/// `parent` is the destination anchor's coordinate (a payload seat, so
/// zero-capable); the ancestry coordinate funnels it to an identity.
Reparented {
dot: Dot,
parent: Option<RawDot>,
},
Parked(Vec<Dot>),
Repaired(Vec<Dot>),
}
pub(in crate::metis::rhapsody) struct PlacementTransition {
pub(in crate::metis::rhapsody) work: usize,
pub(in crate::metis::rhapsody) effect: PlacementEffect,
}
impl Rhapsody {
/// Re-places an already-woven dot at a new locus: the replay primitive
/// of the maintained recension (PRD 0022 R7), never reachable from the
/// record's own write paths (a recorded locus is testimony, minted
/// once; only the decision-layer replay re-places, and only on its own
/// derived copy). The dot keeps its identity, its visibility, and its
/// own children buckets; what moves is its membership in its anchor's
/// bucket and its reading region's slots.
///
/// The caller guarantees acyclicity (`to.anchor` is never inside the
/// dot's own reading region): the recension applies a move only after
/// its cycle verdict, and an unwind restores a locus that was once
/// lawfully applied. The hot transition (placed to placed, every
/// applied replay of a live move) dispatches to
/// [`splice_region`](Self::splice_region), fragment-grade; the
/// remaining transitions compose the existing maintenance paths in
/// the excision protocol's own order (detach the region from the
/// positional plane, replace the one inbound parent edge off the
/// child plane's tail verdict, retire nodes and slots, then park the
/// region unplaced or repair it through
/// [`record_locus`](Self::record_locus)'s own placement transition).
///
/// Returns the work performed, the caller's eager-parity charge: the
/// moved region's fragment count (a placed-to-placed move, at least
/// one) or its member count (the parking and repair transitions) PLUS
/// the old and new sibling buckets' widths, so the child plane's
/// vector shifts (the standing contested-bucket term) are priced into
/// any replay budget exactly like the plane operations themselves.
pub(in crate::metis::rhapsody) fn re_place(
&mut self,
dot: Dot,
to: Locus,
) -> PlacementTransition {
let old = self
.skeleton
.get(&dot)
.expect("a re-placement targets a woven dot");
if old == to {
return PlacementTransition {
work: 1,
effect: PlacementEffect::Unchanged,
};
}
let was_placed = !self.unplaced.contains(&dot);
// The placement transition, `record_locus`'s own rule, read before
// any state moves: the verdict depends only on the anchor's entry.
let placed_new = self.anchor_places(dot, to.anchor);
if was_placed && placed_new {
// The hot transition (every applied replay of a live move):
// fragment-grade, never per slot.
return PlacementTransition {
work: self.splice_region(dot, to),
effect: PlacementEffect::Reparented {
dot,
parent: to.anchor.dot(),
},
};
}
let region: Vec<Dot> = if was_placed {
self.collect_region(dot)
} else {
Vec::new()
};
debug_assert!(
to.anchor
.dot()
.and_then(|raw| Dot::try_from(raw).ok())
.is_none_or(|anchor| !region.contains(&anchor)),
"a re-placement never lands inside its own reading region"
);
if was_placed {
// The region leaves the placed planes entirely (it is about to
// park unplaced): the excision protocol's detach order,
// clearing each member's own edges so every region dot is an
// isolated single-dot segment and retires under the plane's
// own asserts.
for &member in ®ion {
let _ = self.thread.replace_region_end(member, None);
let _ = self.thread.replace_region_start(member, None);
}
}
let old = self
.skeleton
.remove(dot)
.expect("the probed entry is present");
let old_bucket_width = self
.children
.bucket(&self.skeleton, old.anchor)
.map_or(0, |bucket| bucket.len());
let tail_change = self.children.remove(&self.skeleton, old.anchor, dot);
if was_placed && let children::TailChange::Replaced(child) = tail_change {
let linked = match old.anchor {
Anchor::Origin => true,
Anchor::Before(parent) => self
.thread
.replace_region_start(placed_anchor(parent), child),
Anchor::After(parent) => {
self.thread.replace_region_end(placed_anchor(parent), child)
}
};
debug_assert!(linked, "a placed dot's parent has a region node");
}
if was_placed {
for &member in ®ion {
let removed_node = self.thread.remove_region_dot(member);
debug_assert!(removed_node, "every placed region member has a segment");
let removed_slot = self.thread.remove_slot(member);
debug_assert!(removed_slot, "every placed region member holds a slot");
}
}
let inserted = self.skeleton.insert(dot, to);
debug_assert!(inserted, "a just-removed entry re-inserts under the cap");
self.children.insert(&self.skeleton, to.anchor, dot);
let bucket_widths = old_bucket_width
+ self
.children
.bucket(&self.skeleton, to.anchor)
.map_or(0, |bucket| bucket.len());
let (work, effect) = match (was_placed, placed_new) {
(true, false) => {
// The region parks whole: every member's chain now runs
// through the dangling (or self-anchored) new placement.
for &member in ®ion {
let _ = self.unplaced.insert(member);
}
(region.len(), PlacementEffect::Parked(region))
}
(false, true) => {
let _ = self.unplaced.remove(&dot);
let repaired = self.repair_placement_from(dot);
let region_begin = self.walk_slot_position(dot, to.anchor);
self.thread_region(dot, region_begin);
self.register_region_edges(dot, to.anchor, &repaired);
let work = repaired.len();
(work, PlacementEffect::Repaired(repaired))
}
(false, false) => (1, PlacementEffect::Unchanged),
(true, true) => unreachable!("dispatched to the splice above"),
};
PlacementTransition {
work: bucket_widths + work,
effect,
}
}
/// The placed-to-placed re-placement, fragment-grade (the S204 splice,
/// PRD 0022 R7's recorded cure for the slot-granular residual): the
/// region's slots move through the order thread as whole fragments,
/// and the endpoint planes keep every interior edge, because segments
/// and last-child edges are dot-space state, independent of where the
/// region sits in the walk. Only the two boundary edges move: the old
/// parent's tail edge (the child plane's own verdict) and the new
/// parent's, when the dot lands as its bucket's tail. Cost:
/// `O(region fragments log document)` plus the two buckets' widths,
/// never the region's slots: the fragment index pays one map removal
/// and one reinsertion per carried fragment, with tree descent and
/// refresh work per touched leaf beside it (a leaf holds at most
/// eight fragments, and removal never rebalances, so touched leaves
/// are bounded by the fragments, not an eighth of them).
///
/// The caller guarantees acyclicity exactly as
/// [`re_place`](Self::re_place) documents; here that means the
/// destination anchor's slot sits outside the moved interval, which
/// the debug assert checks positionally.
pub(in crate::metis::rhapsody) fn splice_region(&mut self, dot: Dot, to: Locus) -> usize {
let start = self
.thread
.region_start(dot)
.expect("a placed dot has a region start");
let end = self
.thread
.region_end(dot)
.expect("a placed dot has a region end");
let region_begin = self.slot_of_placed(start);
let region_len = self.slot_of_placed(end) + 1 - region_begin;
#[cfg(debug_assertions)]
if let Some(anchor) = to.anchor.dot().and_then(|raw| Dot::try_from(raw).ok()) {
let at = self.slot_of_placed(anchor);
debug_assert!(
!(region_begin..region_begin + region_len).contains(&at),
"a re-placement never lands inside its own reading region"
);
}
let moved = self.thread.extract_range(region_begin, region_len);
let work = moved.fragments().max(1);
let old = self
.skeleton
.remove(dot)
.expect("the probed entry is present");
let old_bucket_width = self
.children
.bucket(&self.skeleton, old.anchor)
.map_or(0, |bucket| bucket.len());
let tail_change = self.children.remove(&self.skeleton, old.anchor, dot);
if let children::TailChange::Replaced(child) = tail_change {
let linked = match old.anchor {
Anchor::Origin => true,
Anchor::Before(parent) => self
.thread
.replace_region_start(placed_anchor(parent), child),
Anchor::After(parent) => {
self.thread.replace_region_end(placed_anchor(parent), child)
}
};
debug_assert!(linked, "a placed dot's parent has a region node");
}
let inserted = self.skeleton.insert(dot, to);
debug_assert!(inserted, "a just-removed entry re-inserts under the cap");
self.children.insert(&self.skeleton, to.anchor, dot);
let destination = self.walk_slot_position(dot, to.anchor);
self.thread.insert_fragments(destination, moved);
let bucket = self
.children
.bucket(&self.skeleton, to.anchor)
.expect("the dot was just bucketed under its anchor");
let new_bucket_width = bucket.len();
if bucket.last() == dot {
let linked = match to.anchor {
Anchor::Origin => true,
Anchor::Before(parent) => self
.thread
.replace_region_start(placed_anchor(parent), Some(dot)),
Anchor::After(parent) => self
.thread
.replace_region_end(placed_anchor(parent), Some(dot)),
};
debug_assert!(linked, "a placed anchor has a region node");
}
old_bucket_width + new_bucket_width + work
}
}