Functional Weave
Code in TypeScript

text.pattern-match@1.0.0

impl/python.py

13,048 bytes · the Python implementation · view raw

# A whole-string matcher for the portable subset of the regular expressions an
# HTML pattern attribute takes. The pattern is compiled to a small program and
# run as a Thompson NFA (a Pike VM without captures), so time is linear in the
# value whatever the pattern: (a+)+b cannot blow up as a backtracking engine
# would. Python's re is not used: its classes, $ and flags answer differently
# from the browser's (see spec/AUTHORING.md, "Same answers in every language").
from typing import List, Optional, Tuple

MAX_PATTERN = 1000
MAX_REPEAT = 1000
MAX_PROGRAM = 20000
MAX_CODE_POINT = 0x10FFFF

DIGIT = [(48, 57)]
WORD = [(48, 57), (65, 90), (95, 95), (97, 122)]
SPACE = [(9, 13), (32, 32)]
# What `.` does not match: the line terminators, as in JavaScript.
LINE_ENDS = [(10, 10), (13, 13), (0x2028, 0x2029)]
SYNTAX = "^$\\.*+?()[]{}|/"
CLASS_SYNTAX = "()[]{}/-\\|"
DOUBLED = "&!#$%*+,.:;<=>?@^`~"
CLASS_PUNCTUATORS = "&-!#%,:;<=>@`~"

CONTROL = {"t": 9, "n": 10, "v": 11, "f": 12, "r": 13}
CLASSES = {"d": (DIGIT, False), "D": (DIGIT, True), "w": (WORD, False), "W": (WORD, True), "s": (SPACE, False), "S": (SPACE, True)}

# A node is (atom, min, max) with max -1 for unbounded; an atom is
# ("class", ranges, negated) or ("group", alternatives).


def _unsupported(detail: str) -> ValueError:
    return ValueError("unsupported pattern: " + detail)


def _is_ascii_digit(c: int) -> bool:
    return 48 <= c <= 57


def _complement(ranges: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
    out = []
    nxt = 0
    for lo, hi in sorted(ranges, key=lambda r: r[0]):
        if lo > nxt:
            out.append((nxt, lo - 1))
        if hi + 1 > nxt:
            nxt = hi + 1
    if nxt <= MAX_CODE_POINT:
        out.append((nxt, MAX_CODE_POINT))
    return out


class _Parser:
    def __init__(self, cps: List[int], end: int, pos: int) -> None:
        self.cps = cps
        self.end = end
        self.pos = pos

    def peek(self) -> Optional[int]:
        return self.cps[self.pos] if self.pos < self.end else None

    def parse_alt(self, depth: int) -> list:
        alt = [self.parse_seq(depth)]
        while self.peek() == 124:  # |
            self.pos += 1
            alt.append(self.parse_seq(depth))
        return alt

    def parse_seq(self, depth: int) -> list:
        seq = []
        while True:
            c = self.peek()
            if c is None or c == 124:
                return seq
            if c == 41:  # )
                if depth == 0:
                    raise _unsupported("unbalanced )")
                return seq
            atom = self.parse_atom(depth)
            lo, hi = self.parse_quantifier()
            seq.append((atom, lo, hi))

    def parse_atom(self, depth: int) -> tuple:
        c = self.cps[self.pos]
        ch = chr(c)
        if ch in "*+?":
            raise _unsupported("nothing to repeat before " + ch)
        if ch == "{":
            if self.read_braces() is not None:
                raise _unsupported("nothing to repeat before {")
            raise _unsupported("a lone { must be escaped as \\{")
        if ch in "}]":
            raise _unsupported("a lone %s must be escaped as \\%s" % (ch, ch))
        if ch == "^":
            raise _unsupported("^ is only supported at the start of the pattern")
        if ch == "$":
            raise _unsupported("$ is only supported at the end of the pattern")
        if ch == ".":
            self.pos += 1
            return ("class", LINE_ENDS, True)
        if ch == "(":
            self.pos += 1
            if self.peek() == 63:  # ?
                if self.pos + 1 < self.end and self.cps[self.pos + 1] == 58:  # :
                    self.pos += 2
                else:
                    raise _unsupported("lookaround, named groups and flags are not supported")
            alt = self.parse_alt(depth + 1)
            if self.peek() != 41:
                raise _unsupported("unbalanced (")
            self.pos += 1
            return ("group", alt)
        if ch == "[":
            return self.parse_class()
        if ch == "\\":
            self.pos += 1
            ranges, negated, _single = self.parse_escape(False)
            return ("class", ranges, negated)
        self.pos += 1
        return ("class", [(c, c)], False)

    def parse_escape(self, in_class: bool) -> tuple:
        # After a backslash: a class escape, a control escape or escaped punctuation.
        c = self.peek()
        if c is None:
            raise _unsupported("the pattern ends with a lone \\")
        self.pos += 1
        ch = chr(c)
        if ch in CLASSES:
            ranges, negated = CLASSES[ch]
            return (ranges, negated, None)
        if ch in CONTROL:
            n = CONTROL[ch]
            return ([(n, n)], False, n)
        # Escaped punctuation: what the v flag accepts, the syntax characters
        # everywhere and the reserved punctuators inside [...].
        if ch in SYNTAX or (in_class and ch in CLASS_PUNCTUATORS):
            return ([(c, c)], False, c)
        raise _unsupported("\\%s is not supported (backreferences, \\b, \\p, \\u and \\x are not)" % ch)

    def parse_class(self) -> tuple:
        self.pos += 1  # [
        negated = False
        if self.peek() == 94:  # ^
            negated = True
            self.pos += 1
        ranges: List[Tuple[int, int]] = []
        while True:
            c = self.peek()
            if c is None:
                raise _unsupported("unbalanced [")
            if c == 93:  # ]
                self.pos += 1
                return ("class", ranges, negated)
            lo_ranges, lo = self.class_atom()
            if self.peek() == 45:  # -
                self.pos += 1
                if self.peek() == 93:
                    raise _unsupported("- must be escaped inside [...]")
                if lo is None:
                    raise _unsupported("a range in [...] must run between two characters")
                if self.peek() is None:
                    raise _unsupported("unbalanced [")
                _hi_ranges, hi = self.class_atom()
                if hi is None:
                    raise _unsupported("a range in [...] must run between two characters")
                if lo > hi:
                    raise _unsupported("a range in [...] runs backwards")
                ranges.append((lo, hi))
            elif lo is not None:
                ranges.append((lo, lo))
            else:
                ranges.extend(lo_ranges)

    def class_atom(self) -> tuple:
        c = self.cps[self.pos]
        ch = chr(c)
        if ch == "\\":
            self.pos += 1
            ranges, negated, single = self.parse_escape(True)
            return (_complement(ranges) if negated else ranges, single)
        if ch in CLASS_SYNTAX:
            raise _unsupported(ch + " must be escaped inside [...]")
        if ch in DOUBLED and self.pos + 1 < self.end and self.cps[self.pos + 1] == c:
            raise _unsupported(ch + ch + " is reserved inside [...]")
        self.pos += 1
        return ([(c, c)], c)

    def read_braces(self) -> Optional[Tuple[int, int]]:
        # {n}, {n,} or {n,m} at pos, or None (pos unchanged) when it is not one.
        p = self.pos + 1

        def number() -> Optional[int]:
            nonlocal p
            start = p
            n = 0
            while p < self.end and _is_ascii_digit(self.cps[p]):
                n = min(n * 10 + (self.cps[p] - 48), MAX_REPEAT + 1)
                p += 1
            return None if p == start else n

        lo = number()
        if lo is None:
            return None
        hi: Optional[int] = lo
        if p < self.end and self.cps[p] == 44:  # ,
            p += 1
            hi = number()
            if hi is None:
                hi = -1
        if p >= self.end or self.cps[p] != 125:  # }
            return None
        self.pos = p + 1
        return (lo, hi)

    def braces_ahead(self) -> bool:
        saved = self.pos
        found = self.read_braces() is not None
        self.pos = saved
        return found

    def parse_quantifier(self) -> Tuple[int, int]:
        c = self.peek()
        if c == 42:
            self.pos += 1
            q = (0, -1)
        elif c == 43:
            self.pos += 1
            q = (1, -1)
        elif c == 63:
            self.pos += 1
            q = (0, 1)
        elif c == 123:
            braces = self.read_braces()
            if braces is None:
                raise _unsupported("a lone { must be escaped as \\{")
            q = braces
            if q[0] > MAX_REPEAT or q[1] > MAX_REPEAT:
                raise _unsupported("a repeat count above %d" % MAX_REPEAT)
            if q[1] != -1 and q[0] > q[1]:
                raise _unsupported("a repeat {n,m} with n above m")
        else:
            return (1, 1)
        if self.peek() == 63:
            self.pos += 1  # lazy: the same answer for a whole-string match
        nxt = self.peek()
        if nxt in (42, 43, 63) or (nxt == 123 and self.braces_ahead()):
            raise _unsupported("nothing to repeat: a quantifier follows a quantifier")
        return q


# The program: ["char", ranges, negated], ["split", x, y], ["jmp", x], ["match"].
class _Compiler:
    def __init__(self) -> None:
        self.prog: list = []

    def push(self, op: list) -> int:
        if len(self.prog) >= MAX_PROGRAM:
            raise _unsupported("it expands to too large a program")
        self.prog.append(op)
        return len(self.prog) - 1

    def alt(self, alt: list) -> None:
        jumps = []
        for i, seq in enumerate(alt):
            if i < len(alt) - 1:
                split = self.push(["split", 0, 0])
                self.prog[split][1] = len(self.prog)
                self.seq(seq)
                jumps.append(self.push(["jmp", 0]))
                self.prog[split][2] = len(self.prog)
            else:
                self.seq(seq)
        for j in jumps:
            self.prog[j][1] = len(self.prog)

    def seq(self, seq: list) -> None:
        for atom, lo, hi in seq:
            for _ in range(lo):
                self.atom(atom)
            if hi == -1:
                split = self.push(["split", 0, 0])
                self.prog[split][1] = len(self.prog)
                self.atom(atom)
                self.push(["jmp", split])
                self.prog[split][2] = len(self.prog)
            else:
                splits = []
                for _ in range(lo, hi):
                    split = self.push(["split", 0, 0])
                    self.prog[split][1] = len(self.prog)
                    splits.append(split)
                    self.atom(atom)
                for s in splits:
                    self.prog[s][2] = len(self.prog)

    def atom(self, atom: tuple) -> None:
        if atom[0] == "class":
            self.push(["char", atom[1], atom[2]])
        else:
            self.alt(atom[1])


def _in_class(ranges: list, negated: bool, c: int) -> bool:
    hit = any(lo <= c <= hi for lo, hi in ranges)
    return hit != negated


def _add_thread(prog: list, out: list, seen: list, pc: int) -> None:
    stack = [pc]
    while stack:
        p = stack.pop()
        if seen[p]:
            continue
        seen[p] = True
        op = prog[p]
        if op[0] == "jmp":
            stack.append(op[1])
        elif op[0] == "split":
            stack.append(op[2])
            stack.append(op[1])
        else:
            out.append(p)


def matches_pattern(pattern: str, value: str) -> bool:
    """Whether the whole value matches the pattern, as an input's pattern
    attribute checks it (the browser wraps it as ^(?:pattern)$). Raises on
    anything outside the portable subset, so a pattern the server cannot check
    exactly as the browser does is caught when it is written."""
    cps = [ord(ch) for ch in pattern]
    if len(cps) > MAX_PATTERN:
        raise ValueError("pattern is too long: at most %d characters" % MAX_PATTERN)
    start = 0
    end = len(cps)
    if end > 0 and cps[0] == 94:
        start = 1
    # A trailing $ is the end anchor unless it is escaped (an odd run of backslashes before it).
    if end > start and cps[end - 1] == 36:
        slashes = 0
        i = end - 2
        while i >= start and cps[i] == 92:
            slashes += 1
            i -= 1
        if slashes % 2 == 0:
            end -= 1
    parser = _Parser(cps, end, start)
    alt = parser.parse_alt(0)
    if parser.pos != end:
        raise _unsupported("unbalanced )")

    compiler = _Compiler()
    compiler.alt(alt)
    compiler.push(["match"])
    prog = compiler.prog

    current: list = []
    _add_thread(prog, current, [False] * len(prog), 0)
    for ch in value:
        c = ord(ch)
        nxt: list = []
        seen = [False] * len(prog)
        for pc in current:
            op = prog[pc]
            if op[0] == "char" and _in_class(op[1], op[2], c):
                _add_thread(prog, nxt, seen, pc + 1)
        current = nxt
        if not current:
            return False
    return any(prog[pc][0] == "match" for pc in current)