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}
43
44pub const COMPOSITE_DEPTH: u32 = 2;
48
49#[derive(Debug, Clone)]
51pub struct RuleExample {
52 pub rule: String,
54 pub text: String,
56}
57
58#[derive(Debug, Clone)]
60pub struct GrammarExamples {
61 pub per_rule: Vec<RuleExample>,
65 pub composite: String,
68}
69
70pub fn examples_from_grammar(grammar: &Grammar) -> Result<GrammarExamples, BuildError> {
76 let synth = Synth::prepare(grammar)?;
77
78 let mut underivable = Vec::new();
79 for (name, _) in &synth.rules_in_order {
80 if synth.rule_cost(name) == INFINITE {
81 underivable.push(Diagnostic::error(
82 codes::NO_FINITE_DERIVATION,
83 format!("rule `{name}` has no finite derivation — no example input exists"),
84 ));
85 }
86 }
87 if !underivable.is_empty() {
88 return Err(BuildError::new(underivable));
89 }
90
91 let mut per_rule = Vec::new();
92 for (name, body) in &synth.rules_in_order {
93 if *name == grammar.start {
94 continue;
95 }
96 if is_reserved_rule(name) {
101 continue;
102 }
103 let mut tokens = Vec::new();
104 synth.emit(body, 0, &mut tokens)?;
105 per_rule.push(RuleExample {
106 rule: name.clone(),
107 text: render(&tokens),
108 });
109 }
110
111 let start_body = synth.rule_body(&grammar.start)?;
112 let mut tokens = Vec::new();
113 synth.emit(start_body, COMPOSITE_DEPTH, &mut tokens)?;
114 let composite = render(&tokens);
115
116 Ok(GrammarExamples {
117 per_rule,
118 composite,
119 })
120}
121
122const INFINITE: u64 = u64::MAX;
124
125struct Synth<'g> {
126 by_name: HashMap<&'g str, &'g Peg>,
128 rules_in_order: Vec<(String, &'g Peg)>,
130 costs: HashMap<String, u64>,
132 key_seq: Cell<u32>,
138}
139
140impl<'g> Synth<'g> {
141 fn prepare(grammar: &'g Grammar) -> Result<Self, BuildError> {
142 let mut by_name = HashMap::new();
143 let mut rules_in_order = Vec::new();
144 for r in &grammar.rules {
145 if let Peg::Rule { name, body, .. } = r {
146 by_name.insert(name.as_str(), body.as_ref());
147 rules_in_order.push((name.clone(), body.as_ref()));
148 }
149 }
150
151 let mut costs: HashMap<String, u64> = rules_in_order
155 .iter()
156 .map(|(n, _)| (n.clone(), INFINITE))
157 .collect();
158 loop {
159 let mut changed = false;
160 for (name, body) in &rules_in_order {
161 let c = peg_cost(body, &costs);
162 if c < costs[name] {
163 costs.insert(name.clone(), c);
164 changed = true;
165 }
166 }
167 if !changed {
168 break;
169 }
170 }
171
172 Ok(Self {
173 by_name,
174 rules_in_order,
175 costs,
176 key_seq: Cell::new(0),
177 })
178 }
179
180 fn rule_cost(&self, name: &str) -> u64 {
181 self.costs.get(name).copied().unwrap_or(INFINITE)
182 }
183
184 fn rule_body(&self, name: &str) -> Result<&'g Peg, BuildError> {
185 self.by_name.get(name).copied().ok_or_else(|| {
186 BuildError::single(Diagnostic::error(
187 codes::UNKNOWN_RULE,
188 format!("reference to undefined rule `{name}`"),
189 ))
190 })
191 }
192
193 fn emit(&self, peg: &Peg, rich_depth: u32, out: &mut Vec<String>) -> Result<(), BuildError> {
197 match peg {
198 Peg::Token { pat, .. } => {
199 out.push(token_input(pat));
200 Ok(())
201 }
202 Peg::Seq { items, .. } => {
203 for item in items {
204 self.emit(item, rich_depth, out)?;
205 }
206 Ok(())
207 }
208 Peg::Choice { alts, .. } => {
209 let arm = self.pick_arm(alts, rich_depth)?;
210 self.emit(arm, rich_depth, out)
211 }
212 Peg::Repeat { body, min, max, .. } => {
213 let count = if rich_depth > 0 {
214 (*min).max(2.min(max.unwrap_or(2)))
215 } else {
216 *min
217 };
218 for _ in 0..count {
219 self.emit(body, rich_depth, out)?;
220 }
221 Ok(())
222 }
223 Peg::RuleRef { name, .. } => {
224 let body = self.rule_body(name)?;
225 self.emit(body, rich_depth.saturating_sub(1), out)
226 }
227 Peg::Rule { body, .. } | Peg::Node { body, .. } | Peg::Field { body, .. } => {
228 self.emit(body, rich_depth, out)
229 }
230 Peg::KeyedEntry { key, value, .. } => {
242 let n = self.key_seq.get() + 1;
243 self.key_seq.set(n);
244 self.emit_key(key, n, rich_depth, out)?;
245 self.emit(value, rich_depth, out)
246 }
247 }
248 }
249
250 fn emit_key(
259 &self,
260 peg: &Peg,
261 n: u32,
262 rich_depth: u32,
263 out: &mut Vec<String>,
264 ) -> Result<(), BuildError> {
265 match peg {
266 Peg::Token { pat, .. } => {
267 out.push(keyed_token_input(pat, n));
268 Ok(())
269 }
270 Peg::Seq { items, .. } => {
271 for item in items {
272 self.emit_key(item, n, rich_depth, out)?;
273 }
274 Ok(())
275 }
276 Peg::Choice { alts, .. } => {
277 let arm = self.pick_arm(alts, rich_depth)?;
278 self.emit_key(arm, n, rich_depth, out)
279 }
280 other => self.emit(other, rich_depth, out),
281 }
282 }
283
284 fn pick_arm<'p>(&self, alts: &'p [Peg], rich_depth: u32) -> Result<&'p Peg, BuildError> {
293 let finite = alts
294 .iter()
295 .filter(|a| !is_reserved_arm(a))
296 .map(|a| (a, peg_cost(a, &self.costs)))
297 .filter(|(_, c)| *c != INFINITE);
298 let picked = if rich_depth > 0 {
299 finite.max_by_key(|(_, c)| *c)
300 } else {
301 finite.min_by_key(|(_, c)| *c)
302 };
303 picked.map(|(a, _)| a).ok_or_else(|| {
304 BuildError::single(Diagnostic::error(
305 codes::NO_FINITE_DERIVATION,
306 "choice has no finite alternative".to_string(),
307 ))
308 })
309 }
310}
311
312fn is_reserved_rule(name: &str) -> bool {
315 name == crate::import::IMPORT_VARIANT || name == crate::allow::ALLOW_VARIANT
316}
317
318fn is_reserved_arm(peg: &Peg) -> bool {
321 match peg {
322 Peg::RuleRef { name, .. } => is_reserved_rule(name),
323 Peg::Node { variant, .. } => is_reserved_rule(variant),
324 _ => false,
325 }
326}
327
328fn peg_cost(peg: &Peg, costs: &HashMap<String, u64>) -> u64 {
331 match peg {
332 Peg::Token { .. } => 1,
333 Peg::Seq { items, .. } => items
334 .iter()
335 .try_fold(0u64, |acc, i| {
336 let c = peg_cost(i, costs);
337 if c == INFINITE {
338 None
339 } else {
340 Some(acc.saturating_add(c))
341 }
342 })
343 .unwrap_or(INFINITE),
344 Peg::Choice { alts, .. } => alts
345 .iter()
346 .map(|a| peg_cost(a, costs))
347 .min()
348 .unwrap_or(INFINITE),
349 Peg::Repeat { body, min, .. } => {
350 if *min == 0 {
351 0
352 } else {
353 let c = peg_cost(body, costs);
354 if c == INFINITE {
355 INFINITE
356 } else {
357 c.saturating_mul(u64::from(*min))
358 }
359 }
360 }
361 Peg::RuleRef { name, .. } => costs.get(name).copied().unwrap_or(INFINITE),
362 Peg::Rule { body, .. } | Peg::Node { body, .. } | Peg::Field { body, .. } => {
363 peg_cost(body, costs)
364 }
365 Peg::KeyedEntry { key, value, .. } => {
368 let (k, v) = (peg_cost(key, costs), peg_cost(value, costs));
369 if k == INFINITE || v == INFINITE {
370 INFINITE
371 } else {
372 k.saturating_add(v)
373 }
374 }
375 }
376}
377
378fn keyed_token_input(pat: &str, n: u32) -> String {
384 match pat {
385 "%str" => format!("\"key{n}\""),
386 "%ident" => format!("key{n}"),
387 other => token_input(other),
388 }
389}
390
391fn token_input(pat: &str) -> String {
393 if let Some(kw) = pat.strip_prefix("%kw:") {
394 return kw.to_string();
395 }
396 match pat {
397 "%int" => "1".to_string(),
398 "%str" => "\"example\"".to_string(),
399 "%ident" => "x".to_string(),
400 "%ws" => " ".to_string(),
401 literal => literal.to_string(),
402 }
403}
404
405fn render(tokens: &[String]) -> String {
409 let mut out = String::new();
410 for t in tokens {
411 let tight_before = matches!(t.as_str(), "," | ")" | "]" | "}" | ":" | "(");
412 let tight_after_prev = out.ends_with('(') || out.ends_with('[') || out.ends_with('{');
413 if !out.is_empty() && !tight_before && !tight_after_prev {
414 out.push(' ');
415 }
416 out.push_str(t);
417 }
418 out
419}
420
421#[cfg(test)]
422mod tests {
423 use super::*;
424 use crate::check_conformance;
425 use crate::schema_gen::checked_grammar_from_schema;
426 use dsl_kit_core::IdGen;
427 use dsl_kit_schema::{
428 ChildSchema, ChildValueShape, FieldSchema, Multiplicity, NodeSchema, VariantSchema,
429 };
430
431 fn demo_schema() -> NodeSchema {
434 NodeSchema {
435 name: "Expr".into(),
436 variants: vec![
437 VariantSchema {
438 name: "Lit".into(),
439 fields: vec![FieldSchema {
440 name: "value".into(),
441 ty: "i64".into(),
442 optional: false,
443 }],
444 children: vec![],
445 },
446 VariantSchema {
447 name: "Name".into(),
448 fields: vec![
449 FieldSchema {
450 name: "text".into(),
451 ty: "String".into(),
452 optional: false,
453 },
454 FieldSchema {
455 name: "quoted".into(),
456 ty: "bool".into(),
457 optional: false,
458 },
459 ],
460 children: vec![],
461 },
462 VariantSchema {
463 name: "Add".into(),
464 fields: vec![],
465 children: vec![
466 ChildSchema {
467 name: "lhs".into(),
468 multiplicity: Multiplicity::One,
469 value_shape: ChildValueShape::Recursive,
470 scalar_shorthands: vec![],
471 non_empty: false,
472 },
473 ChildSchema {
474 name: "rhs".into(),
475 multiplicity: Multiplicity::One,
476 value_shape: ChildValueShape::Recursive,
477 scalar_shorthands: vec![],
478 non_empty: false,
479 },
480 ],
481 },
482 VariantSchema {
483 name: "Neg".into(),
484 fields: vec![],
485 children: vec![ChildSchema {
486 name: "body".into(),
487 multiplicity: Multiplicity::Optional,
488 value_shape: ChildValueShape::Recursive,
489 scalar_shorthands: vec![],
490 non_empty: false,
491 }],
492 },
493 VariantSchema {
494 name: "List".into(),
495 fields: vec![],
496 children: vec![ChildSchema {
497 name: "items".into(),
498 multiplicity: Multiplicity::Many,
499 value_shape: ChildValueShape::Recursive,
500 scalar_shorthands: vec![],
501 non_empty: false,
502 }],
503 },
504 VariantSchema {
505 name: "Env".into(),
506 fields: vec![],
507 children: vec![ChildSchema {
508 name: "entries".into(),
509 multiplicity: Multiplicity::Map,
510 value_shape: ChildValueShape::Recursive,
511 scalar_shorthands: vec![],
512 non_empty: false,
513 }],
514 },
515 VariantSchema {
516 name: "Unit".into(),
517 fields: vec![],
518 children: vec![],
519 },
520 ],
521 }
522 }
523
524 fn demo_examples() -> (Grammar, GrammarExamples) {
525 let g = checked_grammar_from_schema(&demo_schema(), &IdGen::new())
526 .expect("demo schema generates");
527 let ex = examples_from_grammar(&g).expect("examples synthesize");
528 (g, ex)
529 }
530
531 #[test]
532 fn every_per_rule_example_parses_as_its_own_variant() {
533 let (g, ex) = demo_examples();
534 assert_eq!(ex.per_rule.len(), 7, "one example per variant");
535 for e in &ex.per_rule {
536 let tree = g.parse(&e.text).unwrap_or_else(|err| {
537 panic!(
538 "example for `{}` failed to parse: {:?}\n text: {}",
539 e.rule, err.diagnostics, e.text
540 )
541 });
542 assert_eq!(tree.variant, e.rule, "example enters at its own variant");
543 let diags = check_conformance(&tree, &demo_schema());
544 assert!(
545 diags.is_empty(),
546 "conformance clean for {}: {diags:?}",
547 e.rule
548 );
549 }
550 }
551
552 #[test]
553 fn minimal_examples_have_the_expected_spellings() {
554 let (_, ex) = demo_examples();
555 let by_rule: HashMap<&str, &str> = ex
556 .per_rule
557 .iter()
558 .map(|e| (e.rule.as_str(), e.text.as_str()))
559 .collect();
560 assert_eq!(by_rule["Lit"], "Lit(value: 1)");
561 assert_eq!(by_rule["Name"], "Name(text: \"example\", quoted: true)");
562 assert_eq!(
563 by_rule["Add"], "Add(lhs: Unit(), rhs: Unit())",
564 "nested slots fill with the cheapest variant"
565 );
566 assert_eq!(
567 by_rule["Neg"], "Neg(body: none)",
568 "Optional minimal = absent"
569 );
570 assert_eq!(
571 by_rule["List"], "List(items: [])",
572 "Many minimal = empty list"
573 );
574 assert_eq!(
575 by_rule["Env"], "Env(entries: {})",
576 "Map minimal = empty map, braces tight like the empty list"
577 );
578 assert_eq!(by_rule["Unit"], "Unit()");
579 }
580
581 #[test]
587 fn rich_keyed_map_example_uses_distinct_keys() {
588 let map_only = NodeSchema {
589 name: "Cfg".into(),
590 variants: vec![
591 VariantSchema {
592 name: "Env".into(),
593 fields: vec![],
594 children: vec![ChildSchema {
595 name: "entries".into(),
596 multiplicity: Multiplicity::Map,
597 value_shape: ChildValueShape::Recursive,
598 scalar_shorthands: vec![],
599 non_empty: false,
600 }],
601 },
602 VariantSchema {
603 name: "Unit".into(),
604 fields: vec![],
605 children: vec![],
606 },
607 ],
608 };
609 let g = checked_grammar_from_schema(&map_only, &IdGen::new()).expect("generates");
610 let ex = examples_from_grammar(&g).expect("synthesizes");
611
612 let tree = g.parse(&ex.composite).unwrap_or_else(|err| {
613 panic!(
614 "composite failed to parse: {:?}\n text: {}",
615 err.diagnostics, ex.composite
616 )
617 });
618 let entries = tree
619 .keyed_child_slot("entries")
620 .expect("rich mode fills the keyed slot");
621 assert!(
622 entries.len() >= 2,
623 "rich mode should expand the map: {}",
624 ex.composite
625 );
626 let diags = check_conformance(&tree, &map_only);
627 assert!(
628 diags.is_empty(),
629 "synthesized example must conform: {diags:?}\n text: {}",
630 ex.composite
631 );
632 }
633
634 #[test]
638 fn keyed_entry_inherits_an_underivable_value() {
639 let ids = IdGen::new();
640 use crate::peg::{keyed_entry, node, rule, rule_ref, token};
643 let entry = keyed_entry(&ids, "entries", token(&ids, "%ident"), rule_ref(&ids, "s"));
644 let g = Grammar::new(vec![rule(&ids, "s", node(&ids, "N", entry))], "s");
645 let err = examples_from_grammar(&g).expect_err("no finite derivation exists");
646 assert!(
647 err.diagnostics
648 .iter()
649 .any(|d| d.code == codes::NO_FINITE_DERIVATION),
650 "expected NO_FINITE_DERIVATION; got {:?}",
651 err.diagnostics
652 .iter()
653 .map(|d| d.code.as_str())
654 .collect::<Vec<_>>()
655 );
656 }
657
658 #[test]
659 fn composite_parses_and_shows_nesting() {
660 let (g, ex) = demo_examples();
661 let tree = g.parse(&ex.composite).unwrap_or_else(|err| {
662 panic!(
663 "composite failed to parse: {:?}\n text: {}",
664 err.diagnostics, ex.composite
665 )
666 });
667 assert!(check_conformance(&tree, &demo_schema()).is_empty());
668 assert!(
671 !tree.children.is_empty(),
672 "composite has child structure: {}",
673 ex.composite
674 );
675 }
676
677 #[test]
678 fn underivable_rules_fail_loudly_with_the_full_list() {
679 let schema = NodeSchema {
682 name: "Loop".into(),
683 variants: vec![VariantSchema {
684 name: "Rec".into(),
685 fields: vec![],
686 children: vec![ChildSchema {
687 name: "inner".into(),
688 multiplicity: Multiplicity::One,
689 value_shape: ChildValueShape::Recursive,
690 scalar_shorthands: vec![],
691 non_empty: false,
692 }],
693 }],
694 };
695 let g = crate::schema_gen::grammar_from_schema(&schema, &IdGen::new())
696 .expect("generation itself succeeds");
697 let err = examples_from_grammar(&g).expect_err("no finite derivation");
698 assert!(
699 err.diagnostics
700 .iter()
701 .all(|d| d.code == codes::NO_FINITE_DERIVATION),
702 "{:?}",
703 err.diagnostics
704 );
705 assert_eq!(err.diagnostics.len(), 2);
707 }
708}