CodeQL library for Python
codeql/python-all 1.0.1 (changelog, source)
Search

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)