1use std::borrow::Cow;
5
6use oneyaml_core::{Diagnostic, Span};
7
8use super::{NodeId, SyntaxKind, SyntaxTree};
9use crate::event::{Anchor, BlockHeader, ScalarStyle, Tag, TagSource};
10
11#[derive(Clone, Copy)]
19pub struct Node<'t> {
20 tree: &'t SyntaxTree,
21 key: u64,
31}
32
33impl<'t> Node<'t> {
34 pub(super) const fn new(tree: &'t SyntaxTree, index: u32) -> Self {
35 Self::hinted(tree, index, super::NONE)
36 }
37
38 pub(super) const fn hinted(tree: &'t SyntaxTree, index: u32, hint: u32) -> Self {
40 Self {
41 tree,
42 key: (index as u64) | ((hint as u64) << 32),
43 }
44 }
45
46 #[inline]
48 const fn idx(self) -> u32 {
49 self.key as u32
50 }
51
52 #[inline]
54 pub(super) const fn hint(self) -> u32 {
55 (self.key >> 32) as u32
56 }
57
58 fn at(self, index: usize) -> Self {
59 Self::new(self.tree, u32::try_from(index).unwrap_or(super::NONE))
60 }
61
62 fn i(self) -> usize {
63 self.idx() as usize
64 }
65
66 #[must_use]
74 pub const fn slot(self) -> u32 {
75 self.idx()
76 }
77
78 fn edited(self) -> bool {
80 self.tree.edits.is_some()
81 }
82
83 fn with_slot(self, slot: Option<u32>) -> Option<Self> {
84 slot.map(|s| Self::new(self.tree, s))
85 }
86
87 fn with_hinted(self, step: Option<(u32, u32)>) -> Option<Self> {
89 step.map(|(s, h)| Self::hinted(self.tree, s, h))
90 }
91
92 #[inline(never)]
94 fn parent_edited(self) -> Option<Self> {
95 self.with_hinted(self.tree.nav_parent_hinted(self.idx(), self.hint()))
96 }
97
98 #[inline(never)]
100 fn first_child_edited(self) -> Option<Self> {
101 self.with_hinted(self.tree.nav_first_hinted(self.idx(), self.hint()))
102 }
103
104 #[inline(never)]
106 fn last_child_edited(self) -> Option<Self> {
107 self.with_hinted(self.tree.nav_last_hinted(self.idx(), self.hint()))
108 }
109
110 #[inline(never)]
112 fn next_sibling_edited(self) -> Option<Self> {
113 self.with_hinted(self.tree.nav_next_hinted(self.idx(), self.hint()))
114 }
115
116 #[inline(never)]
118 fn prev_sibling_edited(self) -> Option<Self> {
119 self.with_hinted(self.tree.nav_prev_hinted(self.idx(), self.hint()))
120 }
121
122 #[inline(never)]
124 fn pred_edited(self) -> Option<Self> {
125 self.with_hinted(self.tree.nav_pred_hinted(self.idx(), self.hint()))
126 }
127
128 #[inline(never)]
130 fn succ_edited(self) -> Option<Self> {
131 self.with_hinted(self.tree.nav_succ_hinted(self.idx(), self.hint()))
132 }
133
134 #[must_use]
136 pub fn id(self) -> NodeId {
137 self.tree.id_of(self.idx())
138 }
139
140 #[must_use]
145 #[inline]
146 pub fn preorder_index(self) -> usize {
147 if self.edited() {
148 return self.rank_edited();
149 }
150 self.idx() as usize
151 }
152
153 #[inline(never)]
155 fn rank_edited(self) -> usize {
156 self.tree
157 .nav_rank_hinted(self.idx(), self.hint())
158 .and_then(|(r, _)| usize::try_from(r).ok())
159 .unwrap_or(usize::MAX)
160 }
161
162 #[must_use]
164 pub const fn tree(self) -> &'t SyntaxTree {
165 self.tree
166 }
167
168 #[must_use]
170 #[inline]
171 pub fn kind(self) -> SyntaxKind {
172 match self.tree.kind_at(self.i()) {
176 Some(k) => k,
177 None => self.kind_edited(),
178 }
179 }
180
181 #[inline(never)]
184 fn kind_edited(self) -> SyntaxKind {
185 self.tree
186 .kind_hinted(self.idx(), self.hint())
187 .unwrap_or(SyntaxKind::Stream)
188 }
189
190 #[must_use]
192 #[inline]
193 pub fn is_token(self) -> bool {
194 self.kind().is_token()
195 }
196
197 #[must_use]
202 pub fn span(self) -> Span {
203 if self.edited() {
204 return self.span_edited();
205 }
206 self.tree.span_of(self.i())
207 }
208
209 #[must_use]
215 pub fn text(self) -> Cow<'t, str> {
216 if self.edited()
218 && !self
219 .tree
220 .kind_at(self.i())
221 .is_some_and(SyntaxKind::is_token)
222 {
223 return self.text_edited();
224 }
225 let span = self.tree.span_of(self.i());
226 Cow::Borrowed(self.tree.source.get(span.start..span.end).unwrap_or(""))
227 }
228
229 #[inline(never)]
231 fn span_edited(self) -> Span {
232 self.tree.nav_span_hinted(self.idx(), self.hint())
233 }
234
235 #[inline(never)]
237 fn text_edited(self) -> Cow<'t, str> {
238 self.tree.edited_text_hinted(self.idx(), self.hint())
239 }
240
241 #[must_use]
243 pub fn parent(self) -> Option<Self> {
244 super::cost::count(super::cost::Step::Nav);
245 if self.edited() {
246 return self.parent_edited();
247 }
248 self.tree.parent_of(self.i()).map(|p| self.at(p))
249 }
250
251 #[must_use]
253 pub fn first_child(self) -> Option<Self> {
254 super::cost::count(super::cost::Step::Nav);
255 if self.edited() {
256 return self.first_child_edited();
257 }
258 let next = self.i().saturating_add(1);
259 (next < self.tree.end_of(self.i())).then(|| self.at(next))
260 }
261
262 #[must_use]
264 pub fn last_child(self) -> Option<Self> {
265 super::cost::count(super::cost::Step::Nav);
266 if self.edited() {
267 return self.last_child_edited();
268 }
269 let end = self.tree.end_of(self.i());
270 if end <= self.i().saturating_add(1) {
271 return None;
272 }
273 let mut j = end.saturating_sub(1);
275 while let Some(p) = self.tree.parent_of(j) {
276 if p == self.i() {
277 return Some(self.at(j));
278 }
279 j = p;
280 }
281 None
282 }
283
284 #[must_use]
286 pub fn next_sibling(self) -> Option<Self> {
287 super::cost::count(super::cost::Step::Nav);
288 if self.edited() {
289 return self.next_sibling_edited();
290 }
291 let parent = self.tree.parent_of(self.i())?;
292 let next = self.tree.end_of(self.i());
293 (next < self.tree.end_of(parent)).then(|| self.at(next))
294 }
295
296 #[must_use]
298 pub fn prev_sibling(self) -> Option<Self> {
299 super::cost::count(super::cost::Step::Nav);
300 if self.edited() {
301 return self.prev_sibling_edited();
302 }
303 let parent = self.tree.parent_of(self.i())?;
304 let mut j = self.i().checked_sub(1)?;
305 if j == parent {
306 return None;
307 }
308 while let Some(p) = self.tree.parent_of(j) {
310 if p == parent {
311 return Some(self.at(j));
312 }
313 j = p;
314 }
315 None
316 }
317
318 pub(super) fn pred(self) -> Option<Self> {
321 super::cost::count(super::cost::Step::Nav);
322 if self.edited() {
323 return self.pred_edited();
324 }
325 self.with_slot(self.tree.nav_pred(self.idx()))
326 }
327
328 pub(super) fn succ(self) -> Option<Self> {
330 super::cost::count(super::cost::Step::Nav);
331 if self.edited() {
332 return self.succ_edited();
333 }
334 self.with_slot(self.tree.nav_succ(self.idx()))
335 }
336
337 #[must_use]
339 pub fn children(self) -> Children<'t> {
340 if self.edited() {
341 return self.children_edited();
342 }
343 Children {
344 tree: self.tree,
345 edited: false,
346 next: self.first_child().map(Self::i),
347 hint: super::NONE,
348 end: self.tree.end_of(self.i()),
349 }
350 }
351
352 #[inline(never)]
355 fn children_edited(self) -> Children<'t> {
356 let first = self.first_child();
358 let hint = first.map_or(super::NONE, |f| f.hint());
359 Children {
360 tree: self.tree,
361 edited: true,
362 next: first.map(Self::i),
363 hint,
364 end: self.tree.run_slots(hint).1 as usize,
365 }
366 }
367
368 #[must_use]
370 pub fn ancestors(self) -> Ancestors<'t> {
371 Ancestors {
372 next: self.parent(),
373 }
374 }
375
376 #[must_use]
378 pub fn descendants(self) -> Descendants<'t> {
379 if self.edited() {
380 let hint = self.hint();
384 return Descendants {
385 tree: self.tree,
386 edited: true,
387 next: self.i(),
388 hint,
389 run_end: self.tree.run_slots(hint).1,
390 end: usize::try_from(self.tree.nav_size(self.idx())).unwrap_or(0),
391 };
392 }
393 Descendants {
394 tree: self.tree,
395 edited: false,
396 next: self.i(),
397 hint: super::NONE,
398 run_end: 0,
399 end: self.tree.end_of(self.i()),
400 }
401 }
402
403 #[must_use]
406 pub fn walk(self) -> Walk<'t> {
407 let end = if self.edited() {
408 usize::try_from(self.tree.nav_size(self.idx())).unwrap_or(0)
410 } else {
411 self.tree.end_of(self.i())
412 };
413 let hint = self.hint();
415 let (run_start, run_end) = self.tree.run_slots(hint);
416 Walk {
417 tree: self.tree,
418 edited: self.edited(),
419 root: self.idx(),
420 next: self.i(),
421 hint,
422 run_start,
423 run_end,
424 end,
425 current: NO_CURRENT,
426 current_hint: super::NONE,
427 }
428 }
429
430 #[must_use]
435 pub fn diagnostic(self) -> Option<Cow<'t, Diagnostic>> {
436 if self.kind() != SyntaxKind::Error {
437 return None;
438 }
439 self.tree.diagnostic_at(self.i())
440 }
441
442 fn prefix_token(self, kind: SyntaxKind) -> Option<Self> {
447 if !self.kind().is_yaml_node() {
448 return None;
449 }
450 self.children()
451 .take_while(|c| {
452 matches!(
453 c.kind(),
454 SyntaxKind::Anchor
455 | SyntaxKind::Tag
456 | SyntaxKind::BlockScalarHeader
457 | SyntaxKind::Whitespace
458 | SyntaxKind::LineBreak
459 | SyntaxKind::Comment
460 | SyntaxKind::Error
461 | SyntaxKind::Skipped
462 )
463 })
464 .find(|c| c.kind() == kind)
465 }
466
467 #[must_use]
469 pub fn anchor(self) -> Option<Anchor<'t>> {
470 let token = self.prefix_token(SyntaxKind::Anchor)?;
471 if self.edited() {
472 let loc = self.tree.locate_hinted(token.idx(), token.hint())?;
473 let local = loc.flat.token_span(loc.local).start;
474 let mut a = crate::parser::anchor_at(loc.flat.source, local)?;
475 a.span = self.tree.to_global(token.idx(), a.span);
476 return Some(a);
477 }
478 crate::parser::anchor_at(&self.tree.source, token.span().start)
479 }
480
481 #[must_use]
489 pub fn tag(self) -> Option<Tag<'t>> {
490 self.tag_source()?.resolve()
491 }
492
493 #[must_use]
497 pub fn tag_source(self) -> Option<TagSource<'t>> {
498 let (mut t, token) = self.tag_in_arena()?;
499 if self.edited() {
500 t.span = self.tree.to_global(token, t.span);
501 }
502 Some(t)
503 }
504
505 pub(super) fn resolved_tag(self) -> Option<Cow<'t, str>> {
510 self.tag_in_arena()
511 .and_then(|(t, _)| t.resolve())
512 .map(|t| t.resolved)
513 }
514
515 fn tag_in_arena(self) -> Option<(TagSource<'t>, u32)> {
520 let token = self.prefix_token(SyntaxKind::Tag)?;
521 if self.edited() {
522 let loc = self.tree.locate_hinted(token.idx(), token.hint())?;
523 let own = self.tree.locate_hinted(self.idx(), self.hint())?;
524 if !core::ptr::eq(loc.flat.source, own.flat.source) {
526 return None;
527 }
528 let prefix = own.flat.extra(own.local).and_then(|e| e.tag_prefix);
529 let local = loc.flat.token_span(loc.local).start;
530 let t = crate::parser::tag_source_at(loc.flat.source, local, prefix)?;
531 return Some((t, token.idx()));
532 }
533 let prefix = self.tree.extra(self.i()).and_then(|e| e.tag_prefix);
534 let t = crate::parser::tag_source_at(&self.tree.source, token.span().start, prefix)?;
535 Some((t, token.idx()))
536 }
537
538 #[must_use]
540 pub fn block_header(self) -> Option<BlockHeader> {
541 if self.kind() != SyntaxKind::Scalar {
542 return None;
543 }
544 if self.edited() {
545 let mut h = self.local_block_header()?;
546 let token = self.prefix_token(SyntaxKind::BlockScalarHeader)?;
547 h.span = self.tree.to_global(token.idx(), h.span);
548 return Some(h);
549 }
550 self.tree.extra(self.i()).and_then(|e| e.block)
551 }
552
553 fn local_block_header(self) -> Option<BlockHeader> {
555 let own = self.tree.locate_hinted(self.idx(), self.hint())?;
556 own.flat.extra(own.local).and_then(|e| e.block)
557 }
558
559 #[must_use]
563 pub fn value(self) -> Option<Cow<'t, str>> {
564 if self.kind() != SyntaxKind::Scalar {
565 return None;
566 }
567 let text = if self.edited() {
569 self.last_child()?
570 } else {
571 self.at(self.tree.end_of(self.i()).checked_sub(1)?)
572 };
573 let style = match text.kind() {
574 SyntaxKind::PlainScalar => ScalarStyle::Plain,
575 SyntaxKind::SingleQuotedScalar => ScalarStyle::SingleQuoted,
576 SyntaxKind::DoubleQuotedScalar => ScalarStyle::DoubleQuoted,
577 SyntaxKind::LiteralScalar => ScalarStyle::Literal,
578 SyntaxKind::FoldedScalar => ScalarStyle::Folded,
579 _ => return None,
580 };
581 if self.edited() {
582 let loc = self.tree.locate_hinted(text.idx(), text.hint())?;
583 let span = loc.flat.token_span(loc.local);
584 let header = self.local_block_header();
585 let Some(h) = header.filter(|h| h.chomping == crate::event::Chomping::Keep) else {
586 return crate::parser::scalar_value(loc.flat.source, span, style, header);
587 };
588 let own = loc.flat.source.get(span.start..span.end)?;
595 let mut v = crate::parser::scalar_value(own, Span::new(0, own.len()), style, header)?
596 .into_owned();
597 let end = u64::try_from(text.span().end).ok()?;
598 let total = u64::try_from(self.tree.root().span().end).ok()?;
599 let rest = total.saturating_sub(end);
600 let n = u64::try_from(h.content_indent).unwrap_or(u64::MAX);
601 let spaces =
602 rest > 0 && rest <= n && (end..total).all(|i| self.tree.byte_at(i) == Some(b' '));
603 if spaces {
604 v.push('\n');
605 }
606 return Some(Cow::Owned(v));
607 }
608 let header = if matches!(style, ScalarStyle::Literal | ScalarStyle::Folded) {
611 self.block_header()
612 } else {
613 None
614 };
615 crate::parser::scalar_value(&self.tree.source, text.span(), style, header)
616 }
617
618 #[must_use]
620 pub fn alias_name(self) -> Option<&'t str> {
621 if self.kind() != SyntaxKind::Alias {
622 return None;
623 }
624 let token = self.first_child()?;
625 if self.edited() {
626 let loc = self.tree.locate_hinted(token.idx(), token.hint())?;
628 return loc.flat.token_text(loc.local).strip_prefix('*');
629 }
630 self.tree
631 .source
632 .get(token.span().start..token.span().end)?
633 .strip_prefix('*')
634 }
635}
636
637impl PartialEq for Node<'_> {
638 fn eq(&self, other: &Self) -> bool {
640 core::ptr::eq(self.tree, other.tree) && self.idx() == other.idx()
641 }
642}
643
644impl Eq for Node<'_> {}
645
646impl core::hash::Hash for Node<'_> {
647 fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
648 core::ptr::hash(self.tree, state);
649 self.idx().hash(state);
650 }
651}
652
653impl core::fmt::Debug for Node<'_> {
654 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
656 let span = self.span();
657 write!(f, "{:?}@{}..{}", self.kind(), span.start, span.end)
658 }
659}
660
661#[derive(Clone)]
663pub struct Children<'t> {
664 tree: &'t SyntaxTree,
665 next: Option<usize>,
666 hint: u32,
668 end: usize,
672 edited: bool,
675}
676
677impl<'t> Iterator for Children<'t> {
678 type Item = Node<'t>;
679
680 #[inline]
681 fn next(&mut self) -> Option<Node<'t>> {
682 super::cost::count(super::cost::Step::Nav);
683 let i = self.next?;
684 if self.edited {
685 return self.next_edited(i);
686 }
687 let after = self.tree.end_of(i);
688 self.next = (after < self.end && after > i).then_some(after);
689 Some(Node::new(self.tree, u32::try_from(i).ok()?))
690 }
691}
692
693impl<'t> Children<'t> {
694 #[inline(never)]
697 fn next_edited(&mut self, i: usize) -> Option<Node<'t>> {
698 let tree = self.tree;
699 let slot = u32::try_from(i).ok()?;
700 if self.hint == super::NONE {
701 if self.end == 0 {
702 self.next = tree.nav_next(slot).map(|s| s as usize);
705 self.end = 1;
706 return Some(Node::new(tree, slot));
707 }
708 self.hint = tree.hint_of(slot);
712 self.end = tree.run_slots(self.hint).1 as usize;
713 }
714 let hint = self.hint;
715 if hint != super::NONE && i < tree.kinds.len() {
719 let after = tree.end_of(i);
720 if after < self.end {
721 let limit = tree
722 .parent_of(i)
723 .map_or(tree.kinds.len(), |p| tree.end_of(p));
724 self.next = (after < limit && after > i).then_some(after);
725 return Some(Node::hinted(tree, slot, hint));
726 }
727 }
728 let next = tree.nav_next_hinted(slot, hint);
729 self.next = next.map(|(s, _)| s as usize);
730 let h = next.map_or(super::NONE, |(_, h)| h);
731 if h != self.hint {
732 self.hint = h;
733 self.end = tree.run_slots(h).1 as usize;
734 }
735 Some(Node::hinted(tree, slot, hint))
736 }
737}
738
739impl core::iter::FusedIterator for Children<'_> {}
740
741impl core::fmt::Debug for Children<'_> {
744 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
745 f.debug_struct("Children")
746 .field("next", &self.next)
747 .field("end", &self.end)
748 .finish()
749 }
750}
751
752#[derive(Clone, Debug)]
754pub struct Ancestors<'t> {
755 next: Option<Node<'t>>,
756}
757
758impl<'t> Iterator for Ancestors<'t> {
759 type Item = Node<'t>;
760
761 fn next(&mut self) -> Option<Node<'t>> {
762 let node = self.next?;
763 self.next = node.parent();
764 Some(node)
765 }
766}
767
768impl core::iter::FusedIterator for Ancestors<'_> {}
769
770#[derive(Clone)]
772pub struct Descendants<'t> {
773 tree: &'t SyntaxTree,
774 next: usize,
775 hint: u32,
778 run_end: u32,
779 end: usize,
780 edited: bool,
782}
783
784impl<'t> Iterator for Descendants<'t> {
785 type Item = Node<'t>;
786
787 #[inline]
788 fn next(&mut self) -> Option<Node<'t>> {
789 super::cost::count(super::cost::Step::Nav);
790 if self.edited {
791 let i = self.next;
793 let n = i.saturating_add(1);
794 if self.end > 1 && n < self.run_end as usize {
795 self.end = self.end.saturating_sub(1);
796 self.next = n;
797 return Some(Node::hinted(self.tree, u32::try_from(i).ok()?, self.hint));
798 }
799 return self.next_edited();
800 }
801 if self.next >= self.end {
802 return None;
803 }
804 let i = self.next;
805 self.next = i.saturating_add(1);
806 Some(Node::new(self.tree, u32::try_from(i).ok()?))
807 }
808
809 fn size_hint(&self) -> (usize, Option<usize>) {
810 if self.edited {
811 return (self.end, Some(self.end));
812 }
813 let n = self.end.saturating_sub(self.next);
814 (n, Some(n))
815 }
816}
817
818impl<'t> Descendants<'t> {
819 #[inline(never)]
822 fn next_edited(&mut self) -> Option<Node<'t>> {
823 if self.end == 0 {
824 return None;
825 }
826 self.end = self.end.saturating_sub(1);
827 let slot = u32::try_from(self.next).ok()?;
828 let hint = self.hint;
829 if self.end > 0 {
832 match slot.checked_add(1).filter(|n| *n < self.run_end) {
833 Some(n) => self.next = n as usize,
834 None => self.cross(slot),
835 }
836 }
837 Some(Node::hinted(self.tree, slot, hint))
838 }
839
840 fn cross(&mut self, slot: u32) {
842 let next = if self.hint == super::NONE {
843 self.tree
845 .nav_succ_hinted(slot, super::NONE)
846 .map(|(s, h)| (h, s, self.tree.run_slots(h).1))
847 } else {
848 self.tree.run_after(self.hint)
849 };
850 (self.next, self.hint, self.run_end) = match next {
851 Some((h, s, t)) => (s as usize, h, t),
852 None => (usize::MAX, super::NONE, 0),
853 };
854 }
855}
856
857impl ExactSizeIterator for Descendants<'_> {}
858impl core::iter::FusedIterator for Descendants<'_> {}
859
860impl core::fmt::Debug for Descendants<'_> {
861 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
862 f.debug_struct("Descendants")
863 .field("next", &self.next)
864 .field("end", &self.end)
865 .finish()
866 }
867}
868
869#[non_exhaustive]
871#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
872pub enum WalkEvent<T> {
873 Enter(T),
875 Leave(T),
877}
878
879#[derive(Clone)]
882pub struct Walk<'t> {
883 tree: &'t SyntaxTree,
884 next: usize,
885 end: usize,
886 current: usize,
888 root: u32,
889 hint: u32,
894 run_start: u32,
895 run_end: u32,
896 current_hint: u32,
897 edited: bool,
899}
900
901const NO_CURRENT: usize = usize::MAX;
903
904impl<'t> Iterator for Walk<'t> {
905 type Item = WalkEvent<Node<'t>>;
906
907 #[inline]
908 fn next(&mut self) -> Option<Self::Item> {
909 super::cost::count(super::cost::Step::Nav);
910 if self.edited {
911 return self.next_edited();
912 }
913 let c = self.current;
914 if c != NO_CURRENT && self.tree.end_of(c) <= self.next {
915 self.current = if c == self.root as usize {
916 NO_CURRENT
917 } else {
918 self.tree.parent_of(c).unwrap_or(NO_CURRENT)
919 };
920 return Some(WalkEvent::Leave(Node::new(
921 self.tree,
922 u32::try_from(c).ok()?,
923 )));
924 }
925 if self.next >= self.end {
926 return None;
927 }
928 let i = self.next;
929 self.next = i.saturating_add(1);
930 self.current = i;
931 Some(WalkEvent::Enter(Node::new(
932 self.tree,
933 u32::try_from(i).ok()?,
934 )))
935 }
936}
937
938impl<'t> Walk<'t> {
939 #[inline(never)]
944 fn next_edited(&mut self) -> Option<WalkEvent<Node<'t>>> {
945 let tree = self.tree;
946 let (n, h, c) = (self.next, self.hint, self.current);
947 let base = tree.kinds.len();
948 if c != NO_CURRENT && h != super::NONE && n < base {
949 let parent = tree.parent_of(n);
952 if parent == Some(c) && self.end > 1 && n.saturating_add(1) < self.run_end as usize {
953 self.end = self.end.saturating_sub(1);
955 self.next = n.saturating_add(1);
956 self.current = n;
957 self.current_hint = h;
958 return Some(WalkEvent::Enter(Node::hinted(
959 tree,
960 u32::try_from(n).ok()?,
961 h,
962 )));
963 }
964 if parent != Some(c)
965 && self.end > 0
966 && self.current_hint == h
967 && c != self.root as usize
968 {
969 let up = tree.parent_of(c);
971 self.current = up.unwrap_or(NO_CURRENT);
972 self.current_hint = match up {
973 Some(p) if p >= self.run_start as usize => h,
974 _ => super::NONE,
975 };
976 return Some(WalkEvent::Leave(Node::hinted(
977 tree,
978 u32::try_from(c).ok()?,
979 h,
980 )));
981 }
982 }
983 if c != NO_CURRENT {
984 let c32 = u32::try_from(c).ok()?;
985 let ch = self.current_hint;
986 let leave = self.end == 0
988 || u32::try_from(n).ok().and_then(|n| tree.parent_slot(n, h)) != Some(c32);
989 if leave {
990 let up = if c == self.root as usize {
991 None
992 } else if c < base {
993 tree.parent_of(c).and_then(|p| {
996 let ph = if ch == h && p >= self.run_start as usize {
997 ch
998 } else {
999 super::NONE
1000 };
1001 Some((u32::try_from(p).ok()?, ph))
1002 })
1003 } else {
1004 tree.nav_parent_hinted(c32, ch)
1005 };
1006 self.current = up.map_or(NO_CURRENT, |(p, _)| p as usize);
1007 self.current_hint = up.map_or(super::NONE, |(_, ph)| ph);
1008 return Some(WalkEvent::Leave(Node::hinted(tree, c32, ch)));
1009 }
1010 }
1011 if self.end == 0 {
1012 return None;
1013 }
1014 self.end = self.end.saturating_sub(1);
1015 let i = u32::try_from(n).ok()?;
1016 if self.end > 0 {
1017 match i.checked_add(1).filter(|m| *m < self.run_end) {
1018 Some(m) => self.next = m as usize,
1019 None => {
1020 let next = if h == super::NONE {
1021 tree.nav_succ_hinted(i, super::NONE)
1025 .map(|(s, sh)| (sh, s, tree.run_slots(sh).1))
1026 } else {
1027 tree.run_after(h)
1028 };
1029 (self.next, self.hint, self.run_start, self.run_end) = match next {
1030 Some((nh, s, t)) => (s as usize, nh, s, t),
1031 None => (usize::MAX, super::NONE, 0, 0),
1032 };
1033 }
1034 }
1035 }
1036 self.current = i as usize;
1037 self.current_hint = h;
1038 Some(WalkEvent::Enter(Node::hinted(tree, i, h)))
1039 }
1040}
1041
1042impl core::iter::FusedIterator for Walk<'_> {}
1043
1044impl core::fmt::Debug for Walk<'_> {
1045 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
1046 let current = (self.current != NO_CURRENT).then_some(self.current);
1047 f.debug_struct("Walk")
1048 .field("root", &self.root)
1049 .field("next", &self.next)
1050 .field("end", &self.end)
1051 .field("current", ¤t)
1052 .finish()
1053 }
1054}