1use std::fmt;
15
16#[derive(Clone, Debug, PartialEq, Eq)]
18pub struct PatternError {
19 pub pattern: String,
20 pub reason: String,
21}
22
23pub fn json_quote(text: &str) -> String {
27 let mut quoted = String::with_capacity(text.len() + 2);
28 quoted.push('"');
29 for character in text.chars() {
30 match character {
31 '"' => quoted.push_str("\\\""),
32 '\\' => quoted.push_str("\\\\"),
33 '\n' => quoted.push_str("\\n"),
34 '\r' => quoted.push_str("\\r"),
35 '\t' => quoted.push_str("\\t"),
36 '\u{8}' => quoted.push_str("\\b"),
37 '\u{c}' => quoted.push_str("\\f"),
38 control if control < ' ' => quoted.push_str(&format!("\\u{:04x}", u32::from(control))),
39 other => quoted.push(other),
40 }
41 }
42 quoted.push('"');
43 quoted
44}
45
46impl fmt::Display for PatternError {
47 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
48 write!(
49 formatter,
50 "pattern {} is not supported: {}",
51 json_quote(&self.pattern),
52 self.reason
53 )
54 }
55}
56
57impl std::error::Error for PatternError {}
58
59#[derive(Clone, Debug)]
60enum Atom {
61 Char(char),
62 AnyChar,
63 Class {
64 negated: bool,
65 ranges: Vec<(char, char)>,
66 },
67 Group(Vec<Vec<Item>>),
68 Start,
69 End,
70}
71
72#[derive(Clone, Debug)]
73struct Item {
74 atom: Atom,
75 min: usize,
76 max: Option<usize>,
77}
78
79#[derive(Clone, Debug)]
81enum State {
82 Char(char, usize),
83 Any(usize),
84 Class {
85 negated: bool,
86 ranges: Vec<(char, char)>,
87 next: usize,
88 },
89 Split(usize, usize),
90 Start(usize),
91 End(usize),
92 Match,
93}
94
95#[derive(Clone, Debug)]
98pub struct Pattern {
99 states: Vec<State>,
100 entry: usize,
101}
102
103struct Parser<'a> {
104 pattern: &'a str,
105 chars: Vec<char>,
106 position: usize,
107}
108
109impl Parser<'_> {
110 fn fail<T>(&self, reason: &str) -> Result<T, PatternError> {
111 Err(PatternError {
112 pattern: self.pattern.to_owned(),
113 reason: format!("{reason} (at character {})", self.position),
114 })
115 }
116
117 fn peek(&self) -> Option<char> {
118 self.chars.get(self.position).copied()
119 }
120
121 fn eat(&mut self, expected: char) -> bool {
122 if self.peek() == Some(expected) {
123 self.position += 1;
124 true
125 } else {
126 false
127 }
128 }
129
130 fn alternatives(&mut self, nested: bool) -> Result<Vec<Vec<Item>>, PatternError> {
131 let mut alternatives = vec![self.sequence()?];
132 while self.eat('|') {
133 alternatives.push(self.sequence()?);
134 }
135 if nested && self.peek() != Some(')') {
136 return self.fail("a group is not closed");
137 }
138 Ok(alternatives)
139 }
140
141 fn sequence(&mut self) -> Result<Vec<Item>, PatternError> {
142 let mut items = Vec::new();
143 while let Some(next) = self.peek() {
144 if next == '|' || next == ')' {
145 break;
146 }
147 let atom = self.atom()?;
148 let (min, max) = if self.eat('*') {
149 (0, None)
150 } else if self.eat('+') {
151 (1, None)
152 } else if self.eat('?') {
153 (0, Some(1))
154 } else {
155 (1, Some(1))
156 };
157 if matches!(self.peek(), Some('*' | '+' | '?' | '{')) {
158 return self.fail("a second quantifier, a lazy quantifier and counted repetition are not supported");
159 }
160 if matches!(atom, Atom::Start | Atom::End) && (min, max) != (1, Some(1)) {
161 return self.fail("an anchor cannot be quantified");
162 }
163 items.push(Item { atom, min, max });
164 }
165 Ok(items)
166 }
167
168 fn escaped(&mut self, in_class: bool) -> Result<char, PatternError> {
171 let Some(escaped) = self.peek() else {
172 return self.fail("a pattern ends with a backslash");
173 };
174 self.position += 1;
175 match escaped {
176 '^' | '$' | '\\' | '.' | '*' | '+' | '?' | '(' | ')' | '[' | ']' | '{' | '}' | '|'
177 | '/' => Ok(escaped),
178 '-' if in_class => Ok(escaped),
179 _ => self.fail("only escaped punctuation is supported"),
180 }
181 }
182
183 fn atom(&mut self) -> Result<Atom, PatternError> {
184 let Some(next) = self.peek() else {
185 return self.fail("a pattern ends where an atom is expected");
186 };
187 self.position += 1;
188 match next {
189 '.' => Ok(Atom::AnyChar),
190 '^' => Ok(Atom::Start),
191 '$' => Ok(Atom::End),
192 '\\' => self.escaped(false).map(Atom::Char),
193 '(' => {
194 if self.eat('?') && !self.eat(':') {
195 return self.fail("only the (?: group form is supported");
196 }
197 let alternatives = self.alternatives(true)?;
198 self.position += 1;
199 Ok(Atom::Group(alternatives))
200 }
201 '[' => self.class(),
202 '*' | '+' | '?' | '{' | '}' | ']' => {
203 self.fail("a quantifier or bracket has nothing to apply to")
204 }
205 other => Ok(Atom::Char(other)),
206 }
207 }
208
209 fn class_char(&mut self) -> Result<char, PatternError> {
210 let Some(next) = self.peek() else {
211 return self.fail("a class is not closed");
212 };
213 self.position += 1;
214 if next == '\\' {
215 return self.escaped(true);
216 }
217 Ok(next)
218 }
219
220 fn class(&mut self) -> Result<Atom, PatternError> {
221 let negated = self.eat('^');
222 let mut ranges = Vec::new();
223 loop {
224 match self.peek() {
225 None => return self.fail("a class is not closed"),
226 Some(']') => {
227 self.position += 1;
228 break;
229 }
230 Some(_) => {}
231 }
232 let from = self.class_char()?;
233 let is_range = self.peek() == Some('-')
234 && self
235 .chars
236 .get(self.position + 1)
237 .is_some_and(|next| *next != ']');
238 if is_range {
239 self.position += 1;
240 let to = self.class_char()?;
241 if from > to {
242 return self.fail("a class range runs backwards");
243 }
244 ranges.push((from, to));
245 } else {
246 ranges.push((from, from));
247 }
248 }
249 if ranges.is_empty() {
250 return self.fail("an empty class is not supported");
251 }
252 Ok(Atom::Class { negated, ranges })
253 }
254}
255
256fn push(states: &mut Vec<State>, state: State) -> usize {
257 states.push(state);
258 states.len() - 1
259}
260
261fn compile_alternatives(alternatives: &[Vec<Item>], next: usize, states: &mut Vec<State>) -> usize {
262 let mut entries: Vec<usize> = alternatives
263 .iter()
264 .map(|sequence| compile_sequence(sequence, next, states))
265 .collect();
266 let mut entry = entries.pop().unwrap_or(next);
267 while let Some(earlier) = entries.pop() {
268 entry = push(states, State::Split(earlier, entry));
269 }
270 entry
271}
272
273fn compile_sequence(items: &[Item], next: usize, states: &mut Vec<State>) -> usize {
274 items.iter().rev().fold(next, |following, item| {
275 compile_item(item, following, states)
276 })
277}
278
279fn compile_item(item: &Item, next: usize, states: &mut Vec<State>) -> usize {
280 match (item.min, item.max) {
281 (0, Some(1)) => {
282 let atom = compile_atom(&item.atom, next, states);
283 push(states, State::Split(atom, next))
284 }
285 (0, None) => {
286 let split = push(states, State::Split(next, next));
287 let atom = compile_atom(&item.atom, split, states);
288 states[split] = State::Split(atom, next);
289 split
290 }
291 (1, None) => {
292 let split = push(states, State::Split(next, next));
293 let atom = compile_atom(&item.atom, split, states);
294 states[split] = State::Split(atom, next);
295 atom
296 }
297 _ => compile_atom(&item.atom, next, states),
298 }
299}
300
301fn compile_atom(atom: &Atom, next: usize, states: &mut Vec<State>) -> usize {
302 match atom {
303 Atom::Char(expected) => push(states, State::Char(*expected, next)),
304 Atom::AnyChar => push(states, State::Any(next)),
305 Atom::Class { negated, ranges } => push(
306 states,
307 State::Class {
308 negated: *negated,
309 ranges: ranges.clone(),
310 next,
311 },
312 ),
313 Atom::Group(alternatives) => compile_alternatives(alternatives, next, states),
314 Atom::Start => push(states, State::Start(next)),
315 Atom::End => push(states, State::End(next)),
316 }
317}
318
319struct Frontier {
321 stamp: Vec<usize>,
322 generation: usize,
323 consuming: Vec<usize>,
324 matched: bool,
325}
326
327impl Frontier {
328 fn new(size: usize) -> Self {
329 Frontier {
330 stamp: vec![0; size],
331 generation: 1,
332 consuming: Vec::new(),
333 matched: false,
334 }
335 }
336
337 fn clear(&mut self) {
338 self.generation += 1;
339 self.consuming.clear();
340 self.matched = false;
341 }
342}
343
344impl Pattern {
345 pub fn new(pattern: &str) -> Result<Pattern, PatternError> {
347 let mut parser = Parser {
348 pattern,
349 chars: pattern.chars().collect(),
350 position: 0,
351 };
352 let alternatives = parser.alternatives(false)?;
353 if parser.position != parser.chars.len() {
354 return parser.fail("an unmatched closing parenthesis");
355 }
356 let mut states = vec![State::Match];
357 let entry = compile_alternatives(&alternatives, 0, &mut states);
358 Ok(Pattern { states, entry })
359 }
360
361 pub fn is_match(&self, text: &str) -> bool {
363 self.is_match_with_work(text).0
364 }
365
366 pub fn is_match_with_work(&self, text: &str) -> (bool, u64) {
369 let input: Vec<char> = text.chars().collect();
370 let mut work = 0;
371 let mut stack = Vec::new();
372 let mut current = Frontier::new(self.states.len());
373 let mut following = Frontier::new(self.states.len());
374 for position in 0..=input.len() {
375 self.close(
377 self.entry,
378 position,
379 input.len(),
380 &mut current,
381 &mut stack,
382 &mut work,
383 );
384 if current.matched {
385 return (true, work);
386 }
387 let Some(&found) = input.get(position) else {
388 break;
389 };
390 following.clear();
391 for &state in ¤t.consuming {
392 work += 1;
393 let next = match &self.states[state] {
394 State::Char(expected, next) if *expected == found => Some(*next),
395 State::Any(next) if !matches!(found, '\n' | '\r' | '\u{2028}' | '\u{2029}') => {
396 Some(*next)
397 }
398 State::Class {
399 negated,
400 ranges,
401 next,
402 } if ranges
403 .iter()
404 .any(|(from, to)| (*from..=*to).contains(&found))
405 != *negated =>
406 {
407 Some(*next)
408 }
409 _ => None,
410 };
411 if let Some(next) = next {
412 self.close(
413 next,
414 position + 1,
415 input.len(),
416 &mut following,
417 &mut stack,
418 &mut work,
419 );
420 }
421 }
422 std::mem::swap(&mut current, &mut following);
423 }
424 (false, work)
425 }
426
427 fn close(
429 &self,
430 entry: usize,
431 position: usize,
432 length: usize,
433 frontier: &mut Frontier,
434 stack: &mut Vec<usize>,
435 work: &mut u64,
436 ) {
437 stack.push(entry);
438 while let Some(state) = stack.pop() {
439 if frontier.stamp[state] == frontier.generation {
440 continue;
441 }
442 frontier.stamp[state] = frontier.generation;
443 *work += 1;
444 match &self.states[state] {
445 State::Split(first, second) => {
446 stack.push(*second);
447 stack.push(*first);
448 }
449 State::Start(next) if position == 0 => stack.push(*next),
450 State::End(next) if position == length => stack.push(*next),
451 State::Start(_) | State::End(_) => {}
452 State::Match => frontier.matched = true,
453 State::Char(..) | State::Any(_) | State::Class { .. } => {
454 frontier.consuming.push(state)
455 }
456 }
457 }
458 }
459}
460
461#[cfg(test)]
462mod tests {
463 use super::Pattern;
464
465 fn matches(pattern: &str, text: &str) -> bool {
466 Pattern::new(pattern)
467 .expect("a supported pattern")
468 .is_match(text)
469 }
470
471 #[test]
472 fn anchors_and_classes() {
473 assert!(matches("^[a-z0-9][a-z0-9._-]*$", "a.b_c-1"));
474 assert!(!matches("^[a-z0-9][a-z0-9._-]*$", "A"));
475 assert!(!matches("^[a-z0-9][a-z0-9._-]*$", "-a"));
476 assert!(!matches("^[a-z0-9][a-z0-9._-]*$", "a\n"));
477 assert!(matches("[0-9]", "x7y"));
478 }
479
480 #[test]
481 fn groups_and_alternation() {
482 let source = r"^(recorded: .+|[a-z0-9._-]+\.test\.ts: .+)$";
483 assert!(matches(source, "recorded: x"));
484 assert!(matches(source, "a.test.ts: a > b"));
485 assert!(!matches(source, "a.test.ts:"));
486 assert!(!matches(source, "recorded: "));
487 assert!(matches("^(?:ab)+$", "abab"));
488 assert!(!matches("^(?:ab)+$", "aba"));
489 }
490
491 #[test]
492 fn dot_stops_at_a_line_terminator_and_counts_characters() {
493 assert!(!matches("^.$", "\n"));
494 assert!(!matches("^.$", "\u{2028}"));
495 assert!(matches("^.$", "\u{1F600}"));
496 assert!(!matches("^..$", "\u{1F600}"));
497 assert!(matches("^[^/]$", "\u{1F600}"));
498 assert!(matches("^\u{1F600}$", "\u{1F600}"));
499 }
500
501 #[test]
502 fn unsupported_syntax_is_refused() {
503 for source in [
504 "a{2}", "a*?", r"\d", r"a\-b", "(?=a)", "(a", "a)", "[", "[]", "[z-a]", "*", "^*",
505 ] {
506 assert!(Pattern::new(source).is_err(), "{source} must be refused");
507 }
508 assert!(Pattern::new(r"[a\-z]").is_ok());
509 }
510
511 #[test]
512 fn matching_is_linear_in_the_text_and_uses_no_stack_per_character() {
513 let long = "a".repeat(200_000);
514 assert!(matches("^[a-z]*$", &long));
515 assert!(!matches("^[a-z]*$", &format!("{long}!")));
516 let pattern = Pattern::new("^(?:a|a)*$").expect("a supported pattern");
517 let (_, short) = pattern.is_match_with_work(&format!("{}b", "a".repeat(1_000)));
518 let (_, double) = pattern.is_match_with_work(&format!("{}b", "a".repeat(2_000)));
519 assert!(
520 short <= 12 * 1_001,
521 "{short} state visits for 1001 characters"
522 );
523 assert!(
524 double <= 12 * 2_001,
525 "{double} state visits for 2001 characters"
526 );
527 assert!(double < 3 * short, "{double} is not about twice {short}");
528 }
529
530 #[test]
531 fn an_unanchored_search_is_linear_too() {
532 let pattern = Pattern::new("[0-9]+x").expect("a supported pattern");
533 let (_, short) = pattern.is_match_with_work(&"1".repeat(1_000));
534 let (_, double) = pattern.is_match_with_work(&"1".repeat(2_000));
535 assert!(double < 3 * short, "{double} is not about twice {short}");
536 }
537
538 #[test]
539 fn nested_empty_loops_terminate() {
540 assert!(matches("^(?:a*)*$", "aaa"));
541 assert!(!matches("^(?:a*)*b$", "aaa"));
542 }
543}