syntree/tree.rs
1use core::fmt;
2use core::ops::Range;
3
4use crate::links::Links;
5use crate::node::{Children, Event, Node, Walk, WalkEvents};
6#[cfg(feature = "std")]
7use crate::Error;
8use crate::{Flavor, Index, Pointer, Span, Storage, Width};
9
10/// A syntax tree.
11///
12/// A tree is constructed through a [Builder][crate::Builder] or by modifying an
13/// existing tree through a [ChangeSet][crate::edit::ChangeSet].
14///
15/// # Type parameters and bounds
16///
17/// The three type parameters of the tree determines the following properties:
18/// * `T` is the data stored in the tree.
19/// * `I` determines the numerical bounds of spans stored in the tree through
20/// the [Index] trait, if set to [Empty][crate::Empty] the tree does not store
21/// any spans.
22/// * `W` determines the bounds of pointers in the tree through the [Width]
23/// trait, this decides how many elements that can be stored in the tree.
24///
25/// To use the default values, use the [Builder::new][crate::Builder::new]
26/// constructor.
27pub struct Tree<T, F>
28where
29 T: Copy,
30 F: Flavor,
31{
32 /// Links in the tree.
33 tree: F::Storage<Links<T, F::Index, F::Pointer>>,
34 /// The span of the whole tree.
35 span: Span<F::Index>,
36 /// Token indexes for range searches. This contains the value of the token
37 /// cursor each time it is modified and allow for binary searching for
38 /// sequences of nodes which corresponds to the given index.
39 indexes: F::Indexes,
40 /// The first node in the tree.
41 first: Option<F::Pointer>,
42 /// The last node in the tree.
43 last: Option<F::Pointer>,
44}
45
46impl<T, F> Tree<T, F>
47where
48 T: Copy,
49 F: Flavor,
50{
51 /// Construct a new empty tree.
52 pub(crate) const fn new_with() -> Self {
53 Self {
54 tree: F::Storage::EMPTY,
55 span: Span::point(F::Index::EMPTY),
56 indexes: F::Indexes::EMPTY,
57 first: None,
58 last: None,
59 }
60 }
61
62 /// Construct a new tree with the given capacity.
63 #[cfg(feature = "std")]
64 pub(crate) fn with_capacity(capacity: usize) -> Result<Self, Error<F::Error>> {
65 Ok(Self {
66 tree: F::Storage::with_capacity(capacity)?,
67 span: Span::point(F::Index::EMPTY),
68 indexes: F::Indexes::EMPTY,
69 first: None,
70 last: None,
71 })
72 }
73
74 /// Get the span of the current node. The span of a node is the complete
75 /// span of all its children.
76 ///
77 /// # Examples
78 ///
79 /// ```
80 /// use syntree::Span;
81 ///
82 /// let tree = syntree::tree! {
83 /// "root" => {
84 /// "number" => {
85 /// ("lit", 5)
86 /// },
87 /// "ident" => {
88 /// ("lit", 3)
89 /// }
90 /// },
91 /// "root2" => {
92 /// ("whitespace", 5)
93 /// }
94 /// };
95 ///
96 /// assert_eq!(tree.span(), Span::new(0, 13));
97 /// # Ok::<_, Box<dyn core::error::Error>>(())
98 /// ```
99 pub const fn span(&self) -> &Span<F::Index> {
100 &self.span
101 }
102
103 /// Get mutable span from the tree.
104 pub(crate) fn span_mut(&mut self) -> &mut Span<F::Index> {
105 &mut self.span
106 }
107
108 /// The total number of elements in the tree.
109 ///
110 /// # Examples
111 ///
112 /// ```
113 /// let mut tree: syntree::Builder<()> = syntree::Builder::new();
114 /// let tree = tree.build()?;
115 ///
116 /// assert_eq!(tree.len(), 0);
117 ///
118 /// let mut tree = syntree::tree! {
119 /// "root" => {
120 /// "child" => {
121 /// ("token", 2)
122 /// },
123 /// ("whitespace", 1),
124 /// "child2" => {}
125 /// }
126 /// };
127 ///
128 /// assert_eq!(tree.len(), 5);
129 /// # Ok::<_, Box<dyn core::error::Error>>(())
130 /// ```
131 pub fn len(&self) -> usize {
132 self.tree.len()
133 }
134
135 /// Check if the current tree is empty. In that it doesn't have any
136 /// childrens at the root of the tree.
137 ///
138 /// # Examples
139 ///
140 /// ```
141 /// let mut tree: syntree::Builder<()> = syntree::Builder::new();
142 /// let tree = tree.build()?;
143 /// assert!(tree.is_empty());
144 /// # Ok::<_, Box<dyn core::error::Error>>(())
145 /// ```
146 pub fn is_empty(&self) -> bool {
147 self.tree.is_empty()
148 }
149
150 /// Get the capacity of the tree.
151 ///
152 /// # Examples
153 ///
154 /// ```
155 /// let mut tree: syntree::Builder<()> = syntree::Builder::new();
156 /// let tree = tree.build()?;
157 ///
158 /// assert_eq!(tree.capacity(), 0);
159 ///
160 /// let mut tree = syntree::tree! {
161 /// "root" => {
162 /// "child" => {
163 /// ("token", 2)
164 /// },
165 /// ("whitespace", 1),
166 /// "child2" => {}
167 /// }
168 /// };
169 ///
170 /// assert!(tree.capacity() >= 5);
171 /// # Ok::<_, Box<dyn core::error::Error>>(())
172 /// ```
173 pub fn capacity(&self) -> usize {
174 self.tree.capacity()
175 }
176
177 /// Get all root nodes in the tree.
178 ///
179 /// See [Children] for documentation.
180 pub fn children(&self) -> Children<'_, T, F> {
181 Children::new(&self.tree, self.first, self.last)
182 }
183
184 /// Walk the tree forwards in a depth-first fashion visiting every node
185 /// once.
186 ///
187 /// See [`Walk`] for documentation.
188 pub fn walk(&self) -> Walk<'_, T, F> {
189 Walk::new(&self.tree, self.first, Event::Next)
190 }
191
192 /// Walk the tree forwards in a depth-first fashion emitting events
193 /// indicating how the tree is being traversed.
194 ///
195 /// See [`WalkEvents`] for documentation.
196 pub fn walk_events(&self) -> WalkEvents<'_, T, F> {
197 WalkEvents::new(&self.tree, self.first, Event::Next)
198 }
199
200 /// Get the first child node in the tree.
201 ///
202 /// # Examples
203 ///
204 /// ```
205 /// let tree = syntree::tree! {
206 /// "root" => {},
207 /// "root2" => {}
208 /// };
209 ///
210 /// let root = tree.first().ok_or("missing root")?;
211 /// assert_eq!(root.value(), "root");
212 /// # Ok::<_, Box<dyn core::error::Error>>(())
213 /// ```
214 #[inline]
215 pub fn first(&self) -> Option<Node<'_, T, F>> {
216 self.get(self.first?)
217 }
218
219 /// Get the last child node in the tree.
220 ///
221 /// # Examples
222 ///
223 /// ```
224 /// let tree = syntree::tree! {
225 /// "root" => {},
226 /// "root2" => {}
227 /// };
228 ///
229 /// let root = tree.last().ok_or("missing root")?;
230 /// assert_eq!(root.value(), "root2");
231 /// # Ok::<_, Box<dyn core::error::Error>>(())
232 /// ```
233 #[inline]
234 pub fn last(&self) -> Option<Node<'_, T, F>> {
235 self.get(self.last?)
236 }
237
238 /// Get the tree links mutably.
239 pub(crate) fn links_mut(&mut self) -> (&mut Option<F::Pointer>, &mut Option<F::Pointer>) {
240 (&mut self.first, &mut self.last)
241 }
242
243 /// Get a mutable reference to an element in the tree.
244 pub(crate) fn get_mut(
245 &mut self,
246 id: F::Pointer,
247 ) -> Option<&mut Links<T, F::Index, F::Pointer>> {
248 self.tree.get_mut(id.get())
249 }
250
251 /// Push a new node into the tree with the specified links.
252 pub(crate) fn push(&mut self, links: Links<T, F::Index, F::Pointer>) -> Result<(), F::Error> {
253 self.tree.push(links)
254 }
255
256 /// Push the given index.
257 pub(crate) fn indexes_mut(&mut self) -> &mut F::Indexes {
258 &mut self.indexes
259 }
260
261 /// Optionally get the links at the given location.
262 pub(crate) fn links_at_mut(
263 &mut self,
264 index: F::Pointer,
265 ) -> Option<&mut Links<T, F::Index, F::Pointer>> {
266 self.tree.get_mut(index.get())
267 }
268
269 /// Get the ndoe at the given index.
270 ///
271 /// Note that an id might be re-used across different trees. This behavior
272 /// is never unsafe, but is not well-defined.
273 ///
274 /// # Examples
275 ///
276 /// ```
277 /// let tree = syntree::tree! {
278 /// "root" => {
279 /// "number" => {
280 /// ("lit", 5)
281 /// },
282 /// "ident" => {
283 /// ("lit", 3)
284 /// }
285 /// },
286 /// "root2" => {
287 /// ("whitespace", 5)
288 /// }
289 /// };
290 ///
291 /// let node = tree.first().and_then(|n| n.last()).ok_or("missing ident")?;
292 /// assert_eq!(node.value(), "ident");
293 ///
294 /// let id = node.id();
295 /// let node = tree.get(id).ok_or("missing ident")?;
296 /// assert_eq!(node.value(), "ident");
297 /// # Ok::<_, Box<dyn core::error::Error>>(())
298 /// ```
299 pub fn get(&self, id: F::Pointer) -> Option<Node<'_, T, F>> {
300 let cur = self.tree.get(id.get())?;
301 Some(Node::new(cur, &self.tree))
302 }
303
304 /// Access the [Span] of the node as a [Range].
305 ///
306 /// # Examples
307 ///
308 /// ```
309 /// let tree = syntree::tree! {
310 /// "root" => {
311 /// "number" => {
312 /// ("lit", 5)
313 /// },
314 /// "ident" => {
315 /// ("lit", 3)
316 /// }
317 /// },
318 /// "root2" => {
319 /// ("whitespace", 5)
320 /// }
321 /// };
322 ///
323 /// assert_eq!(tree.range(), 0..13);
324 /// # Ok::<_, Box<dyn core::error::Error>>(())
325 /// ```
326 #[must_use]
327 pub fn range(&self) -> Range<usize> {
328 self.span.range()
329 }
330
331 /// Query for the node that matches the given range.
332 ///
333 /// This query finds the node which contains the entirety of the given
334 /// [Range].
335 ///
336 /// # Examples
337 ///
338 /// ```
339 /// let tree = syntree::tree! {
340 /// "root" => {
341 /// "child1" => {
342 /// ("token1", 3)
343 /// },
344 /// "child2" => {
345 /// "nested1" => {
346 /// ("token1", 4),
347 /// },
348 /// ("token4", 1),
349 /// },
350 /// "child3" => {
351 /// ("token5", 5)
352 /// }
353 /// },
354 /// "root2" => {}
355 /// };
356 ///
357 /// let node = tree.node_with_range(0..0).ok_or("missing 0")?;
358 /// assert_eq!(node.value(), "child1");
359 ///
360 /// let node = tree.node_with_range(0..3).ok_or("missing 0")?;
361 /// assert_eq!(node.value(), "child1");
362 ///
363 /// let node = tree.node_with_range(3..3).ok_or("missing 3")?;
364 /// assert_eq!(node.value(), "nested1");
365 ///
366 /// let node = tree.node_with_range(3..7).ok_or("missing 3..7")?;
367 /// assert_eq!(node.value(), "nested1");
368 ///
369 /// let node = tree.node_with_range(7..7).ok_or("missing 7")?;
370 /// assert_eq!(node.value(), "child2");
371 ///
372 /// let node = tree.node_with_range(7..8).ok_or("missing 7..8")?;
373 /// assert_eq!(node.value(), "child2");
374 ///
375 /// let node = tree.node_with_range(8..8).ok_or("missing 8")?;
376 /// assert_eq!(node.value(), "child3");
377 ///
378 /// let node = tree.node_with_range(8..13).ok_or("missing 9")?;
379 /// assert_eq!(node.value(), "child3");
380 ///
381 /// let node = tree.node_with_range(2..4).ok_or("missing 2..4")?;
382 /// assert_eq!(node.value(), "root");
383 /// # Ok::<_, Box<dyn core::error::Error>>(())
384 /// ```
385 ///
386 /// Range queries work as expected with checkpoints:
387 ///
388 /// ```
389 /// let mut tree = syntree::Builder::new();
390 ///
391 /// let c = tree.checkpoint()?;
392 /// tree.open("child")?;
393 /// tree.token("lit", 3)?;
394 /// tree.close()?;
395 /// tree.close_at(&c, "root")?;
396 /// tree.token("sibling", 3)?;
397 ///
398 /// let tree = tree.build()?;
399 ///
400 /// let child = tree.node_with_range(0..3).ok_or("missing at 0..3")?;
401 /// assert_eq!(child.value(), "child");
402 /// # Ok::<_, Box<dyn core::error::Error>>(())
403 /// ```
404 #[must_use]
405 pub fn node_with_range(&self, span: Range<usize>) -> Option<Node<'_, T, F>> {
406 let start = F::Index::from_usize(span.start)?;
407 let end = F::Index::from_usize(span.end)?;
408 self.node_with_span_internal(start, end)
409 }
410
411 /// Query the tree for the first node which encapsulates the whole `span`.
412 ///
413 /// This query finds the node which contains the entirety of the given
414 /// [Span].
415 ///
416 /// # Examples
417 ///
418 /// ```
419 /// use syntree::Span;
420 ///
421 /// let tree = syntree::tree! {
422 /// "root" => {
423 /// "child1" => {
424 /// ("token1", 3)
425 /// },
426 /// "child2" => {
427 /// "nested1" => {
428 /// ("token1", 4),
429 /// },
430 /// ("token4", 1),
431 /// },
432 /// "child3" => {
433 /// ("token5", 5)
434 /// }
435 /// },
436 /// "root2" => {}
437 /// };
438 ///
439 /// let node = tree.node_with_span(Span::point(0)).ok_or("missing 0")?;
440 /// assert_eq!(node.value(), "child1");
441 ///
442 /// let node = tree.node_with_span(Span::new(0, 3)).ok_or("missing 0")?;
443 /// assert_eq!(node.value(), "child1");
444 ///
445 /// let node = tree.node_with_span(Span::point(3)).ok_or("missing 3")?;
446 /// assert_eq!(node.value(), "nested1");
447 ///
448 /// let node = tree.node_with_span(Span::new(3, 7)).ok_or("missing 3..7")?;
449 /// assert_eq!(node.value(), "nested1");
450 ///
451 /// let node = tree.node_with_span(Span::point(7)).ok_or("missing 7")?;
452 /// assert_eq!(node.value(), "child2");
453 ///
454 /// let node = tree.node_with_span(Span::new(7, 8)).ok_or("missing 7..8")?;
455 /// assert_eq!(node.value(), "child2");
456 ///
457 /// let node = tree.node_with_span(Span::point(8)).ok_or("missing 8")?;
458 /// assert_eq!(node.value(), "child3");
459 ///
460 /// let node = tree.node_with_span(Span::new(8, 13)).ok_or("missing 9")?;
461 /// assert_eq!(node.value(), "child3");
462 ///
463 /// let node = tree.node_with_span(Span::new(2, 4)).ok_or("missing 2..4")?;
464 /// assert_eq!(node.value(), "root");
465 /// # Ok::<_, Box<dyn core::error::Error>>(())
466 /// ```
467 ///
468 /// Range queries work as expected with checkpoints:
469 ///
470 /// ```
471 /// use syntree::{Span, Builder};
472 ///
473 /// let mut tree = Builder::new();
474 ///
475 /// let c = tree.checkpoint()?;
476 ///
477 /// tree.open("child1")?;
478 /// tree.token("lit", 3)?;
479 /// tree.close()?;
480 ///
481 /// tree.open("child2")?;
482 /// tree.token("lit", 2)?;
483 /// tree.close()?;
484 ///
485 /// tree.close_at(&c, "root")?;
486 ///
487 /// let tree = tree.build()?;
488 ///
489 /// let child = tree.node_with_span(Span::point(0)).ok_or("missing at point 5")?;
490 /// assert_eq!(child.value(), "child1");
491 ///
492 /// let child = tree.node_with_span(Span::new(0, 3)).ok_or("missing at 0..3")?;
493 /// assert_eq!(child.value(), "child1");
494 ///
495 /// let child = tree.node_with_span(Span::new(3, 5)).ok_or("missing at 3..5")?;
496 /// assert_eq!(child.value(), "child2");
497 ///
498 /// let child = tree.node_with_span(Span::new(4, 5)).ok_or("missing at 4..5")?;
499 /// assert_eq!(child.value(), "child2");
500 ///
501 /// let child = tree.node_with_span(Span::new(3, 4)).ok_or("missing at 3..4")?;
502 /// assert_eq!(child.value(), "child2");
503 ///
504 /// let child = tree.node_with_span(Span::point(3)).ok_or("missing at point 5")?;
505 /// assert_eq!(child.value(), "child2");
506 ///
507 /// let child = tree.node_with_span(Span::new(2, 5)).ok_or("missing at 2..5")?;
508 /// assert_eq!(child.value(), "root");
509 /// # Ok::<_, Box<dyn core::error::Error>>(())
510 /// ```
511 #[must_use]
512 pub fn node_with_span(&self, span: Span<F::Index>) -> Option<Node<'_, T, F>> {
513 self.node_with_span_internal(span.start, span.end)
514 }
515
516 fn node_with_span_internal(&self, start: F::Index, end: F::Index) -> Option<Node<'_, T, F>> {
517 let result = self.indexes.binary_search_by(|f| f.index.cmp(&start));
518
519 let n = match result {
520 Ok(n) => n.saturating_add(1),
521 Err(n) => n,
522 };
523
524 let mut node = self.get(self.indexes.get(n)?.id)?;
525
526 while let Some(parent) = node.parent() {
527 node = parent;
528
529 if parent.span().end >= end {
530 break;
531 }
532 }
533
534 Some(node)
535 }
536}
537
538impl<T, F> Clone for Tree<T, F>
539where
540 T: Copy,
541 F: Flavor<Indexes: Clone, Width: Width<Pointer: Clone>>,
542 F::Storage<Links<T, F::Index, F::Pointer>>: Clone,
543{
544 #[inline]
545 fn clone(&self) -> Self {
546 Self {
547 tree: self.tree.clone(),
548 span: self.span,
549 indexes: self.indexes.clone(),
550 first: self.first,
551 last: self.last,
552 }
553 }
554}
555
556impl<T, F> Default for Tree<T, F>
557where
558 T: Copy,
559 F: Flavor,
560{
561 #[inline]
562 fn default() -> Self {
563 Self::new_with()
564 }
565}
566
567impl<T, A, B> PartialEq<Tree<T, A>> for Tree<T, B>
568where
569 T: Copy + PartialEq,
570 A: Flavor,
571 B: Flavor<Index: PartialEq<A::Index>>,
572{
573 fn eq(&self, other: &Tree<T, A>) -> bool {
574 struct Item<'a, T, F>((isize, Node<'a, T, F>))
575 where
576 T: Copy,
577 F: Flavor;
578
579 // NB: this is needed because the constraints on tuples doesn't allow
580 // for `A` and `B` to be different.
581 impl<'a, T, A, B> PartialEq<Item<'a, T, A>> for Item<'a, T, B>
582 where
583 T: Copy + PartialEq,
584 A: Flavor,
585 B: Flavor<Index: PartialEq<A::Index>>,
586 {
587 #[inline]
588 fn eq(&self, other: &Item<'a, T, A>) -> bool {
589 self.0 .0 == other.0 .0 && self.0 .1.eq(&other.0 .1)
590 }
591 }
592
593 self.walk()
594 .with_depths()
595 .map(Item)
596 .eq(other.walk().with_depths().map(Item))
597 }
598}
599
600impl<T, F> Eq for Tree<T, F>
601where
602 T: Copy + Eq,
603 F: Flavor<Index: Eq>,
604{
605}
606
607impl<T, F> fmt::Debug for Tree<T, F>
608where
609 T: Copy + fmt::Debug,
610 F: Flavor<Index: fmt::Debug>,
611{
612 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
613 struct List<'a, T, F>(&'a Tree<T, F>)
614 where
615 T: Copy,
616 F: Flavor;
617
618 impl<T, F> fmt::Debug for List<'_, T, F>
619 where
620 T: Copy + fmt::Debug,
621 F: Flavor<Index: fmt::Debug>,
622 {
623 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
624 f.debug_list().entries(self.0.walk().with_depths()).finish()
625 }
626 }
627
628 f.debug_tuple("Tree").field(&List(self)).finish()
629 }
630}