Crate abnf_oracle

Expand description

ABNF grammars as a testing oracle.

Parses ABNF grammars (RFC 5234 as amended by RFC 7405 and Errata 2968 and 3076), decides whether an input string is in the language of a rule, and generates strings that are.

The emphasis is on being right, not fast. Alternation is unordered, backtracking is full, ambiguity is tolerated, and the recognizer computes the set of all end positions an element can reach rather than committing to the first branch that matches. What this crate is deliberately not is listed in SCOPE.md 3: no parse trees, no ambiguity detection, no PEG or regex semantics, no byte-oriented matching, and no performance promises.

§Shape of the API

Three types, used in order:

Grammar — the syntactic layer. What the parser produces: definitions as written.
CheckedGrammar — the semantic layer, produced by Grammar::check. Incremental alternatives are merged, names are resolved, and the analyses the recognizer and generator rely on have been run. It is the only route to either of them, so there is no way to recognize against a grammar whose structure was never validated.
Recognizer / Generator — bound to a checked grammar and a start rule.

§Example

use abnf_oracle::{Generator, Grammar, Recognizer};

// A grammar, as it would appear in an RFC.
let source = concat!(
    "full-date     = date-fullyear \"-\" date-month \"-\" date-mday\r\n",
    "date-fullyear = 4DIGIT\r\n",
    "date-month    = 2DIGIT\r\n",
    "date-mday     = 2DIGIT\r\n",
);

// Parse, then check. `check` merges incremental definitions, resolves every name and runs
// the analyses; it is the only way to reach a recognizer or a generator.
let grammar = Grammar::parse(source)
    .expect("valid ABNF")
    .check()
    .expect("no structural errors");

// Recognize.
assert!(Recognizer::new(&grammar, "2026-09-20").accepts("full-date").unwrap());
assert!(!Recognizer::new(&grammar, "20260920").accepts("full-date").unwrap());

// Generate. The same seed always gives the same string.
let mut generator = Generator::new(&grammar, 42);
let produced = generator.generate("full-date").expect("generates");

// What the generator produces, the recognizer accepts.
assert!(Recognizer::new(&grammar, &produced).accepts("full-date").unwrap());

§Errors are not rejections

A limit, a prose value or an unrepresentable terminal makes a question unanswerable, which is different from answering “no”. Every such case is an Err, never Ok(false), so a caller can never mistake “could not decide” for “does not match”.

Structs§

CharVal: A quoted string terminal: char-val in RFC 5234 4.
CheckErrors: Every structural problem found by crate::Grammar::check, in the order found.
CheckedGrammar: A grammar that passed structural validation.
Definition: One name = elements or name =/ elements definition, as written.
GenOptions: How to generate.
Generator: Generates strings that a rule accepts.
Grammar: A parsed grammar: the ordered definitions as written, after local rewrites only.
Ignored: A value that is carried but never compared: every Ignored<T> equals every other.
MatchOptions: Resource limits for recognition.
NodeId: An index into a checked grammar’s node arena.
ParseOptions: Syntactic options for parsing. Never semantic (SCOPE.md 4, D30).
Recognizer: Decides whether an input is in the language of a rule.
Repeat: Repetition bounds, inclusive on both ends.
Rule: A rule in the merged table: =/ folded into its base, body lowered into the arena.
RuleName: A rule name.
Span: A byte range in the grammar source text.

Enums§

CheckError: A structural problem: the grammar cannot be used at all.
DefinedAs: Which definition operator introduced a Definition: defined-as in RFC 5234 4.
Element: An element of a rule body, in the syntactic layer.
GenError: Generation could not be attempted, or could not be finished.
LintWarning: An advisory warning. Never fails check (D5).
MatchError: Recognition could not be attempted, or could not be finished.
MinLen: The length of the shortest string a node can match (SCOPE.md 6.4, D27).
Node: A node in the merged-grammar arena.
NumVal: A numeric terminal, in any of the three radices. The radix is not retained: %d65, %b1000001 and %x41 all parse to the same node and print as %x41 (SCOPE.md 6.7, D37).
ParseError: The grammar text could not be parsed.
RuleId: Identifies a rule in the merged table, distinguishing user rules from the implicit core-rule environment.
Witness: The choice a node’s shortest derivation makes (SCOPE.md 6.4, D28).

Constants§

DEFAULT_GEN_DEPTH: How deep the walk may recurse before it starts following witnesses.
DEFAULT_MAX_DEPTH: How deep the recognizer may recurse before giving up: MatchOptions::max_depth’s default.
DEFAULT_MAX_OUTPUT_LEN: How long a generated string may get before generation gives up.
DEFAULT_MAX_STEPS: How many nodes the walk may visit before it gives up.
DEFAULT_SPREAD: How many extra repetitions a repetition may take beyond its minimum.