rusty_alto/combinators/
product.rs

1use crate::{
2    BottomUpTa, DetBottomUpTa, IndexedBottomUpTa, Symbol, TopDownTa, run::cartesian_product,
3};
4use smallvec::SmallVec;
5
6/// Intersection product of two bottom-up automata.
7///
8/// `Product(a, b)` accepts exactly the trees accepted by both component
9/// automata. Its state is a pair `(state_from_a, state_from_b)`.
10///
11/// The generic [`BottomUpTa`] implementation asks both sides for possible
12/// parent states and emits their cartesian product. When both components are
13/// deterministic, `Product` also implements [`DetBottomUpTa`] and avoids that
14/// result-set enumeration. If both components implement
15/// [`IndexedBottomUpTa`], the product also supports indexed rule joins for
16/// sibling-finder-style parsing algorithms.
17#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
18pub struct Product<A, B>(pub A, pub B);
19
20impl<A, B> BottomUpTa for Product<A, B>
21where
22    A: BottomUpTa,
23    B: BottomUpTa,
24{
25    type State = (A::State, B::State);
26
27    fn step(&self, f: Symbol, children: &[Self::State], out: &mut dyn FnMut(Self::State)) {
28        let mut a_children: SmallVec<[A::State; 4]> = SmallVec::new();
29        let mut b_children: SmallVec<[B::State; 4]> = SmallVec::new();
30        for (a, b) in children {
31            a_children.push(a.clone());
32            b_children.push(b.clone());
33        }
34
35        let mut a_results: SmallVec<[A::State; 2]> = SmallVec::new();
36        self.0.step(f, &a_children, &mut |q| a_results.push(q));
37        if a_results.is_empty() {
38            return;
39        }
40
41        let mut b_results: SmallVec<[B::State; 2]> = SmallVec::new();
42        self.1.step(f, &b_children, &mut |q| b_results.push(q));
43        for qa in &a_results {
44            for qb in &b_results {
45                out((qa.clone(), qb.clone()));
46            }
47        }
48    }
49
50    fn is_accepting(&self, q: &Self::State) -> bool {
51        self.0.is_accepting(&q.0) && self.1.is_accepting(&q.1)
52    }
53}
54
55impl<A, B> DetBottomUpTa for Product<A, B>
56where
57    A: DetBottomUpTa,
58    B: DetBottomUpTa,
59{
60    fn step_det(&self, f: Symbol, children: &[Self::State]) -> Option<Self::State> {
61        let mut a_children: SmallVec<[A::State; 4]> = SmallVec::new();
62        let mut b_children: SmallVec<[B::State; 4]> = SmallVec::new();
63        for (a, b) in children {
64            a_children.push(a.clone());
65            b_children.push(b.clone());
66        }
67
68        let qa = self.0.step_det(f, &a_children)?;
69        let qb = self.1.step_det(f, &b_children)?;
70        Some((qa, qb))
71    }
72}
73
74impl<A, B> IndexedBottomUpTa for Product<A, B>
75where
76    A: IndexedBottomUpTa,
77    B: IndexedBottomUpTa,
78{
79    fn step_partial(
80        &self,
81        f: Symbol,
82        position: usize,
83        state_at_position: &Self::State,
84        out: &mut dyn FnMut(&[Self::State], Self::State),
85    ) {
86        self.0
87            .step_partial(f, position, &state_at_position.0, &mut |a_children, qa| {
88                self.1
89                    .step_partial(f, position, &state_at_position.1, &mut |b_children, qb| {
90                        if a_children.len() != b_children.len() {
91                            return;
92                        }
93
94                        let mut children: SmallVec<[Self::State; 4]> =
95                            SmallVec::with_capacity(a_children.len());
96                        for (a_child, b_child) in a_children.iter().zip(b_children) {
97                            children.push((a_child.clone(), b_child.clone()));
98                        }
99                        out(&children, (qa.clone(), qb));
100                    });
101            });
102    }
103}
104
105impl<A, B> TopDownTa for Product<A, B>
106where
107    A: TopDownTa,
108    B: TopDownTa,
109{
110    fn step_topdown(&self, parent: &Self::State, out: &mut dyn FnMut(Symbol, &[Self::State])) {
111        self.0.step_topdown(&parent.0, &mut |a_symbol, a_children| {
112            self.1.step_topdown(&parent.1, &mut |b_symbol, b_children| {
113                if a_symbol != b_symbol || a_children.len() != b_children.len() {
114                    return;
115                }
116
117                let mut children: SmallVec<[Self::State; 4]> =
118                    SmallVec::with_capacity(a_children.len());
119                for (a_child, b_child) in a_children.iter().zip(b_children) {
120                    children.push((a_child.clone(), b_child.clone()));
121                }
122                out(a_symbol, &children);
123            });
124        });
125    }
126
127    fn initial_states(&self, out: &mut dyn FnMut(Self::State)) {
128        let mut left = SmallVec::<[A::State; 4]>::new();
129        let mut right = SmallVec::<[B::State; 4]>::new();
130        self.0.initial_states(&mut |q| left.push(q));
131        self.1.initial_states(&mut |q| right.push(q));
132        for qa in &left {
133            for qb in &right {
134                out((qa.clone(), qb.clone()));
135            }
136        }
137    }
138}
139
140pub(crate) fn product_step_sets<S: Clone>(pools: &[Vec<S>], mut out: impl FnMut(&[S])) {
141    let slices: SmallVec<[&[S]; 4]> = pools.iter().map(Vec::as_slice).collect();
142    cartesian_product(&slices, |tuple| out(tuple));
143}
144
145#[cfg(test)]
146mod tests {
147    use super::*;
148    use crate::{BottomUpTa, DetBottomUpTa, ExplicitBuilder, Symbol};
149
150    #[test]
151    fn product_intersects_languages() {
152        let a = Symbol(0);
153
154        let mut left_b = ExplicitBuilder::new();
155        let left_q = left_b.new_state();
156        left_b.add_rule(a, vec![], left_q);
157        left_b.add_accepting(left_q);
158        let left = left_b.build();
159
160        let mut right_b = ExplicitBuilder::new();
161        let right_q = right_b.new_state();
162        right_b.add_rule(a, vec![], right_q);
163        right_b.add_accepting(right_q);
164        let right = right_b.build();
165
166        let product = Product(left, right);
167        let mut out = Vec::new();
168        product.step(a, &[], &mut |q| out.push(q));
169        assert_eq!(out.len(), 1);
170        assert!(product.is_accepting(&out[0]));
171        assert_eq!(product.step_det(a, &[]), Some(out[0]));
172    }
173
174    #[test]
175    fn product_rejects_when_one_side_lacks_rule() {
176        let a = Symbol(0);
177        let mut left_b = ExplicitBuilder::new();
178        let left_q = left_b.new_state();
179        left_b.add_rule(a, vec![], left_q);
180        left_b.add_accepting(left_q);
181
182        let mut right_b = ExplicitBuilder::new();
183        right_b.new_state();
184
185        let product = Product(left_b.build(), right_b.build());
186        let mut out = Vec::new();
187        product.step(a, &[], &mut |q| out.push(q));
188        assert!(out.is_empty());
189    }
190
191    #[test]
192    fn indexed_product_joins_matching_partial_rules() {
193        let a = Symbol(0);
194        let f = Symbol(1);
195
196        let mut left_b = ExplicitBuilder::new();
197        let left_leaf = left_b.new_state();
198        let left_root = left_b.new_state();
199        left_b.add_rule(a, vec![], left_leaf);
200        left_b.add_rule(f, vec![left_leaf, left_leaf], left_root);
201        let left = left_b.build();
202
203        let mut right_b = ExplicitBuilder::new();
204        let right_leaf = right_b.new_state();
205        let right_root = right_b.new_state();
206        right_b.add_rule(a, vec![], right_leaf);
207        right_b.add_rule(f, vec![right_leaf, right_leaf], right_root);
208        let right = right_b.build();
209
210        let product = Product(left, right);
211        let child = (left_leaf, right_leaf);
212        let mut found = Vec::new();
213        product.step_partial(f, 0, &child, &mut |children, result| {
214            found.push((children.to_vec(), result));
215        });
216
217        assert_eq!(found, vec![(vec![child, child], (left_root, right_root))]);
218    }
219
220    #[test]
221    fn product_topdown_joins_by_parent_and_symbol() {
222        let a = Symbol(0);
223
224        let mut left_b = ExplicitBuilder::new();
225        let left_q = left_b.new_state();
226        left_b.add_rule(a, vec![], left_q);
227        left_b.add_accepting(left_q);
228
229        let mut right_b = ExplicitBuilder::new();
230        let right_q = right_b.new_state();
231        right_b.add_rule(a, vec![], right_q);
232        right_b.add_accepting(right_q);
233
234        let product = Product(left_b.build(), right_b.build());
235        let parent = (left_q, right_q);
236        let mut rules = Vec::new();
237        product.step_topdown(&parent, &mut |symbol, children| {
238            rules.push((symbol, children.to_vec()));
239        });
240
241        assert_eq!(rules, vec![(a, Vec::new())]);
242    }
243}
rusty_alto/combinators/product.rs

rusty_alto/combinators/
product.rs
