Package pego/sample

import "github.com/ornew/pego/sample"

const (
	DefaultMaxDepth  = 5
	DefaultMaxRepeat = 3
	DefaultMaxLen    = 512
	DefaultAttempts  = 100
	DefaultBudget    = 20000
)

var ErrNoInput = errors.New("sample: no input found that the parser accepts")

var ErrNoInvalid = errors.New("sample: no mutation found that the parser rejects")

#func Generate source

func Generate(p *pego.Parser, n int, opts ...Option) ([]string, error)

Generate returns up to n distinct inputs that p accepts (see Generator.Generate).

#func Seed source

func Seed(f F, p *pego.Parser, n int, opts ...Option) []string

Seed adds up to n distinct inputs that p accepts to the seed corpus of the fuzz test f, each as a single string argument, and returns them; the fuzz target must therefore take one string. It verifies again that p accepts every input, and fails the test if it cannot generate any.

func FuzzParse(f *testing.F) {
	p := ... // the parser under test
	sample.Seed(f, p, 50)
	f.Fuzz(func(t *testing.T, in string) {
		p.Parse(in) // must not panic
	})
}

#type Alternative source

type Alternative struct {
	Rule string `json:"rule"`
	// Kind is "choice", "operand" or "operator".
	Kind string `json:"kind"`
	// Index is the position of the alternative in its choice, or of the operand or operator in the
	// Operators Rule expression (operators are counted across all levels).
	Index int `json:"index"`
	// Expr is the alternative in PEGO syntax.
	Expr string `json:"expr"`
}

Alternative identifies an alternative of an ordered choice, or an operand or operator of a OperatorsRule expression.

#func (Alternative) String source

func (a Alternative) String() string

#type Coverage source

type Coverage struct {
	// Rules counts the rules that the start rule can reach and that can match; RulesCovered those that
	// an accepted input exercised.
	Rules        int `json:"rules"`
	RulesCovered int `json:"rulesCovered"`
	// Alternatives counts the alternatives of ordered choices and the operands and operators of OperatorsRule
	// expressions in those rules, leaving out those that can never match or that occur only inside an
	// expression that can never match, or in OperatorsRule tails that no reachable entry or prefix RHS permits.
	Alternatives        int `json:"alternatives"`
	AlternativesCovered int `json:"alternativesCovered"`
	// MissedRules and MissedAlternatives list what was not exercised.
	MissedRules        []string      `json:"missedRules,omitempty"`
	MissedAlternatives []Alternative `json:"missedAlternatives,omitempty"`
	// Unreachable lists the rules that generation cannot exercise from the start rule: rules that are
	// not called, or called only inside negative lookaheads (!keyword), the skip of #recover, or
	// expressions that can never match or blocked Operators Rule operator parts. Impossible lists the rules
	// that the start rule calls (outside negative lookaheads and #recover) but that can never match,
	// such as rules that end in _|_ to report an error. Neither is counted in Rules.
	Unreachable []string `json:"unreachable,omitempty"`
	Impossible  []string `json:"impossible,omitempty"`
}

Coverage reports which parts of the grammar the accepted inputs exercised.

Coverage is measured on the way the generator derived each accepted input. The parser takes the same way unless the generator could not evaluate a lookahead, a predicate or an earlier alternative of a choice (see the package documentation); counts are therefore close to, but not guaranteed to be, the parser's own coverage.

#func (Coverage) Report source

func (c Coverage) Report() string

Report describes the coverage in detail, one item per line.

#func (Coverage) String source

func (c Coverage) String() string

String summarizes the coverage on one line.

#type F source

type F interface {
	Helper()
	Add(args ...any)
	Fatalf(format string, args ...any)
}

F is the part of *testing.F that Seed uses. (Taking an interface keeps the testing package out of programs that import sample without seeding fuzz tests.)

#type Generator source

type Generator struct {
	// contains filtered or unexported fields
}

Generator generates inputs for a parser. It is not safe for concurrent use.

#func New source

func New(p *pego.Parser, opts ...Option) (*Generator, error)

New returns a generator of inputs for p, starting at p's start rule. The parser must be compiled from the grammar source: a parser loaded from a compiled grammar has no grammar AST and cannot be sampled.

#func (*Generator) Coverage source

func (g *Generator) Coverage() Coverage

Coverage returns the coverage of the inputs accepted so far.

#func (*Generator) Cuts source

func (g *Generator) Cuts() []RuleCuts

Cuts returns the cuts of each rule so far, for the rules with any, the rules with the most cuts first (ties in rule name order).

#func (*Generator) Generate source

func (g *Generator) Generate(n int) ([]string, error)

Generate returns up to n distinct inputs that the parser accepts. It returns fewer if it cannot find more (a grammar may accept only a few inputs; it gives up after as many inputs in a row that it already returned as the attempts per input), and ErrNoInput if it finds none.

#func (*Generator) GenerateInvalid source

func (g *Generator) GenerateInvalid(n int) ([]Invalid, error)

GenerateInvalid returns up to n near-miss invalid inputs with distinct Input. It returns fewer if it cannot find more, and the error of Invalid (ErrNoInput or ErrNoInvalid) if it finds none.

#func (*Generator) Invalid source

func (g *Generator) Invalid() (Invalid, error)

Invalid returns a near-miss invalid input. It returns ErrNoInput if it finds no valid input to mutate, and ErrNoInvalid if no mutation of the valid inputs it found is rejected (a grammar such as .* accepts every input).

#func (*Generator) Next source

func (g *Generator) Next() (string, error)

Next returns an input that the parser accepts. Inputs may repeat. It returns ErrNoInput if no candidate was accepted within the attempts.

#func (*Generator) Stats source

func (g *Generator) Stats() Stats

Stats returns the counts of the work done so far.

#type Invalid source

type Invalid struct {
	Input    string // the mutated input
	Base     string // the valid input it was made from
	Mutation string // the mutation, such as `delete "]" at 12` (positions are byte offsets in Base)
	Err      error  // the error the parser returned for Input
}

Invalid is a near-miss invalid input: an input that the parser accepts, changed by one mutation so that the parser rejects it. It exercises the error paths of the parser and of the code around it.

#type Option source

type Option func(*config)

Option configures a Generator.

#func WithAttempts source

func WithAttempts(n int) Option

WithAttempts sets how many candidates the generator tries for one input before giving up (default DefaultAttempts).

#func WithBudget source

func WithBudget(steps int) Option

WithBudget sets the number of steps one attempt may take before it gives up (default DefaultBudget). A step is a parsing expression generated or a OperatorsRule scope inspected; checks have a budget of their own in proportion. Past WithMaxDepth and WithMaxLen, the generator only prefers the shortest way to finish. The budget and the nesting/iteration limits (see WithMaxDepth and WithMaxRepeat) bound an attempt. Inputs that need many steps, such as an expression repeated 25,000 times, need a larger budget; the budget also bounds the search stack, which grows with the steps of an attempt.

#func WithCoverage source

func WithCoverage() Option

WithCoverage biases the generator toward rules, alternatives of ordered choices, and Operators Rule operands and operators that no accepted input has exercised yet.

#func WithMaxDepth source

func WithMaxDepth(d int) Option

WithMaxDepth bounds recursion: once rule calls are nested d deep inside calls of the same rules, the generator prefers the shortest way to finish (default DefaultMaxDepth). Calls of rules that are not already active do not count. The bound is soft: when the input requires deeper nesting (a predicate that counts it, for example), the search goes deeper, but never beyond d + 8: raise d for inputs that must nest deeper.

#func WithMaxLen source

func WithMaxLen(n int) Option

WithMaxLen sets a soft limit on the length of an input in bytes (default DefaultMaxLen): once the input is that long, the generator prefers the alternatives with the shortest text to finish it.

#func WithMaxRepeat source

func WithMaxRepeat(n int) Option

WithMaxRepeat sets how many iterations an unbounded repetition aims for beyond its minimum, at most (default DefaultMaxRepeat). It also bounds the operators of an Operators Rule expression chain. The search may take more iterations when the input requires them (a predicate after the repetition wants a longer match), but never more than 8 × n + 4 beyond the minimum (28 by default): raise n for inputs with longer repetitions.

#func WithSeed source

func WithSeed(seed uint64) Option

WithSeed sets the seed of the random decisions (default 0). The same parser, options and seed give the same inputs with the same version of this package (see the package documentation).

#type RuleCuts source

type RuleCuts struct {
	Rule       string
	Checks     int
	Predicates int
}

RuleCuts counts the cuts of the checks and predicates in one rule's body (see Stats.CheckCuts and Generator.Cuts). A check belongs to the rule whose body holds the lookahead, choice, optional, repetition or $$ that installed it.

#type Stats source

type Stats struct {
	Candidates int // candidates passed to the parser
	Rejected   int // candidates that the parser rejected
	Failed     int // searches that ended without a candidate
	// Exhausted counts the failed searches that used up their budget (WithBudget). The others gave up
	// on every way to finish the input that they tried: the grammar may accept nothing within the
	// bounds, or the checks below may rule out the ways the search takes.
	Exhausted int
	// Duplicates counts the inputs that Generate and GenerateInvalid found again and skipped.
	Duplicates int
	// CheckCuts counts the ways that the search abandoned because a lookahead, the order of a choice
	// or $$ showed that the parser would not match them; PredicateCuts those abandoned because a
	// predicate would certainly fail. Many cuts in a failing search point at the checks that block it.
	CheckCuts     int
	PredicateCuts int
}

Stats counts the work of a Generator.