Oregami
Repositories/oxedyne/ore

oxedyne/ore/oracle/src/repo.rs

50.6 KiB, 1 run

created by r2848102244:95, 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//! Multi-file file identity: the three candidates of the options note, in one
2//! engine.
3//!
4//! The single-file oracle in `doc.rs` is left exactly as it was. This module is
5//! its multi-file generalisation, and it exists to decide one question: what
6//! names a file, and what does that do to cross-file move, to two branches
7//! creating one path, and to deleting a file whose content has moved out.
8//!
9//! Three identity rules are selectable and the difference between them is the
10//! whole point.
11//!
12//! - [`Identity::Derived`], candidate B. Content operations carry no file
13//! field at all. Every file's creation mints an **origin anchor**, a
14//! one-byte atom that is born dead, so that a splice into an empty file has
15//! something to anchor to and every operation without exception is decided by
16//! content. The repository is one Fugue forest whose root children are the
17//! origin anchors, and a file is the subtree under one of them.
18//! - [`Identity::Recorded`], candidate A. Content operations carry
19//! `file: FileId`, the identity of the `FileCreate` that minted the file. The
20//! renderer builds one Fugue tree per file over the slots recorded as
21//! belonging to it, and the claim register is repository-global.
22//! - [`Identity::RecordedLocal`], candidate A as `fe2o3_ore` stands today: the
23//! same, but with the claim register scoped to the file, because a `Sequence`
24//! is built only from the operations routed to it and never sees a move that
25//! was routed elsewhere. Kept to measure what the status quo does with a
26//! cross-file move rather than to argue for it.
27//!
28//! Everything else is `doc.rs`'s arrangement unchanged: applying an operation is
29//! set insertion, and the whole of the derived state is recomputed from the
30//! operation set on every render. The anchor binding is the successor rule of
31//! design note section 4.3, which is the only one the note now specifies.
32
33use crate::id::{
34 Anchor,
35 ContentId,
36 ContentRange,
37 OpId,
38 Side,
39};
40
41use std::cell::RefCell;
42use std::collections::{
43 BTreeMap,
44 BTreeSet,
45 HashMap,
46 HashSet,
47};
48use std::rc::Rc;
49
50use oxedyne_fe2o3_core::prelude::*;
51
52/// A file's identity: the operation that created it.
53pub type FileId = OpId;
54
55/// What the renderer does with a cycle in the anchor graph that runs between
56/// files.
57///
58/// Every rule here is a render-time function of the operation set: none of them
59/// reads a field an author wrote, and none of them needs one. A cycle confined
60/// to a single file is left to [`CycleRule::Demote`] under every rule, because
61/// the in-file outcome -- one move landing at a stale position -- is annoying
62/// and safe, and only the cross-file outcome is the defect.
63#[derive(Clone, Copy, PartialEq, Eq, Debug)]
64pub enum CycleRule {
65 /// D, the status quo of design note section 5.4: demote the lowest blocked
66 /// slot's left origin, then its right, then drop both.
67 Demote,
68 /// A as the brief phrases it: confine the *demotion victim*, and only it, to
69 /// its source position when demoting would land its content in another file.
70 ConfineVictim,
71 /// A read as a property of the cycle: confine every cross-file member to its
72 /// source, leaving any in-file member of the same cycle to complete.
73 ConfineCycle,
74 /// B: void the cross-file member lowest in op order and let every other
75 /// member proceed.
76 LowestEdge,
77 /// C: the member highest in op order wins wholly and every other member of
78 /// the cycle is voided to its source.
79 WholeCycle,
80}
81
82impl CycleRule {
83 /// Whether the rule may confine anything at all.
84 pub fn confines(&self) -> bool {
85 *self != Self::Demote
86 }
87
88 /// A short name, for tables.
89 pub fn name(&self) -> &'static str {
90 match self {
91 Self::Demote => "Demote",
92 Self::ConfineVictim => "ConfineVictim",
93 Self::ConfineCycle => "ConfineCycle",
94 Self::LowestEdge => "LowestEdge",
95 Self::WholeCycle => "WholeCycle",
96 }
97 }
98}
99
100/// Everything about an operation that the wire carries but this prototype's
101/// `MOp` does not: who had seen what, and which file an author aimed at.
102///
103/// The causal part stands for the parent list every record carries in
104/// `fe2o3_ore`, and it is read for exactly one purpose: to tell a race from a
105/// sequence, so that an author re-moving their own block is not voided for it.
106/// The intent part has no counterpart on the wire at all -- it is the measuring
107/// instrument, not part of any rule, and it is what lets the sweep count moves
108/// that landed in a file their author never named.
109#[derive(Clone, Default, Debug)]
110pub struct Meta {
111 /// For each operation, everything its author had applied when it was minted.
112 pub seen: HashMap<OpId, BTreeSet<OpId>>,
113 /// For each move, the file its author aimed it at. Measurement only.
114 pub intent: HashMap<OpId, FileId>,
115}
116
117impl Meta {
118 /// Whether `a` is in `b`'s causal past.
119 pub fn before(&self, a: &OpId, b: &OpId) -> bool {
120 self.seen.get(b).map(|s| s.contains(a)).unwrap_or(false)
121 }
122}
123
124/// A metadata table shared by every replica of one repository, exactly as the
125/// causal graph is shared by every replica of a real one.
126pub type Shared = Rc<RefCell<Meta>>;
127
128/// A fresh shared metadata table.
129pub fn shared() -> Shared {
130 Rc::new(RefCell::new(Meta::default()))
131}
132
133/// The byte an origin anchor's atom holds. It is born dead and never renders,
134/// so its value is arbitrary; it is not a zero terminator and nothing reads it.
135pub const SEED: u8 = 0;
136
137/// Which candidate the render implements.
138#[derive(Clone, Copy, PartialEq, Eq, Debug)]
139pub enum Identity {
140 /// Candidate B: no file field, origin anchors, one global forest.
141 Derived,
142 /// Candidate A: `file: FileId` on content operations, one tree per file,
143 /// repository-global claim register.
144 Recorded,
145 /// Candidate A with the per-file claim register `fe2o3_ore` has today.
146 RecordedLocal,
147}
148
149impl Identity {
150 /// Whether a file's creation mints an origin anchor.
151 pub fn seeds(&self) -> bool {
152 *self == Self::Derived
153 }
154
155 /// Whether one claim register serves the whole repository.
156 pub fn global_claims(&self) -> bool {
157 *self != Self::RecordedLocal
158 }
159}
160
161/// An operation. The file field is present exactly when the candidate records
162/// one, and is `None` under [`Identity::Derived`].
163#[derive(Clone, PartialEq, Eq, Debug)]
164pub enum MOp {
165 /// Brings a file into existence, empty.
166 FileCreate {
167 /// Operation identity, which is also the file's identity.
168 id: OpId,
169 /// Where the file sits, as bytes rather than as a string.
170 path: Vec<u8>,
171 },
172 /// Moves a file to another path.
173 FileRename {
174 /// Operation identity.
175 id: OpId,
176 /// Which file moves.
177 file: FileId,
178 /// Where it moves to.
179 path: Vec<u8>,
180 },
181 /// Retires a file.
182 FileDelete {
183 /// Operation identity.
184 id: OpId,
185 /// Which file goes.
186 file: FileId,
187 },
188 /// Inserts bytes and kills content ranges.
189 Splice {
190 /// Operation identity.
191 id: OpId,
192 /// Which file, where the candidate records one.
193 file: Option<FileId>,
194 /// Left Fugue origin.
195 left: Anchor,
196 /// Right Fugue origin.
197 right: Anchor,
198 /// What dies.
199 remove: Vec<ContentRange>,
200 /// What is inserted.
201 insert: Vec<u8>,
202 },
203 /// Reclaims existing content at a new position, in any file.
204 Move {
205 /// Operation identity.
206 id: OpId,
207 /// Which file the content lands in, where the candidate records one.
208 file: Option<FileId>,
209 /// What moves, in destination order.
210 src: Vec<ContentRange>,
211 /// Left Fugue origin of the destination.
212 left: Anchor,
213 /// Right Fugue origin of the destination.
214 right: Anchor,
215 },
216}
217
218impl MOp {
219 /// The operation's identity.
220 pub fn id(&self) -> OpId {
221 match self {
222 Self::FileCreate { id, .. } => *id,
223 Self::FileRename { id, .. } => *id,
224 Self::FileDelete { id, .. } => *id,
225 Self::Splice { id, .. } => *id,
226 Self::Move { id, .. } => *id,
227 }
228 }
229
230 /// The operation's destination anchors, where it has any.
231 pub fn anchors(&self) -> (Anchor, Anchor) {
232 match self {
233 Self::Splice { left, right, .. } => (*left, *right),
234 Self::Move { left, right, .. } => (*left, *right),
235 _ => (None, None),
236 }
237 }
238
239 /// Whether the operation is a move.
240 pub fn is_move(&self) -> bool {
241 matches!(self, Self::Move { .. })
242 }
243
244 /// The recorded file, where the candidate records one.
245 pub fn file(&self) -> Option<FileId> {
246 match self {
247 Self::Splice { file, .. } => *file,
248 Self::Move { file, .. } => *file,
249 _ => None,
250 }
251 }
252}
253
254/// What a file is, as the operations describe it.
255#[derive(Clone, Debug)]
256struct FileInfo {
257 path: Vec<u8>,
258 live: bool,
259}
260
261/// One file, rendered.
262#[derive(Clone, Debug)]
263pub struct FileOut {
264 /// The file's identity.
265 pub file: FileId,
266 /// Where it sits.
267 pub path: Vec<u8>,
268 /// Whether it still exists.
269 pub live: bool,
270 /// The rendered bytes.
271 pub bytes: Vec<u8>,
272 /// The content id of each rendered byte.
273 pub prov: Vec<ContentId>,
274}
275
276impl FileOut {
277 /// The rendered bytes as a lossy string, for test messages.
278 pub fn text(&self) -> String {
279 String::from_utf8_lossy(&self.bytes).into_owned()
280 }
281
282 /// The path as a lossy string.
283 pub fn name(&self) -> String {
284 String::from_utf8_lossy(&self.path).into_owned()
285 }
286}
287
288/// Everything the renderer noticed.
289#[derive(Clone, Default, Debug)]
290pub struct MFlags {
291 /// Moves whose source is no longer wholly owned by them.
292 pub torn: Vec<OpId>,
293 /// Anchors demoted to their creating splice by the cycle rule.
294 pub demoted: Vec<(OpId, u32)>,
295 /// Anchors demoted because their target lay outside the file the operation
296 /// was recorded against. Only a recorded-identity candidate can raise it.
297 pub off_file: Vec<(OpId, u32)>,
298 /// Anchors dropped entirely, demotion having failed to resolve them.
299 pub dropped: Vec<(OpId, u32)>,
300 /// Bytes rendered in more than one place, anywhere in the repository.
301 pub duplicated: usize,
302 /// Live files sharing one path.
303 pub path_clash: Vec<(Vec<u8>, Vec<FileId>)>,
304 /// Slots that belong to no file at all.
305 pub orphan: Vec<(OpId, u32)>,
306 /// Moves voided by a confinement rule: the move, the file its content stays
307 /// in, and the file it was denied.
308 pub confined: Vec<(OpId, FileId, FileId)>,
309 /// Moves that won a cross-file cycle outright and completed.
310 pub won: Vec<OpId>,
311 /// Demotions that carried content across a file boundary: the slot, the file
312 /// its content was written into, and the file it renders in. This is the
313 /// shipped `Flag::CrossedFile`.
314 pub crossed: Vec<(OpId, u32, FileId, FileId)>,
315 /// Cycles a confinement rule declined, and why: no move in the cycle to
316 /// void, no member crossing a boundary, or every member informed. Not a
317 /// flag a reader wants; a measurement of how often the rule does not fire.
318 pub declined: [usize; 3],
319}
320
321/// Measurements taken during a render.
322#[derive(Clone, Default, Debug)]
323pub struct MStats {
324 /// Operations in the set.
325 pub ops: usize,
326 /// Files created.
327 pub files: usize,
328 /// Slots before anchor-driven splitting, origin anchors included.
329 pub slots_placed: usize,
330 /// Slots after anchor-driven splitting.
331 pub slots_split: usize,
332 /// Bytes held in atoms, origin anchors included.
333 pub atom_bytes: usize,
334 /// Bytes rendered anywhere, live files and dead ones alike.
335 pub rendered: usize,
336 /// Live bytes held back because the file holding them is deleted.
337 pub withheld: usize,
338 /// Live bytes that render nowhere at all. Any value but zero is a fault.
339 pub lost: usize,
340}
341
342/// The result of rendering a repository.
343#[derive(Clone, Debug)]
344pub struct RepoRender {
345 /// Every file, in identity order, deleted ones included.
346 pub files: Vec<FileOut>,
347 /// What the renderer noticed.
348 pub flags: MFlags,
349 /// Measurements.
350 pub stats: MStats,
351 /// Which file every content id sits in, dead bytes and origin anchors
352 /// included. Measurement, not rule.
353 pub site: HashMap<ContentId, FileId>,
354 /// Which file each atom was written into, read off the slot its creating
355 /// splice placed. In a render with every move voided this is the *birth*
356 /// file of every byte in the repository, which is what the confinement rules
357 /// classify a cycle by.
358 pub birth: HashMap<OpId, FileId>,
359}
360
361impl RepoRender {
362 /// One file by identity.
363 pub fn file(&self, id: FileId) -> Option<&FileOut> {
364 self.files.iter().find(|f| f.file == id)
365 }
366
367 /// The rendered text of one file, or the empty string if it has gone.
368 pub fn text(&self, id: FileId) -> String {
369 self.file(id).map(|f| f.text()).unwrap_or_default()
370 }
371
372 /// Every live file, in ascending order of path and then of identity.
373 pub fn live(&self) -> Vec<&FileOut> {
374 let mut v: Vec<&FileOut> = self.files.iter().filter(|f| f.live).collect();
375 v.sort_by(|a, b| a.path.cmp(&b.path).then(a.file.cmp(&b.file)));
376 v
377 }
378
379 /// The working tree the render describes: a path for every live file, with
380 /// a clash resolved by op order, the loser taking a derived name so that no
381 /// file is displaced into invisibility.
382 pub fn materialise(&self) -> BTreeMap<String, String> {
383 let mut by_path: BTreeMap<&[u8], Vec<&FileOut>> = BTreeMap::new();
384 for f in self.files.iter().filter(|f| f.live) {
385 by_path.entry(&f.path).or_default().push(f);
386 }
387 let mut out = BTreeMap::new();
388 for (path, mut group) in by_path {
389 group.sort_by_key(|f| f.file);
390 let last = group.len() - 1;
391 for (i, f) in group.iter().enumerate() {
392 let name = if i == last {
393 String::from_utf8_lossy(path).into_owned()
394 } else {
395 fmt!("{}~{}", String::from_utf8_lossy(path), f.file)
396 };
397 out.insert(name, f.text());
398 }
399 }
400 out
401 }
402
403 /// A one-line-per-file listing, for test messages.
404 pub fn listing(&self) -> String {
405 let mut s = String::new();
406 for (path, text) in self.materialise() {
407 s.push_str(&fmt!("{}={:?} ", path, text));
408 }
409 s.trim_end().to_string()
410 }
411}
412
413/// A slot, after splitting.
414#[derive(Clone, Debug)]
415struct Piece {
416 place_op: OpId,
417 sub: u32,
418 claim: ContentRange,
419 left: Anchor,
420 right: Anchor,
421 /// The file the placing operation recorded, where the candidate records one.
422 file: Option<FileId>,
423 /// Whether the slot is a file's origin anchor.
424 seed: bool,
425}
426
427/// The repository: an unordered set of operations, and the metadata a real
428/// record would have carried alongside them.
429#[derive(Clone, Debug)]
430pub struct Repo {
431 ops: Vec<MOp>,
432 seen: HashSet<OpId>,
433 ident: Identity,
434 rule: CycleRule,
435 meta: Shared,
436}
437
438impl Repo {
439 /// Creates an empty repository under the given identity rule, with the
440 /// status quo cycle rule and metadata of its own.
441 pub fn new(ident: Identity) -> Self {
442 Self {
443 ops: Vec::new(),
444 seen: HashSet::new(),
445 ident,
446 rule: CycleRule::Demote,
447 meta: shared(),
448 }
449 }
450
451 /// Creates an empty repository under both rules, sharing a metadata table.
452 pub fn with_rule(ident: Identity, rule: CycleRule, meta: Shared) -> Self {
453 Self { ops: Vec::new(), seen: HashSet::new(), ident, rule, meta }
454 }
455
456 /// The identity rule.
457 pub fn ident(&self) -> Identity {
458 self.ident
459 }
460
461 /// The cycle rule.
462 pub fn rule(&self) -> CycleRule {
463 self.rule
464 }
465
466 /// The shared metadata table.
467 pub fn meta(&self) -> Shared {
468 Rc::clone(&self.meta)
469 }
470
471 /// Records what an operation's author had seen when it was minted.
472 pub fn note_seen(&self, id: OpId, seen: BTreeSet<OpId>) {
473 self.meta.borrow_mut().seen.insert(id, seen);
474 }
475
476 /// Records the file a move's author aimed it at. Measurement only.
477 pub fn note_intent(&self, id: OpId, file: FileId) {
478 self.meta.borrow_mut().intent.insert(id, file);
479 }
480
481 /// Applies an operation. Idempotent and order-independent by construction.
482 pub fn apply(&mut self, op: MOp) {
483 if self.seen.insert(op.id()) {
484 self.ops.push(op);
485 }
486 }
487
488 /// The operations applied so far, in arrival order.
489 pub fn ops(&self) -> &[MOp] {
490 &self.ops
491 }
492
493 /// Whether the operation has been applied.
494 pub fn has(&self, id: &OpId) -> bool {
495 self.seen.contains(id)
496 }
497
498 /// Replaces the operation vector, for tests that shuffle it.
499 pub fn set_ops(&mut self, ops: Vec<MOp>) {
500 self.seen = ops.iter().map(|o| o.id()).collect();
501 self.ops = ops;
502 }
503
504 /// The greatest Lamport counter observed.
505 pub fn max_counter(&self) -> u64 {
506 self.ops.iter().map(|o| o.id().counter).max().unwrap_or(0)
507 }
508
509 /// Renders every file in the repository.
510 ///
511 /// Under a confinement rule the render is a fixed point rather than a single
512 /// pass: laying the slots out may decide that a move must be voided, in which
513 /// case the claim register is rebuilt without it and the layout is attempted
514 /// again. Each pass voids at least one move and no move is ever un-voided,
515 /// so the loop terminates; and every decision it takes is a function of the
516 /// operation set, so the fixed point is the same on every replica.
517 pub fn render(&self) -> Outcome<RepoRender> {
518 let mut voided: BTreeSet<OpId> = BTreeSet::new();
519 let mut confined: Vec<(OpId, FileId, FileId)> = Vec::new();
520 let mut won: Vec<OpId> = Vec::new();
521 loop {
522 match res!(self.attempt(&voided, &confined, &won, self.rule)) {
523 Attempt::Done(r) => return Ok(r),
524 Attempt::Void { ops, winner } => {
525 for (id, from, to) in ops {
526 if !voided.insert(id) {
527 return Err(err!(
528 "The move {} was voided twice, so the confinement \
529 loop is not making progress.", id; Bug));
530 }
531 confined.push((id, from, to));
532 }
533 if let Some(w) = winner {
534 won.push(w);
535 }
536 },
537 }
538 }
539 }
540
541 /// One pass of the render, with a given set of moves already voided.
542 fn attempt(
543 &self,
544 voided: &BTreeSet<OpId>,
545 confined: &[(OpId, FileId, FileId)],
546 won: &[OpId],
547 rule: CycleRule,
548 )
549 -> Outcome<Attempt>
550 {
551 let mut ops: Vec<&MOp> = self.ops.iter().collect();
552 ops.sort_by_key(|o| o.id());
553
554 // 1. The files, and what has happened to them.
555 let mut files: BTreeMap<FileId, FileInfo> = BTreeMap::new();
556 for op in &ops {
557 match op {
558 MOp::FileCreate { id, path } => {
559 files.insert(*id, FileInfo { path: path.clone(), live: true });
560 },
561 MOp::FileRename { file, path, .. } => {
562 if let Some(f) = files.get_mut(file) {
563 f.path = path.clone();
564 }
565 },
566 MOp::FileDelete { file, .. } => {
567 if let Some(f) = files.get_mut(file) {
568 f.live = false;
569 }
570 },
571 _ => (),
572 }
573 }
574
575 // 2. Atoms and tombstones. An origin anchor is an atom of one byte that
576 // is born dead, so that it can be named and can never be seen.
577 let mut atoms: BTreeMap<OpId, Vec<u8>> = BTreeMap::new();
578 let mut dead: HashSet<ContentId> = HashSet::new();
579 if self.ident.seeds() {
580 for f in files.keys() {
581 atoms.insert(*f, vec![SEED]);
582 dead.insert(ContentId::new(*f, 0));
583 }
584 }
585 for op in &ops {
586 if let MOp::Splice { id, remove, insert, .. } = op {
587 if !insert.is_empty() {
588 atoms.insert(*id, insert.clone());
589 }
590 for r in remove {
591 for cid in r.ids() {
592 dead.insert(cid);
593 }
594 }
595 }
596 }
597
598 // 3. The claim register, and which file each mover recorded.
599 let mut claims: HashMap<ContentId, OpId> = HashMap::new();
600 let mut mover_file: HashMap<OpId, Option<FileId>> = HashMap::new();
601 for op in &ops {
602 if let MOp::Move { id, file, src, .. } = op {
603 if voided.contains(id) {
604 continue;
605 }
606 mover_file.insert(*id, *file);
607 for r in src {
608 if !atoms.contains_key(&r.op) {
609 return Err(err!(
610 "Move {} names content {} of an unknown atom.",
611 id, r; Invalid, Input));
612 }
613 for cid in r.ids() {
614 claims.insert(cid, *id);
615 }
616 }
617 }
618 }
619
620 // 4. Slots: one origin anchor per file, one per splice, one per source
621 // range of a move.
622 let mut pieces: Vec<Piece> = Vec::new();
623 if self.ident.seeds() {
624 for f in files.keys() {
625 pieces.push(Piece {
626 place_op: *f,
627 sub: 0,
628 claim: res!(ContentRange::new(*f, 0, 1)),
629 left: None,
630 right: None,
631 file: Some(*f),
632 seed: true,
633 });
634 }
635 }
636 for op in &ops {
637 match op {
638 MOp::Splice { id, file, left, right, insert, .. } => {
639 if insert.is_empty() {
640 continue;
641 }
642 if self.ident.seeds() && left.is_none() && right.is_none() {
643 return Err(err!(
644 "Splice {} names no origin at all; under a derived \
645 identity every operation anchors to content, and an \
646 empty file's origin anchor is what it anchors to.",
647 id; Invalid, Input));
648 }
649 pieces.push(Piece {
650 place_op: *id,
651 sub: 0,
652 claim: res!(ContentRange::new(*id, 0, insert.len() as u32)),
653 left: *left,
654 right: *right,
655 file: *file,
656 seed: false,
657 });
658 },
659 MOp::Move { id, file, src, left, right } => {
660 if self.ident.seeds() && left.is_none() && right.is_none() {
661 return Err(err!(
662 "Move {} names no origin at all.", id; Invalid, Input));
663 }
664 // A voided move places nothing. Its slots hold no claim, so
665 // no anchor can resolve to them and nothing is left behind by
666 // dropping them; the bytes render from whoever owns them now,
667 // which is where they were before the move.
668 if voided.contains(id) {
669 continue;
670 }
671 let mut sub = 0u32;
672 for r in src {
673 pieces.push(Piece {
674 place_op: *id,
675 sub,
676 claim: *r,
677 left: *left,
678 right: *right,
679 file: *file,
680 seed: false,
681 });
682 sub += r.len();
683 }
684 },
685 _ => (),
686 }
687 }
688 let slots_placed = pieces.len();
689
690 // 5. Cut points, one per anchor, in content space.
691 let mut cuts: HashMap<OpId, BTreeSet<u32>> = HashMap::new();
692 for op in &ops {
693 let (l, r) = op.anchors();
694 for a in [l, r].into_iter().flatten() {
695 let (cid, side) = a;
696 let at = match side {
697 Side::Before => cid.off,
698 Side::After => cid.off + 1,
699 };
700 cuts.entry(cid.op).or_default().insert(at);
701 }
702 }
703
704 // 6. Split every slot at every cut that falls strictly inside it.
705 let mut split: Vec<Piece> = Vec::with_capacity(pieces.len());
706 for p in pieces.drain(..) {
707 let mut from = p.claim.from;
708 if let Some(set) = cuts.get(&p.claim.op) {
709 for c in set.range((p.claim.from + 1)..p.claim.to) {
710 split.push(Piece {
711 claim: res!(ContentRange::new(p.claim.op, from, *c)),
712 sub: p.sub + (from - p.claim.from),
713 ..p.clone()
714 });
715 from = *c;
716 }
717 }
718 split.push(Piece {
719 claim: res!(ContentRange::new(p.claim.op, from, p.claim.to)),
720 sub: p.sub + (from - p.claim.from),
721 ..p.clone()
722 });
723 }
724 let pieces = split;
725
726 // 7. Lay the slots out, once for the whole repository under a derived
727 // identity and once per file under a recorded one.
728 let mut flags = MFlags::default();
729 let mut out: BTreeMap<FileId, (Vec<u8>, Vec<ContentId>)> = BTreeMap::new();
730 let mut seen_bytes: HashMap<ContentId, usize> = HashMap::new();
731 let mut sites = Sites::default();
732 match self.ident {
733 Identity::Derived => {
734 let scope: Vec<usize> = (0..pieces.len()).collect();
735 let laid = match res!(self.lay_out(
736 &pieces, &scope, &claims, None, voided, rule, &mut flags))
737 {
738 Lay::Done(l) => l,
739 Lay::Void { ops, winner } => return Ok(
740 Attempt::Void { ops, winner }),
741 };
742 res!(self.emit(&pieces, &scope, &laid, &claims, &mover_file, &dead,
743 &atoms, None, &mut out, &mut seen_bytes, &mut sites, &mut flags));
744 },
745 Identity::Recorded | Identity::RecordedLocal => {
746 for f in files.keys() {
747 let scope: Vec<usize> = (0..pieces.len())
748 .filter(|i| pieces[*i].file == Some(*f))
749 .collect();
750 // A recorded identity confines every anchor to its file by
751 // construction, so a cycle can never cross one and the rules
752 // under trial have nothing to decide.
753 let laid = match res!(self.lay_out(&pieces, &scope, &claims,
754 Some(*f), voided, CycleRule::Demote, &mut flags))
755 {
756 Lay::Done(l) => l,
757 Lay::Void { .. } => return Err(err!(
758 "A recorded identity asked for a confinement."; Bug)),
759 };
760 res!(self.emit(&pieces, &scope, &laid, &claims, &mover_file, &dead,
761 &atoms, Some(*f), &mut out, &mut seen_bytes, &mut sites,
762 &mut flags));
763 }
764 // A slot recorded against a file no operation created renders
765 // nowhere, and the renderer says so rather than dropping it.
766 for p in &pieces {
767 match p.file {
768 Some(f) if files.contains_key(&f) => (),
769 _ => flags.orphan.push((p.place_op, p.sub)),
770 }
771 }
772 },
773 }
774
775 // 8. Torn moves, over the whole repository. A voided move owns nothing
776 // and would look torn to a register that could not tell why, so it is
777 // reported as confined instead: the two flags name different events and
778 // an author is owed the one that happened.
779 for op in &ops {
780 if let MOp::Move { id, src, .. } = op {
781 if voided.contains(id) {
782 continue;
783 }
784 let torn = src.iter().any(|r| r.ids().any(|cid| {
785 claims.get(&cid) != Some(id)
786 }));
787 if torn {
788 flags.torn.push(*id);
789 }
790 }
791 }
792 flags.confined = confined.to_vec();
793 flags.won = won.to_vec();
794
795 // 8a. A demotion that carried content over a file boundary. The
796 // comparison is between where the content was written and where the
797 // demoted placement put it, since once a two-file cycle has collapsed
798 // both ends of the demoted origin are in the same file.
799 for (op, sub) in flags.demoted.clone() {
800 let piece = pieces.iter()
801 .find(|p| p.place_op == op && p.sub == sub);
802 let piece = match piece {
803 Some(p) => p,
804 None => continue,
805 };
806 let home = match sites.birth.get(&piece.claim.op) {
807 Some(f) => *f,
808 None => continue,
809 };
810 let now = match sites.slot.get(&(op, sub)) {
811 Some(f) => *f,
812 None => continue,
813 };
814 if home != now {
815 flags.crossed.push((op, sub, home, now));
816 }
817 }
818
819 // 9. Files out, and the paths two of them may be fighting over.
820 let mut out_files: Vec<FileOut> = Vec::new();
821 for (id, info) in &files {
822 let (bytes, prov) = out.remove(id).unwrap_or_default();
823 out_files.push(FileOut {
824 file: *id,
825 path: info.path.clone(),
826 live: info.live,
827 bytes,
828 prov,
829 });
830 }
831 let mut by_path: BTreeMap<Vec<u8>, Vec<FileId>> = BTreeMap::new();
832 for f in out_files.iter().filter(|f| f.live) {
833 by_path.entry(f.path.clone()).or_default().push(f.file);
834 }
835 for (path, ids) in by_path {
836 if ids.len() > 1 {
837 flags.path_clash.push((path, ids));
838 }
839 }
840
841 // 10. Conservation, over the whole repository rather than one file.
842 //
843 // Every byte an operation created is dead, or rendered exactly once
844 // somewhere, or held back because the file holding it has been deleted.
845 // A byte rendered in two files at once is the failure this whole
846 // exercise exists to detect, and it is counted rather than assumed away.
847 let atom_bytes: usize = atoms.values().map(|v| v.len()).sum();
848 let rendered: usize = out_files.iter().map(|f| f.bytes.len()).sum();
849 let duplicated: usize = seen_bytes.values().map(|n| n - 1).sum();
850 flags.duplicated = duplicated;
851 let mut dead_live = 0usize;
852 for cid in &dead {
853 if let Some(a) = atoms.get(&cid.op) {
854 if (cid.off as usize) < a.len() {
855 dead_live += 1;
856 }
857 }
858 }
859 let withheld: usize = out_files.iter()
860 .filter(|f| !f.live)
861 .map(|f| f.bytes.len())
862 .sum();
863 let distinct = seen_bytes.len();
864 let lost = atom_bytes
865 .saturating_sub(distinct)
866 .saturating_sub(dead_live);
867 if distinct + dead_live + lost != atom_bytes {
868 return Err(err!(
869 "Conservation arithmetic does not close: {} distinct, {} dead, \
870 {} lost, {} created.", distinct, dead_live, lost, atom_bytes; Bug));
871 }
872
873 Ok(Attempt::Done(RepoRender {
874 files: out_files,
875 flags,
876 stats: MStats {
877 ops: ops.len(),
878 files: files.len(),
879 slots_placed,
880 slots_split: pieces.len(),
881 atom_bytes,
882 rendered,
883 withheld,
884 lost,
885 },
886 site: sites.site,
887 birth: sites.birth,
888 }))
889 }
890
891 /// The slot that currently owns a content id, within a scope.
892 ///
893 /// `None` where no slot in the scope owns it, which under a recorded
894 /// identity is what a cross-file anchor looks like from inside one file.
895 fn owner(
896 &self,
897 cid: &ContentId,
898 pieces: &[Piece],
899 by_place: &HashMap<OpId, Vec<usize>>,
900 claims: &HashMap<ContentId, OpId>,
901 scope_file: Option<FileId>,
902 demoted: bool,
903 )
904 -> Option<usize>
905 {
906 let owner_op = if demoted {
907 cid.op
908 } else {
909 match claims.get(cid) {
910 Some(id) => {
911 if self.ident.global_claims() {
912 *id
913 } else {
914 // A per-file register never saw a move routed to
915 // another file, so the byte still belongs to whoever
916 // created it as far as this file is concerned.
917 match scope_file {
918 Some(f) if self.mover_is(*id, f) => *id,
919 _ => cid.op,
920 }
921 }
922 },
923 None => cid.op,
924 }
925 };
926 let idxs = match by_place.get(&owner_op) {
927 Some(v) => v,
928 None => return None,
929 };
930 let key = (cid.op, cid.off);
931 let pos = idxs.partition_point(
932 |i| (pieces[*i].claim.op, pieces[*i].claim.from) <= key);
933 if pos > 0 {
934 let i = idxs[pos - 1];
935 if pieces[i].claim.contains(cid) {
936 return Some(i);
937 }
938 }
939 None
940 }
941
942 /// Whether the move `id` recorded the file `f` as its destination.
943 fn mover_is(&self, id: OpId, f: FileId) -> bool {
944 self.ops.iter().any(|o| match o {
945 MOp::Move { id: i, file, .. } => *i == id && *file == Some(f),
946 _ => false,
947 })
948 }
949
950 /// Lays out one scope of slots: resolves the anchors, breaks the cycles, and
951 /// returns a topological order.
952 ///
953 /// Under [`CycleRule::Demote`] a cycle is broken here and now, by design note
954 /// section 5.4. Under a confinement rule a cycle that crosses a file boundary
955 /// is not broken here at all: the layout stops and names the moves to void,
956 /// and the caller rebuilds the claim register without them. A cycle inside
957 /// one file is broken by demotion whatever the rule.
958 #[allow(clippy::too_many_arguments)]
959 fn lay_out(
960 &self,
961 pieces: &[Piece],
962 scope: &[usize],
963 claims: &HashMap<ContentId, OpId>,
964 scope_file: Option<FileId>,
965 voided: &BTreeSet<OpId>,
966 rule: CycleRule,
967 flags: &mut MFlags,
968 )
969 -> Outcome<Lay>
970 {
971 let n = scope.len();
972 let mut local: HashMap<usize, usize> = HashMap::new();
973 for (k, i) in scope.iter().enumerate() {
974 local.insert(*i, k);
975 }
976 let mut by_place: HashMap<OpId, Vec<usize>> = HashMap::new();
977 for i in scope {
978 by_place.entry(pieces[*i].place_op).or_default().push(*i);
979 }
980 let mut prev: Vec<Option<usize>> = vec![None; n];
981 for idxs in by_place.values_mut() {
982 idxs.sort_by_key(|i| (pieces[*i].claim.op, pieces[*i].claim.from));
983 let mut chain: Vec<usize> = idxs.clone();
984 chain.sort_by_key(|i| pieces[*i].sub);
985 for w in chain.windows(2) {
986 if let (Some(a), Some(b)) = (local.get(&w[0]), local.get(&w[1])) {
987 prev[*b] = Some(*a);
988 }
989 }
990 }
991
992 let mut dem: Vec<(bool, bool)> = vec![(false, false); n];
993 let mut drop: Vec<(bool, bool)> = vec![(false, false); n];
994 loop {
995 // Raised afresh on every pass, since a pass that ends in a demotion
996 // is thrown away and only the last one describes the render.
997 let mut off_file: Vec<(OpId, u32)> = Vec::new();
998 let mut deps: Vec<Vec<usize>> = vec![Vec::new(); n];
999 let mut left: Vec<Option<usize>> = vec![None; n];
1000 let mut right: Vec<Option<usize>> = vec![None; n];
1001 for k in 0..n {
1002 if let Some(x) = prev[k] {
1003 deps[k].push(x);
1004 continue;
1005 }
1006 let p = &pieces[scope[k]];
1007 for (side, is_left) in [(p.left, true), (p.right, false)] {
1008 let (cid, want) = match side {
1009 Some(a) => a,
1010 None => continue,
1011 };
1012 if is_left && want != Side::After {
1013 return Err(err!(
1014 "Left anchor {} binds before a byte; a left origin \
1015 binds after one.", cid; Invalid, Input));
1016 }
1017 if !is_left && want != Side::Before {
1018 return Err(err!(
1019 "Right anchor {} binds after a byte; a right origin \
1020 binds before one.", cid; Invalid, Input));
1021 }
1022 let dropped = if is_left { drop[k].0 } else { drop[k].1 };
1023 if dropped {
1024 continue;
1025 }
1026 let asked = if is_left { dem[k].0 } else { dem[k].1 };
1027 let mut got = self.owner(
1028 &cid, pieces, &by_place, claims, scope_file, asked);
1029 if got.is_none() && !asked {
1030 // The anchor names content that has left this file. A
1031 // recorded identity cannot follow it, so it falls back
1032 // to where the content was created.
1033 got = self.owner(
1034 &cid, pieces, &by_place, claims, scope_file, true);
1035 if got.is_some() {
1036 off_file.push((p.place_op, p.sub));
1037 }
1038 }
1039 let idx = match got.and_then(|g| local.get(&g).copied()) {
1040 Some(x) => x,
1041 None => {
1042 flags.dropped.push((p.place_op, p.sub));
1043 if is_left { drop[k].0 = true } else { drop[k].1 = true }
1044 continue;
1045 },
1046 };
1047 if is_left { left[k] = Some(idx) } else { right[k] = Some(idx) }
1048 deps[k].push(idx);
1049 }
1050 }
1051 let mut indeg: Vec<usize> = vec![0; n];
1052 let mut rev: Vec<Vec<usize>> = vec![Vec::new(); n];
1053 for k in 0..n {
1054 indeg[k] = deps[k].len();
1055 for d in &deps[k] {
1056 rev[*d].push(k);
1057 }
1058 }
1059 let mut ready: BTreeSet<(OpId, u32, usize)> = BTreeSet::new();
1060 for k in 0..n {
1061 if indeg[k] == 0 {
1062 ready.insert((pieces[scope[k]].place_op, pieces[scope[k]].sub, k));
1063 }
1064 }
1065 let mut order: Vec<usize> = Vec::with_capacity(n);
1066 while let Some(key) = ready.iter().next().copied() {
1067 ready.remove(&key);
1068 let k = key.2;
1069 order.push(k);
1070 for j in &rev[k] {
1071 indeg[*j] -= 1;
1072 if indeg[*j] == 0 {
1073 ready.insert((
1074 pieces[scope[*j]].place_op, pieces[scope[*j]].sub, *j));
1075 }
1076 }
1077 }
1078 if order.len() == n {
1079 flags.off_file.extend(off_file);
1080 return Ok(Lay::Done(Laid { order, left, right, prev }));
1081 }
1082 // A cycle remains: demote the lowest-op-order blocked slot.
1083 let mut stuck: Vec<usize> = (0..n)
1084 .filter(|k| indeg[*k] > 0 && prev[*k].is_none())
1085 .collect();
1086 stuck.sort_by_key(|k| (pieces[scope[*k]].place_op, pieces[scope[*k]].sub, *k));
1087 let victim = match stuck.first() {
1088 Some(v) => *v,
1089 None => return Err(err!(
1090 "Topological sort stalled with no blocked slot."; Bug)),
1091 };
1092 // Under a confinement rule, ask first whether this cycle crosses a
1093 // file boundary, and if it does, hand the decision back to the caller
1094 // rather than demoting anything.
1095 if rule.confines() {
1096 if let Some(cycle) = cyclic(&deps, &stuck, pieces, scope) {
1097 if let Some(v) = res!(self.confine(
1098 &cycle, pieces, scope, voided, rule, victim, flags))
1099 {
1100 return Ok(v);
1101 }
1102 }
1103 }
1104 let p = &pieces[scope[victim]];
1105 if !dem[victim].0 && p.left.is_some() {
1106 dem[victim].0 = true;
1107 flags.demoted.push((p.place_op, p.sub));
1108 } else if !dem[victim].1 && p.right.is_some() {
1109 dem[victim].1 = true;
1110 flags.demoted.push((p.place_op, p.sub));
1111 } else if !drop[victim].0 && p.left.is_some() {
1112 drop[victim].0 = true;
1113 flags.dropped.push((p.place_op, p.sub));
1114 } else if !drop[victim].1 && p.right.is_some() {
1115 drop[victim].1 = true;
1116 flags.dropped.push((p.place_op, p.sub));
1117 } else {
1118 return Err(err!(
1119 "Cycle through slot {}+{} survives demotion and dropping.",
1120 p.place_op, p.sub; Bug));
1121 }
1122 }
1123 }
1124
1125 /// Decides what a confinement rule does with one cycle.
1126 ///
1127 /// Returns `None` where the rule declines, in which case the caller falls
1128 /// back to design note section 5.4's demotion: that is what happens to a
1129 /// cycle that stays inside one file, to a cycle with no voidable move in it,
1130 /// and to a cycle every one of whose members is informed.
1131 ///
1132 /// **How a cycle is judged to cross a boundary.** Asking which file a
1133 /// member's content is in is circular while the cycle is unbroken, so the
1134 /// question is asked of a repository in which the whole cycle is voided.
1135 /// That repository is well defined and cheap: voiding every member removes
1136 /// every edge of the cycle, so it lays out, and each member then has a
1137 /// *source* file -- where its content sits when it does not move it -- and a
1138 /// *destination* file -- where the content its origin names sits. A cycle
1139 /// crosses a boundary when some member's two differ.
1140 #[allow(clippy::too_many_arguments)]
1141 fn confine(
1142 &self,
1143 cycle: &[usize],
1144 pieces: &[Piece],
1145 scope: &[usize],
1146 voided: &BTreeSet<OpId>,
1147 rule: CycleRule,
1148 victim: usize,
1149 flags: &mut MFlags,
1150 )
1151 -> Outcome<Option<Lay>>
1152 {
1153 // The moves the cycle runs through, in op order. A splice in a cycle is
1154 // not voidable: voiding an insertion would destroy content, and no rule
1155 // under trial proposes it.
1156 let mut members: Vec<OpId> = Vec::new();
1157 for k in cycle {
1158 let op = pieces[scope[*k]].place_op;
1159 if self.is_move(&op) && !voided.contains(&op) && !members.contains(&op) {
1160 members.push(op);
1161 }
1162 }
1163 members.sort();
1164 if members.is_empty() {
1165 flags.declined[0] += 1;
1166 return Ok(None);
1167 }
1168
1169 // A member crosses a boundary if its content and its destination are in
1170 // different files, and that question is asked twice, of two different
1171 // repositories, because neither answer alone is sound.
1172 //
1173 // **Where the bytes were written.** One layout with every move voided,
1174 // acyclic by construction: an origin names content its author had
1175 // already seen, so with no claims in play every edge runs strictly
1176 // downwards in op order. This is the reading of "its origin file" that
1177 // the confinement rule is named for, and it is the only one that sees a
1178 // cycle whose members supersede an earlier move of their own.
1179 //
1180 // **Where the bytes would be if this cycle did not happen.** One layout
1181 // with the cycle's members voided and nothing else. This is what catches
1182 // a cycle between two blocks that both left the files they were born in,
1183 // which the first reading calls a single file and which is not one.
1184 let birth = res!(self.homes());
1185 let mut without: BTreeSet<OpId> = voided.clone();
1186 for m in &members {
1187 without.insert(*m);
1188 }
1189 let site = match res!(self.attempt(&without, &[], &[], CycleRule::Demote)) {
1190 Attempt::Done(r) => r.site,
1191 Attempt::Void { .. } => return Err(err!(
1192 "A trial render under the status quo asked for a confinement."; Bug)),
1193 };
1194
1195 let mut home: BTreeMap<OpId, FileId> = BTreeMap::new();
1196 let mut dest: BTreeMap<OpId, FileId> = BTreeMap::new();
1197 let mut cross: Vec<OpId> = Vec::new();
1198 for m in &members {
1199 let op = match self.ops.iter().find(|o| o.id() == *m) {
1200 Some(o) => o,
1201 None => continue,
1202 };
1203 if let MOp::Move { src, left, right, .. } = op {
1204 let anchor = match left.or(*right) {
1205 Some((cid, _)) => cid,
1206 None => continue,
1207 };
1208 let born_to = birth.get(&anchor.op).copied();
1209 let now_to = site.get(&anchor).copied();
1210 let mut h = None;
1211 let mut differs = false;
1212 for r in src {
1213 let first = ContentId::new(r.op, r.from);
1214 let born_from = birth.get(&r.op).copied();
1215 let now_from = site.get(&first).copied();
1216 if h.is_none() {
1217 h = now_from.or(born_from);
1218 }
1219 if born_from.is_some() && born_from != born_to {
1220 differs = true;
1221 }
1222 if now_from.is_some() && now_to.is_some() && now_from != now_to {
1223 differs = true;
1224 }
1225 }
1226 let h = match h {
1227 Some(f) => f,
1228 None => continue,
1229 };
1230 let d = match now_to.or(born_to) {
1231 Some(f) => f,
1232 None => continue,
1233 };
1234 home.insert(*m, h);
1235 dest.insert(*m, d);
1236 if differs {
1237 cross.push(*m);
1238 }
1239 }
1240 }
1241 if cross.is_empty() {
1242 flags.declined[1] += 1;
1243 return Ok(None);
1244 }
1245
1246 // A member that saw another member is informed rather than racing, and an
1247 // informed move is not voided for racing something it did not race. This
1248 // is the distinction the torn flag had to learn: the claim register
1249 // cannot tell a race from a sequence, and the parents can.
1250 //
1251 // The exemption is for the *last* informed member only. A first form of
1252 // this guard exempted every member with another member in its past, which
1253 // a chain of moves defeats: where a replica has made three moves in a row,
1254 // each informed by the one before it, every member but the first is
1255 // exempt, and where the first is not the one that has to go, the rule
1256 // declines and the collapse it exists to prevent happens anyway. A
1257 // member that is itself superseded by a later member is not owed the
1258 // exemption, since its own author has already moved on.
1259 let meta = self.meta.borrow();
1260 let informed = |m: &OpId| {
1261 members.iter().any(|n| n != m && meta.before(n, m))
1262 && !members.iter().any(|n| n != m && meta.before(m, n))
1263 };
1264
1265 let chosen: Vec<OpId> = match rule {
1266 CycleRule::Demote => Vec::new(),
1267 CycleRule::ConfineVictim => {
1268 let v = pieces[scope[victim]].place_op;
1269 if cross.contains(&v) && !informed(&v) {
1270 vec![v]
1271 } else {
1272 Vec::new()
1273 }
1274 },
1275 CycleRule::ConfineCycle =>
1276 cross.iter().copied().filter(|m| !informed(m)).collect(),
1277 CycleRule::LowestEdge =>
1278 cross.iter().copied().find(|m| !informed(m)).into_iter().collect(),
1279 CycleRule::WholeCycle => {
1280 // Where the cycle runs through only one move -- its other members
1281 // being splices, or the move anchoring inside its own source --
1282 // there is nothing to arbitrate between, and a winner-takes-all
1283 // rule that keeps its only member breaks no cycle at all. Of the
1284 // 774 cycles this rule declined in the general sweep, 232 were of
1285 // that shape and every one fell back to demotion, so the rule is
1286 // completed here: with one move in the cycle, confine it.
1287 if members.len() == 1 {
1288 cross.iter().copied().filter(|m| !informed(m)).collect()
1289 } else {
1290 let winner = members.iter().copied().max();
1291 members.iter()
1292 .copied()
1293 .filter(|m| Some(*m) != winner && !informed(m))
1294 .collect()
1295 }
1296 },
1297 };
1298 if chosen.is_empty() {
1299 flags.declined[2] += 1;
1300 return Ok(None);
1301 }
1302 let winner = match rule {
1303 CycleRule::WholeCycle if members.len() == 1 => None,
1304 CycleRule::WholeCycle => members.iter().copied().max(),
1305 CycleRule::LowestEdge => members.iter()
1306 .copied()
1307 .filter(|m| !chosen.contains(m))
1308 .max(),
1309 _ => None,
1310 };
1311 let mut ops: Vec<(OpId, FileId, FileId)> = Vec::new();
1312 for m in chosen {
1313 let h = match home.get(&m) {
1314 Some(f) => *f,
1315 None => continue,
1316 };
1317 let d = match dest.get(&m) {
1318 Some(f) => *f,
1319 None => h,
1320 };
1321 ops.push((m, h, d));
1322 }
1323 if ops.is_empty() {
1324 flags.declined[2] += 1;
1325 return Ok(None);
1326 }
1327 Ok(Some(Lay::Void { ops, winner }))
1328 }
1329
1330 /// The file every atom was written into.
1331 ///
1332 /// Rendered with every move voided, so that the answer is where the content
1333 /// would be if nothing had ever been moved, which is what "its origin file"
1334 /// means. The layout is always acyclic, so this never recurses.
1335 fn homes(&self) -> Outcome<HashMap<OpId, FileId>> {
1336 let all: BTreeSet<OpId> = self.ops.iter()
1337 .filter(|o| o.is_move())
1338 .map(|o| o.id())
1339 .collect();
1340 match res!(self.attempt(&all, &[], &[], CycleRule::Demote)) {
1341 Attempt::Done(r) => Ok(r.birth),
1342 Attempt::Void { .. } => Err(err!(
1343 "A render with every move voided asked for a confinement."; Bug)),
1344 }
1345 }
1346
1347 /// Whether an operation identity names a move.
1348 fn is_move(&self, id: &OpId) -> bool {
1349 self.ops.iter().any(|o| o.id() == *id && o.is_move())
1350 }
1351
1352 /// Builds the Fugue tree over a laid-out scope, walks it, and appends each
1353 /// slot's bytes to the file the slot turns out to belong to.
1354 #[allow(clippy::too_many_arguments)]
1355 fn emit(
1356 &self,
1357 pieces: &[Piece],
1358 scope: &[usize],
1359 laid: &Laid,
1360 claims: &HashMap<ContentId, OpId>,
1361 mover_file: &HashMap<OpId, Option<FileId>>,
1362 dead: &HashSet<ContentId>,
1363 atoms: &BTreeMap<OpId, Vec<u8>>,
1364 scope_file: Option<FileId>,
1365 out: &mut BTreeMap<FileId, (Vec<u8>, Vec<ContentId>)>,
1366 seen: &mut HashMap<ContentId, usize>,
1367 sites: &mut Sites,
1368 flags: &mut MFlags,
1369 )
1370 -> Outcome<()>
1371 {
1372 let n = scope.len();
1373 let root = n;
1374 const LOG: usize = 20;
1375 let mut parent: Vec<u32> = vec![root as u32; n + 1];
1376 let mut side: Vec<ChildSide> = vec![ChildSide::Right; n + 1];
1377 let mut depth: Vec<u32> = vec![0; n + 1];
1378 let mut up: Vec<[u32; LOG]> = vec![[root as u32; LOG]; n + 1];
1379 let mut kids_l: Vec<Vec<usize>> = vec![Vec::new(); n + 1];
1380 let mut kids_r: Vec<Vec<usize>> = vec![Vec::new(); n + 1];
1381 // Which file each slot belongs to, read off the tree under a derived
1382 // identity and off the scope under a recorded one.
1383 let mut owner_file: Vec<Option<FileId>> = vec![scope_file; n];
1384
1385 for &k in &laid.order {
1386 let (par, sd) = if let Some(prev) = laid.prev[k] {
1387 (prev, ChildSide::Right)
1388 } else {
1389 match (laid.left[k], laid.right[k]) {
1390 (None, None) => (root, ChildSide::Right),
1391 (None, Some(r)) => (r, ChildSide::Left),
1392 (Some(l), None) => (l, ChildSide::Right),
1393 (Some(l), Some(r)) => {
1394 if right_subtree(l, r, &depth, &up, &parent, &side, LOG) {
1395 (r, ChildSide::Left)
1396 } else {
1397 match successor(l, &kids_l, &kids_r, &parent, &side, root) {
1398 Some(s) if right_subtree(
1399 l, s, &depth, &up, &parent, &side, LOG)
1400 => (s, ChildSide::Left),
1401 _ => (l, ChildSide::Right),
1402 }
1403 }
1404 },
1405 }
1406 };
1407 if par == k {
1408 return Err(err!(
1409 "Slot {}+{} resolved to itself as parent.",
1410 pieces[scope[k]].place_op, pieces[scope[k]].sub; Bug));
1411 }
1412 parent[k] = par as u32;
1413 side[k] = sd;
1414 depth[k] = depth[par] + 1;
1415 up[k][0] = par as u32;
1416 for j in 1..LOG {
1417 up[k][j] = up[up[k][j - 1] as usize][j - 1];
1418 }
1419 if self.ident.seeds() {
1420 owner_file[k] = if par == root {
1421 if pieces[scope[k]].seed {
1422 Some(pieces[scope[k]].place_op)
1423 } else {
1424 flags.orphan.push((pieces[scope[k]].place_op, pieces[scope[k]].sub));
1425 None
1426 }
1427 } else {
1428 owner_file[par]
1429 };
1430 }
1431 let list = match sd {
1432 ChildSide::Left => &mut kids_l[par],
1433 ChildSide::Right => &mut kids_r[par],
1434 };
1435 let key = (pieces[scope[k]].place_op, pieces[scope[k]].sub, k);
1436 let pos = list.partition_point(|j| (
1437 pieces[scope[*j]].place_op, pieces[scope[*j]].sub, *j) < key);
1438 list.insert(pos, k);
1439 }
1440
1441 let mut stack: Vec<(usize, bool)> = vec![(root, false)];
1442 while let Some((k, done)) = stack.pop() {
1443 if done {
1444 if k == root {
1445 continue;
1446 }
1447 let p = &pieces[scope[k]];
1448 let file = match owner_file[k] {
1449 Some(f) => f,
1450 None => continue,
1451 };
1452 let atom = match atoms.get(&p.claim.op) {
1453 Some(a) => a,
1454 None => return Err(err!(
1455 "Slot claims content of unknown atom {}.",
1456 p.claim.op; Invalid, Input)),
1457 };
1458 // Where this slot sits, and where the content it shows was
1459 // written. Neither is part of any rule; they are how one render
1460 // tells another what a file would hold if a move were voided.
1461 sites.slot.insert((p.place_op, p.sub), file);
1462 if p.place_op == p.claim.op {
1463 sites.birth.insert(p.claim.op, file);
1464 }
1465 for cid in p.claim.ids() {
1466 let owner_op = match claims.get(&cid) {
1467 Some(id) => {
1468 if self.ident.global_claims() {
1469 *id
1470 } else {
1471 match mover_file.get(id) {
1472 Some(Some(f)) if *f == file => *id,
1473 _ => cid.op,
1474 }
1475 }
1476 },
1477 None => cid.op,
1478 };
1479 if owner_op != p.place_op {
1480 continue;
1481 }
1482 // Recorded before liveness, since a dead byte still sits in a
1483 // file: an origin anchor is dead and its file is the file.
1484 sites.site.insert(cid, file);
1485 if dead.contains(&cid) {
1486 continue;
1487 }
1488 let b = match atom.get(cid.off as usize) {
1489 Some(b) => *b,
1490 None => return Err(err!(
1491 "Content id {} is beyond its atom.", cid; Invalid, Input)),
1492 };
1493 *seen.entry(cid).or_insert(0) += 1;
1494 let slot = out.entry(file).or_default();
1495 slot.0.push(b);
1496 slot.1.push(cid);
1497 }
1498 continue;
1499 }
1500 for c in kids_r[k].iter().rev() {
1501 stack.push((*c, false));
1502 }
1503 stack.push((k, true));
1504 for c in kids_l[k].iter().rev() {
1505 stack.push((*c, false));
1506 }
1507 }
1508 Ok(())
1509 }
1510}
1511
1512/// Which side of its parent a Fugue node sits on.
1513#[derive(Clone, Copy, PartialEq, Eq, Debug)]
1514enum ChildSide {
1515 Left,
1516 Right,
1517}
1518
1519/// Where the render found everything, which is measurement rather than rule.
1520#[derive(Clone, Default, Debug)]
1521struct Sites {
1522 /// The file each content id sits in, dead bytes included.
1523 site: HashMap<ContentId, FileId>,
1524 /// The file each atom was written into, read off the slot its creating
1525 /// splice placed.
1526 birth: HashMap<OpId, FileId>,
1527 /// The file each slot sits in.
1528 slot: HashMap<(OpId, u32), FileId>,
1529}
1530
1531/// What one pass of the render produced.
1532enum Attempt {
1533 /// A finished render.
1534 Done(RepoRender),
1535 /// A confinement decision: void these moves and render again.
1536 Void {
1537 /// The move, the file its content stays in, and the file it was denied.
1538 ops: Vec<(OpId, FileId, FileId)>,
1539 /// The move that wins the cycle outright, where the rule names one.
1540 winner: Option<OpId>,
1541 },
1542}
1543
1544/// What one pass of the layout produced.
1545enum Lay {
1546 /// A topological order.
1547 Done(Laid),
1548 /// A confinement decision, to be taken by the caller.
1549 Void {
1550 /// The move, the file its content stays in, and the file it was denied.
1551 ops: Vec<(OpId, FileId, FileId)>,
1552 /// The move that wins the cycle outright, where the rule names one.
1553 winner: Option<OpId>,
1554 },
1555}
1556
1557/// The strongly connected component of the first blocked slot that lies on a
1558/// cycle, in op order, or `None` where no blocked slot does.
1559///
1560/// A blocked slot need not be on a cycle -- it may merely sit downstream of one
1561/// -- and a rule that voids a move has to know the difference, where a rule that
1562/// demotes an origin does not.
1563fn cyclic(
1564 deps: &[Vec<usize>],
1565 stuck: &[usize],
1566 pieces: &[Piece],
1567 scope: &[usize],
1568)
1569 -> Option<Vec<usize>>
1570{
1571 let n = deps.len();
1572 let mut rev: Vec<Vec<usize>> = vec![Vec::new(); n];
1573 for (k, ds) in deps.iter().enumerate() {
1574 for d in ds {
1575 rev[*d].push(k);
1576 }
1577 }
1578 for v in stuck {
1579 let fwd = reach(deps, *v);
1580 let back = reach(&rev, *v);
1581 let mut scc: Vec<usize> = (0..n).filter(|k| fwd[*k] && back[*k]).collect();
1582 if scc.len() > 1 || deps[*v].contains(v) {
1583 scc.sort_by_key(|k| (pieces[scope[*k]].place_op, pieces[scope[*k]].sub, *k));
1584 return Some(scc);
1585 }
1586 }
1587 None
1588}
1589
1590/// Every node reachable from `from`, itself included.
1591fn reach(adj: &[Vec<usize>], from: usize) -> Vec<bool> {
1592 let mut seen = vec![false; adj.len()];
1593 let mut stack = vec![from];
1594 seen[from] = true;
1595 while let Some(k) = stack.pop() {
1596 for d in &adj[k] {
1597 if !seen[*d] {
1598 seen[*d] = true;
1599 stack.push(*d);
1600 }
1601 }
1602 }
1603 seen
1604}
1605
1606/// A laid-out scope: the topological order and the origins it was computed
1607/// against, all in scope-local indices.
1608struct Laid {
1609 order: Vec<usize>,
1610 left: Vec<Option<usize>>,
1611 right: Vec<Option<usize>>,
1612 prev: Vec<Option<usize>>,
1613}
1614
1615/// The in-order successor of `v` among the nodes placed so far.
1616fn successor(
1617 v: usize,
1618 kids_l: &[Vec<usize>],
1619 kids_r: &[Vec<usize>],
1620 parent: &[u32],
1621 side: &[ChildSide],
1622 root: usize,
1623)
1624 -> Option<usize>
1625{
1626 if let Some(c) = kids_r[v].first() {
1627 let mut cur = *c;
1628 while let Some(x) = kids_l[cur].first() {
1629 cur = *x;
1630 }
1631 return Some(cur);
1632 }
1633 let mut cur = v;
1634 loop {
1635 let p = parent[cur] as usize;
1636 if p == cur || p == root {
1637 return None;
1638 }
1639 if side[cur] == ChildSide::Left {
1640 return Some(p);
1641 }
1642 cur = p;
1643 }
1644}
1645
1646/// Whether `r` lies in the right subtree of `l`, by binary lifting.
1647fn right_subtree(
1648 l: usize,
1649 r: usize,
1650 depth: &[u32],
1651 up: &[[u32; 20]],
1652 parent: &[u32],
1653 side: &[ChildSide],
1654 log: usize,
1655)
1656 -> bool
1657{
1658 if depth[r] <= depth[l] {
1659 return false;
1660 }
1661 let mut climb = depth[r] - depth[l] - 1;
1662 let mut cur = r;
1663 let mut k = 0usize;
1664 while climb > 0 && k < log {
1665 if climb & 1 == 1 {
1666 cur = up[cur][k] as usize;
1667 }
1668 climb >>= 1;
1669 k += 1;
1670 }
1671 parent[cur] as usize == l && side[cur] == ChildSide::Right
1672}