Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_text/src/regex.rs

66.9 KiB, 3 runs

created by r1870400018:20957, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! A backtracking regular-expression engine with the syntax of the Rust `regex` crate.
2//!
3//! The syntax, and the meaning given to it, follow the `regex` crate because that is what Typst's
4//! `regex(...)` compiles with, and a document's `show regex(...)` rules and `str.matches`,
5//! `str.replace` and `str.split` calls must mean here what they mean there. Supported: literals
6//! and the escapes `\n \t \r \a \f \v \x7F \x{...} \u0041 \u{...} \U0001F600 \U{...}`; `.`;
7//! bracketed classes with ranges, nesting, the ASCII classes `[[:alpha:]]` and the set operations
8//! `&&`, `--` and `~~`; the Unicode shorthands `\d \w \s` and their negations; Unicode property
9//! classes `\pL`, `\p{Greek}`, `\p{sc=Grek}`, `\p{scx=Grek}`, `\p{gc!=L}` and `\P{...}` (see
10//! [`crate::unicode::property`]); the anchors `^ $ \A \z` and the word boundaries
11//! `\b \B \< \> \b{start} \b{end} \b{start-half} \b{end-half}`; numbered and named capture groups,
12//! `(...)`, `(?P<name>...)` and `(?<name>...)`, and non-capturing `(?:...)`; the flags `i m s x U`
13//! set inline as `(?im)` or scoped as `(?i:...)`, and cleared with `-`; alternation; and the
14//! quantifiers `* + ? {n} {n,} {n,m}`, greedy or lazy.
15//!
16//! As in the `regex` crate, `\d`, `\w`, `\s` and `\b` are Unicode-aware, `^` and `$` match only at
17//! the ends of the haystack unless `m` is set, alternation is leftmost-first, and an iteration
18//! never yields an empty match where the previous match ended. Absent, as there: backreferences
19//! and look-around. A `{` that does not open a counted repetition is taken literally, where the
20//! `regex` crate refuses it.
21//!
22//! The matcher is a backtracker over a compiled program, built as the `regex` crate's own
23//! bounded backtracker is: the pattern compiles to a small instruction graph of the same shape as
24//! the crate's NFA, the choice points live on a heap stack rather than the call stack, and a
25//! visited set lets each (instruction, position) pair be explored at most once per search. So a
26//! search costs time linear in the pattern times the text -- `(a+)+$` answers rather than running
27//! away -- no text is long enough to overflow the stack, and where a repetition could loop on an
28//! empty iteration the visited set ends it exactly where the crate's does, which decides the
29//! captures `(a*)*` reports. The visited set is a bit per pair, so a search whose pattern and
30//! text together would need more than [`MAX_VISITED`] bits is refused with an error rather than
31//! answered wrongly.
32//!
33//! ```
34//! use oxedyne_fe2o3_text::regex::Regex;
35//!
36//! let re = Regex::new(r"(?<word>\p{Greek}+)\s(\d+)").expect("compile");
37//! let caps = re.captures("see λόγος 12").expect("search").expect("a match");
38//! assert_eq!(caps.name_text("word"), Some("λόγος"));
39//! assert_eq!(caps.text(2), Some("12"));
40//! assert_eq!(re.replace_all("λόγος 12", "$2 ${word}").expect("replace"), "12 λόγος");
41//! ```
42
43use crate::unicode::property::{
44 self,
45 CharClass,
46};
47
48use oxedyne_fe2o3_core::prelude::*;
49
50
51// Limits
52pub const MAX_VISITED: usize = 1 << 28; // visited-set bits, instructions x characters: 32 MiB
53const MAX_INSTS: usize = 1 << 18; // compiled instructions; `(a{100}){100}` is 10,000
54const MAX_REPEAT: u32 = 10_000; // largest count a `{n,m}` may name
55
56
57/// A half-open byte range within the haystack.
58#[derive(Clone, Copy, Debug, Eq, PartialEq)]
59pub struct Span {
60 pub start: usize,
61 pub end: usize,
62}
63
64impl Span {
65
66 pub fn len(&self) -> usize { self.end - self.start }
67
68 pub fn is_empty(&self) -> bool { self.start == self.end }
69
70 /// The text of the span within the haystack it was found in.
71 pub fn as_str<'h>(&self, hay: &'h str) -> &'h str {
72 hay.get(self.start..self.end).unwrap_or("")
73 }
74}
75
76/// How two operands of a class set operation combine.
77#[derive(Clone, Copy, Debug, Eq, PartialEq)]
78enum SetOp {
79 And, // `&&`
80 Minus, // `--`
81 Xor, // `~~`
82}
83
84/// One item inside a character class.
85#[derive(Clone, Debug, Eq, PartialEq)]
86enum Item {
87 Ch(char),
88 Range(char, char), // inclusive, low first
89 Digit(bool), // `\d` when true, `\D` when false
90 Word(bool),
91 Space(bool),
92 Prop(CharClass, bool), // `\p{..}` when true, `\P{..}` when false
93 Nested(Class),
94}
95
96/// The contents of a class: a union of items, or a set operation on two such contents.
97#[derive(Clone, Debug, Eq, PartialEq)]
98enum Set {
99 Union(Vec<Item>),
100 Op(Box<Set>, SetOp, Box<Set>),
101}
102
103/// A bracketed class, `[...]` or `[^...]`, or a shorthand standing alone.
104#[derive(Clone, Debug, Eq, PartialEq)]
105struct Class {
106 neg: bool,
107 ci: bool, // case-insensitive
108 set: Set,
109}
110
111/// A zero-width assertion.
112#[derive(Clone, Copy, Debug, Eq, PartialEq)]
113enum Look {
114 Start, // `\A`, or `^` without `m`
115 End, // `\z`, or `$` without `m`
116 LineStart,
117 LineEnd,
118 Word, // `\b`
119 NotWord, // `\B`
120 WordStart, // `\<`, `\b{start}`
121 WordEnd, // `\>`, `\b{end}`
122 WordStartHalf,
123 WordEndHalf,
124}
125
126/// One node of the parsed pattern.
127///
128/// An enum rather than a trait object, per the house style: the matcher is one `match` and the
129/// whole tree is a plain value that can be cloned, compared and printed.
130#[derive(Clone, Debug, Eq, PartialEq)]
131enum Node {
132 Lit(char),
133 LitCi(char), // already case-folded
134 Any, // any character bar a newline
135 AnyNl, // any character at all, under `s`
136 Cls(Class),
137 Look(Look),
138 Group(usize, Box<Node>),
139 Seq(Vec<Node>),
140 Alt(Vec<Node>), // the first alternative that matches, in written order
141 Rep {
142 node: Box<Node>,
143 min: u32,
144 max: u32,
145 greedy: bool,
146 },
147}
148
149/// One instruction of a compiled pattern. Control passes to the next instruction unless the
150/// instruction names another.
151#[derive(Clone, Debug)]
152enum Inst {
153 Char(char),
154 CharCi(char), // already case-folded
155 Any,
156 AnyNl,
157 Class(Class),
158 Look(Look),
159 Save(usize), // record the position in a capture slot
160 Split(usize, usize), // try the first, then the second
161 Jmp(usize),
162 Match,
163}
164
165/// A pending piece of backtracking work.
166enum Frame {
167 Step(usize, usize), // resume at instruction, position
168 Restore(usize, Option<usize>), // put a capture slot back as it was
169}
170
171/// Capture spans as character indices, group 0 being the whole match.
172type Slots = Vec<Option<(usize, usize)>>;
173
174/// The (instruction, position) pairs a search has explored, a bit each, laid out position by
175/// position so that the pairs one search touched form one run to clear for the next.
176struct Visited {
177 bits: Vec<u64>,
178 ninst: usize,
179 base: usize, // first character position covered
180 lo: usize, // lowest position touched since the last clear
181 hi: usize, // one past the highest
182}
183
184impl Visited {
185
186 fn new(ninst: usize, base: usize, len: usize, src: &str) -> Outcome<Self> {
187 let width = len.saturating_sub(base) + 1;
188 let n = match ninst.checked_mul(width) {
189 Some(n) if n <= MAX_VISITED => n,
190 _ => return Err(err!(
191 "regex '{}': a pattern of {} instructions over {} characters needs more than {} \
192 bits of search state; search a shorter text.", src, ninst, width, MAX_VISITED;
193 Excessive, Input)),
194 };
195 Ok(Self { bits: vec![0; (n + 63) / 64], ninst, base, lo: usize::MAX, hi: 0 })
196 }
197
198 /// Marks a pair, answering whether it was new.
199 fn insert(&mut self, pc: usize, at: usize) -> bool {
200 let i = (at - self.base) * self.ninst + pc;
201 let bit = 1u64 << (i % 64);
202 match self.bits.get_mut(i / 64) {
203 Some(w) if *w & bit == 0 => {
204 *w |= bit;
205 self.lo = self.lo.min(at);
206 self.hi = self.hi.max(at + 1);
207 true
208 }
209 _ => false,
210 }
211 }
212
213 fn clear(&mut self) {
214 if self.lo < self.hi {
215 let a = (self.lo - self.base) * self.ninst / 64;
216 let b = (((self.hi - self.base) * self.ninst + 63) / 64).min(self.bits.len());
217 if let Some(ws) = self.bits.get_mut(a..b) {
218 for w in ws {
219 *w = 0;
220 }
221 }
222 }
223 self.lo = usize::MAX;
224 self.hi = 0;
225 }
226}
227
228/// A haystack decoded once, so a run of searches over it does not decode it again.
229struct Hay<'h> {
230 text: &'h str,
231 chars: Vec<char>,
232 offs: Vec<usize>, // byte offset of each character, and of the end
233}
234
235impl<'h> Hay<'h> {
236
237 fn new(text: &'h str) -> Self {
238 let chars: Vec<char> = text.chars().collect();
239 let mut offs = Vec::with_capacity(chars.len() + 1);
240 for (b, _) in text.char_indices() {
241 offs.push(b);
242 }
243 offs.push(text.len());
244 Self { text, chars, offs }
245 }
246
247 /// The character index at byte offset `b`, which must fall on a character boundary.
248 fn index(&self, b: usize) -> Outcome<usize> {
249 match self.offs.binary_search(&b) {
250 Ok(i) => Ok(i),
251 Err(_) => Err(err!(
252 "regex: search start {} is not a character boundary of a {} byte haystack.",
253 b, self.text.len(); Invalid, Input, Range)),
254 }
255 }
256
257 fn span(&self, (s, e): (usize, usize)) -> Span {
258 Span {
259 start: self.offs.get(s).copied().unwrap_or(self.text.len()),
260 end: self.offs.get(e).copied().unwrap_or(self.text.len()),
261 }
262 }
263}
264
265/// A compiled regular expression.
266#[derive(Clone, Debug)]
267pub struct Regex {
268 prog: Vec<Inst>,
269 names: Vec<Option<String>>, // one per group, group 0 included and unnamed
270 src: String,
271}
272
273impl Regex {
274
275 pub fn new(pattern: &str) -> Outcome<Self> {
276 Self::with_case(pattern, false)
277 }
278
279 /// Compiles a pattern, case-insensitive from the start when `ci` is set, as though it began
280 /// with `(?i)`.
281 pub fn with_case(pattern: &str, ci: bool) -> Outcome<Self> {
282 let chars: Vec<char> = pattern.chars().collect();
283 let mut p = Parser {
284 pat: &chars,
285 at: 0,
286 flags: Flags { i: ci, ..Flags::default() },
287 names: vec![None],
288 };
289 let root = match p.alt() {
290 Ok(n) => n,
291 Err(e) => return Err(err!(e,
292 "regex '{}': could not be compiled, at character {}.", pattern, p.at + 1;
293 Invalid, Input)),
294 };
295 if p.at < p.pat.len() {
296 if p.pat[p.at] == ')' {
297 return Err(err!(
298 "regex '{}': ')' with no '(' before it, at character {}.", pattern, p.at + 1;
299 Invalid, Input));
300 }
301 return Err(err!(
302 "regex '{}': unexpected '{}' at character {}.",
303 pattern, p.pat[p.at], p.at + 1;
304 Invalid, Input));
305 }
306 let mut c = Compiler { prog: Vec::new(), src: pattern };
307 res!(c.node(&root));
308 res!(c.push(Inst::Match));
309 Ok(Self { prog: c.prog, names: p.names, src: pattern.to_string() })
310 }
311
312 pub fn as_str(&self) -> &str {
313 &self.src
314 }
315
316 /// The number of capture groups, counting the whole match as group 0.
317 pub fn captures_len(&self) -> usize {
318 self.names.len()
319 }
320
321 /// The name of each group in order, `None` for group 0 and for unnamed groups.
322 pub fn capture_names(&self) -> impl Iterator<Item = Option<&str>> {
323 self.names.iter().map(|n| n.as_deref())
324 }
325
326 /// The number of the group with this name.
327 pub fn group_index(&self, name: &str) -> Option<usize> {
328 self.names.iter().position(|n| n.as_deref() == Some(name))
329 }
330
331 pub fn is_match(&self, hay: &str) -> Outcome<bool> {
332 Ok(res!(self.find(hay)).is_some())
333 }
334
335 /// The leftmost match in `hay`. An error means the step or stack budget ran out, so the
336 /// answer is unknown, not that there was no match.
337 pub fn find(&self, hay: &str) -> Outcome<Option<Span>> {
338 self.find_at(hay, 0)
339 }
340
341 /// The leftmost match starting at or after byte `start`. The text before `start` still
342 /// counts as context: `^` does not match at `start` unless it is 0, and `\b` looks back past
343 /// it.
344 pub fn find_at(&self, hay: &str, start: usize) -> Outcome<Option<Span>> {
345 let h = Hay::new(hay);
346 let from = res!(h.index(start));
347 let mut vis = res!(Visited::new(self.prog.len(), from, h.chars.len(), &self.src));
348 Ok(res!(self.search(&h, from, &mut vis))
349 .and_then(|s| s.first().copied().flatten().map(|m| h.span(m))))
350 }
351
352 pub fn captures<'r, 'h>(&'r self, hay: &'h str) -> Outcome<Option<Captures<'r, 'h>>> {
353 self.captures_at(hay, 0)
354 }
355
356 /// The captures of the leftmost match starting at or after byte `start`, with the text
357 /// before it as context, as for [`Regex::find_at`].
358 pub fn captures_at<'r, 'h>(
359 &'r self,
360 hay: &'h str,
361 start: usize,
362 )
363 -> Outcome<Option<Captures<'r, 'h>>>
364 {
365 let h = Hay::new(hay);
366 let from = res!(h.index(start));
367 let mut vis = res!(Visited::new(self.prog.len(), from, h.chars.len(), &self.src));
368 Ok(res!(self.search(&h, from, &mut vis)).map(|s| self.wrap(&h, &s)))
369 }
370
371 /// Every successive non-overlapping match, leftmost first. After an error the iterator
372 /// yields nothing more.
373 pub fn find_iter<'r, 'h>(&'r self, hay: &'h str) -> Matches<'r, 'h> {
374 Matches { it: Walk::new(self, hay) }
375 }
376
377 pub fn captures_iter<'r, 'h>(&'r self, hay: &'h str) -> CaptureMatches<'r, 'h> {
378 CaptureMatches { it: Walk::new(self, hay) }
379 }
380
381 /// The pieces of `hay` between successive matches, including the empty pieces before a match
382 /// at the start and after one at the end.
383 pub fn split<'h>(&self, hay: &'h str) -> Outcome<Vec<&'h str>> {
384 let mut out = Vec::new();
385 let mut last = 0;
386 for m in self.find_iter(hay) {
387 let m = res!(m);
388 out.push(hay.get(last..m.start).unwrap_or(""));
389 last = m.end;
390 }
391 out.push(hay.get(last..).unwrap_or(""));
392 Ok(out)
393 }
394
395 /// Replaces every match with `rep`, expanded as by [`Captures::expand`].
396 pub fn replace_all(&self, hay: &str, rep: &str) -> Outcome<String> {
397 self.replacen(hay, 0, rep)
398 }
399
400 /// Replaces the first `limit` matches, or every match when `limit` is zero.
401 pub fn replacen(&self, hay: &str, limit: usize, rep: &str) -> Outcome<String> {
402 let mut out = String::with_capacity(hay.len());
403 let mut last = 0;
404 for (n, caps) in self.captures_iter(hay).enumerate() {
405 if limit > 0 && n >= limit {
406 break;
407 }
408 let caps = res!(caps);
409 let m = caps.whole();
410 out.push_str(hay.get(last..m.start).unwrap_or(""));
411 caps.expand(rep, &mut out);
412 last = m.end;
413 }
414 out.push_str(hay.get(last..).unwrap_or(""));
415 Ok(out)
416 }
417
418 fn wrap<'r, 'h>(&'r self, h: &Hay<'h>, slots: &Slots) -> Captures<'r, 'h> {
419 Captures {
420 hay: h.text,
421 spans: slots.iter().map(|s| s.map(|m| h.span(m))).collect(),
422 names: &self.names,
423 }
424 }
425
426 /// The leftmost match at or after character `from`, as capture spans. The visited set is
427 /// kept across start positions, as the crate keeps it: a pair that failed from one start
428 /// fails from any later one, since what follows it does not depend on where the match began.
429 fn search(&self, h: &Hay, from: usize, vis: &mut Visited) -> Outcome<Option<Slots>> {
430 let out = self.backtrack(h, from, vis);
431 vis.clear();
432 out
433 }
434
435 fn backtrack(&self, h: &Hay, from: usize, vis: &mut Visited) -> Outcome<Option<Slots>> {
436 let chars = &h.chars;
437 let mut slots: Vec<Option<usize>> = vec![None; 2 * self.names.len()];
438 let mut stack: Vec<Frame> = Vec::new();
439 for start in from..=chars.len() {
440 stack.push(Frame::Step(0, start));
441 while let Some(frame) = stack.pop() {
442 let (mut pc, mut at) = match frame {
443 Frame::Step(pc, at) => (pc, at),
444 Frame::Restore(i, old) => {
445 if let Some(s) = slots.get_mut(i) {
446 *s = old;
447 }
448 continue;
449 }
450 };
451 loop {
452 if !vis.insert(pc, at) {
453 break;
454 }
455 let inst = match self.prog.get(pc) {
456 Some(i) => i,
457 None => return Err(err!(
458 "regex '{}': internal -- instruction {} of {} is missing.",
459 self.src, pc, self.prog.len(); Bug, Index)),
460 };
461 let c = chars.get(at).copied();
462 let hit = match inst {
463 Inst::Char(want) => c == Some(*want),
464 Inst::CharCi(want) => c.map(|c| fold(c) == *want).unwrap_or(false),
465 Inst::Any => c.map(|c| c != '\n').unwrap_or(false),
466 Inst::AnyNl => c.is_some(),
467 Inst::Class(cl) => c.map(|c| class_has(cl, c)).unwrap_or(false),
468 Inst::Look(look) => {
469 if look_at(*look, at, chars) {
470 pc += 1;
471 continue;
472 }
473 break;
474 }
475 Inst::Save(i) => {
476 let old = slots.get(*i).copied().flatten();
477 stack.push(Frame::Restore(*i, old));
478 if let Some(s) = slots.get_mut(*i) {
479 *s = Some(at);
480 }
481 pc += 1;
482 continue;
483 }
484 Inst::Split(a, b) => {
485 stack.push(Frame::Step(*b, at));
486 pc = *a;
487 continue;
488 }
489 Inst::Jmp(to) => {
490 pc = *to;
491 continue;
492 }
493 Inst::Match => {
494 let mut out: Slots = Vec::with_capacity(self.names.len());
495 out.push(Some((start, at)));
496 for g in 1..self.names.len() {
497 let pair = match (slots.get(2 * g).copied().flatten(),
498 slots.get(2 * g + 1).copied().flatten())
499 {
500 (Some(a), Some(b)) => Some((a, b)),
501 _ => None,
502 };
503 out.push(pair);
504 }
505 return Ok(Some(out));
506 }
507 };
508 if !hit {
509 break;
510 }
511 pc += 1;
512 at += 1;
513 }
514 }
515 }
516 Ok(None)
517 }
518}
519
520/// Compiles a parsed pattern into instructions, in the shape the `regex` crate's Thompson
521/// compiler gives its NFA. The shape is not incidental: where an iteration can match nothing,
522/// the visited set cuts the loop at the loop's own split, and the captures a match reports
523/// depend on which split that is.
524struct Compiler<'s> {
525 prog: Vec<Inst>,
526 src: &'s str,
527}
528
529impl<'s> Compiler<'s> {
530
531 fn push(&mut self, inst: Inst) -> Outcome<usize> {
532 if self.prog.len() >= MAX_INSTS {
533 return Err(err!(
534 "regex '{}': compiles to more than {} instructions; reduce the repetition counts.",
535 self.src, MAX_INSTS; Excessive, Input));
536 }
537 self.prog.push(inst);
538 Ok(self.prog.len() - 1)
539 }
540
541 /// Points the split at `at` to `body` first and `out` second, or the other way round for a
542 /// lazy repetition.
543 fn aim(&mut self, at: usize, body: usize, out: usize, greedy: bool) {
544 if let Some(i) = self.prog.get_mut(at) {
545 *i = if greedy { Inst::Split(body, out) } else { Inst::Split(out, body) };
546 }
547 }
548
549 fn node(&mut self, n: &Node) -> Outcome<()> {
550 match n {
551 Node::Lit(c) => { res!(self.push(Inst::Char(*c))); }
552 Node::LitCi(c) => { res!(self.push(Inst::CharCi(*c))); }
553 Node::Any => { res!(self.push(Inst::Any)); }
554 Node::AnyNl => { res!(self.push(Inst::AnyNl)); }
555 Node::Cls(cl) => { res!(self.push(Inst::Class(cl.clone()))); }
556 Node::Look(l) => { res!(self.push(Inst::Look(*l))); }
557 Node::Group(i, inner) => {
558 res!(self.push(Inst::Save(2 * i)));
559 res!(self.node(inner));
560 res!(self.push(Inst::Save(2 * i + 1)));
561 }
562 Node::Seq(v) => {
563 for x in v {
564 res!(self.node(x));
565 }
566 }
567 Node::Alt(branches) => {
568 let mut exits = Vec::new();
569 for (k, b) in branches.iter().enumerate() {
570 if k + 1 == branches.len() {
571 res!(self.node(b));
572 } else {
573 let split = res!(self.push(Inst::Split(0, 0)));
574 res!(self.node(b));
575 exits.push(res!(self.push(Inst::Jmp(0))));
576 let next = self.prog.len();
577 self.aim(split, split + 1, next, true);
578 }
579 }
580 let end = self.prog.len();
581 for j in exits {
582 if let Some(i) = self.prog.get_mut(j) {
583 *i = Inst::Jmp(end);
584 }
585 }
586 }
587 Node::Rep { node, min, max, greedy } => res!(self.rep(node, *min, *max, *greedy)),
588 }
589 Ok(())
590 }
591
592 fn rep(&mut self, x: &Node, min: u32, max: u32, greedy: bool) -> Outcome<()> {
593 if max == u32::MAX {
594 if min == 0 {
595 let head = res!(self.push(Inst::Split(0, 0)));
596 if min_len(x) > 0 {
597 // One split that is both the loop's head and its exit.
598 res!(self.node(x));
599 res!(self.push(Inst::Jmp(head)));
600 let end = self.prog.len();
601 self.aim(head, head + 1, end, greedy);
602 } else {
603 // `x*` as `(x+)?` when `x` can match nothing, as the crate compiles it, so
604 // that the first iteration may be empty and a later empty one is cut.
605 let body = head + 1;
606 res!(self.node(x));
607 let back = res!(self.push(Inst::Split(0, 0)));
608 let end = self.prog.len();
609 self.aim(head, body, end, greedy);
610 self.aim(back, body, end, greedy);
611 }
612 } else {
613 for _ in 1..min {
614 res!(self.node(x));
615 }
616 let body = self.prog.len();
617 res!(self.node(x));
618 let back = res!(self.push(Inst::Split(0, 0)));
619 self.aim(back, body, back + 1, greedy);
620 }
621 return Ok(());
622 }
623 for _ in 0..min {
624 res!(self.node(x));
625 }
626 // Each optional copy may skip straight to the end.
627 let mut splits = Vec::new();
628 for _ in min..max {
629 splits.push(res!(self.push(Inst::Split(0, 0))));
630 res!(self.node(x));
631 }
632 let end = self.prog.len();
633 for sp in splits {
634 self.aim(sp, sp + 1, end, greedy);
635 }
636 Ok(())
637 }
638}
639
640/// The fewest characters a node can match.
641fn min_len(n: &Node) -> usize {
642 match n {
643 Node::Lit(_) | Node::LitCi(_) | Node::Any | Node::AnyNl | Node::Cls(_) => 1,
644 Node::Look(_) => 0,
645 Node::Group(_, inner) => min_len(inner),
646 Node::Seq(v) => v.iter().map(min_len).sum(),
647 Node::Alt(v) => v.iter().map(min_len).min().unwrap_or(0),
648 Node::Rep { node, min, .. } => min_len(node).saturating_mul(*min as usize),
649 }
650}
651
652/// The groups of one match, as byte spans into the haystack.
653#[derive(Clone, Debug)]
654pub struct Captures<'r, 'h> {
655 hay: &'h str,
656 spans: Vec<Option<Span>>,
657 names: &'r [Option<String>],
658}
659
660impl<'r, 'h> Captures<'r, 'h> {
661
662 /// The number of groups, counting the whole match as group 0.
663 pub fn len(&self) -> usize { self.spans.len() }
664
665 /// Always false, since group 0 is always there; present to pair with `len`.
666 pub fn is_empty(&self) -> bool { self.spans.is_empty() }
667
668 /// The span of the whole match.
669 pub fn whole(&self) -> Span {
670 self.get(0).unwrap_or(Span { start: 0, end: 0 })
671 }
672
673 /// The span of group `i`, `None` when the group took no part in the match.
674 pub fn get(&self, i: usize) -> Option<Span> {
675 self.spans.get(i).copied().flatten()
676 }
677
678 pub fn text(&self, i: usize) -> Option<&'h str> {
679 self.get(i).map(|s| s.as_str(self.hay))
680 }
681
682 pub fn name(&self, name: &str) -> Option<Span> {
683 match self.names.iter().position(|n| n.as_deref() == Some(name)) {
684 Some(i) => self.get(i),
685 None => None,
686 }
687 }
688
689 pub fn name_text(&self, name: &str) -> Option<&'h str> {
690 self.name(name).map(|s| s.as_str(self.hay))
691 }
692
693 /// Every group's span in order, group 0 first.
694 pub fn spans(&self) -> &[Option<Span>] {
695 &self.spans
696 }
697
698 /// Appends `template` to `out` with each group reference replaced by that group's text, as
699 /// the `regex` crate does: `$2` or `${2}` by number, `$name` or `${name}` by name, `$$` for a
700 /// literal `$`. An unbraced reference takes the longest run of letters, digits and `_`, so
701 /// `$1a` names a group `1a`; write `${1}a`. A reference to a group that does not exist or
702 /// did not take part becomes nothing.
703 pub fn expand(&self, template: &str, out: &mut String) {
704 let mut rest = template;
705 while let Some(i) = rest.find('$') {
706 out.push_str(&rest[..i]);
707 rest = &rest[i + 1..];
708 if let Some(after) = rest.strip_prefix('$') {
709 out.push('$');
710 rest = after;
711 continue;
712 }
713 let (name, after) = if let Some(braced) = rest.strip_prefix('{') {
714 match braced.find('}') {
715 Some(j) if j > 0 => (&braced[..j], &braced[j + 1..]),
716 _ => {
717 out.push('$');
718 continue;
719 }
720 }
721 } else {
722 let n = rest
723 .find(|c: char| !(c.is_ascii_alphanumeric() || c == '_'))
724 .unwrap_or(rest.len());
725 if n == 0 {
726 out.push('$');
727 continue;
728 }
729 (&rest[..n], &rest[n..])
730 };
731 let text = if name.bytes().all(|b| b.is_ascii_digit()) {
732 match name.parse::<usize>() {
733 Ok(i) => self.text(i),
734 Err(_) => None,
735 }
736 } else {
737 self.name_text(name)
738 };
739 out.push_str(text.unwrap_or(""));
740 rest = after;
741 }
742 out.push_str(rest);
743 }
744}
745
746/// The search state shared by the match iterators.
747struct Walk<'r, 'h> {
748 re: &'r Regex,
749 hay: Hay<'h>,
750 vis: Option<Visited>, // made on the first search, so an iterator costs nothing unused
751 at: usize, // character index the next search starts from
752 last: Option<usize>, // where the previous match ended
753 done: bool,
754}
755
756impl<'r, 'h> Walk<'r, 'h> {
757
758 fn new(re: &'r Regex, text: &'h str) -> Self {
759 Self { re, hay: Hay::new(text), vis: None, at: 0, last: None, done: false }
760 }
761
762 /// The next match, by the rule of the `regex` crate: an empty match where the previous one
763 /// ended is passed over, and the search tried again one character on.
764 fn next_slots(&mut self) -> Option<Outcome<Slots>> {
765 if self.done || self.at > self.hay.chars.len() {
766 return None;
767 }
768 if self.vis.is_none() {
769 match Visited::new(self.re.prog.len(), 0, self.hay.chars.len(), &self.re.src) {
770 Ok(v) => self.vis = Some(v),
771 Err(e) => { self.done = true; return Some(Err(e)); }
772 }
773 }
774 let vis = match self.vis.as_mut() {
775 Some(v) => v,
776 None => { self.done = true; return None; }
777 };
778 let mut found = match self.re.search(&self.hay, self.at, vis) {
779 Ok(f) => f,
780 Err(e) => { self.done = true; return Some(Err(e)); }
781 };
782 if let Some((s, e)) = found.as_ref().and_then(|x| x.first().copied().flatten()) {
783 if s == e && Some(e) == self.last {
784 if self.at + 1 > self.hay.chars.len() {
785 self.done = true;
786 return None;
787 }
788 found = match self.re.search(&self.hay, self.at + 1, vis) {
789 Ok(f) => f,
790 Err(e) => { self.done = true; return Some(Err(e)); }
791 };
792 }
793 }
794 let slots = match found {
795 Some(s) => s,
796 None => { self.done = true; return None; }
797 };
798 match slots.first().copied().flatten() {
799 Some((_, e)) => {
800 self.at = e;
801 self.last = Some(e);
802 Some(Ok(slots))
803 }
804 None => {
805 self.done = true;
806 None
807 }
808 }
809 }
810}
811
812/// An iterator over successive match spans; see [`Regex::find_iter`].
813pub struct Matches<'r, 'h> {
814 it: Walk<'r, 'h>,
815}
816
817impl<'r, 'h> Iterator for Matches<'r, 'h> {
818 type Item = Outcome<Span>;
819
820 fn next(&mut self) -> Option<Self::Item> {
821 match self.it.next_slots() {
822 Some(Ok(s)) => {
823 let m = s.first().copied().flatten().unwrap_or((0, 0));
824 Some(Ok(self.it.hay.span(m)))
825 }
826 Some(Err(e)) => Some(Err(e)),
827 None => None,
828 }
829 }
830}
831
832/// An iterator over successive matches with their groups; see [`Regex::captures_iter`].
833pub struct CaptureMatches<'r, 'h> {
834 it: Walk<'r, 'h>,
835}
836
837impl<'r, 'h> Iterator for CaptureMatches<'r, 'h> {
838 type Item = Outcome<Captures<'r, 'h>>;
839
840 fn next(&mut self) -> Option<Self::Item> {
841 match self.it.next_slots() {
842 Some(Ok(s)) => Some(Ok(self.it.re.wrap(&self.it.hay, &s))),
843 Some(Err(e)) => Some(Err(e)),
844 None => None,
845 }
846 }
847}
848
849/// Escapes every character that means something to the parser, so `quote(s)` matches `s`
850/// exactly.
851pub fn quote(literal: &str) -> String {
852 let mut out = String::with_capacity(literal.len() + 8);
853 for c in literal.chars() {
854 if "\\.+*?()|[]{}^$#&-~".contains(c) {
855 out.push('\\');
856 }
857 out.push(c);
858 }
859 out
860}
861
862/// The single character a case mapping gives, or `c` itself when the mapping expands.
863fn single(mut it: impl Iterator<Item = char>, c: char) -> char {
864 match (it.next(), it.next()) {
865 (Some(x), None) => x,
866 _ => c,
867 }
868}
869
870/// Case-folds one character, approximating Unicode simple case folding: upper case then lower,
871/// so that `ſ` and `s`, `ς` and `σ`, `K` (Kelvin) and `k` agree, without letting a mapping that
872/// expands (`ß` to `SS`) turn one character into another. Dotless `ı` is kept apart from `i`, as
873/// simple folding keeps it.
874fn fold(c: char) -> char {
875 if c.is_ascii() {
876 return c.to_ascii_lowercase();
877 }
878 if c == 'ı' {
879 return c;
880 }
881 let up = single(c.to_uppercase(), c);
882 single(up.to_lowercase(), up)
883}
884
885/// The case forms a case-insensitive class tries a character in.
886fn variants(c: char) -> [char; 4] {
887 [c, single(c.to_lowercase(), c), single(c.to_uppercase(), c), fold(c)]
888}
889
890/// Does the assertion hold at `pos`?
891fn look_at(look: Look, pos: usize, chars: &[char]) -> bool {
892 let before = pos > 0 && chars.get(pos - 1).map(|c| property::is_word(*c)).unwrap_or(false);
893 let after = chars.get(pos).map(|c| property::is_word(*c)).unwrap_or(false);
894 match look {
895 Look::Start => pos == 0,
896 Look::End => pos == chars.len(),
897 Look::LineStart => pos == 0 || chars.get(pos - 1) == Some(&'\n'),
898 Look::LineEnd => pos == chars.len() || chars.get(pos) == Some(&'\n'),
899 Look::Word => before != after,
900 Look::NotWord => before == after,
901 Look::WordStart => !before && after,
902 Look::WordEnd => before && !after,
903 Look::WordStartHalf => !before,
904 Look::WordEndHalf => !after,
905 }
906}
907
908/// Does a class admit `c`? Negation comes after case folding, as in the `regex` crate: `(?i)[^a]`
909/// refuses `A` as well as `a`.
910fn class_has(cl: &Class, c: char) -> bool {
911 set_has(&cl.set, c, cl.ci) != cl.neg
912}
913
914fn set_has(set: &Set, c: char, ci: bool) -> bool {
915 match set {
916 Set::Union(items) => items.iter().any(|it| item_has(it, c, ci)),
917 Set::Op(a, op, b) => {
918 let (x, y) = (set_has(a, c, ci), set_has(b, c, ci));
919 match op {
920 SetOp::And => x && y,
921 SetOp::Minus => x && !y,
922 SetOp::Xor => x != y,
923 }
924 }
925 }
926}
927
928/// Does an item admit `c`? Under case-insensitivity the positive form of the item is tried on
929/// each case of `c` and only then negated, so `(?i)\P{Lu}` refuses both `A` and `a`.
930fn item_has(it: &Item, c: char, ci: bool) -> bool {
931 let base = |x: char| -> bool {
932 match it {
933 Item::Ch(y) => x == *y,
934 Item::Range(a, b) => *a <= x && x <= *b,
935 Item::Digit(_) => property::is_digit(x),
936 Item::Word(_) => property::is_word(x),
937 Item::Space(_) => property::is_space(x),
938 Item::Prop(p, _) => p.contains(x),
939 Item::Nested(_) => false,
940 }
941 };
942 let want = match it {
943 Item::Nested(cl) => return class_has(cl, c),
944 Item::Digit(w) | Item::Word(w) | Item::Space(w) | Item::Prop(_, w) => *w,
945 Item::Ch(_) | Item::Range(..) => true,
946 };
947 let hit = if ci { variants(c).iter().any(|v| base(*v)) } else { base(c) };
948 hit == want
949}
950
951
952// ── Parsing ─────────────────────────────────────────────────────────
953
954/// The flags a pattern can set inline.
955#[derive(Clone, Copy, Debug, Default)]
956struct Flags {
957 i: bool, // case-insensitive
958 m: bool, // `^` and `$` match at line ends
959 s: bool, // `.` matches a newline
960 x: bool, // white space and `#` comments ignored
961 u: bool, // `U`: greed swapped
962}
963
964/// A recursive-descent parser over the pattern's characters.
965struct Parser<'a> {
966 pat: &'a [char],
967 at: usize,
968 flags: Flags,
969 names: Vec<Option<String>>, // one per group so far, group 0 included
970}
971
972impl<'a> Parser<'a> {
973
974 /// Parse `seq ('|' seq)*`.
975 fn alt(&mut self) -> Outcome<Node> {
976 let mut branches = vec![res!(self.seq())];
977 while self.peek() == Some('|') {
978 self.at += 1;
979 branches.push(res!(self.seq()));
980 }
981 Ok(if branches.len() == 1 {
982 // `remove` cannot fail: the vector was built with one element and only grows.
983 branches.remove(0)
984 } else {
985 Node::Alt(branches)
986 })
987 }
988
989 /// Parse a run of quantified atoms, stopping at `|` or `)`. A bare flag group, `(?i)`,
990 /// changes the flags for the rest of the enclosing group, alternatives included.
991 fn seq(&mut self) -> Outcome<Node> {
992 let mut nodes = Vec::new();
993 loop {
994 self.skip_x();
995 match self.peek() {
996 None | Some('|') | Some(')') => break,
997 _ => {},
998 }
999 if self.peek() == Some('(') && self.pat.get(self.at + 1) == Some(&'?') {
1000 // Only a bare flag group is taken here; anything else, errors included, is left
1001 // for `group` to parse and to report.
1002 let save = self.at;
1003 self.at += 2;
1004 if let Ok(f) = self.flag_list() {
1005 if self.peek() == Some(')') {
1006 self.at += 1;
1007 self.flags = f;
1008 continue;
1009 }
1010 }
1011 self.at = save;
1012 }
1013 nodes.push(res!(self.quantified()));
1014 }
1015 Ok(Node::Seq(nodes))
1016 }
1017
1018 /// Skip white space and `#` comments when the `x` flag is set.
1019 fn skip_x(&mut self) {
1020 if !self.flags.x {
1021 return;
1022 }
1023 while let Some(c) = self.peek() {
1024 if c.is_whitespace() {
1025 self.at += 1;
1026 } else if c == '#' {
1027 while let Some(c) = self.peek() {
1028 self.at += 1;
1029 if c == '\n' {
1030 break;
1031 }
1032 }
1033 } else {
1034 break;
1035 }
1036 }
1037 }
1038
1039 /// Read flag letters from the cursor, `i`, `m`, `s`, `x`, `U`, `u`, with `-` clearing those
1040 /// after it, stopping before `:` or `)`. Returns the flags as they would then stand.
1041 fn flag_list(&mut self) -> Outcome<Flags> {
1042 let mut f = self.flags;
1043 let mut on = true;
1044 let mut any = false;
1045 while let Some(c) = self.peek() {
1046 match c {
1047 'i' => f.i = on,
1048 'm' => f.m = on,
1049 's' => f.s = on,
1050 'x' => f.x = on,
1051 'U' => f.u = on,
1052 'u' => {}, // Unicode is always on
1053 '-' => {
1054 if !on {
1055 return Err(err!("regex: a flag group has two '-'."; Invalid, Input));
1056 }
1057 on = false;
1058 }
1059 ':' | ')' => break,
1060 _ => return Err(err!(
1061 "regex: '(?{}' is not a flag group this engine knows -- there is no \
1062 look-around, and the flags are i, m, s, x and U.", c;
1063 Unimplemented, Input)),
1064 }
1065 any = true;
1066 self.at += 1;
1067 }
1068 if !any && self.peek() == Some(')') {
1069 return Err(err!("regex: '(?)' is an empty flag group."; Invalid, Input));
1070 }
1071 Ok(f)
1072 }
1073
1074 /// Parse one atom and any quantifier that follows it.
1075 fn quantified(&mut self) -> Outcome<Node> {
1076 let atom = res!(self.atom());
1077 self.skip_x();
1078 let (min, max) = match self.peek() {
1079 Some('*') => { self.at += 1; (0, u32::MAX) }
1080 Some('+') => { self.at += 1; (1, u32::MAX) }
1081 Some('?') => { self.at += 1; (0, 1) }
1082 Some('{') if self.brace_is_a_quantifier() => res!(self.brace()),
1083 _ => return Ok(atom),
1084 };
1085 // A trailing `?` makes the quantifier lazy; under `U` it makes it greedy.
1086 let lazy = if self.peek() == Some('?') {
1087 self.at += 1;
1088 true
1089 } else {
1090 // A trailing `+` is a possessive quantifier elsewhere; here it would silently mean
1091 // something else, so it is refused rather than mis-read.
1092 if self.peek() == Some('+') {
1093 return Err(err!(
1094 "regex: possessive quantifiers ('{}+') are not supported.",
1095 if max == 1 { "?" } else if min == 1 { "+" } else { "*" };
1096 Unimplemented, Input));
1097 }
1098 false
1099 };
1100 Ok(Node::Rep { node: Box::new(atom), min, max, greedy: lazy == self.flags.u })
1101 }
1102
1103 /// Does the `{` at the cursor open a `{n}`, `{n,}` or `{n,m}` quantifier? A `{` that does not
1104 /// is an ordinary character -- `\d{` and `a{b}` both mean what they look like.
1105 fn brace_is_a_quantifier(&self) -> bool {
1106 let mut i = self.at + 1;
1107 let mut digits = 0;
1108 while i < self.pat.len() && self.pat[i].is_ascii_digit() {
1109 i += 1;
1110 digits += 1;
1111 }
1112 if digits == 0 {
1113 return false;
1114 }
1115 if i < self.pat.len() && self.pat[i] == ',' {
1116 i += 1;
1117 while i < self.pat.len() && self.pat[i].is_ascii_digit() {
1118 i += 1;
1119 }
1120 }
1121 i < self.pat.len() && self.pat[i] == '}'
1122 }
1123
1124 /// Parse `{n}`, `{n,}` or `{n,m}`, the cursor sitting on the `{`.
1125 fn brace(&mut self) -> Outcome<(u32, u32)> {
1126 self.at += 1; // the '{'
1127 let min = res!(self.number());
1128 let max = if self.peek() == Some(',') {
1129 self.at += 1;
1130 if self.peek() == Some('}') { u32::MAX } else { res!(self.number()) }
1131 } else {
1132 min
1133 };
1134 if self.peek() != Some('}') {
1135 return Err(err!("regex: unterminated '{{n,m}}' quantifier."; Invalid, Input));
1136 }
1137 self.at += 1;
1138 if min > max {
1139 return Err(err!(
1140 "regex: '{{{},{}}}' asks for at least {} repetitions and at most {}.",
1141 min, max, min, max; Invalid, Input));
1142 }
1143 if min > MAX_REPEAT || (max != u32::MAX && max > MAX_REPEAT) {
1144 return Err(err!(
1145 "regex: a repetition count above {} is refused.", MAX_REPEAT; Excessive, Input));
1146 }
1147 Ok((min, max))
1148 }
1149
1150 /// Read a decimal number at the cursor.
1151 fn number(&mut self) -> Outcome<u32> {
1152 let start = self.at;
1153 while self.peek().map(|c| c.is_ascii_digit()).unwrap_or(false) {
1154 self.at += 1;
1155 }
1156 if start == self.at {
1157 return Err(err!("regex: a number was expected."; Invalid, Input, Missing));
1158 }
1159 let s: String = self.pat[start..self.at].iter().collect();
1160 s.parse::<u32>().map_err(|e| err!(e, "regex: '{}' is not a count.", s; Invalid, Input))
1161 }
1162
1163 /// Parse one atom: a group, a class, a metacharacter, an escape, or a literal.
1164 fn atom(&mut self) -> Outcome<Node> {
1165 let c = match self.peek() {
1166 Some(c) => c,
1167 None => return Err(err!("regex: the pattern ends where an atom was expected.";
1168 Invalid, Input, Missing)),
1169 };
1170 match c {
1171 '(' => self.group(),
1172 '[' => {
1173 let cl = res!(self.class());
1174 Ok(Node::Cls(cl))
1175 }
1176 '.' => { self.at += 1; Ok(if self.flags.s { Node::AnyNl } else { Node::Any }) }
1177 '^' => {
1178 self.at += 1;
1179 Ok(Node::Look(if self.flags.m { Look::LineStart } else { Look::Start }))
1180 }
1181 '$' => {
1182 self.at += 1;
1183 Ok(Node::Look(if self.flags.m { Look::LineEnd } else { Look::End }))
1184 }
1185 '*' | '+' | '?' => Err(err!(
1186 "regex: '{}' has nothing before it to repeat.", c; Invalid, Input)),
1187 '{' if self.brace_is_a_quantifier() => Err(err!(
1188 "regex: a '{{n,m}}' repetition has nothing before it to repeat."; Invalid, Input)),
1189 ')' => Err(err!("regex: ')' with no '(' before it."; Invalid, Input)),
1190 '\\' => {
1191 self.at += 1;
1192 self.escape()
1193 }
1194 _ => { self.at += 1; Ok(self.lit(c)) }
1195 }
1196 }
1197
1198 fn lit(&self, c: char) -> Node {
1199 if self.flags.i { Node::LitCi(fold(c)) } else { Node::Lit(c) }
1200 }
1201
1202 /// Parse a group, the cursor sitting on the `(`. The flags in force outside are restored
1203 /// at its `)`.
1204 fn group(&mut self) -> Outcome<Node> {
1205 self.at += 1;
1206 let outer = self.flags;
1207 let mut idx = None;
1208 if self.peek() == Some('?') {
1209 self.at += 1;
1210 let named = match (self.peek(), self.pat.get(self.at + 1)) {
1211 (Some('P'), Some('<')) => { self.at += 2; true }
1212 (Some('<'), Some(n)) if *n != '=' && *n != '!' => { self.at += 1; true }
1213 (Some('='), _) | (Some('!'), _) | (Some('<'), _) => return Err(err!(
1214 "regex: look-around '(?{}' is not supported.", self.pat[self.at];
1215 Unimplemented, Input)),
1216 _ => false,
1217 };
1218 if named {
1219 let name = res!(self.group_name());
1220 if self.names.iter().any(|n| n.as_deref() == Some(name.as_str())) {
1221 return Err(err!("regex: the group name '{}' is used twice.", name;
1222 Invalid, Input));
1223 }
1224 idx = Some(self.names.len());
1225 self.names.push(Some(name));
1226 } else {
1227 self.flags = res!(self.flag_list());
1228 if self.peek() != Some(':') {
1229 return Err(err!("regex: a flag group must end with ':' or ')'."; Invalid, Input));
1230 }
1231 self.at += 1;
1232 }
1233 } else {
1234 idx = Some(self.names.len());
1235 self.names.push(None);
1236 }
1237 let inner = res!(self.alt());
1238 if self.peek() != Some(')') {
1239 return Err(err!("regex: unclosed '('."; Invalid, Input));
1240 }
1241 self.at += 1;
1242 self.flags = outer;
1243 Ok(match idx {
1244 Some(i) => Node::Group(i, Box::new(inner)),
1245 None => inner,
1246 })
1247 }
1248
1249 /// Read a group name up to and past its `>`.
1250 fn group_name(&mut self) -> Outcome<String> {
1251 let start = self.at;
1252 while let Some(c) = self.peek() {
1253 if c == '>' {
1254 break;
1255 }
1256 let ok = if self.at == start {
1257 c == '_' || c.is_alphabetic()
1258 } else {
1259 c == '_' || c == '.' || c == '[' || c == ']' || c.is_alphanumeric()
1260 };
1261 if !ok {
1262 return Err(err!("regex: '{}' cannot appear in a group name.", c; Invalid, Input));
1263 }
1264 self.at += 1;
1265 }
1266 if self.peek() != Some('>') {
1267 return Err(err!("regex: unclosed group name."; Invalid, Input));
1268 }
1269 if start == self.at {
1270 return Err(err!("regex: an empty group name."; Invalid, Input, Missing));
1271 }
1272 let name: String = self.pat[start..self.at].iter().collect();
1273 self.at += 1;
1274 Ok(name)
1275 }
1276
1277 /// Parse what follows a `\` outside a class.
1278 fn escape(&mut self) -> Outcome<Node> {
1279 let e = match self.peek() {
1280 Some(e) => e,
1281 None => return Err(err!("regex: the pattern ends with a lone '\\'."; Invalid, Input)),
1282 };
1283 let one = |item: Item, ci: bool| Node::Cls(Class { neg: false, ci, set: Set::Union(vec![item]) });
1284 match e {
1285 'b' => {
1286 self.at += 1;
1287 if self.peek() != Some('{') {
1288 return Ok(Node::Look(Look::Word));
1289 }
1290 let end = match self.pat[self.at..].iter().position(|c| *c == '}') {
1291 Some(n) => self.at + n,
1292 None => return Err(err!("regex: unclosed '\\b{{'."; Invalid, Input)),
1293 };
1294 let kind: String = self.pat[self.at + 1..end].iter().collect();
1295 self.at = end + 1;
1296 Ok(Node::Look(match kind.as_str() {
1297 "start" => Look::WordStart,
1298 "end" => Look::WordEnd,
1299 "start-half" => Look::WordStartHalf,
1300 "end-half" => Look::WordEndHalf,
1301 _ => return Err(err!("regex: '\\b{{{}}}' is not a known boundary.", kind;
1302 Invalid, Input)),
1303 }))
1304 }
1305 'B' => { self.at += 1; Ok(Node::Look(Look::NotWord)) }
1306 'A' => { self.at += 1; Ok(Node::Look(Look::Start)) }
1307 'z' => { self.at += 1; Ok(Node::Look(Look::End)) }
1308 '<' => { self.at += 1; Ok(Node::Look(Look::WordStart)) }
1309 '>' => { self.at += 1; Ok(Node::Look(Look::WordEnd)) }
1310 _ => match res!(self.class_escape()) {
1311 Esc::Item(it) => Ok(one(it, self.flags.i)),
1312 Esc::Char(c) => Ok(self.lit(c)),
1313 },
1314 }
1315 }
1316
1317 /// Parse a `\` escape that may also appear inside a class, the cursor after the `\`.
1318 fn class_escape(&mut self) -> Outcome<Esc> {
1319 let e = match self.peek() {
1320 Some(e) => e,
1321 None => return Err(err!("regex: the pattern ends with a lone '\\'."; Invalid, Input)),
1322 };
1323 self.at += 1;
1324 Ok(match e {
1325 'd' => Esc::Item(Item::Digit(true)),
1326 'D' => Esc::Item(Item::Digit(false)),
1327 'w' => Esc::Item(Item::Word(true)),
1328 'W' => Esc::Item(Item::Word(false)),
1329 's' => Esc::Item(Item::Space(true)),
1330 'S' => Esc::Item(Item::Space(false)),
1331 'p' | 'P' => {
1332 let (cc, pos) = res!(self.property());
1333 Esc::Item(Item::Prop(cc, pos == (e == 'p')))
1334 }
1335 'n' => Esc::Char('\n'),
1336 't' => Esc::Char('\t'),
1337 'r' => Esc::Char('\r'),
1338 'a' => Esc::Char('\x07'),
1339 'f' => Esc::Char('\x0C'),
1340 'v' => Esc::Char('\x0B'),
1341 'x' => Esc::Char(res!(self.hex(2))),
1342 'u' => Esc::Char(res!(self.hex(4))),
1343 'U' => Esc::Char(res!(self.hex(8))),
1344 '0'..='9' => return Err(err!(
1345 "regex: '\\{}' -- backreferences and octal escapes are not supported.", e;
1346 Unimplemented, Input)),
1347 _ if e.is_ascii_alphanumeric() => return Err(err!(
1348 "regex: '\\{}' is not a known escape here.", e; Invalid, Input)),
1349 _ => Esc::Char(e),
1350 })
1351 }
1352
1353 /// Read a hexadecimal code point, `digits` long or braced, `{...}`.
1354 fn hex(&mut self, digits: usize) -> Outcome<char> {
1355 let (start, end, next) = if self.peek() == Some('{') {
1356 match self.pat[self.at..].iter().position(|c| *c == '}') {
1357 Some(n) => (self.at + 1, self.at + n, self.at + n + 1),
1358 None => return Err(err!("regex: unclosed hexadecimal escape '{{'."; Invalid, Input)),
1359 }
1360 } else {
1361 (self.at, self.at + digits, self.at + digits)
1362 };
1363 let s: String = match self.pat.get(start..end) {
1364 Some(cs) => cs.iter().collect(),
1365 None => return Err(err!("regex: a hexadecimal escape needs {} digits.", digits;
1366 Invalid, Input, Missing)),
1367 };
1368 if s.is_empty() || s.len() > 8 || !s.chars().all(|c| c.is_ascii_hexdigit()) {
1369 return Err(err!("regex: '{}' is not a hexadecimal code point.", s; Invalid, Input));
1370 }
1371 let v = res!(u32::from_str_radix(&s, 16)
1372 .map_err(|e| err!(e, "regex: '{}' is not hexadecimal.", s; Invalid, Input)));
1373 self.at = next;
1374 match char::from_u32(v) {
1375 Some(c) => Ok(c),
1376 None => Err(err!("regex: U+{:X} is not a Unicode scalar value.", v; Invalid, Input)),
1377 }
1378 }
1379
1380 /// Parse the name after `\p` or `\P`: one letter, or braces holding a name, `name=value`,
1381 /// `name:value` or `name!=value`. The flag says whether the class is positive before any
1382 /// `\P`.
1383 fn property(&mut self) -> Outcome<(CharClass, bool)> {
1384 let body: String = match self.peek() {
1385 Some('{') => {
1386 let end = match self.pat[self.at..].iter().position(|c| *c == '}') {
1387 Some(n) => self.at + n,
1388 None => return Err(err!("regex: unclosed '\\p{{'."; Invalid, Input)),
1389 };
1390 let s = self.pat[self.at + 1..end].iter().collect();
1391 self.at = end + 1;
1392 s
1393 }
1394 Some(c) => { self.at += 1; c.to_string() }
1395 None => return Err(err!("regex: '\\p' with no property after it."; Invalid, Input)),
1396 };
1397 match body.split_once("!=") {
1398 Some((k, v)) => Ok((res!(CharClass::parse(&fmt!("{}={}", k, v))), false)),
1399 None => Ok((res!(CharClass::parse(&body)), true)),
1400 }
1401 }
1402
1403 /// Parse a bracketed class, the cursor sitting on the `[`.
1404 fn class(&mut self) -> Outcome<Class> {
1405 self.at += 1; // the '['
1406 let neg = if self.peek() == Some('^') { self.at += 1; true } else { false };
1407 let mut set = Set::Union(res!(self.class_union(true)));
1408 loop {
1409 let op = match (self.peek(), self.pat.get(self.at + 1)) {
1410 (Some('&'), Some('&')) => SetOp::And,
1411 (Some('-'), Some('-')) => SetOp::Minus,
1412 (Some('~'), Some('~')) => SetOp::Xor,
1413 _ => break,
1414 };
1415 self.at += 2;
1416 let rhs = Set::Union(res!(self.class_union(false)));
1417 set = Set::Op(Box::new(set), op, Box::new(rhs));
1418 }
1419 if self.peek() != Some(']') {
1420 return Err(err!("regex: unclosed '['."; Invalid, Input));
1421 }
1422 self.at += 1;
1423 Ok(Class { neg, ci: self.flags.i, set })
1424 }
1425
1426 /// Parse the items of a class up to a set operator or the closing `]`, which is left for
1427 /// the caller. A `]` first thing in the class is a literal.
1428 fn class_union(&mut self, first: bool) -> Outcome<Vec<Item>> {
1429 let mut items = Vec::new();
1430 if first && self.peek() == Some(']') {
1431 self.at += 1;
1432 items.push(Item::Ch(']'));
1433 }
1434 loop {
1435 if self.flags.x {
1436 while self.peek().map(|c| c.is_whitespace()).unwrap_or(false) {
1437 self.at += 1;
1438 }
1439 }
1440 let c = match self.peek() {
1441 Some(']') => break,
1442 Some(c) => c,
1443 None => return Err(err!("regex: unclosed '['."; Invalid, Input)),
1444 };
1445 let pair = self.pat.get(self.at + 1).copied();
1446 if matches!((c, pair), ('&', Some('&')) | ('-', Some('-')) | ('~', Some('~'))) {
1447 break;
1448 }
1449 let lo = if c == '[' {
1450 if pair == Some(':') {
1451 if let Some(it) = res!(self.posix()) {
1452 items.push(it);
1453 continue;
1454 }
1455 }
1456 let inner = res!(self.class());
1457 items.push(Item::Nested(inner));
1458 continue;
1459 } else if c == '\\' {
1460 self.at += 1;
1461 match res!(self.class_escape()) {
1462 Esc::Item(it) => { items.push(it); continue; }
1463 Esc::Char(ch) => ch,
1464 }
1465 } else {
1466 self.at += 1;
1467 c
1468 };
1469 // A `-` between two single characters makes the pair a range.
1470 let dash_then = self.pat.get(self.at + 1).copied();
1471 if self.peek() == Some('-') && dash_then.is_some() && dash_then != Some(']')
1472 && dash_then != Some('-')
1473 {
1474 self.at += 1; // the '-'
1475 let hi = match self.peek() {
1476 Some('\\') => {
1477 self.at += 1;
1478 match res!(self.class_escape()) {
1479 Esc::Char(ch) => ch,
1480 Esc::Item(_) => return Err(err!(
1481 "regex: a class shorthand cannot end the range from '{}'.", lo;
1482 Invalid, Input)),
1483 }
1484 }
1485 Some(h) => { self.at += 1; h }
1486 None => return Err(err!("regex: unclosed '['."; Invalid, Input)),
1487 };
1488 if hi < lo {
1489 return Err(err!(
1490 "regex: the range '{}-{}' runs backwards.", lo, hi; Invalid, Input));
1491 }
1492 items.push(Item::Range(lo, hi));
1493 } else {
1494 items.push(Item::Ch(lo));
1495 }
1496 }
1497 Ok(items)
1498 }
1499
1500 /// Parse an ASCII class such as `[:alpha:]` or `[:^digit:]`, the cursor on its `[`. `None`,
1501 /// with the cursor unmoved, when what follows is not one, so the `[` opens a nested class.
1502 fn posix(&mut self) -> Outcome<Option<Item>> {
1503 let rest = &self.pat[self.at + 2..];
1504 let end = match rest.windows(2).position(|w| w == [':', ']']) {
1505 Some(n) => n,
1506 None => return Ok(None),
1507 };
1508 let mut name: String = rest[..end].iter().collect();
1509 let neg = name.starts_with('^');
1510 if neg {
1511 name.remove(0);
1512 }
1513 let r = |a: char, b: char| Item::Range(a, b);
1514 let items = match name.as_str() {
1515 "alnum" => vec![r('0', '9'), r('A', 'Z'), r('a', 'z')],
1516 "alpha" => vec![r('A', 'Z'), r('a', 'z')],
1517 "ascii" => vec![r('\0', '\x7F')],
1518 "blank" => vec![Item::Ch('\t'), Item::Ch(' ')],
1519 "cntrl" => vec![r('\0', '\x1F'), Item::Ch('\x7F')],
1520 "digit" => vec![r('0', '9')],
1521 "graph" => vec![r('!', '~')],
1522 "lower" => vec![r('a', 'z')],
1523 "print" => vec![r(' ', '~')],
1524 "punct" => vec![r('!', '/'), r(':', '@'), r('[', '`'), r('{', '~')],
1525 "space" => vec![r('\t', '\r'), Item::Ch(' ')],
1526 "upper" => vec![r('A', 'Z')],
1527 "word" => vec![r('0', '9'), r('A', 'Z'), r('a', 'z'), Item::Ch('_')],
1528 "xdigit" => vec![r('0', '9'), r('A', 'F'), r('a', 'f')],
1529 _ => return Ok(None),
1530 };
1531 self.at += 2 + end + 2;
1532 Ok(Some(Item::Nested(Class { neg, ci: self.flags.i, set: Set::Union(items) })))
1533 }
1534
1535 fn peek(&self) -> Option<char> {
1536 self.pat.get(self.at).copied()
1537 }
1538}
1539
1540/// What an escape stands for: a class item, or one character.
1541enum Esc {
1542 Item(Item),
1543 Char(char),
1544}
1545
1546
1547#[cfg(test)]
1548mod tests {
1549 use super::*;
1550
1551 /// Compile and match, so a test reads as one line.
1552 fn m(pat: &str, hay: &str) -> bool {
1553 let r = match Regex::new(pat) {
1554 Ok(r) => r,
1555 Err(e) => panic!("compiling '{}': {}", pat, e),
1556 };
1557 match r.is_match(hay) {
1558 Ok(b) => b,
1559 Err(e) => panic!("matching '{}' against '{}': {}", pat, hay, e),
1560 }
1561 }
1562
1563 #[test]
1564 fn test_literals_and_dot() {
1565 assert!(m("abc", "xxabcxx"));
1566 assert!(!m("abc", "xxabxx"));
1567 assert!(m("a.c", "abc"));
1568 assert!(!m("a.c", "a\nc"), "'.' must not cross a newline");
1569 assert!(m("(?s)a.c", "a\nc"), "unless 's' is set");
1570 assert!(m("a\\.c", "a.c"));
1571 assert!(!m("a\\.c", "abc"), "an escaped dot is a literal dot");
1572 }
1573
1574 #[test]
1575 fn test_anchors_and_boundaries() {
1576 assert!(m("^abc", "abc"));
1577 assert!(!m("^abc", "xabc"));
1578 assert!(m("abc$", "xabc"));
1579 assert!(!m("abc$", "abcx"));
1580 assert!(!m("^b", "a\nb"), "'^' is the start of the text without 'm'");
1581 assert!(m("(?m)^b$", "a\nb\nc"), "and of a line with it");
1582 assert!(m("\\bcat\\b", "the cat sat"));
1583 assert!(!m("\\bcat\\b", "concatenate"));
1584 assert!(m("\\Bcat", "concat"));
1585 assert!(m("\\bκαι\\b", "λόγος και"), "a word boundary is Unicode-aware");
1586 }
1587
1588 #[test]
1589 fn test_classes() {
1590 assert!(m("[abc]+", "zzbbzz"));
1591 assert!(!m("[abc]", "xyz"));
1592 assert!(m("[^abc]", "x"));
1593 assert!(!m("[^abc]", "a"));
1594 assert!(m("[a-f0-9]{6}", "colour #ff00aa here"));
1595 assert!(!m("[a-f0-9]{6}", "#ffz0aa"));
1596 assert!(m("[]]", "]"), "a ']' first thing in a class is a literal");
1597 assert!(m("[a-]", "-"), "a '-' last thing in a class is a literal");
1598 assert!(m("\\d\\d:\\d\\d", "at 09:45 today"));
1599 assert!(m("[\\d.]+", "3.14"));
1600 assert!(m("^[a-z&&[^aeiou]]+$", "rhythm"));
1601 assert!(!m("^[a-z&&[^aeiou]]+$", "rhyme"));
1602 assert!(m("^[[:alpha:]]+$", "Abc"));
1603 }
1604
1605 #[test]
1606 fn test_quantifiers() {
1607 assert!(m("ab*c", "ac"));
1608 assert!(m("ab*c", "abbbc"));
1609 assert!(!m("ab+c", "ac"));
1610 assert!(m("ab?c", "ac"));
1611 assert!(m("a{3}", "aaa"));
1612 assert!(!m("^a{3}$", "aa"));
1613 assert!(m("a{2,3}b", "aaab"));
1614 assert!(!m("^a{2,3}$", "aaaa"));
1615 assert!(m("a{2,}b", "aaaaab"));
1616 // A '{' that opens no quantifier is a literal brace.
1617 assert!(m("a{b}", "a{b}"));
1618 }
1619
1620 #[test]
1621 fn test_lazy_quantifiers_take_the_shorter_match() {
1622 let r = Regex::new("<.+?>").expect("compile");
1623 let span = r.find("<a><b>").expect("find").expect("a match");
1624 assert_eq!(Span { start: 0, end: 3 }, span, "the lazy '+?' should stop at the first '>'");
1625 let g = Regex::new("<.+>").expect("compile");
1626 let all = g.find("<a><b>").expect("find").expect("a match");
1627 assert_eq!(Span { start: 0, end: 6 }, all, "and the greedy '+' should run to the last");
1628 let u = Regex::new("(?U)<.+>").expect("compile");
1629 let swapped = u.find("<a><b>").expect("find").expect("a match");
1630 assert_eq!(Span { start: 0, end: 3 }, swapped, "'U' swaps greed");
1631 }
1632
1633 #[test]
1634 fn test_alternation_and_groups() {
1635 assert!(m("cat|dog", "a dog here"));
1636 assert!(m("(cat|dog)s", "two dogs"));
1637 assert!(!m("(cat|dog)s", "two dog"));
1638 assert!(m("(?:ab)+c", "ababc"));
1639 assert!(m("^(a|b)*$", "abba"));
1640 }
1641
1642 #[test]
1643 fn test_case_insensitivity() {
1644 let r = Regex::with_case("HeLLo", true).expect("compile");
1645 assert!(r.is_match("say hello there").expect("match"));
1646 let c = Regex::with_case("[A-Z]+", true).expect("compile");
1647 assert!(c.is_match("lower").expect("match"), "a range should fold too");
1648 let n = Regex::with_case("[^a]", true).expect("compile");
1649 assert!(!n.is_match("A").expect("match"),
1650 "a negated class must refuse the other case of what it excludes");
1651 assert!(m("(?i)ΣΟΦΟΣ", "σοφος"), "folding is Unicode");
1652 assert!(m("a(?i:B)c", "abc"));
1653 assert!(!m("a(?i:B)c", "abC"), "a scoped flag ends with its group");
1654 }
1655
1656 #[test]
1657 fn test_a_span_is_reported_in_bytes_through_multibyte_text() {
1658 let r = Regex::new("naïve").expect("compile");
1659 let hay = "a colour — naïve";
1660 let span = r.find(hay).expect("find").expect("a match");
1661 assert_eq!("naïve", &hay[span.start..span.end],
1662 "the span must index the original bytes");
1663 }
1664
1665 #[test]
1666 fn test_a_pathological_pattern_is_answered_in_linear_time() {
1667 // The classic exponential case for a backtracker without a visited set.
1668 let r = Regex::new("(a+)+$").expect("compile");
1669 let hay = "a".repeat(40) + "b";
1670 assert_eq!(r.find(&hay).expect("an answer, not a give-up"), None,
1671 "there is no match: the text ends in 'b'");
1672 }
1673
1674 #[test]
1675 fn test_an_empty_repetition_terminates() {
1676 // `(a*)*` can match nothing for ever; the matcher must notice and move on.
1677 assert!(m("^(a*)*$", ""));
1678 assert!(m("^(a*)*$", "aaa"));
1679 assert!(!m("^(a*)*$", "aab"));
1680 }
1681
1682 #[test]
1683 fn test_a_very_long_line_is_answered_rather_than_aborting_the_process() {
1684 // A minified file is one enormous line. The backtracking stack is on the heap, so neither
1685 // a character repetition nor a repeated group can overflow the call stack; reaching these
1686 // assertions at all is the proof.
1687 let hay = "a".repeat(500_000);
1688 let star = Regex::new("^a*$").expect("compile");
1689 assert!(star.is_match(&hay).expect("a long repetition"));
1690 let mixed = Regex::new("a+b?a").expect("compile");
1691 assert!(mixed.is_match(&hay).expect("and one that must backtrack"));
1692 let grouped = Regex::new("^(?:ab)+$").expect("compile");
1693 let pairs = "ab".repeat(200_000);
1694 assert!(grouped.is_match(&pairs).expect("a group repeated two hundred thousand times"));
1695 }
1696
1697 #[test]
1698 fn test_a_search_too_large_to_hold_says_so() {
1699 // Instructions times characters beyond the visited-set limit is refused, not guessed.
1700 let r = Regex::new("(?:a|b){2000}").expect("compile");
1701 let hay = "a".repeat(200_000);
1702 let e = r.find(&hay).expect_err("this search needs more state than allowed");
1703 assert!(fmt!("{}", e).contains("bits of search state"), "{}", e);
1704 }
1705
1706 #[test]
1707 fn test_bad_patterns_are_refused_with_a_reason() {
1708 for (pat, want) in [
1709 ("(ab", "unclosed '('"),
1710 ("[ab", "unclosed '['"),
1711 ("a)", "')' with no '('"),
1712 ("*a", "nothing before it"),
1713 ("a{3,2}", "at least 3"),
1714 ("[z-a]", "runs backwards"),
1715 ("a\\", "lone '\\'"),
1716 ("(?=a)", "look-around"),
1717 ("(a)\\1", "backreferences"),
1718 ("\\p{Nope}", "not known"),
1719 ("(?<n>a)(?<n>b)", "used twice"),
1720 ("\\q", "not a known escape"),
1721 ] {
1722 let e = Regex::new(pat).expect_err(&fmt!("'{}' should not compile", pat));
1723 let msg = fmt!("{}", e);
1724 assert!(msg.contains(want), "'{}' should say '{}', said: {}", pat, want, msg);
1725 }
1726 }
1727
1728 #[test]
1729 fn test_quote_makes_a_literal_of_anything() {
1730 let raw = "a.b*c(d)[e]{f}|g^h$i+j?k\\l#m&&n--o~~p";
1731 let r = Regex::new(&quote(raw)).expect("a quoted literal must compile");
1732 assert!(r.is_match(raw).expect("match"), "and must match itself");
1733 assert!(!r.is_match("axbxc").expect("match"), "without meaning anything else");
1734 }
1735
1736 #[test]
1737 fn test_alternation_is_leftmost_first() {
1738 let r = Regex::new("a|ab").expect("compile");
1739 let s = r.find("ab").expect("find").expect("a match");
1740 assert_eq!(Span { start: 0, end: 1 }, s, "the first alternative wins, as in Perl");
1741 }
1742
1743 #[test]
1744 fn test_empty_matches_follow_the_regex_crate() {
1745 // The `regex` crate documents that `a*` over "baaa" yields 0..0 and 1..4 and nothing at
1746 // 4..4: an empty match where the previous match ended is passed over.
1747 let r = Regex::new("a*").expect("compile");
1748 let got: Vec<Span> = r.find_iter("baaa").map(|x| x.expect("find")).collect();
1749 assert_eq!(got, vec![Span { start: 0, end: 0 }, Span { start: 1, end: 4 }]);
1750 let e = Regex::new("").expect("compile");
1751 assert_eq!(e.split("abc").expect("split"), vec!["", "a", "b", "c", ""]);
1752 }
1753
1754 #[test]
1755 fn test_expand_follows_the_regex_crate() {
1756 let r = Regex::new("(?P<y>\\d{4})-(\\d{2})").expect("compile");
1757 let c = r.captures("on 2026-09").expect("search").expect("a match");
1758 let mut out = String::new();
1759 c.expand("$2/${y} $$ $1a ${1}a $9 $", &mut out);
1760 assert_eq!(out, "09/2026 $ 2026a $");
1761 }
1762}