Merge concurrent insertions under commutative parents
The mergiraf comparison's top remaining gap: both branches adding imports, use declarations, type members, or object keys at one slot was an insert-insert conflict, though child order carries no meaning there. Each language now declares its commutative kinds, and same-slot insertion runs under them merge as a union, A's first. The union rests on element groups — a named node plus the separators and attributes prefixed to it. Raw per-node dedupe let one branch's comma absorb the other's mid-run, and a run ending in a separator or attribute (its target outside the run) cannot be unioned without changing what a branch wrote, so such runs still conflict. Three guards keep the union from going silently wrong: name-collision now covers shared slots by comparing whole element groups (two different `fn foo` at one slot must not both land, and an attributed insertion stays distinct from a bare one); a new duplicate-insert rule conflicts on identical nameless elements at different slots (a `use` inserted twice is a compile error name-collision cannot see); and the universality checker exempts anonymous separators under commutative parents, whose attribution is ambiguous once both branches contribute one — the parse itself pins how many the output needs. On mergiraf's 54-case example suite, correct outcomes go from 24 to 33 and conflicts-where-mergiraf-merges drop from 24 to 16. Assisted-by: Claude Fable 5 via Claude Code
diff --git a/src/check.rs b/src/check.rs
index 79d6e0b..09fb643 100644
--- a/src/check.rs
+++ b/src/check.rs
@@ -66,6 +66,9 @@ pub fn check(o: &Tree, a: &Tree, b: &Tree, m: &Tree) -> Report {
// 1. No extra insertion: every M node has a preimage under i1 or
// i2 — it came from somewhere.
for node in m.nodes() {
+ if fungible_separator(m, node) {
+ continue;
+ }
if i1.preimage(node).is_none() && i2.preimage(node).is_none() {
violations.push(Violation::ExtraInsertion {
node,
@@ -81,6 +84,9 @@ pub fn check(o: &Tree, a: &Tree, b: &Tree, m: &Tree) -> Report {
// 3. No extra deletion: an O node both branches kept must reach M
// through both routes, and the routes must agree (i1∘f = i2∘g).
for node in o.nodes() {
+ if fungible_separator(o, node) {
+ continue;
+ }
if let (Some(in_a), Some(in_b)) = (f.image(node), g.image(node)) {
let via_a = i1.image(in_a);
let via_b = i2.image(in_b);
@@ -97,6 +103,9 @@ pub fn check(o: &Tree, a: &Tree, b: &Tree, m: &Tree) -> Report {
// 4. No missed deletion: an O node one branch deleted must not
// sneak into M through the other branch.
for node in o.nodes() {
+ if fungible_separator(o, node) {
+ continue;
+ }
let reaches = match (f.image(node), g.image(node)) {
(None, Some(via)) => i2.image(via).is_some(),
(Some(via), None) => i1.image(via).is_some(),
@@ -116,6 +125,20 @@ pub fn check(o: &Tree, a: &Tree, b: &Tree, m: &Tree) -> Report {
}
}
+/// Anonymous tokens under a commutative parent are fungible
+/// separators, exempt from all four conditions. A cross-branch union
+/// merge makes their attribution ambiguous — both branches' commas
+/// legitimately claim the same merged comma, orphaning its twin — and
+/// the parse itself (verified before the conditions run) already pins
+/// how many separators the output holds. Named nodes under the same
+/// parent stay fully checked.
+fn fungible_separator(tree: &Tree, node: NodeId) -> bool {
+ !tree.is_named(node)
+ && tree
+ .parent(node)
+ .is_some_and(|parent| tree.lang().is_commutative(tree.kind(parent)))
+}
+
/// Condition 2 for one branch: nodes the branch inserted (no preimage
/// under its diff from O) must have an image in M.
fn missed_insertions(
@@ -126,6 +149,9 @@ fn missed_insertions(
violations: &mut Vec<Violation>,
) {
for node in branch_tree.nodes() {
+ if fungible_separator(branch_tree, node) {
+ continue;
+ }
if from_o.preimage(node).is_none() && to_m.image(node).is_none() {
violations.push(Violation::MissedInsertion {
branch,
@@ -271,4 +297,62 @@ mod tests {
assert!(report.is_correct());
Ok(())
}
+
+ #[test]
+ fn union_merged_separators_are_not_extra_insertions() -> Result<(), Error> {
+ // Each branch adds one entry, each with its comma. The two
+ // matchings into M are derived independently, so both commas
+ // can claim the same merged comma, orphaning its twin; the
+ // fungible-separator exemption keeps that from flagging.
+ let report = check_json(
+ r#"{"a": 1}"#,
+ r#"{"a": 1, "b": 2}"#,
+ r#"{"a": 1, "c": 3}"#,
+ r#"{"a": 1, "b": 2, "c": 3}"#,
+ )?;
+ assert_eq!(report.violations, Vec::new());
+ assert!(report.is_correct());
+ Ok(())
+ }
+
+ #[test]
+ fn named_nodes_under_commutative_parents_stay_checked() -> Result<(), Error> {
+ // The exemption covers anonymous separators only: an invented
+ // pair inside the object still flags.
+ let report = check_json(
+ r#"{"a": 1}"#,
+ r#"{"a": 1, "b": 2}"#,
+ r#"{"a": 1}"#,
+ r#"{"a": 1, "b": 2, "d": 4}"#,
+ )?;
+ assert!(!report.violations.is_empty());
+ assert!(report.violations.iter().any(|v| match v {
+ Violation::ExtraInsertion { span, .. } => {
+ let m = parse_json(r#"{"a": 1, "b": 2, "d": 4}"#);
+ m.is_ok_and(|m| {
+ m.source_slice(span.clone())
+ .is_some_and(|s| s.contains("4"))
+ })
+ }
+ _ => false,
+ }));
+ Ok(())
+ }
+
+ #[test]
+ fn separators_under_non_commutative_parents_stay_checked() -> Result<(), Error> {
+ // An array is not commutative, so a merge that loses an
+ // element (and its comma) both branches kept flags the comma
+ // too — the exemption must not reach it.
+ let report = check_json("[1, 2]", "[1, 2]", "[1, 2]", "[1]")?;
+ let flags_comma = report.violations.iter().any(|v| match v {
+ Violation::ExtraDeletion { span, .. } => {
+ let o = parse_json("[1, 2]");
+ o.is_ok_and(|o| o.source_slice(span.clone()) == Some(","))
+ }
+ _ => false,
+ });
+ assert!(flags_comma, "{:?}", report.violations);
+ Ok(())
+ }
}
diff --git a/src/lang.rs b/src/lang.rs
index f84fdad..46c2e72 100644
--- a/src/lang.rs
+++ b/src/lang.rs
@@ -14,6 +14,8 @@ pub struct Lang {
name: &'static str,
language: tree_sitter::Language,
node_types: NodeTypes,
+ commutative: &'static [&'static str],
+ binds_forward: &'static [&'static str],
}
impl Lang {
@@ -59,7 +61,33 @@ impl Lang {
&self.node_types
}
- fn new(name: &'static str, language: tree_sitter::Language, node_types_json: &str) -> Self {
+ /// Whether children of `kind` are order-insensitive: imports, use
+ /// declarations, top-level items, type members, JSON object
+ /// entries. Concurrent insertions at one slot under such a parent
+ /// merge as a union instead of conflicting. Kinds whose child
+ /// order carries meaning (statement blocks, arrays, parameter
+ /// lists) must stay off this list.
+ pub fn is_commutative(&self, kind: &str) -> bool {
+ self.commutative.contains(&kind)
+ }
+
+ /// Whether a node of `kind` semantically attaches to the sibling
+ /// that follows it — a Rust attribute governs the next item even
+ /// though the tree makes them siblings. Merging must not splice
+ /// other content between such a node and its target: a union merge
+ /// interleaving another branch's insertions would silently move
+ /// the attribute onto someone else's code.
+ pub fn binds_forward(&self, kind: &str) -> bool {
+ self.binds_forward.contains(&kind)
+ }
+
+ fn new(
+ name: &'static str,
+ language: tree_sitter::Language,
+ node_types_json: &str,
+ commutative: &'static [&'static str],
+ binds_forward: &'static [&'static str],
+ ) -> Self {
// `node_types_json` is the grammar crate's own bundled NODE_TYPES
// constant, not external input — a parse failure here means the
// grammar crate shipped malformed JSON, a build-time invariant
@@ -71,6 +99,8 @@ impl Lang {
name,
language,
node_types,
+ commutative,
+ binds_forward,
}
}
}
@@ -80,6 +110,16 @@ static RUST: LazyLock<Lang> = LazyLock::new(|| {
"rust",
tree_sitter_rust::LANGUAGE.into(),
tree_sitter_rust::NODE_TYPES,
+ // declaration_list is mod/impl/trait bodies; struct fields and
+ // enum variants stay ordered (layout and discriminants).
+ &[
+ "source_file",
+ "declaration_list",
+ "use_list",
+ "trait_bounds",
+ ],
+ // An outer attribute governs the item that follows it.
+ &["attribute_item"],
)
});
@@ -88,6 +128,20 @@ static JAVA: LazyLock<Lang> = LazyLock::new(|| {
"java",
tree_sitter_java::LANGUAGE.into(),
tree_sitter_java::NODE_TYPES,
+ // program covers package/import/type declarations; type_list
+ // is implements/permits clauses and throws is checked
+ // exceptions — order carries no meaning in either. Enum bodies
+ // stay ordered (ordinal values).
+ &[
+ "program",
+ "class_body",
+ "interface_body",
+ "type_list",
+ "throws",
+ ],
+ // Java annotations live inside the declaration they annotate,
+ // not beside it, so nothing binds forward.
+ &[],
)
});
@@ -96,6 +150,9 @@ static JSON: LazyLock<Lang> = LazyLock::new(|| {
"json",
tree_sitter_json::LANGUAGE.into(),
tree_sitter_json::NODE_TYPES,
+ // Objects only: array order is data.
+ &["object"],
+ &[],
)
});
@@ -360,6 +417,32 @@ mod tests {
assert!(node_kind_count.is_some_and(|count| count > 0));
}
+ #[test]
+ fn commutative_parents_are_per_language() {
+ let commutative = |lang: &str, kind: &str| {
+ Lang::by_name(lang).is_some_and(|lang| lang.is_commutative(kind))
+ };
+ assert!(commutative("rust", "source_file"));
+ assert!(commutative("rust", "use_list"));
+ assert!(commutative("rust", "trait_bounds"));
+ assert!(!commutative("rust", "block"));
+ assert!(commutative("java", "class_body"));
+ assert!(commutative("java", "type_list"));
+ assert!(!commutative("java", "block"));
+ assert!(commutative("json", "object"));
+ assert!(!commutative("json", "array"));
+ }
+
+ #[test]
+ fn forward_binding_kinds_are_per_language() {
+ let binds = |lang: &str, kind: &str| {
+ Lang::by_name(lang).is_some_and(|lang| lang.binds_forward(kind))
+ };
+ assert!(binds("rust", "attribute_item"));
+ assert!(!binds("rust", "function_item"));
+ assert!(!binds("java", "annotation"));
+ }
+
#[test]
fn unknown_kind_has_no_fields_or_metadata() {
let lang = Lang::by_name("rust");
diff --git a/src/merge.rs b/src/merge.rs
index 6306ccd..3ae5bf6 100644
--- a/src/merge.rs
+++ b/src/merge.rs
@@ -288,14 +288,6 @@ enum Branch {
B,
}
-/// A graft placed in a slot: its subtree hash for cross-branch dedupe
-/// and whether it can still absorb a duplicate B insertion.
-struct SlotEntry {
- hash: u64,
- id: MergedId,
- dedupes_b: bool,
-}
-
struct Builder<'t> {
o: &'t Tree,
a: &'t Tree,
@@ -335,57 +327,68 @@ impl Builder<'_> {
let base_position: HashMap<NodeId, usize> =
base.iter().enumerate().map(|(i, &c)| (c, i)).collect();
- // Slots: grafts landing before base[i] live in slots[i]; the
- // final slot holds end-of-list grafts. Each graft records its
- // subtree hash so an identical B insertion in the same slot
- // dedupes against A's.
- let mut slots: Vec<Vec<SlotEntry>> = Vec::new();
- slots.resize_with(base.len().saturating_add(1), Vec::new);
+ // Slots: grafts landing before base[i] live in runs[i]; the
+ // final slot holds end-of-list grafts. Each branch's inserted
+ // runs are collected first so cross-branch dedupe can compare
+ // whole runs, then grafted A before B — within a shared slot
+ // A's insertions come first.
+ let slot_count = base.len().saturating_add(1);
+ let collect = |builder: &Self, branch, image: Option<NodeId>| match image {
+ Some(image) => builder.insert_runs(branch, image, &base_position, slot_count),
+ None => vec![Vec::new(); slot_count], // cov-excl-line: survivors have images in both branches.
+ };
+ let runs_a = collect(self, Branch::A, in_a);
+ let runs_b = collect(self, Branch::B, in_b);
+ let kept_b: Vec<Vec<NodeId>> = runs_a
+ .iter()
+ .zip(&runs_b)
+ .map(|(run_a, run_b)| self.dedupe_run(run_a, run_b))
+ .collect();
- if let Some(ya) = in_a {
- self.graft_branch(Branch::A, ya, &base_position, &mut slots);
- }
- if let Some(yb) = in_b {
- self.graft_branch(Branch::B, yb, &base_position, &mut slots);
- }
+ let graft_all = |builder: &mut Self, branch, runs: &[Vec<NodeId>]| -> Vec<Vec<MergedId>> {
+ runs.iter()
+ .map(|run| run.iter().map(|&n| builder.graft(branch, n)).collect())
+ .collect()
+ };
+ let grafted_a = graft_all(self, Branch::A, &runs_a);
+ let grafted_b = graft_all(self, Branch::B, &kept_b);
// Materialize: slot grafts, then the base survivor they
- // precede. Slots are sized base.len()+1, so the indexing below
+ // precede. Runs are sized base.len()+1, so the indexing below
// stays in bounds.
let mut children: Vec<MergedId> = Vec::new();
#[allow(clippy::indexing_slicing)]
for (i, &c) in base.iter().enumerate() {
- children.extend(slots[i].iter().map(|entry| entry.id));
+ children.extend(&grafted_a[i]);
+ children.extend(&grafted_b[i]);
if !self.consumed.contains(&c) {
children.push(self.build_survivor(c));
}
}
#[allow(clippy::indexing_slicing)]
- children.extend(slots[base.len()].iter().map(|entry| entry.id));
+ {
+ children.extend(&grafted_a[base.len()]);
+ children.extend(&grafted_b[base.len()]);
+ }
self.push(MergedNode { origin, children })
}
- /// Walks one branch image's children, grafting insertions into the
- /// slot after the nearest preceding child whose preimage sits in
- /// the base.
- ///
- /// Dedupe is cross-branch only: a B insertion equal (by subtree
- /// hash) to an A insertion in the same slot is the same edit made
- /// twice and lands once, but one branch inserting two equal
- /// subtrees is two real insertions. Each A entry can absorb at
- /// most one B duplicate so multiplicities still add up.
- fn graft_branch(
- &mut self,
+ /// Walks one branch image's children, collecting insertions into
+ /// the slot after the nearest preceding child whose preimage sits
+ /// in the base.
+ fn insert_runs(
+ &self,
branch: Branch,
parent_image: NodeId,
base_position: &HashMap<NodeId, usize>,
- slots: &mut [Vec<SlotEntry>],
- ) {
+ slot_count: usize,
+ ) -> Vec<Vec<NodeId>> {
let (tree, matching) = match branch {
Branch::A => (self.a, self.f),
Branch::B => (self.b, self.g),
};
+ let mut runs: Vec<Vec<NodeId>> = vec![Vec::new(); slot_count];
let mut cursor = 0usize;
for &child in tree.children(parent_image) {
match matching.preimage(child) {
@@ -395,25 +398,65 @@ impl Builder<'_> {
}
}
None => {
- let hash = tree.hash(child);
- // Cursor is at most base.len(); slots has one more.
+ // Cursor is at most base.len(); runs has one more.
#[allow(clippy::indexing_slicing)]
- let slot = &mut slots[cursor];
- if matches!(branch, Branch::B)
- && let Some(twin) = slot
- .iter_mut()
- .find(|entry| entry.dedupes_b && entry.hash == hash)
- {
- twin.dedupes_b = false;
- continue;
+ runs[cursor].push(child);
+ }
+ }
+ }
+ runs
+ }
+
+ /// B's insertions in one slot that survive cross-branch dedupe
+ /// against A's. An equal run is the same edit made twice and lands
+ /// zero of B's nodes. Differing runs dedupe element-group-wise —
+ /// each A group absorbs at most one equal B group so
+ /// multiplicities still add up, and the groups B alone inserted
+ /// survive; this is what merges two branches' insertions under a
+ /// commutative parent. Runs that do not decompose into groups fall
+ /// back to per-node dedupe (equal separators must not absorb one
+ /// another mid-run, but such runs only co-occur in a slot when the
+ /// anchor was deleted, where per-node matching is the old, safe
+ /// behavior). Either way an equal run dedupes completely.
+ fn dedupe_run(&self, run_a: &[NodeId], run_b: &[NodeId]) -> Vec<NodeId> {
+ let hashes = |tree: &Tree, nodes: &[NodeId]| -> Vec<u64> {
+ nodes.iter().map(|&n| tree.hash(n)).collect()
+ };
+ match (
+ rules::element_groups(self.a, run_a),
+ rules::element_groups(self.b, run_b),
+ ) {
+ (Some(groups_a), Some(groups_b)) => {
+ let mut available: Vec<Vec<u64>> =
+ groups_a.iter().map(|group| hashes(self.a, group)).collect();
+ let mut kept = Vec::new();
+ for group in groups_b {
+ let group_hashes = hashes(self.b, &group);
+ match available.iter().position(|twin| *twin == group_hashes) {
+ Some(i) => {
+ available.swap_remove(i);
+ }
+ None => kept.extend(group),
}
- let id = self.graft(branch, child);
- slot.push(SlotEntry {
- hash,
- id,
- dedupes_b: matches!(branch, Branch::A),
- });
}
+ kept
+ }
+ _ => {
+ let mut available = hashes(self.a, run_a);
+ run_b
+ .iter()
+ .copied()
+ .filter(|&node| {
+ let hash = self.b.hash(node);
+ match available.iter().position(|&twin| twin == hash) {
+ Some(i) => {
+ available.swap_remove(i);
+ false
+ }
+ None => true,
+ }
+ })
+ .collect()
}
}
}
@@ -1177,6 +1220,281 @@ mod tests {
)
}
+ #[test]
+ fn concurrent_insertions_under_a_commutative_parent_merge() -> Result<(), Error> {
+ // Both branches add a use declaration at the same slot; item
+ // order carries no meaning at the top level, so the runs merge
+ // as a union, A's first.
+ assert_merges(
+ "rust",
+ "use a;\nfn main() {}",
+ "use a;\nuse b;\nfn main() {}",
+ "use a;\nuse c;\nfn main() {}",
+ "use a;\nuse b;\nuse c;\nfn main() {}",
+ )?;
+ // The same for JSON object entries, where each run carries its
+ // separator: the commas travel with their pairs.
+ assert_merges(
+ "json",
+ r#"{"a": 1}"#,
+ r#"{"a": 1, "b": 2}"#,
+ r#"{"a": 1, "c": 3}"#,
+ r#"{"a": 1, "b": 2, "c": 3}"#,
+ )?;
+ // And for members of a Java class body.
+ assert_merges(
+ "java",
+ "class C { void a() { } }",
+ "class C { void a() { } void b() { } }",
+ "class C { void a() { } void c() { } }",
+ "class C { void a() { } void b() { } void c() { } }",
+ )
+ }
+
+ #[test]
+ fn bound_and_interface_lists_union_too() -> Result<(), Error> {
+ // Trait bounds and implements clauses are commutative: each
+ // branch's addition carries its separator, and order carries
+ // no meaning.
+ assert_merges(
+ "rust",
+ "fn f<T: Clone>() {}",
+ "fn f<T: Clone + Send>() {}",
+ "fn f<T: Clone + Sync>() {}",
+ "fn f<T: Clone + Send + Sync>() {}",
+ )?;
+ assert_merges(
+ "java",
+ "class C implements Foo { }",
+ "class C implements Foo, Bar { }",
+ "class C implements Foo, Baz { }",
+ "class C implements Foo, Bar, Baz { }",
+ )
+ }
+
+ #[test]
+ fn overlapping_commutative_insertions_dedupe_element_wise() -> Result<(), Error> {
+ // Both branches add `use c;`; each also adds its own. The
+ // shared element lands once, group-wise — its separator
+ // dedupes with it instead of being absorbed by an unrelated
+ // twin mid-run.
+ assert_merges(
+ "rust",
+ "use a;\nfn main() {}",
+ "use a;\nuse c;\nuse d;\nfn main() {}",
+ "use a;\nuse c;\nuse e;\nfn main() {}",
+ "use a;\nuse c;\nuse d;\nuse e;\nfn main() {}",
+ )?;
+ assert_merges(
+ "json",
+ r#"{"a": 1}"#,
+ r#"{"a": 1, "k": 9, "b": 2}"#,
+ r#"{"a": 1, "k": 9, "c": 3}"#,
+ r#"{"a": 1, "k": 9, "b": 2, "c": 3}"#,
+ )
+ }
+
+ #[test]
+ fn commutative_insertions_at_different_slots_merge() -> Result<(), Error> {
+ // No shared slot, nothing identical: both land where anchored.
+ // The comma each branch carries is a separator, not a
+ // duplicate element — duplicate-insert must stay silent.
+ assert_merges(
+ "json",
+ r#"{"a": 1, "z": 9}"#,
+ r#"{"a": 1, "b": 2, "z": 9}"#,
+ r#"{"a": 1, "z": 9, "c": 3}"#,
+ r#"{"a": 1, "b": 2, "z": 9, "c": 3}"#,
+ )
+ }
+
+ #[test]
+ fn same_named_commutative_insertions_at_one_slot_conflict() -> Result<(), Error> {
+ // Without name-collision covering the shared slot, the union
+ // merge would emit two `fn foo` definitions.
+ assert_conflicts(
+ "rust",
+ "fn main() {}",
+ "fn main() {}\nfn foo() { a(); }",
+ "fn main() {}\nfn foo() { b(); }",
+ "name-collision",
+ )?;
+ // Identical same-named insertions dedupe instead.
+ assert_merges(
+ "rust",
+ "fn main() {}",
+ "fn main() {}\nfn foo() { a(); }",
+ "fn main() {}\nfn foo() { a(); }",
+ "fn main() {}\nfn foo() { a(); }",
+ )
+ }
+
+ #[test]
+ fn an_attributed_insertion_unions_as_one_element() -> Result<(), Error> {
+ // A's attribute travels with the function it governs, so the
+ // union keeps them adjacent and B's insertion lands after.
+ assert_merges(
+ "rust",
+ "mod m {\n pub fn run() {}\n}\n",
+ "mod m {\n #[inline]\n pub fn setup() {}\n\n pub fn run() {}\n}\n",
+ "mod m {\n pub fn teardown() {}\n\n pub fn run() {}\n}\n",
+ "mod m {\n #[inline]\n pub fn setup() {}\n\n pub fn teardown() {}\n\n pub fn run() {}\n}\n",
+ )
+ }
+
+ #[test]
+ fn a_trailing_attribute_blocks_the_union() -> Result<(), Error> {
+ // A attributes the *surviving* function below the slot, so its
+ // inserted run ends with the attribute; splicing B's insertion
+ // in between would silently move the attribute onto B's code.
+ assert_conflicts(
+ "rust",
+ "mod m {\n pub fn run() {}\n}\n",
+ "mod m {\n pub fn setup() {}\n\n #[cfg(test)]\n pub fn run() {}\n}\n",
+ "mod m {\n pub fn teardown() {}\n\n pub fn run() {}\n}\n",
+ "insert-insert",
+ )?;
+ Ok(())
+ }
+
+ #[test]
+ fn an_attributed_and_a_bare_insertion_of_one_name_conflict() -> Result<(), Error> {
+ // The named nodes hash equal but the element groups differ, so
+ // the builder would land both copies; name-collision must
+ // compare groups, not names alone.
+ assert_conflicts(
+ "rust",
+ "fn main() {}\n",
+ "fn main() {}\n#[inline]\nfn helper() {}\n",
+ "fn main() {}\nfn helper() {}\n",
+ "name-collision",
+ )?;
+ Ok(())
+ }
+
+ #[test]
+ fn identical_nameless_insertions_at_different_slots_conflict() -> Result<(), Error> {
+ // Use declarations carry no name field, so name-collision is
+ // blind to them; without duplicate-insert the union would land
+ // `use c;` twice — a compile error neither branch wrote.
+ assert_conflicts(
+ "rust",
+ "use a;\nuse b;\n\nfn main() {}\n",
+ "use c;\nuse a;\nuse b;\n\nfn main() {}\n",
+ "use a;\nuse b;\nuse c;\n\nfn main() {}\n",
+ "duplicate-insert",
+ )?;
+ Ok(())
+ }
+
+ #[test]
+ fn commutative_insertions_with_trailing_separators_conflict() -> Result<(), Error> {
+ // Prepending into an object leaves each run's comma trailing
+ // (`"b": 2` then `,`); a union would need a separator neither
+ // branch wrote, so this stays an insert-insert conflict.
+ assert_conflicts(
+ "json",
+ r#"{"z": 0}"#,
+ r#"{"b": 2, "z": 0}"#,
+ r#"{"c": 3, "z": 0}"#,
+ "insert-insert",
+ )?;
+ Ok(())
+ }
+
+ #[test]
+ fn ungroupable_runs_fall_back_to_per_node_dedupe() -> Result<(), Error> {
+ // dedupe_run's fallback, driven directly: no rule-clean merge
+ // reaches it without a slot-anchor mismatch between the rules
+ // and the builder. A run ending in a separator cannot group;
+ // per-node matching still dedupes B's comma against A's and
+ // keeps the value A never inserted.
+ let o = parse("[1]", "json")?;
+ let a = parse("[1, 2]", "json")?;
+ let b = parse("[1, 3]", "json")?;
+ let f = diff(&o, &a);
+ let g = diff(&o, &b);
+ let builder = Builder {
+ o: &o,
+ a: &a,
+ b: &b,
+ f: &f,
+ g: &g,
+ nodes: Vec::new(),
+ placed: HashSet::new(),
+ consumed: HashSet::new(),
+ };
+ let comma_and = |tree: &Tree, digit: &str| -> Vec<NodeId> {
+ let comma = tree.nodes().find(|&n| tree.kind(n) == ",");
+ let value = tree.nodes().find(|&n| tree.label(n) == Some(digit));
+ match (comma, value) {
+ (Some(comma), Some(value)) => vec![comma, value],
+ _ => panic!("array literal parses"),
+ }
+ };
+ // A's run is comma-only (ungroupable); B's comma dedupes
+ // against it per-node and B's value survives.
+ let run_a: Vec<NodeId> = comma_and(&a, "2").first().copied().into_iter().collect();
+ let run_b = comma_and(&b, "3");
+ let kept = builder.dedupe_run(&run_a, &run_b);
+ assert_eq!(kept.len(), 1);
+ assert_eq!(kept.first().map(|&n| b.label(n)), Some(Some("3")));
+ Ok(())
+ }
+
+ #[test]
+ fn element_groups_split_on_named_nodes() -> Result<(), Error> {
+ // A run of [comma value comma value] groups pairwise; a run
+ // with a trailing separator does not group at all.
+ let tree = parse("[1, 2, 3]", "json")?;
+ let array = tree
+ .nodes()
+ .find(|&n| tree.kind(n) == "array")
+ .unwrap_or(tree.root());
+ let children = tree.children(array);
+ // children: [ 1 , 2 , 3 ] — drop the brackets.
+ let interior = children
+ .get(1..children.len().saturating_sub(1))
+ .unwrap_or(&[]);
+ let groups = crate::rules::element_groups(&tree, interior);
+ assert_eq!(
+ groups.as_ref().map(Vec::len),
+ Some(3),
+ "1 | ,2 | ,3: {groups:?}"
+ );
+ // Trailing comma (no closing element) refuses to group.
+ let trailing = children
+ .get(1..children.len().saturating_sub(2))
+ .unwrap_or(&[]);
+ assert_eq!(crate::rules::element_groups(&tree, trailing), None);
+ Ok(())
+ }
+
+ #[test]
+ fn element_groups_attach_attributes_to_the_next_item() -> Result<(), Error> {
+ // An attribute is a forward-binding prefix: it joins the
+ // following item's group, and a run it ends refuses to group.
+ let tree = parse("#[inline]\nfn f() {}\nfn g() {}", "rust")?;
+ let children = tree.children(tree.root());
+ // [attribute_item, function_item, function_item]
+ let groups = crate::rules::element_groups(&tree, children);
+ assert_eq!(
+ groups.as_ref().map(Vec::len),
+ Some(2),
+ "attr+f | g: {groups:?}"
+ );
+ assert_eq!(
+ groups.as_ref().and_then(|g| g.first()).map(Vec::len),
+ Some(2)
+ );
+ // A run ending in the attribute (its target elsewhere) refuses
+ // to group.
+ let mut trailing: Vec<NodeId> = children.get(1..).unwrap_or(&[]).to_vec();
+ trailing.extend(children.first());
+ assert_eq!(crate::rules::element_groups(&tree, &trailing), None);
+ Ok(())
+ }
+
#[test]
fn a_wrap_pulls_the_survivor_into_the_graft() -> Result<(), Error> {
// A wraps the array one level deeper; B leaves it alone.
diff --git a/src/rules.rs b/src/rules.rs
index 920ab33..6d15da2 100644
--- a/src/rules.rs
+++ b/src/rules.rs
@@ -51,6 +51,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);
+ duplicate_insert(ctx, edits_a, edits_b, &mut found);
delete_delete(ctx, edits_a, edits_b, &mut found);
found
}
@@ -340,6 +341,14 @@ fn node_satisfies(
/// parent image, same nearest preceding matched sibling — but the
/// inserted subtree sequences differ. Equal sequences at the same
/// slot are one edit made twice and dedupe instead.
+///
+/// Under a commutative parent (imports, use declarations, type
+/// members, JSON object entries) differing sequences are no conflict
+/// either: child order carries no meaning there, so the builder
+/// merges the two runs as a union — provided both runs decompose into
+/// element groups. A run that does not (a trailing separator, or a
+/// trailing attribute with its target outside the run) cannot be
+/// unioned without breaking what a branch wrote.
fn insert_insert(ctx: &Ctx, edits_a: &[Edit], edits_b: &[Edit], found: &mut Vec<Conflict>) {
let slots_a = insert_slots(ctx.a, ctx.f, edits_a);
let slots_b = insert_slots(ctx.b, ctx.g, edits_b);
@@ -353,6 +362,12 @@ fn insert_insert(ctx: &Ctx, edits_a: &[Edit], edits_b: &[Edit], found: &mut Vec<
if hashes(ctx.a, seq_a) == hashes(ctx.b, seq_b) {
continue;
}
+ if ctx.o.lang().is_commutative(ctx.o.kind(anchor.0))
+ && element_groups(ctx.a, seq_a).is_some()
+ && element_groups(ctx.b, seq_b).is_some()
+ {
+ continue;
+ }
let conflict = Conflict {
span_o: Some(ctx.o.span(anchor.0)),
span_a: covering_span(ctx.a, seq_a),
@@ -374,18 +389,33 @@ fn insert_insert(ctx: &Ctx, edits_a: &[Edit], edits_b: &[Edit], found: &mut Vec<
/// `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.
+/// Same-slot pairs are skipped under a non-commutative parent (equal
+/// sequences dedupe and unequal ones are already insert-insert
+/// conflicts); under a commutative parent unequal sequences merge, so
+/// two same-named insertions must conflict here — unless their whole
+/// element groups are equal, which is exactly what the builder's
+/// dedupe merges into one copy. Comparing groups rather than the
+/// named nodes alone keeps an attributed insertion distinct from a
+/// bare one.
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);
+ let slots_a = insert_slots(ctx.a, ctx.f, edits_a);
+ let slots_b = insert_slots(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 {
+ if slot_a == slot_b
+ && (!ctx.o.lang().is_commutative(ctx.o.kind(slot_a.0))
+ || dedupes_together(
+ (ctx.a, &slots_a, *node_a),
+ (ctx.b, &slots_b, *node_b),
+ slot_a,
+ ))
+ {
continue;
}
let conflict = Conflict {
@@ -402,6 +432,83 @@ fn name_collision(ctx: &Ctx, edits_a: &[Edit], edits_b: &[Edit], found: &mut Vec
}
}
+/// Whether two same-slot insertions sit in equal element groups, so
+/// the builder's group-wise dedupe merges them into one copy.
+fn dedupes_together(
+ a: (&Tree, &HashMap<Slot, Vec<NodeId>>, NodeId),
+ b: (&Tree, &HashMap<Slot, Vec<NodeId>>, NodeId),
+ slot: &Slot,
+) -> bool {
+ let group_hashes = |(tree, slots, node): (&Tree, &HashMap<Slot, Vec<NodeId>>, NodeId)| {
+ let run = slots.get(slot)?;
+ let groups = element_groups(tree, run)?;
+ let group = groups.into_iter().find(|group| group.contains(&node))?;
+ Some(
+ group
+ .iter()
+ .map(|&member| tree.hash(member))
+ .collect::<Vec<u64>>(),
+ )
+ };
+ let hashes_a = group_hashes(a);
+ hashes_a.is_some() && hashes_a == group_hashes(b)
+}
+
+/// duplicate-insert: both branches inserted the identical nameless
+/// element — a use declaration, an import — under the same
+/// commutative O parent at different slots. Cross-branch dedupe only
+/// merges grafts sharing a slot and name-collision only sees elements
+/// with a `name`/`key` field, so without this rule the union merge
+/// silently lands the element twice. Separators are excluded (every
+/// comma equals every other comma); named elements are
+/// name-collision's domain.
+fn duplicate_insert(ctx: &Ctx, edits_a: &[Edit], edits_b: &[Edit], found: &mut Vec<Conflict>) {
+ let elements = |tree: &Tree, matching: &Matching, script: &[Edit]| {
+ let mut map: HashMap<(NodeId, u64), Vec<(Slot, NodeId)>> = HashMap::new();
+ for edit in script {
+ let Edit::Insert(node) = edit else {
+ continue;
+ };
+ if !tree.is_named(*node) || node_name(tree, *node).is_some() {
+ continue;
+ }
+ let Some(slot) = insert_anchor(tree, matching, *node) else {
+ continue;
+ };
+ if !ctx.o.lang().is_commutative(ctx.o.kind(slot.0)) {
+ continue;
+ }
+ map.entry((slot.0, tree.hash(*node)))
+ .or_default()
+ .push((slot, *node));
+ }
+ map
+ };
+ let elements_a = elements(ctx.a, ctx.f, edits_a);
+ let elements_b = elements(ctx.b, ctx.g, edits_b);
+ for (key, inserts_a) in &elements_a {
+ let Some(inserts_b) = elements_b.get(key) 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(key.0)),
+ span_a: Some(ctx.a.span(*node_a)),
+ span_b: Some(ctx.b.span(*node_b)),
+ rule: "duplicate-insert",
+ };
+ 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>(
@@ -456,6 +563,27 @@ fn insert_slots(tree: &Tree, matching: &Matching, script: &[Edit]) -> HashMap<Sl
slots
}
+/// Splits an inserted run into element groups: each group is a named
+/// node together with the anonymous separators and forward-binding
+/// prefixes preceding it (a JSON insertion is `, "k": v` — the comma
+/// travels with its pair; a Rust `#[attr]` travels with the item it
+/// governs). `None` when trailing prefix nodes remain: a separator
+/// with no element cannot participate in a union merge, and a
+/// trailing attribute governs something *outside* the run, which a
+/// union would displace. Group-wise dedupe in the builder relies on
+/// the same decomposition.
+pub(crate) fn element_groups(tree: &Tree, run: &[NodeId]) -> Option<Vec<Vec<NodeId>>> {
+ let mut groups = Vec::new();
+ let mut current = Vec::new();
+ for &node in run {
+ current.push(node);
+ if tree.is_named(node) && !tree.lang().binds_forward(tree.kind(node)) {
+ groups.push(std::mem::take(&mut current));
+ }
+ }
+ current.is_empty().then_some(groups)
+}
+
/// The byte range covering a sequence of nodes.
fn covering_span(tree: &Tree, seq: &[NodeId]) -> Option<std::ops::Range<usize>> {
let start = seq.iter().map(|&n| tree.span(n).start).min()?;
diff --git a/tests/corpus/scenarios/attribute-splice/A.rs b/tests/corpus/scenarios/attribute-splice/A.rs
new file mode 100644
index 0000000..3ba77cf
--- /dev/null
+++ b/tests/corpus/scenarios/attribute-splice/A.rs
@@ -0,0 +1,6 @@
+mod m {
+ pub fn setup() {}
+
+ #[cfg(test)]
+ pub fn run() {}
+}
diff --git a/tests/corpus/scenarios/attribute-splice/B.rs b/tests/corpus/scenarios/attribute-splice/B.rs
new file mode 100644
index 0000000..c21c33d
--- /dev/null
+++ b/tests/corpus/scenarios/attribute-splice/B.rs
@@ -0,0 +1,5 @@
+mod m {
+ pub fn teardown() {}
+
+ pub fn run() {}
+}
diff --git a/tests/corpus/scenarios/attribute-splice/O.rs b/tests/corpus/scenarios/attribute-splice/O.rs
new file mode 100644
index 0000000..e0f7e5a
--- /dev/null
+++ b/tests/corpus/scenarios/attribute-splice/O.rs
@@ -0,0 +1,3 @@
+mod m {
+ pub fn run() {}
+}
diff --git a/tests/corpus/scenarios/attribute-splice/expected.CONFLICT b/tests/corpus/scenarios/attribute-splice/expected.CONFLICT
new file mode 100644
index 0000000..8ea65cd
--- /dev/null
+++ b/tests/corpus/scenarios/attribute-splice/expected.CONFLICT
@@ -0,0 +1 @@
+insert-insert
diff --git a/tests/corpus/scenarios/commutative-imports-java/A.java b/tests/corpus/scenarios/commutative-imports-java/A.java
new file mode 100644
index 0000000..607d6c7
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-imports-java/A.java
@@ -0,0 +1,7 @@
+import a.A;
+import b.B;
+
+class C {
+ void a() { }
+ void b() { }
+}
diff --git a/tests/corpus/scenarios/commutative-imports-java/B.java b/tests/corpus/scenarios/commutative-imports-java/B.java
new file mode 100644
index 0000000..026cd27
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-imports-java/B.java
@@ -0,0 +1,7 @@
+import a.A;
+import c.D;
+
+class C {
+ void a() { }
+ void c() { }
+}
diff --git a/tests/corpus/scenarios/commutative-imports-java/O.java b/tests/corpus/scenarios/commutative-imports-java/O.java
new file mode 100644
index 0000000..0ab8fbe
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-imports-java/O.java
@@ -0,0 +1,5 @@
+import a.A;
+
+class C {
+ void a() { }
+}
diff --git a/tests/corpus/scenarios/commutative-imports-java/expected.java b/tests/corpus/scenarios/commutative-imports-java/expected.java
new file mode 100644
index 0000000..7526f83
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-imports-java/expected.java
@@ -0,0 +1,9 @@
+import a.A;
+import b.B;
+import c.D;
+
+class C {
+ void a() { }
+ void b() { }
+ void c() { }
+}
diff --git a/tests/corpus/scenarios/commutative-name-collision/A.rs b/tests/corpus/scenarios/commutative-name-collision/A.rs
new file mode 100644
index 0000000..4f07687
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-name-collision/A.rs
@@ -0,0 +1,5 @@
+fn main() {}
+
+fn helper() {
+ a();
+}
diff --git a/tests/corpus/scenarios/commutative-name-collision/B.rs b/tests/corpus/scenarios/commutative-name-collision/B.rs
new file mode 100644
index 0000000..59bbd34
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-name-collision/B.rs
@@ -0,0 +1,5 @@
+fn main() {}
+
+fn helper() {
+ b();
+}
diff --git a/tests/corpus/scenarios/commutative-name-collision/O.rs b/tests/corpus/scenarios/commutative-name-collision/O.rs
new file mode 100644
index 0000000..f328e4d
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-name-collision/O.rs
@@ -0,0 +1 @@
+fn main() {}
diff --git a/tests/corpus/scenarios/commutative-name-collision/expected.CONFLICT b/tests/corpus/scenarios/commutative-name-collision/expected.CONFLICT
new file mode 100644
index 0000000..2896baf
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-name-collision/expected.CONFLICT
@@ -0,0 +1 @@
+name-collision
diff --git a/tests/corpus/scenarios/commutative-object-json/A.json b/tests/corpus/scenarios/commutative-object-json/A.json
new file mode 100644
index 0000000..062e54f
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-object-json/A.json
@@ -0,0 +1 @@
+{"a": 1, "b": 2}
diff --git a/tests/corpus/scenarios/commutative-object-json/B.json b/tests/corpus/scenarios/commutative-object-json/B.json
new file mode 100644
index 0000000..dbe203b
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-object-json/B.json
@@ -0,0 +1 @@
+{"a": 1, "c": 3}
diff --git a/tests/corpus/scenarios/commutative-object-json/O.json b/tests/corpus/scenarios/commutative-object-json/O.json
new file mode 100644
index 0000000..cb5b2f6
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-object-json/O.json
@@ -0,0 +1 @@
+{"a": 1}
diff --git a/tests/corpus/scenarios/commutative-object-json/expected.json b/tests/corpus/scenarios/commutative-object-json/expected.json
new file mode 100644
index 0000000..dce8ca0
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-object-json/expected.json
@@ -0,0 +1 @@
+{"a": 1, "b": 2, "c": 3}
diff --git a/tests/corpus/scenarios/commutative-prepend-json/A.json b/tests/corpus/scenarios/commutative-prepend-json/A.json
new file mode 100644
index 0000000..5d852f6
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-prepend-json/A.json
@@ -0,0 +1 @@
+{"b": 2, "z": 0}
diff --git a/tests/corpus/scenarios/commutative-prepend-json/B.json b/tests/corpus/scenarios/commutative-prepend-json/B.json
new file mode 100644
index 0000000..23b302d
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-prepend-json/B.json
@@ -0,0 +1 @@
+{"c": 3, "z": 0}
diff --git a/tests/corpus/scenarios/commutative-prepend-json/O.json b/tests/corpus/scenarios/commutative-prepend-json/O.json
new file mode 100644
index 0000000..651329f
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-prepend-json/O.json
@@ -0,0 +1 @@
+{"z": 0}
diff --git a/tests/corpus/scenarios/commutative-prepend-json/expected.CONFLICT b/tests/corpus/scenarios/commutative-prepend-json/expected.CONFLICT
new file mode 100644
index 0000000..8ea65cd
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-prepend-json/expected.CONFLICT
@@ -0,0 +1 @@
+insert-insert
diff --git a/tests/corpus/scenarios/commutative-use-rust/A.rs b/tests/corpus/scenarios/commutative-use-rust/A.rs
new file mode 100644
index 0000000..73f4eac
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-use-rust/A.rs
@@ -0,0 +1,5 @@
+use a;
+use b;
+use c;
+
+fn main() {}
diff --git a/tests/corpus/scenarios/commutative-use-rust/B.rs b/tests/corpus/scenarios/commutative-use-rust/B.rs
new file mode 100644
index 0000000..ab926df
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-use-rust/B.rs
@@ -0,0 +1,5 @@
+use a;
+use b;
+use d;
+
+fn main() {}
diff --git a/tests/corpus/scenarios/commutative-use-rust/O.rs b/tests/corpus/scenarios/commutative-use-rust/O.rs
new file mode 100644
index 0000000..21e5285
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-use-rust/O.rs
@@ -0,0 +1,4 @@
+use a;
+use b;
+
+fn main() {}
diff --git a/tests/corpus/scenarios/commutative-use-rust/expected.rs b/tests/corpus/scenarios/commutative-use-rust/expected.rs
new file mode 100644
index 0000000..b85ba44
--- /dev/null
+++ b/tests/corpus/scenarios/commutative-use-rust/expected.rs
@@ -0,0 +1,6 @@
+use a;
+use b;
+use c;
+use d;
+
+fn main() {}
diff --git a/tests/corpus/scenarios/duplicate-import/A.java b/tests/corpus/scenarios/duplicate-import/A.java
new file mode 100644
index 0000000..47e97fb
--- /dev/null
+++ b/tests/corpus/scenarios/duplicate-import/A.java
@@ -0,0 +1,6 @@
+import c.C;
+import a.A;
+import b.B;
+
+class Main {
+}
diff --git a/tests/corpus/scenarios/duplicate-import/B.java b/tests/corpus/scenarios/duplicate-import/B.java
new file mode 100644
index 0000000..a36965a
--- /dev/null
+++ b/tests/corpus/scenarios/duplicate-import/B.java
@@ -0,0 +1,6 @@
+import a.A;
+import b.B;
+import c.C;
+
+class Main {
+}
diff --git a/tests/corpus/scenarios/duplicate-import/O.java b/tests/corpus/scenarios/duplicate-import/O.java
new file mode 100644
index 0000000..b2e4f47
--- /dev/null
+++ b/tests/corpus/scenarios/duplicate-import/O.java
@@ -0,0 +1,5 @@
+import a.A;
+import b.B;
+
+class Main {
+}
diff --git a/tests/corpus/scenarios/duplicate-import/expected.CONFLICT b/tests/corpus/scenarios/duplicate-import/expected.CONFLICT
new file mode 100644
index 0000000..b5c09b8
--- /dev/null
+++ b/tests/corpus/scenarios/duplicate-import/expected.CONFLICT
@@ -0,0 +1 @@
+duplicate-insert