compile_regex/utils/
stack.rs

1//! Bounded stack implementation with `const fn`s.
2
3use core::{fmt, slice};
4
5#[derive(Debug)]
6pub(crate) struct PushError;
7
8/// Bounded-capacity stack with `const fn` operations. Used to store [syntax spans](crate::ast::Span)
9/// via [`Syntax` type alias](crate::ast::Syntax).
10pub struct Stack<T, const N: usize = 128> {
11    inner: [T; N],
12    len: usize,
13}
14
15impl<T: fmt::Debug, const N: usize> fmt::Debug for Stack<T, N> {
16    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
17        fmt::Debug::fmt(self.as_slice(), formatter)
18    }
19}
20
21impl<T: Copy, const N: usize> Stack<T, N> {
22    pub(crate) const fn new(filler: T) -> Self {
23        Self {
24            inner: [filler; N],
25            len: 0,
26        }
27    }
28
29    pub(crate) const fn push(&mut self, item: T) -> Result<(), PushError> {
30        if self.len == N {
31            Err(PushError)
32        } else {
33            self.inner[self.len] = item;
34            self.len += 1;
35            Ok(())
36        }
37    }
38
39    pub(crate) const fn pop(&mut self) -> Option<T> {
40        if self.len == 0 {
41            None
42        } else {
43            self.len -= 1;
44            Some(self.inner[self.len])
45        }
46    }
47}
48
49impl<T, const N: usize> Stack<T, N> {
50    /// Returns the underlying slice of elements.
51    pub const fn as_slice(&self) -> &[T] {
52        let (start, _) = self.inner.split_at(self.len);
53        start
54    }
55
56    /// Iterates over elements in this stack in the order of their insertion.
57    pub fn iter(&self) -> impl ExactSizeIterator<Item = &T> + DoubleEndedIterator + '_ {
58        self.as_slice().iter()
59    }
60
61    /// Checks whether the stack is empty (has 0 elements).
62    pub const fn is_empty(&self) -> bool {
63        self.len == 0
64    }
65
66    /// Returns the number of elements in the stack.
67    pub const fn len(&self) -> usize {
68        self.len
69    }
70
71    pub(crate) const fn trim(&mut self, new_len: usize) {
72        self.len = new_len;
73    }
74
75    pub(crate) const fn index_mut(&mut self, idx: usize) -> &mut T {
76        assert!(idx < self.len, "index out of range");
77        &mut self.inner[idx]
78    }
79}
80
81impl<T, const N: usize> AsRef<[T]> for Stack<T, N> {
82    fn as_ref(&self) -> &[T] {
83        self.as_slice()
84    }
85}
86
87impl<T: PartialEq, const N: usize> PartialEq for Stack<T, N> {
88    fn eq(&self, other: &Self) -> bool {
89        self.as_slice() == other.as_slice()
90    }
91}
92
93impl<'a, T, const N: usize> IntoIterator for &'a Stack<T, N> {
94    type Item = &'a T;
95    type IntoIter = slice::Iter<'a, T>;
96
97    fn into_iter(self) -> Self::IntoIter {
98        self.as_slice().iter()
99    }
100}
compile_regex/utils/stack.rs

compile_regex/utils/
stack.rs
