1#![allow(clippy::result_unit_err)]
93
94use crate::{BuildError, Diagnostic, ParseTree, RawValue, Span};
95use dsl_kit_core::{NodeId, Suggester};
96use dsl_kit_macros::{DslNode as DslNodeDerive, DslSchema as DslSchemaDerive};
97use std::collections::{BTreeSet, HashMap};
98
99#[derive(Debug, Clone, DslNodeDerive, DslSchemaDerive)]
108pub enum Peg {
109 Rule {
114 id: NodeId,
116 name: String,
118 body: Box<Peg>,
120 },
121 Seq {
123 id: NodeId,
125 items: Vec<Peg>,
127 },
128 Choice {
130 id: NodeId,
132 alts: Vec<Peg>,
134 },
135 Repeat {
137 id: NodeId,
139 body: Box<Peg>,
141 min: u32,
143 max: Option<u32>,
145 },
146 RuleRef {
148 id: NodeId,
150 name: String,
152 },
153 Token {
156 id: NodeId,
158 pat: String,
161 },
162 Node {
164 id: NodeId,
166 variant: String,
168 body: Box<Peg>,
170 },
171 Field {
174 id: NodeId,
176 name: String,
178 body: Box<Peg>,
180 },
181 KeyedEntry {
192 id: NodeId,
194 slot: String,
196 key: Box<Peg>,
198 value: Box<Peg>,
200 },
201}
202
203#[derive(Debug, Clone)]
213pub struct Grammar {
214 pub rules: Vec<Peg>,
218 pub start: String,
220}
221
222impl Grammar {
223 pub fn new(rules: Vec<Peg>, start: impl Into<String>) -> Self {
225 Self {
226 rules,
227 start: start.into(),
228 }
229 }
230
231 pub fn parse(&self, input: &str) -> Result<ParseTree, BuildError> {
240 let mut rules_by_name: HashMap<&str, &Peg> = HashMap::new();
241 for r in &self.rules {
242 if let Peg::Rule { name, .. } = r {
243 rules_by_name.insert(name.as_str(), r);
244 }
245 }
246 let start_rule = rules_by_name
247 .get(self.start.as_str())
248 .copied()
249 .ok_or_else(|| {
250 let names: Vec<&str> = rules_by_name.keys().copied().collect();
251 let base = format!("start rule `{}` is not defined in the grammar", self.start);
252 let msg = match crate::BuiltinLevenshteinSuggester
253 .enrich_unknown(self.start.as_str(), &names)
254 {
255 Some(hint) => format!("{base} ({hint})"),
256 None => base,
257 };
258 BuildError::single(Diagnostic::error(codes::UNKNOWN_RULE, msg))
259 })?;
260
261 let mut interp = Interpreter::new(input, rules_by_name);
262 interp.skip_ws();
264 interp.sink_stack.push(ActiveSink::Top(TopSink::default()));
266
267 match interp.run_peg(start_rule) {
268 Ok(()) => {}
269 Err(()) => {
270 if let Some(fatal) = interp.fatal_error.take() {
271 return Err(BuildError::single(fatal));
272 }
273 return Err(BuildError::single(interp.expected_diagnostic()));
274 }
275 }
276
277 interp.skip_ws();
279 if interp.pos != input.len() {
280 let diag = if interp.farthest_pos >= interp.pos && !interp.farthest_expected.is_empty()
283 {
284 interp.expected_diagnostic()
285 } else {
286 Diagnostic::error(
287 codes::UNEXPECTED,
288 format!("unexpected trailing input at byte {}", interp.pos),
289 )
290 .with_span(Some(Span::new(interp.pos, input.len())))
291 };
292 return Err(BuildError::single(diag));
293 }
294
295 let top = match interp.sink_stack.pop() {
296 Some(ActiveSink::Top(t)) => t,
297 _ => unreachable!("top sink must be present"),
298 };
299 top.tree.ok_or_else(|| {
300 BuildError::single(Diagnostic::error(
301 codes::NO_TOP_TREE,
302 format!(
303 "parse succeeded but produced no top-level `Node`; \
304 start rule `{}` must reach exactly one `Peg::Node`",
305 self.start
306 ),
307 ))
308 })
309 }
310}
311
312pub mod codes {
318 pub const UNEXPECTED: &str = "dsl_kit::parse::peg::unexpected";
321 pub const UNKNOWN_RULE: &str = "dsl_kit::parse::peg::unknown_rule";
325 pub const LEFT_RECURSION: &str = "dsl_kit::parse::peg::left_recursion";
330 pub const NULLABLE_REPEAT: &str = "dsl_kit::parse::peg::nullable_repeat";
335 pub const NO_TOP_TREE: &str = "dsl_kit::parse::peg::no_top_tree";
338}
339
340#[derive(Debug, Clone)]
349enum Production {
350 #[allow(dead_code)] Text(String, Span),
352 Tree(ParseTree),
353}
354
355#[derive(Debug, Default, Clone)]
356struct FieldSink {
357 productions: Vec<Production>,
358}
359
360#[derive(Debug, Default, Clone)]
361struct NodeSink {
362 fields: Vec<(String, RawValue)>,
363 children: Vec<(String, Vec<ParseTree>)>,
364 keyed_children: Vec<(String, Vec<(String, ParseTree)>)>,
365}
366
367#[derive(Debug, Default, Clone)]
368struct TopSink {
369 tree: Option<ParseTree>,
370}
371
372#[derive(Debug, Clone)]
375enum ActiveSink {
376 Top(TopSink),
377 Node(NodeSink),
378 Field(FieldSink),
379}
380
381struct Interpreter<'g, 'i> {
382 input: &'i str,
383 pos: usize,
384 rules_by_name: HashMap<&'g str, &'g Peg>,
385 sink_stack: Vec<ActiveSink>,
386 farthest_pos: usize,
388 farthest_expected: BTreeSet<String>,
389 call_stack: Vec<(&'g str, usize)>,
391 fatal_error: Option<Diagnostic>,
394}
395
396impl<'g, 'i> Interpreter<'g, 'i> {
397 fn new(input: &'i str, rules_by_name: HashMap<&'g str, &'g Peg>) -> Self {
398 Self {
399 input,
400 pos: 0,
401 rules_by_name,
402 sink_stack: Vec::new(),
403 farthest_pos: 0,
404 farthest_expected: BTreeSet::new(),
405 call_stack: Vec::new(),
406 fatal_error: None,
407 }
408 }
409
410 fn top_sink_snapshot(&self) -> ActiveSink {
415 self.sink_stack
416 .last()
417 .cloned()
418 .expect("sink stack has at least the top-level entry during parse")
419 }
420
421 fn restore_top_sink(&mut self, snap: ActiveSink) {
422 let last = self
423 .sink_stack
424 .last_mut()
425 .expect("sink stack has at least the top-level entry during parse");
426 *last = snap;
427 }
428
429 fn contribute_text(&mut self, text: String, span: Span) {
430 match self.sink_stack.last_mut() {
431 Some(ActiveSink::Field(s)) => s.productions.push(Production::Text(text, span)),
432 _ => {
433 }
435 }
436 }
437
438 fn contribute_tree(&mut self, tree: ParseTree) {
439 match self.sink_stack.last_mut() {
440 Some(ActiveSink::Field(s)) => s.productions.push(Production::Tree(tree)),
441 Some(ActiveSink::Node(_)) => {
442 }
446 Some(ActiveSink::Top(t)) => {
447 t.tree = Some(tree);
450 }
451 None => unreachable!("sink stack must not be empty during parse"),
452 }
453 }
454
455 fn contribute_field(&mut self, name: &str, productions: Vec<Production>) {
456 if productions.is_empty() {
457 return;
458 }
459 let all_text = productions
460 .iter()
461 .all(|p| matches!(p, Production::Text(..)));
462 let all_tree = productions
463 .iter()
464 .all(|p| matches!(p, Production::Tree(..)));
465
466 let Some(ActiveSink::Node(node_sink)) = self.sink_stack.last_mut() else {
467 return;
469 };
470
471 if all_text {
472 let joined: String = productions
473 .iter()
474 .filter_map(|p| match p {
475 Production::Text(t, _) => Some(t.as_str()),
476 _ => None,
477 })
478 .collect();
479 node_sink
480 .fields
481 .push((name.to_string(), RawValue::Text(joined)));
482 return;
483 }
484 if all_tree {
485 let trees: Vec<ParseTree> = productions
486 .into_iter()
487 .filter_map(|p| match p {
488 Production::Tree(t) => Some(t),
489 _ => None,
490 })
491 .collect();
492 if let Some(slot) = node_sink.children.iter_mut().find(|(n, _)| n == name) {
493 slot.1.extend(trees);
494 } else {
495 node_sink.children.push((name.to_string(), trees));
496 }
497 return;
498 }
499 let trees: Vec<ParseTree> = productions
502 .into_iter()
503 .filter_map(|p| match p {
504 Production::Tree(t) => Some(t),
505 _ => None,
506 })
507 .collect();
508 if trees.is_empty() {
509 return;
510 }
511 if let Some(slot) = node_sink.children.iter_mut().find(|(n, _)| n == name) {
512 slot.1.extend(trees);
513 } else {
514 node_sink.children.push((name.to_string(), trees));
515 }
516 }
517
518 fn expected(&mut self, what: impl Into<String>) {
523 if self.pos > self.farthest_pos {
524 self.farthest_pos = self.pos;
525 self.farthest_expected.clear();
526 self.farthest_expected.insert(what.into());
527 } else if self.pos == self.farthest_pos {
528 self.farthest_expected.insert(what.into());
529 }
530 }
531
532 fn expected_diagnostic(&self) -> Diagnostic {
533 let expected: Vec<String> = self.farthest_expected.iter().cloned().collect();
534 let expected_msg = if expected.is_empty() {
535 "<unknown>".to_string()
536 } else {
537 expected
538 .iter()
539 .map(|e| format!("`{e}`"))
540 .collect::<Vec<_>>()
541 .join(" | ")
542 };
543 let end = self.input.len().min(self.farthest_pos + 1);
544 let got_msg = if self.farthest_pos >= self.input.len() {
545 "end of input".to_string()
546 } else {
547 let bytes = self.input.as_bytes();
548 let snip_end = self.input.len().min(self.farthest_pos + 8);
550 let snip =
551 std::str::from_utf8(&bytes[self.farthest_pos..snip_end]).unwrap_or("<non-utf8>");
552 format!("`{}`", snip)
553 };
554 Diagnostic::error(
555 codes::UNEXPECTED,
556 format!(
557 "expected {expected_msg} at byte {}, got {got_msg}",
558 self.farthest_pos
559 ),
560 )
561 .with_span(Some(Span::new(self.farthest_pos, end)))
562 }
563
564 fn run_peg(&mut self, peg: &'g Peg) -> Result<(), ()> {
569 match peg {
570 Peg::Rule { body, .. } => self.run_peg(body),
571 Peg::Seq { items, .. } => {
572 for item in items {
573 self.run_peg(item)?;
574 }
575 Ok(())
576 }
577 Peg::Choice { alts, .. } => self.run_choice(alts),
578 Peg::Repeat { body, min, max, .. } => self.run_repeat(body, *min, *max),
579 Peg::RuleRef { name, .. } => self.run_rule_ref(name),
580 Peg::Token { pat, .. } => self.match_token(pat),
581 Peg::Node { variant, body, .. } => self.run_node(variant, body),
582 Peg::Field { name, body, .. } => self.run_field(name, body),
583 Peg::KeyedEntry {
584 slot, key, value, ..
585 } => self.run_keyed_entry(slot, key, value),
586 }
587 }
588
589 fn run_choice(&mut self, alts: &'g [Peg]) -> Result<(), ()> {
590 let start_pos = self.pos;
591 let saved = self.top_sink_snapshot();
592 for alt in alts {
593 self.pos = start_pos;
594 self.restore_top_sink(saved.clone());
595 if self.fatal_error.is_some() {
596 return Err(());
597 }
598 if self.run_peg(alt).is_ok() {
599 return Ok(());
600 }
601 if self.fatal_error.is_some() {
602 return Err(());
603 }
604 }
605 self.pos = start_pos;
606 self.restore_top_sink(saved);
607 Err(())
608 }
609
610 fn run_repeat(&mut self, body: &'g Peg, min: u32, max: Option<u32>) -> Result<(), ()> {
611 let mut count: u32 = 0;
612 loop {
613 if let Some(mx) = max
614 && count >= mx
615 {
616 break;
617 }
618 let saved_pos = self.pos;
619 let saved_sink = self.top_sink_snapshot();
620 match self.run_peg(body) {
621 Ok(()) => {
622 if self.pos == saved_pos {
623 if count < min {
628 self.fatal_error = Some(
629 Diagnostic::error(
630 codes::NULLABLE_REPEAT,
631 "repeat body succeeded without consuming input".to_string(),
632 )
633 .with_span(Some(Span::new(saved_pos, saved_pos))),
634 );
635 return Err(());
636 }
637 break;
638 }
639 count += 1;
640 }
641 Err(()) => {
642 if self.fatal_error.is_some() {
643 return Err(());
644 }
645 self.pos = saved_pos;
646 self.restore_top_sink(saved_sink);
647 break;
648 }
649 }
650 }
651 if count < min { Err(()) } else { Ok(()) }
652 }
653
654 fn run_rule_ref(&mut self, name: &str) -> Result<(), ()> {
655 let Some(&rule) = self.rules_by_name.get(name) else {
656 let candidates: Vec<&str> = self.rules_by_name.keys().copied().collect();
657 let base = format!("reference to undefined rule `{name}`");
658 let msg = match crate::BuiltinLevenshteinSuggester.enrich_unknown(name, &candidates) {
659 Some(hint) => format!("{base} ({hint})"),
660 None => base,
661 };
662 self.fatal_error = Some(
663 Diagnostic::error(codes::UNKNOWN_RULE, msg)
664 .with_span(Some(Span::new(self.pos, self.pos))),
665 );
666 return Err(());
667 };
668 let rule_name: &'g str = self
670 .rules_by_name
671 .keys()
672 .copied()
673 .find(|k| *k == name)
674 .expect("just found");
675 if self
678 .call_stack
679 .iter()
680 .any(|(n, p)| *n == rule_name && *p == self.pos)
681 {
682 self.fatal_error = Some(
683 Diagnostic::error(
684 codes::LEFT_RECURSION,
685 format!(
686 "left recursion detected: rule `{name}` re-entered at byte {}",
687 self.pos
688 ),
689 )
690 .with_span(Some(Span::new(self.pos, self.pos))),
691 );
692 return Err(());
693 }
694 self.call_stack.push((rule_name, self.pos));
695 let r = self.run_peg(rule);
696 self.call_stack.pop();
697 r
698 }
699
700 fn run_node(&mut self, variant: &str, body: &'g Peg) -> Result<(), ()> {
701 let start_pos = self.pos;
702 self.sink_stack.push(ActiveSink::Node(NodeSink::default()));
703 let body_result = self.run_peg(body);
704 let node_sink = match self.sink_stack.pop() {
705 Some(ActiveSink::Node(s)) => s,
706 _ => unreachable!("balanced push/pop of NodeSink"),
707 };
708 body_result?;
709 let end_pos = self.pos;
710 let mut keyed_children = node_sink.keyed_children;
716 for (_, entries) in &mut keyed_children {
717 entries.sort_by(|(a, _), (b, _)| a.cmp(b));
718 }
719
720 let tree = ParseTree {
721 variant: variant.to_string(),
722 fields: node_sink.fields,
723 children: node_sink.children,
724 keyed_children,
725 span: Some(Span::new(start_pos, end_pos)),
726 };
727 self.contribute_tree(tree);
728 Ok(())
729 }
730
731 fn run_field(&mut self, name: &str, body: &'g Peg) -> Result<(), ()> {
732 self.sink_stack
733 .push(ActiveSink::Field(FieldSink::default()));
734 let body_result = self.run_peg(body);
735 let field_sink = match self.sink_stack.pop() {
736 Some(ActiveSink::Field(s)) => s,
737 _ => unreachable!("balanced push/pop of FieldSink"),
738 };
739 body_result?;
740 self.contribute_field(name, field_sink.productions);
741 Ok(())
742 }
743
744 fn run_keyed_entry(&mut self, slot: &str, key: &'g Peg, value: &'g Peg) -> Result<(), ()> {
753 let key_text = {
754 self.sink_stack
755 .push(ActiveSink::Field(FieldSink::default()));
756 let result = self.run_peg(key);
757 let sink = match self.sink_stack.pop() {
758 Some(ActiveSink::Field(s)) => s,
759 _ => unreachable!("balanced push/pop of FieldSink"),
760 };
761 result?;
762 if sink.productions.is_empty() {
771 self.expected("a text production for the keyed-entry key");
772 return Err(());
773 }
774 let mut text = String::new();
775 for production in &sink.productions {
776 match production {
777 Production::Text(t, _) => text.push_str(t),
778 Production::Tree(_) => {
781 self.expected("a text production for the keyed-entry key");
782 return Err(());
783 }
784 }
785 }
786 text
787 };
788
789 self.sink_stack
790 .push(ActiveSink::Field(FieldSink::default()));
791 let value_result = self.run_peg(value);
792 let value_sink = match self.sink_stack.pop() {
793 Some(ActiveSink::Field(s)) => s,
794 _ => unreachable!("balanced push/pop of FieldSink"),
795 };
796 value_result?;
797
798 let mut trees = value_sink.productions.into_iter().filter_map(|p| match p {
799 Production::Tree(t) => Some(t),
800 Production::Text(..) => None,
803 });
804 let Some(tree) = trees.next() else {
805 self.expected("a subtree production for the keyed-entry value");
806 return Err(());
807 };
808 if trees.next().is_some() {
809 self.expected("exactly one subtree for the keyed-entry value");
810 return Err(());
811 }
812
813 let Some(ActiveSink::Node(node_sink)) = self.sink_stack.last_mut() else {
814 return Ok(());
818 };
819 if let Some(existing) = node_sink.keyed_children.iter_mut().find(|(n, _)| n == slot) {
820 existing.1.push((key_text, tree));
821 } else {
822 node_sink
823 .keyed_children
824 .push((slot.to_string(), vec![(key_text, tree)]));
825 }
826 Ok(())
827 }
828
829 fn match_token(&mut self, pat: &str) -> Result<(), ()> {
834 if pat != "%ws" {
835 self.skip_ws();
836 }
837 let start = self.pos;
838 if pat == "%str" {
839 return match self.match_str() {
842 Some(decoded) => {
843 let end = self.pos;
844 self.contribute_text(decoded, Span::new(start, end));
845 Ok(())
846 }
847 None => {
848 self.expected(pat);
849 self.pos = start;
850 Err(())
851 }
852 };
853 }
854 if pat == "%str_raw" {
855 return match self.match_str() {
860 Some(_) => {
861 let end = self.pos;
862 let text = self.input[start..end].to_string();
863 self.contribute_text(text, Span::new(start, end));
864 Ok(())
865 }
866 None => {
867 self.expected(pat);
868 self.pos = start;
869 Err(())
870 }
871 };
872 }
873 let ok = if pat == "%ident" {
874 self.match_ident()
875 } else if pat == "%int" {
876 self.match_int()
877 } else if pat == "%ws" {
878 self.match_ws_required()
879 } else if let Some(word) = pat.strip_prefix("%kw:") {
880 self.match_keyword(word)
881 } else {
882 self.match_literal(pat)
883 };
884 if ok {
885 let end = self.pos;
886 let text = self.input[start..end].to_string();
887 self.contribute_text(text, Span::new(start, end));
888 Ok(())
889 } else {
890 self.expected(pat);
894 self.pos = start;
895 Err(())
896 }
897 }
898
899 fn skip_ws(&mut self) {
900 let bytes = self.input.as_bytes();
901 while let Some(&c) = bytes.get(self.pos) {
902 if matches!(c, b' ' | b'\t' | b'\n' | b'\r') {
903 self.pos += 1;
904 } else {
905 break;
906 }
907 }
908 }
909
910 fn match_ident(&mut self) -> bool {
911 let bytes = self.input.as_bytes();
912 match bytes.get(self.pos) {
913 Some(&c) if is_ident_start(c) => self.pos += 1,
914 _ => return false,
915 }
916 while let Some(&c) = bytes.get(self.pos) {
917 if is_ident_cont(c) {
918 self.pos += 1;
919 } else {
920 break;
921 }
922 }
923 true
924 }
925
926 fn match_int(&mut self) -> bool {
927 let bytes = self.input.as_bytes();
928 let mut p = self.pos;
929 if bytes.get(p) == Some(&b'-') {
930 p += 1;
931 }
932 let digit_start = p;
933 while let Some(&c) = bytes.get(p) {
934 if c.is_ascii_digit() {
935 p += 1;
936 } else {
937 break;
938 }
939 }
940 if p > digit_start {
941 self.pos = p;
942 true
943 } else {
944 false
945 }
946 }
947
948 fn match_str(&mut self) -> Option<String> {
952 let rest = &self.input[self.pos..];
953 let mut chars = rest.char_indices();
954 match chars.next() {
955 Some((_, '"')) => {}
956 _ => return None,
957 }
958 let mut out = String::new();
959 while let Some((i, c)) = chars.next() {
960 match c {
961 '"' => {
962 self.pos += i + 1;
963 return Some(out);
964 }
965 '\\' => match chars.next() {
966 Some((_, '"')) => out.push('"'),
967 Some((_, '\\')) => out.push('\\'),
968 Some((_, 'n')) => out.push('\n'),
969 Some((_, 't')) => out.push('\t'),
970 Some((_, 'r')) => out.push('\r'),
971 _ => return None,
972 },
973 other => out.push(other),
974 }
975 }
976 None
977 }
978
979 fn match_ws_required(&mut self) -> bool {
980 let start = self.pos;
981 let bytes = self.input.as_bytes();
982 while let Some(&c) = bytes.get(self.pos) {
983 if matches!(c, b' ' | b'\t' | b'\n' | b'\r') {
984 self.pos += 1;
985 } else {
986 break;
987 }
988 }
989 self.pos > start
990 }
991
992 fn match_literal(&mut self, s: &str) -> bool {
993 let bytes = self.input.as_bytes();
994 let end = self.pos + s.len();
995 if end > bytes.len() {
996 return false;
997 }
998 if &bytes[self.pos..end] != s.as_bytes() {
999 return false;
1000 }
1001 self.pos = end;
1002 true
1003 }
1004
1005 fn match_keyword(&mut self, word: &str) -> bool {
1006 let saved = self.pos;
1007 if !self.match_literal(word) {
1008 return false;
1009 }
1010 if let Some(&next) = self.input.as_bytes().get(self.pos)
1012 && is_ident_cont(next)
1013 {
1014 self.pos = saved;
1015 return false;
1016 }
1017 true
1018 }
1019}
1020
1021fn is_ident_start(c: u8) -> bool {
1022 c.is_ascii_alphabetic() || c == b'_'
1023}
1024
1025fn is_ident_cont(c: u8) -> bool {
1026 c.is_ascii_alphanumeric() || c == b'_'
1027}
1028
1029use dsl_kit_core::IdGen;
1035
1036pub fn rule(ids: &IdGen, name: impl Into<String>, body: Peg) -> Peg {
1038 Peg::Rule {
1039 id: ids.node(),
1040 name: name.into(),
1041 body: Box::new(body),
1042 }
1043}
1044
1045pub fn seq(ids: &IdGen, items: Vec<Peg>) -> Peg {
1047 Peg::Seq {
1048 id: ids.node(),
1049 items,
1050 }
1051}
1052
1053pub fn choice(ids: &IdGen, alts: Vec<Peg>) -> Peg {
1055 Peg::Choice {
1056 id: ids.node(),
1057 alts,
1058 }
1059}
1060
1061pub fn repeat(ids: &IdGen, body: Peg, min: u32, max: Option<u32>) -> Peg {
1063 Peg::Repeat {
1064 id: ids.node(),
1065 body: Box::new(body),
1066 min,
1067 max,
1068 }
1069}
1070
1071pub fn rule_ref(ids: &IdGen, name: impl Into<String>) -> Peg {
1073 Peg::RuleRef {
1074 id: ids.node(),
1075 name: name.into(),
1076 }
1077}
1078
1079pub fn token(ids: &IdGen, pat: impl Into<String>) -> Peg {
1081 Peg::Token {
1082 id: ids.node(),
1083 pat: pat.into(),
1084 }
1085}
1086
1087pub fn node(ids: &IdGen, variant: impl Into<String>, body: Peg) -> Peg {
1089 Peg::Node {
1090 id: ids.node(),
1091 variant: variant.into(),
1092 body: Box::new(body),
1093 }
1094}
1095
1096pub fn field(ids: &IdGen, name: impl Into<String>, body: Peg) -> Peg {
1098 Peg::Field {
1099 id: ids.node(),
1100 name: name.into(),
1101 body: Box::new(body),
1102 }
1103}
1104
1105pub fn keyed_entry(ids: &IdGen, slot: impl Into<String>, key: Peg, value: Peg) -> Peg {
1110 Peg::KeyedEntry {
1111 id: ids.node(),
1112 slot: slot.into(),
1113 key: Box::new(key),
1114 value: Box::new(value),
1115 }
1116}
1117
1118#[cfg(test)]
1123mod tests {
1124 use super::*;
1125 use dsl_kit_core::IdGen;
1126 use dsl_kit_schema::DslSchema;
1127
1128 #[test]
1131 fn peg_schema_lists_all_variants() {
1132 let s = Peg::schema();
1133 assert_eq!(s.name, "Peg");
1134 let names: Vec<&str> = s.variants.iter().map(|v| v.name.as_str()).collect();
1135 assert_eq!(
1136 names,
1137 vec![
1138 "Rule",
1139 "Seq",
1140 "Choice",
1141 "Repeat",
1142 "RuleRef",
1143 "Token",
1144 "Node",
1145 "Field",
1146 "KeyedEntry"
1147 ]
1148 );
1149 let keyed = s.variant("KeyedEntry").unwrap();
1153 let keyed_children: Vec<&str> = keyed.children.iter().map(|c| c.name.as_str()).collect();
1154 assert_eq!(keyed_children, vec!["key", "value"]);
1155 let keyed_fields: Vec<&str> = keyed.fields.iter().map(|f| f.name.as_str()).collect();
1156 assert_eq!(keyed_fields, vec!["slot"]);
1157
1158 let repeat = s.variant("Repeat").unwrap();
1159 assert_eq!(repeat.children.len(), 1);
1161 assert_eq!(repeat.children[0].name, "body");
1162 let field_names: Vec<&str> = repeat.fields.iter().map(|f| f.name.as_str()).collect();
1163 assert!(field_names.contains(&"min"));
1164 assert!(field_names.contains(&"max"));
1165 }
1166
1167 fn parse_one(g: &Grammar, input: &str) -> Result<ParseTree, BuildError> {
1170 g.parse(input)
1171 }
1172
1173 fn one_rule_grammar(ids: &IdGen, start: &str, body: Peg) -> Grammar {
1174 Grammar::new(vec![rule(ids, start, body)], start)
1175 }
1176
1177 fn keyed_grammar(ids: &IdGen, key: Peg, value: Peg) -> Grammar {
1189 let entry = keyed_entry(ids, "entries", key, value);
1190 one_rule_grammar(
1191 ids,
1192 "start",
1193 node(
1194 ids,
1195 "Env",
1196 seq(
1197 ids,
1198 vec![
1199 token(ids, "{"),
1200 repeat(
1201 ids,
1202 seq(ids, vec![entry, repeat(ids, token(ids, ","), 0, Some(1))]),
1203 0,
1204 None,
1205 ),
1206 token(ids, "}"),
1207 ],
1208 ),
1209 ),
1210 )
1211 }
1212
1213 fn keyed_leaf_value(ids: &IdGen) -> Peg {
1215 seq(
1216 ids,
1217 vec![
1218 token(ids, ":"),
1219 node(ids, "Lit", field(ids, "value", token(ids, "%int"))),
1220 ],
1221 )
1222 }
1223
1224 #[test]
1225 fn keyed_entry_pairs_key_with_subtree_and_sorts() {
1226 let ids = IdGen::new();
1227 let g = keyed_grammar(&ids, token(&ids, "%ident"), keyed_leaf_value(&ids));
1228 let tree = parse_one(&g, "{ b: 2, a: 1 }").unwrap();
1229 let entries = tree.keyed_child_slot("entries").expect("slot bound");
1230 let keys: Vec<&str> = entries.iter().map(|(k, _)| k.as_str()).collect();
1231 assert_eq!(keys, ["a", "b"], "Node emission sorts by key");
1232 let values: Vec<&RawValue> = entries
1234 .iter()
1235 .map(|(_, t)| t.field("value").expect("leaf payload"))
1236 .collect();
1237 assert_eq!(values[0], &RawValue::Text("1".into()));
1238 assert_eq!(values[1], &RawValue::Text("2".into()));
1239 }
1240
1241 #[test]
1242 fn keyed_entry_accepts_an_empty_string_key() {
1243 let ids = IdGen::new();
1244 let g = keyed_grammar(&ids, token(&ids, "%str"), keyed_leaf_value(&ids));
1248 let tree = parse_one(&g, r#"{ "": 1 }"#).unwrap();
1249 let entries = tree.keyed_child_slot("entries").expect("slot bound");
1250 assert_eq!(entries.len(), 1);
1251 assert_eq!(entries[0].0, "");
1252 }
1253
1254 #[test]
1255 fn keyed_entry_rejects_a_key_half_that_produces_nothing() {
1256 let ids = IdGen::new();
1257 let g = keyed_grammar(
1263 &ids,
1264 repeat(&ids, token(&ids, "%ident"), 0, Some(1)),
1265 keyed_leaf_value(&ids),
1266 );
1267 let err = parse_one(&g, "{ : 1 }").unwrap_err();
1268 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1269 }
1270
1271 #[test]
1272 fn keyed_entry_rejects_a_tree_where_the_key_belongs() {
1273 let ids = IdGen::new();
1274 let g = keyed_grammar(
1275 &ids,
1276 node(&ids, "Lit", field(&ids, "value", token(&ids, "%int"))),
1277 keyed_leaf_value(&ids),
1278 );
1279 let err = parse_one(&g, "{ 1: 2 }").unwrap_err();
1280 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1281 }
1282
1283 #[test]
1284 fn keyed_entry_rejects_a_value_half_without_exactly_one_tree() {
1285 let ids = IdGen::new();
1286
1287 let none = keyed_grammar(
1289 &ids,
1290 token(&ids, "%ident"),
1291 seq(&ids, vec![token(&ids, ":"), token(&ids, "%int")]),
1292 );
1293 assert!(parse_one(&none, "{ a: 1 }").is_err());
1294
1295 let leaf = |ids: &IdGen| node(ids, "Lit", field(ids, "value", token(ids, "%int")));
1297 let two = keyed_grammar(
1298 &ids,
1299 token(&ids, "%ident"),
1300 seq(&ids, vec![token(&ids, ":"), leaf(&ids), leaf(&ids)]),
1301 );
1302 assert!(parse_one(&two, "{ a: 1 2 }").is_err());
1303 }
1304
1305 #[test]
1306 fn keyed_entry_survives_backtracking_without_leaking_entries() {
1307 let ids = IdGen::new();
1308 let entry_then_semi = seq(
1314 &ids,
1315 vec![
1316 keyed_entry(
1317 &ids,
1318 "entries",
1319 token(&ids, "%ident"),
1320 keyed_leaf_value(&ids),
1321 ),
1322 token(&ids, ";"),
1323 ],
1324 );
1325 let entry_then_end = seq(
1326 &ids,
1327 vec![
1328 keyed_entry(
1329 &ids,
1330 "entries",
1331 token(&ids, "%ident"),
1332 keyed_leaf_value(&ids),
1333 ),
1334 token(&ids, "}"),
1335 ],
1336 );
1337 let g = one_rule_grammar(
1338 &ids,
1339 "start",
1340 node(
1341 &ids,
1342 "Env",
1343 seq(
1344 &ids,
1345 vec![
1346 token(&ids, "{"),
1347 choice(&ids, vec![entry_then_semi, entry_then_end]),
1348 ],
1349 ),
1350 ),
1351 );
1352
1353 let tree = parse_one(&g, "{ a: 1 }").unwrap();
1354 let entries = tree.keyed_child_slot("entries").expect("slot bound");
1355 assert_eq!(
1356 entries.len(),
1357 1,
1358 "the failed alternative's entry must be rolled back, not kept: {entries:?}"
1359 );
1360 assert_eq!(entries[0].0, "a");
1361 }
1362
1363 #[test]
1364 fn keyed_entry_outside_a_node_drops_the_entry() {
1365 let ids = IdGen::new();
1366 let g = one_rule_grammar(
1371 &ids,
1372 "start",
1373 seq(
1374 &ids,
1375 vec![
1376 keyed_entry(
1377 &ids,
1378 "entries",
1379 token(&ids, "%ident"),
1380 keyed_leaf_value(&ids),
1381 ),
1382 node(&ids, "Env", token(&ids, "!")),
1383 ],
1384 ),
1385 );
1386 let tree = parse_one(&g, "a: 1 !").unwrap();
1387 assert_eq!(tree.variant, "Env");
1388 assert!(
1389 tree.keyed_children.is_empty(),
1390 "a keyed entry with no enclosing Node has nowhere to land: {:?}",
1391 tree.keyed_children
1392 );
1393 }
1394
1395 #[test]
1396 fn literal_token_and_wrap_node() {
1397 let ids = IdGen::new();
1398 let g = one_rule_grammar(
1400 &ids,
1401 "start",
1402 node(&ids, "K", field(&ids, "kw", token(&ids, "let"))),
1403 );
1404 let tree = parse_one(&g, "let").unwrap();
1405 assert_eq!(tree.variant, "K");
1406 assert_eq!(tree.fields.len(), 1);
1407 assert_eq!(tree.fields[0].0, "kw");
1408 match &tree.fields[0].1 {
1409 RawValue::Text(t) => assert_eq!(t, "let"),
1410 _ => panic!("expected text"),
1411 }
1412 }
1413
1414 #[test]
1415 fn keyword_guard_blocks_prefix_match() {
1416 let ids = IdGen::new();
1417 let g = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "%kw:let")));
1420 let err = parse_one(&g, "letme").unwrap_err();
1421 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1422
1423 let g2 = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "%kw:let")));
1425 assert!(parse_one(&g2, "let ").is_ok());
1426 }
1427
1428 #[test]
1429 fn plain_literal_has_no_word_boundary_guard() {
1430 let ids = IdGen::new();
1431 let g = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "a")));
1434 let err = parse_one(&g, "ab").unwrap_err();
1435 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1437 assert!(
1438 err.diagnostics[0].message.contains("trailing"),
1439 "{}",
1440 err.diagnostics[0].message
1441 );
1442 }
1443
1444 #[test]
1445 fn ident_and_int_classes() {
1446 let ids = IdGen::new();
1447 let g = one_rule_grammar(
1448 &ids,
1449 "s",
1450 node(&ids, "Var", field(&ids, "name", token(&ids, "%ident"))),
1451 );
1452 let t = parse_one(&g, "foo_bar1").unwrap();
1453 assert_eq!(t.variant, "Var");
1454 match &t.fields[0].1 {
1455 RawValue::Text(v) => assert_eq!(v, "foo_bar1"),
1456 _ => panic!(),
1457 }
1458
1459 let g2 = one_rule_grammar(
1460 &ids,
1461 "s",
1462 node(&ids, "N", field(&ids, "v", token(&ids, "%int"))),
1463 );
1464 let t2 = parse_one(&g2, "-42").unwrap();
1465 match &t2.fields[0].1 {
1466 RawValue::Text(v) => assert_eq!(v, "-42"),
1467 _ => panic!(),
1468 }
1469 }
1470
1471 #[test]
1474 fn implicit_ws_skip_before_tokens_and_at_boundaries() {
1475 let ids = IdGen::new();
1476 let body = seq(
1478 &ids,
1479 vec![
1480 field(&ids, "a", token(&ids, "%int")),
1481 field(&ids, "b", token(&ids, "%int")),
1482 ],
1483 );
1484 let g = one_rule_grammar(&ids, "s", node(&ids, "P", body));
1485 let t = parse_one(&g, " 3 7 ").unwrap();
1486 assert_eq!(t.fields.len(), 2);
1487 assert_eq!(t.fields[0].0, "a");
1488 assert_eq!(t.fields[1].0, "b");
1489 }
1490
1491 #[test]
1494 fn choice_commits_on_first_match() {
1495 let ids = IdGen::new();
1496 let alt_a = node(&ids, "A", token(&ids, "a"));
1500 let alt_ab = node(&ids, "B", token(&ids, "ab"));
1501 let g = one_rule_grammar(&ids, "s", choice(&ids, vec![alt_a, alt_ab]));
1502 let err = parse_one(&g, "ab").unwrap_err();
1503 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1506 assert!(
1507 err.diagnostics[0].message.contains("byte 1"),
1508 "{}",
1509 err.diagnostics[0].message
1510 );
1511 }
1512
1513 #[test]
1514 fn failed_alt_restores_position() {
1515 let ids = IdGen::new();
1516 let alt_abc = node(&ids, "L", token(&ids, "abc"));
1520 let alt_a = node(&ids, "S", token(&ids, "a"));
1521 let g = one_rule_grammar(&ids, "s", choice(&ids, vec![alt_abc, alt_a]));
1522 let err = parse_one(&g, "ab").unwrap_err();
1523 assert!(
1525 err.diagnostics[0].message.contains("byte 1"),
1526 "{}",
1527 err.diagnostics[0].message
1528 );
1529 }
1530
1531 #[test]
1532 fn repeat_is_greedy_and_no_backtrack_into_completed() {
1533 let ids = IdGen::new();
1534 let g = one_rule_grammar(
1539 &ids,
1540 "s",
1541 node(
1542 &ids,
1543 "N",
1544 seq(
1545 &ids,
1546 vec![repeat(&ids, token(&ids, "a"), 0, None), token(&ids, "a")],
1547 ),
1548 ),
1549 );
1550 let err = parse_one(&g, "aaa").unwrap_err();
1551 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1552 }
1553
1554 #[test]
1555 fn repeat_min_enforced() {
1556 let ids = IdGen::new();
1557 let g = one_rule_grammar(
1558 &ids,
1559 "s",
1560 node(&ids, "N", repeat(&ids, token(&ids, "a"), 2, None)),
1561 );
1562 assert!(parse_one(&g, "a").is_err());
1564 assert!(parse_one(&g, "aa").is_ok());
1566 }
1567
1568 #[test]
1571 fn farthest_failure_carries_position_and_expected_set() {
1572 let ids = IdGen::new();
1573 let g = one_rule_grammar(
1578 &ids,
1579 "s",
1580 node(
1581 &ids,
1582 "N",
1583 seq(
1584 &ids,
1585 vec![token(&ids, "let"), token(&ids, "x"), token(&ids, "=")],
1586 ),
1587 ),
1588 );
1589 let err = parse_one(&g, "let x !").unwrap_err();
1590 let msg = &err.diagnostics[0].message;
1591 assert!(msg.contains("byte 6"), "{msg}");
1592 assert!(msg.contains("`=`"), "{msg}");
1593 }
1594
1595 #[test]
1598 fn left_recursion_is_detected_at_runtime() {
1599 let ids = IdGen::new();
1600 let r = rule(
1603 &ids,
1604 "r",
1605 seq(&ids, vec![rule_ref(&ids, "r"), token(&ids, "a")]),
1606 );
1607 let g = Grammar::new(vec![r], "r");
1608 let err = g.parse("aaa").unwrap_err();
1609 assert_eq!(err.diagnostics[0].code, codes::LEFT_RECURSION);
1610 }
1611
1612 #[test]
1613 fn unknown_rule_ref_is_diagnosed() {
1614 let ids = IdGen::new();
1615 let r = rule(&ids, "start", rule_ref(&ids, "missing"));
1616 let g = Grammar::new(vec![r], "start");
1617 let err = g.parse("").unwrap_err();
1618 assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1619 }
1620
1621 #[test]
1622 fn unknown_rule_ref_suggests_declared_rule() {
1623 let ids = IdGen::new();
1626 let start = rule(&ids, "start", rule_ref(&ids, "helo"));
1627 let target = rule(&ids, "hello", token(&ids, "hi"));
1628 let g = Grammar::new(vec![start, target], "start");
1629 let err = g.parse("hi").unwrap_err();
1630 assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1631 assert!(
1632 err.diagnostics[0].message.contains("did you mean")
1633 && err.diagnostics[0].message.contains("hello"),
1634 "expected hint, got: {}",
1635 err.diagnostics[0].message
1636 );
1637 }
1638
1639 #[test]
1640 fn unknown_start_rule_is_diagnosed() {
1641 let ids = IdGen::new();
1642 let r = rule(&ids, "other", token(&ids, "x"));
1643 let g = Grammar::new(vec![r], "start");
1644 let err = g.parse("x").unwrap_err();
1645 assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1646 }
1647
1648 #[test]
1649 fn unknown_start_rule_suggests_declared_rule() {
1650 let ids = IdGen::new();
1651 let r = rule(&ids, "start", token(&ids, "x"));
1652 let g = Grammar::new(vec![r], "strat");
1653 let err = g.parse("x").unwrap_err();
1654 assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1655 assert!(
1656 err.diagnostics[0].message.contains("did you mean")
1657 && err.diagnostics[0].message.contains("start"),
1658 "expected hint, got: {}",
1659 err.diagnostics[0].message
1660 );
1661 }
1662
1663 #[test]
1664 fn nullable_repeat_body_below_min_is_rejected() {
1665 let ids = IdGen::new();
1666 let empty_body = seq(&ids, vec![]);
1669 let g = one_rule_grammar(
1670 &ids,
1671 "s",
1672 node(&ids, "N", repeat(&ids, empty_body, 1, None)),
1673 );
1674 let err = g.parse("").unwrap_err();
1675 assert_eq!(err.diagnostics[0].code, codes::NULLABLE_REPEAT);
1676 }
1677}