1#![allow(clippy::result_unit_err)]
81
82use crate::{BuildError, Diagnostic, ParseTree, RawValue, Span};
83use dsl_kit_core::{NodeId, Suggester};
84use dsl_kit_macros::{DslNode as DslNodeDerive, DslSchema as DslSchemaDerive};
85use std::collections::{BTreeSet, HashMap};
86
87#[derive(Debug, Clone, DslNodeDerive, DslSchemaDerive)]
96pub enum Peg {
97 Rule {
102 id: NodeId,
104 name: String,
106 body: Box<Peg>,
108 },
109 Seq {
111 id: NodeId,
113 items: Vec<Peg>,
115 },
116 Choice {
118 id: NodeId,
120 alts: Vec<Peg>,
122 },
123 Repeat {
125 id: NodeId,
127 body: Box<Peg>,
129 min: u32,
131 max: Option<u32>,
133 },
134 RuleRef {
136 id: NodeId,
138 name: String,
140 },
141 Token {
144 id: NodeId,
146 pat: String,
149 },
150 Node {
152 id: NodeId,
154 variant: String,
156 body: Box<Peg>,
158 },
159 Field {
162 id: NodeId,
164 name: String,
166 body: Box<Peg>,
168 },
169}
170
171#[derive(Debug, Clone)]
181pub struct Grammar {
182 pub rules: Vec<Peg>,
186 pub start: String,
188}
189
190impl Grammar {
191 pub fn new(rules: Vec<Peg>, start: impl Into<String>) -> Self {
193 Self {
194 rules,
195 start: start.into(),
196 }
197 }
198
199 pub fn parse(&self, input: &str) -> Result<ParseTree, BuildError> {
208 let mut rules_by_name: HashMap<&str, &Peg> = HashMap::new();
209 for r in &self.rules {
210 if let Peg::Rule { name, .. } = r {
211 rules_by_name.insert(name.as_str(), r);
212 }
213 }
214 let start_rule = rules_by_name
215 .get(self.start.as_str())
216 .copied()
217 .ok_or_else(|| {
218 let names: Vec<&str> = rules_by_name.keys().copied().collect();
219 let base = format!("start rule `{}` is not defined in the grammar", self.start);
220 let msg = match crate::BuiltinLevenshteinSuggester
221 .enrich_unknown(self.start.as_str(), &names)
222 {
223 Some(hint) => format!("{base} ({hint})"),
224 None => base,
225 };
226 BuildError::single(Diagnostic::error(codes::UNKNOWN_RULE, msg))
227 })?;
228
229 let mut interp = Interpreter::new(input, rules_by_name);
230 interp.skip_ws();
232 interp.sink_stack.push(ActiveSink::Top(TopSink::default()));
234
235 match interp.run_peg(start_rule) {
236 Ok(()) => {}
237 Err(()) => {
238 if let Some(fatal) = interp.fatal_error.take() {
239 return Err(BuildError::single(fatal));
240 }
241 return Err(BuildError::single(interp.expected_diagnostic()));
242 }
243 }
244
245 interp.skip_ws();
247 if interp.pos != input.len() {
248 let diag = if interp.farthest_pos >= interp.pos && !interp.farthest_expected.is_empty()
251 {
252 interp.expected_diagnostic()
253 } else {
254 Diagnostic::error(
255 codes::UNEXPECTED,
256 format!("unexpected trailing input at byte {}", interp.pos),
257 )
258 .with_span(Some(Span::new(interp.pos, input.len())))
259 };
260 return Err(BuildError::single(diag));
261 }
262
263 let top = match interp.sink_stack.pop() {
264 Some(ActiveSink::Top(t)) => t,
265 _ => unreachable!("top sink must be present"),
266 };
267 top.tree.ok_or_else(|| {
268 BuildError::single(Diagnostic::error(
269 codes::NO_TOP_TREE,
270 format!(
271 "parse succeeded but produced no top-level `Node`; \
272 start rule `{}` must reach exactly one `Peg::Node`",
273 self.start
274 ),
275 ))
276 })
277 }
278}
279
280pub mod codes {
286 pub const UNEXPECTED: &str = "dsl_kit::parse::peg::unexpected";
289 pub const UNKNOWN_RULE: &str = "dsl_kit::parse::peg::unknown_rule";
293 pub const LEFT_RECURSION: &str = "dsl_kit::parse::peg::left_recursion";
298 pub const NULLABLE_REPEAT: &str = "dsl_kit::parse::peg::nullable_repeat";
303 pub const NO_TOP_TREE: &str = "dsl_kit::parse::peg::no_top_tree";
306}
307
308#[derive(Debug, Clone)]
317enum Production {
318 #[allow(dead_code)] Text(String, Span),
320 Tree(ParseTree),
321}
322
323#[derive(Debug, Default, Clone)]
324struct FieldSink {
325 productions: Vec<Production>,
326}
327
328#[derive(Debug, Default, Clone)]
329struct NodeSink {
330 fields: Vec<(String, RawValue)>,
331 children: Vec<(String, Vec<ParseTree>)>,
332}
333
334#[derive(Debug, Default, Clone)]
335struct TopSink {
336 tree: Option<ParseTree>,
337}
338
339#[derive(Debug, Clone)]
342enum ActiveSink {
343 Top(TopSink),
344 Node(NodeSink),
345 Field(FieldSink),
346}
347
348struct Interpreter<'g, 'i> {
349 input: &'i str,
350 pos: usize,
351 rules_by_name: HashMap<&'g str, &'g Peg>,
352 sink_stack: Vec<ActiveSink>,
353 farthest_pos: usize,
355 farthest_expected: BTreeSet<String>,
356 call_stack: Vec<(&'g str, usize)>,
358 fatal_error: Option<Diagnostic>,
361}
362
363impl<'g, 'i> Interpreter<'g, 'i> {
364 fn new(input: &'i str, rules_by_name: HashMap<&'g str, &'g Peg>) -> Self {
365 Self {
366 input,
367 pos: 0,
368 rules_by_name,
369 sink_stack: Vec::new(),
370 farthest_pos: 0,
371 farthest_expected: BTreeSet::new(),
372 call_stack: Vec::new(),
373 fatal_error: None,
374 }
375 }
376
377 fn top_sink_snapshot(&self) -> ActiveSink {
382 self.sink_stack
383 .last()
384 .cloned()
385 .expect("sink stack has at least the top-level entry during parse")
386 }
387
388 fn restore_top_sink(&mut self, snap: ActiveSink) {
389 let last = self
390 .sink_stack
391 .last_mut()
392 .expect("sink stack has at least the top-level entry during parse");
393 *last = snap;
394 }
395
396 fn contribute_text(&mut self, text: String, span: Span) {
397 match self.sink_stack.last_mut() {
398 Some(ActiveSink::Field(s)) => s.productions.push(Production::Text(text, span)),
399 _ => {
400 }
402 }
403 }
404
405 fn contribute_tree(&mut self, tree: ParseTree) {
406 match self.sink_stack.last_mut() {
407 Some(ActiveSink::Field(s)) => s.productions.push(Production::Tree(tree)),
408 Some(ActiveSink::Node(_)) => {
409 }
413 Some(ActiveSink::Top(t)) => {
414 t.tree = Some(tree);
417 }
418 None => unreachable!("sink stack must not be empty during parse"),
419 }
420 }
421
422 fn contribute_field(&mut self, name: &str, productions: Vec<Production>) {
423 if productions.is_empty() {
424 return;
425 }
426 let all_text = productions
427 .iter()
428 .all(|p| matches!(p, Production::Text(..)));
429 let all_tree = productions
430 .iter()
431 .all(|p| matches!(p, Production::Tree(..)));
432
433 let Some(ActiveSink::Node(node_sink)) = self.sink_stack.last_mut() else {
434 return;
436 };
437
438 if all_text {
439 let joined: String = productions
440 .iter()
441 .filter_map(|p| match p {
442 Production::Text(t, _) => Some(t.as_str()),
443 _ => None,
444 })
445 .collect();
446 node_sink
447 .fields
448 .push((name.to_string(), RawValue::Text(joined)));
449 return;
450 }
451 if all_tree {
452 let trees: Vec<ParseTree> = productions
453 .into_iter()
454 .filter_map(|p| match p {
455 Production::Tree(t) => Some(t),
456 _ => None,
457 })
458 .collect();
459 if let Some(slot) = node_sink.children.iter_mut().find(|(n, _)| n == name) {
460 slot.1.extend(trees);
461 } else {
462 node_sink.children.push((name.to_string(), trees));
463 }
464 return;
465 }
466 let trees: Vec<ParseTree> = productions
469 .into_iter()
470 .filter_map(|p| match p {
471 Production::Tree(t) => Some(t),
472 _ => None,
473 })
474 .collect();
475 if trees.is_empty() {
476 return;
477 }
478 if let Some(slot) = node_sink.children.iter_mut().find(|(n, _)| n == name) {
479 slot.1.extend(trees);
480 } else {
481 node_sink.children.push((name.to_string(), trees));
482 }
483 }
484
485 fn expected(&mut self, what: impl Into<String>) {
490 if self.pos > self.farthest_pos {
491 self.farthest_pos = self.pos;
492 self.farthest_expected.clear();
493 self.farthest_expected.insert(what.into());
494 } else if self.pos == self.farthest_pos {
495 self.farthest_expected.insert(what.into());
496 }
497 }
498
499 fn expected_diagnostic(&self) -> Diagnostic {
500 let expected: Vec<String> = self.farthest_expected.iter().cloned().collect();
501 let expected_msg = if expected.is_empty() {
502 "<unknown>".to_string()
503 } else {
504 expected
505 .iter()
506 .map(|e| format!("`{e}`"))
507 .collect::<Vec<_>>()
508 .join(" | ")
509 };
510 let end = self.input.len().min(self.farthest_pos + 1);
511 let got_msg = if self.farthest_pos >= self.input.len() {
512 "end of input".to_string()
513 } else {
514 let bytes = self.input.as_bytes();
515 let snip_end = self.input.len().min(self.farthest_pos + 8);
517 let snip =
518 std::str::from_utf8(&bytes[self.farthest_pos..snip_end]).unwrap_or("<non-utf8>");
519 format!("`{}`", snip)
520 };
521 Diagnostic::error(
522 codes::UNEXPECTED,
523 format!(
524 "expected {expected_msg} at byte {}, got {got_msg}",
525 self.farthest_pos
526 ),
527 )
528 .with_span(Some(Span::new(self.farthest_pos, end)))
529 }
530
531 fn run_peg(&mut self, peg: &'g Peg) -> Result<(), ()> {
536 match peg {
537 Peg::Rule { body, .. } => self.run_peg(body),
538 Peg::Seq { items, .. } => {
539 for item in items {
540 self.run_peg(item)?;
541 }
542 Ok(())
543 }
544 Peg::Choice { alts, .. } => self.run_choice(alts),
545 Peg::Repeat { body, min, max, .. } => self.run_repeat(body, *min, *max),
546 Peg::RuleRef { name, .. } => self.run_rule_ref(name),
547 Peg::Token { pat, .. } => self.match_token(pat),
548 Peg::Node { variant, body, .. } => self.run_node(variant, body),
549 Peg::Field { name, body, .. } => self.run_field(name, body),
550 }
551 }
552
553 fn run_choice(&mut self, alts: &'g [Peg]) -> Result<(), ()> {
554 let start_pos = self.pos;
555 let saved = self.top_sink_snapshot();
556 for alt in alts {
557 self.pos = start_pos;
558 self.restore_top_sink(saved.clone());
559 if self.fatal_error.is_some() {
560 return Err(());
561 }
562 if self.run_peg(alt).is_ok() {
563 return Ok(());
564 }
565 if self.fatal_error.is_some() {
566 return Err(());
567 }
568 }
569 self.pos = start_pos;
570 self.restore_top_sink(saved);
571 Err(())
572 }
573
574 fn run_repeat(&mut self, body: &'g Peg, min: u32, max: Option<u32>) -> Result<(), ()> {
575 let mut count: u32 = 0;
576 loop {
577 if let Some(mx) = max
578 && count >= mx
579 {
580 break;
581 }
582 let saved_pos = self.pos;
583 let saved_sink = self.top_sink_snapshot();
584 match self.run_peg(body) {
585 Ok(()) => {
586 if self.pos == saved_pos {
587 if count < min {
592 self.fatal_error = Some(
593 Diagnostic::error(
594 codes::NULLABLE_REPEAT,
595 "repeat body succeeded without consuming input".to_string(),
596 )
597 .with_span(Some(Span::new(saved_pos, saved_pos))),
598 );
599 return Err(());
600 }
601 break;
602 }
603 count += 1;
604 }
605 Err(()) => {
606 if self.fatal_error.is_some() {
607 return Err(());
608 }
609 self.pos = saved_pos;
610 self.restore_top_sink(saved_sink);
611 break;
612 }
613 }
614 }
615 if count < min { Err(()) } else { Ok(()) }
616 }
617
618 fn run_rule_ref(&mut self, name: &str) -> Result<(), ()> {
619 let Some(&rule) = self.rules_by_name.get(name) else {
620 let candidates: Vec<&str> = self.rules_by_name.keys().copied().collect();
621 let base = format!("reference to undefined rule `{name}`");
622 let msg = match crate::BuiltinLevenshteinSuggester.enrich_unknown(name, &candidates) {
623 Some(hint) => format!("{base} ({hint})"),
624 None => base,
625 };
626 self.fatal_error = Some(
627 Diagnostic::error(codes::UNKNOWN_RULE, msg)
628 .with_span(Some(Span::new(self.pos, self.pos))),
629 );
630 return Err(());
631 };
632 let rule_name: &'g str = self
634 .rules_by_name
635 .keys()
636 .copied()
637 .find(|k| *k == name)
638 .expect("just found");
639 if self
642 .call_stack
643 .iter()
644 .any(|(n, p)| *n == rule_name && *p == self.pos)
645 {
646 self.fatal_error = Some(
647 Diagnostic::error(
648 codes::LEFT_RECURSION,
649 format!(
650 "left recursion detected: rule `{name}` re-entered at byte {}",
651 self.pos
652 ),
653 )
654 .with_span(Some(Span::new(self.pos, self.pos))),
655 );
656 return Err(());
657 }
658 self.call_stack.push((rule_name, self.pos));
659 let r = self.run_peg(rule);
660 self.call_stack.pop();
661 r
662 }
663
664 fn run_node(&mut self, variant: &str, body: &'g Peg) -> Result<(), ()> {
665 let start_pos = self.pos;
666 self.sink_stack.push(ActiveSink::Node(NodeSink::default()));
667 let body_result = self.run_peg(body);
668 let node_sink = match self.sink_stack.pop() {
669 Some(ActiveSink::Node(s)) => s,
670 _ => unreachable!("balanced push/pop of NodeSink"),
671 };
672 body_result?;
673 let end_pos = self.pos;
674 let tree = ParseTree {
675 variant: variant.to_string(),
676 fields: node_sink.fields,
677 children: node_sink.children,
678 span: Some(Span::new(start_pos, end_pos)),
679 };
680 self.contribute_tree(tree);
681 Ok(())
682 }
683
684 fn run_field(&mut self, name: &str, body: &'g Peg) -> Result<(), ()> {
685 self.sink_stack
686 .push(ActiveSink::Field(FieldSink::default()));
687 let body_result = self.run_peg(body);
688 let field_sink = match self.sink_stack.pop() {
689 Some(ActiveSink::Field(s)) => s,
690 _ => unreachable!("balanced push/pop of FieldSink"),
691 };
692 body_result?;
693 self.contribute_field(name, field_sink.productions);
694 Ok(())
695 }
696
697 fn match_token(&mut self, pat: &str) -> Result<(), ()> {
702 if pat != "%ws" {
703 self.skip_ws();
704 }
705 let start = self.pos;
706 if pat == "%str" {
707 return match self.match_str() {
710 Some(decoded) => {
711 let end = self.pos;
712 self.contribute_text(decoded, Span::new(start, end));
713 Ok(())
714 }
715 None => {
716 self.expected(pat);
717 self.pos = start;
718 Err(())
719 }
720 };
721 }
722 if pat == "%str_raw" {
723 return match self.match_str() {
728 Some(_) => {
729 let end = self.pos;
730 let text = self.input[start..end].to_string();
731 self.contribute_text(text, Span::new(start, end));
732 Ok(())
733 }
734 None => {
735 self.expected(pat);
736 self.pos = start;
737 Err(())
738 }
739 };
740 }
741 let ok = if pat == "%ident" {
742 self.match_ident()
743 } else if pat == "%int" {
744 self.match_int()
745 } else if pat == "%ws" {
746 self.match_ws_required()
747 } else if let Some(word) = pat.strip_prefix("%kw:") {
748 self.match_keyword(word)
749 } else {
750 self.match_literal(pat)
751 };
752 if ok {
753 let end = self.pos;
754 let text = self.input[start..end].to_string();
755 self.contribute_text(text, Span::new(start, end));
756 Ok(())
757 } else {
758 self.expected(pat);
762 self.pos = start;
763 Err(())
764 }
765 }
766
767 fn skip_ws(&mut self) {
768 let bytes = self.input.as_bytes();
769 while let Some(&c) = bytes.get(self.pos) {
770 if matches!(c, b' ' | b'\t' | b'\n' | b'\r') {
771 self.pos += 1;
772 } else {
773 break;
774 }
775 }
776 }
777
778 fn match_ident(&mut self) -> bool {
779 let bytes = self.input.as_bytes();
780 match bytes.get(self.pos) {
781 Some(&c) if is_ident_start(c) => self.pos += 1,
782 _ => return false,
783 }
784 while let Some(&c) = bytes.get(self.pos) {
785 if is_ident_cont(c) {
786 self.pos += 1;
787 } else {
788 break;
789 }
790 }
791 true
792 }
793
794 fn match_int(&mut self) -> bool {
795 let bytes = self.input.as_bytes();
796 let mut p = self.pos;
797 if bytes.get(p) == Some(&b'-') {
798 p += 1;
799 }
800 let digit_start = p;
801 while let Some(&c) = bytes.get(p) {
802 if c.is_ascii_digit() {
803 p += 1;
804 } else {
805 break;
806 }
807 }
808 if p > digit_start {
809 self.pos = p;
810 true
811 } else {
812 false
813 }
814 }
815
816 fn match_str(&mut self) -> Option<String> {
820 let rest = &self.input[self.pos..];
821 let mut chars = rest.char_indices();
822 match chars.next() {
823 Some((_, '"')) => {}
824 _ => return None,
825 }
826 let mut out = String::new();
827 while let Some((i, c)) = chars.next() {
828 match c {
829 '"' => {
830 self.pos += i + 1;
831 return Some(out);
832 }
833 '\\' => match chars.next() {
834 Some((_, '"')) => out.push('"'),
835 Some((_, '\\')) => out.push('\\'),
836 Some((_, 'n')) => out.push('\n'),
837 Some((_, 't')) => out.push('\t'),
838 Some((_, 'r')) => out.push('\r'),
839 _ => return None,
840 },
841 other => out.push(other),
842 }
843 }
844 None
845 }
846
847 fn match_ws_required(&mut self) -> bool {
848 let start = self.pos;
849 let bytes = self.input.as_bytes();
850 while let Some(&c) = bytes.get(self.pos) {
851 if matches!(c, b' ' | b'\t' | b'\n' | b'\r') {
852 self.pos += 1;
853 } else {
854 break;
855 }
856 }
857 self.pos > start
858 }
859
860 fn match_literal(&mut self, s: &str) -> bool {
861 let bytes = self.input.as_bytes();
862 let end = self.pos + s.len();
863 if end > bytes.len() {
864 return false;
865 }
866 if &bytes[self.pos..end] != s.as_bytes() {
867 return false;
868 }
869 self.pos = end;
870 true
871 }
872
873 fn match_keyword(&mut self, word: &str) -> bool {
874 let saved = self.pos;
875 if !self.match_literal(word) {
876 return false;
877 }
878 if let Some(&next) = self.input.as_bytes().get(self.pos)
880 && is_ident_cont(next)
881 {
882 self.pos = saved;
883 return false;
884 }
885 true
886 }
887}
888
889fn is_ident_start(c: u8) -> bool {
890 c.is_ascii_alphabetic() || c == b'_'
891}
892
893fn is_ident_cont(c: u8) -> bool {
894 c.is_ascii_alphanumeric() || c == b'_'
895}
896
897use dsl_kit_core::IdGen;
903
904pub fn rule(ids: &IdGen, name: impl Into<String>, body: Peg) -> Peg {
906 Peg::Rule {
907 id: ids.node(),
908 name: name.into(),
909 body: Box::new(body),
910 }
911}
912
913pub fn seq(ids: &IdGen, items: Vec<Peg>) -> Peg {
915 Peg::Seq {
916 id: ids.node(),
917 items,
918 }
919}
920
921pub fn choice(ids: &IdGen, alts: Vec<Peg>) -> Peg {
923 Peg::Choice {
924 id: ids.node(),
925 alts,
926 }
927}
928
929pub fn repeat(ids: &IdGen, body: Peg, min: u32, max: Option<u32>) -> Peg {
931 Peg::Repeat {
932 id: ids.node(),
933 body: Box::new(body),
934 min,
935 max,
936 }
937}
938
939pub fn rule_ref(ids: &IdGen, name: impl Into<String>) -> Peg {
941 Peg::RuleRef {
942 id: ids.node(),
943 name: name.into(),
944 }
945}
946
947pub fn token(ids: &IdGen, pat: impl Into<String>) -> Peg {
949 Peg::Token {
950 id: ids.node(),
951 pat: pat.into(),
952 }
953}
954
955pub fn node(ids: &IdGen, variant: impl Into<String>, body: Peg) -> Peg {
957 Peg::Node {
958 id: ids.node(),
959 variant: variant.into(),
960 body: Box::new(body),
961 }
962}
963
964pub fn field(ids: &IdGen, name: impl Into<String>, body: Peg) -> Peg {
966 Peg::Field {
967 id: ids.node(),
968 name: name.into(),
969 body: Box::new(body),
970 }
971}
972
973#[cfg(test)]
978mod tests {
979 use super::*;
980 use dsl_kit_core::IdGen;
981 use dsl_kit_schema::DslSchema;
982
983 #[test]
986 fn peg_schema_lists_all_variants() {
987 let s = Peg::schema();
988 assert_eq!(s.name, "Peg");
989 let names: Vec<&str> = s.variants.iter().map(|v| v.name.as_str()).collect();
990 assert_eq!(
991 names,
992 vec![
993 "Rule", "Seq", "Choice", "Repeat", "RuleRef", "Token", "Node", "Field"
994 ]
995 );
996 let repeat = s.variant("Repeat").unwrap();
997 assert_eq!(repeat.children.len(), 1);
999 assert_eq!(repeat.children[0].name, "body");
1000 let field_names: Vec<&str> = repeat.fields.iter().map(|f| f.name.as_str()).collect();
1001 assert!(field_names.contains(&"min"));
1002 assert!(field_names.contains(&"max"));
1003 }
1004
1005 fn parse_one(g: &Grammar, input: &str) -> Result<ParseTree, BuildError> {
1008 g.parse(input)
1009 }
1010
1011 fn one_rule_grammar(ids: &IdGen, start: &str, body: Peg) -> Grammar {
1012 Grammar::new(vec![rule(ids, start, body)], start)
1013 }
1014
1015 #[test]
1016 fn literal_token_and_wrap_node() {
1017 let ids = IdGen::new();
1018 let g = one_rule_grammar(
1020 &ids,
1021 "start",
1022 node(&ids, "K", field(&ids, "kw", token(&ids, "let"))),
1023 );
1024 let tree = parse_one(&g, "let").unwrap();
1025 assert_eq!(tree.variant, "K");
1026 assert_eq!(tree.fields.len(), 1);
1027 assert_eq!(tree.fields[0].0, "kw");
1028 match &tree.fields[0].1 {
1029 RawValue::Text(t) => assert_eq!(t, "let"),
1030 _ => panic!("expected text"),
1031 }
1032 }
1033
1034 #[test]
1035 fn keyword_guard_blocks_prefix_match() {
1036 let ids = IdGen::new();
1037 let g = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "%kw:let")));
1040 let err = parse_one(&g, "letme").unwrap_err();
1041 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1042
1043 let g2 = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "%kw:let")));
1045 assert!(parse_one(&g2, "let ").is_ok());
1046 }
1047
1048 #[test]
1049 fn plain_literal_has_no_word_boundary_guard() {
1050 let ids = IdGen::new();
1051 let g = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "a")));
1054 let err = parse_one(&g, "ab").unwrap_err();
1055 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1057 assert!(
1058 err.diagnostics[0].message.contains("trailing"),
1059 "{}",
1060 err.diagnostics[0].message
1061 );
1062 }
1063
1064 #[test]
1065 fn ident_and_int_classes() {
1066 let ids = IdGen::new();
1067 let g = one_rule_grammar(
1068 &ids,
1069 "s",
1070 node(&ids, "Var", field(&ids, "name", token(&ids, "%ident"))),
1071 );
1072 let t = parse_one(&g, "foo_bar1").unwrap();
1073 assert_eq!(t.variant, "Var");
1074 match &t.fields[0].1 {
1075 RawValue::Text(v) => assert_eq!(v, "foo_bar1"),
1076 _ => panic!(),
1077 }
1078
1079 let g2 = one_rule_grammar(
1080 &ids,
1081 "s",
1082 node(&ids, "N", field(&ids, "v", token(&ids, "%int"))),
1083 );
1084 let t2 = parse_one(&g2, "-42").unwrap();
1085 match &t2.fields[0].1 {
1086 RawValue::Text(v) => assert_eq!(v, "-42"),
1087 _ => panic!(),
1088 }
1089 }
1090
1091 #[test]
1094 fn implicit_ws_skip_before_tokens_and_at_boundaries() {
1095 let ids = IdGen::new();
1096 let body = seq(
1098 &ids,
1099 vec![
1100 field(&ids, "a", token(&ids, "%int")),
1101 field(&ids, "b", token(&ids, "%int")),
1102 ],
1103 );
1104 let g = one_rule_grammar(&ids, "s", node(&ids, "P", body));
1105 let t = parse_one(&g, " 3 7 ").unwrap();
1106 assert_eq!(t.fields.len(), 2);
1107 assert_eq!(t.fields[0].0, "a");
1108 assert_eq!(t.fields[1].0, "b");
1109 }
1110
1111 #[test]
1114 fn choice_commits_on_first_match() {
1115 let ids = IdGen::new();
1116 let alt_a = node(&ids, "A", token(&ids, "a"));
1120 let alt_ab = node(&ids, "B", token(&ids, "ab"));
1121 let g = one_rule_grammar(&ids, "s", choice(&ids, vec![alt_a, alt_ab]));
1122 let err = parse_one(&g, "ab").unwrap_err();
1123 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1126 assert!(
1127 err.diagnostics[0].message.contains("byte 1"),
1128 "{}",
1129 err.diagnostics[0].message
1130 );
1131 }
1132
1133 #[test]
1134 fn failed_alt_restores_position() {
1135 let ids = IdGen::new();
1136 let alt_abc = node(&ids, "L", token(&ids, "abc"));
1140 let alt_a = node(&ids, "S", token(&ids, "a"));
1141 let g = one_rule_grammar(&ids, "s", choice(&ids, vec![alt_abc, alt_a]));
1142 let err = parse_one(&g, "ab").unwrap_err();
1143 assert!(
1145 err.diagnostics[0].message.contains("byte 1"),
1146 "{}",
1147 err.diagnostics[0].message
1148 );
1149 }
1150
1151 #[test]
1152 fn repeat_is_greedy_and_no_backtrack_into_completed() {
1153 let ids = IdGen::new();
1154 let g = one_rule_grammar(
1159 &ids,
1160 "s",
1161 node(
1162 &ids,
1163 "N",
1164 seq(
1165 &ids,
1166 vec![repeat(&ids, token(&ids, "a"), 0, None), token(&ids, "a")],
1167 ),
1168 ),
1169 );
1170 let err = parse_one(&g, "aaa").unwrap_err();
1171 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1172 }
1173
1174 #[test]
1175 fn repeat_min_enforced() {
1176 let ids = IdGen::new();
1177 let g = one_rule_grammar(
1178 &ids,
1179 "s",
1180 node(&ids, "N", repeat(&ids, token(&ids, "a"), 2, None)),
1181 );
1182 assert!(parse_one(&g, "a").is_err());
1184 assert!(parse_one(&g, "aa").is_ok());
1186 }
1187
1188 #[test]
1191 fn farthest_failure_carries_position_and_expected_set() {
1192 let ids = IdGen::new();
1193 let g = one_rule_grammar(
1198 &ids,
1199 "s",
1200 node(
1201 &ids,
1202 "N",
1203 seq(
1204 &ids,
1205 vec![token(&ids, "let"), token(&ids, "x"), token(&ids, "=")],
1206 ),
1207 ),
1208 );
1209 let err = parse_one(&g, "let x !").unwrap_err();
1210 let msg = &err.diagnostics[0].message;
1211 assert!(msg.contains("byte 6"), "{msg}");
1212 assert!(msg.contains("`=`"), "{msg}");
1213 }
1214
1215 #[test]
1218 fn left_recursion_is_detected_at_runtime() {
1219 let ids = IdGen::new();
1220 let r = rule(
1223 &ids,
1224 "r",
1225 seq(&ids, vec![rule_ref(&ids, "r"), token(&ids, "a")]),
1226 );
1227 let g = Grammar::new(vec![r], "r");
1228 let err = g.parse("aaa").unwrap_err();
1229 assert_eq!(err.diagnostics[0].code, codes::LEFT_RECURSION);
1230 }
1231
1232 #[test]
1233 fn unknown_rule_ref_is_diagnosed() {
1234 let ids = IdGen::new();
1235 let r = rule(&ids, "start", rule_ref(&ids, "missing"));
1236 let g = Grammar::new(vec![r], "start");
1237 let err = g.parse("").unwrap_err();
1238 assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1239 }
1240
1241 #[test]
1242 fn unknown_rule_ref_suggests_declared_rule() {
1243 let ids = IdGen::new();
1246 let start = rule(&ids, "start", rule_ref(&ids, "helo"));
1247 let target = rule(&ids, "hello", token(&ids, "hi"));
1248 let g = Grammar::new(vec![start, target], "start");
1249 let err = g.parse("hi").unwrap_err();
1250 assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1251 assert!(
1252 err.diagnostics[0].message.contains("did you mean")
1253 && err.diagnostics[0].message.contains("hello"),
1254 "expected hint, got: {}",
1255 err.diagnostics[0].message
1256 );
1257 }
1258
1259 #[test]
1260 fn unknown_start_rule_is_diagnosed() {
1261 let ids = IdGen::new();
1262 let r = rule(&ids, "other", token(&ids, "x"));
1263 let g = Grammar::new(vec![r], "start");
1264 let err = g.parse("x").unwrap_err();
1265 assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1266 }
1267
1268 #[test]
1269 fn unknown_start_rule_suggests_declared_rule() {
1270 let ids = IdGen::new();
1271 let r = rule(&ids, "start", token(&ids, "x"));
1272 let g = Grammar::new(vec![r], "strat");
1273 let err = g.parse("x").unwrap_err();
1274 assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1275 assert!(
1276 err.diagnostics[0].message.contains("did you mean")
1277 && err.diagnostics[0].message.contains("start"),
1278 "expected hint, got: {}",
1279 err.diagnostics[0].message
1280 );
1281 }
1282
1283 #[test]
1284 fn nullable_repeat_body_below_min_is_rejected() {
1285 let ids = IdGen::new();
1286 let empty_body = seq(&ids, vec![]);
1289 let g = one_rule_grammar(
1290 &ids,
1291 "s",
1292 node(&ids, "N", repeat(&ids, empty_body, 1, None)),
1293 );
1294 let err = g.parse("").unwrap_err();
1295 assert_eq!(err.diagnostics[0].code, codes::NULLABLE_REPEAT);
1296 }
1297}