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::cell::Cell;
30use std::collections::HashMap;
31
32use crate::peg::{Grammar, Peg};
33use crate::{BuildError, Diagnostic};
34
35/// Diagnostic codes emitted by example synthesis.
36pub mod codes {
37    /// A rule has no finite derivation (every path recurses forever),
38    /// so no example input exists.
39    pub const NO_FINITE_DERIVATION: &str = "dsl_kit::example_gen::no_finite_derivation";
40    /// A `RuleRef` names a rule the grammar does not define.
41    pub const UNKNOWN_RULE: &str = "dsl_kit::example_gen::unknown_rule";
42}
43
44/// Rich-mode depth budget used by [`examples_from_grammar`] for the
45/// composite program: rule expansions beyond this depth continue
46/// minimally.
47pub const COMPOSITE_DEPTH: u32 = 2;
48
49/// One rule's minimal example.
50#[derive(Debug, Clone)]
51pub struct RuleExample {
52    /// Rule name (for `schema_gen` grammars: the variant name).
53    pub rule: String,
54    /// Input text accepted by the grammar, entering at this rule.
55    pub text: String,
56}
57
58/// Everything [`examples_from_grammar`] synthesizes for one grammar.
59#[derive(Debug, Clone)]
60pub struct GrammarExamples {
61    /// Minimal example per non-start rule, in rule declaration order.
62    /// For `schema_gen` grammars this is exactly one example per
63    /// variant.
64    pub per_rule: Vec<RuleExample>,
65    /// One depth-capped rich expansion of the start rule, showing
66    /// nesting and repetition.
67    pub composite: String,
68}
69
70/// Synthesizes [`GrammarExamples`] for `grammar`.
71///
72/// Fails with one [`codes::NO_FINITE_DERIVATION`] diagnostic per
73/// underivable rule (collected, so the author sees the full list), or
74/// [`codes::UNKNOWN_RULE`] on a dangling reference.
75pub 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
115/// Sentinel cost for "no finite derivation".
116const INFINITE: u64 = u64::MAX;
117
118struct Synth<'g> {
119    /// Rule name → body, for `RuleRef` expansion.
120    by_name: HashMap<&'g str, &'g Peg>,
121    /// `(name, body)` in grammar declaration order.
122    rules_in_order: Vec<(String, &'g Peg)>,
123    /// Shortest-derivation token count per rule (fixpoint result).
124    costs: HashMap<String, u64>,
125    /// Running count of keyed entries emitted, so each one can be
126    /// given a distinct key. Interior mutability because emission
127    /// takes `&self` — the alternative, threading a counter through
128    /// every `emit` signature, would put keyed-slot bookkeeping in the
129    /// path of shapes that have nothing to do with it.
130    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        // Shortest-derivation cost fixpoint: start every rule at
145        // INFINITE and relax until stable. Monotone non-increasing and
146        // bounded, so it terminates.
147        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    /// Appends the input tokens of one derivation of `peg`.
187    /// `rich_depth > 0` selects the expansive arm at choices and up to
188    /// two iterations at repeats; `0` is the minimal mode.
189    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            // A keyed entry emits its key then its value, in that
224            // order — the same shape a two-item `Seq` would, since the
225            // primitive adds no syntax of its own (the separator and
226            // brackets around it live in the enclosing grammar).
227            //
228            // The key goes through `emit_key` so that repeated entries
229            // get *distinct* keys. Emitting the plain token text twice
230            // would synthesize `{ "example": …, "example": … }` — text
231            // the grammar accepts but the schema rejects as a
232            // duplicate key, which is precisely the drift this module
233            // exists to prevent.
234            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    /// Emits a keyed entry's key with occurrence number `n` woven in,
244    /// so sibling entries in one map get distinct keys.
245    ///
246    /// Handles the shapes a key production is made of (tokens, `Seq`,
247    /// `Choice`). Anything richer falls through to the generic
248    /// emitter: keys may then collide, but a collision surfaces as a
249    /// `DUPLICATE_KEY` conformance error on the synthesized example
250    /// rather than being papered over here.
251    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    /// Chooses a choice arm: cheapest finite derivation in minimal
278    /// mode, most expensive finite one in rich mode (ties: first).
279    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
298/// Shortest-derivation token count of `peg` under the current rule
299/// cost estimates ([`INFINITE`]-safe saturating arithmetic).
300fn 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        // Sum of both halves, `INFINITE`-poisoned like `Seq`: an entry
336        // whose value has no finite derivation has none either.
337        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
348/// Input text for a keyed entry's key token, occurrence `n`.
349///
350/// Only the two key spellings `schema_gen` emits are disambiguated;
351/// every other pattern (a literal separator like `:`) renders as
352/// usual.
353fn 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
361/// Input text matching one token pattern.
362fn 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
375/// Joins tokens with canonical-syntax spacing: no space before
376/// punctuation that closes or separates (`,` `)` `]` `}` `:` `(`), no
377/// space after an opener (`(` `[` `{`).
378fn 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    /// Same shape matrix as the schema_gen demo: int / string / bool
402    /// fields, One / Optional / Many children, zero-argument variant.
403    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    /// Rich mode expands a keyed slot to two entries; those entries
542    /// must carry *different* keys. Emitting the bare token text twice
543    /// would produce `{ "example": …, "example": … }` — accepted by the
544    /// grammar, rejected by the schema — which is exactly the
545    /// grammar/schema drift machine-derived examples exist to avoid.
546    #[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    /// A keyed entry whose value has no finite derivation poisons the
593    /// entry's cost, so the rule it sits in is reported as underivable
594    /// instead of sending synthesis into an endless expansion.
595    #[test]
596    fn keyed_entry_inherits_an_underivable_value() {
597        let ids = IdGen::new();
598        // `s` can only be written by writing an `s` inside a keyed
599        // entry: no finite string enters the rule.
600        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        // Rich mode picked an expansive variant and expanded at least
627        // one nested child — pin the property, not the exact string.
628        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        // A single variant whose only child is mandatory and recursive:
638        // no finite tree exists.
639        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        // Both the start rule and the variant rule are underivable.
662        assert_eq!(err.diagnostics.len(), 2);
663    }
664}