syntree/node/
walk.rs

1use core::fmt;
2use core::iter::FusedIterator;
3
4use crate::flavor::Flavor;
5use crate::links::Links;
6use crate::node::Node;
7use crate::node::{Event, SkipTokens, WalkEvents};
8
9/// An iterator that walks over the entire tree, visiting every node exactly
10/// once.
11///
12/// See [`Tree::walk`][crate::Tree::walk] or [`Node::walk`].
13///
14/// # Examples
15///
16/// ```
17/// let tree = syntree::tree! {
18///     "root" => {
19///         "c1" => {
20///             "c2" => {},
21///             "c3" => {},
22///             "c4" => {},
23///         },
24///         "c5" => {},
25///         "c6" => {
26///            "c7" => {},
27///         }
28///     }
29/// };
30///
31/// // Walk the entire tree.
32/// assert_eq!(
33///     tree.walk().map(|n| n.value()).collect::<Vec<_>>(),
34///     ["root", "c1", "c2", "c3", "c4", "c5", "c6", "c7"],
35/// );
36///
37/// // Walk from the root.
38/// let root = tree.first().ok_or("missing root node")?;
39///
40/// assert_eq!(
41///     root.walk().map(|n| n.value()).collect::<Vec<_>>(),
42///     ["root", "c1", "c2", "c3", "c4", "c5", "c6", "c7"],
43/// );
44///
45/// // Walk from c1 and visit siblings.
46/// let c1 = root.first().ok_or("missing c1 node")?;
47///
48/// assert_eq!(
49///     c1.walk().map(|n| n.value()).collect::<Vec<_>>(),
50///     ["c1", "c2", "c3", "c4", "c5", "c6", "c7"],
51/// );
52///
53/// assert_eq!(
54///     c1.walk_from().map(|n| n.value()).collect::<Vec<_>>(),
55///     ["c5", "c6", "c7"],
56/// );
57///
58/// // Walk from c4 and visit parent siblings.
59/// let c4 = c1.last().ok_or("missing c1 node")?;
60///
61/// assert_eq!(
62///     c4.walk().map(|n| n.value()).collect::<Vec<_>>(),
63///     ["c4", "c5", "c6", "c7"],
64/// );
65///
66/// assert_eq!(
67///     c4.walk_from().map(|n| n.value()).collect::<Vec<_>>(),
68///     ["c5", "c6", "c7"],
69/// );
70///
71/// // Walk from c5 and visit siblings.
72/// let c5 = c1.next().ok_or("missing c5 node")?;
73///
74/// assert_eq!(
75///     c5.walk().map(|n| n.value()).collect::<Vec<_>>(),
76///     ["c5", "c6", "c7"],
77/// );
78///
79/// assert_eq!(
80///     c5.walk_from().map(|n| n.value()).collect::<Vec<_>>(),
81///     ["c6", "c7"],
82/// );
83/// # Ok::<_, Box<dyn core::error::Error>>(())
84/// ```
85pub struct Walk<'a, T, F>
86where
87    T: Copy,
88    F: Flavor,
89{
90    iter: WalkEvents<'a, T, F>,
91    // A tree-level walk has no single node to stay inside, so `inside` must
92    // not stop when the walk climbs back to the top level.
93    bounded: bool,
94}
95
96impl<'a, T, F> Walk<'a, T, F>
97where
98    T: Copy,
99    F: Flavor,
100{
101    /// Construct a new walk starting at a node.
102    #[inline]
103    pub(crate) fn new(
104        tree: &'a [Links<T, F::Index, F::Pointer>],
105        node: Option<F::Pointer>,
106        e: Event,
107    ) -> Self {
108        Self {
109            iter: WalkEvents::new(tree, node, e),
110            bounded: true,
111        }
112    }
113
114    /// Construct a new walk over every root of a tree.
115    #[inline]
116    pub(crate) fn tree(
117        tree: &'a [Links<T, F::Index, F::Pointer>],
118        node: Option<F::Pointer>,
119    ) -> Self {
120        Self {
121            iter: WalkEvents::new(tree, node, Event::Next),
122            bounded: false,
123        }
124    }
125
126    /// Convert this iterator into one that limits the walk to inside the
127    /// node it started at, visiting every node exactly once.
128    ///
129    /// The scope is the node the walk was constructed from, such as through
130    /// [`Node::walk`] or [`Node::walk_from`], even if this iterator has already
131    /// been advanced. A walk constructed through
132    /// [`Tree::walk`][crate::Tree::walk] has the whole tree as its scope, so it
133    /// visits the remaining nodes under every root.
134    ///
135    /// # Examples
136    ///
137    /// ```
138    /// let tree = syntree::tree! {
139    ///     "n1" => {
140    ///         "n3" => {
141    ///             "n4" => {},
142    ///             "n5" => {},
143    ///         }
144    ///     },
145    ///     "n6" => {
146    ///         "n7"
147    ///     }
148    /// };
149    ///
150    /// let values = tree.walk().map(|n| n.value()).collect::<Vec<_>>();
151    /// assert_eq!(values, ["n1", "n3", "n4", "n5", "n6", "n7"]);
152    ///
153    /// let n1 = tree.first().ok_or("missing n1")?;
154    ///
155    /// let values = n1.walk().map(|n| n.value()).collect::<Vec<_>>();
156    /// assert_eq!(values, ["n1", "n3", "n4", "n5", "n6", "n7"]);
157    ///
158    /// let values = n1.walk().inside().map(|n| n.value()).collect::<Vec<_>>();
159    /// assert_eq!(values, ["n1", "n3", "n4", "n5"]);
160    ///
161    /// let values = n1.walk_from().inside().map(|n| n.value()).collect::<Vec<_>>();
162    /// let empty: [&str; 0] = [];
163    /// assert_eq!(values, empty);
164    ///
165    /// let values = tree.walk().inside().map(|n| n.value()).collect::<Vec<_>>();
166    /// assert_eq!(values, ["n1", "n3", "n4", "n5", "n6", "n7"]);
167    ///
168    /// let mut walk = n1.walk();
169    /// assert_eq!(walk.next().map(|n| n.value()), Some("n1"));
170    /// assert_eq!(walk.next().map(|n| n.value()), Some("n3"));
171    /// let values = walk.inside().map(|n| n.value()).collect::<Vec<_>>();
172    /// assert_eq!(values, ["n4", "n5"]);
173    ///
174    /// # Ok::<_, Box<dyn core::error::Error>>(())
175    /// ```
176    #[inline]
177    #[must_use]
178    pub fn inside(self) -> Inside<'a, T, F> {
179        Inside {
180            iter: self.iter,
181            bounded: self.bounded,
182        }
183    }
184
185    /// Convert this iterator into one which includes depths.
186    ///
187    /// See [`WithDepths`] for how depths are counted.
188    ///
189    /// # Examples
190    ///
191    /// ```
192    /// let tree = syntree::tree! {
193    ///     "root" => {
194    ///         "c1" => {
195    ///             "c2" => {},
196    ///             "c3" => {},
197    ///         }
198    ///     }
199    /// };
200    ///
201    /// let mut it = tree.walk().with_depths().map(|(d, n)| (d, n.value()));
202    /// assert!(it.eq([(0, "root"), (1, "c1"), (2, "c2"), (2, "c3")]));
203    ///
204    /// # Ok::<_, Box<dyn core::error::Error>>(())
205    /// ```
206    #[inline]
207    #[must_use]
208    pub fn with_depths(self) -> WithDepths<'a, T, F> {
209        WithDepths { iter: self.iter }
210    }
211
212    /// Construct a [`SkipTokens`] iterator from the remainder of this iterator.
213    /// This filters out childless nodes, also known as tokens.
214    ///
215    /// See [`SkipTokens`] for documentation.
216    #[inline]
217    #[must_use]
218    pub fn skip_tokens(self) -> SkipTokens<Self> {
219        SkipTokens::new(self)
220    }
221
222    /// Get the next node with a corresponding depth.
223    ///
224    /// Depths are relative to the node the walk started at and become negative
225    /// once a walk started from a [`Node`] leaves that node's subtree, see
226    /// [`WithDepths`].
227    ///
228    /// Alternatively you can use [`WithDepths`] through [`Walk::with_depths`].
229    ///
230    /// # Examples
231    ///
232    /// ```
233    /// use std::iter;
234    ///
235    /// let tree = syntree::tree! {
236    ///     "root" => {
237    ///         "c1" => {
238    ///             "c2" => {},
239    ///             "c3" => {},
240    ///         }
241    ///     }
242    /// };
243    ///
244    /// let mut it = tree.walk();
245    /// let it = iter::from_fn(move || it.next_with_depth());
246    /// let it = it.map(|(d, n)| (d, n.value()));
247    ///
248    /// assert!(it.eq([(0, "root"), (1, "c1"), (2, "c2"), (2, "c3")]));
249    ///
250    /// # Ok::<_, Box<dyn core::error::Error>>(())
251    /// ```
252    #[inline]
253    #[must_use]
254    pub fn next_with_depth(&mut self) -> Option<(isize, Node<'a, T, F>)> {
255        next_with_depth(&mut self.iter)
256    }
257}
258
259impl<T, F> Clone for Walk<'_, T, F>
260where
261    T: Copy,
262    F: Flavor,
263{
264    #[inline]
265    fn clone(&self) -> Self {
266        Self {
267            iter: self.iter.clone(),
268            bounded: self.bounded,
269        }
270    }
271}
272
273impl<T, F> Default for Walk<'_, T, F>
274where
275    T: Copy,
276    F: Flavor,
277{
278    #[inline]
279    fn default() -> Self {
280        Self {
281            iter: WalkEvents::default(),
282            bounded: true,
283        }
284    }
285}
286
287impl<'a, T, F> Iterator for Walk<'a, T, F>
288where
289    T: Copy,
290    F: Flavor,
291{
292    type Item = Node<'a, T, F>;
293
294    #[inline]
295    fn next(&mut self) -> Option<Self::Item> {
296        loop {
297            let (event, node) = self.iter.next()?;
298
299            if !matches!(event, Event::Up) {
300                return Some(node);
301            }
302        }
303    }
304}
305
306impl<T, F> FusedIterator for Walk<'_, T, F>
307where
308    T: Copy,
309    F: Flavor,
310{
311}
312
313/// An iterator that walks over the entire tree, visiting every node exactly
314/// once and yielding each node together with its depth. This is constructed
315/// with [`Walk::with_depths`].
316///
317/// Depths are relative to the node the walk started at, which has depth `0`.
318/// A walk started from a [`Node`] continues past the end of that node's
319/// subtree into the following siblings of its ancestors, and those nodes have
320/// negative depths. This is why depths are [`isize`]. A walk started through
321/// [`Tree::walk`][crate::Tree::walk] gives every root depth `0`.
322///
323/// # Examples
324///
325/// ```
326/// let tree = syntree::tree! {
327///     "root" => {
328///         "c1" => {
329///             "c2" => {},
330///             "c3" => {},
331///             "c4" => {},
332///         },
333///         "c5" => {},
334///         "c6" => {}
335///     }
336/// };
337///
338/// assert_eq!(
339///     tree.walk().with_depths().map(|(d, n)| (d, n.value())).collect::<Vec<_>>(),
340///     [
341///         (0, "root"),
342///         (1, "c1"),
343///         (2, "c2"),
344///         (2, "c3"),
345///         (2, "c4"),
346///         (1, "c5"),
347///         (1, "c6")
348///     ]
349/// );
350///
351/// let root = tree.first().ok_or("missing root node")?;
352///
353/// assert_eq!(
354///     root.walk().with_depths().map(|(d, n)| (d, n.value())).collect::<Vec<_>>(),
355///     [
356///         (0, "root"),
357///         (1, "c1"),
358///         (2, "c2"),
359///         (2, "c3"),
360///         (2, "c4"),
361///         (1, "c5"),
362///         (1, "c6")
363///     ]
364/// );
365/// # Ok::<_, Box<dyn core::error::Error>>(())
366/// ```
367///
368/// Leaving the subtree of the starting node gives negative depths:
369///
370/// ```
371/// let tree = syntree::tree! {
372///     "root" => {
373///         "b" => {
374///             "b1" => {}
375///         },
376///         "c" => {},
377///         "d" => {}
378///     },
379///     "root2" => {
380///         "e" => {}
381///     }
382/// };
383///
384/// let b1 = tree.walk().find(|n| n.value() == "b1").ok_or("missing b1")?;
385///
386/// assert_eq!(
387///     b1.walk().with_depths().map(|(d, n)| (d, n.value())).collect::<Vec<_>>(),
388///     [(0, "b1"), (-1, "c"), (-1, "d"), (-2, "root2"), (-1, "e")]
389/// );
390///
391/// assert_eq!(
392///     tree.walk().with_depths().map(|(d, n)| (d, n.value())).collect::<Vec<_>>(),
393///     [(0, "root"), (1, "b"), (2, "b1"), (1, "c"), (1, "d"), (0, "root2"), (1, "e")]
394/// );
395/// # Ok::<_, Box<dyn core::error::Error>>(())
396/// ```
397pub struct WithDepths<'a, T, F>
398where
399    T: Copy,
400    F: Flavor,
401{
402    iter: WalkEvents<'a, T, F>,
403}
404
405impl<'a, T, F> Iterator for WithDepths<'a, T, F>
406where
407    T: Copy,
408    F: Flavor,
409{
410    type Item = (isize, Node<'a, T, F>);
411
412    #[inline]
413    fn next(&mut self) -> Option<Self::Item> {
414        next_with_depth(&mut self.iter)
415    }
416}
417
418#[inline]
419fn next_with_depth<'a, T, F>(iter: &mut WalkEvents<'a, T, F>) -> Option<(isize, Node<'a, T, F>)>
420where
421    T: Copy,
422    F: Flavor,
423{
424    loop {
425        let depth = iter.depth();
426        let (event, node) = iter.next()?;
427
428        if !matches!(event, Event::Up) {
429            return Some((depth, node));
430        }
431    }
432}
433
434impl<T, F> FusedIterator for WithDepths<'_, T, F>
435where
436    T: Copy,
437    F: Flavor,
438{
439}
440
441impl<T, F> Clone for WithDepths<'_, T, F>
442where
443    T: Copy,
444    F: Flavor,
445{
446    #[inline]
447    fn clone(&self) -> Self {
448        Self {
449            iter: self.iter.clone(),
450        }
451    }
452}
453
454impl<T, F> Default for WithDepths<'_, T, F>
455where
456    T: Copy,
457    F: Flavor,
458{
459    #[inline]
460    fn default() -> Self {
461        Self {
462            iter: WalkEvents::default(),
463        }
464    }
465}
466
467/// An iterator that limits the walk to inside the node it started at, visiting
468/// every node exactly once. This is constructed with [`Walk::inside`].
469///
470/// The scope is the node the [`Walk`] was constructed from, even if it was
471/// advanced before calling [`Walk::inside`]. For a walk constructed through
472/// [`Tree::walk`][crate::Tree::walk] the scope is the whole tree, covering
473/// every root.
474///
475/// # Examples
476///
477/// ```
478/// let tree = syntree::tree! {
479///     "n1" => {
480///         "n3" => {
481///             "n4" => {},
482///             "n5" => {},
483///         }
484///     },
485///     "n6" => {
486///         "n7"
487///     }
488/// };
489///
490/// let values = tree.walk().map(|n| n.value()).collect::<Vec<_>>();
491/// assert_eq!(values, ["n1", "n3", "n4", "n5", "n6", "n7"]);
492///
493/// let n1 = tree.first().ok_or("missing n1")?;
494///
495/// let values = n1.walk().map(|n| n.value()).collect::<Vec<_>>();
496/// assert_eq!(values, ["n1", "n3", "n4", "n5", "n6", "n7"]);
497///
498/// let values = n1.walk().inside().map(|n| n.value()).collect::<Vec<_>>();
499/// assert_eq!(values, ["n1", "n3", "n4", "n5"]);
500///
501/// let values = n1.walk_from().inside().map(|n| n.value()).collect::<Vec<_>>();
502/// let empty: [&str; 0] = [];
503/// assert_eq!(values, empty);
504///
505/// let values = tree.walk().inside().map(|n| n.value()).collect::<Vec<_>>();
506/// assert_eq!(values, ["n1", "n3", "n4", "n5", "n6", "n7"]);
507///
508/// # Ok::<_, Box<dyn core::error::Error>>(())
509/// ```
510///
511/// The iterator can be named, for example to store it in a struct:
512///
513/// ```
514/// use syntree::node::Inside;
515/// use syntree::FlavorDefault;
516///
517/// struct Values<'a> {
518///     iter: Inside<'a, &'static str, FlavorDefault>,
519/// }
520///
521/// impl Iterator for Values<'_> {
522///     type Item = &'static str;
523///
524///     fn next(&mut self) -> Option<Self::Item> {
525///         Some(self.iter.next()?.value())
526///     }
527/// }
528///
529/// let tree = syntree::tree! {
530///     "n1" => {
531///         "n2" => {}
532///     },
533///     "n3" => {}
534/// };
535///
536/// let n1 = tree.first().ok_or("missing n1")?;
537/// let values = Values { iter: n1.walk().inside() };
538/// assert_eq!(values.collect::<Vec<_>>(), ["n1", "n2"]);
539/// # Ok::<_, Box<dyn core::error::Error>>(())
540/// ```
541pub struct Inside<'a, T, F>
542where
543    T: Copy,
544    F: Flavor,
545{
546    iter: WalkEvents<'a, T, F>,
547    bounded: bool,
548}
549
550impl<'a, T, F> Iterator for Inside<'a, T, F>
551where
552    T: Copy,
553    F: Flavor,
554{
555    type Item = Node<'a, T, F>;
556
557    #[inline]
558    fn next(&mut self) -> Option<Self::Item> {
559        loop {
560            let (event, node) = self.iter.next()?;
561
562            if self.bounded && self.iter.depth() <= 0 {
563                self.iter = WalkEvents::default();
564            }
565
566            if !matches!(event, Event::Up) {
567                return Some(node);
568            }
569        }
570    }
571}
572
573impl<T, F> FusedIterator for Inside<'_, T, F>
574where
575    T: Copy,
576    F: Flavor,
577{
578}
579
580impl<T, F> Clone for Inside<'_, T, F>
581where
582    T: Copy,
583    F: Flavor,
584{
585    #[inline]
586    fn clone(&self) -> Self {
587        Self {
588            iter: self.iter.clone(),
589            bounded: self.bounded,
590        }
591    }
592}
593
594impl<T, F> Default for Inside<'_, T, F>
595where
596    T: Copy,
597    F: Flavor,
598{
599    #[inline]
600    fn default() -> Self {
601        Self {
602            iter: WalkEvents::default(),
603            bounded: true,
604        }
605    }
606}
607
608impl<T, F> fmt::Debug for Walk<'_, T, F>
609where
610    T: Copy + fmt::Debug,
611    F: Flavor<Index: fmt::Debug>,
612{
613    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
614        f.debug_struct("Walk")
615            .field("events", &self.iter)
616            .finish_non_exhaustive()
617    }
618}
619
620impl<T, F> fmt::Debug for WithDepths<'_, T, F>
621where
622    T: Copy + fmt::Debug,
623    F: Flavor<Index: fmt::Debug>,
624{
625    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
626        f.debug_struct("WithDepths")
627            .field("events", &self.iter)
628            .finish()
629    }
630}
631
632impl<T, F> fmt::Debug for Inside<'_, T, F>
633where
634    T: Copy + fmt::Debug,
635    F: Flavor<Index: fmt::Debug>,
636{
637    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
638        f.debug_struct("Inside")
639            .field("events", &self.iter)
640            .finish_non_exhaustive()
641    }
642}
syntree/node/walk.rs

syntree/node/
walk.rs
