posix_regex/
tree.rs

1#[cfg(feature = "no_std")]
2use std::prelude::*;
3
4use std::fmt;
5use std::ops::{Index, IndexMut};
6
7use compile::{Token, Range};
8
9#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
10pub struct NodeId(usize);
11impl From<usize> for NodeId {
12    fn from(id: usize) -> Self {
13        NodeId(id)
14    }
15}
16impl From<NodeId> for usize {
17    fn from(id: NodeId) -> usize {
18        id.0
19    }
20}
21
22#[derive(Clone)]
23pub struct Node {
24    pub token: Token,
25    pub range: Range,
26    pub parent: Option<NodeId>,
27    pub next_sibling: Option<NodeId>,
28    pub child: Option<NodeId>
29}
30impl Node {
31    pub fn children<'a>(&self, arena: &'a Tree) -> NodeIter<'a> {
32        NodeIter(arena, self.child)
33    }
34}
35impl fmt::Debug for Node {
36    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
37        write!(f, "{:?} {:?}", self.token, self.range)?;
38        Ok(())
39    }
40}
41
42pub struct NodeIter<'a>(&'a Tree, Option<NodeId>);
43impl<'a> Iterator for NodeIter<'a> {
44    type Item = NodeId;
45    fn next(&mut self) -> Option<Self::Item> {
46        if let Some(next) = self.1 {
47            self.1 = self.0[next].next_sibling;
48            Some(next)
49        } else {
50            None
51        }
52    }
53}
54
55pub struct Checkpoint {
56    cursor: Option<NodeId>
57}
58
59#[derive(Default)]
60pub struct TreeBuilder {
61    arena: Vec<Node>,
62    parent: Option<NodeId>,
63    cursor: Option<NodeId>
64}
65impl TreeBuilder {
66    fn insert(&mut self, token: Token, range: Range) -> NodeId {
67        let id = NodeId::from(self.arena.len());
68        self.arena.push(Node {
69            token,
70            range,
71            parent: self.parent,
72            next_sibling: None,
73            child: None
74        });
75        if let Some(prev) = self.cursor {
76            self.arena[usize::from(prev)].next_sibling = Some(id);
77        }
78        if let Some(parent) = self.parent {
79            self.arena[usize::from(parent)].child = self.arena[usize::from(parent)].child.or(Some(id));
80        }
81        id
82    }
83    pub fn leaf(&mut self, token: Token, range: Range) {
84        self.cursor = Some(self.insert(token, range));
85    }
86    pub fn start_internal(&mut self, token: Token, range: Range) {
87        self.parent = Some(self.insert(token, range));
88        self.cursor = None;
89    }
90    pub fn finish_internal(&mut self) {
91        self.cursor = self.parent;
92        self.parent = self.parent.and_then(|parent| self.arena[usize::from(parent)].parent);
93    }
94    pub fn checkpoint(&self) -> Checkpoint {
95        Checkpoint {
96            cursor: self.cursor
97        }
98    }
99    pub fn start_internal_at(&mut self, checkpoint: Checkpoint, token: Token, range: Range) {
100        let parent = if let Some(from) = checkpoint.cursor {
101            let id = NodeId::from(self.arena.len());
102            self.arena.push(Node {
103                token,
104                range,
105                parent: self.parent,
106                next_sibling: None,
107                child: self.arena[usize::from(from)].next_sibling
108            });
109            self.arena[usize::from(from)].next_sibling = Some(id);
110            id
111        } else if let Some(parent) = self.parent {
112            let id = NodeId::from(self.arena.len());
113            self.arena.push(Node {
114                token,
115                range,
116                parent: self.parent,
117                next_sibling: None,
118                child: self.arena[usize::from(parent)].child
119            });
120            self.arena[usize::from(parent)].child = Some(id);
121            id
122        } else {
123            let id = NodeId::from(self.arena.len());
124            self.arena.push(Node {
125                token,
126                range,
127                parent: None,
128                next_sibling: None,
129                child: self.cursor
130            });
131            id
132        };
133        // Update parent
134        let mut next = self.arena[usize::from(parent)].child;
135        while let Some(node) = next {
136            let node = &mut self.arena[usize::from(node)];
137            next = node.next_sibling;
138            node.parent = Some(parent);
139        }
140        self.parent = Some(parent);
141        self.cursor = None;
142    }
143    pub fn finish(self) -> Tree {
144        assert!(self.cursor.is_some(), "no item");
145        let cursor = self.cursor.unwrap();
146
147        Tree {
148            arena: self.arena.into_boxed_slice(),
149            root: cursor
150        }
151    }
152}
153
154#[derive(Clone)]
155pub struct Tree {
156    pub arena: Box<[Node]>,
157    pub root: NodeId
158}
159impl Index<NodeId> for Tree {
160    type Output = Node;
161    fn index(&self, index: NodeId) -> &Node {
162        &self.arena[usize::from(index)]
163    }
164}
165impl IndexMut<NodeId> for Tree {
166    fn index_mut(&mut self, index: NodeId) -> &mut Node {
167        &mut self.arena[usize::from(index)]
168    }
169}
170impl fmt::Debug for Tree {
171    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
172        let mut next = Some(self.root);
173        let mut nested: usize = 0;
174        'outer: while let Some(id) = next {
175            let node = &self[id];
176            writeln!(f, "{:indent$}{:?}", "", node, indent = nested * 2)?;
177            if node.child.is_some() {
178                nested += 1;
179                next = node.child;
180            } else {
181                let mut me = Some(node);
182                while me.map(|me| me.next_sibling.is_none()).unwrap_or(false) {
183                    match nested.checked_sub(1) {
184                        Some(new) => nested = new,
185                        None => break 'outer
186                    }
187                    me = me.unwrap().parent.map(|id| &self[id]);
188                }
189                next = me.and_then(|me| me.next_sibling);
190            }
191        }
192        Ok(())
193    }
194}
195
196#[cfg(test)]
197mod tests {
198    use super::*;
199
200    fn sanity_check(tree: &Tree) {
201        let mut next = Some(tree.root);
202        let mut parent = None;
203        while let Some(id) = next {
204            let node = &tree[id];
205            assert_eq!(parent, node.parent);
206
207            if let Some(child) = node.child {
208                next = Some(child);
209                parent = Some(id);
210            } else {
211                let mut node = Some(id);
212                while node.map(|node| tree[node].next_sibling.is_none()).unwrap_or(false) {
213                    node = tree[node.unwrap()].parent;
214                }
215                next = node.and_then(|node| tree[node].next_sibling);
216                parent = node.and_then(|node| tree[node].parent);
217            }
218        }
219    }
220
221    #[test]
222    fn simple_builder() {
223        let mut builder = TreeBuilder::default();
224        builder.start_internal(Token::Root, Range(1, Some(1)));
225            builder.start_internal(Token::Alternative, Range(1, Some(1)));
226                builder.leaf(Token::Start, Range(1, Some(1)));
227                builder.start_internal(Token::Group(1), Range(1, Some(1)));
228                    builder.start_internal(Token::Alternative, Range(1, Some(1)));
229                        builder.leaf(Token::Any, Range(1, Some(1)));
230                    builder.finish_internal();
231                builder.finish_internal();
232            builder.finish_internal();
233            builder.start_internal(Token::Alternative, Range(1, Some(1)));
234                builder.leaf(Token::End, Range(1, Some(1)));
235            builder.finish_internal();
236        builder.finish_internal();
237
238        let tree = builder.finish();
239        sanity_check(&tree);
240
241        assert_eq!(
242            format!("{:?}", tree),
243            "\
244Root 1..1
245  Alternative 1..1
246    ^ 1..1
247    Group(1) 1..1
248      Alternative 1..1
249        . 1..1
250  Alternative 1..1
251    $ 1..1
252"
253        );
254    }
255    #[test]
256    fn builder_checkpoint() {
257        let mut builder = TreeBuilder::default();
258        builder.start_internal(Token::Root, Range(1, Some(1)));
259            let mut alternation = builder.checkpoint();
260                builder.leaf(Token::Start, Range(1, Some(1)));
261                let group = builder.checkpoint();
262                    builder.start_internal(Token::Alternative, Range(1, Some(1)));
263                        builder.leaf(Token::Any, Range(1, Some(1)));
264                    builder.finish_internal();
265                builder.start_internal_at(group, Token::Group(1), Range(1, Some(1)));
266                builder.finish_internal();
267            builder.start_internal_at(alternation, Token::Alternative, Range(1, Some(1)));
268            builder.finish_internal();
269            alternation = builder.checkpoint();
270                builder.leaf(Token::End, Range(1, Some(1)));
271            builder.start_internal_at(alternation, Token::Alternative, Range(1, Some(1)));
272            builder.finish_internal();
273        builder.finish_internal();
274
275        let tree = builder.finish();
276        sanity_check(&tree);
277
278        assert_eq!(
279            format!("{:?}", tree),
280            "\
281Root 1..1
282  Alternative 1..1
283    ^ 1..1
284    Group(1) 1..1
285      Alternative 1..1
286        . 1..1
287  Alternative 1..1
288    $ 1..1
289"
290        );
291    }
292}