minicas_core/
path.rs

1/// A compact representation of the path to take through an AST to
2/// reach a certain node.
3#[derive(Debug, Clone, Eq, Hash)]
4pub enum Path {
5    Opt(u64, usize),
6    Vec(Vec<usize>),
7}
8
9impl Default for Path {
10    fn default() -> Self {
11        Self::Opt(0, 0)
12    }
13}
14
15impl PartialEq for Path {
16    fn eq(&self, other: &Self) -> bool {
17        self.iter().eq(other.iter())
18    }
19}
20
21impl From<Vec<usize>> for Path {
22    fn from(v: Vec<usize>) -> Path {
23        let mut out = Path::default();
24        for v in v.into_iter() {
25            out.push(v);
26        }
27        out
28    }
29}
30
31impl Into<Vec<usize>> for Path {
32    fn into(self: Self) -> Vec<usize> {
33        self.iter().collect()
34    }
35}
36
37impl Path {
38    pub fn with_next(u: usize) -> Self {
39        let mut out = Self::default();
40        out.push(u);
41        out
42    }
43
44    pub fn push(&mut self, u: usize) {
45        match self {
46            Self::Opt(v, cnt) => match stuffed_val_push(*v, u) {
47                Ok(new_v) => {
48                    *v = new_v;
49                    *cnt += 1;
50                }
51                Err(()) => {
52                    let mut new_v: Vec<usize> = self.iter().collect();
53                    new_v.push(u);
54                    *self = Self::Vec(new_v);
55                }
56            },
57            Self::Vec(v) => v.push(u),
58        }
59    }
60
61    pub fn iter<'a>(&'a self) -> PathIter<'a> {
62        PathIter {
63            path: self,
64            offset: 0,
65        }
66    }
67}
68
69/// An iterator over the values in a [Path].
70pub struct PathIter<'a> {
71    path: &'a Path,
72    offset: usize,
73}
74
75impl Iterator for PathIter<'_> {
76    type Item = usize;
77
78    fn next(&mut self) -> Option<Self::Item> {
79        match self.path {
80            Path::Opt(v, cnt) => {
81                if self.offset >= *cnt {
82                    None
83                } else {
84                    self.offset += 1;
85                    let possible = v >> ((cnt - self.offset) * 4);
86                    if possible == 0 {
87                        None
88                    } else if (possible & 0b11) == 0b11 {
89                        todo!("support longer formats")
90                    } else {
91                        Some(((possible >> 1) & 0b11) as usize)
92                    }
93                }
94            }
95            Path::Vec(v) => {
96                if self.offset >= v.len() {
97                    None
98                } else {
99                    self.offset += 1;
100                    Some(v[self.offset - 1])
101                }
102            }
103        }
104    }
105}
106
107#[inline(always)]
108fn stuffed_val_full(v: &u64) -> bool {
109    (v >> 60) != 0
110}
111
112#[inline(always)]
113fn stuffed_val_push(v: u64, n: usize) -> Result<u64, ()> {
114    if stuffed_val_full(&v) {
115        return Err(());
116    }
117    if n > 3 {
118        return Err(());
119    }
120
121    Ok((v << 4) | (n << 1) as u64 | if n == 0 { 1 } else { 0 })
122}
123
124#[cfg(test)]
125mod tests {
126    use super::*;
127
128    #[test]
129    fn opt() {
130        let mut path = Path::default();
131        assert_eq!(path.iter().collect::<Vec<_>>(), vec![]);
132
133        path.push(2);
134        assert_eq!(path.iter().collect::<Vec<_>>(), vec![2]);
135        path.push(0);
136        assert_eq!(path.iter().collect::<Vec<_>>(), vec![2, 0]);
137        path.push(1);
138        assert_eq!(path.iter().collect::<Vec<_>>(), vec![2, 0, 1]);
139        assert!(!matches!(path, Path::Vec(_)));
140    }
141
142    #[test]
143    fn vec() {
144        let mut path = Path::default();
145        assert_eq!(path.iter().collect::<Vec<_>>(), vec![]);
146
147        path.push(4);
148        assert!(matches!(path, Path::Vec(_)));
149        assert_eq!(path.iter().collect::<Vec<_>>(), vec![4]);
150        path.push(1);
151        assert_eq!(path.iter().collect::<Vec<_>>(), vec![4, 1]);
152        path.push(0);
153        assert_eq!(path.iter().collect::<Vec<_>>(), vec![4, 1, 0]);
154    }
155
156    #[test]
157    fn vec_promote() {
158        let mut path = Path::default();
159        assert_eq!(path.iter().collect::<Vec<_>>(), vec![]);
160
161        path.push(0);
162        assert_eq!(path.iter().collect::<Vec<_>>(), vec![0]);
163        path.push(3);
164        assert_eq!(path.iter().collect::<Vec<_>>(), vec![0, 3]);
165        path.push(0);
166        assert_eq!(path.iter().collect::<Vec<_>>(), vec![0, 3, 0]);
167        assert!(!matches!(path, Path::Vec(_)));
168        path.push(88);
169        assert!(matches!(path, Path::Vec(_)));
170        assert_eq!(path.iter().collect::<Vec<_>>(), vec![0, 3, 0, 88]);
171        path.push(1);
172        assert_eq!(path.iter().collect::<Vec<_>>(), vec![0, 3, 0, 88, 1]);
173    }
174}
minicas_core/path.rs

minicas_core/
path.rs
