Chapter 11
Input Generation
A grammar describes the inputs that it accepts, so it can also produce them. The sample package and the sxir sample
command generate inputs that a parser accepts, near-miss inputs that it rejects, and a report of which parts of the
grammar the accepted inputs exercised. They serve tests of code that consumes parse results and the seed corpora of
fuzz tests. This chapter defines what the generator guarantees, its options and its Go API.
The Go API of this chapter is experimental and MAY change incompatibly. Which inputs a seed gives MAY change between versions.
Scope and Terminology
A generator is a value of sample.Generator: it is made for one parser, from the grammar and the start rule of
that parser, and it keeps its state between calls. A candidate is a text that the generator writes by walking the
grammar from the start rule, deciding at each ordered choice, repetition, optional expression and
Operators Rule. An accepted input is a candidate that the parser parsed without
errors; a candidate that the parser accepts only by recovering from errors with #recover is not an accepted input. A near-miss invalid input is an accepted input, the
base, changed by one mutation so that the parser rejects it. Coverage is the part of the rules and
alternatives of the grammar that accepted inputs exercised.
Walking the grammar does not give an accepted input under the semantics of a parsing expression grammar: an ordered choice may never reach a later alternative, a greedy repetition takes all that it can, and lookaheads, predicates and variables depend on the text around them. The generator therefore steers away from the candidates that it can tell the parser would not accept, by evaluating predicates on the text that it has written and by checking what the parser would match as the text grows, and it parses every candidate. It does not evaluate what depends on the results of actions, which only parsing the candidate decides.
Contract
Entry Points
| Command line | Go (syntaxir.dev/sxir/pkg/sample) |
|
|---|---|---|
| Make a generator | sxir sample -g g.sxir |
sample.New(p, opts...) |
| Accepted inputs | -n |
sample.Generate(p, n, opts...), Generator.Generate(n), Generator.Next() |
| Near-miss invalid inputs | -invalid |
Generator.GenerateInvalid(n), Generator.Invalid() |
| Prefer what is not exercised yet, and report it | -coverage |
sample.WithCoverage(), Generator.Coverage() |
| Seed a fuzz test | sample.Seed(f, p, n, opts...) |
|
| Counts of the work | -f json, member stats |
Generator.Stats(), Generator.Cuts() |
Generators
sample.New(p, opts...) returns a generator for the parser p, starting at the start rule of p. It returns an error,
and no generator, if
pis not a parser that the compiler built from a grammar, such as one loaded from a compiled grammar, which holds no grammar (see Compiled Grammars);- the start rule of
pis not defined; or - the start rule can never match, so that no input exists.
A generator is not safe for concurrent use.
Generator.Next()returns an accepted input. Inputs MAY repeat between calls. It returns an error that wrapssample.ErrNoInputif no candidate was accepted within the attempts of one call (see Options); test for it witherrors.Is. The message tells what became of the attempts: how many candidates the parser rejected, how many searches ran out of budget or had no way to finish, how many ways the checks and the predicates cut, and the rules with the most cuts. The wording is not part of the contract.Generator.Generate(n)returns up tondistinct accepted inputs. It returns fewer if it cannot find more: it gives up after as many inputs in a row that it has already returned as the attempts for one input. It returns an error that wrapssample.ErrNoInputonly if it finds none, and no error and an empty list fornof 0 or less.sample.Generate(p, n, opts...)issample.New(p, opts...)followed byGenerate(n).
Every input that the functions of this chapter return as accepted has been parsed by p without errors, and Seed
parses it once more.
Determinism
The same parser, options and seed give the same inputs, in the same order, with the same version of the package,
whichever Go release built it: the package draws its random numbers with its own generator and not with
math/rand. The algorithm MAY change between versions, so a program that needs inputs that never change MUST keep
the inputs themselves.
Options
A sample.Option configures a generator. Values that are out of range are raised to the minimum, and are not errors.
| Option | Default | Effect |
|---|---|---|
WithSeed(seed) |
0 | The seed of the random decisions |
WithMaxDepth(d) |
DefaultMaxDepth, 5 |
A soft bound on recursion: once rule calls are nested d deep inside calls of the same rules, the generator prefers the shortest way to finish. Calls of rules that are not active do not count. The minimum is 0 |
WithMaxRepeat(n) |
DefaultMaxRepeat, 3 |
How many iterations an unbounded repetition aims for beyond its minimum, at most, and a bound on the operators of an Operators Rule chain. The minimum is 0 |
WithMaxLen(n) |
DefaultMaxLen, 512 |
A soft bound on the length of an input in bytes: once the input is that long, the generator prefers the alternatives with the shortest text to finish it. The minimum is 0 |
WithBudget(steps) |
DefaultBudget, 20000 |
The number of steps that one attempt may take before it gives up. A step is a parsing expression that is generated or an Operators Rule scope that is inspected. The minimum is 1 |
WithAttempts(n) |
DefaultAttempts, 100 |
The number of candidates that the generator tries for one input before it gives up. The minimum is 1 |
WithCoverage() |
off | Prefer the rules, the alternatives of ordered choices and the operands and operators of Operators Rules that no accepted input has exercised yet |
The bounds of depth, repetition and length are soft: when the text requires more, such as a predicate that counts the
nesting or a longer match, the search goes beyond them. The search has hard limits, which the options move: a call of a
rule never nests more than d + 8 deep inside calls of the same rules, and a repetition never takes more than
8 × n + 4 iterations beyond its minimum, where d and n are the values of WithMaxDepth and WithMaxRepeat. The
budget of steps also bounds the stack of the search, so an input that needs many steps needs a larger budget.
The budget of WithBudget is not a limit of parsing, and does not bound the analysis that sample.New makes of the
grammar.
Near-Miss Invalid Inputs
Generator.Invalid() takes an accepted input as the base, applies one mutation to it, and returns the result if the
parser rejects it. It tries up to eight mutations of a base, and up to as many bases as the attempts for one input.
It returns an error that wraps sample.ErrNoInput if it finds no accepted input to mutate, and sample.ErrNoInvalid
if it finds bases but no mutation of them that the parser rejects, as for a grammar of .*, which accepts every text.
A sample.Invalid has these members.
| Member | Meaning |
|---|---|
Input |
The mutated text, which the parser rejects. It differs from Base |
Base |
The accepted input that it was made from |
Mutation |
A description of the mutation, such as delete "]" at 12, where the positions are byte offsets in Base |
Err |
The error that the parser returned for Input, with the expectations of the syntax error |
The mutations delete a character or a run of up to 8 characters, insert a token, replace a character by a token, duplicate a run of up to 8 characters, swap two neighboring characters that differ, and truncate the input. A token is a literal or a character of the grammar, or a character chosen from a fixed list of punctuation, white space and a few other characters. A mutation cuts the text only at character boundaries, so a valid UTF-8 base gives a valid UTF-8 input.
Generator.GenerateInvalid(n) returns up to n near-miss inputs with distinct Input. It returns fewer if it cannot
find more, and the error of Invalid only if it finds none.
Coverage
Generator.Coverage() returns a sample.Coverage for the accepted inputs so far. It is measured on the way the
generator derived each input, which is the way the parser takes unless the generator could not evaluate a lookahead, a
predicate or an earlier alternative of a choice; the counts are close to the parser's own coverage, and are not
guaranteed to equal it.
| Member | Meaning |
|---|---|
Rules, RulesCovered |
The number of rules that the start rule can reach and that can match, and the number of them that an accepted input exercised |
Alternatives, AlternativesCovered |
The same for the alternatives of ordered choices and the operands and operators of Operators Rules of those rules. It leaves out alternatives that can never match, that occur only inside an expression that can never match, or that are in the tail of an Operators Rule that no reachable entry or prefix operator permits |
MissedRules |
The rules that were not exercised: each a sample.MissedRule with the Rule and the Why |
MissedAlternatives |
The alternatives that were not exercised: each a sample.MissedAlternative with the Alternative and the Why. A sample.Alternative has the Rule, the Kind (choice, operand or operator), the Index of the alternative in its choice or of the operand or operator in its Operators Rule, counting the operators of all levels, and the Expr in grammar syntax. Alternative.String() is rule: kind index: expr |
Unreachable |
The rules that generation cannot exercise from the start rule: rules that are not called, or that are called only inside negative lookaheads, the skip of #recover, expressions that can never match or blocked operator parts of an Operators Rule |
Impossible |
The rules that the start rule calls outside negative lookaheads and #recover but that can never match, such as a rule that ends in `_ |
Unreachable and Impossible are not counted in Rules.
A sample.Why tells what the generator knows about why no accepted input exercised a target. An attempt tried a
target if its search generated the target at some point; the counts are of the attempts that tried the target and gave
no accepted input that exercises it.
| Member | Meaning |
|---|---|
Bypassed |
The attempts that found an accepted input without the target: the search left every way through it that it tried |
Rejected |
The candidates that the parser rejected |
Failed |
The searches that ended without a candidate |
Exhausted |
The failed searches that used up their budget |
Cuts |
The rules whose checks and predicates cut the most ways in those attempts, at most three, each a sample.RuleCuts (see Statistics), in the order of Generator.Cuts() |
MinLen |
The length in bytes of the shortest input that exercises the target as far as the structure of the grammar tells, leaving out lookaheads, predicates and the order of choices: a lower bound |
No attempt means that no search took the target: the generator preferred other options, or the bounds kept it away,
as when MinLen is beyond WithMaxLen. Attempts with many cuts name the checks and predicates that stopped them, and
rejected candidates point at what the generator cannot evaluate, such as an earlier alternative of a choice that
matches the same text; attempts that only bypassed it, with cuts, point at the checks that ruled out the ways through
it. The counts are kept with and without WithCoverage.
The members have the JSON names rules, rulesCovered, alternatives, alternativesCovered, missedRules,
missedAlternatives, unreachable and impossible; the members of a missed rule rule, those of a missed
alternative rule, kind, index and expr, and in both the members of Why: bypassed, rejected, failed,
exhausted, cuts and minLen. An empty list is omitted.
Coverage.String() is rules a/b (p%), alternatives a/b (p%), where a percentage is rounded to a whole number and is
100% when the total is 0. Coverage.Report() is that line followed by a line for each missed rule (missed rule: name), for each missed alternative (missed followed by rule: kind index: expr), and for the unreachable rules
(unreachable: names) and the impossible rules (never match: names) when there are any. A missed line ends with
Why.String() in parentheses: not tried, or tried in n attempts: followed by the counts that are not zero among
b accepted without it, r rejected by the parser, e out of budget and w without a way to finish (the failed
searches within their budget), and by ; most cuts in rule (c by checks, p by predicates) for the rules of Cuts;
then ; shortest input n bytes. An inline action is shown as written in the grammar and not as the anonymous rule
that implements it.
Statistics
Generator.Stats() returns the counts of the work done so far.
| Member | Counts |
|---|---|
Candidates |
Candidates that the generator passed to the parser |
Rejected |
Candidates that the parser rejected |
Failed |
Searches that ended without a candidate |
Exhausted |
The failed searches that used up their budget; the others tried every way to finish that they knew |
Duplicates |
Inputs that Generate and GenerateInvalid found again and skipped |
CheckCuts |
Ways that the search abandoned because a lookahead, the order of a choice or $$ showed that the parser would not match them |
PredicateCuts |
Ways that the search abandoned because a predicate would certainly fail |
Generator.Cuts() splits the cuts by rule: a sample.RuleCuts has the Rule, the number of Checks and the number of
Predicates (JSON names rule, checks and predicates), for each rule that has any, the rules with the most cuts
first and rules with the same number in the order of their names. A check belongs to the rule whose body holds the lookahead, choice, optional expression,
repetition or $$ that installed it, even when the text that decides it comes from another rule.
Seeding Fuzz Tests
sample.Seed(f, p, n, opts...) adds up to n distinct accepted inputs of p to the seed corpus of the fuzz test f,
each as a single string argument, and returns them; the fuzz target therefore takes one string. f is any value with
the methods Helper, Add and Fatalf of *testing.F, as sample.F says. Seed fails the test through Fatalf if
it cannot generate any input, or if p does not accept a generated input when it parses it again.
The Command
sxir sample -g g.sxir prints distinct accepted inputs: -s selects the start rule, -n the number (10; a negative number is
an error), -seed, -max-depth, -max-repeat, -max-len and -budget the options with the same names, -coverage
the coverage and -invalid near-miss inputs instead. The grammar is SyntaxIR source or grammar JSON; a compiled
grammar is an error, as is an unknown value of -f.
- With
-f lines, the default, each input is printed as a Go-quoted string on a line, so that an input with line breaks stays on one line, andstrconv.Unquotereads it back. With-coverage, the report ofCoverage.Report()goes to the standard error. - With
-f json, the command prints one document with the membersstart,seed,inputs(orinvalid, a list of objects withinput,base,mutationanderror, with-invalid),coverage(with-coverage, the JSON form ofCoverage) andstats, which has the members ofStatsin camel case and the list ofGenerator.Cuts()as the member ruleCuts, with the membersrule,checksandpredicates. Empty lists are omitted. - If the generator finds fewer inputs than
-nbut at least one, the command prints them, sayssxir sample: found only N distinct inputson the standard error and succeeds. If it finds none it fails with the error of the generator; with-coveragethe report, and with-coverageand-f jsonthe document, are still printed.
Validation and Errors
| Condition | Result |
|---|---|
sample.New for a parser without the grammar, with an undefined start rule, or whose start rule can never match |
An error |
| No accepted input within the attempts | An error that matches sample.ErrNoInput |
| Accepted inputs but no mutation that the parser rejects | sample.ErrNoInvalid |
Seed that cannot generate an input |
Fatalf of the test |
| An option out of range | The nearest value that is in range |
Compatibility and Support
The generator needs the grammar, so it works for a parser built from grammar source or grammar JSON and not for one
loaded from a compiled grammar. It is part of the Go API and the sxir command and not of generated parsers.
Conformance
The tests of the sample package establish that every generated input parses, that the same seed gives the same inputs,
the options and their limits, the coverage counts on grammars with known coverage, the explanations of missed targets,
and the predicates and the Operators Rules that the generator has to evaluate. The tests of the command establish its output.