1 // pest. The Elegant Parser
2 // Copyright (c) 2018 Dragoș Tiselice
3 //
4 // Licensed under the Apache License, Version 2.0
5 // <LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0> or the MIT
6 // license <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
7 // option. All files in the project carrying such notice may not be copied,
8 // modified, or distributed except according to those terms.
9 
10 use alloc::vec;
11 use alloc::vec::Vec;
12 use core::ops::{Index, Range};
13 
14 /// Implementation of a `Stack` which maintains popped elements and length of previous states
15 /// in order to rewind the stack to a previous state.
16 #[derive(Debug)]
17 pub struct Stack<T: Clone> {
18     /// All elements in the stack.
19     cache: Vec<T>,
20     /// All elements that are in previous snapshots but may not be in the next state.
21     /// They will be pushed back to `cache` if the snapshot is restored,
22     /// otherwise be dropped if the snapshot is cleared.
23     ///
24     /// Those elements from a sequence of snapshots are stacked in one [`Vec`], and
25     /// `popped.len() == lengths.iter().map(|(len, remained)| len - remained).sum()`
26     popped: Vec<T>,
27     /// Every element corresponds to a snapshot, and each element has two fields:
28     /// - Length of `cache` when corresponding snapshot is taken (AKA `len`).
29     /// - Count of elements that come from corresponding snapshot
30     ///   and are still in next snapshot or current state (AKA `remained`).
31     ///
32     /// And `len` is never less than `remained`.
33     ///
34     /// On restoring, the `cache` can be divided into two parts:
35     /// - `0..remained` are untouched since the snapshot is taken.
36     ///
37     ///   There's nothing to do with those elements. Just let them stay where they are.
38     ///
39     /// - `remained..cache.len()` are pushed after the snapshot is taken.
40     lengths: Vec<(usize, usize)>,
41 }
42 
43 impl<T: Clone> Default for Stack<T> {
default() -> Self44     fn default() -> Self {
45         Self::new()
46     }
47 }
48 
49 impl<T: Clone> Stack<T> {
50     /// Creates a new `Stack`.
new() -> Self51     pub fn new() -> Self {
52         Stack {
53             cache: vec![],
54             popped: vec![],
55             lengths: vec![],
56         }
57     }
58 
59     /// Returns `true` if the stack is currently empty.
60     #[allow(dead_code)]
is_empty(&self) -> bool61     pub fn is_empty(&self) -> bool {
62         self.cache.is_empty()
63     }
64 
65     /// Returns the top-most `&T` in the `Stack`.
peek(&self) -> Option<&T>66     pub fn peek(&self) -> Option<&T> {
67         self.cache.last()
68     }
69 
70     /// Pushes a `T` onto the `Stack`.
push(&mut self, elem: T)71     pub fn push(&mut self, elem: T) {
72         self.cache.push(elem);
73     }
74 
75     /// Pops the top-most `T` from the `Stack`.
pop(&mut self) -> Option<T>76     pub fn pop(&mut self) -> Option<T> {
77         let len = self.cache.len();
78         let popped = self.cache.pop();
79         if let Some(popped) = &popped {
80             if let Some((_, remained_count)) = self.lengths.last_mut() {
81                 // `len >= *unpopped_count`
82                 if len == *remained_count {
83                     *remained_count -= 1;
84                     self.popped.push(popped.clone());
85                 }
86             }
87         }
88         popped
89     }
90 
91     /// Returns the size of the stack
len(&self) -> usize92     pub fn len(&self) -> usize {
93         self.cache.len()
94     }
95 
96     /// Takes a snapshot of the current `Stack`.
snapshot(&mut self)97     pub fn snapshot(&mut self) {
98         self.lengths.push((self.cache.len(), self.cache.len()))
99     }
100 
101     /// The parsing after the last snapshot was successful so clearing it.
clear_snapshot(&mut self)102     pub fn clear_snapshot(&mut self) {
103         if let Some((len, unpopped)) = self.lengths.pop() {
104             // Popped elements from previous state are no longer needed.
105             self.popped.truncate(self.popped.len() - (len - unpopped));
106         }
107     }
108 
109     /// Rewinds the `Stack` to the most recent `snapshot()`. If no `snapshot()` has been taken, this
110     /// function return the stack to its initial state.
restore(&mut self)111     pub fn restore(&mut self) {
112         match self.lengths.pop() {
113             Some((len_stack, remained)) => {
114                 if remained < self.cache.len() {
115                     // Remove those elements that are pushed after the snapshot.
116                     self.cache.truncate(remained);
117                 }
118                 if len_stack > remained {
119                     let rewind_count = len_stack - remained;
120                     let new_len = self.popped.len() - rewind_count;
121                     let recovered_elements = self.popped.drain(new_len..);
122                     self.cache.extend(recovered_elements.rev());
123                     debug_assert_eq!(self.popped.len(), new_len);
124                 }
125             }
126             None => {
127                 self.cache.clear();
128                 // As `self.popped` and `self.lengths` should already be empty,
129                 // there is no need to clear it.
130                 debug_assert!(self.popped.is_empty());
131                 debug_assert!(self.lengths.is_empty());
132             }
133         }
134     }
135 }
136 
137 impl<T: Clone> Index<Range<usize>> for Stack<T> {
138     type Output = [T];
139 
index(&self, range: Range<usize>) -> &[T]140     fn index(&self, range: Range<usize>) -> &[T] {
141         self.cache.index(range)
142     }
143 }
144 
145 #[cfg(test)]
146 mod test {
147     use super::Stack;
148 
149     #[test]
snapshot_with_empty()150     fn snapshot_with_empty() {
151         let mut stack = Stack::new();
152 
153         stack.snapshot();
154         // []
155         assert!(stack.is_empty());
156         // [0]
157         stack.push(0);
158         stack.restore();
159         assert!(stack.is_empty());
160     }
161 
162     #[test]
snapshot_twice()163     fn snapshot_twice() {
164         let mut stack = Stack::new();
165 
166         stack.push(0);
167 
168         stack.snapshot();
169         stack.snapshot();
170         stack.restore();
171         stack.restore();
172 
173         assert_eq!(stack[0..stack.len()], [0]);
174     }
175     #[test]
restore_without_snapshot()176     fn restore_without_snapshot() {
177         let mut stack = Stack::new();
178 
179         stack.push(0);
180         stack.restore();
181 
182         assert_eq!(stack[0..stack.len()], [0; 0]);
183     }
184 
185     #[test]
snapshot_pop_restore()186     fn snapshot_pop_restore() {
187         let mut stack = Stack::new();
188 
189         stack.push(0);
190         stack.snapshot();
191         stack.pop();
192         stack.restore();
193 
194         assert_eq!(stack[0..stack.len()], [0]);
195     }
196 
197     #[test]
snapshot_pop_push_restore()198     fn snapshot_pop_push_restore() {
199         let mut stack = Stack::new();
200 
201         stack.push(0);
202         stack.snapshot();
203         stack.pop();
204         stack.push(1);
205         stack.restore();
206 
207         assert_eq!(stack[0..stack.len()], [0]);
208     }
209 
210     #[test]
snapshot_push_pop_restore()211     fn snapshot_push_pop_restore() {
212         let mut stack = Stack::new();
213 
214         stack.push(0);
215         stack.snapshot();
216         stack.push(1);
217         stack.push(2);
218         stack.pop();
219         stack.restore();
220 
221         assert_eq!(stack[0..stack.len()], [0]);
222     }
223 
224     #[test]
snapshot_push_clear()225     fn snapshot_push_clear() {
226         let mut stack = Stack::new();
227 
228         stack.push(0);
229         stack.snapshot();
230         stack.push(1);
231         stack.clear_snapshot();
232 
233         assert_eq!(stack[0..stack.len()], [0, 1]);
234     }
235 
236     #[test]
snapshot_pop_clear()237     fn snapshot_pop_clear() {
238         let mut stack = Stack::new();
239 
240         stack.push(0);
241         stack.push(1);
242         stack.snapshot();
243         stack.pop();
244         stack.clear_snapshot();
245 
246         assert_eq!(stack[0..stack.len()], [0]);
247     }
248 
249     #[test]
stack_ops()250     fn stack_ops() {
251         let mut stack = Stack::new();
252 
253         // []
254         assert!(stack.is_empty());
255         assert_eq!(stack.peek(), None);
256         assert_eq!(stack.pop(), None);
257 
258         // [0]
259         stack.push(0);
260         assert!(!stack.is_empty());
261         assert_eq!(stack.peek(), Some(&0));
262 
263         // [0, 1]
264         stack.push(1);
265         assert!(!stack.is_empty());
266         assert_eq!(stack.peek(), Some(&1));
267 
268         // [0]
269         assert_eq!(stack.pop(), Some(1));
270         assert!(!stack.is_empty());
271         assert_eq!(stack.peek(), Some(&0));
272 
273         // [0, 2]
274         stack.push(2);
275         assert!(!stack.is_empty());
276         assert_eq!(stack.peek(), Some(&2));
277 
278         // [0, 2, 3]
279         stack.push(3);
280         assert!(!stack.is_empty());
281         assert_eq!(stack.peek(), Some(&3));
282 
283         // Take a snapshot of the current stack
284         // [0, 2, 3]
285         stack.snapshot();
286 
287         // [0, 2]
288         assert_eq!(stack.pop(), Some(3));
289         assert!(!stack.is_empty());
290         assert_eq!(stack.peek(), Some(&2));
291 
292         // Take a snapshot of the current stack
293         // [0, 2]
294         stack.snapshot();
295 
296         // [0]
297         assert_eq!(stack.pop(), Some(2));
298         assert!(!stack.is_empty());
299         assert_eq!(stack.peek(), Some(&0));
300 
301         // []
302         assert_eq!(stack.pop(), Some(0));
303         assert!(stack.is_empty());
304 
305         // Test backtracking
306         // [0, 2]
307         stack.restore();
308         assert_eq!(stack.pop(), Some(2));
309         assert_eq!(stack.pop(), Some(0));
310         assert_eq!(stack.pop(), None);
311 
312         // Test backtracking
313         // [0, 2, 3]
314         stack.restore();
315         assert_eq!(stack.pop(), Some(3));
316         assert_eq!(stack.pop(), Some(2));
317         assert_eq!(stack.pop(), Some(0));
318         assert_eq!(stack.pop(), None);
319     }
320 }
321