1#[derive(Clone, Debug, Eq, PartialEq)]
14pub struct Rule {
15 pub name: String,
17 pub ty: RuleType,
19 pub expr: Expr,
21}
22
23#[derive(Clone, Copy, Debug, Eq, PartialEq)]
25pub enum RuleType {
26 Normal,
28 Silent,
34 Atomic,
42 CompoundAtomic,
46 NonAtomic,
49}
50
51#[derive(Clone, Debug, Eq, PartialEq)]
60pub enum Expr {
61 Str(String),
63 Insens(String),
65 Range(String, String),
67 Ident(String),
69 PeekSlice(i32, Option<i32>),
71 PosPred(Box<Expr>),
73 NegPred(Box<Expr>),
75 Seq(Box<Expr>, Box<Expr>),
77 Choice(Box<Expr>, Box<Expr>),
79 Opt(Box<Expr>),
81 Rep(Box<Expr>),
83 RepOnce(Box<Expr>),
85 RepExact(Box<Expr>, u32),
87 RepMin(Box<Expr>, u32),
89 RepMax(Box<Expr>, u32),
91 RepMinMax(Box<Expr>, u32, u32),
93 Skip(Vec<String>),
95 Push(Box<Expr>),
97 #[cfg(feature = "grammar-extras")]
99 PushLiteral(String),
100 #[cfg(feature = "grammar-extras")]
102 NodeTag(Box<Expr>, String),
103}
104
105impl Expr {
106 pub fn iter_top_down(&self) -> ExprTopDownIterator {
108 ExprTopDownIterator::new(self)
109 }
110
111 pub fn map_top_down<F>(self, mut f: F) -> Expr
113 where
114 F: FnMut(Expr) -> Expr,
115 {
116 fn map_internal<F>(expr: Expr, f: &mut F) -> Expr
117 where
118 F: FnMut(Expr) -> Expr,
119 {
120 let expr = f(expr);
121
122 match expr {
123 Expr::PosPred(expr) => {
124 let mapped = Box::new(map_internal(*expr, f));
125 Expr::PosPred(mapped)
126 }
127 Expr::NegPred(expr) => {
128 let mapped = Box::new(map_internal(*expr, f));
129 Expr::NegPred(mapped)
130 }
131 Expr::Seq(lhs, rhs) => {
132 let mapped_lhs = Box::new(map_internal(*lhs, f));
133 let mapped_rhs = Box::new(map_internal(*rhs, f));
134 Expr::Seq(mapped_lhs, mapped_rhs)
135 }
136 Expr::Choice(lhs, rhs) => {
137 let mapped_lhs = Box::new(map_internal(*lhs, f));
138 let mapped_rhs = Box::new(map_internal(*rhs, f));
139 Expr::Choice(mapped_lhs, mapped_rhs)
140 }
141 Expr::Rep(expr) => {
142 let mapped = Box::new(map_internal(*expr, f));
143 Expr::Rep(mapped)
144 }
145 Expr::RepOnce(expr) => {
146 let mapped = Box::new(map_internal(*expr, f));
147 Expr::RepOnce(mapped)
148 }
149 Expr::RepExact(expr, max) => {
150 let mapped = Box::new(map_internal(*expr, f));
151 Expr::RepExact(mapped, max)
152 }
153 Expr::RepMin(expr, num) => {
154 let mapped = Box::new(map_internal(*expr, f));
155 Expr::RepMin(mapped, num)
156 }
157 Expr::RepMax(expr, num) => {
158 let mapped = Box::new(map_internal(*expr, f));
159 Expr::RepMax(mapped, num)
160 }
161 Expr::RepMinMax(expr, min, max) => {
162 let mapped = Box::new(map_internal(*expr, f));
163 Expr::RepMinMax(mapped, min, max)
164 }
165 Expr::Opt(expr) => {
166 let mapped = Box::new(map_internal(*expr, f));
167 Expr::Opt(mapped)
168 }
169 Expr::Push(expr) => {
170 let mapped = Box::new(map_internal(*expr, f));
171 Expr::Push(mapped)
172 }
173 #[cfg(feature = "grammar-extras")]
174 Expr::NodeTag(expr, tag) => {
175 let mapped = Box::new(map_internal(*expr, f));
176 Expr::NodeTag(mapped, tag)
177 }
178 expr => expr,
179 }
180 }
181
182 map_internal(self, &mut f)
183 }
184
185 pub fn map_bottom_up<F>(self, mut f: F) -> Expr
187 where
188 F: FnMut(Expr) -> Expr,
189 {
190 fn map_internal<F>(expr: Expr, f: &mut F) -> Expr
191 where
192 F: FnMut(Expr) -> Expr,
193 {
194 let mapped = match expr {
195 Expr::PosPred(expr) => {
196 let mapped = Box::new(map_internal(*expr, f));
197 Expr::PosPred(mapped)
198 }
199 Expr::NegPred(expr) => {
200 let mapped = Box::new(map_internal(*expr, f));
201 Expr::NegPred(mapped)
202 }
203 Expr::Seq(lhs, rhs) => {
204 let mapped_lhs = Box::new(map_internal(*lhs, f));
205 let mapped_rhs = Box::new(map_internal(*rhs, f));
206 Expr::Seq(mapped_lhs, mapped_rhs)
207 }
208 Expr::Choice(lhs, rhs) => {
209 let mapped_lhs = Box::new(map_internal(*lhs, f));
210 let mapped_rhs = Box::new(map_internal(*rhs, f));
211 Expr::Choice(mapped_lhs, mapped_rhs)
212 }
213 Expr::Rep(expr) => {
214 let mapped = Box::new(map_internal(*expr, f));
215 Expr::Rep(mapped)
216 }
217 Expr::RepOnce(expr) => {
218 let mapped = Box::new(map_internal(*expr, f));
219 Expr::RepOnce(mapped)
220 }
221 Expr::RepExact(expr, num) => {
222 let mapped = Box::new(map_internal(*expr, f));
223 Expr::RepExact(mapped, num)
224 }
225 Expr::RepMin(expr, max) => {
226 let mapped = Box::new(map_internal(*expr, f));
227 Expr::RepMin(mapped, max)
228 }
229 Expr::RepMax(expr, max) => {
230 let mapped = Box::new(map_internal(*expr, f));
231 Expr::RepMax(mapped, max)
232 }
233 Expr::RepMinMax(expr, min, max) => {
234 let mapped = Box::new(map_internal(*expr, f));
235 Expr::RepMinMax(mapped, min, max)
236 }
237 Expr::Opt(expr) => {
238 let mapped = Box::new(map_internal(*expr, f));
239 Expr::Opt(mapped)
240 }
241 Expr::Push(expr) => {
242 let mapped = Box::new(map_internal(*expr, f));
243 Expr::Push(mapped)
244 }
245 #[cfg(feature = "grammar-extras")]
246 Expr::NodeTag(expr, tag) => {
247 let mapped = Box::new(map_internal(*expr, f));
248 Expr::NodeTag(mapped, tag)
249 }
250 expr => expr,
251 };
252
253 f(mapped)
254 }
255
256 map_internal(self, &mut f)
257 }
258}
259
260impl core::fmt::Display for Expr {
261 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
262 match self {
263 Expr::Str(s) => write!(f, "{:?}", s),
264 Expr::Insens(s) => write!(f, "^{:?}", s),
265 Expr::Range(start, end) => {
266 let start = start.chars().next().expect("Empty range start.");
267 let end = end.chars().next().expect("Empty range end.");
268 write!(f, "({:?}..{:?})", start, end)
269 }
270 Expr::Ident(id) => write!(f, "{}", id),
271 Expr::PeekSlice(start, end) => match end {
272 Some(end) => write!(f, "PEEK[{}..{}]", start, end),
273 None => write!(f, "PEEK[{}..]", start),
274 },
275 Expr::PosPred(expr) => write!(f, "&{}", expr.as_ref()),
276 Expr::NegPred(expr) => write!(f, "!{}", expr.as_ref()),
277 Expr::Seq(lhs, rhs) => {
278 let mut nodes = Vec::new();
279 nodes.push(lhs);
280 let mut current = rhs;
281 while let Expr::Seq(lhs, rhs) = current.as_ref() {
282 nodes.push(lhs);
283 current = rhs;
284 }
285 nodes.push(current);
286 let sequence = nodes
287 .iter()
288 .map(|node| format!("{}", node))
289 .collect::<Vec<_>>()
290 .join(" ~ ");
291 write!(f, "({})", sequence)
292 }
293 Expr::Choice(lhs, rhs) => {
294 let mut nodes = Vec::new();
295 nodes.push(lhs);
296 let mut current = rhs;
297 while let Expr::Choice(lhs, rhs) = current.as_ref() {
298 nodes.push(lhs);
299 current = rhs;
300 }
301 nodes.push(current);
302 let sequence = nodes
303 .iter()
304 .map(|node| format!("{}", node))
305 .collect::<Vec<_>>()
306 .join(" | ");
307 write!(f, "({})", sequence)
308 }
309 Expr::Opt(expr) => write!(f, "{}?", expr),
310 Expr::Rep(expr) => write!(f, "{}*", expr),
311 Expr::RepOnce(expr) => write!(f, "{}+", expr),
312 Expr::RepExact(expr, n) => write!(f, "{}{{{}}}", expr, n),
313 Expr::RepMin(expr, min) => write!(f, "{}{{{},}}", expr, min),
314 Expr::RepMax(expr, max) => write!(f, "{}{{,{}}}", expr, max),
315 Expr::RepMinMax(expr, min, max) => write!(f, "{}{{{}, {}}}", expr, min, max),
316 Expr::Skip(strings) => {
317 let strings = strings
318 .iter()
319 .map(|s| format!("{:?}", s))
320 .collect::<Vec<_>>()
321 .join(" | ");
322 write!(f, "(!({}) ~ ANY)*", strings)
323 }
324 Expr::Push(expr) => write!(f, "PUSH({})", expr),
325 #[cfg(feature = "grammar-extras")]
326 Expr::PushLiteral(s) => write!(f, "PUSH_LITERAL({:?})", s),
327 #[cfg(feature = "grammar-extras")]
328 Expr::NodeTag(expr, tag) => {
329 write!(f, "(#{} = {})", tag, expr)
330 }
331 }
332 }
333}
334
335pub struct ExprTopDownIterator {
337 current: Option<Expr>,
338 next: Option<Expr>,
339 right_branches: Vec<Expr>,
340}
341
342impl ExprTopDownIterator {
343 pub fn new(expr: &Expr) -> Self {
345 let mut iter = ExprTopDownIterator {
346 current: None,
347 next: None,
348 right_branches: vec![],
349 };
350 iter.iterate_expr(expr.clone());
351 iter
352 }
353
354 fn iterate_expr(&mut self, expr: Expr) {
355 self.current = Some(expr.clone());
356 match expr {
357 Expr::Seq(lhs, rhs) => {
358 self.right_branches.push(*rhs);
359 self.next = Some(*lhs);
360 }
361 Expr::Choice(lhs, rhs) => {
362 self.right_branches.push(*rhs);
363 self.next = Some(*lhs);
364 }
365 Expr::PosPred(expr)
366 | Expr::NegPred(expr)
367 | Expr::Rep(expr)
368 | Expr::RepOnce(expr)
369 | Expr::RepExact(expr, _)
370 | Expr::RepMin(expr, _)
371 | Expr::RepMax(expr, _)
372 | Expr::RepMinMax(expr, ..)
373 | Expr::Opt(expr)
374 | Expr::Push(expr) => {
375 self.next = Some(*expr);
376 }
377 #[cfg(feature = "grammar-extras")]
378 Expr::NodeTag(expr, _) => {
379 self.next = Some(*expr);
380 }
381 _ => {
382 self.next = None;
383 }
384 }
385 }
386}
387
388impl Iterator for ExprTopDownIterator {
389 type Item = Expr;
390
391 fn next(&mut self) -> Option<Self::Item> {
392 let result = self.current.take();
393
394 if let Some(expr) = self.next.take() {
395 self.iterate_expr(expr);
396 } else if let Some(expr) = self.right_branches.pop() {
397 self.iterate_expr(expr);
398 }
399
400 result
401 }
402}
403
404#[cfg(test)]
405mod tests {
406 use super::*;
407
408 #[test]
409 fn top_down_iterator() {
410 let expr = Expr::Choice(
411 Box::new(Expr::Str(String::from("a"))),
412 Box::new(Expr::Str(String::from("b"))),
413 );
414 let mut top_down = expr.iter_top_down();
415 assert_eq!(top_down.next(), Some(expr));
416 assert_eq!(top_down.next(), Some(Expr::Str(String::from("a"))));
417 assert_eq!(top_down.next(), Some(Expr::Str(String::from("b"))));
418 assert_eq!(top_down.next(), None);
419 }
420
421 #[test]
422 fn identity() {
423 let expr = Expr::Choice(
424 Box::new(Expr::Seq(
425 Box::new(Expr::Ident("a".to_owned())),
426 Box::new(Expr::Str("b".to_owned())),
427 )),
428 Box::new(Expr::PosPred(Box::new(Expr::NegPred(Box::new(Expr::Rep(
429 Box::new(Expr::RepOnce(Box::new(Expr::Opt(Box::new(Expr::Choice(
430 Box::new(Expr::Insens("c".to_owned())),
431 Box::new(Expr::Push(Box::new(Expr::Range(
432 "'d'".to_owned(),
433 "'e'".to_owned(),
434 )))),
435 )))))),
436 )))))),
437 );
438
439 assert_eq!(
440 expr.clone()
441 .map_bottom_up(|expr| expr)
442 .map_top_down(|expr| expr),
443 expr,
444 );
445 }
446
447 mod display {
448 use super::super::*;
449
450 #[test]
451 fn string() {
452 assert_eq!(Expr::Str("a".to_owned()).to_string(), r#""a""#);
453 }
454
455 #[test]
456 fn insens() {
457 assert_eq!(Expr::Insens("a".to_owned()).to_string(), r#"^"a""#);
458 }
459
460 #[test]
461 fn range() {
462 assert_eq!(
463 Expr::Range("a".to_owned(), "z".to_owned()).to_string(),
464 r#"('a'..'z')"#,
465 );
466 }
467
468 #[test]
469 fn ident() {
470 assert_eq!(Expr::Ident("a".to_owned()).to_string(), "a");
471 }
472
473 #[test]
474 fn peek_slice() {
475 assert_eq!(Expr::PeekSlice(0, None).to_string(), "PEEK[0..]");
476 assert_eq!(Expr::PeekSlice(0, Some(-1)).to_string(), "PEEK[0..-1]");
477 }
478
479 #[test]
480 fn pos_pred() {
481 assert_eq!(
482 Expr::PosPred(Box::new(Expr::Ident("e".to_owned()))).to_string(),
483 "&e",
484 );
485 }
486
487 #[test]
488 fn neg_pred() {
489 assert_eq!(
490 Expr::NegPred(Box::new(Expr::Ident("e".to_owned()))).to_string(),
491 "!e",
492 );
493 }
494
495 #[test]
496 fn seq() {
497 assert_eq!(
498 Expr::Seq(
499 Box::new(Expr::Ident("e1".to_owned())),
500 Box::new(Expr::Ident("e2".to_owned())),
501 )
502 .to_string(),
503 "(e1 ~ e2)",
504 );
505 assert_eq!(
506 Expr::Seq(
507 Box::new(Expr::Ident("e1".to_owned())),
508 Box::new(Expr::Seq(
509 Box::new(Expr::Ident("e2".to_owned())),
510 Box::new(Expr::Ident("e3".to_owned())),
511 )),
512 )
513 .to_string(),
514 "(e1 ~ e2 ~ e3)",
515 );
516 assert_eq!(
517 Expr::Seq(
518 Box::new(Expr::Ident("e1".to_owned())),
519 Box::new(Expr::Seq(
520 Box::new(Expr::Ident("e2".to_owned())),
521 Box::new(Expr::Seq(
522 Box::new(Expr::Ident("e3".to_owned())),
523 Box::new(Expr::Ident("e4".to_owned())),
524 )),
525 )),
526 )
527 .to_string(),
528 "(e1 ~ e2 ~ e3 ~ e4)",
529 );
530 assert_eq!(
531 Expr::Seq(
532 Box::new(Expr::Ident("e1".to_owned())),
533 Box::new(Expr::Choice(
534 Box::new(Expr::Ident("e2".to_owned())),
535 Box::new(Expr::Seq(
536 Box::new(Expr::Ident("e3".to_owned())),
537 Box::new(Expr::Ident("e4".to_owned())),
538 )),
539 )),
540 )
541 .to_string(),
542 "(e1 ~ (e2 | (e3 ~ e4)))",
543 );
544 assert_eq!(
545 Expr::Seq(
546 Box::new(Expr::Ident("e1".to_owned())),
547 Box::new(Expr::Seq(
548 Box::new(Expr::Ident("e2".to_owned())),
549 Box::new(Expr::Choice(
550 Box::new(Expr::Ident("e3".to_owned())),
551 Box::new(Expr::Ident("e4".to_owned())),
552 )),
553 )),
554 )
555 .to_string(),
556 "(e1 ~ e2 ~ (e3 | e4))",
557 );
558 }
559
560 #[test]
561 fn choice() {
562 assert_eq!(
563 Expr::Choice(
564 Box::new(Expr::Ident("e1".to_owned())),
565 Box::new(Expr::Ident("e2".to_owned())),
566 )
567 .to_string(),
568 "(e1 | e2)",
569 );
570 assert_eq!(
571 Expr::Choice(
572 Box::new(Expr::Ident("e1".to_owned())),
573 Box::new(Expr::Choice(
574 Box::new(Expr::Ident("e2".to_owned())),
575 Box::new(Expr::Ident("e3".to_owned())),
576 )),
577 )
578 .to_string(),
579 "(e1 | e2 | e3)",
580 );
581 assert_eq!(
582 Expr::Choice(
583 Box::new(Expr::Ident("e1".to_owned())),
584 Box::new(Expr::Choice(
585 Box::new(Expr::Ident("e2".to_owned())),
586 Box::new(Expr::Choice(
587 Box::new(Expr::Ident("e3".to_owned())),
588 Box::new(Expr::Ident("e4".to_owned())),
589 )),
590 )),
591 )
592 .to_string(),
593 "(e1 | e2 | e3 | e4)",
594 );
595 assert_eq!(
596 Expr::Choice(
597 Box::new(Expr::Ident("e1".to_owned())),
598 Box::new(Expr::Seq(
599 Box::new(Expr::Ident("e2".to_owned())),
600 Box::new(Expr::Choice(
601 Box::new(Expr::Ident("e3".to_owned())),
602 Box::new(Expr::Ident("e4".to_owned())),
603 )),
604 )),
605 )
606 .to_string(),
607 "(e1 | (e2 ~ (e3 | e4)))",
608 );
609 }
610
611 #[test]
612 fn opt() {
613 assert_eq!(
614 Expr::Opt(Box::new(Expr::Ident("e".to_owned()))).to_string(),
615 "e?",
616 );
617 }
618
619 #[test]
620 fn rep() {
621 assert_eq!(
622 Expr::Rep(Box::new(Expr::Ident("e".to_owned()))).to_string(),
623 "e*",
624 );
625 }
626
627 #[test]
628 fn rep_once() {
629 assert_eq!(
630 Expr::RepOnce(Box::new(Expr::Ident("e".to_owned()))).to_string(),
631 "e+",
632 );
633 }
634
635 #[test]
636 fn rep_exact() {
637 assert_eq!(
638 Expr::RepExact(Box::new(Expr::Ident("e".to_owned())), 1).to_string(),
639 "e{1}",
640 );
641 }
642
643 #[test]
644 fn rep_min() {
645 assert_eq!(
646 Expr::RepMin(Box::new(Expr::Ident("e".to_owned())), 1).to_string(),
647 "e{1,}",
648 );
649 }
650
651 #[test]
652 fn rep_max() {
653 assert_eq!(
654 Expr::RepMax(Box::new(Expr::Ident("e".to_owned())), 1).to_string(),
655 "e{,1}",
656 );
657 }
658
659 #[test]
660 fn rep_min_max() {
661 assert_eq!(
662 Expr::RepMinMax(Box::new(Expr::Ident("e".to_owned())), 1, 2).to_string(),
663 "e{1, 2}",
664 );
665 }
666
667 #[test]
668 fn skip() {
669 assert_eq!(
670 Expr::Skip(
671 ["a", "bc"]
672 .into_iter()
673 .map(|s| s.to_owned())
674 .collect::<Vec<_>>(),
675 )
676 .to_string(),
677 r#"(!("a" | "bc") ~ ANY)*"#,
678 );
679 }
680
681 #[test]
682 fn push() {
683 assert_eq!(
684 Expr::Push(Box::new(Expr::Ident("e".to_owned()))).to_string(),
685 "PUSH(e)",
686 );
687 }
688
689 #[test]
690 #[cfg(feature = "grammar-extras")]
691 fn push_literal() {
692 assert_eq!(
693 Expr::PushLiteral("one \" ' two".to_string()).to_string(),
694 r#"PUSH_LITERAL("one \" ' two")"#
695 )
696 }
697
698 #[test]
699 #[cfg(feature = "grammar-extras")]
700 fn node_tag() {
701 assert_eq!(
702 Expr::NodeTag(Box::new(Expr::Ident("expr".to_owned())), "label".to_owned())
703 .to_string(),
704 "(#label = expr)",
705 );
706 }
707 }
708}