diff: anchor only subtrees that carry a labeled leaf
Structure-only subtrees — empty blocks, bare token runs — hash equal
across unrelated positions, and a unique-unique pair of them anchors
the diff to the wrong twin: an empty inner class body matched a
different class's empty body one nesting level up, which let a merge
re-anchor an insertion into the wrong class. Content identity needs
content; candidates without any labeled leaf are dropped, and the
alignment passes still match such tokens positionally within gaps.
Assisted-by: Claude Fable 5 via Claude Code
diff --git a/src/diff.rs b/src/diff.rs
index a94ef36..8661e5f 100644
--- a/src/diff.rs
+++ b/src/diff.rs
@@ -162,10 +162,20 @@ pub fn anchor(src: &Tree, dst: &Tree) -> Matching {
let src_unique = unique_subtrees(src);
let dst_unique = unique_subtrees(dst);
+ // Anchors assert content identity, so a candidate must contain at
+ // least one labeled leaf. Structure-only subtrees — empty blocks,
+ // bare token runs — collide across unrelated positions (two `{}`
+ // class bodies at different nesting levels hash equal) and would
+ // pin the diff to the wrong twin.
+ let has_label = labeled_subtrees(src);
+
let mut candidates: Vec<(NodeId, NodeId)> = src_unique
.iter()
.filter_map(|(hash, &s)| {
let s = s?;
+ if !has_label.get(s.index()).copied().unwrap_or(false) {
+ return None;
+ }
let d = dst_unique.get(hash).copied().flatten()?;
Some((s, d))
})
@@ -616,6 +626,24 @@ fn unique_subtrees(tree: &Tree) -> HashMap<u64, Option<NodeId>> {
map
}
+/// Whether each subtree contains a labeled leaf, indexed like the
+/// arena.
+fn labeled_subtrees(tree: &Tree) -> Vec<bool> {
+ let ids: Vec<_> = tree.nodes().collect();
+ let mut labeled = vec![false; ids.len()];
+ for &id in ids.iter().rev() {
+ let own = tree.label(id).is_some()
+ || tree
+ .children(id)
+ .iter()
+ .any(|child| labeled.get(child.index()).copied().unwrap_or(false));
+ if let Some(slot) = labeled.get_mut(id.index()) {
+ *slot = own;
+ }
+ }
+ labeled
+}
+
/// Node counts per subtree, indexed like the arena.
fn subtree_sizes(tree: &Tree) -> Vec<usize> {
let ids: Vec<_> = tree.nodes().collect();
@@ -940,6 +968,18 @@ mod tests {
Ok(())
}
+ #[test]
+ fn structure_only_subtrees_do_not_anchor() -> Result<(), Error> {
+ // O's inner [] and A's array hash equal and occur once each,
+ // but an empty array carries no content identity — anchoring
+ // them would pin the diff across nesting levels.
+ let o = parse_json("[[]]")?;
+ let a = parse_json("[]")?;
+ let m = anchor(&o, &a);
+ assert_eq!(m.pairs().count(), 0);
+ Ok(())
+ }
+
#[test]
fn duplicated_subtrees_do_not_anchor() -> Result<(), Error> {
// The number 1 appears twice in O, so its hash is not unique