# CRDT vs AST Merge

*Three architectures for collaborative editing. Each is correct for a different problem. Only one of them is correct for code.*

> The choice of merge mechanism is the single most important design decision in a collaborative editor. Get it wrong and every feature you build on top inherits the pathology.

## The Concern

If Aura wants to do collaborative editing at all, it has to pick a merge mechanism. There are three serious candidates, each with published theory and production deployments. The tradeoffs matter, and engineers evaluating Aura have a right to know which we picked and why.

The three options:

1. **CRDT (Conflict-free Replicated Data Types)** — character-level operations with mathematical guarantees of eventual convergence. Used by Figma, Google Docs, Notion, Automerge, Y.js.
2. **AST-aware merge** — operations at the granularity of syntax tree nodes. Used by mergiraf, Spork, IntelliMerge, and Aura.
3. **Git-style three-way text merge, with UX improvements** — line-based diff and merge with better tooling around it. Used by Git, Mercurial, Sapling, jj.

Each is a legitimate engineering choice. The question is which one fits code.

## How Aura Handles It

Aura uses AST-aware merge, with a Git three-way text merge as the fallback when the AST cannot be parsed. We explicitly rejected CRDT. Here is the reasoning.

### Option 1: CRDT

A CRDT represents a document as a sequence of small operations (insert character, delete character, set attribute) with enough metadata — usually a unique ID per operation and a causal history — that any two replicas, given the same set of operations in any order, will converge to the same final document.

CRDTs are an extraordinary piece of distributed systems research. They solve a hard problem (eventual consistency without coordination) in a way that is mathematically sound and has excellent implementations.

**Where CRDTs shine:**

- Documents where any interleaving of edits produces a well-formed document (prose, rich text, scene graphs, structured data).
- Settings where the cost of divergence or coordination is higher than the cost of occasional weird-looking output (multi-user whiteboards).
- Offline-first applications where replicas may be disconnected for long periods.

**Where CRDTs struggle with code:**

- A source file is not "well-formed for any interleaving." It is well-formed only for interleavings that produce valid syntax. A CRDT has no notion of syntactic validity. It cheerfully converges to a state where both users' character edits are interleaved inside a function signature, producing garbage that the compiler rejects.
- The natural unit of coherence for code is the function, not the character. CRDTs operate one level too low.
- Conflict resolution in a CRDT is implicit (whichever operation wins by tie-breaker wins). For prose this is fine. For code it is exactly the silent-conflict problem.

You can build a CRDT over ASTs rather than characters. Research in this area exists (notably the AST-CRDT line of work from the past decade). It is promising and we read the papers. But production-grade AST-CRDT systems across many languages do not yet exist, and the algorithms get significantly more complex when the tree structure itself changes (moving a function, renaming a parameter across all uses, etc.). We consider this open research. See [scale limits and research](/scale-limits-and-research).

### Option 2: AST-aware merge (Aura's choice)

AST-aware merge parses both sides of a merge into syntax trees, diffs the trees structurally, and produces a merged tree that preserves the edits on both sides where they do not conflict. It uses a parser per language. Aura uses tree-sitter, which provides fast, error-tolerant grammars for dozens of languages.

The merge operates at tree-node granularity. The natural node for code is the function, but Aura also tracks finer-grained nodes (method bodies, struct fields, import statements) to handle cases where two peers edit inside the same function in non-overlapping ways (e.g., both adding independent imports at the top).

**Why it wins for code:**

- It understands that the function is a meaningful atomic unit. A merge either preserves the function as one side wrote it, preserves it as the other wrote it, or raises a conflict. It does not interleave at the character level.
- It handles structural edits correctly. If you rename a parameter from `x` to `amount` throughout a function, the AST diff sees one semantic change, not fifty character edits.
- It composes with function identity tracking. See [function-level identity](/function-level-identity). When a function is renamed, Aura follows; a concurrent edit to the renamed function is not a conflict.
- Conflict detection is semantic. Two peers touching different functions do not conflict. Two peers touching the same function raise an explicit conflict that a human resolves. This is exactly the behavior from [the silent conflict problem](/silent-conflict-problem).

**Where it struggles:**

- It requires a working tree-sitter grammar for the language. Rust, TypeScript, JavaScript, Python, Go, Java, C, C#, Ruby, and PHP are well-supported. Some languages have grammars that struggle on modern syntax (C++ templates, Swift macros). Heavy Lisp-style macros can produce trees that do not reflect the expanded semantics.
- It is slower than a CRDT for low-latency character-by-character updates. Parsing a file takes milliseconds, not microseconds. This is why Aura batches at ~5 seconds, not per keystroke. See [code is not Figma](/code-is-not-figma).
- It is more complex than text merge. Tree diff algorithms have worse worst-case complexity than Myers diff. In practice this rarely matters because code files are small, but on pathological inputs we fall back to text merge.
- Tree diffs can be ambiguous. If you move a block of code and simultaneously edit it, the tree diff may or may not recognize the move. Aura's algorithm is conservative and will occasionally flag a conflict where a human would see none. See [AST merge](/ast-merge).

### Option 3: Git-style three-way text merge

Traditional VCS approach: find a common ancestor, compute line-based diffs from ancestor to each side, combine them, flag overlapping edits as conflicts. Well understood, battle-tested across forty years of version control.

**Why it still matters:**

- It is the lingua franca. Every tool understands it. Every auditor understands it. Every new hire understands it.
- It is language-agnostic. Fortran, assembly, Jupyter notebooks, JSON, YAML, obscure DSLs — all work with `diff3`.
- It handles the 95% of cases that do not need semantic reasoning cheaply and correctly.

**Where it fails for code:**

- It flags spurious conflicts (two peers added an import on adjacent lines).
- It misses real conflicts (two peers each "fixed" the same function in semantically incompatible ways, but on different lines).
- It has no notion of function identity, rename, or move.
- Its conflict markers (`<<<<<<<`, `=======`, `>>>>>>>`) are notoriously painful to resolve in large blocks.

Aura does not replace Git's text merge. We run it as a fallback when AST merge cannot apply, and we run **on top of** it to add semantic awareness. See [aura is not a Git killer](/aura-is-not-a-git-killer).

## The Comparison Table

| Property | CRDT | AST-aware (Aura) | Git 3-way text |
|---|---|---|---|
| Granularity | character | syntax tree node | line |
| Requires language parser | no | yes | no |
| Preserves syntactic validity | no | yes (at commit) | no |
| Conflict model | implicit (tie-break) | explicit (flagged) | explicit (flagged) |
| Works offline | yes | yes | yes |
| Eventual consistency guarantee | strong | best-effort | n/a (snapshot model) |
| Handles rename/move | poor | good | none |
| Latency for live sync | microseconds | seconds | n/a (at merge time) |
| Language coverage | all text | depends on grammar | all text |
| Research maturity for code | open | shipped | shipped |

The honest reading: CRDT is strong on consistency guarantees and weak on syntactic awareness. AST merge is strong on syntactic awareness and weak on very-low-latency sync. Git 3-way is strong on universality and weak on semantic understanding.

For collaborative prose, pick CRDT. For a version control system that a team can adopt, pick Git 3-way. For a semantic layer that sits on top of Git and handles the cases Git cannot see, pick AST merge.

## Why Tree-sitter Specifically

Aura's AST layer is built on [tree-sitter](https://tree-sitter.github.io/). A few properties made tree-sitter the right foundation:

- **Incremental.** Tree-sitter re-parses a file in milliseconds after small edits, not from scratch. This matters for the five-second sync cadence. Parsing 10,000 files every time a function changes would not be viable. Incremental parsing makes it viable.
- **Error-tolerant.** Tree-sitter returns a partial tree even for invalid input. This lets Aura reason about files that are mid-edit without giving up. A broken file yields a tree with error nodes, which Aura treats as "do not sync this function yet" but still allows the rest of the file to sync.
- **Language coverage.** Tree-sitter grammars exist for dozens of languages, many maintained by the language communities themselves. This is better than any in-house parser Aura could build.
- **Content-addressed tree hashes.** Aura computes a stable hash of each subtree, which becomes the [semantic identity](/function-level-identity) of the function. This survives whitespace changes, comment edits, and variable renames that do not change structure.

We are not dogmatic about tree-sitter. If Rust-analyzer's or TypeScript's language-server ASTs become easier to consume, we would consider them. In practice, tree-sitter's cross-language consistency outweighs the incremental gains a per-language parser would offer.

## What Aura Does Not Solve

**Non-trivial structural merges.** If two peers each refactor a class differently — one extracts a trait, the other inlines methods — the tree diff may produce an AST-level conflict that is technically correct but not what a human would write. Aura surfaces the conflict honestly. It does not author the correct merge for you.

**Consistency across many replicas in real time.** Aura's model assumes a small number of concurrent writers per function (typically 1–3). If twenty people edit the same function simultaneously, Aura will raise repeated conflicts and the experience will be poor. CRDTs would merge silently in the same scenario, but as discussed, the merged result would not be code you want to run. The correct answer at that scale is coordination, not a better merge algorithm.

**Languages without good grammars.** Truly esoteric or rapidly evolving syntax is beyond our AST layer. We fall back to text merge. This is correct but means you lose the benefits that drew you to Aura in the first place, for those files.

## The Honest Tradeoff

AST merge is the right mechanism for code, but it is not free. You pay in parsing latency (milliseconds per sync), in grammar maintenance (someone has to update tree-sitter grammars as languages evolve), and in occasional over-flagging of conflicts that a human would see as trivially mergeable. In exchange, you get a merge layer that understands the shape of your code, not just its bytes.

If you are building a tool for collaborative prose, use Y.js and do not look back. If you are building a tool for collaborative code, AST merge is, in our opinion, the only defensible choice today.

## See Also

- [AST merge](/ast-merge) — Aura's specific algorithm
- [Code is not Figma](/code-is-not-figma) — why character-level sync is wrong for code
- [Function-level identity](/function-level-identity) — tracking functions across renames
- [Silent conflict problem](/silent-conflict-problem) — the conflict model
- [Aura is not a Git killer](/aura-is-not-a-git-killer) — why AST merge sits on top of Git, not alongside
- [Scale limits and research](/scale-limits-and-research) — what remains open