logos_codegen/graph/
rope.rs

1use std::ops::Deref;
2
3use crate::graph::{Disambiguate, Fork, Graph, NodeId, Range};
4
5#[derive(PartialEq, Clone, Hash)]
6pub struct Rope {
7    pub pattern: Pattern,
8    pub then: NodeId,
9    pub miss: Miss,
10}
11
12#[derive(PartialEq, Clone, Hash)]
13pub struct Pattern(pub Vec<Range>);
14
15impl Deref for Pattern {
16    type Target = [Range];
17
18    fn deref(&self) -> &[Range] {
19        &self.0
20    }
21}
22
23/// Because Ropes could potentially fail a match mid-pattern,
24/// a regular `Option` is not sufficient here.
25#[derive(PartialEq, Clone, Copy, Hash)]
26pub enum Miss {
27    /// Same as Option::None, error on fail
28    None,
29    /// Jump to id if first byte does not match, fail on partial match
30    First(NodeId),
31    /// Jump to id on partial or empty match
32    Any(NodeId),
33}
34
35impl Miss {
36    pub fn is_none(&self) -> bool {
37        matches!(self, Miss::None)
38    }
39
40    pub fn first(self) -> Option<NodeId> {
41        match self {
42            Miss::First(id) | Miss::Any(id) => Some(id),
43            _ => None,
44        }
45    }
46
47    pub fn take_first(&mut self) -> Option<NodeId> {
48        match *self {
49            Miss::First(id) => {
50                *self = Miss::None;
51
52                Some(id)
53            }
54            Miss::Any(id) => Some(id),
55            Miss::None => None,
56        }
57    }
58}
59
60impl From<Option<NodeId>> for Miss {
61    fn from(miss: Option<NodeId>) -> Self {
62        match miss {
63            Some(id) => Miss::First(id),
64            None => Miss::None,
65        }
66    }
67}
68
69impl From<NodeId> for Miss {
70    fn from(id: NodeId) -> Self {
71        Miss::First(id)
72    }
73}
74
75impl Rope {
76    pub fn new<P>(pattern: P, then: NodeId) -> Self
77    where
78        P: Into<Pattern>,
79    {
80        Rope {
81            pattern: pattern.into(),
82            then,
83            miss: Miss::None,
84        }
85    }
86
87    pub fn miss<M>(mut self, miss: M) -> Self
88    where
89        M: Into<Miss>,
90    {
91        self.miss = miss.into();
92        self
93    }
94
95    pub fn miss_any(mut self, miss: NodeId) -> Self {
96        self.miss = Miss::Any(miss);
97        self
98    }
99
100    pub fn into_fork<T>(mut self, graph: &mut Graph<T>) -> Fork
101    where
102        T: Disambiguate,
103    {
104        let first = self.pattern.0.remove(0);
105        let miss = self.miss.take_first();
106
107        // The new fork will lead to a new rope,
108        // or the old target if no new rope was created
109        let then = match self.pattern.len() {
110            0 => self.then,
111            _ => graph.push(self),
112        };
113
114        Fork::new().branch(first, then).miss(miss)
115    }
116
117    pub fn prefix(&self, other: &Self) -> Option<(Pattern, Miss)> {
118        let count = self
119            .pattern
120            .iter()
121            .zip(other.pattern.iter())
122            .take_while(|(a, b)| a == b)
123            .count();
124
125        let pattern = match count {
126            0 => return None,
127            n => self.pattern[..n].into(),
128        };
129        let miss = match (self.miss, other.miss) {
130            (Miss::None, miss) => miss,
131            (miss, Miss::None) => miss,
132            _ => return None,
133        };
134
135        Some((pattern, miss))
136    }
137
138    pub fn split_at<T>(mut self, at: usize, graph: &mut Graph<T>) -> Option<Rope>
139    where
140        T: Disambiguate,
141    {
142        match at {
143            0 => return None,
144            n if n == self.pattern.len() => return Some(self),
145            _ => (),
146        }
147
148        let (this, next) = self.pattern.split_at(at);
149
150        let next_miss = match self.miss {
151            Miss::Any(_) => self.miss,
152            _ => Miss::None,
153        };
154
155        let next = graph.push(Rope {
156            pattern: next.into(),
157            miss: next_miss,
158            then: self.then,
159        });
160
161        self.pattern = this.into();
162        self.then = next;
163
164        Some(self)
165    }
166
167    pub fn remainder<T>(mut self, at: usize, graph: &mut Graph<T>) -> NodeId
168    where
169        T: Disambiguate,
170    {
171        self.pattern = self.pattern[at..].into();
172
173        match self.pattern.len() {
174            0 => self.then,
175            _ => graph.push(self),
176        }
177    }
178
179    pub fn shake<T>(&self, graph: &Graph<T>, filter: &mut [bool]) {
180        if let Some(id) = self.miss.first() {
181            if !filter[id.get()] {
182                filter[id.get()] = true;
183                graph[id].shake(graph, filter);
184            }
185        }
186
187        if !filter[self.then.get()] {
188            filter[self.then.get()] = true;
189            graph[self.then].shake(graph, filter);
190        }
191    }
192}
193
194impl Pattern {
195    pub fn to_bytes(&self) -> Option<Vec<u8>> {
196        let mut out = Vec::with_capacity(self.len());
197
198        for range in self.iter() {
199            out.push(range.as_byte()?);
200        }
201
202        Some(out)
203    }
204}
205
206impl<T> From<&[T]> for Pattern
207where
208    T: Into<Range> + Copy,
209{
210    fn from(slice: &[T]) -> Self {
211        Pattern(slice.iter().copied().map(Into::into).collect())
212    }
213}
214
215impl<T> From<Vec<T>> for Pattern
216where
217    T: Into<Range>,
218{
219    fn from(vec: Vec<T>) -> Self {
220        Pattern(vec.into_iter().map(Into::into).collect())
221    }
222}
223
224impl From<&str> for Pattern {
225    fn from(slice: &str) -> Self {
226        slice.as_bytes().into()
227    }
228}
229
230#[cfg(test)]
231mod tests {
232    use super::*;
233    use crate::graph::Node;
234    use pretty_assertions::assert_eq;
235
236    #[test]
237    fn into_fork() {
238        let mut graph = Graph::new();
239
240        let leaf = graph.push(Node::Leaf("LEAF"));
241        let rope = Rope::new("foobar", leaf);
242
243        let fork = rope.into_fork(&mut graph);
244
245        assert_eq!(leaf, NodeId::new(1));
246        assert_eq!(fork, Fork::new().branch(b'f', NodeId::new(2)));
247        assert_eq!(graph[NodeId::new(2)], Rope::new("oobar", leaf));
248    }
249
250    #[test]
251    fn into_fork_one_byte() {
252        let mut graph = Graph::new();
253
254        let leaf = graph.push(Node::Leaf("LEAF"));
255        let rope = Rope::new("!", leaf);
256
257        let fork = rope.into_fork(&mut graph);
258
259        assert_eq!(leaf, NodeId::new(1));
260        assert_eq!(fork, Fork::new().branch(b'!', NodeId::new(1)));
261    }
262
263    #[test]
264    fn into_fork_miss_any() {
265        let mut graph = Graph::new();
266
267        let leaf = graph.push(Node::Leaf("LEAF"));
268        let rope = Rope::new("42", leaf).miss_any(NodeId::new(42));
269
270        let fork = rope.into_fork(&mut graph);
271
272        assert_eq!(leaf, NodeId::new(1));
273        assert_eq!(
274            fork,
275            Fork::new()
276                .branch(b'4', NodeId::new(2))
277                .miss(NodeId::new(42))
278        );
279        assert_eq!(
280            graph[NodeId::new(2)],
281            Rope::new("2", leaf).miss_any(NodeId::new(42))
282        );
283    }
284
285    #[test]
286    fn into_fork_miss_first() {
287        let mut graph = Graph::new();
288
289        let leaf = graph.push(Node::Leaf("LEAF"));
290        let rope = Rope::new("42", leaf).miss(Miss::First(NodeId::new(42)));
291
292        let fork = rope.into_fork(&mut graph);
293
294        assert_eq!(leaf, NodeId::new(1));
295        assert_eq!(
296            fork,
297            Fork::new()
298                .branch(b'4', NodeId::new(2))
299                .miss(NodeId::new(42))
300        );
301        assert_eq!(graph[NodeId::new(2)], Rope::new("2", leaf));
302    }
303
304    #[test]
305    fn split_at() {
306        let mut graph = Graph::new();
307
308        let leaf = graph.push(Node::Leaf("LEAF"));
309        let rope = Rope::new("foobar", leaf);
310
311        assert_eq!(rope.clone().split_at(6, &mut graph).unwrap(), rope);
312
313        let split = rope.split_at(3, &mut graph).unwrap();
314        let expected_id = NodeId::new(leaf.get() + 1);
315
316        assert_eq!(split, Rope::new("foo", expected_id));
317        assert_eq!(graph[expected_id], Rope::new("bar", leaf));
318    }
319
320    #[test]
321    fn pattern_to_bytes() {
322        let pat = Pattern::from("foobar");
323
324        assert_eq!(pat.to_bytes().unwrap(), b"foobar");
325
326        let ranges = Pattern::from(vec![0..=0, 42..=42, b'{'..=b'}']);
327
328        assert_eq!(ranges.to_bytes(), None);
329    }
330}
logos_codegen/graph/rope.rs

logos_codegen/graph/
rope.rs
