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 let tree = 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 crate::allow::collapse(tree)
315 }
316}
317
318pub mod codes {
324 pub const UNEXPECTED: &str = "dsl_kit::parse::peg::unexpected";
327 pub const UNKNOWN_RULE: &str = "dsl_kit::parse::peg::unknown_rule";
331 pub const LEFT_RECURSION: &str = "dsl_kit::parse::peg::left_recursion";
336 pub const NULLABLE_REPEAT: &str = "dsl_kit::parse::peg::nullable_repeat";
341 pub const NO_TOP_TREE: &str = "dsl_kit::parse::peg::no_top_tree";
344}
345
346#[derive(Debug, Clone)]
355enum Production {
356 #[allow(dead_code)] Text(String, Span),
358 Tree(ParseTree),
359}
360
361#[derive(Debug, Default, Clone)]
362struct FieldSink {
363 productions: Vec<Production>,
364}
365
366#[derive(Debug, Default, Clone)]
367struct NodeSink {
368 fields: Vec<(String, RawValue)>,
369 children: Vec<(String, Vec<ParseTree>)>,
370 keyed_children: Vec<(String, Vec<(String, ParseTree)>)>,
371}
372
373#[derive(Debug, Default, Clone)]
374struct TopSink {
375 tree: Option<ParseTree>,
376}
377
378#[derive(Debug, Clone)]
381enum ActiveSink {
382 Top(TopSink),
383 Node(NodeSink),
384 Field(FieldSink),
385}
386
387struct Interpreter<'g, 'i> {
388 input: &'i str,
389 pos: usize,
390 rules_by_name: HashMap<&'g str, &'g Peg>,
391 sink_stack: Vec<ActiveSink>,
392 farthest_pos: usize,
394 farthest_expected: BTreeSet<String>,
395 call_stack: Vec<(&'g str, usize)>,
397 fatal_error: Option<Diagnostic>,
400}
401
402impl<'g, 'i> Interpreter<'g, 'i> {
403 fn new(input: &'i str, rules_by_name: HashMap<&'g str, &'g Peg>) -> Self {
404 Self {
405 input,
406 pos: 0,
407 rules_by_name,
408 sink_stack: Vec::new(),
409 farthest_pos: 0,
410 farthest_expected: BTreeSet::new(),
411 call_stack: Vec::new(),
412 fatal_error: None,
413 }
414 }
415
416 fn top_sink_snapshot(&self) -> ActiveSink {
421 self.sink_stack
422 .last()
423 .cloned()
424 .expect("sink stack has at least the top-level entry during parse")
425 }
426
427 fn restore_top_sink(&mut self, snap: ActiveSink) {
428 let last = self
429 .sink_stack
430 .last_mut()
431 .expect("sink stack has at least the top-level entry during parse");
432 *last = snap;
433 }
434
435 fn contribute_text(&mut self, text: String, span: Span) {
436 match self.sink_stack.last_mut() {
437 Some(ActiveSink::Field(s)) => s.productions.push(Production::Text(text, span)),
438 _ => {
439 }
441 }
442 }
443
444 fn contribute_tree(&mut self, tree: ParseTree) {
445 match self.sink_stack.last_mut() {
446 Some(ActiveSink::Field(s)) => s.productions.push(Production::Tree(tree)),
447 Some(ActiveSink::Node(_)) => {
448 }
452 Some(ActiveSink::Top(t)) => {
453 t.tree = Some(tree);
456 }
457 None => unreachable!("sink stack must not be empty during parse"),
458 }
459 }
460
461 fn contribute_field(&mut self, name: &str, productions: Vec<Production>) {
462 if productions.is_empty() {
463 return;
464 }
465 let all_text = productions
466 .iter()
467 .all(|p| matches!(p, Production::Text(..)));
468 let all_tree = productions
469 .iter()
470 .all(|p| matches!(p, Production::Tree(..)));
471
472 let Some(ActiveSink::Node(node_sink)) = self.sink_stack.last_mut() else {
473 return;
475 };
476
477 if all_text {
478 let joined: String = productions
479 .iter()
480 .filter_map(|p| match p {
481 Production::Text(t, _) => Some(t.as_str()),
482 _ => None,
483 })
484 .collect();
485 node_sink
486 .fields
487 .push((name.to_string(), RawValue::Text(joined)));
488 return;
489 }
490 if all_tree {
491 let trees: Vec<ParseTree> = productions
492 .into_iter()
493 .filter_map(|p| match p {
494 Production::Tree(t) => Some(t),
495 _ => None,
496 })
497 .collect();
498 if let Some(slot) = node_sink.children.iter_mut().find(|(n, _)| n == name) {
499 slot.1.extend(trees);
500 } else {
501 node_sink.children.push((name.to_string(), trees));
502 }
503 return;
504 }
505 let trees: Vec<ParseTree> = productions
508 .into_iter()
509 .filter_map(|p| match p {
510 Production::Tree(t) => Some(t),
511 _ => None,
512 })
513 .collect();
514 if trees.is_empty() {
515 return;
516 }
517 if let Some(slot) = node_sink.children.iter_mut().find(|(n, _)| n == name) {
518 slot.1.extend(trees);
519 } else {
520 node_sink.children.push((name.to_string(), trees));
521 }
522 }
523
524 fn expected(&mut self, what: impl Into<String>) {
529 if self.pos > self.farthest_pos {
530 self.farthest_pos = self.pos;
531 self.farthest_expected.clear();
532 self.farthest_expected.insert(what.into());
533 } else if self.pos == self.farthest_pos {
534 self.farthest_expected.insert(what.into());
535 }
536 }
537
538 fn expected_diagnostic(&self) -> Diagnostic {
539 let expected: Vec<String> = self.farthest_expected.iter().cloned().collect();
540 let expected_msg = if expected.is_empty() {
541 "<unknown>".to_string()
542 } else {
543 expected
544 .iter()
545 .map(|e| format!("`{e}`"))
546 .collect::<Vec<_>>()
547 .join(" | ")
548 };
549 let end = self.input.len().min(self.farthest_pos + 1);
550 let got_msg = if self.farthest_pos >= self.input.len() {
551 "end of input".to_string()
552 } else {
553 let bytes = self.input.as_bytes();
554 let snip_end = self.input.len().min(self.farthest_pos + 8);
556 let snip =
557 std::str::from_utf8(&bytes[self.farthest_pos..snip_end]).unwrap_or("<non-utf8>");
558 format!("`{}`", snip)
559 };
560 Diagnostic::error(
561 codes::UNEXPECTED,
562 format!(
563 "expected {expected_msg} at byte {}, got {got_msg}",
564 self.farthest_pos
565 ),
566 )
567 .with_span(Some(Span::new(self.farthest_pos, end)))
568 }
569
570 fn run_peg(&mut self, peg: &'g Peg) -> Result<(), ()> {
575 match peg {
576 Peg::Rule { body, .. } => self.run_peg(body),
577 Peg::Seq { items, .. } => {
578 for item in items {
579 self.run_peg(item)?;
580 }
581 Ok(())
582 }
583 Peg::Choice { alts, .. } => self.run_choice(alts),
584 Peg::Repeat { body, min, max, .. } => self.run_repeat(body, *min, *max),
585 Peg::RuleRef { name, .. } => self.run_rule_ref(name),
586 Peg::Token { pat, .. } => self.match_token(pat),
587 Peg::Node { variant, body, .. } => self.run_node(variant, body),
588 Peg::Field { name, body, .. } => self.run_field(name, body),
589 Peg::KeyedEntry {
590 slot, key, value, ..
591 } => self.run_keyed_entry(slot, key, value),
592 }
593 }
594
595 fn run_choice(&mut self, alts: &'g [Peg]) -> Result<(), ()> {
596 let start_pos = self.pos;
597 let saved = self.top_sink_snapshot();
598 for alt in alts {
599 self.pos = start_pos;
600 self.restore_top_sink(saved.clone());
601 if self.fatal_error.is_some() {
602 return Err(());
603 }
604 if self.run_peg(alt).is_ok() {
605 return Ok(());
606 }
607 if self.fatal_error.is_some() {
608 return Err(());
609 }
610 }
611 self.pos = start_pos;
612 self.restore_top_sink(saved);
613 Err(())
614 }
615
616 fn run_repeat(&mut self, body: &'g Peg, min: u32, max: Option<u32>) -> Result<(), ()> {
617 let mut count: u32 = 0;
618 loop {
619 if let Some(mx) = max
620 && count >= mx
621 {
622 break;
623 }
624 let saved_pos = self.pos;
625 let saved_sink = self.top_sink_snapshot();
626 match self.run_peg(body) {
627 Ok(()) => {
628 if self.pos == saved_pos {
629 if count < min {
634 self.fatal_error = Some(
635 Diagnostic::error(
636 codes::NULLABLE_REPEAT,
637 "repeat body succeeded without consuming input".to_string(),
638 )
639 .with_span(Some(Span::new(saved_pos, saved_pos))),
640 );
641 return Err(());
642 }
643 break;
644 }
645 count += 1;
646 }
647 Err(()) => {
648 if self.fatal_error.is_some() {
649 return Err(());
650 }
651 self.pos = saved_pos;
652 self.restore_top_sink(saved_sink);
653 break;
654 }
655 }
656 }
657 if count < min { Err(()) } else { Ok(()) }
658 }
659
660 fn run_rule_ref(&mut self, name: &str) -> Result<(), ()> {
661 let Some(&rule) = self.rules_by_name.get(name) else {
662 let candidates: Vec<&str> = self.rules_by_name.keys().copied().collect();
663 let base = format!("reference to undefined rule `{name}`");
664 let msg = match crate::BuiltinLevenshteinSuggester.enrich_unknown(name, &candidates) {
665 Some(hint) => format!("{base} ({hint})"),
666 None => base,
667 };
668 self.fatal_error = Some(
669 Diagnostic::error(codes::UNKNOWN_RULE, msg)
670 .with_span(Some(Span::new(self.pos, self.pos))),
671 );
672 return Err(());
673 };
674 let rule_name: &'g str = self
676 .rules_by_name
677 .keys()
678 .copied()
679 .find(|k| *k == name)
680 .expect("just found");
681 if self
684 .call_stack
685 .iter()
686 .any(|(n, p)| *n == rule_name && *p == self.pos)
687 {
688 self.fatal_error = Some(
689 Diagnostic::error(
690 codes::LEFT_RECURSION,
691 format!(
692 "left recursion detected: rule `{name}` re-entered at byte {}",
693 self.pos
694 ),
695 )
696 .with_span(Some(Span::new(self.pos, self.pos))),
697 );
698 return Err(());
699 }
700 self.call_stack.push((rule_name, self.pos));
701 let r = self.run_peg(rule);
702 self.call_stack.pop();
703 r
704 }
705
706 fn run_node(&mut self, variant: &str, body: &'g Peg) -> Result<(), ()> {
707 let start_pos = self.pos;
708 self.sink_stack.push(ActiveSink::Node(NodeSink::default()));
709 let body_result = self.run_peg(body);
710 let node_sink = match self.sink_stack.pop() {
711 Some(ActiveSink::Node(s)) => s,
712 _ => unreachable!("balanced push/pop of NodeSink"),
713 };
714 body_result?;
715 let end_pos = self.pos;
716 let mut keyed_children = node_sink.keyed_children;
722 for (_, entries) in &mut keyed_children {
723 entries.sort_by(|(a, _), (b, _)| a.cmp(b));
724 }
725
726 let tree = ParseTree {
727 variant: variant.to_string(),
728 fields: node_sink.fields,
729 children: node_sink.children,
730 keyed_children,
731 allows: Vec::new(),
732 span: Some(Span::new(start_pos, end_pos)),
733 };
734 self.contribute_tree(tree);
735 Ok(())
736 }
737
738 fn run_field(&mut self, name: &str, body: &'g Peg) -> Result<(), ()> {
739 self.sink_stack
740 .push(ActiveSink::Field(FieldSink::default()));
741 let body_result = self.run_peg(body);
742 let field_sink = match self.sink_stack.pop() {
743 Some(ActiveSink::Field(s)) => s,
744 _ => unreachable!("balanced push/pop of FieldSink"),
745 };
746 body_result?;
747 self.contribute_field(name, field_sink.productions);
748 Ok(())
749 }
750
751 fn run_keyed_entry(&mut self, slot: &str, key: &'g Peg, value: &'g Peg) -> Result<(), ()> {
760 let key_text = {
761 self.sink_stack
762 .push(ActiveSink::Field(FieldSink::default()));
763 let result = self.run_peg(key);
764 let sink = match self.sink_stack.pop() {
765 Some(ActiveSink::Field(s)) => s,
766 _ => unreachable!("balanced push/pop of FieldSink"),
767 };
768 result?;
769 if sink.productions.is_empty() {
778 self.expected("a text production for the keyed-entry key");
779 return Err(());
780 }
781 let mut text = String::new();
782 for production in &sink.productions {
783 match production {
784 Production::Text(t, _) => text.push_str(t),
785 Production::Tree(_) => {
788 self.expected("a text production for the keyed-entry key");
789 return Err(());
790 }
791 }
792 }
793 text
794 };
795
796 self.sink_stack
797 .push(ActiveSink::Field(FieldSink::default()));
798 let value_result = self.run_peg(value);
799 let value_sink = match self.sink_stack.pop() {
800 Some(ActiveSink::Field(s)) => s,
801 _ => unreachable!("balanced push/pop of FieldSink"),
802 };
803 value_result?;
804
805 let mut trees = value_sink.productions.into_iter().filter_map(|p| match p {
806 Production::Tree(t) => Some(t),
807 Production::Text(..) => None,
810 });
811 let Some(tree) = trees.next() else {
812 self.expected("a subtree production for the keyed-entry value");
813 return Err(());
814 };
815 if trees.next().is_some() {
816 self.expected("exactly one subtree for the keyed-entry value");
817 return Err(());
818 }
819
820 let Some(ActiveSink::Node(node_sink)) = self.sink_stack.last_mut() else {
821 return Ok(());
825 };
826 if let Some(existing) = node_sink.keyed_children.iter_mut().find(|(n, _)| n == slot) {
827 existing.1.push((key_text, tree));
828 } else {
829 node_sink
830 .keyed_children
831 .push((slot.to_string(), vec![(key_text, tree)]));
832 }
833 Ok(())
834 }
835
836 fn match_token(&mut self, pat: &str) -> Result<(), ()> {
841 if pat != "%ws" {
842 self.skip_ws();
843 }
844 let start = self.pos;
845 if pat == "%str" {
846 return match self.match_str() {
849 Some(decoded) => {
850 let end = self.pos;
851 self.contribute_text(decoded, Span::new(start, end));
852 Ok(())
853 }
854 None => {
855 self.expected(pat);
856 self.pos = start;
857 Err(())
858 }
859 };
860 }
861 if pat == "%str_raw" {
862 return match self.match_str() {
867 Some(_) => {
868 let end = self.pos;
869 let text = self.input[start..end].to_string();
870 self.contribute_text(text, Span::new(start, end));
871 Ok(())
872 }
873 None => {
874 self.expected(pat);
875 self.pos = start;
876 Err(())
877 }
878 };
879 }
880 let ok = if pat == "%ident" {
881 self.match_ident()
882 } else if pat == "%int" {
883 self.match_int()
884 } else if pat == "%ws" {
885 self.match_ws_required()
886 } else if let Some(word) = pat.strip_prefix("%kw:") {
887 self.match_keyword(word)
888 } else {
889 self.match_literal(pat)
890 };
891 if ok {
892 let end = self.pos;
893 let text = self.input[start..end].to_string();
894 self.contribute_text(text, Span::new(start, end));
895 Ok(())
896 } else {
897 self.expected(pat);
901 self.pos = start;
902 Err(())
903 }
904 }
905
906 fn skip_ws(&mut self) {
907 let bytes = self.input.as_bytes();
908 while let Some(&c) = bytes.get(self.pos) {
909 if matches!(c, b' ' | b'\t' | b'\n' | b'\r') {
910 self.pos += 1;
911 } else {
912 break;
913 }
914 }
915 }
916
917 fn match_ident(&mut self) -> bool {
918 let bytes = self.input.as_bytes();
919 match bytes.get(self.pos) {
920 Some(&c) if is_ident_start(c) => self.pos += 1,
921 _ => return false,
922 }
923 while let Some(&c) = bytes.get(self.pos) {
924 if is_ident_cont(c) {
925 self.pos += 1;
926 } else {
927 break;
928 }
929 }
930 true
931 }
932
933 fn match_int(&mut self) -> bool {
934 let bytes = self.input.as_bytes();
935 let mut p = self.pos;
936 if bytes.get(p) == Some(&b'-') {
937 p += 1;
938 }
939 let digit_start = p;
940 while let Some(&c) = bytes.get(p) {
941 if c.is_ascii_digit() {
942 p += 1;
943 } else {
944 break;
945 }
946 }
947 if p > digit_start {
948 self.pos = p;
949 true
950 } else {
951 false
952 }
953 }
954
955 fn match_str(&mut self) -> Option<String> {
959 let rest = &self.input[self.pos..];
960 let mut chars = rest.char_indices();
961 match chars.next() {
962 Some((_, '"')) => {}
963 _ => return None,
964 }
965 let mut out = String::new();
966 while let Some((i, c)) = chars.next() {
967 match c {
968 '"' => {
969 self.pos += i + 1;
970 return Some(out);
971 }
972 '\\' => match chars.next() {
973 Some((_, '"')) => out.push('"'),
974 Some((_, '\\')) => out.push('\\'),
975 Some((_, 'n')) => out.push('\n'),
976 Some((_, 't')) => out.push('\t'),
977 Some((_, 'r')) => out.push('\r'),
978 _ => return None,
979 },
980 other => out.push(other),
981 }
982 }
983 None
984 }
985
986 fn match_ws_required(&mut self) -> bool {
987 let start = self.pos;
988 let bytes = self.input.as_bytes();
989 while let Some(&c) = bytes.get(self.pos) {
990 if matches!(c, b' ' | b'\t' | b'\n' | b'\r') {
991 self.pos += 1;
992 } else {
993 break;
994 }
995 }
996 self.pos > start
997 }
998
999 fn match_literal(&mut self, s: &str) -> bool {
1000 let bytes = self.input.as_bytes();
1001 let end = self.pos + s.len();
1002 if end > bytes.len() {
1003 return false;
1004 }
1005 if &bytes[self.pos..end] != s.as_bytes() {
1006 return false;
1007 }
1008 self.pos = end;
1009 true
1010 }
1011
1012 fn match_keyword(&mut self, word: &str) -> bool {
1013 let saved = self.pos;
1014 if !self.match_literal(word) {
1015 return false;
1016 }
1017 if let Some(&next) = self.input.as_bytes().get(self.pos)
1019 && is_ident_cont(next)
1020 {
1021 self.pos = saved;
1022 return false;
1023 }
1024 true
1025 }
1026}
1027
1028fn is_ident_start(c: u8) -> bool {
1029 c.is_ascii_alphabetic() || c == b'_'
1030}
1031
1032fn is_ident_cont(c: u8) -> bool {
1033 c.is_ascii_alphanumeric() || c == b'_'
1034}
1035
1036use dsl_kit_core::IdGen;
1042
1043pub fn rule(ids: &IdGen, name: impl Into<String>, body: Peg) -> Peg {
1045 Peg::Rule {
1046 id: ids.node(),
1047 name: name.into(),
1048 body: Box::new(body),
1049 }
1050}
1051
1052pub fn seq(ids: &IdGen, items: Vec<Peg>) -> Peg {
1054 Peg::Seq {
1055 id: ids.node(),
1056 items,
1057 }
1058}
1059
1060pub fn choice(ids: &IdGen, alts: Vec<Peg>) -> Peg {
1062 Peg::Choice {
1063 id: ids.node(),
1064 alts,
1065 }
1066}
1067
1068pub fn repeat(ids: &IdGen, body: Peg, min: u32, max: Option<u32>) -> Peg {
1070 Peg::Repeat {
1071 id: ids.node(),
1072 body: Box::new(body),
1073 min,
1074 max,
1075 }
1076}
1077
1078pub fn rule_ref(ids: &IdGen, name: impl Into<String>) -> Peg {
1080 Peg::RuleRef {
1081 id: ids.node(),
1082 name: name.into(),
1083 }
1084}
1085
1086pub fn token(ids: &IdGen, pat: impl Into<String>) -> Peg {
1088 Peg::Token {
1089 id: ids.node(),
1090 pat: pat.into(),
1091 }
1092}
1093
1094pub fn node(ids: &IdGen, variant: impl Into<String>, body: Peg) -> Peg {
1096 Peg::Node {
1097 id: ids.node(),
1098 variant: variant.into(),
1099 body: Box::new(body),
1100 }
1101}
1102
1103pub fn field(ids: &IdGen, name: impl Into<String>, body: Peg) -> Peg {
1105 Peg::Field {
1106 id: ids.node(),
1107 name: name.into(),
1108 body: Box::new(body),
1109 }
1110}
1111
1112pub fn keyed_entry(ids: &IdGen, slot: impl Into<String>, key: Peg, value: Peg) -> Peg {
1117 Peg::KeyedEntry {
1118 id: ids.node(),
1119 slot: slot.into(),
1120 key: Box::new(key),
1121 value: Box::new(value),
1122 }
1123}
1124
1125#[cfg(test)]
1130mod tests {
1131 use super::*;
1132 use dsl_kit_core::IdGen;
1133 use dsl_kit_schema::DslSchema;
1134
1135 #[test]
1138 fn peg_schema_lists_all_variants() {
1139 let s = Peg::schema();
1140 assert_eq!(s.name, "Peg");
1141 let names: Vec<&str> = s.variants.iter().map(|v| v.name.as_str()).collect();
1142 assert_eq!(
1143 names,
1144 vec![
1145 "Rule",
1146 "Seq",
1147 "Choice",
1148 "Repeat",
1149 "RuleRef",
1150 "Token",
1151 "Node",
1152 "Field",
1153 "KeyedEntry"
1154 ]
1155 );
1156 let keyed = s.variant("KeyedEntry").unwrap();
1160 let keyed_children: Vec<&str> = keyed.children.iter().map(|c| c.name.as_str()).collect();
1161 assert_eq!(keyed_children, vec!["key", "value"]);
1162 let keyed_fields: Vec<&str> = keyed.fields.iter().map(|f| f.name.as_str()).collect();
1163 assert_eq!(keyed_fields, vec!["slot"]);
1164
1165 let repeat = s.variant("Repeat").unwrap();
1166 assert_eq!(repeat.children.len(), 1);
1168 assert_eq!(repeat.children[0].name, "body");
1169 let field_names: Vec<&str> = repeat.fields.iter().map(|f| f.name.as_str()).collect();
1170 assert!(field_names.contains(&"min"));
1171 assert!(field_names.contains(&"max"));
1172 }
1173
1174 fn parse_one(g: &Grammar, input: &str) -> Result<ParseTree, BuildError> {
1177 g.parse(input)
1178 }
1179
1180 fn one_rule_grammar(ids: &IdGen, start: &str, body: Peg) -> Grammar {
1181 Grammar::new(vec![rule(ids, start, body)], start)
1182 }
1183
1184 fn keyed_grammar(ids: &IdGen, key: Peg, value: Peg) -> Grammar {
1196 let entry = keyed_entry(ids, "entries", key, value);
1197 one_rule_grammar(
1198 ids,
1199 "start",
1200 node(
1201 ids,
1202 "Env",
1203 seq(
1204 ids,
1205 vec![
1206 token(ids, "{"),
1207 repeat(
1208 ids,
1209 seq(ids, vec![entry, repeat(ids, token(ids, ","), 0, Some(1))]),
1210 0,
1211 None,
1212 ),
1213 token(ids, "}"),
1214 ],
1215 ),
1216 ),
1217 )
1218 }
1219
1220 fn keyed_leaf_value(ids: &IdGen) -> Peg {
1222 seq(
1223 ids,
1224 vec![
1225 token(ids, ":"),
1226 node(ids, "Lit", field(ids, "value", token(ids, "%int"))),
1227 ],
1228 )
1229 }
1230
1231 #[test]
1232 fn keyed_entry_pairs_key_with_subtree_and_sorts() {
1233 let ids = IdGen::new();
1234 let g = keyed_grammar(&ids, token(&ids, "%ident"), keyed_leaf_value(&ids));
1235 let tree = parse_one(&g, "{ b: 2, a: 1 }").unwrap();
1236 let entries = tree.keyed_child_slot("entries").expect("slot bound");
1237 let keys: Vec<&str> = entries.iter().map(|(k, _)| k.as_str()).collect();
1238 assert_eq!(keys, ["a", "b"], "Node emission sorts by key");
1239 let values: Vec<&RawValue> = entries
1241 .iter()
1242 .map(|(_, t)| t.field("value").expect("leaf payload"))
1243 .collect();
1244 assert_eq!(values[0], &RawValue::Text("1".into()));
1245 assert_eq!(values[1], &RawValue::Text("2".into()));
1246 }
1247
1248 #[test]
1249 fn keyed_entry_accepts_an_empty_string_key() {
1250 let ids = IdGen::new();
1251 let g = keyed_grammar(&ids, token(&ids, "%str"), keyed_leaf_value(&ids));
1255 let tree = parse_one(&g, r#"{ "": 1 }"#).unwrap();
1256 let entries = tree.keyed_child_slot("entries").expect("slot bound");
1257 assert_eq!(entries.len(), 1);
1258 assert_eq!(entries[0].0, "");
1259 }
1260
1261 #[test]
1262 fn keyed_entry_rejects_a_key_half_that_produces_nothing() {
1263 let ids = IdGen::new();
1264 let g = keyed_grammar(
1270 &ids,
1271 repeat(&ids, token(&ids, "%ident"), 0, Some(1)),
1272 keyed_leaf_value(&ids),
1273 );
1274 let err = parse_one(&g, "{ : 1 }").unwrap_err();
1275 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1276 }
1277
1278 #[test]
1279 fn keyed_entry_rejects_a_tree_where_the_key_belongs() {
1280 let ids = IdGen::new();
1281 let g = keyed_grammar(
1282 &ids,
1283 node(&ids, "Lit", field(&ids, "value", token(&ids, "%int"))),
1284 keyed_leaf_value(&ids),
1285 );
1286 let err = parse_one(&g, "{ 1: 2 }").unwrap_err();
1287 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1288 }
1289
1290 #[test]
1291 fn keyed_entry_rejects_a_value_half_without_exactly_one_tree() {
1292 let ids = IdGen::new();
1293
1294 let none = keyed_grammar(
1296 &ids,
1297 token(&ids, "%ident"),
1298 seq(&ids, vec![token(&ids, ":"), token(&ids, "%int")]),
1299 );
1300 assert!(parse_one(&none, "{ a: 1 }").is_err());
1301
1302 let leaf = |ids: &IdGen| node(ids, "Lit", field(ids, "value", token(ids, "%int")));
1304 let two = keyed_grammar(
1305 &ids,
1306 token(&ids, "%ident"),
1307 seq(&ids, vec![token(&ids, ":"), leaf(&ids), leaf(&ids)]),
1308 );
1309 assert!(parse_one(&two, "{ a: 1 2 }").is_err());
1310 }
1311
1312 #[test]
1313 fn keyed_entry_survives_backtracking_without_leaking_entries() {
1314 let ids = IdGen::new();
1315 let entry_then_semi = seq(
1321 &ids,
1322 vec![
1323 keyed_entry(
1324 &ids,
1325 "entries",
1326 token(&ids, "%ident"),
1327 keyed_leaf_value(&ids),
1328 ),
1329 token(&ids, ";"),
1330 ],
1331 );
1332 let entry_then_end = seq(
1333 &ids,
1334 vec![
1335 keyed_entry(
1336 &ids,
1337 "entries",
1338 token(&ids, "%ident"),
1339 keyed_leaf_value(&ids),
1340 ),
1341 token(&ids, "}"),
1342 ],
1343 );
1344 let g = one_rule_grammar(
1345 &ids,
1346 "start",
1347 node(
1348 &ids,
1349 "Env",
1350 seq(
1351 &ids,
1352 vec![
1353 token(&ids, "{"),
1354 choice(&ids, vec![entry_then_semi, entry_then_end]),
1355 ],
1356 ),
1357 ),
1358 );
1359
1360 let tree = parse_one(&g, "{ a: 1 }").unwrap();
1361 let entries = tree.keyed_child_slot("entries").expect("slot bound");
1362 assert_eq!(
1363 entries.len(),
1364 1,
1365 "the failed alternative's entry must be rolled back, not kept: {entries:?}"
1366 );
1367 assert_eq!(entries[0].0, "a");
1368 }
1369
1370 #[test]
1371 fn keyed_entry_outside_a_node_drops_the_entry() {
1372 let ids = IdGen::new();
1373 let g = one_rule_grammar(
1378 &ids,
1379 "start",
1380 seq(
1381 &ids,
1382 vec![
1383 keyed_entry(
1384 &ids,
1385 "entries",
1386 token(&ids, "%ident"),
1387 keyed_leaf_value(&ids),
1388 ),
1389 node(&ids, "Env", token(&ids, "!")),
1390 ],
1391 ),
1392 );
1393 let tree = parse_one(&g, "a: 1 !").unwrap();
1394 assert_eq!(tree.variant, "Env");
1395 assert!(
1396 tree.keyed_children.is_empty(),
1397 "a keyed entry with no enclosing Node has nowhere to land: {:?}",
1398 tree.keyed_children
1399 );
1400 }
1401
1402 #[test]
1403 fn literal_token_and_wrap_node() {
1404 let ids = IdGen::new();
1405 let g = one_rule_grammar(
1407 &ids,
1408 "start",
1409 node(&ids, "K", field(&ids, "kw", token(&ids, "let"))),
1410 );
1411 let tree = parse_one(&g, "let").unwrap();
1412 assert_eq!(tree.variant, "K");
1413 assert_eq!(tree.fields.len(), 1);
1414 assert_eq!(tree.fields[0].0, "kw");
1415 match &tree.fields[0].1 {
1416 RawValue::Text(t) => assert_eq!(t, "let"),
1417 _ => panic!("expected text"),
1418 }
1419 }
1420
1421 #[test]
1422 fn keyword_guard_blocks_prefix_match() {
1423 let ids = IdGen::new();
1424 let g = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "%kw:let")));
1427 let err = parse_one(&g, "letme").unwrap_err();
1428 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1429
1430 let g2 = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "%kw:let")));
1432 assert!(parse_one(&g2, "let ").is_ok());
1433 }
1434
1435 #[test]
1436 fn plain_literal_has_no_word_boundary_guard() {
1437 let ids = IdGen::new();
1438 let g = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "a")));
1441 let err = parse_one(&g, "ab").unwrap_err();
1442 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1444 assert!(
1445 err.diagnostics[0].message.contains("trailing"),
1446 "{}",
1447 err.diagnostics[0].message
1448 );
1449 }
1450
1451 #[test]
1452 fn ident_and_int_classes() {
1453 let ids = IdGen::new();
1454 let g = one_rule_grammar(
1455 &ids,
1456 "s",
1457 node(&ids, "Var", field(&ids, "name", token(&ids, "%ident"))),
1458 );
1459 let t = parse_one(&g, "foo_bar1").unwrap();
1460 assert_eq!(t.variant, "Var");
1461 match &t.fields[0].1 {
1462 RawValue::Text(v) => assert_eq!(v, "foo_bar1"),
1463 _ => panic!(),
1464 }
1465
1466 let g2 = one_rule_grammar(
1467 &ids,
1468 "s",
1469 node(&ids, "N", field(&ids, "v", token(&ids, "%int"))),
1470 );
1471 let t2 = parse_one(&g2, "-42").unwrap();
1472 match &t2.fields[0].1 {
1473 RawValue::Text(v) => assert_eq!(v, "-42"),
1474 _ => panic!(),
1475 }
1476 }
1477
1478 #[test]
1481 fn implicit_ws_skip_before_tokens_and_at_boundaries() {
1482 let ids = IdGen::new();
1483 let body = seq(
1485 &ids,
1486 vec![
1487 field(&ids, "a", token(&ids, "%int")),
1488 field(&ids, "b", token(&ids, "%int")),
1489 ],
1490 );
1491 let g = one_rule_grammar(&ids, "s", node(&ids, "P", body));
1492 let t = parse_one(&g, " 3 7 ").unwrap();
1493 assert_eq!(t.fields.len(), 2);
1494 assert_eq!(t.fields[0].0, "a");
1495 assert_eq!(t.fields[1].0, "b");
1496 }
1497
1498 #[test]
1501 fn choice_commits_on_first_match() {
1502 let ids = IdGen::new();
1503 let alt_a = node(&ids, "A", token(&ids, "a"));
1507 let alt_ab = node(&ids, "B", token(&ids, "ab"));
1508 let g = one_rule_grammar(&ids, "s", choice(&ids, vec![alt_a, alt_ab]));
1509 let err = parse_one(&g, "ab").unwrap_err();
1510 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1513 assert!(
1514 err.diagnostics[0].message.contains("byte 1"),
1515 "{}",
1516 err.diagnostics[0].message
1517 );
1518 }
1519
1520 #[test]
1521 fn failed_alt_restores_position() {
1522 let ids = IdGen::new();
1523 let alt_abc = node(&ids, "L", token(&ids, "abc"));
1527 let alt_a = node(&ids, "S", token(&ids, "a"));
1528 let g = one_rule_grammar(&ids, "s", choice(&ids, vec![alt_abc, alt_a]));
1529 let err = parse_one(&g, "ab").unwrap_err();
1530 assert!(
1532 err.diagnostics[0].message.contains("byte 1"),
1533 "{}",
1534 err.diagnostics[0].message
1535 );
1536 }
1537
1538 #[test]
1539 fn repeat_is_greedy_and_no_backtrack_into_completed() {
1540 let ids = IdGen::new();
1541 let g = one_rule_grammar(
1546 &ids,
1547 "s",
1548 node(
1549 &ids,
1550 "N",
1551 seq(
1552 &ids,
1553 vec![repeat(&ids, token(&ids, "a"), 0, None), token(&ids, "a")],
1554 ),
1555 ),
1556 );
1557 let err = parse_one(&g, "aaa").unwrap_err();
1558 assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1559 }
1560
1561 #[test]
1562 fn repeat_min_enforced() {
1563 let ids = IdGen::new();
1564 let g = one_rule_grammar(
1565 &ids,
1566 "s",
1567 node(&ids, "N", repeat(&ids, token(&ids, "a"), 2, None)),
1568 );
1569 assert!(parse_one(&g, "a").is_err());
1571 assert!(parse_one(&g, "aa").is_ok());
1573 }
1574
1575 #[test]
1578 fn farthest_failure_carries_position_and_expected_set() {
1579 let ids = IdGen::new();
1580 let g = one_rule_grammar(
1585 &ids,
1586 "s",
1587 node(
1588 &ids,
1589 "N",
1590 seq(
1591 &ids,
1592 vec![token(&ids, "let"), token(&ids, "x"), token(&ids, "=")],
1593 ),
1594 ),
1595 );
1596 let err = parse_one(&g, "let x !").unwrap_err();
1597 let msg = &err.diagnostics[0].message;
1598 assert!(msg.contains("byte 6"), "{msg}");
1599 assert!(msg.contains("`=`"), "{msg}");
1600 }
1601
1602 #[test]
1605 fn left_recursion_is_detected_at_runtime() {
1606 let ids = IdGen::new();
1607 let r = rule(
1610 &ids,
1611 "r",
1612 seq(&ids, vec![rule_ref(&ids, "r"), token(&ids, "a")]),
1613 );
1614 let g = Grammar::new(vec![r], "r");
1615 let err = g.parse("aaa").unwrap_err();
1616 assert_eq!(err.diagnostics[0].code, codes::LEFT_RECURSION);
1617 }
1618
1619 #[test]
1620 fn unknown_rule_ref_is_diagnosed() {
1621 let ids = IdGen::new();
1622 let r = rule(&ids, "start", rule_ref(&ids, "missing"));
1623 let g = Grammar::new(vec![r], "start");
1624 let err = g.parse("").unwrap_err();
1625 assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1626 }
1627
1628 #[test]
1629 fn unknown_rule_ref_suggests_declared_rule() {
1630 let ids = IdGen::new();
1633 let start = rule(&ids, "start", rule_ref(&ids, "helo"));
1634 let target = rule(&ids, "hello", token(&ids, "hi"));
1635 let g = Grammar::new(vec![start, target], "start");
1636 let err = g.parse("hi").unwrap_err();
1637 assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1638 assert!(
1639 err.diagnostics[0].message.contains("did you mean")
1640 && err.diagnostics[0].message.contains("hello"),
1641 "expected hint, got: {}",
1642 err.diagnostics[0].message
1643 );
1644 }
1645
1646 #[test]
1647 fn unknown_start_rule_is_diagnosed() {
1648 let ids = IdGen::new();
1649 let r = rule(&ids, "other", token(&ids, "x"));
1650 let g = Grammar::new(vec![r], "start");
1651 let err = g.parse("x").unwrap_err();
1652 assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1653 }
1654
1655 #[test]
1656 fn unknown_start_rule_suggests_declared_rule() {
1657 let ids = IdGen::new();
1658 let r = rule(&ids, "start", token(&ids, "x"));
1659 let g = Grammar::new(vec![r], "strat");
1660 let err = g.parse("x").unwrap_err();
1661 assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1662 assert!(
1663 err.diagnostics[0].message.contains("did you mean")
1664 && err.diagnostics[0].message.contains("start"),
1665 "expected hint, got: {}",
1666 err.diagnostics[0].message
1667 );
1668 }
1669
1670 #[test]
1671 fn nullable_repeat_body_below_min_is_rejected() {
1672 let ids = IdGen::new();
1673 let empty_body = seq(&ids, vec![]);
1676 let g = one_rule_grammar(
1677 &ids,
1678 "s",
1679 node(&ids, "N", repeat(&ids, empty_body, 1, None)),
1680 );
1681 let err = g.parse("").unwrap_err();
1682 assert_eq!(err.diagnostics[0].code, codes::NULLABLE_REPEAT);
1683 }
1684}