Conflict on same-named insertions at different slots
Both branches adding a definition with one name at different
positions slipped past every slot-based rule: insert-insert wants a
shared slot and dedupe cannot merge grafts landing in different
places, so the merge held two `class Config` declarations or a JSON
object with the same key twice. Found by running d3j over mergiraf's
example suite, where five of six silent bad merges were this shape.
The new name-collision aggregate rule keys inserted nodes by their
`name` or `key` field child, staying grammar-driven rather than
per-language. That is coarser than real signatures: concurrently
inserted same-name Java overloads conflict too, and identical
insertions at different slots conflict instead of deduping.
Assisted-by: Claude Fable 5 via Claude Code
diff --git a/src/merge.rs b/src/merge.rs
index 30c70f2..4079e35 100644
--- a/src/merge.rs
+++ b/src/merge.rs
@@ -734,6 +734,70 @@ mod tests {
Ok(())
}
+ #[test]
+ fn same_key_inserted_at_different_slots_conflicts() -> Result<(), Error> {
+ // A adds "k" at the front, B adds "k" at the back, values
+ // differ. No shared slot, so insert-insert is blind; without
+ // name-collision the merge holds the key twice.
+ let conflicts = assert_conflicts(
+ "json",
+ r#"{"a": 1, "b": 2}"#,
+ r#"{"k": 8, "a": 1, "b": 2}"#,
+ r#"{"a": 1, "b": 2, "k": 9}"#,
+ "name-collision",
+ )?;
+ // The conflict carries both inserted pairs.
+ let a = parse(r#"{"k": 8, "a": 1, "b": 2}"#, "json")?;
+ let witnessed = conflicts.iter().any(|c| {
+ c.rule == "name-collision"
+ && c.span_a
+ .clone()
+ .and_then(|span| a.source_slice(span))
+ .is_some_and(|text| text.contains("\"k\""))
+ && c.span_b.is_some()
+ });
+ assert!(witnessed);
+ Ok(())
+ }
+
+ #[test]
+ fn identical_key_inserted_at_different_slots_conflicts() -> Result<(), Error> {
+ // Identical values still conflict: dedupe only merges grafts
+ // sharing a slot, so accepting this would keep both copies.
+ assert_conflicts(
+ "json",
+ r#"{"a": 1, "b": 2}"#,
+ r#"{"k": 8, "a": 1, "b": 2}"#,
+ r#"{"a": 1, "b": 2, "k": 8}"#,
+ "name-collision",
+ )?;
+ Ok(())
+ }
+
+ #[test]
+ fn same_class_inserted_at_different_slots_conflicts() -> Result<(), Error> {
+ assert_conflicts(
+ "java",
+ "class P { }\nclass Q { }",
+ "class N { int x; }\nclass P { }\nclass Q { }",
+ "class P { }\nclass Q { }\nclass N { boolean y; }",
+ "name-collision",
+ )?;
+ Ok(())
+ }
+
+ #[test]
+ fn same_key_inserted_into_different_objects_merges() -> Result<(), Error> {
+ // Same name under different parents is no collision.
+ assert_merges(
+ "json",
+ r#"{"x": {"a": 1}, "y": {"b": 2}}"#,
+ r#"{"x": {"k": 1, "a": 1}, "y": {"b": 2}}"#,
+ r#"{"x": {"a": 1}, "y": {"b": 2, "k": 2}}"#,
+ r#"{"x": {"k": 1, "a": 1}, "y": {"b": 2, "k": 2}}"#,
+ )
+ }
+
#[test]
fn relabel_and_delete_in_different_functions_merge() -> Result<(), Error> {
// The rule must not fire when the relabel is outside the
diff --git a/src/rules.rs b/src/rules.rs
index 73d9a15..920ab33 100644
--- a/src/rules.rs
+++ b/src/rules.rs
@@ -21,6 +21,10 @@ pub(crate) struct Ctx<'t> {
/// A conflict rule over one (edit-from-A, edit-from-B) pair.
type PairRule = fn(&Edit, &Edit, &Ctx) -> Option<Conflict>;
+/// Where an insertion lands: the parent's O preimage plus the O
+/// preimage of the nearest preceding matched sibling.
+type Slot = (NodeId, Option<NodeId>);
+
const PAIR_RULES: &[PairRule] = &[relabel_relabel, relabel_delete, insert_delete];
/// Runs the pairwise rules over every cross-branch edit pair and the
@@ -46,6 +50,7 @@ pub(crate) fn conflicts(ctx: &Ctx, edits_a: &[Edit], edits_b: &[Edit]) -> Vec<Co
}
}
insert_insert(ctx, edits_a, edits_b, &mut found);
+ name_collision(ctx, edits_a, edits_b, &mut found);
delete_delete(ctx, edits_a, edits_b, &mut found);
found
}
@@ -360,15 +365,86 @@ fn insert_insert(ctx: &Ctx, edits_a: &[Edit], edits_b: &[Edit], found: &mut Vec<
}
}
+/// name-collision: both branches inserted same-named definitions
+/// under the same O parent at different slots. The builder grafts
+/// both, yielding duplicate definitions — two `class Hello`, a JSON
+/// object holding the same key twice — that no slot-based rule sees:
+/// insert-insert wants a shared slot, and dedupe cannot merge grafts
+/// landing in different places. A node's "name" is its `name` or
+/// `key` field child, keeping the rule grammar-driven; that is
+/// deliberately coarser than real signatures, so concurrently
+/// inserting two distinct same-name Java overloads conflicts too.
+/// Same-slot pairs are skipped: equal sequences dedupe and unequal
+/// ones are already insert-insert conflicts.
+fn name_collision(ctx: &Ctx, edits_a: &[Edit], edits_b: &[Edit], found: &mut Vec<Conflict>) {
+ let names_a = insert_names(ctx.a, ctx.f, edits_a);
+ let names_b = insert_names(ctx.b, ctx.g, edits_b);
+ for (name, inserts_a) in &names_a {
+ let Some(inserts_b) = names_b.get(name) else {
+ continue;
+ };
+ for (slot_a, node_a) in inserts_a {
+ for (slot_b, node_b) in inserts_b {
+ if slot_a == slot_b {
+ continue;
+ }
+ let conflict = Conflict {
+ span_o: Some(ctx.o.span(name.0)),
+ span_a: Some(ctx.a.span(*node_a)),
+ span_b: Some(ctx.b.span(*node_b)),
+ rule: "name-collision",
+ };
+ if !found.contains(&conflict) {
+ found.push(conflict);
+ }
+ }
+ }
+ }
+}
+
+/// A branch's named top-level insertions, keyed by the O parent they
+/// graft under plus the name text, valued by (slot, inserted node).
+fn insert_names<'t>(
+ tree: &'t Tree,
+ matching: &Matching,
+ script: &[Edit],
+) -> HashMap<(NodeId, &'t str), Vec<(Slot, NodeId)>> {
+ let mut names: HashMap<(NodeId, &'t str), Vec<(Slot, NodeId)>> = HashMap::new();
+ for edit in script {
+ let Edit::Insert(node) = edit else {
+ continue;
+ };
+ let Some(slot) = insert_anchor(tree, matching, *node) else {
+ continue;
+ };
+ let Some(name) = node_name(tree, *node) else {
+ continue;
+ };
+ names.entry((slot.0, name)).or_default().push((slot, *node));
+ }
+ names
+}
+
+/// The text of a node's `name` or `key` field child, if it has one.
+fn node_name(tree: &Tree, node: NodeId) -> Option<&str> {
+ let language = tree.lang().language();
+ tree.children(node).iter().find_map(|&child| {
+ let field = tree
+ .field_id(child)
+ .and_then(|fid| language.field_name_for_id(fid.get()))?;
+ if field == "name" || field == "key" {
+ tree.source_slice(tree.span(child))
+ } else {
+ None
+ }
+ })
+}
+
/// Groups a branch's top-level insertions by slot, in sibling order
/// (the edit script lists inserts in pre-order, so same-slot siblings
/// arrive left to right).
-fn insert_slots(
- tree: &Tree,
- matching: &Matching,
- script: &[Edit],
-) -> HashMap<(NodeId, Option<NodeId>), Vec<NodeId>> {
- let mut slots: HashMap<(NodeId, Option<NodeId>), Vec<NodeId>> = HashMap::new();
+fn insert_slots(tree: &Tree, matching: &Matching, script: &[Edit]) -> HashMap<Slot, Vec<NodeId>> {
+ let mut slots: HashMap<Slot, Vec<NodeId>> = HashMap::new();
for edit in script {
let Edit::Insert(node) = edit else {
continue;
@@ -387,15 +463,10 @@ fn covering_span(tree: &Tree, seq: &[NodeId]) -> Option<std::ops::Range<usize>>
Some(start..end)
}
-/// The slot an inserted node lands in: its parent's O preimage plus
-/// the O preimage of the nearest preceding matched sibling. `None`
-/// for nested insertions (their parent is inserted too — they ride
-/// along with the top-level graft).
-fn insert_anchor(
- tree: &Tree,
- matching: &Matching,
- node: NodeId,
-) -> Option<(NodeId, Option<NodeId>)> {
+/// The slot an inserted node lands in. `None` for nested insertions
+/// (their parent is inserted too — they ride along with the
+/// top-level graft).
+fn insert_anchor(tree: &Tree, matching: &Matching, node: NodeId) -> Option<Slot> {
let parent = tree.parent(node)?;
let parent_o = matching.preimage(parent)?;
let mut left = None;
diff --git a/tests/corpus/scenarios/name-collision-java/A.java b/tests/corpus/scenarios/name-collision-java/A.java
new file mode 100644
index 0000000..171c807
--- /dev/null
+++ b/tests/corpus/scenarios/name-collision-java/A.java
@@ -0,0 +1,3 @@
+class Config { int retries; }
+class App { }
+class Util { }
diff --git a/tests/corpus/scenarios/name-collision-java/B.java b/tests/corpus/scenarios/name-collision-java/B.java
new file mode 100644
index 0000000..118f8b7
--- /dev/null
+++ b/tests/corpus/scenarios/name-collision-java/B.java
@@ -0,0 +1,3 @@
+class App { }
+class Util { }
+class Config { boolean verbose; }
diff --git a/tests/corpus/scenarios/name-collision-java/O.java b/tests/corpus/scenarios/name-collision-java/O.java
new file mode 100644
index 0000000..29b4f91
--- /dev/null
+++ b/tests/corpus/scenarios/name-collision-java/O.java
@@ -0,0 +1,2 @@
+class App { }
+class Util { }
diff --git a/tests/corpus/scenarios/name-collision-java/expected.CONFLICT b/tests/corpus/scenarios/name-collision-java/expected.CONFLICT
new file mode 100644
index 0000000..2896baf
--- /dev/null
+++ b/tests/corpus/scenarios/name-collision-java/expected.CONFLICT
@@ -0,0 +1 @@
+name-collision
diff --git a/tests/corpus/scenarios/name-collision-json/A.json b/tests/corpus/scenarios/name-collision-json/A.json
new file mode 100644
index 0000000..7522cc0
--- /dev/null
+++ b/tests/corpus/scenarios/name-collision-json/A.json
@@ -0,0 +1,5 @@
+{
+ "timeout": 30,
+ "host": "localhost",
+ "port": 8080
+}
diff --git a/tests/corpus/scenarios/name-collision-json/B.json b/tests/corpus/scenarios/name-collision-json/B.json
new file mode 100644
index 0000000..3c956d2
--- /dev/null
+++ b/tests/corpus/scenarios/name-collision-json/B.json
@@ -0,0 +1,5 @@
+{
+ "host": "localhost",
+ "port": 8080,
+ "timeout": 60
+}
diff --git a/tests/corpus/scenarios/name-collision-json/O.json b/tests/corpus/scenarios/name-collision-json/O.json
new file mode 100644
index 0000000..156f7af
--- /dev/null
+++ b/tests/corpus/scenarios/name-collision-json/O.json
@@ -0,0 +1,4 @@
+{
+ "host": "localhost",
+ "port": 8080
+}
diff --git a/tests/corpus/scenarios/name-collision-json/expected.CONFLICT b/tests/corpus/scenarios/name-collision-json/expected.CONFLICT
new file mode 100644
index 0000000..2896baf
--- /dev/null
+++ b/tests/corpus/scenarios/name-collision-json/expected.CONFLICT
@@ -0,0 +1 @@
+name-collision