rusty_alto/algebras/
tag_string.rs

1//! TAG string algebra and its lazy decomposition automaton.
2//!
3//! The domain has two sorts: ordinary strings and pairs of strings separated
4//! by a gap. Operations use the reserved names from Alto's TAG algebra.
5
6use super::{Algebra, Span};
7use crate::{
8    BottomUpTa, CondensedTa, DisplayCodec, FxHashMap, IndexedBottomUpTa, OutputCodec, Signature,
9    StateUniverse, Symbol, SymbolSet, TextVisualizationCodec, TopDownTa, VisualRepresentation,
10};
11use std::{convert::Infallible, fmt};
12
13/// Concatenate two ordinary strings.
14pub const CONC11: &str = "*CONC11*";
15/// Prefix a string to the left component of a string pair.
16pub const CONC12: &str = "*CONC12*";
17/// Append a string to the right component of a string pair.
18pub const CONC21: &str = "*CONC21*";
19/// Fill the gap of a string pair with an ordinary string.
20pub const WRAP21: &str = "*WRAP21*";
21/// Insert one string pair into the gap of another.
22pub const WRAP22: &str = "*WRAP22*";
23/// Constant denoting the empty ordinary string.
24pub const TAG_E: &str = "*E*";
25/// Constant denoting a pair of empty strings.
26pub const TAG_EE: &str = "*EE*";
27
28/// A TAG string-algebra value: either one contiguous string or a pair of strings.
29#[derive(Clone, Debug, PartialEq, Eq, Hash)]
30pub enum TagStringValue<T> {
31    /// One contiguous string.
32    String(Vec<T>),
33    /// Material to the left and right of one gap.
34    Pair(Vec<T>, Vec<T>),
35}
36
37impl<T: fmt::Display> fmt::Display for TagStringValue<T> {
38    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
39        fn words<T: fmt::Display>(f: &mut fmt::Formatter<'_>, values: &[T]) -> fmt::Result {
40            for (index, value) in values.iter().enumerate() {
41                if index > 0 {
42                    f.write_str(" ")?;
43                }
44                write!(f, "{value}")?;
45            }
46            Ok(())
47        }
48
49        match self {
50            Self::String(value) => words(f, value),
51            Self::Pair(left, right) => {
52                f.write_str("[")?;
53                words(f, left)?;
54                f.write_str(" / ")?;
55                words(f, right)?;
56                f.write_str("]")
57            }
58        }
59    }
60}
61
62#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
63enum Operation {
64    Conc11,
65    Conc12,
66    Conc21,
67    Wrap21,
68    Wrap22,
69    E,
70    Ee,
71}
72
73/// Alto-compatible TAG string algebra.
74#[derive(Clone, Debug)]
75pub struct TagStringAlgebra {
76    signature: Signature,
77    operations: FxHashMap<Symbol, Operation>,
78    display_codec: TextVisualizationCodec<DisplayCodec>,
79}
80
81impl TagStringAlgebra {
82    /// Construct an algebra containing all reserved TAG operations.
83    pub fn new() -> Self {
84        Self::with_signature(Signature::new())
85    }
86
87    /// Construct an algebra over an existing target signature.
88    pub fn with_signature(mut signature: Signature) -> Self {
89        let mut operations = FxHashMap::default();
90        for (name, arity, operation) in [
91            (CONC11, 2, Operation::Conc11),
92            (CONC12, 2, Operation::Conc12),
93            (CONC21, 2, Operation::Conc21),
94            (WRAP21, 2, Operation::Wrap21),
95            (WRAP22, 2, Operation::Wrap22),
96            (TAG_E, 0, Operation::E),
97            (TAG_EE, 0, Operation::Ee),
98        ] {
99            let symbol = signature.intern(name.to_owned(), arity).unwrap();
100            operations.insert(symbol, operation);
101        }
102        Self {
103            signature,
104            operations,
105            display_codec: TextVisualizationCodec::new(DisplayCodec),
106        }
107    }
108
109    /// Intern a nullary lexical symbol.
110    pub fn intern_word(&mut self, word: impl Into<String>) -> Symbol {
111        self.signature.intern(word.into(), 0).unwrap()
112    }
113
114    /// Resolve an operation or lexical symbol by name.
115    pub fn operation_symbol(&self, name: &str) -> Option<Symbol> {
116        self.signature.get(name)
117    }
118
119    /// Parse whitespace-separated tokens as a contiguous string.
120    pub fn parse_string(&mut self, input: &str) -> TagStringValue<Symbol> {
121        TagStringValue::String(
122            input
123                .split_whitespace()
124                .map(|word| self.intern_word(word.to_owned()))
125                .collect(),
126        )
127    }
128
129    /// Build a lazy decomposition for a contiguous input string.
130    ///
131    /// Complete string-pair values are not parse inputs, matching Alto.
132    pub fn decompose(
133        &self,
134        value: TagStringValue<Symbol>,
135    ) -> Option<TagStringDecompositionAutomaton> {
136        let TagStringValue::String(words) = value else {
137            return None;
138        };
139        Some(TagStringDecompositionAutomaton::new(
140            self.operations.clone(),
141            words,
142        ))
143    }
144}
145
146impl Default for TagStringAlgebra {
147    fn default() -> Self {
148        Self::new()
149    }
150}
151
152fn append<T: Clone>(left: &[T], right: &[T]) -> Vec<T> {
153    let mut result = Vec::with_capacity(left.len() + right.len());
154    result.extend_from_slice(left);
155    result.extend_from_slice(right);
156    result
157}
158
159impl Algebra for TagStringAlgebra {
160    type InternalValue = TagStringValue<Symbol>;
161    type Value = TagStringValue<String>;
162    type ParseError = Infallible;
163
164    fn signature(&self) -> &Signature {
165        &self.signature
166    }
167
168    fn evaluate(
169        &self,
170        symbol: Symbol,
171        children: &[Self::InternalValue],
172    ) -> Option<Self::InternalValue> {
173        use TagStringValue::{Pair, String as One};
174        match self.operations.get(&symbol).copied() {
175            Some(Operation::Conc11) => match children {
176                [One(left), One(right)] => Some(One(append(left, right))),
177                _ => None,
178            },
179            Some(Operation::Conc12) => match children {
180                [One(first), Pair(left, right)] => Some(Pair(append(first, left), right.clone())),
181                _ => None,
182            },
183            Some(Operation::Conc21) => match children {
184                [Pair(left, right), One(second)] => Some(Pair(left.clone(), append(right, second))),
185                _ => None,
186            },
187            Some(Operation::Wrap21) => match children {
188                [Pair(left, right), One(middle)] => Some(One(append(&append(left, middle), right))),
189                _ => None,
190            },
191            Some(Operation::Wrap22) => match children {
192                [
193                    Pair(first_left, first_right),
194                    Pair(second_left, second_right),
195                ] => Some(Pair(
196                    append(first_left, second_left),
197                    append(second_right, first_right),
198                )),
199                _ => None,
200            },
201            Some(Operation::E) if children.is_empty() => Some(One(Vec::new())),
202            Some(Operation::Ee) if children.is_empty() => Some(Pair(Vec::new(), Vec::new())),
203            Some(_) => None,
204            None if children.is_empty() => Some(One(vec![symbol])),
205            None => None,
206        }
207    }
208
209    fn parse_object(&mut self, input: &str) -> Result<Self::InternalValue, Self::ParseError> {
210        Ok(self.parse_string(input))
211    }
212
213    fn to_external(&self, value: &Self::InternalValue) -> Self::Value {
214        let resolve = |values: &[Symbol]| {
215            values
216                .iter()
217                .map(|&symbol| self.signature.resolve(symbol).to_owned())
218                .collect()
219        };
220        match value {
221            TagStringValue::String(words) => TagStringValue::String(resolve(words)),
222            TagStringValue::Pair(left, right) => {
223                TagStringValue::Pair(resolve(left), resolve(right))
224            }
225        }
226    }
227
228    fn visualize(&self, value: &Self::Value) -> VisualRepresentation {
229        self.display_codec.encode(value)
230    }
231}
232
233/// A TAG string decomposition state.
234#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
235pub enum TagSpan {
236    /// One half-open input span.
237    String(Span),
238    /// Two ordered, non-overlapping half-open spans.
239    Pair(Span, Span),
240}
241
242impl fmt::Display for TagSpan {
243    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
244        match self {
245            Self::String(span) => write!(f, "{span}"),
246            Self::Pair(left, right) => write!(
247                f,
248                "[{}-{}, {}-{}]",
249                left.start, left.end, right.start, right.end
250            ),
251        }
252    }
253}
254
255impl TagSpan {
256    fn valid(self, n: usize) -> bool {
257        match self {
258            Self::String(span) => span.start <= span.end && span.end <= n,
259            Self::Pair(left, right) => {
260                left.start <= left.end
261                    && left.end <= right.start
262                    && right.start <= right.end
263                    && right.end <= n
264            }
265        }
266    }
267}
268
269/// Lazy decomposition automaton for a fixed TAG string value.
270#[derive(Clone, Debug)]
271pub struct TagStringDecompositionAutomaton {
272    operations: FxHashMap<Symbol, Operation>,
273    words: Vec<Symbol>,
274    positions_by_word: FxHashMap<Symbol, Vec<usize>>,
275}
276
277impl TagStringDecompositionAutomaton {
278    fn new(operations: FxHashMap<Symbol, Operation>, words: Vec<Symbol>) -> Self {
279        let mut positions_by_word = FxHashMap::default();
280        for (position, &word) in words.iter().enumerate() {
281            positions_by_word
282                .entry(word)
283                .or_insert_with(Vec::new)
284                .push(position);
285        }
286        Self {
287            operations,
288            words,
289            positions_by_word,
290        }
291    }
292
293    /// Return the number of tokens in the fixed input.
294    pub fn len(&self) -> usize {
295        self.words.len()
296    }
297
298    /// Return whether the fixed input is empty.
299    pub fn is_empty(&self) -> bool {
300        self.words.is_empty()
301    }
302
303    fn operation(&self, symbol: Symbol) -> Option<Operation> {
304        self.operations.get(&symbol).copied()
305    }
306
307    fn symbol_for(&self, operation: Operation) -> Symbol {
308        self.operations
309            .iter()
310            .find_map(|(&symbol, &candidate)| (candidate == operation).then_some(symbol))
311            .expect("all TAG operations are registered")
312    }
313
314    fn step_operation(
315        &self,
316        operation: Operation,
317        children: &[TagSpan],
318        out: &mut dyn FnMut(TagSpan),
319    ) {
320        use TagSpan::{Pair, String as One};
321        match (operation, children) {
322            (Operation::Conc11, [One(left), One(right)]) if left.end == right.start => {
323                out(One(Span::new(left.start, right.end)));
324            }
325            (Operation::Conc12, [One(first), Pair(left, right)]) if first.end == left.start => {
326                out(Pair(Span::new(first.start, left.end), *right));
327            }
328            (Operation::Conc21, [Pair(left, right), One(second)]) if right.end == second.start => {
329                out(Pair(*left, Span::new(right.start, second.end)));
330            }
331            (Operation::Wrap21, [Pair(left, right), One(middle)])
332                if left.end == middle.start && middle.end == right.start =>
333            {
334                out(One(Span::new(left.start, right.end)));
335            }
336            (
337                Operation::Wrap22,
338                [
339                    Pair(first_left, first_right),
340                    Pair(second_left, second_right),
341                ],
342            ) if first_left.end == second_left.start && second_right.end == first_right.start => {
343                out(Pair(
344                    Span::new(first_left.start, second_left.end),
345                    Span::new(second_right.start, first_right.end),
346                ));
347            }
348            (Operation::E, []) => {
349                for i in 0..=self.len() {
350                    out(One(Span::new(i, i)));
351                }
352            }
353            (Operation::Ee, []) => {
354                for i in 0..=self.len() {
355                    for j in i..=self.len() {
356                        out(Pair(Span::new(i, i), Span::new(j, j)));
357                    }
358                }
359            }
360            _ => {}
361        }
362    }
363}
364
365impl BottomUpTa for TagStringDecompositionAutomaton {
366    type State = TagSpan;
367
368    fn step(&self, symbol: Symbol, children: &[TagSpan], out: &mut dyn FnMut(TagSpan)) {
369        if let Some(operation) = self.operation(symbol) {
370            self.step_operation(operation, children, &mut |state| {
371                if state.valid(self.len()) {
372                    out(state);
373                }
374            });
375        } else if children.is_empty()
376            && let Some(positions) = self.positions_by_word.get(&symbol)
377        {
378            for &position in positions {
379                out(TagSpan::String(Span::new(position, position + 1)));
380            }
381        }
382    }
383
384    fn is_accepting(&self, state: &TagSpan) -> bool {
385        *state == TagSpan::String(Span::new(0, self.len()))
386    }
387}
388
389impl StateUniverse for TagStringDecompositionAutomaton {
390    fn all_states(&self, out: &mut dyn FnMut(TagSpan)) {
391        let n = self.len();
392        for start in 0..=n {
393            for end in start..=n {
394                out(TagSpan::String(Span::new(start, end)));
395            }
396        }
397        for i in 0..=n {
398            for j in i..=n {
399                for k in j..=n {
400                    for l in k..=n {
401                        out(TagSpan::Pair(Span::new(i, j), Span::new(k, l)));
402                    }
403                }
404            }
405        }
406    }
407}
408
409impl TopDownTa for TagStringDecompositionAutomaton {
410    fn step_topdown(&self, parent: &TagSpan, out: &mut dyn FnMut(Symbol, &[TagSpan])) {
411        use TagSpan::{Pair, String as One};
412        if !parent.valid(self.len()) {
413            return;
414        }
415
416        match *parent {
417            One(span) => {
418                if span.len() == 1 {
419                    out(self.words[span.start], &[]);
420                }
421                if span.is_empty() {
422                    out(self.symbol_for(Operation::E), &[]);
423                }
424                for split in span.start..=span.end {
425                    let children = [
426                        One(Span::new(span.start, split)),
427                        One(Span::new(split, span.end)),
428                    ];
429                    out(self.symbol_for(Operation::Conc11), &children);
430                }
431                for start in span.start..=span.end {
432                    for end in start..=span.end {
433                        let children = [
434                            Pair(Span::new(span.start, start), Span::new(end, span.end)),
435                            One(Span::new(start, end)),
436                        ];
437                        out(self.symbol_for(Operation::Wrap21), &children);
438                    }
439                }
440            }
441            Pair(left, right) => {
442                if left.is_empty() && right.is_empty() {
443                    out(self.symbol_for(Operation::Ee), &[]);
444                }
445                for split in left.start..=left.end {
446                    let children = [
447                        One(Span::new(left.start, split)),
448                        Pair(Span::new(split, left.end), right),
449                    ];
450                    out(self.symbol_for(Operation::Conc12), &children);
451                }
452                for split in right.start..=right.end {
453                    let children = [
454                        Pair(left, Span::new(right.start, split)),
455                        One(Span::new(split, right.end)),
456                    ];
457                    out(self.symbol_for(Operation::Conc21), &children);
458                }
459                for split_left in left.start..=left.end {
460                    for split_right in right.start..=right.end {
461                        let children = [
462                            Pair(
463                                Span::new(left.start, split_left),
464                                Span::new(split_right, right.end),
465                            ),
466                            Pair(
467                                Span::new(split_left, left.end),
468                                Span::new(right.start, split_right),
469                            ),
470                        ];
471                        out(self.symbol_for(Operation::Wrap22), &children);
472                    }
473                }
474            }
475        }
476    }
477
478    fn initial_states(&self, out: &mut dyn FnMut(TagSpan)) {
479        out(TagSpan::String(Span::new(0, self.len())));
480    }
481}
482
483impl CondensedTa for TagStringDecompositionAutomaton {
484    fn condensed_rules(&self, out: &mut dyn FnMut(&[TagSpan], &SymbolSet, TagSpan)) {
485        self.all_states(&mut |state| {
486            self.step_topdown(&state, &mut |symbol, children| {
487                let mut symbols = SymbolSet::new();
488                symbols.insert(symbol);
489                out(children, &symbols, state);
490            });
491        });
492    }
493
494    fn condensed_nullary_rules(&self, out: &mut dyn FnMut(&SymbolSet, TagSpan)) {
495        for (position, &word) in self.words.iter().enumerate() {
496            let mut symbols = SymbolSet::new();
497            symbols.insert(word);
498            out(&symbols, TagSpan::String(Span::new(position, position + 1)));
499        }
500        let mut e = SymbolSet::new();
501        e.insert(self.symbol_for(Operation::E));
502        for i in 0..=self.len() {
503            out(&e, TagSpan::String(Span::new(i, i)));
504        }
505        let mut ee = SymbolSet::new();
506        ee.insert(self.symbol_for(Operation::Ee));
507        for i in 0..=self.len() {
508            for j in i..=self.len() {
509                out(&ee, TagSpan::Pair(Span::new(i, i), Span::new(j, j)));
510            }
511        }
512    }
513
514    fn condensed_rules_by_child(
515        &self,
516        position: usize,
517        state: &TagSpan,
518        out: &mut dyn FnMut(&[TagSpan], &SymbolSet, TagSpan),
519    ) {
520        if position > 1 {
521            return;
522        }
523        self.all_states(&mut |parent| {
524            self.step_topdown(&parent, &mut |symbol, children| {
525                if children.get(position) == Some(state) {
526                    let mut symbols = SymbolSet::new();
527                    symbols.insert(symbol);
528                    out(children, &symbols, parent);
529                }
530            });
531        });
532    }
533}
534
535impl IndexedBottomUpTa for TagStringDecompositionAutomaton {
536    fn step_partial(
537        &self,
538        symbol: Symbol,
539        position: usize,
540        state_at_position: &TagSpan,
541        out: &mut dyn FnMut(&[TagSpan], TagSpan),
542    ) {
543        let Some(operation) = self.operation(symbol) else {
544            return;
545        };
546        if !matches!(
547            operation,
548            Operation::Conc11
549                | Operation::Conc12
550                | Operation::Conc21
551                | Operation::Wrap21
552                | Operation::Wrap22
553        ) || position > 1
554        {
555            return;
556        }
557
558        self.all_states(&mut |partner| {
559            let children = if position == 0 {
560                [*state_at_position, partner]
561            } else {
562                [partner, *state_at_position]
563            };
564            self.step_operation(operation, &children, &mut |parent| {
565                if parent.valid(self.len()) {
566                    out(&children, parent);
567                }
568            });
569        });
570    }
571}
572
573#[cfg(test)]
574mod tests {
575    use super::*;
576
577    #[test]
578    fn displays_string_and_pair_spans_compactly() {
579        assert_eq!(TagSpan::String(Span::new(2, 5)).to_string(), "[2-5]");
580        assert_eq!(
581            TagSpan::Pair(Span::new(2, 3), Span::new(3, 4)).to_string(),
582            "[2-3, 3-4]"
583        );
584    }
585
586    #[test]
587    fn evaluates_all_operations() {
588        let mut algebra = TagStringAlgebra::new();
589        let a = TagStringValue::String(vec![algebra.intern_word("a")]);
590        let b = TagStringValue::String(vec![algebra.intern_word("b")]);
591        let pair = TagStringValue::Pair(
592            vec![algebra.intern_word("l")],
593            vec![algebra.intern_word("r")],
594        );
595
596        let eval = |name, children: &[TagStringValue<Symbol>]| {
597            algebra.evaluate(algebra.operation_symbol(name).unwrap(), children)
598        };
599        assert!(
600            matches!(eval(CONC11, &[a.clone(), b.clone()]), Some(TagStringValue::String(v)) if v.len() == 2)
601        );
602        assert!(
603            matches!(eval(CONC12, &[a.clone(), pair.clone()]), Some(TagStringValue::Pair(l, r)) if l.len() == 2 && r.len() == 1)
604        );
605        assert!(
606            matches!(eval(CONC21, &[pair.clone(), b.clone()]), Some(TagStringValue::Pair(l, r)) if l.len() == 1 && r.len() == 2)
607        );
608        assert!(
609            matches!(eval(WRAP21, &[pair.clone(), b.clone()]), Some(TagStringValue::String(v)) if v.len() == 3)
610        );
611        assert!(
612            matches!(eval(WRAP22, &[pair.clone(), pair.clone()]), Some(TagStringValue::Pair(l, r)) if l.len() == 2 && r.len() == 2)
613        );
614    }
615
616    #[test]
617    fn decomposition_accepts_empty_and_repeated_words() {
618        let mut algebra = TagStringAlgebra::new();
619        let value = algebra.parse_string("a a");
620        let decomp = algebra.decompose(value).unwrap();
621        let a = algebra.signature().get("a").unwrap();
622        let mut states = Vec::new();
623        decomp.step(a, &[], &mut |state| states.push(state));
624        assert_eq!(states.len(), 2);
625
626        let empty_value = algebra.parse_string("");
627        let empty = algebra.decompose(empty_value).unwrap();
628        let e = algebra.operation_symbol(TAG_E).unwrap();
629        let mut empty_states = Vec::new();
630        empty.step(e, &[], &mut |state| empty_states.push(state));
631        assert!(empty_states.iter().any(|state| empty.is_accepting(state)));
632    }
633}
rusty_alto/algebras/tag_string.rs

rusty_alto/algebras/
tag_string.rs
