syntree/node/walk.rs
1use core::iter::FusedIterator;
2
3use crate::flavor::Flavor;
4use crate::links::Links;
5use crate::node::Node;
6use crate::node::{Event, SkipTokens, WalkEvents};
7
8/// An iterator that walks over the entire tree, visiting every node exactly
9/// once.
10///
11/// See [`Tree::walk`][crate::Tree::walk] or [`Node::walk`].
12///
13/// # Examples
14///
15/// ```
16/// let tree = syntree::tree! {
17/// "root" => {
18/// "c1" => {
19/// "c2" => {},
20/// "c3" => {},
21/// "c4" => {},
22/// },
23/// "c5" => {},
24/// "c6" => {
25/// "c7" => {},
26/// }
27/// }
28/// };
29///
30/// // Walk the entire tree.
31/// assert_eq!(
32/// tree.walk().map(|n| n.value()).collect::<Vec<_>>(),
33/// ["root", "c1", "c2", "c3", "c4", "c5", "c6", "c7"],
34/// );
35///
36/// // Walk from the root.
37/// let root = tree.first().ok_or("missing root node")?;
38///
39/// assert_eq!(
40/// root.walk().map(|n| n.value()).collect::<Vec<_>>(),
41/// ["root", "c1", "c2", "c3", "c4", "c5", "c6", "c7"],
42/// );
43///
44/// // Walk from c1 and visit siblings.
45/// let c1 = root.first().ok_or("missing c1 node")?;
46///
47/// assert_eq!(
48/// c1.walk().map(|n| n.value()).collect::<Vec<_>>(),
49/// ["c1", "c2", "c3", "c4", "c5", "c6", "c7"],
50/// );
51///
52/// assert_eq!(
53/// c1.walk_from().map(|n| n.value()).collect::<Vec<_>>(),
54/// ["c5", "c6", "c7"],
55/// );
56///
57/// // Walk from c4 and visit parent siblings.
58/// let c4 = c1.last().ok_or("missing c1 node")?;
59///
60/// assert_eq!(
61/// c4.walk().map(|n| n.value()).collect::<Vec<_>>(),
62/// ["c4", "c5", "c6", "c7"],
63/// );
64///
65/// assert_eq!(
66/// c4.walk_from().map(|n| n.value()).collect::<Vec<_>>(),
67/// ["c5", "c6", "c7"],
68/// );
69///
70/// // Walk from c5 and visit siblings.
71/// let c5 = c1.next().ok_or("missing c5 node")?;
72///
73/// assert_eq!(
74/// c5.walk().map(|n| n.value()).collect::<Vec<_>>(),
75/// ["c5", "c6", "c7"],
76/// );
77///
78/// assert_eq!(
79/// c5.walk_from().map(|n| n.value()).collect::<Vec<_>>(),
80/// ["c6", "c7"],
81/// );
82/// # Ok::<_, Box<dyn core::error::Error>>(())
83/// ```
84pub struct Walk<'a, T, F>
85where
86 T: Copy,
87 F: Flavor,
88{
89 iter: WalkEvents<'a, T, F>,
90}
91
92impl<'a, T, F> Walk<'a, T, F>
93where
94 T: Copy,
95 F: Flavor,
96{
97 /// Construct a new walk.
98 #[inline]
99 pub(crate) fn new(
100 tree: &'a [Links<T, F::Index, F::Pointer>],
101 node: Option<F::Pointer>,
102 e: Event,
103 ) -> Self {
104 Self {
105 iter: WalkEvents::new(tree, node, e),
106 }
107 }
108
109 /// Convert this iterator into one that limits the walk to inside the
110 /// current node, visiting every node exactly once.
111 ///
112 /// # Examples
113 ///
114 /// ```
115 /// let tree = syntree::tree! {
116 /// "n1" => {
117 /// "n3" => {
118 /// "n4" => {},
119 /// "n5" => {},
120 /// }
121 /// },
122 /// "n6" => {
123 /// "n7"
124 /// }
125 /// };
126 ///
127 /// let values = tree.walk().map(|n| n.value()).collect::<Vec<_>>();
128 /// assert_eq!(values, ["n1", "n3", "n4", "n5", "n6", "n7"]);
129 ///
130 /// let n1 = tree.first().ok_or("missing n1")?;
131 ///
132 /// let values = n1.walk().map(|n| n.value()).collect::<Vec<_>>();
133 /// assert_eq!(values, ["n1", "n3", "n4", "n5", "n6", "n7"]);
134 ///
135 /// let values = n1.walk().inside().map(|n| n.value()).collect::<Vec<_>>();
136 /// assert_eq!(values, ["n1", "n3", "n4", "n5"]);
137 ///
138 /// let values = n1.walk_from().inside().map(|n| n.value()).collect::<Vec<_>>();
139 /// let empty: [&str; 0] = [];
140 /// assert_eq!(values, empty);
141 ///
142 /// # Ok::<_, Box<dyn core::error::Error>>(())
143 /// ```
144 #[inline]
145 #[must_use]
146 pub fn inside(self) -> Inside<'a, T, F> {
147 Inside { iter: self.iter }
148 }
149
150 /// Convert this iterator into one which includes depths.
151 ///
152 /// # Examples
153 ///
154 /// ```
155 /// let tree = syntree::tree! {
156 /// "root" => {
157 /// "c1" => {
158 /// "c2" => {},
159 /// "c3" => {},
160 /// }
161 /// }
162 /// };
163 ///
164 /// let mut it = tree.walk().with_depths().map(|(d, n)| (d, n.value()));
165 /// assert!(it.eq([(0, "root"), (1, "c1"), (2, "c2"), (2, "c3")]));
166 ///
167 /// # Ok::<_, Box<dyn core::error::Error>>(())
168 /// ```
169 #[inline]
170 #[must_use]
171 pub fn with_depths(self) -> WithDepths<'a, T, F> {
172 WithDepths { iter: self.iter }
173 }
174
175 /// Construct a [`SkipTokens`] iterator from the remainder of this iterator.
176 /// This filters out childless nodes, also known as tokens.
177 ///
178 /// See [`SkipTokens`] for documentation.
179 #[inline]
180 #[must_use]
181 pub fn skip_tokens(self) -> SkipTokens<Self> {
182 SkipTokens::new(self)
183 }
184
185 /// Get the next node with a corresponding depth.
186 ///
187 /// Alternatively you can use [`WithDepths`] through [`Walk::with_depths`].
188 ///
189 /// # Examples
190 ///
191 /// ```
192 /// use std::iter;
193 ///
194 /// let tree = syntree::tree! {
195 /// "root" => {
196 /// "c1" => {
197 /// "c2" => {},
198 /// "c3" => {},
199 /// }
200 /// }
201 /// };
202 ///
203 /// let mut it = tree.walk();
204 /// let it = iter::from_fn(move || it.next_with_depth());
205 /// let it = it.map(|(d, n)| (d, n.value()));
206 ///
207 /// assert!(it.eq([(0, "root"), (1, "c1"), (2, "c2"), (2, "c3")]));
208 ///
209 /// # Ok::<_, Box<dyn core::error::Error>>(())
210 /// ```
211 #[inline]
212 #[must_use]
213 pub fn next_with_depth(&mut self) -> Option<(isize, Node<'a, T, F>)> {
214 loop {
215 let depth = self.iter.depth();
216 let (event, node) = self.iter.next()?;
217
218 if !matches!(event, Event::Up) {
219 return Some((depth, node));
220 }
221 }
222 }
223}
224
225impl<T, F> Clone for Walk<'_, T, F>
226where
227 T: Copy,
228 F: Flavor,
229{
230 #[inline]
231 fn clone(&self) -> Self {
232 Self {
233 iter: self.iter.clone(),
234 }
235 }
236}
237
238impl<T, F> Default for Walk<'_, T, F>
239where
240 T: Copy,
241 F: Flavor,
242{
243 #[inline]
244 fn default() -> Self {
245 Self {
246 iter: WalkEvents::default(),
247 }
248 }
249}
250
251impl<'a, T, F> Iterator for Walk<'a, T, F>
252where
253 T: Copy,
254 F: Flavor,
255{
256 type Item = Node<'a, T, F>;
257
258 #[inline]
259 fn next(&mut self) -> Option<Self::Item> {
260 loop {
261 let (event, node) = self.iter.next()?;
262
263 if !matches!(event, Event::Up) {
264 return Some(node);
265 }
266 }
267 }
268}
269
270impl<T, F> FusedIterator for Walk<'_, T, F>
271where
272 T: Copy,
273 F: Flavor,
274{
275}
276
277/// An iterator that walks over the entire tree, visiting every node exactly
278/// once. This is constructed with [`Walk::with_depths`].
279///
280/// # Examples
281///
282/// ```
283/// let tree = syntree::tree! {
284/// "root" => {
285/// "c1" => {
286/// "c2" => {},
287/// "c3" => {},
288/// "c4" => {},
289/// },
290/// "c5" => {},
291/// "c6" => {}
292/// }
293/// };
294///
295/// assert_eq!(
296/// tree.walk().with_depths().map(|(d, n)| (d, n.value())).collect::<Vec<_>>(),
297/// [
298/// (0, "root"),
299/// (1, "c1"),
300/// (2, "c2"),
301/// (2, "c3"),
302/// (2, "c4"),
303/// (1, "c5"),
304/// (1, "c6")
305/// ]
306/// );
307///
308/// let root = tree.first().ok_or("missing root node")?;
309///
310/// assert_eq!(
311/// root.walk().with_depths().map(|(d, n)| (d, n.value())).collect::<Vec<_>>(),
312/// [
313/// (0, "root"),
314/// (1, "c1"),
315/// (2, "c2"),
316/// (2, "c3"),
317/// (2, "c4"),
318/// (1, "c5"),
319/// (1, "c6")
320/// ]
321/// );
322/// # Ok::<_, Box<dyn core::error::Error>>(())
323/// ```
324pub struct WithDepths<'a, T, F>
325where
326 T: Copy,
327 F: Flavor,
328{
329 iter: WalkEvents<'a, T, F>,
330}
331
332impl<'a, T, F> Iterator for WithDepths<'a, T, F>
333where
334 T: Copy,
335 F: Flavor,
336{
337 type Item = (isize, Node<'a, T, F>);
338
339 #[inline]
340 fn next(&mut self) -> Option<Self::Item> {
341 loop {
342 let depth = self.iter.depth();
343 let (event, node) = self.iter.next()?;
344
345 if !matches!(event, Event::Up) {
346 return Some((depth, node));
347 }
348 }
349 }
350}
351
352impl<T, F> FusedIterator for WithDepths<'_, T, F>
353where
354 T: Copy,
355 F: Flavor,
356{
357}
358
359impl<T, F> Clone for WithDepths<'_, T, F>
360where
361 T: Copy,
362 F: Flavor,
363{
364 #[inline]
365 fn clone(&self) -> Self {
366 Self {
367 iter: self.iter.clone(),
368 }
369 }
370}
371
372impl<T, F> Default for WithDepths<'_, T, F>
373where
374 T: Copy,
375 F: Flavor,
376{
377 #[inline]
378 fn default() -> Self {
379 Self {
380 iter: WalkEvents::default(),
381 }
382 }
383}
384
385/// An iterator that limits the walk to inside the current node, visiting every
386/// node exactly once. This is constructed with [`Walk::inside`].
387///
388/// # Examples
389///
390/// ```
391/// let tree = syntree::tree! {
392/// "n1" => {
393/// "n3" => {
394/// "n4" => {},
395/// "n5" => {},
396/// }
397/// },
398/// "n6" => {
399/// "n7"
400/// }
401/// };
402///
403/// let values = tree.walk().map(|n| n.value()).collect::<Vec<_>>();
404/// assert_eq!(values, ["n1", "n3", "n4", "n5", "n6", "n7"]);
405///
406/// let n1 = tree.first().ok_or("missing n1")?;
407///
408/// let values = n1.walk().map(|n| n.value()).collect::<Vec<_>>();
409/// assert_eq!(values, ["n1", "n3", "n4", "n5", "n6", "n7"]);
410///
411/// let values = n1.walk().inside().map(|n| n.value()).collect::<Vec<_>>();
412/// assert_eq!(values, ["n1", "n3", "n4", "n5"]);
413///
414/// let values = n1.walk_from().inside().map(|n| n.value()).collect::<Vec<_>>();
415/// let empty: [&str; 0] = [];
416/// assert_eq!(values, empty);
417///
418/// # Ok::<_, Box<dyn core::error::Error>>(())
419/// ```
420pub struct Inside<'a, T, F>
421where
422 T: Copy,
423 F: Flavor,
424{
425 iter: WalkEvents<'a, T, F>,
426}
427
428impl<'a, T, F> Iterator for Inside<'a, T, F>
429where
430 T: Copy,
431 F: Flavor,
432{
433 type Item = Node<'a, T, F>;
434
435 #[inline]
436 fn next(&mut self) -> Option<Self::Item> {
437 loop {
438 let (event, node) = self.iter.next()?;
439
440 if self.iter.depth() <= 0 {
441 self.iter = WalkEvents::default();
442 }
443
444 if !matches!(event, Event::Up) {
445 return Some(node);
446 }
447 }
448 }
449}
450
451impl<T, F> FusedIterator for Inside<'_, T, F>
452where
453 T: Copy,
454 F: Flavor,
455{
456}
457
458impl<T, F> Clone for Inside<'_, T, F>
459where
460 T: Copy,
461 F: Flavor,
462{
463 #[inline]
464 fn clone(&self) -> Self {
465 Self {
466 iter: self.iter.clone(),
467 }
468 }
469}
470
471impl<T, F> Default for Inside<'_, T, F>
472where
473 T: Copy,
474 F: Flavor,
475{
476 #[inline]
477 fn default() -> Self {
478 Self {
479 iter: WalkEvents::default(),
480 }
481 }
482}