Oregami
Repositories/oxedyne/ore

oxedyne/ore/oracle/src/cases.rs

10.1 KiB, 1 run

created by r2848102244:71, 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 one: the named adversarial cases, hand-written, each with the answer
2//! the literature or the design note prescribes.
3
4use crate::doc::{
5 Bind,
6 Doc,
7 Flags,
8 Mode,
9 Render,
10};
11use crate::op::Op;
12use crate::replica::Replica;
13
14use oxedyne_fe2o3_core::prelude::*;
15
16/// The shopping list of Kleppmann's Figure 4, with ASCII bullets so that byte
17/// offsets and character offsets coincide.
18pub const LIST: &[u8] = b"- Eggs\n- Milk\n- Cheese\n";
19
20/// A twenty-byte alphabet, for range arithmetic that is easy to read.
21pub const ALPHA: &[u8] = b"0123456789ABCDEFGHIJ";
22
23/// The result of running one adversarial case in one mode.
24#[derive(Clone, Debug)]
25pub struct CaseOut {
26 /// Case name.
27 pub name: &'static str,
28 /// What the literature or the design note says should happen.
29 pub expect: String,
30 /// What happened.
31 pub text: String,
32 /// Flags the renderer raised.
33 pub flags: Flags,
34 /// Number of delivery orders checked.
35 pub orders: usize,
36}
37
38impl CaseOut {
39 /// Whether the case met its stated expectation.
40 pub fn met(&self) -> bool {
41 self.expect == self.text
42 }
43}
44
45/// Applies an operation set in every permutation when the set is small, or in
46/// a handful of rotations when it is not, and checks that every order renders
47/// the same bytes.
48pub fn converge(mode: Mode, bind: Bind, ops: &[Op]) -> Outcome<(Render, usize)> {
49 let mut orders: Vec<Vec<usize>> = Vec::new();
50 let n = ops.len();
51 if n <= 6 {
52 let mut idx: Vec<usize> = (0..n).collect();
53 permute(&mut idx, 0, &mut orders);
54 } else {
55 for k in 0..n {
56 orders.push((0..n).map(|i| (i + k) % n).collect());
57 }
58 orders.push((0..n).rev().collect());
59 }
60 let mut first: Option<Render> = None;
61 for ord in &orders {
62 let mut d = Doc::with_bind(mode, bind);
63 for i in ord {
64 d.apply(ops[*i].clone());
65 }
66 let r = res!(d.render());
67 match &first {
68 None => first = Some(r),
69 Some(f) => {
70 if f.bytes != r.bytes {
71 return Err(err!(
72 "Delivery order changed the render: {:?} against {:?}.",
73 String::from_utf8_lossy(&f.bytes),
74 String::from_utf8_lossy(&r.bytes); Mismatch, Data));
75 }
76 },
77 }
78 }
79 let f = match first {
80 Some(f) => f,
81 None => return Err(err!("No delivery order was tried."; Bug)),
82 };
83 Ok((f, orders.len()))
84}
85
86/// Generates every permutation of `idx`.
87fn permute(idx: &mut Vec<usize>, k: usize, out: &mut Vec<Vec<usize>>) {
88 if k == idx.len() {
89 out.push(idx.clone());
90 return;
91 }
92 for i in k..idx.len() {
93 idx.swap(k, i);
94 permute(idx, k + 1, out);
95 idx.swap(k, i);
96 }
97}
98
99/// Seeds `n` replicas with one splice carrying the whole initial text.
100fn seed(mode: Mode, bind: Bind, text: &[u8], n: u32) -> Outcome<(Vec<Replica>, Op)> {
101 let mut origin = Replica::with_bind(0, mode, bind);
102 let op = res!(origin.insert(0, text));
103 let mut out = Vec::new();
104 for i in 1..=n {
105 let mut r = Replica::with_bind(i, mode, bind);
106 r.recv(op.clone());
107 out.push(r);
108 }
109 Ok((out, op))
110}
111
112/// Runs every case in the given mode.
113pub fn all(mode: Mode, bind: Bind) -> Outcome<Vec<CaseOut>> {
114 Ok(vec![
115 res!(case_fig4(mode, bind)),
116 res!(case_identical_move(mode, bind)),
117 res!(case_overlapping_move(mode, bind)),
118 res!(case_nested_destinations(mode, bind)),
119 res!(case_edit_inside(mode, bind)),
120 res!(case_three_way_insert(mode, bind)),
121 res!(case_boundary_edits(mode, bind)),
122 res!(case_move_versus_delete(mode, bind)),
123 res!(case_split_boundary_disagreement(mode, bind)),
124 res!(case_backward_interleaving(mode, bind)),
125 ])
126}
127
128/// Builds a case result from an operation set.
129fn run(
130 name: &'static str,
131 expect: &str,
132 mode: Mode,
133 bind: Bind,
134 ops: Vec<Op>,
135)
136 -> Outcome<CaseOut>
137{
138 let (r, orders) = res!(converge(mode, bind, &ops));
139 Ok(CaseOut {
140 name,
141 expect: expect.to_string(),
142 text: r.text(),
143 flags: r.flags,
144 orders,
145 })
146}
147
148/// Kleppmann Figure 4 expecting Figure 5: a move of one list item concurrent
149/// with an edit inside that item.
150pub fn case_fig4(mode: Mode, bind: Bind) -> Outcome<CaseOut> {
151 let (mut reps, seed_op) = res!(seed(mode, bind, LIST, 2));
152 let (b, a) = reps.split_at_mut(1);
153 let a = &mut a[0]; // replica 2
154 let b = &mut b[0]; // replica 1
155 // B moves "- Milk\n", bytes 7..14, to the top.
156 let mv = res!(b.move_range(7, 7, 0));
157 // A concurrently turns "Milk" into "Soy milk".
158 let ed = res!(a.replace(9, 1, b"Soy m"));
159 run(
160 "Kleppmann Fig 4 -> Fig 5",
161 "- Soy milk\n- Eggs\n- Cheese\n",
162 mode,
163 bind,
164 vec![seed_op, mv, ed],
165 )
166}
167
168/// Two replicas move the identical range to different destinations.
169pub fn case_identical_move(mode: Mode, bind: Bind) -> Outcome<CaseOut> {
170 let (mut reps, seed_op) = res!(seed(mode, bind, LIST, 2));
171 let (r1, r2) = reps.split_at_mut(1);
172 let m1 = res!(r1[0].move_range(7, 7, 0)); // replica 1, loses
173 let m2 = res!(r2[0].move_range(7, 7, 23)); // replica 2, wins
174 // Unarbitrated per-element moves reproduce Kleppmann's Figure 2 anomaly,
175 // the duplication that his construction exists to remove.
176 let expect = match mode {
177 Mode::SplitBeforeMoveNaive => "- Milk\n- Eggs\n- Cheese\n- Milk\n",
178 _ => "- Eggs\n- Cheese\n- Milk\n",
179 };
180 run("Concurrent identical-range move", expect, mode, bind, vec![seed_op, m1, m2])
181}
182
183/// Two replicas move partially overlapping ranges.
184pub fn case_overlapping_move(mode: Mode, bind: Bind) -> Outcome<CaseOut> {
185 let (mut reps, seed_op) = res!(seed(mode, bind, ALPHA, 2));
186 let (r1, r2) = reps.split_at_mut(1);
187 let m1 = res!(r1[0].move_range(0, 10, 20)); // replica 1, loses the overlap
188 let m2 = res!(r2[0].move_range(5, 10, 0)); // replica 2, wins the overlap
189 let expect = match mode {
190 Mode::ClaimRegister => "FGHIJ56789ABCDE01234",
191 Mode::SplitBeforeMove => "56789ABCDE01234FGHIJ",
192 Mode::SplitBeforeMoveNaive => "FGHIJ56789ABCDE0123456789",
193 };
194 run("Overlapping-range concurrent moves", expect, mode, bind, vec![seed_op, m1, m2])
195}
196
197/// Two moves whose destinations sit inside each other's source ranges.
198pub fn case_nested_destinations(mode: Mode, bind: Bind) -> Outcome<CaseOut> {
199 let (mut reps, seed_op) = res!(seed(mode, bind, ALPHA, 2));
200 let (r1, r2) = reps.split_at_mut(1);
201 // A moves "01234" into the middle of "ABCDE".
202 let m1 = res!(r1[0].move_range(0, 5, 12));
203 // B moves "ABCDE" into the middle of "01234".
204 let m2 = res!(r2[0].move_range(10, 5, 2));
205 run(
206 "Mutually nested move destinations",
207 "5678901ABCDE234FGHIJ",
208 mode,
209 bind,
210 vec![seed_op, m1, m2],
211 )
212}
213
214/// A move concurrent with an insertion strictly inside the moved range.
215pub fn case_edit_inside(mode: Mode, bind: Bind) -> Outcome<CaseOut> {
216 let (mut reps, seed_op) = res!(seed(mode, bind, LIST, 2));
217 let (r1, r2) = reps.split_at_mut(1);
218 let mv = res!(r1[0].move_range(7, 7, 0));
219 let ed = res!(r2[0].insert(11, b"!"));
220 run(
221 "Edit inside a concurrently moved range",
222 "- Mi!lk\n- Eggs\n- Cheese\n",
223 mode,
224 bind,
225 vec![seed_op, mv, ed],
226 )
227}
228
229/// Three replicas insert runs at the same point.
230pub fn case_three_way_insert(mode: Mode, bind: Bind) -> Outcome<CaseOut> {
231 let (mut reps, seed_op) = res!(seed(mode, bind, b"AB", 3));
232 let mut ops = vec![seed_op];
233 for (i, r) in reps.iter_mut().enumerate() {
234 let run_bytes = match i {
235 0 => b"xxx".to_vec(),
236 1 => b"yyy".to_vec(),
237 _ => b"zzz".to_vec(),
238 };
239 ops.push(res!(r.insert(1, &run_bytes)));
240 }
241 run("Three concurrent inserts at one point", "AxxxyyyzzzB", mode, bind, ops)
242}
243
244/// Insertions immediately before the start and immediately after the end of a
245/// concurrently moved range.
246pub fn case_boundary_edits(mode: Mode, bind: Bind) -> Outcome<CaseOut> {
247 let (mut reps, seed_op) = res!(seed(mode, bind, LIST, 2));
248 let (r1, r2) = reps.split_at_mut(1);
249 let mv = res!(r1[0].move_range(7, 7, 0));
250 let before = res!(r2[0].insert(7, b"<"));
251 r2[0].recv(before.clone());
252 let after = res!(r2[0].insert(15, b">"));
253 run(
254 "Edits abutting a moved range",
255 "- Milk\n>- Eggs\n<- Cheese\n",
256 mode,
257 bind,
258 vec![seed_op, mv, before, after],
259 )
260}
261
262/// A move concurrent with a deletion inside the moved range.
263pub fn case_move_versus_delete(mode: Mode, bind: Bind) -> Outcome<CaseOut> {
264 let (mut reps, seed_op) = res!(seed(mode, bind, LIST, 2));
265 let (r1, r2) = reps.split_at_mut(1);
266 let mv = res!(r1[0].move_range(7, 7, 0));
267 let del = res!(r2[0].delete(9, 4)); // "Milk"
268 run(
269 "Move versus delete inside the range",
270 "- \n- Eggs\n- Cheese\n",
271 mode,
272 bind,
273 vec![seed_op, mv, del],
274 )
275}
276
277/// The field note's own listed risk: two replicas split the sequence at
278/// different boundaries before moving.
279pub fn case_split_boundary_disagreement(mode: Mode, bind: Bind) -> Outcome<CaseOut> {
280 let (mut reps, seed_op) = res!(seed(mode, bind, ALPHA, 2));
281 let (r1, r2) = reps.split_at_mut(1);
282 // A treats "0123456789" as the element and moves it to the end.
283 let m1 = res!(r1[0].move_range(0, 10, 20));
284 // B treats "012345" as the element and moves it to the end.
285 let m2 = res!(r2[0].move_range(0, 6, 20));
286 // Under the claim register, section 5.5 tie-break 1 gives B bytes 0..6 and
287 // leaves A bytes 6..10, so the base slot renders the unclaimed "ABCDEFGHIJ"
288 // and the two move slots, being same-side siblings at the end of the file,
289 // render in op order ascending: A's "6789" then B's "012345". Under
290 // arbitration A does not exist at all.
291 let expect = match mode {
292 Mode::ClaimRegister => "ABCDEFGHIJ6789012345",
293 Mode::SplitBeforeMove => "6789ABCDEFGHIJ012345",
294 Mode::SplitBeforeMoveNaive => "ABCDEFGHIJ0123456789012345",
295 };
296 run("Different split boundaries before move", expect, mode, bind, vec![seed_op, m1, m2])
297}
298
299/// Fugue's own Figure 2: two authors each write a section, then go back and put
300/// a heading above it. Every algorithm except Fugue interleaves here, and this
301/// version runs at run granularity, which is where section 8's risk 2 lives.
302pub fn case_backward_interleaving(mode: Mode, bind: Bind) -> Outcome<CaseOut> {
303 let (mut reps, seed_op) = res!(seed(mode, bind, b"\n", 2));
304 let (r1, r2) = reps.split_at_mut(1);
305 let s1 = res!(r1[0].insert(1, b"section A\n"));
306 r1[0].recv(s1.clone());
307 let h1 = res!(r1[0].insert(1, b"HEADING A\n"));
308 let s2 = res!(r2[0].insert(1, b"section B\n"));
309 r2[0].recv(s2.clone());
310 let h2 = res!(r2[0].insert(1, b"HEADING B\n"));
311 run(
312 "Fugue Fig 2, backward interleaving",
313 "\nHEADING A\nsection A\nHEADING B\nsection B\n",
314 mode,
315 bind,
316 vec![seed_op, s1, h1, s2, h2],
317 )
318}