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 std::ops::{Index, Range};
11 
12 /// Implementation of a `Stack` which maintains an log of `StackOp`s in order to rewind the stack
13 /// to a previous state.
14 #[derive(Debug)]
15 pub struct Stack<T: Clone> {
16     ops: Vec<StackOp<T>>,
17     cache: Vec<T>,
18     snapshots: Vec<usize>,
19 }
20 
21 impl<T: Clone> Stack<T> {
22     /// Creates a new `Stack`.
new() -> Self23     pub fn new() -> Self {
24         Stack {
25             ops: vec![],
26             cache: vec![],
27             snapshots: vec![],
28         }
29     }
30 
31     /// Returns `true` if the stack is currently empty.
32     #[allow(dead_code)]
is_empty(&self) -> bool33     pub fn is_empty(&self) -> bool {
34         self.cache.is_empty()
35     }
36 
37     /// Returns the top-most `&T` in the `Stack`.
peek(&self) -> Option<&T>38     pub fn peek(&self) -> Option<&T> {
39         self.cache.last()
40     }
41 
42     /// Pushes a `T` onto the `Stack`.
push(&mut self, elem: T)43     pub fn push(&mut self, elem: T) {
44         self.ops.push(StackOp::Push(elem.clone()));
45         self.cache.push(elem);
46     }
47 
48     /// Pops the top-most `T` from the `Stack`.
pop(&mut self) -> Option<T>49     pub fn pop(&mut self) -> Option<T> {
50         let popped = self.cache.pop();
51         if let Some(ref val) = popped {
52             self.ops.push(StackOp::Pop(val.clone()));
53         }
54         popped
55     }
56 
57     /// Returns the size of the stack
len(&self) -> usize58     pub fn len(&self) -> usize {
59         self.cache.len()
60     }
61 
62     /// Takes a snapshot of the current `Stack`.
snapshot(&mut self)63     pub fn snapshot(&mut self) {
64         self.snapshots.push(self.ops.len());
65     }
66 
67     /// The parsing after the last snapshot was successful so clearing it.
clear_snapshot(&mut self)68     pub fn clear_snapshot(&mut self) {
69         self.snapshots.pop();
70     }
71 
72     /// Rewinds the `Stack` to the most recent `snapshot()`. If no `snapshot()` has been taken, this
73     /// function return the stack to its initial state.
restore(&mut self)74     pub fn restore(&mut self) {
75         match self.snapshots.pop() {
76             Some(ops_index) => {
77                 self.rewind_to(ops_index);
78                 self.ops.truncate(ops_index);
79             }
80             None => {
81                 self.cache.clear();
82                 self.ops.clear();
83             }
84         }
85     }
86 
87     // Rewind the stack to a particular index
rewind_to(&mut self, index: usize)88     fn rewind_to(&mut self, index: usize) {
89         let ops_to_rewind = &self.ops[index..];
90         for op in ops_to_rewind.iter().rev() {
91             match *op {
92                 StackOp::Push(_) => {
93                     self.cache.pop();
94                 }
95                 StackOp::Pop(ref elem) => {
96                     self.cache.push(elem.clone());
97                 }
98             }
99         }
100     }
101 }
102 
103 impl<T: Clone> Index<Range<usize>> for Stack<T> {
104     type Output = [T];
105 
index(&self, range: Range<usize>) -> &[T]106     fn index(&self, range: Range<usize>) -> &[T] {
107         self.cache.index(range)
108     }
109 }
110 
111 #[derive(Debug)]
112 enum StackOp<T> {
113     Push(T),
114     Pop(T),
115 }
116 
117 #[cfg(test)]
118 mod test {
119     use super::Stack;
120 
121     #[test]
snapshot_with_empty()122     fn snapshot_with_empty() {
123         let mut stack = Stack::new();
124 
125         stack.snapshot();
126         // []
127         assert!(stack.is_empty());
128         // [0]
129         stack.push(0);
130         stack.restore();
131         assert!(stack.is_empty());
132     }
133 
134     #[test]
snapshot_twice()135     fn snapshot_twice() {
136         let mut stack = Stack::new();
137 
138         stack.push(0);
139 
140         stack.snapshot();
141         stack.snapshot();
142         stack.restore();
143         stack.restore();
144 
145         assert_eq!(stack[0..stack.len()], [0]);
146     }
147 
148     #[test]
stack_ops()149     fn stack_ops() {
150         let mut stack = Stack::new();
151 
152         // []
153         assert!(stack.is_empty());
154         assert_eq!(stack.peek(), None);
155         assert_eq!(stack.pop(), None);
156 
157         // [0]
158         stack.push(0);
159         assert!(!stack.is_empty());
160         assert_eq!(stack.peek(), Some(&0));
161 
162         // [0, 1]
163         stack.push(1);
164         assert!(!stack.is_empty());
165         assert_eq!(stack.peek(), Some(&1));
166 
167         // [0]
168         assert_eq!(stack.pop(), Some(1));
169         assert!(!stack.is_empty());
170         assert_eq!(stack.peek(), Some(&0));
171 
172         // [0, 2]
173         stack.push(2);
174         assert!(!stack.is_empty());
175         assert_eq!(stack.peek(), Some(&2));
176 
177         // [0, 2, 3]
178         stack.push(3);
179         assert!(!stack.is_empty());
180         assert_eq!(stack.peek(), Some(&3));
181 
182         // Take a snapshot of the current stack
183         // [0, 2, 3]
184         stack.snapshot();
185 
186         // [0, 2]
187         assert_eq!(stack.pop(), Some(3));
188         assert!(!stack.is_empty());
189         assert_eq!(stack.peek(), Some(&2));
190 
191         // Take a snapshot of the current stack
192         // [0, 2]
193         stack.snapshot();
194 
195         // [0]
196         assert_eq!(stack.pop(), Some(2));
197         assert!(!stack.is_empty());
198         assert_eq!(stack.peek(), Some(&0));
199 
200         // []
201         assert_eq!(stack.pop(), Some(0));
202         assert!(stack.is_empty());
203 
204         // Test backtracking
205         // [0, 2]
206         stack.restore();
207         assert_eq!(stack.pop(), Some(2));
208         assert_eq!(stack.pop(), Some(0));
209         assert_eq!(stack.pop(), None);
210 
211         // Test backtracking
212         // [0, 2, 3]
213         stack.restore();
214         assert_eq!(stack.pop(), Some(3));
215         assert_eq!(stack.pop(), Some(2));
216         assert_eq!(stack.pop(), Some(0));
217         assert_eq!(stack.pop(), None);
218     }
219 }
220