Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_ore/src/seq/slot.rs

21.2 KiB, 127 runs

created by r1870400018:17916, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! The placement layer: slots, how they divide, and how they order.
2//!
3//! A repository is an ordered set of slots, each claiming a run of content. The
4//! order is Fugue's -- slots form a left-child / right-child tree whose in-order
5//! traversal is the text -- with one departure: an origin names a content
6//! identifier rather than an element, and is resolved through the claim register
7//! at render time. That departure is the whole design, because it is what lets
8//! an insertion follow the content it was written against when a move takes that
9//! content elsewhere, into another file included.
10//!
11//! # One forest, and a file is a subtree
12//!
13//! There is one tree for the whole repository rather than one per file, and its
14//! root children are exactly the **seed** slots: one per file, claiming that
15//! file's origin anchor. A file is the subtree beneath its seed, so a slot's file
16//! is read off the tree rather than off the record, and a move between files
17//! needs no routing -- its destination anchor already names content in the file
18//! it lands in.
19//!
20//! Resolving origins induces a directed graph over slots, an edge from S to T
21//! when S's origin names content T owns. Where that graph is acyclic the order
22//! is a function of the operation set and nothing else. Where it is not --
23//! two moves whose destinations sit inside each other's sources, or a move whose
24//! destination sits inside its own source -- one edge is demoted to the splice
25//! that created the anchored content, which is strictly earlier in op order than
26//! anything in the cycle and so cannot be in it.
27//!
28//! Demotion is the answer for a cycle inside one file, and only for that. A cycle
29//! that crosses a file boundary is arbitrated instead, by the render, and
30//! [`Slots::cycles`] is what tells it where the cycles are.
31//!
32//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
33//! Anthropic Claude
34
35use crate::id::{
36 Anchor,
37 ContentId,
38 ContentRange,
39 OpId,
40 Side,
41};
42use crate::op::{
43 Op,
44 Placing,
45};
46use crate::seq::claim::Claims;
47use crate::seq::OpOrder;
48
49use oxedyne_fe2o3_core::prelude::*;
50
51use std::collections::{
52 BTreeMap,
53 BTreeSet,
54};
55use std::fmt;
56
57
58/// Which of a slot's two origins is meant.
59#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
60pub enum Origin {
61 Left, // what the slot follows
62 Right, // what the slot precedes
63}
64
65impl Origin {
66 pub const fn code(&self) -> u8 {
67 match self {
68 Self::Left => 0,
69 Self::Right => 1,
70 }
71 }
72
73 pub fn from_code(code: u8)
74 -> Outcome<Self>
75 {
76 match code {
77 0 => Ok(Self::Left),
78 1 => Ok(Self::Right),
79 other => Err(err!(
80 "An Origin code is 0 for Left or 1 for Right, got {}.", other;
81 Decode, Input, Invalid)),
82 }
83 }
84}
85
86impl fmt::Display for Origin {
87 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
88 match self {
89 Self::Left => write!(f, "left"),
90 Self::Right => write!(f, "right"),
91 }
92 }
93}
94
95
96/// One placed view of a run of content.
97///
98/// `sub` is the byte offset of this piece within everything its placing
99/// operation placed, which is what makes a split arithmetic: both halves keep
100/// the placing operation and take `sub` values derived from the split point, so
101/// nothing is minted and two replicas that split the same slot at different
102/// points compose.
103#[derive(Clone, Debug, Eq, PartialEq)]
104pub struct Slot {
105 pub place: OpId, // the operation that placed the slot
106 pub sub: u64, // byte offset within its placement
107 pub claim: ContentRange, // the content the slot shows
108 pub left: Option<Anchor>, // left origin as recorded
109 pub right: Option<Anchor>, // right origin as recorded
110 pub seed: bool, // a file's origin anchor, and a root child
111}
112
113impl Slot {
114 /// The key by which same-side siblings are ordered: op order of the placing
115 /// operation, then offset within that placement.
116 pub fn order_key(&self) -> (OpOrder, u64) {
117 (OpOrder::of(&self.place), self.sub)
118 }
119}
120
121
122/// Every slot an operation set places, divided at every anchor's cut point.
123#[derive(Clone, Debug, Default)]
124pub struct Slots {
125 slots: Vec<Slot>, // in placement and division order
126 by_place: BTreeMap<OpId, Vec<usize>>, // indices by placer, sorted by claim
127 prev: Vec<Option<usize>>, // the preceding piece of a placement
128 placed: usize, // slots placed before dividing
129}
130
131impl Slots {
132
133 /// Places one seed slot per file, one slot per splice and one per source run
134 /// of a move, then divides every slot at every anchor that falls strictly
135 /// inside its claim.
136 ///
137 /// Dividing at every anchor, whether or not the anchor is used, is what
138 /// makes the division a function of the operation set rather than of the
139 /// order the anchors arrived in.
140 pub fn place(ops: &[(OpId, &Op)])
141 -> Outcome<Self>
142 {
143 Self::place_without(ops, &BTreeSet::new())
144 }
145
146 /// Places the slots as [`Slots::place`] does, except that a move named in
147 /// `voided` places none.
148 ///
149 /// A voided move holds no claim either (see [`Claims::build_without`]), so no
150 /// origin can resolve to it and nothing is left behind by leaving its slots
151 /// out: the bytes render from whoever owns them now, which is where they were
152 /// before the move.
153 ///
154 /// **The cut points are still taken from every operation's origins, voided
155 /// ones included.** Division has to be a function of the operation set alone,
156 /// or two replicas that void at different moments would divide their slots
157 /// differently and diverge, and the whole point of the render is that they do
158 /// not.
159 pub fn place_without(ops: &[(OpId, &Op)], voided: &BTreeSet<OpId>)
160 -> Outcome<Self>
161 {
162 let mut slots: Vec<Slot> = Vec::new();
163 for (id, op) in ops {
164 if voided.contains(id) && op.is_move() {
165 continue;
166 }
167 match op {
168 Op::FileCreate { .. } => {
169 slots.push(Slot {
170 place: *id,
171 sub: 0,
172 claim: res!(ContentRange::new(*id, 0, 1)),
173 left: None,
174 right: None,
175 seed: true,
176 });
177 },
178 Op::Splice { left, right, insert, .. } => {
179 if insert.is_empty() {
180 continue;
181 }
182 slots.push(Slot {
183 place: *id,
184 sub: 0,
185 claim: res!(ContentRange::new(*id, 0, insert.len() as u64)),
186 left: *left,
187 right: *right,
188 seed: false,
189 });
190 },
191 Op::Move { src, left, right } => {
192 let mut sub = 0u64;
193 for r in src {
194 if r.is_empty() {
195 continue;
196 }
197 slots.push(Slot {
198 place: *id,
199 sub,
200 claim: *r,
201 left: *left,
202 right: *right,
203 seed: false,
204 });
205 sub += r.len();
206 }
207 },
208 // A forgotten operation keeps its place in the order exactly as
209 // it stood, so that what was anchored inside it is laid out where
210 // it always was; only the bytes are gone, and they are buried.
211 Op::Forgotten { placing: Placing::File } => {
212 slots.push(Slot {
213 place: *id,
214 sub: 0,
215 claim: res!(ContentRange::new(*id, 0, 1)),
216 left: None,
217 right: None,
218 seed: true,
219 });
220 },
221 Op::Forgotten { placing: Placing::Splice { left, right, len, .. } } => {
222 if *len == 0 {
223 continue;
224 }
225 slots.push(Slot {
226 place: *id,
227 sub: 0,
228 claim: res!(ContentRange::new(*id, 0, *len)),
229 left: *left,
230 right: *right,
231 seed: false,
232 });
233 },
234 _ => (),
235 }
236 }
237 let placed = slots.len();
238
239 // One cut point in content space per anchor, on the side the anchor
240 // binds to.
241 let mut cuts: BTreeMap<OpId, BTreeSet<u64>> = BTreeMap::new();
242 for (_, op) in ops {
243 let (l, r) = op.origins();
244 for a in [l, r].into_iter().flatten() {
245 let at = match a.side {
246 Side::Before => a.content.off,
247 Side::After => a.content.off + 1,
248 };
249 cuts.entry(a.content.op).or_default().insert(at);
250 }
251 }
252
253 let mut divided: Vec<Slot> = Vec::with_capacity(slots.len());
254 for slot in slots.drain(..) {
255 let mut from = slot.claim.from();
256 if let Some(set) = cuts.get(&slot.claim.op()) {
257 for cut in set.range((slot.claim.from() + 1)..slot.claim.to()) {
258 divided.push(Slot {
259 place: slot.place,
260 sub: slot.sub + (from - slot.claim.from()),
261 claim: res!(ContentRange::new(slot.claim.op(), from, *cut)),
262 left: slot.left,
263 right: slot.right,
264 seed: slot.seed,
265 });
266 from = *cut;
267 }
268 }
269 divided.push(Slot {
270 place: slot.place,
271 sub: slot.sub + (from - slot.claim.from()),
272 claim: res!(ContentRange::new(slot.claim.op(), from, slot.claim.to())),
273 left: slot.left,
274 right: slot.right,
275 seed: slot.seed,
276 });
277 }
278 let slots = divided;
279 let n = slots.len();
280
281 // An index for owner lookup, and the chain of pieces of one placement.
282 let mut by_place: BTreeMap<OpId, Vec<usize>> = BTreeMap::new();
283 for (i, slot) in slots.iter().enumerate() {
284 by_place.entry(slot.place).or_default().push(i);
285 }
286 let mut prev: Vec<Option<usize>> = vec![None; n];
287 for idxs in by_place.values_mut() {
288 idxs.sort_by_key(|i| (slots[*i].claim.op(), slots[*i].claim.from()));
289 let mut chain: Vec<usize> = idxs.clone();
290 chain.sort_by_key(|i| slots[*i].sub);
291 for pair in chain.windows(2) {
292 prev[pair[1]] = Some(pair[0]);
293 }
294 }
295
296 Ok(Self { slots, by_place, prev, placed })
297 }
298
299 /// The slots, in no particular order.
300 pub fn all(&self) -> &[Slot] {
301 &self.slots
302 }
303
304 pub fn get(&self, i: usize)
305 -> Outcome<&Slot>
306 {
307 match self.slots.get(i) {
308 Some(s) => Ok(s),
309 None => Err(err!(
310 "Slot {} does not exist; there are {}.", i, self.slots.len();
311 Bug, Index, Range)),
312 }
313 }
314
315 /// The number of slots after dividing.
316 pub fn len(&self) -> usize {
317 self.slots.len()
318 }
319
320 pub fn is_empty(&self) -> bool {
321 self.slots.is_empty()
322 }
323
324 /// The number of slots placed before dividing, which is one per splice and one
325 /// per source run of a move.
326 pub fn placed(&self) -> usize {
327 self.placed
328 }
329
330 /// How a flag raised against `(operation, offset)` finds the slot it is about,
331 /// the pair being what the flags name and what a reader can act on.
332 pub fn find(&self, place: &OpId, sub: u64)
333 -> Option<usize>
334 {
335 self.by_place.get(place)
336 .and_then(|idxs| idxs.iter().copied().find(|i| self.slots[*i].sub == sub))
337 }
338
339 /// The preceding piece of this placement, if this is not the first.
340 pub fn prev(&self, i: usize)
341 -> Option<usize>
342 {
343 self.prev.get(i).copied().flatten()
344 }
345
346 /// The slot that currently shows the named byte.
347 ///
348 /// With `demoted` set, the claim register is ignored and the slot placed by
349 /// the splice that created the byte is returned instead, which is the
350 /// fallback the cycle rule falls back to.
351 pub fn owner_slot(&self, cid: &ContentId, claims: &Claims, demoted: bool)
352 -> Outcome<usize>
353 {
354 let owner = if demoted { cid.op } else { claims.owner(cid) };
355 let idxs = match self.by_place.get(&owner) {
356 Some(v) => v,
357 None => return Err(err!(
358 "No slot placed by {} shows {}; the operation set is not causally \
359 complete.", owner, cid;
360 Invalid, Input, Missing)),
361 };
362 // The index is sorted by claimed content, so the slot covering the byte,
363 // if there is one, is the last whose claim starts at or before it.
364 let key = (cid.op, cid.off);
365 let pos = idxs.partition_point(
366 |i| (self.slots[*i].claim.op(), self.slots[*i].claim.from()) <= key);
367 if pos > 0 {
368 let i = idxs[pos - 1];
369 if self.slots[i].claim.contains(cid) {
370 return Ok(i);
371 }
372 }
373 Err(err!(
374 "The slots placed by {} do not cover {}, which they are recorded as \
375 showing.", owner, cid;
376 Bug, Missing))
377 }
378
379 /// Resolves a slot's two origins, honouring the demotion state.
380 ///
381 /// A left origin binds after a byte and a right origin before one. The
382 /// reverse is refused rather than guessed at: a left origin bound before a
383 /// byte would name the slot preceding that byte's owner, which is not
384 /// determinable without first knowing the order the origin is being used to
385 /// decide.
386 fn origins_of(&self, i: usize, claims: &Claims, dem: &[(bool, bool)])
387 -> Outcome<(Option<usize>, Option<usize>)>
388 {
389 let slot = res!(self.get(i));
390 let mut left = None;
391 let mut right = None;
392 if let Some(a) = slot.left {
393 if a.side != Side::After {
394 return Err(err!(
395 "The left origin {} binds before its byte; a left origin binds \
396 after one.", a;
397 Invalid, Input));
398 }
399 left = Some(res!(self.owner_slot(&a.content, claims, dem[i].0)));
400 }
401 if let Some(a) = slot.right {
402 if a.side != Side::Before {
403 return Err(err!(
404 "The right origin {} binds after its byte; a right origin binds \
405 before one.", a;
406 Invalid, Input));
407 }
408 right = Some(res!(self.owner_slot(&a.content, claims, dem[i].1)));
409 }
410 Ok((left, right))
411 }
412
413 /// The cycles of the anchor graph, before anything is demoted.
414 ///
415 /// The graph is the one [`Slots::order`] builds on its first pass, and a cycle
416 /// is a strongly connected component with more than one member, or one member
417 /// with an edge to itself. Each is returned in op order, and a slot that is not
418 /// on a cycle is in none of them.
419 ///
420 /// This is what the cross-file rule needs and demotion does not. Demotion asks
421 /// only which slot is blocked, and a blocked slot need not be on a cycle -- it
422 /// may merely sit downstream of one -- whereas a rule that voids a whole move
423 /// has to name the moves the cycle actually runs through.
424 pub fn cycles(&self, claims: &Claims)
425 -> Outcome<Vec<Vec<usize>>>
426 {
427 let n = self.slots.len();
428 let dem: Vec<(bool, bool)> = vec![(false, false); n];
429 let mut deps: Vec<Vec<usize>> = vec![Vec::new(); n];
430 for (i, dep) in deps.iter_mut().enumerate() {
431 if let Some(x) = self.prev(i) {
432 dep.push(x);
433 continue;
434 }
435 let (l, r) = res!(self.origins_of(i, claims, &dem));
436 for x in [l, r].into_iter().flatten() {
437 dep.push(x);
438 }
439 }
440 Ok(self.components(&deps))
441 }
442
443 /// The strongly connected components of a dependency graph that are cycles,
444 /// each sorted by op order, by Tarjan's algorithm run iteratively.
445 fn components(&self, deps: &[Vec<usize>]) -> Vec<Vec<usize>> {
446 let n = deps.len();
447 // Depth-first index and low link of each slot, and whether it is on the
448 // component stack.
449 let mut index: Vec<Option<usize>> = vec![None; n];
450 let mut low: Vec<usize> = vec![0; n];
451 let mut on: Vec<bool> = vec![false; n];
452 let mut stack: Vec<usize> = Vec::new();
453 let mut next = 0usize;
454 let mut out: Vec<Vec<usize>> = Vec::new();
455 // The explicit call stack: a slot, and how far through its dependencies the
456 // walk had got when it descended.
457 let mut work: Vec<(usize, usize)> = Vec::new();
458 for root in 0..n {
459 if index[root].is_some() {
460 continue;
461 }
462 work.push((root, 0));
463 while let Some((v, at)) = work.pop() {
464 if at == 0 {
465 index[v] = Some(next);
466 low[v] = next;
467 next += 1;
468 stack.push(v);
469 on[v] = true;
470 }
471 let mut descended = false;
472 for (k, w) in deps[v].iter().enumerate().skip(at) {
473 match index[*w] {
474 None => {
475 work.push((v, k + 1));
476 work.push((*w, 0));
477 descended = true;
478 break;
479 },
480 Some(seen) => {
481 if on[*w] {
482 low[v] = low[v].min(seen);
483 }
484 },
485 }
486 }
487 if descended {
488 continue;
489 }
490 if Some(low[v]) == index[v] {
491 let mut scc: Vec<usize> = Vec::new();
492 while let Some(w) = stack.pop() {
493 on[w] = false;
494 scc.push(w);
495 if w == v {
496 break;
497 }
498 }
499 if scc.len() > 1 || deps[v].contains(&v) {
500 scc.sort_by_key(|i| {
501 let (ord, sub) = self.slots[*i].order_key();
502 (ord, sub, *i)
503 });
504 out.push(scc);
505 }
506 }
507 // A finished slot hands its low link back to whoever descended into
508 // it, which is the entry now on top of the work stack.
509 if let Some((parent, _)) = work.last().copied() {
510 low[parent] = low[parent].min(low[v]);
511 }
512 }
513 }
514 out.sort_by_key(|scc| scc.first().copied().unwrap_or(0));
515 out
516 }
517
518 /// Orders the slots topologically over the anchor graph, breaking any cycle
519 /// by demotion.
520 ///
521 /// Cycles are broken one edge at a time: the blocked slot lowest in op order
522 /// has its left origin demoted to the creating splice, then its right, and
523 /// only then are the edges dropped. Each demotion strictly reduces the number
524 /// of cycle edges, because the fallback target precedes every slot in the
525 /// cycle in op order and so cannot be in it, which is why this terminates.
526 ///
527 /// The graph is rebuilt after each demotion, so the cost is the number of
528 /// demotions times the number of slots. Finding the strongly connected
529 /// components once and demoting every cycle's lowest edge in a single pass
530 /// would reach the same answer for less, and is the obvious thing to do when
531 /// this becomes the render's cost centre.
532 ///
533 /// **Every cycle this sees is inside one file.** A cycle that crosses a file
534 /// boundary is arbitrated before the order is asked for, by
535 /// [`crate::seq::Sequence::render_with`], and its losing moves are voided, so
536 /// by the time this runs no such cycle is left. Demoting an origin inside one
537 /// file lands a placement at a stale position, which is deterministic,
538 /// flagged and safe; demoting one across two would land it in the other file,
539 /// and that is the outcome the arbitration exists to prevent.
540 pub fn order(&self, claims: &Claims)
541 -> Outcome<Order>
542 {
543 let n = self.slots.len();
544 // Whether each origin of each slot has been demoted, and then dropped.
545 let mut dem: Vec<(bool, bool)> = vec![(false, false); n];
546 let mut cut: Vec<(bool, bool)> = vec![(false, false); n];
547 let mut demoted: Vec<(OpId, u64, Origin)> = Vec::new();
548 let mut dropped: Vec<(OpId, u64, Origin)> = Vec::new();
549
550 loop {
551 // Dependencies under the current demotion state. A slot that is not
552 // the first piece of its placement chains to its predecessor and
553 // resolves no origins of its own.
554 let mut deps: Vec<Vec<usize>> = vec![Vec::new(); n];
555 for i in 0..n {
556 if let Some(x) = self.prev(i) {
557 deps[i].push(x);
558 continue;
559 }
560 // A self-edge is a cycle of length one, which is what a move
561 // whose destination names content the move itself claims
562 // produces. It is left in so that the demotion rule sees it;
563 // unseen, it would detach the move's slots from the tree and
564 // lose their bytes.
565 let (l, r) = res!(self.origins_of(i, claims, &dem));
566 if let Some(x) = l {
567 if !cut[i].0 {
568 deps[i].push(x);
569 }
570 }
571 if let Some(x) = r {
572 if !cut[i].1 {
573 deps[i].push(x);
574 }
575 }
576 }
577
578 // Kahn's algorithm, ties broken by op order then offset within the
579 // placement, so the order is a function of the operation set.
580 let mut indeg: Vec<usize> = vec![0; n];
581 let mut rev: Vec<Vec<usize>> = vec![Vec::new(); n];
582 for i in 0..n {
583 indeg[i] = deps[i].len();
584 for d in &deps[i] {
585 rev[*d].push(i);
586 }
587 }
588 let mut ready: BTreeSet<(OpOrder, u64, usize)> = BTreeSet::new();
589 for i in 0..n {
590 if indeg[i] == 0 {
591 let (ord, sub) = self.slots[i].order_key();
592 ready.insert((ord, sub, i));
593 }
594 }
595 let mut order: Vec<usize> = Vec::with_capacity(n);
596 while let Some(key) = ready.iter().next().copied() {
597 ready.remove(&key);
598 let i = key.2;
599 order.push(i);
600 for j in &rev[i] {
601 indeg[*j] -= 1;
602 if indeg[*j] == 0 {
603 let (ord, sub) = self.slots[*j].order_key();
604 ready.insert((ord, sub, *j));
605 }
606 }
607 }
608
609 if order.len() == n {
610 let mut left = vec![None; n];
611 let mut right = vec![None; n];
612 for i in 0..n {
613 if self.prev(i).is_some() {
614 continue;
615 }
616 let (l, r) = res!(self.origins_of(i, claims, &dem));
617 left[i] = if cut[i].0 { None } else { l };
618 right[i] = if cut[i].1 { None } else { r };
619 }
620 return Ok(Order { order, left, right, demoted, dropped });
621 }
622
623 // A cycle remains. Demote the lowest blocked slot in op order.
624 let mut stuck: Vec<usize> = (0..n)
625 .filter(|i| indeg[*i] > 0 && self.prev(*i).is_none())
626 .collect();
627 stuck.sort_by_key(|i| {
628 let (ord, sub) = self.slots[*i].order_key();
629 (ord, sub, *i)
630 });
631 let victim = match stuck.first() {
632 Some(v) => *v,
633 None => return Err(err!(
634 "The topological sort stalled with no blocked slot, so a cycle \
635 runs through slots that chain within a placement."; Bug)),
636 };
637 let slot = &self.slots[victim];
638 if !dem[victim].0 && slot.left.is_some() {
639 dem[victim].0 = true;
640 demoted.push((slot.place, slot.sub, Origin::Left));
641 } else if !dem[victim].1 && slot.right.is_some() {
642 dem[victim].1 = true;
643 demoted.push((slot.place, slot.sub, Origin::Right));
644 } else if !cut[victim].0 && slot.left.is_some() {
645 cut[victim].0 = true;
646 dropped.push((slot.place, slot.sub, Origin::Left));
647 } else if !cut[victim].1 && slot.right.is_some() {
648 cut[victim].1 = true;
649 dropped.push((slot.place, slot.sub, Origin::Right));
650 } else {
651 return Err(err!(
652 "A cycle through the slot placed by {} at offset {} survives \
653 both demotion and dropping.", slot.place, slot.sub;
654 Bug));
655 }
656 }
657 }
658}
659
660
661/// A topological order over the anchor graph, with the origins it was resolved
662/// against.
663#[derive(Clone, Debug, Default, Eq, PartialEq)]
664pub struct Order {
665 pub order: Vec<usize>, // each after its origins
666 pub left: Vec<Option<usize>>, // resolved left origins
667 pub right: Vec<Option<usize>>, // resolved right origins
668 // Origins given up to break a cycle, named by placing operation, offset
669 // within that placement, and which of the two origins.
670 pub demoted: Vec<(OpId, u64, Origin)>, // demoted to the creating splice
671 pub dropped: Vec<(OpId, u64, Origin)>, // dropped where demotion failed
672}