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 an log of `StackOp`s in order to rewind the stack 15 /// to a previous state. 16 #[derive(Debug)] 17 pub struct Stack<T: Clone> { 18 ops: Vec<StackOp<T>>, 19 cache: Vec<T>, 20 snapshots: Vec<usize>, 21 } 22 23 impl<T: Clone> Stack<T> { 24 /// Creates a new `Stack`. new() -> Self25 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)] is_empty(&self) -> bool35 pub fn is_empty(&self) -> bool { 36 self.cache.is_empty() 37 } 38 39 /// Returns the top-most `&T` in the `Stack`. peek(&self) -> Option<&T>40 pub fn peek(&self) -> Option<&T> { 41 self.cache.last() 42 } 43 44 /// Pushes a `T` onto the `Stack`. push(&mut self, elem: T)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`. pop(&mut self) -> Option<T>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 len(&self) -> usize60 pub fn len(&self) -> usize { 61 self.cache.len() 62 } 63 64 /// Takes a snapshot of the current `Stack`. snapshot(&mut self)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. clear_snapshot(&mut self)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. restore(&mut self)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 rewind_to(&mut self, index: usize)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 105 impl<T: Clone> Index<Range<usize>> for Stack<T> { 106 type Output = [T]; 107 index(&self, range: Range<usize>) -> &[T]108 fn index(&self, range: Range<usize>) -> &[T] { 109 self.cache.index(range) 110 } 111 } 112 113 #[derive(Debug)] 114 enum StackOp<T> { 115 Push(T), 116 Pop(T), 117 } 118 119 #[cfg(test)] 120 mod test { 121 use super::Stack; 122 123 #[test] snapshot_with_empty()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] snapshot_twice()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] stack_ops()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