Skip to main content

dsl_kit_parse/
example_gen.rs

1//! Example synthesis from a grammar (item Q-1).
2//!
3//! Walks a [`Grammar`]'s [`Peg`] — not the schema — and emits input
4//! strings that the grammar accepts **by construction**: every choice
5//! picks a concrete arm, every token contributes matching input text
6//! (`%int` → `1`, `%str` → `"example"`, keywords verbatim). Because
7//! synthesis reads the grammar itself, spellings supplied through
8//! `schema_gen::SyntaxOverrides` fall out automatically — no separate
9//! example registration.
10//!
11//! Two synthesis modes drive the output of [`examples_from_grammar`]:
12//!
13//! - **Minimal** (per-rule examples) — at every choice take the arm
14//!   with the cheapest finite derivation, at every repeat emit the
15//!   minimum count. Terminates by the shortest-derivation argument:
16//!   each step either emits a token or strictly reduces the remaining
17//!   derivation cost.
18//! - **Rich** (the composite program) — while a depth budget lasts,
19//!   choices take the *most expensive* finite arm and repeats emit up
20//!   to two iterations, showing nesting and list syntax; the budget
21//!   decrements per rule expansion and exhaustion falls back to
22//!   Minimal.
23//!
24//! The intended consumer is an AI writing the canonical text syntax:
25//! few-shot examples beat a formal grammar table for one-shot
26//! accuracy, and machine-derived examples cannot drift from the
27//! grammar the way hand-written documentation does.
28
29use std::collections::HashMap;
30
31use crate::peg::{Grammar, Peg};
32use crate::{BuildError, Diagnostic};
33
34/// Diagnostic codes emitted by example synthesis.
35pub mod codes {
36    /// A rule has no finite derivation (every path recurses forever),
37    /// so no example input exists.
38    pub const NO_FINITE_DERIVATION: &str = "dsl_kit::example_gen::no_finite_derivation";
39    /// A `RuleRef` names a rule the grammar does not define.
40    pub const UNKNOWN_RULE: &str = "dsl_kit::example_gen::unknown_rule";
41}
42
43/// Rich-mode depth budget used by [`examples_from_grammar`] for the
44/// composite program: rule expansions beyond this depth continue
45/// minimally.
46pub const COMPOSITE_DEPTH: u32 = 2;
47
48/// One rule's minimal example.
49#[derive(Debug, Clone)]
50pub struct RuleExample {
51    /// Rule name (for `schema_gen` grammars: the variant name).
52    pub rule: String,
53    /// Input text accepted by the grammar, entering at this rule.
54    pub text: String,
55}
56
57/// Everything [`examples_from_grammar`] synthesizes for one grammar.
58#[derive(Debug, Clone)]
59pub struct GrammarExamples {
60    /// Minimal example per non-start rule, in rule declaration order.
61    /// For `schema_gen` grammars this is exactly one example per
62    /// variant.
63    pub per_rule: Vec<RuleExample>,
64    /// One depth-capped rich expansion of the start rule, showing
65    /// nesting and repetition.
66    pub composite: String,
67}
68
69/// Synthesizes [`GrammarExamples`] for `grammar`.
70///
71/// Fails with one [`codes::NO_FINITE_DERIVATION`] diagnostic per
72/// underivable rule (collected, so the author sees the full list), or
73/// [`codes::UNKNOWN_RULE`] on a dangling reference.
74pub 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
114/// Sentinel cost for "no finite derivation".
115const INFINITE: u64 = u64::MAX;
116
117struct Synth<'g> {
118    /// Rule name → body, for `RuleRef` expansion.
119    by_name: HashMap<&'g str, &'g Peg>,
120    /// `(name, body)` in grammar declaration order.
121    rules_in_order: Vec<(String, &'g Peg)>,
122    /// Shortest-derivation token count per rule (fixpoint result).
123    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        // Shortest-derivation cost fixpoint: start every rule at
138        // INFINITE and relax until stable. Monotone non-increasing and
139        // bounded, so it terminates.
140        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    /// Appends the input tokens of one derivation of `peg`.
179    /// `rich_depth > 0` selects the expansive arm at choices and up to
180    /// two iterations at repeats; `0` is the minimal mode.
181    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    /// Chooses a choice arm: cheapest finite derivation in minimal
219    /// mode, most expensive finite one in rich mode (ties: first).
220    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
239/// Shortest-derivation token count of `peg` under the current rule
240/// cost estimates ([`INFINITE`]-safe saturating arithmetic).
241fn 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
279/// Input text matching one token pattern.
280fn 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
293/// Joins tokens with canonical-syntax spacing: no space before
294/// punctuation that closes or separates (`,` `)` `]` `:` `(`), no
295/// space after an opener (`(` `[`).
296fn 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    /// Same shape matrix as the schema_gen demo: int / string / bool
318    /// fields, One / Optional / Many children, zero-argument variant.
319    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        // Rich mode picked an expansive variant and expanded at least
451        // one nested child — pin the property, not the exact string.
452        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        // A single variant whose only child is mandatory and recursive:
462        // no finite tree exists.
463        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        // Both the start rule and the variant rule are underivable.
485        assert_eq!(err.diagnostics.len(), 2);
486    }
487}