Predicate Make::isPumpable
Holds if matching repetitions of pump
can:
- Transition from
pivot
back topivot
. - Transition from
pivot
topumpEnd
. - Transition from
pumpEnd
topumpEnd
.
From theorem 3 in the paper linked in the top of this file we can therefore conclude that the regular expression has polynomial backtracking - if a rejecting suffix exists.
This predicate is used by SuperLinearReDoSConfiguration
, and the final results are
available in the hasReDoSResult
predicate.
Import path
import codeql.regex.nfa.SuperlinearBackTracking
predicate isPumpable(State pivot, State pumpEnd, string pump)