Assisted-by: Claude Fable 5 via Claude Code

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..dadea7c
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1 @@
+/2607.07987v1.pdf
diff --git a/docs/plans/2026-07-10-d3j-design.md b/docs/plans/2026-07-10-d3j-design.md
new file mode 100644
index 0000000..1f2f0c4
--- /dev/null
+++ b/docs/plans/2026-07-10-d3j-design.md
@@ -0,0 +1,202 @@
+# 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