meta_language/grammar/inference/
sequitur.rs

1//! Sequitur structural compression for a single symbol sequence.
2//!
3//! The implementation follows the two invariants from Nevill-Manning and
4//! Witten's Sequitur algorithm: every live digram is unique, and every generated
5//! rule is referenced more than once. It uses an index-linked arena rather than
6//! reference-counted cells so substitutions and inlining can update local list
7//! boundaries directly. The digram table is a [`BTreeMap`] to keep emitted rule
8//! names and conflict handling deterministic.
9
10use std::collections::{BTreeMap, VecDeque};
11
12use crate::grammar::{Grammar, GrammarExpr, GrammarFormat, GrammarRule};
13
14/// Terminal symbol consumed by [`run_sequitur`].
15pub type Symbol = String;
16
17type NodeId = usize;
18type RuleId = usize;
19
20const START_RULE: RuleId = 0;
21
22/// Runs Sequitur over `sequence` and emits the compressed hierarchy as grammar IR.
23///
24/// The result contains a `start` rule plus zero or more generated `R1`, `R2`, ...
25/// rules. Terminals are emitted as [`GrammarExpr::Terminal`] values, generated
26/// rule references as [`GrammarExpr::NonTerminal`], and the grammar source format
27/// is set to [`GrammarFormat::Inferred`]. The grammar accepts exactly the
28/// concatenation of the input symbols; later inference stages are responsible for
29/// generalising beyond that single sequence.
30#[must_use]
31pub fn run_sequitur(sequence: &[Symbol]) -> Grammar {
32    let mut builder = Sequitur::new();
33    for symbol in sequence {
34        builder.append(symbol.clone());
35    }
36    builder.finish()
37}
38
39#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
40enum SymRef {
41    Terminal(Symbol),
42    Rule(RuleId),
43}
44
45#[derive(Clone, Debug)]
46struct SymbolNode {
47    value: SymRef,
48    prev: Option<NodeId>,
49    next: Option<NodeId>,
50    rule: RuleId,
51    alive: bool,
52}
53
54#[derive(Clone, Debug)]
55struct RuleState {
56    head: Option<NodeId>,
57    tail: Option<NodeId>,
58    active: bool,
59    ref_count: usize,
60}
61
62impl RuleState {
63    const fn active() -> Self {
64        Self {
65            head: None,
66            tail: None,
67            active: true,
68            ref_count: 0,
69        }
70    }
71}
72
73#[derive(Debug)]
74struct Sequitur {
75    nodes: Vec<SymbolNode>,
76    rules: Vec<RuleState>,
77    digrams: BTreeMap<(SymRef, SymRef), NodeId>,
78    digram_queue: VecDeque<NodeId>,
79    utility_queue: VecDeque<RuleId>,
80}
81
82impl Sequitur {
83    fn new() -> Self {
84        Self {
85            nodes: Vec::new(),
86            rules: vec![RuleState::active()],
87            digrams: BTreeMap::new(),
88            digram_queue: VecDeque::new(),
89            utility_queue: VecDeque::new(),
90        }
91    }
92
93    fn append(&mut self, terminal: Symbol) {
94        let node = self.append_node(START_RULE, SymRef::Terminal(terminal));
95        if let Some(prev) = self.nodes[node].prev {
96            self.queue_digram(prev);
97        }
98        self.settle();
99    }
100
101    fn finish(mut self) -> Grammar {
102        self.settle();
103
104        let names = self.final_rule_names();
105        let mut grammar = Grammar::new().with_source_format(GrammarFormat::Inferred);
106        grammar.add_rule(GrammarRule::new(
107            "start",
108            GrammarExpr::Sequence(self.rule_exprs(START_RULE, &names)),
109        ));
110
111        for rule_id in 1..self.rules.len() {
112            if self.rules[rule_id].active {
113                let name = names
114                    .get(&rule_id)
115                    .expect("active generated rules must be named")
116                    .clone();
117                grammar.add_rule(GrammarRule::new(
118                    name,
119                    GrammarExpr::Sequence(self.rule_exprs(rule_id, &names)),
120                ));
121            }
122        }
123
124        grammar.set_start("start");
125        grammar
126    }
127
128    fn settle(&mut self) {
129        while !self.digram_queue.is_empty() || !self.utility_queue.is_empty() {
130            if let Some(start) = self.digram_queue.pop_front() {
131                self.enforce_digram_at(start);
132            } else if let Some(rule_id) = self.utility_queue.pop_front() {
133                self.enforce_rule_utility(rule_id);
134            }
135        }
136    }
137
138    fn append_node(&mut self, rule: RuleId, value: SymRef) -> NodeId {
139        self.increment_ref_in_value(&value);
140
141        let node = self.nodes.len();
142        let prev = self.rules[rule].tail;
143        self.nodes.push(SymbolNode {
144            value,
145            prev,
146            next: None,
147            rule,
148            alive: true,
149        });
150
151        if let Some(prev) = prev {
152            self.nodes[prev].next = Some(node);
153        } else {
154            self.rules[rule].head = Some(node);
155        }
156        self.rules[rule].tail = Some(node);
157
158        node
159    }
160
161    fn insert_node_after(&mut self, previous: NodeId, value: SymRef) -> NodeId {
162        self.increment_ref_in_value(&value);
163
164        let node = self.nodes.len();
165        let rule = self.nodes[previous].rule;
166        let next = self.nodes[previous].next;
167        self.nodes.push(SymbolNode {
168            value,
169            prev: Some(previous),
170            next,
171            rule,
172            alive: true,
173        });
174
175        self.nodes[previous].next = Some(node);
176        if let Some(next) = next {
177            self.nodes[next].prev = Some(node);
178        } else {
179            self.rules[rule].tail = Some(node);
180        }
181
182        node
183    }
184
185    fn enforce_digram_at(&mut self, start: NodeId) {
186        let Some(key) = self.digram_key(start) else {
187            return;
188        };
189
190        let Some(existing) = self.digrams.get(&key).copied() else {
191            self.digrams.insert(key, start);
192            return;
193        };
194
195        if existing == start {
196            return;
197        }
198
199        if self.digram_key(existing).as_ref() != Some(&key) {
200            self.digrams.remove(&key);
201            self.queue_digram(start);
202            return;
203        }
204
205        if self.occurrences_overlap(existing, start) {
206            return;
207        }
208
209        if let Some(rule_id) = self.rule_matching_body(existing) {
210            self.replace_digram_with_rule(start, rule_id);
211        } else {
212            self.create_rule_for_duplicate(key, existing, start);
213        }
214    }
215
216    fn create_rule_for_duplicate(
217        &mut self,
218        key: (SymRef, SymRef),
219        existing: NodeId,
220        current: NodeId,
221    ) {
222        if self.digram_key(existing).as_ref() != Some(&key)
223            || self.digram_key(current).as_ref() != Some(&key)
224        {
225            self.queue_digram(current);
226            return;
227        }
228
229        let rule_id = self.rules.len();
230        self.rules.push(RuleState::active());
231        let first = self.append_node(rule_id, key.0.clone());
232        self.append_node(rule_id, key.1.clone());
233
234        self.replace_digram_with_rule(existing, rule_id);
235        if self.digram_key(current).as_ref() == Some(&key) {
236            self.replace_digram_with_rule(current, rule_id);
237        }
238
239        if self.rules[rule_id].active {
240            self.digrams.insert(key, first);
241            if self.rules[rule_id].ref_count <= 1 {
242                self.queue_utility(rule_id);
243            }
244        }
245    }
246
247    fn replace_digram_with_rule(&mut self, start: NodeId, rule_id: RuleId) {
248        let Some(second) = self.nodes.get(start).and_then(|node| node.next) else {
249            return;
250        };
251        if !self.nodes[start].alive
252            || !self.nodes[second].alive
253            || self.nodes[start].rule != self.nodes[second].rule
254        {
255            return;
256        }
257
258        let containing_rule = self.nodes[start].rule;
259        let prev = self.nodes[start].prev;
260        let next = self.nodes[second].next;
261
262        if let Some(prev) = prev {
263            self.unregister_digram_at(prev);
264        }
265        self.unregister_digram_at(start);
266        self.unregister_digram_at(second);
267
268        let first_value = self.nodes[start].value.clone();
269        let second_value = self.nodes[second].value.clone();
270        self.decrement_ref_in_value(&first_value);
271        self.decrement_ref_in_value(&second_value);
272
273        self.nodes[start].value = SymRef::Rule(rule_id);
274        self.increment_ref(rule_id);
275        self.nodes[start].next = next;
276
277        if let Some(next) = next {
278            self.nodes[next].prev = Some(start);
279        } else {
280            self.rules[containing_rule].tail = Some(start);
281        }
282
283        self.nodes[second].alive = false;
284        self.nodes[second].prev = None;
285        self.nodes[second].next = None;
286
287        if self.rules[containing_rule].head == Some(second) {
288            self.rules[containing_rule].head = Some(start);
289        }
290        if self.rules[containing_rule].tail == Some(second) {
291            self.rules[containing_rule].tail = Some(start);
292        }
293
294        if let Some(prev) = prev {
295            self.queue_digram(prev);
296        }
297        self.queue_digram(start);
298    }
299
300    fn enforce_rule_utility(&mut self, rule_id: RuleId) {
301        if rule_id == START_RULE
302            || !self
303                .rules
304                .get(rule_id)
305                .is_some_and(|rule| rule.active && rule.ref_count <= 1)
306        {
307            return;
308        }
309
310        if self.rules[rule_id].ref_count == 0 {
311            self.delete_rule(rule_id);
312            return;
313        }
314
315        if let Some(reference) = self.find_reference(rule_id) {
316            self.inline_rule_at(reference, rule_id);
317        } else {
318            self.rules[rule_id].ref_count = 0;
319            self.delete_rule(rule_id);
320        }
321    }
322
323    fn inline_rule_at(&mut self, reference: NodeId, rule_id: RuleId) {
324        let body = self.rule_values(rule_id);
325        if body.is_empty() {
326            self.remove_node(reference);
327            self.delete_rule(rule_id);
328            return;
329        }
330
331        let prev = self.nodes[reference].prev;
332        let old_next = self.nodes[reference].next;
333
334        if let Some(prev) = prev {
335            self.unregister_digram_at(prev);
336        }
337        self.unregister_digram_at(reference);
338
339        let old_value = self.nodes[reference].value.clone();
340        self.decrement_ref_in_value(&old_value);
341
342        self.nodes[reference].value = body[0].clone();
343        self.increment_ref_in_value(&body[0]);
344
345        let mut last = reference;
346        for value in body.into_iter().skip(1) {
347            last = self.insert_node_after(last, value);
348        }
349
350        if let Some(prev) = prev {
351            self.queue_digram(prev);
352        }
353        self.queue_inserted_digrams(reference, old_next);
354        self.delete_rule(rule_id);
355    }
356
357    fn remove_node(&mut self, node: NodeId) {
358        if !self.nodes[node].alive {
359            return;
360        }
361
362        let rule = self.nodes[node].rule;
363        let prev = self.nodes[node].prev;
364        let next = self.nodes[node].next;
365
366        if let Some(prev) = prev {
367            self.unregister_digram_at(prev);
368        }
369        self.unregister_digram_at(node);
370
371        let value = self.nodes[node].value.clone();
372        self.decrement_ref_in_value(&value);
373
374        if let Some(prev) = prev {
375            self.nodes[prev].next = next;
376        } else {
377            self.rules[rule].head = next;
378        }
379        if let Some(next) = next {
380            self.nodes[next].prev = prev;
381        } else {
382            self.rules[rule].tail = prev;
383        }
384
385        self.nodes[node].alive = false;
386        self.nodes[node].prev = None;
387        self.nodes[node].next = None;
388
389        if let Some(prev) = prev {
390            self.queue_digram(prev);
391        }
392    }
393
394    fn delete_rule(&mut self, rule_id: RuleId) {
395        if rule_id == START_RULE || !self.rules[rule_id].active {
396            return;
397        }
398
399        let mut cursor = self.rules[rule_id].head;
400        while let Some(node) = cursor {
401            cursor = self.nodes[node].next;
402            self.unregister_digram_at(node);
403        }
404
405        cursor = self.rules[rule_id].head;
406        while let Some(node) = cursor {
407            cursor = self.nodes[node].next;
408            let value = self.nodes[node].value.clone();
409            self.decrement_ref_in_value(&value);
410            self.nodes[node].alive = false;
411            self.nodes[node].prev = None;
412            self.nodes[node].next = None;
413        }
414
415        self.rules[rule_id].head = None;
416        self.rules[rule_id].tail = None;
417        self.rules[rule_id].active = false;
418        self.rules[rule_id].ref_count = 0;
419    }
420
421    fn find_reference(&self, rule_id: RuleId) -> Option<NodeId> {
422        self.nodes.iter().enumerate().find_map(|(node_id, node)| {
423            (node.alive && node.value == SymRef::Rule(rule_id)).then_some(node_id)
424        })
425    }
426
427    fn queue_inserted_digrams(&mut self, first: NodeId, old_next: Option<NodeId>) {
428        let mut cursor = Some(first);
429        while let Some(node) = cursor {
430            self.queue_digram(node);
431            if self.nodes[node].next == old_next {
432                break;
433            }
434            cursor = self.nodes[node].next;
435        }
436    }
437
438    fn queue_digram(&mut self, start: NodeId) {
439        if self.nodes.get(start).is_some_and(|node| node.alive) {
440            self.digram_queue.push_back(start);
441        }
442    }
443
444    fn queue_utility(&mut self, rule_id: RuleId) {
445        if rule_id != START_RULE {
446            self.utility_queue.push_back(rule_id);
447        }
448    }
449
450    fn unregister_digram_at(&mut self, start: NodeId) {
451        let Some(key) = self.digram_key(start) else {
452            return;
453        };
454        if self.digrams.get(&key).copied() == Some(start) {
455            self.digrams.remove(&key);
456        }
457    }
458
459    fn digram_key(&self, start: NodeId) -> Option<(SymRef, SymRef)> {
460        let node = self.nodes.get(start)?;
461        if !node.alive {
462            return None;
463        }
464        let next = node.next?;
465        let next_node = self.nodes.get(next)?;
466        if !next_node.alive || next_node.rule != node.rule {
467            return None;
468        }
469
470        Some((node.value.clone(), next_node.value.clone()))
471    }
472
473    fn occurrences_overlap(&self, left: NodeId, right: NodeId) -> bool {
474        left == right
475            || self.nodes[left].next == Some(right)
476            || self.nodes[right].next == Some(left)
477    }
478
479    fn rule_matching_body(&self, start: NodeId) -> Option<RuleId> {
480        let node = self.nodes.get(start)?;
481        let rule_id = node.rule;
482        if rule_id == START_RULE {
483            return None;
484        }
485
486        let next = node.next?;
487        let rule = self.rules.get(rule_id)?;
488        (rule.active && rule.head == Some(start) && rule.tail == Some(next)).then_some(rule_id)
489    }
490
491    fn increment_ref_in_value(&mut self, value: &SymRef) {
492        if let SymRef::Rule(rule_id) = value {
493            self.increment_ref(*rule_id);
494        }
495    }
496
497    fn increment_ref(&mut self, rule_id: RuleId) {
498        if let Some(rule) = self.rules.get_mut(rule_id) {
499            rule.ref_count = rule.ref_count.saturating_add(1);
500        }
501    }
502
503    fn decrement_ref_in_value(&mut self, value: &SymRef) {
504        if let SymRef::Rule(rule_id) = value {
505            self.decrement_ref(*rule_id);
506        }
507    }
508
509    fn decrement_ref(&mut self, rule_id: RuleId) {
510        if rule_id == START_RULE {
511            return;
512        }
513
514        let should_queue = if let Some(rule) = self.rules.get_mut(rule_id) {
515            rule.ref_count = rule.ref_count.saturating_sub(1);
516            rule.active && rule.ref_count <= 1
517        } else {
518            false
519        };
520
521        if should_queue {
522            self.queue_utility(rule_id);
523        }
524    }
525
526    fn final_rule_names(&self) -> BTreeMap<RuleId, String> {
527        let mut names = BTreeMap::from([(START_RULE, "start".to_string())]);
528        let mut next = 1usize;
529
530        for rule_id in 1..self.rules.len() {
531            if self.rules[rule_id].active {
532                names.insert(rule_id, format!("R{next}"));
533                next += 1;
534            }
535        }
536
537        names
538    }
539
540    fn rule_exprs(&self, rule_id: RuleId, names: &BTreeMap<RuleId, String>) -> Vec<GrammarExpr> {
541        self.rule_values(rule_id)
542            .into_iter()
543            .map(|value| Self::symref_to_expr(value, names))
544            .collect()
545    }
546
547    fn rule_values(&self, rule_id: RuleId) -> Vec<SymRef> {
548        let mut values = Vec::new();
549        let mut cursor = self.rules[rule_id].head;
550
551        while let Some(node) = cursor {
552            if self.nodes[node].alive {
553                values.push(self.nodes[node].value.clone());
554            }
555            cursor = self.nodes[node].next;
556        }
557
558        values
559    }
560
561    fn symref_to_expr(value: SymRef, names: &BTreeMap<RuleId, String>) -> GrammarExpr {
562        match value {
563            SymRef::Terminal(value) => GrammarExpr::Terminal(value),
564            SymRef::Rule(rule_id) => GrammarExpr::NonTerminal(
565                names
566                    .get(&rule_id)
567                    .expect("referenced generated rules must be named")
568                    .clone(),
569            ),
570        }
571    }
572}
meta_language/grammar/inference/sequitur.rs

meta_language/grammar/inference/
sequitur.rs
