Provides classes for working with regular expressions that can perform backtracking in superlinear/exponential time.
This module contains a number of utility predicates for compiling a regular expression into a NFA and reasoning about this NFA.
ReDoSConfiguration contains a
isReDoSCandidate predicate that is used to
to determine which states the prefix/suffix search should happen on.
There is only meant to exist one
ReDoSConfiguration at a time.
hasReDoSResult outputs a de-duplicated set of
states that will cause backtracking (a rejecting suffix exists).
This module should provide a class hierarchy corresponding to a parse tree of regular expressions. This is the interface to the shared ReDoS library.
Gets a state the NFA may be in after matching
Holds if the NFA has a transition from
Holds if there is a state
Gets a state that has an epsilon transition to
Gets a state that
Gets a symbol that matches
Gets the canonical CharClass for
Gets a string reperesentation of the flags used with the regular expression. Only the flags that are relevant for the canonicalization are included.
Gets the root containing the given term, that is, the root of the literal, or a branch of the root disjunction.
Holds if the state
Gets a character that is represented by both
Gets a state that is about to match the regular expression
An abstract input symbol that represents a character class.
A lookahead/lookbehind that matches the empty string.
An abstract input symbol, representing a set of concrete characters.
A configuration for which parts of a regular expression should be considered relevant for the different predicates in
A branch in a disjunction that is the root node in a literal, or a literal whose root node is not a disjunction.
A regexp term that is relevant for this ReDoS analysis.
A state in the NFA corresponding to a regular expression.
A state in the NFA.