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 }],
329 children: vec![],
330 },
331 VariantSchema {
332 name: "Name".into(),
333 fields: vec![
334 FieldSchema {
335 name: "text".into(),
336 ty: "String".into(),
337 },
338 FieldSchema {
339 name: "quoted".into(),
340 ty: "bool".into(),
341 },
342 ],
343 children: vec![],
344 },
345 VariantSchema {
346 name: "Add".into(),
347 fields: vec![],
348 children: vec![
349 ChildSchema {
350 name: "lhs".into(),
351 multiplicity: Multiplicity::One,
352 },
353 ChildSchema {
354 name: "rhs".into(),
355 multiplicity: Multiplicity::One,
356 },
357 ],
358 },
359 VariantSchema {
360 name: "Neg".into(),
361 fields: vec![],
362 children: vec![ChildSchema {
363 name: "body".into(),
364 multiplicity: Multiplicity::Optional,
365 }],
366 },
367 VariantSchema {
368 name: "List".into(),
369 fields: vec![],
370 children: vec![ChildSchema {
371 name: "items".into(),
372 multiplicity: Multiplicity::Many,
373 }],
374 },
375 VariantSchema {
376 name: "Unit".into(),
377 fields: vec![],
378 children: vec![],
379 },
380 ],
381 }
382 }
383
384 fn demo_examples() -> (Grammar, GrammarExamples) {
385 let g = checked_grammar_from_schema(&demo_schema(), &IdGen::new())
386 .expect("demo schema generates");
387 let ex = examples_from_grammar(&g).expect("examples synthesize");
388 (g, ex)
389 }
390
391 #[test]
392 fn every_per_rule_example_parses_as_its_own_variant() {
393 let (g, ex) = demo_examples();
394 assert_eq!(ex.per_rule.len(), 6, "one example per variant");
395 for e in &ex.per_rule {
396 let tree = g.parse(&e.text).unwrap_or_else(|err| {
397 panic!(
398 "example for `{}` failed to parse: {:?}\n text: {}",
399 e.rule, err.diagnostics, e.text
400 )
401 });
402 assert_eq!(tree.variant, e.rule, "example enters at its own variant");
403 let diags = check_conformance(&tree, &demo_schema());
404 assert!(
405 diags.is_empty(),
406 "conformance clean for {}: {diags:?}",
407 e.rule
408 );
409 }
410 }
411
412 #[test]
413 fn minimal_examples_have_the_expected_spellings() {
414 let (_, ex) = demo_examples();
415 let by_rule: HashMap<&str, &str> = ex
416 .per_rule
417 .iter()
418 .map(|e| (e.rule.as_str(), e.text.as_str()))
419 .collect();
420 assert_eq!(by_rule["Lit"], "Lit(value: 1)");
421 assert_eq!(by_rule["Name"], "Name(text: \"example\", quoted: true)");
422 assert_eq!(
423 by_rule["Add"], "Add(lhs: Unit(), rhs: Unit())",
424 "nested slots fill with the cheapest variant"
425 );
426 assert_eq!(
427 by_rule["Neg"], "Neg(body: none)",
428 "Optional minimal = absent"
429 );
430 assert_eq!(
431 by_rule["List"], "List(items: [])",
432 "Many minimal = empty list"
433 );
434 assert_eq!(by_rule["Unit"], "Unit()");
435 }
436
437 #[test]
438 fn composite_parses_and_shows_nesting() {
439 let (g, ex) = demo_examples();
440 let tree = g.parse(&ex.composite).unwrap_or_else(|err| {
441 panic!(
442 "composite failed to parse: {:?}\n text: {}",
443 err.diagnostics, ex.composite
444 )
445 });
446 assert!(check_conformance(&tree, &demo_schema()).is_empty());
447 assert!(
450 !tree.children.is_empty(),
451 "composite has child structure: {}",
452 ex.composite
453 );
454 }
455
456 #[test]
457 fn underivable_rules_fail_loudly_with_the_full_list() {
458 let schema = NodeSchema {
461 name: "Loop".into(),
462 variants: vec![VariantSchema {
463 name: "Rec".into(),
464 fields: vec![],
465 children: vec![ChildSchema {
466 name: "inner".into(),
467 multiplicity: Multiplicity::One,
468 }],
469 }],
470 };
471 let g = crate::schema_gen::grammar_from_schema(&schema, &IdGen::new())
472 .expect("generation itself succeeds");
473 let err = examples_from_grammar(&g).expect_err("no finite derivation");
474 assert!(
475 err.diagnostics
476 .iter()
477 .all(|d| d.code == codes::NO_FINITE_DERIVATION),
478 "{:?}",
479 err.diagnostics
480 );
481 assert_eq!(err.diagnostics.len(), 2);
483 }
484}