Functional Weave
Code in TypeScript

text.pattern-match@1.0.0

impl/typescript.ts

13,779 bytes · the TypeScript 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. 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");
}