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