toolchain/docs/lex/mismatched_brackets.md
Everything downstream of lexing assumes the token stream is well bracketed: each
(, [, and { has a matching closer, and the two cross-reference each other.
When the source doesn't satisfy that, the lexer repairs the stream before
handing it on, inserting recovery tokens and turning brackets it can't place
into error tokens.
The interesting question is not whether a bracket is unmatched — a stack
matcher answers that — but where the missing one belongs. Recovery has to pick
an insertion point, and that choice matters twice over: it is what the
diagnostic tells the developer, and it decides how much of the rest of the file
is misinterpreted. A } missing from the middle of a class definition, closed
at end of file instead of where it belongs, turns every following declaration
into a member of that class.
So we treat recovery as a search: enumerate ways to make a damaged part of the file well bracketed, price each by how plausible the mistake it implies is, and take the cheapest. The prices form a cost model calibrated by measurement against real Carbon code, and the evidence it reasons from is indentation, structural facts about the language, and formatting conventions.
FixMismatchedBrackets is the whole of that: it takes the token sequence and
returns a list of BracketCorrections, each pairing a diagnostic to report with
a fix to apply to the token stream. Nothing else in the lexer knows how the
decision was made.
A repair is built from four moves:
Giving up is what lets the rest of the model be assertive. It is always available at a fixed price, so it acts as a ceiling: a repair less plausible than admitting defeat is not chosen.
Recovery does not see tokens. It sees a MismatchedBracketToken per token: a
projection onto the properties bracket structure could depend on. That is a
coarse BracketTokenKind (the six brackets, ;, ,, ., statement
introducers, leaf tokens that form a complete primary expression on their own,
three flavors of operator, end of file, and everything else), the line and
indentation, and a few flags — whether a { looks like a struct literal,
whether a keyword demands a bracket after it, whether whitespace precedes the
token. Nothing else about the source is available, which keeps the search cheap
and the rules easy to reason about.
An ordinary stack match runs first. Most of the pairs it finds are genuine, and
reconsidering them would be both slow and risky, so every pair that passes a
cleanliness test collapses into a single Item that the search steps over as a
unit. Item is the search's unit of input from here on: one per token, except
where a trusted pair spans several.
Cleanliness is deliberately conservative. A brace pair is trusted when its }
lines up with the indentation of the statement that owns the { — not with the
column of the {, which for a header wrapped across lines is somewhere else
entirely — and when the separators directly inside it suit the brace's flavor: a
; directly inside a struct literal, or a , directly inside a block, means
the pairing has captured too much. A paren or square pair is suspect when an
unmatched opener of the same kind appears earlier in the same statement, or an
unmatched closer of the same kind later, because either could be the real
partner. Finally, the interior must be clean itself, with nothing inside it
pairing to something outside.
The resulting item sequence is cut at top-level declaration boundaries: a statement introducer at column 1 whose predecessor ended a statement. Each region is solved independently. That bounds how far one mistake can smear, and it gives unclosed brackets a natural place to be closed — before the next declaration, rather than at end of file.
Regions whose remaining loose brackets already balance are skipped without searching at all. That is the large majority of them, since a region typically holds pairs that merely failed the cleanliness test, and skipping them is worth an order of magnitude in running time.
RegionSearch solves one region. A search state — a BeamNode — is a position
in the item sequence plus the stack of brackets open at that point, together
with which closer, if any, was inserted at this position already.
The search runs in layers, one per item. Within a layer, insertion moves are applied: these don't consume the item, so they stay in the layer and can chain, which is how several groups get closed at one point. Then every surviving state advances over the item into the next layer. Both phases prune to a fixed beam width, keeping the cheapest states.
Two states in a layer whose stacks agree are interchangeable, so they merge. A merged state retains every cheapest way it was reached rather than one, which is what makes ambiguity visible at the end.
The search is bounded in each direction: beam width, stack depth, items per region, and paths enumerated. Exceeding a bound costs quality, never correctness — the fallback for an oversized region is a naive greedy matcher, and the output is well bracketed either way. Beam search offers no guarantee of finding the cheapest repair, but an intended repair is a cheap one by construction, so it survives pruning.
Costs are ordinal; only their ordering carries meaning. They live in three
tables of BracketRules:
CloserRules prices inserting a closing bracket before the current token.OpenerRules prices inserting an opening bracket before it.AdvanceRules prices stepping over the token with the current group still
open.The first two are first-match tables, ordered from the most specific cue to the least, and a row may decline outright, meaning the move is not worth considering there. The third is additive: every matching row contributes and the penalties sum. That table is the other half of the same judgment as the first: a penalty for swallowing a token that has no business inside the current group is what makes "close the group before it" win.
A lookup buckets on two categorical facts — the context category (which bracket
is innermost, or which one would be inserted, with block and struct braces
distinguished) and the token's kind — and a compile-time index maps each bucket
to the rows that could apply in it, so only a handful are ever tested. Rows
condition further on Cues, as sets of properties that must all hold, must not
hold, must not all hold, or must hold in part.
The model is calibrated on a single principle: the intended repair must be strictly cheapest. A tie is not resolved but reported, as described below, so a rule that gets the right answer only about half the time is worse than no rule at all.
{: a } lines up with its if even when
the { sits at the end of a wrapped header. A first-on-line else is
treated the same way, by walking back over complete blocks to the branch it
continues.; cannot appear inside ( or [ at all.
A block { cannot be the content of a keyword's parentheses or of a struct
literal. A binary operator cannot start a group. A leaf cannot directly
follow a value-ending token, so finding that pair is evidence a bracket is
missing between them. if, while, for, and match require a following
(, and forall a following [.,,
), or ., and none before a call's (. A space in one of those positions
means the code is unformatted or something was deleted from the gap, and
either way is weak evidence that a bracket belongs there. Such cues can only
fire on input that isn't formatted, which is what makes them safe to state
liberally.Once the cheapest cost is known, every repair achieving it is enumerated, up to a cap. A suggestion present in one cheapest repair but absent from another is ambiguous: the model has no basis for preferring either placement. Rather than guess, we discard the suggestion and replace the bracket with an error token. The developer is told the bracket is unmatched and is not pointed anywhere misleading, and the parser receives a stream with no invented structure.
This is the reason the tables are ordered and priced as deliberately as they are. Two competing repairs at distinguishable prices produce one answer; the same two at equal prices produce none.
Each correction produces an error at the bracket that has no partner, plus a
note at the position the missing bracket would occupy. That position lies
between two tokens rather than at one, so the note is emitted against a source
pointer: immediately past the end of the token the bracket would follow, then
adjusted for how the bracket is conventionally written. A } at end of line
moves past the newline and in to its opener's indentation, since it belongs on a
line of its own, and an opening bracket moves past any spaces, since it binds to
what follows.
Insertions are buffered in an ErrorRecoveryBuffer and applied in one pass that
renumbers the token stream, after which bracket cross-references are recomputed.
Insertions requested at the same anchor are ordered closers before openers, so
that the result is well nested.
mismatched_brackets_eval measures recovery by corrupting known-good code and
asking whether recovery reconstructs it. It deletes brackets from the Carbon
files in this repository, re-lexes, and compares the suggestions against what it
deleted:
bazel run -c opt //toolchain/lex:mismatched_brackets_eval -- \
--trials=4587 --d-values=1 --mode=gapless
There are four corruption modes, because how a bracket goes missing changes what evidence survives:
Scoring is by structure, not position. A suggestion is matched to the deletion it restores through the first surviving token it precedes, so closing anywhere in trailing whitespace, or anywhere within a run of identical brackets, counts as the same repair, while closing somewhere that changes the structure — re-pairing a surviving bracket, swallowing the next declaration — does not. Each trial is then Correct, Partial, None, or Incorrect.
Those outcomes are not weighted equally. An Incorrect suggestion misparses the file and points the developer at the wrong place, whereas a trial with no suggestion falls back to an error token and costs only the missing note. The model is therefore tuned to minimize Incorrect first and maximize Correct second.
Every rule carries a name, which the eval aggregates into per-rule firing counts and precision. That is how an over-firing rule is found, and it is also what makes the cost column tunable mechanically, by coordinate descent against the eval rather than by hand.
--d-values sets how many brackets a trial deletes, which is worth raising to
see how gracefully recovery degrades when mistakes overlap. With one deletion
per trial, as of this writing:
| Mode | Correct | Incorrect |
|---|---|---|
| blank | 95.6% | 0.0% |
| gapless | 82.3% | 4.3% |
| truncate | 98.9% | 0.9% |
| truncate-region | 82.6% | 16.5% |
The fail_mismatched_brackets tests in testdata are
a showcase rather than a corpus: each case is a shape recovery handles, with a
comment naming the cue that decides it.
( or [ has nothing local to work from
and over-extends.