The character to be repeated in order to create an input for which the analysed literal will have super-linear runtime behavior.
A literal that represents set.
E.g. if set only contained the character "a" (lower case A), then the literal may be /a/.
A single character that can be repeated to cause super-linear runtime.
The implementation is allowed to pick any character in set but makes a best effort to pick a
"humanly readable" character.
A non-empty set of characters that can be repeated to cause super-linear runtime.
CharSet is a class from the refa library.
This type can never cause exponential backtracking.
The unbounded quantifier that caused this report.
Returns a new literal with this cause of super-linear runtime being fixed. If the cause of this report could not
be automatically fixed, undefined will be returned.
A fixed literal is guaranteed to behave exactly the same as the analysed literal.
This report indicates super-linear runtime cause by the matching algorithm moving the regexes across the input string.
Examples
/a+b/Description
This type of super-linear runtime is not caused by backtracking but by the matching algorithm itself. While the regex engine will try to optimize as much as possible, in some cases, it will be forced to match a pattern against every suffix of the given input string according the ECMAScript specification. Because there are n many suffixes for a rejecting input string with length n, the total runtime will be the time it takes to reject every suffix times n. For non-finite languages, even a DFA (that guarantees O(n) for every suffix) might have a total worst-case time complexity of O(n^2).
Fixing
This type of super-linear runtime is the hardest to fix (if at all possible) because the fixed regex has to reject all suffixes with an average worst-case time complexity of O(1).
Notes
Literals with the sticky flag (e.g.
/a+b/y) and anchored literals (e.g./^a+b/and/\ba+b/but not/^\s+b/mand/\Ba+b/) are immune to this type of super-linear runtime.This type can never cause exponential backtracking.