In an editor that re-scans a buffer after every keystroke, why can typing one character re-tokenize the rest of the file?

## Why the blast radius exceeds the edit Scanning is a left-to-right pass with carried state: the rule set in force, any open mode, any nesting depth. For most characters the state before and after an edit is identical, so the tokens after it are unchanged except for a shift in their offsets. But a handful of characters change the carried state itself: - an opening block-comment marker turns the remainder of the buffer into comment text until a closing marker is found; - an unmatched quote opens a string that runs to the end of the line, or to the end of the file in a multi-line string syntax; - deleting a closing marker has the same effect in reverse; - opening or closing an embedded-expression hole flips the mode stack for everything after it. That is the honest answer to the question: not every keystroke propagates, but the ones that alter carried state propagate to wherever the state next re-converges, which may be nowhere before end of input. ## What an incremental scanner caches To avoid re-scanning from the top of the file on every keystroke, the scanner stores checkpoints. A common arrangement is one checkpoint per line holding: - the scanner's full carried state at the line's first character - mode stack and any nesting depth, not just a mode name; - the offset that state corresponds to; - optionally the tokens produced on that line, so unchanged lines need no re-scan at all. The cache is what makes the work proportional to the damage rather than to the file. ## The re-scan algorithm 1. Find the checkpoint at or before the start of the edited region and restore its state; everything before it is untouched by construction. 2. Shift the offsets of all cached checkpoints after the edit by the edit's length delta, so old and new positions are comparable. 3. Re-scan forward from the checkpoint, emitting tokens. 4. After each emitted token, compare the pair `(carried state, offset)` with the pair recorded in the previous run at that shifted offset. 5. The first time both halves match, the scan has **re-converged**: from here on the old tokens are identical to what a full re-scan would produce, so stop and keep them. 6. If re-convergence never happens, the scan runs to end of input - which is exactly the unmatched-quote case. Step 4 is where the correctness lives, and both halves are needed. Matching offsets alone is not enough: the same position can be reached in a different mode, and then every token after it differs. Matching state alone is not enough either, since a token boundary that has shifted means the old tokens no longer line up with the text. ## What it buys, in practice | Edit | Typical re-scan extent | |---|---| | A letter inside an identifier | one token, then immediate re-convergence | | Inserting a space | one or two tokens | | Typing an opening comment marker | to the next closing marker, or end of file | | Typing one quote character | to the end of that string's scope, often end of file | | Deleting a closing brace of an embedded hole | end of file, because the mode stack never empties | So the common case is a few tokens and the pathological case is the whole buffer - and the pathological case is transient, because the user is usually one keystroke away from typing the closer that restores convergence. This is why a highlighter can visibly repaint an entire file for a moment when a quote is typed, then settle. ## Tokens are not the only thing that moves Even where tokens are unchanged, their **spans** are not: everything after the edit shifts by the delta. An implementation either rewrites the offsets or stores spans relative to a checkpoint so that shifting a checkpoint moves its tokens implicitly. Getting this wrong produces the classic symptom of decorations drifting one character further off with each edit, while the token classes themselves remain perfectly correct. ## The judgment this question is really probing The interviewer is checking whether the candidate sees tokenization as a stateful pass rather than a pure function of a window of text. The follow-through - cache the carried state, compare state and boundary, accept an unbounded worst case that resolves itself - is the design every incremental front end converges on, and the same convergence argument is what later stages reuse when they try to reuse a subtree instead of a token.