Oregami
Repositories/oxedyne/fe2o3

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

49.9 KiB, 816 runs

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

download · who wrote it · its history

1//! The adversarial cases, each with the answer the literature or the design
2//! prescribes, and each checked under every delivery order.
3//!
4//! A case that merely converges proves little, because the state here is the
5//! operation set and a render is a function of it, so agreement between
6//! delivery orders is nearly free. What the cases test is that the answer
7//! converged on is the right one: the one the published counter-examples say a
8//! correct structure must give.
9//!
10//! Every case here is single-file, and every expectation is what it was before
11//! file identity: the repository now holds a file rather than a bare sequence,
12//! and a splice into that file anchors after its origin anchor rather than after
13//! nothing, and none of the ten answers moves. The multi-file cases are beside
14//! this file in `file_tests.rs`.
15//!
16//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
17//! Anthropic Claude
18
19use crate::id::{
20 Anchor,
21 ContentId,
22 ContentRange,
23 OpId,
24 ReplicaId,
25};
26use crate::op::{
27 Header,
28 Mode,
29 Op,
30 Record,
31};
32use crate::seq::render::{
33 Flag,
34 Rendered,
35 Repo,
36 Run,
37 Span,
38 Stats,
39};
40use crate::seq::slot::Origin;
41use crate::seq::Sequence;
42
43use oxedyne_fe2o3_core::prelude::*;
44
45use std::collections::BTreeMap;
46
47
48// Plain hyphens, so that byte offsets and character offsets coincide.
49const LIST: &[u8] = b"- Eggs\n- Milk\n- Cheese\n";
50
51// Twenty bytes whose order is easy to read off a rendered string.
52const ALPHA: &[u8] = b"0123456789ABCDEFGHIJ";
53
54
55/// One replica of a repository holding one file: the frontend that turns
56/// index-based editing intent into content-anchored operations, which is what a
57/// real editor would be.
58pub(super) struct Replica {
59 pub(super) id: u64, // every operation of this replica is named by it
60 pub(super) seq: Sequence,
61 pub(super) file: OpId, // the file being edited
62}
63
64impl Replica {
65
66 pub(super) fn new(id: u64, file: OpId) -> Self {
67 Self { id, seq: Sequence::new(), file }
68 }
69
70 /// A Lamport counter, and everything this replica can see as the operation's
71 /// parents.
72 fn next_head(&self)
73 -> Outcome<Header>
74 {
75 let seen = self.seq.iter().map(|(id, _)| id.counter).max().unwrap_or(0);
76 Header::new(
77 OpId::new(ReplicaId::new(self.id), seen + 1),
78 self.seq.causality().heads(),
79 )
80 }
81
82 pub(super) fn recv(&mut self, op: (Header, Op))
83 -> Outcome<()>
84 {
85 self.seq.apply(op.0, op.1)
86 }
87
88 pub(super) fn view(&self)
89 -> Outcome<Rendered>
90 {
91 let repo = res!(self.seq.render());
92 match repo.file(self.file) {
93 Some(f) => Ok(f.clone()),
94 None => Err(err!(
95 "The replica has no file {}.", self.file; Test, Missing)),
96 }
97 }
98
99 pub(super) fn author(&mut self, op: Op)
100 -> Outcome<(Header, Op)>
101 {
102 let head = res!(self.next_head());
103 res!(self.seq.apply(head.clone(), op.clone()));
104 Ok((head, op))
105 }
106
107 pub(super) fn insert(&mut self, at: usize, bytes: &[u8])
108 -> Outcome<(Header, Op)>
109 {
110 let op = res!(res!(self.view()).splice(at, 0, bytes.to_vec()));
111 self.author(op)
112 }
113
114 fn delete(&mut self, at: usize, len: usize)
115 -> Outcome<(Header, Op)>
116 {
117 let op = res!(res!(self.view()).splice(at, len, Vec::new()));
118 self.author(op)
119 }
120
121 /// One operation, not a deletion and an insertion.
122 fn replace(&mut self, at: usize, len: usize, bytes: &[u8])
123 -> Outcome<(Header, Op)>
124 {
125 let op = res!(res!(self.view()).splice(at, len, bytes.to_vec()));
126 self.author(op)
127 }
128
129 fn move_range(&mut self, at: usize, len: usize, to: usize)
130 -> Outcome<(Header, Op)>
131 {
132 let op = res!(res!(self.view()).move_range(at, len, to));
133 self.author(op)
134 }
135
136 fn note(&mut self, at: usize, len: usize, text: &[u8])
137 -> Outcome<(Header, Op)>
138 {
139 let op = res!(res!(self.view()).note_on(at, len, text.to_vec()));
140 self.author(op)
141 }
142}
143
144
145/// A repository staged with one file carrying some initial text, and the
146/// replicas that have seen it.
147pub(super) struct Stage {
148 pub(super) reps: Vec<Replica>, // each holding everything staged
149 pub(super) ops: Vec<(Header, Op)>, // the file's creation, then the seeding splice
150 pub(super) file: OpId,
151 pub(super) seed: OpId, // the splice that wrote the initial text
152}
153
154/// Creates one file, writes `text` into it, and hands out `replicas` replicas
155/// that have seen both operations.
156pub(super) fn seed(text: &[u8], replicas: u64)
157 -> Outcome<Stage>
158{
159 let mut origin = Replica::new(0, OpId::default());
160 let create = res!(origin.author(Op::FileCreate { path: b"f".to_vec() }));
161 let file = create.0.id();
162 origin.file = file;
163 let mut ops = vec![create];
164 let seed = res!(origin.insert(0, text));
165 let seed_id = seed.0.id();
166 ops.push(seed);
167 let mut out = Vec::new();
168 for i in 1..=replicas {
169 let mut r = Replica::new(i, file);
170 for op in &ops {
171 res!(r.recv(op.clone()));
172 }
173 out.push(r);
174 }
175 Ok(Stage { reps: out, ops, file, seed: seed_id })
176}
177
178fn permute(idx: &mut Vec<usize>, k: usize, out: &mut Vec<Vec<usize>>) {
179 if k == idx.len() {
180 out.push(idx.clone());
181 return;
182 }
183 for i in k..idx.len() {
184 idx.swap(k, i);
185 permute(idx, k + 1, out);
186 idx.swap(k, i);
187 }
188}
189
190/// Applies an operation set in every delivery order, requiring that all of them
191/// render the same bytes in every file and raise the same flags, and returns
192/// that render.
193pub(super) fn converge(ops: &[(Header, Op)])
194 -> Outcome<Repo>
195{
196 let n = ops.len();
197 let mut orders: Vec<Vec<usize>> = Vec::new();
198 if n <= 6 {
199 let mut idx: Vec<usize> = (0..n).collect();
200 permute(&mut idx, 0, &mut orders);
201 } else {
202 for k in 0..n {
203 orders.push((0..n).map(|i| (i + k) % n).collect());
204 }
205 orders.push((0..n).rev().collect());
206 }
207 let mut first: Option<Repo> = None;
208 for order in &orders {
209 let mut seq = Sequence::new();
210 for i in order {
211 res!(seq.apply(ops[*i].0.clone(), ops[*i].1.clone()));
212 }
213 let got = res!(seq.render());
214 res!(seq.check_conservation(&got));
215 match &first {
216 None => first = Some(got),
217 Some(want) => {
218 if listing(want) != listing(&got) {
219 return Err(err!(
220 "Delivery order changed the render: {} against {}.",
221 listing(want), listing(&got);
222 Test, Mismatch));
223 }
224 if want.flags() != got.flags() {
225 return Err(err!(
226 "Delivery order changed the flags: {:?} against {:?}.",
227 want.flags(), got.flags();
228 Test, Mismatch));
229 }
230 if want.notes() != got.notes() {
231 return Err(err!(
232 "Delivery order changed the notes: {:?} against {:?}.",
233 want.notes(), got.notes();
234 Test, Mismatch));
235 }
236 for (a, b) in want.files().iter().zip(got.files()) {
237 if a.notes() != b.notes() {
238 return Err(err!(
239 "Delivery order changed the notes of the file {}: {:?} \
240 against {:?}.", a.file(), a.notes(), b.notes();
241 Test, Mismatch));
242 }
243 }
244 },
245 }
246 }
247 match first {
248 Some(r) => Ok(r),
249 None => Err(err!("No delivery order was tried."; Test, Bug)),
250 }
251}
252
253/// A one-line rendering of every file, for test messages and comparison.
254fn listing(repo: &Repo) -> String {
255 let mut s = String::new();
256 for f in repo.files() {
257 s.push_str(&fmt!(
258 "{}{}={:?} ",
259 f.path_lossy(),
260 if f.is_live() { "" } else { " (deleted)" },
261 f.text_lossy(),
262 ));
263 }
264 s.trim_end().to_string()
265}
266
267/// Runs an operation set under every delivery order and checks one file's render
268/// against the answer the case prescribes.
269pub(super) fn case(file: OpId, expect: &str, ops: &[(Header, Op)])
270 -> Outcome<Rendered>
271{
272 let repo = res!(converge(ops));
273 let got = match repo.file(file) {
274 Some(f) => f.clone(),
275 None => return Err(err!(
276 "The render holds no file {}.", file; Test, Missing)),
277 };
278 assert_eq!(got.text_lossy(), expect);
279 Ok(got)
280}
281
282fn count(repo: &Rendered, kind: fn(&Flag) -> bool) -> usize {
283 repo.flags().iter().filter(|f| kind(f)).count()
284}
285
286fn is_torn(flag: &Flag) -> bool {
287 matches!(flag, Flag::Torn { .. })
288}
289
290fn is_demoted(flag: &Flag) -> bool {
291 matches!(flag, Flag::Demoted { .. })
292}
293
294fn is_dropped(flag: &Flag) -> bool {
295 matches!(flag, Flag::Dropped { .. })
296}
297
298/// Whether a flag reports two operations naming the same content.
299fn is_overlap(flag: &Flag) -> bool {
300 matches!(flag, Flag::Overlap { .. })
301}
302
303
304// ┌───────────────────────────────────────────────────────────────────────────┐
305// │ THE TEN ADVERSARIAL CASES │
306// └───────────────────────────────────────────────────────────────────────────┘
307
308/// The case the structure exists for. One replica moves a list item to the top
309/// while another rewrites a word inside it; the published construction loses the
310/// rewrite, because the insertion is anchored to a position the move did not
311/// touch. Here the anchor names content, the move claimed that content, and the
312/// insertion goes where the content went.
313#[test]
314fn an_edit_inside_a_moved_line_travels_with_it() -> Outcome<()> {
315 let mut st = res!(seed(LIST, 2));
316 let (b, a) = st.reps.split_at_mut(1);
317 // Replica 1 moves "- Milk\n" to the top.
318 st.ops.push(res!(b[0].move_range(7, 7, 0)));
319 // Replica 2 concurrently turns "Milk" into "Soy milk".
320 st.ops.push(res!(a[0].replace(9, 1, b"Soy m")));
321 let out = res!(case(st.file, "- Soy milk\n- Eggs\n- Cheese\n", &st.ops));
322 assert_eq!(count(&out, is_torn), 0);
323 assert_eq!(count(&out, is_demoted), 0);
324 Ok(())
325}
326
327/// Two replicas move the identical run to different destinations. One copy
328/// survives, at the destination of the move that is higher in op order, and the
329/// loser is told its source is no longer its own. Duplication here is the
330/// anomaly the published single-element construction exists to remove.
331#[test]
332fn two_moves_of_one_run_leave_one_copy() -> Outcome<()> {
333 let mut st = res!(seed(LIST, 2));
334 let seed_id = st.seed;
335 let (r1, r2) = st.reps.split_at_mut(1);
336 let lost = res!(r1[0].move_range(7, 7, 0)); // replica 1 loses
337 let won = res!(r2[0].move_range(7, 7, 23)); // replica 2 wins
338 st.ops.push(lost.clone());
339 st.ops.push(won);
340 let out = res!(case(st.file, "- Eggs\n- Cheese\n- Milk\n", &st.ops));
341 assert_eq!(count(&out, is_torn), 1);
342 assert!(out.flags().contains(&Flag::Torn {
343 op: lost.0.id(),
344 lost: vec![res!(ContentRange::new(seed_id, 7, 14))],
345 }), "flags were {:?}", out.flags());
346 assert_eq!(count(&out, is_overlap), 1,
347 "the two moves named the same seven bytes");
348 Ok(())
349}
350
351/// Two replicas move partly overlapping runs. The block tears at the overlap:
352/// twenty bytes in, twenty bytes out, nothing duplicated, nothing lost, and
353/// neither author's block in one piece. That is the prescribed outcome, and the
354/// flag on the losing move is what makes it acceptable rather than merely
355/// tolerable.
356#[test]
357fn overlapping_moves_tear_at_the_overlap() -> Outcome<()> {
358 let mut st = res!(seed(ALPHA, 2));
359 let seed_id = st.seed;
360 let (r1, r2) = st.reps.split_at_mut(1);
361 let torn = res!(r1[0].move_range(0, 10, 20)); // replica 1 loses the overlap
362 let won = res!(r2[0].move_range(5, 10, 0)); // replica 2 wins it
363 st.ops.push(torn.clone());
364 st.ops.push(won);
365 let out = res!(case(st.file, "FGHIJ56789ABCDE01234", &st.ops));
366 assert_eq!(count(&out, is_torn), 1);
367 assert!(out.flags().contains(&Flag::Torn {
368 op: torn.0.id(),
369 lost: vec![res!(ContentRange::new(seed_id, 5, 10))],
370 }), "flags were {:?}", out.flags());
371 Ok(())
372}
373
374/// Two moves whose destinations sit inside each other's sources: a cycle in the
375/// anchor graph that neither replica could have known it was making. Two origins
376/// are demoted to the splice that created their content, all twenty bytes
377/// survive, and the lower move lands where its anchor content was written rather
378/// than where it now lives.
379#[test]
380fn mutually_nested_destinations_break_the_cycle_without_loss() -> Outcome<()> {
381 let mut st = res!(seed(ALPHA, 2));
382 let (r1, r2) = st.reps.split_at_mut(1);
383 // Replica 1 moves "01234" into the middle of "ABCDE".
384 let m1 = res!(r1[0].move_range(0, 5, 12));
385 // Replica 2 moves "ABCDE" into the middle of "01234".
386 let m2 = res!(r2[0].move_range(10, 5, 2));
387 st.ops.push(m1.clone());
388 st.ops.push(m2);
389 let out = res!(case(st.file, "5678901ABCDE234FGHIJ", &st.ops));
390 assert_eq!(out.len(), 20, "no byte may be lost to a cycle");
391 assert_eq!(count(&out, is_dropped), 0, "demotion sufficed");
392 // Both origins of the lower move in op order give way, and the higher move
393 // keeps the destination it asked for. The cycle is inside one file, so
394 // nothing crossed a boundary and no cross-file flag is raised.
395 assert_eq!(out.flags(), &[
396 Flag::Demoted { op: m1.0.id(), sub: 0, origin: Origin::Left },
397 Flag::Demoted { op: m1.0.id(), sub: 0, origin: Origin::Right },
398 ]);
399 Ok(())
400}
401
402#[test]
403fn an_insertion_inside_a_moved_run_goes_with_it() -> Outcome<()> {
404 let mut st = res!(seed(LIST, 2));
405 let (r1, r2) = st.reps.split_at_mut(1);
406 st.ops.push(res!(r1[0].move_range(7, 7, 0)));
407 st.ops.push(res!(r2[0].insert(11, b"!")));
408 res!(case(st.file, "- Mi!lk\n- Eggs\n- Cheese\n", &st.ops));
409 Ok(())
410}
411
412/// The runs stay whole and follow op order; interleaving them is the failure most
413/// published algorithms exhibit.
414#[test]
415fn three_concurrent_runs_at_one_point_do_not_interleave() -> Outcome<()> {
416 let mut st = res!(seed(b"AB", 3));
417 for (i, r) in st.reps.iter_mut().enumerate() {
418 let run = match i {
419 0 => b"xxx".to_vec(),
420 1 => b"yyy".to_vec(),
421 _ => b"zzz".to_vec(),
422 };
423 st.ops.push(res!(r.insert(1, &run)));
424 }
425 res!(case(st.file, "AxxxyyyzzzB", &st.ops));
426 Ok(())
427}
428
429/// Insertions abutting a moved run, one immediately before its start and one
430/// immediately after its end. The asymmetry is inherent and worth stating: an
431/// insertion abutting the start stays where it was, one abutting the end travels
432/// with the move. Under the published ordering rule read literally, the first of
433/// them lands at the end of the file instead, which is the failure the successor
434/// rule exists to prevent.
435#[test]
436fn edits_abutting_a_moved_run_stay_beside_their_neighbour() -> Outcome<()> {
437 let mut st = res!(seed(LIST, 2));
438 let (r1, r2) = st.reps.split_at_mut(1);
439 st.ops.push(res!(r1[0].move_range(7, 7, 0)));
440 st.ops.push(res!(r2[0].insert(7, b"<")));
441 st.ops.push(res!(r2[0].insert(15, b">")));
442 res!(case(st.file, "- Milk\n>- Eggs\n<- Cheese\n", &st.ops));
443 Ok(())
444}
445
446/// A move and a deletion inside the moved run need no tie-break between them.
447/// The bytes move, and they are dead, and a dead byte renders as nothing
448/// wherever it is.
449#[test]
450fn a_move_and_a_deletion_inside_it_compose() -> Outcome<()> {
451 let mut st = res!(seed(LIST, 2));
452 let (r1, r2) = st.reps.split_at_mut(1);
453 st.ops.push(res!(r1[0].move_range(7, 7, 0)));
454 st.ops.push(res!(r2[0].delete(9, 4))); // "Milk"
455 res!(case(st.file, "- \n- Eggs\n- Cheese\n", &st.ops));
456 Ok(())
457}
458
459/// Two replicas that disagree about where the block they are moving begins and
460/// ends. The claim register gives each byte to the higher mover, so the lower
461/// move keeps only what the higher one did not want, and its fragments render
462/// apart from each other. Deterministic, flagged, and not what its author meant.
463#[test]
464fn moves_with_different_boundaries_split_between_them() -> Outcome<()> {
465 let mut st = res!(seed(ALPHA, 2));
466 let seed_id = st.seed;
467 let (r1, r2) = st.reps.split_at_mut(1);
468 // Replica 1 treats "0123456789" as the block.
469 let m1 = res!(r1[0].move_range(0, 10, 20));
470 // Replica 2 treats "012345" as the block.
471 let m2 = res!(r2[0].move_range(0, 6, 20));
472 st.ops.push(m1.clone());
473 st.ops.push(m2);
474 let out = res!(case(st.file, "ABCDEFGHIJ6789012345", &st.ops));
475 assert_eq!(count(&out, is_torn), 1);
476 assert!(out.flags().contains(&Flag::Torn {
477 op: m1.0.id(),
478 lost: vec![res!(ContentRange::new(seed_id, 0, 6))],
479 }), "flags were {:?}", out.flags());
480 Ok(())
481}
482
483/// Two authors each write a section and then go back to put a heading above it.
484/// Every surveyed algorithm but one interleaves the four runs here; this
485/// structure keeps each heading with its own section, at run granularity rather
486/// than the per-element granularity the published proof is stated over.
487#[test]
488fn a_heading_added_after_the_fact_stays_with_its_section() -> Outcome<()> {
489 let mut st = res!(seed(b"\n", 2));
490 let (r1, r2) = st.reps.split_at_mut(1);
491 st.ops.push(res!(r1[0].insert(1, b"section A\n")));
492 st.ops.push(res!(r1[0].insert(1, b"HEADING A\n")));
493 st.ops.push(res!(r2[0].insert(1, b"section B\n")));
494 st.ops.push(res!(r2[0].insert(1, b"HEADING B\n")));
495 res!(case(
496 st.file,
497 "\nHEADING A\nsection A\nHEADING B\nsection B\n",
498 &st.ops,
499 ));
500 Ok(())
501}
502
503
504// ┌───────────────────────────────────────────────────────────────────────────┐
505// │ THE TORN FLAG AND CAUSALITY │
506// └───────────────────────────────────────────────────────────────────────────┘
507
508/// A move superseded by a later move of the same content, by the same author,
509/// is a sequence of two decisions and not a race, and raises nothing.
510///
511/// The claim register cannot tell the two apart on its own: in both cases it
512/// names somebody other than the earlier move. The parents can, and the flag
513/// consults them. Before it did, every deliberate re-move reported a tear, which
514/// is a flag nobody can act on sitting on top of the ones they can.
515#[test]
516fn a_move_superseded_on_purpose_does_not_tear() -> Outcome<()> {
517 let mut st = res!(seed(LIST, 1));
518 let first = res!(st.reps[0].move_range(7, 7, 0));
519 // The same author, having seen the first move, moves the same line again.
520 let second = res!(st.reps[0].move_range(0, 7, 23));
521 assert!(second.0.parents().contains(&first.0.id()),
522 "the second move was written knowing the first");
523 st.ops.push(first.clone());
524 st.ops.push(second);
525 let out = res!(case(st.file, "- Eggs\n- Cheese\n- Milk\n", &st.ops));
526 assert_eq!(count(&out, is_torn), 0, "flags were {:?}", out.flags());
527 assert_eq!(count(&out, is_overlap), 0,
528 "nor were the two moves in conflict, one having seen the other");
529 Ok(())
530}
531
532/// The fix narrows the flag rather than removing it.
533#[test]
534fn genuinely_concurrent_moves_still_tear() -> Outcome<()> {
535 let mut st = res!(seed(LIST, 2));
536 let (r1, r2) = st.reps.split_at_mut(1);
537 let lower = res!(r1[0].move_range(7, 7, 0));
538 let higher = res!(r2[0].move_range(7, 7, 23));
539 assert!(!lower.0.parents().contains(&higher.0.id()));
540 assert!(!higher.0.parents().contains(&lower.0.id()));
541 st.ops.push(lower.clone());
542 st.ops.push(higher);
543 let out = res!(case(st.file, "- Eggs\n- Cheese\n- Milk\n", &st.ops));
544 assert_eq!(count(&out, is_torn), 1, "flags were {:?}", out.flags());
545 match out.flags().iter().find(|f| is_torn(f)) {
546 Some(Flag::Torn { op, .. }) => assert_eq!(*op, lower.0.id()),
547 _ => return Err(err!("The torn flag went missing."; Test, Missing)),
548 }
549 Ok(())
550}
551
552
553// ┌───────────────────────────────────────────────────────────────────────────┐
554// │ PROPERTIES │
555// └───────────────────────────────────────────────────────────────────────────┘
556
557#[test]
558fn every_delivery_order_of_a_mixed_set_agrees() -> Outcome<()> {
559 let mut st = res!(seed(b"alpha beta gamma", 3));
560 let (r1, rest) = st.reps.split_at_mut(1);
561 let (r2, r3) = rest.split_at_mut(1);
562 st.ops.push(res!(r1[0].move_range(0, 6, 16))); // "alpha " to the end
563 st.ops.push(res!(r2[0].insert(11, b"very "))); // before "gamma"
564 st.ops.push(res!(r3[0].delete(6, 4))); // "beta"
565 let out = res!(converge(&st.ops));
566 assert_eq!(out.stats().ops, 5);
567 let file = match out.file(st.file) {
568 Some(f) => f,
569 None => return Err(err!("The file went missing."; Test, Missing)),
570 };
571 assert_eq!(file.len(), 16 + 5 - 4 - 6 + 6);
572 Ok(())
573}
574
575/// Convergence is nearly free here, since the state is the operation set; what
576/// this earns is the breadth. It walks the renderer over operation sets nobody
577/// wrote by hand, including the ones that tear, cycle and anchor into
578/// themselves.
579#[test]
580fn random_operation_sets_render_alike_and_conserve() -> Outcome<()> {
581 // A small linear congruential generator, so a failure can be reproduced.
582 let mut seed_state = 0x2545_F491_4F6C_DD1Du64;
583 let mut next = move || {
584 seed_state = seed_state
585 .wrapping_mul(6_364_136_223_846_793_005)
586 .wrapping_add(1_442_695_040_888_963_407);
587 (seed_state >> 33) as usize
588 };
589 for trial in 0..60 {
590 let mut st = res!(seed(b"0123456789abcdefghij", 3));
591 let staged = st.ops.len();
592 // How much of the operation list each replica has received. Operations
593 // are delivered as a prefix, because an operation is anchored in what
594 // its author could see, so a prefix is always causally complete.
595 let mut upto = vec![staged; st.reps.len()];
596 for _ in 0..16 {
597 let who = next() % st.reps.len();
598 let target = upto[who] + next() % (st.ops.len() - upto[who] + 1);
599 while upto[who] < target {
600 let op = st.ops[upto[who]].clone();
601 res!(st.reps[who].recv(op));
602 upto[who] += 1;
603 }
604 let view = res!(st.reps[who].view());
605 let n = view.len();
606 if n == 0 {
607 continue;
608 }
609 let at = next() % (n + 1);
610 let op = match next() % 3 {
611 0 => res!(view.splice(at, 0, b"[]".to_vec())),
612 1 => {
613 let len = (1 + next() % 4).min(n - at);
614 if len == 0 {
615 continue;
616 }
617 res!(view.splice(at, len, Vec::new()))
618 },
619 _ => {
620 let len = (1 + next() % 5).min(n - at);
621 if len == 0 {
622 continue;
623 }
624 res!(view.move_range(at, len, next() % (n + 1)))
625 },
626 };
627 let made = res!(st.reps[who].author(op));
628 st.ops.push(made);
629 }
630 // Every replica ends up holding everything, in a different order each
631 // time, and must agree.
632 let mut want: Option<Repo> = None;
633 for round in 0..4 {
634 let mut seq = Sequence::new();
635 let mut order: Vec<usize> = (0..st.ops.len()).collect();
636 for i in (1..order.len()).rev() {
637 order.swap(i, next() % (i + 1));
638 }
639 for i in order {
640 res!(seq.apply(st.ops[i].0.clone(), st.ops[i].1.clone()));
641 }
642 let got = res!(seq.render());
643 res!(seq.check_conservation(&got));
644 match &want {
645 None => want = Some(got),
646 Some(first) => {
647 assert_eq!(listing(first), listing(&got),
648 "trial {} round {} disagreed on the bytes", trial, round);
649 assert_eq!(first.flags(), got.flags(),
650 "trial {} round {} disagreed on the flags", trial, round);
651 },
652 }
653 }
654 }
655 Ok(())
656}
657
658/// Every byte created is either rendered exactly once or dead, where that is
659/// hardest to hold: a torn move, a cycle and a deletion in one operation set.
660#[test]
661fn conservation_holds_through_a_tear_and_a_cycle() -> Outcome<()> {
662 let mut st = res!(seed(ALPHA, 3));
663 let (r1, rest) = st.reps.split_at_mut(1);
664 let (r2, r3) = rest.split_at_mut(1);
665 st.ops.push(res!(r1[0].move_range(0, 10, 20)));
666 st.ops.push(res!(r2[0].move_range(5, 10, 0)));
667 st.ops.push(res!(r3[0].move_range(10, 5, 2)));
668 st.ops.push(res!(r3[0].delete(18, 2)));
669 let mut seq = Sequence::new();
670 for op in &st.ops {
671 res!(seq.apply(op.0.clone(), op.1.clone()));
672 }
673 let out = res!(seq.render());
674 res!(seq.check_conservation(&out));
675 // Two bytes died, and one more is the file's origin anchor, which is born
676 // dead and never rendered.
677 assert_eq!(
678 out.stats().rendered + 2 + 1,
679 out.stats().atom_bytes,
680 "every byte is rendered once or dead",
681 );
682 Ok(())
683}
684
685/// A conservation failure is reported rather than rendered. The check is fed a
686/// render short of a byte, which is what a slot detached from the forest would
687/// produce, and it says so.
688#[test]
689fn conservation_notices_a_missing_byte() -> Outcome<()> {
690 let st = res!(seed(b"abcdef", 0));
691 let seed_id = st.seed;
692 let mut seq = Sequence::new();
693 for op in &st.ops {
694 res!(seq.apply(op.0.clone(), op.1.clone()));
695 }
696 let out = res!(seq.render());
697 let file = match out.file(st.file) {
698 Some(f) => f,
699 None => return Err(err!("The file went missing."; Test, Missing)),
700 };
701 let short = Repo::new(
702 vec![Rendered::new(
703 st.file,
704 b"f".to_vec(),
705 Mode::Normal,
706 true,
707 file.bytes()[..5].to_vec(),
708 vec![Run {
709 at: 0,
710 content: res!(ContentRange::new(seed_id, 0, 5)),
711 }],
712 Vec::new(),
713 Vec::new(),
714 )],
715 Vec::new(),
716 Vec::new(),
717 BTreeMap::new(),
718 Stats::default(),
719 );
720 assert!(seq.check_conservation(&short).is_err(),
721 "five of six bytes accounted for is not conservation");
722 Ok(())
723}
724
725/// The refusal says which operation named what rather than guessing.
726#[test]
727fn a_causally_incomplete_set_is_refused() -> Outcome<()> {
728 let mut st = res!(seed(LIST, 1));
729 let ins = res!(st.reps[0].insert(9, b"!"));
730 let mv = res!(st.reps[0].move_range(7, 7, 0));
731 // The insertion names the seeding splice as its parent, and its anchor names
732 // the content that splice created.
733 assert_eq!(ins.0.parents(), &[st.seed]);
734 let mut without_seed = Sequence::new();
735 res!(without_seed.apply(ins.0.clone(), ins.1.clone()));
736 assert!(without_seed.render().is_err(),
737 "an operation without its parent cannot be resolved");
738 // The move's source names the same absent content.
739 let mut moved = Sequence::new();
740 res!(moved.apply(mv.0, mv.1));
741 assert!(moved.render().is_err(),
742 "a move naming an absent atom cannot be resolved");
743 // With the whole staging present, both render.
744 let mut whole = Sequence::new();
745 for op in &st.ops {
746 res!(whole.apply(op.0.clone(), op.1.clone()));
747 }
748 res!(whole.apply(ins.0, ins.1));
749 assert!(whole.render().is_ok());
750 Ok(())
751}
752
753/// A file's origin anchor is content the set has to hold like any other.
754#[test]
755fn an_operation_anchored_in_an_absent_file_is_refused() -> Outcome<()> {
756 let ghost = OpId::new(ReplicaId::new(9), 1);
757 let mut seq = Sequence::new();
758 res!(seq.apply(Header::root(OpId::new(ReplicaId::new(1), 1)), Op::Splice {
759 left: Some(Anchor::origin(ghost)),
760 right: None,
761 remove: Vec::new(),
762 insert: b"orphan".to_vec().into(),
763 }));
764 assert!(seq.render().is_err(),
765 "the origin anchor names a file no operation created");
766 // So is a rename or a deletion of a file nobody created.
767 for op in [
768 Op::FileRename { file: ghost, path: b"g".to_vec() },
769 Op::FileDelete { file: ghost },
770 ] {
771 let mut seq = Sequence::new();
772 res!(seq.apply(Header::root(OpId::new(ReplicaId::new(1), 1)), op));
773 assert!(seq.render().is_err());
774 }
775 Ok(())
776}
777
778/// The causal precondition is read off the parents, so it is refused even where
779/// every byte it names is present.
780#[test]
781fn an_operation_ahead_of_its_parent_is_refused() -> Outcome<()> {
782 let mut st = res!(seed(LIST, 1));
783 // Two operations from one replica: the second was written knowing the first.
784 let one = res!(st.reps[0].insert(0, b"# "));
785 let two = res!(st.reps[0].insert(0, b"! "));
786 assert_eq!(two.0.parents(), &[one.0.id()]);
787 let mut without_middle = Sequence::new();
788 for op in &st.ops {
789 res!(without_middle.apply(op.0.clone(), op.1.clone()));
790 }
791 res!(without_middle.apply(two.0.clone(), two.1.clone()));
792 assert!(without_middle.render().is_err(),
793 "the operation names a parent the set does not hold");
794 // The same set with the middle operation restored renders.
795 let mut whole = Sequence::new();
796 for op in st.ops.iter().cloned().chain([one, two]) {
797 res!(whole.apply(op.0, op.1));
798 }
799 assert!(whole.render().is_ok());
800 Ok(())
801}
802
803/// For the same reason as the last: the set does not hold the byte.
804#[test]
805fn an_anchor_past_the_end_of_its_atom_is_refused() -> Outcome<()> {
806 let st = res!(seed(b"abc", 0));
807 let mut seq = Sequence::new();
808 for op in &st.ops {
809 res!(seq.apply(op.0.clone(), op.1.clone()));
810 }
811 let stray = Op::Splice {
812 left: Some(Anchor::after(ContentId::new(st.seed, 99))),
813 right: None,
814 remove: Vec::new(),
815 insert: b"x".to_vec().into(),
816 };
817 let head = res!(Header::new(OpId::new(ReplicaId::new(1), 3), vec![st.seed]));
818 res!(seq.apply(head, stray));
819 assert!(seq.render().is_err());
820 Ok(())
821}
822
823/// Every operation the sequence consumes, written down as a record and put
824/// through the wire codec, comes back as the same operation and renders the same
825/// repository.
826#[test]
827fn the_wire_vocabulary_renders_the_same_repository() -> Outcome<()> {
828 let mut st = res!(seed(LIST, 1));
829 st.ops.push(res!(st.reps[0].move_range(7, 7, 0)));
830 st.ops.push(res!(st.reps[0].replace(2, 4, b"Soy")));
831 let mut replayed = Sequence::new();
832 for (head, op) in &st.ops {
833 let rec = Record::new(head.clone(), op.clone());
834 let back = res!(Record::decode_all(&res!(rec.encode())));
835 assert_eq!(rec, back);
836 assert_eq!(res!(Record::from_dat(&rec.to_dat())), rec);
837 res!(replayed.apply_record(&back));
838 }
839 let repo = res!(replayed.render());
840 match repo.file(st.file) {
841 Some(f) => assert_eq!(f.text_lossy(), "- Soy\n- Eggs\n- Cheese\n"),
842 None => return Err(err!("The file went missing."; Test, Missing)),
843 }
844 Ok(())
845}
846
847/// What a frontend authors names content and never a file, and the file it lands
848/// in is what the render works out.
849#[test]
850fn an_authored_operation_names_no_file() -> Outcome<()> {
851 let mut st = res!(seed(LIST, 1));
852 let (_, mv) = res!(st.reps[0].move_range(7, 7, 0));
853 let (_, sp) = res!(st.reps[0].replace(2, 4, b"Soy"));
854 for op in [&mv, &sp] {
855 assert_eq!(op.names_file(), None);
856 res!(op.check_placement());
857 }
858 // A splice at the start of a file is anchored after that file's origin
859 // anchor, which is how it says where it lands without saying which file.
860 let (_, ins) = res!(st.reps[0].insert(0, b"x"));
861 assert_eq!(ins.origins().0, Some(Anchor::origin(st.file)));
862 assert_eq!(ins.names_file(), None);
863 Ok(())
864}
865
866/// Every operation the log holds belongs to the repository, including the
867/// lifecycle changes, and a mark says nothing about any byte.
868#[test]
869fn every_operation_crosses_into_the_repository() -> Outcome<()> {
870 let mut seq = Sequence::new();
871 let file = OpId::new(ReplicaId::new(1), 1);
872 let ops = vec![
873 (Header::root(file), Op::FileCreate { path: b"f".to_vec() }),
874 (
875 res!(Header::new(OpId::new(ReplicaId::new(1), 2), vec![file])),
876 Op::Mark { name: fmt!("v1"), body: None, time: None },
877 ),
878 (
879 res!(Header::new(OpId::new(ReplicaId::new(1), 3), vec![
880 OpId::new(ReplicaId::new(1), 2),
881 ])),
882 Op::FileRename { file, path: b"g".to_vec() },
883 ),
884 (
885 res!(Header::new(OpId::new(ReplicaId::new(1), 4), vec![
886 OpId::new(ReplicaId::new(1), 3),
887 ])),
888 Op::FileDelete { file },
889 ),
890 ];
891 for (head, op) in &ops {
892 res!(seq.apply_record(&Record::new(head.clone(), op.clone())));
893 }
894 assert_eq!(seq.len(), 4, "a mark is kept, so the causal graph has no holes");
895 let repo = res!(seq.render());
896 match repo.file(file) {
897 Some(f) => {
898 assert_eq!(f.path(), b"g", "the rename moved it");
899 assert!(!f.is_live(), "the deletion retired it");
900 assert!(f.is_empty());
901 },
902 None => return Err(err!("The file went missing."; Test, Missing)),
903 }
904 assert!(repo.live().is_empty());
905 Ok(())
906}
907
908/// Two branches meet by absorbing one another's operations, and what the union
909/// renders is what each branch renders once it has heard the other.
910#[test]
911fn two_divergent_branches_absorb_into_one_repository() -> Outcome<()> {
912 let mut st = res!(seed(LIST, 2));
913 // Each branch edits without having seen the other.
914 let left = res!(st.reps[0].insert(0, b"- Bread\n"));
915 let right = res!(st.reps[1].delete(7, 7));
916 // A third party takes the union, and the staging is not taken twice.
917 let mut both = Sequence::new();
918 assert_eq!(res!(both.absorb(&st.reps[0].seq)), 3,
919 "the file, the seeding splice and the branch's own edit");
920 assert_eq!(res!(both.absorb(&st.reps[1].seq)), 1, "the staging is already held");
921 assert_eq!(both.len(), 4);
922 // Which is what each branch renders once it has received the other's edit.
923 res!(st.reps[0].recv(right));
924 res!(st.reps[1].recv(left));
925 let merged = res!(both.render());
926 let want = match merged.file(st.file) {
927 Some(f) => f.text_lossy(),
928 None => return Err(err!("The file went missing."; Test, Missing)),
929 };
930 assert_eq!(want, res!(st.reps[0].view()).text_lossy());
931 assert_eq!(want, res!(st.reps[1].view()).text_lossy());
932 assert_eq!(want, "- Bread\n- Eggs\n- Cheese\n");
933 // Absorbing what is already held says so, and changes nothing.
934 let before = both.clone();
935 assert_eq!(res!(both.absorb(&st.reps[0].seq)), 0);
936 assert_eq!(res!(both.absorb(&st.reps[1].seq)), 0);
937 assert_eq!(both, before);
938 Ok(())
939}
940
941/// Absorption is the union of two sets, so it does not matter which way round it
942/// is taken, nor in how many steps.
943#[test]
944fn absorbing_either_way_round_gives_one_repository() -> Outcome<()> {
945 let mut st = res!(seed(ALPHA, 2));
946 res!(st.reps[0].insert(4, b"xy"));
947 res!(st.reps[1].move_range(0, 3, 10));
948 let mut left = st.reps[0].seq.clone();
949 res!(left.absorb(&st.reps[1].seq));
950 let mut right = st.reps[1].seq.clone();
951 res!(right.absorb(&st.reps[0].seq));
952 assert_eq!(left, right, "the union is the union");
953 assert_eq!(listing(&res!(left.render())), listing(&res!(right.render())));
954 Ok(())
955}
956
957/// One identity naming two different operations is not two branches of one
958/// history, and the merge is refused whole rather than half taken.
959#[test]
960fn absorbing_a_clashing_identity_is_refused() -> Outcome<()> {
961 let st = res!(seed(b"abc", 0));
962 let seed_id = st.seed;
963 let head = res!(Header::new(OpId::new(ReplicaId::new(1), 3), vec![seed_id]));
964 let insert = |bytes: &[u8]| Op::Splice {
965 left: Some(Anchor::after(ContentId::new(seed_id, 0))),
966 right: None,
967 remove: Vec::new(),
968 insert: bytes.to_vec().into(),
969 };
970 let mut mine = Sequence::new();
971 for op in &st.ops {
972 res!(mine.apply(op.0.clone(), op.1.clone()));
973 }
974 res!(mine.apply(head.clone(), insert(b"one")));
975 // The other repository holds the staging, something new, and a clash.
976 let mut theirs = Sequence::new();
977 for op in &st.ops {
978 res!(theirs.apply(op.0.clone(), op.1.clone()));
979 }
980 res!(theirs.apply(head, insert(b"two")));
981 let other = res!(Header::new(OpId::new(ReplicaId::new(2), 4), vec![seed_id]));
982 res!(theirs.apply(other.clone(), insert(b"three")));
983 assert!(mine.absorb(&theirs).is_err());
984 assert_eq!(mine.len(), 3, "nothing at all was taken");
985 assert!(!mine.contains(&other.id()));
986 Ok(())
987}
988
989/// There is no routing step: every record goes to the same place, and which file
990/// each operation landed in is what the render works out and reports, which is
991/// the association a wire field would have asserted.
992#[test]
993fn a_repository_of_two_files_replays_from_the_log() -> Outcome<()> {
994 use crate::log::OpLog;
995
996 let mut log = OpLog::new();
997 let r1 = ReplicaId::new(1);
998 let r2 = ReplicaId::new(2);
999 // A file each, written alternately, so that every operation's parents name
1000 // operations of the other file.
1001 let a = res!(log.author(r1, Op::FileCreate { path: b"a.txt".to_vec() }));
1002 let b = res!(log.author(r2, Op::FileCreate { path: b"b.txt".to_vec() }));
1003 let a_seed = res!(log.author(r1, Op::Splice {
1004 left: Some(Anchor::origin(a.id())),
1005 right: None,
1006 remove: Vec::new(),
1007 insert: b"alpha".to_vec().into(),
1008 }));
1009 let b_seed = res!(log.author(r2, Op::Splice {
1010 left: Some(Anchor::origin(b.id())),
1011 right: None,
1012 remove: Vec::new(),
1013 insert: b"beta".to_vec().into(),
1014 }));
1015 // Each operation is written against the whole frontier, which after the
1016 // second file was created is that creation alone.
1017 assert_eq!(b.parents(), &[a.id()]);
1018 assert_eq!(a_seed.parents(), &[b.id()]);
1019 assert_eq!(b_seed.parents(), &[a_seed.id()]);
1020 let tail = res!(log.author(r1, Op::Splice {
1021 left: Some(Anchor::after(ContentId::new(a_seed.id(), 4))),
1022 right: None,
1023 remove: Vec::new(),
1024 insert: b" and omega".to_vec().into(),
1025 }));
1026 // Replay: every record goes to the one repository.
1027 let mut seq = Sequence::new();
1028 for rec in log.iter() {
1029 res!(seq.apply_record(rec));
1030 }
1031 assert_eq!(seq.len(), 5);
1032 let repo = res!(seq.render());
1033 match repo.file(a.id()) {
1034 Some(f) => assert_eq!(f.text_lossy(), "alpha and omega"),
1035 None => return Err(err!("The file a.txt went missing."; Test, Missing)),
1036 }
1037 match repo.file(b.id()) {
1038 Some(f) => assert_eq!(f.text_lossy(), "beta"),
1039 None => return Err(err!("The file b.txt went missing."; Test, Missing)),
1040 }
1041 // The derived association: which file each placement landed in, computed by
1042 // the render rather than asserted on the wire.
1043 assert_eq!(repo.file_of(&a_seed.id()), Some(a.id()));
1044 assert_eq!(repo.file_of(&b_seed.id()), Some(b.id()));
1045 assert_eq!(repo.file_of(&tail.id()), Some(a.id()));
1046 assert_eq!(repo.index().len(), 5, "two files and three placements");
1047 // Rendering against the log's own graph gives the same answer.
1048 let cause = log.causality();
1049 assert_eq!(listing(&res!(seq.render_with(&cause))), listing(&repo));
1050 // A graph that does not describe an operation the sequence holds is refused
1051 // rather than guessed at.
1052 let empty = Sequence::new();
1053 assert!(seq.render_with(&empty.causality()).is_err());
1054 Ok(())
1055}
1056
1057/// Applying an operation twice does nothing the second time; applying two
1058/// different operations under one identity is refused.
1059#[test]
1060fn an_identity_names_one_operation() -> Outcome<()> {
1061 let st = res!(seed(b"abc", 0));
1062 let first = st.ops[1].clone();
1063 let mut seq = Sequence::new();
1064 for op in &st.ops {
1065 res!(seq.apply(op.0.clone(), op.1.clone()));
1066 }
1067 res!(seq.apply(first.0.clone(), first.1.clone()));
1068 assert_eq!(seq.len(), 2);
1069 let other = Op::Splice {
1070 left: Some(Anchor::origin(st.file)),
1071 right: None,
1072 remove: Vec::new(),
1073 insert: b"different".to_vec().into(),
1074 };
1075 assert!(seq.apply(first.0.clone(), other).is_err());
1076 // Two headers differing only in their parents are two operations too.
1077 let reparented = res!(Header::new(first.0.id(), vec![OpId::new(ReplicaId::new(9), 1)]));
1078 assert!(seq.apply(reparented, first.1).is_err());
1079 Ok(())
1080}
1081
1082/// Origins bind on one side each, a move may not name a byte twice, and an
1083/// operation that places bytes names at least one origin.
1084#[test]
1085fn an_operation_the_structure_cannot_resolve_is_refused() -> Outcome<()> {
1086 let id = OpId::new(ReplicaId::new(1), 1);
1087 let cid = ContentId::new(id, 0);
1088 let mut seq = Sequence::new();
1089 let head = || Header::root(OpId::new(ReplicaId::new(2), 2));
1090 assert!(seq.apply(head(), Op::Splice {
1091 left: Some(Anchor::before(cid)),
1092 right: None,
1093 remove: Vec::new(),
1094 insert: b"x".to_vec().into(),
1095 }).is_err());
1096 assert!(seq.apply(head(), Op::Splice {
1097 left: None,
1098 right: Some(Anchor::after(cid)),
1099 remove: Vec::new(),
1100 insert: b"x".to_vec().into(),
1101 }).is_err());
1102 assert!(seq.apply(head(), Op::Move {
1103 src: vec![
1104 res!(ContentRange::new(id, 0, 4)),
1105 res!(ContentRange::new(id, 2, 6)),
1106 ],
1107 left: Some(Anchor::origin(id)),
1108 right: None,
1109 }).is_err());
1110 // And one that places bytes without naming where.
1111 assert!(seq.apply(head(), Op::Splice {
1112 left: None,
1113 right: None,
1114 remove: Vec::new(),
1115 insert: b"x".to_vec().into(),
1116 }).is_err());
1117 assert!(seq.is_empty());
1118 Ok(())
1119}
1120
1121/// A move whose destination sits inside its own source is a cycle of length one.
1122/// Left unseen it detaches the move's slots from the forest and loses their
1123/// bytes; the demotion rule sees it, and every byte survives.
1124#[test]
1125fn a_move_into_its_own_source_keeps_its_bytes() -> Outcome<()> {
1126 let mut st = res!(seed(ALPHA, 1));
1127 let view = res!(st.reps[0].view());
1128 // Take "0123456789" and land it in the middle of itself.
1129 let src = res!(view.span(0, 10));
1130 let (left, right) = res!(view.gap(5));
1131 let op = res!(st.reps[0].author(Op::Move { src, left, right }));
1132 let op_id = op.0.id();
1133 let mut seq = Sequence::new();
1134 for staged in &st.ops {
1135 res!(seq.apply(staged.0.clone(), staged.1.clone()));
1136 }
1137 res!(seq.apply(op.0, op.1));
1138 let out = res!(seq.render());
1139 res!(seq.check_conservation(&out));
1140 let file = match out.file(st.file) {
1141 Some(f) => f,
1142 None => return Err(err!("The file went missing."; Test, Missing)),
1143 };
1144 assert_eq!(file.len(), 20, "the moved bytes must not vanish");
1145 assert_eq!(out.flags(), &[
1146 Flag::Demoted { op: op_id, sub: 0, origin: Origin::Left },
1147 Flag::Demoted { op: op_id, sub: 0, origin: Origin::Right },
1148 ]);
1149 Ok(())
1150}
1151
1152/// In the terms the cost model is stated in.
1153#[test]
1154fn the_render_reports_what_it_cost() -> Outcome<()> {
1155 let mut st = res!(seed(LIST, 2));
1156 let (r1, r2) = st.reps.split_at_mut(1);
1157 st.ops.push(res!(r1[0].move_range(7, 7, 0)));
1158 st.ops.push(res!(r2[0].replace(9, 1, b"Soy m")));
1159 let mut seq = Sequence::new();
1160 for op in &st.ops {
1161 res!(seq.apply(op.0.clone(), op.1.clone()));
1162 }
1163 let out = res!(seq.render());
1164 let stats = out.stats();
1165 assert_eq!(stats.ops, 4);
1166 assert_eq!(stats.files, 1);
1167 assert_eq!(stats.atoms, 3, "the file's origin anchor and the two splices");
1168 assert_eq!(stats.atom_bytes, LIST.len() as u64 + 5 + 1,
1169 "the origin anchor is a byte like any other, and is born dead");
1170 assert!(stats.slots_divided >= stats.slots_placed,
1171 "dividing a slot never yields fewer");
1172 assert_eq!(stats.claim_intervals, 1, "one contiguous run moved");
1173 assert_eq!(stats.dead_intervals, 2, "one byte died, and the origin anchor");
1174 assert_eq!(stats.withheld, 0, "no file was deleted");
1175 assert_eq!(stats.orphaned, 0);
1176 match out.file(st.file) {
1177 Some(f) => assert_eq!(stats.rendered, f.len() as u64),
1178 None => return Err(err!("The file went missing."; Test, Missing)),
1179 }
1180 Ok(())
1181}
1182
1183/// The rendered runs still name the content that made them, so an index in the
1184/// render can be turned back into a name.
1185#[test]
1186fn provenance_follows_the_bytes() -> Outcome<()> {
1187 let mut st = res!(seed(LIST, 1));
1188 let seed_id = st.seed;
1189 st.ops.push(res!(st.reps[0].move_range(7, 7, 0)));
1190 let mut seq = Sequence::new();
1191 for op in &st.ops {
1192 res!(seq.apply(op.0.clone(), op.1.clone()));
1193 }
1194 let out = res!(seq.render());
1195 let file = match out.file(st.file) {
1196 Some(f) => f,
1197 None => return Err(err!("The file went missing."; Test, Missing)),
1198 };
1199 assert_eq!(file.text_lossy(), "- Milk\n- Eggs\n- Cheese\n");
1200 // The first rendered byte is now the eighth byte the seeding splice made.
1201 assert_eq!(res!(file.content_at(0)), ContentId::new(seed_id, 7));
1202 assert_eq!(res!(file.content_at(7)), ContentId::new(seed_id, 0));
1203 assert_eq!(res!(file.span(0, 7)), vec![res!(ContentRange::new(seed_id, 7, 14))]);
1204 assert!(file.content_at(file.len()).is_err());
1205 // The gap at the start of a file names that file's origin anchor, which is
1206 // what an operation binds to when there is nothing else to bind to.
1207 let (left, _) = res!(file.gap(0));
1208 assert_eq!(left, Some(Anchor::origin(st.file)));
1209 Ok(())
1210}
1211
1212/// The run is taken to the front of the file, and the note's spans move with it.
1213///
1214/// Nothing was written to make this happen. A note names bytes, the render says
1215/// where each byte is, and the move had already changed the answer.
1216#[test]
1217fn a_note_follows_a_move() -> Outcome<()> {
1218 let mut st = res!(seed(ALPHA, 1));
1219 st.ops.push(res!(st.reps[0].note(5, 5, b"why five?")));
1220 let before = res!(converge(&st.ops));
1221 let file = match before.file(st.file) {
1222 Some(f) => f,
1223 None => return Err(err!("The file went missing."; Test, Missing)),
1224 };
1225 assert_eq!(file.notes().len(), 1);
1226 assert_eq!(file.notes()[0].spans(), &[Span::new(5, 5)]);
1227 assert_eq!(file.notes()[0].text_lossy(), "why five?");
1228 // Take the noted run to the front.
1229 st.ops.push(res!(st.reps[0].move_range(5, 5, 0)));
1230 let after = res!(converge(&st.ops));
1231 let file = match after.file(st.file) {
1232 Some(f) => f,
1233 None => return Err(err!("The file went missing."; Test, Missing)),
1234 };
1235 assert_eq!(file.text_lossy(), "5678901234ABCDEFGHIJ");
1236 assert_eq!(file.notes().len(), 1);
1237 assert_eq!(file.notes()[0].spans(), &[Span::new(0, 5)],
1238 "the note went where the bytes went");
1239 // And the repository says the same, once.
1240 assert_eq!(after.notes().len(), 1);
1241 assert!(!after.notes()[0].on_dead());
1242 assert_eq!(after.notes()[0].files().len(), 1);
1243 assert_eq!(after.notes()[0].spans_in(st.file), &[Span::new(0, 5)]);
1244 Ok(())
1245}
1246
1247/// The note is about content, and some of that content is gone.
1248#[test]
1249fn a_note_narrows_to_the_surviving_content() -> Outcome<()> {
1250 let mut st = res!(seed(ALPHA, 1));
1251 st.ops.push(res!(st.reps[0].note(5, 5, b"about 56789")));
1252 // Delete "67" from the middle of the noted run.
1253 st.ops.push(res!(st.reps[0].delete(6, 2)));
1254 let repo = res!(converge(&st.ops));
1255 let file = match repo.file(st.file) {
1256 Some(f) => f,
1257 None => return Err(err!("The file went missing."; Test, Missing)),
1258 };
1259 assert_eq!(file.text_lossy(), "01234589ABCDEFGHIJ");
1260 assert_eq!(file.notes().len(), 1);
1261 // Three of the five bytes are left, and they are still adjacent.
1262 assert_eq!(file.notes()[0].spans(), &[Span::new(5, 3)]);
1263 assert_eq!(file.notes()[0].len(), 3);
1264 // An insertion inside the run is not part of the note: the note is about the
1265 // bytes it named, and those are not among them.
1266 st.ops.push(res!(st.reps[0].insert(6, b"xx")));
1267 let repo = res!(converge(&st.ops));
1268 let file = match repo.file(st.file) {
1269 Some(f) => f,
1270 None => return Err(err!("The file went missing."; Test, Missing)),
1271 };
1272 assert_eq!(file.text_lossy(), "012345xx89ABCDEFGHIJ");
1273 assert_eq!(file.notes()[0].spans(), &[Span::new(5, 1), Span::new(8, 2)]);
1274 Ok(())
1275}
1276
1277/// A note whose content has been deleted entirely is not lost: it is reported as
1278/// a note on dead content, and it shows in no file.
1279#[test]
1280fn a_note_on_deleted_content_says_so() -> Outcome<()> {
1281 let mut st = res!(seed(ALPHA, 1));
1282 st.ops.push(res!(st.reps[0].note(5, 5, b"doomed")));
1283 st.ops.push(res!(st.reps[0].delete(5, 5)));
1284 let repo = res!(converge(&st.ops));
1285 let file = match repo.file(st.file) {
1286 Some(f) => f,
1287 None => return Err(err!("The file went missing."; Test, Missing)),
1288 };
1289 assert_eq!(file.text_lossy(), "01234ABCDEFGHIJ");
1290 assert!(file.notes().is_empty(), "no margin has anything to point at");
1291 assert_eq!(repo.notes().len(), 1, "the note itself is not lost");
1292 assert!(repo.notes()[0].on_dead());
1293 assert!(repo.notes()[0].files().is_empty());
1294 assert_eq!(repo.notes()[0].text_lossy(), "doomed");
1295 assert_eq!(repo.dead_notes().len(), 1);
1296 assert_eq!(repo.stats().notes, 1);
1297 Ok(())
1298}
1299
1300/// Two spans, because that is where its content is.
1301#[test]
1302fn a_note_tears_with_its_content() -> Outcome<()> {
1303 let mut st = res!(seed(ALPHA, 1));
1304 st.ops.push(res!(st.reps[0].note(5, 5, b"one run, for now")));
1305 // Take the middle two bytes of the noted run to the end of the file.
1306 st.ops.push(res!(st.reps[0].move_range(7, 2, 20)));
1307 let repo = res!(converge(&st.ops));
1308 let file = match repo.file(st.file) {
1309 Some(f) => f,
1310 None => return Err(err!("The file went missing."; Test, Missing)),
1311 };
1312 assert_eq!(file.text_lossy(), "01234569ABCDEFGHIJ78");
1313 assert_eq!(file.notes().len(), 1);
1314 assert_eq!(file.notes()[0].spans().len(), 2,
1315 "the noted run is in two places, so the note is in two places");
1316 assert_eq!(file.notes()[0].len(), 5, "and no byte of it was lost");
1317 Ok(())
1318}
1319
1320/// Two notes on one file are handed over in the order a margin would draw them,
1321/// and a note lands on the exact bytes it named.
1322#[test]
1323fn notes_arrive_in_render_order() -> Outcome<()> {
1324 let mut st = res!(seed(ALPHA, 1));
1325 st.ops.push(res!(st.reps[0].note(12, 4, b"second")));
1326 st.ops.push(res!(st.reps[0].note(2, 3, b"first")));
1327 let repo = res!(converge(&st.ops));
1328 let file = match repo.file(st.file) {
1329 Some(f) => f,
1330 None => return Err(err!("The file went missing."; Test, Missing)),
1331 };
1332 let texts: Vec<String> = file.notes().iter().map(|n| n.text_lossy()).collect();
1333 assert_eq!(texts, vec![fmt!("first"), fmt!("second")]);
1334 // The repository lists them in identifier order instead, which is what every
1335 // other list in the render is in.
1336 let ids: Vec<OpId> = repo.notes().iter().map(|n| n.note()).collect();
1337 let mut sorted = ids.clone();
1338 sorted.sort();
1339 assert_eq!(ids, sorted);
1340 // The span names exactly the bytes the note was written against.
1341 let n = match file.note(ids[0]) {
1342 Some(n) => n,
1343 None => return Err(err!("A note went missing."; Test, Missing)),
1344 };
1345 let span = n.spans()[0];
1346 assert_eq!(
1347 &file.bytes()[span.at as usize..span.end() as usize],
1348 match n.text_lossy().as_str() {
1349 "second" => &b"CDEF"[..],
1350 _ => &b"234"[..],
1351 },
1352 );
1353 Ok(())
1354}
1355
1356/// A note about nothing is refused by the frontend that would have written it,
1357/// and by the structure that would have held it.
1358#[test]
1359fn a_note_about_nothing_is_refused() -> Outcome<()> {
1360 let st = res!(seed(ALPHA, 1));
1361 let view = res!(st.reps[0].view());
1362 assert!(view.note_on(4, 0, b"about what?".to_vec()).is_err());
1363 // And beyond the file, which is the other way to name nothing.
1364 assert!(view.note_on(40, 2, b"beyond".to_vec()).is_err());
1365 Ok(())
1366}
1367
1368/// The render read backwards puts named content where a reader will find it,
1369/// wherever a move has since taken it.
1370///
1371/// This is the lookup a note resolves through, asked directly, because a flag
1372/// names content too and its reader wants a position in a file rather than an
1373/// offset into an operation.
1374#[test]
1375fn content_is_found_where_it_now_renders() -> Outcome<()> {
1376 let mut st = res!(seed(ALPHA, 1));
1377 // Take "56789" to the front, so that the seeded content renders in three runs
1378 // and none of them where it was written.
1379 st.ops.push(res!(st.reps[0].move_range(5, 5, 0)));
1380 let repo = res!(converge(&st.ops));
1381 let file = match repo.file(st.file) {
1382 Some(f) => f,
1383 None => return Err(err!("The file went missing."; Test, Missing)),
1384 };
1385 assert_eq!(file.text_lossy(), "5678901234ABCDEFGHIJ");
1386 let placed = repo.placement();
1387 // The moved run, which is at the front now.
1388 let found = placed.find(&[res!(ContentRange::new(st.seed, 5, 10))]);
1389 assert_eq!(found.len(), 1, "one file shows it");
1390 assert_eq!(found[0].file, st.file);
1391 assert_eq!(found[0].spans, vec![Span::new(0, 5)]);
1392 // A range straddling the move renders in two places, and the two runs that
1393 // abut are reported as one span rather than as the seam between them.
1394 let found = placed.find(&[res!(ContentRange::new(st.seed, 3, 12))]);
1395 assert_eq!(found.len(), 1);
1396 assert_eq!(found[0].spans, vec![Span::new(0, 5), Span::new(8, 4)]);
1397 Ok(())
1398}
1399
1400/// Content that renders nowhere is answered with nowhere, which is what lets a
1401/// caller say so rather than invent a place.
1402#[test]
1403fn dead_content_is_found_in_no_file() -> Outcome<()> {
1404 let mut st = res!(seed(ALPHA, 1));
1405 st.ops.push(res!(st.reps[0].delete(5, 5)));
1406 let repo = res!(converge(&st.ops));
1407 let placed = repo.placement();
1408 assert!(placed.find(&[res!(ContentRange::new(st.seed, 5, 10))]).is_empty(),
1409 "the bytes are dead, so no file shows them");
1410 // The live neighbours of the dead run are still found, so the emptiness is
1411 // about the content and not about the lookup.
1412 let found = placed.find(&[res!(ContentRange::new(st.seed, 0, 20))]);
1413 assert_eq!(found.len(), 1);
1414 assert_eq!(found[0].spans, vec![Span::new(0, 15)]);
1415 Ok(())
1416}