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 ¤t {
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()))
}