# d3j: structural three-way merge in Rust with tree-sitter

A Rust implementation of the structural merge tool and correctness
criteria from Mori & Hashimoto, "On the Correctness of Software
Merge" (ASE 2025, arXiv:2607.07987). The paper's d3j targets Java
with a custom OCaml parser; this implementation is language-generic,
built on tree-sitter.

## Scope

Two deliverables, built together:

- A three-way merge tool: parse base O and branches A and B, diff
  structurally, compute the merged tree as a pushout, emit merged
  source or conflict markers.
- A correctness checker: given O, A, B, and any merge result M,
  verify M is parsable and universal. The checker is also the merge
  tool's test oracle — every merge the tool emits must pass it.

Non-scope for v1: move detection (a move degrades to delete+insert,
which is conservative but never wrong), comment merging (comments
survive only via span reuse), semantic correctness, and falling back
to textual merge.

## Correctness criteria (from the paper)

A conflict-free merge M is correct iff it is parsable and universal.
Universality is stated over the partial inclusion maps f: O→A,
g: O→B, i1: A→M, i2: B→M:

1. No extra insertion: every node of M comes from A or B.
2. No missed insertion: every node inserted in A or B has an image
   in M.
3. No extra deletion: every O node surviving in both A and B
   survives in M.
4. No missed deletion: every O node deleted in A or B is absent
   from M.

These four conditions plus commutativity make M a pushout of f and g
in the category of ordered sets and partial inclusion maps.

## Decisions

| Question | Decision |
|---|---|
| Scope | Merge tool and checker together; checker as oracle |
| Language support | Generic core driven by tree-sitter grammar metadata; concrete languages are thin layers |
| Interface | Merge-driver CLI (diff3-style) plus library crate |
| Output | Span-based synthesis from original sources; preserves formatting and comments |
| Diff engine | Anchored Zhang–Shasha; insert/delete/relabel only in v1, moves in a later milestone |

## Architecture

Single crate `d3j` (library plus thin binary):

```
src/
  lang.rs    # grammar registry: language detection, node-types.json metadata
  tree.rs    # arena AST lifted from tree-sitter CST
  diff.rs    # matching → partial inclusion map + derived edit script
  merge.rs   # pushout construction + conflict rules
  check.rs   # universality checker (the oracle)
  synth.rs   # span-based output synthesis
  main.rs    # CLI
```

Data flow: parse O, A, B → lift CSTs to arena trees → diff O→A and
O→B → construct pushout under conflict rules → synthesize text from
origin spans → self-check (re-parse + universality) → emit.

### Core representation

The partial inclusion map is the first-class object; edit scripts
are derived views. A matching between trees is a set of
order-preserving node pairs. Unmatched-in-source means deleted,
unmatched-in-target means inserted, matched-with-different-label
means relabeled. The universality conditions are set-membership
statements over these maps, so the merger and checker share one
vocabulary.

```rust
struct Tree { nodes: Vec<Node> }  // root = index 0
struct Node {
    kind: u16,               // tree-sitter grammar kind id
    label: Option<String>,   // identifier text for named leaves
    span: Range<usize>,      // byte range in origin source
    children: Vec<NodeId>,
    field: Option<u16>,      // tree-sitter field id (fixed-arity slot)
}
```

Only named entities (identifiers, literals) carry labels, which
restrains relabel to meaningful cases; structural nodes match by
kind alone. Comment and other "extra" nodes are excluded from the
tree in v1.

### Diff engine

`diff(O, A) → Matching` runs in three phases:

1. Anchor identical subtrees. Merkle-hash every subtree (kind, label,
   child hashes). Unique equal hashes match wholesale. This typically
   covers most nodes and keeps phase 2 affordable.
2. Zhang–Shasha on the residue. Costs: 0 for same-kind/same-label,
   small for relabel (same kind, different label), unit for
   insert/delete, infinite across kinds — a `binary_expression`
   never matches an `if_statement`.
3. Order enforcement. The map must preserve ancestry and sibling
   order. Anchors that cross are demoted to delete+insert.

Internal consistency property, tested continuously:
`apply(derive_edits(diff(O, A)), O) == A`.

### Pushout construction

Given f: O→A and g: O→B:

1. An O node survives into M iff it has images in both A and B.
2. Common edits apply once: identical relabels deduplicate; equal
   insertions (by subtree hash) at the same anchor deduplicate.
3. Inserted nodes graft at their parent's image. Sibling order within
   a branch is preserved; cross-branch order at the same slot is
   A-then-B.
4. Conflict rules run over pairs of edits touching related nodes.
   Each rule is `(EditA, EditB, &Ctx) → Option<Conflict>`.

V1 ships the paper's five core rules, generalized to grammar
metadata instead of hand-written Java checks:

- relabel-relabel: one O node relabeled differently in each branch.
- delete-delete: connected deletion regions that overlap without
  coinciding.
- insert-delete: an insertion under a node deleted in the other
  branch, with no surviving ancestor of the same syntactic category.
- insert-insert: different-shape insertions at the same slot.
- arity/category: every parent's children must stay compatible with
  the grammar — fixed-arity nodes use tree-sitter fields,
  variable-arity nodes use the category sets from node-types.json.

On conflict: emit diff3-style markers built from the original source
spans of the conflicting regions, exit 1.

### Synthesis and self-check

Every M node records its origin (O, A, or B, plus byte span). Output
is assembled depth-first, emitting source slices and reusing an
origin's contiguous run wherever consecutive nodes share a source
file, so untouched regions are byte-identical to their input —
formatting and comments survive. Whitespace at stitch points comes
from the side contributing the inserted material.

Before emitting, the tool checks its own work: re-parse the output
(zero tree-sitter error nodes required) and run the universality
checker on A→M and B→M. A failure means a d3j bug; the tool reports
a conflict rather than emit an incorrect merge. This enforces the
paper's headline property — no incorrect conflict-free merges — at
runtime.

### CLI

```
d3j merge <O> <A> <B> [-o out] [--lang X]   # exit 0 = merged, 1 = conflicts
d3j check <O> <A> <B> <M>                    # reports violated conditions
```

Argument order is diff3-compatible so the binary drops into jj's
merge-tools config. Language is detected by extension. V1 bundles a
small grammar set (Rust, Java, JSON for tests).

Error space: unparsable input or unknown language exits 2, distinct
from conflicts. The tool never silently falls back to textual merge.

## Testing

Three layers:

1. Unit tests on toy trees; the paper's Figures 2, 3, and 10 become
   literal test cases.
2. Properties: the diff round-trip (`apply(diff(O,A), O) == A`) and
   checker-as-oracle on every merge output, driven by proptest with
   random edit scripts applied to seed files.
3. Scenario corpus: directories of O/A/B/expected as integration
   tests, seeded from the paper's figures and grown from real
   conflicts.

## Milestones

1. `tree.rs` + `lang.rs`: parse and lift, subtree hashing.
2. `diff.rs`: anchored ZS matching with the round-trip property.
3. `check.rs`: universality checker (testable against git-merge
   output before the merger exists).
4. `merge.rs`: pushout + the five conflict rules.
5. `synth.rs` + CLI: span synthesis, self-check, merge-driver exit
   codes.
6. Later: move detection, comment merging, more languages, the
   paper's replication datasets.

## Reference

Paper: https://arxiv.org/abs/2607.07987 (a copy lives untracked at
the repository root as `2607.07987v1.pdf`).
Replication package: https://doi.org/10.5281/zenodo.13335352