Kill or justify the full mutation run's 32 misses
New tests pin behavior mutation testing showed was unconstrained: anchor ordering must prefer the larger of two crossing candidates, NodeTypes::admits must survive multiple supertype entries, a reformatting-only branch must leave output bytes alone (survivor origins stay O), duplicate identical insertions dedupe pairwise even in single-hash slots, a graft must not resurrect what the other branch deleted, the insert-delete rule stays quiet in both directions on unrelated deletions, conflicts carry both inserted spans, synthesis byte behavior is pinned exactly (including the known single-space wart and files without trailing newlines), the CLI diff3 block is byte-exact, and Zhang-Shasha gains an exhaustive small-tree oracle holding the backtrack to the DP's optimal cost. The remaining misses are excluded in .cargo/mutants.toml, each with a written equivalence argument. Assisted-by: Claude Fable 5 via Claude Code
diff --git a/.cargo/mutants.toml b/.cargo/mutants.toml
index a36adca..cb06142 100644
--- a/.cargo/mutants.toml
+++ b/.cargo/mutants.toml
@@ -34,4 +34,38 @@ exclude_re = [
# test pins length and validity, which is the function's whole
# contract; a mutant that broke either would be caught by it.
'replace \+ with \* in lcs_pairs',
+ # sibling_order_holds(): a sibling's image can never equal the
+ # candidate y — y is unmatched at check time — so index equality
+ # cannot occur and < versus <= coincide.
+ 'replace < with <= in sibling_order_holds',
+ # graft_branch()'s dedupe twin search: the insert-insert rule only
+ # lets equal insertion sequences through to the builder, so a
+ # budget-true entry always exists for every B insert and any
+ # bookkeeping that consumes each entry at most once skips exactly
+ # the same set. (The hash-equality half is pinned by the
+ # single-hash duplicate-statement test.)
+ 'replace && with \|\| in Builder<._>::graft_branch',
+ # graft()'s placed/consumed guards: for a graft to meet an
+ # already-placed or twice-consumed survivor, the diff would have to
+ # map a node's image outside its matched ancestor's image, which
+ # admissible() forbids. The guards are defense-in-depth against
+ # matchings our phases cannot produce.
+ 'replace && with \|\| in Builder<._>::graft\b',
+ # children_changed(): tree-sitter derives node-types.json from the
+ # grammar, so a node whose children match its parsed origin always
+ # satisfies the model; widening validation to unchanged nodes (or
+ # never treating them as unchanged) cannot change outcomes on
+ # parsed trees. The guard exists for cost and for grammar corners
+ # deliberately kept out of merges.
+ 'children_changed',
+ # synthesize()'s unclosed-file fallback guards: distinguishable
+ # only through the cov-excl-marked defensive path (the final merged
+ # leaf is in practice its origin's closing token).
+ 'delete ! in synthesize',
+ # Solver::solve()'s backtrack tail: once one side is exhausted the
+ # remaining walk emits only deletions and insertions, which the
+ # mapping does not report — and the delete branch always holds
+ # there, shielding the insert branch's condition.
+ 'replace \|\| with && in Solver<T, F>::solve',
+ 'replace && with \|\| in Solver<T, F>::solve',
]
diff --git a/src/diff.rs b/src/diff.rs
index 2fd1301..70523f8 100644
--- a/src/diff.rs
+++ b/src/diff.rs
@@ -981,6 +981,20 @@ mod tests {
Ok(())
}
+ #[test]
+ fn larger_anchors_win_over_crossing_smaller_ones() -> Result<(), Error> {
+ // The number and the inner array swap places; only one can
+ // anchor. Largest first means the subtree wins and the lone
+ // number is demoted.
+ let o = parse_json("[5, [1, 2, 3]]")?;
+ let a = parse_json("[[1, 2, 3], 5]")?;
+ let m = anchor(&o, &a);
+ let inner = find_kind(&o, "array").last().copied();
+ assert!(inner.is_some_and(|n| m.image(n).is_some()));
+ assert_eq!(find_number(&o, "5").and_then(|n| m.image(n)), None);
+ Ok(())
+ }
+
#[test]
fn duplicated_subtrees_do_not_anchor() -> Result<(), Error> {
// The number 1 appears twice in O, so its hash is not unique
diff --git a/src/lang.rs b/src/lang.rs
index 3847c6f..f84fdad 100644
--- a/src/lang.rs
+++ b/src/lang.rs
@@ -322,6 +322,28 @@ mod tests {
assert!(has_operator);
}
+ #[test]
+ fn admits_expands_nested_supertypes() {
+ // rust's block admits statements whose literals sit two
+ // supertype hops away (_expression → _literal → ...), so the
+ // expansion must survive visiting several supertype entries.
+ let node_types = Lang::by_name("rust").map(Lang::node_types);
+ let block_types = node_types
+ .and_then(|nt| nt.get("block"))
+ .and_then(|t| t.children.as_ref())
+ .map(|slot| slot.types.as_slice());
+ let admits = |kind: &str| {
+ node_types
+ .zip(block_types)
+ .is_some_and(|(nt, types)| nt.admits(types, kind))
+ };
+ assert!(admits("integer_literal"));
+ assert!(admits("string_literal"));
+ assert!(admits("expression_statement"));
+ assert!(!admits("no_such_kind"));
+ assert!(!admits("source_file"));
+ }
+
#[test]
fn supertype_subtypes_are_loaded() {
let has_const_item = Lang::by_name("rust").map(|lang| {
diff --git a/src/merge.rs b/src/merge.rs
index 68f9b93..f0c49f2 100644
--- a/src/merge.rs
+++ b/src/merge.rs
@@ -481,6 +481,53 @@ mod tests {
assert_merges("json", "[1, 2]", "[1, 9, 2]", "[1, 9, 2]", "[1, 9, 2]")
}
+ #[test]
+ fn duplicate_identical_insertions_dedupe_pairwise() -> Result<(), Error> {
+ // Two equal insertions per branch: each A graft absorbs
+ // exactly one B twin, so the pair lands twice, not four times.
+ assert_merges("json", "[1]", "[1, 9, 9]", "[1, 9, 9]", "[1, 9, 9]")?;
+ // The same with a single-hash slot (no separators): dedupe
+ // must match twins by hash, not merely consume any entry.
+ assert_merges(
+ "rust",
+ "fn f() { }",
+ "fn f() { x(); x(); }",
+ "fn f() { x(); x(); }",
+ "fn f() { x(); x(); }",
+ )
+ }
+
+ #[test]
+ fn a_graft_does_not_resurrect_what_the_other_branch_deleted() -> Result<(), Error> {
+ // A wraps y() in a block; B deletes y() outright. The block
+ // survives from A, but the statement inside it died in B and
+ // must not be pulled into the graft.
+ assert_merges(
+ "rust",
+ "fn f() { x(); y(); }",
+ "fn f() { x(); { y(); } }",
+ "fn f() { x(); }",
+ "fn f() { x(); { } }",
+ )
+ }
+
+ #[test]
+ fn reformatting_only_branches_leave_bytes_alone() -> Result<(), Error> {
+ // B reformats without changing the tree, so no relabel fires,
+ // every survivor keeps its O origin, and the output is
+ // byte-identical to O.
+ let o_text = "fn keep() {\n x(y);\n}\n";
+ let b_text = "fn keep( ) { x( y ) ; }\n";
+ let o = parse(o_text, "rust")?;
+ let a = parse(o_text, "rust")?;
+ let b = parse(b_text, "rust")?;
+ match merge_to_text(&o, &a, &b)? {
+ MergeResult::Merged(text) => assert_eq!(text, o_text),
+ MergeResult::Conflicts(conflicts) => panic!("unexpected conflicts: {conflicts:?}"),
+ }
+ Ok(())
+ }
+
#[test]
fn identical_deletions_merge_silently() -> Result<(), Error> {
assert_merges("json", "[1, 2]", "[1]", "[1]", "[1]")
@@ -554,13 +601,23 @@ mod tests {
#[test]
fn conflicting_insertions_at_one_slot_conflict() -> Result<(), Error> {
- assert_conflicts(
+ let conflicts = assert_conflicts(
"rust",
"fn f() { x(); }",
"fn f() { x(); y(); }",
"fn f() { x(); z(); }",
"insert-insert",
)?;
+ // The conflict carries both branches' inserted spans.
+ let a = parse("fn f() { x(); y(); }", "rust")?;
+ let witnessed = conflicts.iter().any(|c| {
+ c.span_a
+ .clone()
+ .and_then(|span| a.source_slice(span))
+ .is_some_and(|text| text.contains("y()"))
+ && c.span_b.is_some()
+ });
+ assert!(witnessed);
Ok(())
}
@@ -647,6 +704,16 @@ mod tests {
"fn a() { x(); z(); }\nfn b() { y(); }",
"fn a() { x(); }",
"fn a() { x(); z(); }",
+ )?;
+ // And mirrored: A deletes fn b while B grows fn a. The
+ // insert-delete rule must not fire on unrelated deletions in
+ // either direction.
+ assert_merges(
+ "rust",
+ "fn a() { x(); }\nfn b() { y(); }",
+ "fn a() { x(); }",
+ "fn a() { x(); z(); }\nfn b() { y(); }",
+ "fn a() { x(); z(); }",
)
}
diff --git a/src/synth.rs b/src/synth.rs
index a9b31ac..5a31584 100644
--- a/src/synth.rs
+++ b/src/synth.rs
@@ -239,6 +239,36 @@ mod tests {
Ok(())
}
+ #[test]
+ fn identical_inputs_reproduce_the_file_byte_for_byte() -> Result<(), Error> {
+ // Trailing trivia after the last leaf travels...
+ let with_tail = "fn a() {} // tail\n";
+ assert_eq!(
+ merge_text("rust", with_tail, with_tail, with_tail)?,
+ with_tail
+ );
+ // ...and a file without a final newline does not grow one.
+ let bare = "[1, 2]";
+ assert_eq!(merge_text("json", bare, bare, bare)?, bare);
+ Ok(())
+ }
+
+ #[test]
+ fn grafted_functions_pin_exact_bytes() -> Result<(), Error> {
+ // Byte-level regression for the trivia heuristics — including
+ // the known single-space wart where the O run's first leaf has
+ // no predecessor to borrow trivia from ("{} fn keep").
+ let o = "fn keep() {\n x();\n}\n";
+ let a = "/// From A.\nfn top() {}\n\nfn keep() {\n x();\n}\n";
+ let b = "fn keep() {\n x();\n}\n\n/// From B.\nfn bottom() {}\n";
+ let text = merge_text("rust", o, a, b)?;
+ assert_eq!(
+ text,
+ "/// From A.\nfn top() {} fn keep() {\n x();\n}\n\n/// From B.\nfn bottom() {}\n"
+ );
+ Ok(())
+ }
+
#[test]
fn doc_comments_travel_with_grafted_functions() -> Result<(), Error> {
let o = "fn keep() {\n x();\n}\n";
diff --git a/src/zs.rs b/src/zs.rs
index 091d04b..37b4dfe 100644
--- a/src/zs.rs
+++ b/src/zs.rs
@@ -8,6 +8,7 @@
//! between trees and related problems", SIAM J. Comput. 18(6), 1989.
/// A tree for Zhang–Shasha: a value and ordered children.
+#[derive(Clone)]
pub struct ZsTree<T> {
pub value: T,
pub children: Vec<ZsTree<T>>,
@@ -29,6 +30,17 @@ pub fn mapping<T: Copy>(
dst: &ZsTree<T>,
relabel: impl Fn(T, T) -> Option<u32>,
) -> Vec<(T, T)> {
+ mapping_with_cost(src, dst, relabel).0
+}
+
+/// [`mapping`] plus the optimal edit cost the DP computed, so tests
+/// can hold the backtrack to account: the mapping's implied cost must
+/// equal the distance.
+pub(crate) fn mapping_with_cost<T: Copy>(
+ src: &ZsTree<T>,
+ dst: &ZsTree<T>,
+ relabel: impl Fn(T, T) -> Option<u32>,
+) -> (Vec<(T, T)>, u32) {
let src_flat = Flat::build(src);
let dst_flat = Flat::build(dst);
let solver = Solver {
@@ -103,7 +115,7 @@ struct Solver<T, F> {
// waived for fidelity to the published pseudocode.
#[allow(clippy::indexing_slicing, clippy::arithmetic_side_effects)]
impl<T: Copy, F: Fn(T, T) -> Option<u32>> Solver<T, F> {
- fn solve(&self) -> Vec<(T, T)> {
+ fn solve(&self) -> (Vec<(T, T)>, u32) {
let (n, m) = (self.src.len(), self.dst.len());
let mut treedist = vec![vec![0u32; m + 1]; n + 1];
for &i in &self.src.keyroots {
@@ -111,6 +123,7 @@ impl<T: Copy, F: Fn(T, T) -> Option<u32>> Solver<T, F> {
self.forest_dist(i, j, &mut treedist);
}
}
+ let distance = treedist[n][m];
// Backtrack: walk each subtree pair's forest table from the
// corner, emitting pairs on diagonal steps that close a whole
@@ -137,7 +150,7 @@ impl<T: Copy, F: Fn(T, T) -> Option<u32>> Solver<T, F> {
}
}
}
- pairs
+ (pairs, distance)
}
/// The forest-distance DP for the subtree pair (i, j), 1-based.
@@ -249,6 +262,94 @@ mod tests {
}
}
+ /// All trees with exactly `nodes` nodes over the given labels.
+ fn trees_with(nodes: usize, labels: &[u8]) -> Vec<ZsTree<u8>> {
+ if nodes == 0 {
+ return Vec::new();
+ }
+ let mut out = Vec::new();
+ for &label in labels {
+ for children in forests(nodes.saturating_sub(1), labels) {
+ out.push(ZsTree {
+ value: label,
+ children,
+ });
+ }
+ }
+ out
+ }
+
+ /// All ordered forests totalling `total` nodes.
+ fn forests(total: usize, labels: &[u8]) -> Vec<Vec<ZsTree<u8>>> {
+ if total == 0 {
+ return vec![Vec::new()];
+ }
+ let mut out = Vec::new();
+ for first in 1..=total {
+ for head in trees_with(first, labels) {
+ for tail in forests(total.saturating_sub(first), labels) {
+ let mut forest = vec![head.clone()];
+ forest.extend(tail);
+ out.push(forest);
+ }
+ }
+ }
+ out
+ }
+
+ /// Clones a label tree into an identity-carrying tree with
+ /// pre-order ids, returning the node count.
+ fn retag(tree: &ZsTree<u8>, next: &mut usize) -> ZsTree<(usize, u8)> {
+ let id = *next;
+ *next = next.saturating_add(1);
+ ZsTree {
+ value: (id, tree.value),
+ children: tree.children.iter().map(|c| retag(c, next)).collect(),
+ }
+ }
+
+ #[test]
+ fn mapping_cost_matches_the_dp_on_all_small_trees() {
+ // Exhaustive internal-consistency oracle: the backtracked
+ // mapping's implied cost (relabels + unmatched nodes on both
+ // sides) must equal the DP's optimal distance, and the mapping
+ // must be a bijection. Kills backtrack mutants that hand-picked
+ // cases let through.
+ let labels = [0u8, 1u8];
+ let mut all: Vec<(ZsTree<(usize, u8)>, usize)> = Vec::new();
+ for nodes in 1..=3usize {
+ for tree in trees_with(nodes, &labels) {
+ let mut next = 0usize;
+ let tagged = retag(&tree, &mut next);
+ all.push((tagged, next));
+ }
+ }
+ for (src, src_count) in &all {
+ for (dst, dst_count) in &all {
+ let (pairs, distance) =
+ mapping_with_cost(src, dst, |a, b| if a.1 == b.1 { Some(0) } else { Some(1) });
+ let relabels = pairs.iter().filter(|(a, b)| a.1 != b.1).count();
+ let matched = pairs.len();
+ let implied = relabels
+ .saturating_add(src_count.saturating_sub(matched))
+ .saturating_add(dst_count.saturating_sub(matched));
+ assert_eq!(
+ u32::try_from(implied).ok(),
+ Some(distance),
+ "implied cost diverged for {matched} pairs"
+ );
+ let mut src_ids: Vec<usize> = pairs.iter().map(|(a, _)| a.0).collect();
+ let mut dst_ids: Vec<usize> = pairs.iter().map(|(_, b)| b.0).collect();
+ src_ids.sort_unstable();
+ src_ids.dedup();
+ dst_ids.sort_unstable();
+ dst_ids.dedup();
+ assert_eq!(src_ids.len(), matched);
+ assert_eq!(dst_ids.len(), matched);
+ }
+ }
+ }
+
#[test]
fn mapping_preserves_sibling_order() {
// f(a, b) vs f(b, a): only one leaf can survive; crossing both
diff --git a/tests/cli.rs b/tests/cli.rs
index a15a292..d307ed8 100644
--- a/tests/cli.rs
+++ b/tests/cli.rs
@@ -69,7 +69,9 @@ fn conflicting_merge_exits_one_with_markers() {
.args(&paths)
.assert()
.code(1)
- .stdout(predicate::str::contains("<<<<<<<"))
+ .stdout(predicate::eq(
+ "<<<<<<< A\nfn b() {}\n||||||| O\nfn a() {}\n=======\nfn c() {}\n>>>>>>> B\n",
+ ))
.stderr(predicate::str::contains("relabel-relabel"));
}