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 let mut tokens = Vec::new();
97 synth.emit(body, 0, &mut tokens)?;
98 per_rule.push(RuleExample {
99 rule: name.clone(),
100 text: render(&tokens),
101 });
102 }
103
104 let start_body = synth.rule_body(&grammar.start)?;
105 let mut tokens = Vec::new();
106 synth.emit(start_body, COMPOSITE_DEPTH, &mut tokens)?;
107 let composite = render(&tokens);
108
109 Ok(GrammarExamples {
110 per_rule,
111 composite,
112 })
113}
114
115const INFINITE: u64 = u64::MAX;
117
118struct Synth<'g> {
119 by_name: HashMap<&'g str, &'g Peg>,
121 rules_in_order: Vec<(String, &'g Peg)>,
123 costs: HashMap<String, u64>,
125 key_seq: Cell<u32>,
131}
132
133impl<'g> Synth<'g> {
134 fn prepare(grammar: &'g Grammar) -> Result<Self, BuildError> {
135 let mut by_name = HashMap::new();
136 let mut rules_in_order = Vec::new();
137 for r in &grammar.rules {
138 if let Peg::Rule { name, body, .. } = r {
139 by_name.insert(name.as_str(), body.as_ref());
140 rules_in_order.push((name.clone(), body.as_ref()));
141 }
142 }
143
144 let mut costs: HashMap<String, u64> = rules_in_order
148 .iter()
149 .map(|(n, _)| (n.clone(), INFINITE))
150 .collect();
151 loop {
152 let mut changed = false;
153 for (name, body) in &rules_in_order {
154 let c = peg_cost(body, &costs);
155 if c < costs[name] {
156 costs.insert(name.clone(), c);
157 changed = true;
158 }
159 }
160 if !changed {
161 break;
162 }
163 }
164
165 Ok(Self {
166 by_name,
167 rules_in_order,
168 costs,
169 key_seq: Cell::new(0),
170 })
171 }
172
173 fn rule_cost(&self, name: &str) -> u64 {
174 self.costs.get(name).copied().unwrap_or(INFINITE)
175 }
176
177 fn rule_body(&self, name: &str) -> Result<&'g Peg, BuildError> {
178 self.by_name.get(name).copied().ok_or_else(|| {
179 BuildError::single(Diagnostic::error(
180 codes::UNKNOWN_RULE,
181 format!("reference to undefined rule `{name}`"),
182 ))
183 })
184 }
185
186 fn emit(&self, peg: &Peg, rich_depth: u32, out: &mut Vec<String>) -> Result<(), BuildError> {
190 match peg {
191 Peg::Token { pat, .. } => {
192 out.push(token_input(pat));
193 Ok(())
194 }
195 Peg::Seq { items, .. } => {
196 for item in items {
197 self.emit(item, rich_depth, out)?;
198 }
199 Ok(())
200 }
201 Peg::Choice { alts, .. } => {
202 let arm = self.pick_arm(alts, rich_depth)?;
203 self.emit(arm, rich_depth, out)
204 }
205 Peg::Repeat { body, min, max, .. } => {
206 let count = if rich_depth > 0 {
207 (*min).max(2.min(max.unwrap_or(2)))
208 } else {
209 *min
210 };
211 for _ in 0..count {
212 self.emit(body, rich_depth, out)?;
213 }
214 Ok(())
215 }
216 Peg::RuleRef { name, .. } => {
217 let body = self.rule_body(name)?;
218 self.emit(body, rich_depth.saturating_sub(1), out)
219 }
220 Peg::Rule { body, .. } | Peg::Node { body, .. } | Peg::Field { body, .. } => {
221 self.emit(body, rich_depth, out)
222 }
223 Peg::KeyedEntry { key, value, .. } => {
235 let n = self.key_seq.get() + 1;
236 self.key_seq.set(n);
237 self.emit_key(key, n, rich_depth, out)?;
238 self.emit(value, rich_depth, out)
239 }
240 }
241 }
242
243 fn emit_key(
252 &self,
253 peg: &Peg,
254 n: u32,
255 rich_depth: u32,
256 out: &mut Vec<String>,
257 ) -> Result<(), BuildError> {
258 match peg {
259 Peg::Token { pat, .. } => {
260 out.push(keyed_token_input(pat, n));
261 Ok(())
262 }
263 Peg::Seq { items, .. } => {
264 for item in items {
265 self.emit_key(item, n, rich_depth, out)?;
266 }
267 Ok(())
268 }
269 Peg::Choice { alts, .. } => {
270 let arm = self.pick_arm(alts, rich_depth)?;
271 self.emit_key(arm, n, rich_depth, out)
272 }
273 other => self.emit(other, rich_depth, out),
274 }
275 }
276
277 fn pick_arm<'p>(&self, alts: &'p [Peg], rich_depth: u32) -> Result<&'p Peg, BuildError> {
280 let finite = alts
281 .iter()
282 .map(|a| (a, peg_cost(a, &self.costs)))
283 .filter(|(_, c)| *c != INFINITE);
284 let picked = if rich_depth > 0 {
285 finite.max_by_key(|(_, c)| *c)
286 } else {
287 finite.min_by_key(|(_, c)| *c)
288 };
289 picked.map(|(a, _)| a).ok_or_else(|| {
290 BuildError::single(Diagnostic::error(
291 codes::NO_FINITE_DERIVATION,
292 "choice has no finite alternative".to_string(),
293 ))
294 })
295 }
296}
297
298fn peg_cost(peg: &Peg, costs: &HashMap<String, u64>) -> u64 {
301 match peg {
302 Peg::Token { .. } => 1,
303 Peg::Seq { items, .. } => items
304 .iter()
305 .try_fold(0u64, |acc, i| {
306 let c = peg_cost(i, costs);
307 if c == INFINITE {
308 None
309 } else {
310 Some(acc.saturating_add(c))
311 }
312 })
313 .unwrap_or(INFINITE),
314 Peg::Choice { alts, .. } => alts
315 .iter()
316 .map(|a| peg_cost(a, costs))
317 .min()
318 .unwrap_or(INFINITE),
319 Peg::Repeat { body, min, .. } => {
320 if *min == 0 {
321 0
322 } else {
323 let c = peg_cost(body, costs);
324 if c == INFINITE {
325 INFINITE
326 } else {
327 c.saturating_mul(u64::from(*min))
328 }
329 }
330 }
331 Peg::RuleRef { name, .. } => costs.get(name).copied().unwrap_or(INFINITE),
332 Peg::Rule { body, .. } | Peg::Node { body, .. } | Peg::Field { body, .. } => {
333 peg_cost(body, costs)
334 }
335 Peg::KeyedEntry { key, value, .. } => {
338 let (k, v) = (peg_cost(key, costs), peg_cost(value, costs));
339 if k == INFINITE || v == INFINITE {
340 INFINITE
341 } else {
342 k.saturating_add(v)
343 }
344 }
345 }
346}
347
348fn keyed_token_input(pat: &str, n: u32) -> String {
354 match pat {
355 "%str" => format!("\"key{n}\""),
356 "%ident" => format!("key{n}"),
357 other => token_input(other),
358 }
359}
360
361fn token_input(pat: &str) -> String {
363 if let Some(kw) = pat.strip_prefix("%kw:") {
364 return kw.to_string();
365 }
366 match pat {
367 "%int" => "1".to_string(),
368 "%str" => "\"example\"".to_string(),
369 "%ident" => "x".to_string(),
370 "%ws" => " ".to_string(),
371 literal => literal.to_string(),
372 }
373}
374
375fn render(tokens: &[String]) -> String {
379 let mut out = String::new();
380 for t in tokens {
381 let tight_before = matches!(t.as_str(), "," | ")" | "]" | "}" | ":" | "(");
382 let tight_after_prev = out.ends_with('(') || out.ends_with('[') || out.ends_with('{');
383 if !out.is_empty() && !tight_before && !tight_after_prev {
384 out.push(' ');
385 }
386 out.push_str(t);
387 }
388 out
389}
390
391#[cfg(test)]
392mod tests {
393 use super::*;
394 use crate::check_conformance;
395 use crate::schema_gen::checked_grammar_from_schema;
396 use dsl_kit_core::IdGen;
397 use dsl_kit_schema::{
398 ChildSchema, ChildValueShape, FieldSchema, Multiplicity, NodeSchema, VariantSchema,
399 };
400
401 fn demo_schema() -> NodeSchema {
404 NodeSchema {
405 name: "Expr".into(),
406 variants: vec![
407 VariantSchema {
408 name: "Lit".into(),
409 fields: vec![FieldSchema {
410 name: "value".into(),
411 ty: "i64".into(),
412 optional: false,
413 }],
414 children: vec![],
415 },
416 VariantSchema {
417 name: "Name".into(),
418 fields: vec![
419 FieldSchema {
420 name: "text".into(),
421 ty: "String".into(),
422 optional: false,
423 },
424 FieldSchema {
425 name: "quoted".into(),
426 ty: "bool".into(),
427 optional: false,
428 },
429 ],
430 children: vec![],
431 },
432 VariantSchema {
433 name: "Add".into(),
434 fields: vec![],
435 children: vec![
436 ChildSchema {
437 name: "lhs".into(),
438 multiplicity: Multiplicity::One,
439 value_shape: ChildValueShape::Recursive,
440 },
441 ChildSchema {
442 name: "rhs".into(),
443 multiplicity: Multiplicity::One,
444 value_shape: ChildValueShape::Recursive,
445 },
446 ],
447 },
448 VariantSchema {
449 name: "Neg".into(),
450 fields: vec![],
451 children: vec![ChildSchema {
452 name: "body".into(),
453 multiplicity: Multiplicity::Optional,
454 value_shape: ChildValueShape::Recursive,
455 }],
456 },
457 VariantSchema {
458 name: "List".into(),
459 fields: vec![],
460 children: vec![ChildSchema {
461 name: "items".into(),
462 multiplicity: Multiplicity::Many,
463 value_shape: ChildValueShape::Recursive,
464 }],
465 },
466 VariantSchema {
467 name: "Env".into(),
468 fields: vec![],
469 children: vec![ChildSchema {
470 name: "entries".into(),
471 multiplicity: Multiplicity::Map,
472 value_shape: ChildValueShape::Recursive,
473 }],
474 },
475 VariantSchema {
476 name: "Unit".into(),
477 fields: vec![],
478 children: vec![],
479 },
480 ],
481 }
482 }
483
484 fn demo_examples() -> (Grammar, GrammarExamples) {
485 let g = checked_grammar_from_schema(&demo_schema(), &IdGen::new())
486 .expect("demo schema generates");
487 let ex = examples_from_grammar(&g).expect("examples synthesize");
488 (g, ex)
489 }
490
491 #[test]
492 fn every_per_rule_example_parses_as_its_own_variant() {
493 let (g, ex) = demo_examples();
494 assert_eq!(ex.per_rule.len(), 7, "one example per variant");
495 for e in &ex.per_rule {
496 let tree = g.parse(&e.text).unwrap_or_else(|err| {
497 panic!(
498 "example for `{}` failed to parse: {:?}\n text: {}",
499 e.rule, err.diagnostics, e.text
500 )
501 });
502 assert_eq!(tree.variant, e.rule, "example enters at its own variant");
503 let diags = check_conformance(&tree, &demo_schema());
504 assert!(
505 diags.is_empty(),
506 "conformance clean for {}: {diags:?}",
507 e.rule
508 );
509 }
510 }
511
512 #[test]
513 fn minimal_examples_have_the_expected_spellings() {
514 let (_, ex) = demo_examples();
515 let by_rule: HashMap<&str, &str> = ex
516 .per_rule
517 .iter()
518 .map(|e| (e.rule.as_str(), e.text.as_str()))
519 .collect();
520 assert_eq!(by_rule["Lit"], "Lit(value: 1)");
521 assert_eq!(by_rule["Name"], "Name(text: \"example\", quoted: true)");
522 assert_eq!(
523 by_rule["Add"], "Add(lhs: Unit(), rhs: Unit())",
524 "nested slots fill with the cheapest variant"
525 );
526 assert_eq!(
527 by_rule["Neg"], "Neg(body: none)",
528 "Optional minimal = absent"
529 );
530 assert_eq!(
531 by_rule["List"], "List(items: [])",
532 "Many minimal = empty list"
533 );
534 assert_eq!(
535 by_rule["Env"], "Env(entries: {})",
536 "Map minimal = empty map, braces tight like the empty list"
537 );
538 assert_eq!(by_rule["Unit"], "Unit()");
539 }
540
541 #[test]
547 fn rich_keyed_map_example_uses_distinct_keys() {
548 let map_only = NodeSchema {
549 name: "Cfg".into(),
550 variants: vec![
551 VariantSchema {
552 name: "Env".into(),
553 fields: vec![],
554 children: vec![ChildSchema {
555 name: "entries".into(),
556 multiplicity: Multiplicity::Map,
557 value_shape: ChildValueShape::Recursive,
558 }],
559 },
560 VariantSchema {
561 name: "Unit".into(),
562 fields: vec![],
563 children: vec![],
564 },
565 ],
566 };
567 let g = checked_grammar_from_schema(&map_only, &IdGen::new()).expect("generates");
568 let ex = examples_from_grammar(&g).expect("synthesizes");
569
570 let tree = g.parse(&ex.composite).unwrap_or_else(|err| {
571 panic!(
572 "composite failed to parse: {:?}\n text: {}",
573 err.diagnostics, ex.composite
574 )
575 });
576 let entries = tree
577 .keyed_child_slot("entries")
578 .expect("rich mode fills the keyed slot");
579 assert!(
580 entries.len() >= 2,
581 "rich mode should expand the map: {}",
582 ex.composite
583 );
584 let diags = check_conformance(&tree, &map_only);
585 assert!(
586 diags.is_empty(),
587 "synthesized example must conform: {diags:?}\n text: {}",
588 ex.composite
589 );
590 }
591
592 #[test]
596 fn keyed_entry_inherits_an_underivable_value() {
597 let ids = IdGen::new();
598 use crate::peg::{keyed_entry, node, rule, rule_ref, token};
601 let entry = keyed_entry(&ids, "entries", token(&ids, "%ident"), rule_ref(&ids, "s"));
602 let g = Grammar::new(vec![rule(&ids, "s", node(&ids, "N", entry))], "s");
603 let err = examples_from_grammar(&g).expect_err("no finite derivation exists");
604 assert!(
605 err.diagnostics
606 .iter()
607 .any(|d| d.code == codes::NO_FINITE_DERIVATION),
608 "expected NO_FINITE_DERIVATION; got {:?}",
609 err.diagnostics
610 .iter()
611 .map(|d| d.code.as_str())
612 .collect::<Vec<_>>()
613 );
614 }
615
616 #[test]
617 fn composite_parses_and_shows_nesting() {
618 let (g, ex) = demo_examples();
619 let tree = g.parse(&ex.composite).unwrap_or_else(|err| {
620 panic!(
621 "composite failed to parse: {:?}\n text: {}",
622 err.diagnostics, ex.composite
623 )
624 });
625 assert!(check_conformance(&tree, &demo_schema()).is_empty());
626 assert!(
629 !tree.children.is_empty(),
630 "composite has child structure: {}",
631 ex.composite
632 );
633 }
634
635 #[test]
636 fn underivable_rules_fail_loudly_with_the_full_list() {
637 let schema = NodeSchema {
640 name: "Loop".into(),
641 variants: vec![VariantSchema {
642 name: "Rec".into(),
643 fields: vec![],
644 children: vec![ChildSchema {
645 name: "inner".into(),
646 multiplicity: Multiplicity::One,
647 value_shape: ChildValueShape::Recursive,
648 }],
649 }],
650 };
651 let g = crate::schema_gen::grammar_from_schema(&schema, &IdGen::new())
652 .expect("generation itself succeeds");
653 let err = examples_from_grammar(&g).expect_err("no finite derivation");
654 assert!(
655 err.diagnostics
656 .iter()
657 .all(|d| d.code == codes::NO_FINITE_DERIVATION),
658 "{:?}",
659 err.diagnostics
660 );
661 assert_eq!(err.diagnostics.len(), 2);
663 }
664}