How AST Merge Works

Three-way merge at the syntax tree, not the text buffer.

Overview

Git merges text. Aura merges meaning. When two branches diverge, Git walks the file line by line and asks a narrow question: "did the same line change on both sides?" If yes, conflict. If no, zip the hunks together. That model was revolutionary in 2005 and it is the reason CONFLICT (content) is the most expensive sentence in software engineering.

Aura replaces that model with a three-way Abstract Syntax Tree merge. Instead of lines, Aura sees declarations, expressions, statements, and blocks. Instead of asking "did this line change?", it asks "did this function, this field, this import change?" The result: two developers editing different functions in the same file merge automatically, with zero human intervention, every time.

A merge conflict is not a property of the code. It is a property of the merge algorithm. Change the algorithm, most conflicts disappear.

This page walks through the algorithm end to end — ancestor discovery, delta computation, delta application, conflict detection — and shows concrete before/after ASTs for a realistic diverge-and-merge scenario.

How It Works

Step 1: Find the common ancestor

Aura piggybacks on the Git object graph for history. Given ours (the branch you are on) and theirs (the branch you are merging), Aura asks Git for the merge base — the most recent commit reachable from both. That commit's version of the file is the ancestor.

aura merge feature/login
# internally: git merge-base HEAD feature/login -> abc123
#             git show abc123:src/auth.ts     -> ancestor text
#             git show HEAD:src/auth.ts       -> ours text
#             git show feature/login:src/auth.ts -> theirs text

Three texts in, one merged text out. Same input Git uses. Different algorithm after that.

Step 2: Parse all three versions

Each of the three versions is parsed by the appropriate tree-sitter grammar (see tree-sitter integration). The output is a concrete syntax tree, which Aura normalizes into a simpler AST by collapsing trivia (whitespace, stand-alone comments) and stamping each node with a stable identity.

Node identity is the critical move. A node's identity is not its position in the tree — if it were, a single line insertion would renumber everything and produce spurious conflicts. Instead, identity is derived from:

Kind (function_declaration, class, variable_statement, ...)
Name (if the node has one — login, UserService, MAX_RETRIES)
Structural path (module → class → method, when names repeat)
Content hash (fallback for anonymous nodes)

Renaming a function counts as delete + insert. Moving a function within a file does not — identity is stable across reordering.

Step 3: Compute deltas

With three trees in hand, Aura diffs ancestor→ours and ancestor→theirs independently. Each diff produces a delta — an ordered list of node-level operations:

Delta = [
  Insert(node),
  Delete(id),
  Modify(id, new_node),
  Move(id, new_parent, new_index)
]

Delta computation runs in O(n) over node count for shallow trees and O(n log n) with the Zhang-Shasha-inspired tree edit distance on deeper ones. For typical source files (hundreds to low thousands of nodes), this completes in single-digit milliseconds.

Step 4: Classify each pair of operations

For every node touched by either side, Aura computes an interaction class:

| Ours | Theirs | Classification | |-------------|-------------|----------------| | Unchanged | Modified | Take theirs | | Modified | Unchanged | Keep ours | | Modified | Modified | Potential conflict — compare payloads | | Inserted | Inserted | If identical, dedupe; else conflict | | Deleted | Modified | Conflict — ours removed what theirs edited | | Modified | Deleted | Conflict — theirs removed what ours edited | | Deleted | Deleted | Agree — delete | | Moved | Modified | Apply both (move + edit are orthogonal) |

The row that matters is Modified / Modified. If both sides produce the exact same new payload for a node, Aura collapses it — no conflict. If payloads differ, Aura inspects one level deeper. Two edits to the same function that touch disjoint statements are auto-merged. Two edits to the same statement raise a conflict.

Step 5: Apply disjoint deltas

Non-conflicting operations are applied in dependency order:

Deletes first (so subsequent inserts can reuse positions cleanly).
Modifies next (in-place updates keyed by node id).
Inserts last, ordered by their stable parent + index.
Moves resolved against the post-insert layout.

The result is a new AST. Aura then pretty-prints it back to source text using the language's formatter profile, preserving the project's existing style (tabs vs spaces, trailing commas, import ordering). The merged file lands on disk identical to what a careful human would produce.

Step 6: Surface conflicts

True conflicts — the ones a human must decide — are packaged into a Conflict record: the node id, the three candidate payloads (ancestor, ours, theirs), the file path, and a human-readable summary. These drive the interactive conflict picker and the aura conflicts list API. See conflict resolution for the full structure.

Examples

A: Two functions, one file

Ancestor src/auth.ts:

export function login(user: string, pass: string) {
  return db.verify(user, pass);
}

export function validate(token: string) {
  return jwt.check(token);
}

On main, Alice hardens login:

export function login(user: string, pass: string) {
  const hashed = bcrypt.hash(pass);
  return db.verify(user, hashed);
}

On feature/jwt, Bob rewrites validate:

export function validate(token: string): Claims | null {
  try { return jwt.verify(token, SECRET); }
  catch { return null; }
}

Git produces a conflict: both sides changed overlapping line ranges. Aura's delta classification:

ours    = [Modify(login)]
theirs  = [Modify(validate)]
intersection = {} -> no conflict
merged  = [Modify(login), Modify(validate)]

Both deltas apply. The merged file contains the hardened login and the rewritten validate. No prompt, no human, no <<<<<<< HEAD.

B: Same function, disjoint statements

Ancestor:

function charge(amount: number) {
  log("charging");
  stripe.create({ amount });
  log("charged");
}

Ours adds a guard at the top:

function charge(amount: number) {
  if (amount <= 0) throw new Error("invalid");
  log("charging");
  stripe.create({ amount });
  log("charged");
}

Theirs adds a metric at the bottom:

function charge(amount: number) {
  log("charging");
  stripe.create({ amount });
  log("charged");
  metrics.increment("charge");
}

Statement-level delta:

ours    = [InsertStmt(charge, index=0, "if (amount <= 0)...")]
theirs  = [InsertStmt(charge, index=4, "metrics.increment...")]

Inserts at different indices into the same block commute. Merged body:

function charge(amount: number) {
  if (amount <= 0) throw new Error("invalid");
  log("charging");
  stripe.create({ amount });
  log("charged");
  metrics.increment("charge");
}

C: A real conflict

Ancestor:

const RETRIES = 3;

Ours:

const RETRIES = 5;

Theirs:

const RETRIES = 10;

Both sides modified the same leaf. Payloads differ. Aura raises a conflict with all three values visible:

CONFLICT: src/config.ts :: RETRIES (variable_declaration)
  ancestor: 3
  ours:     5
  theirs:   10
resolve with: aura resolve src/config.ts

D: Move + edit

Alice moves login from src/auth.ts to src/auth/login.ts. Bob edits login's body in place. Because identity is structural + name-based and Aura tracks file-spanning moves through semantic IDs, both operations apply:

ours    = [MoveNode(login, src/auth.ts -> src/auth/login.ts)]
theirs  = [Modify(login, body=...)]
merged  = [MoveNode, then Modify at new location]

The edited body lands in the new file. Git would have produced a delete/modify conflict and lost Bob's work if anyone hit "accept current."

Edge Cases

Formatting-only changes. If one side reformats a function (prettier pass, trailing comma cleanup) and the other edits it, the reformat produces a structurally identical AST. Aura sees no modification on the formatting side, applies the edit, and reformats the result. Git would have flagged every touched line.

Comment-only edits. Stand-alone comments are trivia and do not carry node identity. If both sides add comments to the same function, both survive — comments are union-merged within their attachment point. If both sides modify the same doc comment above the same node, Aura raises a comment-level conflict.

Rename collisions. Ours renames login to signIn. Theirs renames login to authenticate. Aura sees this as delete(login) on both sides plus two inserts with conflicting names. It raises a conflict with both candidate names. A rename on one side plus an edit to the original name on the other is resolved by transposing the edit onto the renamed node (the semantic-union strategy goes further; see merge strategies).

Parse failure on one side. If theirs has a syntax error, that side's tree is unusable for AST merge. Aura falls back to text merge for this file and emits a parse_failed diagnostic, so you know why. See limitations and edge cases.

Huge generated files. AST merge on a 200k-line lockfile is a bad trade. Aura applies heuristics — file size, node count, grammar suitability — and defers to the file-type-specific merger: JSON for lockfiles, text for minified bundles.

Whitespace-only diffs. A developer ran prettier across the whole repo on one side. Every file has thousands of changed lines. Aura parses both sides, sees identical ASTs, and emits a format-only marker. The merge takes the ours-side formatting and applies any real edits from theirs unchanged. Git would have produced thousands of hunks to hand-resolve.

Circular imports and cross-file identity. A function moved from module A to module B while its call sites remained in A. Aura's identity engine is file-local by default; cross-file moves are surfaced as a paired delete + insert with a cross-file-rename hint, so the picker can present them together rather than as two unrelated conflicts.

Declaration order changes. If ours reorders top-level declarations while theirs edits one of them, Aura keeps ours's order and applies theirs's edit — order is a preference, not a semantic fact. The reordering is noted in the merge summary rather than as a conflict. If both sides reorder differently, Aura picks ours's order deterministically and records the alternative.

Very fast merges. Aura's three-way AST merge typically runs in single-digit to low double-digit milliseconds per file on modern hardware for files under 10k lines. A complete repo-wide merge of a thousand-file diff finishes in seconds, not minutes. The slow path is almost always disk I/O, not the algorithm.