Lesson 1.10 — Lossless lexing with trivia, and incremental relexing for IDEs

Techniques: tokens with attached trivia (Roslyn, SwiftSyntax, Pebble's LeadingTrivia), trivia as tokens (rustc_lexer, rust-analyzer's rowan trees), incremental relexing (tree-sitter; Wagner–Graham) · Pebble implements: lossless tokens with leading trivia (E5); the unit test PebbleLexer.CorpusIsLossless checks the round trip on every corpus file and 3000 random inputs · Prerequisites: Lessons 1.5, 1.7 · Time: 3–4 hours

A batch compiler throws whitespace and comments away. An IDE, a formatter, a refactoring tool or a documentation generator cannot: renaming a variable must preserve every comment, clang-format must know where the blank lines were, and an editor must re-lex after every keystroke without re-reading a 10 000-line file. This lesson covers the two properties those tools need from a lexer: losslessness (the token stream reproduces the file byte for byte) and incrementality (after an edit, only the tokens near the edit are recomputed).

1. Problem and motivation

Input: a file, and later a sequence of edits. Output: a token stream from which the exact source text can be rebuilt, updated after each edit in time proportional to the change, not the file.

Tokens with attached trivia

Roslyn (C#) and SwiftSyntax attach whitespace and comments ("trivia") to the neighboring tokens as leading and trailing trivia, so that every byte of the file belongs to exactly one token and a syntax tree prints back to its source [ROSLYN-Lexer, SWIFTSYNTAX-Trivia]. Pebble's Token::LeadingTrivia is the minimal version: a byte count of the whitespace and comments before each token, with the eof token carrying the trailing trivia of the file.

Trivia as tokens

The alternative is to make whitespace and comments ordinary tokens. rustc's lexer crate, rustc_lexer, returns Whitespace, LineComment and BlockComment tokens with their lengths, and rust-analyzer builds lossless syntax trees ("green trees", the rowan library) in which these tokens are leaves [RA-LexedStr]. Parsers skip them; tools see everything.

Incremental relexing

An editor edits a few bytes; relexing the file from the start costs time proportional to its size, on every keystroke. Wagner and Graham [WG98] showed how to relex and reparse incrementally: find the first token the edit can have affected, relex from there, and stop as soon as the new token stream falls back into step with the old one. tree-sitter [TS-Parser] does exactly this for every language it supports, and editors from Neovim to GitHub's code view use it.

2. Definitions and algorithms

Definition 1.10.1 (Lossless token stream)

A token stream \(t_1, \dots, t_m\) (the last being eof) for a source \(w\) is lossless if each token has a spelling \(s_i\) and trivia \(\tau_i\) (leading), or trivia split as \(\lambda_i\) (leading) and \(\rho_i\) (trailing), such that the concatenation reproduces the source:

\[ w = \tau_1 s_1\, \tau_2 s_2 \cdots \tau_m s_m \qquad \text{or} \qquad w = \lambda_1 s_1 \rho_1\, \lambda_2 s_2 \rho_2 \cdots \lambda_m s_m \rho_m . \]

Pebble stores \(\tau_i\) implicitly: Token::LeadingTrivia \(= \lvert \tau_i \rvert\) and the bytes are the ones just before Token::Loc.

Definition 1.10.2 (Roslyn/SwiftSyntax trivia attachment)

Given the trivia run \(\theta\) between tokens \(t_i\) and \(t_{i+1}\): the trailing trivia of \(t_i\) is the longest prefix of \(\theta\) that contains no line break, plus the first line break if there is one; the leading trivia of \(t_{i+1}\) is the rest. The file's first token takes all trivia before it as leading trivia; eof takes the rest.

Definition 1.10.3 (Trivia tokens and green trees)

In a trivia-as-tokens stream, whitespace and comments are tokens of kinds WHITESPACE, COMMENT; the parser's token cursor skips them, and the syntax tree builder attaches them as leaves between the nodes. A green tree (rowan) is an immutable tree whose nodes store their kind and total text length but not their absolute position, so equal subtrees can be shared and reused after an edit.

Definition 1.10.4 (Edit, lookahead extent)

An edit replaces the bytes \([a, b)\) of \(w\) by a string \(x\), giving \(w'\); its shift is \(\Delta = \lvert x \rvert - (b - a)\). The lookahead extent of a token is the index one past the last byte the lexer examined while producing it, trivia included (for a maximal-munch scanner: up to and including the byte that led to the dead state, Definition 1.6.4). The first affected token is the first token whose lookahead extent is greater than \(a\): the first token that examined a byte at or after the edit. A token boundary is the position just after a token (where the next token's leading trivia begins).

Definition 1.10.5 (Lexer state)

The lexer state at a token boundary is everything the next lex() call depends on besides the input bytes: for Pebble, the interpolation stack (Definition 1.7.2); for Python, the indentation stack and the bracket depth; for a pure DFA lexer, nothing.

Tokens with attached trivia

Algorithm 1.10.6 (Leading-trivia lexing and Roslyn-style splitting)

• Input: the source \(w\); a lexer that skips trivia before each token.
• Output: tokens with \(\lvert\tau_i\rvert\) (Pebble), or with \((\lambda_i, \rho_i)\) (Roslyn style).
• Precondition: every byte is either trivia or part of a token (error bytes become unknown tokens, never silently dropped).
• Postcondition: the stream is lossless (Theorem 1.10.9).
• Invariant: cursor = the number of bytes accounted for by the tokens and trivia emitted so far.

function LexLossless(w):                          # Pebble
    cursor ← 0;  out ← []
    loop:
        triviaStart ← cursor;  cursor ← SkipTrivia(w, cursor)
        (kind, end) ← ScanToken(w, cursor)        # end = cursor for eof
        append Token{kind, loc: cursor, spelling: w[cursor..end), leadingTrivia: cursor − triviaStart}
        cursor ← end
        if kind = eof: return out

function SplitTrivia(theta):                      # Roslyn/SwiftSyntax (Definition 1.10.2)
    k ← index of the first line break in theta, or |theta| if none
    trailing ← theta[0 .. k+1) if k < |theta| else theta
    leading  ← theta[|trailing| ..)
    return (trailing, leading)

Pebble keeps a trivia count per token; Clang keeps only two flags

Reproduce (ch01-lexdump built from this repository with -DPEBBLE_USE_SOLUTION=lexer, clang 23.1.2):

printf 'let x = 1; // one\n  /* two */ y\n' > triv.pbl
ch01-lexdump --trivia triv.pbl
printf 'int x = 1; // one\n  /* two */ int y;\n' > triv.c
clang-23 -fsyntax-only -Xclang -dump-tokens triv.c 2>&1

Output (complete):

1:1 kw_let 'let' trivia=0
1:5 identifier 'x' trivia=1
1:7 equal '=' trivia=1
1:9 int_literal '1' = 1 trivia=1
1:10 semi ';' trivia=0
2:13 identifier 'y' trivia=20
3:1 eof '' trivia=1
int              'int'                           Loc=<triv.c:1:1>     [StartOfLine]
identifier       'x'                             Loc=<triv.c:1:5>     [LeadingSpace]
equal            '='                             Loc=<triv.c:1:7>     [LeadingSpace]
numeric_constant '1'                             Loc=<triv.c:1:9>     [LeadingSpace]
semi             ';'                             Loc=<triv.c:1:10>   
int              'int'                           Loc=<triv.c:2:13>    [StartOfLine] [LeadingSpace]
identifier       'y'                             Loc=<triv.c:2:17>    [LeadingSpace]
semi             ';'                             Loc=<triv.c:2:18>   
eof              ''                              Loc=<triv.c:2:19>   

What to notice: y carries trivia=20: the 20 bytes // one\n /* two */ before it, so Pebble's stream is lossless (Definition 1.10.1) and a tool can recover the comments from the source buffer. Clang keeps only the flags [StartOfLine] and [LeadingSpace] per token (enough for -E output and some diagnostics); clang-format and other tools re-lex the buffer themselves in a raw mode that keeps comments as tokens.

Trivia as tokens

Algorithm 1.10.7 (Trivia tokens with a skipping cursor)

• Input: \(w\); a lexer that returns trivia as tokens (Definition 1.10.3).
• Output: the full token list, and a parser cursor over non-trivia tokens.
• Precondition: every byte belongs to exactly one token (unknown bytes included).
• Postcondition: concatenating all token texts gives \(w\) (Theorem 1.10.9); the parser sees the same tokens as a trivia-skipping lexer.
• Invariant: the sum of the lengths of the tokens returned so far is the current offset.

function Tokenize(w):
    pos ← 0;  toks ← []
    while pos < |w|:
        (kind, len) ← AdvanceToken(w, pos)       # rustc_lexer::Cursor::advance_token
        append (kind, len) to toks;  pos ← pos + len
    return toks

function ParserCursor(toks):                      # rust-analyzer: skip trivia, remember them
    i ← 0
    next(): while toks[i].kind ∈ {WHITESPACE, COMMENT}: i ← i + 1
            return toks[i++]
    # the tree builder re-inserts every skipped trivia token as a leaf of the green tree

rustc's lexer returns whitespace and comments as tokens

Reproduce (rustc 1.94.1, cargo 1.94.1; ra-ap-rustc_lexer 0.174.0 is rustc_lexer as published from rust-lang/rust; unicode-ident pinned to 1.0.24 to match its Unicode version):

cargo new --quiet ratrivia && cd ratrivia
cargo add ra-ap-rustc_lexer@=0.174.0
cargo update -q -p unicode-ident --precise 1.0.24
cat > src/main.rs <<'EOF'
use ra_ap_rustc_lexer::{tokenize, FrontmatterAllowed};

fn main() {
    let src = "let x = 1; // one\nlet s = r#\"a \"quoted\" b\"#;/* c /* nested */ */\n";
    let mut pos = 0;
    for tok in tokenize(src, FrontmatterAllowed::No) {
        let len = tok.len as usize;
        println!("{:>3}..{:<3} {:?} {:?}", pos, pos + len, tok.kind, &src[pos..pos + len]);
        pos += len;
    }
}
EOF
cargo run -q

Output (complete):

  0..3   Ident "let"
  3..4   Whitespace " "
  4..5   Ident "x"
  5..6   Whitespace " "
  6..7   Eq "="
  7..8   Whitespace " "
  8..9   Literal { kind: Int { base: Decimal, empty_int: false }, suffix_start: 1 } "1"
  9..10  Semi ";"
 10..11  Whitespace " "
 11..17  LineComment { doc_style: None } "// one"
 17..18  Whitespace "\n"
 18..21  Ident "let"
 21..22  Whitespace " "
 22..23  Ident "s"
 23..24  Whitespace " "
 24..25  Eq "="
 25..26  Whitespace " "
 26..43  Literal { kind: RawStr { n_hashes: Some(1) }, suffix_start: 17 } "r#\"a \"quoted\" b\"#"
 43..44  Semi ";"
 44..64  BlockComment { doc_style: None, terminated: true } "/* c /* nested */ */"
 64..65  Whitespace "\n"

What to notice: the token lengths tile the input from 0 to 65 with no gaps (Algorithm 1.10.7's invariant): whitespace and comments are tokens. Keywords are not recognized here (let is Ident): rustc classifies them later through its symbol table (Lesson 1.8). The raw string records n_hashes: Some(1) (Lesson 1.7) and the nested block comment is one token with terminated: true, the same nesting rule as Pebble.

Incremental relexing

Algorithm 1.10.8 (Incremental relexing, Wagner–Graham style)

• Input: the old token list (with start, length, lookahead extent and lexer state at each boundary); an edit \(([a, b), x)\) turning \(w\) into \(w'\).
• Output: the new token list.
• Precondition: the lexer is deterministic: its output from a boundary depends only on the bytes from there and the lexer state (Definition 1.10.5).
• Postcondition: the result equals a full relex of \(w'\) (Theorem 1.10.10).
• Invariant: the new tokens emitted so far are exactly the full relex of \(w'\) up to the current position.

function Relex(old, a, b, x):
    Δ ← |x| − (b − a)
    k ← index of the first old token whose lookahead extent > a        # it examined a changed byte
    pos ← boundary before old[k];  state ← lexer state at that boundary
    new ← old[0 .. k)                                                  # unchanged prefix, reused
    j ← k                                                              # candidate old token to resync after
    loop:
        (tok, state) ← LexOne(w', pos, state)                          # trivia + one token
        append tok to new;  pos ← tok.end
        if tok = eof: return new
        if pos ≥ b + Δ:                                                # past the edited region
            while j < |old| and old[j].end + Δ < pos: j ← j + 1
            if j < |old| and old[j].end + Δ = pos and old[j].stateAfter = state:
                return new ++ shift(old[j+1 ..], Δ)                    # back in step: reuse the rest

tree-sitter keeps the tokens as leaves of its syntax tree; ts_tree_edit shifts positions and marks the affected nodes, and the next parse re-lexes only where a reused leaf is not valid (ts_parser__can_reuse_first_leaf checks that the leaf's lookahead did not cross the edit).

tree-sitter reparses after an edit and reports the changed range

Reproduce (Python 3.11.15 with py-tree-sitter 0.26.0 and tree-sitter-python 0.25.0 from PyPI; any OS):

python3 -m venv venv && ./venv/bin/pip install -q tree-sitter==0.26.0 tree-sitter-python==0.25.0
cat > tsdemo.py <<'EOF'
import tree_sitter_python as tspython
from tree_sitter import Language, Parser


def leaves(node, out):
    if node.child_count == 0:
        out.append(f"{node.type}@{node.start_byte}-{node.end_byte}")
    for child in node.children:
        leaves(child, out)
    return out


parser = Parser(Language(tspython.language()))
old_src = b"x = 1\ny = 'abc'\nz = x + y\n"
old = parser.parse(old_src)
print("before:", " ".join(leaves(old.root_node, [])))

# Insert one quote at byte 10: y = ''abc'  -> the string now ends early
new_src = old_src[:10] + b"'" + old_src[10:]
old.edit(start_byte=10, old_end_byte=10, new_end_byte=11,
         start_point=(1, 4), old_end_point=(1, 4), new_end_point=(1, 5))
new = parser.parse(new_src, old)          # reuses the unchanged parts of `old`
print("after: ", " ".join(leaves(new.root_node, [])))
for r in old.changed_ranges(new):
    print("changed range: bytes", r.start_byte, "to", r.end_byte)
EOF
./venv/bin/python tsdemo.py

Output (complete):

before: identifier@0-1 =@2-3 integer@4-5 identifier@6-7 =@8-9 string_start@10-11 string_content@11-14 string_end@14-15 identifier@16-17 =@18-19 identifier@20-21 +@22-23 identifier@24-25
after:  identifier@0-1 =@2-3 integer@4-5 identifier@6-7 =@8-9 string_start@10-11 string_end@11-12 identifier@12-15 string_start@15-16 identifier@17-18 =@19-20 identifier@21-22 +@23-24 identifier@25-26
changed range: bytes 10 to 26

What to notice: the tokens before the edit (x = 1, y =) are reused unchanged. After the inserted quote, '' is an empty string, abc becomes an identifier and the old closing quote opens a new, unterminated string: one byte of edit changed the meaning of everything to the end of the file (changed range: bytes 10 to 26). Relexing cannot resynchronize while a string is open, which is why Pebble ends an unterminated string at the line break (E0108): the damage of a stray quote is then bounded by one line (unless the quote turns a \( into an interpolation that stays open, Proposition 1.10.11).

3. Worked example

Tokens with attached trivia

The Pebble input let x = 1; // one⏎ /* two */ y⏎ (32 bytes). Leading trivia (Pebble) and the Roslyn split (Definition 1.10.2):

token	spelling	Pebble \(\lvert\tau\rvert\)	Roslyn leading	Roslyn trailing
let	let	0	–	␣
x	x	1	–	␣
=	=	1	–	␣
1	1	1	–	–
;	;	0	–	␣// one⏎
y	y	20	␣␣/* two */␣	⏎
eof	–	1	–	–

Check: the spellings have \(3+1+1+1+1+1 = 8\) bytes and Pebble's trivia counts sum to \(0+1+1+1+0+20+1 = 24\), together the 32 bytes of the input; the Roslyn columns hold \(1+1+1+8+12+1 = 24\) trivia bytes too. In the Roslyn split the comment // one belongs to ; (same line) and /* two */ to y (next line).

Trivia as tokens

The same input with trivia tokens (rustc_lexer style): let, WS ␣, x, WS, =, WS, 1, ;, WS, COMMENT // one, WS ⏎␣␣, COMMENT /* two */, WS ␣, y, WS ⏎. The parser cursor skips the 8 trivia tokens and sees let x = 1 ; y, the same six tokens as Pebble's stream.

Incremental relexing

Old Pebble source let s = "ab";⏎let n = 1;⏎ (line 2 starts at byte 14; the lexer state, the interpolation stack, is empty at every boundary).

Edit 1: replace the 1 at byte 22 by 12 (\(a = 22\), \(b = 23\), \(\Delta = +1\)). The token = at 20 examined byte 21 (to rule out ==): extent 22, not greater than \(a\). The token 1 at 22 examined the ; at 23: extent 24 > 22, so it is the first affected token. Relex from its boundary (21): 12, ending at 24. The old token 1 ended at 23 and \(23 + \Delta = 24\), with the same (empty) state after it: resynchronized after one new token; ;, eof and everything else are reused, shifted by one.

Edit 2: insert " at byte 9, inside the string: line 1 becomes let s = ""ab";. The string token at 8 examined bytes up to 11 (extent 12 > 9): first affected. Relex: "" (8–10, a complete empty string), ab (10–12, an identifier), and a " at 12 that opens a string running to the line break: E0108, token "; (12–14). The old ; ended at 13, and \(13 + \Delta = 14\) = the new position, with the same empty state: resynchronized. Three new tokens and one diagnostic; line 2 is reused untouched. Without line-bounded string recovery the new string would run to the end of the file, as in the tree-sitter box.

4. Invariants and correctness

Tokens with attached trivia

Theorem 1.10.9 (Losslessness)

If every byte of \(w\) is either consumed by SkipTrivia or by ScanToken (the precondition of Algorithms 1.10.6 and 1.10.7), then the streams they produce are lossless (Definition 1.10.1), and SplitTrivia assigns every trivia byte to exactly one token.

Proof

By the invariant of Algorithm 1.10.6, after each token cursor equals the total length of the trivia and spellings emitted so far; each step appends exactly the bytes \([\mathit{triviaStart}, \mathit{cursor})\) as trivia and \([\mathit{cursor}, \mathit{end})\) as spelling, contiguous with the previous step. The loop ends at eof, whose position is \(\lvert w \rvert\), so the concatenation is \(w\). For SplitTrivia, trailing and leading are a partition of \(\theta\) into a prefix and a suffix. The same argument applies to trivia tokens (Algorithm 1.10.7). Pebble's unit test PebbleLexer.CorpusIsLossless checks the concatenation on every corpus file and RandomInputsAreLosslessAndTerminate on 3000 random inputs, including invalid UTF-8 and unterminated constructs. \(\square\)

Trivia as tokens

The correctness claim for trivia tokens is Theorem 1.10.9 (second part) together with the observation that a cursor that skips a fixed set of kinds presents the parser with exactly the non-trivia subsequence, which is the stream a trivia-skipping lexer produces when both lexers agree on token boundaries. The corpus comparison of Pebble's two lexers (Lesson 1.5's table lexer returns trivia tokens; TableLexer.AgreesWithTheHandWrittenPebbleLexer drops them and compares) is a mechanical check of that agreement.

Incremental relexing

Theorem 1.10.10 (Incremental relexing is exact)

Under the precondition of Algorithm 1.10.8, the returned list equals the full relex of \(w'\).

Proof sketch (full treatment: [WG98, §4])

Prefix: tokens \(0..k-1\) examined only bytes before \(a\) (their lookahead extents are \(\le a\)), which are unchanged, and they were produced from the same states; by determinism the full relex of \(w'\) produces them again. Middle: from token \(k\) on the algorithm is the full relex (it calls LexOne from the same position and state as the full relex would), so the invariant holds. Suffix: when the new stream reaches a boundary \(p \ge b + \Delta\) in state \(s\), and an old token boundary \(q\) (the end of old[j]) satisfies \(q + \Delta = p\) with the same state after it, then the bytes from \(p\) in \(w'\) equal the bytes from \(q\) in \(w\) (both are after the edit), and the states agree; by determinism the rest of the full relex of \(w'\) is the old suffix shifted by \(\Delta\). If no resynchronization happens, the loop relexes to eof and the result is a full relex. \(\square\)

When it breaks: a lexer with hidden state that is not recorded at token boundaries (a global counter, a symbol table used by a lexer hack, Lesson 1.7) violates determinism-from-a-boundary; the lexer state must be part of what is stored and compared. Unbounded lookahead (a raw string waiting for its delimiter) makes the lookahead extent large, so many tokens become "possibly affected".

5. Complexity

Variables: \(n = \lvert w \rvert\); \(m\) = number of tokens; \(d\) = number of tokens relexed after an edit; \(h\) = height of the token tree.

Technique	Time	Space	Notes
Leading trivia count (Pebble)	\(O(n)\), no extra work	4 bytes per token	text recovered from the buffer
Leading/trailing trivia lists (Roslyn, SwiftSyntax)	\(O(n)\)	trivia pieces per token	structured (kind of each piece)
Trivia tokens (rustc_lexer, rowan)	\(O(n)\); parser skips them	one token per trivia run	green trees share subtrees
Incremental relexing	\(O(d + \log m)\) with a balanced token tree (locate the first affected token in \(O(\log m)\), relex \(d\) tokens)	old token list + states	worst case \(d = \Theta(m)\)

Proposition 1.10.11 (Incremental relexing can be forced to relex everything)

For a lexer whose strings may span lines, inserting one " near the start of a file of \(m\) tokens can force \(d = \Theta(m)\) tokens to be relexed. For Pebble, whose strings end at a line break, a single-byte edit relexes at most the tokens of the edited line plus one, provided that in both the old and the new text no block comment and no interpolation is open at the end of the edited line. Without that proviso Pebble also has a \(\Theta(m)\) case: inserting * after a / opens a block comment that can run to the end of the file.

Proof

Multi-line strings: after the inserted quote, every later quote pairs differently (open/close roles swap), so no old boundary is reached in the same state until the end of the file (the tree-sitter box shows this). Pebble: a string piece cannot extend past a line break (E0108 ends it there), so the only lexer state that can survive a line break is an open block comment (trivia, which may span lines) or a non-empty interpolation stack (code inside \( … ) may span lines). Under the proviso, both the old and the new lexer are outside any comment and have an empty stack at the end of the edited line, so the first token of the next line starts at corresponding positions (\(q + \Delta = p\)) in the same state in both runs: the relex resynchronizes there (Theorem 1.10.10), after the tokens of the edited line and at most the one token that crosses its end. The counterexample: in a / b followed by \(m\) lines of code without */, inserting * after the / turns every later byte into comment trivia, and no old boundary is reached in the same state until the end of the file. \(\square\)

At scale. tree-sitter reparses a typical keystroke in microseconds to a few milliseconds regardless of file size, because only the damaged region is relexed and reparsed [TS-Parser]; the Pebble lexer relexes a 10 000-line file from scratch in about 3 ms (104 MB/s in ch01-regexbench, ~300 KB), which is why a batch compiler does not bother.

6. Variants and refinements

Tokens with attached trivia

• Structured trivia (Roslyn): preprocessor directives and XML doc comments are trivia with their own syntax trees, so tools can inspect them.
• Trivia pieces vs byte counts: SwiftSyntax stores trivia as arrays of TriviaPiece (spaces(4), lineComment("// x")) [SWIFTSYNTAX-Trivia]; Pebble stores only a count and relies on the buffer.

Trivia as tokens

• Green/red trees (Roslyn and rowan): immutable, position-free green nodes shared across versions; red nodes computed on demand add parent pointers and absolute offsets.
• Token-skipping at the parser boundary (rust-analyzer's LexedStr → parser input) vs trivia in the grammar (rarely done: it pollutes every production).

Incremental relexing

• Lookahead-based invalidation (Wagner–Graham [WG98], tree-sitter): store each token's lookahead extent and invalidate exactly the tokens whose extent crosses the edit.
• Line-based relexing (many editors' syntax highlighters): store the lexer state at every line start and relex line by line until the state at a line start matches the old one; simple and robust when tokens rarely span lines.

7. In real compilers

Tokens with attached trivia

• Roslyn src/Compilers/CSharp/Portable/Parser/Lexer.cs — LexSyntaxLeadingTrivia, LexSyntaxTrailingTrivia, LexSyntaxTrivia (tag Visual-Studio-2022-Version-17.12) [ROSLYN-Lexer].
• SwiftSyntax Sources/SwiftSyntax/Trivia.swift — Trivia, TriviaPiece (tag 600.0.1) [SWIFTSYNTAX-Trivia].
• Pebble Token::LeadingTrivia (pebble/include/pebble/Lex/Token.h); box in §2.

Trivia as tokens

• rustc compiler/rustc_lexer/src/lib.rs — tokenize, Cursor::advance_token returning Whitespace, LineComment, BlockComment (Rust 1.94.1) [RUSTC-Lexer]; box in §2.
• rust-analyzer crates/parser/src/lexed_str.rs — LexedStr::new maps rustc_lexer::TokenKind::Whitespace to WHITESPACE and comments to COMMENT (tag 2026-09-21) [RA-LexedStr].

Find where LLVM does it. Clang's lexer can keep comments: open clang/lib/Lex/Lexer.cpp at llvmorg-23.1.2 and find how SkipLineComment behaves when the lexer is in "keep comments" mode. Question: which member function reports whether comments should be returned as tokens? (Quiz llvm-keep-comments.)

Incremental relexing

• tree-sitter lib/src/parser.c — ts_parser__lex, ts_parser__can_reuse_first_leaf, ts_parser__reuse_node; lib/src/lexer.c — ts_lexer__advance (tag v0.25.3) [TS-Parser]; box in §2.

8. Comparison

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Tokens with attached trivia	lossless; trivia owned by tokens	no overhead in lexing	tools see comments next to their tokens	small (count) to moderate (structured pieces)	Roslyn, SwiftSyntax, Pebble
Trivia as tokens	lossless; uniform token stream	slightly more tokens; parser skips them	exact positions of every comment	small in the lexer, a skipping cursor in the parser	rustc_lexer, rust-analyzer, the lab's table lexer
Incremental relexing	exact (Theorem 1.10.10)	\(O(d + \log m)\) per edit, \(d\) usually tiny	same tokens as a full relex	high (states, extents, resync)	tree-sitter, IDEs, editors

Choose attached trivia when your syntax tree API should present "a token and its comments" (refactoring, formatting). Choose trivia tokens when you want the lexer to stay simple and let a tree library attach them. Add incremental relexing when the lexer serves an editor; design string and comment recovery so that damage stays local.

9. Assessment

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Tokens with attached trivia	trivia-count, roslyn-trailing	./course drill lexer-modes (hard also asks structure); justification below	trivia	E5
Trivia as tokens	trivia-tokens-count, llvm-keep-comments	justification below	trivia-tokens	Lab L7 ★ (the table lexer returns trivia tokens)
Incremental relexing	incremental-first-token, incremental-worst-case	justification below	incremental-relexing	—

No drill generates trivia or incremental-relexing problems: the computations are counts and boundary searches on a given input, which the quiz asks directly (trivia-count, incremental-first-token); the corpus test PebbleLexer.CorpusIsLossless is the practice for implementing losslessness.

Pitfall

Losslessness is easy to lose in error paths: a lexer that silently skips an invalid byte, or ends an unterminated comment without accounting for its bytes, produces a stream whose concatenation is shorter than the file. Pebble turns every invalid byte into an unknown token for this reason, and the random-input test checks it.

References

See the chapter references.