fluidattacks_blends_domain/stack/resolve/
path.rs

1use alloc::vec::Vec;
2
3use crate::stack::resolve::{
4    PartialBindings, PartialSymbolStack, SymbolStackVariable, TransitionError, UnifyError,
5};
6use crate::stack::{StackGraph, StackNode};
7use crate::NodeId;
8
9/// An edge a partial path follows.
10#[derive(Clone, Copy, PartialEq, Eq, Debug)]
11#[non_exhaustive]
12pub struct PathEdge {
13    /// The node the edge leaves.
14    pub source: NodeId,
15    /// The edge's precedence.
16    pub precedence: i64,
17}
18
19/// A walk from `start` to `end`: the symbol stack it needs on entry and the one it leaves.
20#[derive(Clone, PartialEq, Eq, Debug)]
21#[non_exhaustive]
22pub struct PartialPath<'a> {
23    /// The node the walk starts at.
24    pub start: NodeId,
25    /// The node the walk ends at.
26    pub end: NodeId,
27    /// The symbol stack the walk needs on entry.
28    pub pre: PartialSymbolStack<'a>,
29    /// The symbol stack the walk leaves.
30    pub post: PartialSymbolStack<'a>,
31    /// The edges followed, in order.
32    pub edges: Vec<PathEdge>,
33}
34
35/// Why two partial paths do not form one walk.
36#[derive(Clone, Copy, PartialEq, Eq, Debug)]
37#[non_exhaustive]
38pub enum PathError {
39    /// The second path does not start where the first one ends.
40    DisjointPaths,
41    /// The node where the paths meet does not match the stacks around it.
42    Transition(TransitionError),
43    /// The stack one path leaves does not match the stack the other needs.
44    Unify(UnifyError),
45    /// The stack left ends in a variable the stack needed lacks.
46    UnboundVariable,
47    /// Renaming the variables apart ran past the last variable number.
48    VariableOverflow,
49}
50
51impl From<TransitionError> for PathError {
52    fn from(error: TransitionError) -> Self {
53        Self::Transition(error)
54    }
55}
56
57impl From<UnifyError> for PathError {
58    fn from(error: UnifyError) -> Self {
59        Self::Unify(error)
60    }
61}
62
63impl PartialPath<'_> {
64    /// This walk followed by `rhs`, which must start where this one ends.
65    ///
66    /// # Errors
67    ///
68    /// Returns the [`PathError`] that keeps the walks apart.
69    pub fn concatenate(&self, graph: &StackGraph, rhs: &Self) -> Result<Self, PathError> {
70        if self.end != rhs.start {
71            return Err(PathError::DisjointPaths);
72        }
73        let largest = self
74            .pre
75            .variable
76            .max(self.post.variable)
77            .map_or(0, SymbolStackVariable::get);
78        let rhs_pre = rhs
79            .pre
80            .with_offset(largest)
81            .ok_or(PathError::VariableOverflow)?;
82        let rhs_post = rhs
83            .post
84            .with_offset(largest)
85            .ok_or(PathError::VariableOverflow)?;
86        let (left, right) = match graph
87            .nodes
88            .get(&self.end)
89            .ok_or(TransitionError::UnknownNode)?
90        {
91            StackNode::PushSymbol(push) => (pop_top(&self.post, &push.symbol)?, rhs_pre),
92            StackNode::PopSymbol(pop) => (self.post.clone(), pop_top(&rhs_pre, &pop.symbol)?),
93            StackNode::Root | StackNode::Scope(_) => (self.post.clone(), rhs_pre),
94        };
95        let mut bindings = PartialBindings::new();
96        bindings.unify(&left, &right)?;
97        let pre = self.pre.apply_bindings(&bindings);
98        let post = rhs_post.apply_bindings(&bindings);
99        if post.variable.is_some() && post.variable != pre.variable {
100            return Err(PathError::UnboundVariable);
101        }
102        Ok(Self {
103            start: self.start,
104            end: rhs.end,
105            pre,
106            post,
107            edges: self.edges.iter().chain(&rhs.edges).copied().collect(),
108        })
109    }
110}
111
112fn pop_top<'a>(
113    symbols: &PartialSymbolStack<'a>,
114    symbol: &str,
115) -> Result<PartialSymbolStack<'a>, TransitionError> {
116    let mut rest = symbols.clone();
117    match rest.symbols.pop_front() {
118        None => Err(TransitionError::EmptySymbolStack),
119        Some(top) if top != symbol => Err(TransitionError::IncorrectPoppedSymbol),
120        Some(_) => Ok(rest),
121    }
122}
123
124#[cfg(test)]
125mod tests {
126    use super::{PartialPath, PathEdge, PathError};
127    use crate::stack::resolve::{
128        PartialSymbolStack, SymbolStackVariable, TransitionError, UnifyError,
129    };
130    use crate::stack::{Definition, StackGraph, StackNode, StackScope, SymbolPop, SymbolPush};
131    use crate::NodeId;
132    use alloc::borrow::ToOwned;
133    use alloc::vec::Vec;
134
135    const PUSH_X: NodeId = NodeId(10);
136    const PUSH_Y: NodeId = NodeId(11);
137    const SCOPE: NodeId = NodeId(20);
138    const OTHER_SCOPE: NodeId = NodeId(21);
139    const POP_X: NodeId = NodeId(30);
140
141    fn push(symbol: &str) -> StackNode {
142        StackNode::PushSymbol(SymbolPush {
143            symbol: symbol.to_owned(),
144            precedence: 0,
145            is_reference: true,
146        })
147    }
148
149    fn graph() -> StackGraph {
150        let mut graph = StackGraph::new();
151        graph.add_node(PUSH_X, push("x"));
152        graph.add_node(PUSH_Y, push("y"));
153        graph.add_node(SCOPE, StackNode::Scope(StackScope::default()));
154        graph.add_node(OTHER_SCOPE, StackNode::Scope(StackScope::default()));
155        graph.add_node(
156            POP_X,
157            StackNode::PopSymbol(SymbolPop {
158                symbol: "x".to_owned(),
159                precedence: 0,
160                definition: Some(Definition::default()),
161                import: None,
162            }),
163        );
164        graph
165    }
166
167    fn symbols<'a>(names: &[&'a str], variable: Option<u32>) -> PartialSymbolStack<'a> {
168        PartialSymbolStack::new(
169            names.iter().copied().collect(),
170            variable.and_then(SymbolStackVariable::new),
171        )
172    }
173
174    fn path<'a>(
175        start: NodeId,
176        end: NodeId,
177        pre: PartialSymbolStack<'a>,
178        post: PartialSymbolStack<'a>,
179    ) -> PartialPath<'a> {
180        PartialPath {
181            start,
182            end,
183            pre,
184            post,
185            edges: Vec::new(),
186        }
187    }
188
189    fn through(start: NodeId, end: NodeId) -> PartialPath<'static> {
190        path(start, end, symbols(&[], Some(1)), symbols(&[], Some(1)))
191    }
192
193    #[test]
194    fn a_reference_path_joined_with_a_definition_path_leaves_the_stack_as_it_was() {
195        let graph = graph();
196        let reference = path(
197            PUSH_X,
198            SCOPE,
199            symbols(&[], Some(1)),
200            symbols(&["x"], Some(1)),
201        );
202        let definition = path(
203            SCOPE,
204            POP_X,
205            symbols(&["x"], Some(1)),
206            symbols(&[], Some(1)),
207        );
208
209        assert_eq!(
210            reference.concatenate(&graph, &definition),
211            Ok(through(PUSH_X, POP_X))
212        );
213    }
214
215    #[test]
216    fn paths_that_do_not_meet_do_not_concatenate() {
217        assert_eq!(
218            through(PUSH_X, SCOPE).concatenate(&graph(), &through(OTHER_SCOPE, POP_X)),
219            Err(PathError::DisjointPaths)
220        );
221    }
222
223    #[test]
224    fn a_push_where_the_paths_meet_is_counted_once() {
225        let graph = graph();
226        let lhs = path(
227            SCOPE,
228            PUSH_X,
229            symbols(&[], Some(1)),
230            symbols(&["x"], Some(1)),
231        );
232        let rhs = path(
233            PUSH_X,
234            PUSH_Y,
235            symbols(&[], Some(1)),
236            symbols(&["y", "x"], Some(1)),
237        );
238
239        assert_eq!(
240            lhs.concatenate(&graph, &rhs).map(|joined| joined.post),
241            Ok(symbols(&["y", "x"], Some(1)))
242        );
243    }
244
245    #[test]
246    fn a_pop_where_the_paths_meet_is_required_once() {
247        let graph = graph();
248        let lhs = path(
249            SCOPE,
250            POP_X,
251            symbols(&["x"], Some(1)),
252            symbols(&[], Some(1)),
253        );
254        let rhs = path(
255            POP_X,
256            OTHER_SCOPE,
257            symbols(&["x"], Some(1)),
258            symbols(&[], Some(1)),
259        );
260
261        assert_eq!(
262            lhs.concatenate(&graph, &rhs).map(|joined| joined.pre),
263            Ok(symbols(&["x"], Some(1)))
264        );
265    }
266
267    #[test]
268    fn a_push_of_another_symbol_where_the_paths_meet_does_not_concatenate() {
269        let lhs = path(
270            SCOPE,
271            PUSH_X,
272            symbols(&[], Some(1)),
273            symbols(&["y"], Some(1)),
274        );
275
276        assert_eq!(
277            lhs.concatenate(&graph(), &through(PUSH_X, PUSH_Y)),
278            Err(PathError::Transition(
279                TransitionError::IncorrectPoppedSymbol
280            ))
281        );
282    }
283
284    #[test]
285    fn a_symbol_left_that_the_next_path_does_not_need_does_not_concatenate() {
286        let lhs = path(
287            PUSH_X,
288            SCOPE,
289            symbols(&[], Some(1)),
290            symbols(&["x"], Some(1)),
291        );
292        let rhs = path(
293            SCOPE,
294            OTHER_SCOPE,
295            symbols(&["y"], Some(1)),
296            symbols(&[], Some(1)),
297        );
298
299        assert_eq!(
300            lhs.concatenate(&graph(), &rhs),
301            Err(PathError::Unify(UnifyError))
302        );
303    }
304
305    #[test]
306    fn the_variables_of_the_second_path_are_renamed_apart_from_the_first() {
307        let graph = graph();
308        let lhs = path(
309            PUSH_X,
310            SCOPE,
311            symbols(&[], Some(1)),
312            symbols(&["x"], Some(1)),
313        );
314        let rhs = path(
315            SCOPE,
316            OTHER_SCOPE,
317            symbols(&[], Some(1)),
318            symbols(&["y"], Some(1)),
319        );
320
321        assert_eq!(
322            lhs.concatenate(&graph, &rhs).map(|joined| joined.post),
323            Ok(symbols(&["y", "x"], Some(1)))
324        );
325    }
326
327    #[test]
328    fn renaming_past_the_last_variable_number_does_not_concatenate() {
329        let rhs = path(
330            SCOPE,
331            OTHER_SCOPE,
332            symbols(&[], Some(u32::MAX)),
333            symbols(&[], Some(u32::MAX)),
334        );
335
336        assert_eq!(
337            through(PUSH_X, SCOPE).concatenate(&graph(), &rhs),
338            Err(PathError::VariableOverflow)
339        );
340    }
341
342    #[test]
343    fn a_variable_left_that_was_not_needed_does_not_concatenate() {
344        let lhs = path(PUSH_X, SCOPE, symbols(&[], None), symbols(&[], Some(1)));
345
346        assert_eq!(
347            lhs.concatenate(&graph(), &through(SCOPE, OTHER_SCOPE)),
348            Err(PathError::UnboundVariable)
349        );
350    }
351
352    #[test]
353    fn the_joined_path_follows_the_edges_of_both_in_order() {
354        let edge = |source| PathEdge {
355            source,
356            precedence: 0,
357        };
358        let lhs = PartialPath {
359            edges: Vec::from([edge(PUSH_X)]),
360            ..through(PUSH_X, SCOPE)
361        };
362        let rhs = PartialPath {
363            edges: Vec::from([edge(SCOPE)]),
364            ..through(SCOPE, OTHER_SCOPE)
365        };
366
367        assert_eq!(
368            lhs.concatenate(&graph(), &rhs).map(|joined| joined.edges),
369            Ok(Vec::from([edge(PUSH_X), edge(SCOPE)]))
370        );
371    }
372}
fluidattacks_blends_domain/stack/resolve/path.rs

fluidattacks_blends_domain/stack/resolve/
path.rs
