Predicate Make::isStartLoops
Holds if pivot
and pumpEnd
are a pair of loops that could be the beginning of a quadratic blowup.
There is a slight implementation difference compared to the paper: this predicate requires that pivot != pumpEnd
.
The case where pivot = pumpEnd
causes exponential backtracking and is handled by the js/redos
query.
Import path
import codeql.regex.nfa.SuperlinearBackTracking
predicate isStartLoops(State pivot, State pumpEnd)