fluidattacks_blends_domain/stack/resolve/
partial.rs

1use alloc::collections::{BTreeMap, VecDeque};
2use core::cmp::Ordering;
3
4use crate::stack::resolve::SymbolStackVariable;
5
6/// A symbol stack pattern: known symbols, top first, over an optional unknown rest.
7#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Default)]
8#[non_exhaustive]
9pub struct PartialSymbolStack<'a> {
10    /// The known symbols, top first.
11    pub symbols: VecDeque<&'a str>,
12    /// The unknown rest below them; `None` when the stack ends there.
13    pub variable: Option<SymbolStackVariable>,
14}
15
16/// The symbol stack each variable of unified partial stacks stands for.
17#[derive(Clone, PartialEq, Eq, Debug, Default)]
18#[non_exhaustive]
19pub struct PartialBindings<'a> {
20    /// The symbol stack each variable stands for.
21    pub symbols: BTreeMap<SymbolStackVariable, PartialSymbolStack<'a>>,
22}
23
24/// Two partial symbol stacks have no stack in common.
25#[derive(Clone, Copy, PartialEq, Eq, Debug)]
26#[non_exhaustive]
27pub struct UnifyError;
28
29impl<'a> PartialSymbolStack<'a> {
30    /// `symbols`, top first, over `variable`.
31    #[must_use]
32    pub fn new(symbols: VecDeque<&'a str>, variable: Option<SymbolStackVariable>) -> Self {
33        Self { symbols, variable }
34    }
35
36    /// Only the unknown rest `variable`.
37    #[must_use]
38    pub fn from_variable(variable: SymbolStackVariable) -> Self {
39        Self::new(VecDeque::new(), Some(variable))
40    }
41
42    /// This stack with its variable renumbered `offset` places up; `None` past the last number.
43    #[must_use]
44    pub fn with_offset(&self, offset: u32) -> Option<Self> {
45        let variable = self.variable.map_or(Some(None), |variable| {
46            variable.with_offset(offset).map(Some)
47        })?;
48        Some(Self::new(self.symbols.clone(), variable))
49    }
50
51    /// This stack with its variable replaced by what `bindings` binds it to.
52    #[must_use]
53    pub fn apply_bindings(&self, bindings: &PartialBindings<'a>) -> Self {
54        self.variable
55            .and_then(|variable| bindings.symbols.get(&variable))
56            .map_or_else(
57                || self.clone(),
58                |bound| {
59                    let bound = bound.apply_bindings(bindings);
60                    Self::new(
61                        self.symbols.iter().chain(&bound.symbols).copied().collect(),
62                        bound.variable,
63                    )
64                },
65            )
66    }
67}
68
69impl<'a> PartialBindings<'a> {
70    /// No variable bound.
71    #[must_use]
72    pub fn new() -> Self {
73        Self::default()
74    }
75
76    /// The symbol stack both `lhs` and `rhs` match, binding their variables.
77    ///
78    /// # Errors
79    ///
80    /// Returns [`UnifyError`] when they have no stack in common, leaving the bindings unchanged.
81    pub fn unify(
82        &mut self,
83        lhs: &PartialSymbolStack<'a>,
84        rhs: &PartialSymbolStack<'a>,
85    ) -> Result<PartialSymbolStack<'a>, UnifyError> {
86        let lhs = lhs.apply_bindings(self);
87        let rhs = rhs.apply_bindings(self);
88        if lhs
89            .symbols
90            .iter()
91            .zip(&rhs.symbols)
92            .any(|(left, right)| left != right)
93        {
94            return Err(UnifyError);
95        }
96        let common = lhs.symbols.len().min(rhs.symbols.len());
97        let unified = self.join_rests(&lhs, &rhs, common)?.clone();
98        Ok(unified.apply_bindings(self))
99    }
100
101    fn join_rests<'s>(
102        &mut self,
103        lhs: &'s PartialSymbolStack<'a>,
104        rhs: &'s PartialSymbolStack<'a>,
105        common: usize,
106    ) -> Result<&'s PartialSymbolStack<'a>, UnifyError> {
107        match (
108            lhs.symbols.len().cmp(&rhs.symbols.len()),
109            lhs.variable,
110            rhs.variable,
111        ) {
112            (Ordering::Greater, _, _) => self.bind_rest(rhs.variable, lhs, common).map(|()| lhs),
113            (Ordering::Less, _, _) => self.bind_rest(lhs.variable, rhs, common).map(|()| rhs),
114            (Ordering::Equal, Some(left), Some(right)) if left != right => {
115                self.symbols
116                    .insert(right, PartialSymbolStack::from_variable(left));
117                Ok(lhs)
118            }
119            (Ordering::Equal, None, Some(right)) => {
120                self.symbols.insert(right, PartialSymbolStack::default());
121                Ok(lhs)
122            }
123            (Ordering::Equal, Some(left), None) => {
124                self.symbols.insert(left, PartialSymbolStack::default());
125                Ok(rhs)
126            }
127            (Ordering::Equal, _, _) => Ok(lhs),
128        }
129    }
130
131    fn bind_rest(
132        &mut self,
133        variable: Option<SymbolStackVariable>,
134        longer: &PartialSymbolStack<'a>,
135        common: usize,
136    ) -> Result<(), UnifyError> {
137        let variable = variable
138            .filter(|variable| longer.variable != Some(*variable))
139            .ok_or(UnifyError)?;
140        let rest = PartialSymbolStack::new(
141            longer.symbols.iter().skip(common).copied().collect(),
142            longer.variable,
143        );
144        self.symbols.insert(variable, rest);
145        Ok(())
146    }
147}
148
149#[cfg(test)]
150mod tests {
151    use super::{PartialBindings, PartialSymbolStack, UnifyError};
152    use crate::stack::resolve::SymbolStackVariable;
153    use alloc::collections::BTreeMap;
154
155    fn variable(id: u32) -> SymbolStackVariable {
156        SymbolStackVariable::new(id).unwrap()
157    }
158
159    fn symbols<'a>(names: &[&'a str], variable: Option<u32>) -> PartialSymbolStack<'a> {
160        PartialSymbolStack::new(
161            names.iter().copied().collect(),
162            variable.and_then(SymbolStackVariable::new),
163        )
164    }
165
166    fn unify<'a>(
167        lhs: &PartialSymbolStack<'a>,
168        rhs: &PartialSymbolStack<'a>,
169    ) -> (
170        Result<PartialSymbolStack<'a>, UnifyError>,
171        PartialBindings<'a>,
172    ) {
173        let mut bindings = PartialBindings::new();
174        let unified = bindings.unify(lhs, rhs);
175        (unified, bindings)
176    }
177
178    #[test]
179    fn identical_stacks_unify_to_themselves_without_bindings() {
180        let stack = symbols(&["a", "b"], Some(1));
181
182        assert_eq!(
183            unify(&stack, &stack),
184            (Ok(stack.clone()), PartialBindings::new())
185        );
186    }
187
188    #[test]
189    fn different_symbols_do_not_unify() {
190        assert_eq!(
191            unify(&symbols(&["a"], Some(1)), &symbols(&["b"], Some(2))).0,
192            Err(UnifyError)
193        );
194    }
195
196    #[test]
197    fn a_variable_binds_the_symbols_the_other_stack_has_below_the_common_prefix() {
198        let (unified, bindings) = unify(&symbols(&["a"], Some(1)), &symbols(&["a", "b"], Some(2)));
199
200        assert_eq!(unified, Ok(symbols(&["a", "b"], Some(2))));
201        assert_eq!(
202            bindings.symbols,
203            BTreeMap::from([(variable(1), symbols(&["b"], Some(2)))])
204        );
205    }
206
207    #[test]
208    fn a_longer_left_stack_binds_the_right_variable() {
209        let (unified, bindings) = unify(&symbols(&["a", "b"], None), &symbols(&["a"], Some(1)));
210
211        assert_eq!(unified, Ok(symbols(&["a", "b"], None)));
212        assert_eq!(
213            bindings.symbols,
214            BTreeMap::from([(variable(1), symbols(&["b"], None))])
215        );
216    }
217
218    #[test]
219    fn two_variables_over_the_same_symbols_bind_the_right_one_to_the_left_one() {
220        let (unified, bindings) = unify(&symbols(&["a"], Some(1)), &symbols(&["a"], Some(2)));
221
222        assert_eq!(unified, Ok(symbols(&["a"], Some(1))));
223        assert_eq!(
224            bindings.symbols,
225            BTreeMap::from([(variable(2), symbols(&[], Some(1)))])
226        );
227    }
228
229    #[test]
230    fn a_variable_facing_the_end_of_a_stack_binds_the_empty_stack() {
231        let (unified, bindings) = unify(&symbols(&["a"], Some(1)), &symbols(&["a"], None));
232
233        assert_eq!(unified, Ok(symbols(&["a"], None)));
234        assert_eq!(
235            bindings.symbols,
236            BTreeMap::from([(variable(1), PartialSymbolStack::default())])
237        );
238    }
239
240    #[test]
241    fn a_stack_without_variable_does_not_unify_with_a_longer_one() {
242        assert_eq!(
243            unify(&symbols(&["a"], None), &symbols(&["a", "b"], None)).0,
244            Err(UnifyError)
245        );
246    }
247
248    #[test]
249    fn a_variable_cannot_stand_for_symbols_over_itself() {
250        assert_eq!(
251            unify(&symbols(&[], Some(1)), &symbols(&["a"], Some(1))).0,
252            Err(UnifyError)
253        );
254    }
255
256    #[test]
257    fn a_failed_unification_keeps_the_earlier_bindings() {
258        let mut bindings = PartialBindings::new();
259        bindings
260            .unify(&symbols(&[], Some(1)), &symbols(&["b"], None))
261            .unwrap();
262        let before = bindings.clone();
263
264        assert_eq!(
265            bindings.unify(&symbols(&["a"], Some(2)), &symbols(&["c"], Some(1))),
266            Err(UnifyError)
267        );
268        assert_eq!(bindings, before);
269    }
270
271    #[test]
272    fn a_variable_bound_twice_must_agree_with_its_first_binding() {
273        let mut bindings = PartialBindings::new();
274        bindings
275            .unify(&symbols(&[], Some(1)), &symbols(&["b"], None))
276            .unwrap();
277
278        assert_eq!(
279            bindings.unify(&symbols(&[], Some(1)), &symbols(&["c"], None)),
280            Err(UnifyError)
281        );
282    }
283
284    #[test]
285    fn an_alias_resolves_to_what_its_target_is_bound_to_later() {
286        let mut bindings = PartialBindings::new();
287        bindings
288            .unify(&symbols(&[], Some(2)), &symbols(&[], Some(1)))
289            .unwrap();
290        bindings
291            .unify(&symbols(&[], Some(2)), &symbols(&["a"], None))
292            .unwrap();
293
294        assert_eq!(
295            symbols(&[], Some(1)).apply_bindings(&bindings),
296            symbols(&["a"], None)
297        );
298    }
299
300    #[test]
301    fn a_variable_cannot_stand_for_symbols_over_its_alias() {
302        let mut bindings = PartialBindings::new();
303        bindings
304            .unify(&symbols(&[], Some(2)), &symbols(&[], Some(1)))
305            .unwrap();
306
307        assert_eq!(
308            bindings.unify(&symbols(&[], Some(2)), &symbols(&["a"], Some(1))),
309            Err(UnifyError)
310        );
311    }
312
313    #[test]
314    fn a_variable_bound_through_an_alias_must_agree_with_its_first_binding() {
315        let mut bindings = PartialBindings::new();
316        bindings
317            .unify(&symbols(&[], Some(2)), &symbols(&[], Some(1)))
318            .unwrap();
319        bindings
320            .unify(&symbols(&[], Some(2)), &symbols(&["a"], None))
321            .unwrap();
322
323        assert_eq!(
324            bindings.unify(&symbols(&[], Some(1)), &symbols(&["b"], None)),
325            Err(UnifyError)
326        );
327    }
328
329    #[test]
330    fn applying_bindings_replaces_the_variable_with_its_stack() {
331        let mut bindings = PartialBindings::new();
332        bindings
333            .symbols
334            .insert(variable(1), symbols(&["b"], Some(2)));
335
336        assert_eq!(
337            symbols(&["a"], Some(1)).apply_bindings(&bindings),
338            symbols(&["a", "b"], Some(2))
339        );
340    }
341
342    #[test]
343    fn an_unbound_variable_stays_after_applying_bindings() {
344        let stack = symbols(&["a"], Some(1));
345
346        assert_eq!(stack.apply_bindings(&PartialBindings::new()), stack);
347    }
348
349    #[test]
350    fn an_offset_renumbers_the_variable_up() {
351        assert_eq!(
352            symbols(&["a"], Some(1)).with_offset(2),
353            Some(symbols(&["a"], Some(3)))
354        );
355    }
356
357    #[test]
358    fn an_offset_past_the_last_number_gives_no_stack() {
359        assert_eq!(symbols(&["a"], Some(u32::MAX)).with_offset(1), None);
360    }
361}
fluidattacks_blends_domain/stack/resolve/partial.rs

fluidattacks_blends_domain/stack/resolve/
partial.rs
