Functional Weave
Code in TypeScript

text.pattern-match@1.0.0

impl/rust.rs

16,398 bytes · the Rust implementation · view raw

Imports name this capability’s declared dependencies, which fune builds next to it in your project; each one links to its page.

use super::funejson::Value;  ← the fune runtime: the JSON value the test vectors use; fune build keeps it only where a signature takes one

// 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 (chars), as the browser's
// v-flag regex is.

const MAX_PATTERN: usize = 1000;
const MAX_REPEAT: i64 = 1000;
const MAX_PROGRAM: usize = 20000;
const MAX_CODE_POINT: u32 = 0x10FFFF;

type Range = (u32, u32);

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: &str = "^$\\.*+?()[]{}|/";
const CLASS_SYNTAX: &str = "()[]{}/-\\|";
const DOUBLED: &str = "&!#$%*+,.:;<=>?@^`~";
const CLASS_PUNCTUATORS: &str = "&-!#%,:;<=>@`~";

enum Atom {
    Class(Vec<Range>, bool),
    Group(Vec<Vec<Node>>),
}

struct Node {
    atom: Atom,
    min: i64,
    max: i64, // -1: unbounded
}

fn unsupported(detail: &str) -> ! {
    panic!("unsupported pattern: {}", detail)
}

fn is_ascii_digit(c: u32) -> bool {
    (48..=57).contains(&c)
}

fn complement(ranges: &[Range]) -> Vec<Range> {
    let mut sorted: Vec<Range> = ranges.to_vec();
    sorted.sort_by_key(|r| r.0);
    let mut out = Vec::new();
    let mut next: u32 = 0;
    for (lo, hi) in 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));
    }
    out
}

struct Parser {
    cps: Vec<u32>,
    end: usize,
    pos: usize,
}

struct Escape {
    ranges: Vec<Range>,
    negated: bool,
    single: Option<u32>,
}

fn ch_of(c: u32) -> char {
    char::from_u32(c).unwrap_or('\u{FFFD}')
}

impl Parser {
    fn peek(&self) -> Option<u32> {
        if self.pos < self.end {
            Some(self.cps[self.pos])
        } else {
            None
        }
    }

    fn parse_alt(&mut self, depth: usize) -> Vec<Vec<Node>> {
        let mut alt = vec![self.parse_seq(depth)];
        while self.peek() == Some(124) {
            self.pos += 1;
            alt.push(self.parse_seq(depth));
        }
        alt
    }

    fn parse_seq(&mut self, depth: usize) -> Vec<Node> {
        let mut seq = Vec::new();
        loop {
            match self.peek() {
                None | Some(124) => return seq,
                Some(41) => {
                    if depth == 0 {
                        unsupported("unbalanced )");
                    }
                    return seq;
                }
                _ => {}
            }
            let atom = self.parse_atom(depth);
            let (min, max) = self.parse_quantifier();
            seq.push(Node { atom, min, max });
        }
    }

    fn parse_atom(&mut self, depth: usize) -> Atom {
        let c = self.cps[self.pos];
        let ch = ch_of(c);
        match ch {
            '*' | '+' | '?' => unsupported(&format!("nothing to repeat before {}", ch)),
            '{' => {
                if self.read_braces().is_some() {
                    unsupported("nothing to repeat before {");
                }
                unsupported("a lone { must be escaped as \\{")
            }
            '}' | ']' => unsupported(&format!("a lone {} must be escaped as \\{}", ch, ch)),
            '^' => unsupported("^ is only supported at the start of the pattern"),
            '$' => unsupported("$ is only supported at the end of the pattern"),
            '.' => {
                self.pos += 1;
                Atom::Class(LINE_ENDS.to_vec(), true)
            }
            '(' => {
                self.pos += 1;
                if self.peek() == Some(63) {
                    if self.pos + 1 < self.end && self.cps[self.pos + 1] == 58 {
                        self.pos += 2;
                    } else {
                        unsupported("lookaround, named groups and flags are not supported");
                    }
                }
                let alt = self.parse_alt(depth + 1);
                if self.peek() != Some(41) {
                    unsupported("unbalanced (");
                }
                self.pos += 1;
                Atom::Group(alt)
            }
            '[' => self.parse_class(),
            '\\' => {
                self.pos += 1;
                let e = self.parse_escape(false);
                Atom::Class(e.ranges, e.negated)
            }
            _ => {
                self.pos += 1;
                Atom::Class(vec![(c, c)], false)
            }
        }
    }

    // After a backslash: a class escape, a control escape or escaped punctuation.
    fn parse_escape(&mut self, in_class: bool) -> Escape {
        let c = match self.peek() {
            Some(c) => c,
            None => unsupported("the pattern ends with a lone \\"),
        };
        self.pos += 1;
        let ch = ch_of(c);
        let class = |ranges: &[Range], negated: bool| Escape { ranges: ranges.to_vec(), negated, single: None };
        let single = |n: u32| Escape { ranges: vec![(n, n)], negated: false, single: Some(n) };
        match ch {
            'd' => return class(DIGIT, false),
            'D' => return class(DIGIT, true),
            'w' => return class(WORD, false),
            'W' => return class(WORD, true),
            's' => return class(SPACE, false),
            'S' => return class(SPACE, true),
            't' => return single(9),
            'n' => return single(10),
            'v' => return single(11),
            'f' => return single(12),
            'r' => return single(13),
            _ => {}
        }
        // Escaped punctuation: what the v flag accepts, the syntax characters
        // everywhere and the reserved punctuators inside [...].
        if SYNTAX.contains(ch) || (in_class && CLASS_PUNCTUATORS.contains(ch)) {
            return single(c);
        }
        unsupported(&format!("\\{} is not supported (backreferences, \\b, \\p, \\u and \\x are not)", ch))
    }

    fn parse_class(&mut self) -> Atom {
        self.pos += 1; // [
        let mut negated = false;
        if self.peek() == Some(94) {
            negated = true;
            self.pos += 1;
        }
        let mut ranges: Vec<Range> = Vec::new();
        loop {
            match self.peek() {
                None => unsupported("unbalanced ["),
                Some(93) => {
                    self.pos += 1;
                    return Atom::Class(ranges, negated);
                }
                _ => {}
            }
            let (lo_ranges, lo) = self.class_atom();
            if self.peek() == Some(45) {
                self.pos += 1;
                if self.peek() == Some(93) {
                    unsupported("- must be escaped inside [...]");
                }
                let lo = match lo {
                    Some(lo) => lo,
                    None => unsupported("a range in [...] must run between two characters"),
                };
                if self.peek().is_none() {
                    unsupported("unbalanced [");
                }
                let (_, hi) = self.class_atom();
                let hi = match hi {
                    Some(hi) => hi,
                    None => unsupported("a range in [...] must run between two characters"),
                };
                if lo > hi {
                    unsupported("a range in [...] runs backwards");
                }
                ranges.push((lo, hi));
            } else if let Some(lo) = lo {
                ranges.push((lo, lo));
            } else {
                ranges.extend(lo_ranges);
            }
        }
    }

    fn class_atom(&mut self) -> (Vec<Range>, Option<u32>) {
        let c = self.cps[self.pos];
        let ch = ch_of(c);
        if ch == '\\' {
            self.pos += 1;
            let e = self.parse_escape(true);
            let ranges = if e.negated { complement(&e.ranges) } else { e.ranges };
            return (ranges, e.single);
        }
        if CLASS_SYNTAX.contains(ch) {
            unsupported(&format!("{} must be escaped inside [...]", ch));
        }
        if DOUBLED.contains(ch) && self.pos + 1 < self.end && self.cps[self.pos + 1] == c {
            unsupported(&format!("{}{} is reserved inside [...]", ch, ch));
        }
        self.pos += 1;
        (vec![(c, c)], Some(c))
    }

    // {n}, {n,} or {n,m} at pos, or None (pos unchanged) when it is not one.
    fn read_braces(&mut self) -> Option<(i64, i64)> {
        let mut p = self.pos + 1;
        let number = |p: &mut usize| -> Option<i64> {
            let start = *p;
            let mut n: i64 = 0;
            while *p < self.end && is_ascii_digit(self.cps[*p]) {
                n = (n * 10 + (self.cps[*p] as i64 - 48)).min(MAX_REPEAT + 1);
                *p += 1;
            }
            if *p == start {
                None
            } else {
                Some(n)
            }
        };
        let min = number(&mut p)?;
        let mut max = min;
        if p < self.end && self.cps[p] == 44 {
            p += 1;
            max = number(&mut p).unwrap_or(-1);
        }
        if p >= self.end || self.cps[p] != 125 {
            return None;
        }
        self.pos = p + 1;
        Some((min, max))
    }

    fn braces_ahead(&mut self) -> bool {
        let saved = self.pos;
        let found = self.read_braces().is_some();
        self.pos = saved;
        found
    }

    fn parse_quantifier(&mut self) -> (i64, i64) {
        let q = match self.peek() {
            Some(42) => {
                self.pos += 1;
                (0, -1)
            }
            Some(43) => {
                self.pos += 1;
                (1, -1)
            }
            Some(63) => {
                self.pos += 1;
                (0, 1)
            }
            Some(123) => {
                let q = match self.read_braces() {
                    Some(q) => q,
                    None => unsupported("a lone { must be escaped as \\{"),
                };
                if q.0 > MAX_REPEAT || q.1 > MAX_REPEAT {
                    unsupported(&format!("a repeat count above {}", MAX_REPEAT));
                }
                if q.1 != -1 && q.0 > q.1 {
                    unsupported("a repeat {n,m} with n above m");
                }
                q
            }
            _ => return (1, 1),
        };
        if self.peek() == Some(63) {
            self.pos += 1; // lazy: the same answer for a whole-string match
        }
        let next = self.peek();
        if matches!(next, Some(42) | Some(43) | Some(63)) || (next == Some(123) && self.braces_ahead()) {
            unsupported("nothing to repeat: a quantifier follows a quantifier");
        }
        q
    }
}

// The program: a character test, a fork, a jump or the match.
enum Op {
    Char(Vec<Range>, bool),
    Split(usize, usize),
    Jmp(usize),
    Match,
}

struct Compiler {
    prog: Vec<Op>,
}

impl Compiler {
    fn push(&mut self, op: Op) -> usize {
        if self.prog.len() >= MAX_PROGRAM {
            unsupported("it expands to too large a program");
        }
        self.prog.push(op);
        self.prog.len() - 1
    }

    fn set_x(&mut self, at: usize, to: usize) {
        match &mut self.prog[at] {
            Op::Split(x, _) | Op::Jmp(x) => *x = to,
            _ => {}
        }
    }

    fn set_y(&mut self, at: usize, to: usize) {
        if let Op::Split(_, y) = &mut self.prog[at] {
            *y = to;
        }
    }

    fn alt(&mut self, alt: &[Vec<Node>]) {
        let mut jumps = Vec::new();
        for (i, seq) in alt.iter().enumerate() {
            if i < alt.len() - 1 {
                let split = self.push(Op::Split(0, 0));
                let here = self.prog.len();
                self.set_x(split, here);
                self.seq(seq);
                jumps.push(self.push(Op::Jmp(0)));
                let here = self.prog.len();
                self.set_y(split, here);
            } else {
                self.seq(seq);
            }
        }
        let here = self.prog.len();
        for j in jumps {
            self.set_x(j, here);
        }
    }

    fn seq(&mut self, seq: &[Node]) {
        for node in seq {
            for _ in 0..node.min {
                self.atom(&node.atom);
            }
            if node.max == -1 {
                let split = self.push(Op::Split(0, 0));
                let here = self.prog.len();
                self.set_x(split, here);
                self.atom(&node.atom);
                self.push(Op::Jmp(split));
                let here = self.prog.len();
                self.set_y(split, here);
            } else {
                let mut splits = Vec::new();
                for _ in node.min..node.max {
                    let split = self.push(Op::Split(0, 0));
                    let here = self.prog.len();
                    self.set_x(split, here);
                    splits.push(split);
                    self.atom(&node.atom);
                }
                let here = self.prog.len();
                for s in splits {
                    self.set_y(s, here);
                }
            }
        }
    }

    fn atom(&mut self, atom: &Atom) {
        match atom {
            Atom::Class(ranges, negated) => {
                self.push(Op::Char(ranges.clone(), *negated));
            }
            Atom::Group(alt) => self.alt(alt),
        }
    }
}

fn add_thread(prog: &[Op], out: &mut Vec<usize>, seen: &mut [bool], pc: usize) {
    let mut stack = vec![pc];
    while let Some(p) = stack.pop() {
        if seen[p] {
            continue;
        }
        seen[p] = true;
        match &prog[p] {
            Op::Jmp(x) => stack.push(*x),
            Op::Split(x, y) => {
                stack.push(*y);
                stack.push(*x);
            }
            _ => out.push(p),
        }
    }
}

/// Whether the whole value matches the pattern, as an input's pattern
/// attribute checks it (the browser wraps it as ^(?:pattern)$).
///
/// # Panics
/// Panics with "unsupported pattern: ..." on anything outside the portable
/// subset, and "pattern is too long" over 1000 characters, so a pattern the
/// server cannot check exactly as the browser does is caught when written.
pub fn matches_pattern(pattern: &str, value: &str) -> bool {
    let cps: Vec<u32> = pattern.chars().map(|c| c as u32).collect();
    if cps.len() > MAX_PATTERN {
        panic!("pattern is too long: at most {} characters", MAX_PATTERN);
    }
    let mut start = 0;
    let mut end = cps.len();
    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 mut slashes = 0;
        let mut i = end - 1;
        while i > start && cps[i - 1] == 92 {
            slashes += 1;
            i -= 1;
        }
        if slashes % 2 == 0 {
            end -= 1;
        }
    }
    let mut parser = Parser { cps, end, pos: start };
    let alt = parser.parse_alt(0);
    if parser.pos != end {
        unsupported("unbalanced )");
    }

    let mut compiler = Compiler { prog: Vec::new() };
    compiler.alt(&alt);
    compiler.push(Op::Match);
    let prog = compiler.prog;

    let mut current = Vec::new();
    add_thread(&prog, &mut current, &mut vec![false; prog.len()], 0);
    for ch in value.chars() {
        let c = ch as u32;
        let mut next = Vec::new();
        let mut seen = vec![false; prog.len()];
        for &pc in &current {
            if let Op::Char(ranges, negated) = &prog[pc] {
                let hit = ranges.iter().any(|&(lo, hi)| c >= lo && c <= hi);
                if hit != *negated {
                    add_thread(&prog, &mut next, &mut seen, pc + 1);
                }
            }
        }
        current = next;
        if current.is_empty() {
            return false;
        }
    }
    current.iter().any(|&pc| matches!(prog[pc], Op::Match))
}

pub fn fune_vector(args: &[Value]) -> Value {
    Value::Bool(matches_pattern(args[0].as_str(), args[1].as_str()))
}