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 popped elements and length of previous states 15 /// in order to rewind the stack to a previous state. 16 #[derive(Debug)] 17 pub 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 43 impl<T: Clone> Default for Stack<T> { default() -> Self44 fn default() -> Self { 45 Self::new() 46 } 47 } 48 49 impl<T: Clone> Stack<T> { 50 /// Creates a new `Stack`. new() -> Self51 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)] is_empty(&self) -> bool61 pub fn is_empty(&self) -> bool { 62 self.cache.is_empty() 63 } 64 65 /// Returns the top-most `&T` in the `Stack`. peek(&self) -> Option<&T>66 pub fn peek(&self) -> Option<&T> { 67 self.cache.last() 68 } 69 70 /// Pushes a `T` onto the `Stack`. push(&mut self, elem: T)71 pub fn push(&mut self, elem: T) { 72 self.cache.push(elem); 73 } 74 75 /// Pops the top-most `T` from the `Stack`. pop(&mut self) -> Option<T>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 len(&self) -> usize92 pub fn len(&self) -> usize { 93 self.cache.len() 94 } 95 96 /// Takes a snapshot of the current `Stack`. snapshot(&mut self)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. clear_snapshot(&mut self)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. restore(&mut self)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 137 impl<T: Clone> Index<Range<usize>> for Stack<T> { 138 type Output = [T]; 139 index(&self, range: Range<usize>) -> &[T]140 fn index(&self, range: Range<usize>) -> &[T] { 141 self.cache.index(range) 142 } 143 } 144 145 #[cfg(test)] 146 mod test { 147 use super::Stack; 148 149 #[test] snapshot_with_empty()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] snapshot_twice()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] restore_without_snapshot()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] snapshot_pop_restore()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] snapshot_pop_push_restore()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] snapshot_push_pop_restore()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] snapshot_push_clear()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] snapshot_pop_clear()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] stack_ops()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