Incremental Reparsing After an Edit

A compiler parses a file once. An editor parses the same file after every keystroke. The difference is not a constant factor: a full parse of a large file costs an amount of work that grows with the file, while the edit itself is a few bytes, so the ratio between the two is not bounded by any constant.

Incremental parsing reuses the previous tree. The question is which parts of it are still valid, and the answer cannot be decided by looking at the changed bytes alone, because a one-character edit can change the parse of an arbitrarily large region.

The invalidation problem stated sharply

Deleting a { can make every following token parse differently until the matching } is found. Adding a ) can close a construct that previously swallowed the remainder as an error recovery region. Inserting a character can merge two tokens into one, which changes the token stream itself rather than only the parse.

So the region to reparse is not the changed range; it is the changed range extended until the parser is provably in the same state as before. For an LR parser, that state is the stack; for a recursive-descent parser, it is the call stack plus the lookahead. Once the parser reaches a position where the new parse’s state equals the old parse’s state at the same position, the old subtree can be reused from there to the end.

That condition is the basis of the standard algorithm. Reparse forward from the edit with the new text, and at each position compare the parser state to the state recorded in the old tree. On a match, splice the old subtree back in. The splice is correct because a parser whose state matches at a position will behave identically on all following input, so the old subtree is exactly what the new parse would produce.

Recording state in the tree

For the comparison to be possible, the tree must record the parser state at each node boundary. An LR-based incremental parser stores the state stack entry at each node, which costs one integer per node. A recursive-descent-based one stores the rule identity and the token offset at the point of entry, which is coarser but usually sufficient because the rule determines the remaining behaviour.

The comparison must be conservative. If two states are equal but the parser would behave differently because of information outside the state, the reuse is unsound. Symbol tables are the usual culprit: a state that has parsed an identifier is the same whether or not that identifier is a type name, and reusing a subtree parsed under the other assumption produces a wrong tree. This is why incremental parsers for C-like languages either record the symbol table version in the state or invalidate scopes rather than nodes.

Why error recovery breaks reuse

A tree node built by error recovery is not the result of a successful parse. It records that the parser skipped some tokens and resumed, which means its correctness depends on the surrounding text in a way that a successful node’s does not.

Consider a statement list where the parser recovered from a missing semicolon by inserting one. The node for that statement has a recorded state, and if the edit later supplies the semicolon, the new parse reaches the same state at the same position and would splice the old node back. The old node is missing the semicolon in its structure, so the tree now disagrees with the text.

The standard fix is to mark recovery nodes and treat a state match at a recovery node as no match. The parser then reparses through the region rather than reusing it. The cost is that a file with errors is reparsed more than a clean file, which is the right trade: errors are rare in a steady state, and correctness of the tree matters more when the file is broken.

Token-level reuse

Lexing is cheaper than parsing, but not free: a large file is scanned byte by byte, and the scanner’s work is proportional to its length. Reusing tokens across an edit is simpler than reusing parse trees because token boundaries are local, with one exception.

An edit can extend a token across a previous boundary. Deleting a space between two identifiers merges them into one; inserting a quote can make the rest of the file a string. The safe rule is to re-lex from the start of the token containing the edit, and to continue until a new token boundary coincides with an old boundary where the old and new offsets differ by the length change the edit made. At that point the rest of the stream can be shifted by the same delta and reused. If the boundaries never line up, the re-lex runs to end of file.

Inside a token whose text repeats, the choice of start offset matters. If the edit lies in the middle of a run of characters that can extend in both directions, such as a long string literal or a comment, re-lexing from the token’s original start still produces the correct extent, because the scanner for that token consumes forward from the start without looking backward. The backward part of the extent is therefore the old start, not the edit position.

For a line-oriented editor, an additional optimisation is to keep a line index so that a token start can be found without scanning from the file start. Without that index, the “start of the token containing the edit” requires a scan from offset zero, which defeats the purpose.

The data structure choice

Two families of tree representation serve incremental parsing, and they differ in what an edit costs.

A mutable tree with parent pointers allows a splice in time proportional to the depth of the affected node, which is small. It also makes the tree hard to share between threads and hard to undo, because every edit mutates in place. Where the tree is a zipper or a cursor that holds the path from the root, the rebuild cost is the same path length.

A persistent tree, such as a balanced tree of nodes keyed by offset, allows an edit to produce a new version sharing most nodes with the old, in time logarithmic in the number of nodes. The cost is more allocation along the path from the root and an indirection per node access. Editors that need undo, multiple views, or concurrent analysis of a snapshot choose this.

A third option is the piece table or rope, which stores the text as a list of immutable buffers with a mutable index. It solves the text side of the problem without touching the tree. Its own edit cost is the cost of finding the piece that contains the offset and splitting it, which is logarithmic for a tree-shaped rope and linear for a flat piece list; what it buys is that inserting text never copies the surrounding text.

What must be recomputed, and what need not

A parse tree is rarely the only derived structure. Editors also hold syntax highlighting spans, fold regions, and scope information. Each has a different invalidation rule.

Highlighting is local: a token’s class depends on its kind and possibly on the enclosing string or comment mode. Reusing tokens across the edit reuses the highlighting with them, provided the mode at the reuse point matches.

Fold regions are structural: a block’s extent is determined by its braces, so a splice that changes a block’s content without changing its extent preserves the region, and a splice that changes the extent invalidates it. Regions are cheap to recompute from the tree, so most editors recompute them for the spliced subtrees only.

Scope information is the expensive one, because it depends on the whole tree in a way that a local splice can change. A declaration added at the top of a file changes the meaning of every use below it. Incremental scope analysis is a separate problem from incremental parsing, and an editor that does both must either recompute scopes for the whole file after an edit or track dependencies between declarations and uses. The latter is a dataflow problem, not a parsing one.

Latency budget and the fallback

The point of incremental parsing is latency, so the algorithm needs a bound and a fallback. A reparse that reaches the end of the file without a state match has done a full parse with extra bookkeeping, which is worse than not being incremental at all.

Practical implementations cap the reparse distance. If the forward parse has not resynchronised within some number of tokens or lines, the editor discards the partial result and reparses the file from the start, reusing only the token stream. That keeps the worst case at one full parse, which is the same as the non-incremental baseline.

The fallback also handles the case where the parser is nondeterministic. A GLR parser has a set of states rather than one, and the state comparison becomes a set comparison, which is more expensive and less likely to match. A packrat parser has the opposite problem: every memo entry is keyed by an absolute input position, so an edit changes the position of everything after it and invalidates those entries even though the text they covered is unchanged. For such parsers, incremental reuse is usually limited to the token stream and to subtrees whose extent is enclosed by the edit, which is a weaker guarantee for a simpler implementation.

The state comparison is only meaningful if the parser’s state is a value rather than a mutable object graph; the same condition that makes the graph-structured stack awkward to checkpoint incrementally. For hand-written parsers, the state is a token offset and a rule, and the machinery in Recursive Descent and the Cost of One Token of Lookahead is what makes that state small enough to record per node.