yggdrasil_rt/enhance/
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, vec::Vec};
11use core::ops::{Index, Range};
12
13/// Implementation of a `Stack` which maintains popped elements and length of previous states
14/// in order to rewind the stack to a previous state.
15#[derive(Debug)]
16pub struct Stack<T: Clone> {
17    /// All elements in the stack.
18    cache: Vec<T>,
19    /// All elements that are in previous snapshots but may not be in the next state.
20    /// They will be pushed back to `cache` if the snapshot is restored,
21    /// otherwise be dropped if the snapshot is cleared.
22    ///
23    /// Those elements from a sequence of snapshots are stacked in one [`Vec`], and
24    /// `popped.len() == lengths.iter().map(|(len, remained)| len - remained).sum()`
25    popped: Vec<T>,
26    /// Every element corresponds to a snapshot, and each element has two fields:
27    /// - Length of `cache` when corresponding snapshot is taken (AKA `len`).
28    /// - Count of elements that come from corresponding snapshot
29    ///   and are still in next snapshot or current state (AKA `remained`).
30    ///
31    /// And `len` is never less than `remained`.
32    ///
33    /// On restoring, the `cache` can be divided into two parts:
34    /// - `0..remained` are untouched since the snapshot is taken.
35    ///
36    ///   There's nothing to do with those elements. Just let them stay where they are.
37    ///
38    /// - `remained..cache.len()` are pushed after the snapshot is taken.
39    lengths: Vec<(usize, usize)>,
40}
41
42impl<T: Clone> Default for Stack<T> {
43    fn default() -> Self {
44        Self::new()
45    }
46}
47
48impl<T: Clone> Stack<T> {
49    /// Creates a new `Stack`.
50    pub fn new() -> Self {
51        Stack { cache: vec![], popped: vec![], lengths: vec![] }
52    }
53
54    /// Returns `true` if the stack is currently empty.
55    #[allow(dead_code)]
56    pub fn is_empty(&self) -> bool {
57        self.cache.is_empty()
58    }
59
60    /// Returns the top-most `&T` in the `Stack`.
61    pub fn peek(&self) -> Option<&T> {
62        self.cache.last()
63    }
64
65    /// Pushes a `T` onto the `Stack`.
66    pub fn push(&mut self, elem: T) {
67        self.cache.push(elem);
68    }
69
70    /// Pops the top-most `T` from the `Stack`.
71    pub fn pop(&mut self) -> Option<T> {
72        let len = self.cache.len();
73        let popped = self.cache.pop();
74        if let Some(popped) = &popped {
75            if let Some((_, remained_count)) = self.lengths.last_mut() {
76                // `len >= *unpopped_count`
77                if len == *remained_count {
78                    *remained_count -= 1;
79                    self.popped.push(popped.clone());
80                }
81            }
82        }
83        popped
84    }
85
86    /// Returns the size of the stack
87    pub fn len(&self) -> usize {
88        self.cache.len()
89    }
90
91    /// Takes a snapshot of the current `Stack`.
92    pub fn snapshot(&mut self) {
93        self.lengths.push((self.cache.len(), self.cache.len()))
94    }
95
96    /// The parsing after the last snapshot was successful so clearing it.
97    pub fn clear_snapshot(&mut self) {
98        if let Some((len, unpopped)) = self.lengths.pop() {
99            // Popped elements from previous state are no longer needed.
100            self.popped.truncate(self.popped.len() - (len - unpopped));
101        }
102    }
103
104    /// Rewinds the `Stack` to the most recent `snapshot()`. If no `snapshot()` has been taken, this
105    /// function return the stack to its initial state.
106    pub fn restore(&mut self) {
107        match self.lengths.pop() {
108            Some((len_stack, remained)) => {
109                if remained < self.cache.len() {
110                    // Remove those elements that are pushed after the snapshot.
111                    self.cache.truncate(remained);
112                }
113                if len_stack > remained {
114                    let rewind_count = len_stack - remained;
115                    let new_len = self.popped.len() - rewind_count;
116                    let recovered_elements = self.popped.drain(new_len..);
117                    self.cache.extend(recovered_elements.rev());
118                    debug_assert_eq!(self.popped.len(), new_len);
119                }
120            }
121            None => {
122                self.cache.clear();
123                // As `self.popped` and `self.lengths` should already be empty,
124                // there is no need to clear it.
125                debug_assert!(self.popped.is_empty());
126                debug_assert!(self.lengths.is_empty());
127            }
128        }
129    }
130}
131
132impl<T: Clone> Index<Range<usize>> for Stack<T> {
133    type Output = [T];
134
135    fn index(&self, range: Range<usize>) -> &[T] {
136        self.cache.index(range)
137    }
138}
yggdrasil_rt/enhance/stack.rs

yggdrasil_rt/enhance/
stack.rs
