aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--src/document/changes.rs234
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"
+ );
+ }
}