1#![allow(clippy::result_unit_err)]
74
75use crate::{BuildError, Diagnostic, ParseTree, RawValue, Span};
76use dsl_kit_core::{NodeId, Suggester};
77use dsl_kit_macros::{DslNode as DslNodeDerive, DslSchema as DslSchemaDerive};
78use std::collections::{BTreeSet, HashMap};
79
80#[derive(Debug, Clone, DslNodeDerive, DslSchemaDerive)]
89pub enum Peg {
90 Rule {
95 id: NodeId,
97 name: String,
99 body: Box<Peg>,
101 },
102 Seq {
104 id: NodeId,
106 items: Vec<Peg>,
108 },
109 Choice {
111 id: NodeId,
113 alts: Vec<Peg>,
115 },
116 Repeat {
118 id: NodeId,
120 body: Box<Peg>,
122 min: u32,
124 max: Option<u32>,
126 },
127 RuleRef {
129 id: NodeId,
131 name: String,
133 },
134 Token {
137 id: NodeId,
139 pat: String,
142 },
143 Node {
145 id: NodeId,
147 variant: String,
149 body: Box<Peg>,
151 },
152 Field {
155 id: NodeId,
157 name: String,
159 body: Box<Peg>,
161 },
162}
163
164#[derive(Debug, Clone)]
174pub struct Grammar {
175 pub rules: Vec<Peg>,
179 pub start: String,
181}
182
183impl Grammar {
184 pub fn new(rules: Vec<Peg>, start: impl Into<String>) -> Self {
186 Self {
187 rules,
188 start: start.into(),
189 }
190 }
191
192 pub fn parse(&self, input: &str) -> Result<ParseTree, BuildError> {
201 let mut rules_by_name: HashMap<&str, &Peg> = HashMap::new();
202 for r in &self.rules {
203 if let Peg::Rule { name, .. } = r {
204 rules_by_name.insert(name.as_str(), r);
205 }
206 }
207 let start_rule = rules_by_name
208 .get(self.start.as_str())
209 .copied()
210 .ok_or_else(|| {
211 let names: Vec<&str> = rules_by_name.keys().copied().collect();
212 let base = format!("start rule `{}` is not defined in the grammar", self.start);
213 let msg = match crate::BuiltinLevenshteinSuggester
214 .enrich_unknown(self.start.as_str(), &names)
215 {
216 Some(hint) => format!("{base} ({hint})"),
217 None => base,
218 };
219 BuildError::single(Diagnostic::error(codes::UNKNOWN_RULE, msg))
220 })?;
221
222 let mut interp = Interpreter::new(input, rules_by_name);
223 interp.skip_ws();
225 interp.sink_stack.push(ActiveSink::Top(TopSink::default()));
227
228 match interp.run_peg(start_rule) {
229 Ok(()) => {}
230 Err(()) => {
231 if let Some(fatal) = interp.fatal_error.take() {
232 return Err(BuildError::single(fatal));
233 }
234 return Err(BuildError::single(interp.expected_diagnostic()));
235 }
236 }
237
238 interp.skip_ws();
240 if interp.pos != input.len() {
241 let diag = if interp.farthest_pos >= interp.pos && !interp.farthest_expected.is_empty()
244 {
245 interp.expected_diagnostic()
246 } else {
247 Diagnostic::error(
248 codes::UNEXPECTED,
249 format!("unexpected trailing input at byte {}", interp.pos),
250 )
251 .with_span(Some(Span::new(interp.pos, input.len())))
252 };
253 return Err(BuildError::single(diag));
254 }
255
256 let top = match interp.sink_stack.pop() {
257 Some(ActiveSink::Top(t)) => t,
258 _ => unreachable!("top sink must be present"),
259 };
260 top.tree.ok_or_else(|| {
261 BuildError::single(Diagnostic::error(
262 codes::NO_TOP_TREE,
263 format!(
264 "parse succeeded but produced no top-level `Node`; \
265 start rule `{}` must reach exactly one `Peg::Node`",
266 self.start
267 ),
268 ))
269 })
270 }
271}
272
273pub mod codes {
279 pub const UNEXPECTED: &str = "dsl_kit::parse::peg::unexpected";
282 pub const UNKNOWN_RULE: &str = "dsl_kit::parse::peg::unknown_rule";
286 pub const LEFT_RECURSION: &str = "dsl_kit::parse::peg::left_recursion";
291 pub const NULLABLE_REPEAT: &str = "dsl_kit::parse::peg::nullable_repeat";
296 pub const NO_TOP_TREE: &str = "dsl_kit::parse::peg::no_top_tree";
299}
300
301#[derive(Debug, Clone)]
310enum Production {
311 #[allow(dead_code)] Text(String, Span),
313 Tree(ParseTree),
314}
315
316#[derive(Debug, Default, Clone)]
317struct FieldSink {
318 productions: Vec<Production>,
319}
320
321#[derive(Debug, Default, Clone)]
322struct NodeSink {
323 fields: Vec<(String, RawValue)>,
324 children: Vec<(String, Vec<ParseTree>)>,
325}
326
327#[derive(Debug, Default, Clone)]
328struct TopSink {
329 tree: Option<ParseTree>,
330}
331
332#[derive(Debug, Clone)]
335enum ActiveSink {
336 Top(TopSink),
337 Node(NodeSink),
338 Field(FieldSink),
339}
340
341struct Interpreter<'g, 'i> {
342 input: &'i str,
343 pos: usize,
344 rules_by_name: HashMap<&'g str, &'g Peg>,
345 sink_stack: Vec<ActiveSink>,
346 farthest_pos: usize,
348 farthest_expected: BTreeSet<String>,
349 call_stack: Vec<(&'g str, usize)>,
351 fatal_error: Option<Diagnostic>,
354}
355
356impl<'g, 'i> Interpreter<'g, 'i> {
357 fn new(input: &'i str, rules_by_name: HashMap<&'g str, &'g Peg>) -> Self {
358 Self {
359 input,
360 pos: 0,
361 rules_by_name,
362 sink_stack: Vec::new(),
363 farthest_pos: 0,
364 farthest_expected: BTreeSet::new(),
365 call_stack: Vec::new(),
366 fatal_error: None,
367 }
368 }
369
370 fn top_sink_snapshot(&self) -> ActiveSink {
375 self.sink_stack
376 .last()
377 .cloned()
378 .expect("sink stack has at least the top-level entry during parse")
379 }
380
381 fn restore_top_sink(&mut self, snap: ActiveSink) {
382 let last = self
383 .sink_stack
384 .last_mut()
385 .expect("sink stack has at least the top-level entry during parse");
386 *last = snap;
387 }
388
389 fn contribute_text(&mut self, text: String, span: Span) {
390 match self.sink_stack.last_mut() {
391 Some(ActiveSink::Field(s)) => s.productions.push(Production::Text(text, span)),
392 _ => {
393 }
395 }
396 }
397
398 fn contribute_tree(&mut self, tree: ParseTree) {
399 match self.sink_stack.last_mut() {
400 Some(ActiveSink::Field(s)) => s.productions.push(Production::Tree(tree)),
401 Some(ActiveSink::Node(_)) => {
402 }
406 Some(ActiveSink::Top(t)) => {
407 t.tree = Some(tree);
410 }
411 None => unreachable!("sink stack must not be empty during parse"),
412 }
413 }
414
415 fn contribute_field(&mut self, name: &str, productions: Vec<Production>) {
416 if productions.is_empty() {
417 return;
418 }
419 let all_text = productions
420 .iter()
421 .all(|p| matches!(p, Production::Text(..)));
422 let all_tree = productions
423 .iter()
424 .all(|p| matches!(p, Production::Tree(..)));
425
426 let Some(ActiveSink::Node(node_sink)) = self.sink_stack.last_mut() else {
427 return;
429 };
430
431 if all_text {
432 let joined: String = productions
433 .iter()
434 .filter_map(|p| match p {
435 Production::Text(t, _) => Some(t.as_str()),
436 _ => None,
437 })
438 .collect();
439 node_sink
440 .fields
441 .push((name.to_string(), RawValue::Text(joined)));
442 return;
443 }
444 if all_tree {
445 let trees: Vec<ParseTree> = productions
446 .into_iter()
447 .filter_map(|p| match p {
448 Production::Tree(t) => Some(t),
449 _ => None,
450 })
451 .collect();
452 if let Some(slot) = node_sink.children.iter_mut().find(|(n, _)| n == name) {
453 slot.1.extend(trees);
454 } else {
455 node_sink.children.push((name.to_string(), trees));
456 }
457 return;
458 }
459 let trees: Vec<ParseTree> = productions
462 .into_iter()
463 .filter_map(|p| match p {
464 Production::Tree(t) => Some(t),
465 _ => None,
466 })
467 .collect();
468 if trees.is_empty() {
469 return;
470 }
471 if let Some(slot) = node_sink.children.iter_mut().find(|(n, _)| n == name) {
472 slot.1.extend(trees);
473 } else {
474 node_sink.children.push((name.to_string(), trees));
475 }
476 }
477
478 fn expected(&mut self, what: impl Into<String>) {
483 if self.pos > self.farthest_pos {
484 self.farthest_pos = self.pos;
485 self.farthest_expected.clear();
486 self.farthest_expected.insert(what.into());
487 } else if self.pos == self.farthest_pos {
488 self.farthest_expected.insert(what.into());
489 }
490 }
491
492 fn expected_diagnostic(&self) -> Diagnostic {
493 let expected: Vec<String> = self.farthest_expected.iter().cloned().collect();
494 let expected_msg = if expected.is_empty() {
495 "<unknown>".to_string()
496 } else {
497 expected
498 .iter()
499 .map(|e| format!("`{e}`"))
500 .collect::<Vec<_>>()
501 .join(" | ")
502 };
503 let end = self.input.len().min(self.farthest_pos + 1);
504 let got_msg = if self.farthest_pos >= self.input.len() {
505 "end of input".to_string()
506 } else {
507 let bytes = self.input.as_bytes();
508 let snip_end = self.input.len().min(self.farthest_pos + 8);
510 let snip =
511 std::str::from_utf8(&bytes[self.farthest_pos..snip_end]).unwrap_or("<non-utf8>");
512 format!("`{}`", snip)
513 };
514 Diagnostic::error(
515 codes::UNEXPECTED,
516 format!(
517 "expected {expected_msg} at byte {}, got {got_msg}",
518 self.farthest_pos
519 ),
520 )
521 .with_span(Some(Span::new(self.farthest_pos, end)))
522 }
523
524 fn run_peg(&mut self, peg: &'g Peg) -> Result<(), ()> {
529 match peg {
530 Peg::Rule { body, .. } => self.run_peg(body),
531 Peg::Seq { items, .. } => {
532 for item in items {
533 self.run_peg(item)?;
534 }
535 Ok(())
536 }
537 Peg::Choice { alts, .. } => self.run_choice(alts),
538 Peg::Repeat { body, min, max, .. } => self.run_repeat(body, *min, *max),
539 Peg::RuleRef { name, .. } => self.run_rule_ref(name),
540 Peg::Token { pat, .. } => self.match_token(pat),
541 Peg::Node { variant, body, .. } => self.run_node(variant, body),
542 Peg::Field { name, body, .. } => self.run_field(name, body),
543 }
544 }
545
546 fn run_choice(&mut self, alts: &'g [Peg]) -> Result<(), ()> {
547 let start_pos = self.pos;
548 let saved = self.top_sink_snapshot();
549 for alt in alts {
550 self.pos = start_pos;
551 self.restore_top_sink(saved.clone());
552 if self.fatal_error.is_some() {
553 return Err(());
554 }
555 if self.run_peg(alt).is_ok() {
556 return Ok(());
557 }
558 if self.fatal_error.is_some() {
559 return Err(());
560 }
561 }
562 self.pos = start_pos;
563 self.restore_top_sink(saved);
564 Err(())
565 }
566
567 fn run_repeat(&mut self, body: &'g Peg, min: u32, max: Option<u32>) -> Result<(), ()> {
568 let mut count: u32 = 0;
569 loop {
570 if let Some(mx) = max
571 && count >= mx
572 {
573 break;
574 }
575 let saved_pos = self.pos;
576 let saved_sink = self.top_sink_snapshot();
577 match self.run_peg(body) {
578 Ok(()) => {
579 if self.pos == saved_pos {
580 if count < min {
585 self.fatal_error = Some(
586 Diagnostic::error(
587 codes::NULLABLE_REPEAT,
588 "repeat body succeeded without consuming input".to_string(),
589 )
590 .with_span(Some(Span::new(saved_pos, saved_pos))),
591 );
592 return Err(());
593 }
594 break;
595 }
596 count += 1;
597 }
598 Err(()) => {
599 if self.fatal_error.is_some() {
600 return Err(());
601 }
602 self.pos = saved_pos;
603 self.restore_top_sink(saved_sink);
604 break;
605 }
606 }
607 }
608 if count < min { Err(()) } else { Ok(()) }
609 }
610
611 fn run_rule_ref(&mut self, name: &str) -> Result<(), ()> {
612 let Some(&rule) = self.rules_by_name.get(name) else {
613 let candidates: Vec<&str> = self.rules_by_name.keys().copied().collect();
614 let base = format!("reference to undefined rule `{name}`");
615 let msg = match crate::BuiltinLevenshteinSuggester.enrich_unknown(name, &candidates) {
616 Some(hint) => format!("{base} ({hint})"),
617 None => base,
618 };
619 self.fatal_error = Some(
620 Diagnostic::error(codes::UNKNOWN_RULE, msg)
621 .with_span(Some(Span::new(self.pos, self.pos))),
622 );
623 return Err(());
624 };
625 let rule_name: &'g str = self
627 .rules_by_name
628 .keys()
629 .copied()
630 .find(|k| *k == name)
631 .expect("just found");
632 if self
635 .call_stack
636 .iter()
637 .any(|(n, p)| *n == rule_name && *p == self.pos)
638 {
639 self.fatal_error = Some(
640 Diagnostic::error(
641 codes::LEFT_RECURSION,
642 format!(
643 "left recursion detected: rule `{name}` re-entered at byte {}",
644 self.pos
645 ),
646 )
647 .with_span(Some(Span::new(self.pos, self.pos))),
648 );
649 return Err(());
650 }
651 self.call_stack.push((rule_name, self.pos));
652 let r = self.run_peg(rule);
653 self.call_stack.pop();
654 r
655 }
656
657 fn run_node(&mut self, variant: &str, body: &'g Peg) -> Result<(), ()> {
658 let start_pos = self.pos;
659 self.sink_stack.push(ActiveSink::Node(NodeSink::default()));
660 let body_result = self.run_peg(body);
661 let node_sink = match self.sink_stack.pop() {
662 Some(ActiveSink::Node(s)) => s,
663 _ => unreachable!("balanced push/pop of NodeSink"),
664 };
665 body_result?;
666 let end_pos = self.pos;
667 let tree = ParseTree {
668 variant: variant.to_string(),
669 fields: node_sink.fields,
670 children: node_sink.children,
671 span: Some(Span::new(start_pos, end_pos)),
672 };
673 self.contribute_tree(tree);
674 Ok(())
675 }
676
677 fn run_field(&mut self, name: &str, body: &'g Peg) -> Result<(), ()> {
678 self.sink_stack
679 .push(ActiveSink::Field(FieldSink::default()));
680 let body_result = self.run_peg(body);
681 let field_sink = match self.sink_stack.pop() {
682 Some(ActiveSink::Field(s)) => s,
683 _ => unreachable!("balanced push/pop of FieldSink"),
684 };
685 body_result?;
686 self.contribute_field(name, field_sink.productions);
687 Ok(())
688 }
689
690 fn match_token(&mut self, pat: &str) -> Result<(), ()> {
695 if pat != "%ws" {
696 self.skip_ws();
697 }
698 let start = self.pos;
699 if pat == "%str" {
700 return match self.match_str() {
703 Some(decoded) => {
704 let end = self.pos;
705 self.contribute_text(decoded, Span::new(start, end));
706 Ok(())
707 }
708 None => {
709 self.expected(pat);
710 self.pos = start;
711 Err(())
712 }
713 };
714 }
715 let ok = if pat == "%ident" {
716 self.match_ident()
717 } else if pat == "%int" {
718 self.match_int()
719 } else if pat == "%ws" {
720 self.match_ws_required()
721 } else if let Some(word) = pat.strip_prefix("%kw:") {
722 self.match_keyword(word)
723 } else {
724 self.match_literal(pat)
725 };
726 if ok {
727 let end = self.pos;
728 let text = self.input[start..end].to_string();
729 self.contribute_text(text, Span::new(start, end));
730 Ok(())
731 } else {
732 self.expected(pat);
736 self.pos = start;
737 Err(())
738 }
739 }
740
741 fn skip_ws(&mut self) {
742 let bytes = self.input.as_bytes();
743 while let Some(&c) = bytes.get(self.pos) {
744 if matches!(c, b' ' | b'\t' | b'\n' | b'\r') {
745 self.pos += 1;
746 } else {
747 break;
748 }
749 }
750 }
751
752 fn match_ident(&mut self) -> bool {
753 let bytes = self.input.as_bytes();
754 match bytes.get(self.pos) {
755 Some(&c) if is_ident_start(c) => self.pos += 1,
756 _ => return false,
757 }
758 while let Some(&c) = bytes.get(self.pos) {
759 if is_ident_cont(c) {
760 self.pos += 1;
761 } else {
762 break;
763 }
764 }
765 true
766 }
767
768 fn match_int(&mut self) -> bool {
769 let bytes = self.input.as_bytes();
770 let mut p = self.pos;
771 if bytes.get(p) == Some(&b'-') {
772 p += 1;
773 }
774 let digit_start = p;
775 while let Some(&c) = bytes.get(p) {
776 if c.is_ascii_digit() {
777 p += 1;
778 } else {
779 break;
780 }
781 }
782 if p > digit_start {
783 self.pos = p;
784 true
785 } else {
786 false
787 }
788 }
789
790 fn match_str(&mut self) -> Option<String> {
794 let rest = &self.input[self.pos..];
795 let mut chars = rest.char_indices();
796 match chars.next() {
797 Some((_, '"')) => {}
798 _ => return None,
799 }
800 let mut out = String::new();
801 while let Some((i, c)) = chars.next() {
802 match c {
803 '"' => {
804 self.pos += i + 1;
805 return Some(out);
806 }
807 '\\' => match chars.next() {
808 Some((_, '"')) => out.push('"'),
809 Some((_, '\\')) => out.push('\\'),
810 Some((_, 'n')) => out.push('\n'),
811 Some((_, 't')) => out.push('\t'),
812 Some((_, 'r')) => out.push('\r'),
813 _ => return None,
814 },
815 other => out.push(other),
816 }
817 }
818 None
819 }
820
821 fn match_ws_required(&mut self) -> bool {
822 let start = self.pos;
823 let bytes = self.input.as_bytes();
824 while let Some(&c) = bytes.get(self.pos) {
825 if matches!(c, b' ' | b'\t' | b'\n' | b'\r') {
826 self.pos += 1;
827 } else {
828 break;
829 }
830 }
831 self.pos > start
832 }
833
834 fn match_literal(&mut self, s: &str) -> bool {
835 let bytes = self.input.as_bytes();
836 let end = self.pos + s.len();
837 if end > bytes.len() {
838 return false;
839 }
840 if &bytes[self.pos..end] != s.as_bytes() {
841 return false;
842 }
843 self.pos = end;
844 true
845 }
846
847 fn match_keyword(&mut self, word: &str) -> bool {
848 let saved = self.pos;
849 if !self.match_literal(word) {
850 return false;
851 }
852 if let Some(&next) = self.input.as_bytes().get(self.pos)
854 && is_ident_cont(next)
855 {
856 self.pos = saved;
857 return false;
858 }
859 true
860 }
861}
862
863fn is_ident_start(c: u8) -> bool {
864 c.is_ascii_alphabetic() || c == b'_'
865}
866
867fn is_ident_cont(c: u8) -> bool {
868 c.is_ascii_alphanumeric() || c == b'_'
869}
870
871use dsl_kit_core::IdGen;
877
878pub fn rule(ids: &IdGen, name: impl Into<String>, body: Peg) -> Peg {
880 Peg::Rule {
881 id: ids.node(),
882 name: name.into(),
883 body: Box::new(body),
884 }
885}
886
887pub fn seq(ids: &IdGen, items: Vec<Peg>) -> Peg {
889 Peg::Seq {
890 id: ids.node(),
891 items,
892 }
893}
894
895pub fn choice(ids: &IdGen, alts: Vec<Peg>) -> Peg {
897 Peg::Choice {
898 id: ids.node(),
899 alts,
900 }
901}
902
903pub fn repeat(ids: &IdGen, body: Peg, min: u32, max: Option<u32>) -> Peg {
905 Peg::Repeat {
906 id: ids.node(),
907 body: Box::new(body),
908 min,
909 max,
910 }
911}
912
913pub fn rule_ref(ids: &IdGen, name: impl Into<String>) -> Peg {
915 Peg::RuleRef {
916 id: ids.node(),
917 name: name.into(),
918 }
919}
920
921pub fn token(ids: &IdGen, pat: impl Into<String>) -> Peg {
923 Peg::Token {
924 id: ids.node(),
925 pat: pat.into(),
926 }
927}
928
929pub fn node(ids: &IdGen, variant: impl Into<String>, body: Peg) -> Peg {
931 Peg::Node {
932 id: ids.node(),
933 variant: variant.into(),
934 body: Box::new(body),
935 }
936}
937
938pub fn field(ids: &IdGen, name: impl Into<String>, body: Peg) -> Peg {
940 Peg::Field {
941 id: ids.node(),
942 name: name.into(),
943 body: Box::new(body),
944 }
945}
946
947#[cfg(test)]
952mod tests {
953 use super::*;
954 use dsl_kit_core::IdGen;
955 use dsl_kit_schema::DslSchema;
956
957 #[test]
960 fn peg_schema_lists_all_variants() {
961 let s = Peg::schema();
962 assert_eq!(s.name, "Peg");
963 let names: Vec<&str> = s.variants.iter().map(|v| v.name.as_str()).collect();
964 assert_eq!(
965 names,
966 vec![
967 "Rule", "Seq", "Choice", "Repeat", "RuleRef", "Token", "Node", "Field"
968 ]
969 );
970 let repeat = s.variant("Repeat").unwrap();
971 assert_eq!(repeat.children.len(), 1);
973 assert_eq!(repeat.children[0].name, "body");
974 let field_names: Vec<&str> = repeat.fields.iter().map(|f| f.name.as_str()).collect();
975 assert!(field_names.contains(&"min"));
976 assert!(field_names.contains(&"max"));
977 }
978
979 fn parse_one(g: &Grammar, input: &str) -> Result<ParseTree, BuildError> {
982 g.parse(input)
983 }
984
985 fn one_rule_grammar(ids: &IdGen, start: &str, body: Peg) -> Grammar {
986 Grammar::new(vec![rule(ids, start, body)], start)
987 }
988
989 #[test]
990 fn literal_token_and_wrap_node() {
991 let ids = IdGen::new();
992 let g = one_rule_grammar(
994 &ids,
995 "start",
996 node(&ids, "K", field(&ids, "kw", token(&ids, "let"))),
997 );
998 let tree = parse_one(&g, "let").unwrap();
999 assert_eq!(tree.variant, "K");
1000 assert_eq!(tree.fields.len(), 1);
1001 assert_eq!(tree.fields[0].0, "kw");
1002 match &tree.fields[0].1 {
1003 RawValue::Text(t) => assert_eq!(t, "let"),
1004 _ => panic!("expected text"),
1005 }
1006 }
1007
1008 #[test]
1009 fn keyword_guard_blocks_prefix_match() {
1010 let ids = IdGen::new();
1011 let g = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "%kw:let")));
1014 let err = parse_one(&g, "letme").unwrap_err();
1015 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1016
1017 let g2 = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "%kw:let")));
1019 assert!(parse_one(&g2, "let ").is_ok());
1020 }
1021
1022 #[test]
1023 fn plain_literal_has_no_word_boundary_guard() {
1024 let ids = IdGen::new();
1025 let g = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "a")));
1028 let err = parse_one(&g, "ab").unwrap_err();
1029 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1031 assert!(
1032 err.diagnostics[0].message.contains("trailing"),
1033 "{}",
1034 err.diagnostics[0].message
1035 );
1036 }
1037
1038 #[test]
1039 fn ident_and_int_classes() {
1040 let ids = IdGen::new();
1041 let g = one_rule_grammar(
1042 &ids,
1043 "s",
1044 node(&ids, "Var", field(&ids, "name", token(&ids, "%ident"))),
1045 );
1046 let t = parse_one(&g, "foo_bar1").unwrap();
1047 assert_eq!(t.variant, "Var");
1048 match &t.fields[0].1 {
1049 RawValue::Text(v) => assert_eq!(v, "foo_bar1"),
1050 _ => panic!(),
1051 }
1052
1053 let g2 = one_rule_grammar(
1054 &ids,
1055 "s",
1056 node(&ids, "N", field(&ids, "v", token(&ids, "%int"))),
1057 );
1058 let t2 = parse_one(&g2, "-42").unwrap();
1059 match &t2.fields[0].1 {
1060 RawValue::Text(v) => assert_eq!(v, "-42"),
1061 _ => panic!(),
1062 }
1063 }
1064
1065 #[test]
1068 fn implicit_ws_skip_before_tokens_and_at_boundaries() {
1069 let ids = IdGen::new();
1070 let body = seq(
1072 &ids,
1073 vec![
1074 field(&ids, "a", token(&ids, "%int")),
1075 field(&ids, "b", token(&ids, "%int")),
1076 ],
1077 );
1078 let g = one_rule_grammar(&ids, "s", node(&ids, "P", body));
1079 let t = parse_one(&g, " 3 7 ").unwrap();
1080 assert_eq!(t.fields.len(), 2);
1081 assert_eq!(t.fields[0].0, "a");
1082 assert_eq!(t.fields[1].0, "b");
1083 }
1084
1085 #[test]
1088 fn choice_commits_on_first_match() {
1089 let ids = IdGen::new();
1090 let alt_a = node(&ids, "A", token(&ids, "a"));
1094 let alt_ab = node(&ids, "B", token(&ids, "ab"));
1095 let g = one_rule_grammar(&ids, "s", choice(&ids, vec![alt_a, alt_ab]));
1096 let err = parse_one(&g, "ab").unwrap_err();
1097 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1100 assert!(
1101 err.diagnostics[0].message.contains("byte 1"),
1102 "{}",
1103 err.diagnostics[0].message
1104 );
1105 }
1106
1107 #[test]
1108 fn failed_alt_restores_position() {
1109 let ids = IdGen::new();
1110 let alt_abc = node(&ids, "L", token(&ids, "abc"));
1114 let alt_a = node(&ids, "S", token(&ids, "a"));
1115 let g = one_rule_grammar(&ids, "s", choice(&ids, vec![alt_abc, alt_a]));
1116 let err = parse_one(&g, "ab").unwrap_err();
1117 assert!(
1119 err.diagnostics[0].message.contains("byte 1"),
1120 "{}",
1121 err.diagnostics[0].message
1122 );
1123 }
1124
1125 #[test]
1126 fn repeat_is_greedy_and_no_backtrack_into_completed() {
1127 let ids = IdGen::new();
1128 let g = one_rule_grammar(
1133 &ids,
1134 "s",
1135 node(
1136 &ids,
1137 "N",
1138 seq(
1139 &ids,
1140 vec![repeat(&ids, token(&ids, "a"), 0, None), token(&ids, "a")],
1141 ),
1142 ),
1143 );
1144 let err = parse_one(&g, "aaa").unwrap_err();
1145 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1146 }
1147
1148 #[test]
1149 fn repeat_min_enforced() {
1150 let ids = IdGen::new();
1151 let g = one_rule_grammar(
1152 &ids,
1153 "s",
1154 node(&ids, "N", repeat(&ids, token(&ids, "a"), 2, None)),
1155 );
1156 assert!(parse_one(&g, "a").is_err());
1158 assert!(parse_one(&g, "aa").is_ok());
1160 }
1161
1162 #[test]
1165 fn farthest_failure_carries_position_and_expected_set() {
1166 let ids = IdGen::new();
1167 let g = one_rule_grammar(
1172 &ids,
1173 "s",
1174 node(
1175 &ids,
1176 "N",
1177 seq(
1178 &ids,
1179 vec![token(&ids, "let"), token(&ids, "x"), token(&ids, "=")],
1180 ),
1181 ),
1182 );
1183 let err = parse_one(&g, "let x !").unwrap_err();
1184 let msg = &err.diagnostics[0].message;
1185 assert!(msg.contains("byte 6"), "{msg}");
1186 assert!(msg.contains("`=`"), "{msg}");
1187 }
1188
1189 #[test]
1192 fn left_recursion_is_detected_at_runtime() {
1193 let ids = IdGen::new();
1194 let r = rule(
1197 &ids,
1198 "r",
1199 seq(&ids, vec![rule_ref(&ids, "r"), token(&ids, "a")]),
1200 );
1201 let g = Grammar::new(vec![r], "r");
1202 let err = g.parse("aaa").unwrap_err();
1203 assert_eq!(err.diagnostics[0].code, codes::LEFT_RECURSION);
1204 }
1205
1206 #[test]
1207 fn unknown_rule_ref_is_diagnosed() {
1208 let ids = IdGen::new();
1209 let r = rule(&ids, "start", rule_ref(&ids, "missing"));
1210 let g = Grammar::new(vec![r], "start");
1211 let err = g.parse("").unwrap_err();
1212 assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1213 }
1214
1215 #[test]
1216 fn unknown_rule_ref_suggests_declared_rule() {
1217 let ids = IdGen::new();
1220 let start = rule(&ids, "start", rule_ref(&ids, "helo"));
1221 let target = rule(&ids, "hello", token(&ids, "hi"));
1222 let g = Grammar::new(vec![start, target], "start");
1223 let err = g.parse("hi").unwrap_err();
1224 assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1225 assert!(
1226 err.diagnostics[0].message.contains("did you mean")
1227 && err.diagnostics[0].message.contains("hello"),
1228 "expected hint, got: {}",
1229 err.diagnostics[0].message
1230 );
1231 }
1232
1233 #[test]
1234 fn unknown_start_rule_is_diagnosed() {
1235 let ids = IdGen::new();
1236 let r = rule(&ids, "other", token(&ids, "x"));
1237 let g = Grammar::new(vec![r], "start");
1238 let err = g.parse("x").unwrap_err();
1239 assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1240 }
1241
1242 #[test]
1243 fn unknown_start_rule_suggests_declared_rule() {
1244 let ids = IdGen::new();
1245 let r = rule(&ids, "start", token(&ids, "x"));
1246 let g = Grammar::new(vec![r], "strat");
1247 let err = g.parse("x").unwrap_err();
1248 assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1249 assert!(
1250 err.diagnostics[0].message.contains("did you mean")
1251 && err.diagnostics[0].message.contains("start"),
1252 "expected hint, got: {}",
1253 err.diagnostics[0].message
1254 );
1255 }
1256
1257 #[test]
1258 fn nullable_repeat_body_below_min_is_rejected() {
1259 let ids = IdGen::new();
1260 let empty_body = seq(&ids, vec![]);
1263 let g = one_rule_grammar(
1264 &ids,
1265 "s",
1266 node(&ids, "N", repeat(&ids, empty_body, 1, None)),
1267 );
1268 let err = g.parse("").unwrap_err();
1269 assert_eq!(err.diagnostics[0].code, codes::NULLABLE_REPEAT);
1270 }
1271}