/rust/registry/src/index.crates.io-1949cf8c6b5b557f/pest-2.9.0/src/stack.rs

Source
// 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 popped elements and length of previous states
/// in order to rewind the stack to a previous state.
#[derive(Debug)]
pub struct Stack<T: Clone> {
    /// All elements in the stack.
    cache: Vec<T>,
    /// All elements that are in previous snapshots but may not be in the next state.
    /// They will be pushed back to `cache` if the snapshot is restored,
    /// otherwise be dropped if the snapshot is cleared.
    ///
    /// Those elements from a sequence of snapshots are stacked in one [`Vec`], and
    /// `popped.len() == lengths.iter().map(|(len, remained)| len - remained).sum()`
    popped: Vec<T>,
    /// Every element corresponds to a snapshot, and each element has two fields:
    /// - Length of `cache` when corresponding snapshot is taken (AKA `len`).
    /// - Count of elements that come from corresponding snapshot
    ///   and are still in next snapshot or current state (AKA `remained`).
    ///
    /// And `len` is never less than `remained`.
    ///
    /// On restoring, the `cache` can be divided into two parts:
    /// - `0..remained` are untouched since the snapshot is taken.
    ///
    ///   There's nothing to do with those elements. Just let them stay where they are.
    ///
    /// - `remained..cache.len()` are pushed after the snapshot is taken.
    lengths: Vec<(usize, usize)>,
}

impl<T: Clone> Default for Stack<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T: Clone> Stack<T> {
    /// Creates a new `Stack`.
    pub fn new() -> Self {
        Stack {
            cache: vec![],
            popped: vec![],
            lengths: 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.cache.push(elem);
    }

    /// Pops the top-most `T` from the `Stack`.
    pub fn pop(&mut self) -> Option<T> {
        let len = self.cache.len();
        let popped = self.cache.pop();
        if let Some(popped) = &popped {
            if let Some((_, remained_count)) = self.lengths.last_mut() {
                // `len >= *unpopped_count`
                if len == *remained_count {
                    *remained_count -= 1;
                    self.popped.push(popped.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.lengths.push((self.cache.len(), self.cache.len()))
    }

    /// The parsing after the last snapshot was successful so clearing it.
    pub fn clear_snapshot(&mut self) {
        if let Some((len, remained)) = self.lengths.pop() {
            let popped_count = len - remained;
            if let Some((_, parent_remained)) = self.lengths.last_mut() {
                let merged_remained = (*parent_remained).min(remained);
                let parent_popped = *parent_remained - merged_remained;
                *parent_remained = merged_remained;

                let popped_start = self.popped.len() - popped_count;
                drop(
                    self.popped
                        .drain(popped_start..popped_start + popped_count - parent_popped),
                );
            } else {
                self.popped.truncate(self.popped.len() - popped_count);
            }
        }
    }

    /// 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.lengths.pop() {
            Some((len_stack, remained)) => {
                if remained < self.cache.len() {
                    // Remove those elements that are pushed after the snapshot.
                    self.cache.truncate(remained);
                }
                if len_stack > remained {
                    let rewind_count = len_stack - remained;
                    let new_len = self.popped.len() - rewind_count;
                    let recovered_elements = self.popped.drain(new_len..);
                    self.cache.extend(recovered_elements.rev());
                    debug_assert_eq!(self.popped.len(), new_len);
                }
            }
            None => {
                self.cache.clear();
                // As `self.popped` and `self.lengths` should already be empty,
                // there is no need to clear it.
                debug_assert!(self.popped.is_empty());
                debug_assert!(self.lengths.is_empty());
            }
        }
    }
}

impl<T: Clone> Index<Range<usize>> for Stack<T> {
    type Output = [T];

    fn index(&self, range: Range<usize>) -> &[T] {
        self.cache.index(range)
    }
}

#[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 restore_without_snapshot() {
        let mut stack = Stack::new();

        stack.push(0);
        stack.restore();

        assert_eq!(stack[0..stack.len()], [0; 0]);
    }

    #[test]
    fn snapshot_pop_restore() {
        let mut stack = Stack::new();

        stack.push(0);
        stack.snapshot();
        stack.pop();
        stack.restore();

        assert_eq!(stack[0..stack.len()], [0]);
    }

    #[test]
    fn snapshot_pop_push_restore() {
        let mut stack = Stack::new();

        stack.push(0);
        stack.snapshot();
        stack.pop();
        stack.push(1);
        stack.restore();

        assert_eq!(stack[0..stack.len()], [0]);
    }

    #[test]
    fn snapshot_push_pop_restore() {
        let mut stack = Stack::new();

        stack.push(0);
        stack.snapshot();
        stack.push(1);
        stack.push(2);
        stack.pop();
        stack.restore();

        assert_eq!(stack[0..stack.len()], [0]);
    }

    #[test]
    fn snapshot_push_clear() {
        let mut stack = Stack::new();

        stack.push(0);
        stack.snapshot();
        stack.push(1);
        stack.clear_snapshot();

        assert_eq!(stack[0..stack.len()], [0, 1]);
    }

    #[test]
    fn snapshot_pop_clear() {
        let mut stack = Stack::new();

        stack.push(0);
        stack.push(1);
        stack.snapshot();
        stack.pop();
        stack.clear_snapshot();

        assert_eq!(stack[0..stack.len()], [0]);
    }

    #[test]
    fn nested_snapshot_pop_clear_restore() {
        let mut stack = Stack::new();

        stack.push(0);
        stack.snapshot();
        stack.snapshot();
        stack.pop();
        stack.clear_snapshot();
        stack.restore();

        assert_eq!(stack[0..stack.len()], [0]);
    }

    #[test]
    fn nested_snapshot_clear_preserves_outer_boundary() {
        let mut stack = Stack::new();

        stack.push(0);
        stack.snapshot();
        stack.push(1);
        stack.snapshot();
        stack.pop();
        stack.clear_snapshot();
        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);
    }
}

Coverage Report

Created: 2026-09-03 06:10

Line	Count	Source
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> {
44	0	fn default() -> Self {
45	0	Self::new()
46	0	}
47		}
48
49		impl<T: Clone> Stack<T> {
50		/// Creates a new `Stack`.
51	0	pub fn new() -> Self {
52	0	Stack {
53	0	cache: vec![],
54	0	popped: vec![],
55	0	lengths: vec![],
56	0	}
57	0	} Unexecuted instantiation: <pest::stack::Stack<pest::parser_state::SpanOrLiteral>>::new Unexecuted instantiation: <pest::stack::Stack<_>>::new
58
59		/// Returns `true` if the stack is currently empty.
60		#[allow(dead_code)]
61	0	pub fn is_empty(&self) -> bool {
62	0	self.cache.is_empty()
63	0	}
64
65		/// Returns the top-most `&T` in the `Stack`.
66	0	pub fn peek(&self) -> Option<&T> {
67	0	self.cache.last()
68	0	}
69
70		/// Pushes a `T` onto the `Stack`.
71	0	pub fn push(&mut self, elem: T) {
72	0	self.cache.push(elem);
73	0	}
74
75		/// Pops the top-most `T` from the `Stack`.
76	0	pub fn pop(&mut self) -> Option<T> {
77	0	let len = self.cache.len();
78	0	let popped = self.cache.pop();
79	0	if let Some(popped) = &popped {
80	0	if let Some((_, remained_count)) = self.lengths.last_mut() {
81		// `len >= *unpopped_count`
82	0	if len == *remained_count {
83	0	*remained_count -= 1;
84	0	self.popped.push(popped.clone());
85	0	}
86	0	}
87	0	}
88	0	popped
89	0	}
90
91		/// Returns the size of the stack
92	0	pub fn len(&self) -> usize {
93	0	self.cache.len()
94	0	}
95
96		/// Takes a snapshot of the current `Stack`.
97	0	pub fn snapshot(&mut self) {
98	0	self.lengths.push((self.cache.len(), self.cache.len()))
99	0	} Unexecuted instantiation: <pest::stack::Stack<pest::parser_state::SpanOrLiteral>>::snapshot Unexecuted instantiation: <pest::stack::Stack<_>>::snapshot
100
101		/// The parsing after the last snapshot was successful so clearing it.
102	0	pub fn clear_snapshot(&mut self) {
103	0	if let Some((len, remained)) = self.lengths.pop() {
104	0	let popped_count = len - remained;
105	0	if let Some((_, parent_remained)) = self.lengths.last_mut() {
106	0	let merged_remained = (*parent_remained).min(remained);
107	0	let parent_popped = *parent_remained - merged_remained;
108	0	*parent_remained = merged_remained;
109	0
110	0	let popped_start = self.popped.len() - popped_count;
111	0	drop(
112	0	self.popped
113	0	.drain(popped_start..popped_start + popped_count - parent_popped),
114	0	);
115	0	} else {
116	0	self.popped.truncate(self.popped.len() - popped_count);
117	0	}
118	0	}
119	0	} Unexecuted instantiation: <pest::stack::Stack<pest::parser_state::SpanOrLiteral>>::clear_snapshot Unexecuted instantiation: <pest::stack::Stack<_>>::clear_snapshot
120
121		/// Rewinds the `Stack` to the most recent `snapshot()`. If no `snapshot()` has been taken, this
122		/// function return the stack to its initial state.
123	0	pub fn restore(&mut self) {
124	0	match self.lengths.pop() {
125	0	Some((len_stack, remained)) => {
126	0	if remained < self.cache.len() {
127	0	// Remove those elements that are pushed after the snapshot.
128	0	self.cache.truncate(remained);
129	0	}
130	0	if len_stack > remained {
131	0	let rewind_count = len_stack - remained;
132	0	let new_len = self.popped.len() - rewind_count;
133	0	let recovered_elements = self.popped.drain(new_len..);
134	0	self.cache.extend(recovered_elements.rev());
135	0	debug_assert_eq!(self.popped.len(), new_len);
136	0	}
137		}
138		None => {
139	0	self.cache.clear();
140		// As `self.popped` and `self.lengths` should already be empty,
141		// there is no need to clear it.
142	0	debug_assert!(self.popped.is_empty());
143	0	debug_assert!(self.lengths.is_empty());
144		}
145		}
146	0	} Unexecuted instantiation: <pest::stack::Stack<pest::parser_state::SpanOrLiteral>>::restore Unexecuted instantiation: <pest::stack::Stack<_>>::restore
147		}
148
149		impl<T: Clone> Index<Range<usize>> for Stack<T> {
150		type Output = [T];
151
152	0	fn index(&self, range: Range<usize>) -> &[T] {
153	0	self.cache.index(range)
154	0	}
155		}
156
157		#[cfg(test)]
158		mod test {
159		use super::Stack;
160
161		#[test]
162		fn snapshot_with_empty() {
163		let mut stack = Stack::new();
164
165		stack.snapshot();
166		// []
167		assert!(stack.is_empty());
168		// [0]
169		stack.push(0);
170		stack.restore();
171		assert!(stack.is_empty());
172		}
173
174		#[test]
175		fn snapshot_twice() {
176		let mut stack = Stack::new();
177
178		stack.push(0);
179
180		stack.snapshot();
181		stack.snapshot();
182		stack.restore();
183		stack.restore();
184
185		assert_eq!(stack[0..stack.len()], [0]);
186		}
187		#[test]
188		fn restore_without_snapshot() {
189		let mut stack = Stack::new();
190
191		stack.push(0);
192		stack.restore();
193
194		assert_eq!(stack[0..stack.len()], [0; 0]);
195		}
196
197		#[test]
198		fn snapshot_pop_restore() {
199		let mut stack = Stack::new();
200
201		stack.push(0);
202		stack.snapshot();
203		stack.pop();
204		stack.restore();
205
206		assert_eq!(stack[0..stack.len()], [0]);
207		}
208
209		#[test]
210		fn snapshot_pop_push_restore() {
211		let mut stack = Stack::new();
212
213		stack.push(0);
214		stack.snapshot();
215		stack.pop();
216		stack.push(1);
217		stack.restore();
218
219		assert_eq!(stack[0..stack.len()], [0]);
220		}
221
222		#[test]
223		fn snapshot_push_pop_restore() {
224		let mut stack = Stack::new();
225
226		stack.push(0);
227		stack.snapshot();
228		stack.push(1);
229		stack.push(2);
230		stack.pop();
231		stack.restore();
232
233		assert_eq!(stack[0..stack.len()], [0]);
234		}
235
236		#[test]
237		fn snapshot_push_clear() {
238		let mut stack = Stack::new();
239
240		stack.push(0);
241		stack.snapshot();
242		stack.push(1);
243		stack.clear_snapshot();
244
245		assert_eq!(stack[0..stack.len()], [0, 1]);
246		}
247
248		#[test]
249		fn snapshot_pop_clear() {
250		let mut stack = Stack::new();
251
252		stack.push(0);
253		stack.push(1);
254		stack.snapshot();
255		stack.pop();
256		stack.clear_snapshot();
257
258		assert_eq!(stack[0..stack.len()], [0]);
259		}
260
261		#[test]
262		fn nested_snapshot_pop_clear_restore() {
263		let mut stack = Stack::new();
264
265		stack.push(0);
266		stack.snapshot();
267		stack.snapshot();
268		stack.pop();
269		stack.clear_snapshot();
270		stack.restore();
271
272		assert_eq!(stack[0..stack.len()], [0]);
273		}
274
275		#[test]
276		fn nested_snapshot_clear_preserves_outer_boundary() {
277		let mut stack = Stack::new();
278
279		stack.push(0);
280		stack.snapshot();
281		stack.push(1);
282		stack.snapshot();
283		stack.pop();
284		stack.clear_snapshot();
285		stack.restore();
286
287		assert_eq!(stack[0..stack.len()], [0]);
288		}
289
290		#[test]
291		fn stack_ops() {
292		let mut stack = Stack::new();
293
294		// []
295		assert!(stack.is_empty());
296		assert_eq!(stack.peek(), None);
297		assert_eq!(stack.pop(), None);
298
299		// [0]
300		stack.push(0);
301		assert!(!stack.is_empty());
302		assert_eq!(stack.peek(), Some(&0));
303
304		// [0, 1]
305		stack.push(1);
306		assert!(!stack.is_empty());
307		assert_eq!(stack.peek(), Some(&1));
308
309		// [0]
310		assert_eq!(stack.pop(), Some(1));
311		assert!(!stack.is_empty());
312		assert_eq!(stack.peek(), Some(&0));
313
314		// [0, 2]
315		stack.push(2);
316		assert!(!stack.is_empty());
317		assert_eq!(stack.peek(), Some(&2));
318
319		// [0, 2, 3]
320		stack.push(3);
321		assert!(!stack.is_empty());
322		assert_eq!(stack.peek(), Some(&3));
323
324		// Take a snapshot of the current stack
325		// [0, 2, 3]
326		stack.snapshot();
327
328		// [0, 2]
329		assert_eq!(stack.pop(), Some(3));
330		assert!(!stack.is_empty());
331		assert_eq!(stack.peek(), Some(&2));
332
333		// Take a snapshot of the current stack
334		// [0, 2]
335		stack.snapshot();
336
337		// [0]
338		assert_eq!(stack.pop(), Some(2));
339		assert!(!stack.is_empty());
340		assert_eq!(stack.peek(), Some(&0));
341
342		// []
343		assert_eq!(stack.pop(), Some(0));
344		assert!(stack.is_empty());
345
346		// Test backtracking
347		// [0, 2]
348		stack.restore();
349		assert_eq!(stack.pop(), Some(2));
350		assert_eq!(stack.pop(), Some(0));
351		assert_eq!(stack.pop(), None);
352
353		// Test backtracking
354		// [0, 2, 3]
355		stack.restore();
356		assert_eq!(stack.pop(), Some(3));
357		assert_eq!(stack.pop(), Some(2));
358		assert_eq!(stack.pop(), Some(0));
359		assert_eq!(stack.pop(), None);
360		}
361		}