fuel_pest/
stack.rs

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 std::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}