// 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. Everything is over Unicode code points, as the browser's v-flag regex is.
const MAX_PATTERN = 1000;
const MAX_REPEAT = 1000;
const MAX_PROGRAM = 20000;
const MAX_CODE_POINT = 0x10ffff;
type Range = [number, number];
interface ClassNode { kind: "class"; ranges: Range[]; negated: boolean }
interface GroupNode { kind: "group"; alt: Node[][] }
type Atom = ClassNode | GroupNode;
interface Node { atom: Atom; min: number; max: number } // max -1: unbounded
const DIGIT: Range[] = [[48, 57]];
const WORD: Range[] = [[48, 57], [65, 90], [95, 95], [97, 122]];
const SPACE: Range[] = [[9, 13], [32, 32]];
// What `.` does not match: the line terminators, as in JavaScript.
const LINE_ENDS: Range[] = [[10, 10], [13, 13], [0x2028, 0x2029]];
const SYNTAX = "^$\\.*+?()[]{}|/";
const CLASS_SYNTAX = "()[]{}/-\\|";
const DOUBLED = "&!#$%*+,.:;<=>?@^`~";
const CLASS_PUNCTUATORS = "&-!#%,:;<=>@`~";
function unsupported(detail: string): Error {
return new Error(`unsupported pattern: ${detail}`);
}
function isAsciiDigit(c: number): boolean {
return c >= 48 && c <= 57;
}
function complement(ranges: Range[]): Range[] {
const sorted = ranges.map((r): Range => [r[0], r[1]]).sort((a, b) => a[0] - b[0]);
const out: Range[] = [];
let next = 0;
for (const [lo, hi] of sorted) {
if (lo > next) out.push([next, lo - 1]);
if (hi + 1 > next) next = hi + 1;
}
if (next <= MAX_CODE_POINT) out.push([next, MAX_CODE_POINT]);
return out;
}
class Parser {
pos = 0;
readonly cps: number[];
readonly end: number;
constructor(cps: number[], end: number) {
this.cps = cps;
this.end = end;
}
peek(): number | undefined {
return this.pos < this.end ? this.cps[this.pos] : undefined;
}
parseAlt(depth: number): Node[][] {
const alt: Node[][] = [this.parseSeq(depth)];
while (this.peek() === 124 /* | */) {
this.pos++;
alt.push(this.parseSeq(depth));
}
return alt;
}
parseSeq(depth: number): Node[] {
const seq: Node[] = [];
for (;;) {
const c = this.peek();
if (c === undefined || c === 124) return seq;
if (c === 41 /* ) */) {
if (depth === 0) throw unsupported("unbalanced )");
return seq;
}
const atom = this.parseAtom(depth);
const [min, max] = this.parseQuantifier();
seq.push({ atom, min, max });
}
}
parseAtom(depth: number): Atom {
const c = this.cps[this.pos];
const ch = String.fromCodePoint(c);
if (ch === "*" || ch === "+" || ch === "?") throw unsupported(`nothing to repeat before ${ch}`);
if (ch === "{") {
if (this.readBraces() !== null) throw unsupported("nothing to repeat before {");
throw unsupported("a lone { must be escaped as \\{");
}
if (ch === "}" || ch === "]") throw unsupported(`a lone ${ch} must be escaped as \\${ch}`);
if (ch === "^") throw unsupported("^ is only supported at the start of the pattern");
if (ch === "$") throw unsupported("$ is only supported at the end of the pattern");
if (ch === ".") {
this.pos++;
return { kind: "class", ranges: LINE_ENDS, negated: true };
}
if (ch === "(") {
this.pos++;
if (this.peek() === 63 /* ? */) {
if (this.cps[this.pos + 1] === 58 /* : */ && this.pos + 1 < this.end) this.pos += 2;
else throw unsupported("lookaround, named groups and flags are not supported");
}
const alt = this.parseAlt(depth + 1);
if (this.peek() !== 41) throw unsupported("unbalanced (");
this.pos++;
return { kind: "group", alt };
}
if (ch === "[") return this.parseClass();
if (ch === "\\") {
this.pos++;
const escaped = this.parseEscape(false);
return { kind: "class", ranges: escaped.ranges, negated: escaped.negated };
}
this.pos++;
return { kind: "class", ranges: [[c, c]], negated: false };
}
// After a backslash: a class escape, a control escape or escaped punctuation.
parseEscape(inClass: boolean): { ranges: Range[]; negated: boolean; single: number | null } {
const c = this.peek();
if (c === undefined) throw unsupported("the pattern ends with a lone \\");
this.pos++;
const ch = String.fromCodePoint(c);
switch (ch) {
case "d": return { ranges: DIGIT, negated: false, single: null };
case "D": return { ranges: DIGIT, negated: true, single: null };
case "w": return { ranges: WORD, negated: false, single: null };
case "W": return { ranges: WORD, negated: true, single: null };
case "s": return { ranges: SPACE, negated: false, single: null };
case "S": return { ranges: SPACE, negated: true, single: null };
case "t": return { ranges: [[9, 9]], negated: false, single: 9 };
case "n": return { ranges: [[10, 10]], negated: false, single: 10 };
case "v": return { ranges: [[11, 11]], negated: false, single: 11 };
case "f": return { ranges: [[12, 12]], negated: false, single: 12 };
case "r": return { ranges: [[13, 13]], negated: false, single: 13 };
}
// Escaped punctuation: what the v flag accepts, the syntax characters
// everywhere and the reserved punctuators inside [...].
if (SYNTAX.includes(ch) || (inClass && CLASS_PUNCTUATORS.includes(ch))) {
return { ranges: [[c, c]], negated: false, single: c };
}
throw unsupported(`\\${ch} is not supported (backreferences, \\b, \\p, \\u and \\x are not)`);
}
parseClass(): ClassNode {
this.pos++; // [
let negated = false;
if (this.peek() === 94 /* ^ */) {
negated = true;
this.pos++;
}
const ranges: Range[] = [];
for (;;) {
const c = this.peek();
if (c === undefined) throw unsupported("unbalanced [");
if (c === 93 /* ] */) {
this.pos++;
return { kind: "class", ranges, negated };
}
const lo = this.classAtom();
if (this.peek() === 45 /* - */) {
this.pos++;
if (this.peek() === 93) throw unsupported("- must be escaped inside [...]");
if (lo.single === null) throw unsupported("a range in [...] must run between two characters");
if (this.peek() === undefined) throw unsupported("unbalanced [");
const hi = this.classAtom();
if (hi.single === null) throw unsupported("a range in [...] must run between two characters");
if (lo.single > hi.single) throw unsupported("a range in [...] runs backwards");
ranges.push([lo.single, hi.single]);
} else if (lo.single !== null) {
ranges.push([lo.single, lo.single]);
} else {
for (const r of lo.ranges) ranges.push(r);
}
}
}
classAtom(): { ranges: Range[]; single: number | null } {
const c = this.cps[this.pos];
const ch = String.fromCodePoint(c);
if (ch === "\\") {
this.pos++;
const e = this.parseEscape(true);
return { ranges: e.negated ? complement(e.ranges) : e.ranges, single: e.single };
}
if (CLASS_SYNTAX.includes(ch)) throw unsupported(`${ch} must be escaped inside [...]`);
if (DOUBLED.includes(ch) && this.pos + 1 < this.end && this.cps[this.pos + 1] === c) {
throw unsupported(`${ch}${ch} is reserved inside [...]`);
}
this.pos++;
return { ranges: [[c, c]], single: c };
}
// {n}, {n,} or {n,m} at pos, or null (pos unchanged) when it is not one.
readBraces(): [number, number] | null {
let p = this.pos + 1;
const number = (): number | null => {
const start = p;
let n = 0;
while (p < this.end && isAsciiDigit(this.cps[p])) {
n = Math.min(n * 10 + (this.cps[p] - 48), MAX_REPEAT + 1);
p++;
}
return p === start ? null : n;
};
const min = number();
if (min === null) return null;
let max: number | null = min;
if (p < this.end && this.cps[p] === 44 /* , */) {
p++;
max = number();
if (max === null) max = -1;
}
if (p >= this.end || this.cps[p] !== 125 /* } */) return null;
this.pos = p + 1;
return [min, max];
}
parseQuantifier(): [number, number] {
const c = this.peek();
let q: [number, number];
if (c === 42) { this.pos++; q = [0, -1]; }
else if (c === 43) { this.pos++; q = [1, -1]; }
else if (c === 63) { this.pos++; q = [0, 1]; }
else if (c === 123) {
const braces = this.readBraces();
if (braces === null) throw unsupported("a lone { must be escaped as \\{");
q = braces;
if (q[0] > MAX_REPEAT || q[1] > MAX_REPEAT) throw unsupported(`a repeat count above ${MAX_REPEAT}`);
if (q[1] !== -1 && q[0] > q[1]) throw unsupported("a repeat {n,m} with n above m");
} else return [1, 1];
if (this.peek() === 63) this.pos++; // lazy: the same answer for a whole-string match
const next = this.peek();
if (next === 42 || next === 43 || next === 63 || (next === 123 && this.readBracesAhead())) {
throw unsupported("nothing to repeat: a quantifier follows a quantifier");
}
return q;
}
readBracesAhead(): boolean {
const saved = this.pos;
const found = this.readBraces() !== null;
this.pos = saved;
return found;
}
}
// The program: a character test, a fork, a jump or the match.
type Op =
| { op: "char"; ranges: Range[]; negated: boolean }
| { op: "split"; x: number; y: number }
| { op: "jmp"; x: number }
| { op: "match" };
class Compiler {
prog: Op[] = [];
push(op: Op): number {
if (this.prog.length >= MAX_PROGRAM) throw unsupported("it expands to too large a program");
this.prog.push(op);
return this.prog.length - 1;
}
alt(alt: Node[][]): void {
const jumps: number[] = [];
for (let i = 0; i < alt.length; i++) {
if (i < alt.length - 1) {
const split = this.push({ op: "split", x: 0, y: 0 });
(this.prog[split] as { x: number }).x = this.prog.length;
this.seq(alt[i]);
jumps.push(this.push({ op: "jmp", x: 0 }));
(this.prog[split] as { y: number }).y = this.prog.length;
} else {
this.seq(alt[i]);
}
}
for (const j of jumps) (this.prog[j] as { x: number }).x = this.prog.length;
}
seq(seq: Node[]): void {
for (const node of seq) {
for (let i = 0; i < node.min; i++) this.atom(node.atom);
if (node.max === -1) {
const split = this.push({ op: "split", x: 0, y: 0 });
(this.prog[split] as { x: number }).x = this.prog.length;
this.atom(node.atom);
this.push({ op: "jmp", x: split });
(this.prog[split] as { y: number }).y = this.prog.length;
} else {
const splits: number[] = [];
for (let i = node.min; i < node.max; i++) {
const split = this.push({ op: "split", x: 0, y: 0 });
(this.prog[split] as { x: number }).x = this.prog.length;
splits.push(split);
this.atom(node.atom);
}
for (const s of splits) (this.prog[s] as { y: number }).y = this.prog.length;
}
}
}
atom(atom: Atom): void {
if (atom.kind === "class") this.push({ op: "char", ranges: atom.ranges, negated: atom.negated });
else this.alt(atom.alt);
}
}
function inClass(op: { ranges: Range[]; negated: boolean }, c: number): boolean {
let hit = false;
for (const [lo, hi] of op.ranges) {
if (c >= lo && c <= hi) {
hit = true;
break;
}
}
return hit !== op.negated;
}
function addThread(prog: Op[], list: number[], seen: Uint8Array, pc: number): void {
const stack = [pc];
while (stack.length > 0) {
const p = stack.pop() as number;
if (seen[p]) continue;
seen[p] = 1;
const op = prog[p];
if (op.op === "jmp") stack.push(op.x);
else if (op.op === "split") {
stack.push(op.y);
stack.push(op.x);
} else list.push(p);
}
}
/**
* Whether the whole value matches the pattern, as an input's pattern
* attribute checks it (the browser wraps it as ^(?:pattern)$). Throws on
* anything outside the portable subset, so a pattern the server cannot check
* exactly as the browser does is caught when it is written, not in production.
*/
export function matchesPattern(pattern: string, value: string): boolean {
const cps = Array.from(pattern, (s) => s.codePointAt(0) as number);
if (cps.length > MAX_PATTERN) throw new Error(`pattern is too long: at most ${MAX_PATTERN} characters`);
let start = 0;
let end = cps.length;
if (end > 0 && 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 && cps[end - 1] === 36 /* $ */) {
let slashes = 0;
for (let i = end - 2; i >= start && cps[i] === 92; i--) slashes++;
if (slashes % 2 === 0) end--;
}
const parser = new Parser(cps, end);
parser.pos = start;
const alt = parser.parseAlt(0);
if (parser.pos !== end) throw unsupported("unbalanced )");
const compiler = new Compiler();
compiler.alt(alt);
compiler.push({ op: "match" });
const prog = compiler.prog;
let current: number[] = [];
addThread(prog, current, new Uint8Array(prog.length), 0);
for (const s of value) {
const c = s.codePointAt(0) as number;
const next: number[] = [];
const seen = new Uint8Array(prog.length);
for (const pc of current) {
const op = prog[pc];
if (op.op === "char" && inClass(op, c)) addThread(prog, next, seen, pc + 1);
}
current = next;
if (current.length === 0) return false;
}
return current.some((pc) => prog[pc].op === "match");
}