Skip to main content

trilean_json_shape_pattern/
lib.rs

1//! The regular expressions a `pattern` constraint may use: the subset of ECMAScript patterns whose meaning is the
2//! same in every JSON Schema validator, so the validator of `trilean-json-shape` and one written for the schema it emits
3//! agree. It is a crate of its own so that the derive, which refuses an unsupported pattern at compile time, and the
4//! validator, which matches with it, compile one grammar and cannot disagree about which patterns exist. A pattern
5//! is unanchored unless it says `^` and `$`, and is matched over Unicode scalar values, as ECMAScript does with the
6//! `u` flag, which is how Ajv compiles a schema's patterns.
7//!
8//! Supported: literal characters, `.` (any character except a line terminator), escaped punctuation (`\.`, `\\`,
9//! `\/` and the other syntax characters, and `\-` inside a class), classes with ranges and negation (`[a-z0-9._-]`,
10//! `[^/]`), groups (`(...)` and `(?:...)`), alternation, the greedy quantifiers `*`, `+` and `?`, and the anchors `^`
11//! and `$`. Anything else (counted repetition, lazy quantifiers, `\d`-style classes, lookaround) is refused, so a
12//! pattern that would mean something else in another engine does not compile.
13
14use std::fmt;
15
16/// Why a pattern is not in the supported subset.
17#[derive(Clone, Debug, PartialEq, Eq)]
18pub struct PatternError {
19    pub pattern: String,
20    pub reason: String,
21}
22
23/// The text as a JSON string literal, which is how every message writes a string. The escapes are the ones
24/// `JSON.stringify` writes: `\"`, `\\`, the short forms of the control characters that have one, and `\u00XX` for
25/// the rest below U+0020; everything else is written as it is.
26pub 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/// One state of the automaton a pattern compiles to. A state that consumes a character names the state to go to next.
80#[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/// A compiled pattern, matched by simulating a Thompson automaton: no backtracking and no recursion over the text,
96/// so matching costs time linear in the text times the size of the pattern, and constant stack, whatever the text.
97#[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    /// The character an escape after a backslash stands for: punctuation only, and `-` only inside a class, as the
169    /// `u` flag allows.
170    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
319/// The states reached so far at one position in the text.
320struct 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    /// Compiles `pattern`, or says which part of it is outside the supported subset.
346    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    /// Whether the pattern matches anywhere in `text`, as `new RegExp(pattern, "u").test(text)` does.
362    pub fn is_match(&self, text: &str) -> bool {
363        self.is_match_with_work(text).0
364    }
365
366    /// [`Pattern::is_match`] and the number of automaton states it visited, which is at most a constant times the
367    /// text's length plus one, times the number of states of the pattern.
368    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            // A match may start at any position, so the start of the pattern joins the states already reached.
376            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 &current.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    /// Adds `entry` and every state reachable from it without consuming a character to `frontier`.
428    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}