parsecheck

stdlib/extra/parsecheck.hk: check a parser's failure diagnostics by brute force.

A hand-written parser can report the wrong failure position, or an expected set that has drifted from the grammar, and no ordinary test notices: the parse still rejects the input, and the only thing wrong is the message. This module turns both into assertions.

It needs nothing but the parse function. Given a subject that answers, for any input, either "accepted" or "failed at offset N", two facts about a rejected input are computable by brute force:

the position is right the reported offset is the length of the longest viable prefix, the point past which no continuation could have saved the parse. That length is what Report.honest_at records

the expected set is a byte is a viable continuation when appending it complete leaves the prefix viable; probing all 256 gives the true set, against which the parser's own labels must be neither short nor invented

The whole thing rests on one observation: a prefix is viable when the subject either accepts it outright, or fails only for want of more input, at the prefix's own end. A parser that fails at offset 2 of a 2-byte input consumed everything and wanted more; one that fails at offset 2 of a 3-byte input choked on something it saw. No grammar and no parser internals, and this reads a hand-written, table-driven or generated parser the same way.

It is expensive, 256 probes per rejected input plus one per prefix, and that is what it is for. It is a test and no parse.

Two classes of would-be finding are no findings at all, a real parser's corpus having measured them as the entire noise floor: bytes the author declines to name (check's ignore, whitespace for a parser that skips it), and bytes that merely extend a parse at end of input, where the parser's own "expected )" completion message is the better one (recorded on Report.viable_only and never demanded). Both exist to let explain be empty on a parser whose diagnostics are right, which is the negative result this tool certifies.

Outcome

struct Outcome
  accepted: bool
  at: int
end

What the subject answers about one input. at is meaningful only when the input was rejected.

accepted

def accepted() -> Outcome

The subject accepted the whole input.

accepted().accepted => true

failed_at

def failed_at(at: int) -> Outcome

The subject rejected the input, having got as far as offset at.

failed_at(3).at => 3

alphabet

def alphabet() -> List<bytes>

Every single-byte value, in byte order, which puts the one-byte bytes for byte i at index i. Built from hex and not by arithmetic, which leaves byte 0 and byte 255 as reachable as the printable middle.

alphabet().length => 256

viable?

def viable?(probe: (bytes) -> Outcome, s: bytes) -> bool

Is s a prefix of something the subject would accept? True when the subject accepts it, and when it rejects it only at the very end, having consumed everything and stopped for want of more input.

>= and not ==: a parser that reports the position it wanted to read, and not the last one it read, lands one past the end.

viable?(|s| accepted(), "ab".to_bytes()) => true
viable?(|s| failed_at(0), "ab".to_bytes()) => false
viable?(|s| failed_at(2), "ab".to_bytes()) => true

frontier

def frontier(probe: (bytes) -> Outcome, input: bytes) -> int

The length of the longest viable prefix of input, which is where the failure belongs. Prefixes are probed shortest-first and the first non-viable one settles it: viability is monotone, since a prefix that cannot be extended into an accepting parse cannot regain the ability by growing.

frontier(|s| failed_at(1), "abc".to_bytes()) => 1

continuations

def continuations(probe: (bytes) -> Outcome, input: bytes, at: int) -> List<int>

The byte values that could have continued a parse at at: the true expected set, as bytes and not as labels.

continuations(|s| accepted(), "ab".to_bytes(), 1).length => 256
continuations(|s| failed_at(0), "ab".to_bytes(), 1).length => 0

completions

def completions(probe: (bytes) -> Outcome, input: bytes, at: int) -> List<int>

The byte values that complete a parse at at: appending one yields an input the subject accepts outright. Always a subset of continuations; the rest of that set merely leaves the parse alive, which is a different claim, and check treats the two differently at an end-of-input frontier.

completions(|s| accepted(), "ab".to_bytes(), 1).length => 256
completions(|s| failed_at(0), "ab".to_bytes(), 1).length => 0

Report

struct Report
  input: string
  reported_at: int
  honest_at: int
  missing: List<int>
  viable_only: List<int>
  phantom: List<string>
end

What a check found for one rejected input. viable_only is informational: at an end-of-input frontier it is the unnamed bytes that would have left the parse alive without completing it, the class explain omits by design, the parser's own "expected )" being the better message and the extensions per-report noise. At a mid-input frontier it is empty: there such bytes are genuine omissions and land in missing.

impl Report

clean?

prop clean?(self) -> bool

Nothing to complain about: the reported position was the right one, every byte that had to be named is covered by some label, and every label covers a byte that would have left the parse alive. viable_only does not count against cleanliness; it is the set this checker declines to demand a name for.

Report(input="x", reported_at=1, honest_at=1, missing=[], viable_only=[], phantom=[]).clean? => true
Report(input="x", reported_at=0, honest_at=1, missing=[], viable_only=[], phantom=[]).clean? => false

check

def check(probe: (bytes) -> Outcome, input: string, reported_at: int, expected: List<string>, covers: (string, int) -> bool, ignore: List<int>) -> Report

Measure one rejected input against what the subject said about it.

probe answers for any input; reported_at and expected are what the subject's own diagnostic claimed; covers says whether one of those labels would admit a given byte: the only thing the caller has to supply, the caller alone knowing that "a number" means the ASCII digits. ignore is the bytes the author declines to name at all; a parser that skips whitespace passes the whitespace bytes here, or every report would carry "never expects " forever.

What a byte must do to land in missing depends on where the frontier is, because the two positions make different claims:

Mid-input (the subject refused a byte it saw): every uncovered viable byte is a genuine omission. "A leading - would also have parsed" is the defect this tool exists to catch.

End of input (the subject consumed everything and wanted more): only the uncovered completing bytes count. For (1 + 2 the parser's "expected )" is the right message, and the digits that merely extend the expression are noise; they are recorded on viable_only and never demanded.

A subject that accepts everything reports the right stopping point and expects nothing, and every byte that would have parsed therefore counts as missing:

check(|s| accepted(), "ab", 2, [], |l: string, b: int| false, []).honest_at => 2
check(|s| accepted(), "ab", 2, [], |l: string, b: int| false, []).missing.length => 256

show_byte

def show_byte(b: int) -> string

A byte as it should read in a message: the character itself when printable, and a hex escape otherwise.

show_byte(0) => "0x00"
show_byte(255) => "0xff"

explain

def explain(r: Report) -> string

One line naming everything wrong with r, or the empty string when nothing is, which lets a caller collect the non-empty ones and fail with all of them.

explain(Report(input="x", reported_at=1, honest_at=1, missing=[], viable_only=[], phantom=[])) => ""

_byte

def _byte(s: bytes, i: int) -> int

_demo

def _demo(s: bytes) -> Outcome

_covers?

def _covers?(label: string, b: int) -> bool

_paren

def _paren(s: bytes) -> Outcome

parencovers?

def _paren_covers?(label: string, b: int) -> bool