| r"""Linear-time signature matching for Python's backtracking `re`. |
| |
| A branch shaped `X .* Y` (or `X [^c]* Y`) is quadratic on crafted input: every occurrence of X rescans the rest of the |
| text looking for Y ("<a<a<a..." for `<[a-z][^>]*\son\w+=`, "../a../a..." for `\.\.[/\\][^|\s]*\.env`: seconds per 16 KB). |
| For a yes/no answer only the *first* X of each stretch matters - any later X's run is a suffix of the first one's - so |
| `Gap` finds the first X, then Y after it inside the same stretch (one forward pass per stretch, linear overall), and |
| gives the same answer as `re.search` on the joined pattern. `Sig` is a compiled regex for the cheap branches plus such |
| gaps, with the `.search(text)` of a regex. The Go fast path needs none of this: RE2 is linear by construction, so the |
| Go signatures keep these branches in their regexes (and the parity fixtures prove the answers agree). |
| """ |
| from __future__ import annotations |
|
|
| import re |
|
|
|
|
| class Gap: |
| """parts[0] <run> parts[1] <run> ... parts[-1]: each <run> any characters except `stop` (a character class such as |
| r"[|\\s]", or None: any character but a newline unless `flags` has re.S). A last part ending in "$" must reach the |
| end of the text, so it only counts in the last stretch.""" |
|
|
| def __init__(self, parts: list[str], stop: str | None = None, flags: int = 0): |
| self.parts = [re.compile(p, flags) for p in parts] |
| self.end_anchored = parts[-1].endswith("$") and not parts[-1].endswith("\\$") |
| if stop is None and not flags & re.S: |
| stop = "\n" |
| self.stop = re.compile(stop) if stop is not None else None |
|
|
| def search(self, text: str): |
| n, pos = len(text), 0 |
| while pos <= n: |
| m = self.parts[0].search(text, pos) |
| if m is None: |
| return None |
| lim = n |
| if self.stop is not None: |
| st = self.stop.search(text, m.end()) |
| lim = st.start() if st else n |
| ok = not (self.end_anchored and lim < n) |
| p = m.end() |
| if ok: |
| for i, r in enumerate(self.parts[1:], 1): |
| |
| m2 = r.search(text, p) if (self.end_anchored and i == len(self.parts) - 1) else r.search(text, p, lim) |
| if m2 is None: |
| ok = False |
| break |
| p = m2.end() |
| if ok: |
| return m2 if len(self.parts) > 1 else m |
| if self.stop is None or lim >= n: |
| return None |
| pos = lim + 1 |
| return None |
|
|
|
|
| class Sig: |
| """a signature: one regex (linear branches) or-ed with gaps / other matchers; .search(text) like a regex""" |
|
|
| def __init__(self, pattern: str | None, *extra, flags: int = 0): |
| self.re = re.compile(pattern, flags) if pattern else None |
| self.extra = extra |
| self.pattern = pattern or "" |
|
|
| def search(self, text: str): |
| if self.re is not None: |
| m = self.re.search(text) |
| if m: |
| return m |
| for x in self.extra: |
| m = x.search(text) |
| if m: |
| return m |
| return None |
|
|
