diag

stdlib/extra/diag.hk: failure reporting for hand-written parsers.

A recursive-descent parser knows where it failed; saying so usefully is the part that costs. Threading a failure value back up through every return is invasive enough that most hand-written parsers skip it and report the position they gave up at, which is rarely the position that mattered.

The idiom production parsers use, rustc among them, is a farthest frontier: one accumulator, updated wherever a terminal test fails, recording only the furthest offset reached and the labels expected there. A branch that fails at offset 3 and a branch that fails at offset 11 need no reconciling by the caller; the frontier records 11.

The whole protocol is one rule: every terminal test's failing branch calls want once. Nothing on success paths, no merges in signatures. Records left by branches that later succeed are harmless: a further branch overwrites them, and they surface only if the whole parse fails anyway.

Carrying the accumulator is not free. A parse function that takes a Diag and hands one back costs the parameter on every call, success or failure, and on tools/bench's calculator that is roughly a quarter more than the same parser with no diagnostics at all (calcbase against calcdiag). Thread it only through a parser that reports. A hot parser is left with its plain signature and answers success or failure; when it fails, run a diagnosing twin, the same grammar with the accumulator threaded through, over the same input, and report what the twin says. Parsing twice leaves the success path paying nothing and the failure path, already the slow one, paying one more parse. The two parsers must agree on what they reject and where, and that is what parsecheck is for: it certifies a parser's failure offset and expected set by brute force from outside, checking each twin against the grammar independently and needing no differential harness between them.

Place

struct Place
  line: int
  column: int
end

Where an offset lands, 1-based and counted in scalars, on the convention hanki check prints.

Diag

struct Diag
  farthest: int
  expected: List<string>
  labelled: bool
end

The farthest-frontier accumulator: the greatest offset any terminal test reached, and the labels expected there. farthest is -1 for an untouched accumulator, which is what distinguishes "nothing was tried" from "something failed at offset 0".

nowhere

def nowhere() -> Diag

An untouched accumulator, to fold want into.

nowhere().farthest    => -1
nowhere().expected    => []

want

def want(d: Diag, at: int, label: string) -> Diag

Record that label was expected at offset at.

Farthest wins outright, an equal offset unions the labels (without duplicating one already recorded), and an earlier offset is a no-op. A parser may therefore call this from any failing branch in any order, and the accumulator still describes the furthest point reached.

want(nowhere(), 4, "a digit").farthest                  => 4
want(want(nowhere(), 4, "a digit"), 2, "'(' ").farthest  => 4
want(want(nowhere(), 4, "a digit"), 9, "an operator").expected => ["an operator"]
want(want(nowhere(), 4, "a digit"), 4, "a letter").expected    => ["a digit", "a letter"]
want(want(nowhere(), 4, "a digit"), 4, "a digit").expected     => ["a digit"]

expect

def expect(d: Diag, at: int, label: string) -> Diag

Record that label names what the parser was trying to read at at, in the phrase a reader wants: "a number" and never the raw [0-9] a terminal test would report.

A labelled record outranks raw ones at the same offset: it replaces whatever want accumulated there, and want calls that follow are ignored. The innermost label wins, which leaves a rule already labelled by an inner expect alone under an outer one, the same rule extra/peg applies to its own expect combinator, and for the same reason: the narrowest phrase is the informative one.

expect(want(nowhere(), 4, "[0-9]"), 4, "a number").expected  => ["a number"]
want(expect(nowhere(), 4, "a number"), 4, "[0-9]").expected  => ["a number"]
expect(expect(nowhere(), 4, "a number"), 4, "an operand").expected => ["a number"]
expect(nowhere(), 4, "a number").farthest                    => 4
expect(want(nowhere(), 9, "[0-9]"), 4, "a number").expected  => ["[0-9]"]

place_of

def place_of(input: bytes, at: int) -> Place

Where offset at lands in input, 1-based. One pass, once, at the end: the frontier is threaded as an offset to leave every parse step out of this cost.

place_of("ab\ncd".to_bytes(), 0).line   => 1
place_of("ab\ncd".to_bytes(), 0).column => 1
place_of("ab\ncd".to_bytes(), 4).line   => 2
place_of("ab\ncd".to_bytes(), 4).column => 2

render

def render(input: bytes, d: Diag) -> string

Render d against the input it was accumulated over: line:column followed by what was expected there. An untouched accumulator renders at the start of input, since there is no frontier to point at.

render("1+".to_bytes(), want(nowhere(), 2, "a digit")) => "1:3: expected a digit"
render("1+".to_bytes(), nowhere())                     => "1:1: no match"