Oregami
Repositories/oxedyne/fe2o3

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

31.3 KiB, 42 runs

created by r1870400018:20413, 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 overlap-arbitration cases: what a file holds when two people rewrite one
2//! region at once.
3//!
4//! Every case here is transcribed from the planted sweep that settled the rule,
5//! and every expectation is that sweep's own render under the rule this crate now
6//! implements: the connected components of the overlap graph are the arbitration
7//! groups, components contended by the same replicas over the same files are one
8//! group, the op-order maximum prevails, and every member concurrent with it
9//! yields. The sweep's replicas were numbered from two because its first replica
10//! typed the base text; here replica zero creates the file and writes it, so each
11//! of the sweep's authors is one lower.
12//!
13//! Three properties are asserted throughout, because they are what the rule was
14//! adopted for. The contended region holds **whole hunks and never an interleave**
15//! -- which is not the same as holding one author's work, and the case that shows
16//! the difference is here. Nothing is lost: a yielded insertion is dead, not
17//! homeless, and the conservation check runs inside every delivery order of every
18//! case. And both sides are told, by one flag that names the group and the
19//! operation that prevailed rather than a pair that may never have met.
20//!
21//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
22//! Anthropic Claude
23
24use crate::id::{
25 OpId,
26 ReplicaId,
27};
28use crate::op::{
29 Header,
30 Op,
31};
32use crate::seq::render::{
33 Flag,
34 Rendered,
35 Repo,
36};
37use crate::seq::Sequence;
38
39use oxedyne_fe2o3_core::prelude::*;
40
41
42// The trial's own `src/util.rs`, which is round 3's base.
43const PARSE: &str = "\
44/// Parses a decimal string, treating anything malformed as zero.
45pub fn parse_or_zero(s: &str) -> i64 {
46\tmatch s.trim().parse::<i64>() {
47\t\tOk(v) => v,
48\t\tErr(_) => 0,
49\t}
50}
51";
52
53// Two functions in one file, which is what a two-component collision needs.
54const TWO: &str = "\
55pub fn parse_or_zero(s: &str) -> i64 {
56\tmatch s.trim().parse::<i64>() {
57\t\tOk(v) => v,
58\t\tErr(_) => 0,
59\t}
60}
61
62pub fn twice(n: i64) -> i64 {
63\tlet m = n * 2;
64\tm
65}
66";
67
68// A paragraph, for the containment, chain and partial-sync cases.
69const PROSE: &str = "The renderer places every run against the anchors it was \
70written at, and the result is convergent, conserved and attributed. It is not a \
71text.\n";
72
73// The body of the parser, which several cases replace whole.
74const BODY: &str = "\tmatch s.trim().parse::<i64>() {\n\t\tOk(v) => v,\n\t\tErr(_) => 0,\n\t}\n";
75
76// What the parser reads as once one author has had it.
77const REWRITTEN: &str = "\
78/// Parses a decimal string, treating anything malformed as zero.
79pub fn parse_or_zero(s: &str) -> i64 {
80\tlet cleaned = s.trim();
81\tcleaned.parse::<i64>().unwrap_or(0)
82}
83";
84
85
86/// One replica of a repository holding one file: the frontend that turns editing
87/// intent into content-anchored operations, which is what an editor would be.
88struct Replica {
89 id: u64, // every operation of this replica is named by it
90 seq: Sequence,
91 file: OpId, // the file being edited
92}
93
94impl Replica {
95
96 fn new(id: u64, file: OpId) -> Self {
97 Self { id, seq: Sequence::new(), file }
98 }
99
100 /// A Lamport counter, and everything this replica can see as the operation's
101 /// parents.
102 fn next_head(&self)
103 -> Outcome<Header>
104 {
105 let seen = self.seq.iter().map(|(id, _)| id.counter).max().unwrap_or(0);
106 Header::new(
107 OpId::new(ReplicaId::new(self.id), seen + 1),
108 self.seq.causality().heads(),
109 )
110 }
111
112 fn recv(&mut self, op: (Header, Op))
113 -> Outcome<()>
114 {
115 self.seq.apply(op.0, op.1)
116 }
117
118 fn view(&self)
119 -> Outcome<Rendered>
120 {
121 let repo = res!(self.seq.render());
122 match repo.file(self.file) {
123 Some(f) => Ok(f.clone()),
124 None => Err(err!("The replica has no file {}.", self.file; Test, Missing)),
125 }
126 }
127
128 fn author(&mut self, op: Op)
129 -> Outcome<(Header, Op)>
130 {
131 let head = res!(self.next_head());
132 res!(self.seq.apply(head.clone(), op.clone()));
133 Ok((head, op))
134 }
135
136 /// The offset of the first occurrence of some text in this replica's view.
137 fn at(&self, find: &str)
138 -> Outcome<usize>
139 {
140 let text = res!(self.view()).text_lossy();
141 match text.find(find) {
142 Some(i) => Ok(i),
143 None => Err(err!(
144 "The replica's view does not hold {:?}.", find; Test, Missing)),
145 }
146 }
147
148 /// One splice, which is the shape a capture emits for one hunk.
149 fn rep(&mut self, find: &str, with: &str)
150 -> Outcome<(Header, Op)>
151 {
152 let at = res!(self.at(find));
153 let op = res!(res!(self.view()).splice(at, find.len(), with.as_bytes().to_vec()));
154 self.author(op)
155 }
156
157 fn del(&mut self, find: &str)
158 -> Outcome<(Header, Op)>
159 {
160 let at = res!(self.at(find));
161 let op = res!(res!(self.view()).splice(at, find.len(), Vec::new()));
162 self.author(op)
163 }
164
165 /// Immediately after the first occurrence.
166 fn ins(&mut self, find: &str, with: &str)
167 -> Outcome<(Header, Op)>
168 {
169 let at = res!(self.at(find)) + find.len();
170 let op = res!(res!(self.view()).splice(at, 0, with.as_bytes().to_vec()));
171 self.author(op)
172 }
173}
174
175
176/// Creates one file, writes `text` into it on replica zero, and hands out `n`
177/// replicas that have seen both operations.
178fn seed(text: &str, n: u64)
179 -> Outcome<(Vec<Replica>, Vec<(Header, Op)>, OpId)>
180{
181 let mut origin = Replica::new(0, OpId::default());
182 let create = res!(origin.author(Op::FileCreate { path: b"util.rs".to_vec() }));
183 let file = create.0.id();
184 origin.file = file;
185 let mut ops = vec![create];
186 ops.push(res!(origin.rep("", text)));
187 let mut reps: Vec<Replica> = Vec::new();
188 for i in 1..=n {
189 let mut r = Replica::new(i, file);
190 for op in &ops {
191 res!(r.recv(op.clone()));
192 }
193 reps.push(r);
194 }
195 Ok((reps, ops, file))
196}
197
198fn permute(idx: &mut Vec<usize>, k: usize, out: &mut Vec<Vec<usize>>) {
199 if k == idx.len() {
200 out.push(idx.clone());
201 return;
202 }
203 for i in k..idx.len() {
204 idx.swap(k, i);
205 permute(idx, k + 1, out);
206 idx.swap(k, i);
207 }
208}
209
210/// A one-line listing of the live files.
211fn listing(repo: &Repo) -> String {
212 let mut s = String::new();
213 for f in repo.files().iter().filter(|f| f.is_live()) {
214 s.push_str(&fmt!("{}={:?} ", f.path_lossy(), f.text_lossy()));
215 }
216 s.trim_end().to_string()
217}
218
219/// Applies an operation set in every delivery order where the set is small
220/// enough, or in every rotation, the reverse and a spread of shuffles where it is
221/// not, and requires that all of them render the same bytes and raise the same
222/// flags.
223///
224/// Conservation is checked on every order, which is the whole of what says a
225/// yielded insertion is dead rather than lost.
226fn converge(ops: &[(Header, Op)])
227 -> Outcome<Repo>
228{
229 let n = ops.len();
230 let mut orders: Vec<Vec<usize>> = Vec::new();
231 if n <= 7 {
232 let mut idx: Vec<usize> = (0..n).collect();
233 permute(&mut idx, 0, &mut orders);
234 } else {
235 for k in 0..n {
236 orders.push((0..n).map(|i| (i + k) % n).collect());
237 }
238 orders.push((0..n).rev().collect());
239 let mut state = 0x0f1e_2d3c_4b5a_6978u64.wrapping_add(n as u64);
240 let mut next = move || {
241 state = state
242 .wrapping_mul(6_364_136_223_846_793_005)
243 .wrapping_add(1_442_695_040_888_963_407);
244 (state >> 33) as usize
245 };
246 for _ in 0..60 {
247 let mut idx: Vec<usize> = (0..n).collect();
248 for i in (1..idx.len()).rev() {
249 idx.swap(i, next() % (i + 1));
250 }
251 orders.push(idx);
252 }
253 }
254 let mut first: Option<Repo> = None;
255 for order in &orders {
256 let mut seq = Sequence::new();
257 for i in order {
258 res!(seq.apply(ops[*i].0.clone(), ops[*i].1.clone()));
259 }
260 let got = res!(seq.render());
261 res!(seq.check_conservation(&got));
262 assert_eq!(got.stats().orphaned, 0, "a slot belonged to no file");
263 match &first {
264 None => first = Some(got),
265 Some(want) => {
266 if listing(want) != listing(&got) {
267 return Err(err!(
268 "Delivery order changed the render: {} against {}.",
269 listing(want), listing(&got);
270 Test, Mismatch));
271 }
272 if want.flags() != got.flags() {
273 return Err(err!(
274 "Delivery order changed the flags: {:?} against {:?}.",
275 want.flags(), got.flags();
276 Test, Mismatch));
277 }
278 },
279 }
280 }
281 match first {
282 Some(r) => Ok(r),
283 None => Err(err!("No delivery order was tried."; Test, Bug)),
284 }
285}
286
287/// Checks the file's render against the answer the case prescribes, under every
288/// delivery order.
289fn case(file: OpId, expect: &str, ops: &[(Header, Op)])
290 -> Outcome<Repo>
291{
292 let repo = res!(converge(ops));
293 let got = match repo.file(file) {
294 Some(f) => f.clone(),
295 None => return Err(err!("The render holds no file {}.", file; Test, Missing)),
296 };
297 assert_eq!(got.text_lossy(), expect);
298 Ok(repo)
299}
300
301fn id(replica: u64, counter: u64) -> OpId {
302 OpId::new(ReplicaId::new(replica), counter)
303}
304
305/// Every yield the render decided, as `(yielder, prevailed, group, through)`.
306fn yields(repo: &Repo) -> Vec<(OpId, OpId, Vec<OpId>, Option<OpId>)> {
307 repo.flags().iter()
308 .filter_map(|f| match f {
309 Flag::Yielded { op, to, group, through }
310 => Some((*op, *to, group.clone(), *through)),
311 _ => None,
312 })
313 .collect()
314}
315
316fn yielded_to(repo: &Repo, op: OpId) -> Option<OpId> {
317 yields(repo).into_iter().find(|(o, ..)| *o == op).map(|(_, to, ..)| to)
318}
319
320/// Whether the two operations were flagged as having named the same content.
321fn overlapped(repo: &Repo, a: OpId, b: OpId) -> bool {
322 repo.flags().iter().any(|f| match f {
323 Flag::Overlap { ops, .. } => ops.contains(&a) && ops.contains(&b),
324 _ => false,
325 })
326}
327
328fn count(repo: &Repo, kind: fn(&Flag) -> bool) -> usize {
329 repo.flags().iter().filter(|f| kind(f)).count()
330}
331
332
333/// Round 3 of the self-hosting trial: two authors rewrite one function body,
334/// each capture emitting two hunks.
335///
336/// The status quo renders the surviving fragments of the base interleaved with
337/// two authors' insertions, which compiles for nobody. Under arbitration the two
338/// hunks of each author form one component -- each author's second hunk is
339/// causally after their first, so neither author's pair is a race with itself --
340/// the op-order maximum prevails, and the region reads as whole hunks.
341#[test]
342fn two_authors_rewriting_one_body_leave_one_authors_function() -> Outcome<()> {
343 let (mut reps, mut ops, file) = res!(seed(PARSE, 2));
344 ops.push(res!(reps[0].rep(
345 "\tmatch s.trim().parse::<i64>() {\n",
346 "\ts.trim().parse::<i64>().unwrap_or(0)\n")));
347 ops.push(res!(reps[0].del("\t\tOk(v) => v,\n\t\tErr(_) => 0,\n\t}\n")));
348 ops.push(res!(reps[1].rep(
349 "\tmatch s.trim().parse::<i64>() {\n",
350 "\tlet cleaned = s.trim();\n\tcleaned.parse::<i64>().unwrap_or(0)\n")));
351 ops.push(res!(reps[1].del("\t\tOk(v) => v,\n\t\tErr(_) => 0,\n\t}\n")));
352
353 let repo = res!(case(file, REWRITTEN, &ops));
354 // Replica 2 is the group's maximum on the replica tie-break, both authors
355 // having minted the same counters, so replica 1's two hunks yield.
356 assert_eq!(yielded_to(&repo, id(1, 3)), Some(id(2, 4)));
357 assert_eq!(yielded_to(&repo, id(1, 4)), Some(id(2, 4)));
358 assert_eq!(yielded_to(&repo, id(2, 3)), None);
359 assert_eq!(yielded_to(&repo, id(2, 4)), None);
360 // The raw fact stays beneath the arbitration.
361 assert!(count(&repo, |f| matches!(f, Flag::Overlap { .. })) > 0);
362 Ok(())
363}
364
365/// Round 3 again, planted as the minimal hunks a real diff emits, so that the
366/// base's common substrings stay alive between the two authors' fragments.
367///
368/// This is the faithful shape of the trial's defect: six provenance runs of
369/// nobody's function. The rule is the same and so is the answer.
370#[test]
371fn the_minimal_hunks_of_round_three_leave_one_authors_function() -> Outcome<()> {
372 let (mut reps, mut ops, file) = res!(seed(PARSE, 2));
373 // Replica 1, towards `s.trim().parse::<i64>().unwrap_or(0)`.
374 ops.push(res!(reps[0].del("match ")));
375 ops.push(res!(reps[0].rep(") {\n", ").unwrap_or(0)\n")));
376 ops.push(res!(reps[0].del("\t\tOk(v) => v,\n\t\tErr(_) => 0,\n\t}\n")));
377 // Replica 2, towards the `let cleaned = ...` form.
378 ops.push(res!(reps[1].rep("match ", "let cleaned = ")));
379 ops.push(res!(reps[1].ins("s.trim()", ";\n\tcleaned")));
380 ops.push(res!(reps[1].rep(") {\n", ").unwrap_or(0)\n")));
381 ops.push(res!(reps[1].del("\t\tOk(v) => v,\n\t\tErr(_) => 0,\n\t}\n")));
382
383 let repo = res!(case(file, REWRITTEN, &ops));
384 assert!(!yields(&repo).is_empty());
385 // Every rendered byte of the body is replica 2's or the base's: no fragment of
386 // replica 1 survives between them, which is what "whole hunks" means.
387 for (op, ..) in yields(&repo) {
388 assert_eq!(op.replica, ReplicaId::new(1));
389 }
390 Ok(())
391}
392
393/// Two authors rewrite the same two functions, in opposite order, so that the two
394/// components have different op-order maxima.
395///
396/// Separate components would leave one author's doubler beside the other's
397/// parser: two whole hunks by different people, which is the known weakness of
398/// the component rule and is what the same-contenders merge exists to remove. The
399/// two components are contended by the same pair of replicas over the same file,
400/// so they are one group; its maximum is replica 2's parser, and replica 2's
401/// doubler survives on the causal exemption.
402#[test]
403fn two_functions_rewritten_in_opposite_order_read_as_one_author() -> Outcome<()> {
404 let (mut reps, mut ops, file) = res!(seed(TWO, 2));
405 let parser = "\tmatch s.trim().parse::<i64>() {\n\t\tOk(v) => v,\n\t\tErr(_) => 0,\n\t}\n";
406 let doubler = "\tlet m = n * 2;\n\tm\n";
407 // Replica 1 does the parser first, then the doubler.
408 ops.push(res!(reps[0].rep(parser, "\ts.trim().parse::<i64>().unwrap_or(0)\n")));
409 ops.push(res!(reps[0].rep(doubler, "\tn * 2\n")));
410 // Replica 2 does the doubler first, then the parser.
411 ops.push(res!(reps[1].rep(doubler, "\tn + n\n")));
412 ops.push(res!(reps[1].rep(parser,
413 "\tlet cleaned = s.trim();\n\tcleaned.parse::<i64>().unwrap_or(0)\n")));
414
415 let repo = res!(case(file, "\
416pub fn parse_or_zero(s: &str) -> i64 {
417\tlet cleaned = s.trim();
418\tcleaned.parse::<i64>().unwrap_or(0)
419}
420
421pub fn twice(n: i64) -> i64 {
422\tn + n
423}
424", &ops));
425 // One group of four, whose maximum is replica 2's parser hunk.
426 let ys = yields(&repo);
427 assert_eq!(ys.len(), 2);
428 for (_, to, group, through) in &ys {
429 assert_eq!(*to, id(2, 4));
430 assert_eq!(*group, vec![id(1, 3), id(2, 3), id(1, 4), id(2, 4)]);
431 assert_eq!(*through, None);
432 }
433 // Replica 2's own doubler is in the winner's causal past, so the exemption
434 // keeps it and the file reads as one author throughout.
435 assert_eq!(yielded_to(&repo, id(2, 3)), None);
436 Ok(())
437}
438
439/// Three authors in a chain: the first overlaps the second, the second the third,
440/// and the first and the third are disjoint.
441///
442/// A component is a component-wide decision, so the first yields to the third --
443/// an operation it never named a byte of. The flag has to say that the *group*
444/// prevailed and name its maximum, because "this operation rewrote your region"
445/// is simply false here, and the sweep found it false of roughly three yields in
446/// ten.
447#[test]
448fn a_chain_yields_to_a_group_maximum_it_never_met() -> Outcome<()> {
449 let (mut reps, mut ops, file) = res!(seed(PROSE, 3));
450 ops.push(res!(reps[0].rep("renderer places every run", "engine puts each run")));
451 ops.push(res!(reps[1].rep("every run against the anchors",
452 "each run where its anchors say")));
453 ops.push(res!(reps[2].rep("against the anchors it was written at",
454 "at the anchors it was authored against")));
455
456 let repo = res!(case(file, "The renderer places every run at the anchors it was \
457authored against, and the result is convergent, conserved and attributed. It is \
458not a text.\n", &ops));
459 // All three are one component; the maximum is replica 3.
460 assert_eq!(yielded_to(&repo, id(1, 3)), Some(id(3, 3)));
461 assert_eq!(yielded_to(&repo, id(2, 3)), Some(id(3, 3)));
462 assert_eq!(yielded_to(&repo, id(3, 3)), None);
463 // And replica 1 yielded to an operation it never overlapped.
464 assert!(!overlapped(&repo, id(1, 3), id(3, 3)));
465 assert!(overlapped(&repo, id(1, 3), id(2, 3)));
466 Ok(())
467}
468
469/// Three parties over two functions, both contended by all three.
470///
471/// This is the merge's honest loss, and it is worth having in the suite for that
472/// reason. Under separate components replica 2 would take the parser and replica
473/// 3 the doubler, and the file would read as two authors; merged, replica 3 takes
474/// both, and replica 2 -- which had won a collision outright -- shows nothing.
475/// What the merge does not do is void the work of somebody who was not
476/// contending: every merged component has the same contender set by construction.
477#[test]
478fn three_parties_over_two_functions_read_as_one_author() -> Outcome<()> {
479 let (mut reps, mut ops, file) = res!(seed(TWO, 3));
480 let parser = "\tmatch s.trim().parse::<i64>() {\n\t\tOk(v) => v,\n\t\tErr(_) => 0,\n\t}\n";
481 let doubler = "\tlet m = n * 2;\n\tm\n";
482 // Replica 1: parser then doubler.
483 ops.push(res!(reps[0].rep(parser, "\ts.trim().parse::<i64>().unwrap_or(0)\n")));
484 ops.push(res!(reps[0].rep(doubler, "\tn * 2\n")));
485 // Replica 2: doubler then parser.
486 ops.push(res!(reps[1].rep(doubler, "\tn + n\n")));
487 ops.push(res!(reps[1].rep(parser,
488 "\tlet cleaned = s.trim();\n\tcleaned.parse::<i64>().unwrap_or(0)\n")));
489 // Replica 3: parser then doubler.
490 ops.push(res!(reps[2].rep(parser, "\ts.trim().parse().unwrap_or_default()\n")));
491 ops.push(res!(reps[2].rep(doubler, "\tn.saturating_mul(2)\n")));
492
493 let repo = res!(case(file, "\
494pub fn parse_or_zero(s: &str) -> i64 {
495\ts.trim().parse().unwrap_or_default()
496}
497
498pub fn twice(n: i64) -> i64 {
499\tn.saturating_mul(2)
500}
501", &ops));
502 // Four yields, all to replica 3's doubler hunk, which is the merged group's
503 // op-order maximum; replica 3's own parser hunk is exempt.
504 let ys = yields(&repo);
505 assert_eq!(ys.len(), 4);
506 for (op, to, ..) in &ys {
507 assert_eq!(*to, id(3, 4));
508 assert!(op.replica != ReplicaId::new(3));
509 }
510 assert_eq!(yielded_to(&repo, id(3, 3)), None);
511 Ok(())
512}
513
514/// Two concurrent pure deletions over overlapping text.
515///
516/// The yielding operation's removals do not bury, so the text only the loser
517/// deleted comes back and the arbitrating render is **larger** than the
518/// unarbitrated one. Yielding is not only subtractive, and a reader of the rule
519/// who expects it only ever to take things off the disk is wrong.
520#[test]
521fn two_concurrent_deletions_render_more_than_the_status_quo_would() -> Outcome<()> {
522 let (mut reps, mut ops, file) = res!(seed(PROSE, 2));
523 ops.push(res!(reps[0].del("places every run against the anchors it was")));
524 ops.push(res!(reps[1].del("against the anchors it was written at, and")));
525
526 let want = "The renderer places every run the result is convergent, conserved \
527and attributed. It is not a text.\n";
528 let repo = res!(case(file, want, &ops));
529 assert_eq!(yielded_to(&repo, id(1, 3)), Some(id(2, 3)));
530 // The union of the two deletions is 101 bytes shorter than the base; only the
531 // prevailing one buries, so the render keeps 17 bytes the status quo removed.
532 assert!(want.len() > PROSE.len() - 101);
533 assert_eq!(want.len(), 101);
534 // A pure deletion places no slot, so the flag belongs to no file and is the
535 // repository's alone.
536 assert!(repo.files().iter().all(|f|
537 !f.flags().iter().any(|g| matches!(g, Flag::Yielded { .. }))));
538 Ok(())
539}
540
541/// One author deletes the region another rewrites, and the deleter is higher in
542/// op order.
543///
544/// The rewriter yields, its insertion is buried, and the region is simply empty.
545/// This is the trial's "delete beats edit", decided rather than accidental, and
546/// told to both. It is the honest loss in the other direction: arbitration can
547/// take off the disk text the status quo would have shown, and the bytes are then
548/// in the log and one flag away.
549#[test]
550fn a_deletion_prevails_over_a_rewrite_it_raced() -> Outcome<()> {
551 let (mut reps, mut ops, file) = res!(seed(PARSE, 2));
552 ops.push(res!(reps[0].rep(BODY, "\ts.trim().parse::<i64>().unwrap_or(0)\n")));
553 ops.push(res!(reps[1].del(BODY)));
554
555 let repo = res!(case(file, "\
556/// Parses a decimal string, treating anything malformed as zero.
557pub fn parse_or_zero(s: &str) -> i64 {
558}
559", &ops));
560 assert_eq!(yielded_to(&repo, id(1, 3)), Some(id(2, 3)));
561 Ok(())
562}
563
564/// A third author who synced with one side of a collision and not the other.
565///
566/// This is what falsifies the guarantee the rule was first stated with. Replica 1
567/// and replica 2 collide; replica 3 has seen replica 1 and not replica 2, and
568/// edits an adjacent stretch replica 2 had also named. All three are one
569/// component, the maximum is replica 3, replica 2 yields -- and replica 1 does
570/// **not**, because it is in replica 3's causal past and the exemption protects
571/// it. The region then holds two authors' hunks, each whole.
572///
573/// The exemption is load-bearing, so this is a consequence of the rule and not a
574/// defect in it. What the rule guarantees is whole hunks, never an interleave; it
575/// does not guarantee one author.
576#[test]
577fn a_third_party_synced_with_one_side_composes_two_authors_whole_hunks() -> Outcome<()> {
578 let (mut reps, mut ops, file) = res!(seed(PROSE, 3));
579 let first = res!(reps[0].rep("convergent", "correct"));
580 ops.push(first.clone());
581 ops.push(res!(reps[1].rep("convergent, conserved and attributed",
582 "right, and unreadable")));
583 // Replica 3 has seen replica 1's edit and not replica 2's.
584 res!(reps[2].recv(first));
585 ops.push(res!(reps[2].rep("conserved and attributed",
586 "conserved, ordered and attributed")));
587
588 let repo = res!(case(file, "The renderer places every run against the anchors it \
589was written at, and the result is correct, conserved, ordered and attributed. It \
590is not a text.\n", &ops));
591 // One yield, and the exempt author's hunk is in the region beside the winner's.
592 assert_eq!(yielded_to(&repo, id(2, 3)), Some(id(3, 4)));
593 assert_eq!(yielded_to(&repo, id(1, 3)), None);
594 assert_eq!(yields(&repo).len(), 1);
595 // Whole hunks, never an interleave: each author's insertion renders as one run
596 // of its own, and no run holds bytes of two operations.
597 let f = match repo.file(file) {
598 Some(f) => f.clone(),
599 None => return Err(err!("The render holds no file {}.", file; Test, Missing)),
600 };
601 let mine: Vec<_> = f.runs().iter().filter(|r| r.content.op() == id(1, 3)).collect();
602 let theirs: Vec<_> = f.runs().iter().filter(|r| r.content.op() == id(3, 4)).collect();
603 assert_eq!(mine.len(), 1);
604 assert_eq!(theirs.len(), 1);
605 Ok(())
606}
607
608/// The losing author had already refined its own new text before syncing, so its
609/// second operation is anchored wholly inside its first.
610///
611/// Burying the first without the second leaves the second rendering as a fragment
612/// at a dead site, and no flag fires for it, because no concurrent operation
613/// deleted anything -- which is the smaller scramble one round later. Yielding is
614/// therefore transitive: a splice anchored wholly within buried content yields
615/// too. The sweep counted 807 such fragments across four thousand trials without
616/// the completion and none with it.
617#[test]
618fn an_edit_inside_a_buried_insertion_yields_with_it() -> Outcome<()> {
619 let (mut reps, mut ops, file) = res!(seed(PARSE, 2));
620 ops.push(res!(reps[0].rep(BODY, "\ts.trim().parse::<i64>().unwrap_or(0)\n")));
621 // The same author, having seen nobody, refines its own new line.
622 ops.push(res!(reps[0].ins("\ts.trim()", ".to_owned()")));
623 ops.push(res!(reps[1].rep(BODY,
624 "\tlet cleaned = s.trim();\n\tcleaned.parse::<i64>().unwrap_or(0)\n")));
625
626 let repo = res!(case(file, REWRITTEN, &ops));
627 // The refinement never contended with anybody, and yields through its host.
628 assert_eq!(yielded_to(&repo, id(1, 3)), Some(id(2, 3)));
629 let (_, to, group, through) = match yields(&repo).into_iter().find(|(o, ..)| *o == id(1, 4)) {
630 Some(y) => y,
631 None => return Err(err!("The refinement did not yield."; Test, Missing)),
632 };
633 assert_eq!(to, id(2, 3));
634 assert_eq!(through, Some(id(1, 3)));
635 assert_eq!(group, vec![id(1, 3), id(2, 3)]);
636 // Nothing is stranded, because nothing is left rendering at a dead site.
637 assert_eq!(count(&repo, |f| matches!(f, Flag::Stranded { .. })), 0);
638 assert_eq!(count(&repo, |f| matches!(f, Flag::Orphaned { .. })), 0);
639 Ok(())
640}
641
642/// A capture that emits two hunks authors the second with the first as its
643/// parent, so without the exemption a winner would void its own other hunk every
644/// time a diff produced more than one. Replica 2 rewrites the head of the body and
645/// then its tail; replica 1 rewrites the whole body at once, concurrently with
646/// both. Replica 2's pair is a sequence, not a race, and both of its hunks
647/// survive.
648#[test]
649fn the_winners_own_earlier_hunk_survives_the_arbitration() -> Outcome<()> {
650 let (mut reps, mut ops, file) = res!(seed(PARSE, 2));
651 ops.push(res!(reps[1].rep("\tmatch s.trim().parse::<i64>() {\n",
652 "\tmatch s.trim().parse() {\n")));
653 ops.push(res!(reps[1].rep("\t\tErr(_) => 0,\n", "\t\tErr(_) => -1,\n")));
654 ops.push(res!(reps[0].rep(BODY, "\ts.trim().parse::<i64>().unwrap_or(0)\n")));
655
656 let repo = res!(case(file, "\
657/// Parses a decimal string, treating anything malformed as zero.
658pub fn parse_or_zero(s: &str) -> i64 {
659\tmatch s.trim().parse() {
660\t\tOk(v) => v,
661\t\tErr(_) => -1,
662\t}
663}
664", &ops));
665 assert_eq!(yields(&repo).len(), 1);
666 assert_eq!(yielded_to(&repo, id(1, 3)), Some(id(2, 4)));
667 assert_eq!(yielded_to(&repo, id(2, 3)), None);
668 Ok(())
669}
670
671/// This is the shape the sweep found the merge worse in, five trials in 3,252,
672/// and it is expected rather than a defect. Two components are contended by the
673/// same pair of replicas and merge; the merged group's maximum is replica 1's
674/// later hunk rather than replica 2's deletion, so replica 1's earlier hunk --
675/// which separate components would have buried under replica 2's deletion -- is
676/// now in the winner's causal past, the exemption protects it, and its bytes
677/// render again. A third component contended by a different pair does not merge,
678/// keeps its own winner, and the file then reads as two authors.
679///
680/// Merging is therefore not monotone in the shape of the file. Guarding against
681/// it would need a rule with no precedent in the design, and recording it is
682/// enough.
683#[test]
684fn merging_two_components_can_revive_an_edit_separation_would_have_buried()
685 -> Outcome<()>
686{
687 let (mut reps, mut ops, file) = res!(seed("one\ntwo\nthree\nfour\n", 3));
688 // Replica 1: a hunk it would lose outright on its own, an unrelated edit that
689 // lifts its counter, and then the hunk that becomes the merged group's maximum.
690 ops.push(res!(reps[0].rep("one\n", "uno\n")));
691 ops.push(res!(reps[0].rep("four\n", "cuatro\n")));
692 ops.push(res!(reps[0].rep("two\n", "dos\n")));
693 // Replica 2 contends over the first two regions, and over the third with
694 // replica 3.
695 ops.push(res!(reps[1].del("one\n")));
696 ops.push(res!(reps[1].rep("two\n", "zwei\n")));
697 ops.push(res!(reps[1].rep("three\n", "drei\n")));
698 // Replica 3 contends over the third region only.
699 ops.push(res!(reps[2].rep("three\n", "tres\n")));
700
701 let repo = res!(case(file, "uno\ndos\ndrei\ncuatro\n", &ops));
702 // The first two components are contended by replicas 1 and 2 alike, so they
703 // are one group of four whose maximum is replica 1's third operation.
704 let ys = yields(&repo);
705 assert_eq!(yielded_to(&repo, id(2, 3)), Some(id(1, 5)));
706 assert_eq!(yielded_to(&repo, id(2, 4)), Some(id(1, 5)));
707 // Replica 2's deletion never named a byte replica 1's third operation named.
708 assert!(!overlapped(&repo, id(2, 3), id(1, 5)));
709 // Replica 1's first hunk is in the merged winner's causal past, so it is
710 // exempt and renders, although its own component's maximum was concurrent with
711 // it and higher.
712 assert_eq!(yielded_to(&repo, id(1, 3)), None);
713 // The third component keeps its own winner, and the file reads as two authors,
714 // each hunk whole.
715 assert_eq!(yielded_to(&repo, id(3, 3)), Some(id(2, 5)));
716 assert_eq!(ys.len(), 3);
717 Ok(())
718}
719
720/// The flag survives the wire, group and host included.
721#[test]
722fn a_yield_flag_round_trips_through_its_dat_form() -> Outcome<()> {
723 for through in [None, Some(id(1, 3))] {
724 let flag = Flag::Yielded {
725 op: id(1, 4),
726 to: id(2, 7),
727 group: vec![id(1, 3), id(2, 3), id(2, 7)],
728 through,
729 };
730 let back = res!(Flag::from_dat(&flag.to_dat()));
731 assert_eq!(back, flag);
732 assert_eq!(flag.code(), crate::seq::render::CODE_YIELDED);
733 assert_eq!(flag.name(), "Yielded");
734 assert_eq!(flag.op(), Some(id(1, 4)));
735 }
736 Ok(())
737}
738
739/// A planted sweep: several authors rewriting overlapping regions of one file at
740/// once, rendered under permuted delivery.
741///
742/// The planted cases say the rule gives the right answer on the shapes it was
743/// designed against. This says the rule cannot be inert and cannot leave the
744/// hazard its second completion exists for. Three properties, over every trial
745/// that planted a collision:
746///
747/// - **The arbitration fires.** A rule nothing reaches is a rule nothing tests,
748/// and the count is asserted rather than hoped for.
749/// - **No fragment renders at a dead site.** A splice both of whose anchors name
750/// content inside a buried insertion is the smaller scramble one round later,
751/// and the transitive completion exists to bury it too; the sweep that settled
752/// the rule counted 807 of these without the completion and none with it.
753/// - **Nothing diverges and nothing is lost**, which [`converge`] checks on every
754/// delivery order.
755#[test]
756fn a_planted_sweep_of_overlapping_rewrites_converges_and_strands_nothing()
757 -> Outcome<()>
758{
759 let mut state = 0x51ed_3c9a_7b2f_0e41u64;
760 let mut next = move || {
761 state = state
762 .wrapping_mul(6_364_136_223_846_793_005)
763 .wrapping_add(1_442_695_040_888_963_407);
764 (state >> 33) as usize
765 };
766 let mut collisions = 0usize;
767 let mut yielded = 0usize;
768 for _ in 0..100 {
769 let lines = 6 + next() % 5;
770 let mut base = String::new();
771 for i in 0..lines {
772 base.push_str(&fmt!("line {} of the file\n", i));
773 }
774 let k = 2 + next() % 3;
775 let (mut reps, mut ops, file) = res!(seed(&base, k as u64));
776 for r in 0..k {
777 // The order an author works through its hunks in is not the order the
778 // hunks sit in the file, which is what two people fixing one file
779 // actually do and is what lets two components take different winners.
780 let mut which: Vec<usize> = (0..lines).collect();
781 for i in (1..which.len()).rev() {
782 which.swap(i, next() % (i + 1));
783 }
784 which.truncate(1 + next() % 3);
785 for (n, l) in which.iter().enumerate() {
786 let find = fmt!("line {} of the file\n", l);
787 if next() % 4 == 0 {
788 ops.push(res!(reps[r].del(&find)));
789 continue;
790 }
791 let with = fmt!("row {} by {}\n", l, r + 1);
792 ops.push(res!(reps[r].rep(&find, &with)));
793 // A quarter of the authors refine their own new text before
794 // syncing, which is what the transitive completion is for.
795 if n == 0 && next() % 4 == 0 {
796 let host = fmt!("row {}", l);
797 ops.push(res!(reps[r].ins(&host, " (revised)")));
798 }
799 }
800 }
801 let repo = res!(converge(&ops));
802 let ys = yields(&repo);
803 if ys.is_empty() {
804 continue;
805 }
806 collisions += 1;
807 yielded += ys.len();
808 assert_eq!(count(&repo, |f| matches!(f, Flag::Orphaned { .. })), 0);
809
810 // Nothing renders at a dead site. The insertions that were buried whole,
811 // and then every operation that still shows bytes: none of them may be
812 // anchored inside one.
813 let buried: Vec<OpId> = ys.iter()
814 .map(|(op, ..)| *op)
815 .filter(|op| ops.iter().any(|(h, o)| h.id() == *op && match o {
816 Op::Splice { insert, .. } => !insert.is_empty(),
817 _ => false,
818 }))
819 .collect();
820 let f = match repo.file(file) {
821 Some(f) => f.clone(),
822 None => return Err(err!("The render holds no file {}.", file; Test, Missing)),
823 };
824 for run in f.runs() {
825 let op = match ops.iter().find(|(h, _)| h.id() == run.content.op()) {
826 Some((_, o)) => o,
827 None => continue,
828 };
829 let (l, r) = op.origins();
830 let hosted = |a: &Option<crate::id::Anchor>| a.as_ref()
831 .map(|x| buried.contains(&x.content.op))
832 .unwrap_or(false);
833 assert!(!(hosted(&l) && hosted(&r)),
834 "{} renders inside buried content", run.content.op());
835 }
836 }
837 assert!(collisions > 10,
838 "the sweep planted too few collisions to say anything: {}", collisions);
839 assert!(yielded > collisions,
840 "the arbitration barely fired: {} yields over {} collisions",
841 yielded, collisions);
842 Ok(())
843}