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
10use alloc::vec;
11use alloc::vec::Vec;
12use 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)]
17pub 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
43impl<T: Clone> Default for Stack<T> {
44 fn default() -> Self {
45 Self::new()
46 }
47}
48
49impl<T: Clone> Stack<T> {
50 /// Creates a new `Stack`.
51 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)]
61 pub fn is_empty(&self) -> bool {
62 self.cache.is_empty()
63 }
64
65 /// Returns the top-most `&T` in the `Stack`.
66 pub fn peek(&self) -> Option<&T> {
67 self.cache.last()
68 }
69
70 /// Pushes a `T` onto the `Stack`.
71 pub fn push(&mut self, elem: T) {
72 self.cache.push(elem);
73 }
74
75 /// Pops the top-most `T` from the `Stack`.
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
92 pub fn len(&self) -> usize {
93 self.cache.len()
94 }
95
96 /// Takes a snapshot of the current `Stack`.
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.
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.
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
137impl<T: Clone> Index<Range<usize>> for Stack<T> {
138 type Output = [T];
139
140 fn index(&self, range: Range<usize>) -> &[T] {
141 self.cache.index(range)
142 }
143}
144
145#[cfg(test)]
146mod test {
147 use super::Stack;
148
149 #[test]
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]
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]
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]
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]
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]
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]
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]
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]
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