Incremental parsing

Deep dive

How it works

Parts:

• Old tree — immutable green nodes (kind, width, children, lookahead, lexer state); shared across versions.
• Edit record — (start, old_end, new_end) bytes (tree-sitter TSInputEdit adds row/column).
• Relexer — restarts at a safe token boundary before the edit, stops when tokens realign with old ones.
• Parser with reuse oracle — at each position asks "is a clean old subtree here?" and takes it whole.
• Red views — thin on-demand wrappers adding parent and absolute offset; thrown away per version.

1. Apply the edit to the old tree: nodes after it shift by delta = new_len - old_len; nodes touching it are marked changed.
2. Find the damaged region, wider than the edit: tokens merge (foo + bar) and nodes may have peeked past their end. A node is reusable only if the edit misses [start, end + lookahead).
3. Relex from a boundary where the lexer mode is the start state (outside strings and comments).
4. Reparse with reuse: take an old node if kind, context and cleanliness match and jump over its width; otherwise descend and parse normally.
5. Splice: rebuild only the path to the root (path copying); everything else is shared.
6. Changed ranges (optional): diff old and new trees so highlighting, folding and diagnostics redo only those ranges.

edit(start, old_end, new_end)
old tree ──► damaged region ──► relex window ──► parse; at each position ask "clean old subtree here?"
  (shared green nodes)                              yes: take it whole, skip its width
                                                    no: descend and parse
new tree = rebuilt path to the root + shared old subtrees ──► changed ranges

old:  [A][B <edit>][C][D]
new:  [A][B'      ][C][D]     A, C, D shared (C, D shifted); B' and the root path are new

Wagner-Graham (tree-sitter's lineage) does this inside an LR parser: nodes store their parse state, an old subtree is shifted whole when the state matches, else broken into children and retried. Red-green trees (Roslyn, rowan): green nodes store only kind and width, have no parent pointer and are position-independent, so subtrees are shared across versions.

Code

A toy incremental parser: a file is a list of top-level name { ... } blocks. After an edit, items wholly before it are kept, parsing resumes after them, and as soon as the parser sits at a top-level boundary past the edit where an old item (shifted by the delta) begins, the whole tail is reused. Each item keeps a content hash for comparing versions.

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Kind { Item, Error } // Error = unterminated block, runs to EOF

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct Item { pub start: usize, pub end: usize, pub kind: Kind, pub hash: u64 }

/// Old bytes [start, old_end) became `new_len` bytes.
pub struct Edit { pub start: usize, pub old_end: usize, pub new_len: usize }

fn fnv(b: &[u8]) -> u64 {
    b.iter().fold(0xcbf29ce484222325, |h, &c| (h ^ c as u64).wrapping_mul(0x100000001b3))
}

/// Parse one item at `i`: `name { ... }` with nested braces.
fn item(src: &[u8], i: usize) -> Item {
    let (mut j, mut depth, mut kind) = (i, 0u32, Kind::Error);
    while j < src.len() {
        match src[j] {
            b'{' => depth += 1,
            b'}' if depth > 0 => {
                depth -= 1;
                if depth == 0 { j += 1; kind = Kind::Item; break; }
            }
            _ => {}
        }
        j += 1;
    }
    Item { start: i, end: j, kind, hash: fnv(&src[i..j]) }
}

fn skip_ws(src: &[u8], mut i: usize) -> usize {
    while i < src.len() && src[i].is_ascii_whitespace() { i += 1; }
    i
}

pub fn parse_full(src: &[u8]) -> Vec<Item> {
    let (mut out, mut i) = (Vec::new(), skip_ws(src, 0));
    while i < src.len() {
        let it = item(src, i);
        i = skip_ws(src, it.end);
        out.push(it);
    }
    out
}

/// Returns (items, reused, parsed).
pub fn reparse(old: &[Item], e: &Edit, new_src: &[u8]) -> (Vec<Item>, usize, usize) {
    let delta = e.new_len as isize - (e.old_end - e.start) as isize;
    let new_end = e.start + e.new_len;
    // Head: items ending at or before the edit are untouched (they end at '}').
    let head = old.iter().take_while(|it| it.end <= e.start).count();
    let mut out: Vec<Item> = old[..head].to_vec();
    let (reused, mut parsed) = (head, 0);
    let mut i = skip_ws(new_src, out.last().map_or(0, |it| it.end));
    let first = old.iter().position(|it| it.start >= e.old_end).unwrap_or(old.len());
    let (tail, mut t) = (&old[first..], 0);
    let shifted = |x: usize| (x as isize + delta) as usize;
    while i < new_src.len() {
        if i >= new_end { // resync: an old item begins here, at top level
            while t < tail.len() && shifted(tail[t].start) < i { t += 1; }
            if t < tail.len() && shifted(tail[t].start) == i {
                for it in &tail[t..] {
                    out.push(Item { start: shifted(it.start), end: shifted(it.end), ..*it });
                }
                return (out, reused + tail.len() - t, parsed);
            }
        }
        let it = item(new_src, i);
        i = skip_ws(new_src, it.end);
        out.push(it);
        parsed += 1;
    }
    (out, reused, parsed)
}

Tested with asserts against parse_full on four edits: inside one item (2 head + 2 tail reused, 1 parsed), deleting a closing brace (the item swallows the rest: 2 reused, 1 parsed), inserting a new item (all 5 old items reused, 1 parsed) and editing the first item (4 reused, 1 parsed). Here the tail is shifted in a loop; a red-green tree stores widths, so the shift is free.

Complexity and constants

• Reparse O(damaged bytes + tree depth + number of reused siblings visited); a full parse is O(file). Worst case (edit at a { that opens a huge block, or an unclosed delimiter) falls back to O(file).
• Space: old and new trees share every unchanged node (reference counted); only the changed path is duplicated.
• Cost drivers: nodes allocated per edit (path to root plus new subtrees), cache misses walking old nodes, relexing bytes. Nothing else touches the disk or the kernel; the work is pure CPU and allocation.

Efficiency

• Cost: a local edit allocates a handful of nodes (new leaves plus the root path, order of tree depth, tens of nodes) and relexes tens to hundreds of bytes; compute- and allocation-bound, microseconds to low milliseconds for a typical edit, against milliseconds to tens of ms for a full parse of a large file (order of; measure on your grammar).
• Levers:
  • Reuse unchanged subtrees whole — work scales with the edit, not the file (Wagner-Graham 1998) — whenever the edit is local.
  • Immutable shared green nodes — no copying on edit, safe snapshots for background threads (rust-analyzer syntax docs) — in any language-server design.
  • Hash-consing (rowan's node cache) — equal subtrees stored once, fewer allocations and faster equality — repetitive code.
  • Changed ranges — downstream passes (highlight, fold, diagnostics) redo only the changed ranges (tree-sitter docs) — whenever consumers can work per region.
  • Coalesce edits — one reparse per burst instead of per keystroke — pastes, multi-cursor edits, formatting.
• Naive → standard → state of the art:
  • Reparse whole file per keystroke · O(file) per edit
  • Reparse the enclosing block or token, splice into immutable tree (rust-analyzer) · O(block)
  • Parser-level reuse of any clean subtree with lookahead tracking (tree-sitter) · O(edit + depth), plus changed ranges

Implementation notes

• Offset-free nodes: store widths, never absolute positions; compute offsets on descent. Then a shifted subtree is the same bytes in memory and the shift costs O(1).
• Lookahead tracking: store per node how far past its end the lexer or parser peeked; reuse only nodes whose [start, end + lookahead) misses the edit.
• Edit coordinates: byte offsets (and row/column) must match what the editor reports; see text position encoding for UTF-16 vs UTF-8 conversions in LSP.
• Test oracle: after every edit in fuzz tests assert incremental == full; this one test finds nearly all bugs.

Pitfalls

• Stale lookahead: reusing a node whose last token was decided by text now changed (e.g. a followed by = vs ==) gives a tree that differs from a full parse.
• Context-sensitive lexing: an inserted quote or /* changes the meaning of everything after it; the damaged region then extends to the end of the file, and that is correct.
• Error recovery: error nodes depend on what comes after them, so reusing a subtree that contains an error can freeze an outdated recovery. Recovery that is local and deterministic (parser error recovery) makes reuse sound. A recursive-descent parser (recursive-descent parsing) with a resilient design (never aborts, wraps junk in error nodes) fits region reparse well.
• Stale positions: nodes or ranges held outside the tree keep old offsets after an edit; tree-sitter requires editing them with the same edit value.
• Missing fallback: block reparse fails when an edit unbalances delimiters; keep a tested full-parse fallback.

Variants and alternatives

In production

• Desktop editors: Zed re-parses with tree-sitter's incremental parsing after each edit (blog); Neovim and Helix embed tree-sitter.
• Browser-based editors: Lezer drives CodeMirror 6 and re-parses incrementally (guide).
• Code hosting: GitHub code navigation is built on tree-sitter (docs).
• IDEs and language servers: Roslyn (C#/VB) uses red-green trees and incremental reparse in Visual Studio; rust-analyzer reparses by token or block over rowan trees.

Implementations

Sources

• Tim A. Wagner, Susan L. Graham, Efficient and Flexible Incremental Parsing, ACM TOPLAS 20(5), 1998. paper
• Tim A. Wagner, Practical Algorithms for Incremental Software Development Environments, PhD thesis, UC Berkeley, 1998 (Tech. Report UCB/CSD-97-946).
• tree-sitter docs, Advanced Parsing (editing, changed ranges). docs · code
• Eric Lippert, Persistence, Facades and Roslyn's Red-Green Trees, 2012. blog
• rust-analyzer, Syntax trees (green/red layers) and crates/syntax/src/parsing/reparsing.rs. syntax docs · reparsing.rs