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 | |
| 40 | use crate::id::{ |
| 41 | OpId, |
| 42 | ReplicaId, |
| 43 | }; |
| 44 | use crate::op::{ |
| 45 | Header, |
| 46 | Op, |
| 47 | }; |
| 48 | use crate::seq::atom::Atoms; |
| 49 | use crate::seq::claim::Dead; |
| 50 | use crate::seq::render::{ |
| 51 | Flag, |
| 52 | Rendered, |
| 53 | Repo, |
| 54 | }; |
| 55 | use crate::seq::twin::{ |
| 56 | Cause, |
| 57 | Twins, |
| 58 | }; |
| 59 | use crate::seq::Sequence; |
| 60 | |
| 61 | use oxedyne_fe2o3_core::prelude::*; |
| 62 | |
| 63 | use std::collections::{ |
| 64 | BTreeMap, |
| 65 | BTreeSet, |
| 66 | }; |
| 67 | use std::time::Instant; |
| 68 | |
| 69 | |
| 70 | const BASE: &str = "head\none decimal two\nthree\nfour\ntail\n"; |
| 71 | const SEED: u64 = 0x5eed_0f_7a1e_2026; // fixed: the sweep is the same on every run |
| 72 | const HISTORIES: usize = 2400; // distinct histories drawn |
| 73 | const EVERY: usize = 5; // every order up to this many operations |
| 74 | |
| 75 | |
| 76 | #[derive(Clone, Copy, Debug, Eq, PartialEq)] |
| 77 | enum 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 | |
| 92 | const TWIN_ACTS: [Act; 5] = [Act::Add, Act::Word, Act::Delete, Act::Rewrite, Act::Inside]; |
| 93 | const 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. |
| 100 | struct 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 | |
| 107 | struct Author { |
| 108 | seq: Sequence, |
| 109 | undo: Vec<Undo>, |
| 110 | } |
| 111 | |
| 112 | struct 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 | |
| 120 | struct Rng(u64); |
| 121 | |
| 122 | impl 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. |
| 132 | fn 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 | |
| 147 | fn 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 | |
| 156 | fn 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 | |
| 167 | impl 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. |
| 395 | fn 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 | |
| 432 | fn 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. |
| 441 | fn 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. |
| 456 | struct Fault { |
| 457 | key: String, |
| 458 | text: String, |
| 459 | } |
| 460 | |
| 461 | /// Judges one render of the history by the invariant. |
| 462 | fn 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. |
| 717 | fn 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] |
| 762 | fn 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] |
| 826 | fn 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 | } |