Lesson 5.8 — Diagnostics: spans, notes and fix-its, error recovery and poisoning, typo correction¶

Techniques: diagnostics as data — severity, stable code, primary span, notes and machine-applicable fix-its (Clang's DiagnosticBuilder and FixItHint, rustc's Diag and suggestions, pebblec's DiagnosticEngine), error recovery by poisoning — error types and error symbols that suppress cascades (GCC's error_mark_node, Clang's RecoveryExpr and contains-errors, rustc's {type error}, Pebble's <error> type and error symbols), and "did you mean" typo correction by edit distance — Levenshtein (1966) with Wagner–Fischer (1974), Damerau (1964) and optimal string alignment, and Burkhard–Keller trees (1973) for searching a dictionary under a metric · Pebble implements: codes, spans and notes for every E03xx diagnostic, error symbols (one report per name, namespace and item), and Clang's typo-correction rule (exercise E4); drill edit-distance · Prerequisites: Lessons 5.1–5.3 · Time: 3 hours

A compiler's analyses are judged by their verdicts; a compiler is judged by its messages. After the parser (Ch 4) has recovered from syntax errors, semantic analysis produces most of the diagnostics a programmer sees: undeclared names, redefinitions, uninitialized variables. Three techniques decide their quality. Spans, notes and fix-its say exactly where the problem is, which other places are involved, and what edit would fix it — in a form an IDE can apply. Poisoning keeps one mistake from producing a page of consequences. Typo correction turns "use of undeclared identifier" into "did you mean count?". This lesson gives each its data model, algorithm and correctness argument, and ends with the distance functions and search trees behind the suggestions.

1. Problem and motivation¶

The problem. Given the errors an analysis finds, report each one (a) at a precise location with a stable code, (b) with the related locations that explain it, (c) with a suggested edit when one is likely, (d) exactly once — no diagnostics caused only by earlier ones — and (e) without slowing down error-free compilation.

Spans, notes and fix-its¶

Early compilers printed a line number and a message. Clang's diagnostics (2007 onward) made ranges, carets and fix-it hints standard: each diagnostic carries a primary source range, optional notes at other locations ("previous definition is here"), and fix-its — replacements, insertions, removals of source ranges — which IDEs and clang -fixit can apply mechanically [CLANG-Internals]. rustc followed with multi-span labels and machine-applicable suggestions, serialized as JSON for tools [RUSTC-DevDiag]. pebblec stores diagnostics as data (pebble/include/pebble/Support/Diagnostic.h: severity, code, message, range, notes) and renders them as text or JSON lines, so tests match codes and positions rather than wording (pebble-spec §13).

Error recovery and poisoning¶

A resolver that reports "undeclared name x" and then gives up leaves x's uses without a declaration, and every later phase that looks at them may complain again: x + 1 is ill-typed, f(x) has the wrong argument, x is uninitialized. These are cascading errors. The classic remedy [ALSU07, §4.1.4; EaC3, Ch. 3] is to poison: enter an error symbol for x so that its later uses resolve silently, and give ill-formed expressions an error type that every check accepts. GCC binds an undeclared identifier to error_mark_node in the function scope ("each undeclared identifier is reported only once for each function it appears in"); Clang wraps broken expressions in RecoveryExpr and propagates a contains-errors bit so that dependent checks stay silent; Pebble's resolver keeps error symbols per item and namespace, and the type checker (Ch 6) gives such expressions the <error> type, "compatible with everything" (pebble-spec §13).

Typo correction¶

When lookup fails, the most helpful message names what the programmer probably meant. That is a nearest-neighbor query: among the names visible at the use, find those at small edit distance from the typo. Levenshtein [Lev66] defined the distance with insertions, deletions and substitutions; Damerau [Dam64] observed that most spelling errors are a single insertion, deletion, substitution or transposition of adjacent letters; Wagner and Fischer [WF74] gave the dynamic program. Clang's Sema::CorrectTypo searches the visible names with LLVM's edit_distance and accepts a candidate only if its distance is at most a third of the typo's length [CLANG-SemaLookup]; GCC and rustc use the optimal string alignment (restricted Damerau–Levenshtein) variant [GCC-Spellcheck, RUSTC-EditDistance]. For very large dictionaries (spell checkers, fuzzy search), Burkhard–Keller trees [BK73] avoid comparing the typo with every word by using the triangle inequality of a metric.

2. Definitions and algorithms¶

Spans, notes and fix-its¶

Definition 5.8.1 (Diagnostic, span, note, fix-it)

A span is a half-open byte range \([b, e)\) in one file (for Pebble, in the SourceManager's global offset space). A diagnostic is a tuple (severity, code, message, primary span, notes, fix-its), where each note is (span, message) and each fix-it is an edit (span, replacement text): insertion (\(b = e\)), removal (empty text) or replacement. A set of fix-its is applicable if their spans are pairwise disjoint (touching insertions at the same point are ordered by their order in the diagnostic).

Algorithm 5.8.2 (Rendering a span as line:column with a caret line)

Input: a file's text, its line table (the sorted start offsets \(s_1 = 0 < s_2 < \dots < s_L\) of its lines), a span \([b, e)\).
Output: line:col of \(b\), the source line, and a caret line ^~~~ under \([b, e)\).
Precondition: \(0 \le b \le e \le\) file length; the line table was built once, in one scan of the file.
Postcondition: line \(\ell\) satisfies \(s_\ell \le b < s_{\ell+1}\) (with \(s_{L+1} = \infty\)), and col \(= b - s_\ell + 1\) (bytes, 1-based).
Invariant: the binary search keeps \(s_{\mathit{lo}} \le b < s_{\mathit{hi}}\).

function Render(text, starts, b, e):
    lo ← 1;  hi ← L + 1                     # starts[L + 1] = ∞
    while hi − lo > 1:
        mid ← ⌊(lo + hi) / 2⌋
        if starts[mid] ≤ b: lo ← mid else: hi ← mid
    line ← lo;  col ← b − starts[lo] + 1
    src ← text[starts[lo] .. starts[lo + 1] − 1]  (without the newline)
    width ← max(1, min(e, starts[lo + 1] − 1) − b)
    return "line:col", src, (col − 1 spaces) + "^" + (width − 1 times "~")

Error recovery and poisoning¶

Definition 5.8.3 (Cascade, error symbol, error type)

A diagnostic \(\Delta_2\) is a cascade of \(\Delta_1\) if it would not be reported in the program obtained by fixing \(\Delta_1\) in the way its message suggests (declaring the name, deleting the duplicate, …). An error symbol for name \(n\) in namespace \(\nu\) and item \(I\) is an entry in the symbol table that makes every later lookup of \(n\) in \(\nu\) within \(I\) succeed silently with "no declaration". The error type \(\mathsf{err}\) is a type such that every type check with \(\mathsf{err}\) as an operand succeeds and yields \(\mathsf{err}\) (or the expected type).

Algorithm 5.8.4 (Resolution with error symbols, as in the reference resolveNames)

Input: a use of name \(n\) in namespace \(\nu\) inside item \(I\).
Output: a declaration, or "no declaration" (the use stays unbound: <none> in the resolution dump).
Precondition: \(\mathrm{Poisoned}_\nu\) is cleared at the start of each item.
Postcondition: each distinct unresolved \((n, \nu)\) is reported once per item (Theorem 5.8.9).
Invariant: \(n \in \mathrm{Poisoned}_\nu\) iff an error for \(n\) in \(\nu\) was reported in the current item.

function ResolveUse(n, ν):
    d ← Lookup(n, ν)                      # Lessons 5.2–5.3
    if d exists: return d
    if n ∈ Poisoned[ν]: return none       # an error symbol: silent
    Poisoned[ν] ← Poisoned[ν] ∪ {n}
    if n is declared in another namespace: report "not a value/function" (E0309/E0308) + note
    else: report "undeclared" (E0301/E0303) + a note: "declared later" or "did you mean"
    return none

Typo correction¶

Definition 5.8.5 (Edit distances)

For strings \(a\) and \(b\), the Levenshtein distance \(\mathrm{lev}(a, b)\) is the least number of single-character insertions, deletions and substitutions that transform \(a\) into \(b\). The (unrestricted) Damerau–Levenshtein distance \(\mathrm{dam}(a, b)\) also allows the transposition of two adjacent characters at cost 1. The optimal string alignment distance \(\mathrm{osa}(a, b)\) allows the same four operations but edits no substring more than once — it is what the DP of Algorithm 5.8.6 with the transposition case computes. Always \(\mathrm{dam} \le \mathrm{osa} \le \mathrm{lev}\).

Algorithm 5.8.6 (Wagner–Fischer, with the OSA transposition case)

Input: strings \(a = a_1 \cdots a_n\) and \(b = b_1 \cdots b_m\); a flag for transpositions.
Output: \(\mathrm{lev}(a, b)\), or \(\mathrm{osa}(a, b)\) with the flag.
Precondition: none.
Postcondition: \(D[n][m]\) is the distance (Theorem 5.8.10).
Invariant: after row \(i\) is filled, \(D[i][j]\) is the distance between the prefixes \(a_1 \cdots a_i\) and \(b_1 \cdots b_j\) for every \(j\).

function Distance(a, b, transpositions):
    for i in 0..n: D[i][0] ← i                # delete all of a's prefix
    for j in 0..m: D[0][j] ← j                # insert all of b's prefix
    for i in 1..n:
        for j in 1..m:
            cost ← 0 if a_i = b_j else 1
            D[i][j] ← min(D[i−1][j] + 1,            # delete a_i
                          D[i][j−1] + 1,            # insert b_j
                          D[i−1][j−1] + cost)       # match or substitute
            if transpositions and i > 1 and j > 1 and a_i = b_(j−1) and a_(i−1) = b_j:
                D[i][j] ← min(D[i][j], D[i−2][j−2] + 1)   # swap a_(i−1) a_i
    return D[n][m]

Algorithm 5.8.7 (Burkhard–Keller tree insertion and range query)

Input: a metric \(\mathrm{dist}\) on words; a sequence of words to insert; a query word \(q\) and a tolerance \(t\).
Output: all inserted words \(w\) with \(\mathrm{dist}(q, w) \le t\).
Precondition: \(\mathrm{dist}\) is a metric (in particular it satisfies the triangle inequality), with integer values.
Postcondition: the output is exactly the words within distance \(t\) (Theorem 5.8.12).
Invariant: every word stored in the subtree reached from node \(u\) by the edge labeled \(k\) is at distance exactly \(k\) from \(u\)'s word.

function Insert(tree, w):
    if tree is empty: tree.root ← node(w);  return
    u ← tree.root
    loop:
        k ← dist(w, u.word)
        if k = 0: return                          # already present
        if u has no child labeled k: u.child[k] ← node(w);  return
        u ← u.child[k]

function Query(tree, q, t):
    result ← [];  stack ← [tree.root]
    while stack is not empty:
        u ← pop stack;  d ← dist(q, u.word)
        if d ≤ t: append u.word to result
        for each label k of u's children with d − t ≤ k ≤ d + t:  push u.child[k]
    return result

The acceptance rule of Clang's typo correction, which pebblec copies (pebble-spec §13.2): for a typo of length \(\ell \ge 3\), among the visible names of the right namespace, take those at the smallest distance \(d\); suggest the name if it is unique at that distance and \(3d \le \ell\) (Clang: TypoLen / ED < 3 rejects).

3. Worked example¶

Spans, notes and fix-its¶

tests/ch05/Inputs/err-undeclared.pbl, lines 1–3 and 6–7, and what ch05-resolve reports (primary span and note spans are byte ranges rendered by Algorithm 5.8.2):

fn helper(count: int) -> int {
    return cout + 1;          // E0301, did you mean 'count'?
}
    ...
    print(later);             // E0301, declared later
    let later = 1;

diagnostic	primary span → line:col	note	note span → line:col
E0301 `use of undeclared name 'cout'`	`cout` → 2:12	`did you mean 'count'?`	the same span (a candidate fix-it: replace 2:12–2:16 by `count`)
E0301 `use of undeclared name 'later'`	`later` → 6:11	`'later' is declared here, after its use; …`	`later` in `let later` → 7:9

Rendering 2:12: the line table of the file starts 0, 31, … (line 1 has 30 characters plus the newline, so line 2 starts at byte 31); cout begins at byte 42, so the binary search finds line 2 and column \(42 - 31 + 1 = 12\), and the caret line is 11 spaces, ^ and three ~.

Error recovery and poisoning¶

tests/ch05/Inputs/err-recovery.pbl with Algorithm 5.8.4 (item f, then item main):

step	use	lookup	Poisoned (values; calls)	reported?
1	`missing` in `let a = missing + 1`	fails	{missing}; {}	E0301 at 2:13
2	`missing` in `let b = a + missing`	fails	unchanged	no (error symbol)
3	`missing` in `c = missing * b`	fails	unchanged	no
4	call `unknownf(a)`	fails	{missing};	E0301 at 6:16
5	call `unknownf(b)`	fails	unchanged	no
6	new item `main`: clear both sets		{}; {}

Two diagnostics for five failed lookups; checkFlow does not even run (resolution failed), so c is not reported as uninitialized either. Without error symbols, a naive resolver would print five E0301s, all cascades of two mistakes.

Typo correction¶

The Wagner–Fischer tables for the typo cuont against count (rows: the typo, columns: the candidate):

Levenshtein	ε	c	o	u	n	t
ε	0	1	2	3	4	5
c	1	0	1	2	3	4
u	2	1	1	1	2	3
o	3	2	1	2	2	3
n	4	3	2	2	2	3
t	5	4	3	3	3	2

OSA	ε	c	o	u	n	t
ε	0	1	2	3	4	5
c	1	0	1	2	3	4
u	2	1	1	1	2	3
o	3	2	1	1	2	3
n	4	3	2	2	1	2
t	5	4	3	3	2	1

The OSA table differs from row o, column u on: \(a_2 a_3\) = uo is \(b_2 b_3\) = ou swapped (\(a_3 = b_2\) and \(a_2 = b_3\)), so \(D[3][3] = D[1][1] + 1 = 1\) (one transposition) instead of 2.
Clang's rule with Levenshtein: \(\ell = 5\), \(d = 2\), \(3 \cdot 2 = 6 > 5\): no suggestion. With OSA: \(d = 1\), \(3 \le 5\): suggest count. This is exactly the difference between Clang and GCC in the §7 box, and pebblec (OSA) suggests count.

BK-tree. Inserting count, counter, cursor, scope, score, store, total, index with the Levenshtein distance gives the edges count —2→ counter, count —4→ scope, count —5→ cursor, scope —1→ score, scope —5→ total, cursor —5→ store, cursor —6→ index. Query stor with tolerance 1:

step	node	\(d(\texttt{stor}, \text{node})\)	match?	labels followed (\([d-1, d+1]\))	labels skipped
1	count	5	no	4, 5	2
2	scope	3	no	—	1, 5
3	cursor	4	no	5	6
4	store	1	yes	—	—

Four distance computations instead of eight; the subtrees skipped (counter, score, total, index) provably contain no word within distance 1 (Theorem 5.8.12).

Try it

./course drill edit-distance --seed 2 --difficulty medium --solution prints both tables for a generated typo; --difficulty hard builds a BK-tree and traces a query.

4. Invariants and correctness¶

Spans, notes and fix-its¶

Proposition 5.8.8 (Line lookup is correct and logarithmic)

Algorithm 5.8.2 returns the unique line \(\ell\) with \(s_\ell \le b < s_{\ell+1}\) after \(\lceil \log_2 (L + 1) \rceil\) iterations, and the column \(b - s_\ell + 1\).

Proof

Invariant: initially \(s_1 = 0 \le b < s_{L+1} = \infty\). Each iteration picks \(\mathit{mid}\) strictly between \(\mathit{lo}\) and \(\mathit{hi}\) and keeps the half in which \(b\) lies (\(s_{\mathit{mid}} \le b\) moves \(\mathit{lo}\), otherwise \(\mathit{hi}\)), preserving \(s_{\mathit{lo}} \le b < s_{\mathit{hi}}\). Termination: \(\mathit{hi} - \mathit{lo}\) halves (rounded up) and the loop stops at 1, i.e. \(\mathit{hi} = \mathit{lo} + 1\), which with the invariant is the claimed line; the starts are strictly increasing, so the line is unique. The column follows from the definition of a 1-based byte column.

Error recovery and poisoning¶

Theorem 5.8.9 (Error symbols report each unresolved name once per item, and only cascades are suppressed)

With Algorithm 5.8.4: (a) for each item and namespace, each name that fails to resolve at one or more uses produces exactly one diagnostic, at its first use in resolution order; (b) every suppressed failure is a cascade of a reported one (Definition 5.8.3): declaring the reported name (in the way its message suggests) also resolves it.

Proof

(a) At the first failed lookup of \((n, \nu)\) in the item, \(n \notin \mathrm{Poisoned}_\nu\) by the invariant (nothing was reported yet), so the algorithm reports and inserts \(n\); at every later failed lookup of \((n, \nu)\) in the same item, \(n \in \mathrm{Poisoned}_\nu\) and nothing is reported. The set is cleared per item, so another item reports again. Uses that succeed are never reported. (b) A suppressed failure is a later failed lookup of the same \((n, \nu)\) in the same item as a reported one. Fixing the reported error by declaring \(n\) in \(\nu\) at the start of the item (for a function: at its body's start; for a missing item: at module level) makes that declaration a candidate at every use of \(n\) in the item — the region is the whole item — so the suppressed lookup succeeds as well: it was a cascade. (A diagnostic for a different name, or in another item, is never suppressed.)

Typo correction¶

Theorem 5.8.10 (Wagner–Fischer computes the edit distance)

Without transpositions, Algorithm 5.8.6 returns \(\mathrm{lev}(a, b)\). With them, it returns \(\mathrm{osa}(a, b)\).

Proof

By induction on \(i + j\), show \(D[i][j] = \mathrm{lev}(a_{1..i}, b_{1..j})\). Base: turning a prefix of length \(i\) into the empty string needs exactly \(i\) deletions (each deletion shortens by one, nothing else helps), and symmetrically for insertions. Step: consider an optimal edit sequence for \(a_{1..i}\) and \(b_{1..j}\), written as an alignment (each character of \(a\) deleted or aligned with one of \(b\), each character of \(b\) inserted or aligned, order preserved). Look at the last column of the alignment: either \(a_i\) is deleted (cost \(1 + \mathrm{lev}(a_{1..i-1}, b_{1..j})\)), or \(b_j\) is inserted (\(1 + \mathrm{lev}(a_{1..i}, b_{1..j-1})\)), or \(a_i\) is aligned with \(b_j\) (cost \([a_i \ne b_j] + \mathrm{lev}(a_{1..i-1}, b_{1..j-1})\)). The rest of an optimal alignment is optimal for the remaining prefixes (otherwise replace it by a cheaper one: exchange argument), so the distance is the minimum of the three, which the induction hypothesis says are the three cells the algorithm reads. Transpositions: OSA alignments may additionally end with a swapped pair \(a_{i-1} a_i = b_j b_{j-1}\) that is not edited further (no substring edited twice), adding the fourth case \(1 + D[i-2][j-2]\) under exactly the condition the algorithm tests.

Lemma 5.8.11 (OSA is not a metric)

\(\mathrm{osa}\) violates the triangle inequality: \(\mathrm{osa}(\texttt{ca}, \texttt{abc}) = 3 > \mathrm{osa}(\texttt{ca}, \texttt{ac}) + \mathrm{osa}(\texttt{ac}, \texttt{abc}) = 1 + 1\).

Proof

\(\texttt{ca} \to \texttt{ac}\) is one transposition, and \(\texttt{ac} \to \texttt{abc}\) one insertion. For \(\texttt{ca} \to \texttt{abc}\) the only two-edit route is "swap, then insert between the swapped characters", which edits the transposed substring again and is not an OSA alignment; running Algorithm 5.8.6 gives \(D[2][3] = 3\) (the course oracle course.lib.editdist.osa agrees, and the unrestricted \(\mathrm{dam}(\texttt{ca}, \texttt{abc}) = 2\)). GCC's spellcheck.cc states the same counterexample in its self-test.

Theorem 5.8.12 (BK-tree queries are exact for a metric)

If \(\mathrm{dist}\) is a metric, Query(tree, q, t) returns exactly the stored words \(w\) with \(\mathrm{dist}(q, w) \le t\).

Proof

Every visited node is tested directly, so everything returned is within \(t\) and every visited match is returned. It remains to show that a skipped subtree contains no match. Suppose the query is at node \(u\) with \(d = \mathrm{dist}(q, u)\) and skips the child subtree with label \(k\), so \(\lvert k - d \rvert > t\). By the invariant, every word \(w\) in that subtree has \(\mathrm{dist}(u, w) = k\). The triangle inequality gives \(\mathrm{dist}(q, w) \ge \lvert \mathrm{dist}(u, w) - \mathrm{dist}(u, q) \rvert = \lvert k - d \rvert > t\). So no word of the subtree matches. The invariant holds because Insert places \(w\) below \(u\) only along the edge labeled \(\mathrm{dist}(w, u)\). With OSA (Lemma 5.8.11), the inequality can fail and a query can miss a match — so BK-trees must use Levenshtein or the true Damerau–Levenshtein distance.

5. Complexity¶

Variables: \(L\) lines of a file; \(N\) names in scope (the dictionary); \(\ell\) the typo length and \(\bar{\ell}\) the average name length; \(t\) the tolerance; \(u\) the number of failed lookups.

Technique	Time	Space	Pathological input
Spans and rendering (Alg. 5.8.2)	\(O(\log L)\) per location after an \(O(\text{file})\) line-table scan	\(O(L)\) per file	none; the line table is built lazily, only when a diagnostic is rendered
Notes, fix-its	\(O(1)\) per note; applying \(k\) fix-its \(O(k \log k + \text{file})\) (sort by span)	\(O(k)\)	overlapping fix-its must be rejected
Error symbols (Alg. 5.8.4)	\(O(1)\) expected per failed lookup	\(O(\text{distinct unresolved names per item})\)	none
Typo correction by scan	\(O(N \cdot \ell \bar{\ell})\) per failed lookup, pruned by \(\lvert \ell - \lvert w \rvert \rvert > \ell/3\)	\(O(\bar{\ell})\) (two DP rows)	a file with thousands of undeclared names in a namespace with thousands of names: Clang caps the number of corrections it attempts
BK-tree query	\(O(N)\) worst case, sublinear for small \(t\) in practice	\(O(N)\) nodes	\(t \ge\) typical distances: every subtree is searched

Justification. The DP fills \((\ell + 1)(\lvert w \rvert + 1)\) cells per candidate, and the length filter discards a candidate in \(O(1)\) when the lengths alone exceed the threshold (a distance is at least the length difference). For BK-trees, Burkhard and Keller [BK73] analyze the expected number of distance computations for random dictionaries; in the §3 example the query computed 4 of 8 distances. Clang's typo correction is expensive enough that it limits how many typos per translation unit it corrects (-ftypo-correction can be disabled), because it can look through every visible declaration and every namespace [CLANG-SemaLookup].

Spans, notes and fix-its¶

Structured output: clang -fdiagnostics-parseable-fixits, -fdiagnostics-format=sarif, rustc's --error-format=json, pebblec --diagnostics=json: diagnostics as data for IDEs and CI.
Applicability levels (rustc: machine-applicable, maybe-incorrect, has-placeholders): only machine-applicable suggestions are applied by cargo fix.
Macro and desugaring backtraces: a span inside an expansion carries the chain of expansion sites (Clang's "expanded from macro", rustc's DesugaringKind, Lesson 5.6).

Error recovery and poisoning¶

Error types in type checkers (Ch 6): <error> unifies with everything; rustc's {type error} (ty::Error carrying an ErrorGuaranteed token proving an error was emitted, so no "success" can be claimed by accident).
Recovery expressions (Clang's RecoveryExpr with a best-guess type) keep enough structure that later phases can still type-check around the error and IDEs can still offer completion.
Error caps and stops: -ferror-limit, Pebble's E0211 (Ch 4); some compilers stop after the first phase with errors — pebblec's analyze does not run the type checker after resolution errors.

Typo correction¶

Distances: Levenshtein (Clang, via llvm::StringRef::edit_distance), OSA (GCC, rustc, pebblec), true Damerau (a metric, usable with BK-trees), keyboard- or case-aware weights (GCC counts a case change as cheaper than another substitution).
Candidate sets: visible names only (Pebble), plus names in other namespaces with a qualifier (Clang suggested geo::norm1 in Lesson 5.4), plus keywords; ranking by distance, then by scope proximity or usage frequency.
Indexes: BK-trees [BK73], VP-trees, n-gram indexes (rust-analyzer uses fuzzy matching over a symbol index), or plain length-bucketed scans — a compiler's scopes are small enough that scanning is usually fine.

7. In real compilers¶

Spans, notes and fix-its¶

Clang: DiagnosticBuilder collects arguments, ranges and FixItHints; TextDiagnostic::emitParseableFixits prints them in machine form (clang/lib/Frontend/TextDiagnostic.cpp, LLVM 23.1.2 [CLANG-TextDiag]); the diagnostics themselves are declared in TableGen files such as clang/include/clang/Basic/DiagnosticSemaKinds.td (err_undeclared_var_use_suggest, warn_decl_shadow [CLANG-DiagSema]). pebblec: pebble/include/pebble/Support/DiagnosticKinds.def is the same idea as an X-macro list.

Spans, notes and a machine-applicable fix-it from Clang 23

Reproduce (clang 23.1.2):

cat > typo.c <<'EOF'
int total(int count) {
  int result = 0;
  for (int i = 0; i < cuont; i++)
    reslt += i;
  return result;
}
EOF
clang-23 -fsyntax-only typo.c
clang-23 -fsyntax-only -fdiagnostics-parseable-fixits typo.c 2>&1 | grep '^fix-it'

Output (complete; the diagnostics, then the fix-it line):

typo.c:3:23: error: use of undeclared identifier 'cuont'
    3 |   for (int i = 0; i < cuont; i++)
      |                       ^~~~~
typo.c:4:5: error: use of undeclared identifier 'reslt'; did you mean 'result'?
    4 |     reslt += i;
      |     ^~~~~
      |     result
typo.c:2:7: note: 'result' declared here
    2 |   int result = 0;
      |       ^
2 errors generated.
fix-it:"typo.c":{4:5-4:10}:"result"

What to notice: each diagnostic has a primary span rendered with ^~~~~ (Algorithm 5.8.2), the second has a note at another location and a fix-it — the replacement text shown under the caret and, in parseable form, as the edit {4:5-4:10} → "result" (Definition 5.8.1). cuont gets no suggestion: see "Typo correction" below.

Error recovery and poisoning¶

GCC: undeclared_variable in gcc/c/c-decl.cc (gcc-15 [GCC-CDecl]) reports the error, prints the "reported only once" note the first time, and calls bind (id, error_mark_node, scope, …) in the function scope — an error symbol exactly as in Algorithm 5.8.4. Clang: RecoveryExpr (clang/include/clang/AST/Expr.h [CLANG-Expr]) and the ExprDependence::Error bit printed as contains-errors. pebblec: the PoisonedValues/PoisonedCalls/PoisonedTypes sets of the reference solution.

GCC 14's error symbol and Clang 23's contains-errors poisoning

Reproduce (gcc 14.2.0, clang 23.1.2; typo.c is the file of the previous box):

gcc-14 -fsyntax-only typo.c
cat > recover.cpp <<'EOF'
int f(int x) {
  int y = undeclared(x) + 1;   // one error; no follow-on errors for y
  return y * 2;
}
EOF
clang++-23 -fsyntax-only recover.cpp
clang++-23 -fsyntax-only -Xclang -ast-dump -fno-color-diagnostics recover.cpp 2>/dev/null \
  | sed -n '/FunctionDecl.*f /,$p' | sed -E 's/0x[0-9a-f]+ //g; s/ <[^>]*>//'

Output (complete; GCC on typo.c from the box above, then Clang's diagnostic and AST):

typo.c: In function 'total':
typo.c:3:23: error: 'cuont' undeclared (first use in this function); did you mean 'count'?
    3 |   for (int i = 0; i < cuont; i++)
      |                       ^~~~~
      |                       count
typo.c:3:23: note: each undeclared identifier is reported only once for each function it appears in
typo.c:4:5: error: 'reslt' undeclared (first use in this function); did you mean 'result'?
    4 |     reslt += i;
      |     ^~~~~
      |     result
recover.cpp:2:11: error: use of undeclared identifier 'undeclared'
    2 |   int y = undeclared(x) + 1;   // one error; no follow-on errors for y
      |           ^~~~~~~~~~
1 error generated.
`-FunctionDecl line:1:5 f 'int (int)' external-linkage
  |-ParmVarDecl col:11 used x 'int'
  `-CompoundStmt
    |-DeclStmt
    | `-VarDecl col:7 used y 'int' cinit
    |   `-BinaryOperator '<dependent type>' contains-errors '+'
    |     |-RecoveryExpr '<dependent type>' contains-errors lvalue
    |     | |-UnresolvedLookupExpr '<overloaded function type>' lvalue (ADL) = 'undeclared' empty
    |     | `-DeclRefExpr 'int' lvalue ParmVar 'x' 'int'
    |     `-IntegerLiteral 'int' 1
    `-ReturnStmt
      `-BinaryOperator 'int' contains-errors '*'
        |-ImplicitCastExpr 'int' contains-errors <LValueToRValue>
        | `-DeclRefExpr 'int' contains-errors lvalue Var 'y' 'int'
        `-IntegerLiteral 'int' 2

What to notice: GCC's note states Theorem 5.8.9's policy in words: after the first report, the identifier is bound to an error node in the function scope. Clang keeps the broken call as a RecoveryExpr, and the contains-errors bit spreads to every expression built from it (y's initializer, then y * 2), so no check complains about y: poisoning by propagation instead of by symbol.

Typo correction¶

Clang: Sema::CorrectTypo and TypoCorrectionConsumer::addName (clang/lib/Sema/SemaLookup.cpp, LLVM 23.1.2 [CLANG-SemaLookup]) compute edit_distance (Levenshtein, llvm/include/llvm/ADT/edit_distance.h [LLVM-EditDistance]) with the upper bound (TypoStr.size() + 2) / 3 and reject a best candidate when TypoLen / ED < 3 or when it is not unique. GCC: get_edit_distance (OSA, with case changes cheaper) and get_edit_distance_cutoff in gcc/spellcheck.cc (gcc-15 [GCC-Spellcheck]). rustc: edit_distance (OSA) and find_best_match_for_name in compiler/rustc_span/src/edit_distance.rs (rustc 1.94.1 [RUSTC-EditDistance]).

rustc 1.94 suggests both corrections; Clang's Levenshtein misses the transposition

Reproduce (rustc 1.94.1):

cat > typo.rs <<'EOF'
fn total(count: u32) -> u32 {
    let mut result = 0;
    for i in 0..cuont {
        reslt += i;
    }
    result
}
fn main() { println!("{}", total(3)); }
EOF
rustc --edition 2021 typo.rs -o typo

Output (complete):

error[E0425]: cannot find value `cuont` in this scope
 --> typo.rs:3:17
  |
3 |     for i in 0..cuont {
  |                 ^^^^^
  |
help: a local variable with a similar name exists
  |
3 -     for i in 0..cuont {
3 +     for i in 0..count {
  |

error[E0425]: cannot find value `reslt` in this scope
 --> typo.rs:4:9
  |
4 |         reslt += i;
  |         ^^^^^
  |
help: a local variable with a similar name exists
  |
4 |         result += i;
  |            +

error: aborting due to 2 previous errors

For more information about this error, try `rustc --explain E0425`.

What to notice: the same two typos as the Clang box. rustc and GCC suggest count for cuont because OSA counts the swap uo → ou as one edit (\(d = 1\), §3's second table); Clang's Levenshtein distance is 2, and with \(\ell = 5\) its rule \(3d \le \ell\) fails, so Clang offers nothing. reslt → result is one insertion under every distance. rustc renders the suggestion as a diff (-/+ lines) — a fix-it with an applicability level.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Spans, notes and fix-its	Exact byte ranges, related locations, machine-applicable edits	\(O(\log L)\) per rendered location; zero cost when there are no errors	Best-in-class when every diagnostic carries a span and a code; fix-its let tools repair code	Medium: every diagnostic site must supply spans and notes	Clang, rustc, Swift, `pebblec`
Error recovery and poisoning	One report per mistake (Theorem 5.8.9); later phases keep working around errors	\(O(1)\) per failed lookup	Removes cascades; a missed poisoning shows up as a wall of errors	Low for error symbols; pervasive for error types (every check must accept them)	GCC `error_mark_node`, Clang `RecoveryExpr`, rustc `{type error}`, `pebblec`
Typo correction	Suggestions within \(\lfloor \ell / 3 \rfloor\) edits; OSA catches transpositions, Levenshtein does not; BK-trees exact only for metrics (Theorem 5.8.12)	\(O(N \ell \bar{\ell})\) per failed lookup by scan; BK-tree sublinear in practice	"Did you mean" with a fix-it; a wrong suggestion is worse than none (hence the thresholds and the uniqueness rule)	Low (a DP and a threshold); higher with ranking and indexes	Clang, GCC, rustc, Swift, `pebblec`

Choose spans, notes and codes from the first version of a compiler: retrofitting ranges into diagnostics is expensive, and tests should match codes and positions, not wording. Choose error symbols and error types together: symbols stop repeated name errors, types stop the type errors built on them. Choose OSA with a length-relative threshold for identifier suggestions (transpositions are the commonest typo), a uniqueness rule to avoid coin-flip suggestions, and a metric distance if you index the dictionary with a BK-tree.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Spans, notes and fix-its	`span-line-col`, `find-clang-fixits`	— (E4's tests check every note's position)	`spans-fixits`	E4
Error recovery and poisoning	`poison-count`, `gcc-error-mark`	—	`recovery-poisoning`	E4
Typo correction	`lev-osa-count`, `clang-threshold`, `bk-visited`	`edit-distance` (all levels)	`typo-correction`	E4

References¶

See the chapter references.

Lesson 5.8 — Diagnostics: spans, notes and fix-its, error recovery and poisoning, typo correction¶

1. Problem and motivation¶

Spans, notes and fix-its¶

Error recovery and poisoning¶

Typo correction¶

2. Definitions and algorithms¶

Spans, notes and fix-its¶

Error recovery and poisoning¶

Typo correction¶

3. Worked example¶

Spans, notes and fix-its¶

Error recovery and poisoning¶

Typo correction¶

4. Invariants and correctness¶

Spans, notes and fix-its¶

Error recovery and poisoning¶

Typo correction¶

5. Complexity¶

6. Variants and refinements¶

Spans, notes and fix-its¶

Error recovery and poisoning¶

Typo correction¶

7. In real compilers¶

Spans, notes and fix-its¶

Error recovery and poisoning¶

Typo correction¶

8. Comparison¶

9. Assessment¶

References¶