Oregami
Repositories/oxedyne/ore

oxedyne/ore/oracle/src/doc.rs

24.7 KiB, 1 run

created by r2848102244:77, 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 convergence oracle proper: an in-memory transcription of design note
2//! section 4, plus the section 4.3 alternative from the field note.
3//!
4//! Everything here is deliberately naive. Applying an operation is pure
5//! accumulation; the whole of the derived state -- claims, tombstones, slot
6//! splitting, anchor resolution, Fugue ordering -- is recomputed from the
7//! operation set on every render, which is the arrangement design note section
8//! 2.7 licenses.
9
10use crate::id::{
11 Anchor,
12 ContentId,
13 ContentRange,
14 OpId,
15 Side,
16};
17use crate::op::Op;
18
19use std::collections::{
20 BTreeMap,
21 BTreeSet,
22 HashMap,
23 HashSet,
24};
25
26use oxedyne_fe2o3_core::prelude::*;
27
28/// Which move mechanism the render uses.
29#[derive(Clone, Copy, PartialEq, Eq, Debug)]
30pub enum Mode {
31 /// Design note section 4.4: a per-byte last-writer-wins claim register.
32 /// Overlapping concurrent moves tear at the overlap boundary.
33 ClaimRegister,
34 /// Field note section 4.3, arbitrated: the moved region is treated as one
35 /// element, so a move that overlaps a higher-op-order move cannot exist as
36 /// an element at all and is discarded whole.
37 SplitBeforeMove,
38 /// Field note section 4.3, unarbitrated: each move keeps its own element
39 /// and both apply. Retained only to demonstrate what it does.
40 SplitBeforeMoveNaive,
41}
42
43/// What the renderer does when a slot's two origins are no longer adjacent,
44/// which is a state the published Fugue rule cannot reach and a move can.
45#[derive(Clone, Copy, PartialEq, Eq, Debug)]
46pub enum Bind {
47 /// The design note as written: Fugue's parent rule, applied to whatever the
48 /// two anchors now resolve to. When the right origin is not in the left
49 /// origin's right subtree the node becomes a right child of the left
50 /// origin, which places it after that origin's whole existing subtree.
51 LeftBias,
52 /// The repair: when the two origins are no longer adjacent, re-run Fugue's
53 /// parent rule against the left origin's current in-order successor, so
54 /// that the node lands immediately after its left origin.
55 Successor,
56}
57
58/// Everything the renderer noticed that the design note says should be flagged.
59#[derive(Clone, Default, Debug)]
60pub struct Flags {
61 /// Moves whose source is no longer wholly owned by them (section 6.2).
62 pub torn: Vec<OpId>,
63 /// Moves discarded whole by `SplitBeforeMove` arbitration.
64 pub invalidated: Vec<OpId>,
65 /// Anchors demoted to their creating splice by section 5.4's rule.
66 pub demoted: Vec<(OpId, u32)>,
67 /// Anchors dropped entirely because demotion did not break the cycle.
68 pub dropped: Vec<(OpId, u32)>,
69 /// Bytes rendered more than once.
70 pub duplicated: usize,
71}
72
73/// Measurements taken during a render.
74#[derive(Clone, Default, Debug)]
75pub struct Stats {
76 /// Operations in the set.
77 pub ops: usize,
78 /// Slots before anchor-driven splitting.
79 pub slots_placed: usize,
80 /// Slots after anchor-driven splitting.
81 pub slots_split: usize,
82 /// Entries in the naive per-byte claim register.
83 pub claim_entries: usize,
84 /// Entries in the naive per-byte tombstone set.
85 pub dead_entries: usize,
86 /// Total bytes held in atoms.
87 pub atom_bytes: usize,
88 /// Deepest path in the Fugue tree.
89 pub max_depth: u32,
90 /// Bytes one slot occupies in this prototype's layout.
91 pub slot_struct: usize,
92 /// Tombstone entries once coalesced into intervals, as section 4.5
93 /// specifies but this prototype deliberately does not implement.
94 pub dead_intervals: usize,
95 /// Claim entries once coalesced into intervals, as section 4.4 specifies.
96 pub claim_intervals: usize,
97}
98
99/// One slot as the renderer finally saw it, for debugging only.
100#[derive(Clone, Debug)]
101pub struct PieceInfo {
102 /// Placing operation.
103 pub place_op: OpId,
104 /// Sub-offset within the placement.
105 pub sub: u32,
106 /// The content the slot claims.
107 pub claim: ContentRange,
108 /// Bytes the slot actually rendered.
109 pub emitted: usize,
110 /// Whether the slot was reached by the traversal.
111 pub visited: bool,
112}
113
114/// The result of a render.
115#[derive(Clone, Debug)]
116pub struct Render {
117 /// The rendered bytes.
118 pub bytes: Vec<u8>,
119 /// The content id of each rendered byte, in the same order.
120 pub prov: Vec<ContentId>,
121 /// Measurements.
122 pub stats: Stats,
123 /// Flags raised.
124 pub flags: Flags,
125 /// Every slot, for debugging only.
126 pub pieces: Vec<PieceInfo>,
127}
128
129impl Render {
130 /// The rendered bytes as a lossy string, for test messages.
131 pub fn text(&self) -> String {
132 String::from_utf8_lossy(&self.bytes).into_owned()
133 }
134}
135
136/// A slot, after splitting. `sub` is the byte offset of this piece within its
137/// placing operation's total placed span, which makes splits arithmetic and
138/// mints nothing (section 4.1).
139#[derive(Clone, Debug)]
140struct Piece {
141 place_op: OpId,
142 sub: u32,
143 claim: ContentRange,
144 left: Anchor,
145 right: Anchor,
146}
147
148/// The document: an unordered set of operations and nothing else.
149#[derive(Clone, Debug)]
150pub struct Doc {
151 ops: Vec<Op>,
152 seen: HashSet<OpId>,
153 mode: Mode,
154 bind: Bind,
155}
156
157impl Doc {
158 /// Creates an empty document in the given move mode, with the design note's
159 /// own anchor binding.
160 pub fn new(mode: Mode) -> Self {
161 Self { ops: Vec::new(), seen: HashSet::new(), mode, bind: Bind::LeftBias }
162 }
163
164 /// Creates an empty document with an explicit anchor binding rule.
165 pub fn with_bind(mode: Mode, bind: Bind) -> Self {
166 Self { ops: Vec::new(), seen: HashSet::new(), mode, bind }
167 }
168
169 /// The move mode.
170 pub fn mode(&self) -> Mode {
171 self.mode
172 }
173
174 /// The anchor binding rule.
175 pub fn bind(&self) -> Bind {
176 self.bind
177 }
178
179 /// Applies an operation. Idempotent, and order-independent by
180 /// construction: the state is the set of operations.
181 pub fn apply(&mut self, op: Op) {
182 if self.seen.insert(op.id()) {
183 self.ops.push(op);
184 }
185 }
186
187 /// The operations applied so far, in arrival order.
188 pub fn ops(&self) -> &[Op] {
189 &self.ops
190 }
191
192 /// Whether the operation has been applied.
193 pub fn has(&self, id: &OpId) -> bool {
194 self.seen.contains(id)
195 }
196
197 /// The identities of every operation applied.
198 pub fn seen(&self) -> Vec<OpId> {
199 let mut v: Vec<OpId> = self.seen.iter().copied().collect();
200 v.sort();
201 v
202 }
203
204 /// Replaces the operation vector, used by tests that shuffle it to check
205 /// that the render does not depend on arrival order.
206 pub fn set_ops(&mut self, ops: Vec<Op>) {
207 self.seen = ops.iter().map(|o| o.id()).collect();
208 self.ops = ops;
209 }
210
211 /// The greatest Lamport counter observed, for minting the next operation.
212 pub fn max_counter(&self) -> u64 {
213 self.ops.iter().map(|o| o.id().counter).max().unwrap_or(0)
214 }
215
216 /// Renders the file.
217 pub fn render(&self) -> Outcome<Render> {
218 // 1. Operations in op order.
219 let mut ops: Vec<&Op> = self.ops.iter().collect();
220 ops.sort_by_key(|o| o.id());
221
222 // 2. Atoms and tombstones.
223 let mut atoms: BTreeMap<OpId, Vec<u8>> = BTreeMap::new();
224 let mut dead: HashSet<ContentId> = HashSet::new();
225 for op in &ops {
226 if let Op::Splice { id, remove, insert, .. } = op {
227 if !insert.is_empty() {
228 atoms.insert(*id, insert.clone());
229 }
230 for r in remove {
231 for cid in r.ids() {
232 dead.insert(cid);
233 }
234 }
235 }
236 }
237
238 // 3. Which moves are permitted to write claims.
239 let live_moves = res!(self.live_moves(&ops));
240
241 // 4. The naive per-byte claim register. Vectors are kept sorted; the
242 // last entry is the op-order winner.
243 let mut claims: HashMap<ContentId, Vec<OpId>> = HashMap::new();
244 for op in &ops {
245 if let Op::Move { id, src, .. } = op {
246 if !live_moves.contains(id) {
247 continue;
248 }
249 for r in src {
250 if !atoms.contains_key(&r.op) {
251 return Err(err!(
252 "Move {} names content {} of an unknown atom.",
253 id, r; Invalid, Input));
254 }
255 for cid in r.ids() {
256 let e = claims.entry(cid).or_default();
257 match self.mode {
258 Mode::SplitBeforeMoveNaive => {
259 e.push(*id);
260 },
261 _ => {
262 e.clear();
263 e.push(*id);
264 },
265 }
266 }
267 }
268 }
269 }
270
271 // 5. Slots, one per splice and one per source range of a move.
272 let mut pieces: Vec<Piece> = Vec::new();
273 for op in &ops {
274 match op {
275 Op::Splice { id, left, right, insert, .. } => {
276 if insert.is_empty() {
277 continue;
278 }
279 pieces.push(Piece {
280 place_op: *id,
281 sub: 0,
282 claim: res!(ContentRange::new(*id, 0, insert.len() as u32)),
283 left: *left,
284 right: *right,
285 });
286 },
287 Op::Move { id, src, left, right } => {
288 if !live_moves.contains(id) {
289 continue;
290 }
291 let mut sub = 0u32;
292 for r in src {
293 pieces.push(Piece {
294 place_op: *id,
295 sub,
296 claim: *r,
297 left: *left,
298 right: *right,
299 });
300 sub += r.len();
301 }
302 },
303 }
304 }
305 let slots_placed = pieces.len();
306
307 // 6. Cut points, in content space, one per anchor.
308 let mut cuts: HashMap<OpId, BTreeSet<u32>> = HashMap::new();
309 for op in &ops {
310 let (l, r) = op.anchors();
311 for a in [l, r].into_iter().flatten() {
312 let (cid, side) = a;
313 let at = match side {
314 Side::Before => cid.off,
315 Side::After => cid.off + 1,
316 };
317 cuts.entry(cid.op).or_default().insert(at);
318 }
319 }
320
321 // 7. Split every slot at every cut that falls strictly inside it.
322 let mut split: Vec<Piece> = Vec::with_capacity(pieces.len());
323 for p in pieces.drain(..) {
324 let mut from = p.claim.from;
325 if let Some(set) = cuts.get(&p.claim.op) {
326 for c in set.range((p.claim.from + 1)..p.claim.to) {
327 split.push(Piece {
328 place_op: p.place_op,
329 sub: p.sub + (from - p.claim.from),
330 claim: res!(ContentRange::new(p.claim.op, from, *c)),
331 left: p.left,
332 right: p.right,
333 });
334 from = *c;
335 }
336 }
337 split.push(Piece {
338 place_op: p.place_op,
339 sub: p.sub + (from - p.claim.from),
340 claim: res!(ContentRange::new(p.claim.op, from, p.claim.to)),
341 left: p.left,
342 right: p.right,
343 });
344 }
345 let pieces = split;
346 let n = pieces.len();
347
348 // 8. Index for owner lookup, and the chain of pieces of one placement.
349 let mut by_place: HashMap<OpId, Vec<usize>> = HashMap::new();
350 for (i, p) in pieces.iter().enumerate() {
351 by_place.entry(p.place_op).or_default().push(i);
352 }
353 let mut prev_piece: Vec<Option<usize>> = vec![None; n];
354 for idxs in by_place.values_mut() {
355 idxs.sort_by_key(|i| (pieces[*i].claim.op, pieces[*i].claim.from));
356 let mut chain: Vec<usize> = idxs.clone();
357 chain.sort_by_key(|i| pieces[*i].sub);
358 for w in chain.windows(2) {
359 prev_piece[w[1]] = Some(w[0]);
360 }
361 }
362
363 // 9. Resolve anchors, break cycles, order topologically.
364 let ord = res!(self.order_pieces(&pieces, &by_place, &prev_piece, &claims));
365
366 // 10. Build the Fugue tree and traverse it.
367 let out = res!(self.traverse(&pieces, &ord, &claims, &dead, &atoms));
368
369 let mut flags = ord.flags.clone();
370 flags.duplicated = out.duplicated;
371 if self.mode == Mode::ClaimRegister || self.mode == Mode::SplitBeforeMoveNaive {
372 for op in &ops {
373 if let Op::Move { id, src, .. } = op {
374 if !live_moves.contains(id) {
375 continue;
376 }
377 let torn = src.iter().any(|r| r.ids().any(|cid| {
378 claims.get(&cid).map(|v| v.last() != Some(id)).unwrap_or(true)
379 }));
380 if torn {
381 flags.torn.push(*id);
382 }
383 }
384 }
385 }
386 flags.invalidated = ops.iter()
387 .filter(|o| o.is_move() && !live_moves.contains(&o.id()))
388 .map(|o| o.id())
389 .collect();
390
391 // Conservation. Every content id that exists and is not dead must be
392 // rendered by exactly one slot; an oracle that loses a byte quietly is
393 // worse than useless.
394 let mut dead_live = 0usize;
395 for cid in &dead {
396 if let Some(a) = atoms.get(&cid.op) {
397 if (cid.off as usize) < a.len() {
398 dead_live += 1;
399 }
400 }
401 }
402 let distinct = out.prov.iter().collect::<HashSet<_>>().len();
403 let atom_bytes: usize = atoms.values().map(|v| v.len()).sum();
404 if distinct + dead_live != atom_bytes {
405 return Err(err!(
406 "Conservation failed: {} distinct bytes rendered plus {} dead \
407 against {} created.", distinct, dead_live, atom_bytes; Bug));
408 }
409
410 Ok(Render {
411 bytes: out.bytes,
412 prov: out.prov,
413 stats: Stats {
414 ops: ops.len(),
415 slots_placed,
416 slots_split: n,
417 claim_entries: claims.len(),
418 dead_entries: dead.len(),
419 atom_bytes,
420 max_depth: out.max_depth,
421 slot_struct: std::mem::size_of::<Piece>(),
422 dead_intervals: intervals(dead.iter().map(|c| (OpId::new(0, 0), *c))),
423 claim_intervals: intervals(claims.iter()
424 .filter_map(|(c, v)| v.last().map(|o| (*o, *c)))),
425 },
426 flags,
427 pieces: out.info,
428 })
429 }
430
431 /// Which moves may write claims.
432 ///
433 /// Under `ClaimRegister` every move writes, and per-byte last-writer-wins
434 /// sorts out the overlap. Under `SplitBeforeMove` a move whose source
435 /// intersects that of any higher-op-order move cannot be a single element
436 /// and is discarded whole.
437 fn live_moves(&self, ops: &[&Op]) -> Outcome<HashSet<OpId>> {
438 let moves: Vec<(&OpId, &Vec<ContentRange>)> = ops.iter()
439 .filter_map(|o| match o {
440 Op::Move { id, src, .. } => Some((id, src)),
441 _ => None,
442 })
443 .collect();
444 let mut live: HashSet<OpId> = moves.iter().map(|(id, _)| **id).collect();
445 if self.mode == Mode::SplitBeforeMove {
446 for (i, (id_a, src_a)) in moves.iter().enumerate() {
447 for (id_b, src_b) in moves.iter().skip(i + 1) {
448 let overlap = src_a.iter().any(|a| src_b.iter().any(|b| a.intersects(b)));
449 if !overlap {
450 continue;
451 }
452 // The higher op order wins the element outright.
453 if id_a < id_b {
454 live.remove(id_a);
455 } else {
456 live.remove(id_b);
457 }
458 }
459 }
460 }
461 Ok(live)
462 }
463
464 /// Resolves an anchor's content id to the piece that currently owns it.
465 fn owner(
466 &self,
467 cid: &ContentId,
468 pieces: &[Piece],
469 by_place: &HashMap<OpId, Vec<usize>>,
470 claims: &HashMap<ContentId, Vec<OpId>>,
471 demoted: bool,
472 )
473 -> Outcome<usize>
474 {
475 let owner_op = if demoted {
476 cid.op
477 } else {
478 match claims.get(cid).and_then(|v| v.last()) {
479 Some(id) => *id,
480 None => cid.op,
481 }
482 };
483 let idxs = match by_place.get(&owner_op) {
484 Some(v) => v,
485 None => return Err(err!(
486 "No slot placed by {} owns {}.", owner_op, cid; Invalid, Input)),
487 };
488 // `idxs` is sorted by (claim.op, claim.from).
489 let key = (cid.op, cid.off);
490 let pos = idxs.partition_point(|i| (pieces[*i].claim.op, pieces[*i].claim.from) <= key);
491 if pos > 0 {
492 let i = idxs[pos - 1];
493 if pieces[i].claim.contains(cid) {
494 return Ok(i);
495 }
496 }
497 Err(err!("Slot placed by {} does not cover {}.", owner_op, cid; Invalid, Input))
498 }
499
500 /// The resolved origins of a piece, with the demotion state applied.
501 fn origins(
502 &self,
503 i: usize,
504 pieces: &[Piece],
505 by_place: &HashMap<OpId, Vec<usize>>,
506 claims: &HashMap<ContentId, Vec<OpId>>,
507 dem: &[(bool, bool)],
508 )
509 -> Outcome<(Option<usize>, Option<usize>)>
510 {
511 let p = &pieces[i];
512 let mut l = None;
513 let mut r = None;
514 if let Some((cid, side)) = p.left {
515 if side != Side::After {
516 return Err(err!(
517 "Left anchor {} uses Side::Before; the oracle accepts only \
518 Side::After for a left origin.", cid; Invalid, Input));
519 }
520 l = Some(res!(self.owner(&cid, pieces, by_place, claims, dem[i].0)));
521 }
522 if let Some((cid, side)) = p.right {
523 if side != Side::Before {
524 return Err(err!(
525 "Right anchor {} uses Side::After; the oracle accepts only \
526 Side::Before for a right origin.", cid; Invalid, Input));
527 }
528 r = Some(res!(self.owner(&cid, pieces, by_place, claims, dem[i].1)));
529 }
530 Ok((l, r))
531 }
532
533 /// A topological order over the anchor graph of section 5.2, with section
534 /// 5.4's lowest-op-order edge demotion applied to any cycle.
535 fn order_pieces(
536 &self,
537 pieces: &[Piece],
538 by_place: &HashMap<OpId, Vec<usize>>,
539 prev_piece: &[Option<usize>],
540 claims: &HashMap<ContentId, Vec<OpId>>,
541 )
542 -> Outcome<Ordering>
543 {
544 let n = pieces.len();
545 let mut dem: Vec<(bool, bool)> = vec![(false, false); n];
546 let mut drop: Vec<(bool, bool)> = vec![(false, false); n];
547 let mut flags = Flags::default();
548
549 loop {
550 // Dependencies under the current demotion state.
551 let mut deps: Vec<Vec<usize>> = vec![Vec::new(); n];
552 for i in 0..n {
553 // Only the first piece of a placement uses its anchors; the
554 // rest chain to their predecessor.
555 if let Some(x) = prev_piece[i] {
556 deps[i].push(x);
557 continue;
558 }
559 // A self-edge is a cycle of length one, which happens when a
560 // move's destination anchor names content the move itself
561 // claims. It is left in so that the demotion rule of section
562 // 5.4 sees it and breaks it.
563 let (l, r) = res!(self.origins(i, pieces, by_place, claims, &dem));
564 if let Some(x) = l {
565 if !drop[i].0 {
566 deps[i].push(x);
567 }
568 }
569 if let Some(x) = r {
570 if !drop[i].1 {
571 deps[i].push(x);
572 }
573 }
574 }
575 let mut indeg: Vec<usize> = vec![0; n];
576 let mut rev: Vec<Vec<usize>> = vec![Vec::new(); n];
577 for i in 0..n {
578 indeg[i] = deps[i].len();
579 for d in &deps[i] {
580 rev[*d].push(i);
581 }
582 }
583 // Kahn, ties broken by (op order, sub) ascending.
584 let mut ready: BTreeSet<(OpId, u32, usize)> = BTreeSet::new();
585 for i in 0..n {
586 if indeg[i] == 0 {
587 ready.insert((pieces[i].place_op, pieces[i].sub, i));
588 }
589 }
590 let mut order: Vec<usize> = Vec::with_capacity(n);
591 while let Some(k) = ready.iter().next().copied() {
592 ready.remove(&k);
593 let i = k.2;
594 order.push(i);
595 for j in &rev[i] {
596 indeg[*j] -= 1;
597 if indeg[*j] == 0 {
598 ready.insert((pieces[*j].place_op, pieces[*j].sub, *j));
599 }
600 }
601 }
602 if order.len() == n {
603 let mut left = vec![None; n];
604 let mut right = vec![None; n];
605 for i in 0..n {
606 if prev_piece[i].is_some() {
607 continue;
608 }
609 let (l, r) = res!(self.origins(i, pieces, by_place, claims, &dem));
610 left[i] = if drop[i].0 { None } else { l };
611 right[i] = if drop[i].1 { None } else { r };
612 }
613 return Ok(Ordering { order, left, right, prev: prev_piece.to_vec(), flags });
614 }
615 // A cycle remains. Demote the lowest-op-order blocked piece.
616 let mut stuck: Vec<usize> = (0..n)
617 .filter(|i| indeg[*i] > 0 && prev_piece[*i].is_none())
618 .collect();
619 stuck.sort_by_key(|i| (pieces[*i].place_op, pieces[*i].sub, *i));
620 let victim = match stuck.first() {
621 Some(v) => *v,
622 None => return Err(err!(
623 "Topological sort stalled with no blocked slot."; Bug)),
624 };
625 let p = &pieces[victim];
626 if !dem[victim].0 && p.left.is_some() {
627 dem[victim].0 = true;
628 flags.demoted.push((p.place_op, p.sub));
629 } else if !dem[victim].1 && p.right.is_some() {
630 dem[victim].1 = true;
631 flags.demoted.push((p.place_op, p.sub));
632 } else if !drop[victim].0 && p.left.is_some() {
633 drop[victim].0 = true;
634 flags.dropped.push((p.place_op, p.sub));
635 } else if !drop[victim].1 && p.right.is_some() {
636 drop[victim].1 = true;
637 flags.dropped.push((p.place_op, p.sub));
638 } else {
639 return Err(err!(
640 "Cycle through slot {}+{} survives demotion and dropping.",
641 p.place_op, p.sub; Bug));
642 }
643 }
644 }
645
646 /// Builds the Fugue tree in topological order and traverses it.
647 fn traverse(
648 &self,
649 pieces: &[Piece],
650 ord: &Ordering,
651 claims: &HashMap<ContentId, Vec<OpId>>,
652 dead: &HashSet<ContentId>,
653 atoms: &BTreeMap<OpId, Vec<u8>>,
654 )
655 -> Outcome<Traversal>
656 {
657 let n = pieces.len();
658 let root = n;
659 const LOG: usize = 20;
660 let mut parent: Vec<u32> = vec![root as u32; n + 1];
661 let mut side: Vec<ChildSide> = vec![ChildSide::Right; n + 1];
662 let mut depth: Vec<u32> = vec![0; n + 1];
663 let mut up: Vec<[u32; LOG]> = vec![[root as u32; LOG]; n + 1];
664 let mut kids_l: Vec<Vec<usize>> = vec![Vec::new(); n + 1];
665 let mut kids_r: Vec<Vec<usize>> = vec![Vec::new(); n + 1];
666
667 let mut max_depth = 0u32;
668 for &i in &ord.order {
669 // A piece that is not the first of its placement chains to its
670 // predecessor as a right child, which is Yjs's split rule.
671 let (par, sd) = if let Some(prev) = ord.prev[i] {
672 (prev, ChildSide::Right)
673 } else {
674 match (ord.left[i], ord.right[i]) {
675 (None, None) => (root, ChildSide::Right),
676 (None, Some(r)) => (r, ChildSide::Left),
677 (Some(l), None) => (l, ChildSide::Right),
678 (Some(l), Some(r)) => {
679 if right_subtree(l, r, &depth, &up, &parent, &side, LOG) {
680 (r, ChildSide::Left)
681 } else if self.bind == Bind::LeftBias {
682 (l, ChildSide::Right)
683 } else {
684 // The origins have been torn apart by a move.
685 // Re-run the rule against the left origin's
686 // current successor, so that the slot lands
687 // immediately after the content it was
688 // anchored to.
689 match successor(l, &kids_l, &kids_r, &parent, &side, root) {
690 Some(s) if right_subtree(
691 l, s, &depth, &up, &parent, &side, LOG)
692 => (s, ChildSide::Left),
693 _ => (l, ChildSide::Right),
694 }
695 }
696 },
697 }
698 };
699 if par == i {
700 return Err(err!(
701 "Slot {}+{} resolved to itself as parent.",
702 pieces[i].place_op, pieces[i].sub; Bug));
703 }
704 parent[i] = par as u32;
705 side[i] = sd;
706 depth[i] = depth[par] + 1;
707 max_depth = max_depth.max(depth[i]);
708 up[i][0] = par as u32;
709 for k in 1..LOG {
710 up[i][k] = up[up[i][k - 1] as usize][k - 1];
711 }
712 // Same-side siblings are kept in op order ascending, then sub
713 // ascending, so that the successor walk sees a correct tree.
714 let list = match sd {
715 ChildSide::Left => &mut kids_l[par],
716 ChildSide::Right => &mut kids_r[par],
717 };
718 let k = (pieces[i].place_op, pieces[i].sub, i);
719 let pos = list.partition_point(
720 |j| (pieces[*j].place_op, pieces[*j].sub, *j) < k);
721 list.insert(pos, i);
722 }
723
724 let mut bytes: Vec<u8> = Vec::new();
725 let mut prov: Vec<ContentId> = Vec::new();
726 let mut seen: HashSet<ContentId> = HashSet::new();
727 let mut duplicated = 0usize;
728 let mut info: Vec<PieceInfo> = pieces.iter().map(|p| PieceInfo {
729 place_op: p.place_op,
730 sub: p.sub,
731 claim: p.claim,
732 emitted: 0,
733 visited: false,
734 }).collect();
735 let mut stack: Vec<(usize, bool)> = vec![(root, false)];
736 while let Some((i, emitted)) = stack.pop() {
737 if emitted {
738 if i == root {
739 continue;
740 }
741 let p = &pieces[i];
742 info[i].visited = true;
743 let atom = match atoms.get(&p.claim.op) {
744 Some(a) => a,
745 None => return Err(err!(
746 "Slot claims content of unknown atom {}.", p.claim.op; Invalid, Input)),
747 };
748 for cid in p.claim.ids() {
749 let owned = match claims.get(&cid) {
750 Some(v) => v.contains(&p.place_op),
751 None => cid.op == p.place_op,
752 };
753 if !owned || dead.contains(&cid) {
754 continue;
755 }
756 let b = match atom.get(cid.off as usize) {
757 Some(b) => *b,
758 None => return Err(err!(
759 "Content id {} is beyond its atom.", cid; Invalid, Input)),
760 };
761 if !seen.insert(cid) {
762 duplicated += 1;
763 }
764 bytes.push(b);
765 prov.push(cid);
766 info[i].emitted += 1;
767 }
768 continue;
769 }
770 for c in kids_r[i].iter().rev() {
771 stack.push((*c, false));
772 }
773 stack.push((i, true));
774 for c in kids_l[i].iter().rev() {
775 stack.push((*c, false));
776 }
777 }
778
779 Ok(Traversal { bytes, prov, duplicated, max_depth, info })
780 }
781}
782
783/// Which side of its parent a Fugue node sits on.
784#[derive(Clone, Copy, PartialEq, Eq, Debug)]
785enum ChildSide {
786 Left,
787 Right,
788}
789
790/// Counts the maximal runs in a set of `(owner, content id)` pairs, which is
791/// what an interval map would store where this prototype stores one entry per
792/// byte.
793fn intervals<I>(it: I) -> usize
794where
795 I: Iterator<Item = (OpId, ContentId)>,
796{
797 let mut v: Vec<(OpId, OpId, u32)> = it
798 .map(|(owner, cid)| (owner, cid.op, cid.off))
799 .collect();
800 v.sort();
801 let mut n = 0usize;
802 let mut prev: Option<(OpId, OpId, u32)> = None;
803 for e in v {
804 let extend = match prev {
805 Some(p) => p.0 == e.0 && p.1 == e.1 && p.2 + 1 == e.2,
806 None => false,
807 };
808 if !extend {
809 n += 1;
810 }
811 prev = Some(e);
812 }
813 n
814}
815
816/// The in-order successor of `v` among the nodes placed so far.
817fn successor(
818 v: usize,
819 kids_l: &[Vec<usize>],
820 kids_r: &[Vec<usize>],
821 parent: &[u32],
822 side: &[ChildSide],
823 root: usize,
824)
825 -> Option<usize>
826{
827 if let Some(c) = kids_r[v].first() {
828 let mut cur = *c;
829 while let Some(x) = kids_l[cur].first() {
830 cur = *x;
831 }
832 return Some(cur);
833 }
834 let mut cur = v;
835 loop {
836 let p = parent[cur] as usize;
837 if p == cur || p == root {
838 return None;
839 }
840 if side[cur] == ChildSide::Left {
841 return Some(p);
842 }
843 cur = p;
844 }
845}
846
847/// Whether `r` lies in the right subtree of `l`, by binary lifting.
848fn right_subtree(
849 l: usize,
850 r: usize,
851 depth: &[u32],
852 up: &[[u32; 20]],
853 parent: &[u32],
854 side: &[ChildSide],
855 log: usize,
856)
857 -> bool
858{
859 if depth[r] <= depth[l] {
860 return false;
861 }
862 let mut climb = depth[r] - depth[l] - 1;
863 let mut cur = r;
864 let mut k = 0usize;
865 while climb > 0 && k < log {
866 if climb & 1 == 1 {
867 cur = up[cur][k] as usize;
868 }
869 climb >>= 1;
870 k += 1;
871 }
872 parent[cur] as usize == l && side[cur] == ChildSide::Right
873}
874
875/// The topological order and the resolved origins it was computed against.
876struct Ordering {
877 order: Vec<usize>,
878 left: Vec<Option<usize>>,
879 right: Vec<Option<usize>>,
880 prev: Vec<Option<usize>>,
881 flags: Flags,
882}
883
884/// The output of the tree traversal.
885struct Traversal {
886 bytes: Vec<u8>,
887 prov: Vec<ContentId>,
888 duplicated: usize,
889 max_depth: u32,
890 info: Vec<PieceInfo>,
891}