Cheap shape check for the well-known catastrophic-backtracking regex
forms: a quantifier (+, *, {n,}) inside a group, itself followed
by another quantifier — (a+)+, (a+)*, (.*)+, (.*)* and their
siblings. Does not attempt to analyse nested groups beyond one level,
or catastrophic shapes built from alternation (e.g. (a|a)*) — see
the module doc comment.
Implemented as a manual scan, not a single regex against the pattern
string. A naive /\([^()]*[+*][^()]*\)\s*[+*{]/ scan is blind to
character classes: [^()]* cannot cross a ) written inside a
[...] class (e.g. the harmless-looking ) in [)]), so a pattern
like ^(a+[)]?a+)+$ desyncs the scan's idea of where the group ends
and the check never fires — even though the pattern is genuinely
catastrophic (it is (a+)+ with a no-op optional literal ) spliced
in). The scan below tracks whether it is inside an unescaped [...]
class and, while inside one, does not treat ( or ) as group
delimiters at all — matching how the regex engine itself parses them.
It also respects backslash escapes so \(, \), and \[ are never
mistaken for real syntax.
Cheap shape check for the well-known catastrophic-backtracking regex forms: a quantifier (
+,*,{n,}) inside a group, itself followed by another quantifier —(a+)+,(a+)*,(.*)+,(.*)*and their siblings. Does not attempt to analyse nested groups beyond one level, or catastrophic shapes built from alternation (e.g.(a|a)*) — see the module doc comment.Implemented as a manual scan, not a single regex against the pattern string. A naive
/\([^()]*[+*][^()]*\)\s*[+*{]/scan is blind to character classes:[^()]*cannot cross a)written inside a[...]class (e.g. the harmless-looking)in[)]), so a pattern like^(a+[)]?a+)+$desyncs the scan's idea of where the group ends and the check never fires — even though the pattern is genuinely catastrophic (it is(a+)+with a no-op optional literal)spliced in). The scan below tracks whether it is inside an unescaped[...]class and, while inside one, does not treat(or)as group delimiters at all — matching how the regex engine itself parses them. It also respects backslash escapes so\(,\), and\[are never mistaken for real syntax.