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