CodeQL library for Python
codeql/python-all 0.9.2 ( 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 )