meta_language/grammar/inference/
eval.rs

1//! Deterministic evaluation utilities for inferred grammars.
2
3mod metrics;
4mod recognizer;
5mod sampler;
6
7use std::error::Error;
8use std::fmt;
9
10use crate::grammar::Grammar;
11
12/// Decides language membership for a target language.
13pub trait MembershipOracle {
14    /// Returns `true` when `text` belongs to the oracle's language.
15    fn accepts(&self, text: &str) -> bool;
16}
17
18/// [`Grammar`] backed membership oracle.
19#[derive(Clone, Copy, Debug)]
20pub struct GrammarOracle<'g>(pub &'g Grammar);
21
22impl<'g> GrammarOracle<'g> {
23    /// Builds an oracle over `grammar`.
24    #[must_use]
25    pub const fn new(grammar: &'g Grammar) -> Self {
26        Self(grammar)
27    }
28
29    /// Returns `true` when `text` is accepted by the wrapped grammar.
30    #[must_use]
31    pub fn accepts(&self, text: &str) -> bool {
32        <Self as MembershipOracle>::accepts(self, text)
33    }
34}
35
36impl MembershipOracle for GrammarOracle<'_> {
37    fn accepts(&self, text: &str) -> bool {
38        recognizer::accepts(self.0, text)
39    }
40}
41
42/// Deterministic sampler configuration.
43#[derive(Clone, Copy, Debug, PartialEq, Eq)]
44pub struct SampleConfig {
45    /// Deterministic PRNG seed.
46    pub seed: u64,
47    /// Number of derivations to draw before duplicate removal.
48    pub count: usize,
49    /// Maximum non-terminal recursion depth before shortest terminating choices are forced.
50    pub max_depth: usize,
51    /// Maximum generated repetitions for `*`, `+`, and unbounded counted repetition.
52    pub repeat_cap: usize,
53}
54
55impl Default for SampleConfig {
56    fn default() -> Self {
57        Self {
58            seed: 0xD1E5_EED5_17A7_E001,
59            count: 256,
60            max_depth: 16,
61            repeat_cap: 4,
62        }
63    }
64}
65
66/// Primary inference-evaluation metrics.
67#[derive(Clone, Debug, PartialEq)]
68pub struct MetricScores {
69    /// Fraction of inferred samples accepted by the golden oracle.
70    pub precision: f64,
71    /// Fraction of golden samples or held-out positives accepted by the inferred grammar.
72    pub recall: f64,
73    /// Harmonic mean of [`Self::precision`] and [`Self::recall`].
74    pub f1: f64,
75    /// Raw grammar size measured as rule-name symbols plus expression nodes.
76    pub size_symbols: usize,
77    /// Deterministic two-part MDL score in bits; lower is better.
78    pub mdl_bits: f64,
79}
80
81/// Recall source used by an evaluation report.
82#[derive(Clone, Copy, Debug, PartialEq, Eq)]
83pub enum ScoringMode {
84    /// Recall was measured by sampling a golden grammar.
85    GoldenGrammar,
86    /// Recall was measured against held-out positive corpus examples.
87    Corpus,
88}
89
90/// End-to-end benchmark result for one corpus.
91#[derive(Clone, Debug, PartialEq)]
92pub struct BenchmarkReport {
93    /// Corpus identifier.
94    pub corpus: &'static str,
95    /// Metric values for this corpus run.
96    pub scores: MetricScores,
97    /// Number of unique samples/examples considered by precision and recall.
98    pub samples_drawn: usize,
99    /// Sampler seed used for this run.
100    pub seed: u64,
101    /// Recall source used for this report.
102    pub scoring_mode: ScoringMode,
103}
104
105/// Evaluation failure.
106#[derive(Clone, Debug, PartialEq, Eq)]
107pub enum EvalError {
108    /// The grammar has no start rule to sample or recognize.
109    EmptyGrammar,
110    /// Corpus-mode recall was requested without held-out positive examples.
111    EmptyCorpus,
112    /// Sampling produced no unique strings for the named source.
113    EmptySample {
114        /// Source that produced no samples.
115        source: &'static str,
116    },
117    /// A reachable rule cannot produce a finite string.
118    NonTerminating {
119        /// Rule name that cannot terminate.
120        rule: String,
121    },
122    /// A reachable non-terminal references a missing rule.
123    UnknownRule {
124        /// Missing rule name.
125        rule: String,
126    },
127    /// A character range has its start after its end.
128    InvalidCharRange {
129        /// Inclusive range start.
130        start: char,
131        /// Inclusive range end.
132        end: char,
133    },
134    /// A character class has no character that the sampler can emit.
135    EmptyCharClass,
136    /// A counted repetition has a maximum smaller than its minimum.
137    InvalidRepeat {
138        /// Minimum repetition count.
139        min: usize,
140        /// Maximum repetition count.
141        max: usize,
142    },
143    /// A named corpus was not registered.
144    CorpusNotFound {
145        /// Requested corpus name.
146        corpus: String,
147    },
148}
149
150impl fmt::Display for EvalError {
151    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
152        match self {
153            Self::EmptyGrammar => formatter.write_str("grammar has no start rule"),
154            Self::EmptyCorpus => formatter.write_str("corpus-mode recall requires positives"),
155            Self::EmptySample { source } => write!(formatter, "{source} sampling produced no text"),
156            Self::NonTerminating { rule } => write!(formatter, "rule `{rule}` cannot terminate"),
157            Self::UnknownRule { rule } => write!(formatter, "unknown grammar rule `{rule}`"),
158            Self::InvalidCharRange { start, end } => {
159                write!(formatter, "invalid character range {start:?}..={end:?}")
160            }
161            Self::EmptyCharClass => formatter.write_str("character class has no sampleable member"),
162            Self::InvalidRepeat { min, max } => {
163                write!(formatter, "invalid repetition bounds {min}..={max}")
164            }
165            Self::CorpusNotFound { corpus } => write!(formatter, "unknown corpus `{corpus}`"),
166        }
167    }
168}
169
170impl Error for EvalError {}
171
172/// Registry entry for an in-repository golden corpus.
173#[derive(Clone, Copy, Debug)]
174pub struct GoldenCorpus {
175    name: &'static str,
176    positives: &'static [&'static str],
177    golden_grammar: fn() -> Grammar,
178}
179
180impl GoldenCorpus {
181    /// Builds a corpus descriptor.
182    #[must_use]
183    pub const fn new(
184        name: &'static str,
185        positives: &'static [&'static str],
186        golden_grammar: fn() -> Grammar,
187    ) -> Self {
188        Self {
189            name,
190            positives,
191            golden_grammar,
192        }
193    }
194
195    /// Corpus identifier.
196    #[must_use]
197    pub const fn name(&self) -> &'static str {
198        self.name
199    }
200
201    /// Held-out positive examples for corpus-mode recall or MDL data.
202    #[must_use]
203    pub const fn positives(&self) -> &'static [&'static str] {
204        self.positives
205    }
206
207    /// Builds the corpus golden grammar.
208    #[must_use]
209    pub fn golden_grammar(&self) -> Grammar {
210        (self.golden_grammar)()
211    }
212}
213
214const LIST_POSITIVES: &[&str] = &["a", "b", "a,b", "b,a"];
215const ASSIGNMENT_POSITIVES: &[&str] = &["let a=1;", "let b=2;", "let x=9;"];
216
217/// Built-in smoke corpora for exercising the harness without vendored competitors.
218pub const GOLDEN_CORPORA: &[GoldenCorpus] = &[
219    GoldenCorpus::new("inference-eval:list", LIST_POSITIVES, list_corpus_grammar),
220    GoldenCorpus::new(
221        "inference-eval:assignment",
222        ASSIGNMENT_POSITIVES,
223        assignment_corpus_grammar,
224    ),
225];
226
227/// Generates deterministic strings from `grammar`.
228///
229/// The sampler uses `SplitMix64` with the exact transition implemented in this
230/// module, never system entropy. Duplicate draws are removed while preserving
231/// first-seen order. Reachable rules that cannot emit any finite string return
232/// [`EvalError::NonTerminating`].
233pub fn sample(grammar: &Grammar, config: &SampleConfig) -> Result<Vec<String>, EvalError> {
234    sampler::sample(grammar, config)
235}
236
237/// Evaluates an inferred grammar against a golden oracle.
238///
239/// Precision is the fraction of samples drawn from `inferred` that `golden`
240/// accepts. When `golden_sampler` is present, recall is the fraction of samples
241/// drawn from that grammar that `inferred` accepts. When `golden_sampler` is
242/// absent, recall is the fraction of `positives` accepted by `inferred`.
243pub fn evaluate(
244    inferred: &Grammar,
245    golden: &dyn MembershipOracle,
246    golden_sampler: Option<&Grammar>,
247    positives: &[&str],
248    config: &SampleConfig,
249) -> Result<MetricScores, EvalError> {
250    evaluate_outcome(inferred, golden, golden_sampler, positives, config)
251        .map(|outcome| outcome.scores)
252}
253
254/// Runs one registered corpus against an inferred grammar.
255pub fn run_corpus(
256    corpus: &GoldenCorpus,
257    inferred: &Grammar,
258    config: &SampleConfig,
259) -> Result<BenchmarkReport, EvalError> {
260    let golden = corpus.golden_grammar();
261    let oracle = GrammarOracle(&golden);
262    let outcome = evaluate_outcome(inferred, &oracle, Some(&golden), corpus.positives(), config)?;
263
264    Ok(BenchmarkReport {
265        corpus: corpus.name(),
266        scores: outcome.scores,
267        samples_drawn: outcome.samples_drawn,
268        seed: config.seed,
269        scoring_mode: outcome.scoring_mode,
270    })
271}
272
273/// Runs a registered corpus by name.
274pub fn run_named_corpus(
275    corpus: &str,
276    inferred: &Grammar,
277    config: &SampleConfig,
278) -> Result<BenchmarkReport, EvalError> {
279    let descriptor = GOLDEN_CORPORA
280        .iter()
281        .find(|candidate| candidate.name() == corpus)
282        .ok_or_else(|| EvalError::CorpusNotFound {
283            corpus: corpus.to_string(),
284        })?;
285    run_corpus(descriptor, inferred, config)
286}
287
288/// Counts grammar symbols as rule-name symbols plus expression nodes.
289#[must_use]
290pub fn size_symbols(grammar: &Grammar) -> usize {
291    metrics::size_symbols(grammar)
292}
293
294/// Computes the deterministic two-part MDL score for `grammar` and `data`.
295///
296/// `L(G)` is `size_symbols(G) * ceil(log2(alphabet(G)))`, where the alphabet is
297/// the distinct set of rule names, terminals, character primitives, and grammar
298/// operators. `L(D | G)` uses a fixed deterministic code: accepted examples cost
299/// one emitted-symbol bit per Unicode scalar plus a stop bit; rejected examples
300/// fall back to their UTF-8 byte length plus a 64-bit escape penalty.
301#[must_use]
302pub fn mdl(grammar: &Grammar, data: &[&str]) -> f64 {
303    metrics::mdl(grammar, data)
304}
305
306#[derive(Clone, Debug)]
307struct EvaluationOutcome {
308    scores: MetricScores,
309    samples_drawn: usize,
310    scoring_mode: ScoringMode,
311}
312
313fn evaluate_outcome(
314    inferred: &Grammar,
315    golden: &dyn MembershipOracle,
316    golden_sampler: Option<&Grammar>,
317    positives: &[&str],
318    config: &SampleConfig,
319) -> Result<EvaluationOutcome, EvalError> {
320    let inferred_samples = sample(inferred, config)?;
321    if inferred_samples.is_empty() {
322        return Err(EvalError::EmptySample { source: "inferred" });
323    }
324
325    let precision_hits = inferred_samples
326        .iter()
327        .filter(|text| golden.accepts(text))
328        .count();
329    let precision = metrics::ratio(precision_hits, inferred_samples.len());
330    let inferred_oracle = GrammarOracle(inferred);
331
332    let (recall, mdl_bits, samples_drawn, scoring_mode) =
333        if let Some(golden_grammar) = golden_sampler {
334            let reference_samples = sample(golden_grammar, config)?;
335            if reference_samples.is_empty() {
336                return Err(EvalError::EmptySample { source: "golden" });
337            }
338            let recall_hits = reference_samples
339                .iter()
340                .filter(|text| inferred_oracle.accepts(text))
341                .count();
342            let data = reference_samples
343                .iter()
344                .map(String::as_str)
345                .collect::<Vec<_>>();
346            (
347                metrics::ratio(recall_hits, reference_samples.len()),
348                mdl(inferred, &data),
349                inferred_samples
350                    .len()
351                    .saturating_add(reference_samples.len()),
352                ScoringMode::GoldenGrammar,
353            )
354        } else {
355            if positives.is_empty() {
356                return Err(EvalError::EmptyCorpus);
357            }
358            let recall_hits = positives
359                .iter()
360                .filter(|text| inferred_oracle.accepts(text))
361                .count();
362            (
363                metrics::ratio(recall_hits, positives.len()),
364                mdl(inferred, positives),
365                inferred_samples.len().saturating_add(positives.len()),
366                ScoringMode::Corpus,
367            )
368        };
369
370    let f1 = if precision + recall == 0.0 {
371        0.0
372    } else {
373        2.0 * precision * recall / (precision + recall)
374    };
375
376    Ok(EvaluationOutcome {
377        scores: MetricScores {
378            precision,
379            recall,
380            f1,
381            size_symbols: size_symbols(inferred),
382            mdl_bits,
383        },
384        samples_drawn,
385        scoring_mode,
386    })
387}
388
389fn list_corpus_grammar() -> Grammar {
390    let expr = Grammar::expr();
391    Grammar::builder()
392        .start("list")
393        .rule(
394            "list",
395            expr.seq([
396                expr.nt("item"),
397                expr.rep0(expr.seq([expr.term(","), expr.nt("item")])),
398            ]),
399        )
400        .rule(
401            "item",
402            expr.choice_unordered([expr.term("a"), expr.term("b")]),
403        )
404        .build()
405}
406
407fn assignment_corpus_grammar() -> Grammar {
408    let expr = Grammar::expr();
409    Grammar::builder()
410        .start("assignment")
411        .rule(
412            "assignment",
413            expr.seq([
414                expr.term("let "),
415                expr.nt("letter"),
416                expr.term("="),
417                expr.nt("digit"),
418                expr.term(";"),
419            ]),
420        )
421        .rule("letter", expr.char_range('a', 'z'))
422        .rule("digit", expr.char_range('0', '9'))
423        .build()
424}
meta_language/grammar/inference/eval.rs

meta_language/grammar/inference/
eval.rs
