1pub 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 return Err("Unmatched ')'".to_string());
35 }
36 Ok(())
37}
38
39fn 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#[derive(Clone, Copy)]
70enum Quant {
71 Yes,
72 Assertion,
74 Refused,
76}
77
78enum 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 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 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 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 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 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; }
200 }
201 Ok(())
202 }
203
204 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 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 fn group(&mut self) -> Res<Quant> {
244 self.i += 1; 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 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 _ => {
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 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 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 fn atom_escape(&mut self) -> Res<Quant> {
372 self.i += 1; 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 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 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 _ => {
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 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 '^' | '$' | '\\' | '.' | '*' | '+' | '?' | '(' | ')' | '[' | ']' | '{' | '}' | '|'
507 | '/' => ch(c as u32),
508 '-' if in_class || !self.unicode => ch('-' as u32),
509 '&' | '!' | '#' | '%' | ',' | ':' | ';' | '<' | '=' | '>' | '@' | '`' | '~'
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 fn class(&mut self) -> Res<()> {
522 const UNTERMINATED: &str = "Unterminated character class";
523 self.i += 1; 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 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 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
619fn property_is_known(name: &str) -> bool {
624 !name.is_empty() && regex::Regex::new(&format!("\\p{{{name}}}")).is_ok()
625}