diff options
| author | tv <tv@krebsco.de> | 2026-11-13 16:45:52 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-13 16:45:52 +0000 |
| commit | 02b4ee25950a7edd527d728a5a7234ba24361428 (patch) | |
| tree | fd71edd0793b2a5dac4059d4898d2f18963d7015 /src/document/changes.rs | |
| parent | 29e70c16546f3f2b0134147a31ec335f82433289 (diff) | |
changes: a test that generates changes and asks what passes to stay sound
Twice, crafting changes by hand missed some that pass screening's checks
and break Automerge; a program generating them found three more kinds.
This test does the same: on documents three honest writers wrote at once
(maps, a list, a text, a counter), changes of one to four operations of
every kind, at random places, naming as replaced nothing, what is there,
or any operation. Each that passes the checks is applied, given back by
its hash, saved and loaded, taken by a peer that lacks it, written after
by an honest node, and saved and loaded again; nothing of that may fail
or panic. The run is seeded, the seed named where it fails, and
CHANGES_GENERATED sets how many documents (60 by default) for a longer
run.
Diffstat (limited to 'src/document/changes.rs')
| -rw-r--r-- | src/document/changes.rs | 234 |
1 files changed, 234 insertions, 0 deletions
diff --git a/src/document/changes.rs b/src/document/changes.rs index cc04c7f..bb448e0 100644 --- a/src/document/changes.rs +++ b/src/document/changes.rs @@ -1578,4 +1578,238 @@ mod tests { // Not taken: screening refuses it as forged. assert_eq!(written.check(&ours, &honest, &honest.decode()), None); } + + /// Changes generated, not listed: on documents honest nodes wrote at once (maps, a + /// list, a text, counters), changes of one to four operations of every kind, at + /// random places, naming as replaced nothing, what is there, or any operation. + /// Each that passes the checks is applied, given back by its hash, saved and + /// loaded, taken by a peer that lacks it, written after by an honest node, and + /// saved and loaded again: none of it may fail or panic. `CHANGES_GENERATED` + /// sets how many documents (default 60); the seed is in what fails. + #[test] + fn what_passes_leaves_automerge_sound() { + use crate::document::testing::try_change; + use automerge::legacy::{ElementId, Key, ObjectId, OpId, OpType}; + use automerge::{ObjType, ScalarValue}; + + /// SplitMix64: the same seed, the same run. + struct Random(u64); + impl Random { + fn next(&mut self) -> u64 { + self.0 = self.0.wrapping_add(0x9e37_79b9_7f4a_7c15); + let mut z = self.0; + z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9); + z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb); + z ^ (z >> 31) + } + fn below(&mut self, n: usize) -> usize { + (self.next() % n.max(1) as u64) as usize + } + fn one<'a, T>(&mut self, of: &'a [T]) -> Option<&'a T> { + (!of.is_empty()).then(|| &of[self.below(of.len())]) + } + fn actor(&mut self) -> ActorId { + ActorId::from(self.next().to_be_bytes().to_vec()) + } + } + + /// One honest write, at random; refused writes (a deletion of nothing) are + /// dropped. + fn honest_write(doc: &mut Document, random: &mut Random) { + let pick = random.below(9); + let key = format!("k{}", random.below(4)); + let at = random.below(4); + let value = random.next() as i64 % 100; + let _ = try_change(doc, |tx| -> Result<(), automerge::AutomergeError> { + let (_, map) = tx.get(ROOT, "map")?.expect("the map"); + let (_, list) = tx.get(ROOT, "list")?.expect("the list"); + let (_, text) = tx.get(ROOT, "text")?.expect("the text"); + let len = tx.length(&list); + let text_len = tx.length(&text); + match pick { + 0 => tx.put(&map, key, value)?, + 1 => tx.delete(&map, key)?, + 2 => tx.insert(&list, at.min(len), value)?, + 3 if len > 0 => tx.put(&list, at % len, value)?, + 4 if len > 0 => tx.delete(&list, at % len)?, + 5 => tx.splice_text(&text, at.min(text_len), 0, "xy")?, + 6 if text_len > 0 => tx.splice_text(&text, at % text_len, 1, "")?, + 7 => tx.increment(ROOT, "count", 1)?, + _ => { + tx.put_object(&map, key, ObjType::List)?; + } + } + Ok(()) + }); + } + + /// What a document is made of: every operation by its ID, the object it is in, + /// its key, whether it inserted, and the object it made. + type Made = Vec<(OpId, ObjectId, Key, bool, Option<ObjType>)>; + fn made(doc: &Document) -> Made { + let mut made = Vec::new(); + for change in doc.get_changes(&[]) { + let start = change.start_op().get(); + let actor = change.actor_id().clone(); + for (index, op) in change.decode().operations.into_iter().enumerate() { + let makes = match op.action { + OpType::Make(kind) => Some(kind), + _ => None, + }; + made.push(( + OpId(start + index as u64, actor.clone()), + op.obj, + op.key, + op.insert, + makes, + )); + } + } + made + } + + /// `crafted`, applied to a copy of `doc`, and all the rest asked of it. + fn sound(doc: &Document, crafted: &Change, random: &mut Random) -> Result<(), String> { + let mut doc = doc.clone(); + doc.apply_changes([crafted.clone()]) + .map_err(|e| format!("applied: {e}"))?; + let back = doc + .get_change_by_hash(&crafted.hash()) + .ok_or("not given back")?; + if back.raw_bytes() != crafted.raw_bytes() { + return Err("another change given back under its hash".to_owned()); + } + let loaded = Document::load(&doc.save()).map_err(|e| format!("loaded: {e}"))?; + if loaded.get_heads() != doc.get_heads() { + return Err("loaded with other heads".to_owned()); + } + let mut peer = Document::new(); + peer.apply_changes(doc.get_changes(&[])) + .map_err(|e| format!("taken by a peer: {e}"))?; + if peer.get_heads() != doc.get_heads() { + return Err("a peer came to other heads".to_owned()); + } + let mut after = loaded.with_actor(random.actor()); + let before = after.get_heads(); + for _ in 0..4 { + honest_write(&mut after, random); + } + let _ = after.get_last_local_change(); + let _ = after.save_after(&before); + Document::load(&after.save()).map_err(|e| format!("written after, loaded: {e}"))?; + Ok(()) + } + + let documents: u64 = std::env::var("CHANGES_GENERATED") + .ok() + .and_then(|count| count.parse().ok()) + .unwrap_or(60); + let (mut passed, mut checked) = (0, 0); + for seed in 0..documents { + let mut random = Random(seed); + let mut doc = Document::new().with_actor(random.actor()); + change(&mut doc, |tx| { + tx.put_object(ROOT, "map", ObjType::Map).unwrap(); + let list = tx.put_object(ROOT, "list", ObjType::List).unwrap(); + tx.insert(&list, 0, 0).unwrap(); + let text = tx.put_object(ROOT, "text", ObjType::Text).unwrap(); + tx.splice_text(&text, 0, 0, "ab").unwrap(); + tx.put(ROOT, "count", ScalarValue::counter(0)).unwrap(); + }); + let mut writers: Vec<Document> = (0..3) + .map(|_| doc.fork().with_actor(random.actor())) + .collect(); + for _ in 0..8 { + let writer = random.below(writers.len()); + honest_write(&mut writers[writer], &mut random); + } + for writer in &mut writers { + doc.merge(writer).unwrap(); + } + let made = made(&doc); + let objects: Vec<(ObjectId, ObjType)> = std::iter::once((ObjectId::Root, ObjType::Map)) + .chain(made.iter().filter_map(|(id, _, _, _, makes)| { + makes.map(|kind| (ObjectId::Id(id.clone()), kind)) + })) + .collect(); + for _ in 0..40 { + // Honest puts, as many as the operations crafted, then made over. + let count = 1 + random.below(4); + let mut fork = doc.fork().with_actor(random.actor()); + change(&mut fork, |tx| { + for index in 0..count { + tx.put(ROOT, format!("z{index}"), 0).unwrap(); + } + }); + let honest = fork.get_last_local_change().unwrap(); + let crafted = crafted(&honest, |change| { + for op in change.operations.iter_mut() { + let (obj, kind) = random.one(&objects).unwrap().clone(); + op.obj = obj.clone(); + let elements: Vec<OpId> = made + .iter() + .filter(|(_, in_obj, _, insert, _)| *insert && *in_obj == obj) + .map(|(id, ..)| id.clone()) + .collect(); + let in_list = matches!(kind, ObjType::List | ObjType::Text); + op.key = match (in_list != (random.below(8) == 0), random.below(3)) { + (false, _) => Key::Map(format!("k{}", random.below(4)).into()), + (true, 0) => Key::Seq(ElementId::Head), + (true, _) => match random.one(&elements) { + Some(id) => Key::Seq(ElementId::Id(id.clone())), + None => Key::Seq(ElementId::Head), + }, + }; + op.insert = in_list && random.below(2) == 0; + op.action = match random.below(7) { + 0 => OpType::Make(ObjType::Map), + 1 => OpType::Make(ObjType::List), + 2 => OpType::Delete, + 3 => OpType::Increment(1), + 4 => OpType::Put(ScalarValue::counter(1)), + _ => OpType::Put(ScalarValue::Int(7)), + }; + // Named as replaced: nothing, what is at that place, or any. + let there: Vec<OpId> = made + .iter() + .filter(|(id, in_obj, key, insert, _)| { + *in_obj == obj + && (*key == op.key + || (*insert + && op.key == Key::Seq(ElementId::Id(id.clone())))) + }) + .map(|(id, ..)| id.clone()) + .collect(); + let any: Vec<OpId> = made.iter().map(|(id, ..)| id.clone()).collect(); + op.pred = match random.below(4) { + 0 => Vec::new(), + 1 | 2 => random.one(&there).into_iter().cloned().collect(), + _ => random.one(&any).into_iter().cloned().collect(), + } + .into(); + } + }); + checked += 1; + let decoded = crafted.decode(); + if Written::default().check(&doc, &crafted, &decoded).is_some() { + continue; + } + passed += 1; + let outcome = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| { + sound(&doc, &crafted, &mut random) + })) + .unwrap_or_else(|_| Err("panicked".to_owned())); + if let Err(what) = outcome { + panic!( + "seed {seed}: a change that passed broke Automerge ({what}): {:?}", + decoded.operations + ); + } + } + } + assert!( + passed > 0 && passed < checked, + "{passed} of {checked} passed" + ); + } } |
