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 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}