diff options
Diffstat (limited to 'src')
| -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" + ); + } } |
