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
//! Fragment-grade range extraction and insertion.
extern crate alloc;
use alloc::vec::Vec;
use super::{Dot, Extraction, FRAG_CAP, Fragment, LEAF_FRAGS, NIL, Node, NodeKind, OrderThread};
impl OrderThread {
/// The leaf holding slot-space `position` (strictly in range) and the
/// offset within it: the strict twin of
/// [`leaf_at_slot`](Self::leaf_at_slot), landing INSIDE the subtree
/// carrying the slot rather than at the end of its left neighbor,
/// which is what the splice paths need to find the fragment a
/// boundary opens.
fn leaf_at_slot_start(&self, position: usize) -> (u32, usize) {
debug_assert!(position < self.slot_len());
let mut id = self.root;
let mut remaining = position;
loop {
match &self.nodes[id as usize].kind {
NodeKind::Internal(children) => {
let mut next = None;
for &child in children {
let slots = self.nodes[child as usize].slots;
if remaining < slots {
next = Some(child);
break;
}
remaining -= slots;
}
id = next.expect("an in-range slot always lands");
}
NodeKind::Leaf(_) => return (id, remaining),
}
}
}
/// The fragment position at an exact fragment boundary `within` one
/// leaf's slot space (the caller has split any spanning fragment
/// first; a leaf-end boundary lands one past the last fragment).
const fn boundary_position(frags: &[Fragment], within: usize) -> usize {
let mut offset = within;
let mut at = 0;
while offset > 0 {
offset = offset
.checked_sub(frags[at].slots())
.expect("the caller established a fragment boundary");
at += 1;
}
at
}
/// Ensures a fragment boundary exists at slot-space `position`
/// (`0..=slot_len`): the fragment spanning it, if any, splits in
/// place, so slots `position - 1` and `position` never share a
/// fragment afterward. Layout only: no slot, visibility, or
/// aggregate moves (a leaf overflowing its fragment cap splits, sums
/// preserved).
fn split_fragment_boundary(&mut self, position: usize) {
if position == 0 || position >= self.slot_len() {
return;
}
let (leaf, within) = self.leaf_at_slot_start(position);
let NodeKind::Leaf(frags) = &mut self.nodes[leaf as usize].kind else {
unreachable!("slot descent returns leaves only");
};
let mut frag_position = 0;
let mut offset = within;
while offset >= frags[frag_position].slots() {
offset -= frags[frag_position].slots();
frag_position += 1;
}
if offset == 0 {
return;
}
let head = frags[frag_position];
let cut = u8::try_from(offset).expect("fragment offsets fit u8");
let tail = Fragment {
station: head.station,
base: head.base.saturating_add(u64::from(cut)),
len: head.len - cut,
visible: head.visible >> cut,
};
frags[frag_position] = Fragment {
visible: head.visible & ((1u64 << cut) - 1),
len: cut,
..head
};
frags.insert(frag_position + 1, tail);
let _ = self.index.insert(tail.base_dot(), leaf);
self.split_leaf_if_over(leaf);
}
/// Merges the two fragments meeting at slot-space `position` when
/// they are one chain (same station, consecutive dots, combined width
/// under the cap), including across a leaf boundary: the seam repair
/// that keeps splice churn (a move and its undo, an unwound replay)
/// from fragmenting the thread permanently. Layout only; tolerant of
/// a position that is not a fragment boundary (nothing to do).
fn coalesce_boundary(&mut self, position: usize) {
if position == 0 || position >= self.slot_len() {
return;
}
let (right_leaf, right_within) = self.leaf_at_slot_start(position);
let (right_at, right) = {
let NodeKind::Leaf(frags) = &self.nodes[right_leaf as usize].kind else {
unreachable!("slot descent returns leaves only");
};
let mut offset = right_within;
let mut at = 0;
loop {
if offset == 0 {
break (at, frags[at]);
}
let Some(rest) = offset.checked_sub(frags[at].slots()) else {
return; // the two slots already share a fragment
};
offset = rest;
at += 1;
}
};
let (left_leaf, left_at, left) = {
let (leaf, within) = self.leaf_at_slot_start(position - 1);
let NodeKind::Leaf(frags) = &self.nodes[leaf as usize].kind else {
unreachable!("slot descent returns leaves only");
};
let mut offset = within;
let mut at = 0;
while offset >= frags[at].slots() {
offset -= frags[at].slots();
at += 1;
}
debug_assert_eq!(
offset + 1,
frags[at].slots(),
"the right scan proved the boundary"
);
(leaf, at, frags[at])
};
if left.station != right.station
|| left.base.checked_add(u64::from(left.len)) != Some(right.base)
|| left.slots() + right.slots() > FRAG_CAP
{
return;
}
// The right fragment leaves its leaf first; a same-leaf left
// position stays valid because the right sits strictly after it.
{
let NodeKind::Leaf(frags) = &mut self.nodes[right_leaf as usize].kind else {
unreachable!("slot descent returns leaves only");
};
let _ = frags.remove(right_at);
}
let _ = self.index.remove(&right.base_dot());
let emptied = {
let NodeKind::Leaf(frags) = &self.nodes[right_leaf as usize].kind else {
unreachable!("slot descent returns leaves only");
};
frags.is_empty()
};
if emptied {
self.detach_empty(right_leaf);
} else {
self.refresh_to_root(right_leaf);
}
{
let NodeKind::Leaf(frags) = &mut self.nodes[left_leaf as usize].kind else {
unreachable!("slot descent returns leaves only");
};
let frag = &mut frags[left_at];
frag.visible |= right.visible << frag.len;
frag.len += right.len;
}
self.refresh_to_root(left_leaf);
}
/// Lifts the slot range `[from, from + len)` out of the thread as
/// whole fragments (boundary fragments split first), in walk order,
/// with their index entries removed: the detach half of the region
/// splice (PRD 0022 R7's fragment-grade re-placement). Emptied leaves
/// retire, the source junction re-coalesces, and the remaining
/// aggregates are exact on return.
/// `O(range fragments log document)`: one index removal per drained
/// fragment, with descent and refresh work per touched leaf beside
/// it (a leaf holds at most eight fragments, and removal never
/// rebalances).
pub(in crate::metis::rhapsody) fn extract_range(
&mut self,
from: usize,
len: usize,
) -> Extraction {
debug_assert!(from + len <= self.slot_len());
if len == 0 {
return Extraction { frags: Vec::new() };
}
self.split_fragment_boundary(from);
self.split_fragment_boundary(from + len);
let mut extracted: Vec<Fragment> = Vec::new();
let mut remaining = len;
while remaining > 0 {
let (leaf, within) = self.leaf_at_slot_start(from);
let drained: Vec<Fragment> = {
let NodeKind::Leaf(frags) = &mut self.nodes[leaf as usize].kind else {
unreachable!("slot descent returns leaves only");
};
let at = Self::boundary_position(frags, within);
let mut end = at;
let mut taken = 0usize;
while end < frags.len() && taken + frags[end].slots() <= remaining {
taken += frags[end].slots();
end += 1;
}
debug_assert!(end > at, "the boundary splits tile the range whole");
frags.drain(at..end).collect()
};
for frag in &drained {
let _ = self.index.remove(&frag.base_dot());
}
remaining -= drained.iter().map(Fragment::slots).sum::<usize>();
extracted.extend(drained);
let emptied = {
let NodeKind::Leaf(frags) = &self.nodes[leaf as usize].kind else {
unreachable!("slot descent returns leaves only");
};
frags.is_empty()
};
if emptied {
self.detach_empty(leaf);
} else {
self.refresh_to_root(leaf);
}
}
self.coalesce_boundary(from);
Extraction { frags: extracted }
}
/// Splices previously extracted fragments back in, their first slot
/// landing at slot-space `to` (post-extraction coordinates), re-homing
/// their index entries and re-coalescing both seams: the attach half
/// of the region splice. An emptied thread rebuilds from the carried
/// fragments (the whole document moved).
/// `O(carried fragments log document)`: the carried fragments
/// partition into final leaves directly (the destination leaf fills
/// to its cap, the rest chunk into fresh leaves attached in walk
/// order, the destination's own tail re-homed once at the end), so
/// each index entry is written exactly once and no leaf ever
/// overfills into a repartition.
pub(in crate::metis::rhapsody) fn insert_fragments(
&mut self,
to: usize,
extraction: Extraction,
) {
let Extraction { frags: moved } = extraction;
if moved.is_empty() {
return;
}
let landed: usize = moved.iter().map(Fragment::slots).sum();
if self.root == NIL {
debug_assert_eq!(to, 0, "an emptied thread re-enters at the front");
self.build_from_fragments(&moved);
return;
}
debug_assert!(to <= self.slot_len());
self.split_fragment_boundary(to);
let (leaf, within) = self.leaf_at_slot(to);
// The small splice fits in place (the returned-region and
// single-fragment shapes): splice into the leaf's own row, at
// most one carried entry per fragment and no restructuring.
{
let NodeKind::Leaf(frags) = &mut self.nodes[leaf as usize].kind else {
unreachable!("slot descent returns leaves only");
};
if frags.len() + moved.len() <= LEAF_FRAGS {
let at = Self::boundary_position(frags, within);
let tail: Vec<Fragment> = frags.split_off(at);
let bases: Vec<Dot> = moved.iter().map(Fragment::base_dot).collect();
frags.extend(moved);
frags.extend(tail);
for dot in bases {
let _ = self.index.insert(dot, leaf);
}
self.refresh_to_root(leaf);
self.coalesce_boundary(to);
self.coalesce_boundary(to + landed);
return;
}
}
// The bulk splice partitions into final leaves directly: the
// destination leaf keeps its head and fills to its cap from the
// carried run, the remainder chunks into fresh leaves attached in
// walk order, and the leaf's own detached tail lands last, so
// each index entry is written exactly once and no leaf ever
// overfills into a repartition (the review's `O(F log F)`
// finding, answered structurally).
let (tail, fill): (Vec<Fragment>, Vec<Fragment>) = {
let NodeKind::Leaf(frags) = &mut self.nodes[leaf as usize].kind else {
unreachable!("slot descent returns leaves only");
};
let at = Self::boundary_position(frags, within);
let tail = frags.split_off(at);
let room = LEAF_FRAGS - frags.len();
let mut carried = moved;
let rest = carried.split_off(carried.len().min(room));
frags.extend(carried.iter().copied());
(tail, rest)
};
for frag in {
let NodeKind::Leaf(frags) = &self.nodes[leaf as usize].kind else {
unreachable!("slot descent returns leaves only");
};
frags.clone()
} {
let _ = self.index.insert(frag.base_dot(), leaf);
}
self.refresh(leaf);
let mut previous = leaf;
let mut pending: Vec<Fragment> = fill;
pending.extend(tail);
for chunk in pending.chunks(LEAF_FRAGS) {
let taken = chunk.to_vec();
let bases: Vec<Dot> = taken.iter().map(Fragment::base_dot).collect();
let sibling = self.alloc(Node {
parent: NIL,
slots: 0,
visible: 0,
kind: NodeKind::Leaf(taken),
});
for dot in bases {
let _ = self.index.insert(dot, sibling);
}
self.refresh(sibling);
self.attach_after(previous, sibling);
self.refresh_to_root(sibling);
previous = sibling;
}
self.refresh_to_root(leaf);
self.coalesce_boundary(to);
self.coalesce_boundary(to + landed);
}
}