Documentation
¶
Index ¶
- Variables
- func GenerateGoParser(g *Grammar, root, pkg string) ([]byte, error)
- func GenerateGoParserFromABNF(abnfSource []byte, root, pkg string, opts ...ABNFOption) ([]byte, error)
- func SemvalABNF(g *Grammar) error
- func WithRepMax(repMax int) repMaxOption
- func WithThreshold(threshold int) thresholdOption
- type ABNFOption
- type ASTGenOption
- type ASTGenerator
- type Alternation
- type BSRForest
- type Concatenation
- type CoverageMode
- type Depgraph
- type ElemCharVal
- type ElemGroup
- type ElemItf
- type ElemNumVal
- type ElemOption
- type ElemProseVal
- type ElemRulename
- type ErrCoreRuleModify
- type ErrCyclicRule
- type ErrDependencyNotFound
- type ErrDuplicatedRule
- type ErrForestTooLarge
- type ErrGrammarTooLarge
- type ErrMaxNodesExceeded
- type ErrMultipleSolutionsFound
- type ErrRegexTooLarge
- type ErrRuleNotFound
- type ErrSemanticRepetition
- type ErrTooLargeNumeral
- type Forest
- type ForestOption
- type GenOption
- type GenerateOption
- type Generator
- func (g *Generator) ExpectedNext(prefix []byte) (next []byte, accepts bool, ok bool)
- func (g *Generator) Generate(tape []byte) []byte
- func (g *Generator) GenerateRand(r *rand.Rand) []byte
- func (g *Generator) NearMiss(tape []byte) (production []byte, label string, ok bool)
- func (g *Generator) NearMissRand(r *rand.Rand) (production []byte, label string, ok bool)
- type Grammar
- func (g *Grammar) DependencyGraph() Depgraph
- func (g *Grammar) Generate(seed int64, rulename string, opts ...GenerateOption) ([]byte, error)
- func (g *Grammar) IsDAG() bool
- func (g *Grammar) IsValid(rulename string, input []byte) (bool, error)
- func (g *Grammar) PrettyPrint() string
- func (g *Grammar) Regex(rulename string, opts ...RegexOption) (string, error)
- func (g *Grammar) RuleContainsCycle(rulename string) (bool, error)
- func (g *Grammar) String() string
- func (g *Grammar) TransitionGraph(rulename string, opts ...TGOption) (*TransitionGraph, error)
- type Node
- type ParseError
- type ParseTree
- type ReaderOption
- type RegexOption
- type Repetition
- type Rule
- type Status
- type TGOption
- type TransitionGraph
- type TransitionGraphReader
Constants ¶
This section is empty.
Variables ¶
var ( // ErrNoSolutionFound is an error returned when parsing an ABNF // grammar and no solution has been found. // // On the ABNF parsing path it is wrapped by a [*ParseError] carrying the // position at which parsing got stuck; errors.Is(err, ErrNoSolutionFound) // keeps matching. ErrNoSolutionFound = errors.New("no solution found, input ABNF grammar may be invalid") // ErrHandlingProseVal is an error returned when an operation tried // to produce something on a prose-val, but it can't be handled properly. ErrHandlingProseVal = errors.New("can't handle prose-val descriptions") // ErrProseValInTransitionGraph is returned when building a transition graph // from a grammar that contains a prose-val, which has no defined expansion. ErrProseValInTransitionGraph = errors.New("prose value is not supported in transition graphs") // ErrRepetitionThreshold is returned when expanding a repetition whose bound // exceeds the threshold set with WithRepetitionThreshold. ErrRepetitionThreshold = errors.New("repetition threshold reached") // ErrRepetitionMinNotOne is returned when a mandatory (max == 1) repetition // has a minimum other than 1. ErrRepetitionMinNotOne = errors.New("repetition minimum must be 1 when maximum is 1") // ErrRepetitionMinGtMax is returned when a repetition has a minimum greater // than its maximum. ErrRepetitionMinGtMax = errors.New("repetition minimum is greater than maximum") )
var ABNF = &Grammar{ Rulemap: map[string]*Rule{ abnfRulelist.Name: abnfRulelist, abnfRule.Name: abnfRule, abnfRulename.Name: abnfRulename, abnfDefinedAs.Name: abnfDefinedAs, abnfElements.Name: abnfElements, abnfCWsp.Name: abnfCWsp, abnfCNl.Name: abnfCNl, abnfComment.Name: abnfComment, abnfAlternation.Name: abnfAlternation, abnfConcatenation.Name: abnfConcatenation, abnfRepetition.Name: abnfRepetition, abnfRepeat.Name: abnfRepeat, abnfElement.Name: abnfElement, abnfGroup.Name: abnfGroup, abnfOption.Name: abnfOption, abnfCharVal.Name: abnfCharVal, abnfCaseInsensitiveString.Name: abnfCaseInsensitiveString, abnfCaseSensitiveString.Name: abnfCaseSensitiveString, abnfQuotedString.Name: abnfQuotedString, abnfNumVal.Name: abnfNumVal, abnfBinVal.Name: abnfBinVal, abnfDecVal.Name: abnfDecVal, abnfHexVal.Name: abnfHexVal, abnfProseVal.Name: abnfProseVal, }, }
ABNF is the manually parsed+evaluated+validated ABNF grammar.
Functions ¶
func GenerateGoParser ¶ added in v0.5.0
GenerateGoParser emits a standalone Go source file containing a parser SPECIALISED to grammar g rooted at root. Unlike a table-driven interpreter, the grammar is compiled into control flow:
- the parse loop is a jump-table switch over slot IDs; each case is the straight-line code for that one slot (its symbol, its successor, its completion), so there is no per-step table lookup and no symbol-kind dispatch at runtime;
- terminals are inlined as byte comparisons / rune decodes against baked literals (no ElemItf, no closure table);
- nonterminal calls, completions, and the {min,max} repetition gating are baked as constants at each site;
- only the genuinely grammar-independent machinery (GSS, descriptor worklist, BSR set) remains as fixed runtime, plus a compact metadata table used solely by the reconstruction queries (NumTrees/Ambiguous/Tree), which inherently need grammar structure.
The output depends only on the standard library, is panic-free (input decoded via utf8, no manual indexing) and bounded (MaxElements aborts pathological inputs with ErrTooLarge). It is validated against ParseBSR via the differential harness. pkg is the package name for the emitted file.
func GenerateGoParserFromABNF ¶ added in v0.5.0
func GenerateGoParserFromABNF(abnfSource []byte, root, pkg string, opts ...ABNFOption) ([]byte, error)
GenerateGoParserFromABNF is a convenience wrapper that parses ABNF grammar source and generates a specialised parser for it in one step. root is the rule the generated parser starts from; pkg is the package name of the emitted file. It is the natural entry point for a code-generation command (e.g. driven by `go generate`).
func SemvalABNF ¶
SemvalABNF proceed to semantic validations of an ABNF grammar. It currently support the following checks: - for all rules, its dependencies (rules) exist - for repetition, min <= max - for num-val, that the value fits in 7-bits (US-ASCII encoded) To update this list, please open an issue.
func WithRepMax ¶
func WithRepMax(repMax int) repMaxOption
WithRepMax defines the maximum repetition to stop generating at.
func WithThreshold ¶
func WithThreshold(threshold int) thresholdOption
WithThreshold defines the length threshold to stop generating at.
Types ¶
type ABNFOption ¶ added in v0.3.0
type ABNFOption interface {
// contains filtered or unexported methods
}
ABNFOption defines the interface for parsing ABNF functional options.
func WithRedefineCoreRules ¶ added in v0.3.0
func WithRedefineCoreRules(redefine bool) ABNFOption
WithRedefineCoreRules returns a functional option to enable redefining a core rule. Default is false.
WARNING: use with caution, as we left to the user the responsibility to ensure the redefinition keeps the ABNF grammar coherent (i.e. there is an isomorphism between the core rule and the redefinition, not especially the same textual representation).
func WithValidation ¶
func WithValidation(validate bool) ABNFOption
WithValidation returns a functional option to proceed to validation or not. Default is true.
type ASTGenOption ¶ added in v0.5.0
type ASTGenOption interface {
// contains filtered or unexported methods
}
ASTGenOption configures an ASTGenerator.
func WithMaxDepth ¶ added in v0.5.0
func WithMaxDepth(n int) ASTGenOption
WithMaxDepth bounds rule-expansion (recursion) depth; past it the generator steers toward terminating expansions. Defaults to 32.
func WithMaxLen ¶ added in v0.5.0
func WithMaxLen(n int) ASTGenOption
WithMaxLen bounds the output length; past it the generator steers toward terminating expansions. Defaults to 4096. (Mandatory repetitions are always emitted, so the bound is soft -- a single huge fixed repetition can exceed it.)
func WithMaxRepeat ¶ added in v0.5.0
func WithMaxRepeat(n int) ASTGenOption
WithMaxRepeat caps how far an unbounded ("*" / "1*") repetition is unrolled. Defaults to 16.
type ASTGenerator ¶ added in v0.5.0
type ASTGenerator struct {
// contains filtered or unexported fields
}
ASTGenerator generates strings admitted by a (possibly recursive) grammar rule, directly from the AST.
func NewASTGenerator ¶ added in v0.5.0
func NewASTGenerator(g *Grammar, rule string, opts ...ASTGenOption) (*ASTGenerator, error)
NewASTGenerator prepares a generator for rule. It errors if the rule is undefined, or if any rule reachable from it is undefined or non-productive (cannot derive any finite string), since neither can be generated. Unlike the transition-graph generator, recursive rules are fully supported.
func (*ASTGenerator) Generate ¶ added in v0.5.0
func (ag *ASTGenerator) Generate(tape []byte) []byte
Generate maps the tape to a production the grammar admits. Total and deterministic: any tape (including nil) yields a valid production; an exhausted tape biases toward the shortest one.
func (*ASTGenerator) GenerateRand ¶ added in v0.5.0
func (ag *ASTGenerator) GenerateRand(r *rand.Rand) []byte
GenerateRand draws a production using r as the entropy source.
type Alternation ¶
type Alternation struct {
// Concatenations contains the variants that validate the upper
// object (i.e. rule, group or option).
Concatenations []Concatenation
}
Alternation represents an ABNF alternation object.
This is exposed for custom evaluation purposes, please don't use it else.
func (Alternation) String ¶
func (alt Alternation) String() string
type BSRForest ¶ added in v0.5.0
type BSRForest struct {
// contains filtered or unexported fields
}
BSRForest is the BSR analogue of Forest: a set of binary subtree elements plus an index for reconstruction. Valid/NumTrees/Ambiguous/Tree mirror Forest.
func ParseBSR ¶ added in v0.5.0
func ParseBSR(input []byte, grammar *Grammar, rootRulename string, opts ...ForestOption) (*BSRForest, error)
ParseBSR parses input under rootRulename using the BSR engine. It accepts the same options as ParseForest (WithMaxForestNodes bounds the BSR set size).
func (*BSRForest) Ambiguous ¶ added in v0.5.0
Ambiguous reports whether the input has more than one distinct parse tree.
func (*BSRForest) Nodes ¶ added in v0.5.0
Nodes returns the number of BSR elements (the representation's size).
func (*BSRForest) NumTrees ¶ added in v0.5.0
NumTrees returns the number of distinct parse trees represented, or -1 for infinitely many (a cycle, i.e. an infinitely-ambiguous grammar). It mirrors Forest.NumTrees but counts over BSR extents instead of SPPF nodes.
type Concatenation ¶
type Concatenation struct {
// Repetitions contains the following repetitions, order matter.
Repetitions []Repetition
}
Concatenation represents an ABNF concatenation object.
This is exposed for custom evaluation purposes, please don't use it else.
func (Concatenation) String ¶
func (cnt Concatenation) String() string
type CoverageMode ¶ added in v0.5.0
type CoverageMode int
CoverageMode selects what set of strings a TransitionGraphReader produces.
const ( // CoverageAllTrails (mode A, the default) emits every entrypoint->endpoint // trail (a walk using each directed edge at most once) and, for each trail, // every combination of its nodes' terminal variations. It is finite and // terminating for any graph, but on dense graphs or wide range/charval nodes // the number of trail x variation combinations can be very large. CoverageAllTrails CoverageMode = iota // CoverageCompact (mode B) emits a small set of strings that still covers // every reachable vertex, every edge, and every terminal value (each charval // casing, each numval range value) at least once, then stops. Its size is // bounded by roughly (#edges + #vertices + sum of per-node variations), so it // stays small even for grammars where CoverageAllTrails explodes. CoverageCompact )
type Depgraph ¶
type Depgraph map[string]*node
Depgraph contains for each rule the rules it depends on. Notice it does not differentiate between a mandatory dependency or an avoidable one.
type ElemCharVal ¶
type ElemCharVal struct {
// Sensitive is by default false, support clarrified by RFC 7405 hence
// only works on a-z and A-Z.
Sensitive bool
Values []rune
}
ElemCharVal represents an ABNF char-val object.
This is exposed for custom evaluation purposes, please don't use it else.
func (ElemCharVal) String ¶
func (ecvl ElemCharVal) String() string
type ElemGroup ¶
type ElemGroup struct {
Alternation Alternation
}
ElemGroup represents an ABNF group object. It will be straightly passed through with its underlying alternation.
This is exposed for custom evaluation purposes, please don't use it else.
type ElemItf ¶
ElemItf defines the interface of all the element alternations: - ElemRulename - ElemGroup - ElemOption - ElemProseVal - ElemNumVal - ElemCharVal
This is exposed for custom evaluation purposes, please don't use it else.
type ElemNumVal ¶
type ElemNumVal struct {
Base string
// Status could be:
// - `statSeries`: `elems` contains all the expected
// values in the order of the grammar defined them ;
// - `statRange`: `elems` contains the start and end
// bounds (so no more than two).
Status Status
Elems []string
}
ElemNumVal represents an ABNF num-val object.
This is exposed for custom evaluation purposes, please don't use it else.
func (ElemNumVal) String ¶
func (envl ElemNumVal) String() string
type ElemOption ¶
type ElemOption struct {
Alternation Alternation
}
ElemOption represents an ABNF option object. It will be straightly converted to a 0*1 repetition.
This is exposed for custom evaluation purposes, please don't use it else.
func (ElemOption) String ¶
func (eopt ElemOption) String() string
type ElemProseVal ¶
type ElemProseVal struct {
// contains filtered or unexported fields
}
ElemProseVal represents an ABNF prose-val object.
This is exposed for custom evaluation purposes, please don't use it else.
func (ElemProseVal) String ¶
func (epvl ElemProseVal) String() string
type ElemRulename ¶
type ElemRulename struct {
// Name is the unique rule name.
// Notice it is case-insensitive according to RFC 5234 Section 2.1.
Name string
}
ElemRulename represents an ABNF rulename object.
This is exposed for custom evaluation purposes, please don't use it else.
func (ElemRulename) String ¶
func (erln ElemRulename) String() string
type ErrCoreRuleModify ¶
type ErrCoreRuleModify struct {
CoreRulename string
}
ErrCoreRuleModify is an error returned when an incremental alternative for a core rule.
func (ErrCoreRuleModify) Error ¶
func (err ErrCoreRuleModify) Error() string
type ErrCyclicRule ¶
type ErrCyclicRule struct {
Rulename string
}
ErrCyclicRule is an error returned when can't work due to an unavoidable cyclic rule.
func (ErrCyclicRule) Error ¶
func (err ErrCyclicRule) Error() string
type ErrDependencyNotFound ¶
type ErrDependencyNotFound struct {
Rulename string
}
ErrDependencyNotFound is an error returned during ABNF grammar semantic vaildation, if a rule depends on an unexisting rule.
func (ErrDependencyNotFound) Error ¶
func (err ErrDependencyNotFound) Error() string
type ErrDuplicatedRule ¶
type ErrDuplicatedRule struct {
Rulename string
}
ErrDuplicatedRule is an error returned when the rule already exist as part of the grammar.
func (ErrDuplicatedRule) Error ¶
func (err ErrDuplicatedRule) Error() string
type ErrForestTooLarge ¶ added in v0.5.0
type ErrForestTooLarge struct{ Max int }
ErrForestTooLarge is returned by ParseForest when the SPPF exceeds the configured WithMaxForestNodes budget.
func (*ErrForestTooLarge) Error ¶ added in v0.5.0
func (e *ErrForestTooLarge) Error() string
type ErrGrammarTooLarge ¶ added in v0.5.0
type ErrGrammarTooLarge struct{ Max int }
ErrGrammarTooLarge is returned by ParseForest when lowering the grammar would exceed the WithMaxSlots budget, typically because of an absurd repetition bound (e.g. a = 9999999999"x").
func (*ErrGrammarTooLarge) Error ¶ added in v0.5.0
func (e *ErrGrammarTooLarge) Error() string
type ErrMaxNodesExceeded ¶ added in v0.5.0
type ErrMaxNodesExceeded struct {
Max int
}
ErrMaxNodesExceeded is returned by TransitionGraph when construction would allocate more nodes than the budget set with WithMaxNodes.
func (ErrMaxNodesExceeded) Error ¶ added in v0.5.0
func (err ErrMaxNodesExceeded) Error() string
type ErrMultipleSolutionsFound ¶
type ErrMultipleSolutionsFound struct{}
ErrMultipleSolutionsFound is an error returned when a parser found multiple solutions when none or one were expected.
func (ErrMultipleSolutionsFound) Error ¶
func (err ErrMultipleSolutionsFound) Error() string
type ErrRegexTooLarge ¶ added in v0.5.0
type ErrRegexTooLarge struct{ Max int }
ErrRegexTooLarge is returned by Regex when the output would exceed the budget set with WithMaxRegexLen.
func (*ErrRegexTooLarge) Error ¶ added in v0.5.0
func (e *ErrRegexTooLarge) Error() string
type ErrRuleNotFound ¶
type ErrRuleNotFound struct {
Rulename string
}
ErrRuleNotFound is an error returned when the rule was not found as part of the grammar.
func (ErrRuleNotFound) Error ¶
func (err ErrRuleNotFound) Error() string
type ErrSemanticRepetition ¶
type ErrSemanticRepetition struct {
Repetition Repetition
}
ErrSemanticRepetition is an error returned during ABNF grammar semantic validation, if a repetition has min < max.
func (ErrSemanticRepetition) Error ¶
func (err ErrSemanticRepetition) Error() string
type ErrTooLargeNumeral ¶
type ErrTooLargeNumeral struct {
Base, Value string
}
ErrTooLargeNumeral is an error returned when the numeral value provided to parse cannot be handled as a 7-bit US-ASCII valid value.
func (ErrTooLargeNumeral) Error ¶
func (err ErrTooLargeNumeral) Error() string
type Forest ¶ added in v0.5.0
type Forest struct {
// contains filtered or unexported fields
}
Forest is a shared packed parse forest produced by ParseForest.
func Parse ¶
Parse parses input against grammar starting at rootRulename using the GLL engine, returning the shared packed parse forest. Unlike the previous backtracking parser it accepts ANY grammar -- left, right and mutual recursion and ambiguity included -- in worst-case cubic time, so it never stack-overflows on left recursion nor blows up exponentially. Inspect the result with the Forest methods (Valid, Ambiguous, NumTrees, Tree).
func ParseForest ¶ added in v0.5.0
func ParseForest(input []byte, grammar *Grammar, rootRulename string, opts ...ForestOption) (*Forest, error)
ParseForest parses input with grammar starting at rootRulename using GLL, returning the shared packed parse forest. It runs in worst-case O(n^3) time and space for ANY grammar -- left/right/mutual recursion and ambiguity included -- so it is safe on untrusted or malformed grammars.
func (*Forest) Ambiguous ¶ added in v0.5.0
Ambiguous reports whether the input has more than one distinct parse tree.
func (*Forest) Nodes ¶ added in v0.5.0
Nodes returns the number of forest nodes reachable from the root.
func (*Forest) NumTrees ¶ added in v0.5.0
NumTrees returns the number of distinct parse trees the forest represents. A result of -1 means infinitely many (a cycle in the forest, i.e. an infinitely-ambiguous grammar such as A = A / "x").
func (*Forest) ParseError ¶ added in v0.5.0
func (f *Forest) ParseError() *ParseError
ParseError returns the furthest-failure diagnostic for an invalid forest: where parsing got stuck and which terminals were expected there. It returns nil when the forest is valid. The returned error unwraps to ErrNoSolutionFound.
type ForestOption ¶ added in v0.5.0
type ForestOption func(*forestConfig)
ForestOption configures ParseForest.
func WithMaxForestNodes ¶ added in v0.5.0
func WithMaxForestNodes(n int) ForestOption
WithMaxForestNodes bounds the number of SPPF nodes the forest may allocate. Because a complete SPPF is worst-case cubic in the input length, this caps the time and memory ParseForest can spend on adversarial input. 0 means unbounded.
func WithMaxSlots ¶ added in v0.5.0
func WithMaxSlots(n int) ForestOption
WithMaxSlots bounds the number of nonterminals produced while lowering the grammar. A finite repetition m*n lowers to ~n nonterminals, so this caps the cost of an adversarial grammar such as a = 9999999999"x". 0 means unbounded; the default is 65536.
type GenOption ¶ added in v0.5.0
type GenOption interface {
// contains filtered or unexported methods
}
GenOption configures a Generator.
func WithMaxLength ¶ added in v0.5.0
WithMaxLength bounds the number of bytes a generated production may contain. Once reached the walk steers to the nearest endpoint. Defaults to 4096.
func WithMaxReps ¶ added in v0.5.0
WithMaxReps bounds how many times a single edge may be traversed, which caps how far repetitions ("*" / "1*" / "n*m") are unrolled. Defaults to 32.
func WithMaxSteps ¶ added in v0.5.0
WithMaxSteps is a hard backstop on the total number of walk steps, defending against pathological graphs. Defaults to 100000.
func WithStableAddressing ¶ added in v0.5.0
func WithStableAddressing() GenOption
WithStableAddressing makes Generate address the tape by decision number (fixed-width slots) instead of a moving cursor. This improves locality for a coverage-guided engine -- a one-byte tape edit perturbs a single decision rather than reframing every decision downstream of it -- at the cost of consuming the tape less densely. Recommended for use under testing.F.
type GenerateOption ¶
type GenerateOption interface {
// contains filtered or unexported methods
}
GenerateOption is an option for the *Grammar.Generate method.
type Generator ¶ added in v0.5.0
type Generator struct {
// contains filtered or unexported fields
}
Generator produces strings admitted by a transition graph.
func NewGenerator ¶ added in v0.5.0
func NewGenerator(tg *TransitionGraph, opts ...GenOption) (*Generator, error)
NewGenerator prepares a Generator from a transition graph. The graph must be fully expanded -- build it with WithDeflateRules(true) when the target rule references other rules -- because an unexpanded rule node carries no bytes and could not be turned into a valid production. It returns an error naming the first such node otherwise. (Recursive rules cannot be expanded at all; in that case TransitionGraph itself returns ErrCyclicRule before reaching here.)
func (*Generator) ExpectedNext ¶ added in v0.5.0
ExpectedNext simulates the automaton over prefix and reports the octets that may legally follow it, whether prefix is itself a complete word, and whether the analysis succeeded (ok is false only when the graph uses a feature this analyzer declines to expand, e.g. an enormous multi-byte num-val range). When prefix is not a viable prefix of any word, next is empty and accepts is false.
func (*Generator) Generate ¶ added in v0.5.0
Generate maps the tape to a production the grammar admits. It is total: any tape (including nil) yields a valid production; an exhausted tape biases toward the shortest completion.
func (*Generator) GenerateRand ¶ added in v0.5.0
GenerateRand draws a production using r as the entropy source.
func (*Generator) NearMiss ¶ added in v0.5.0
NearMiss returns a string just outside the grammar together with a label describing how it violates the grammar, or ok=false if no minimal perturbation within the attempt budget produced a string the grammar rejects. It is deterministic in tape and total.
type Grammar ¶
Grammar represents an ABNF grammar as defined by RFC 5234. It is constituted of a set of rules with a unique name.
func EvaluateABNF ¶ added in v0.3.0
func EvaluateABNF(input []byte, f *Forest, opts ...ABNFOption) (*Grammar, error)
EvaluateABNF evaluates a parse forest -- produced by parsing an ABNF source against the ABNF meta-grammar -- into a ready-to-use *Grammar.
func ParseABNF ¶
func ParseABNF(input []byte, opts ...ABNFOption) (*Grammar, error)
ParseABNF is a helper facilitating the call to Parse using the pre-computed ABNF grammar and evaluated the resulting to produce a ready-to-use grammar.
func (*Grammar) DependencyGraph ¶
DependencyGraph creates a dependency graph for a whole grammar. It includes core rules only if necessary.
func (*Grammar) Generate ¶
Generate is an experimental feature that consumes a seed for a pseudo-random number generator, used to randomly travel through the grammar given a rulename to work on. With this, it provides reproducibility, usefull for fuzz crashers.
You can leverage its capacities (maximum repetitions, length threshold, etc.) with the functional options.
It is a good capability for testing and fuzzing parsers during testing, compliance, fuzzing or optimization.
func (*Grammar) IsDAG ¶
IsDag find Strongly Connected Components using Tarjan's algorithm and returns whether it contains cycle or not. Could be improved by Nuutila's or Pearce's algorithms, or replaced by Kosaraju's algorithm.
func (*Grammar) IsValid ¶
IsValid checks there exist at least a path that completly consumes input, hence is valid given this grammar and especially one of its rule.
func (*Grammar) PrettyPrint ¶
PrettyPrint returns a prettified string that represents the grammar.
func (*Grammar) Regex ¶
func (g *Grammar) Regex(rulename string, opts ...RegexOption) (string, error)
Regex builds a regular expression that recognises the given rulename.
The rule must not contain a cycle in its dependency graph: a regular expression (RE2, no subroutines) cannot express recursion.
Because RE2 has no subroutine/backreference, a rule referenced N times is inlined N times, so the output can grow exponentially with reference-nesting depth for diamond-shaped grammars. Pass WithMaxRegexLen to fail fast with *ErrRegexTooLarge instead of exhausting memory. The output is simplified (character classes merged, redundant groups and {1} quantifiers dropped) but is not guaranteed minimal.
func (*Grammar) RuleContainsCycle ¶
RuleContainsCycle returns whether the rule contains a cycle or not. It travels through the whole rule dependency graph, such that it checks if the rule is cyclic AND if one of its dependency is too.
func (*Grammar) String ¶
String returns the representation of the grammar that is valid according to the ABNF specifications/RFCs. This notably imply the use of CRLF instead of LF, and does not preserve the initial order nor pretty print it.
func (*Grammar) TransitionGraph ¶ added in v0.2.0
func (g *Grammar) TransitionGraph(rulename string, opts ...TGOption) (*TransitionGraph, error)
TransitionGraph builds a transition graph out of a grammar and the given rulename. TODO it is possible to build transition graph out of cylic rules iff it is not concatenated to another repetition (can't pipe O->I as there is no O). For instance, `a = "a" a` can exist.
type Node ¶ added in v0.2.0
Node of a TransitionGraph. Unically identifiate the node of the transition graph along with its underlying element and its next nodes.
type ParseError ¶ added in v0.5.0
type ParseError struct {
// Offset is the byte offset into the input of the furthest position the
// parser was able to reach before failing.
Offset int
// Line and Col are the 1-based line and column of Offset.
Line, Col int
// Expected lists the terminals the parser could have consumed at Offset, if
// that information was available. It may be empty.
Expected []string
// Found describes the input byte at Offset (e.g. `%x0A (LF)`), or "EOF" when
// Offset is at the end of input. It may be empty.
Found string
// Hint, when set, gives a plain-language diagnosis of a common mistake (e.g.
// bare LF line endings where ABNF requires CR LF).
Hint string
}
ParseError reports where parsing input against a grammar got stuck. It is returned (wrapped around ErrNoSolutionFound) when an input does not parse, to help locate the offending construct -- in particular when writing or debugging an ABNF grammar.
func (*ParseError) Error ¶ added in v0.5.0
func (e *ParseError) Error() string
func (*ParseError) Unwrap ¶ added in v0.5.0
func (e *ParseError) Unwrap() error
Unwrap reports ErrNoSolutionFound so that callers matching the historical sentinel with errors.Is keep working.
type ParseTree ¶ added in v0.5.0
ParseTree is a concrete syntax tree keyed by grammar rules: rule nodes carry the rule name, terminals are leaves with empty Rule.
type ReaderOption ¶ added in v0.5.0
type ReaderOption interface {
// contains filtered or unexported methods
}
ReaderOption configures a TransitionGraphReader.
func WithCoverageMode ¶ added in v0.5.0
func WithCoverageMode(mode CoverageMode) ReaderOption
WithCoverageMode selects the coverage strategy of the reader (CoverageAllTrails by default, or CoverageCompact for a bounded covering set).
type RegexOption ¶ added in v0.5.0
type RegexOption interface {
// contains filtered or unexported methods
}
RegexOption configures Regex.
func WithMaxRegexLen ¶ added in v0.5.0
func WithMaxRegexLen(n int) RegexOption
WithMaxRegexLen bounds the produced regex length in bytes. When the budget is exceeded, Regex returns *ErrRegexTooLarge. Zero (the default) is unbounded.
type Repetition ¶
Repetition represents an ABNF repetition object.
This is exposed for custom evaluation purposes, please don't use it else.
func (Repetition) String ¶
func (rep Repetition) String() string
type Rule ¶
type Rule struct {
// Name is the unique rule name.
// Notice it is case-insensitive according to RFC 5234 Section 2.1.
Name string
Alternation Alternation
}
Rule represents an ABNF rule, with its name and underlying alternation.
This is exposed for custom evaluation purposes, please don't use it else.
func GetRule ¶
GetRule returns the rule by the given rulename, whether it is a core rule or present in the grammar, or nil if not found. It validates the RFC 5234 Section 2.1 "rule names are case insensitive".
type Status ¶
type Status int
Status defines the type of a num-val, rather StatSeries or StatRange.
This is exposed for custom evaluation purposes, please don't use it else.
type TGOption ¶ added in v0.2.0
type TGOption interface {
// contains filtered or unexported methods
}
func WithDeflateCharVals ¶ added in v0.2.0
WithDeflateCharVals when passed to true, will replace a single node representing the char value to an exhaustive concatenation of all characters (lower and upper case) and the transitions between them.
func WithDeflateNumVals ¶ added in v0.2.0
WithDeflateNumVals when passed to true, will replace a single node representing the ranges or series of multiple numeric values to individual nodes. It generates a more complex but exhaustive transition graph.
func WithDeflateRules ¶ added in v0.2.0
WithDeflateRules when passed to true, will recursively build the transition graphs of the rules it uses (reuse them if possible) and concatenate the sub transition graphs. It generates a more complex but exhaustive transition graph.
func WithMaxNodes ¶ added in v0.5.0
WithMaxNodes bounds the total number of nodes the transition graph may allocate during construction. Unlike WithRepetitionThreshold, which only caps a single repetition, this bounds the *whole* graph and so also defends against the combinatorial blow-up of nested repetitions (e.g. 10( 10( 10("a") ) )) and of wide num-val ranges deflated with WithDeflateNumVals. When the bound would be exceeded, construction stops with *ErrMaxNodesExceeded before the nodes are allocated.
A value <= 0 (the default) means unbounded, preserving the previous behaviour. Set a positive bound when building transition graphs from untrusted grammars to keep the work within a controlled domain.
func WithRepetitionThreshold ¶ added in v0.2.0
WithRepetitionThreshold defines the threshold to block a large repetition to occur, elseway it may consum all memory to build the transition graph. For instance, a rule defined as follows may self-DoS go-abnf.
a = 9555("a")
WARNING it does not avoid such memory consumption on chained repetitions. For instance, the two following cases could produce large transition graphs without control with this functional option.
a = 10( 10( 10("a") ) )
a = 10 ( 10*"a" ( 10"a" 9"a" 8"a" ) / ( *10"a" *10"a" *10"a" ) ) 10"a"
Defaults to 256.
type TransitionGraph ¶ added in v0.2.0
type TransitionGraph struct {
Entrypoints []*Node
Endpoints []*Node
// contains filtered or unexported fields
}
TransitionGraph represent a grammar transition graph. It contains the list of entrypoints and endpoints. You could travel through the graph starting from the entrypoints.
func (*TransitionGraph) Reader ¶ added in v0.2.0
func (tg *TransitionGraph) Reader(opts ...ReaderOption) *TransitionGraphReader
func (*TransitionGraph) ToMermaid ¶ added in v0.2.0
func (tg *TransitionGraph) ToMermaid() string
ToMermaid produces a mermaid-encoded representation of the transition graph.
type TransitionGraphReader ¶ added in v0.2.0
type TransitionGraphReader struct {
// contains filtered or unexported fields
}
TransitionGraphReader produces a finite set of strings that COVERS the transition graph: every reachable vertex and edge that lies on some entrypoint->endpoint walk appears in at least one produced string. It does so by enumerating every entrypoint->endpoint *trail* (a walk that uses each directed edge at most once) in order of increasing length, and for each trail every combination of its nodes' terminal variations (char-val casing, num-val ranges). Trails are bounded by the number of edges, so the set is finite and enumeration always terminates -- for any graph, cyclic or not.
func (*TransitionGraphReader) Next ¶ added in v0.2.0
func (tgr *TransitionGraphReader) Next() bool
Next reports whether another covering string is available.
func (*TransitionGraphReader) Scan ¶ added in v0.2.0
func (tgr *TransitionGraphReader) Scan() []byte
Scan returns the next covering string, or nil once coverage is complete.