1use std::fmt;
11
12#[derive(Clone)]
14pub struct Pattern {
15 source: String,
16 prog: Vec<Inst>,
17 groups: usize,
18 fold: bool,
19 anchored: bool,
21}
22
23impl fmt::Debug for Pattern {
24 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
25 write!(f, "Pattern({:?})", self.source)
26 }
27}
28
29impl PartialEq for Pattern {
30 fn eq(&self, other: &Self) -> bool {
31 self.source == other.source
32 }
33}
34
35#[derive(Clone, Debug)]
36enum Matcher {
37 Char(char),
38 Class(Vec<(char, char)>, bool),
39}
40
41#[derive(Clone, Debug)]
42enum Inst {
43 Char(Matcher),
44 Split(usize, usize),
45 Jmp(usize),
46 Save(usize),
47 Start,
48 End,
49 Match,
50}
51
52#[derive(Clone, Debug)]
53enum Ast {
54 Empty,
55 Char(Matcher),
56 Start,
57 End,
58 Group(Box<Ast>, Option<usize>),
59 Concat(Vec<Ast>),
60 Alt(Vec<Ast>),
61 Repeat(Box<Ast>, u32, Option<u32>, bool),
62}
63
64#[derive(Clone, Debug)]
66pub struct Captures {
67 slots: Vec<Option<usize>>,
68}
69
70impl Captures {
71 pub fn span(&self, i: usize) -> Option<(usize, usize)> {
73 match (self.slots.get(2 * i).copied().flatten(), self.slots.get(2 * i + 1).copied().flatten()) {
74 (Some(a), Some(b)) if a <= b => Some((a, b)),
75 _ => None,
76 }
77 }
78
79 pub fn get<'t>(&self, text: &'t str, i: usize) -> Option<&'t str> {
81 self.span(i).and_then(|(a, b)| text.get(a..b))
82 }
83
84 pub fn whole(&self) -> (usize, usize) {
86 self.span(0).unwrap_or((0, 0))
87 }
88}
89
90struct Parser<'a> {
91 chars: Vec<char>,
92 i: usize,
93 groups: usize,
94 fold: bool,
95 _src: &'a str,
96}
97
98#[derive(Clone, Debug, PartialEq, Eq)]
100pub struct PatternError(pub String);
101
102impl fmt::Display for PatternError {
103 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
104 f.write_str(&self.0)
105 }
106}
107
108impl Pattern {
109 pub fn new(source: &str) -> Result<Pattern, PatternError> {
111 let mut p = Parser { chars: source.chars().collect(), i: 0, groups: 1, fold: false, _src: source };
112 if p.chars.starts_with(&['(', '?', 'i', ')']) {
113 p.fold = true;
114 p.i = 4;
115 }
116 let ast = p.alt()?;
117 if p.i != p.chars.len() {
118 return Err(PatternError(format!("unexpected {:?} in {source}", p.chars[p.i])));
119 }
120 let mut prog = vec![Inst::Save(0)];
121 compile(&ast, &mut prog);
122 prog.push(Inst::Save(1));
123 prog.push(Inst::Match);
124 let anchored = starts_anchored(&ast);
125 Ok(Pattern { source: source.to_string(), prog, groups: p.groups, fold: p.fold, anchored })
126 }
127
128 pub(crate) fn must(source: &str) -> Pattern {
130 match Pattern::new(source) {
131 Ok(p) => p,
132 Err(e) => Pattern::never(&e.0),
134 }
135 }
136
137 fn never(source: &str) -> Pattern {
139 Pattern {
140 source: source.to_string(),
141 prog: vec![Inst::Char(Matcher::Class(Vec::new(), false)), Inst::Match],
142 groups: 1,
143 fold: false,
144 anchored: false,
145 }
146 }
147
148 pub fn as_str(&self) -> &str {
150 &self.source
151 }
152
153 pub fn is_match(&self, text: &str) -> bool {
155 self.run(text, 0, 0, true).is_some()
156 }
157
158 pub fn find(&self, text: &str) -> Option<(usize, usize)> {
160 self.captures_at(text, 0).map(|c| c.whole())
161 }
162
163 pub fn find_str<'t>(&self, text: &'t str) -> Option<&'t str> {
165 self.find(text).and_then(|(a, b)| text.get(a..b))
166 }
167
168 pub fn captures(&self, text: &str) -> Option<Captures> {
170 self.captures_at(text, 0)
171 }
172
173 pub fn find_iter(&self, text: &str) -> Vec<(usize, usize)> {
175 self.captures_iter(text).iter().map(Captures::whole).collect()
176 }
177
178 pub fn captures_iter(&self, text: &str) -> Vec<Captures> {
180 let mut out = Vec::new();
181 let mut at = 0;
182 while at <= text.len() {
183 let Some(c) = self.captures_at(text, at) else { break };
184 let (a, b) = c.whole();
185 out.push(c);
186 at = if b > a {
187 b
188 } else {
189 match text[b..].chars().next() {
190 Some(ch) => b + ch.len_utf8(),
191 None => break,
192 }
193 };
194 }
195 out
196 }
197
198 pub fn replace_all(&self, text: &str, mut f: impl FnMut(&Captures) -> String) -> String {
200 let mut out = String::with_capacity(text.len());
201 let mut last = 0;
202 for c in self.captures_iter(text) {
203 let (a, b) = c.whole();
204 out.push_str(&text[last..a]);
205 out.push_str(&f(&c));
206 last = b;
207 }
208 out.push_str(&text[last..]);
209 out
210 }
211
212 pub fn captures_at(&self, text: &str, start: usize) -> Option<Captures> {
214 self.run(text, start, self.groups * 2, false).map(|slots| Captures { slots })
215 }
216
217 fn run(&self, text: &str, start: usize, slots: usize, any: bool) -> Option<Vec<Option<usize>>> {
220 if start > text.len() || !text.is_char_boundary(start) || self.anchored && start > 0 {
221 return None;
222 }
223 let n = self.prog.len();
224 let mut clist = Threads::new(n);
225 let mut nlist = Threads::new(n);
226 let mut matched: Option<Vec<Option<usize>>> = None;
227 let mut pos = start;
228 loop {
229 if matched.is_none() && (!self.anchored || pos == 0) {
230 self.add(&mut clist, 0, pos, text, vec![None; slots]);
231 }
232 if clist.list.is_empty() {
233 break;
234 }
235 let ch = text[pos..].chars().next();
236 let next = pos + ch.map_or(0, char::len_utf8);
237 nlist.clear();
238 let threads = std::mem::take(&mut clist.list);
239 for (pc, caps) in threads {
240 match &self.prog[pc] {
241 Inst::Char(m) => {
242 if let Some(c) = ch
243 && self.matches(m, c)
244 {
245 self.add(&mut nlist, pc + 1, next, text, caps);
246 }
247 }
248 Inst::Match => {
249 matched = Some(caps);
250 if any {
251 return matched;
252 }
253 break;
254 }
255 _ => {}
256 }
257 }
258 std::mem::swap(&mut clist, &mut nlist);
259 if ch.is_none() {
260 break;
261 }
262 pos = next;
263 }
264 matched
265 }
266
267 fn matches(&self, m: &Matcher, c: char) -> bool {
268 let fold = self.fold;
269 match m {
270 Matcher::Char(x) => *x == c || fold && x.eq_ignore_ascii_case(&c),
271 Matcher::Class(ranges, negated) => {
272 let hit = |c: char| ranges.iter().any(|&(a, b)| a <= c && c <= b);
273 let mut found = hit(c);
274 if !found && fold && c.is_ascii_alphabetic() {
275 found = hit(c.to_ascii_lowercase()) || hit(c.to_ascii_uppercase());
276 }
277 found != *negated
278 }
279 }
280 }
281
282 fn add(&self, list: &mut Threads, pc: usize, pos: usize, text: &str, mut caps: Vec<Option<usize>>) {
284 let mut stack: Vec<(usize, Restore)> = vec![(pc, None)];
285 while let Some((pc, restore)) = stack.pop() {
287 if let Some((slot, old)) = restore {
288 caps[slot] = old;
289 continue;
290 }
291 if list.seen[pc] == list.generation {
292 continue;
293 }
294 list.seen[pc] = list.generation;
295 match &self.prog[pc] {
296 Inst::Jmp(t) => stack.push((*t, None)),
297 Inst::Split(a, b) => {
298 stack.push((*b, None));
299 stack.push((*a, None));
300 }
301 Inst::Save(slot) => {
302 if *slot < caps.len() {
303 let old = caps[*slot];
304 caps[*slot] = Some(pos);
305 stack.push((0, Some((*slot, old))));
306 stack.push((pc + 1, None));
307 } else {
308 stack.push((pc + 1, None));
309 }
310 }
311 Inst::Start => {
312 if pos == 0 {
313 stack.push((pc + 1, None));
314 }
315 }
316 Inst::End => {
317 if pos == text.len() {
318 stack.push((pc + 1, None));
319 }
320 }
321 Inst::Char(_) | Inst::Match => list.list.push((pc, caps.clone())),
322 }
323 }
324 }
325}
326
327type Restore = Option<(usize, Option<usize>)>;
329
330struct Threads {
331 seen: Vec<u32>,
333 generation: u32,
334 list: Vec<(usize, Vec<Option<usize>>)>,
335}
336
337impl Threads {
338 fn new(n: usize) -> Threads {
339 Threads { seen: vec![0; n], generation: 1, list: Vec::new() }
340 }
341 fn clear(&mut self) {
342 self.generation = self.generation.wrapping_add(1);
343 if self.generation == 0 {
344 self.seen.iter_mut().for_each(|s| *s = 0);
345 self.generation = 1;
346 }
347 self.list.clear();
348 }
349}
350
351fn starts_anchored(ast: &Ast) -> bool {
353 match ast {
354 Ast::Start => true,
355 Ast::Concat(items) => items.first().is_some_and(starts_anchored),
356 Ast::Group(inner, _) => starts_anchored(inner),
357 Ast::Alt(items) => !items.is_empty() && items.iter().all(starts_anchored),
358 _ => false,
359 }
360}
361
362fn compile(ast: &Ast, prog: &mut Vec<Inst>) {
363 match ast {
364 Ast::Empty => {}
365 Ast::Char(m) => prog.push(Inst::Char(m.clone())),
366 Ast::Start => prog.push(Inst::Start),
367 Ast::End => prog.push(Inst::End),
368 Ast::Group(inner, index) => {
369 if let Some(i) = index {
370 prog.push(Inst::Save(2 * i));
371 compile(inner, prog);
372 prog.push(Inst::Save(2 * i + 1));
373 } else {
374 compile(inner, prog);
375 }
376 }
377 Ast::Concat(items) => items.iter().for_each(|a| compile(a, prog)),
378 Ast::Alt(items) => {
379 let mut jumps = Vec::new();
380 for (k, item) in items.iter().enumerate() {
381 if k + 1 < items.len() {
382 let split = prog.len();
383 prog.push(Inst::Split(split + 1, 0));
384 compile(item, prog);
385 jumps.push(prog.len());
386 prog.push(Inst::Jmp(0));
387 let next = prog.len();
388 prog[split] = Inst::Split(split + 1, next);
389 } else {
390 compile(item, prog);
391 }
392 }
393 let end = prog.len();
394 for j in jumps {
395 prog[j] = Inst::Jmp(end);
396 }
397 }
398 Ast::Repeat(inner, min, max, greedy) => {
399 for _ in 0..*min {
400 compile(inner, prog);
401 }
402 match max {
403 None => {
404 let split = prog.len();
405 prog.push(Inst::Split(0, 0));
406 compile(inner, prog);
407 prog.push(Inst::Jmp(split));
408 let out = prog.len();
409 prog[split] = if *greedy { Inst::Split(split + 1, out) } else { Inst::Split(out, split + 1) };
410 }
411 Some(max) => {
412 let mut splits = Vec::new();
413 for _ in *min..*max {
414 splits.push(prog.len());
415 prog.push(Inst::Split(0, 0));
416 compile(inner, prog);
417 }
418 let out = prog.len();
419 for s in splits {
420 prog[s] = if *greedy { Inst::Split(s + 1, out) } else { Inst::Split(out, s + 1) };
421 }
422 }
423 }
424 }
425 }
426}
427
428impl Parser<'_> {
429 fn peek(&self) -> Option<char> {
430 self.chars.get(self.i).copied()
431 }
432
433 fn err<T>(&self, what: &str) -> Result<T, PatternError> {
434 Err(PatternError(format!("{what} at {}", self.i)))
435 }
436
437 fn alt(&mut self) -> Result<Ast, PatternError> {
438 let mut items = vec![self.concat()?];
439 while self.peek() == Some('|') {
440 self.i += 1;
441 items.push(self.concat()?);
442 }
443 Ok(if items.len() == 1 { items.pop().unwrap_or(Ast::Empty) } else { Ast::Alt(items) })
444 }
445
446 fn concat(&mut self) -> Result<Ast, PatternError> {
447 let mut items = Vec::new();
448 while let Some(c) = self.peek() {
449 if c == '|' || c == ')' {
450 break;
451 }
452 let atom = self.atom()?;
453 let atom = self.quantified(atom)?;
454 items.push(atom);
455 }
456 Ok(Ast::Concat(items))
457 }
458
459 fn quantified(&mut self, atom: Ast) -> Result<Ast, PatternError> {
460 let (min, max) = match self.peek() {
461 Some('*') => {
462 self.i += 1;
463 (0, None)
464 }
465 Some('+') => {
466 self.i += 1;
467 (1, None)
468 }
469 Some('?') => {
470 self.i += 1;
471 (0, Some(1))
472 }
473 Some('{') => {
474 let save = self.i;
475 self.i += 1;
476 let Some(min) = self.number() else {
477 self.i = save;
478 return Ok(atom);
479 };
480 let max = if self.peek() == Some(',') {
481 self.i += 1;
482 if self.peek() == Some('}') { None } else { self.number() }
483 } else {
484 Some(min)
485 };
486 if self.peek() != Some('}') {
487 return self.err("bad repetition");
488 }
489 self.i += 1;
490 if max.is_some_and(|m| m < min) || min > 1000 || max.is_some_and(|m| m > 1000) {
491 return self.err("bad repetition");
492 }
493 (min, max)
494 }
495 _ => return Ok(atom),
496 };
497 let greedy = if self.peek() == Some('?') {
498 self.i += 1;
499 false
500 } else {
501 true
502 };
503 Ok(Ast::Repeat(Box::new(atom), min, max, greedy))
504 }
505
506 fn number(&mut self) -> Option<u32> {
507 let start = self.i;
508 let mut n: u32 = 0;
509 while let Some(c) = self.peek().filter(char::is_ascii_digit) {
510 n = n.saturating_mul(10).saturating_add(c as u32 - '0' as u32);
511 self.i += 1;
512 }
513 (self.i > start).then_some(n)
514 }
515
516 fn atom(&mut self) -> Result<Ast, PatternError> {
517 let Some(c) = self.peek() else { return self.err("unexpected end") };
518 self.i += 1;
519 match c {
520 '^' => Ok(Ast::Start),
521 '$' => Ok(Ast::End),
522 '.' => Ok(Ast::Char(Matcher::Class(vec![('\n', '\n')], true))),
523 '(' => {
524 let index = if self.chars[self.i..].starts_with(&['?', ':']) {
525 self.i += 2;
526 None
527 } else {
528 let g = self.groups;
529 self.groups += 1;
530 Some(g)
531 };
532 let inner = self.alt()?;
533 if self.peek() != Some(')') {
534 return self.err("unclosed group");
535 }
536 self.i += 1;
537 Ok(Ast::Group(Box::new(inner), index))
538 }
539 '[' => self.class(),
540 '\\' => {
541 let ranges = self.escape()?;
542 Ok(Ast::Char(ranges))
543 }
544 '*' | '+' | '?' => self.err("nothing to repeat"),
545 c => Ok(Ast::Char(Matcher::Char(c))),
546 }
547 }
548
549 fn escape(&mut self) -> Result<Matcher, PatternError> {
551 let Some(c) = self.peek() else { return self.err("trailing backslash") };
552 self.i += 1;
553 Ok(match c {
554 't' => Matcher::Char('\t'),
555 'n' => Matcher::Char('\n'),
556 'r' => Matcher::Char('\r'),
557 'v' => Matcher::Char('\u{b}'),
558 'f' => Matcher::Char('\u{c}'),
559 'w' => Matcher::Class(vec![('0', '9'), ('A', 'Z'), ('_', '_'), ('a', 'z')], false),
560 'd' => Matcher::Class(vec![('0', '9')], false),
561 's' => Matcher::Class(vec![('\t', '\n'), ('\u{c}', '\r'), (' ', ' ')], false),
562 'W' => Matcher::Class(vec![('0', '9'), ('A', 'Z'), ('_', '_'), ('a', 'z')], true),
563 'D' => Matcher::Class(vec![('0', '9')], true),
564 'S' => Matcher::Class(vec![('\t', '\n'), ('\u{c}', '\r'), (' ', ' ')], true),
565 'x' => {
566 if self.peek() != Some('{') {
567 return self.err("bad \\x");
568 }
569 self.i += 1;
570 let mut v: u32 = 0;
571 while let Some(d) = self.peek().and_then(|d| d.to_digit(16)) {
572 v = v.saturating_mul(16).saturating_add(d);
573 self.i += 1;
574 }
575 if self.peek() != Some('}') {
576 return self.err("bad \\x");
577 }
578 self.i += 1;
579 match char::from_u32(v) {
580 Some(ch) => Matcher::Char(ch),
581 None => return self.err("bad \\x"),
582 }
583 }
584 c if c.is_ascii_punctuation() => Matcher::Char(c),
585 _ => return self.err("unknown escape"),
586 })
587 }
588
589 fn class(&mut self) -> Result<Ast, PatternError> {
590 let negated = self.peek() == Some('^');
591 if negated {
592 self.i += 1;
593 }
594 let mut ranges = Vec::new();
595 let mut first = true;
596 loop {
597 let Some(c) = self.peek() else { return self.err("unclosed class") };
598 if c == ']' && !first {
599 self.i += 1;
600 break;
601 }
602 first = false;
603 self.i += 1;
604 let lo = if c == '\\' {
605 match self.escape()? {
606 Matcher::Char(ch) => ch,
607 Matcher::Class(rs, false) => {
608 ranges.extend(rs);
609 continue;
610 }
611 Matcher::Class(rs, true) => {
613 ranges.extend(complement(rs));
614 continue;
615 }
616 }
617 } else {
618 c
619 };
620 if self.peek() == Some('-') && self.chars.get(self.i + 1).is_some_and(|&n| n != ']') {
621 self.i += 1;
622 let Some(h) = self.peek() else { return self.err("unclosed class") };
623 self.i += 1;
624 let hi = if h == '\\' {
625 match self.escape()? {
626 Matcher::Char(ch) => ch,
627 Matcher::Class(..) => return self.err("bad range"),
628 }
629 } else {
630 h
631 };
632 if hi < lo {
633 return self.err("bad range");
634 }
635 ranges.push((lo, hi));
636 } else {
637 ranges.push((lo, lo));
638 }
639 }
640 Ok(Ast::Char(Matcher::Class(ranges, negated)))
641 }
642}
643
644fn complement(mut ranges: Vec<(char, char)>) -> Vec<(char, char)> {
646 ranges.sort_unstable();
647 let mut out = Vec::new();
648 let mut next = 0u32;
649 for (lo, hi) in ranges {
650 if (lo as u32) > next
651 && let (Some(a), Some(b)) = (char::from_u32(next), char::from_u32(lo as u32 - 1))
652 {
653 out.push((a, b));
654 }
655 next = next.max(hi as u32 + 1);
656 }
657 if let Some(a) = char::from_u32(next) {
658 out.push((a, char::MAX));
659 }
660 out
661}
662
663#[cfg(test)]
664mod tests {
665 use super::*;
666
667 #[test]
668 fn matches_like_re2() {
669 let p = Pattern::must(r"^(\*\*)?(MUST NOT|MUST)(?:\[([^\]\s]*)\])?:(\*\*)?[ \t]+(\S.*)$".replace(r"\S", r"[^\s]").as_str());
670 let c = p.captures("**MUST NOT[x]:** go").unwrap();
671 assert_eq!(c.get("**MUST NOT[x]:** go", 2), Some("MUST NOT"));
672 assert_eq!(c.get("**MUST NOT[x]:** go", 3), Some("x"));
673 assert_eq!(c.get("**MUST NOT[x]:** go", 5), Some("go"));
674 assert!(Pattern::must("^sha256:[0-9a-f]{64}$").is_match(&format!("sha256:{}", "a".repeat(64))));
675 assert!(!Pattern::must("^sha256:[0-9a-f]{64}$").is_match(&format!("sha256:{}", "a".repeat(63))));
676 let lazy = Pattern::must(r"^#{1,6}[ \t].*?[ \t](\{[^{}]*\})[ \t]*$");
677 assert_eq!(lazy.captures("## A {x} b {#id}").and_then(|c| c.get("## A {x} b {#id}", 1).map(String::from)), Some("{#id}".into()));
678 assert_eq!(Pattern::must("`+").find_iter("a `` b ` c"), vec![(2, 4), (7, 8)]);
679 assert!(Pattern::must("(?i)^https?://x$").is_match("HTTPS://X"));
680 let nested = Pattern::must(r"^(?:/(?:[^~]|~[01])*)*$");
681 assert!(!nested.is_match(&format!("{}~x", "/".repeat(5000))));
682 assert_eq!(Pattern::must("a|ab").find("ab"), Some((0, 1)));
683 assert!(Pattern::must(r"\S").is_match(" x "));
685 assert!(!Pattern::must(r"\S").is_match(" \t\n"));
686 assert!(Pattern::must(r"^[\D]+$").is_match("ab"));
687 assert!(!Pattern::must(r"^[\D]+$").is_match("a1"));
688 assert!(Pattern::must(r"^\W\w$").is_match("-a"));
689 assert!(!Pattern::must(r"^\W$").is_match("_"));
690 }
691}