meta_language/grammar/inference/
prior.rs

1//! Delimiter-skeleton structural prior for positive grammar inference.
2
3use std::collections::BTreeSet;
4
5use super::lexical::{categorise, CharCategory};
6use crate::{LinkNetwork, ParseConfiguration};
7
8const PRIOR_LANGUAGE: &str = "grammar-prior";
9
10/// Half-open byte span `[start, end)` into the owning example string.
11#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
12pub struct ByteSpan {
13    /// First byte in the span.
14    pub start: usize,
15    /// Byte immediately after the span.
16    pub end: usize,
17}
18
19impl ByteSpan {
20    /// Creates a byte span.
21    ///
22    /// # Panics
23    ///
24    /// Panics when `start` is greater than `end`.
25    #[must_use]
26    pub const fn new(start: usize, end: usize) -> Self {
27        assert!(start <= end, "byte span start must not exceed end");
28        Self { start, end }
29    }
30
31    /// Returns `true` when the span contains no bytes.
32    #[must_use]
33    pub const fn is_empty(self) -> bool {
34        self.start == self.end
35    }
36}
37
38/// The kind of an opaque terminal leaf.
39#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
40pub enum LeafKind {
41    /// Unquoted text.
42    Text,
43    /// Single-quoted text kept opaque.
44    SingleQuote,
45    /// Double-quoted text kept opaque.
46    DoubleQuote,
47    /// Backtick-quoted text kept opaque.
48    Backtick,
49}
50
51/// Delimiter family for a seed-tree group.
52#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
53pub enum Delimiter {
54    /// Parenthesized `(...)` group.
55    Paren,
56    /// Curly-braced `{...}` group.
57    Curly,
58    /// Square-bracketed `[...]` group.
59    Square,
60    /// Synthetic root wrapping one whole example.
61    Root,
62}
63
64/// One node of a seed parse tree over a single example string.
65#[derive(Clone, Debug, PartialEq, Eq)]
66pub enum SeedNode {
67    /// An opaque terminal slice.
68    Leaf {
69        /// Span of the leaf in the owning example.
70        span: ByteSpan,
71        /// Leaf classification.
72        kind: LeafKind,
73    },
74    /// A bracketed or synthetic grouped constituent.
75    Group {
76        /// Delimiter family that produced this group.
77        delimiter: Delimiter,
78        /// Ordered child nodes.
79        children: Vec<Self>,
80        /// Span of the group in the owning example.
81        span: ByteSpan,
82    },
83}
84
85/// One positive example paired with its seed tree.
86#[derive(Clone, Debug, PartialEq, Eq)]
87pub struct SeedTree {
88    /// Original example string.
89    pub example: String,
90    /// Synthetic root group for the example.
91    pub root: SeedNode,
92}
93
94/// A batch of seed trees plus the shared terminal alphabet.
95#[derive(Clone, Debug, PartialEq, Eq)]
96pub struct StructuralPrior {
97    /// One seed tree per input example, preserving input order.
98    pub trees: Vec<SeedTree>,
99    /// Distinct terminal slices observed across all leaves, sorted lexicographically.
100    pub alphabet: Vec<String>,
101}
102
103/// Whitespace policy for text leaves.
104#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
105pub enum WhitespacePolicy {
106    /// Strip ASCII whitespace around text runs and split internal runs into fine leaves.
107    #[default]
108    Trim,
109    /// Keep each text run as one verbatim leaf.
110    Keep,
111}
112
113/// Configuration for structural-prior construction.
114#[derive(Clone, Copy, Debug, PartialEq, Eq)]
115pub struct PriorOptions {
116    /// Merge each text run into a single leaf after whitespace handling.
117    pub coalesce_runs: bool,
118    /// Whitespace handling for text runs.
119    pub whitespace: WhitespacePolicy,
120}
121
122impl Default for PriorOptions {
123    fn default() -> Self {
124        Self {
125            coalesce_runs: false,
126            whitespace: WhitespacePolicy::Trim,
127        }
128    }
129}
130
131/// Builds the delimiter-skeleton structural prior for positive examples.
132#[must_use]
133pub fn build_structural_prior(examples: &[String], opts: PriorOptions) -> StructuralPrior {
134    let mut alphabet = BTreeSet::new();
135    let trees = examples
136        .iter()
137        .map(|example| {
138            let root = build_seed_root(example, opts);
139            collect_alphabet(&root, example, &mut alphabet);
140            SeedTree {
141                example: example.clone(),
142                root,
143            }
144        })
145        .collect();
146
147    StructuralPrior {
148        trees,
149        alphabet: alphabet.into_iter().collect(),
150    }
151}
152
153fn build_seed_root(example: &str, opts: PriorOptions) -> SeedNode {
154    let _skeleton = skeletonise(example);
155    let children = DelimiterParser::new(example, opts)
156        .parse()
157        .unwrap_or_else(|()| flat_leaves(example, opts));
158
159    SeedNode::Group {
160        delimiter: Delimiter::Root,
161        children,
162        span: ByteSpan::new(0, example.len()),
163    }
164}
165
166fn skeletonise(text: &str) -> LinkNetwork {
167    LinkNetwork::parse(text, PRIOR_LANGUAGE, ParseConfiguration::default())
168}
169
170struct DelimiterParser<'input> {
171    text: &'input str,
172    opts: PriorOptions,
173    cursor: usize,
174}
175
176impl<'input> DelimiterParser<'input> {
177    const fn new(text: &'input str, opts: PriorOptions) -> Self {
178        Self {
179            text,
180            opts,
181            cursor: 0,
182        }
183    }
184
185    fn parse(mut self) -> Result<Vec<SeedNode>, ()> {
186        self.parse_children_until(None)
187    }
188
189    fn parse_children_until(&mut self, closing: Option<char>) -> Result<Vec<SeedNode>, ()> {
190        let mut children = Vec::new();
191        while self.cursor < self.text.len() {
192            let character = self.current_char().expect("cursor is inside text");
193            if Some(character) == closing {
194                self.advance_char();
195                return Ok(children);
196            }
197
198            match character {
199                '(' => children.push(self.parse_group(Delimiter::Paren, ')')?),
200                '{' => children.push(self.parse_group(Delimiter::Curly, '}')?),
201                '[' => children.push(self.parse_group(Delimiter::Square, ']')?),
202                ')' | '}' | ']' => return Err(()),
203                '\'' | '"' | '`' => children.push(self.parse_quoted(character)?),
204                _ => children.extend(self.parse_text_run()),
205            }
206        }
207
208        if closing.is_some() {
209            Err(())
210        } else {
211            Ok(children)
212        }
213    }
214
215    fn parse_group(&mut self, delimiter: Delimiter, closing: char) -> Result<SeedNode, ()> {
216        let start = self.cursor;
217        self.advance_char();
218        let children = self.parse_children_until(Some(closing))?;
219
220        Ok(SeedNode::Group {
221            delimiter,
222            children,
223            span: ByteSpan::new(start, self.cursor),
224        })
225    }
226
227    fn parse_quoted(&mut self, quote: char) -> Result<SeedNode, ()> {
228        let start = self.cursor;
229        let end = quoted_end(self.text, start, quote).ok_or(())?;
230        self.cursor = end;
231
232        Ok(SeedNode::Leaf {
233            span: ByteSpan::new(start, end),
234            kind: quote_kind(quote),
235        })
236    }
237
238    fn parse_text_run(&mut self) -> Vec<SeedNode> {
239        let start = self.cursor;
240        while self.cursor < self.text.len() {
241            let character = self.current_char().expect("cursor is inside text");
242            if is_structural_delimiter(character) || is_quote(character) {
243                break;
244            }
245            self.advance_char();
246        }
247        text_leaves(self.text, start, self.cursor, self.opts)
248    }
249
250    fn current_char(&self) -> Option<char> {
251        self.text[self.cursor..].chars().next()
252    }
253
254    fn advance_char(&mut self) {
255        self.cursor += self
256            .current_char()
257            .expect("cursor is inside text")
258            .len_utf8();
259    }
260}
261
262fn flat_leaves(text: &str, opts: PriorOptions) -> Vec<SeedNode> {
263    let mut leaves = Vec::new();
264    let mut cursor = 0;
265    let mut text_start = 0;
266
267    while cursor < text.len() {
268        let character = text[cursor..]
269            .chars()
270            .next()
271            .expect("cursor is inside text");
272        if is_quote(character) {
273            if let Some(end) = quoted_end(text, cursor, character) {
274                leaves.extend(text_leaves(text, text_start, cursor, opts));
275                leaves.push(SeedNode::Leaf {
276                    span: ByteSpan::new(cursor, end),
277                    kind: quote_kind(character),
278                });
279                cursor = end;
280                text_start = cursor;
281                continue;
282            }
283        }
284
285        cursor += character.len_utf8();
286    }
287
288    leaves.extend(text_leaves(text, text_start, text.len(), opts));
289    leaves
290}
291
292fn text_leaves(text: &str, start: usize, end: usize, opts: PriorOptions) -> Vec<SeedNode> {
293    if start == end {
294        return Vec::new();
295    }
296
297    match opts.whitespace {
298        WhitespacePolicy::Keep => text_leaf(start, end).into_iter().collect(),
299        WhitespacePolicy::Trim if opts.coalesce_runs => trim_ascii_span(text, start, end)
300            .and_then(|(trimmed_start, trimmed_end)| text_leaf(trimmed_start, trimmed_end))
301            .into_iter()
302            .collect(),
303        WhitespacePolicy::Trim => split_trimmed_text(text, start, end),
304    }
305}
306
307fn split_trimmed_text(text: &str, start: usize, end: usize) -> Vec<SeedNode> {
308    let mut leaves = Vec::new();
309    let mut cursor = start;
310
311    while cursor < end {
312        cursor = skip_ascii_whitespace(text, cursor, end);
313        if cursor >= end {
314            break;
315        }
316
317        let token_start = cursor;
318        let token_category = current_category(text, cursor);
319        cursor += current_char(text, cursor).len_utf8();
320
321        if !is_atomic(token_category) {
322            while cursor < end {
323                let next = current_char(text, cursor);
324                if next.is_ascii_whitespace() {
325                    break;
326                }
327
328                let next_category = categorise(next);
329                if continues_text_token(token_category, next_category) {
330                    cursor += next.len_utf8();
331                } else {
332                    break;
333                }
334            }
335        }
336
337        leaves.push(SeedNode::Leaf {
338            span: ByteSpan::new(token_start, cursor),
339            kind: LeafKind::Text,
340        });
341    }
342
343    leaves
344}
345
346fn trim_ascii_span(text: &str, start: usize, end: usize) -> Option<(usize, usize)> {
347    let trimmed_start = skip_ascii_whitespace(text, start, end);
348    let mut trimmed_end = end;
349
350    while trimmed_start < trimmed_end {
351        let character_start = previous_char_start(text, trimmed_start, trimmed_end);
352        let character = current_char(text, character_start);
353        if !character.is_ascii_whitespace() {
354            break;
355        }
356        trimmed_end = character_start;
357    }
358
359    (trimmed_start < trimmed_end).then_some((trimmed_start, trimmed_end))
360}
361
362fn skip_ascii_whitespace(text: &str, mut cursor: usize, end: usize) -> usize {
363    while cursor < end {
364        let character = current_char(text, cursor);
365        if !character.is_ascii_whitespace() {
366            break;
367        }
368        cursor += character.len_utf8();
369    }
370    cursor
371}
372
373fn text_leaf(start: usize, end: usize) -> Option<SeedNode> {
374    (start < end).then_some(SeedNode::Leaf {
375        span: ByteSpan::new(start, end),
376        kind: LeafKind::Text,
377    })
378}
379
380fn quoted_end(text: &str, start: usize, quote: char) -> Option<usize> {
381    let mut cursor = start + quote.len_utf8();
382    while cursor < text.len() {
383        let character = current_char(text, cursor);
384        if character == '\\' {
385            cursor += character.len_utf8();
386            if cursor < text.len() {
387                cursor += current_char(text, cursor).len_utf8();
388            }
389            continue;
390        }
391
392        if character == quote {
393            let close_end = cursor + quote.len_utf8();
394            if text[close_end..].starts_with(quote) {
395                cursor = close_end + quote.len_utf8();
396                continue;
397            }
398            return Some(close_end);
399        }
400
401        cursor += character.len_utf8();
402    }
403
404    None
405}
406
407fn collect_alphabet(node: &SeedNode, example: &str, alphabet: &mut BTreeSet<String>) {
408    match node {
409        SeedNode::Leaf { span, .. } => {
410            alphabet.insert(example[span.start..span.end].to_string());
411        }
412        SeedNode::Group { children, .. } => {
413            for child in children {
414                collect_alphabet(child, example, alphabet);
415            }
416        }
417    }
418}
419
420fn current_char(text: &str, cursor: usize) -> char {
421    text[cursor..]
422        .chars()
423        .next()
424        .expect("cursor is inside text")
425}
426
427fn current_category(text: &str, cursor: usize) -> CharCategory {
428    categorise(current_char(text, cursor))
429}
430
431fn previous_char_start(text: &str, start: usize, end: usize) -> usize {
432    text[start..end]
433        .char_indices()
434        .last()
435        .map_or(start, |(offset, _)| start + offset)
436}
437
438fn continues_text_token(current: CharCategory, next: CharCategory) -> bool {
439    if is_atomic(current) || is_atomic(next) {
440        return false;
441    }
442
443    current == next || (current == CharCategory::Letter && next == CharCategory::Digit)
444}
445
446const fn is_atomic(category: CharCategory) -> bool {
447    matches!(
448        category,
449        CharCategory::Delimiter | CharCategory::Punctuation
450    )
451}
452
453const fn is_structural_delimiter(value: char) -> bool {
454    matches!(value, '(' | ')' | '[' | ']' | '{' | '}')
455}
456
457const fn is_quote(value: char) -> bool {
458    matches!(value, '\'' | '"' | '`')
459}
460
461const fn quote_kind(quote: char) -> LeafKind {
462    match quote {
463        '\'' => LeafKind::SingleQuote,
464        '"' => LeafKind::DoubleQuote,
465        '`' => LeafKind::Backtick,
466        _ => unreachable!(),
467    }
468}
meta_language/grammar/inference/prior.rs

meta_language/grammar/inference/
prior.rs
