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