add changed_path minimality test

1 files changed, 69 insertions, 0 deletions

diff --git a/src/remake/delta.rs b/src/remake/delta.rs
index ef6a60a..80e5443 100644
--- a/src/remake/delta.rs
+++ b/src/remake/delta.rs
@@ -344,6 +344,75 @@ mod tests {
         });
     }
 
+    /// Every non-empty-object value of `json` with its path.
+    fn leaves(
+        json: &serde_json::Value,
+        path: &mut Vec<String>,
+        out: &mut Vec<(Vec<String>, String)>,
+    ) {
+        match json {
+            serde_json::Value::Object(map) => {
+                for (key, value) in map {
+                    path.push(key.clone());
+                    leaves(value, path, out);
+                    path.pop();
+                }
+            }
+            other => out.push((path.clone(), other.to_string())),
+        }
+    }
+
+    /// Over random histories (writes and deletes, some on concurrent forks): the paths
+    /// are sorted, none is a prefix of another, and together they cover every value that
+    /// differs between before and after.
+    #[test]
+    fn changed_paths_cover_every_change_minimally() {
+        crate::testrand::for_seeds(300, |rng| {
+            let actor = |i: u8| ActorId::from(&[i; 16][..]);
+            let mut doc = AutoCommit::new().with_actor(actor(0));
+            for _ in 0..rng.between(0, 8) {
+                random_write(rng, &mut doc);
+            }
+            let before = doc.get_heads();
+            let mut forks: Vec<AutoCommit> = (1..=rng.between(1, 3))
+                .map(|i| doc.fork().with_actor(actor(i as u8)))
+                .collect();
+            for _ in 0..rng.between(0, 12) {
+                let fork = rng.below(forks.len());
+                random_write(rng, &mut forks[fork]);
+            }
+            for fork in &mut forks {
+                doc.merge(fork).unwrap();
+            }
+            let after = doc.get_heads();
+
+            let paths = changed_paths(&mut doc, &before, &after);
+            for pair in paths.windows(2) {
+                assert!(pair[0] < pair[1], "not sorted: {paths:?}");
+                assert!(!pair[1].starts_with(&pair[0]), "not minimal: {paths:?}");
+            }
+
+            let mut old = Vec::new();
+            leaves(
+                &view(&doc.fork_at(&before).unwrap()),
+                &mut Vec::new(),
+                &mut old,
+            );
+            let mut new = Vec::new();
+            leaves(&view(&doc), &mut Vec::new(), &mut new);
+            let differing = old
+                .iter()
+                .filter(|leaf| !new.contains(leaf))
+                .chain(new.iter().filter(|leaf| !old.contains(leaf)));
+            for (path, _) in differing {
+                assert!(
+                    paths.iter().any(|changed| path.starts_with(changed)),
+                    "{path:?} changed, but {paths:?} don't cover it"
+                );
+            }
+        });
+    }
+
     #[test]
     fn minimal_paths() {
         let mut doc = AutoCommit::new();