pub struct Grammar { /* private fields */ }Expand description
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§
Source§impl Grammar
impl Grammar
Sourcepub fn expression<V: Visitor>(
&self,
u: &mut Unstructured<'_>,
max_depth: Option<usize>,
) -> Result<V>
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" ;Sourcepub fn how_many(&self, max_depth: Option<usize>) -> Option<u64>
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.
§Parameters
max_depth is the maximum nested references that the traversal is allowed.
A max_depth of 0 will always return 0.
grammar.how_many(depth) is the number of unique values possible from
grammar.expression::<u64>(u, depth), barring hash collisions.
§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.
§Limitations
-
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.
-
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§
Source§impl Display for Grammar
Pretty prints the state machine.
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)