syntree/builder.rs
1mod checkpoint;
2
3use core::cell::Cell;
4use core::fmt;
5
6use crate::links::Links;
7use crate::{
8 Error, Flavor, FlavorDefault, Index, Length, Pointer, Span, Storage, Tree, TreeIndex, Width,
9};
10
11pub use self::checkpoint::Checkpoint;
12
13/// A builder for a [Tree].
14///
15/// This maintains a stack of nodes being built which has to be balanced with
16/// calls to [`Builder::open`] and [`Builder::close`].
17///
18/// # Type parameters and bounds
19///
20/// The two type parameters of the builder determine the following properties:
21/// * `T` is the data stored in the tree.
22/// * `F` is the [Flavor], declared with [`flavor!`][crate::flavor!]. Its
23/// [`Index`][Flavor::Index] determines the numerical bounds of spans, and if
24/// set to [Empty][crate::Empty] the tree does not store any spans. Its
25/// [`Width`][Flavor::Width] determines the bounds of pointers in the tree,
26/// which decides how many nodes can be stored in it. It also selects the
27/// [`Storage`][Flavor::Storage] used and its error type.
28///
29/// To use the default values, use the [Builder::new][Builder::new] constructor.
30///
31/// # Errors
32///
33/// Besides the errors documented on each method, any method which adds a node
34/// or token can fail with [`Error::Flavor`] if the flavor's storage fails to
35/// grow.
36///
37/// # Examples
38///
39/// ```
40/// let mut tree = syntree::Builder::new();
41///
42/// tree.open("root")?;
43/// tree.open("child")?;
44/// tree.close()?;
45/// tree.open("child")?;
46/// tree.close()?;
47/// tree.close()?;
48///
49/// let tree = tree.build()?;
50///
51/// let expected = syntree::tree! {
52/// "root" => {
53/// "child" => {},
54/// "child" => {}
55/// }
56/// };
57///
58/// assert_eq!(tree, expected);
59/// # Ok::<_, Box<dyn core::error::Error>>(())
60/// ```
61pub struct Builder<T, F = FlavorDefault>
62where
63 T: Copy,
64 F: Flavor,
65{
66 /// Data in the tree being built.
67 tree: Tree<T, F>,
68 /// The last checkpoint that was handed out.
69 checkpoint: Option<Checkpoint<F::Pointer>>,
70 /// Reference the current parent to the node being built. It itself has its
71 /// parent set in the tree, so that is what is used to traverse ancestors of
72 /// a node.
73 parent: Option<F::Pointer>,
74 /// Reference to last sibling inserted.
75 sibling: Option<F::Pointer>,
76 /// The current cursor.
77 cursor: F::Index,
78}
79
80impl<T> Builder<T, FlavorDefault>
81where
82 T: Copy,
83{
84 /// Construct a new tree with a default [`Span`] based on `u32`.
85 ///
86 /// For a constructor that can use custom bounds, use [Builder::new_with].
87 ///
88 /// # Examples
89 ///
90 /// ```
91 /// let mut tree = syntree::Builder::new();
92 ///
93 /// tree.open("root")?;
94 ///
95 /// tree.open("child")?;
96 /// tree.token("token", 5)?;
97 /// tree.close()?;
98 ///
99 /// tree.open("child2")?;
100 /// tree.close()?;
101 ///
102 /// tree.close()?;
103 ///
104 /// let tree = tree.build()?;
105 ///
106 /// let expected = syntree::tree! {
107 /// "root" => {
108 /// "child" => {
109 /// ("token", 5)
110 /// },
111 /// "child2" => {}
112 /// }
113 /// };
114 ///
115 /// assert_eq!(tree, expected);
116 /// # Ok::<_, Box<dyn core::error::Error>>(())
117 /// ```
118 #[must_use]
119 pub const fn new() -> Self {
120 Self::new_with()
121 }
122}
123
124impl<T, F> Builder<T, F>
125where
126 T: Copy,
127 F: Flavor,
128{
129 /// Construct a new tree with a custom span.
130 ///
131 /// To build a tree with default bounds, see [Builder::new]. Also see the
132 /// [Builder] documentation for what the different bounds means.
133 ///
134 /// # Examples
135 ///
136 /// ```
137 /// use syntree::{Builder, Empty, EmptyVec, TreeIndex, Tree};
138 ///
139 /// syntree::flavor! {
140 /// struct FlavorEmpty {
141 /// type Index = Empty;
142 /// type Width = u32;
143 /// type Indexes = EmptyVec<TreeIndex<Self>>;
144 /// }
145 /// }
146 ///
147 /// let mut tree: Builder<_, FlavorEmpty> = Builder::new_with();
148 ///
149 /// tree.open("root")?;
150 ///
151 /// tree.open("child")?;
152 /// tree.token("token", Empty)?;
153 /// tree.close()?;
154 ///
155 /// tree.open("child2")?;
156 /// tree.close()?;
157 ///
158 /// tree.close()?;
159 ///
160 /// let tree = tree.build()?;
161 ///
162 /// let expected: Tree<_, FlavorEmpty> = syntree::tree_with! {
163 /// "root" => {
164 /// "child" => {
165 /// "token"
166 /// },
167 /// "child2" => {}
168 /// }
169 /// };
170 ///
171 /// assert_eq!(tree, expected);
172 /// # Ok::<_, Box<dyn core::error::Error>>(())
173 /// ```
174 #[must_use]
175 pub const fn new_with() -> Self {
176 Builder {
177 tree: Tree::new_with(),
178 parent: None,
179 checkpoint: None,
180 sibling: None,
181 cursor: F::Index::EMPTY,
182 }
183 }
184
185 #[cfg(feature = "std")]
186 pub(crate) fn with_capacity(capacity: usize) -> Result<Self, Error<F::Error>> {
187 Ok(Builder {
188 tree: Tree::with_capacity(capacity)?,
189 parent: None,
190 checkpoint: None,
191 sibling: None,
192 cursor: F::Index::EMPTY,
193 })
194 }
195
196 /// Get a reference to the current cursor position of the syntax tree.
197 ///
198 /// The cursor position is the position in which it's been advanced so far
199 /// as a result of calls to [Builder::token] and indicates the current
200 /// starting index of the next span.
201 ///
202 /// # Examples
203 ///
204 /// ```
205 /// let mut tree = syntree::Builder::new();
206 ///
207 /// assert_eq!(*tree.cursor(), 0);
208 /// tree.open("child")?;
209 /// assert_eq!(*tree.cursor(), 0);
210 /// tree.token("lit", 4)?;
211 /// assert_eq!(*tree.cursor(), 4);
212 /// tree.close()?;
213 /// assert_eq!(*tree.cursor(), 4);
214 ///
215 /// let tree = tree.build()?;
216 ///
217 /// let expected = syntree::tree! {
218 /// "child" => {
219 /// ("lit", 4)
220 /// }
221 /// };
222 ///
223 /// assert_eq!(tree, expected);
224 /// # Ok::<_, Box<dyn core::error::Error>>(())
225 /// ```
226 #[inline]
227 pub const fn cursor(&self) -> &F::Index {
228 &self.cursor
229 }
230
231 /// Set the cursor position of the syntax tree.
232 ///
233 /// This is used to implicitly set spans when using spanless constructions
234 /// methods. Range queries such as [`Tree::node_with_range`] assume that
235 /// tokens are added in non-decreasing order, so the cursor should not be
236 /// moved backwards past an already added token.
237 ///
238 /// # Examples
239 ///
240 /// ```
241 /// use syntree::Span;
242 ///
243 /// let mut tree = syntree::Builder::new();
244 ///
245 /// tree.open("child")?;
246 /// tree.token("lit", 4)?;
247 /// // Skip two units of input which are not part of the tree.
248 /// tree.set_cursor(6);
249 /// assert_eq!(*tree.cursor(), 6);
250 /// tree.token("lit", 2)?;
251 /// tree.close()?;
252 ///
253 /// let tree = tree.build()?;
254 ///
255 /// let child = tree.first().ok_or("missing child")?;
256 /// assert_eq!(child.span(), &Span::new(0, 8));
257 ///
258 /// let spans = child.children().map(|n| *n.span()).collect::<Vec<_>>();
259 /// assert_eq!(spans, [Span::new(0, 4), Span::new(6, 8)]);
260 /// # Ok::<_, Box<dyn core::error::Error>>(())
261 /// ```
262 pub fn set_cursor(&mut self, cursor: F::Index) {
263 self.cursor = cursor;
264 }
265
266 /// Start a node with the given `data`.
267 ///
268 /// This pushes a new link with the given type onto the stack which links
269 /// itself onto the last sibling node that was introduced either through
270 /// [`Builder::close`], [`Builder::close_at`], or
271 /// [`Builder::close_at_with`].
272 ///
273 /// # Errors
274 ///
275 /// Errors with [`Error::Overflow`] in case we run out of node
276 /// identifiers.
277 ///
278 /// # Examples
279 ///
280 /// ```
281 /// let mut tree = syntree::Builder::new();
282 ///
283 /// tree.open("root")?;
284 ///
285 /// tree.open("child")?;
286 /// tree.close()?;
287 ///
288 /// tree.open("child")?;
289 /// tree.close()?;
290 ///
291 /// tree.close()?;
292 /// # Ok::<_, Box<dyn core::error::Error>>(())
293 /// ```
294 pub fn open(&mut self, data: T) -> Result<F::Pointer, Error<F::Error>> {
295 let id = self.insert(data, Span::point(self.cursor))?;
296 self.parent = Some(id);
297 Ok(id)
298 }
299
300 /// Start a node with the given `data` and span.
301 ///
302 /// This pushes a new link with the given type onto the stack which links
303 /// itself onto the last sibling node that was introduced either through
304 /// [`Builder::close`], [`Builder::close_at`] or [`Builder::close_at_with`].
305 ///
306 /// This does not advance the cursor position, in order to fix tree
307 /// construction use [`Builder::set_cursor`].
308 ///
309 /// # Errors
310 ///
311 /// Errors with [`Error::Overflow`] in case we run out of node
312 /// identifiers.
313 ///
314 /// # Examples
315 ///
316 /// ```
317 /// use syntree::Span;
318 ///
319 /// let mut tree = syntree::Builder::new();
320 ///
321 /// tree.open("root")?;
322 ///
323 /// tree.open_with("child", Span::new(0, 3))?;
324 /// tree.close()?;
325 ///
326 /// tree.open_with("child", Span::new(3, 6))?;
327 /// tree.close()?;
328 ///
329 /// tree.close()?;
330 ///
331 /// let tree = tree.build()?;
332 ///
333 /// let expected = syntree::tree! {
334 /// ("root", (0, 6)) => {
335 /// ("child", (0, 3)) => {},
336 /// ("child", (3, 6)) => {}
337 /// }
338 /// };
339 ///
340 /// assert_eq!(tree, expected);
341 /// # Ok::<_, Box<dyn core::error::Error>>(())
342 /// ```
343 pub fn open_with(
344 &mut self,
345 data: T,
346 span: Span<F::Index>,
347 ) -> Result<F::Pointer, Error<F::Error>> {
348 let id = self.insert(data, span)?;
349 self.parent = Some(id);
350 Ok(id)
351 }
352
353 /// End a node being built.
354 ///
355 /// This will pop a value of the stack, and set that value as the next
356 /// sibling which will be used with [`Builder::open`].
357 ///
358 /// # Errors
359 ///
360 /// This call must be balanced with a prior call to [`Builder::open`].
361 /// If not this will result in an [`Error::CloseError`] being raised.
362 ///
363 /// # Examples
364 ///
365 /// ```
366 /// let mut tree = syntree::Builder::new();
367 ///
368 /// tree.open("root")?;
369 ///
370 /// tree.open("child")?;
371 /// tree.close()?;
372 ///
373 /// tree.open("child")?;
374 /// tree.close()?;
375 ///
376 /// tree.close()?;
377 /// # Ok::<_, Box<dyn core::error::Error>>(())
378 /// ```
379 pub fn close(&mut self) -> Result<(), Error<F::Error>> {
380 let head = self.parent.take().ok_or(Error::CloseError)?;
381
382 self.sibling = Some(head);
383
384 let &mut Links { parent, span, .. } = self
385 .tree
386 .get_mut(head)
387 .ok_or_else(|| Error::MissingNode(head.get()))?;
388
389 if let Some(id) = parent {
390 let parent = self
391 .tree
392 .get_mut(id)
393 .ok_or_else(|| Error::MissingNode(id.get()))?;
394
395 parent.span = parent.span.join(&span);
396 self.parent = Some(id);
397 }
398
399 self.cursor = span.end;
400 Ok(())
401 }
402
403 /// Declare a token with the specified `value` and a corresponding `len`.
404 ///
405 /// A token is always a terminating element without children.
406 ///
407 /// # Errors
408 ///
409 /// Errors with [`Error::Overflow`] in case we run out of node
410 /// identifiers.
411 ///
412 /// # Examples
413 ///
414 /// ```
415 /// let mut tree = syntree::Builder::new();
416 ///
417 /// tree.open("child")?;
418 /// tree.token("lit", 4)?;
419 /// tree.close()?;
420 ///
421 /// let tree = tree.build()?;
422 ///
423 /// let expected = syntree::tree! {
424 /// "child" => {
425 /// ("lit", 4)
426 /// }
427 /// };
428 ///
429 /// assert_eq!(tree, expected);
430 /// # Ok::<_, Box<dyn core::error::Error>>(())
431 /// ```
432 pub fn token(&mut self, value: T, len: F::Length) -> Result<F::Pointer, Error<F::Error>> {
433 let start = self.cursor;
434
435 if !len.is_empty() {
436 self.cursor = self.cursor.checked_add_len(len).ok_or(Error::Overflow)?;
437 }
438
439 let id = self.insert(value, Span::new(start, self.cursor))?;
440 self.sibling = Some(id);
441
442 if !len.is_empty() {
443 self.tree.indexes_mut().push(TreeIndex {
444 index: self.cursor,
445 id,
446 })?;
447 }
448
449 Ok(id)
450 }
451
452 /// Insert a token with a custom span.
453 ///
454 /// The span is joined into the spans of the enclosing nodes and the tree.
455 /// Range queries such as [`Tree::node_with_range`] assume that tokens are
456 /// added in non-decreasing order of their spans, so a token should not
457 /// start before the end of the previous one.
458 ///
459 /// # Errors
460 ///
461 /// Errors with [`Error::Overflow`] in case we run out of node identifiers.
462 ///
463 /// # Examples
464 ///
465 /// ```
466 /// use syntree::Span;
467 ///
468 /// let mut tree = syntree::Builder::new();
469 ///
470 /// tree.open_with("child", Span::new(0, 10))?;
471 /// tree.token_with("lit", Span::new(2, 4))?;
472 /// tree.token_with("lit2", Span::new(4, 6))?;
473 /// tree.close()?;
474 ///
475 /// let tree = tree.build()?;
476 ///
477 /// let child = tree.first().ok_or("missing child")?;
478 /// assert_eq!(child.span(), &Span::new(0, 10));
479 ///
480 /// let spans = child.children().map(|n| (n.value(), *n.span())).collect::<Vec<_>>();
481 /// assert_eq!(spans, [("lit", Span::new(2, 4)), ("lit2", Span::new(4, 6))]);
482 ///
483 /// assert_eq!(tree.span(), &Span::new(0, 10));
484 /// # Ok::<_, Box<dyn core::error::Error>>(())
485 /// ```
486 ///
487 /// Tokens with spans forces the cursor to be set to the end of the span.
488 ///
489 /// ```
490 /// use syntree::Span;
491 ///
492 /// let mut tree = syntree::Builder::new();
493 ///
494 /// tree.open("child")?;
495 /// tree.token_with("lit", Span::new(2, 4))?;
496 /// tree.token_with("lit2", Span::new(4, 6))?;
497 /// assert_eq!(*tree.cursor(), 6);
498 /// tree.token("lit3", 6)?;
499 /// tree.close()?;
500 ///
501 /// let tree = tree.build()?;
502 ///
503 /// let child = tree.first().ok_or("missing child")?;
504 /// assert_eq!(child.span(), &Span::new(0, 12));
505 ///
506 /// let lit3 = child.last().ok_or("missing lit3")?;
507 /// assert_eq!(lit3.value(), "lit3");
508 /// assert_eq!(lit3.span(), &Span::new(6, 12));
509 ///
510 /// assert_eq!(tree.span(), &Span::new(0, 12));
511 /// # Ok::<_, Box<dyn core::error::Error>>(())
512 /// ```
513 pub fn token_with(
514 &mut self,
515 value: T,
516 span: Span<F::Index>,
517 ) -> Result<F::Pointer, Error<F::Error>> {
518 let id = self.insert(value, span)?;
519 self.sibling = Some(id);
520
521 if !span.is_empty() {
522 self.tree.indexes_mut().push(TreeIndex {
523 index: span.end,
524 id,
525 })?;
526 }
527
528 self.cursor = span.end;
529 Ok(id)
530 }
531
532 /// Declare a token with the specified `value` and an empty length.
533 ///
534 /// A token is always a terminating element without children.
535 ///
536 /// # Errors
537 ///
538 /// Errors with [`Error::Overflow`] in case we run out of node
539 /// identifiers.
540 ///
541 /// # Examples
542 ///
543 /// ```
544 /// let mut tree = syntree::Builder::new();
545 ///
546 /// tree.open("child")?;
547 /// tree.token_empty("lit")?;
548 /// tree.close()?;
549 ///
550 /// let tree = tree.build()?;
551 ///
552 /// let expected = syntree::tree! {
553 /// "child" => {
554 /// "lit"
555 /// }
556 /// };
557 ///
558 /// assert_eq!(tree, expected);
559 /// # Ok::<_, Box<dyn core::error::Error>>(())
560 /// ```
561 pub fn token_empty(&mut self, value: T) -> Result<F::Pointer, Error<F::Error>> {
562 self.token(value, F::Length::EMPTY)
563 }
564
565 /// Get a checkpoint corresponding to the current position in the tree.
566 ///
567 /// # Mixing checkpoints
568 ///
569 /// Note that using checkpoints from a different tree doesn't have a
570 /// well-specified behavior - it might seemingly work or it might raise an
571 /// error during closing such as [`Error::MissingNode`].
572 ///
573 /// The following *is not* well-defined, here we're using a checkpoint for a
574 /// different tree but it "just happens" to work because both trees have
575 /// identical internal topologies:
576 ///
577 /// ```
578 /// use syntree::{Builder, Error};
579 ///
580 /// let mut a = Builder::new();
581 /// let mut b = Builder::new();
582 ///
583 /// let c = b.checkpoint()?;
584 ///
585 /// a.open("child")?;
586 /// a.close()?;
587 ///
588 /// b.open("child")?;
589 /// b.close()?;
590 ///
591 /// // Checkpoint use from different tree.
592 /// a.close_at(&c, "root")?;
593 ///
594 /// let unexpected = syntree::tree! {
595 /// "root" => {
596 /// "child"
597 /// }
598 /// };
599 ///
600 /// assert_eq!(a.build()?, unexpected);
601 /// # Ok::<_, Box<dyn core::error::Error>>(())
602 /// ```
603 ///
604 /// # Errors
605 ///
606 /// Errors with [`Error::Overflow`] in case we run out of node
607 /// identifiers.
608 ///
609 /// # Examples
610 ///
611 /// ```
612 /// let mut tree = syntree::Builder::new();
613 ///
614 /// let c = tree.checkpoint()?;
615 /// tree.open("child")?;
616 /// tree.token("lit", 3)?;
617 /// tree.close()?;
618 /// tree.close_at(&c, "root")?;
619 ///
620 /// let tree = tree.build()?;
621 ///
622 /// let expected = syntree::tree! {
623 /// "root" => {
624 /// "child" => {
625 /// ("lit", 3)
626 /// }
627 /// }
628 /// };
629 ///
630 /// assert_eq!(tree, expected);
631 /// # Ok::<_, Box<dyn core::error::Error>>(())
632 /// ```
633 pub fn checkpoint(&mut self) -> Result<Checkpoint<F::Pointer>, Error<F::Error>> {
634 let node = F::Pointer::new(self.tree.len()).ok_or(Error::Overflow)?;
635
636 if let Some(c) = &self.checkpoint {
637 if c.node() == node && c.parent() == self.parent {
638 return Ok(c.clone());
639 }
640 }
641
642 let c = Checkpoint::new(node, self.parent);
643 self.checkpoint = Some(c.clone());
644 Ok(c)
645 }
646
647 /// Insert a node that wraps from the given checkpointed location.
648 ///
649 /// # Errors
650 ///
651 /// The checkpoint being closed *must* be a sibling. Otherwise a
652 /// [`Error::CloseAtError`] will be raised.
653 ///
654 /// This might also sporadically error with [`Error::MissingNode`], in case
655 /// a checkpoint is used that was constructed from another tree.
656 ///
657 /// # Examples
658 ///
659 /// ```
660 /// let mut tree = syntree::Builder::new();
661 ///
662 /// let c = tree.checkpoint()?;
663 /// tree.token("lit", 3)?;
664 /// tree.close_at(&c, "root")?;
665 ///
666 /// let tree = tree.build()?;
667 ///
668 /// let expected = syntree::tree! {
669 /// "root" => {
670 /// ("lit", 3)
671 /// }
672 /// };
673 ///
674 /// assert_eq!(tree, expected);
675 /// # Ok::<_, Box<dyn core::error::Error>>(())
676 /// ```
677 ///
678 /// More complex example:
679 ///
680 /// ```
681 /// let mut tree = syntree::Builder::new();
682 ///
683 /// let c = tree.checkpoint()?;
684 ///
685 /// tree.open("number")?;
686 /// tree.token("lit", 3)?;
687 /// tree.close()?;
688 ///
689 /// tree.token("whitespace", 1)?;
690 ///
691 /// tree.open("number")?;
692 /// tree.token("lit", 2)?;
693 /// tree.close()?;
694 ///
695 /// tree.close_at(&c, "root")?;
696 ///
697 /// let tree = tree.build()?;
698 ///
699 /// let expected = syntree::tree! {
700 /// "root" => {
701 /// "number" => {
702 /// ("lit", 3)
703 /// },
704 /// ("whitespace", 1),
705 /// "number" => {
706 /// ("lit", 2)
707 /// },
708 /// }
709 /// };
710 ///
711 /// assert_eq!(tree, expected);
712 /// # Ok::<_, Box<dyn core::error::Error>>(())
713 /// ```
714 ///
715 /// Adding a token after a checkpoint:
716 ///
717 /// ```
718 /// let mut tree = syntree::Builder::new();
719 ///
720 /// let c = tree.checkpoint()?;
721 /// tree.open("child")?;
722 /// tree.token("lit", 3)?;
723 /// tree.close()?;
724 /// tree.close_at(&c, "root")?;
725 /// tree.token("sibling", 3)?;
726 ///
727 /// let tree = tree.build()?;
728 ///
729 /// let lit = tree.node_with_range(0..3).ok_or("missing at 0..3")?;
730 /// assert_eq!(lit.value(), "lit");
731 ///
732 /// let child = lit.parent().ok_or("missing child")?;
733 /// assert_eq!(child.value(), "child");
734 ///
735 /// let root = lit.ancestors().last().ok_or("missing root")?;
736 /// assert_eq!(root.value(), "root");
737 /// assert_eq!(root.parent(), None);
738 ///
739 /// let expected = syntree::tree! {
740 /// "root" => {
741 /// "child" => {
742 /// ("lit", 3)
743 /// }
744 /// },
745 /// ("sibling", 3)
746 /// };
747 ///
748 /// assert_eq!(tree, expected);
749 /// # Ok::<_, Box<dyn core::error::Error>>(())
750 /// ```
751 pub fn close_at(
752 &mut self,
753 c: &Checkpoint<F::Pointer>,
754 data: T,
755 ) -> Result<F::Pointer, Error<F::Error>> {
756 self.close_at_inner(c, data, None)
757 }
758
759 /// Insert a node with a custom length.
760 ///
761 /// # Errors
762 ///
763 /// The checkpoint being closed *must* be a sibling. Otherwise a
764 /// [`Error::CloseAtError`] will be raised.
765 ///
766 /// This might also sporadically error with [`Error::MissingNode`], in case
767 /// a checkpoint is used that was constructed from another tree.
768 ///
769 /// # Examples
770 ///
771 /// ```
772 /// use syntree::Span;
773 ///
774 /// let mut tree = syntree::Builder::new();
775 ///
776 /// let c = tree.checkpoint()?;
777 /// tree.token_with("lit", Span::new(1, 3))?;
778 /// tree.close_at_with(&c, "custom", Span::new(0, 6))?;
779 /// tree.token_with("lit2", Span::new(6, 8))?;
780 ///
781 /// let tree = tree.build()?;
782 ///
783 /// let root = tree.first().ok_or("missing root")?;
784 /// assert_eq!(root.value(), "custom");
785 /// assert_eq!(root.span(), &Span::new(0, 6));
786 /// assert_eq!(tree.span(), &Span::new(0, 8));
787 /// # Ok::<_, Box<dyn core::error::Error>>(())
788 /// ```
789 pub fn close_at_with(
790 &mut self,
791 c: &Checkpoint<F::Pointer>,
792 data: T,
793 span: Span<F::Index>,
794 ) -> Result<F::Pointer, Error<F::Error>> {
795 self.close_at_inner(c, data, Some(span))
796 }
797
798 /// Wrap everything since the checkpoint in a new node, using `span` or the
799 /// span covered by the wrapped nodes when it is `None`.
800 fn close_at_inner(
801 &mut self,
802 c: &Checkpoint<F::Pointer>,
803 data: T,
804 span: Option<Span<F::Index>>,
805 ) -> Result<F::Pointer, Error<F::Error>> {
806 let (id, parent) = c.get();
807
808 if parent != self.parent {
809 return Err(Error::CloseAtError);
810 }
811
812 let new_id = F::Pointer::new(self.tree.len()).ok_or(Error::Overflow)?;
813
814 let Some(links) = self.tree.get_mut(id) else {
815 // Nothing was added since the checkpoint, so wrap an empty node.
816 // Any other missing id means the checkpoint is from another tree.
817 if id != new_id {
818 return Err(Error::MissingNode(id.get()));
819 }
820
821 let new_id = self.insert(data, span.unwrap_or(Span::point(self.cursor)))?;
822 self.sibling = Some(new_id);
823 return Ok(new_id);
824 };
825
826 let parent = links.parent.replace(new_id);
827 let prev = links.prev.take();
828 let start = links.span.start;
829
830 // Re-parent the siblings following the checkpointed node, which also
831 // gives the end of the wrapped span.
832 let (last, end) = match links.next {
833 Some(next) => restructure_close_at(&mut self.tree, new_id, next)?,
834 None => (id, links.span.end),
835 };
836
837 // The wrapper takes every node from the checkpoint onwards, so it is
838 // always the last node at its level.
839 let level = match parent {
840 Some(parent) => self
841 .tree
842 .get_mut(parent)
843 .map(|links| (&mut links.first, &mut links.last)),
844 None => Some(self.tree.links_mut()),
845 };
846
847 if let Some((first, last)) = level {
848 if *first == Some(id) {
849 *first = Some(new_id);
850 }
851
852 *last = Some(new_id);
853 }
854
855 if let Some(prev) = prev.and_then(|id| self.tree.get_mut(id)) {
856 prev.next = Some(new_id);
857 }
858
859 if let Some(span) = span {
860 if let Some(links) = parent.and_then(|id| self.tree.get_mut(id)) {
861 links.span = links.span.join(&span);
862 }
863
864 self.join_tree_span(&span);
865 }
866
867 self.tree.push(Links {
868 data: Cell::new(data),
869 span: span.unwrap_or(Span::new(start, end)),
870 prev,
871 parent,
872 next: None,
873 first: Some(id),
874 last: Some(last),
875 })?;
876
877 self.sibling = Some(new_id);
878 c.set(new_id, parent);
879 Ok(new_id)
880 }
881
882 /// Build a [Tree] from the current state of the builder.
883 ///
884 /// # Errors
885 ///
886 /// This requires the stack in the builder to be empty. Otherwise a
887 /// [`Error::BuildError`] will be raised.
888 ///
889 /// # Examples
890 ///
891 /// ```
892 /// let mut tree = syntree::Builder::new();
893 ///
894 /// tree.open("child")?;
895 /// tree.token("number", 3)?;
896 /// tree.close()?;
897 /// tree.open("child")?;
898 /// tree.close()?;
899 ///
900 /// let tree = tree.build()?;
901 ///
902 /// let expected = syntree::tree! {
903 /// "child" => {
904 /// ("number", 3)
905 /// },
906 /// "child" => {},
907 /// };
908 ///
909 /// assert_eq!(tree, expected);
910 /// # Ok::<_, Box<dyn core::error::Error>>(())
911 /// ```
912 ///
913 /// If a tree is unbalanced during construction, building will fail with an error:
914 ///
915 /// ```
916 /// use syntree::{Error, Span, Builder};
917 ///
918 /// let mut tree = syntree::Builder::new();
919 ///
920 /// tree.open("number")?;
921 /// tree.token("lit", 3)?;
922 /// tree.close()?;
923 ///
924 /// tree.open("number")?;
925 ///
926 /// // "number" is left open.
927 /// assert!(matches!(tree.build(), Err(Error::BuildError)));
928 /// # Ok::<_, Box<dyn core::error::Error>>(())
929 /// ```
930 pub fn build(self) -> Result<Tree<T, F>, Error<F::Error>> {
931 if self.parent.is_some() {
932 return Err(Error::BuildError);
933 }
934
935 Ok(self.tree)
936 }
937
938 /// Insert a new node.
939 fn insert(&mut self, data: T, span: Span<F::Index>) -> Result<F::Pointer, Error<F::Error>> {
940 let new = F::Pointer::new(self.tree.len()).ok_or(Error::Overflow)?;
941
942 let prev = self.sibling.take();
943
944 self.tree.push(Links {
945 data: Cell::new(data),
946 span,
947 parent: self.parent,
948 prev,
949 next: None,
950 first: None,
951 last: None,
952 })?;
953
954 if let Some(id) = self.parent {
955 if let Some(node) = self.tree.links_at_mut(id) {
956 if node.first.is_none() {
957 node.first = Some(new);
958 }
959
960 node.last = Some(new);
961 node.span = node.span.join(&span);
962 }
963 } else {
964 let (first, last) = self.tree.links_mut();
965
966 if first.is_none() {
967 *first = Some(new);
968 }
969
970 *last = Some(new);
971 }
972
973 if let Some(node) = prev.and_then(|id| self.tree.links_at_mut(id)) {
974 node.next = Some(new);
975 }
976
977 self.join_tree_span(&span);
978 Ok(new)
979 }
980
981 /// Extend the span of the whole tree to cover `span`. Empty spans are
982 /// ignored, like they are when indexing tokens.
983 fn join_tree_span(&mut self, span: &Span<F::Index>) {
984 if !span.is_empty() {
985 let tree = self.tree.span_mut();
986 *tree = tree.join(span);
987 }
988 }
989}
990
991impl<T, F> Clone for Builder<T, F>
992where
993 T: Copy,
994 F: Flavor<Indexes: Clone, Width: Width<Pointer: Clone>>,
995 F::Storage<Links<T, F::Index, F::Pointer>>: Clone,
996{
997 #[inline]
998 fn clone(&self) -> Self {
999 Self {
1000 tree: self.tree.clone(),
1001 parent: self.parent,
1002 // Not shared, so that checkpoints handed out by the clone are
1003 // independent of the original.
1004 checkpoint: self.checkpoint.as_ref().map(Checkpoint::deep_clone),
1005 sibling: self.sibling,
1006 cursor: self.cursor,
1007 }
1008 }
1009}
1010
1011impl<T, F> fmt::Debug for Builder<T, F>
1012where
1013 T: Copy + fmt::Debug,
1014 F: Flavor<Index: fmt::Debug>,
1015{
1016 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1017 f.debug_struct("Builder")
1018 .field("tree", &self.tree)
1019 .field("checkpoint", &self.checkpoint)
1020 .field("parent", &self.parent)
1021 .field("sibling", &self.sibling)
1022 .field("cursor", &self.cursor)
1023 .finish()
1024 }
1025}
1026
1027impl<T, F> Default for Builder<T, F>
1028where
1029 T: Copy,
1030 F: Flavor,
1031{
1032 #[inline]
1033 fn default() -> Self {
1034 Self::new_with()
1035 }
1036}
1037
1038// Adjust span to encapsulate all children and check that we just inserted the
1039// checkpointed node in the right location which should be the tail sibling of
1040// the replaced node.
1041#[allow(clippy::type_complexity)]
1042fn restructure_close_at<T, F>(
1043 tree: &mut Tree<T, F>,
1044 parent_id: F::Pointer,
1045 next: F::Pointer,
1046) -> Result<(F::Pointer, F::Index), Error<F::Error>>
1047where
1048 T: Copy,
1049 F: Flavor,
1050{
1051 let mut links = tree
1052 .get_mut(next)
1053 .ok_or_else(|| Error::MissingNode(next.get()))?;
1054 let mut last = (next, links.span.end);
1055 links.parent = Some(parent_id);
1056
1057 while let Some(next) = links.next {
1058 links = tree
1059 .get_mut(next)
1060 .ok_or_else(|| Error::MissingNode(next.get()))?;
1061 last = (next, links.span.end);
1062 links.parent = Some(parent_id);
1063 }
1064
1065 Ok(last)
1066}