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