Incremental Parsing and Tree Reuse in Editor Syntax Engines

Syntax structure in an editor serves several consumers at once: indentation, bracket matching, code folding, the outline of declarations, and increasingly the queries that decide whether a keystroke creates an autoclose pair. Each of them wants a tree over the document, and each wants it within the interval between two keystrokes. A parser that rebuilds the tree from scratch is linear in file size per edit; on a small file that is invisible, and on a file of a few hundred thousand characters it consumes the whole frame budget for a single typed character. Incremental parsing is the set of techniques that make the cost proportional to the size of the change and the depth of the nodes that contain it, rather than to the size of the document.

Why full reparsing fails the typing loop

A conventional parser has one input pointer and one output tree; when the tree is finished, the parser is discarded. Reparsing therefore repeats work that is provably still valid: text outside the edited range did not change, so any subtree whose extent lies entirely outside the edit parses to exactly what it parsed to before.

The quantity that matters is the size of the invalidated region. Inserting a keyword in the middle of a function body invalidates the statement containing it and, transitively, the block, the function, and everything up to the file root — a path of O(log n) to O(n) nodes depending on the tree’s branching factor, plus the text of the affected node. Inserting a quote character that opens an unterminated string literal invalidates everything to the end of the file, because the string continues past it. Tokenizers show the same behaviour through their state stack: a change that alters the lexical state at some point stays wrong until the state converges back, or until the end of input.

What a reparse actually reuses

The design that makes reuse possible is an immutable tree. Nodes are not modified after construction; an edit produces new nodes along the path from the root to the change and shares every node outside it. Because the old root is still valid, a background consumer can keep reading a previous version of the tree while the foreground edits, and the memory cost of keeping the previous version is only the nodes on the changed path.

The reparse itself proceeds in two steps. First, the edit is described to the tree: a start position, the end position of the replaced text, and the end position of the inserted text, in the units the parser uses internally. Every node whose extent lies entirely before the edit is unaffected; every node that spans the edit is marked to be reparsed. Second, parsing resumes at the earliest affected leaf and proceeds with the remaining input; when a candidate parse for a region exactly reproduces a previously parsed subtree — detectable by comparing the region’s text identity, which implementations typically reduce to a hash of the covered text — that subtree is adopted as-is instead of being rebuilt.

class Node:
    __slots__ = ("kind", "start", "end", "children", "hash")

    def invalidated(self, edit_start, old_end, new_end):
        """Nodes wholly before the edit keep their identity."""
        if self.end <= edit_start:
            return False
        if self.start >= old_end:              # wholly after the edited span
            self.start += new_end - old_end    # shift only
            return False
        return True                            # spans the edit: reparse

Two details make the difference between a working implementation and a slow one. The reuse test must be based on content, not on position, because insertion shifts every following position; and the reuse test must be cheap compared with parsing, which is why a hash of the covered text is stored per node rather than comparing text directly. Hash collisions trade correctness for speed, and implementations that reuse on hash equality accept the (astronomically unlikely, but non-zero) risk of adopting a subtree that differs.

Error recovery as a first-class requirement

Editors parse text that does not compile. At any instant during typing, the document is likely to contain an unterminated string, a missing closing brace, or a half-typed expression, and the syntax engine must nonetheless produce a usable tree, because folding and highlighting read it continuously.

Classical parsers handle this with panic-mode recovery, discarding input until a token that can legally follow the error can be consumed, and with error productions written into the grammar for common mistakes. Both are usable for batch compilation and poor for an editor, because discarding input destroys the structure of the very region the user is looking at, and because hand-written error productions only cover mistakes someone anticipated.

The approach that suits editing is to allow the parse to continue while recording an error node that spans the unparseable region, or to explore several parses in parallel and keep the one whose error cost is lowest, which is the generalized-parsing technique described by Wagner and Graham. The by-product is that the tree always covers the whole document, with explicit markers where structure could not be determined, so downstream queries can ask for the deepest node at a position and get an answer regardless of how broken the file is. The cost is that error recovery affects reuse: when an error node is removed by a fix, the region that was inside it must be reparsed even if its own text did not change, since the parse under an error state is not the parse under a valid state.

Incremental parsers must also decide how far an error propagates. A region marked erroneous is excluded from hashed reuse, so a file with a persistent syntax error near the top loses reuse for everything below it and degrades toward full reparsing — which is the correct behaviour, and worth knowing before measuring an editing loop on a file that does not compile.

Line-oriented tokenization and its ceiling

Before incremental parsers were common in editors, highlighting was driven by regular-expression grammars: patterns for keywords, strings, comments, and numbers, matched against the text line by line, with a stack of begin/end rules recording which multi-line construct is open. TextMate introduced this model, and it is still the basis of host-language grammars and of the highlighting in many editors.

The model has real advantages. Grammar files are declarative, a new language can be added by writing regex patterns rather than parser code, and the per-line cost is proportional to the line’s length. Its incremental strategy follows from that: after an edit, retokenize the changed line, and continue into following lines until the begin/end state stack at a line boundary matches what it was before the edit, at which point the rest of the file keeps its previous tokens.

The ceiling is that the result is a sequence of tokens, not a tree. Nesting is limited to what the state stack encodes, so constructs that need context — distinguishing a < operator from the start of a generic argument list, or recognizing a declaration whose meaning depends on an enclosing scope — cannot be expressed. Propagation is also unbounded in the wrong direction: inserting the characters that open a block comment in line 1 invalidates the tokens for every subsequent line, so a retokenize from the edit to the end of the file is the honest worst case.

Modern editors therefore run both layers: a token stream for colour, which is cheap and forgiving, and an incremental tree for structure, which is more expensive but precise. The colour layer also receives semantic information from a language server for the parts of the document the parser cannot resolve, which is where the delta-encoded token channel described in Semantic Tokens: Relative Encoding and Delta Updates enters the picture.

Embedded languages and injected ranges

Documents routinely contain other languages: script and style blocks in markup, query strings inside source code, templating directives in HTML. The structure is a tree of regions, where the outer document determines which ranges are handed to which inner grammar, and inner parses are cached per range.

Editing interacts with injection awkwardly. Changing the delimiter of an embedded region invalidates the range itself, not just its content, so the inner parser’s whole subtree is discarded; changing a byte inside the region invalidates only the inner tree. Because ranges are computed from the outer tree, an edit that shifts positions also shifts the ranges of every injection after it, which is one of the reasons positions inside an incremental parser should be expressed in units that the editing model can convert without rescanning — the same units problem described in Byte Offsets, UTF-16 Code Units, and Editor Positions.

When incremental parsing degenerates to a full parse

Three conditions turn the incremental path back into a linear one, and all three are reachable from ordinary typing. An edit inside a region that invalidates a node high in the tree — an unterminated comment marker, an unbalanced brace near the top of a file — forces a reparse of everything the node covers. A file that is entirely invalid loses reuse because error regions must be reparsed. And a grammar with heavy left recursion or a parser that keeps many competing stacks during recovery can spend more time deciding reuse than a straightforward parse would take, since reuse decisions are made per node.

The mitigation that matters in practice is bounding the work rather than eliminating it: capping the reparsed region, deferring tree updates while typing continues in the same region, and cancelling a parse in progress when a new edit arrives — the last of which is the same cancellation mechanism that language servers need, described in Cancellation, Progress, and Partial Results in the Language Server Protocol. A tree that is one keystroke stale is usually better than a frame that is one keystroke late.