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:
return48 <= c <= 57def _complement(ranges: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
out = []
nxt = 0for lo, hi in sorted(ranges, key=lambda r: r[0]):
if lo > nxt:
out.append((nxt, lo - 1))
if hi + 1 > nxt:
nxt = hi + 1if 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 elseNonedef 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 = []
whileTrue:
c = self.peek()
if c isNoneor 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() isnotNone:
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 += 1return ("class", LINE_ENDS, True)
if ch == "(":
self.pos += 1if self.peek() == 63: # ?if self.pos + 1 < self.end and self.cps[self.pos + 1] == 58: # :
self.pos += 2else:
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 += 1return ("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 += 1return ("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 isNone:
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 = Falseif self.peek() == 94: # ^
negated = True
self.pos += 1
ranges: List[Tuple[int, int]] = []
whileTrue:
c = self.peek()
if c isNone:
raise _unsupported("unbalanced [")
if c == 93: # ]
self.pos += 1return ("class", ranges, negated)
lo_ranges, lo = self.class_atom()
if self.peek() == 45: # -
self.pos += 1if self.peek() == 93:
raise _unsupported("- must be escaped inside [...]")
if lo isNone:
raise _unsupported("a range in [...] must run between two characters")
if self.peek() isNone:
raise _unsupported("unbalanced [")
_hi_ranges, hi = self.class_atom()
if hi isNone:
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 isnotNone:
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 += 1return ([(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 + 1def number() -> Optional[int]:
nonlocal p
start = p
n = 0while p < self.end and _is_ascii_digit(self.cps[p]):
n = min(n * 10 + (self.cps[p] - 48), MAX_REPEAT + 1)
p += 1returnNoneif p == start else n
lo = number()
if lo isNone:
returnNone
hi: Optional[int] = lo
if p < self.end and self.cps[p] == 44: # ,
p += 1
hi = number()
if hi isNone:
hi = -1if p >= self.end or self.cps[p] != 125: # }returnNone
self.pos = p + 1return (lo, hi)
def braces_ahead(self) -> bool:
saved = self.pos
found = self.read_braces() isnotNone
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 isNone:
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] != -1and 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 == 123and 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) - 1def 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 > 0and 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 - 2while i >= start and cps[i] == 92:
slashes += 1
i -= 1if 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
ifnot current:
returnFalsereturn any(prog[pc][0] == "match"for pc in current)