Spans, Source Maps, and Diagnostics

This is the chapter that decides whether your language is pleasant to use. Everything in it costs almost nothing to build now and is nearly impossible to retrofit — which is why it appears in Section 1, before there is anything to report an error about.

Three concepts: the span, the source map, and diagnostic rendering.

Concept 1: The Span

1. Concept

A span is a half-open byte range into a source file: [start, end). It is the answer to "where did this come from?" and it is attached to every token, every AST node, every constant, and every instruction.

2. Problem

Compare:

error: attempt to multiply a string by a number

with:

policy.ember:12:17: error: attempt to multiply a string by a number

  12 │     score = article.tag * 2
     │             ^^^^^^^^^^^ this is a string

The information required for the second is exactly: which file, which byte range, and what was there. All of that is a span plus the source text. Without spans, no amount of effort in the error module produces the second message.

3. Mental model

A span is a pointer into the source text that survives every transformation. Tokens carry it, AST nodes merge it, the compiler stores it per instruction, the VM reports it in a traceback. It is the thread that connects a runtime failure back to the character a human typed.

4. Implementation

#![allow(unused)]
fn main() {
// src/span.rs
#[derive(Copy, Clone, PartialEq, Eq, Debug, Default)]
pub struct Span { pub start: u32, pub end: u32 }

impl Span {
    pub const EMPTY: Span = Span { start: 0, end: 0 };
    pub fn new(start: u32, end: u32) -> Span { Span { start, end } }
    /// The smallest span covering both — how a parent node gets its extent.
    pub fn merge(self, other: Span) -> Span {
        Span { start: self.start.min(other.start), end: self.end.max(other.end) }
    }
    pub fn len(self) -> u32 { self.end - self.start }
}
}

Eight bytes, Copy, no lifetime. Those three properties are why it can be attached to everything without anyone thinking about it — and that is the design goal. A span that is expensive to carry will not get carried.

5. Alternatives

6. Decision

Option A, with the file identified separately by a SourceId carried on the Chunk and on the error, not on every span.

Byte offsets because they are cheap, mergeable, and unambiguous. A separate SourceId rather than rustc's global offset space (C) because Ember compiles one chunk at a time and a Chunk already knows which source it came from — so paying 4 bytes per chunk beats a lookup per diagnostic.

u32 rather than usize because it halves the size and caps source files at 4 GiB, which is a limit Section 5 enforces at the host boundary anyway. Note the interaction: a size limit you enforce elsewhere lets you choose a smaller integer here. That is a normal and underused kind of design coupling; write it in a comment so the next person does not "fix" it to usize.

7. Tradeoffs

8. Production concerns

• Span::EMPTY is a lie detector. Any node with an empty span is a node whose span someone forgot. Add a test that walks the AST and asserts no node has Span::EMPTY, and run it over the whole golden corpus. It catches every missed merge in one shot.
• Synthetic nodes need a source span anyway. When the parser desugars t.k into Index { key: Str("k") }, the synthetic Str node gets the span of the k token. Not empty, not the whole expression. The rule: a synthetic node points at the syntax that caused it.
• Spans must survive the compiler. Section 3's Chunk stores a span per instruction. If the compiler drops them, runtime errors lose their location and you are back to error: runtime error.

Concept 2: The Source Map

1–3. Concept, problem, mental model

The SourceMap owns the text of every source Ember has seen, and translates byte offsets into human coordinates.

The SourceMap is the only thing that knows what a line is. Nothing else counts newlines. Centralizing that turns "off-by-one line numbers on Windows" from a class of bug into one function with one test.

4. Implementation

#![allow(unused)]
fn main() {
// src/span.rs
#[derive(Copy, Clone, PartialEq, Eq, Debug)]
pub struct SourceId(pub u32);

pub struct SourceFile {
    pub name: String,        // "policy.ember", "<repl:3>", "<host>"
    pub text: String,
    line_starts: Vec<u32>,   // byte offset of the first character of each line
}

impl SourceFile {
    fn new(name: String, text: String) -> SourceFile {
        // ONE pass, at load time. Every later line lookup is a binary search.
        let mut line_starts = vec![0];
        for (i, b) in text.bytes().enumerate() {
            if b == b'\n' { line_starts.push(i as u32 + 1); }
        }
        SourceFile { name, text, line_starts }
    }

    /// 1-based line and column. Column counts CHARACTERS, not bytes — see below.
    pub fn location(&self, offset: u32) -> (u32, u32) {
        let line = self.line_starts.partition_point(|&s| s <= offset) - 1;
        let line_start = self.line_starts[line] as usize;
        let col = self.text[line_start..offset as usize].chars().count() + 1;
        (line as u32 + 1, col as u32)
    }

    pub fn line_text(&self, line: u32) -> &str {
        let i = (line - 1) as usize;
        let start = self.line_starts[i] as usize;
        let end = self.line_starts.get(i + 1)
                      .map(|&e| e as usize - 1)          // exclude the '\n'
                      .unwrap_or(self.text.len());
        self.text[start..end].trim_end_matches('\r')      // and the '\r' before it
    }
}

pub struct SourceMap { files: Vec<SourceFile> }
}

The parts that carry meaning:

• line_starts is built once and searched with partition_point — O(log n) per lookup, versus O(n) if you rescan the text. Errors are rare so O(n) would be acceptable, but the REPL and Section 6's tracebacks do many lookups and the table is 4 bytes per line.
• trim_end_matches('\r') is the CRLF fix, in the one place that can fix it. Test it with a file authored with \r\n; every language implementation gets this wrong at least once.
• location returns a character column, not a byte column. That is a decision, and it is the wrong one for some purposes — see below.

5–7. Alternatives, decision, tradeoffs — what is a "column"?

There are three defensible answers and they disagree on the same line of text:

    local emoji = "🔥"          -- the string literal starts at...
    ^byte 20?  ^char 20?  ^display column 20?

Decision: characters for the reported line:col, display width for caret alignment.

Those are two different jobs and using one number for both is why carets are misaligned in so many tools. The reported column goes in policy.ember:12:17 and is what a human counts to. The caret's indentation is computed by measuring the rendered width of the prefix, and Ember approximates it as "one column per character, except tabs echo verbatim" — documented in docs/limitations.md, with full unicode-width handling listed as a known gap rather than silently wrong.

Being explicit about that is the point. Nearly every tool has this bug; the difference is whether it is written down.

8. Production concerns

• REPL chunks are sources too. Each REPL line becomes a SourceFile named <repl:N>, so a traceback through three REPL definitions shows three distinct locations. If you skip this, every REPL error says line 1.
• The SourceMap grows forever. A long-lived Engine that compiles many scripts accumulates every source. Section 5 either bounds it or lets the host evict — and a source that is evicted while a Chunk still references it must degrade to "location unavailable", not panic. Decide which, and test it.
• Never put the file name in an error message string. The name comes from the SourceMap at render time. If a message embeds it, you cannot render the same error without a path, which matters when a host does not want to leak filesystem paths to a partially-trusted caller.

Concept 3: Rendering a Diagnostic

4. Implementation

#![allow(unused)]
fn main() {
// src/error.rs
pub fn render(err: &EmberError, map: &SourceMap, src: SourceId) -> String {
    let mut out = String::new();
    let file = map.file(src);

    match err.span {
        None => { out.push_str(&format!("error: {}\n", err.message)); }
        Some(sp) => {
            let (line, col) = file.location(sp.start);
            let text = file.line_text(line);
            let gutter = line.to_string().len().max(2);

            out.push_str(&format!("{}:{}:{}: error: {}\n\n",
                                  file.name, line, col, err.message));
            out.push_str(&format!("{:>w$} │ {}\n", line, text, w = gutter));

            // The caret row. Prefix width is measured in CHARACTERS of the
            // actual prefix text, so it lines up under proportionally-spaced
            // content in a monospaced terminal.
            let line_start = file.line_start(line);
            let prefix = &text[..(sp.start - line_start) as usize];
            let pad: String = prefix.chars()
                .map(|c| if c == '\t' { '\t' } else { ' ' }).collect();
            let width = file.text[sp.start as usize..sp.end.min(line_end) as usize]
                            .chars().count().max(1);
            out.push_str(&format!("{:>w$} │ {}{}\n", "", pad, "^".repeat(width),
                                  w = gutter));
        }
    }

    for frame in &err.traceback {                 // empty until §3
        out.push_str(&format!("  in {} {}:{}\n", frame.name, frame.file, frame.line));
    }
    out
}
}

Note the tab handling: the padding copies tabs through rather than converting them to spaces, so the caret aligns regardless of the reader's tab width. That trick costs one map and fixes the most common caret misalignment.

The Trace: three errors, three layers

$ ember run -e 'return 0x'
<argv>:1:8: error: malformed hexadecimal number

   1 │ return 0x
     │        ^^

$ ember run -e 'return 1 + * 2'
<argv>:1:12: error: expected an expression, found '*'

   1 │ return 1 + * 2
     │            ^

$ ember run -e 'return "x" * 2'
<argv>:1:8: error: attempt to multiply a string by a number

   1 │ return "x" * 2
     │        ^^^ this is a string

Three different subsystems produced those — the lexer, the parser, and the evaluator — and they share one error type, one span type, and one renderer. That uniformity is what makes it cheap to have good errors everywhere instead of good errors in one place.

Note the third one carefully: the caret is under "x", not under * and not under the whole expression. The runtime error knows which operand was wrong because the Binary node kept its children's spans. That is the AST chapter's design decision 4 paying off two labs later.

8. Production concerns

• Truncate long lines. A 10,000-character minified line renders as 10,000 characters of noise. Window it around the span and mark the elision.
• Color is optional, not assumed. --no-color, and honor NO_COLOR. Golden tests run with color off; a diagnostic containing ANSI codes in a .expected file is a maintenance trap.
• Multi-line spans. A span crossing lines cannot be underlined with one caret row. Ember renders the first line plus ... (continues to line N). Rendering a proper multi-line diagnostic is a challenge extension and is where ariadne earns its dependency.
• Diagnostics are an API. Once a host parses your error output, its format is a compatibility surface. Ember's EmberError exposes kind, message, and span as data; the rendered string is explicitly documented as unstable. Hosts should match on kind, never on text.

9. References

• rustc_span and rustc_errors — the industry reference. Read MultiSpan and the primary/secondary label distinction.
• ariadne and codespan-reporting crates — build yours first, then read theirs and write down what you would adopt.
• CPython PEP 626 (precise line numbers) and PEP 657 (fine-grained error locations, Python 3.11). PEP 657 is exactly this chapter's argument, made a decade late by a mature language, and the before/after examples in it are the best possible motivation.
• Lua's lineinfo/abslineinfo in lobject.h and ldebug.c: per-instruction line info, delta-encoded to one byte per instruction where possible. Section 3 copies the idea.

Things to Notice

• Spans are the cheapest high-leverage decision in the whole curriculum. Eight bytes, added in Lab 1, and they are the reason Section 6's diagnostics are a lab rather than a rewrite.
• One SourceMap means one place gets newlines wrong. Centralizing a rule is how you make a bug class into a bug.
• "Column" has four definitions and they disagree. Any tool that does not say which it means is wrong for someone. Say which.
• The error type is shared across the lexer, parser, compiler, VM, and host. That is unusual and deliberate: one EmberError, one renderer, one experience. The alternative — a per-layer error type, converted at each boundary — is more "correct" and produces five renderers that drift.

Validation / Self-check

1. Why are spans byte offsets rather than line and column?
2. Why is Span u32 rather than usize, and what elsewhere makes that safe?
3. What span does the synthetic Str("k") node get when t.k is desugared, and why not the whole expression?
4. Give the four definitions of "column" and say which Ember uses for the reported location and which for caret alignment. Why are they different?
5. How does SourceFile make line lookup O(log n), and where is the CRLF fix?
6. In return "x" * 2, why is the caret under "x" rather than under *? Which earlier design decision made that possible?
7. Name three things that must be true of a diagnostic renderer used in golden tests.
8. Why should a host match on EmberError::kind rather than on the rendered message?

Next: Lab 1 — The Lexer.