Skip to main content

nodejs/
regexp_syntax.rs

1//! Early-error validation of a JavaScript regular-expression pattern.
2//!
3//! [`crate::regexp`] translates a pattern into fancy-regex syntax and lets that
4//! engine reject what it cannot compile — which accepts patterns JavaScript
5//! refuses (`/{/u`, `/\-/u`, a duplicate group name) and words the ones it does
6//! refuse in its own vocabulary. This module is the pattern GRAMMAR of
7//! ECMA-262 22.2.1 (with the Annex B.1.2 relaxations outside unicode mode),
8//! walked once before translation, reporting V8's wording
9//! (`src/regexp/regexp-error.h`) for the first early error.
10//!
11//! It only ever REJECTS: a pattern it accepts still goes through `translate`
12//! and the engine, so a gap here costs a worse message, never a wrong match.
13//! `v` (unicodeSets) class bodies nest and use set operators that this walk
14//! does not model; their brackets are balanced and their contents left to the
15//! engine.
16
17/// The first early error in `pat`, with V8's reason text.
18pub fn validate(pat: &str, unicode: bool, sets: bool) -> Result<(), String> {
19    let chars: Vec<char> = pat.chars().collect();
20    let (group_total, names) = group_census(&chars);
21    let mut p = Parser {
22        c: &chars,
23        i: 0,
24        unicode,
25        sets,
26        group_total,
27        has_named: !names.is_empty(),
28        all_names: names,
29        path_names: Vec::new(),
30    };
31    p.disjunction()?;
32    if p.i < p.c.len() {
33        // `disjunction` stops at an unmatched `)`.
34        return Err("Unmatched ')'".to_string());
35    }
36    Ok(())
37}
38
39/// How many capturing groups the pattern has and the names they carry. A decimal
40/// escape is a backreference only when it does not exceed the TOTAL count, and
41/// `\k` is only a named reference when a name exists anywhere in the pattern —
42/// both are decided before the walk reaches the group, so they are counted first.
43fn group_census(c: &[char]) -> (usize, Vec<String>) {
44    let mut count = 0;
45    let mut names = Vec::new();
46    let mut in_class = false;
47    let mut i = 0;
48    while i < c.len() {
49        match c[i] {
50            '\\' => i += 1,
51            '[' => in_class = true,
52            ']' => in_class = false,
53            '(' if !in_class => {
54                if c.get(i + 1) != Some(&'?') {
55                    count += 1;
56                } else if c.get(i + 2) == Some(&'<') && !matches!(c.get(i + 3), Some('=' | '!')) {
57                    count += 1;
58                    names.push(c[i + 3..].iter().take_while(|ch| **ch != '>').collect());
59                }
60            }
61            _ => {}
62        }
63        i += 1;
64    }
65    (count, names)
66}
67
68/// Whether a quantifier may follow the atom just parsed.
69#[derive(Clone, Copy)]
70enum Quant {
71    Yes,
72    /// `^`, `$`, `\b`, `\B`: nothing to repeat.
73    Assertion,
74    /// A lookbehind (or a lookahead under `u`): a group that cannot repeat.
75    Refused,
76}
77
78/// What one ClassAtom contributes to a range: a single code point, or a set
79/// (`\d`, `\p{…}`) which cannot be a range endpoint in unicode mode.
80enum ClassAtom {
81    Char(u32),
82    Set,
83}
84
85struct Parser<'a> {
86    c: &'a [char],
87    i: usize,
88    unicode: bool,
89    sets: bool,
90    group_total: usize,
91    has_named: bool,
92    all_names: Vec<String>,
93    /// Group names declared on the path from the pattern's start to here. A
94    /// name may repeat only across alternatives that exclude one another.
95    path_names: Vec<String>,
96}
97
98type Res<T> = Result<T, String>;
99
100impl Parser<'_> {
101    fn peek(&self) -> Option<char> {
102        self.c.get(self.i).copied()
103    }
104
105    fn peek_at(&self, n: usize) -> Option<char> {
106        self.c.get(self.i + n).copied()
107    }
108
109    fn disjunction(&mut self) -> Res<()> {
110        let base = self.path_names.len();
111        let mut declared_in_any: Vec<String> = Vec::new();
112        loop {
113            self.path_names.truncate(base);
114            self.alternative()?;
115            declared_in_any.extend(self.path_names.drain(base..));
116            if self.peek() == Some('|') {
117                self.i += 1;
118            } else {
119                break;
120            }
121        }
122        // After the disjunction every alternative's names are on the path.
123        self.path_names.extend(declared_in_any);
124        Ok(())
125    }
126
127    fn alternative(&mut self) -> Res<()> {
128        while let Some(c) = self.peek() {
129            if c == '|' || c == ')' {
130                break;
131            }
132            self.term()?;
133        }
134        Ok(())
135    }
136
137    fn term(&mut self) -> Res<()> {
138        let c = self.peek().expect("term called at end of pattern");
139        // What may follow the atom. `Assertion` (`^ $ \b \B`) takes no quantifier
140        // at all (`Nothing to repeat`); a lookbehind, or a lookahead under `u`,
141        // is a group that merely refuses one (`Invalid quantifier`).
142        let quantifiable = match c {
143            '^' | '$' => {
144                self.i += 1;
145                Quant::Assertion
146            }
147            '(' => self.group()?,
148            '\\' => self.atom_escape()?,
149            '[' => {
150                self.class()?;
151                Quant::Yes
152            }
153            '*' | '+' | '?' => return Err("Nothing to repeat".to_string()),
154            '{' => {
155                if self.braces_quantifier()?.is_some() {
156                    return Err("Nothing to repeat".to_string());
157                }
158                if self.unicode {
159                    return Err("Lone quantifier brackets".to_string());
160                }
161                self.i += 1;
162                Quant::Yes
163            }
164            '}' | ']' if self.unicode => {
165                return Err("Lone quantifier brackets".to_string());
166            }
167            _ => {
168                self.i += 1;
169                Quant::Yes
170            }
171        };
172        self.quantifier(quantifiable)
173    }
174
175    /// An optional quantifier after an atom. `quantifiable` is false for
176    /// assertions, which refuse one (`/^*/`, `/\b+/`, a lookbehind).
177    fn quantifier(&mut self, quantifiable: Quant) -> Res<()> {
178        let quantified = match self.peek() {
179            Some('*' | '+' | '?') => {
180                self.i += 1;
181                true
182            }
183            Some('{') => match self.braces_quantifier()? {
184                Some(()) => true,
185                None if self.unicode => return Err("Incomplete quantifier".to_string()),
186                // Outside unicode mode a malformed `{` is just a literal.
187                None => false,
188            },
189            _ => false,
190        };
191        if quantified {
192            match quantifiable {
193                Quant::Yes => {}
194                Quant::Assertion => return Err("Nothing to repeat".to_string()),
195                Quant::Refused => return Err("Invalid quantifier".to_string()),
196            }
197            if self.peek() == Some('?') {
198                self.i += 1; // lazy
199            }
200        }
201        Ok(())
202    }
203
204    /// A `{n}`, `{n,}` or `{n,m}` at the cursor. `Ok(Some)` consumes it,
205    /// `Ok(None)` leaves the cursor alone (not a quantifier), and `n > m` is the
206    /// error V8 words as "numbers out of order".
207    fn braces_quantifier(&mut self) -> Res<Option<()>> {
208        let mut j = self.i + 1;
209        let digits = |j: &mut usize| {
210            let start = *j;
211            while self.c.get(*j).is_some_and(char::is_ascii_digit) {
212                *j += 1;
213            }
214            self.c[start..*j].iter().collect::<String>()
215        };
216        let lo = digits(&mut j);
217        if lo.is_empty() {
218            return Ok(None);
219        }
220        let mut hi = None;
221        if self.c.get(j) == Some(&',') {
222            j += 1;
223            let h = digits(&mut j);
224            hi = Some(h);
225        }
226        if self.c.get(j) != Some(&'}') {
227            return Ok(None);
228        }
229        if let Some(h) = hi.filter(|h| !h.is_empty()) {
230            // Compared as decimal strings of arbitrary length, since either
231            // bound may exceed every machine integer.
232            let norm = |s: &str| s.trim_start_matches('0').to_string();
233            let (a, b) = (norm(&lo), norm(&h));
234            if a.len() > b.len() || (a.len() == b.len() && a > b) {
235                return Err("numbers out of order in {} quantifier".to_string());
236            }
237        }
238        self.i = j + 1;
239        Ok(Some(()))
240    }
241
242    /// A parenthesised group. Returns whether a quantifier may follow it.
243    fn group(&mut self) -> Res<Quant> {
244        self.i += 1; // (
245        let mut quantifiable = Quant::Yes;
246        if self.peek() == Some('?') {
247            match (self.peek_at(1), self.peek_at(2)) {
248                (Some(':'), _) => self.i += 2,
249                (Some('=' | '!'), _) => {
250                    self.i += 2;
251                    // Annex B.1.2: a lookahead is quantifiable outside `u`.
252                    if self.unicode {
253                        quantifiable = Quant::Refused;
254                    }
255                }
256                (Some('<'), Some('=' | '!')) => {
257                    self.i += 3;
258                    quantifiable = Quant::Refused;
259                }
260                (Some('<'), _) => {
261                    self.i += 2;
262                    let name = self.group_name()?;
263                    if self.path_names.contains(&name) {
264                        return Err("Duplicate capture group name".to_string());
265                    }
266                    self.path_names.push(name);
267                }
268                // `(?ims-ims:` modifiers: judged by `regexp::check_group`.
269                _ => {
270                    self.i += 1;
271                    while self
272                        .peek()
273                        .is_some_and(|c| matches!(c, 'i' | 'm' | 's' | '-'))
274                    {
275                        self.i += 1;
276                    }
277                    if self.peek() != Some(':') {
278                        return Err("Invalid group".to_string());
279                    }
280                    self.i += 1;
281                }
282            }
283        }
284        self.disjunction()?;
285        if self.peek() != Some(')') {
286            return Err("Unterminated group".to_string());
287        }
288        self.i += 1;
289        Ok(quantifiable)
290    }
291
292    /// The `name>` of a `(?<name>` / `\k<name>`, cursor just past the `<`.
293    fn group_name(&mut self) -> Res<String> {
294        const BAD: &str = "Invalid capture group name";
295        let mut name = String::new();
296        loop {
297            let Some(c) = self.peek() else {
298                return Err(BAD.to_string());
299            };
300            self.i += 1;
301            let ch = match c {
302                '>' => break,
303                '\\' if self.peek() == Some('u') => {
304                    self.i += 1;
305                    self.unicode_escape_value(true)
306                        .ok_or_else(|| BAD.to_string())?
307                }
308                c => c as u32,
309            };
310            let ch = char::from_u32(ch).ok_or_else(|| BAD.to_string())?;
311            let ok = if name.is_empty() {
312                ch == '$' || ch == '_' || ch.is_alphabetic()
313            } else {
314                ch == '$'
315                    || ch == '_'
316                    || ch.is_alphanumeric()
317                    || ch == '\u{200C}'
318                    || ch == '\u{200D}'
319            };
320            if !ok {
321                return Err(BAD.to_string());
322            }
323            name.push(ch);
324        }
325        if name.is_empty() {
326            return Err(BAD.to_string());
327        }
328        Ok(name)
329    }
330
331    /// After `\u`: the code point of `XXXX` (with a following `\uXXXX` low
332    /// surrogate folded in) or, when `braces`, of `{X…}`. Consumes on success.
333    fn unicode_escape_value(&mut self, braces: bool) -> Option<u32> {
334        let hex = |p: &Self, from: usize, n: usize| -> Option<u32> {
335            let mut v = 0;
336            for k in 0..n {
337                v = v * 16 + p.c.get(from + k)?.to_digit(16)?;
338            }
339            Some(v)
340        };
341        if braces && self.peek() == Some('{') {
342            let mut j = self.i + 1;
343            let mut v: u32 = 0;
344            let mut any = false;
345            while let Some(d) = self.c.get(j).and_then(|c| c.to_digit(16)) {
346                v = v.saturating_mul(16).saturating_add(d);
347                any = true;
348                j += 1;
349            }
350            if !any || self.c.get(j) != Some(&'}') || v > 0x10FFFF {
351                return None;
352            }
353            self.i = j + 1;
354            return Some(v);
355        }
356        let hi = hex(self, self.i, 4)?;
357        self.i += 4;
358        if (0xD800..=0xDBFF).contains(&hi)
359            && self.peek() == Some('\\')
360            && self.peek_at(1) == Some('u')
361        {
362            if let Some(lo) = hex(self, self.i + 2, 4).filter(|l| (0xDC00..=0xDFFF).contains(l)) {
363                self.i += 6;
364                return Some(0x10000 + ((hi - 0xD800) << 10) + (lo - 0xDC00));
365            }
366        }
367        Some(hi)
368    }
369
370    /// `\` outside a class. Returns whether a quantifier may follow.
371    fn atom_escape(&mut self) -> Res<Quant> {
372        self.i += 1; // backslash
373        let Some(c) = self.peek() else {
374            return Err("\\ at end of pattern".to_string());
375        };
376        match c {
377            'b' | 'B' => {
378                self.i += 1;
379                Ok(Quant::Assertion)
380            }
381            '1'..='9' => {
382                let start = self.i;
383                while self.peek().is_some_and(|d| d.is_ascii_digit()) {
384                    self.i += 1;
385                }
386                let n: usize = self.c[start..self.i]
387                    .iter()
388                    .collect::<String>()
389                    .parse()
390                    .unwrap_or(usize::MAX);
391                if n > self.group_total {
392                    if self.unicode {
393                        return Err("Invalid escape".to_string());
394                    }
395                    // Annex B: a legacy octal escape, or the digit itself.
396                    self.i = start + 1;
397                }
398                Ok(Quant::Yes)
399            }
400            'k' if self.unicode || self.has_named => {
401                self.i += 1;
402                if self.peek() != Some('<') {
403                    return Err("Invalid named reference".to_string());
404                }
405                self.i += 1;
406                let name = self
407                    .group_name()
408                    .map_err(|_| "Invalid named reference".to_string())?;
409                if !self.all_names.contains(&name) {
410                    return Err("Invalid named capture referenced".to_string());
411                }
412                Ok(Quant::Yes)
413            }
414            _ => {
415                self.character_escape(false)?;
416                Ok(Quant::Yes)
417            }
418        }
419    }
420
421    /// The escape after a `\` that stands for one character or a class set,
422    /// cursor on its first character. Shared by atoms and class atoms.
423    fn character_escape(&mut self, in_class: bool) -> Res<ClassAtom> {
424        let c = self.peek().expect("caller checked for end of pattern");
425        self.i += 1;
426        let ch = |v: u32| Ok(ClassAtom::Char(v));
427        match c {
428            'd' | 'D' | 's' | 'S' | 'w' | 'W' => Ok(ClassAtom::Set),
429            'f' => ch(0x0C),
430            'n' => ch(0x0A),
431            'r' => ch(0x0D),
432            't' => ch(0x09),
433            'v' => ch(0x0B),
434            'b' if in_class => ch(0x08),
435            'c' => match self.peek() {
436                Some(l) if l.is_ascii_alphabetic() => {
437                    self.i += 1;
438                    ch(l as u32 % 32)
439                }
440                Some(l) if in_class && !self.unicode && (l.is_ascii_digit() || l == '_') => {
441                    self.i += 1;
442                    ch(l as u32 % 32)
443                }
444                _ if self.unicode => Err("Invalid Unicode escape".to_string()),
445                // Annex B: the backslash stands for itself; `c` is read next.
446                _ => {
447                    self.i -= 1;
448                    ch('\\' as u32)
449                }
450            },
451            '0' if !self.peek().is_some_and(|d| d.is_ascii_digit()) => ch(0),
452            '0'..='7' if !self.unicode => {
453                // Legacy octal escape.
454                let mut v = c.to_digit(8).unwrap_or(0);
455                let max = if c <= '3' { 3 } else { 2 };
456                for _ in 1..max {
457                    match self.peek().and_then(|d| d.to_digit(8)) {
458                        Some(d) => {
459                            v = v * 8 + d;
460                            self.i += 1;
461                        }
462                        None => break,
463                    }
464                }
465                ch(v)
466            }
467            '0'..='9' if self.unicode => Err(if in_class || c == '0' {
468                "Invalid decimal escape".to_string()
469            } else {
470                "Invalid escape".to_string()
471            }),
472            '8' | '9' => ch(c as u32),
473            'x' => {
474                let h = |k: usize| self.c.get(self.i + k).and_then(|d| d.to_digit(16));
475                match (h(0), h(1)) {
476                    (Some(a), Some(b)) => {
477                        self.i += 2;
478                        ch(a * 16 + b)
479                    }
480                    _ if self.unicode => Err("Invalid escape".to_string()),
481                    _ => ch('x' as u32),
482                }
483            }
484            'u' => match self.unicode_escape_value(self.unicode) {
485                Some(v) => ch(v),
486                None if self.unicode => Err("Invalid Unicode escape".to_string()),
487                None => ch('u' as u32),
488            },
489            'p' | 'P' if self.unicode => {
490                if self.peek() != Some('{') {
491                    return Err(property_error(in_class));
492                }
493                let close = self.c[self.i..].iter().position(|&d| d == '}');
494                let Some(close) = close else {
495                    return Err(property_error(in_class));
496                };
497                let name: String = self.c[self.i + 1..self.i + close].iter().collect();
498                if !property_is_known(&name) {
499                    return Err(property_error(in_class));
500                }
501                self.i += close + 1;
502                Ok(ClassAtom::Set)
503            }
504            // SyntaxCharacter and `/` are always identity escapes; `-` only
505            // inside a class under `u`.
506            '^' | '$' | '\\' | '.' | '*' | '+' | '?' | '(' | ')' | '[' | ']' | '{' | '}' | '|'
507            | '/' => ch(c as u32),
508            '-' if in_class || !self.unicode => ch('-' as u32),
509            // ClassSetReservedPunctuator: escapable inside a `v` class.
510            '&' | '!' | '#' | '%' | ',' | ':' | ';' | '<' | '=' | '>' | '@' | '`' | '~'
511                if in_class && self.sets =>
512            {
513                ch(c as u32)
514            }
515            _ if self.unicode => Err("Invalid escape".to_string()),
516            _ => ch(c as u32),
517        }
518    }
519
520    /// A `[...]` class, cursor on the `[`.
521    fn class(&mut self) -> Res<()> {
522        const UNTERMINATED: &str = "Unterminated character class";
523        self.i += 1; // [
524        if self.peek() == Some('^') {
525            self.i += 1;
526        }
527        loop {
528            match self.peek() {
529                None => return Err(UNTERMINATED.to_string()),
530                Some(']') => {
531                    self.i += 1;
532                    return Ok(());
533                }
534                _ => {}
535            }
536            if self.sets && self.set_syntax()? {
537                continue;
538            }
539            let lo = self.class_atom()?;
540            if self.peek() == Some('-')
541                && self.peek_at(1).is_some_and(|c| c != ']')
542                && !(self.sets && self.peek_at(1) == Some('-'))
543            {
544                self.i += 1;
545                let hi = self.class_atom()?;
546                match (lo, hi) {
547                    (ClassAtom::Char(a), ClassAtom::Char(b)) if a > b => {
548                        return Err("Range out of order in character class".to_string());
549                    }
550                    (ClassAtom::Set, _) | (_, ClassAtom::Set) if self.unicode => {
551                        return Err("Invalid character class".to_string());
552                    }
553                    _ => {}
554                }
555            }
556        }
557    }
558
559    fn class_atom(&mut self) -> Res<ClassAtom> {
560        let c = self
561            .peek()
562            .ok_or_else(|| "Unterminated character class".to_string())?;
563        if c != '\\' {
564            self.i += 1;
565            return Ok(ClassAtom::Char(c as u32));
566        }
567        self.i += 1;
568        match self.peek() {
569            None => Err("\\ at end of pattern".to_string()),
570            // `\k`, `\B` and the decimal forms inside a class are judged by
571            // `regexp::translate`, which owns their wording.
572            Some('B') if self.unicode => Err("Invalid escape".to_string()),
573            Some('k' | 'B') => {
574                let k = self.peek().unwrap_or('k');
575                self.i += 1;
576                Ok(ClassAtom::Char(k as u32))
577            }
578            Some(_) => self.character_escape(true),
579        }
580    }
581
582    /// The `v`-mode (unicodeSets) members of a class that are not a plain
583    /// ClassAtom: a nested class, the `&&` and `--` operators, a `\q{…}` string
584    /// disjunction, and the ClassSetSyntaxCharacters that may not appear bare.
585    /// Returns true when it consumed something.
586    fn set_syntax(&mut self) -> Res<bool> {
587        match (self.peek(), self.peek_at(1)) {
588            (Some('['), _) => {
589                self.class()?;
590                Ok(true)
591            }
592            (Some('&'), Some('&')) | (Some('-'), Some('-')) => {
593                self.i += 2;
594                Ok(true)
595            }
596            (Some('\\'), Some('q')) if self.peek_at(2) == Some('{') => {
597                while self.peek().is_some_and(|c| c != '}') {
598                    self.i += 1;
599                }
600                self.i += 1;
601                Ok(true)
602            }
603            (Some('(' | ')' | '{' | '}' | '/' | '|'), _) => {
604                Err("Invalid character in character class".to_string())
605            }
606            _ => Ok(false),
607        }
608    }
609}
610
611fn property_error(in_class: bool) -> String {
612    if in_class {
613        "Invalid property name in character class".to_string()
614    } else {
615        "Invalid property name".to_string()
616    }
617}
618
619/// Whether `name` (the text inside `\p{…}`) names a property the engine knows.
620/// The set JavaScript accepts is the Unicode-property subset ECMA-262 lists
621/// (Table 68/69), which the regex layer's property tables cover; asking it to
622/// compile `\p{name}` is the lookup.
623fn property_is_known(name: &str) -> bool {
624    !name.is_empty() && regex::Regex::new(&format!("\\p{{{name}}}")).is_ok()
625}