Diagnosticsimplementation

Spans and Ranges

A span is two offsets, half-open, threaded through every stage of the compiler. This is the lesson where the discipline of carrying them finally pays: underlines, secondary labels, jump-to-definition, rename, quick fixes and source maps are all one data structure.

The question

Why do compilers store a range rather than a position, and what does carrying it through every phase actually buy?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

A span is [start, end) — two byte offsets, half-open — attached to every token, every AST node, every IR instruction that a human could ever be told about, and every symbol. It is the only thing in the compiler that still refers to the source text after the source text has been abstracted away, and its purpose is to answer, at any stage, the question "which characters is this about" — asked by a phase that has long since discarded the characters.

What this phase may assume or do

A phase that constructs a node from other nodes must give it a span covering all of them; a phase that transforms a node must carry its span forward or explicitly mark the result as compiler-generated. This is a real obligation and it is enforced by nothing: a transformation that invents a node with an empty span produces a diagnostic pointing at byte zero, and no test that checks *behaviour* will catch it. The half-open convention is what makes the arithmetic sound — end - start is the length, start == end is a valid empty position, and adjacent spans neither overlap nor leave gaps.

Key points

A span is [start, end) — half-open byte offsets — which makes length subtraction, empty spans representable, and adjacent spans tile exactly.
A zero-width span is an insertion point, and it is what every suggested fix that adds text is built on.
A node's span is the union of what it was built from, never the span of its first token.
Nodes need more than one span: the operator's, the argument list's, the signature's. Those extras are the difference between a helpful diagnostic and a technically correct one.
Every IDE feature — jump-to-definition, find-references, rename, hover, folding, quick fixes — is a span query. The frontend that threaded spans became a language server.
Spans are compressed to stay affordable at scale: rustc packs one into 32 bits over a global offset space, spilling macro context to a side table.
A macro-expanded token has no single source location, so a span must encode an expansion chain, not a range.
Spans die at desugaring, at optimization and at code generation, and each death removes a category of tooling permanently.

Half-open, and why the convention is load-bearing

A span is [start, end): start included, end excluded. This is the same convention as a slice, an iterator range and every well-behaved interval API, and the reasons are the same three.

Length is subtraction. end - start, with no off-by-one, ever. Under a closed convention the length is end - start + 1 and every place that forgets the + 1 produces an underline one character short.

Empty is representable. start == end is a valid, zero-width span. That matters far more here than it sounds: an *insertion point* is a zero-width span. "Add a semicolon here" is a suggested fix whose range is empty. Under a closed convention [5, 4] is the only way to express it, which every consumer treats as malformed.

Adjacency composes. [0, 3) and [3, 7) are adjacent with no overlap and no gap, so the union of a node's children's spans is exactly what you expect, and a sequence of tokens tiles the source exactly. Under a closed convention adjacency requires end + 1 == start, and the arithmetic leaks into every consumer.

The convention is essentially universal — LSP ranges are half-open, rustc's spans are half-open, tree-sitter's byte ranges are half-open — and the one place it commonly goes wrong is a hand-rolled underline renderer that computes end - start + 1 carets out of habit.

Nodes get their spans from their children

The rule is mechanical and it is the one people get wrong: a node's span is the union of everything it was built from, not the span of its first token. The parser in [[recursive-descent]] computed join(left.span, right.span) for exactly this reason.

And a node frequently needs more than one span. A binary expression carries the span of the whole expression *and* the span of the operator token, so a type error about + can underline the operator rather than the whole line. A function carries the span of its signature separately from the span of its body, so "this function is too complex" underlines the name and not four hundred lines. A call carries the span of the argument list separately, so "expected 2 arguments, found 3" can underline the third argument.

Those extra spans cost eight bytes each and are the entire difference between a diagnostic that helps and one that is technically correct. They also cannot be added later without touching every construction site, which is why they get added on day one or never.

Spans on an AST for foo(a, b + 1) — note that nodes carry more than one

AST — only what later phases match on

Call“foo(a, b + 1) [0,13)”— Also carries the argument-list span [3,13) so an arity error can underline just the arguments.

├── Name foo“foo [0,3)”— The callee span, used for jump-to-definition and for "cannot find function `foo`".

├── Name a“a [4,5)”

└── Binary +“b + 1 [7,12)”— Union of its children. Also carries opSpan [9,10) so a type error can underline the `+` alone.

├── Name b“b [7,8)”

└── Number 1“1 [11,12)”

Read it asEvery span is a union of its children plus the punctuation the node consumed. The Call node spans byte 0 to 13 because it includes the closing parenthesis, which is not any child's span — punctuation is dropped as a node and kept as an extent. That is [[parse-tree-vs-ast]]'s projection done correctly: discard the node, keep the position.

What the span is spent on

This is the payoff, and it is worth enumerating because the cost was paid in the lexer and the benefit arrives everywhere else. Every feature below is a query over spans, and none of them is implementable without them.

Notice how many are not compiler features at all. Jump-to-definition, find-references, rename, hover, semantic highlighting, code folding and quick fixes are IDE features, and they exist because a compiler frontend recorded ranges. That is the strongest argument for the discipline: the frontend that threaded spans became a language server, and the one that did not stayed a compiler.

Everything that is a span querytypical

Feature	The query	Needs
Error underline	Render the span's line, underline start..end	One span, plus the original buffer
Secondary label	Render a second span with its own message	Two spans, possibly on different lines
"Expected 2 args, found 3"	Underline the extra argument only	A per-argument span, not just the call's
Jump to definition	Cursor offset → node → symbol → declaration span	Spans on both the use and the declaration
Find references	Symbol → every node bound to it → their spans	Spans preserved through name resolution
Rename	Find references, then edit each byte range	Spans that index the file exactly, or the edit corrupts it
Quick fix / fixit	Emit (span, replacement) pairs	Zero-width spans for pure insertions
Semantic highlighting	Every token span plus its resolved kind	Spans surviving into the typed AST
Code coverage	Map an executed IR instruction back to a range	Spans surviving lowering into IR
Source maps / debug infoimplementation	Map generated position → original span	Spans surviving all the way to codegen

Making them cheap enough to carry everywhere

implementationThe 32-bit packed span with an out-of-line spill table is rustc's design (rustc_span::Span plus SpanData); Clang uses a comparable scheme with SourceLocation as an opaque offset into a SourceManager that also encodes macro expansion. Go's token.Pos is a plain offset into a FileSet with no macro machinery, because Go has no macros. The compression is worth copying only where node counts are large; a small frontend should store two u32s and move on.

A span on every node is not free. Two 64-bit offsets is sixteen bytes per node, on a tree with millions of nodes, and if a node needs three spans it is forty-eight. That is a serious fraction of frontend memory, and the temptation is to attach spans only where a diagnostic currently needs them — which forecloses every diagnostic you have not written yet.

The standard answer is compression. rustc packs a Span into 32 bits covering a *global* offset space across every file in the crate, so one integer identifies file and range together; spans that are too large to pack, or that carry macro-expansion context, spill to an out-of-line SpanData table indexed by that integer. The result is four bytes per span and full expressiveness for the rare cases, which is what makes "a span on absolutely everything" affordable.

The macro case is worth naming separately, because it is where spans stop being a range and start being a *history*. When a macro expands, the resulting tokens exist at no source location — they came from the macro body, invoked at the call site, possibly nested several deep. A span must therefore be able to say "this token is from the macro definition at X, expanded at Y, itself expanded at Z", which is why rustc's SyntaxContext and Clang's SourceLocation both encode expansion chains rather than plain offsets. Without it, an error inside an expanded macro points at the macro definition and the user has no idea which of their forty call sites caused it.

Span operations that every frontend ends up needing

1#[derive(Copy, Clone, PartialEq, Eq)]
2pub struct Span { lo: u32, hi: u32 }   // half-open [lo, hi), global offset space
3 
4impl Span {
5    /// The union: a parent node's span from its children's.
6    pub fn to(self, other: Span) -> Span {
7        Span { lo: self.lo.min(other.lo), hi: self.hi.max(other.hi) }
8    }
9 
10    /// The gap between two spans — "expected a semicolon HERE".
11    pub fn between(self, other: Span) -> Span {
12        Span { lo: self.hi, hi: other.lo }
13    }
14 
15    /// Everything from self up to (not including) other — trims a trailing token.
16    pub fn until(self, other: Span) -> Span {
17        Span { lo: self.lo, hi: other.lo }
18    }
19 
20    /// Zero-width at the end: the insertion point for a suggested fix.
21    pub fn shrink_to_hi(self) -> Span {
22        Span { lo: self.hi, hi: self.hi }
23    }
24 
25    pub fn contains(self, other: Span) -> bool {
26        self.lo <= other.lo && other.hi <= self.hi   // cursor-in-node, for the IDE
27    }
28 
29    pub fn len(self) -> u32 { self.hi - self.lo }    // no +1 anywhere
30}

shrink_to_hi is the operation that only exists because the convention is half-open, and it is the one that suggested fixes are built on: "insert ; after this expression" is a replacement over a zero-width span. between is how a parser says "you are missing something *here*" rather than pointing at the token that followed. Neither is expressible if a span is a single position.

Where spans die, and what dies with them

Spans are lost at three predictable points, and each loss removes a category of feature permanently.

Desugaring and lowering. A for loop rewritten into a while produces nodes that correspond to no source text. If they are given empty spans, an error inside a desugared construct points at nothing; if they are given the whole loop's span, the error points at four lines. The correct answer is a span that records both the source range and the fact that it was compiler-generated, which is what rustc's ExpnKind::Desugaring does — and it is why an error in an async block can still say which await caused it.

Optimization. An optimizer that merges two instructions has to choose a span, and there is no right answer — which is exactly why [[debugging-optimized-code]] is hard and why a debugger steps erratically through optimized code.

Code generation. Spans become line-table entries in debug info, or entries in a source map for a compile-to-JavaScript language. Everything not encoded there is gone, and the granularity of what survives is the granularity a debugger can offer — see [[debug-information]] and [[source-maps]].

How it works

The steps, in the order the compiler takes them.

The lexer records [start, end) for every token as byte offsets into the unmodified source buffer.
The parser gives each node the union of the spans of every token and child it consumed, including punctuation it did not keep as a node.
Constructs that need finer detail record additional spans — the operator, the argument list, the signature — at construction time, because they cannot be recovered later.
Name resolution attaches spans to symbols, so a declaration has a location and every use can be traced to it.
Desugaring gives generated nodes a span that records both the originating source range and the fact of generation, so an error inside a desugared construct still points somewhere meaningful.
Diagnostics carry a primary span plus zero or more labelled secondary spans; the renderer converts each to (line, column) only at the point of display.
Lowering to IR attaches the span of the originating construct to each instruction, which becomes debug-info line entries or source-map segments at code generation.
A language server converts spans to protocol ranges at the boundary, in the negotiated position encoding — see [[source-locations]].

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

An underline is one character too long on every diagnostic, because the renderer computed end - start + 1 carets for a half-open span.
A diagnostic about a compound expression underlines only its first token, because the node took its span from its leftmost child instead of the union.
A quick fix that should insert a semicolon replaces the preceding token instead, because a zero-width insertion point was implemented as a one-character span.
Rename corrupts a file: the byte ranges were computed against a normalised buffer and applied to the original, so every edit after the first non-ASCII character lands in the wrong place.
An error inside an expanded macro points at the macro definition, and the user cannot tell which of forty call sites triggered it.
A desugared for loop reports an error at byte zero of the file, because the generated nodes were constructed with a default span nobody filled in.
A debugger steps backwards through optimized code, because merged instructions inherited the span of whichever operand happened to be first.
An IDE feature is proposed two years in and is impossible, because spans were attached only to the nodes that had diagnostics at the time.

When it helps

Building any tooling on a frontend: the answer to "can we support rename" is entirely determined by whether spans index the original file exactly.
Improving a diagnostic from "somewhere in this expression" to "this operator": usually the fix is to record one more span at construction, not to change the analysis.
Debugging misplaced underlines and off-by-one carets, where the half-open convention is the first thing to check.
Reviewing a new pass: any node it constructs without an explicit span is a future diagnostic pointing at byte zero.

When it hurts

A one-off script or a code generator whose output nobody debugs. Threading spans through it costs real effort and buys nothing.
Frontends whose node count makes uncompressed spans a memory problem and whose team does not have the appetite for an interning scheme — in which case the honest choice is fewer nodes, not fewer spans.

What it costs

Every one of these is paid by something.

A span on every node buys every present and future diagnostic and every IDE feature, and pays eight to sixteen bytes per node — a substantial fraction of frontend memory on a large crate, which is why compression schemes exist.
Multiple spans per node buy precise underlines — the operator, the third argument, the signature — and pay both memory and the discipline of populating them at every construction site, with nothing to catch the ones that were missed.
Encoding macro-expansion chains buys errors that point at the user's call site rather than the macro body, and pays an indirection on every span access plus a side table that must be kept alive for the whole compilation.
Interning spans into 32 bits buys affordability at scale and pays a hard limit on total source size per compilation unit, plus a debugging experience where a span is an opaque integer until you resolve it.
Carrying spans through lowering and optimization buys debuggable optimized code and source maps, and pays a decision at every merge about which span survives — a decision that is frequently arbitrary and shows up as a debugger stepping oddly.

What else you could do

What a different compiler or language does instead, and when that is better.

Store a single position rather than a range. Halves the memory and eliminates underlines, secondary labels, rename and every fix that replaces text. Some early compilers did this and none added it back cheaply.
Store (line, column) pairs, which makes rendering trivial and every span operation — union, containment, adjacency — a special-cased comparison. See [[source-locations]].
Reconstruct positions by re-lexing on demand rather than storing them, which trades memory for time and fails as soon as a node has no direct token correspondence.
Keep a lossless concrete syntax tree so every node *is* a range into the buffer by construction, as tree-sitter and rowan do. Spans become derived rather than stored — see [[concrete-syntax-tree]].

See it for yourself

The flag, dump or tool that shows you this directly.

rustc: --error-format=json prints byte_start and byte_end for every span in every diagnostic, including the secondary labels, which makes the multi-span structure of a real error visible.
RUSTC_LOG or -Z macro-backtrace shows the expansion chain behind a span, which is the clearest demonstration that a span is a history and not just a range.
Clang: -fdiagnostics-print-source-range-info appends the exact ranges to each diagnostic in a machine-readable form.
tree-sitter: every node exposes start_byte, end_byte, start_point and end_point; tree-sitter query lets you select nodes and print their ranges, which is the span-query model made directly usable.
LSP: enable verbose tracing in your editor and read the range objects in publishDiagnostics and in a textDocument/rename response — the rename edits are literally a list of spans and replacements.
Our pipeline explorer at /compilers/pipeline links spans across all eight panels; clicking an IR instruction highlights the characters it came from, which is only possible because every intermediate stage carried the span forward.

Plausible wrong readings

Stated the way a confident engineer states them.

"A span is where the error is." A diagnostic usually needs several: where it was detected, where the conflicting thing was declared, and where the fix goes. A single span is why some compilers can only say "somewhere around here".
"Half-open versus closed is a style preference." It decides whether an insertion point is representable at all, which decides whether machine-applicable fixes are possible.
"We can compute spans later from the AST." Only for nodes that correspond to source text. Anything desugared, synthesised or merged has no derivable span, and those are exactly the constructs whose errors are most confusing.
"Spans are a frontend concern." They are how a debugger maps an instruction back to a line, how a coverage tool attributes execution, and how a source map works. They are a whole-pipeline concern that happens to originate in the frontend.
"Storing spans is expensive so we should be selective." Selective means the feature you have not thought of yet is impossible. The industry answer is to make spans cheap enough to store unconditionally, not to store fewer.

Misconceptions

The claim, and what is actually true.

A span is just a convenience for error messages.

It is the only remaining link between every later representation and the source text. Debug info, source maps, coverage, rename and every IDE navigation are all downstream of it.

The end offset is the last character of the construct.

It is one past it. Under a half-open convention end is not part of the span, which is what makes length subtraction and zero-width insertion points work.

Compiler-generated nodes do not need spans because the user did not write them.

The user wrote the construct that generated them, and an error inside a desugared async block or an expanded macro is exactly where a missing span hurts most.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

A span is a pair of byte offsets marking a stretch of source: start included, end excluded. Every token and every tree node carries one, and a node's span covers everything inside it. That one piece of bookkeeping is what lets a compiler underline the exact characters in an error, and what lets an editor jump to a definition, rename a variable or offer a fix — all of those are just questions about which node a range belongs to.

practical

Use half-open ranges everywhere and never write + 1. Give every node the union of its children rather than its first child's span, and record the extra spans — the operator, the argument, the signature — at construction, because you cannot recover them later. When a diagnostic points at the wrong thing, the bug is almost always at the construction site rather than in the analysis. And when you desugar or synthesise nodes, give them a span deliberately: an unfilled default is how errors end up pointing at byte zero.

advanced

The design question spans force is whether your compiler is a compiler or a frontend platform. A compiler needs a span where it currently emits a diagnostic. A platform needs a span on everything, because the next consumer — a linter, a refactoring engine, a coverage tool, a language server — will ask about nodes nobody anticipated. That is only affordable if a span costs four bytes rather than sixteen, which is why the interning work is not micro-optimization but the thing that makes the platform possible. The same reasoning explains the macro-expansion context: a span that is merely a range is adequate until the code was generated, at which point it must become a history, and retrofitting a history into a type that every pass copies by value is a change touching the entire frontend. Both decisions are made once, early, and everything the frontend can ever support is downstream of them.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationThe Span API shown — to, until, between, shrink_to_hi — is modelled on rustc's rustc_span::Span, whose exact method set changes between versions. Clang exposes the equivalent through SourceRange and SourceManager; Go's token.Pos has no span type at all, since Go diagnostics point at a position rather than a range. The operations generalise; the names do not.

typicalThat spans survive into debug info and source maps is true of mainstream toolchains at default optimization settings, and degrades sharply as optimization increases: merged, hoisted and vectorized instructions have no single originating span, and the line table records a choice rather than a fact. Any claim that a debugger will show the right line for optimized code needs measuring, not assuming.

simplifiedOur spans are byte offsets into one buffer. Real frontends additionally carry a file identity (or a global offset space that encodes it), an expansion context for macro-generated tokens, and often a flag distinguishing user-written from compiler-generated code. Each of those exists because a diagnostic pointed somewhere useless without it.

If you were asked this in an interview

Why half-open rather than inclusive ranges?
A type error on a + b underlines the whole statement. Where is the bug, and what would you change?
What has to be true of a compiler frontend before you can build a rename refactoring on it?

Connections

DSAbinary-search interval-tree n-ary-tree

Domains that do not exist yet

Testing & Reliability Engineering — Golden-file testing of rendered output
Span bugs are invisible to behavioural tests and obvious in a rendered diagnostic, so the standard defence is snapshot testing of the exact printed output. The technique is owned there; [[golden-tests]] is our compiler-specific treatment.