Struct Grammar 

pub struct Grammar { /* private fields */ }

A state machine that produces Arbitrary matching expressions or byte sequences from Unstructured.

Implementation

Construction

Grammar is constructed using from_str of a string that specifies the syntax of expressions:

• A peg parser converts the string into an “intermediary representation” AST (in ir.rs).
• The IR is validated for duplicate and conflicting rule definitions
• The IR is converted to a state machine in which regex is parsed and rule definitions are indexed.

Expression Generation

Unstructured is used to generate arbitrary choices and loops to traverse the state machine. When a “leaf” state is reached, e.g. a pre-defined rule, regex, or string literal, Unstructured is used to write arbitrary data (except for string literals) to an output buffer.

Implementations

impl Grammar

pub fn expression<V: Visitor>( &self, u: &mut Unstructured<'_>, max_depth: Option<usize>, ) -> Result<V>

Returns a resulting Visitor after an arbitirary state machine traversal.

The state machine traversal starts at the first rule in the grammar.

Parameters

max_depth is nesting limit of rule referencing during the traversal. For example, the below grammar generates numbers less than or equal to the max_depth parameter.

one   : "1" | two ;
two   : "2" | three ;
three : "3" ;

pub fn how_many(&self, max_depth: Option<usize>) -> Option<u64>

Returns the number of possible state machine traversals for this state machine or None if the result exceeds u64::MAX.

In other words, grammar.how_many(depth) is the number of unique values possible from grammar.expression::<u64>(u, depth) (barring hash collisions).

Parameters

max_depth is the maximum nested references that the traversal is allowed. A max_depth of 0 will always return 0.

Usage

Provides a rough possible number of equivalence classes of the grammar, which is useful for estimating overall coverage as the fuzzer discovers more classes over time. Equivalence classes summarize the space of all inputs based on high level strcuture, not the actual data of terminal nodes. A large how_many means achieving full coverage may challenge your time constraints. A small how_many signals that you could increase the complexity or granularity of your grammar.

Limitations

1. No traversals are counted inside of Regex and pre-defined (e.g. String) rules i.e. are counted as 1 possible traversal even though many regex expressions or Strings are possible.

2. The result is not aware of duplicate outputs, e.g.

expr : "foo" | "foo" ;

counts as 2 traversals, even though every output is “foo”.

Trait Implementations

impl Debug for Grammar

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Display for Grammar

Pretty prints the state machine.

It’s helpful to check if the compiled state machine matches what is expected from the the un-parsed grammar (the printed rules are more verbose and order of operations is clearer)

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl FromStr for Grammar

type Err = Error

The associated error which can be returned from parsing.

fn from_str(s: &str) -> Result<Self, Self::Err>

Parses a string s to return a value of this type.

impl TryFrom<Vec<(String, Expr)>> for Grammar

type Error = Error

The type returned in the event of a conversion error.

fn try_from(value: Vec<(String, Expr)>) -> Result<Self, Self::Error>

Performs the conversion.