1use std::collections::HashMap;
30
31use crate::peg::{Grammar, Peg};
32use crate::{BuildError, Diagnostic};
33
34pub mod codes {
36 pub const NO_FINITE_DERIVATION: &str = "dsl_kit::example_gen::no_finite_derivation";
39 pub const UNKNOWN_RULE: &str = "dsl_kit::example_gen::unknown_rule";
41}
42
43pub const COMPOSITE_DEPTH: u32 = 2;
47
48#[derive(Debug, Clone)]
50pub struct RuleExample {
51 pub rule: String,
53 pub text: String,
55}
56
57#[derive(Debug, Clone)]
59pub struct GrammarExamples {
60 pub per_rule: Vec<RuleExample>,
64 pub composite: String,
67}
68
69pub fn examples_from_grammar(grammar: &Grammar) -> Result<GrammarExamples, BuildError> {
75 let synth = Synth::prepare(grammar)?;
76
77 let mut underivable = Vec::new();
78 for (name, _) in &synth.rules_in_order {
79 if synth.rule_cost(name) == INFINITE {
80 underivable.push(Diagnostic::error(
81 codes::NO_FINITE_DERIVATION,
82 format!("rule `{name}` has no finite derivation — no example input exists"),
83 ));
84 }
85 }
86 if !underivable.is_empty() {
87 return Err(BuildError::new(underivable));
88 }
89
90 let mut per_rule = Vec::new();
91 for (name, body) in &synth.rules_in_order {
92 if *name == grammar.start {
93 continue;
94 }
95 let mut tokens = Vec::new();
96 synth.emit(body, 0, &mut tokens)?;
97 per_rule.push(RuleExample {
98 rule: name.clone(),
99 text: render(&tokens),
100 });
101 }
102
103 let start_body = synth.rule_body(&grammar.start)?;
104 let mut tokens = Vec::new();
105 synth.emit(start_body, COMPOSITE_DEPTH, &mut tokens)?;
106 let composite = render(&tokens);
107
108 Ok(GrammarExamples {
109 per_rule,
110 composite,
111 })
112}
113
114const INFINITE: u64 = u64::MAX;
116
117struct Synth<'g> {
118 by_name: HashMap<&'g str, &'g Peg>,
120 rules_in_order: Vec<(String, &'g Peg)>,
122 costs: HashMap<String, u64>,
124}
125
126impl<'g> Synth<'g> {
127 fn prepare(grammar: &'g Grammar) -> Result<Self, BuildError> {
128 let mut by_name = HashMap::new();
129 let mut rules_in_order = Vec::new();
130 for r in &grammar.rules {
131 if let Peg::Rule { name, body, .. } = r {
132 by_name.insert(name.as_str(), body.as_ref());
133 rules_in_order.push((name.clone(), body.as_ref()));
134 }
135 }
136
137 let mut costs: HashMap<String, u64> = rules_in_order
141 .iter()
142 .map(|(n, _)| (n.clone(), INFINITE))
143 .collect();
144 loop {
145 let mut changed = false;
146 for (name, body) in &rules_in_order {
147 let c = peg_cost(body, &costs);
148 if c < costs[name] {
149 costs.insert(name.clone(), c);
150 changed = true;
151 }
152 }
153 if !changed {
154 break;
155 }
156 }
157
158 Ok(Self {
159 by_name,
160 rules_in_order,
161 costs,
162 })
163 }
164
165 fn rule_cost(&self, name: &str) -> u64 {
166 self.costs.get(name).copied().unwrap_or(INFINITE)
167 }
168
169 fn rule_body(&self, name: &str) -> Result<&'g Peg, BuildError> {
170 self.by_name.get(name).copied().ok_or_else(|| {
171 BuildError::single(Diagnostic::error(
172 codes::UNKNOWN_RULE,
173 format!("reference to undefined rule `{name}`"),
174 ))
175 })
176 }
177
178 fn emit(&self, peg: &Peg, rich_depth: u32, out: &mut Vec<String>) -> Result<(), BuildError> {
182 match peg {
183 Peg::Token { pat, .. } => {
184 out.push(token_input(pat));
185 Ok(())
186 }
187 Peg::Seq { items, .. } => {
188 for item in items {
189 self.emit(item, rich_depth, out)?;
190 }
191 Ok(())
192 }
193 Peg::Choice { alts, .. } => {
194 let arm = self.pick_arm(alts, rich_depth)?;
195 self.emit(arm, rich_depth, out)
196 }
197 Peg::Repeat { body, min, max, .. } => {
198 let count = if rich_depth > 0 {
199 (*min).max(2.min(max.unwrap_or(2)))
200 } else {
201 *min
202 };
203 for _ in 0..count {
204 self.emit(body, rich_depth, out)?;
205 }
206 Ok(())
207 }
208 Peg::RuleRef { name, .. } => {
209 let body = self.rule_body(name)?;
210 self.emit(body, rich_depth.saturating_sub(1), out)
211 }
212 Peg::Rule { body, .. } | Peg::Node { body, .. } | Peg::Field { body, .. } => {
213 self.emit(body, rich_depth, out)
214 }
215 }
216 }
217
218 fn pick_arm<'p>(&self, alts: &'p [Peg], rich_depth: u32) -> Result<&'p Peg, BuildError> {
221 let finite = alts
222 .iter()
223 .map(|a| (a, peg_cost(a, &self.costs)))
224 .filter(|(_, c)| *c != INFINITE);
225 let picked = if rich_depth > 0 {
226 finite.max_by_key(|(_, c)| *c)
227 } else {
228 finite.min_by_key(|(_, c)| *c)
229 };
230 picked.map(|(a, _)| a).ok_or_else(|| {
231 BuildError::single(Diagnostic::error(
232 codes::NO_FINITE_DERIVATION,
233 "choice has no finite alternative".to_string(),
234 ))
235 })
236 }
237}
238
239fn peg_cost(peg: &Peg, costs: &HashMap<String, u64>) -> u64 {
242 match peg {
243 Peg::Token { .. } => 1,
244 Peg::Seq { items, .. } => items
245 .iter()
246 .try_fold(0u64, |acc, i| {
247 let c = peg_cost(i, costs);
248 if c == INFINITE {
249 None
250 } else {
251 Some(acc.saturating_add(c))
252 }
253 })
254 .unwrap_or(INFINITE),
255 Peg::Choice { alts, .. } => alts
256 .iter()
257 .map(|a| peg_cost(a, costs))
258 .min()
259 .unwrap_or(INFINITE),
260 Peg::Repeat { body, min, .. } => {
261 if *min == 0 {
262 0
263 } else {
264 let c = peg_cost(body, costs);
265 if c == INFINITE {
266 INFINITE
267 } else {
268 c.saturating_mul(u64::from(*min))
269 }
270 }
271 }
272 Peg::RuleRef { name, .. } => costs.get(name).copied().unwrap_or(INFINITE),
273 Peg::Rule { body, .. } | Peg::Node { body, .. } | Peg::Field { body, .. } => {
274 peg_cost(body, costs)
275 }
276 }
277}
278
279fn token_input(pat: &str) -> String {
281 if let Some(kw) = pat.strip_prefix("%kw:") {
282 return kw.to_string();
283 }
284 match pat {
285 "%int" => "1".to_string(),
286 "%str" => "\"example\"".to_string(),
287 "%ident" => "x".to_string(),
288 "%ws" => " ".to_string(),
289 literal => literal.to_string(),
290 }
291}
292
293fn render(tokens: &[String]) -> String {
297 let mut out = String::new();
298 for t in tokens {
299 let tight_before = matches!(t.as_str(), "," | ")" | "]" | ":" | "(");
300 let tight_after_prev = out.ends_with('(') || out.ends_with('[');
301 if !out.is_empty() && !tight_before && !tight_after_prev {
302 out.push(' ');
303 }
304 out.push_str(t);
305 }
306 out
307}
308
309#[cfg(test)]
310mod tests {
311 use super::*;
312 use crate::check_conformance;
313 use crate::schema_gen::checked_grammar_from_schema;
314 use dsl_kit_core::IdGen;
315 use dsl_kit_schema::{ChildSchema, FieldSchema, Multiplicity, NodeSchema, VariantSchema};
316
317 fn demo_schema() -> NodeSchema {
320 NodeSchema {
321 name: "Expr".into(),
322 variants: vec![
323 VariantSchema {
324 name: "Lit".into(),
325 fields: vec![FieldSchema {
326 name: "value".into(),
327 ty: "i64".into(),
328 optional: false,
329 }],
330 children: vec![],
331 },
332 VariantSchema {
333 name: "Name".into(),
334 fields: vec![
335 FieldSchema {
336 name: "text".into(),
337 ty: "String".into(),
338 optional: false,
339 },
340 FieldSchema {
341 name: "quoted".into(),
342 ty: "bool".into(),
343 optional: false,
344 },
345 ],
346 children: vec![],
347 },
348 VariantSchema {
349 name: "Add".into(),
350 fields: vec![],
351 children: vec![
352 ChildSchema {
353 name: "lhs".into(),
354 multiplicity: Multiplicity::One,
355 },
356 ChildSchema {
357 name: "rhs".into(),
358 multiplicity: Multiplicity::One,
359 },
360 ],
361 },
362 VariantSchema {
363 name: "Neg".into(),
364 fields: vec![],
365 children: vec![ChildSchema {
366 name: "body".into(),
367 multiplicity: Multiplicity::Optional,
368 }],
369 },
370 VariantSchema {
371 name: "List".into(),
372 fields: vec![],
373 children: vec![ChildSchema {
374 name: "items".into(),
375 multiplicity: Multiplicity::Many,
376 }],
377 },
378 VariantSchema {
379 name: "Unit".into(),
380 fields: vec![],
381 children: vec![],
382 },
383 ],
384 }
385 }
386
387 fn demo_examples() -> (Grammar, GrammarExamples) {
388 let g = checked_grammar_from_schema(&demo_schema(), &IdGen::new())
389 .expect("demo schema generates");
390 let ex = examples_from_grammar(&g).expect("examples synthesize");
391 (g, ex)
392 }
393
394 #[test]
395 fn every_per_rule_example_parses_as_its_own_variant() {
396 let (g, ex) = demo_examples();
397 assert_eq!(ex.per_rule.len(), 6, "one example per variant");
398 for e in &ex.per_rule {
399 let tree = g.parse(&e.text).unwrap_or_else(|err| {
400 panic!(
401 "example for `{}` failed to parse: {:?}\n text: {}",
402 e.rule, err.diagnostics, e.text
403 )
404 });
405 assert_eq!(tree.variant, e.rule, "example enters at its own variant");
406 let diags = check_conformance(&tree, &demo_schema());
407 assert!(
408 diags.is_empty(),
409 "conformance clean for {}: {diags:?}",
410 e.rule
411 );
412 }
413 }
414
415 #[test]
416 fn minimal_examples_have_the_expected_spellings() {
417 let (_, ex) = demo_examples();
418 let by_rule: HashMap<&str, &str> = ex
419 .per_rule
420 .iter()
421 .map(|e| (e.rule.as_str(), e.text.as_str()))
422 .collect();
423 assert_eq!(by_rule["Lit"], "Lit(value: 1)");
424 assert_eq!(by_rule["Name"], "Name(text: \"example\", quoted: true)");
425 assert_eq!(
426 by_rule["Add"], "Add(lhs: Unit(), rhs: Unit())",
427 "nested slots fill with the cheapest variant"
428 );
429 assert_eq!(
430 by_rule["Neg"], "Neg(body: none)",
431 "Optional minimal = absent"
432 );
433 assert_eq!(
434 by_rule["List"], "List(items: [])",
435 "Many minimal = empty list"
436 );
437 assert_eq!(by_rule["Unit"], "Unit()");
438 }
439
440 #[test]
441 fn composite_parses_and_shows_nesting() {
442 let (g, ex) = demo_examples();
443 let tree = g.parse(&ex.composite).unwrap_or_else(|err| {
444 panic!(
445 "composite failed to parse: {:?}\n text: {}",
446 err.diagnostics, ex.composite
447 )
448 });
449 assert!(check_conformance(&tree, &demo_schema()).is_empty());
450 assert!(
453 !tree.children.is_empty(),
454 "composite has child structure: {}",
455 ex.composite
456 );
457 }
458
459 #[test]
460 fn underivable_rules_fail_loudly_with_the_full_list() {
461 let schema = NodeSchema {
464 name: "Loop".into(),
465 variants: vec![VariantSchema {
466 name: "Rec".into(),
467 fields: vec![],
468 children: vec![ChildSchema {
469 name: "inner".into(),
470 multiplicity: Multiplicity::One,
471 }],
472 }],
473 };
474 let g = crate::schema_gen::grammar_from_schema(&schema, &IdGen::new())
475 .expect("generation itself succeeds");
476 let err = examples_from_grammar(&g).expect_err("no finite derivation");
477 assert!(
478 err.diagnostics
479 .iter()
480 .all(|d| d.code == codes::NO_FINITE_DERIVATION),
481 "{:?}",
482 err.diagnostics
483 );
484 assert_eq!(err.diagnostics.len(), 2);
486 }
487}