parol_runtime/parser_common/
parse_tree_stack.rs

1use std::fmt::{Display, Error, Formatter};
2
3use log::trace;
4
5/// A stack for the parse tree nodes.
6#[derive(Debug, Default)]
7pub struct ParseTreeStack<T: Display> {
8    /// The actual stack.
9    pub stack: Vec<T>,
10}
11
12impl<T: Display> ParseTreeStack<T> {
13    /// Creates a new instance.
14    pub fn new() -> Self {
15        Self { stack: Vec::new() }
16    }
17
18    /// Pushes a node onto the stack.
19    pub fn push(&mut self, node: T) {
20        trace!("ParseTreeStack: Pushing node: {node}");
21        self.stack.push(node);
22    }
23
24    /// Pops a node from the stack.
25    pub fn pop(&mut self) -> Option<T> {
26        let node = self.stack.pop();
27        node.inspect(|n| {
28            trace!("LRParseTreeStack: Popping node: {n}");
29        })
30    }
31
32    /// Returns the node at the top of the stack.
33    pub fn last(&self) -> Option<&T> {
34        self.stack.last()
35    }
36
37    /// Pops nodes from the stack where 'at' is the index of the first node to pop.
38    pub fn split_off(&mut self, at: usize) -> Vec<T> {
39        self.stack.split_off(at)
40    }
41
42    /// Pop n nodes from the stack and calculate n by applying the given function to each node.
43    /// The function returns true if the node should be counted.
44    /// Actually, this function is used to pop n nodes from the stack that are part of the parse
45    /// tree plus additional nodes that are not part of the parse tree, such as skip tokens.
46    pub fn pop_n(&mut self, n: usize, f: impl Fn(&T) -> bool) -> Vec<T> {
47        // len is the split_off index
48        let mut len = 0;
49        // i is the number of nodes to pop
50        let mut i = 0;
51        while i < n && len < self.stack.len() {
52            // Call the function for each node starting from the end and increment the number of
53            // nodes to pop if the function returns true
54            if f(&self.stack[self.stack.len() - 1 - len]) {
55                // Increment the number of counted nodes
56                i += 1;
57            }
58            // Increment the split_off index
59            len += 1;
60        }
61        // Ensure we do not pop more nodes than available
62        if len > self.stack.len() {
63            len = self.stack.len();
64        }
65        // Pop the nodes from the stack at the calculated index
66        self.split_off(self.stack.len() - len)
67    }
68
69    /// Returns the length of the stack.
70    pub fn len(&self) -> usize {
71        self.stack.len()
72    }
73
74    /// Returns true if the stack is empty.
75    pub fn is_empty(&self) -> bool {
76        self.stack.is_empty()
77    }
78
79    /// Pops all nodes from the stack.
80    pub(crate) fn pop_all(&mut self) -> Vec<T> {
81        // use mem::swap to avoid clone
82        let mut stack = Vec::new();
83        std::mem::swap(&mut stack, &mut self.stack);
84        stack
85    }
86}
87
88impl<T: Display> Display for ParseTreeStack<T> {
89    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
90        self.stack
91            .iter()
92            .rev()
93            .enumerate()
94            .try_for_each(|(i, e)| writeln!(f, "{i} - {e}"))
95    }
96}
97
98#[cfg(test)]
99mod tests {
100    use super::*;
101
102    fn init() {
103        let _ = env_logger::builder().is_test(true).try_init();
104    }
105
106    #[test]
107    fn test_push_pop() {
108        init();
109        let mut stack = ParseTreeStack::new();
110        stack.push("a");
111        stack.push("b");
112        stack.push("c");
113        assert_eq!(stack.pop(), Some("c"));
114        assert_eq!(stack.pop(), Some("b"));
115        assert_eq!(stack.pop(), Some("a"));
116        assert_eq!(stack.pop(), None);
117    }
118
119    #[test]
120    fn test_split_off() {
121        init();
122        let mut stack = ParseTreeStack::new();
123        stack.push("a");
124        stack.push("b");
125        stack.push("c");
126        stack.push("d");
127        stack.push("e");
128        let split = stack.split_off(2);
129        assert_eq!(split, vec!["c", "d", "e"]);
130        assert_eq!(stack.stack, vec!["a", "b"]);
131    }
132
133    #[test]
134    fn test_pop_3() {
135        init();
136        let mut stack = ParseTreeStack::new();
137        stack.push("a");
138        stack.push("b");
139        stack.push("c");
140        stack.push("d");
141        stack.push("e");
142        let split = stack.pop_n(3, |_| true);
143        assert_eq!(split, vec!["c", "d", "e"]);
144        assert_eq!(stack.stack, vec!["a", "b"]);
145    }
146
147    #[test]
148    fn test_pop_5() {
149        init();
150        let mut stack = ParseTreeStack::new();
151        stack.push("a");
152        stack.push("b");
153        stack.push("c");
154        stack.push("d");
155        stack.push("e");
156        let split = stack.pop_n(3, |_| false);
157        assert_eq!(split, vec!["a", "b", "c", "d", "e"]);
158        assert_eq!(stack.stack, Vec::<&str>::new());
159    }
160
161    #[test]
162    fn test_pop_n() {
163        init();
164        let mut stack = ParseTreeStack::new();
165        stack.push("a");
166        stack.push("b");
167        stack.push("c");
168        stack.push("d");
169        stack.push("e");
170        // As a test function, we use a function that returns true for all nodes except "d"
171        let split = stack.pop_n(3, |n| *n != "d");
172        // Because the function returns false for "d", we should pop actually 4 nodes
173        assert_eq!(split, vec!["b", "c", "d", "e"]);
174        assert_eq!(stack.stack, vec!["a"]);
175    }
176}
parol_runtime/parser_common/parse_tree_stack.rs

parol_runtime/parser_common/
parse_tree_stack.rs
