peg

stdlib/extra/peg.hk: parsing expression grammars, as plain data.

The structured complement to regex, and the split between them is a threat model and no taste. regex covers flat lexical scanning where the pattern itself may be hostile, and it therefore takes linear time from a Pike VM at the cost of backreferences and lookaround. peg covers recursive, structured matching, grammars, nesting and captures, where the grammar is author code and only the input is untrusted. Reach for regex when a stranger writes the pattern; reach for peg when you write it and a stranger writes the text.

A pattern here is a value and no closure. sequence([literal("("), …]) builds an inspectable tree, which is what lets a later task validate a grammar statically, and what lets a top-level binding fold at compile time (see below). Combinator libraries that store closures cannot do either, and Hanki values are acyclic, and a closure-shaped recursive grammar could not even exist as a value.

Semantics, all locked by tests below

anchored matching starts at offset 0 and never searches forward ordered choice takes the first option that matches, and never the longest - choice([literal("a"), literal("ab")]) never matches ab whole possessive a completed repetition is never re-entered, and a zero_or_more that ate too much does not give any back committed a sequence whose later part fails fails whole; the enclosing choice is what retries zero-width ahead / not_ahead / end_of_input consume nothing scalar-safe any and the sets consume whole UTF-8 scalars, and a matched length is always a valid slice boundary. A literal matches its bytes, whatever they encode unicode a class bound, a literal and a capture may all be arbitrary scalars and not ASCII alone: scalar_range("α", "ω") matches γ, and a capture over multi-byte text comes back whole. The matcher compares raw bytes when every bound in a class happens to be one byte, and that is an optimisation and never the contract: a class mixing widths falls back to comparing scalars as text, for all of it

Possessive repetition is not an implementation shortcut. It is what a PEG trades away regular-expression semantics for, and it is why the bound below can be depth alone.

Bounds: the depth cap, and no other

Repetition being possessive means unbounded work needs recursion, and the depth cap bounds recursion, at 128, json.hk's tradition, reported as an ordinary typed failure, TooDeep, and no fault. The cap also bounds host stack on the AOT tier, where deep native recursion is a SIGSEGV and no other bound would catch it.

The two bounds that are not the same one

The cap counts effective nesting: what the matcher descends through, and never what the author typed (docs/design/peg-rationale.md says why). The two checks need telling apart: they bound different things, and a grammar can pass one and trip the other:

RuleTooDeep raised while a grammar is built, by the same walk that resolves rule references. It counts structural nesting inside one rule body and does not follow a reference; it cannot, rules being mutually recursive. So it catches a single body written past the cap TooDeep raised while matching. It counts every descent, including each rule reference, and accumulates across the whole parse. So ten rules of twenty levels each pass the build check and can still exhaust the cap at run time

The second is the real bound on recursion; the first is an early refusal for the case that could never match anything at all.

There is no step budget: the grammar is trusted author code, unlike regex's patterns. And no packrat memo table, whose input times rules of storage is against this runtime's memory posture - the linear-time guarantee it gains is not one this module claims.

Grammars: recursion, and what is checked before it runs

rule(name) refers to a rule; define(name, pattern) names one; and grammar(start, definitions) turns a list of definitions into a Grammar, or says why it will not build. That compile is where a PEG earns its keep: every way a grammar could misbehave at run time is a static error with the rule named:

UnknownRule a rule(name) with nothing defining it DuplicateRule two definitions of one name, leaving a reference ambiguous LeftRecursion a rule reachable from itself with nothing consumed on the way, reported as the cycle in reference order NullableLoop an unbounded repetition over a body that matches nothing RuleTooDeep a body nesting past the depth cap, which no input could ever get through

Left recursion is the one worth dwelling on. sum <- sum "+" term is how arithmetic is written in most grammar formalisms and is what a PEG cannot run: it would call sum at the same offset for ever. Detecting it needs to know which rules can match nothing, and nullability is therefore computed first, by fixpoint: a rule's nullability depends on the rules it calls, so one pass would under-report a mutual pair. The same nullability feeds the NullableLoop check, and the same leftmost-reference graph is what a later step's expected sets will be built from.

A validated Grammar has every rule reference already resolved to an index, and matching therefore looks a rule up with List.get and never touches a Map.

Compile-time folding

A top-level NUMBER: Result<peg.Grammar, peg.GrammarError> = peg.grammar(…) folds at compile time, validation and all, as does a top-level compile(source). What folds is the validation and never the value: the binding interns as one constant, materialised once per actor on the bytecode tier and once per thread on the AOT tier (HANKI.md §16). Naming such a binding inside a function that runs per input costs nothing per call.

Anything added to this module must stay foldable, which means what the pattern tree already is: lists and small structs, no Map, no Set, no closures. The top-level binding at the foot of this file is the probe that catches a regression. docs/design/peg-rationale.md records how the rule was arrived at and what the fold is worth.

Captures: what a parse produces

Nothing is captured unless asked for, the LPeg stance: a grammar that only recognises builds no tree and allocates nothing per scalar. Three constructors opt in. capture(p) retains the text p matched, tag(name, p) folds whatever p captured into one Node under that name, the tree builder, and it nests, and position() records an offset without consuming anything. Grammar.parse hands back the List<Capture>, and Capture is a public sum, and a caller reads the result by matching it, the same way json is read.

Two capture rules are stated here in place of discovered:

rollback a branch that failed contributes nothing, including a repetition's last, failed iteration. That falls out of the accumulator being an ordinary immutable value: a losing branch's caller retains the one it already had, and there is no length to record and slice back to predicates ahead / not_ahead discard whatever was captured inside them even where they succeed, which is standard PEG semantics and the thing people are surprised by

A Text payload is always a valid slice, every primitive consuming whole scalars and so no capture offset can land mid-scalar. The hazard that guards against: str.slice rounds a mid-scalar offset down, and a byte-level capture would therefore lose a character without saying so.

Failures: where, and what would have helped

A ParseFailure reports the farthest offset any branch reached, its 1-based line and column, what could have advanced there, and why it stopped. The farthest part is what matters: an ordered choice whose first option dies at offset 0 must not report offset 0 when a later option got to 20, and the classic "no match at 0" is asserted away by a test and never hoped for.

The merge rule is megaparsec's. The greater offset wins outright, equal offsets union their expected sets, and that is enough: the grammar's first sets are never precomputed, a terminal that failed already knows what it wanted and says so on the way out.

expect(p, label) names what p is for in one phrase, and a failure therefore reads "expected a number" in place of listing the terminals p bottoms out in. An expect inside another leaves the inner one alone: the innermost label is the specific one, and the specific one is what helps.

Line and column are computed once, at failure-construction time, in one pass over the input, and never during matching, where they would cost something on every step and be thrown away on nearly all of them. They count scalars and never bytes, which is what hanki check prints for its own diagnostics: a line of ééé puts its fourth column at byte 6.

Write it as text. The constructors are for grammars built from data

compile(source) reads Ford's notation - name <- expression, the first rule the start, and hands back the same validated Grammar the constructors build. It is the spelling to reach for. sum <- product ('+' product)* is most of it: / for ordered choice, juxtaposition for sequence, * + ? for repetition, & ! for the predicates, . for one scalar, [a-z] for a class, \n \r \t and \<punctuation> for an escape, {…} for a capture, {:name: … :} for a named one, {} for a position, and -- to end of line for a comment. !. is end of input, which needs no syntax of its own: it is "no scalar follows".

Two of those are choices and no transcriptions, and both surprise someone eventually. Comments are -- and not #: a grammar sits inside a Hanki string literal where #{ opens an interpolation. And a definition's expression runs until the next name <-, and a line missing its arrow therefore continues the rule above, Ford as specified, and caught in practice by the grammar compile, which reports the run-on word as a rule nothing defines.

A named capture is a tag, and text therefore builds the same tree the constructors do and parse_into decodes it the same way.

Reach for the constructors where the grammar's form comes from data: a keyword list becoming a choice of literals, which text can only do by splicing strings, losing the static check and inviting injection. And for expect, the one construct with no notation spelling (banked, hanki-ppzv). That is LPeg's arrangement too: re is the sugar, the combinator API is for generated patterns.

Neither is the expensive one. A top-level compile(source) folds at build time as a grammar(…) binding does, notation parse and validation together. And what it builds is the same: a class compiles to one set and no choice of alternatives, and a one-element sequence or choice wrapper is elided, and the two spellings therefore measure within a few percent of each other across the calc, json, match and url fixtures.

matched_length matches a bare pattern with no grammar around it, and it runs none of the checks above and builds no tree: a nullable loop it tolerates, a rule reference it reports as UnresolvedRule. Reach for pattern(p) to get the same single pattern validated, and its captures.

What this costs, and where not to reach for it

A grammar costs about 5x a hand-written parser on a realistic workload, and much more on small ones. Measured against hand-written parsers by tools/bench.hk, on the AOT tier, which is the one a shipped program runs:

json, a ~500-byte document 4.84x (steps 7.45x, bytes 3.72x) RFC 3339, a ~25-byte timestamp ~5x http.parse_url, a short string ~17x

The spread is the important part and it is not noise. peg's overhead is heavily per parse and not per byte, entering the matcher, walking the grammar, setting up captures, and it therefore amortises over a document and dominates a short string. A parser called once on something long is peg at its best; a parser called in a loop on something short is peg at its worst.

So: reach for a grammar for application-level parsing - a config file, a data format, a small language, anything where the parse is not the program's inner loop. The cost is real and it is not what will make that program slow, and what you get back is a grammar that reads like the language it accepts, static validation that names the broken rule, and located failures with expected sets that cannot drift from the grammar.

Do not reach for it where parsing is performance-critical, and in particular not inside the stdlib. That second rule is stronger than it looks: a stdlib author cannot know whether a caller parses one URL at startup or a million in a loop, and the cost of a conversion is inherited by every user and cannot be reasoned about locally. extra/json, extra/http and extra/datetime retain their hand-written parsers for this reason, and that is a decision about who pays and no verdict on the module. Converting a stdlib parser to a grammar is a tools/bench.hk measurement first; every candidate measured so far was refused.

docs/design/peg-rationale.md has the cost floor these numbers sit on and the rest of the measurement record.

ParseFailure

struct ParseFailure
  position: int
  line: int
  column: int
  expected: List<string>
  reason: MatchReason
end

How far a parse got, why it stopped there, and what would have let it go on. position is the farthest byte offset any branch reached, and never where the last branch happened to give up: an ordered choice whose first option dies at offset 0 must not report offset 0 when a later option got to 20.

line and column are 1-based and counted in scalars, matching what hanki check prints for its own diagnostics, and computed here rather than during matching: one pass over the input, once, at the end.

MatchReason

type MatchReason
  NoMatch
  TooDeep
  UnresolvedRule
end

Why matching stopped. TooDeep is the depth cap and no pattern that did not fit: the two look the same to a caller who only sees a failure.

impl Display<MatchReason>

to_string

def to_string(self) -> string

Renders the reason as a phrase, for a caller assembling its own message.

NoMatch.to_string() => "no match"

impl Eq<MatchReason>

eq?

def eq?(self, other: Self) -> bool

Equal when both name the same reason.

NoMatch.eq?(NoMatch) => true
NoMatch.eq?(TooDeep) => false

impl Display<ParseFailure>

to_string

def to_string(self) -> string

One located line, in the form hanki check uses: line:column: what.

ParseFailure(position=6, line=3, column=7, expected=["\"+\"", "a digit"], reason=NoMatch).to_string() => "3:7: expected one of \"+\", a digit"
ParseFailure(position=0, line=1, column=1, expected=["\"a\""], reason=NoMatch).to_string() => "1:1: expected \"a\""
ParseFailure(position=4, line=1, column=5, expected=[], reason=TooDeep).to_string() => "1:5: pattern nested past the depth cap"

_explain

def _explain(failure: ParseFailure) -> string

expectedphrase

def _expected_phrase(expected: List<string>) -> string

impl Eq<ParseFailure>

eq?

def eq?(self, other: Self) -> bool

Structural, which lets a test name the failure it expects.

ParseFailure(position=1, line=1, column=2, expected=[], reason=NoMatch).eq?(ParseFailure(position=1, line=1, column=2, expected=[], reason=NoMatch)) => true

samestrings?

def _same_strings?(a: List<string>, b: List<string>) -> bool

_rank

def _rank(r: MatchReason) -> int

Capture

type Capture
  Text(string)
  Node(string, List<Capture>)
  Index(int)
end

What a parse produced. Captures are opt-in: nothing is captured unless a capture, tag or position asked for it, and a parse that only recognises allocates nothing per scalar.

Text payloads are always valid slices, every primitive consuming whole scalars. str.slice rounds a mid-scalar offset down, and a byte-level capture could lose a character unreported, and this module is built so the offsets never land there.

impl Display<Capture>

to_string

def to_string(self) -> string

Text in quotes, a position as @n, a tagged node as name(children).

Text("ab").to_string() => "\"ab\""
Index(3).to_string() => "@3"
Node("pair", [Text("a"), Index(1)]).to_string() => "pair(\"a\", @1)"

impl Eq<Capture>

eq?

def eq?(self, other: Self) -> bool

Structural, which lets a test name the tree it expects.

Text("a").eq?(Text("a")) => true
Node("x", [Text("a")]).eq?(Node("x", [Text("b")])) => false

samecaptures?

def _same_captures?(a: List<Capture>, b: List<Capture>) -> bool

Prefix

struct Prefix
  length: int
  captures: List<Capture>
end

How much of the input a prefix parse consumed, and what it produced.

_PegRange

struct _PegRange
  lo: string
  hi: string
  lo_byte: int
  hi_byte: int
end

One inclusive scalar range. Scalars compare as single-scalar strings: UTF-8 byte order is code point order, and lo <= c <= hi reads the same in both.

asciicode

def _ascii_code(c: string) -> int

The byte value of a one-byte scalar, or -1 for anything wider.

The table is a local literal and no top-level binding, and that is forced and not chosen: this def runs during compile-time evaluation of the grammar constants, and a top-level constant it referenced would not be resolved yet ("its body did not lower before the module's constants were resolved"). A literal costs nothing here: a string is a primitive and interns into the constant pool, where an aggregate would be rebuilt at every reference (hanki-k1sr).

find returns a byte offset into printable ASCII starting at 32, and the offset plus 32 is the code. Doing it this way in place of through to_bytes is also the cheaper shape, and it used to be forced: the bytes accessors did not fold at compile time, and one here would have stopped a top-level grammar binding folding at all. bytes.length and bytes.get_or fold now (HANKI.md 21), added when the matcher moved onto bytes and took compile's fold with it. That path cannot be probed from inside this module - compile reads the _NOTATION constant, and one constant cannot depend on another in the same module, and the probe is therefore a caller: crates/hanki-cli/tests/lang/peg_notation_folds.rs.

_range

def _range(lo: string, hi: string) -> _PegRange

_PegClass

struct _PegClass
  ranges: List<_PegRange>
  negated: bool
  all_ascii: bool
  ascii_lo: List<int>
  ascii_hi: List<int>
end

_class

def _class(ranges: List<_PegRange>, negated: bool) -> _PegClass

all_ascii and the two bound lists are decided once, when the grammar is built, and a top-level grammar binding decides them at compile time. The matcher then never asks.

The bounds are held as parallel List<int> and not read back off ranges, and the per-scalar test can therefore index them with get_or and an int default, which allocates nothing, where a _PegRange default would have to construct the very thing the fast path exists to avoid.

_PegRepeat

struct _PegRepeat
  inner: _PegNode
  min: int
  max: Option<int>
end

A repeated node. max None is unbounded. Repetition is possessive: a completed repeat is never re-entered, which is what gives a PEG its bound.

_PegNode

type _PegNode
  PegEmpty
  PegLiteral(string)
  PegAny
  PegSet(_PegClass)
  PegSequence(List<_PegNode>)
  PegChoice(List<_PegNode>)
  PegRepeat(_PegRepeat)
  PegAhead(_PegNode)
  PegNotAhead(_PegNode)
  PegEndOfInput
  PegRule(string)
  PegRuleAt(int)
  PegCapture(_PegNode)
  PegTag(string, _PegNode)
  PegPosition
  PegExpect(string, _PegNode)
end

Peg

opaque Peg
  _node: _PegNode
end

A parsing expression, built from the constructors below and matched by matched_length.

max_depth

def max_depth() -> int

How deeply a pattern may nest before matching gives up.

max_depth() => 128

literal

def literal(text: string) -> Peg

Matches text, byte for byte.

matched_length(literal("abc"), "abcdef") => Ok(3)
matched_length(literal(""), "abc") => Ok(0)

any

def any() -> Peg

Matches one Unicode scalar, whatever it is.

matched_length(any(), "a") => Ok(1)
matched_length(any(), "é") => Ok(2)

one_of

def one_of(chars: string) -> Peg

Matches one scalar drawn from chars.

matched_length(one_of("abc"), "b") => Ok(1)
matched_length(one_of("abc"), "z").map_err(|e| e.position) => Err(0)

none_of

def none_of(chars: string) -> Peg

Matches one scalar that is NOT in chars. It still consumes a scalar, so it fails at the end of the input in place of succeeding on nothing.

matched_length(none_of("abc"), "z") => Ok(1)
matched_length(none_of("abc"), "").map_err(|e| e.position) => Err(0)

scalar_range

def scalar_range(lo: string, hi: string) -> Peg

Matches one scalar between lo and hi inclusive.

matched_length(scalar_range("a", "f"), "c") => Ok(1)
matched_length(scalar_range("α", "ω"), "γ") => Ok(2)

ascii_digit

def ascii_digit() -> Peg

Matches one ASCII decimal digit.

matched_length(one_or_more(ascii_digit()), "2026x") => Ok(4)

ascii_alphabetic

def ascii_alphabetic() -> Peg

Matches one ASCII letter, either case.

matched_length(one_or_more(ascii_alphabetic()), "abZ9") => Ok(3)

ascii_alphanumeric

def ascii_alphanumeric() -> Peg

Matches one ASCII letter or decimal digit.

matched_length(one_or_more(ascii_alphanumeric()), "a9Z-") => Ok(3)

ascii_whitespace

def ascii_whitespace() -> Peg

Matches one ASCII space, tab, newline or carriage return.

matched_length(one_or_more(ascii_whitespace()), "  x") => Ok(2)

sequence

def sequence(parts: List<Peg>) -> Peg

Matches parts in order. A part that fails fails the whole sequence: a PEG sequence does not try shorter prefixes of an earlier part, the enclosing choice is what retries.

matched_length(sequence([literal("a"), literal("b")]), "ab") => Ok(2)

choice

def choice(options: List<Peg>) -> Peg

Tries options in order and takes the first that matches. Ordered choice, not the longest alternative: choice([literal("a"), literal("ab")]) never matches ab whole.

matched_length(choice([literal("a"), literal("ab")]), "ab") => Ok(1)
matched_length(choice([literal("ab"), literal("a")]), "ab") => Ok(2)

optional

def optional(p: Peg) -> Peg

Matches p if it is there, and matches nothing if it is not. Never fails, and a sequence therefore never stalls on it.

matched_length(optional(literal("a")), "ab") => Ok(1)
matched_length(optional(literal("a")), "b") => Ok(0)

zeroormore

def zero_or_more(p: Peg) -> Peg

Matches p as many times as it will go, zero included. Possessive: what it consumed it retains, even where a later part of the sequence then fails.

matched_length(zero_or_more(literal("a")), "aaab") => Ok(3)

oneormore

def one_or_more(p: Peg) -> Peg

Matches p at least once, then as many more times as it will go. Fails when the first one does.

matched_length(one_or_more(literal("a")), "aaab") => Ok(3)
matched_length(one_or_more(literal("a")), "b").map_err(|e| e.position) => Err(0)

repeat

def repeat(p: Peg, min: int, max: int) -> Peg

Matches p between min and max times inclusive. Bounds that cross (max below min) can never be met, and the pattern therefore never matches.

matched_length(repeat(literal("a"), 2, 3), "aaaa") => Ok(3)

capture

def capture(p: Peg) -> Peg

Captures the text p matched, as a Text.

pattern(capture(one_or_more(ascii_digit()))).map(|g| g.parse("2026")) => Ok(Ok([Text("2026")]))

tag

def tag(name: string, p: Peg) -> Peg

Collects whatever p captured into one Node under name. This is the tree builder, and it nests: a tag inside a tag becomes a child.

pattern(tag("pair", sequence([capture(any()), capture(any())]))).map(|g| g.parse("ab")) => Ok(Ok([Node("pair", [Text("a"), Text("b")])]))

expect

def expect(p: Peg, label: string) -> Peg

Names what p is for, in one phrase, and a failure therefore says "expected an identifier" in place of listing the terminals p bottoms out in. An expect inside another leaves the inner one alone: the innermost label is the specific one, and the specific one is what helps a reader.

pattern(expect(one_or_more(ascii_digit()), "a number")).map(|g| g.parse("x").map_err(|e| e.to_string())) => Ok(Err("1:1: expected a number"))

position

def position() -> Peg

Captures the current byte offset as an Index, consuming nothing.

pattern(sequence([literal("ab"), position()])).map(|g| g.parse("ab")) => Ok(Ok([Index(2)]))

ahead

def ahead(p: Peg) -> Peg

Matches where p matches, consuming nothing.

matched_length(sequence([ahead(literal("a")), literal("ab")]), "ab") => Ok(2)

not_ahead

def not_ahead(p: Peg) -> Peg

Matches where p does NOT match, consuming nothing.

matched_length(not_ahead(literal("z")), "ab") => Ok(0)

endofinput

def end_of_input() -> Peg

Matches only at the end of the input, consuming nothing.

matched_length(sequence([literal("ab"), end_of_input()]), "ab") => Ok(2)

alphabeticranges

def _alphabetic_ranges() -> List<_PegRange>

scalarranges

def _scalar_ranges(chars: string) -> List<_PegRange>

Every scalar of chars as a one-scalar range. A set is a list of ranges so one_of and scalar_range share one membership test.

_Step

struct _Step
  text: string
  width: int
end

One scalar and the bytes it occupies.

scalarwidth

def _scalar_width(b: bytes, i: int) -> int

How many bytes the scalar at i occupies, or 0 at or past the end, read off the UTF-8 lead byte, and it allocates nothing. _scalar_at below still exists for the two callers that need the scalar's text; the matcher itself does not, which is the division: a scan that only has to advance should not have to build a one-character string, a _Step and an Option to learn how far.

scalarat

def _scalar_at(s: string, i: int) -> Option<_Step>

The scalar starting at byte offset i, or None at or past the end. slice rounds a mid-scalar stop down, and a too-short window comes back empty and the width grows until the whole scalar fits. ASCII takes the first turn of that loop, which is the common case and costs one slice.

inclass?

def _in_class?(k: _PegClass, c: string) -> bool

inclass_byte?

def _in_class_byte?(k: _PegClass, c: int) -> bool

The same test against a raw byte, for a class whose every bound is one byte (all_ascii, decided when the grammar is built). Identical semantics on that subset: a one-byte scalar compares the same as the one-character string it would have been sliced into, and no allocation at all.

failcode

def _fail_code() -> int

The outcome is encoded in _Progress.next: a non-negative value is the offset matching advanced to, and the three ways of not advancing are negative sentinels. A sum variant would be a heap allocation on every node visit, and the floor measurement on hanki-pl6r.8 puts allocation at most of what a minimal parse costs - zero_or_more(any()) runs about 150 bytecode steps per character, four to six of them allocations.

The comparisons are written out at each site and not wrapped in predicates: a predicate is a call, and at three or four tests per visit that costs more than the single dispatch the encoding removed, measured at +1.7% of steps for -12% of bytes, which inlining turns back into a win on both. Nothing outside this file sees the encoding.

deepcode

def _deep_code() -> int

unresolvedcode

def _unresolved_code() -> int

_Reach

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

One node's result: where matching continues, plus the farthest offset any branch reached on the way, retained even on success, a later sibling's failure reports the farthest of the whole attempt. How far any branch reached and what would have let it go on. The merge rule is megaparsec's: the greater offset wins outright, and equal offsets union their expected sets. labelled records that an expect already replaced the raw terminals here, and an outer expect therefore leaves it alone: the innermost label is the one a reader wants.

_reach

def _reach(at: int) -> _Reach

_wanted

def _wanted(at: int, what: string) -> _Reach

_merge

def _merge(a: _Reach, b: _Reach) -> _Reach

The two empty? arms are no optimisation of the union: they are the union, for the case that dominates. A branch that succeeded wants nothing, so its expected is empty and its labelled false, and every merge along a successful parse is therefore against a reach that contributes nothing. Falling through to _union there allocates a closure, a filter result and a concat result to reproduce a list that is already correct.

_union

def _union(a: List<string>, b: List<string>) -> List<string>

_Progress

struct _Progress
  next: int
  reach: _Reach
  captures: List<Capture>
end

_advanced

def _advanced(next: int, reach: _Reach, captures: List<Capture>) -> _Progress

The merge exists to record that matching reached at least next. When the accumulated reach is already at or past it, which it is wherever any branch failed further along, and after any part that consumed input, the merge returns reach unchanged, and building _reach(next) first therefore allocates a _Reach and an empty list purely to throw them away. Composite nodes run this on every visit, and a sequence visit was measured at roughly 220 bytecode steps against a whole-document floor of 150 per character.

_stepped

def _stepped(next: int, captures: List<Capture>) -> _Progress

What a terminal reports: it advanced, and the farthest anything reached is where it advanced to. _advanced(next, _reach(next), acc) says the same thing but says it twice, building one _Reach at the call site and a second inside, then merging two identical values. Terminals are the nodes run per input scalar, and that pair is most of what a scan allocates.

_failed

def _failed(reach: _Reach) -> _Progress

The three failure shapes carry no captures: a branch that did not match contributes nothing, and its caller retains the accumulator it already had.

_unresolved

def _unresolved(at: int) -> _Progress

_exhausted

def _exhausted(at: int) -> _Progress

_max

def _max(a: int, b: int) -> int

_match

def _match(rules: List<_PegNode>, node: _PegNode, input: string, b: bytes, pos: int, depth: int, cap: int, acc: List<Capture>) -> _Progress

rules is the grammar's resolved rule bodies, empty when matching a bare pattern: a rule reference then has nothing to resolve against and says so in place of matching nothing unreported.

matchcapture

def _match_capture(rules: List<_PegNode>, inner: _PegNode, input: string, b: bytes, pos: int, depth: int, cap: int, acc: List<Capture>) -> _Progress

capture(p) retains the text p consumed. The slice is boundary-valid by construction: every primitive consumes whole scalars, and neither offset can land mid-scalar.

matchtag

def _match_tag(rules: List<_PegNode>, name: string, inner: _PegNode, input: string, b: bytes, pos: int, depth: int, cap: int, acc: List<Capture>) -> _Progress

tag(name, p) runs p over its OWN accumulator and folds whatever it gathered into one node, and nesting a tag inside a tag therefore nests the tree.

matchliteral

def _match_literal(text: string, input: string, pos: int, acc: List<Capture>) -> _Progress

matchany

def _match_any(b: bytes, pos: int, acc: List<Capture>) -> _Progress

Advancing over one scalar needs its width and no more, and this therefore reads the lead byte and allocates nothing at all.

matchset

def _match_set(k: _PegClass, input: string, b: bytes, pos: int, acc: List<Capture>) -> _Progress

The hottest path in the module: one class test per input scalar. A class whose bounds are all one byte, which is nearly all of them, takes the first branch and allocates nothing. Anything wider falls back to slicing the scalar out and comparing it as text, which is what bounds scalar_range("α", "ω") working.

_describe

def _describe(k: _PegClass) -> string

A set renders the way it was written: [a-z0-9], or [^abc] when inverted. A one-scalar range collapses to the scalar it admits.

matchexpect

def _match_expect(rules: List<_PegNode>, label: string, inner: _PegNode, input: string, b: bytes, pos: int, depth: int, cap: int, acc: List<Capture>) -> _Progress

expect(p, label) says what p is for, in one phrase, in place of whatever terminals it happens to bottom out in. An expect inside another leaves the inner one alone: the innermost label is the specific one, and the specific one is what helps.

matchsequence

def _match_sequence(rules: List<_PegNode>, parts: List<_PegNode>, input: string, b: bytes, pos: int, depth: int, cap: int, acc: List<Capture>) -> _Progress

matchchoice

def _match_choice(rules: List<_PegNode>, options: List<_PegNode>, input: string, b: bytes, pos: int, depth: int, cap: int, acc: List<Capture>) -> _Progress

matchrepeat

def _match_repeat(rules: List<_PegNode>, r: _PegRepeat, input: string, b: bytes, pos: int, depth: int, cap: int, acc: List<Capture>) -> _Progress

A counting loop, never per-item recursion: the item count is input-sized, and recursion there would spend host stack proportional to the input.

repeatfull?

def _repeat_full?(r: _PegRepeat, count: int) -> bool

matchahead

def _match_ahead(rules: List<_PegNode>, inner: _PegNode, input: string, b: bytes, pos: int, depth: int, cap: int, acc: List<Capture>, expect: bool) -> _Progress

expect true is ahead, false is not_ahead. Both consume nothing, and the farthest offset the predicate reached is not retained: a lookahead that ran past the failure point would move the reported position to text no branch ever committed to.

matched_length

def matched_length(pattern: Peg, input: string) -> Result<int, ParseFailure>

How many bytes of input the pattern consumes from offset 0, or how far it got before failing. Matching is anchored: it starts at 0 and never searches forward, and a pattern that does not match the beginning fails.

matched_length(literal("ab"), "abc") => Ok(2)
matched_length(literal("z"), "abc").map_err(|e| e.position) => Err(0)

_outcome

def _outcome(step: _Progress, input: string) -> Result<int, ParseFailure>

A finished match as a caller sees it. Line and column are computed here and here alone: one pass over the input at the end, and never per step.

_failure

def _failure(reach: _Reach, input: string, reason: MatchReason) -> ParseFailure

_Place

struct _Place
  line: int
  column: int
end

linecolumn

def _line_column(input: string, at: int) -> _Place

1-based line and column at byte offset at, counted in scalars, the convention hanki check prints for its own diagnostics, where a multibyte scalar is one column and not its byte width.

rule

def rule(name: string) -> Peg

Refers to the rule named name, resolved when the grammar is compiled. On its own, handed to matched_length and not to grammar, it has nothing to resolve against and fails with UnresolvedRule.

grammar("pair", [define("pair", sequence([rule("digit"), rule("digit")])), define("digit", ascii_digit())]).map(|g| g.parse("42")) => Ok(Ok([]))
matched_length(rule("nowhere"), "abc").map_err(|e| e.reason) => Err(UnresolvedRule)

Definition

struct Definition
  name: string
  pattern: Peg
end

One named rule.

define

def define(name: string, pattern: Peg) -> Definition

Names pattern so other rules can refer to it with rule(name).

define("digits", one_or_more(ascii_digit())).name => "digits"
grammar("greeting", [define("greeting", sequence([rule("hi"), literal("!")])), define("hi", literal("hello"))]).map(|g| g.parse("hello!")) => Ok(Ok([]))

GrammarError

type GrammarError
  UnknownRule(string, string)
  DuplicateRule(string)
  LeftRecursion(List<string>)
  NullableLoop(string)
  RuleTooDeep(string)
end

Why a grammar would not compile. Every arm names the rule involved - a grammar that will not build should say which line of it is wrong.

impl Display<GrammarError>

to_string

def to_string(self) -> string

Renders one line naming the rule at fault.

DuplicateRule("term").to_string() => "duplicate rule `term`"
LeftRecursion(["sum", "sum"]).to_string() => "left recursion: sum -> sum"

impl Eq<GrammarError>

eq?

def eq?(self, other: Self) -> bool

Structural, which lets a test name the error it expects.

DuplicateRule("a").eq?(DuplicateRule("a")) => true
DuplicateRule("a").eq?(DuplicateRule("b")) => false

Grammar

opaque Grammar
  _rules: List<_PegNode>
  _names: List<string>
  _start: int
end

A validated grammar: every rule reference already resolved to an index, so matching looks a rule up with List.get and never touches a Map.

grammar

def grammar(start: string, definitions: List<Definition>) -> Result<Grammar, GrammarError>

Compiles definitions into a grammar starting at the rule named start, or says why it will not build. Every check here is static: a grammar that compiles cannot recurse for ever on any input.

grammar("word", [define("word", one_or_more(ascii_alphabetic()))]).map(|g| g.parse_prefix("abc1").map(|p| p.length)) => Ok(Ok(3))
grammar("gone", []).map(|_| "ok").map_err(|e| e.to_string()) => Err("unknown start rule `gone`")

pattern

def pattern(p: Peg) -> Result<Grammar, GrammarError>

The rule-less case: one anonymous pattern as a grammar. Still fallible, because the nullable-loop check applies to it like any rule body.

pattern(one_or_more(ascii_digit())).map(|g| g.parse("2026")) => Ok(Ok([]))
pattern(zero_or_more(optional(literal("a")))).map(|_| "ok").map_err(|e| e.to_string()) => Err("rule `pattern` repeats a pattern that can match nothing")

impl Grammar

parse

def parse(self, input: string) -> Result<List<Capture>, ParseFailure>

Matches the whole of input, anchored at 0. Input left over is a failure positioned where the leftovers begin.

pattern(one_or_more(ascii_digit())).map(|g| g.parse("2026")) => Ok(Ok([]))
pattern(one_or_more(ascii_digit())).map(|g| g.parse("2026x").map_err(|e| e.position)) => Ok(Err(4))

parsewithmax_depth

def parse_with_max_depth(self, input: string, cap: int) -> Result<List<Capture>, ParseFailure>

parse with the depth cap named and not defaulted, for a grammar whose nesting is known to run deeper, or is held shallower by design.

pattern(literal("ab")).map(|g| g.parse_with_max_depth("ab", 4)) => Ok(Ok([]))

parse_prefix

def parse_prefix(self, input: string) -> Result<Prefix, ParseFailure>

How many bytes of input the grammar consumes from 0, leftovers allowed.

pattern(one_or_more(ascii_digit())).map(|g| g.parse_prefix("20x26").map(|p| p.length)) => Ok(Ok(2))

rule_names

prop rule_names(self) -> List<string>

The rule names, in definition order.

grammar("a", [define("a", literal("x"))]).map(|g| g.rule_names) => Ok(["a"])

noduplicates

def _no_duplicates(names: List<string>) -> Result<(), GrammarError>

resolveall

def _resolve_all(definitions: List<Definition>, names: List<string>) -> Result<List<_PegNode>, GrammarError>

_resolve

def _resolve(node: _PegNode, names: List<string>, owner: string, depth: int) -> Result<_PegNode, GrammarError>

Rewrites every PegRule(name) into the index it names. The depth check rides along on this one walk: a body nesting past the cap could never be matched, and refusing it here therefore beats failing every input later.

resolvelist

def _resolve_list(nodes: List<_PegNode>, names: List<string>, owner: string, depth: int) -> Result<List<_PegNode>, GrammarError>

nullablerules

def _nullable_rules(rules: List<_PegNode>) -> List<bool>

Which rules can match nothing, by fixpoint: start with none, and keep recomputing until the answer stops changing. A rule's nullability depends on the rules it calls, and one pass would under-report a mutual pair.

sameflags?

def _same_flags?(a: List<bool>, b: List<bool>) -> bool

_nullable?

def _nullable?(node: _PegNode, flags: List<bool>) -> bool

nonullable_loop

def _no_nullable_loop(rules: List<_PegNode>, names: List<string>, flags: List<bool>) -> Result<(), GrammarError>

nullableloop?

def _nullable_loop?(node: _PegNode, flags: List<bool>) -> bool

unboundednullable?

def _unbounded_nullable?(r: _PegRepeat, flags: List<bool>) -> bool

leftmostrefs

def _leftmost_refs(node: _PegNode, flags: List<bool>) -> List<int>

Every rule reachable at the leftmost position of node: the references a match would follow before consuming anything, which is the graph a left-recursive cycle sits in.

sequencerefs

def _sequence_refs(parts: List<_PegNode>, flags: List<bool>) -> List<int>

A sequence reaches its first part, and the one after it only while the parts before could all have matched nothing.

noleft_recursion

def _no_left_recursion(rules: List<_PegNode>, names: List<string>, flags: List<bool>) -> Result<(), GrammarError>

_Walk

struct _Walk
  cycle: Option<List<int>>
  done: List<int>
end

A depth-first walk with two marks: path is what is on the stack right now, and meeting it again is therefore the cycle, and done is what has been fully explored, and a shared subgraph is walked once and not once per route. Both are lists and no sets: a Set's hashing does not evaluate at compile time, and a grammar folding at compile time is the whole point of the pattern tree being data. Rule counts are small enough that the linear membership test costs nothing worth measuring.

walkleft

def _walk_left(rules: List<_PegNode>, flags: List<bool>, at: int, path: List<int>, done: List<int>) -> _Walk

NotationError

type NotationError
  Syntax(ParseFailure)
  Invalid(GrammarError)
end

Why a grammar written as text would not build: either the text itself is not the notation, or it is but the grammar it describes is not valid.

impl Display<NotationError>

to_string

def to_string(self) -> string

Renders whichever failure came back, both of which already locate themselves: a syntax error into the grammar text, a grammar error by rule name.

Invalid(DuplicateRule("term")).to_string() => "duplicate rule `term`"

impl Eq<NotationError>

eq?

def eq?(self, other: Self) -> bool

Structural, and a syntax error and a grammar error therefore never compare equal however similarly they happen to render.

Invalid(DuplicateRule("a")).eq?(Invalid(DuplicateRule("a"))) => true
Invalid(DuplicateRule("a")).eq?(Invalid(DuplicateRule("b"))) => false

_comment

def _comment() -> Peg

-- _spacing: whitespace and -- comments, both skippable anywhere ------

_spacing

def _spacing() -> Peg

_token

def _token(p: Peg) -> Peg

_word

def _word(text: string) -> Peg

namechar

def _name_char() -> Peg

-- names ---------------------------------------------------------------

rulename

def _rule_name() -> Peg

escapevalue

def _escape_value(c: string) -> string

What one backslash escape stands for. Everything unlisted stands for itself, which is what makes \], \-, \' and \\ work without enumerating punctuation, and it is strictly better than the alternative, since an unrecognised escape used to match the backslash as well.

_unescape

def _unescape(s: string) -> string

Decodes the escapes in a captured literal or class item.

Without this the notation had no escapes AT ALL, and the failure was silent and unreported: '\n' matched a backslash followed by an n, and [^\r\n] excluded the letters r and n while admitting a real carriage return. A grammar that looked like it rejected header injection did not, which is the reason this is a correctness fix and not a convenience one.

escapedor

def _escaped_or(excluded: string) -> Peg

One scalar of a literal or class, or a backslash and whatever follows it. The escape pair is tried first, and a \' inside a '...' literal therefore does not end the literal and a \] inside a class does not close the class.

_quoted

def _quoted(quote: string) -> Peg

literaltext

def _literal_text() -> Peg

classitem

def _class_item() -> Peg

charclass

def _char_class() -> Peg

anydot

def _any_dot() -> Peg

_expression

def _expression() -> Peg

-- the _expression grammar, by name -------------------------------------

namedcapture

def _named_capture() -> Peg

A named capture, {:name: p :}, spelled the way LPeg's re spells it. Without this the notation can capture text but cannot name it, so Capture.tagged has nothing to read and the whole typed-decode bridge is unreachable from a notation-written grammar, which is what held the readable spelling from being the recommended one.

positioncapture

def _position_capture() -> Peg

{} records an offset without consuming anything. It is the empty case of the capture braces and, again, LPeg re's spelling.

_primary

def _primary() -> Peg

Order matters: choice takes the first option that matches and all three of these start with {: the named form must be tried before the plain one or { would match and :name: would have to parse as an expression, and {} before { p } for the same reason.

_definitions

def _definitions() -> Peg

_bootstrap

def _bootstrap() -> Result<Grammar, GrammarError>

textof

def _text_of(c: Capture) -> string

childrenof

def _children_of(c: Capture) -> List<Capture>

tagof

def _tag_of(c: Capture) -> string

_elided

def _elided(parts: List<Peg>, wrap: (List<Peg>) -> Peg) -> Peg

choice node -> choice over its sequences A one-element wrapper is dropped and never built. choice([x]) and sequence([x]) mean x, and the depth cap counts effective nesting, what the matcher descends through, and eliding one cannot change when TooDeep fires.

That category measures empty for grammars one-part sequences across the json, url and rfc3339 grammars. Those are written with the constructors, where an author never writes a wrapper they does not need. The notation emits one for every construct it compiles: every expression became choice([sequence([...])]) - so the category is empty on one side of this module and full on the other, and Part 2 moves the weight onto the full side.

An empty list is left alone: sequence([]) matches nothing successfully and choice([]) fails, and neither is x.

toexpression

def _to_expression(c: Capture) -> Peg

tosequence

def _to_sequence(c: Capture) -> Peg

toprefixed

def _to_prefixed(c: Capture) -> Peg

tosuffixed_list

def _to_suffixed_list(kids: List<Capture>) -> Peg

tosuffixed

def _to_suffixed(c: Capture) -> Peg

suffixed node -> the _primary, wrapped in whatever repeat follows it

toprimary

def _to_primary(c: Capture) -> Peg

toclass

def _to_class(c: Capture) -> Peg

A class compiles to ONE set, the same node one_of / none_of / scalar_range build, and never to a choice of alternatives.

It did not always, and the cost was not small. [a-z0-9] used to become choice([scalar_range(a, z), scalar_range(0, 9)]) - a dispatch per alternative per character, and a negated class was worse: [^:/@[\r\n] became sequence([not_ahead(choice([six literals])), any()]), and every character of a host name tried six alternatives inside a lookahead and then consumed a scalar separately. Measured on tools/bench/url_peg.hk, whose host class is that: 10.2s against the constructor spelling's 2.4s, for a grammar accepting the same language and returning the same answer.

That mattered beyond one fixture. The notation is the spelling this module recommends, and the argument for recommending it is that it costs nothing over the constructors, which was false by 4.3x for any grammar with a negated class, until this.

toclass_range

def _to_class_range(c: Capture) -> _PegRange

One class item as a range. A single scalar is the degenerate range s-s, which is what lets every item share one set in place of taking a node each.

todefinition

def _to_definition(c: Capture) -> Definition

_NOTATION

_NOTATION: Result<Grammar, GrammarError> = _bootstrap()

The notation's own grammar, bound at the top level so it is built once at compile time and not per compile call, and this module therefore cannot ship a bootstrap that does not fold.

compile

def compile(source: string) -> Result<Grammar, NotationError>

Compile a grammar written in the text notation. The first rule is the start rule.

compile("word <- [a-z]+\n").map(|g| g.parse("abc").map(|_| "yes").map_err(|e| e.to_string())) => Ok(Ok("yes"))
compile("a <- 'x'\na <- 'y'\n").map(|_| "ok").map_err(|e| e.to_string()) => Err("duplicate rule `a`")
compile("bad <- ('x'\n").map(|_| "ok").map_err(|e| e.to_string().starts_with?("2:1:")) => Err(true)

CaptureShapeError

type CaptureShapeError
  UnexpectedShape(string, string)
  MissingChild(string, string)
  BadScalar(string, string)
end

Why a capture tree did not fit the type asked for, carrying the path it failed at as a chain/number-style name chain (a positional step reads [2]). The path an accessor reports starts at the capture it was called on; wrap a nested decode with within_capture to extend it upward.

impl Display<CaptureShapeError>

to_string

def to_string(self) -> string

Renders as path: what went wrong, and a nested cause therefore prints as expr/chain/number: "x" is not a valid scalar.

UnexpectedShape("chain", "a tagged node").to_string() => "chain: expected a tagged node"
MissingChild("chain", "[2]").to_string() => "chain: no child [2]"
BadScalar("number", "x").to_string() => "number: \"x\" is not a valid scalar"

impl Eq<CaptureShapeError>

eq?

def eq?(self, other: Self) -> bool

Structural, arm by arm, which lets a test name the failure it expects. No comparison of the rendered forms: BadScalar reports untrusted input text, which is the payload most able to render into another arm's form.

MissingChild("a", "b").eq?(MissingChild("a", "b")) => true
MissingChild("a", "b").eq?(MissingChild("a", "c")) => false
UnexpectedShape("a", "b").eq?(MissingChild("a", "b")) => false

within_capture

def within_capture<T>(parent: string, result: Result<T, CaptureShapeError>) -> Result<T, CaptureShapeError>

Extend a nested decode error's path with a parent segment: a failure at number inside the decode of a chain becomes chain/number.

within_capture("chain", Err(MissingChild("number", "[0]"))).map(|x: int| x).map_err(|e| e.to_string()) => Err("chain/number: no child [0]")
within_capture("chain", Ok(7)).map_err(|e| e.to_string()) => Ok(7)

_under

def _under(parent: string, e: CaptureShapeError) -> CaptureShapeError

pathof

def _path_of(c: Capture) -> string

What a capture is called when it appears in a path: a node's tag, and the kind for a leaf, which has no name of its own.

scalarof

def _scalar_of(c: Capture) -> Capture

The capture a scalar decode reads: a leaf as itself, or the single child of a tag, since tag("age", capture(digits)) is how a named scalar field is spelled and the accessors hand back the node. Peeling is one level and one child only: a tag with several children is a record and no scalar, and a tag wrapping a tag is one too.

Peeling before the kind is inspected, and not after, is what lets a named position() decode: tag("at", position()) reaches the int impl as the Index it wraps, where reading only text would have made a named offset field unspellable.

FromCaptures

trait FromCaptures

Rebuild a value of Self from one capture, or report how it did not fit.

A struct's impl is usually derived and not written: @derive(FromCaptures) reads each field from the capture tagged with its own name, which is what the grammar already spells. Writing it by hand cost tools/bench/url_peg.hk more tokens than its whole grammar did. Reach for the hand-written impl when the mapping is not field-name-to-tag: a sum, a generic, or a field needing child(at) by position.

from_captures

def from_captures(c: Capture) -> Result<Self, CaptureShapeError>

Decode a Self from c.

@no-doctest: a trait declaration has no behaviour of its own; each impl below has its own example

impl FromCaptures<string>

from_captures

def from_captures(c: Capture) -> Result<string, CaptureShapeError>

The text a capture kept, verbatim.

string.from_captures(Text("ada")) => Ok("ada")
string.from_captures(Index(3)).map_err(|e| e.to_string()) => Err("position: expected captured text")

impl FromCaptures<int>

from_captures

def from_captures(c: Capture) -> Result<int, CaptureShapeError>

Captured text parsed as an arbitrary-precision integer, or a position() capture, which already is one, named or bare, tag("at", position()) is the only way to give an offset a name.

int.from_captures(Text("2026")) => Ok(2026)
int.from_captures(Index(3)) => Ok(3)
int.from_captures(Node("at", [Index(3)])) => Ok(3)
int.from_captures(Text("x")).map_err(|e| e.to_string()) => Err("text: \"x\" is not a valid scalar")

impl FromCaptures<decimal>

from_captures

def from_captures(c: Capture) -> Result<decimal, CaptureShapeError>

Captured text parsed as an exact decimal. The lowercase tier is the default here and not f64: a capture is text, and parsing it into a rounding type would lose precision the input still had. Cross to f64 explicitly with to_f64() when hardware semantics are what is wanted.

decimal.from_captures(Text("1.5")) => Ok(1.5)
decimal.from_captures(Text("x")).map_err(|e| e.to_string()) => Err("text: \"x\" is not a valid scalar")

eachchild

def _each_child<T: FromCaptures>(name: string, kids: List<Capture>) -> Result<List<T>, CaptureShapeError>

_at

def _at(owner: string, at: int) -> string

The path segment for the at-th child of owner. Without the index, every element of a repetition reports the same path and the one that failed cannot be told from its siblings.

impl<T: FromCaptures> FromCaptures<List<T>>

from_captures

def from_captures(c: Capture) -> Result<List<T>, CaptureShapeError>

Every child of a tagged node, in match order. A leaf has no children to decode, and it is therefore a shape failure and no empty list.

xs: Result<List<int>, CaptureShapeError> = List.from_captures(Node("row", [Text("1"), Text("2")]))
xs => Ok([1, 2])
ys: Result<List<int>, CaptureShapeError> = List.from_captures(Text("1"))
ys.map_err(|e| e.to_string()) => Err("text: expected a tagged node")

childrennamed

def _children_named(kids: List<Capture>, name: string) -> List<Capture>

impl Capture

child

def child<T: FromCaptures>(self, at: int) -> Result<T, CaptureShapeError>

Decode the child at at, the positional field read. A leaf has no children, and an index past the end is a MissingChild.

pair = Node("pair", [Text("ada"), Text("36")])
who: Result<string, CaptureShapeError> = pair.child(0)
who => Ok("ada")
age: Result<int, CaptureShapeError> = pair.child(1)
age => Ok(36)
gone: Result<int, CaptureShapeError> = pair.child(9)
gone.map_err(|e| e.to_string()) => Err("pair: no child [9]")

tagged

def tagged<T: FromCaptures>(self, name: string) -> Result<T, CaptureShapeError>

Decode the first child tagged name, the named field read.

row = Node("row", [Node("who", [Text("ada")]), Node("age", [Text("36")])])
who: Result<string, CaptureShapeError> = row.tagged("who")
who => Ok("ada")
gone: Result<int, CaptureShapeError> = row.tagged("nope")
gone.map_err(|e| e.to_string()) => Err("row: no child `nope`")

optional_tagged

def optional_tagged<T: FromCaptures>(self, name: string) -> Result<Option<T>, CaptureShapeError>

Decode the first child tagged name when there is one. An optional(p) that did not match contributes no capture, and absence is Ok(None) and no failure.

row = Node("row", [Node("who", [Text("ada")])])
who: Result<Option<string>, CaptureShapeError> = row.optional_tagged("who")
who => Ok(Some("ada"))
age: Result<Option<int>, CaptureShapeError> = row.optional_tagged("age")
age => Ok(None)

all_tagged

def all_tagged<T: FromCaptures>(self, name: string) -> Result<List<T>, CaptureShapeError>

Decode every child tagged name, in match order, the repeated field read. None of them is an empty list and no failure; the first child that fails to decode stops the rest.

rows = Node("rows", [Node("n", [Text("1")]), Node("n", [Text("2")]), Node("other", [])])
ns: Result<List<int>, CaptureShapeError> = rows.all_tagged("n")
ns => Ok([1, 2])

DecodeError

type DecodeError
  Unparsed(ParseFailure)
  Unshaped(CaptureShapeError)
end

Why parse_into did not produce a value: the input did not match the grammar at all, or it matched and the captures did not fit the type.

impl Display<DecodeError>

to_string

def to_string(self) -> string

Renders whichever failure came back; both already locate themselves, one into the input and one into the capture tree.

Unshaped(MissingChild("row", "`age`")).to_string() => "row: no child `age`"

impl Eq<DecodeError>

eq?

def eq?(self, other: Self) -> bool

Structural. The two arms remain distinct; comparing rendered forms would not keep them apart: an Unparsed renders as line:column: what, and an Unshaped whose path happens to read 1:1 renders identically, which would defeat the whole reason the two are separate arms.

Unshaped(BadScalar("n", "x")).eq?(Unshaped(BadScalar("n", "x"))) => true
Unshaped(UnexpectedShape("1:1", "\"a\"")).eq?(Unshaped(BadScalar("n", "x"))) => false

_sole

def _sole(captures: List<Capture>) -> Option<Capture>

impl Grammar

parse_into

def parse_into<T: FromCaptures>(self, input: string) -> Result<T, DecodeError>

Parse input and decode what it captured into a T, in one step.

The grammar must produce one top-level capture and no more, a T being one value: a decoding grammar wraps its start rule in a tag, which is the same thing that gives the record its fields. Anything else is a shape failure and no guess about which capture was meant.

n: Result<Result<int, DecodeError>, GrammarError> = pattern(capture(one_or_more(ascii_digit()))).map(|g| g.parse_into("2026"))
n => Ok(Ok(2026))
m: Result<Result<int, DecodeError>, GrammarError> = pattern(sequence([capture(any()), capture(any())])).map(|g| g.parse_into("ab"))
m.map(|r| r.map_err(|e| e.to_string())) => Ok(Err("parse: expected exactly one top-level capture"))

_nest

def _nest(n: int) -> Peg

n sequences wrapped one inside the next, for the depth-cap test.

NUMBER

NUMBER: Result<Grammar, GrammarError> = grammar("number", [
  define("number", sequence([optional(literal("-")), rule("digits")])),
  define("digits", one_or_more(ascii_digit()))
])

A two-rule grammar bound at the top level. Top-level bindings are compile-time-evaluated, and this file therefore does not compile at all unless the whole of grammar folds, which makes the binding itself the probe.

onlytext_children?

def _only_text_children?(c: Capture) -> bool

_accepts

def _accepts(built: Result<Grammar, NotationError>, inputs: List<string>) -> List<bool>

Which of inputs a compiled grammar accepts whole, as a list of bools - what two spellings of one language must agree on.

_Person

struct _Person
  name: string
  age: int
  nickname: Option<string>
end

The worked shape a hand-written FromCaptures impl takes: one tag per record, one tagged child per field, read by name so the grammar can be reordered without touching the decode.

impl Eq<_Person>

eq?

def eq?(self, other: Self) -> bool

Structural, which lets a decode test name the record it expects.

@no-doctest: a fixture for the decode tests below; no public surface

impl FromCaptures<_Person>

from_captures

def from_captures(c: Capture) -> Result<_Person, CaptureShapeError>

Reads each field by its own tag and not by position, which lets the grammar can be reordered without touching the decode.

@no-doctest: a fixture for the decode tests below; no public surface

persongrammar

def _person_grammar() -> Result<Grammar, GrammarError>