# 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)