Oregami
Repositories/oxedyne/ore

oxedyne/ore/oracle/src/mcases.rs

22.3 KiB, 1 run

created by r2848102244:83, 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//! Stage four: the file-identity cases, hand-written, each with the answer the
2//! options note predicts *before* the case is run.
3//!
4//! Every case is checked under every delivery order, and every case checks
5//! conservation across the whole repository rather than one file: no byte may
6//! render in two files at once, and no live byte may render nowhere. That is
7//! the invariant design note section 4.8 claims falls out of a global claim
8//! register for free, and it is the one this stage exists to test rather than
9//! assume.
10
11use crate::cases::{
12 ALPHA,
13 LIST,
14};
15use crate::id::{
16 after,
17 ContentId,
18 ContentRange,
19 OpId,
20};
21use crate::mrep::MRep;
22use crate::random::Rng;
23use crate::repo::{
24 FileId,
25 Identity,
26 MFlags,
27 MOp,
28 Repo,
29 RepoRender,
30};
31
32use oxedyne_fe2o3_core::prelude::*;
33
34/// The result of running one case under one identity rule.
35#[derive(Clone, Debug)]
36pub struct MCaseOut {
37 /// Case name.
38 pub name: &'static str,
39 /// Which candidate.
40 pub ident: Identity,
41 /// What the options note predicted, written before the case was run.
42 pub expect: String,
43 /// What happened.
44 pub got: String,
45 /// Delivery orders checked.
46 pub orders: usize,
47 /// Bytes rendered in more than one place.
48 pub duplicated: usize,
49 /// Live bytes rendered nowhere at all.
50 pub lost: usize,
51 /// Live bytes held back by a deleted file.
52 pub withheld: usize,
53 /// Everything the renderer noticed.
54 pub flags: MFlags,
55}
56
57impl MCaseOut {
58 /// Whether the case met its stated prediction.
59 pub fn met(&self) -> bool {
60 self.expect == self.got
61 }
62
63 /// Whether conservation held: nothing rendered twice, nothing lost.
64 pub fn conserved(&self) -> bool {
65 self.duplicated == 0 && self.lost == 0
66 }
67}
68
69/// Applies an operation set in every permutation when the set is small, or in a
70/// handful of rotations when it is not, and checks that every order renders the
71/// same bytes *and* raises the same flags.
72pub fn converge(ident: Identity, ops: &[MOp])
73 -> Outcome<(RepoRender, usize)>
74{
75 let n = ops.len();
76 let mut orders: Vec<Vec<usize>> = Vec::new();
77 if n <= 8 {
78 let mut idx: Vec<usize> = (0..n).collect();
79 permute(&mut idx, 0, &mut orders);
80 } else {
81 // Every rotation, the reverse, and a fixed thousand shuffles, since
82 // enumerating nine factorial orders buys nothing over sampling them.
83 for k in 0..n {
84 orders.push((0..n).map(|i| (i + k) % n).collect());
85 }
86 orders.push((0..n).rev().collect());
87 let mut rng = Rng::new(0x0_5EED_u64.wrapping_add(n as u64));
88 for _ in 0..1000 {
89 let mut idx: Vec<usize> = (0..n).collect();
90 rng.shuffle(&mut idx);
91 orders.push(idx);
92 }
93 }
94 let mut first: Option<RepoRender> = None;
95 for ord in &orders {
96 let mut repo = Repo::new(ident);
97 for i in ord {
98 repo.apply(ops[*i].clone());
99 }
100 let r = res!(repo.render());
101 match &first {
102 None => first = Some(r),
103 Some(f) => {
104 if f.listing() != r.listing() {
105 return Err(err!(
106 "Delivery order changed the render:\n {}\n {}",
107 f.listing(), r.listing(); Mismatch, Data));
108 }
109 if summary(&f.flags) != summary(&r.flags) {
110 return Err(err!(
111 "Delivery order changed the flags:\n {}\n {}",
112 summary(&f.flags), summary(&r.flags); Mismatch, Data));
113 }
114 },
115 }
116 }
117 match first {
118 Some(f) => Ok((f, orders.len())),
119 None => Err(err!("No delivery order was tried."; Bug)),
120 }
121}
122
123/// A one-line rendering of the flags, for comparison and for reports.
124pub fn summary(f: &MFlags) -> String {
125 fmt!(
126 "torn={:?} demoted={:?} off_file={:?} dropped={:?} dup={} orphan={:?} clash={:?}",
127 f.torn.iter().map(|i| i.to_string()).collect::<Vec<_>>(),
128 f.demoted.iter().map(|(o, s)| fmt!("{}+{}", o, s)).collect::<Vec<_>>(),
129 f.off_file.iter().map(|(o, s)| fmt!("{}+{}", o, s)).collect::<Vec<_>>(),
130 f.dropped.iter().map(|(o, s)| fmt!("{}+{}", o, s)).collect::<Vec<_>>(),
131 f.duplicated,
132 f.orphan.iter().map(|(o, s)| fmt!("{}+{}", o, s)).collect::<Vec<_>>(),
133 f.path_clash.iter()
134 .map(|(p, ids)| fmt!("{}:{}", String::from_utf8_lossy(p), ids.len()))
135 .collect::<Vec<_>>(),
136 )
137}
138
139/// Generates every permutation of `idx`.
140fn permute(idx: &mut Vec<usize>, k: usize, out: &mut Vec<Vec<usize>>) {
141 if k == idx.len() {
142 out.push(idx.clone());
143 return;
144 }
145 for i in k..idx.len() {
146 idx.swap(k, i);
147 permute(idx, k + 1, out);
148 idx.swap(k, i);
149 }
150}
151
152/// Creates the named files with the given contents on replica zero, then hands
153/// out `n` further replicas that have seen all of it.
154fn stage(ident: Identity, files: &[(&[u8], &[u8])], n: u32)
155 -> Outcome<(Vec<MRep>, Vec<MOp>, Vec<FileId>)>
156{
157 let mut origin = MRep::new(0, ident);
158 let mut ops: Vec<MOp> = Vec::new();
159 let mut ids: Vec<FileId> = Vec::new();
160 for (path, text) in files {
161 let (op, id) = res!(origin.create(path));
162 ops.push(op);
163 ids.push(id);
164 if !text.is_empty() {
165 ops.push(res!(origin.insert(id, 0, text)));
166 }
167 }
168 let mut reps: Vec<MRep> = Vec::new();
169 for i in 1..=n {
170 let mut r = MRep::new(i, ident);
171 for op in &ops {
172 r.recv(op.clone());
173 }
174 reps.push(r);
175 }
176 Ok((reps, ops, ids))
177}
178
179/// Builds a case result from an operation set and a prediction.
180fn run(
181 name: &'static str,
182 expect: &str,
183 ident: Identity,
184 ops: Vec<MOp>,
185 whole: bool,
186)
187 -> Outcome<MCaseOut>
188{
189 let (r, orders) = res!(converge(ident, &ops));
190 let got = if whole {
191 r.listing()
192 } else {
193 match r.live().first() {
194 Some(f) => f.text(),
195 None => String::new(),
196 }
197 };
198 Ok(MCaseOut {
199 name,
200 ident,
201 expect: expect.to_string(),
202 got,
203 orders,
204 duplicated: r.flags.duplicated,
205 lost: r.stats.lost,
206 withheld: r.stats.withheld,
207 flags: r.flags,
208 })
209}
210
211/// Every file-identity case, under one identity rule.
212pub fn all(ident: Identity) -> Outcome<Vec<MCaseOut>> {
213 Ok(vec![
214 res!(case_cross_file_move_with_edit(ident)),
215 res!(case_cross_file_move_at_destination(ident)),
216 res!(case_same_path_twice(ident)),
217 res!(case_delete_after_move_out(ident)),
218 res!(case_content_delete_after_move_out(ident)),
219 res!(case_cross_file_cycle(ident)),
220 res!(case_move_out_races_delete(ident)),
221 res!(case_splice_races_rename(ident)),
222 res!(case_three_file_cycle(ident)),
223 res!(case_move_into_a_deleted_file(ident)),
224 res!(case_chained_cross_file_move(ident)),
225 ])
226}
227
228/// The headline claim of design note section 4.8: a concurrent edit inside a
229/// range that moves *between files* follows it, for exactly the reason an
230/// in-file one does.
231pub fn case_cross_file_move_with_edit(ident: Identity) -> Outcome<MCaseOut> {
232 let (mut reps, mut ops, ids) = res!(stage(
233 ident, &[(b"a.txt", LIST), (b"b.txt", b"HEADER\n")], 2));
234 let (a, b) = (ids[0], ids[1]);
235 let (r1, r2) = reps.split_at_mut(1);
236 // Replica 1 moves "- Milk\n" out of a.txt and onto the end of b.txt.
237 ops.push(res!(r1[0].move_across(a, 7, 7, b, 7)));
238 // Replica 2 concurrently turns "Milk" into "Soy milk", in a.txt.
239 ops.push(res!(r2[0].replace(a, 9, 1, b"Soy m")));
240 let expect = match ident {
241 // The edit follows the content into the other file.
242 Identity::Derived => "a.txt=\"- Eggs\\n- Cheese\\n\" b.txt=\"HEADER\\n- Soy milk\\n\"",
243 // The edit's anchor names content that has left a.txt, and a recorded
244 // identity cannot follow it out, so the insertion stays behind and the
245 // word is split across two files.
246 Identity::Recorded => "a.txt=\"- Eggs\\nSoy m- Cheese\\n\" b.txt=\"HEADER\\n- ilk\\n\"",
247 // A per-file claim register never saw the move, so a.txt still renders
248 // the bytes b.txt has taken: six of them exist twice.
249 Identity::RecordedLocal =>
250 "a.txt=\"- Eggs\\n- Soy milk\\n- Cheese\\n\" b.txt=\"HEADER\\n- ilk\\n\"",
251 };
252 run("Cross-file move with a concurrent edit inside it", expect, ident, ops, true)
253}
254
255/// A cross-file move racing an in-file insertion at the same destination gap.
256pub fn case_cross_file_move_at_destination(ident: Identity) -> Outcome<MCaseOut> {
257 let (mut reps, mut ops, ids) = res!(stage(
258 ident, &[(b"a.txt", LIST), (b"b.txt", b"HEADER\n")], 2));
259 let (a, b) = (ids[0], ids[1]);
260 let (r1, r2) = reps.split_at_mut(1);
261 // Replica 1 moves "- Milk\n" to the start of b.txt.
262 ops.push(res!(r1[0].move_across(a, 7, 7, b, 0)));
263 // Replica 2 concurrently types an X at the start of b.txt.
264 ops.push(res!(r2[0].insert(b, 0, b"X")));
265 let expect = match ident {
266 Identity::RecordedLocal =>
267 "a.txt=\"- Eggs\\n- Milk\\n- Cheese\\n\" b.txt=\"- Milk\\nXHEADER\\n\"",
268 _ => "a.txt=\"- Eggs\\n- Cheese\\n\" b.txt=\"- Milk\\nXHEADER\\n\"",
269 };
270 run("Cross-file move racing an edit at the destination", expect, ident, ops, true)
271}
272
273/// Two branches independently create the same path and splice into it.
274///
275/// The CLI's walk decides this by order and one of the two files renders
276/// nowhere. Both candidates here record the association instead, so both files
277/// exist, both keep their bytes, and the clash is a naming question at
278/// materialisation time.
279pub fn case_same_path_twice(ident: Identity) -> Outcome<MCaseOut> {
280 let mut r1 = MRep::new(1, ident);
281 let mut r2 = MRep::new(2, ident);
282 let (c1, f1) = res!(r1.create(b"notes.md"));
283 let s1 = res!(r1.insert(f1, 0, b"one"));
284 let (c2, f2) = res!(r2.create(b"notes.md"));
285 let s2 = res!(r2.insert(f2, 0, b"two"));
286 run(
287 "Two branches create one path",
288 "notes.md=\"two\" notes.md~1:1=\"one\"",
289 ident,
290 vec![c1, s1, c2, s2],
291 true,
292 )
293}
294
295/// A file deleted just after content moved out of it. The bytes that left must
296/// survive; the bytes that stayed must not be rendered anywhere.
297pub fn case_delete_after_move_out(ident: Identity) -> Outcome<MCaseOut> {
298 let (mut reps, mut ops, ids) = res!(stage(
299 ident, &[(b"a.txt", b"keep\nmove\n"), (b"b.txt", b"")], 1));
300 let (a, b) = (ids[0], ids[1]);
301 ops.push(res!(reps[0].move_across(a, 5, 5, b, 0)));
302 ops.push(res!(reps[0].remove(a)));
303 run(
304 "Delete of a file whose content moved out",
305 "b.txt=\"move\\n\"",
306 ident,
307 ops,
308 true,
309 )
310}
311
312/// The same, with the deletion expressed the way it must not be: as a splice
313/// removing everything the file held.
314///
315/// This is design note section 4.8's second cost stated as a test. A tombstone
316/// is repository-global and follows the content, so a delete that kills bytes
317/// rather than retiring a file destroys what has just moved out of it.
318pub fn case_content_delete_after_move_out(ident: Identity) -> Outcome<MCaseOut> {
319 let (mut reps, mut ops, ids) = res!(stage(
320 ident, &[(b"a.txt", b"keep\nmove\n"), (b"b.txt", b"")], 2));
321 let (a, b) = (ids[0], ids[1]);
322 let (r1, r2) = reps.split_at_mut(1);
323 ops.push(res!(r1[0].move_across(a, 5, 5, b, 0)));
324 // Replica 2 empties a.txt by content, concurrently.
325 ops.push(res!(r2[0].delete(a, 0, 10)));
326 run(
327 "A content delete of a file whose content moved out",
328 "a.txt=\"\" b.txt=\"\"",
329 ident,
330 ops,
331 true,
332 )
333}
334
335/// Design note section 4.8's named hazard: two agents reorganising two files at
336/// once, each moving one file's contents into the other.
337pub fn case_cross_file_cycle(ident: Identity) -> Outcome<MCaseOut> {
338 let (mut reps, mut ops, ids) = res!(stage(
339 ident, &[(b"a.txt", b"abc\n"), (b"b.txt", b"xyz\n")], 2));
340 let (a, b) = (ids[0], ids[1]);
341 let (r1, r2) = reps.split_at_mut(1);
342 // Replica 1 moves the whole of a.txt into b.txt, after its first byte.
343 ops.push(res!(r1[0].move_across(a, 0, 4, b, 1)));
344 // Replica 2 concurrently moves the whole of b.txt into a.txt, after its
345 // first byte.
346 ops.push(res!(r2[0].move_across(b, 0, 4, a, 1)));
347 let expect = match ident {
348 // The anchor graph has a cycle across the two files. Section 5.4
349 // demotes the lower-op-order move to where its anchor content was
350 // created, which is inside b.txt, and the higher-op-order move then
351 // follows its anchor content there too: a.txt is emptied.
352 Identity::Derived => "a.txt=\"\" b.txt=\"axyz\\nbc\\n\"",
353 // A recorded identity cannot let an anchor leave its file, so there is
354 // no cycle to break: each move lands where the file it names says, and
355 // the two blocks swap files cleanly.
356 Identity::Recorded => "a.txt=\"xyz\\n\" b.txt=\"abc\\n\"",
357 // With a per-file register neither file learns that its content was
358 // claimed away, so both files hold both blocks.
359 Identity::RecordedLocal => "a.txt=\"axyz\\nbc\\n\" b.txt=\"xabc\\nyz\\n\"",
360 };
361 run("A cross-file move cycle", expect, ident, ops, true)
362}
363
364/// A move out of a file racing that file's deletion.
365pub fn case_move_out_races_delete(ident: Identity) -> Outcome<MCaseOut> {
366 let (mut reps, mut ops, ids) = res!(stage(
367 ident, &[(b"a.txt", b"keep\nmove\n"), (b"b.txt", b"")], 2));
368 let (a, b) = (ids[0], ids[1]);
369 let (r1, r2) = reps.split_at_mut(1);
370 ops.push(res!(r1[0].move_across(a, 5, 5, b, 0)));
371 ops.push(res!(r2[0].remove(a)));
372 run(
373 "A move out of a file racing that file's delete",
374 "b.txt=\"move\\n\"",
375 ident,
376 ops,
377 true,
378 )
379}
380
381/// An insertion into an empty file racing that file's rename.
382///
383/// Neither candidate has any difficulty with it, and it is here because the
384/// vocabulary it replaces does: a splice that names no existing content can
385/// only be routed by the path it recorded, and the rename has just made that
386/// path wrong.
387pub fn case_splice_races_rename(ident: Identity) -> Outcome<MCaseOut> {
388 let (mut reps, mut ops, ids) = res!(stage(ident, &[(b"a.txt", b"")], 2));
389 let a = ids[0];
390 let (r1, r2) = reps.split_at_mut(1);
391 ops.push(res!(r1[0].rename(a, b"b.txt")));
392 ops.push(res!(r2[0].insert(a, 0, b"hi")));
393 run("An insertion racing the rename of its file", "b.txt=\"hi\"", ident, ops, true)
394}
395
396/// Three agents reorganising three files at once, each emptying one into the
397/// next: the cycle of section 5.4 at length three, and across files.
398pub fn case_three_file_cycle(ident: Identity) -> Outcome<MCaseOut> {
399 let (mut reps, mut ops, ids) = res!(stage(
400 ident,
401 &[(b"a.txt", b"abc\n"), (b"b.txt", b"xyz\n"), (b"c.txt", b"123\n")],
402 3,
403 ));
404 let (a, b, c) = (ids[0], ids[1], ids[2]);
405 ops.push(res!(reps[0].move_across(a, 0, 4, b, 1)));
406 ops.push(res!(reps[1].move_across(b, 0, 4, c, 1)));
407 ops.push(res!(reps[2].move_across(c, 0, 4, a, 1)));
408 let expect = match ident {
409 // One demotion breaks the three-cycle, and the other two moves follow
410 // their anchor content into the same file.
411 Identity::Derived =>
412 "a.txt=\"\" b.txt=\"a1xyz\\n23\\nbc\\n\" c.txt=\"\"",
413 // No anchor may leave its file, so the three blocks rotate.
414 Identity::Recorded =>
415 "a.txt=\"123\\n\" b.txt=\"abc\\n\" c.txt=\"xyz\\n\"",
416 // Every file keeps what it had and gains what it was given.
417 Identity::RecordedLocal =>
418 "a.txt=\"a123\\nbc\\n\" b.txt=\"xabc\\nyz\\n\" c.txt=\"1xyz\\n23\\n\"",
419 };
420 run("A three-file move cycle", expect, ident, ops, true)
421}
422
423/// Content moved into a file that is concurrently deleted.
424///
425/// The bytes are not lost -- they are owned by a slot in the deleted file and
426/// the log still holds them -- but nothing renders them, which is a hazard the
427/// design note does not currently name.
428pub fn case_move_into_a_deleted_file(ident: Identity) -> Outcome<MCaseOut> {
429 let (mut reps, mut ops, ids) = res!(stage(
430 ident, &[(b"a.txt", b"keep\nmove\n"), (b"b.txt", b"")], 2));
431 let (a, b) = (ids[0], ids[1]);
432 let (r1, r2) = reps.split_at_mut(1);
433 ops.push(res!(r1[0].move_across(a, 5, 5, b, 0)));
434 ops.push(res!(r2[0].remove(b)));
435 let expect = match ident {
436 Identity::RecordedLocal => "a.txt=\"keep\\nmove\\n\"",
437 _ => "a.txt=\"keep\\n\"",
438 };
439 run("A move into a file deleted concurrently", expect, ident, ops, true)
440}
441
442/// A range moved from one file to a second and then to a third, with an edit
443/// made concurrently with the first move. The edit has to arrive two files
444/// away from where its author was looking.
445pub fn case_chained_cross_file_move(ident: Identity) -> Outcome<MCaseOut> {
446 let (mut reps, mut ops, ids) = res!(stage(
447 ident,
448 &[(b"a.txt", LIST), (b"b.txt", b"B\n"), (b"c.txt", b"C\n")],
449 2,
450 ));
451 let (a, b, c) = (ids[0], ids[1], ids[2]);
452 let (r1, r2) = reps.split_at_mut(1);
453 ops.push(res!(r1[0].move_across(a, 7, 7, b, 2)));
454 ops.push(res!(r1[0].move_across(b, 2, 7, c, 2)));
455 ops.push(res!(r2[0].replace(a, 9, 1, b"Soy m")));
456 let expect = match ident {
457 Identity::Derived =>
458 "a.txt=\"- Eggs\\n- Cheese\\n\" b.txt=\"B\\n\" c.txt=\"C\\n- Soy milk\\n\"",
459 Identity::Recorded =>
460 "a.txt=\"- Eggs\\nSoy m- Cheese\\n\" b.txt=\"B\\n\" c.txt=\"C\\n- ilk\\n\"",
461 Identity::RecordedLocal =>
462 "a.txt=\"- Eggs\\n- Soy milk\\n- Cheese\\n\" b.txt=\"B\\n\" \
463 c.txt=\"C\\n- ilk\\n\"",
464 };
465 run("A cross-file move chained through a third file", expect, ident, ops, true)
466}
467
468
469/// A move whose source names a file's origin anchor.
470///
471/// No frontend can author this: the origin anchor is born dead and never
472/// appears in a render, so nothing a user points at can name it. It is here
473/// because a wire format has to say what a receiver does with an operation
474/// nobody meant to send, and because what it does turns out to be coherent:
475/// the whole of one file lands inside another.
476pub fn case_moving_an_origin_anchor() -> Outcome<MCaseOut> {
477 let ident = Identity::Derived;
478 let (reps, mut ops, ids) = res!(stage(
479 ident, &[(b"a.txt", b"AAA\n"), (b"b.txt", b"BBB\n")], 1));
480 let (a, b) = (ids[0], ids[1]);
481 ops.push(MOp::Move {
482 id: OpId::new(reps[0].repo.max_counter() + 1, 1),
483 file: None,
484 src: vec![res!(ContentRange::new(b, 0, 1))],
485 left: after(ContentId::new(a, 0)),
486 right: None,
487 });
488 run(
489 "A move of a file's origin anchor",
490 "a.txt=\"AAA\\nBBB\\n\" b.txt=\"\"",
491 ident,
492 ops,
493 true,
494 )
495}
496
497
498/// The stage-one cases again, in a repository that has a file in it.
499///
500/// File identity must not perturb single-file semantics, and the instrument for
501/// saying so is the ten expectations stage one already settled: every one of
502/// them must come out the same through the multi-file engine.
503pub fn regression(ident: Identity) -> Outcome<Vec<MCaseOut>> {
504 Ok(vec![
505 res!(reg_fig4(ident)),
506 res!(reg_identical_move(ident)),
507 res!(reg_overlapping_move(ident)),
508 res!(reg_nested_destinations(ident)),
509 res!(reg_edit_inside(ident)),
510 res!(reg_three_way_insert(ident)),
511 res!(reg_boundary_edits(ident)),
512 res!(reg_move_versus_delete(ident)),
513 res!(reg_split_boundary_disagreement(ident)),
514 res!(reg_backward_interleaving(ident)),
515 ])
516}
517
518/// Kleppmann Figure 4 expecting Figure 5.
519fn reg_fig4(ident: Identity) -> Outcome<MCaseOut> {
520 let (mut reps, mut ops, ids) = res!(stage(ident, &[(b"f", LIST)], 2));
521 let f = ids[0];
522 let (r1, r2) = reps.split_at_mut(1);
523 ops.push(res!(r1[0].move_within(f, 7, 7, 0)));
524 ops.push(res!(r2[0].replace(f, 9, 1, b"Soy m")));
525 run("Kleppmann Fig 4 -> Fig 5", "- Soy milk\n- Eggs\n- Cheese\n", ident, ops, false)
526}
527
528/// Two replicas move the identical range to different destinations.
529fn reg_identical_move(ident: Identity) -> Outcome<MCaseOut> {
530 let (mut reps, mut ops, ids) = res!(stage(ident, &[(b"f", LIST)], 2));
531 let f = ids[0];
532 let (r1, r2) = reps.split_at_mut(1);
533 ops.push(res!(r1[0].move_within(f, 7, 7, 0)));
534 ops.push(res!(r2[0].move_within(f, 7, 7, 23)));
535 run("Concurrent identical-range move", "- Eggs\n- Cheese\n- Milk\n", ident, ops, false)
536}
537
538/// Two replicas move partially overlapping ranges.
539fn reg_overlapping_move(ident: Identity) -> Outcome<MCaseOut> {
540 let (mut reps, mut ops, ids) = res!(stage(ident, &[(b"f", ALPHA)], 2));
541 let f = ids[0];
542 let (r1, r2) = reps.split_at_mut(1);
543 ops.push(res!(r1[0].move_within(f, 0, 10, 20)));
544 ops.push(res!(r2[0].move_within(f, 5, 10, 0)));
545 run("Overlapping-range concurrent moves", "FGHIJ56789ABCDE01234", ident, ops, false)
546}
547
548/// Two moves whose destinations sit inside each other's source ranges.
549fn reg_nested_destinations(ident: Identity) -> Outcome<MCaseOut> {
550 let (mut reps, mut ops, ids) = res!(stage(ident, &[(b"f", ALPHA)], 2));
551 let f = ids[0];
552 let (r1, r2) = reps.split_at_mut(1);
553 ops.push(res!(r1[0].move_within(f, 0, 5, 12)));
554 ops.push(res!(r2[0].move_within(f, 10, 5, 2)));
555 run("Mutually nested move destinations", "5678901ABCDE234FGHIJ", ident, ops, false)
556}
557
558/// A move concurrent with an insertion strictly inside the moved range.
559fn reg_edit_inside(ident: Identity) -> Outcome<MCaseOut> {
560 let (mut reps, mut ops, ids) = res!(stage(ident, &[(b"f", LIST)], 2));
561 let f = ids[0];
562 let (r1, r2) = reps.split_at_mut(1);
563 ops.push(res!(r1[0].move_within(f, 7, 7, 0)));
564 ops.push(res!(r2[0].insert(f, 11, b"!")));
565 run("Edit inside a concurrently moved range", "- Mi!lk\n- Eggs\n- Cheese\n", ident, ops, false)
566}
567
568/// Three replicas insert runs at the same point.
569fn reg_three_way_insert(ident: Identity) -> Outcome<MCaseOut> {
570 let (mut reps, mut ops, ids) = res!(stage(ident, &[(b"f", b"AB")], 3));
571 let f = ids[0];
572 for (i, r) in reps.iter_mut().enumerate() {
573 let bytes = match i {
574 0 => b"xxx".to_vec(),
575 1 => b"yyy".to_vec(),
576 _ => b"zzz".to_vec(),
577 };
578 ops.push(res!(r.insert(f, 1, &bytes)));
579 }
580 run("Three concurrent inserts at one point", "AxxxyyyzzzB", ident, ops, false)
581}
582
583/// Insertions abutting the start and the end of a concurrently moved range.
584fn reg_boundary_edits(ident: Identity) -> Outcome<MCaseOut> {
585 let (mut reps, mut ops, ids) = res!(stage(ident, &[(b"f", LIST)], 2));
586 let f = ids[0];
587 let (r1, r2) = reps.split_at_mut(1);
588 ops.push(res!(r1[0].move_within(f, 7, 7, 0)));
589 let before = res!(r2[0].insert(f, 7, b"<"));
590 ops.push(before);
591 ops.push(res!(r2[0].insert(f, 15, b">")));
592 run("Edits abutting a moved range", "- Milk\n>- Eggs\n<- Cheese\n", ident, ops, false)
593}
594
595/// A move concurrent with a deletion inside the moved range.
596fn reg_move_versus_delete(ident: Identity) -> Outcome<MCaseOut> {
597 let (mut reps, mut ops, ids) = res!(stage(ident, &[(b"f", LIST)], 2));
598 let f = ids[0];
599 let (r1, r2) = reps.split_at_mut(1);
600 ops.push(res!(r1[0].move_within(f, 7, 7, 0)));
601 ops.push(res!(r2[0].delete(f, 9, 4)));
602 run("Move versus delete inside the range", "- \n- Eggs\n- Cheese\n", ident, ops, false)
603}
604
605/// Two replicas split the sequence at different boundaries before moving.
606fn reg_split_boundary_disagreement(ident: Identity) -> Outcome<MCaseOut> {
607 let (mut reps, mut ops, ids) = res!(stage(ident, &[(b"f", ALPHA)], 2));
608 let f = ids[0];
609 let (r1, r2) = reps.split_at_mut(1);
610 ops.push(res!(r1[0].move_within(f, 0, 10, 20)));
611 ops.push(res!(r2[0].move_within(f, 0, 6, 20)));
612 run("Different split boundaries before move", "ABCDEFGHIJ6789012345", ident, ops, false)
613}
614
615/// Fugue's own Figure 2, at run granularity.
616fn reg_backward_interleaving(ident: Identity) -> Outcome<MCaseOut> {
617 let (mut reps, mut ops, ids) = res!(stage(ident, &[(b"f", b"\n")], 2));
618 let f = ids[0];
619 let (r1, r2) = reps.split_at_mut(1);
620 ops.push(res!(r1[0].insert(f, 1, b"section A\n")));
621 ops.push(res!(r1[0].insert(f, 1, b"HEADING A\n")));
622 ops.push(res!(r2[0].insert(f, 1, b"section B\n")));
623 ops.push(res!(r2[0].insert(f, 1, b"HEADING B\n")));
624 run(
625 "Fugue Fig 2, backward interleaving",
626 "\nHEADING A\nsection A\nHEADING B\nsection B\n",
627 ident,
628 ops,
629 false,
630 )
631}