File size: 3,355 Bytes
5d97275 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | 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):
# an end-anchored last part is searched against the real end (endpos would move '$')
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 # every X left in this stretch has a shorter run: skip to the next
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
|