Oregami
Repositories/oxedyne/fe2o3

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

50.6 KiB, 534 runs

created by r1870400018:17914, 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//! Turning the ordered slots back into bytes, and saying what happened.
2//!
3//! The forest is built in the topological order of the anchor graph and walked
4//! in order, and each slot emits the parts of its claim that it still owns and
5//! that are still alive, into the file whose subtree it turned out to be in.
6//! Everything the walk noticed is returned with the bytes as a [`Flag`], because
7//! a structure that always converges owes the reader an account of what it
8//! converged to: a torn move, an anchor demoted to break a cycle, a move confined
9//! because it lost a cross-file cycle, a splice that lost an overlap arbitration,
10//! content moved into a file that has since been deleted, or an edit whose context
11//! or whose whole file a concurrent operation deleted. Flags are facts derived from
12//! the operation set, not a log of what the renderer happened to do, so two
13//! replicas holding the same operations report the same flags.
14//!
15//! # Notes are resolved here too
16//!
17//! An [`crate::op::Op::Note`] names content and renders none. What a reader wants
18//! is where that content ended up, and the render is the one place that is known,
19//! so the same walk that produced the bytes is read backwards to produce a
20//! [`Note`]: the note's identity, its text, and the spans of rendered bytes its
21//! content occupies. A note is resolved against a file where its content renders
22//! there, against the repository once however many files it is scattered over, and
23//! reported as [`RepoNote::on_dead`] where its content renders nowhere at all.
24//! Like a flag, a resolved note is a function of the operation set alone.
25//!
26//! That backwards reading is [`Placement`], and it is public because a note is
27//! not the only thing that names content and wants a position: a flag names
28//! content too, and a reader of one wants the file and the offset rather than an
29//! offset into an operation. Content that renders nowhere is answered with no
30//! place, which is the truth about it.
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};
41use crate::op::{
42 Mode,
43 Op,
44};
45use crate::seq::atom::Atoms;
46use crate::seq::claim::{
47 Claims,
48 Dead,
49};
50use crate::seq::slot::{
51 Order,
52 Origin,
53 Slots,
54};
55use crate::seq::OpOrder;
56
57use oxedyne_fe2o3_core::prelude::*;
58use oxedyne_fe2o3_jdat::prelude::*;
59
60use std::collections::BTreeMap;
61use std::ops::Range;
62
63
64//// Flag wire codes.
65pub const CODE_TORN: u8 = 1;
66pub const CODE_DEMOTED: u8 = 2;
67pub const CODE_DROPPED: u8 = 3;
68pub const CODE_OVERLAP: u8 = 4;
69pub const CODE_CROSSED_FILE: u8 = 5;
70pub const CODE_MOVED_INTO_DELETED: u8 = 6;
71pub const CODE_ORPHANED: u8 = 7;
72pub const CODE_CONFINED: u8 = 8;
73pub const CODE_WON: u8 = 9;
74pub const CODE_STRANDED: u8 = 10;
75pub const CODE_SPLICED_INTO_DELETED: u8 = 11;
76pub const CODE_YIELDED: u8 = 12;
77
78
79/// Something the renderer noticed that the reader should be told.
80///
81/// Every flag is a function of the operation set, so the same set flags the same
82/// things everywhere. None of them means the render failed; each means the
83/// render made a choice that a person might want to revisit.
84#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
85pub enum Flag {
86 // A concurrent move took this move's source: the block tore at the overlap and
87 // its pieces render in two places. A move superseded on purpose, by a later
88 // move of the same content, is a sequence of two decisions rather than a race,
89 // and raises nothing.
90 Torn {
91 op: OpId,
92 lost: Vec<ContentRange>, // content it named and no longer shows
93 },
94 // An origin resolved against the splice that created its content rather than
95 // against the slot that now shows it, to break a cycle. The placement lands
96 // where its anchor content was written rather than where it now lives, which
97 // is deterministic and surprising in equal measure.
98 Demoted {
99 op: OpId,
100 sub: u64, // offset within that operation's placement
101 origin: Origin,
102 },
103 // An origin dropped entirely because demotion did not break the cycle, so the
104 // placement fell back to whatever the partly built tree gave it.
105 Dropped {
106 op: OpId,
107 sub: u64, // offset within that operation's placement
108 origin: Origin,
109 },
110 // Two concurrent operations named overlapping content: both removed it, both
111 // moved it, or one removed what the other moved. This is the raw fact beneath
112 // the arbitration, and the only flag that says which two operations actually
113 // met; it fires over a move as well as a splice, where the arbitration is
114 // confined to splices.
115 Overlap {
116 ops: Vec<OpId>, // ascending by identifier
117 region: ContentRange,
118 },
119 // Breaking a cycle carried content across a file boundary: the placement was
120 // demoted, and what it holds was written into one file and renders in another.
121 // A cross-file cycle is arbitrated rather than demoted, so what still reaches
122 // this is a demotion inside one file whose content had changed files earlier.
123 CrossedFile {
124 op: OpId,
125 sub: u64, // offset within that operation's placement
126 from: OpId, // the file the content it holds was written into
127 to: OpId, // the file it renders in instead
128 },
129 // A move landed content in a file that has been deleted, so the content is
130 // held by a slot and named by the log but rendered nowhere a reader looks.
131 // Nothing is lost; what is lost is visibility.
132 MovedIntoDeleted {
133 op: OpId,
134 file: OpId, // which is not live
135 },
136 // A slot ended up in no file at all, its origins having been dropped, so the
137 // bytes it owns render nowhere. A fault rather than a choice, and reported
138 // rather than hidden because conservation must account for the bytes.
139 Orphaned {
140 op: OpId,
141 sub: u64, // offset within that operation's placement
142 },
143 // A move that lost a cross-file cycle: it did not happen, and its content is
144 // where it was before. The cycle is arbitrated as one concurrent group, the
145 // member highest in op order completes, and the rest write no claims at all,
146 // so nothing has to be undone.
147 Confined {
148 op: OpId,
149 home: OpId, // the file its content stays in
150 denied: OpId, // the file it was aimed at and did not reach
151 },
152 // A move that won a cross-file cycle outright and completed. Derivable from
153 // the confinements and kept anyway: the loser's flag reads badly alone, and
154 // the two together are the whole story of what the arbitration did.
155 Won {
156 op: OpId,
157 },
158 // A splice whose insertion anchored into content a concurrent operation
159 // deleted: every neighbour it was written beside is a tombstone, so the bytes
160 // render as a fragment at the deletion site. This is what a capture-side
161 // "move" -- a deletion in one file and a fresh insertion in another -- does to
162 // a concurrent edit inside the block. It fires only where no anchored
163 // neighbour survives, and names one concurrent deleter per flag.
164 Stranded {
165 op: OpId,
166 by: OpId, // the concurrent operation that deleted the context
167 },
168 // A splice that placed content in a file a concurrent Op::FileDelete retired.
169 // Every edit ever made goes dark when its file is deliberately deleted, and
170 // flagging all of them would bury the one fact worth raising: an edit and a
171 // deletion that raced, neither author able to see the other's decision.
172 SplicedIntoDeleted {
173 op: OpId,
174 file: OpId, // which is not live
175 del: OpId, // the concurrent deletion the splice did not see
176 },
177 // A splice that lost an overlap arbitration: its removals did not bury and its
178 // insertion is buried whole, so the edit is in the log and not in the file.
179 // The decision is the group's and not a pair's, a group being a connected
180 // component of the overlap graph, so a yielder routinely never named a byte
181 // the prevailing operation named. The region then reads as whole hunks, never
182 // an interleave, though not always as one author's: a member in the winner's
183 // causal past keeps its work.
184 Yielded {
185 op: OpId,
186 to: OpId, // the group's op-order maximum, which prevailed
187 group: Vec<OpId>, // ascending op order, so that the last is `to`
188 through: Option<OpId>, // the buried insertion this one sits inside
189 },
190}
191
192
193impl Flag {
194 pub fn code(&self) -> u8 {
195 match self {
196 Self::Torn { .. } => CODE_TORN,
197 Self::Demoted { .. } => CODE_DEMOTED,
198 Self::Dropped { .. } => CODE_DROPPED,
199 Self::Overlap { .. } => CODE_OVERLAP,
200 Self::CrossedFile { .. } => CODE_CROSSED_FILE,
201 Self::MovedIntoDeleted { .. } => CODE_MOVED_INTO_DELETED,
202 Self::Orphaned { .. } => CODE_ORPHANED,
203 Self::Confined { .. } => CODE_CONFINED,
204 Self::Won { .. } => CODE_WON,
205 Self::Stranded { .. } => CODE_STRANDED,
206 Self::SplicedIntoDeleted { .. } => CODE_SPLICED_INTO_DELETED,
207 Self::Yielded { .. } => CODE_YIELDED,
208 }
209 }
210
211 pub fn name(&self) -> &'static str {
212 match self {
213 Self::Torn { .. } => "Torn",
214 Self::Demoted { .. } => "Demoted",
215 Self::Dropped { .. } => "Dropped",
216 Self::Overlap { .. } => "Overlap",
217 Self::CrossedFile { .. } => "CrossedFile",
218 Self::MovedIntoDeleted { .. } => "MovedIntoDeleted",
219 Self::Orphaned { .. } => "Orphaned",
220 Self::Confined { .. } => "Confined",
221 Self::Won { .. } => "Won",
222 Self::Stranded { .. } => "Stranded",
223 Self::SplicedIntoDeleted { .. } => "SplicedIntoDeleted",
224 Self::Yielded { .. } => "Yielded",
225 }
226 }
227
228 /// The operation the flag is chiefly about.
229 pub fn op(&self) -> Option<OpId> {
230 match self {
231 Self::Torn { op, .. } => Some(*op),
232 Self::Demoted { op, .. } => Some(*op),
233 Self::Dropped { op, .. } => Some(*op),
234 Self::Overlap { .. } => None,
235 Self::CrossedFile { op, .. } => Some(*op),
236 Self::MovedIntoDeleted { op, .. } => Some(*op),
237 Self::Orphaned { op, .. } => Some(*op),
238 Self::Confined { op, .. } => Some(*op),
239 Self::Won { op } => Some(*op),
240 Self::Stranded { op, .. } => Some(*op),
241 Self::SplicedIntoDeleted { op, .. } => Some(*op),
242 Self::Yielded { op, .. } => Some(*op),
243 }
244 }
245
246 /// The wire shape is `[code, field, ...]`, the fields in declaration order.
247 pub fn to_dat(&self) -> Dat {
248 match self {
249 Self::Torn { op, lost } => Dat::List(vec![
250 Dat::U8(CODE_TORN),
251 op.to_dat(),
252 Dat::List(lost.iter().map(|r| r.to_dat()).collect()),
253 ]),
254 Self::Demoted { op, sub, origin } => Dat::List(vec![
255 Dat::U8(CODE_DEMOTED),
256 op.to_dat(),
257 Dat::U64(*sub),
258 Dat::U8(origin.code()),
259 ]),
260 Self::Dropped { op, sub, origin } => Dat::List(vec![
261 Dat::U8(CODE_DROPPED),
262 op.to_dat(),
263 Dat::U64(*sub),
264 Dat::U8(origin.code()),
265 ]),
266 Self::Overlap { ops, region } => Dat::List(vec![
267 Dat::U8(CODE_OVERLAP),
268 Dat::List(ops.iter().map(|id| id.to_dat()).collect()),
269 region.to_dat(),
270 ]),
271 Self::CrossedFile { op, sub, from, to } => Dat::List(vec![
272 Dat::U8(CODE_CROSSED_FILE),
273 op.to_dat(),
274 Dat::U64(*sub),
275 from.to_dat(),
276 to.to_dat(),
277 ]),
278 Self::MovedIntoDeleted { op, file } => Dat::List(vec![
279 Dat::U8(CODE_MOVED_INTO_DELETED),
280 op.to_dat(),
281 file.to_dat(),
282 ]),
283 Self::Orphaned { op, sub } => Dat::List(vec![
284 Dat::U8(CODE_ORPHANED),
285 op.to_dat(),
286 Dat::U64(*sub),
287 ]),
288 Self::Confined { op, home, denied } => Dat::List(vec![
289 Dat::U8(CODE_CONFINED),
290 op.to_dat(),
291 home.to_dat(),
292 denied.to_dat(),
293 ]),
294 Self::Won { op } => Dat::List(vec![
295 Dat::U8(CODE_WON),
296 op.to_dat(),
297 ]),
298 Self::Stranded { op, by } => Dat::List(vec![
299 Dat::U8(CODE_STRANDED),
300 op.to_dat(),
301 by.to_dat(),
302 ]),
303 Self::SplicedIntoDeleted { op, file, del } => Dat::List(vec![
304 Dat::U8(CODE_SPLICED_INTO_DELETED),
305 op.to_dat(),
306 file.to_dat(),
307 del.to_dat(),
308 ]),
309 Self::Yielded { op, to, group, through } => Dat::List(vec![
310 Dat::U8(CODE_YIELDED),
311 op.to_dat(),
312 to.to_dat(),
313 Dat::List(group.iter().map(|id| id.to_dat()).collect()),
314 Dat::Opt(Box::new(through.as_ref().map(|id| id.to_dat()))),
315 ]),
316 }
317 }
318
319 pub fn from_dat(dat: &Dat)
320 -> Outcome<Self>
321 {
322 let v = match dat {
323 Dat::List(v) if !v.is_empty() => v,
324 _ => return Err(err!(
325 "A Flag expects a non-empty Dat::List, got {:?}.", dat;
326 Decode, Input, Mismatch)),
327 };
328 let code = match &v[0] {
329 Dat::U8(c) => *c,
330 other => return Err(err!(
331 "A Flag code expects Dat::U8, got {:?}.", other;
332 Decode, Input, Mismatch)),
333 };
334 match code {
335 CODE_TORN => {
336 res!(flag_len(v, 3, "Torn"));
337 Ok(Self::Torn {
338 op: res!(OpId::from_dat(&v[1])),
339 lost: res!(flag_ranges(&v[2], "Torn lost")),
340 })
341 },
342 CODE_DEMOTED | CODE_DROPPED => {
343 let what = if code == CODE_DEMOTED { "Demoted" } else { "Dropped" };
344 res!(flag_len(v, 4, what));
345 let op = res!(OpId::from_dat(&v[1]));
346 let sub = res!(flag_u64(&v[2], what, "offset"));
347 let origin = res!(flag_origin(&v[3], what));
348 Ok(if code == CODE_DEMOTED {
349 Self::Demoted { op, sub, origin }
350 } else {
351 Self::Dropped { op, sub, origin }
352 })
353 },
354 CODE_OVERLAP => {
355 res!(flag_len(v, 3, "Overlap"));
356 let listed = match &v[1] {
357 Dat::List(l) => l,
358 other => return Err(err!(
359 "A Flag::Overlap operation list expects Dat::List, got {:?}.",
360 other;
361 Decode, Input, Mismatch)),
362 };
363 let mut ops = Vec::with_capacity(listed.len());
364 for item in listed {
365 ops.push(res!(OpId::from_dat(item)));
366 }
367 Ok(Self::Overlap {
368 ops,
369 region: res!(ContentRange::from_dat(&v[2])),
370 })
371 },
372 CODE_CROSSED_FILE => {
373 res!(flag_len(v, 5, "CrossedFile"));
374 Ok(Self::CrossedFile {
375 op: res!(OpId::from_dat(&v[1])),
376 sub: res!(flag_u64(&v[2], "CrossedFile", "offset")),
377 from: res!(OpId::from_dat(&v[3])),
378 to: res!(OpId::from_dat(&v[4])),
379 })
380 },
381 CODE_MOVED_INTO_DELETED => {
382 res!(flag_len(v, 3, "MovedIntoDeleted"));
383 Ok(Self::MovedIntoDeleted {
384 op: res!(OpId::from_dat(&v[1])),
385 file: res!(OpId::from_dat(&v[2])),
386 })
387 },
388 CODE_ORPHANED => {
389 res!(flag_len(v, 3, "Orphaned"));
390 Ok(Self::Orphaned {
391 op: res!(OpId::from_dat(&v[1])),
392 sub: res!(flag_u64(&v[2], "Orphaned", "offset")),
393 })
394 },
395 CODE_CONFINED => {
396 res!(flag_len(v, 4, "Confined"));
397 Ok(Self::Confined {
398 op: res!(OpId::from_dat(&v[1])),
399 home: res!(OpId::from_dat(&v[2])),
400 denied: res!(OpId::from_dat(&v[3])),
401 })
402 },
403 CODE_WON => {
404 res!(flag_len(v, 2, "Won"));
405 Ok(Self::Won {
406 op: res!(OpId::from_dat(&v[1])),
407 })
408 },
409 CODE_STRANDED => {
410 res!(flag_len(v, 3, "Stranded"));
411 Ok(Self::Stranded {
412 op: res!(OpId::from_dat(&v[1])),
413 by: res!(OpId::from_dat(&v[2])),
414 })
415 },
416 CODE_SPLICED_INTO_DELETED => {
417 res!(flag_len(v, 4, "SplicedIntoDeleted"));
418 Ok(Self::SplicedIntoDeleted {
419 op: res!(OpId::from_dat(&v[1])),
420 file: res!(OpId::from_dat(&v[2])),
421 del: res!(OpId::from_dat(&v[3])),
422 })
423 },
424 CODE_YIELDED => {
425 res!(flag_len(v, 5, "Yielded"));
426 let listed = match &v[3] {
427 Dat::List(l) => l,
428 other => return Err(err!(
429 "A Flag::Yielded group expects Dat::List, got {:?}.", other;
430 Decode, Input, Mismatch)),
431 };
432 let mut group = Vec::with_capacity(listed.len());
433 for item in listed {
434 group.push(res!(OpId::from_dat(item)));
435 }
436 let through = match &v[4] {
437 Dat::Opt(boxed) => match boxed.as_ref() {
438 Some(d) => Some(res!(OpId::from_dat(d))),
439 None => None,
440 },
441 other => return Err(err!(
442 "A Flag::Yielded host expects Dat::Opt, got {:?}.", other;
443 Decode, Input, Mismatch)),
444 };
445 Ok(Self::Yielded {
446 op: res!(OpId::from_dat(&v[1])),
447 to: res!(OpId::from_dat(&v[2])),
448 group,
449 through,
450 })
451 },
452 other => Err(err!(
453 "Flag code {} is not recognised.", other;
454 Decode, Input, Invalid)),
455 }
456 }
457}
458
459fn flag_len(v: &[Dat], want: usize, what: &str)
460 -> Outcome<()>
461{
462 if v.len() != want {
463 return Err(err!(
464 "A Flag::{} expects {} list elements, got {}.", what, want, v.len();
465 Decode, Input, Mismatch));
466 }
467 Ok(())
468}
469
470fn flag_u64(dat: &Dat, what: &str, field: &str)
471 -> Outcome<u64>
472{
473 match dat {
474 Dat::U64(n) => Ok(*n),
475 other => Err(err!(
476 "A Flag::{} {} expects Dat::U64, got {:?}.", what, field, other;
477 Decode, Input, Mismatch)),
478 }
479}
480
481fn flag_origin(dat: &Dat, what: &str)
482 -> Outcome<Origin>
483{
484 match dat {
485 Dat::U8(c) => Origin::from_code(*c),
486 other => Err(err!(
487 "A Flag::{} origin expects Dat::U8, got {:?}.", what, other;
488 Decode, Input, Mismatch)),
489 }
490}
491
492fn flag_ranges(dat: &Dat, what: &str)
493 -> Outcome<Vec<ContentRange>>
494{
495 match dat {
496 Dat::List(v) => {
497 let mut out = Vec::with_capacity(v.len());
498 for item in v {
499 out.push(res!(ContentRange::from_dat(item)));
500 }
501 Ok(out)
502 },
503 other => Err(err!(
504 "A Flag {} expects Dat::List, got {:?}.", what, other;
505 Decode, Input, Mismatch)),
506 }
507}
508
509
510/// What a render cost, in the terms the cost model is stated in.
511///
512/// The figures are the repository's, since the render is the repository's: one
513/// forest is laid out and walked, and a file is a subtree of it.
514///
515/// `rendered` and `withheld` count bytes this render materialised and `atom_bytes`
516/// does not: since 2026-08-20 an atom's bytes are shared with the record they came
517/// from rather than copied out of it, so that figure says how much content the
518/// history holds and not what holding it costs. See
519/// [`crate::seq::atom::Atoms::total`], which it comes from.
520#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
521pub struct Stats {
522 pub ops: usize, // operations in the set
523 pub files: usize, // created, deleted ones included
524 pub atoms: usize, // one per file, one per inserting splice
525 pub atom_bytes: u64, // alive or dead, origin anchors included
526 pub slots_placed: usize, // one per file, splice and move source run
527 pub slots_divided: usize, // after dividing at anchors
528 pub claim_intervals: usize, // the standing cost of every move made
529 pub dead_intervals: usize, // in the tombstone set
530 pub notes: usize, // resolved and on dead content alike
531 pub max_depth: u32, // deepest path in the Fugue forest
532 pub rendered: u64, // live files and deleted ones alike
533 pub withheld: u64, // rendered into deleted files
534 pub orphaned: u64, // in no file at all; not zero is a fault
535}
536
537
538/// A run of rendered bytes, and the content it shows.
539#[derive(Clone, Copy, Debug, Eq, PartialEq)]
540pub struct Run {
541 pub at: u64, // offset in the render at which it begins
542 pub content: ContentRange,
543}
544
545
546impl Run {
547 /// The wire shape is `[at, content]`.
548 pub fn to_dat(&self) -> Dat {
549 Dat::List(vec![
550 Dat::U64(self.at),
551 self.content.to_dat(),
552 ])
553 }
554
555 pub fn from_dat(dat: &Dat)
556 -> Outcome<Self>
557 {
558 let v = match dat {
559 Dat::List(v) if v.len() == 2 => v,
560 _ => return Err(err!(
561 "A Run expects a 2-element Dat::List, got {:?}.", dat;
562 Decode, Input, Mismatch)),
563 };
564 let at = match &v[0] {
565 Dat::U64(n) => *n,
566 other => return Err(err!(
567 "A Run offset expects Dat::U64, got {:?}.", other;
568 Decode, Input, Mismatch)),
569 };
570 Ok(Self {
571 at,
572 content: res!(ContentRange::from_dat(&v[1])),
573 })
574 }
575}
576
577
578/// A run of rendered bytes, named by where it begins and how far it goes.
579///
580/// This is what a note resolves to, and it is deliberately not a [`Run`]: a run
581/// says which content is being shown, and a span says only which bytes of the
582/// render a margin should be drawn against. A frontend that wants the content
583/// under a span asks [`Rendered::span`] for it.
584#[derive(Clone, Copy, Debug, Default, Eq, Ord, PartialEq, PartialOrd)]
585pub struct Span {
586 pub at: u64, // offset in the render at which it begins
587 pub len: u64,
588}
589
590impl Span {
591 pub const fn new(at: u64, len: u64) -> Self {
592 Self { at, len }
593 }
594
595 /// The offset just past the span.
596 pub const fn end(&self) -> u64 {
597 self.at + self.len
598 }
599
600 /// The wire shape is `[at, len]`.
601 pub fn to_dat(&self) -> Dat {
602 Dat::List(vec![
603 Dat::U64(self.at),
604 Dat::U64(self.len),
605 ])
606 }
607
608 pub fn from_dat(dat: &Dat)
609 -> Outcome<Self>
610 {
611 let v = match dat {
612 Dat::List(v) if v.len() == 2 => v,
613 _ => return Err(err!(
614 "A Span expects a 2-element Dat::List, got {:?}.", dat;
615 Decode, Input, Mismatch)),
616 };
617 let mut n = [0u64; 2];
618 for (i, dat) in v.iter().enumerate() {
619 n[i] = match dat {
620 Dat::U64(x) => *x,
621 other => return Err(err!(
622 "A Span bound expects Dat::U64, got {:?}.", other;
623 Decode, Input, Mismatch)),
624 };
625 }
626 Ok(Self { at: n[0], len: n[1] })
627 }
628}
629
630
631/// A note as one file's render resolved it: what the note says, and where in this
632/// file the content it is about now sits.
633///
634/// The spans are ascending, disjoint and maximal. There may be several, because
635/// the content a note was written against can be torn apart by later edits and by
636/// moves; there is never a span of no bytes, because a note that resolves to
637/// nothing here is not reported here at all.
638#[derive(Clone, Debug, Default, Eq, PartialEq)]
639pub struct Note {
640 note: OpId, // the operation that wrote it
641 text: Vec<u8>, // what it says, as bytes
642 spans: Vec<Span>, // where its content renders here, ascending
643}
644
645impl Note {
646 pub fn new(note: OpId, text: Vec<u8>, spans: Vec<Span>) -> Self {
647 Self { note, text, spans }
648 }
649
650 pub const fn note(&self) -> OpId {
651 self.note
652 }
653
654 pub fn text(&self) -> &[u8] {
655 &self.text
656 }
657
658 /// For messages and tests; the bytes themselves are the record.
659 pub fn text_lossy(&self) -> String {
660 String::from_utf8_lossy(&self.text).into_owned()
661 }
662
663 pub fn spans(&self) -> &[Span] {
664 &self.spans
665 }
666
667 /// The number of bytes the note's content occupies in this file.
668 pub fn len(&self) -> u64 {
669 self.spans.iter().map(|s| s.len).sum()
670 }
671
672 /// A resolved note never covers no bytes of this file.
673 pub fn is_empty(&self) -> bool {
674 self.spans.is_empty()
675 }
676
677 /// The wire shape is `[note, text, [span, ...]]`.
678 ///
679 /// The text is a [`Dat::BU64`] for the reason a file's bytes are: a note may
680 /// be longer than the 255 bytes a [`Dat::BU8`] length field can express, and a
681 /// truncated length there would corrupt silently.
682 pub fn to_dat(&self) -> Dat {
683 Dat::List(vec![
684 self.note.to_dat(),
685 Dat::BU64(self.text.clone()),
686 Dat::List(self.spans.iter().map(|s| s.to_dat()).collect()),
687 ])
688 }
689
690 pub fn from_dat(dat: &Dat)
691 -> Outcome<Self>
692 {
693 let v = match dat {
694 Dat::List(v) if v.len() == 3 => v,
695 _ => return Err(err!(
696 "A Note expects a 3-element Dat::List, got {:?}.", dat;
697 Decode, Input, Mismatch)),
698 };
699 let note = res!(OpId::from_dat(&v[0]));
700 let text = match &v[1] {
701 Dat::BU64(b) => b.clone(),
702 other => return Err(err!(
703 "The text of the note {} expects Dat::BU64, got {:?}.", note, other;
704 Decode, Input, Mismatch)),
705 };
706 let listed = match &v[2] {
707 Dat::List(l) => l,
708 other => return Err(err!(
709 "The spans of the note {} expect Dat::List, got {:?}.", note, other;
710 Decode, Input, Mismatch)),
711 };
712 let mut spans = Vec::with_capacity(listed.len());
713 for item in listed {
714 spans.push(res!(Span::from_dat(item)));
715 }
716 Ok(Self { note, text, spans })
717 }
718}
719
720
721/// Where a stretch of content renders: the file showing it, and the spans of
722/// that file's bytes it occupies.
723///
724/// A note resolves to a list of these, and so does anything else that names
725/// content and wants to say where a reader will find it; see [`Placement`].
726#[derive(Clone, Debug, Default, Eq, PartialEq)]
727pub struct Place {
728 pub file: OpId,
729 pub spans: Vec<Span>, // ascending
730}
731
732
733/// The render read backwards: which file shows a given stretch of content, and
734/// where in it.
735///
736/// A render says, for each file, which content each run of its bytes shows. This
737/// is the other direction -- given content, where is it -- and it is what turns
738/// an operation's name for some bytes into a position a reader can go to. Notes
739/// are resolved through it, and so is a flag whose reader wants a line number
740/// rather than an offset into an operation.
741///
742/// Content that renders nowhere is not found rather than refused: [`Placement::find`]
743/// answers with no place at all for a range that is dead, buried or in a slot that
744/// reached no file, which is the truthful answer to "where is it" and not a fault.
745#[derive(Clone, Debug, Default)]
746pub struct Placement {
747 // For each atom, the offsets of it that render, the file showing them, and the
748 // rendered offset the run begins at. Ascending and disjoint, so a range is
749 // found by binary search.
750 shown: BTreeMap<OpId, Vec<(Range<u64>, OpId, u64)>>,
751}
752
753impl Placement {
754
755 /// Builds the lookup from each file's provenance runs.
756 pub fn of<'a, I>(files: I) -> Self
757 where
758 I: IntoIterator<Item = (OpId, &'a [Run])>,
759 {
760 let mut shown: BTreeMap<OpId, Vec<(Range<u64>, OpId, u64)>> = BTreeMap::new();
761 for (file, runs) in files {
762 for run in runs {
763 if run.content.is_empty() {
764 continue;
765 }
766 shown.entry(run.content.op())
767 .or_default()
768 .push((run.content.offsets(), file, run.at));
769 }
770 }
771 for v in shown.values_mut() {
772 v.sort_by_key(|(iv, file, at)| (iv.start, iv.end, *file, *at));
773 }
774 Self { shown }
775 }
776
777 /// Where the content the ranges name renders, one entry per file, ascending
778 /// by file identity.
779 ///
780 /// Abutting spans are merged, because what a reader wants is the region and
781 /// not the seams a later edit left in it, and a range that renders nowhere
782 /// contributes nothing.
783 pub fn find(&self, ranges: &[ContentRange]) -> Vec<Place> {
784 let mut found: BTreeMap<OpId, Vec<Span>> = BTreeMap::new();
785 for r in ranges {
786 if r.is_empty() {
787 continue;
788 }
789 let line = match self.shown.get(&r.op()) {
790 Some(v) => v,
791 None => continue,
792 };
793 // The first entry that can reach the range, and every one after it that
794 // still starts before the range ends.
795 let mut k = line.partition_point(|(iv, _, _)| iv.end <= r.from());
796 while k < line.len() && line[k].0.start < r.to() {
797 let (iv, file, at) = &line[k];
798 let lo = iv.start.max(r.from());
799 let hi = iv.end.min(r.to());
800 if hi > lo {
801 found.entry(*file).or_default().push(Span {
802 at: at + (lo - iv.start),
803 len: hi - lo,
804 });
805 }
806 k += 1;
807 }
808 }
809 let mut out: Vec<Place> = Vec::with_capacity(found.len());
810 for (file, mut spans) in found {
811 spans.sort();
812 let mut merged: Vec<Span> = Vec::with_capacity(spans.len());
813 for span in spans {
814 match merged.last_mut() {
815 Some(last) if last.end() >= span.at => {
816 let end = last.end().max(span.end());
817 last.len = end - last.at;
818 },
819 _ => merged.push(span),
820 }
821 }
822 out.push(Place { file, spans: merged });
823 }
824 out
825 }
826}
827
828
829/// A note as the repository's render resolved it: what it says, every file its
830/// content reaches, and whether it reaches any.
831///
832/// A note is listed here once however many files its content is scattered over,
833/// which is the difference between this and [`Rendered::notes`]: the file view
834/// answers "what should this margin show", and the repository view answers "where
835/// did this note end up".
836///
837/// There is no codec for this type, and that is deliberate: a repository view is
838/// derived from the file views a render already carries, except for a note on
839/// dead content, which is derived from the operation log. Storing it would be
840/// storing a join.
841#[derive(Clone, Debug, Default, Eq, PartialEq)]
842pub struct RepoNote {
843 note: OpId, // the operation that wrote it
844 text: Vec<u8>, // what it says, as bytes
845 files: Vec<Place>, // ascending by identity
846 on_dead: bool, // nothing it names renders anywhere
847}
848
849impl RepoNote {
850 pub(super) fn new(note: OpId, text: Vec<u8>, files: Vec<Place>) -> Self {
851 let on_dead = files.is_empty();
852 Self { note, text, files, on_dead }
853 }
854
855 pub const fn note(&self) -> OpId {
856 self.note
857 }
858
859 pub fn text(&self) -> &[u8] {
860 &self.text
861 }
862
863 pub fn text_lossy(&self) -> String {
864 String::from_utf8_lossy(&self.text).into_owned()
865 }
866
867 pub fn files(&self) -> &[Place] {
868 &self.files
869 }
870
871 pub fn spans_in(&self, file: OpId) -> &[Span] {
872 self.files
873 .iter()
874 .find(|p| p.file == file)
875 .map(|p| p.spans.as_slice())
876 .unwrap_or(&[])
877 }
878
879 /// Has every byte the note is about been deleted, so that the note renders
880 /// nowhere?
881 ///
882 /// A note in this state is not lost and is not a fault: the log still holds
883 /// what it says and what it was about, and this is what says a reader will not
884 /// find it in any margin. A note on content that moved into a *deleted file*
885 /// is not in this state, because those bytes still render -- into a file no
886 /// reader looks at, which is what [`Flag::MovedIntoDeleted`] is for.
887 pub const fn on_dead(&self) -> bool {
888 self.on_dead
889 }
890}
891
892
893/// One file as a render produced it: which file it is, where it sits, what it
894/// is, whether it still exists, its bytes, what they are made of, and what the
895/// renderer noticed about it.
896///
897/// A file is named by the identity of the [`Op::FileCreate`] that minted it, and
898/// its path is metadata that a rename may change. Two live files may share a
899/// path, that being a state the repository can genuinely be in; which of them a
900/// working copy materialises under the shared name is a policy the caller owns.
901#[derive(Clone, Debug, Default, Eq, PartialEq)]
902pub struct Rendered {
903 file: OpId, // the identity of its creating operation
904 path: Vec<u8>, // where the file sits, as bytes
905 mode: Mode, // after every Op::FileMode the set holds
906 live: bool, // whether the file still exists
907 bytes: Vec<u8>,
908 runs: Vec<Run>, // provenance, in render order and coalesced
909 flags: Vec<Flag>, // what the renderer noticed about this file
910 notes: Vec<Note>, // whose content renders here, in render order
911}
912
913impl Rendered {
914
915
916 #[allow(clippy::too_many_arguments)]
917 pub(super) fn new(
918 file: OpId,
919 path: Vec<u8>,
920 mode: Mode,
921 live: bool,
922 bytes: Vec<u8>,
923 runs: Vec<Run>,
924 flags: Vec<Flag>,
925 notes: Vec<Note>,
926 )
927 -> Self
928 {
929 Self { file, path, mode, live, bytes, runs, flags, notes }
930 }
931
932 pub const fn file(&self) -> OpId {
933 self.file
934 }
935
936 pub fn path(&self) -> &[u8] {
937 &self.path
938 }
939
940 /// For messages and tests; the bytes themselves are the record.
941 pub fn path_lossy(&self) -> String {
942 String::from_utf8_lossy(&self.path).into_owned()
943 }
944
945 /// [`Mode::Normal`] unless an [`Op::FileMode`] said otherwise.
946 pub const fn mode(&self) -> Mode {
947 self.mode
948 }
949
950 pub const fn is_live(&self) -> bool {
951 self.live
952 }
953
954 pub fn bytes(&self) -> &[u8] {
955 &self.bytes
956 }
957
958 /// Runs are maximal: a run continues for as long as the content it shows is
959 /// contiguous, whatever the slot structure underneath.
960 pub fn runs(&self) -> &[Run] {
961 &self.runs
962 }
963
964 pub fn flags(&self) -> &[Flag] {
965 &self.flags
966 }
967
968 /// The notes whose content renders in this file, in the order a margin would
969 /// draw them: by where each note's first span begins, and then by the identity
970 /// of the note.
971 ///
972 /// A note appears here for every file its content reaches, which is more than
973 /// one where a later move split that content across two; the whole of it is
974 /// [`Repo::notes`]. A note whose content has been deleted appears in no file
975 /// at all, and is reported by [`RepoNote::on_dead`].
976 pub fn notes(&self) -> &[Note] {
977 &self.notes
978 }
979
980 pub fn note(&self, note: OpId)
981 -> Option<&Note>
982 {
983 self.notes.iter().find(|n| n.note == note)
984 }
985
986 pub fn len(&self) -> usize {
987 self.bytes.len()
988 }
989
990 pub fn is_empty(&self) -> bool {
991 self.bytes.is_empty()
992 }
993
994 /// For messages and tests; the bytes themselves are the record.
995 pub fn text_lossy(&self) -> String {
996 String::from_utf8_lossy(&self.bytes).into_owned()
997 }
998
999 pub fn content_at(&self, index: usize)
1000 -> Outcome<ContentId>
1001 {
1002 let at = index as u64;
1003 let pos = self.runs.partition_point(|r| r.at <= at);
1004 if pos > 0 {
1005 let run = self.runs[pos - 1];
1006 if at < run.at + run.content.len() {
1007 return Ok(ContentId::new(run.content.op(), run.content.from() + (at - run.at)));
1008 }
1009 }
1010 Err(err!(
1011 "Rendered index {} is beyond the {} bytes rendered.", index, self.bytes.len();
1012 Invalid, Input, Range))
1013 }
1014
1015 /// The content a rendered span is made of, as the fewest runs that name it.
1016 pub fn span(&self, at: usize, len: usize)
1017 -> Outcome<Vec<ContentRange>>
1018 {
1019 let end = match at.checked_add(len) {
1020 Some(e) => e,
1021 None => return Err(err!(
1022 "A span of {} bytes at index {} overflows.", len, at;
1023 Invalid, Input, Overflow)),
1024 };
1025 if end > self.bytes.len() {
1026 return Err(err!(
1027 "A span of {}..{} reaches beyond the {} bytes rendered.",
1028 at, end, self.bytes.len();
1029 Invalid, Input, Range));
1030 }
1031 // Runs are already maximal, so no two of them can be joined and the walk
1032 // is one step per run touched.
1033 let mut out: Vec<ContentRange> = Vec::new();
1034 let mut pos = at as u64;
1035 let end = end as u64;
1036 let mut next = self.runs.partition_point(|r| r.at <= pos);
1037 while pos < end {
1038 if next == 0 {
1039 return Err(err!(
1040 "Rendered index {} lies in no run, though {} bytes were \
1041 rendered.", pos, self.bytes.len();
1042 Bug, Missing));
1043 }
1044 let run = self.runs[next - 1];
1045 let within = pos - run.at;
1046 if within >= run.content.len() {
1047 return Err(err!(
1048 "Rendered index {} falls in the gap after the run at {}; runs \
1049 must cover the render.", pos, run.at;
1050 Bug, Missing));
1051 }
1052 let take = (run.content.len() - within).min(end - pos);
1053 out.push(res!(ContentRange::new(
1054 run.content.op(),
1055 run.content.from() + within,
1056 run.content.from() + within + take,
1057 )));
1058 pos += take;
1059 next += 1;
1060 }
1061 Ok(out)
1062 }
1063
1064 /// The two origins bracketing the gap at a rendered index.
1065 ///
1066 /// The left origin binds after the byte before the gap; at the start of the
1067 /// file there is no such byte in the render, and the origin is the file's
1068 /// **origin anchor**, which is what makes an empty file addressable and is
1069 /// how an operation says which file it lands in. The right origin binds
1070 /// before the byte after the gap, and is absent at the end of the file, there
1071 /// being nothing to name it by.
1072 pub fn gap(&self, at: usize)
1073 -> Outcome<(Option<Anchor>, Option<Anchor>)>
1074 {
1075 if at > self.bytes.len() {
1076 return Err(err!(
1077 "The gap at index {} is beyond the {} bytes rendered.",
1078 at, self.bytes.len();
1079 Invalid, Input, Range));
1080 }
1081 let left = if at > 0 {
1082 Some(Anchor::after(res!(self.content_at(at - 1))))
1083 } else {
1084 Some(Anchor::origin(self.file))
1085 };
1086 let right = if at < self.bytes.len() {
1087 Some(Anchor::before(res!(self.content_at(at))))
1088 } else {
1089 None
1090 };
1091 Ok((left, right))
1092 }
1093
1094 /// Builds a content-anchored splice from index-based editing intent:
1095 /// replace `len` bytes at `at` with `insert`.
1096 ///
1097 /// This is the bridge a frontend crosses. An editor knows where the cursor
1098 /// is; the structure knows only what the bytes are called, and the render is
1099 /// the one place both are known at once.
1100 pub fn splice(&self, at: usize, len: usize, insert: Vec<u8>)
1101 -> Outcome<Op>
1102 {
1103 let remove = res!(self.span(at, len));
1104 // A splice inserting nothing places no slot, so its origins would say
1105 // nothing about where anything goes, nor about which file.
1106 let (left, right) = if insert.is_empty() {
1107 (None, None)
1108 } else {
1109 res!(self.gap(at))
1110 };
1111 Ok(Op::Splice { left, right, remove, insert: insert.into() })
1112 }
1113
1114 /// Builds a content-anchored move from index-based editing intent: take
1115 /// `len` bytes at `at` to the gap at `to`, in this file.
1116 pub fn move_range(&self, at: usize, len: usize, to: usize)
1117 -> Outcome<Op>
1118 {
1119 let src = res!(self.span(at, len));
1120 let (left, right) = res!(self.gap(to));
1121 Ok(Op::Move { src, left, right })
1122 }
1123
1124 /// Builds a content-anchored move that takes `len` bytes at `at` in this file
1125 /// to the gap at `to` in another.
1126 ///
1127 /// Nothing distinguishes this from [`Rendered::move_range`] except which
1128 /// render the destination gap is read from. That is the whole of cross-file
1129 /// move: the source names content, which is repository-wide, and the
1130 /// destination names content in the file it lands in.
1131 pub fn move_into(&self, at: usize, len: usize, dest: &Self, to: usize)
1132 -> Outcome<Op>
1133 {
1134 let src = res!(self.span(at, len));
1135 let (left, right) = res!(dest.gap(to));
1136 Ok(Op::Move { src, left, right })
1137 }
1138
1139 /// Builds a content-anchored note from index-based intent: say `text` about
1140 /// the `len` bytes at `at`.
1141 ///
1142 /// This is the same bridge [`Rendered::splice`] is, for the same reason: the
1143 /// reader points at a region of the screen, and the render is where that region
1144 /// acquires the names that will follow it through every later edit.
1145 ///
1146 /// Fails on a region of no bytes, since a note is about something.
1147 pub fn note_on(&self, at: usize, len: usize, text: Vec<u8>)
1148 -> Outcome<Op>
1149 {
1150 let on = res!(self.span(at, len));
1151 let op = Op::Note { on, text };
1152 res!(op.check_note());
1153 Ok(op)
1154 }
1155}
1156
1157
1158/// The repository as a render produced it: every file, everything the renderer
1159/// noticed, and what it cost.
1160///
1161/// Rendering is repository-wide because ordering is: a file is a subtree of one
1162/// forest, so laying out that forest is what decides which file each slot is in.
1163/// Reading one file is then [`Repo::file`], and the closure-scoped renderer that
1164/// would lay out less than the whole repository is design work owed rather than
1165/// work done.
1166#[derive(Clone, Debug, Default, Eq, PartialEq)]
1167pub struct Repo {
1168 files: Vec<Rendered>, // ascending by identity, deleted included
1169 flags: Vec<Flag>, // sorted and without repetition
1170 notes: Vec<RepoNote>, // ascending by identity
1171 index: BTreeMap<OpId, OpId>, // which file each placer landed in
1172 stats: Stats, // what the render cost
1173}
1174
1175impl Repo {
1176
1177 pub(super) fn new(
1178 files: Vec<Rendered>,
1179 flags: Vec<Flag>,
1180 notes: Vec<RepoNote>,
1181 index: BTreeMap<OpId, OpId>,
1182 stats: Stats,
1183 )
1184 -> Self
1185 {
1186 Self { files, flags, notes, index, stats }
1187 }
1188
1189
1190 pub fn files(&self) -> &[Rendered] {
1191 &self.files
1192 }
1193
1194 pub fn file(&self, file: OpId)
1195 -> Option<&Rendered>
1196 {
1197 self.files
1198 .binary_search_by(|f| f.file.cmp(&file))
1199 .ok()
1200 .and_then(|i| self.files.get(i))
1201 }
1202
1203 /// The live files, ascending by path and then by identity.
1204 pub fn live(&self) -> Vec<&Rendered> {
1205 let mut v: Vec<&Rendered> = self.files.iter().filter(|f| f.live).collect();
1206 v.sort_by(|a, b| a.path.cmp(&b.path).then(a.file.cmp(&b.file)));
1207 v
1208 }
1209
1210 /// The live files at a path, in ascending order of identity.
1211 ///
1212 /// More than one is legal: two branches that independently created a path
1213 /// minted two files, both of which exist and both of which keep their bytes.
1214 pub fn at_path(&self, path: &[u8]) -> Vec<&Rendered> {
1215 let mut v: Vec<&Rendered> = self.files.iter()
1216 .filter(|f| f.live && f.path == path)
1217 .collect();
1218 v.sort_by_key(|f| f.file);
1219 v
1220 }
1221
1222 /// The paths more than one live file is claiming, each with those files in
1223 /// ascending order of identity.
1224 ///
1225 /// Which of them a working copy writes under the shared name is a policy for
1226 /// the caller: the repository's answer is that both files exist.
1227 pub fn clashes(&self) -> Vec<(&[u8], Vec<OpId>)> {
1228 let mut by_path: BTreeMap<&[u8], Vec<OpId>> = BTreeMap::new();
1229 for f in self.files.iter().filter(|f| f.live) {
1230 by_path.entry(&f.path).or_default().push(f.file);
1231 }
1232 by_path.into_iter()
1233 .filter(|(_, ids)| ids.len() > 1)
1234 .map(|(path, mut ids)| {
1235 ids.sort();
1236 (path, ids)
1237 })
1238 .collect()
1239 }
1240
1241 pub fn flags(&self) -> &[Flag] {
1242 &self.flags
1243 }
1244
1245 /// Every note the operation set holds, in ascending order of identity, each
1246 /// listed once however many files its content is scattered over.
1247 ///
1248 /// A note whose content has been deleted entirely is here too, saying so; see
1249 /// [`RepoNote::on_dead`].
1250 pub fn notes(&self) -> &[RepoNote] {
1251 &self.notes
1252 }
1253
1254 pub fn note(&self, note: OpId)
1255 -> Option<&RepoNote>
1256 {
1257 self.notes
1258 .binary_search_by(|n| n.note.cmp(&note))
1259 .ok()
1260 .and_then(|i| self.notes.get(i))
1261 }
1262
1263 pub fn dead_notes(&self) -> Vec<&RepoNote> {
1264 self.notes.iter().filter(|n| n.on_dead).collect()
1265 }
1266
1267 pub fn stats(&self) -> &Stats {
1268 &self.stats
1269 }
1270
1271 /// The number of files, deleted ones included.
1272 pub fn len(&self) -> usize {
1273 self.files.len()
1274 }
1275
1276 pub fn is_empty(&self) -> bool {
1277 self.files.is_empty()
1278 }
1279
1280 /// The file an operation's placement landed in, if it placed anything that
1281 /// reached a file.
1282 ///
1283 /// This is the derived association a wire field would have asserted. It is
1284 /// computed by the render and may be cached beside the log, which is what a
1285 /// lazy fetcher needs in order to select one file's operations without
1286 /// resolving every anchor; a derived index may be rebuilt when it is wrong,
1287 /// and a wire field may not.
1288 pub fn file_of(&self, op: &OpId) -> Option<OpId> {
1289 self.index.get(op).copied()
1290 }
1291
1292 /// Which file each placing operation landed in.
1293 pub fn index(&self) -> &BTreeMap<OpId, OpId> {
1294 &self.index
1295 }
1296
1297 /// The render read backwards, which answers where named content ended up.
1298 ///
1299 /// [`Repo::file_of`] answers the coarser question, which file an operation's
1300 /// placement reached; this answers where in that file, and it answers it for
1301 /// content the asking operation did not write. Building it walks every run
1302 /// once, so a caller with several questions builds it once and asks it
1303 /// repeatedly.
1304 pub fn placement(&self) -> Placement {
1305 Placement::of(self.files.iter().map(|f| (f.file, f.runs.as_slice())))
1306 }
1307}
1308
1309
1310/// Which side of its parent a node sits on.
1311#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1312enum ChildSide {
1313 Left, // visited before the parent
1314 Right, // visited after the parent
1315}
1316
1317
1318/// The bytes a traversal produced, where they went, and what it cost.
1319/// Whether a walk is wanted for the bytes it lays out, or only for where each
1320/// slot ended up.
1321///
1322/// [`Sequence::layout`] asks the second question and used to be answered with
1323/// the first: it materialised every byte of every file into a
1324/// `BTreeMap<OpId, (Vec<u8>, Vec<Run>)>`, kept `owner`, and dropped the rest.
1325/// That is a whole copy of the working tree computed, written and never read,
1326/// and it happened twice on every repository open -- once under `render_with`
1327/// and once under `check_conservation`. Measured 2026-08-20 on a 44,628
1328/// operation history: removing one of the two took peak resident memory from
1329/// 263,136 kB to 243,380 kB.
1330#[derive(Clone, Copy, Debug, Eq, PartialEq)]
1331pub(super) enum Emit {
1332 Bytes, // lay the content out, for a caller that renders
1333 OwnersOnly, // answer which file each slot is in, and allocate nothing for content
1334}
1335
1336pub(super) struct Traversal {
1337 pub files: BTreeMap<OpId, (Vec<u8>, Vec<Run>)>,
1338 pub owner: Vec<Option<OpId>>, // the file each slot ended up in
1339 pub orphans: Vec<(OpId, u64)>, // by placing operation and offset
1340 pub orphaned: u64, // live bytes owned by those slots
1341 pub max_depth: u32, // deepest path in the forest
1342}
1343
1344/// Builds the Fugue forest in topological order and walks it in order, emitting
1345/// each slot's bytes into the file whose subtree it is in.
1346///
1347/// The forest's root children are the seed slots, one per file, so a slot's file
1348/// is whichever seed it descends from. A slot that reaches the root without being
1349/// a seed belongs to no file: its origins were dropped, and it is reported rather
1350/// than quietly discarded, because the bytes it owns have to be accounted for.
1351///
1352/// Where a slot's two origins are still adjacent the published rule applies
1353/// unchanged. Where a move has separated them, the rule is re-run against the
1354/// left origin's current in-order successor, which is Fugue's own Algorithm 1
1355/// with "the next element" read at render time rather than taken from the
1356/// recorded anchor. Without that, an insertion abutting a moved range lands at
1357/// the far end of its left origin's subtree, which for a document of any size is
1358/// the end of the file. One recorded sense of the re-run: where the anchor pair
1359/// is not adjacent, concurrent authors' blocks order by descending op order
1360/// rather than Algorithm 1's ascending, each block whole either way -- a
1361/// departure only from an ordering the paper calls arbitrary.
1362pub(super) fn traverse(
1363 slots: &Slots,
1364 ord: &Order,
1365 claims: &Claims,
1366 dead: &Dead,
1367 atoms: &Atoms,
1368 want: Emit,
1369)
1370 -> Outcome<Traversal>
1371{
1372 let sl = slots.all();
1373 let n = sl.len();
1374 if n >= u32::MAX as usize {
1375 return Err(err!(
1376 "A repository of {} slots exceeds what the forest's indices can address.", n;
1377 Excessive, Size));
1378 }
1379 let root = n;
1380 // Ancestor jumps for the subtree test, in powers of two.
1381 let mut log = 1usize;
1382 while (1usize << log) <= n {
1383 log += 1;
1384 }
1385 let mut parent: Vec<u32> = vec![root as u32; n + 1];
1386 let mut side: Vec<ChildSide> = vec![ChildSide::Right; n + 1];
1387 let mut depth: Vec<u32> = vec![0; n + 1];
1388 let mut up: Vec<u32> = vec![root as u32; (n + 1) * log];
1389 let mut kids_l: Vec<Vec<usize>> = vec![Vec::new(); n + 1];
1390 let mut kids_r: Vec<Vec<usize>> = vec![Vec::new(); n + 1];
1391 let mut owner: Vec<Option<OpId>> = vec![None; n];
1392 let mut orphans: Vec<(OpId, u64)> = Vec::new();
1393 let mut max_depth = 0u32;
1394
1395 for &i in &ord.order {
1396 // A piece that is not the first of its placement hangs off its
1397 // predecessor, so a divided slot stays in one piece in the order.
1398 let (par, sd) = match slots.prev(i) {
1399 Some(prev) => (prev, ChildSide::Right),
1400 None => match (ord.left[i], ord.right[i]) {
1401 (None, None) => (root, ChildSide::Right),
1402 (None, Some(r)) => (r, ChildSide::Left),
1403 (Some(l), None) => (l, ChildSide::Right),
1404 (Some(l), Some(r)) => {
1405 if in_right_subtree(l, r, &depth, &up, &parent, &side, log) {
1406 (r, ChildSide::Left)
1407 } else {
1408 // The origins have been torn apart by a move, so the
1409 // recorded right origin says nothing about where this
1410 // belongs. The left origin's successor does.
1411 match successor(l, &kids_l, &kids_r, &parent, &side, root) {
1412 Some(s) if in_right_subtree(
1413 l, s, &depth, &up, &parent, &side, log)
1414 => (s, ChildSide::Left),
1415 _ => (l, ChildSide::Right),
1416 }
1417 }
1418 },
1419 },
1420 };
1421 if par == i {
1422 return Err(err!(
1423 "The slot placed by {} at offset {} resolved to itself as its own \
1424 parent.", sl[i].place, sl[i].sub;
1425 Bug));
1426 }
1427 parent[i] = par as u32;
1428 side[i] = sd;
1429 depth[i] = depth[par] + 1;
1430 max_depth = max_depth.max(depth[i]);
1431 up[i * log] = par as u32;
1432 for k in 1..log {
1433 up[i * log + k] = up[up[i * log + k - 1] as usize * log + k - 1];
1434 }
1435 // A slot's file is read off the forest: a seed opens one, and everything
1436 // beneath a slot is in the same file it is.
1437 owner[i] = if par == root {
1438 if sl[i].seed {
1439 Some(sl[i].place)
1440 } else {
1441 orphans.push((sl[i].place, sl[i].sub));
1442 None
1443 }
1444 } else {
1445 owner[par]
1446 };
1447 // Same-side siblings sit in op order, then in placement offset, which is
1448 // Fugue's sibling rule and the last of the five tie-breaks.
1449 let key = (OpOrder::of(&sl[i].place), sl[i].sub, i);
1450 let list = match sd {
1451 ChildSide::Left => &mut kids_l[par],
1452 ChildSide::Right => &mut kids_r[par],
1453 };
1454 let pos = list.partition_point(
1455 |j| (OpOrder::of(&sl[*j].place), sl[*j].sub, *j) < key);
1456 list.insert(pos, i);
1457 }
1458
1459 let mut files: BTreeMap<OpId, (Vec<u8>, Vec<Run>)> = BTreeMap::new();
1460 let mut orphaned = 0u64;
1461 let mut stack: Vec<(usize, bool)> = vec![(root, false)];
1462 while let Some((i, emit)) = stack.pop() {
1463 if emit {
1464 if i == root {
1465 continue;
1466 }
1467 let slot = &sl[i];
1468 // A slot shows the parts of its claim it still owns, minus whatever
1469 // has died. A slot that has lost all of its claim shows nothing and
1470 // stays as an anchor target.
1471 let claimed = slot.claim.op();
1472 for (span, holder) in claims.runs(&slot.claim) {
1473 if holder != slot.place {
1474 continue;
1475 }
1476 for live in dead.live_runs(&claimed, span.clone()) {
1477 let run = res!(ContentRange::new(claimed, live.start, live.end));
1478 let file = match owner[i] {
1479 Some(f) => f,
1480 None => {
1481 orphaned += run.len();
1482 continue;
1483 },
1484 };
1485 // `orphaned` above is counted either way: it is a fact about
1486 // ownership, which is what the cheap walk is for.
1487 if want == Emit::OwnersOnly {
1488 continue;
1489 }
1490 let out = files.entry(file).or_default();
1491 let at = out.0.len() as u64;
1492 out.0.extend_from_slice(res!(atoms.slice(&run)));
1493 match out.1.last_mut() {
1494 Some(last) if last.content.op() == run.op()
1495 && last.content.to() == run.from()
1496 => res!(last.content.set_to(run.to())),
1497 _ => out.1.push(Run { at, content: run }),
1498 }
1499 }
1500 }
1501 continue;
1502 }
1503 for c in kids_r[i].iter().rev() {
1504 stack.push((*c, false));
1505 }
1506 stack.push((i, true));
1507 for c in kids_l[i].iter().rev() {
1508 stack.push((*c, false));
1509 }
1510 }
1511
1512 Ok(Traversal { files, owner, orphans, orphaned, max_depth })
1513}
1514
1515/// Resolves every note the operation set holds against the bytes the walk
1516/// produced, giving the notes each file should show and the repository's own view
1517/// of all of them.
1518///
1519/// The work is a reverse lookup over the provenance the walk already returned,
1520/// which is [`Placement`]: each run says which content is showing and where, so a
1521/// note's content is intersected with the runs and each intersection becomes a
1522/// span. Nothing here consults an anchor, a claim or a slot, which is why a note
1523/// follows a move for nothing -- the move has already happened, in the runs.
1524///
1525/// Everything the function reads is a function of the operation set, and every
1526/// list it returns is sorted by a total order over that set, so two replicas
1527/// holding the same operations resolve the same notes whatever order they arrived
1528/// in.
1529pub(super) fn notes(
1530 ops: &[(OpId, &Op)],
1531 files: &BTreeMap<OpId, (Vec<u8>, Vec<Run>)>,
1532)
1533 -> (BTreeMap<OpId, Vec<Note>>, Vec<RepoNote>)
1534{
1535 let placed = Placement::of(
1536 files.iter().map(|(file, (_, runs))| (*file, runs.as_slice())));
1537
1538 let mut per_file: BTreeMap<OpId, Vec<Note>> = BTreeMap::new();
1539 let mut repo: Vec<RepoNote> = Vec::new();
1540 for (id, op) in ops {
1541 let text = match op {
1542 Op::Note { text, .. } => text,
1543 _ => continue,
1544 };
1545 let places = placed.find(op.note_on());
1546 for place in &places {
1547 per_file.entry(place.file)
1548 .or_default()
1549 .push(Note::new(*id, text.clone(), place.spans.clone()));
1550 }
1551 repo.push(RepoNote::new(*id, text.clone(), places));
1552 }
1553
1554 // In each file, the order a margin draws them in; over the repository, the
1555 // order every other list in the render is in.
1556 for v in per_file.values_mut() {
1557 v.sort_by_key(|n| (n.spans.first().map(|s| s.at).unwrap_or(0), n.note));
1558 }
1559 repo.sort_by_key(|n| n.note);
1560 (per_file, repo)
1561}
1562
1563/// The in-order successor of `v` among the nodes placed so far.
1564fn successor(
1565 v: usize,
1566 kids_l: &[Vec<usize>],
1567 kids_r: &[Vec<usize>],
1568 parent: &[u32],
1569 side: &[ChildSide],
1570 root: usize,
1571)
1572 -> Option<usize>
1573{
1574 if let Some(c) = kids_r[v].first() {
1575 let mut cur = *c;
1576 while let Some(x) = kids_l[cur].first() {
1577 cur = *x;
1578 }
1579 return Some(cur);
1580 }
1581 let mut cur = v;
1582 loop {
1583 let p = parent[cur] as usize;
1584 if p == cur || p == root {
1585 return None;
1586 }
1587 if side[cur] == ChildSide::Left {
1588 return Some(p);
1589 }
1590 cur = p;
1591 }
1592}
1593
1594/// Does `r` lie in the right subtree of `l`? Found by climbing `r`'s ancestors
1595/// in powers of two.
1596fn in_right_subtree(
1597 l: usize,
1598 r: usize,
1599 depth: &[u32],
1600 up: &[u32],
1601 parent: &[u32],
1602 side: &[ChildSide],
1603 log: usize,
1604)
1605 -> bool
1606{
1607 if depth[r] <= depth[l] {
1608 return false;
1609 }
1610 // Climb to the child of `l`'s depth, then ask whether that is `l`'s right
1611 // child.
1612 let mut climb = depth[r] - depth[l] - 1;
1613 let mut cur = r;
1614 let mut k = 0usize;
1615 while climb > 0 && k < log {
1616 if climb & 1 == 1 {
1617 cur = up[cur * log + k] as usize;
1618 }
1619 climb >>= 1;
1620 k += 1;
1621 }
1622 parent[cur] as usize == l && side[cur] == ChildSide::Right
1623}