1use std::cell::Cell;
30use std::collections::HashMap;
31
32use crate::peg::{Grammar, Peg};
33use crate::{BuildError, Diagnostic};
34
35pub mod codes {
37 pub const NO_FINITE_DERIVATION: &str = "dsl_kit::example_gen::no_finite_derivation";
40 pub const UNKNOWN_RULE: &str = "dsl_kit::example_gen::unknown_rule";
42 pub const UNKNOWN_TOKEN: &str = "dsl_kit::example_gen::unknown_token";
46}
47
48pub const COMPOSITE_DEPTH: u32 = 2;
52
53#[derive(Debug, Clone)]
55pub struct RuleExample {
56 pub rule: String,
58 pub text: String,
60}
61
62#[derive(Debug, Clone)]
64pub struct GrammarExamples {
65 pub per_rule: Vec<RuleExample>,
69 pub composite: String,
72}
73
74pub fn examples_from_grammar(grammar: &Grammar) -> Result<GrammarExamples, BuildError> {
80 let synth = Synth::prepare(grammar)?;
81
82 let mut underivable = Vec::new();
83 for (name, _) in &synth.rules_in_order {
84 if synth.rule_cost(name) == INFINITE {
85 underivable.push(Diagnostic::error(
86 codes::NO_FINITE_DERIVATION,
87 format!("rule `{name}` has no finite derivation — no example input exists"),
88 ));
89 }
90 }
91 if !underivable.is_empty() {
92 return Err(BuildError::new(underivable));
93 }
94
95 let mut per_rule = Vec::new();
96 for (name, body) in &synth.rules_in_order {
97 if *name == grammar.start {
98 continue;
99 }
100 if is_reserved_rule(name) {
105 continue;
106 }
107 let mut tokens = Vec::new();
108 synth.emit(body, 0, &mut tokens)?;
109 per_rule.push(RuleExample {
110 rule: name.clone(),
111 text: render(&tokens),
112 });
113 }
114
115 let start_body = synth.rule_body(&grammar.start)?;
116 let mut tokens = Vec::new();
117 synth.emit(start_body, COMPOSITE_DEPTH, &mut tokens)?;
118 let composite = render(&tokens);
119
120 Ok(GrammarExamples {
121 per_rule,
122 composite,
123 })
124}
125
126const INFINITE: u64 = u64::MAX;
128
129struct Synth<'g> {
130 by_name: HashMap<&'g str, &'g Peg>,
132 rules_in_order: Vec<(String, &'g Peg)>,
134 costs: HashMap<String, u64>,
136 key_seq: Cell<u32>,
142}
143
144impl<'g> Synth<'g> {
145 fn prepare(grammar: &'g Grammar) -> Result<Self, BuildError> {
146 let mut by_name = HashMap::new();
147 let mut rules_in_order = Vec::new();
148 for r in &grammar.rules {
149 if let Peg::Rule { name, body, .. } = r {
150 by_name.insert(name.as_str(), body.as_ref());
151 rules_in_order.push((name.clone(), body.as_ref()));
152 }
153 }
154
155 let mut costs: HashMap<String, u64> = rules_in_order
159 .iter()
160 .map(|(n, _)| (n.clone(), INFINITE))
161 .collect();
162 loop {
163 let mut changed = false;
164 for (name, body) in &rules_in_order {
165 let c = peg_cost(body, &costs);
166 if c < costs[name] {
167 costs.insert(name.clone(), c);
168 changed = true;
169 }
170 }
171 if !changed {
172 break;
173 }
174 }
175
176 Ok(Self {
177 by_name,
178 rules_in_order,
179 costs,
180 key_seq: Cell::new(0),
181 })
182 }
183
184 fn rule_cost(&self, name: &str) -> u64 {
185 self.costs.get(name).copied().unwrap_or(INFINITE)
186 }
187
188 fn rule_body(&self, name: &str) -> Result<&'g Peg, BuildError> {
189 self.by_name.get(name).copied().ok_or_else(|| {
190 BuildError::single(Diagnostic::error(
191 codes::UNKNOWN_RULE,
192 format!("reference to undefined rule `{name}`"),
193 ))
194 })
195 }
196
197 fn emit(&self, peg: &Peg, rich_depth: u32, out: &mut Vec<String>) -> Result<(), BuildError> {
201 match peg {
202 Peg::Token { pat, .. } => {
203 out.push(token_input(pat)?);
204 Ok(())
205 }
206 Peg::Seq { items, .. } => {
207 for item in items {
208 self.emit(item, rich_depth, out)?;
209 }
210 Ok(())
211 }
212 Peg::Choice { alts, .. } => {
213 let arm = self.pick_arm(alts, rich_depth)?;
214 self.emit(arm, rich_depth, out)
215 }
216 Peg::Repeat { body, min, max, .. } => {
217 let count = if rich_depth > 0 {
218 (*min).max(2.min(max.unwrap_or(2)))
219 } else {
220 *min
221 };
222 for _ in 0..count {
223 self.emit(body, rich_depth, out)?;
224 }
225 Ok(())
226 }
227 Peg::RuleRef { name, .. } => {
228 let body = self.rule_body(name)?;
229 self.emit(body, rich_depth.saturating_sub(1), out)
230 }
231 Peg::Rule { body, .. } | Peg::Node { body, .. } | Peg::Field { body, .. } => {
232 self.emit(body, rich_depth, out)
233 }
234 Peg::KeyedEntry { key, value, .. } => {
246 let n = self.key_seq.get() + 1;
247 self.key_seq.set(n);
248 self.emit_key(key, n, rich_depth, out)?;
249 self.emit(value, rich_depth, out)
250 }
251 }
252 }
253
254 fn emit_key(
263 &self,
264 peg: &Peg,
265 n: u32,
266 rich_depth: u32,
267 out: &mut Vec<String>,
268 ) -> Result<(), BuildError> {
269 match peg {
270 Peg::Token { pat, .. } => {
271 out.push(keyed_token_input(pat, n)?);
272 Ok(())
273 }
274 Peg::Seq { items, .. } => {
275 for item in items {
276 self.emit_key(item, n, rich_depth, out)?;
277 }
278 Ok(())
279 }
280 Peg::Choice { alts, .. } => {
281 let arm = self.pick_arm(alts, rich_depth)?;
282 self.emit_key(arm, n, rich_depth, out)
283 }
284 other => self.emit(other, rich_depth, out),
285 }
286 }
287
288 fn pick_arm<'p>(&self, alts: &'p [Peg], rich_depth: u32) -> Result<&'p Peg, BuildError> {
297 let finite = alts
298 .iter()
299 .filter(|a| !is_reserved_arm(a))
300 .map(|a| (a, peg_cost(a, &self.costs)))
301 .filter(|(_, c)| *c != INFINITE);
302 let picked = if rich_depth > 0 {
303 finite.max_by_key(|(_, c)| *c)
304 } else {
305 finite.min_by_key(|(_, c)| *c)
306 };
307 picked.map(|(a, _)| a).ok_or_else(|| {
308 BuildError::single(Diagnostic::error(
309 codes::NO_FINITE_DERIVATION,
310 "choice has no finite alternative".to_string(),
311 ))
312 })
313 }
314}
315
316fn is_reserved_rule(name: &str) -> bool {
319 name == crate::import::IMPORT_VARIANT || name == crate::allow::ALLOW_VARIANT
320}
321
322fn is_reserved_arm(peg: &Peg) -> bool {
325 match peg {
326 Peg::RuleRef { name, .. } => is_reserved_rule(name),
327 Peg::Node { variant, .. } => is_reserved_rule(variant),
328 _ => false,
329 }
330}
331
332fn peg_cost(peg: &Peg, costs: &HashMap<String, u64>) -> u64 {
335 match peg {
336 Peg::Token { .. } => 1,
337 Peg::Seq { items, .. } => items
338 .iter()
339 .try_fold(0u64, |acc, i| {
340 let c = peg_cost(i, costs);
341 if c == INFINITE {
342 None
343 } else {
344 Some(acc.saturating_add(c))
345 }
346 })
347 .unwrap_or(INFINITE),
348 Peg::Choice { alts, .. } => alts
349 .iter()
350 .map(|a| peg_cost(a, costs))
351 .min()
352 .unwrap_or(INFINITE),
353 Peg::Repeat { body, min, .. } => {
354 if *min == 0 {
355 0
356 } else {
357 let c = peg_cost(body, costs);
358 if c == INFINITE {
359 INFINITE
360 } else {
361 c.saturating_mul(u64::from(*min))
362 }
363 }
364 }
365 Peg::RuleRef { name, .. } => costs.get(name).copied().unwrap_or(INFINITE),
366 Peg::Rule { body, .. } | Peg::Node { body, .. } | Peg::Field { body, .. } => {
367 peg_cost(body, costs)
368 }
369 Peg::KeyedEntry { key, value, .. } => {
372 let (k, v) = (peg_cost(key, costs), peg_cost(value, costs));
373 if k == INFINITE || v == INFINITE {
374 INFINITE
375 } else {
376 k.saturating_add(v)
377 }
378 }
379 }
380}
381
382fn keyed_token_input(pat: &str, n: u32) -> Result<String, BuildError> {
388 match pat {
389 "%str" | "%str_raw" => Ok(format!("\"key{n}\"")),
390 "%ident" => Ok(format!("key{n}")),
391 other => token_input(other),
392 }
393}
394
395fn token_input(pat: &str) -> Result<String, BuildError> {
404 if let Some(kw) = pat.strip_prefix("%kw:") {
405 return Ok(kw.to_string());
406 }
407 Ok(match pat {
408 "%int" => "1".to_string(),
409 "%str" | "%str_raw" => "\"example\"".to_string(),
410 "%ident" => "x".to_string(),
411 "%ws" => " ".to_string(),
412 unknown if unknown.starts_with('%') => {
413 return Err(BuildError::single(Diagnostic::error(
414 codes::UNKNOWN_TOKEN,
415 format!("token pattern `{unknown}` has no example input text"),
416 )));
417 }
418 literal => literal.to_string(),
419 })
420}
421
422fn render(tokens: &[String]) -> String {
426 let mut out = String::new();
427 for t in tokens {
428 let tight_before = matches!(t.as_str(), "," | ")" | "]" | "}" | ":" | "(");
429 let tight_after_prev = out.ends_with('(') || out.ends_with('[') || out.ends_with('{');
430 if !out.is_empty() && !tight_before && !tight_after_prev {
431 out.push(' ');
432 }
433 out.push_str(t);
434 }
435 out
436}
437
438#[cfg(test)]
439mod tests {
440 use super::*;
441 use crate::check_conformance;
442 use crate::schema_gen::checked_grammar_from_schema;
443 use dsl_kit_core::IdGen;
444 use dsl_kit_schema::{
445 ChildSchema, ChildValueShape, FieldSchema, Multiplicity, NodeSchema, VariantSchema,
446 };
447
448 fn demo_schema() -> NodeSchema {
451 NodeSchema {
452 name: "Expr".into(),
453 variants: vec![
454 VariantSchema {
455 name: "Lit".into(),
456 fields: vec![FieldSchema {
457 name: "value".into(),
458 ty: "i64".into(),
459 optional: false,
460 }],
461 children: vec![],
462 },
463 VariantSchema {
464 name: "Name".into(),
465 fields: vec![
466 FieldSchema {
467 name: "text".into(),
468 ty: "String".into(),
469 optional: false,
470 },
471 FieldSchema {
472 name: "quoted".into(),
473 ty: "bool".into(),
474 optional: false,
475 },
476 ],
477 children: vec![],
478 },
479 VariantSchema {
480 name: "Add".into(),
481 fields: vec![],
482 children: vec![
483 ChildSchema {
484 name: "lhs".into(),
485 multiplicity: Multiplicity::One,
486 value_shape: ChildValueShape::Recursive,
487 scalar_shorthands: vec![],
488 non_empty: false,
489 },
490 ChildSchema {
491 name: "rhs".into(),
492 multiplicity: Multiplicity::One,
493 value_shape: ChildValueShape::Recursive,
494 scalar_shorthands: vec![],
495 non_empty: false,
496 },
497 ],
498 },
499 VariantSchema {
500 name: "Neg".into(),
501 fields: vec![],
502 children: vec![ChildSchema {
503 name: "body".into(),
504 multiplicity: Multiplicity::Optional,
505 value_shape: ChildValueShape::Recursive,
506 scalar_shorthands: vec![],
507 non_empty: false,
508 }],
509 },
510 VariantSchema {
511 name: "List".into(),
512 fields: vec![],
513 children: vec![ChildSchema {
514 name: "items".into(),
515 multiplicity: Multiplicity::Many,
516 value_shape: ChildValueShape::Recursive,
517 scalar_shorthands: vec![],
518 non_empty: false,
519 }],
520 },
521 VariantSchema {
522 name: "Env".into(),
523 fields: vec![],
524 children: vec![ChildSchema {
525 name: "entries".into(),
526 multiplicity: Multiplicity::Map,
527 value_shape: ChildValueShape::Recursive,
528 scalar_shorthands: vec![],
529 non_empty: false,
530 }],
531 },
532 VariantSchema {
533 name: "Unit".into(),
534 fields: vec![],
535 children: vec![],
536 },
537 ],
538 }
539 }
540
541 fn demo_examples() -> (Grammar, GrammarExamples) {
542 let g = checked_grammar_from_schema(&demo_schema(), &IdGen::new())
543 .expect("demo schema generates");
544 let ex = examples_from_grammar(&g).expect("examples synthesize");
545 (g, ex)
546 }
547
548 #[test]
549 fn every_per_rule_example_parses_as_its_own_variant() {
550 let (g, ex) = demo_examples();
551 assert_eq!(ex.per_rule.len(), 7, "one example per variant");
552 for e in &ex.per_rule {
553 let tree = g.parse(&e.text).unwrap_or_else(|err| {
554 panic!(
555 "example for `{}` failed to parse: {:?}\n text: {}",
556 e.rule, err.diagnostics, e.text
557 )
558 });
559 assert_eq!(tree.variant, e.rule, "example enters at its own variant");
560 let diags = check_conformance(&tree, &demo_schema());
561 assert!(
562 diags.is_empty(),
563 "conformance clean for {}: {diags:?}",
564 e.rule
565 );
566 }
567 }
568
569 #[test]
570 fn minimal_examples_have_the_expected_spellings() {
571 let (_, ex) = demo_examples();
572 let by_rule: HashMap<&str, &str> = ex
573 .per_rule
574 .iter()
575 .map(|e| (e.rule.as_str(), e.text.as_str()))
576 .collect();
577 assert_eq!(by_rule["Lit"], "Lit(value: 1)");
578 assert_eq!(by_rule["Name"], "Name(text: \"example\", quoted: true)");
579 assert_eq!(
580 by_rule["Add"], "Add(lhs: Unit(), rhs: Unit())",
581 "nested slots fill with the cheapest variant"
582 );
583 assert_eq!(
584 by_rule["Neg"], "Neg(body: none)",
585 "Optional minimal = absent"
586 );
587 assert_eq!(
588 by_rule["List"], "List(items: [])",
589 "Many minimal = empty list"
590 );
591 assert_eq!(
592 by_rule["Env"], "Env(entries: {})",
593 "Map minimal = empty map, braces tight like the empty list"
594 );
595 assert_eq!(by_rule["Unit"], "Unit()");
596 }
597
598 #[test]
604 fn rich_keyed_map_example_uses_distinct_keys() {
605 let map_only = NodeSchema {
606 name: "Cfg".into(),
607 variants: vec![
608 VariantSchema {
609 name: "Env".into(),
610 fields: vec![],
611 children: vec![ChildSchema {
612 name: "entries".into(),
613 multiplicity: Multiplicity::Map,
614 value_shape: ChildValueShape::Recursive,
615 scalar_shorthands: vec![],
616 non_empty: false,
617 }],
618 },
619 VariantSchema {
620 name: "Unit".into(),
621 fields: vec![],
622 children: vec![],
623 },
624 ],
625 };
626 let g = checked_grammar_from_schema(&map_only, &IdGen::new()).expect("generates");
627 let ex = examples_from_grammar(&g).expect("synthesizes");
628
629 let tree = g.parse(&ex.composite).unwrap_or_else(|err| {
630 panic!(
631 "composite failed to parse: {:?}\n text: {}",
632 err.diagnostics, ex.composite
633 )
634 });
635 let entries = tree
636 .keyed_child_slot("entries")
637 .expect("rich mode fills the keyed slot");
638 assert!(
639 entries.len() >= 2,
640 "rich mode should expand the map: {}",
641 ex.composite
642 );
643 let diags = check_conformance(&tree, &map_only);
644 assert!(
645 diags.is_empty(),
646 "synthesized example must conform: {diags:?}\n text: {}",
647 ex.composite
648 );
649 }
650
651 #[test]
655 fn keyed_entry_inherits_an_underivable_value() {
656 let ids = IdGen::new();
657 use crate::peg::{keyed_entry, node, rule, rule_ref, token};
660 let entry = keyed_entry(&ids, "entries", token(&ids, "%ident"), rule_ref(&ids, "s"));
661 let g = Grammar::new(vec![rule(&ids, "s", node(&ids, "N", entry))], "s");
662 let err = examples_from_grammar(&g).expect_err("no finite derivation exists");
663 assert!(
664 err.diagnostics
665 .iter()
666 .any(|d| d.code == codes::NO_FINITE_DERIVATION),
667 "expected NO_FINITE_DERIVATION; got {:?}",
668 err.diagnostics
669 .iter()
670 .map(|d| d.code.as_str())
671 .collect::<Vec<_>>()
672 );
673 }
674
675 #[test]
676 fn composite_parses_and_shows_nesting() {
677 let (g, ex) = demo_examples();
678 let tree = g.parse(&ex.composite).unwrap_or_else(|err| {
679 panic!(
680 "composite failed to parse: {:?}\n text: {}",
681 err.diagnostics, ex.composite
682 )
683 });
684 assert!(check_conformance(&tree, &demo_schema()).is_empty());
685 assert!(
688 !tree.children.is_empty(),
689 "composite has child structure: {}",
690 ex.composite
691 );
692 }
693
694 #[test]
699 fn str_raw_token_renders_as_a_string_literal() {
700 let schema = NodeSchema {
701 name: "Meta".into(),
702 variants: vec![VariantSchema {
703 name: "Row".into(),
704 fields: vec![
705 FieldSchema::required("name", "String"),
706 FieldSchema::optional("tags", "Vec<String>"),
707 ],
708 children: vec![],
709 }],
710 };
711 let g = checked_grammar_from_schema(&schema, &IdGen::new()).unwrap();
712 let ex = examples_from_grammar(&g).unwrap();
713 assert_eq!(
715 ex.composite,
716 "Row(name: \"example\", tags: [\"example\", \"example\", \"example\"])"
717 );
718 for text in ex.per_rule.iter().map(|e| &e.text).chain([&ex.composite]) {
719 assert!(!text.contains("%str_raw"), "{text}");
720 let tree = g.parse(text).unwrap_or_else(|e| panic!("`{text}`: {e:?}"));
721 assert!(check_conformance(&tree, &schema).is_empty(), "{text}");
722 }
723 }
724
725 #[test]
729 fn unknown_token_pattern_is_a_diagnostic() {
730 use crate::peg::{Grammar, field, node, rule, token};
731 let ids = IdGen::new();
732 let g = Grammar::new(
733 vec![rule(
734 &ids,
735 "Lit",
736 node(&ids, "Lit", field(&ids, "value", token(&ids, "%float"))),
737 )],
738 "Lit",
739 );
740 let err = examples_from_grammar(&g).expect_err("unknown token");
741 assert_eq!(err.diagnostics.len(), 1);
742 assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_TOKEN);
743 assert!(err.diagnostics[0].message.contains("%float"));
744 }
745
746 #[test]
747 fn underivable_rules_fail_loudly_with_the_full_list() {
748 let schema = NodeSchema {
751 name: "Loop".into(),
752 variants: vec![VariantSchema {
753 name: "Rec".into(),
754 fields: vec![],
755 children: vec![ChildSchema {
756 name: "inner".into(),
757 multiplicity: Multiplicity::One,
758 value_shape: ChildValueShape::Recursive,
759 scalar_shorthands: vec![],
760 non_empty: false,
761 }],
762 }],
763 };
764 let g = crate::schema_gen::grammar_from_schema(&schema, &IdGen::new())
765 .expect("generation itself succeeds");
766 let err = examples_from_grammar(&g).expect_err("no finite derivation");
767 assert!(
768 err.diagnostics
769 .iter()
770 .all(|d| d.code == codes::NO_FINITE_DERIVATION),
771 "{:?}",
772 err.diagnostics
773 );
774 assert_eq!(err.diagnostics.len(), 2);
776 }
777}