1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
//! Alternation, concatenation and quantifier parsing.
use super::ast::*;
use super::lexer::TokenKind;
use super::state::Parser;
use crate::error::{Error, ErrorKind, Result};
impl Parser<'_> {
/// Parses alternation (lowest precedence): a|b|c
pub(super) fn parse_alternation(&mut self) -> Result<Expr> {
let mut left = self.parse_concat()?;
if matches!(self.current.kind, TokenKind::Pipe) {
let mut alternatives = vec![left];
while matches!(self.current.kind, TokenKind::Pipe) {
self.advance()?;
alternatives.push(self.parse_concat()?);
}
left = Expr::Alt(alternatives);
}
Ok(left)
}
/// Parses concatenation: abc
fn parse_concat(&mut self) -> Result<Expr> {
let mut exprs = Vec::new();
while !self.is_at_end() && !self.is_concat_terminator() {
let outer_flags = self.flags;
exprs.push(self.parse_repeat()?);
// A bare `(?flags)` sets flags for everything that follows it, so
// the remainder of this branch is parsed under the new flags and
// wrapped in a group carrying them. Without this the change would
// only reach the AST's single global flag set, and would silently
// apply to the whole pattern instead of the part after it.
if self.flags != outer_flags {
// Capture before recursing: a later `(?flags)` in the rest of
// the branch moves `self.flags` on again.
let scoped_flags = self.flags;
let rest = self.parse_concat()?;
exprs.push(Expr::Group(Box::new(Group {
expr: rest,
kind: GroupKind::Flagged(scoped_flags),
})));
break;
}
}
Ok(match exprs.len() {
0 => Expr::Empty,
1 => exprs.pop().unwrap(),
_ => Expr::Concat(exprs),
})
}
/// Returns true if the current token terminates concatenation.
fn is_concat_terminator(&self) -> bool {
matches!(
self.current.kind,
TokenKind::Pipe | TokenKind::CloseParen | TokenKind::Eof
)
}
/// Parses repetition: a*, a+, a?, a{n,m}
fn parse_repeat(&mut self) -> Result<Expr> {
let expr = self.parse_atom()?;
self.parse_quantifier(expr)
}
/// Parses a quantifier if present.
fn parse_quantifier(&mut self, expr: Expr) -> Result<Expr> {
let (min, max) = match &self.current.kind {
TokenKind::Star => {
self.advance()?;
(0, None)
}
TokenKind::Plus => {
self.advance()?;
(1, None)
}
TokenKind::Question => {
self.advance()?;
(0, Some(1))
}
TokenKind::OpenBrace => {
self.advance()?;
let (min, max) = self.parse_repetition_range()?;
self.expect(TokenKind::CloseBrace)?;
(min, max)
}
_ => return Ok(expr),
};
// Check for non-greedy modifier (? after quantifier)
let greedy = if matches!(self.current.kind, TokenKind::Question) {
self.advance()?;
false
} else {
true
};
// Check for nested quantifier (*, +, {n} after a quantifier)
// Note: This comes AFTER handling non-greedy ?, so *? is allowed
if matches!(
self.current.kind,
TokenKind::Star | TokenKind::Plus | TokenKind::Question | TokenKind::OpenBrace
) {
return Err(Error::with_span(
ErrorKind::NestedQuantifier,
self.pattern,
self.current.span,
));
}
Ok(Expr::Repeat(Box::new(Repeat::new(expr, min, max, greedy))))
}
/// Parses repetition range: {n}, {n,}, {n,m}
fn parse_repetition_range(&mut self) -> Result<(u32, Option<u32>)> {
// Parse first number (min)
let mut min = 0u32;
while let TokenKind::Digit(d) = self.current.kind {
min = min.saturating_mul(10).saturating_add(d);
self.advance()?;
}
// Check for {n}
if matches!(self.current.kind, TokenKind::CloseBrace) {
return Ok((min, Some(min)));
}
// Expect comma
if !matches!(self.current.kind, TokenKind::Comma) {
return Err(Error::with_span(
ErrorKind::InvalidRepetition,
self.pattern,
self.current.span,
));
}
self.advance()?; // consume comma
// Check for {n,}
if matches!(self.current.kind, TokenKind::CloseBrace) {
return Ok((min, None));
}
// Parse second number (max)
let mut max = 0u32;
let mut has_max = false;
while let TokenKind::Digit(d) = self.current.kind {
has_max = true;
max = max.saturating_mul(10).saturating_add(d);
self.advance()?;
}
if !has_max {
return Err(Error::with_span(
ErrorKind::InvalidRepetition,
self.pattern,
self.current.span,
));
}
if max < min {
return Err(Error::with_span(
ErrorKind::InvalidRepetition,
self.pattern,
self.current.span,
));
}
Ok((min, Some(max)))
}
}