fluidattacks_blends_domain/stack/resolve/
minimal.rs

1use alloc::collections::{BTreeSet, VecDeque};
2use alloc::vec::Vec;
3
4use crate::stack::resolve::{PartialPath, PathEdge, TransitionError};
5use crate::stack::{StackGraph, StackNode};
6use crate::NodeId;
7
8/// The edges a search from one endpoint tries before it stops by default.
9pub const DEFAULT_MAX_WORK: usize = 2_000;
10
11/// The walks a search found, and the endpoints whose search ran out of work.
12#[derive(Clone, PartialEq, Eq, Debug, Default)]
13#[non_exhaustive]
14pub struct MinimalPartialPaths<'a> {
15    /// The walks found, endpoint by endpoint.
16    pub paths: Vec<PartialPath<'a>>,
17    /// The endpoints whose search stopped with edges left to try.
18    pub exhausted: Vec<NodeId>,
19}
20
21/// Every walk of `graph` from one endpoint to the next, without passing another endpoint,
22/// trying at most `max_work` edges from each endpoint.
23///
24/// Endpoints are references, definitions and the root.
25#[must_use]
26pub fn minimal_partial_paths(graph: &StackGraph, max_work: usize) -> MinimalPartialPaths<'_> {
27    let mut found = MinimalPartialPaths::default();
28    let seeds = graph
29        .nodes
30        .iter()
31        .filter(|(_, node)| is_endpoint(node))
32        .flat_map(|(id, _)| PartialPath::seed(graph, *id));
33    for seed in seeds {
34        let start = seed.start;
35        if paths_from(graph, seed, max_work, &mut found.paths) {
36            found.exhausted.push(start);
37        }
38    }
39    found
40}
41
42fn paths_from<'a>(
43    graph: &'a StackGraph,
44    seed: PartialPath<'a>,
45    max_work: usize,
46    paths: &mut Vec<PartialPath<'a>>,
47) -> bool {
48    let mut visited = BTreeSet::new();
49    let mut queue = VecDeque::from([seed]);
50    let mut left = max_work;
51    while let Some(path) = queue.pop_front() {
52        for (sink, precedence) in graph.successors(path.end) {
53            let Some(rest) = left.checked_sub(1) else {
54                return true;
55            };
56            left = rest;
57            let Ok(next) = append(graph, &path, sink, precedence) else {
58                continue;
59            };
60            if !visited.insert((next.end, next.pre.clone(), next.post.clone())) {
61                continue;
62            }
63            if graph.nodes.get(&sink).is_some_and(is_endpoint) {
64                paths.push(next);
65            } else {
66                queue.push_back(next);
67            }
68        }
69    }
70    false
71}
72
73fn append<'a>(
74    graph: &'a StackGraph,
75    path: &PartialPath<'a>,
76    sink: NodeId,
77    precedence: i64,
78) -> Result<PartialPath<'a>, TransitionError> {
79    let mut next = path.clone();
80    match graph.nodes.get(&sink).ok_or(TransitionError::UnknownNode)? {
81        StackNode::PushSymbol(push) => next.post.symbols.push_front(&push.symbol),
82        StackNode::PopSymbol(pop) => match next.post.symbols.pop_front() {
83            Some(top) if top == pop.symbol => {}
84            Some(_) => return Err(TransitionError::IncorrectPoppedSymbol),
85            None if next.post.variable.is_some() => next.pre.symbols.push_back(&pop.symbol),
86            None => return Err(TransitionError::EmptySymbolStack),
87        },
88        StackNode::Root | StackNode::Scope(_) => {}
89    }
90    next.end = sink;
91    next.edges.push(PathEdge {
92        source: path.end,
93        precedence,
94    });
95    Ok(next)
96}
97
98fn is_endpoint(node: &StackNode) -> bool {
99    node.is_reference() || node.is_definition() || matches!(node, StackNode::Root)
100}
101
102#[cfg(test)]
103mod tests {
104    use super::{minimal_partial_paths, DEFAULT_MAX_WORK};
105    use crate::stack::resolve::{PartialSymbolStack, PathEdge, SymbolStackVariable};
106    use crate::stack::{Definition, StackGraph, StackNode, StackScope, SymbolPop, SymbolPush};
107    use crate::NodeId;
108    use alloc::borrow::ToOwned;
109    use alloc::vec::Vec;
110
111    const ROOT: NodeId = NodeId(1);
112    const REFERENCE: NodeId = NodeId(2);
113    const SCOPE: NodeId = NodeId(3);
114    const OTHER_SCOPE: NodeId = NodeId(4);
115    const DEFINITION: NodeId = NodeId(5);
116    const OTHER_DEFINITION: NodeId = NodeId(6);
117    const RELAY: NodeId = NodeId(7);
118
119    fn push(symbol: &str, is_reference: bool) -> StackNode {
120        StackNode::PushSymbol(SymbolPush {
121            symbol: symbol.to_owned(),
122            precedence: 0,
123            is_reference,
124        })
125    }
126
127    fn pop(symbol: &str) -> StackNode {
128        StackNode::PopSymbol(SymbolPop {
129            symbol: symbol.to_owned(),
130            precedence: 0,
131            definition: Some(Definition::default()),
132            import: None,
133        })
134    }
135
136    fn node(id: NodeId) -> StackNode {
137        match id {
138            ROOT => StackNode::Root,
139            REFERENCE => push("x", true),
140            RELAY => push("m", false),
141            DEFINITION => pop("x"),
142            OTHER_DEFINITION => pop("y"),
143            _ => StackNode::Scope(StackScope::default()),
144        }
145    }
146
147    fn graph(edges: &[(NodeId, NodeId)]) -> StackGraph {
148        let mut graph = StackGraph::new();
149        for (source, sink) in edges {
150            graph.add_node(*source, node(*source));
151            graph.add_node(*sink, node(*sink));
152            graph.add_edge(*source, *sink, 0);
153        }
154        graph
155    }
156
157    fn stack<'a>(symbols: &[&'a str]) -> PartialSymbolStack<'a> {
158        PartialSymbolStack::new(
159            symbols.iter().copied().collect(),
160            Some(SymbolStackVariable::INITIAL),
161        )
162    }
163
164    type Walk<'a> = (
165        NodeId,
166        NodeId,
167        PartialSymbolStack<'a>,
168        PartialSymbolStack<'a>,
169    );
170
171    fn walks(graph: &StackGraph) -> Vec<Walk<'_>> {
172        minimal_partial_paths(graph, DEFAULT_MAX_WORK)
173            .paths
174            .into_iter()
175            .map(|path| (path.start, path.end, path.pre, path.post))
176            .collect()
177    }
178
179    #[test]
180    fn a_reference_reaches_the_definition_of_its_symbol_with_the_stack_as_it_found_it() {
181        assert_eq!(
182            walks(&graph(&[(REFERENCE, SCOPE), (SCOPE, DEFINITION)])),
183            [(REFERENCE, DEFINITION, stack(&[]), stack(&[]))]
184        );
185    }
186
187    #[test]
188    fn a_reference_does_not_reach_the_definition_of_another_symbol() {
189        assert_eq!(
190            walks(&graph(&[(REFERENCE, SCOPE), (SCOPE, OTHER_DEFINITION)])),
191            []
192        );
193    }
194
195    #[test]
196    fn a_definition_reached_from_the_root_needs_its_symbol_on_the_stack() {
197        assert_eq!(
198            walks(&graph(&[(ROOT, DEFINITION)])),
199            [(ROOT, DEFINITION, stack(&["x"]), stack(&[]))]
200        );
201    }
202
203    #[test]
204    fn a_relay_push_leaves_its_symbol_without_ending_the_walk() {
205        assert_eq!(
206            walks(&graph(&[(REFERENCE, RELAY), (RELAY, ROOT)])),
207            [(REFERENCE, ROOT, stack(&[]), stack(&["m", "x"]))]
208        );
209    }
210
211    #[test]
212    fn a_walk_ends_at_the_first_endpoint_it_reaches() {
213        assert_eq!(
214            walks(&graph(&[
215                (SCOPE, ROOT),
216                (ROOT, REFERENCE),
217                (REFERENCE, SCOPE)
218            ])),
219            [
220                (ROOT, REFERENCE, stack(&[]), stack(&["x"])),
221                (REFERENCE, ROOT, stack(&[]), stack(&["x"])),
222            ]
223        );
224    }
225
226    #[test]
227    fn a_cycle_without_endpoints_ends_the_search_without_walks() {
228        assert_eq!(
229            walks(&graph(&[
230                (REFERENCE, SCOPE),
231                (SCOPE, OTHER_SCOPE),
232                (OTHER_SCOPE, SCOPE)
233            ])),
234            []
235        );
236    }
237
238    #[test]
239    fn two_routes_with_the_same_stacks_give_one_walk() {
240        assert_eq!(
241            walks(&graph(&[
242                (REFERENCE, SCOPE),
243                (REFERENCE, OTHER_SCOPE),
244                (SCOPE, DEFINITION),
245                (OTHER_SCOPE, DEFINITION),
246            ])),
247            [(REFERENCE, DEFINITION, stack(&[]), stack(&[]))]
248        );
249    }
250
251    #[test]
252    fn a_walk_follows_its_edges_from_the_start() {
253        let graph = graph(&[(REFERENCE, SCOPE), (SCOPE, DEFINITION)]);
254        let edge = |source| PathEdge {
255            source,
256            precedence: 0,
257        };
258
259        assert_eq!(
260            minimal_partial_paths(&graph, DEFAULT_MAX_WORK)
261                .paths
262                .into_iter()
263                .map(|path| path.edges)
264                .collect::<Vec<_>>(),
265            [Vec::from([edge(REFERENCE), edge(SCOPE)])]
266        );
267    }
268
269    #[test]
270    fn a_cycle_that_keeps_growing_the_stack_stops_at_the_budget_and_reports_its_endpoint() {
271        let graph = graph(&[(REFERENCE, SCOPE), (SCOPE, RELAY), (RELAY, SCOPE)]);
272
273        assert_eq!(minimal_partial_paths(&graph, 100).exhausted, [REFERENCE]);
274    }
275
276    #[test]
277    fn a_search_with_exactly_the_work_it_needs_is_not_exhausted() {
278        let graph = graph(&[(REFERENCE, SCOPE), (SCOPE, DEFINITION)]);
279
280        assert_eq!(minimal_partial_paths(&graph, 2).exhausted, []);
281    }
282
283    #[test]
284    fn a_search_stopped_before_its_last_edge_is_exhausted() {
285        let graph = graph(&[(REFERENCE, SCOPE), (SCOPE, DEFINITION)]);
286
287        assert_eq!(minimal_partial_paths(&graph, 1).exhausted, [REFERENCE]);
288    }
289}
fluidattacks_blends_domain/stack/resolve/minimal.rs

fluidattacks_blends_domain/stack/resolve/
minimal.rs
