use std::fmt;
#[derive(Clone)]
pub struct Pattern {
source: String,
prog: Vec<Inst>,
groups: usize,
fold: bool,
anchored: bool,
}
impl fmt::Debug for Pattern {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "Pattern({:?})", self.source)
}
}
impl PartialEq for Pattern {
fn eq(&self, other: &Self) -> bool {
self.source == other.source
}
}
#[derive(Clone, Debug)]
enum Matcher {
Char(char),
Class(Vec<(char, char)>, bool),
}
#[derive(Clone, Debug)]
enum Inst {
Char(Matcher),
Split(usize, usize),
Jmp(usize),
Save(usize),
Start,
End,
Match,
}
#[derive(Clone, Debug)]
enum Ast {
Empty,
Char(Matcher),
Start,
End,
Group(Box<Ast>, Option<usize>),
Concat(Vec<Ast>),
Alt(Vec<Ast>),
Repeat(Box<Ast>, u32, Option<u32>, bool),
}
#[derive(Clone, Debug)]
pub struct Captures {
slots: Vec<Option<usize>>,
}
impl Captures {
pub fn span(&self, i: usize) -> Option<(usize, usize)> {
match (self.slots.get(2 * i).copied().flatten(), self.slots.get(2 * i + 1).copied().flatten()) {
(Some(a), Some(b)) if a <= b => Some((a, b)),
_ => None,
}
}
pub fn get<'t>(&self, text: &'t str, i: usize) -> Option<&'t str> {
self.span(i).and_then(|(a, b)| text.get(a..b))
}
pub fn whole(&self) -> (usize, usize) {
self.span(0).unwrap_or((0, 0))
}
}
struct Parser<'a> {
chars: Vec<char>,
i: usize,
groups: usize,
fold: bool,
_src: &'a str,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct PatternError(pub String);
impl fmt::Display for PatternError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(&self.0)
}
}
impl Pattern {
pub fn new(source: &str) -> Result<Pattern, PatternError> {
let mut p = Parser { chars: source.chars().collect(), i: 0, groups: 1, fold: false, _src: source };
if p.chars.starts_with(&['(', '?', 'i', ')']) {
p.fold = true;
p.i = 4;
}
let ast = p.alt()?;
if p.i != p.chars.len() {
return Err(PatternError(format!("unexpected {:?} in {source}", p.chars[p.i])));
}
let mut prog = vec![Inst::Save(0)];
compile(&ast, &mut prog);
prog.push(Inst::Save(1));
prog.push(Inst::Match);
let anchored = starts_anchored(&ast);
Ok(Pattern { source: source.to_string(), prog, groups: p.groups, fold: p.fold, anchored })
}
pub(crate) fn must(source: &str) -> Pattern {
match Pattern::new(source) {
Ok(p) => p,
Err(e) => Pattern::never(&e.0),
}
}
fn never(source: &str) -> Pattern {
Pattern {
source: source.to_string(),
prog: vec![Inst::Char(Matcher::Class(Vec::new(), false)), Inst::Match],
groups: 1,
fold: false,
anchored: false,
}
}
pub fn as_str(&self) -> &str {
&self.source
}
pub fn is_match(&self, text: &str) -> bool {
self.run(text, 0, 0, true).is_some()
}
pub fn find(&self, text: &str) -> Option<(usize, usize)> {
self.captures_at(text, 0).map(|c| c.whole())
}
pub fn find_str<'t>(&self, text: &'t str) -> Option<&'t str> {
self.find(text).and_then(|(a, b)| text.get(a..b))
}
pub fn captures(&self, text: &str) -> Option<Captures> {
self.captures_at(text, 0)
}
pub fn find_iter(&self, text: &str) -> Vec<(usize, usize)> {
self.captures_iter(text).iter().map(Captures::whole).collect()
}
pub fn captures_iter(&self, text: &str) -> Vec<Captures> {
let mut out = Vec::new();
let mut at = 0;
while at <= text.len() {
let Some(c) = self.captures_at(text, at) else { break };
let (a, b) = c.whole();
out.push(c);
at = if b > a {
b
} else {
match text[b..].chars().next() {
Some(ch) => b + ch.len_utf8(),
None => break,
}
};
}
out
}
pub fn replace_all(&self, text: &str, mut f: impl FnMut(&Captures) -> String) -> String {
let mut out = String::with_capacity(text.len());
let mut last = 0;
for c in self.captures_iter(text) {
let (a, b) = c.whole();
out.push_str(&text[last..a]);
out.push_str(&f(&c));
last = b;
}
out.push_str(&text[last..]);
out
}
pub fn captures_at(&self, text: &str, start: usize) -> Option<Captures> {
self.run(text, start, self.groups * 2, false).map(|slots| Captures { slots })
}
fn run(&self, text: &str, start: usize, slots: usize, any: bool) -> Option<Vec<Option<usize>>> {
if start > text.len() || !text.is_char_boundary(start) || self.anchored && start > 0 {
return None;
}
let n = self.prog.len();
let mut clist = Threads::new(n);
let mut nlist = Threads::new(n);
let mut matched: Option<Vec<Option<usize>>> = None;
let mut pos = start;
loop {
if matched.is_none() && (!self.anchored || pos == 0) {
self.add(&mut clist, 0, pos, text, vec![None; slots]);
}
if clist.list.is_empty() {
break;
}
let ch = text[pos..].chars().next();
let next = pos + ch.map_or(0, char::len_utf8);
nlist.clear();
let threads = std::mem::take(&mut clist.list);
for (pc, caps) in threads {
match &self.prog[pc] {
Inst::Char(m) => {
if let Some(c) = ch
&& self.matches(m, c)
{
self.add(&mut nlist, pc + 1, next, text, caps);
}
}
Inst::Match => {
matched = Some(caps);
if any {
return matched;
}
break;
}
_ => {}
}
}
std::mem::swap(&mut clist, &mut nlist);
if ch.is_none() {
break;
}
pos = next;
}
matched
}
fn matches(&self, m: &Matcher, c: char) -> bool {
let fold = self.fold;
match m {
Matcher::Char(x) => *x == c || fold && x.eq_ignore_ascii_case(&c),
Matcher::Class(ranges, negated) => {
let hit = |c: char| ranges.iter().any(|&(a, b)| a <= c && c <= b);
let mut found = hit(c);
if !found && fold && c.is_ascii_alphabetic() {
found = hit(c.to_ascii_lowercase()) || hit(c.to_ascii_uppercase());
}
found != *negated
}
}
}
fn add(&self, list: &mut Threads, pc: usize, pos: usize, text: &str, mut caps: Vec<Option<usize>>) {
let mut stack: Vec<(usize, Restore)> = vec![(pc, None)];
while let Some((pc, restore)) = stack.pop() {
if let Some((slot, old)) = restore {
caps[slot] = old;
continue;
}
if list.seen[pc] == list.generation {
continue;
}
list.seen[pc] = list.generation;
match &self.prog[pc] {
Inst::Jmp(t) => stack.push((*t, None)),
Inst::Split(a, b) => {
stack.push((*b, None));
stack.push((*a, None));
}
Inst::Save(slot) => {
if *slot < caps.len() {
let old = caps[*slot];
caps[*slot] = Some(pos);
stack.push((0, Some((*slot, old))));
stack.push((pc + 1, None));
} else {
stack.push((pc + 1, None));
}
}
Inst::Start => {
if pos == 0 {
stack.push((pc + 1, None));
}
}
Inst::End => {
if pos == text.len() {
stack.push((pc + 1, None));
}
}
Inst::Char(_) | Inst::Match => list.list.push((pc, caps.clone())),
}
}
}
}
type Restore = Option<(usize, Option<usize>)>;
struct Threads {
seen: Vec<u32>,
generation: u32,
list: Vec<(usize, Vec<Option<usize>>)>,
}
impl Threads {
fn new(n: usize) -> Threads {
Threads { seen: vec![0; n], generation: 1, list: Vec::new() }
}
fn clear(&mut self) {
self.generation = self.generation.wrapping_add(1);
if self.generation == 0 {
self.seen.iter_mut().for_each(|s| *s = 0);
self.generation = 1;
}
self.list.clear();
}
}
fn starts_anchored(ast: &Ast) -> bool {
match ast {
Ast::Start => true,
Ast::Concat(items) => items.first().is_some_and(starts_anchored),
Ast::Group(inner, _) => starts_anchored(inner),
Ast::Alt(items) => !items.is_empty() && items.iter().all(starts_anchored),
_ => false,
}
}
fn compile(ast: &Ast, prog: &mut Vec<Inst>) {
match ast {
Ast::Empty => {}
Ast::Char(m) => prog.push(Inst::Char(m.clone())),
Ast::Start => prog.push(Inst::Start),
Ast::End => prog.push(Inst::End),
Ast::Group(inner, index) => {
if let Some(i) = index {
prog.push(Inst::Save(2 * i));
compile(inner, prog);
prog.push(Inst::Save(2 * i + 1));
} else {
compile(inner, prog);
}
}
Ast::Concat(items) => items.iter().for_each(|a| compile(a, prog)),
Ast::Alt(items) => {
let mut jumps = Vec::new();
for (k, item) in items.iter().enumerate() {
if k + 1 < items.len() {
let split = prog.len();
prog.push(Inst::Split(split + 1, 0));
compile(item, prog);
jumps.push(prog.len());
prog.push(Inst::Jmp(0));
let next = prog.len();
prog[split] = Inst::Split(split + 1, next);
} else {
compile(item, prog);
}
}
let end = prog.len();
for j in jumps {
prog[j] = Inst::Jmp(end);
}
}
Ast::Repeat(inner, min, max, greedy) => {
for _ in 0..*min {
compile(inner, prog);
}
match max {
None => {
let split = prog.len();
prog.push(Inst::Split(0, 0));
compile(inner, prog);
prog.push(Inst::Jmp(split));
let out = prog.len();
prog[split] = if *greedy { Inst::Split(split + 1, out) } else { Inst::Split(out, split + 1) };
}
Some(max) => {
let mut splits = Vec::new();
for _ in *min..*max {
splits.push(prog.len());
prog.push(Inst::Split(0, 0));
compile(inner, prog);
}
let out = prog.len();
for s in splits {
prog[s] = if *greedy { Inst::Split(s + 1, out) } else { Inst::Split(out, s + 1) };
}
}
}
}
}
}
impl Parser<'_> {
fn peek(&self) -> Option<char> {
self.chars.get(self.i).copied()
}
fn err<T>(&self, what: &str) -> Result<T, PatternError> {
Err(PatternError(format!("{what} at {}", self.i)))
}
fn alt(&mut self) -> Result<Ast, PatternError> {
let mut items = vec![self.concat()?];
while self.peek() == Some('|') {
self.i += 1;
items.push(self.concat()?);
}
Ok(if items.len() == 1 { items.pop().unwrap_or(Ast::Empty) } else { Ast::Alt(items) })
}
fn concat(&mut self) -> Result<Ast, PatternError> {
let mut items = Vec::new();
while let Some(c) = self.peek() {
if c == '|' || c == ')' {
break;
}
let atom = self.atom()?;
let atom = self.quantified(atom)?;
items.push(atom);
}
Ok(Ast::Concat(items))
}
fn quantified(&mut self, atom: Ast) -> Result<Ast, PatternError> {
let (min, max) = match self.peek() {
Some('*') => {
self.i += 1;
(0, None)
}
Some('+') => {
self.i += 1;
(1, None)
}
Some('?') => {
self.i += 1;
(0, Some(1))
}
Some('{') => {
let save = self.i;
self.i += 1;
let Some(min) = self.number() else {
self.i = save;
return Ok(atom);
};
let max = if self.peek() == Some(',') {
self.i += 1;
if self.peek() == Some('}') { None } else { self.number() }
} else {
Some(min)
};
if self.peek() != Some('}') {
return self.err("bad repetition");
}
self.i += 1;
if max.is_some_and(|m| m < min) || min > 1000 || max.is_some_and(|m| m > 1000) {
return self.err("bad repetition");
}
(min, max)
}
_ => return Ok(atom),
};
let greedy = if self.peek() == Some('?') {
self.i += 1;
false
} else {
true
};
Ok(Ast::Repeat(Box::new(atom), min, max, greedy))
}
fn number(&mut self) -> Option<u32> {
let start = self.i;
let mut n: u32 = 0;
while let Some(c) = self.peek().filter(char::is_ascii_digit) {
n = n.saturating_mul(10).saturating_add(c as u32 - '0' as u32);
self.i += 1;
}
(self.i > start).then_some(n)
}
fn atom(&mut self) -> Result<Ast, PatternError> {
let Some(c) = self.peek() else { return self.err("unexpected end") };
self.i += 1;
match c {
'^' => Ok(Ast::Start),
'$' => Ok(Ast::End),
'.' => Ok(Ast::Char(Matcher::Class(vec![('\n', '\n')], true))),
'(' => {
let index = if self.chars[self.i..].starts_with(&['?', ':']) {
self.i += 2;
None
} else {
let g = self.groups;
self.groups += 1;
Some(g)
};
let inner = self.alt()?;
if self.peek() != Some(')') {
return self.err("unclosed group");
}
self.i += 1;
Ok(Ast::Group(Box::new(inner), index))
}
'[' => self.class(),
'\\' => {
let ranges = self.escape()?;
Ok(Ast::Char(ranges))
}
'*' | '+' | '?' => self.err("nothing to repeat"),
c => Ok(Ast::Char(Matcher::Char(c))),
}
}
fn escape(&mut self) -> Result<Matcher, PatternError> {
let Some(c) = self.peek() else { return self.err("trailing backslash") };
self.i += 1;
Ok(match c {
't' => Matcher::Char('\t'),
'n' => Matcher::Char('\n'),
'r' => Matcher::Char('\r'),
'v' => Matcher::Char('\u{b}'),
'f' => Matcher::Char('\u{c}'),
'w' => Matcher::Class(vec![('0', '9'), ('A', 'Z'), ('_', '_'), ('a', 'z')], false),
'd' => Matcher::Class(vec![('0', '9')], false),
's' => Matcher::Class(vec![('\t', '\n'), ('\u{c}', '\r'), (' ', ' ')], false),
'W' => Matcher::Class(vec![('0', '9'), ('A', 'Z'), ('_', '_'), ('a', 'z')], true),
'D' => Matcher::Class(vec![('0', '9')], true),
'S' => Matcher::Class(vec![('\t', '\n'), ('\u{c}', '\r'), (' ', ' ')], true),
'x' => {
if self.peek() != Some('{') {
return self.err("bad \\x");
}
self.i += 1;
let mut v: u32 = 0;
while let Some(d) = self.peek().and_then(|d| d.to_digit(16)) {
v = v.saturating_mul(16).saturating_add(d);
self.i += 1;
}
if self.peek() != Some('}') {
return self.err("bad \\x");
}
self.i += 1;
match char::from_u32(v) {
Some(ch) => Matcher::Char(ch),
None => return self.err("bad \\x"),
}
}
c if c.is_ascii_punctuation() => Matcher::Char(c),
_ => return self.err("unknown escape"),
})
}
fn class(&mut self) -> Result<Ast, PatternError> {
let negated = self.peek() == Some('^');
if negated {
self.i += 1;
}
let mut ranges = Vec::new();
let mut first = true;
loop {
let Some(c) = self.peek() else { return self.err("unclosed class") };
if c == ']' && !first {
self.i += 1;
break;
}
first = false;
self.i += 1;
let lo = if c == '\\' {
match self.escape()? {
Matcher::Char(ch) => ch,
Matcher::Class(rs, false) => {
ranges.extend(rs);
continue;
}
Matcher::Class(rs, true) => {
ranges.extend(complement(rs));
continue;
}
}
} else {
c
};
if self.peek() == Some('-') && self.chars.get(self.i + 1).is_some_and(|&n| n != ']') {
self.i += 1;
let Some(h) = self.peek() else { return self.err("unclosed class") };
self.i += 1;
let hi = if h == '\\' {
match self.escape()? {
Matcher::Char(ch) => ch,
Matcher::Class(..) => return self.err("bad range"),
}
} else {
h
};
if hi < lo {
return self.err("bad range");
}
ranges.push((lo, hi));
} else {
ranges.push((lo, lo));
}
}
Ok(Ast::Char(Matcher::Class(ranges, negated)))
}
}
fn complement(mut ranges: Vec<(char, char)>) -> Vec<(char, char)> {
ranges.sort_unstable();
let mut out = Vec::new();
let mut next = 0u32;
for (lo, hi) in ranges {
if (lo as u32) > next
&& let (Some(a), Some(b)) = (char::from_u32(next), char::from_u32(lo as u32 - 1))
{
out.push((a, b));
}
next = next.max(hi as u32 + 1);
}
if let Some(a) = char::from_u32(next) {
out.push((a, char::MAX));
}
out
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn matches_like_re2() {
let p = Pattern::must(r"^(\*\*)?(MUST NOT|MUST)(?:\[([^\]\s]*)\])?:(\*\*)?[ \t]+(\S.*)$".replace(r"\S", r"[^\s]").as_str());
let c = p.captures("**MUST NOT[x]:** go").unwrap();
assert_eq!(c.get("**MUST NOT[x]:** go", 2), Some("MUST NOT"));
assert_eq!(c.get("**MUST NOT[x]:** go", 3), Some("x"));
assert_eq!(c.get("**MUST NOT[x]:** go", 5), Some("go"));
assert!(Pattern::must("^sha256:[0-9a-f]{64}$").is_match(&format!("sha256:{}", "a".repeat(64))));
assert!(!Pattern::must("^sha256:[0-9a-f]{64}$").is_match(&format!("sha256:{}", "a".repeat(63))));
let lazy = Pattern::must(r"^#{1,6}[ \t].*?[ \t](\{[^{}]*\})[ \t]*$");
assert_eq!(lazy.captures("## A {x} b {#id}").and_then(|c| c.get("## A {x} b {#id}", 1).map(String::from)), Some("{#id}".into()));
assert_eq!(Pattern::must("`+").find_iter("a `` b ` c"), vec![(2, 4), (7, 8)]);
assert!(Pattern::must("(?i)^https?://x$").is_match("HTTPS://X"));
let nested = Pattern::must(r"^(?:/(?:[^~]|~[01])*)*$");
assert!(!nested.is_match(&format!("{}~x", "/".repeat(5000))));
assert_eq!(Pattern::must("a|ab").find("ab"), Some((0, 1)));
assert!(Pattern::must(r"\S").is_match(" x "));
assert!(!Pattern::must(r"\S").is_match(" \t\n"));
assert!(Pattern::must(r"^[\D]+$").is_match("ab"));
assert!(!Pattern::must(r"^[\D]+$").is_match("a1"));
assert!(Pattern::must(r"^\W\w$").is_match("-a"));
assert!(!Pattern::must(r"^\W$").is_match("_"));
}
}