use super::funejson::Value; // 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, bool), Group(Vec>), } 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 { let mut sorted: Vec = 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, end: usize, pos: usize, } struct Escape { ranges: Vec, negated: bool, single: Option, } fn ch_of(c: u32) -> char { char::from_u32(c).unwrap_or('\u{FFFD}') } impl Parser { fn peek(&self) -> Option { if self.pos < self.end { Some(self.cps[self.pos]) } else { None } } fn parse_alt(&mut self, depth: usize) -> Vec> { 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 { 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 = 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, Option) { 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 { 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, bool), Split(usize, usize), Jmp(usize), Match, } struct Compiler { prog: Vec, } 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]) { 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, 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 = 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())) }