regast_syntax/
parser.rs

1use std::{collections::HashSet, sync::Arc};
2
3use crate::{
4    AstKind, ClassItem, ClassRange, ClassSet, GroupInfo, GroupKind, Node, NodeId, ParseError,
5    ParseErrorKind, Pattern, PerlClass, RepKind, Span,
6};
7
8const MAX_REPEAT: u32 = 1_000;
9
10/// Parse a regular-expression pattern.
11///
12/// # Errors
13///
14/// Returns [`ParseError`] for malformed syntax and deliberately unsupported features.
15pub fn parse(src: &str) -> Result<Pattern, ParseError> {
16    Parser::new(src).parse()
17}
18
19struct Parser {
20    src: Arc<str>,
21    pos: usize,
22    nodes: Vec<Node>,
23    groups: Vec<GroupInfo>,
24    names: HashSet<Box<str>>,
25}
26
27type ParsedClassAtom = (char, bool, Option<(PerlClass, bool)>);
28
29struct Frame {
30    group: Option<GroupFrame>,
31    expression_start: usize,
32    arm_start: usize,
33    arms: Vec<NodeId>,
34    parts: Vec<NodeId>,
35}
36
37struct GroupFrame {
38    start: usize,
39    kind: GroupKind,
40    group_slot: Option<usize>,
41}
42
43impl Frame {
44    const fn root() -> Self {
45        Self {
46            group: None,
47            expression_start: 0,
48            arm_start: 0,
49            arms: Vec::new(),
50            parts: Vec::new(),
51        }
52    }
53
54    const fn group(group: GroupFrame, inner_start: usize) -> Self {
55        Self {
56            group: Some(group),
57            expression_start: inner_start,
58            arm_start: inner_start,
59            arms: Vec::new(),
60            parts: Vec::new(),
61        }
62    }
63}
64
65impl Parser {
66    fn new(src: &str) -> Self {
67        Self {
68            src: Arc::from(src),
69            pos: 0,
70            nodes: Vec::new(),
71            groups: Vec::new(),
72            names: HashSet::new(),
73        }
74    }
75
76    fn parse(mut self) -> Result<Pattern, ParseError> {
77        let mut stack = vec![Frame::root()];
78        while let Some(c) = self.peek() {
79            match c {
80                '(' => {
81                    let group = self.open_group()?;
82                    stack.push(group);
83                }
84                ')' => self.close_group(&mut stack)?,
85                '|' => self.finish_arm(&mut stack),
86                '*' | '+' | '?' => {
87                    return Err(self.error(
88                        ParseErrorKind::DanglingQuantifier,
89                        self.pos,
90                        self.pos + 1,
91                    ));
92                }
93                _ => {
94                    let start = self.pos;
95                    let atom = self.atom()?;
96                    let repeated = self.quantify(atom, start)?;
97                    stack
98                        .last_mut()
99                        .expect("root frame exists")
100                        .parts
101                        .push(repeated);
102                }
103            }
104        }
105        if stack.len() != 1 {
106            let start = stack
107                .last()
108                .and_then(|frame| frame.group.as_ref())
109                .map_or(self.pos, |group| group.start);
110            return Err(self.error(ParseErrorKind::UnbalancedParen, start, self.pos));
111        }
112        let root = self.finish_frame(stack.pop().expect("root frame exists"), self.pos);
113        Ok(Pattern {
114            src: self.src,
115            nodes: self.nodes,
116            groups: self.groups,
117            root,
118        })
119    }
120
121    fn open_group(&mut self) -> Result<Frame, ParseError> {
122        let start = self.pos;
123        self.bump();
124        let kind = self.group_kind(start)?;
125        let group_slot = if let GroupKind::Capture { index, name } = &kind {
126            let slot = self.groups.len();
127            self.groups.push(GroupInfo {
128                index: *index,
129                name: name.clone(),
130                node: NodeId(u32::MAX),
131            });
132            Some(slot)
133        } else {
134            None
135        };
136        Ok(Frame::group(
137            GroupFrame {
138                start,
139                kind,
140                group_slot,
141            },
142            self.pos,
143        ))
144    }
145
146    fn group_kind(&mut self, start: usize) -> Result<GroupKind, ParseError> {
147        if self.peek() != Some('?') {
148            return Ok(GroupKind::Capture {
149                index: self.next_group_index(),
150                name: None,
151            });
152        }
153        self.bump();
154        match self.bump() {
155            Some(':') => Ok(GroupKind::NonCapture),
156            Some('<') => self.named_group(start),
157            _ => Err(self.error(
158                ParseErrorKind::UnsupportedFeature("lookaround or inline flags"),
159                start,
160                self.pos,
161            )),
162        }
163    }
164
165    fn named_group(&mut self, start: usize) -> Result<GroupKind, ParseError> {
166        let name_start = self.pos;
167        while self.peek().is_some_and(|c| c != '>') {
168            self.bump();
169        }
170        if self.peek() != Some('>') || self.pos == name_start {
171            return Err(self.error(
172                ParseErrorKind::UnsupportedFeature("invalid named group"),
173                start,
174                self.pos,
175            ));
176        }
177        let name: Box<str> = self.src[name_start..self.pos].into();
178        self.bump();
179        if !self.names.insert(name.clone()) {
180            return Err(self.error(
181                ParseErrorKind::DuplicateGroupName(name),
182                name_start,
183                self.pos - 1,
184            ));
185        }
186        Ok(GroupKind::Capture {
187            index: self.next_group_index(),
188            name: Some(name),
189        })
190    }
191
192    fn next_group_index(&self) -> u32 {
193        u32::try_from(self.groups.len()).expect("group arena exceeds u32") + 1
194    }
195
196    fn close_group(&mut self, stack: &mut Vec<Frame>) -> Result<(), ParseError> {
197        if stack.len() == 1 {
198            return Err(self.error(ParseErrorKind::UnbalancedParen, self.pos, self.pos + 1));
199        }
200        let end = self.pos;
201        self.bump();
202        let frame = stack.pop().expect("non-root frame exists");
203        let group = frame.group.as_ref().expect("group frame");
204        let start = group.start;
205        let kind = group.kind.clone();
206        let group_slot = group.group_slot;
207        let inner = self.finish_frame(frame, end);
208        let node = self.add_parent(AstKind::Group { kind, inner }, Span::new(start, self.pos));
209        if let Some(slot) = group_slot {
210            self.groups[slot].node = node;
211        }
212        let repeated = self.quantify(node, start)?;
213        stack
214            .last_mut()
215            .expect("parent frame exists")
216            .parts
217            .push(repeated);
218        Ok(())
219    }
220
221    fn finish_arm(&mut self, stack: &mut [Frame]) {
222        let frame = stack.last_mut().expect("root frame exists");
223        let parts = std::mem::take(&mut frame.parts);
224        let arm = self.finish_concat(parts, frame.arm_start, self.pos);
225        frame.arms.push(arm);
226        self.bump();
227        frame.arm_start = self.pos;
228    }
229
230    fn finish_frame(&mut self, mut frame: Frame, end: usize) -> NodeId {
231        let last = self.finish_concat(frame.parts, frame.arm_start, end);
232        if frame.arms.is_empty() {
233            return last;
234        }
235        frame.arms.push(last);
236        self.add_parent(
237            AstKind::Alt { arms: frame.arms },
238            Span::new(frame.expression_start, end),
239        )
240    }
241
242    fn finish_concat(&mut self, parts: Vec<NodeId>, start: usize, end: usize) -> NodeId {
243        match parts.len() {
244            0 => self.add(AstKind::Empty, Span::new(start, start)),
245            1 => parts[0],
246            _ => self.add_parent(AstKind::Concat { parts }, Span::new(start, end)),
247        }
248    }
249
250    fn quantify(&mut self, inner: NodeId, start: usize) -> Result<NodeId, ParseError> {
251        let kind = match self.peek() {
252            Some('?') => {
253                self.bump();
254                Some(RepKind::ZeroOrOne)
255            }
256            Some('*') => {
257                self.bump();
258                Some(RepKind::ZeroOrMore)
259            }
260            Some('+') => {
261                self.bump();
262                Some(RepKind::OneOrMore)
263            }
264            Some('{') => self.counted()?,
265            _ => None,
266        };
267        let Some(kind) = kind else { return Ok(inner) };
268        let greedy = if self.peek() == Some('?') {
269            self.bump();
270            false
271        } else {
272            true
273        };
274        if matches!(self.peek(), Some('*' | '+' | '?')) {
275            return Err(self.error(ParseErrorKind::DanglingQuantifier, self.pos, self.pos + 1));
276        }
277        Ok(self.add_parent(
278            AstKind::Repeat {
279                inner,
280                kind,
281                greedy,
282            },
283            Span::new(start, self.pos),
284        ))
285    }
286
287    fn counted(&mut self) -> Result<Option<RepKind>, ParseError> {
288        let start = self.pos;
289        let after_brace = start + 1;
290        if !self.src[after_brace..]
291            .chars()
292            .next()
293            .is_some_and(|c| c.is_ascii_digit())
294        {
295            return Ok(None);
296        }
297        self.bump();
298        let min = self.number()?;
299        let (max, had_comma) = if self.peek() == Some(',') {
300            self.bump();
301            let max = self
302                .peek()
303                .is_some_and(|c| c.is_ascii_digit())
304                .then(|| self.number())
305                .transpose()?;
306            (max, true)
307        } else {
308            (Some(min), false)
309        };
310        if self.peek() != Some('}') {
311            return Err(self.error(
312                ParseErrorKind::InvalidCounted,
313                start,
314                self.pos.max(start + 1),
315            ));
316        }
317        self.bump();
318        if min > MAX_REPEAT || max.is_some_and(|max| min > max || max > MAX_REPEAT) {
319            return Err(self.error(ParseErrorKind::InvalidCounted, start, self.pos));
320        }
321        Ok(Some(RepKind::Range {
322            min,
323            max: if had_comma { max } else { Some(min) },
324        }))
325    }
326
327    fn number(&mut self) -> Result<u32, ParseError> {
328        let start = self.pos;
329        while self.peek().is_some_and(|c| c.is_ascii_digit()) {
330            self.bump();
331        }
332        self.src[start..self.pos]
333            .parse()
334            .map_err(|_| self.error(ParseErrorKind::InvalidCounted, start, self.pos))
335    }
336
337    fn atom(&mut self) -> Result<NodeId, ParseError> {
338        let start = self.pos;
339        let Some(c) = self.bump() else {
340            return Ok(self.add(AstKind::Empty, Span::new(start, start)));
341        };
342        match c {
343            '[' => self.class(start),
344            '.' => Ok(self.add(AstKind::Dot, Span::new(start, self.pos))),
345            '\\' => self.escaped_atom(start),
346            '^' => Ok(self.add(
347                AstKind::Anchor {
348                    kind: crate::AnchorKind::Start,
349                },
350                Span::new(start, self.pos),
351            )),
352            '$' => Ok(self.add(
353                AstKind::Anchor {
354                    kind: crate::AnchorKind::End,
355                },
356                Span::new(start, self.pos),
357            )),
358            '(' | ')' | '|' => unreachable!("structural tokens are handled by parse loop"),
359            literal => Ok(self.add(
360                AstKind::Literal {
361                    c: literal,
362                    escaped: false,
363                },
364                Span::new(start, self.pos),
365            )),
366        }
367    }
368
369    fn escaped_atom(&mut self, start: usize) -> Result<NodeId, ParseError> {
370        let Some(escaped) = self.bump() else {
371            return Err(self.error(ParseErrorKind::InvalidEscape('\\'), start, self.pos));
372        };
373        if escaped.is_ascii_digit() {
374            return Err(self.error(
375                ParseErrorKind::UnsupportedFeature("backreferences"),
376                start,
377                self.pos,
378            ));
379        }
380        if let Some((class, negated)) = perl_class(escaped) {
381            let mut set = class.set();
382            if negated {
383                set = set.negate();
384            }
385            return Ok(self.add(
386                AstKind::Class {
387                    negated: false,
388                    items: vec![ClassItem::Perl { class, negated }],
389                    set,
390                },
391                Span::new(start, self.pos),
392            ));
393        }
394        let c = escape_char(escaped)
395            .ok_or_else(|| self.error(ParseErrorKind::InvalidEscape(escaped), start, self.pos))?;
396        Ok(self.add(
397            AstKind::Literal { c, escaped: true },
398            Span::new(start, self.pos),
399        ))
400    }
401
402    fn class(&mut self, start: usize) -> Result<NodeId, ParseError> {
403        let negated = if self.peek() == Some('^') {
404            self.bump();
405            true
406        } else {
407            false
408        };
409        let mut items = Vec::new();
410        let mut set = ClassSet::empty();
411        while let Some(c) = self.peek() {
412            if c == ']' && !items.is_empty() {
413                self.bump();
414                if negated {
415                    set = set.negate();
416                }
417                return Ok(self.add(
418                    AstKind::Class {
419                        negated,
420                        items,
421                        set,
422                    },
423                    Span::new(start, self.pos),
424                ));
425            }
426            let (left, escaped, perl) = self.class_atom(start)?;
427            if let Some((class, class_negated)) = perl {
428                let item_set = if class_negated {
429                    class.set().negate()
430                } else {
431                    class.set()
432                };
433                set = set.union(&item_set);
434                items.push(ClassItem::Perl {
435                    class,
436                    negated: class_negated,
437                });
438                continue;
439            }
440            if self.peek() == Some('-')
441                && self.src[self.pos + 1..]
442                    .chars()
443                    .next()
444                    .is_some_and(|c| c != ']')
445            {
446                self.bump();
447                let (right, _, right_perl) = self.class_atom(start)?;
448                if right_perl.is_some() || left > right {
449                    return Err(self.error(
450                        ParseErrorKind::InvalidRange {
451                            lo: left,
452                            hi: right,
453                        },
454                        start,
455                        self.pos,
456                    ));
457                }
458                set = set.union(&ClassSet::from_ranges([ClassRange {
459                    start: left,
460                    end: right,
461                }]));
462                items.push(ClassItem::Range {
463                    lo: left,
464                    hi: right,
465                });
466            } else {
467                set = set.union(&ClassSet::singleton(left));
468                items.push(ClassItem::Single { c: left, escaped });
469            }
470        }
471        Err(self.error(ParseErrorKind::UnclosedClass, start, self.pos))
472    }
473
474    fn class_atom(&mut self, class_start: usize) -> Result<ParsedClassAtom, ParseError> {
475        let start = self.pos;
476        let Some(c) = self.bump() else {
477            return Err(self.error(ParseErrorKind::UnclosedClass, class_start, self.pos));
478        };
479        if c != '\\' {
480            return Ok((c, false, None));
481        }
482        let Some(escaped) = self.bump() else {
483            return Err(self.error(ParseErrorKind::InvalidEscape('\\'), start, self.pos));
484        };
485        if let Some(perl) = perl_class(escaped) {
486            return Ok(('\0', true, Some(perl)));
487        }
488        let value = escape_char(escaped)
489            .ok_or_else(|| self.error(ParseErrorKind::InvalidEscape(escaped), start, self.pos))?;
490        Ok((value, true, None))
491    }
492
493    fn add(&mut self, kind: AstKind, span: Span) -> NodeId {
494        let id = NodeId(u32::try_from(self.nodes.len()).expect("node arena exceeds u32"));
495        self.nodes.push(Node {
496            kind,
497            span,
498            parent: None,
499        });
500        id
501    }
502
503    fn add_parent(&mut self, kind: AstKind, span: Span) -> NodeId {
504        let children = kind.children().to_vec();
505        let id = self.add(kind, span);
506        for child in children {
507            self.nodes[child.0 as usize].parent = Some(id);
508        }
509        id
510    }
511
512    fn peek(&self) -> Option<char> {
513        self.src[self.pos..].chars().next()
514    }
515
516    fn bump(&mut self) -> Option<char> {
517        let c = self.peek()?;
518        self.pos += c.len_utf8();
519        Some(c)
520    }
521
522    fn error(&self, kind: ParseErrorKind, start: usize, end: usize) -> ParseError {
523        ParseError::new(kind, Span::new(start, end), &self.src)
524    }
525}
526
527fn perl_class(c: char) -> Option<(PerlClass, bool)> {
528    Some(match c {
529        'd' => (PerlClass::Digit, false),
530        'D' => (PerlClass::Digit, true),
531        'w' => (PerlClass::Word, false),
532        'W' => (PerlClass::Word, true),
533        's' => (PerlClass::Space, false),
534        'S' => (PerlClass::Space, true),
535        _ => return None,
536    })
537}
538
539fn escape_char(c: char) -> Option<char> {
540    Some(match c {
541        'n' => '\n',
542        'r' => '\r',
543        't' => '\t',
544        '\\' | '.' | '+' | '*' | '?' | '(' | ')' | '[' | ']' | '{' | '}' | '|' | '^' | '$'
545        | '-' => c,
546        _ => return None,
547    })
548}
549
550#[cfg(test)]
551mod tests {
552    use super::*;
553
554    #[test]
555    fn parses_complete_grammar_and_parent_links() {
556        let pattern = parse(r"(?<word>[a-z]+)(?:\s|_){1,3}?").unwrap();
557        assert_eq!(pattern.groups().len(), 1);
558        assert_eq!(pattern.root().text(), pattern.source());
559        for cursor in pattern.root().walk().skip(1) {
560            assert!(cursor.parent().is_some());
561        }
562    }
563
564    #[test]
565    fn is_lossless_for_escapes() {
566        let pattern = parse(r"\n[\dA-Z]").unwrap();
567        assert_eq!(pattern.root().text(), r"\n[\dA-Z]");
568    }
569
570    #[test]
571    fn reports_unsupported_features() {
572        assert!(matches!(
573            parse(r"(a)\1").unwrap_err().kind,
574            ParseErrorKind::UnsupportedFeature("backreferences")
575        ));
576    }
577
578    #[test]
579    fn reports_each_structural_error() {
580        assert!(matches!(
581            parse("a**").unwrap_err().kind,
582            ParseErrorKind::DanglingQuantifier
583        ));
584        assert!(matches!(
585            parse("[z-a]").unwrap_err().kind,
586            ParseErrorKind::InvalidRange { .. }
587        ));
588        assert!(matches!(
589            parse("[abc").unwrap_err().kind,
590            ParseErrorKind::UnclosedClass
591        ));
592        assert!(matches!(
593            parse("a{3,1}").unwrap_err().kind,
594            ParseErrorKind::InvalidCounted
595        ));
596        assert!(matches!(
597            parse("a{1001}").unwrap_err().kind,
598            ParseErrorKind::InvalidCounted
599        ));
600        assert!(matches!(
601            parse("(?<x>a)(?<x>b)").unwrap_err().kind,
602            ParseErrorKind::DuplicateGroupName(_)
603        ));
604        assert!(matches!(
605            parse("(abc").unwrap_err().kind,
606            ParseErrorKind::UnbalancedParen
607        ));
608    }
609
610    #[test]
611    fn raw_brace_is_a_literal_when_not_a_count() {
612        let pattern = parse("a{x}").unwrap();
613        assert_eq!(pattern.root().text(), "a{x}");
614    }
615
616    #[test]
617    fn parses_deep_groups_without_call_stack_growth() {
618        let depth = 20_000;
619        let source = format!("{}a{}", "(".repeat(depth), ")".repeat(depth));
620        let pattern = parse(&source).unwrap();
621        assert_eq!(pattern.groups().len(), depth);
622        assert_eq!(pattern.root().walk().count(), depth + 1);
623        assert_eq!(pattern.root().text(), source);
624    }
625}
regast_syntax/parser.rs

regast_syntax/
parser.rs
