Oregami
Repositories/oxedyne/fe2o3

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

27.8 KiB, 135 runs

created by r1192329593:77995, 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//! A generated sweep of small histories around twin edits, each run through its
2//! delivery orders and judged by one invariant: **every author's bytes are
3//! rendered where they were written, or their loss is named.**
4//!
5//! Stated as checks on each render:
6//!
7//! - every delivery order renders the same bytes and raises the same flags;
8//! - every byte the operations created is rendered once, or dead (conservation);
9//! - an operation is named by a `Yielded` flag -- an `Overlap` is not enough --
10//! when its insertion is gone and no splice that saw it took it out, when what
11//! it removed still renders, or when it was built on a buried insertion;
12//! - nothing built on a buried insertion renders;
13//! - a `Yielded` names an edit that stands; one through a host names a buried
14//! insertion its edit was built on, and one without names an edit that had not
15//! seen it;
16//! - a byte renders at most once, and a folded copy's never;
17//! - an insertion renders between its origins, wherever they render (asked only of
18//! a history without a move);
19//! - a move landing inside a buried insertion is flagged, and so is each copy a
20//! move took without having seen it, beside the move.
21//!
22//! "Built on" is read off the operations, not the render: a splice is built on an
23//! insertion when any byte it removes is that insertion's, or when both its
24//! origins lie in buried insertions. What is built on a buried insertion is dead
25//! in turn.
26//!
27//! The histories are drawn from a fixed seed: two to four authors over a short
28//! file, a twin edit (a line added alike, a word replaced alike, a line deleted or
29//! rewritten alike, bytes put inside a line alike) on any line, by two authors or
30//! more, possibly inside a region one of them rewrote first and possibly after one
31//! of them made an edit the others did not see, then up to five further steps
32//! drawn from deleting, rewriting or undoing one's own copy, redoing the undo,
33//! replacing a region about the twin, deleting past it, editing beside or inside
34//! it, moving a line, a second twin, a far edit that raises an author's counter,
35//! and syncing one author from another.
36//!
37//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
38//! Anthropic Claude
39
40use crate::id::{
41 OpId,
42 ReplicaId,
43};
44use crate::op::{
45 Header,
46 Op,
47};
48use crate::seq::atom::Atoms;
49use crate::seq::claim::Dead;
50use crate::seq::render::{
51 Flag,
52 Rendered,
53 Repo,
54};
55use crate::seq::twin::{
56 Cause,
57 Twins,
58};
59use crate::seq::Sequence;
60
61use oxedyne_fe2o3_core::prelude::*;
62
63use std::collections::{
64 BTreeMap,
65 BTreeSet,
66};
67use std::time::Instant;
68
69
70const BASE: &str = "head\none decimal two\nthree\nfour\ntail\n";
71const SEED: u64 = 0x5eed_0f_7a1e_2026; // fixed: the sweep is the same on every run
72const HISTORIES: usize = 2400; // distinct histories drawn
73const EVERY: usize = 5; // every order up to this many operations
74
75
76#[derive(Clone, Copy, Debug, Eq, PartialEq)]
77enum Act {
78 Add, // a line after the target line
79 Word, // the target line's first word, replaced
80 Delete, // the target line
81 Rewrite, // the target line, as another
82 Region, // the target line and the next, replaced by two lines
83 Spill, // the target line and the head of the next, deleted
84 Undo, // the author's last splice, inverted
85 Bump, // a line at the end, which only raises the author's counter
86 Inside, // a few bytes inside the target line, after its first byte
87 Beside, // a few bytes after the target line's first word, before the rest
88 Move, // the target line, moved below the line after next
89 Twin, // a second twin: two authors, synced, make one edit alike
90}
91
92const TWIN_ACTS: [Act; 5] = [Act::Add, Act::Word, Act::Delete, Act::Rewrite, Act::Inside];
93const SOLO_ACTS: [Act; 13] = [
94 Act::Delete, Act::Rewrite, Act::Undo, Act::Undo, Act::Region, Act::Spill,
95 Act::Add, Act::Word, Act::Bump, Act::Inside, Act::Beside, Act::Move, Act::Twin,
96];
97
98
99/// A splice of the author's own, and what inverts it.
100struct Undo {
101 id: OpId,
102 len: usize, // bytes it inserted
103 removed: Vec<u8>, // bytes it took out
104 line: usize, // where a pure deletion is put back
105}
106
107struct Author {
108 seq: Sequence,
109 undo: Vec<Undo>,
110}
111
112struct History {
113 file: OpId,
114 ops: Vec<(Header, Op)>, // as authored, the seed's two first
115 authors: Vec<Author>, // replica i + 1 at index i
116 label: BTreeMap<OpId, String>, // what each operation was, for the report
117 script: Vec<String>,
118}
119
120struct Rng(u64);
121
122impl Rng {
123 fn below(&mut self, n: usize) -> usize {
124 self.0 = self.0
125 .wrapping_mul(6_364_136_223_846_793_005)
126 .wrapping_add(1_442_695_040_888_963_407);
127 ((self.0 >> 33) as usize) % n
128 }
129}
130
131/// Each line as its start and length, the line ending included.
132fn lines(text: &[u8]) -> Vec<(usize, usize)> {
133 let mut out = Vec::new();
134 let mut s = 0;
135 for (i, b) in text.iter().enumerate() {
136 if *b == b'\n' {
137 out.push((s, i + 1 - s));
138 s = i + 1;
139 }
140 }
141 if s < text.len() {
142 out.push((s, text.len() - s));
143 }
144 out
145}
146
147fn author_on(seq: &mut Sequence, rid: u64, op: Op)
148 -> Outcome<(Header, Op)>
149{
150 let seen = seq.iter().map(|(id, _)| id.counter).max().unwrap_or(0);
151 let head = res!(Header::new(OpId::new(ReplicaId::new(rid), seen + 1), seq.causality().heads()));
152 res!(seq.apply(head.clone(), op.clone()));
153 Ok((head, op))
154}
155
156fn view_of(seq: &Sequence, file: OpId)
157 -> Outcome<(Repo, Rendered)>
158{
159 let repo = res!(seq.render());
160 let view = match repo.file(file) {
161 Some(f) => f.clone(),
162 None => return Err(err!("The view holds no file {}.", file; Test, Missing)),
163 };
164 Ok((repo, view))
165}
166
167impl History {
168
169 fn new(n: u64)
170 -> Outcome<Self>
171 {
172 let mut origin = Sequence::new();
173 let create = res!(author_on(&mut origin, 0, Op::FileCreate { path: b"f.rs".to_vec() }));
174 let file = create.0.id();
175 let (_, view) = res!(view_of(&origin, file));
176 let write = res!(author_on(&mut origin, 0, res!(view.splice(0, 0, BASE.as_bytes().to_vec(), None))));
177 let ops = vec![create, write];
178 let mut authors = Vec::new();
179 for _ in 0..n {
180 let mut seq = Sequence::new();
181 for (h, op) in &ops {
182 res!(seq.apply(h.clone(), op.clone()));
183 }
184 authors.push(Author { seq, undo: Vec::new() });
185 }
186 Ok(Self { file, ops, authors, label: BTreeMap::new(), script: Vec::new() })
187 }
188
189 fn generated(&self) -> usize {
190 self.ops.len() - 2
191 }
192
193 /// Replica `to` receives everything replica `from` holds.
194 fn sync(&mut self, to: usize, from: usize)
195 -> Outcome<()>
196 {
197 for (h, op) in &self.ops {
198 let id = h.id();
199 if self.authors[from].seq.contains(&id) && !self.authors[to].seq.contains(&id) {
200 res!(self.authors[to].seq.apply(h.clone(), op.clone()));
201 }
202 }
203 Ok(())
204 }
205
206 /// One edit by replica `a + 1` on its own view, or `None` where it does not
207 /// apply there.
208 fn act(&mut self, a: usize, act: Act, line: usize, tag: &str)
209 -> Outcome<Option<OpId>>
210 {
211 let (repo, view) = res!(view_of(&self.authors[a].seq, self.file));
212 let text = view.bytes().to_vec();
213 let ls = lines(&text);
214 if ls.is_empty() && act != Act::Bump && act != Act::Undo {
215 return Ok(None);
216 }
217 let k = if ls.is_empty() { 0 } else { line % ls.len() };
218 let (s, l) = ls.get(k).copied().unwrap_or((0, 0));
219 let body = if l > 0 && text[s + l - 1] == b'\n' { l - 1 } else { l };
220 let next = ls.get(k + 1).map(|(_, n)| *n);
221 if act == Act::Move {
222 // Not undone: the undo stack holds splices.
223 let to = ls.get(k + 2).map(|(s, n)| s + n).unwrap_or(text.len());
224 if l == 0 || to <= s + l {
225 return Ok(None);
226 }
227 let op = res!(view.move_range(s, l, to, None));
228 let (h, op) = res!(author_on(&mut self.authors[a].seq, a as u64 + 1, op));
229 let id = h.id();
230 self.ops.push((h, op));
231 return Ok(Some(id));
232 }
233 let (at, len, ins, undo_line): (usize, usize, Vec<u8>, usize) = match act {
234 Act::Add => (s + l, 0, fmt!("x{}\n", tag).into_bytes(), k + 1),
235 Act::Word => {
236 let w = text[s..s + body].iter().position(|b| *b == b' ').unwrap_or(body);
237 if w == 0 {
238 return Ok(None);
239 }
240 (s, w, [&text[s..s + w], tag.as_bytes(), b"*"].concat(), k)
241 },
242 Act::Delete => (s, l, Vec::new(), k),
243 Act::Rewrite => (s, body, [&text[s..s + body], tag.as_bytes(), b"~"].concat(), k),
244 Act::Region => (s, l + next.unwrap_or(0), fmt!("R{}\nS{}\n", tag, tag).into_bytes(), k),
245 Act::Spill => (s, l + next.map(|n| n.saturating_sub(1).min(2)).unwrap_or(0), Vec::new(), k),
246 Act::Bump => (text.len(), 0, fmt!("z{}\n", a + 1).into_bytes(), ls.len()),
247 Act::Inside => {
248 if body == 0 {
249 return Ok(None);
250 }
251 (s + 1, 0, fmt!("i{}", tag).into_bytes(), k)
252 },
253 Act::Beside => {
254 let w = text[s..s + body].iter().position(|b| *b == b' ').unwrap_or(body);
255 (s + w, 0, fmt!("b{}", tag).into_bytes(), k)
256 },
257 Act::Move | Act::Twin => return Ok(None),
258 Act::Undo => {
259 let u = match self.authors[a].undo.pop() {
260 Some(u) => u,
261 None => return Ok(None),
262 };
263 if u.len > 0 {
264 // Its bytes, under whichever copy of them renders.
265 let twins = repo.twins_of(&u.id);
266 let found = view.runs().iter().find(|r| {
267 (r.content.op() == u.id || twins.contains(&r.content.op()))
268 && r.content.from() == 0
269 && r.content.len() == u.len as u64
270 });
271 match found {
272 Some(r) => (r.at as usize, u.len, u.removed, u.line),
273 None => return Ok(None),
274 }
275 } else {
276 let at = ls.get(u.line).map(|(s, _)| *s).unwrap_or(text.len());
277 (at, 0, u.removed, u.line)
278 }
279 },
280 };
281 if len == 0 && ins.is_empty() {
282 return Ok(None);
283 }
284 let op = res!(view.splice(at, len, ins.clone(), None));
285 let (h, op) = res!(author_on(&mut self.authors[a].seq, a as u64 + 1, op));
286 let id = h.id();
287 self.ops.push((h, op));
288 self.authors[a].undo.push(Undo {
289 id,
290 len: ins.len(),
291 removed: text[at..at + len].to_vec(),
292 line: undo_line,
293 });
294 Ok(Some(id))
295 }
296
297 /// One edit made alike by each of `who`, synced with each other first, and how
298 /// many copies were made. Author `raise`, if any, first makes a far edit the
299 /// others do not see.
300 fn twin(&mut self, who: &[usize], act: Act, line: usize, raise: Option<usize>)
301 -> Outcome<usize>
302 {
303 for i in who {
304 for j in who {
305 if i != j {
306 res!(self.sync(*i, *j));
307 }
308 }
309 }
310 if let Some(a) = raise {
311 res!(self.solo(a, Act::Bump, 0));
312 }
313 let mut made = 0;
314 for a in who {
315 if let Some(id) = res!(self.act(*a, act, line, "")) {
316 self.label.insert(id, fmt!("{}:twin {:?}", a + 1, act));
317 made += 1;
318 }
319 }
320 let names: Vec<String> = who.iter().map(|a| fmt!("{}", a + 1)).collect();
321 self.script.push(fmt!("{}:twin {:?}@{}", names.join("+"), act, line));
322 Ok(made)
323 }
324
325 fn solo(&mut self, a: usize, act: Act, line: usize)
326 -> Outcome<()>
327 {
328 if let Some(id) = res!(self.act(a, act, line, &fmt!("{}", a + 1))) {
329 self.label.insert(id, fmt!("{}:{:?}", a + 1, act));
330 self.script.push(fmt!("{}:{:?}@{}", a + 1, act, line));
331 }
332 Ok(())
333 }
334
335 /// Draws one history.
336 fn draw(rng: &mut Rng)
337 -> Outcome<Self>
338 {
339 let n = 2 + rng.below(3);
340 let mut h = res!(Self::new(n as u64));
341 let cap = 5 + rng.below(3);
342 // A region rewritten first, which the twin may land inside.
343 if rng.below(3) == 0 {
344 let act = [Act::Region, Act::Rewrite, Act::Add][rng.below(3)];
345 res!(h.solo(rng.below(n), act, 1 + rng.below(2)));
346 }
347 // The twin, by two authors or more, on any line, the first and last included.
348 let mut who: Vec<usize> = (0..n).collect();
349 while who.len() > 2 && rng.below(4) != 0 {
350 who.remove(rng.below(who.len()));
351 }
352 let act = TWIN_ACTS[rng.below(TWIN_ACTS.len())];
353 let line = rng.below(5);
354 // Authors whose pasts differ: one has made an edit the others have not seen,
355 // so the copies differ in counter.
356 let raise = if rng.below(3) == 0 { Some(who[rng.below(who.len())]) } else { None };
357 if res!(h.twin(&who, act, line, raise)) < 2 {
358 return Err(err!("No twin was made."; Test, Missing));
359 }
360 let hot = if act == Act::Add { line + 1 } else { line };
361 // What follows.
362 let mut steps = 0;
363 while h.generated() < cap && steps < 8 {
364 steps += 1;
365 if rng.below(4) == 0 {
366 let to = rng.below(n);
367 let from = (to + 1 + rng.below(n - 1)) % n;
368 res!(h.sync(to, from));
369 h.script.push(fmt!("{}<{}", to + 1, from + 1));
370 continue;
371 }
372 let a = rng.below(n);
373 let act = SOLO_ACTS[rng.below(SOLO_ACTS.len())];
374 let line = match rng.below(7) {
375 0..=3 => hot,
376 4 => hot + 1,
377 5 => hot.saturating_sub(1),
378 _ => rng.below(6),
379 };
380 if act == Act::Twin {
381 let b = (a + 1 + rng.below(n - 1)) % n;
382 let act = TWIN_ACTS[rng.below(TWIN_ACTS.len())];
383 res!(h.twin(&[a, b], act, line, None));
384 continue;
385 }
386 res!(h.solo(a, act, line));
387 }
388 Ok(h)
389 }
390}
391
392
393/// The delivery orders tried: the seed first, then every order of the rest up to
394/// `EVERY` operations, or every rotation, the reverse and six shuffles beyond.
395fn orders(n: usize, rng: &mut Rng) -> Vec<Vec<usize>> {
396 let g: Vec<usize> = (2..n).collect();
397 let mut out: Vec<Vec<usize>> = Vec::new();
398 if g.len() <= EVERY {
399 fn permute(idx: &mut Vec<usize>, k: usize, out: &mut Vec<Vec<usize>>) {
400 if k == idx.len() {
401 out.push(idx.clone());
402 return;
403 }
404 for i in k..idx.len() {
405 idx.swap(k, i);
406 permute(idx, k + 1, out);
407 idx.swap(k, i);
408 }
409 }
410 let mut idx = g.clone();
411 permute(&mut idx, 0, &mut out);
412 } else {
413 for k in 0..g.len() {
414 out.push((0..g.len()).map(|i| g[(i + k) % g.len()]).collect());
415 }
416 out.push(g.iter().rev().copied().collect());
417 for _ in 0..6 {
418 let mut idx = g.clone();
419 for i in (1..idx.len()).rev() {
420 idx.swap(i, rng.below(i + 1));
421 }
422 out.push(idx);
423 }
424 }
425 for o in out.iter_mut() {
426 o.insert(0, 1);
427 o.insert(0, 0);
428 }
429 out
430}
431
432fn listing(repo: &Repo) -> String {
433 let mut s = String::new();
434 for f in repo.files().iter().filter(|f| f.is_live()) {
435 s.push_str(&fmt!("{:?}", f.text_lossy()));
436 }
437 s
438}
439
440/// The insertions arbitration buried, as the render's own tombstones took them.
441fn buried(seq: &Sequence)
442 -> Outcome<BTreeSet<OpId>>
443{
444 let all = seq.in_op_order();
445 let graph = seq.causality();
446 let twins = Twins::find(&all, &graph);
447 let held = res!(twins.rewrite(&all));
448 let ops = twins.fold(&all, &held);
449 let cause = Cause::new(&graph, &twins);
450 let atoms = res!(Atoms::build(&ops));
451 let birth = res!(Sequence::birth_files(&ops, &res!(Dead::build(&ops)), &atoms));
452 Ok(res!(Sequence::yields(&ops, &birth, &cause)).buried)
453}
454
455/// One breach of the invariant: a key naming its shape, and the detail.
456struct Fault {
457 key: String,
458 text: String,
459}
460
461/// Judges one render of the history by the invariant.
462fn judge(h: &History, seq: &Sequence, repo: &Repo)
463 -> Outcome<Vec<Fault>>
464{
465 let graph = seq.causality();
466 let buried = res!(buried(seq));
467 let kept = |o: &OpId| -> OpId { repo.twins_of(o).first().copied().unwrap_or(*o) };
468 let class = |o: &OpId| -> Vec<OpId> {
469 match repo.twins_of(o) {
470 [] => vec![*o],
471 c => c.to_vec(),
472 }
473 };
474 let label = |x: &OpId| -> String {
475 let l = h.label.get(x).cloned().unwrap_or_else(|| fmt!("{}", x));
476 // The shape, without the replica.
477 match l.split_once(':') {
478 Some((_, s)) => s.to_string(),
479 None => l,
480 }
481 };
482 let op_of = |x: &OpId| -> Option<&Op> {
483 h.ops.iter().find(|(hd, _)| hd.id() == *x).map(|(_, op)| op)
484 };
485 let mut out: Vec<Fault> = Vec::new();
486
487 // Each byte shown, where, and how often.
488 let mut shown: BTreeMap<(OpId, u64), (u64, usize)> = BTreeMap::new();
489 for f in repo.files() {
490 for r in f.runs() {
491 for o in r.content.from()..r.content.to() {
492 let e = shown.entry((r.content.op(), o)).or_insert((r.at + o - r.content.from(), 0));
493 e.1 += 1;
494 }
495 }
496 }
497 // Text from one operation renders at most once, and a folded copy's not at all.
498 if let Some(((op, o), (_, n))) = shown.iter().find(|((op, _), (_, n))| *n > 1 || kept(op) != *op) {
499 out.push(Fault {
500 key: fmt!("duplicated: {} renders twice", label(op)),
501 text: fmt!("byte {} of {} ({}) renders {} times, its class kept as {}", o, op, label(op), n, kept(op)),
502 });
503 }
504 let named: BTreeSet<OpId> = repo.flags().iter()
505 .filter_map(|f| match f {
506 Flag::Yielded { op, .. } => Some(*op),
507 _ => None,
508 })
509 .collect();
510 let overlapped: BTreeSet<OpId> = repo.flags().iter()
511 .flat_map(|f| match f {
512 Flag::Overlap { ops, .. } => ops.clone(),
513 _ => Vec::new(),
514 })
515 .collect();
516 // Is `x` named by a flag beside `y`, or alone where `y` is `None`?
517 let told = |x: &OpId, y: Option<&OpId>| -> bool {
518 repo.flags().iter().any(|f| match (f, y) {
519 (Flag::Overlap { ops, .. }, Some(y)) => ops.contains(x) && ops.contains(y),
520 (Flag::Overlap { ops, .. }, None) => ops.contains(x),
521 (Flag::Yielded { op, to, .. }, Some(y)) => op == x && to == y,
522 (f, _) => f.op() == Some(*x),
523 })
524 };
525
526 // What each splice was built on, read off the operations: an insertion any byte
527 // of its removal belongs to, or the one both its origins lie in. The dead are
528 // the buried insertions, and every splice built on dead text, in turn.
529 let on = |op: &Op, gone: &BTreeSet<OpId>, k: &OpId| -> Option<OpId> {
530 let (left, right, remove) = match op {
531 Op::Splice { left, right, remove, .. } => (left, right, remove),
532 _ => return None,
533 };
534 let rm = remove.iter()
535 .filter(|r| !r.is_empty())
536 .map(|r| kept(&r.op()))
537 .find(|p| p != k && gone.contains(p));
538 match (rm, left, right) {
539 (Some(p), _, _) => Some(p),
540 (None, Some(l), Some(r)) => {
541 let (l, r) = (kept(&l.content.op), kept(&r.content.op));
542 (l != *k && gone.contains(&l) && gone.contains(&r)).then_some(l)
543 },
544 _ => None,
545 }
546 };
547 let mut gone: BTreeSet<OpId> = buried.clone();
548 loop {
549 let mut added = false;
550 for (head, op) in &h.ops {
551 let k = kept(&head.id());
552 if !gone.contains(&k) && on(op, &gone, &k).is_some() {
553 gone.insert(k);
554 added = true;
555 }
556 }
557 if !added {
558 break;
559 }
560 }
561 let moves = h.ops.iter().any(|(_, op)| matches!(op, Op::Move { .. }));
562
563 for (head, op) in &h.ops[2..] {
564 let x = head.id();
565 let k = kept(&x);
566 let mates = class(&x);
567 let (left, right, remove, insert) = match op {
568 Op::Splice { left, right, remove, insert, .. } => (left, right, remove, insert),
569 Op::Move { src, left, right, .. } => {
570 // A move lands wholly inside a buried insertion: its bytes render at a
571 // dead site, which must be said.
572 if let (Some(l), Some(r)) = (left, right) {
573 let shows = src.iter().any(|c| (c.from()..c.to())
574 .any(|o| shown.contains_key(&(kept(&c.op()), o))));
575 if shows
576 && gone.contains(&kept(&l.content.op))
577 && gone.contains(&kept(&r.content.op))
578 && !told(&x, None)
579 {
580 out.push(Fault {
581 key: fmt!("fragment: {} lands inside a buried insertion, unflagged", label(&x)),
582 text: fmt!("{} ({}) lands inside {}, buried", x, label(&x), kept(&l.content.op)),
583 });
584 }
585 }
586 // Copies it moved without having seen them: each author is told, with
587 // the move named beside the copy.
588 for c in src.iter().filter(|c| !c.is_empty()) {
589 for m in class(&c.op()) {
590 if !graph.reaches(&x, &m) && !told(&m, Some(&x)) {
591 out.push(Fault {
592 key: fmt!("unnamed: {} moves an unseen copy", label(&x)),
593 text: fmt!("{} ({}) moves {} ({}), unseen, unflagged", x, label(&x), m, label(&m)),
594 });
595 }
596 }
597 }
598 continue;
599 },
600 _ => continue,
601 };
602 let mut lost: Option<&str> = None;
603 let mut fragment = false;
604 for o in 0..insert.len() as u64 {
605 if shown.contains_key(&(k, o)) {
606 fragment |= gone.contains(&k);
607 continue;
608 }
609 // Gone: fine only if a splice that saw this one took it out, and that
610 // removal stands. A move takes nothing out.
611 let taken = h.ops.iter().any(|(zh, zop)| {
612 let z = zh.id();
613 let rm = match zop {
614 Op::Splice { remove, .. } => remove,
615 _ => return false,
616 };
617 z != x
618 && rm.iter().any(|r| mates.contains(&r.op()) && r.from() <= o && o < r.to())
619 && graph.reaches(&z, &x)
620 && !gone.contains(&kept(&z))
621 });
622 if !taken {
623 lost = Some("insertion gone");
624 }
625 }
626 for r in remove.iter() {
627 let rk = kept(&r.op());
628 if (r.from()..r.to()).any(|o| shown.contains_key(&(rk, o))) {
629 lost = Some("removal undone");
630 }
631 }
632 if gone.contains(&k) {
633 lost = lost.or(Some("yielded"));
634 if fragment {
635 let p = on(op, &gone, &k).map(|p| fmt!("{} ({})", p, label(&p))).unwrap_or_default();
636 out.push(Fault {
637 key: fmt!("fragment: {} renders built on a buried insertion", label(&x)),
638 text: fmt!("{} ({}) renders, built on {}, buried", x, label(&x), p),
639 });
640 }
641 }
642 if let Some(why) = lost {
643 if !named.contains(&x) {
644 let how = if overlapped.contains(&x) { "Overlap only" } else { "no flag" };
645 out.push(Fault {
646 key: fmt!("unnamed: {}, {}, {}", label(&x), why, how),
647 text: fmt!("{} ({}): {}, {}", x, label(&x), why, how),
648 });
649 }
650 }
651 // Where it was written: between its origins, wherever they render. A move
652 // changes where things are, so a history with one is not asked.
653 if !moves && !fragment && !gone.contains(&k) && !insert.is_empty() {
654 let at = |c: &crate::id::ContentId| shown.get(&(kept(&c.op), c.off)).map(|(p, _)| *p);
655 let first = shown.get(&(k, 0)).map(|(p, _)| *p);
656 let last = shown.get(&(k, insert.len() as u64 - 1)).map(|(p, _)| *p);
657 let before = left.as_ref().and_then(|a| at(&a.content));
658 let after = right.as_ref().and_then(|a| at(&a.content));
659 let wrong = match (first, last) {
660 (Some(f), Some(l)) => before.map(|b| b >= f).unwrap_or(false)
661 || after.map(|a| a <= l).unwrap_or(false),
662 _ => false,
663 };
664 if wrong {
665 out.push(Fault {
666 key: fmt!("misplaced: {} renders outside its origins", label(&x)),
667 text: fmt!("{} ({}) at {:?}..{:?}, origins at {:?} and {:?}", x, label(&x), first, last, before, after),
668 });
669 }
670 }
671 }
672
673 // A Yielded names an edit that stands; one through a host names a buried
674 // insertion its edit was built on; one without names an edit that had not
675 // seen it, since what the winner saw keeps its work.
676 for f in repo.flags() {
677 let (op, to, through) = match f {
678 Flag::Yielded { op, to, through, .. } => (op, to, through),
679 _ => continue,
680 };
681 let bad = if gone.contains(&kept(to)) {
682 Some("to an edit that does not stand")
683 } else {
684 match through {
685 Some(t) if !gone.contains(&kept(t)) => Some("through a host that stands"),
686 Some(t) => {
687 let t = kept(t);
688 let built = match op_of(op) {
689 Some(Op::Splice { left, right, remove, .. }) =>
690 remove.iter().any(|r| !r.is_empty() && kept(&r.op()) == t)
691 || match (left, right) {
692 (Some(l), Some(r)) => {
693 let (l, r) = (kept(&l.content.op), kept(&r.content.op));
694 (l == t || r == t) && gone.contains(&l) && gone.contains(&r)
695 },
696 _ => false,
697 },
698 _ => false,
699 };
700 (!built).then_some("through an insertion it was not built on")
701 },
702 None if graph.reaches(to, op) => Some("to an edit that had seen it"),
703 None => None,
704 }
705 };
706 if let Some(why) = bad {
707 out.push(Fault {
708 key: fmt!("misnamed: {} yields {}", label(op), why),
709 text: fmt!("{} ({}) yields to {} ({}) through {:?}: {}", op, label(op), to, label(to), through, why),
710 });
711 }
712 }
713 Ok(out)
714}
715
716/// Runs one history through its orders, then judges it.
717fn check(h: &History, rng: &mut Rng, renders: &mut usize)
718 -> Outcome<(Repo, Vec<Fault>)>
719{
720 let mut first: Option<(Repo, Sequence)> = None;
721 let mut out: Vec<Fault> = Vec::new();
722 for order in orders(h.ops.len(), rng) {
723 let mut seq = Sequence::new();
724 for i in &order {
725 res!(seq.apply(h.ops[*i].0.clone(), h.ops[*i].1.clone()));
726 }
727 let got = match seq.render() {
728 Ok(r) => r,
729 Err(e) => {
730 out.push(Fault { key: fmt!("render failed"), text: fmt!("{}", e) });
731 break;
732 },
733 };
734 *renders += 1;
735 if let Err(e) = seq.check_conservation(&got) {
736 out.push(Fault { key: fmt!("not conserved"), text: fmt!("{}", e) });
737 break;
738 }
739 match &first {
740 None => first = Some((got, seq)),
741 Some((want, _)) => {
742 if listing(want) != listing(&got) || want.flags() != got.flags() {
743 out.push(Fault {
744 key: fmt!("diverged"),
745 text: fmt!("{} against {}", listing(want), listing(&got)),
746 });
747 break;
748 }
749 },
750 }
751 }
752 match first {
753 Some((repo, seq)) => {
754 out.extend(res!(judge(h, &seq, &repo)));
755 Ok((repo, out))
756 },
757 None => Err(err!("No order rendered: {:?}.", out.first().map(|f| f.text.clone()); Test, Bug)),
758 }
759}
760
761#[test]
762fn every_small_twin_history_renders_each_authors_bytes_or_names_their_loss() -> Outcome<()> {
763 let start = Instant::now();
764 let mut rng = Rng(SEED);
765 let mut seen: BTreeSet<String> = BTreeSet::new();
766 let mut renders = 0;
767 let mut faulted = 0;
768 let mut twinned = 0;
769 // Each shape, with how often it was hit and its smallest reproduction.
770 let mut shapes: BTreeMap<String, (usize, usize, String)> = BTreeMap::new();
771 let mut tries = 0;
772 while seen.len() < HISTORIES && tries < HISTORIES * 4 {
773 tries += 1;
774 let h = match History::draw(&mut rng) {
775 Ok(h) => h,
776 Err(_) => continue,
777 };
778 let script = h.script.join(" ");
779 if !seen.insert(script.clone()) {
780 continue;
781 }
782 let (repo, faults) = res!(check(&h, &mut rng, &mut renders));
783 if h.ops.iter().any(|(hd, _)| !repo.twins_of(&hd.id()).is_empty()) {
784 twinned += 1;
785 }
786 if faults.is_empty() {
787 continue;
788 }
789 faulted += 1;
790 let flags: Vec<String> = repo.flags().iter().map(|f| fmt!("{:?}", f)).collect();
791 let detail = fmt!(
792 "{}\n render {}\n faults {}\n flags {}",
793 script,
794 listing(&repo),
795 faults.iter().map(|f| f.text.clone()).collect::<Vec<_>>().join("; "),
796 flags.join(" "),
797 );
798 for f in &faults {
799 let e = shapes.entry(f.key.clone()).or_insert((0, usize::MAX, String::new()));
800 e.0 += 1;
801 if h.generated() < e.1 {
802 e.1 = h.generated();
803 e.2 = detail.clone();
804 }
805 }
806 }
807 eprintln!(
808 "SWEEP {} histories ({} with a folded twin), {} renders, {} faulted, {:.1?}",
809 seen.len(), twinned, renders, faulted, start.elapsed(),
810 );
811 for (key, (n, ops, detail)) in &shapes {
812 eprintln!("SHAPE {} -- {} histories; smallest, {} operations:\n {}", key, n, ops, detail);
813 }
814 if faulted > 0 {
815 return Err(err!(
816 "{} of {} histories lose or garble an author's bytes unnamed, in {} shapes.",
817 faulted, seen.len(), shapes.len();
818 Test, Mismatch));
819 }
820 Ok(())
821}
822
823/// The independent reads' counter-examples, C1 to C5, and two adjacency cases, by script: each a replica,
824/// an act and a line, run through every order and judged as the sweep judges.
825#[test]
826fn the_reads_counter_examples_render_whole_hunks_and_name_their_losses() -> Outcome<()> {
827 use Act::*;
828 let cases: [(&str, u64, &[(usize, Act, usize, &str)]); 7] = [
829 ("C1", 2, &[(1, Bump, 0, "2"), (0, Word, 1, ""), (1, Word, 1, ""), (0, Undo, 0, "1"), (0, Rewrite, 1, "1")]),
830 ("C2", 2, &[(1, Bump, 0, "2"), (0, Word, 1, ""), (1, Word, 1, ""), (0, Undo, 0, "1"), (0, Undo, 0, "1")]),
831 ("C3", 3, &[(0, Word, 1, ""), (1, Word, 1, ""), (2, Bump, 0, "3"), (2, Word, 1, "3"), (0, Rewrite, 1, "1")]),
832 ("C4", 3, &[(0, Word, 1, "1"), (2, Bump, 0, "3"), (2, Word, 1, "3"), (0, Rewrite, 1, "1")]),
833 ("C5", 2, &[(1, Word, 3, "2"), (0, Add, 4, ""), (1, Add, 4, ""), (0, Delete, 5, "1"), (0, Undo, 0, "1"), (0, Rewrite, 5, "1")]),
834 // Beside a buried word, one origin in it and one in the base: it stands.
835 ("A1", 3, &[(0, Word, 1, "1"), (2, Bump, 0, "3"), (2, Word, 1, "3"), (0, Beside, 1, "1")]),
836 // C4, with the rewrite higher than the word that beat what it was built on.
837 ("A2", 3, &[(0, Word, 1, "1"), (2, Word, 1, "3"), (0, Bump, 0, "1"), (0, Rewrite, 1, "1")]),
838 ];
839 let mut bad = 0;
840 for (name, n, steps) in cases {
841 let mut h = res!(History::new(n));
842 for (a, act, line, tag) in steps {
843 if let Some(id) = res!(h.act(*a, *act, *line, tag)) {
844 h.label.insert(id, fmt!("{}:{:?}", a + 1, act));
845 }
846 }
847 let mut rng = Rng(SEED);
848 let mut renders = 0;
849 let (repo, faults) = res!(check(&h, &mut rng, &mut renders));
850 let flags: Vec<String> = repo.flags().iter().map(|f| fmt!("{:?}", f)).collect();
851 eprintln!("CASE {} {} renders {}\n faults [{}]\n flags {}", name, renders, listing(&repo),
852 faults.iter().map(|f| f.text.clone()).collect::<Vec<_>>().join("; "), flags.join(" "));
853 if !faults.is_empty() {
854 bad += 1;
855 }
856 }
857 if bad > 0 {
858 return Err(err!("{} of the reads' counter-examples fault.", bad; Test, Mismatch));
859 }
860 Ok(())
861}