Token Metadata
Kind, value and position. The first two are obvious; the third is the one that pays for itself, because every diagnostic, hover, rename, source map and debugger line table in the entire toolchain is derived from byte ranges recorded once, here, and never recoverable afterwards.
Why does every token need to remember exactly where it came from, when the parser only looks at the kind?
A token as a record with three parts: the *kind* the grammar matches on, the *value or text* a later phase will interpret, and the *span* — a half-open byte range into a specific source file. The span is the only field no later phase can reconstruct, which is what makes it structurally different from the other two.
A span must identify a range in the original source text, not in any transformed version of it. This is a real constraint rather than a formality: once a preprocessor, a macro expander or a template instantiator has produced text nobody wrote, a span into *that* text is useless to a user, so every such transformation must carry an expansion history alongside the range or the diagnostics it produces are unactionable.
Key points
- A token is kind, payload and span; only the span cannot be recomputed by re-lexing, which is why dropping it is permanent.
- Spans propagate upward through AST, IR and machine code, ending as the line table a debugger reads.
- Line and column are derived from byte offsets by a side index, not stored per token — that is what makes incremental reparsing viable.
- Real compilers store an encoded location id rather than a line/column pair, so that macro expansions have representable positions.
- Byte offsets, Unicode scalar offsets and UTF-16 code units are three different numbers; the LSP uses UTF-16 and compilers use bytes.
- Spans are half-open, which makes length, adjacency and zero-width insertion points all fall out without special cases.
- The right caret for a missing token is at the *end* of the previous token, which is only available if every token recorded one.
Three fields, and only one of them is unrecoverable
A token record has a kind, some payload, and a position. The kind can be recomputed by re-lexing. The payload can be recomputed by re-lexing. The position cannot be recomputed by anything, because once the token list exists the relationship between it and the original bytes is gone unless it was written down.
That asymmetry is the whole lesson. A compiler that discards spans is not slightly worse at diagnostics — it is permanently incapable of them, and no later phase can fix it. The best such a compiler can do is "syntax error", which is what compilers in fact said for the first thirty years of the field.
The example below is two lines, and the interesting token is the last identifier. z occupies bytes 23 to 24 — one byte — and that is exactly what a diagnostic will underline. Not the line, not the statement: the name. The difference between an error message that says "line 2" and one that draws a caret under z is entirely in whether these two numbers were recorded.
let x = 1;
let y = x + z;Read it asTwenty-five bytes, twelve tokens. Line and column are *derived* from these offsets by a separate line-index table, not stored per token — which is why an off-by-one in the offsets moves every reported position at once, and why rebuilding the line index after an edit is cheaper than renumbering every token.
What the span buys, concretely
[[symbolication]] exists as a separate step for those builds.It is easy to agree that positions are good and hard to see how much rests on them. The list below is not a list of nice-to-haves; each item is a product feature that is impossible without spans and nearly free with them.
The pattern to notice is that spans propagate *upward*. An AST node takes the span covering its tokens; a type error on that node reports that span; an IR instruction carries the AST node's span as debug metadata; a machine instruction inherits it; and the line table in the binary is that metadata serialised. One recording at the lexer becomes a debugger breakpoint twelve stages later. Every stage that drops it breaks the chain permanently for everything after.
- Diagnostics with a caret. "expected
;after expression" with the caret under the exact byte, rather than a line number and a guess. - Suggested fixes. A machine-applicable suggestion is a span plus replacement text. Without the span there is nothing to replace — see
[[suggested-fixes]]. - Language server features. Go-to-definition maps a cursor offset to a token to a symbol; hover, rename, find-references and semantic highlighting are all the same lookup — see
[[lsp]]. - Source maps. A JavaScript bundle's stack trace names your TypeScript file because a mapping from generated ranges to original ranges was carried through every transformation — see
[[source-maps]]. - Debug information. A breakpoint on a line works because the compiler emitted a line table mapping machine addresses back to source positions that started life as token spans — see
[[debug-information]]. - Coverage and profiling attribution. Line-level coverage and per-line profile annotations are both span lookups against the same tables.
Representing a span is a real decision
The obvious representation is a (line, column) pair per token. It is also the one production compilers avoid, for three reasons. It is larger; it must be recomputed when text above it changes, which is fatal for an incremental language server; and it cannot represent a position inside a macro expansion, because there is no line in any file that corresponds to it.
What real compilers store instead is a single integer offset into a global coordinate space, with a side table doing the interpretation. Clang's SourceLocation is a 32-bit value indexing a SourceManager that knows about files, macro expansion records and include stacks — which is why Clang can print "in expansion of macro X, expanded from macro Y" backtraces at all. rustc uses a byte-offset Span into a global SourceMap, with expansion context in a side table, for exactly the same reason.
The column question has a second trap that only appears with non-ASCII source. A byte offset, a Unicode scalar offset and a UTF-16 code unit offset are three different numbers for the same position, and they disagree the moment an emoji or an accented character appears. The Language Server Protocol specified UTF-16 code units because that is what JavaScript strings are indexed in; compilers overwhelmingly work in bytes. A language server therefore performs a conversion at the boundary, and a server that forgets it produces squiggles that drift right by one character per non-ASCII character earlier on the line.
| Representation | Size | Survives an edit above it | Macro expansions |
|---|---|---|---|
| (line, column) pair | Two integers per token | No — every position below shifts | Cannot represent them |
| Byte offset into one file | One integer per token | Positions below shift by the edit delta | Cannot represent them |
| Offset into a global source mapimplementation | One integer, plus a shared table | Same, but the table absorbs file identity | Only with a side table |
| Encoded location id (Clang)implementation | 32 bits | Same | Yes — expansion is part of the coordinate space |
The half-open convention, and why off-by-one here is so expensive
Spans are conventionally half-open: [start, end), where end is the offset one past the last byte. The convention matters because it makes the arithmetic total — length is end - start, adjacency is a.end === b.start, and an empty span at a position is [p, p), which is what an "insert here" suggestion needs. A closed convention makes all three special cases.
An off-by-one in span computation is unusually expensive to live with because it is *systematic*. Every diagnostic in the compiler shifts by one, so the bug does not look like a bug in the lexer — it looks like the compiler being vaguely bad at pointing at things, and it is usually rationalised for a long time before anyone measures it. The classic version is recording the position *after* the match rather than before, which points every error at the token following the mistake.
The related trap is the error position for a missing token. When the parser wants a ; and does not find one, the useful caret is at the *end of the previous token*, not at the start of the unexpected one — because that is where the user should type. Getting this right is what separates "expected ;" pointing at the next line from "expected ;" pointing at the exact gap, and it needs the previous token's end, which is only available if spans were recorded.
How it works
The steps, in the order the compiler takes them.
- Record the start offset before consuming any characters of the token, and the end offset after the last one.
- Store the pair on the token, and store a file or source-map identifier alongside it or encode it into the offset space.
- Build a line-start index once per file so that
(line, column)can be derived by binary search when a message is actually printed. - Give every AST node a span covering its first token's start and its last token's end, so structure inherits position automatically.
- Thread that span into IR instructions as debug metadata and preserve it across transformations, or accept that the transformation is a point at which debugging becomes harder.
- Convert at every external boundary — to UTF-16 for the LSP, to line/column for a terminal message, to a DWARF line entry for a debugger.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- Every error message points one character past the actual problem, because the start offset was recorded after the match rather than before. It reads as the compiler being imprecise rather than as a bug.
- A user with a non-ASCII identifier earlier on the line sees the editor squiggle land several characters to the right of the error, and only users writing non-ASCII source ever report it.
- A macro-generated error reports a position inside expanded text the user never wrote, so the message names a line that does not exist in their file.
- A bundler transforms code without maintaining the mapping, and every production stack trace names a generated file and a column in the ten-thousands.
- An optimizer merges two instructions and keeps one of their spans arbitrarily, so a breakpoint on one source line silently never fires and the debugger reports the other line instead.
- The compiler reports "expected
;" at the start of the following line rather than at the end of the offending statement, and users consistently insert the semicolon in the wrong place.
When it helps
- Any tool that has to communicate with a human about a specific piece of their source, which is every compiler, linter, formatter and language server.
- Any pipeline with more than one transformation step, where the only way to attribute a runtime failure to authored code is a chain of preserved mappings.
- Incremental tooling, where a byte-offset representation lets an edited region be reparsed without renumbering everything after it.
When it hurts
- Spans cost memory on every token and every node, which on a very large translation unit is a real number — Clang's
SourceLocationis 32 bits specifically to keep it down. - For a compiler that will only ever consume machine-generated input and report to a machine, the diagnostic payoff is zero and the memory is spent for nothing.
What it costs
Every one of these is paid by something.
- Recording spans costs memory proportional to token and node count, plus discipline in every transformation, and buys every diagnostic, IDE feature and debugging capability the toolchain will ever have.
- An encoded location id buys macro-expansion backtraces and a compact representation, and costs a
SourceManager-style indirection that every consumer must go through — you can no longer read a position without a context object. - Preserving spans through optimization buys debuggable release builds and costs both metadata size in the binary and constraints on how freely a pass may merge or reorder instructions while keeping attribution honest.
- Converting to UTF-16 at the LSP boundary buys editor correctness and costs a per-line scan of the source text on every position exchange, which shows up on very long lines in minified files.
What else you could do
What a different compiler or language does instead, and when that is better.
- Line-and-column pairs stored directly, which is what many small tools and DSL implementations do. Simpler to read in a debugger, and it gives up macro positions and incremental reparsing.
- No spans at all, reporting only "syntax error". This is what a first-pass toy implementation does, and it is a decision that cannot be reversed cheaply once the rest of the compiler assumes tokens are positionless.
- A full concrete syntax tree that retains every byte including trivia, so positions are implied by the tree rather than stored. This is the tree-sitter and Roslyn model; it makes formatting and full-fidelity round-tripping trivial and costs substantially more memory — see
[[concrete-syntax-tree]].
See it for yourself
The flag, dump or tool that shows you this directly.
clang -Xclang -dump-tokens -fsyntax-only x.cprints aLoc=<file:line:col>for every token, which is the decoded form of theSourceLocationthis lesson describes.clang -fcaret-diagnostics(on by default) draws the caret and the underline;-fno-caret-diagnosticsturns it off, which shows exactly what is lost without spans.python3 -m tokenize file.pyprintsstartandendas(row, col)pairs for every token, including the exact ranges of multi-line strings.readelf --debug-dump=decodedline a.outorllvm-dwarfdump --debug-line a.outprints the line table — the far end of the chain that began with these offsets.- For a source map,
npx source-map-clior the browser devtools "original source" view both resolve a generated position back through the mapping.
Plausible wrong readings
Stated the way a confident engineer states them.
- "Spans are for error messages." They are for error messages, fixes, hover, rename, find-references, coverage, profiling attribution, source maps and debugging. Error messages are the cheapest thing they buy.
- "The parser can recompute positions." It cannot. Once the token list exists, the mapping back to bytes is gone unless it was stored.
- "A column is a column." Byte, scalar and UTF-16 columns are three different numbers, and the LSP and your compiler almost certainly disagree about which one they mean.
- "Storing line and column is simpler." It is simpler until an edit happens above the token, or until a macro expands, at which point it is unusable.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
Every token records what kind it is, what text it matched, and where in the file it came from. The position is the important one: it is the only part that cannot be worked out again later, and it is what lets a compiler draw a caret under the exact character that is wrong.
practical
Store half-open byte offsets, derive line and column only when printing, and record the start offset *before* consuming the token. For a missing-token error, point the caret at the end of the previous token rather than the start of the next one — that is where the user has to type. If you are writing a language server, convert to UTF-16 code units at the protocol boundary or negotiate UTF-8, because the LSP default is not what your compiler is using.
advanced
The design pressure on span representation comes from two directions that pull opposite ways. Diagnostics want rich positions with expansion history, which argues for an indirected coordinate space. Memory wants one small integer per node on a translation unit with millions of nodes, which argues for the opposite. Clang resolves it by making the coordinate space itself carry the structure: a 32-bit id whose value range partitions into file locations and macro-expansion locations, so a location *is* the expansion chain without a per-token side field. The cost is that no position can be interpreted without the SourceManager, so every layer of the compiler takes a context object it would otherwise not need, and serialising an AST means serialising the source manager with it. That single decision shapes the API of the entire front end, which is a good illustration of how a data-representation choice in the lexer becomes an architectural constraint everywhere.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
SourceLocation plus SourceManager, and rustc's Span plus SourceMap. GCC uses location_t with its own line-map structure and reaches a similar result by different means. A compiler for a language without macros — Go, for instance — has no reason for the indirection and stores a file plus offset directly.[[debugging-optimized-code]].If you were asked this in an interview
- Why can a compiler not recompute token positions after the fact?
- The parser wants a semicolon and does not find one. Where should the caret go, and what does that require?
- Your language server's squiggles are offset for users writing Japanese comments. What is wrong?
Connections
- Programming Languages & Runtime Internals — How a runtime turns a return address into a source line at the moment an exception is thrownThe line table is emitted by the compiler from these spans, but the lookup at throw time — and what it costs to capture a stack trace — is the runtime's side of the same mechanism.