Skip to main content

oneyaml_syntax/tree/
node.rs

1//! Borrowed views of tree elements and iterative traversals (every
2//! traversal is an index loop over the flat arena; nothing recurses).
3
4use 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/// A node or token of a [`SyntaxTree`]: a cheap, copyable view.
12///
13/// Navigation is O(1) per step, except [`Node::last_child`] and
14/// [`Node::prev_sibling`], which are O(depth) (the arena links forward).
15/// In an edited tree too, as long as the step stays inside one of the
16/// edits' runs, so sequential reads cost amortised O(1) per
17/// element (see [`SyntaxTree::is_edited`]).
18#[derive(Clone, Copy)]
19pub struct Node<'t> {
20    tree: &'t SyntaxTree,
21    /// The element's slot (low 32 bits) and, its **hint**
22    /// (high 32 bits): in an edited tree, the treap item of the run holding
23    /// the element when known (`NONE` otherwise, and always for an
24    /// unedited tree). The tree is borrowed immutably, so the overlay
25    /// cannot change while the hint exists. The hint is not part of the
26    /// element's identity (`PartialEq`, `Hash`). One `u64`, so a `Node`
27    /// is two words that stay in registers (two `u32` fields made the
28    /// compiler build it in memory field by field and read it back whole,
29    /// a store-forwarding stall on every step of a parsed tree's loops).
30    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    /// An element of an edited tree with its run's item.
39    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    /// The element's slot.
47    #[inline]
48    const fn idx(self) -> u32 {
49        self.key as u32
50    }
51
52    /// The element's hint.
53    #[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    /// The element's slot: a 4-byte name of the element for the tree's
67    /// whole life (edits never reuse a slot), resolved with
68    /// [`SyntaxTree::node_at_slot`]. Meant for compact indexes
69    /// over one tree; unlike a [`NodeId`](super::NodeId) it does not name
70    /// its tree, so it is meaningful only with the tree that issued it (and
71    /// a [`fork`](SyntaxTree::fork) of it, for slots issued before the
72    /// fork). O(1).
73    #[must_use]
74    pub const fn slot(self) -> u32 {
75        self.idx()
76    }
77
78    /// The tree has been edited: read through the overlay.
79    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    /// The element of a hinted step.
88    fn with_hinted(self, step: Option<(u32, u32)>) -> Option<Self> {
89        step.map(|(s, h)| Self::hinted(self.tree, s, h))
90    }
91
92    /// [`Node::parent`] in an edited tree (out of line, see [`Node::kind`]).
93    #[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    /// [`Node::first_child`] in an edited tree (out of line, see [`Node::kind`]).
99    #[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    /// [`Node::last_child`] in an edited tree (out of line, see [`Node::kind`]).
105    #[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    /// [`Node::next_sibling`] in an edited tree (out of line, see [`Node::kind`]).
111    #[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    /// [`Node::prev_sibling`] in an edited tree (out of line, see [`Node::kind`]).
117    #[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    /// [`Node::pred`] in an edited tree (out of line, see [`Node::kind`]).
123    #[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    /// [`Node::succ`] in an edited tree (out of line, see [`Node::kind`]).
129    #[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    /// A stable handle to this element.
135    #[must_use]
136    pub fn id(self) -> NodeId {
137        self.tree.id_of(self.idx())
138    }
139
140    /// The element's position in preorder (= source order), 0 for the root.
141    /// Positions compare elements of one tree: an element comes before
142    /// everything in its subtree and after its preceding siblings. O(1);
143    /// O(log R) in an edited tree (R: runs, see [`SyntaxTree::is_edited`]).
144    #[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    /// [`Node::preorder_index`] in an edited tree (out of line).
154    #[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    /// The tree this element belongs to.
163    #[must_use]
164    pub const fn tree(self) -> &'t SyntaxTree {
165        self.tree
166    }
167
168    /// What the element is.
169    #[must_use]
170    #[inline]
171    pub fn kind(self) -> SyntaxKind {
172        // A base slot's kind is the base arrays', edited or not
173        // (edits never change an arena); only an inserted slot reads its
174        // arena through the overlay.
175        match self.tree.kind_at(self.i()) {
176            Some(k) => k,
177            None => self.kind_edited(),
178        }
179    }
180
181    /// [`Node::kind`] in an edited tree (out of line, so the unedited
182    /// read stays small enough to inline).
183    #[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    /// `true` for a leaf token.
191    #[must_use]
192    #[inline]
193    pub fn is_token(self) -> bool {
194        self.kind().is_token()
195    }
196
197    /// The source bytes the element covers (UTF-8 byte range); in an
198    /// edited tree, the range in [`SyntaxTree::emit`]'s text. O(1) (a run
199    /// of nodes opening at one byte aside); edited: O(log R) when the
200    /// subtree is untouched, else O(depth).
201    #[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    /// The source text the element covers; in an edited tree, its text in
210    /// [`SyntaxTree::emit`]. Borrowed from the tree (always for a parsed
211    /// tree and for tokens); a node whose text an edit split over several
212    /// arenas is built from them on each call (O(node size)): the tree
213    /// keeps no copies of its text.
214    #[must_use]
215    pub fn text(self) -> Cow<'t, str> {
216        // A base token's text is its source bytes, edited or not.
217        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    /// [`Node::span`] in an edited tree (out of line, see [`Node::kind`]).
230    #[inline(never)]
231    fn span_edited(self) -> Span {
232        self.tree.nav_span_hinted(self.idx(), self.hint())
233    }
234
235    /// [`Node::text`] in an edited tree (out of line, see [`Node::kind`]).
236    #[inline(never)]
237    fn text_edited(self) -> Cow<'t, str> {
238        self.tree.edited_text_hinted(self.idx(), self.hint())
239    }
240
241    /// The enclosing node; `None` for the root.
242    #[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    /// The first child; `None` for a token or an empty node.
252    #[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    /// The last child. O(depth).
263    #[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        // The last element of the subtree, then up to our child.
274        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    /// The next sibling.
285    #[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    /// The previous sibling. O(depth).
297    #[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        // The element before us ends the previous sibling's subtree.
309        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    /// The previous element in preorder (a token, or an enclosing or empty
319    /// node). O(1); O(log R) in an edited tree.
320    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    /// The next element in preorder. O(1); O(log R) in an edited tree.
329    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    /// The children, in order.
338    #[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    /// [`Node::children`] in an edited tree (out of line, see
353    /// [`Node::kind`]).
354    #[inline(never)]
355    fn children_edited(self) -> Children<'t> {
356        // (Without a hint, the first step finds one: see `Children`.)
357        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    /// The enclosing nodes, innermost first.
369    #[must_use]
370    pub fn ancestors(self) -> Ancestors<'t> {
371        Ancestors {
372            next: self.parent(),
373        }
374    }
375
376    /// This element and everything under it, in preorder (= source order).
377    #[must_use]
378    pub fn descendants(self) -> Descendants<'t> {
379        if self.edited() {
380            // Edited: `next` is a slot, `end` the count still to yield (the
381            // subtree is that many consecutive elements of the order).
382            // (Without a hint, the first step finds one, see `cross`.)
383            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    /// A preorder walk of this subtree that also reports leaving each
404    /// element (tokens are entered and left at once).
405    #[must_use]
406    pub fn walk(self) -> Walk<'t> {
407        let end = if self.edited() {
408            // Edited: `end` is the count still to enter.
409            usize::try_from(self.tree.nav_size(self.idx())).unwrap_or(0)
410        } else {
411            self.tree.end_of(self.i())
412        };
413        // (Without a hint, the first step finds one.)
414        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    /// The diagnostic of an [`SyntaxKind::Error`] node (in an edited tree,
431    /// with its spans moved to the edited text). Past `max_diagnostics` it
432    /// is a skeleton, without texts (see
433    /// [`SyntaxTree::suppressed_diagnostics`](crate::tree::SyntaxTree::suppressed_diagnostics)).
434    #[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    // ------------------------------------------------------------ meaning
443
444    /// The first child of `kind` among a YAML node's own leading children
445    /// (its properties and header), before its content.
446    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    /// A YAML node's anchor (ยง6.9.2), read as the event stream reads it.
468    #[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    /// A YAML node's tag, resolved as the event stream resolves it
482    /// (`%TAG` prefix and `%XX` escapes, ยง6.9.1).
483    ///
484    /// Cost: O(prefix + suffix) **per call**; the resolved text copies the
485    /// `%TAG` prefix, which may be long. To read many tags, cache by
486    /// [`TagSource::key`] ([`Node::tag_source`]) and resolve each distinct
487    /// tag once.
488    #[must_use]
489    pub fn tag(self) -> Option<Tag<'t>> {
490        self.tag_source()?.resolve()
491    }
492
493    /// A YAML node's tag as written, not yet resolved: O(the property's
494    /// text), whatever the `%TAG` prefix's length. Its
495    /// span is in the edited text, as [`Node::tag`]'s.
496    #[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    /// The resolved text of the node's tag ([`Node::tag`] without its
506    /// span: the well-formedness comparison reads
507    /// only this, and moving the span to the edited text cost an O(log R)
508    /// rank per node).
509    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    /// The node's tag as written, its span in the arena holding the
516    /// tag token (the source for an unedited tree), and that token's slot.
517    /// The one reading behind [`Node::tag`] and
518    /// [`Node::resolved_tag`], so the two never differ.
519    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            // A tag token moves only with its node (edit.rs): same arena.
525            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    /// A block scalar's header as the event carried it (C5).
539    #[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    /// An edited tree's scalar header, spans local to its arena.
554    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    /// A scalar node's value after escapes, folding, and chomping, decoded
560    /// by the event stream's own decoder. Borrowed from the source
561    /// when it is a slice of it.
562    #[must_use]
563    pub fn value(self) -> Option<Cow<'t, str>> {
564        if self.kind() != SyntaxKind::Scalar {
565            return None;
566        }
567        // A scalar's text token is always its last child.
568        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            // A keep scalar's value depends on the text
589            // after it (an unterminated last line of spaces at the end of
590            // the text is one more empty line). The token's arena ends
591            // where its fragment did, so that is read from the tree's own
592            // text, never from the arena's (at most `content_indent`
593            // bytes).
594            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        // Only a block scalar has a header (read from the extras by binary
609        // search: skipped for flow scalars).
610        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    /// An alias node's anchor name, without `*`.
619    #[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            // A token lies in one arena: its text is always borrowed.
627            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    /// The same element of the same tree instance.
639    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    /// `Kind@start..end` (not the subtree: see [`SyntaxTree`]'s `Debug`).
655    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/// The children of a node ([`Node::children`]).
662#[derive(Clone)]
663pub struct Children<'t> {
664    tree: &'t SyntaxTree,
665    next: Option<usize>,
666    /// The hint of `next` (edited trees).
667    hint: u32,
668    /// One past the last index of the parent's subtree; edited: one past
669    /// the last slot of `next`'s run (without a hint: 0 before the first
670    /// step, 1 after it).
671    end: usize,
672    /// The tree was edited when the iterator was made (read once, so the
673    /// unedited loop stays as tight as before the overlay existed).
674    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    /// An edited tree's step (kept out of line so the unedited loop stays
695    /// small enough to inline).
696    #[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                // The first step without a hint is the unhinted step (many
703                // iterations stop after one child); `end` = 1 marks it.
704                self.next = tree.nav_next(slot).map(|s| s as usize);
705                self.end = 1;
706                return Some(Node::new(tree, slot));
707            }
708            // Going on: one run lookup (what every step cost before
709            // the hints), then the steps inside the run are the arrays'
710            // arithmetic.
711            self.hint = tree.hint_of(slot);
712            self.end = tree.run_slots(self.hint).1 as usize;
713        }
714        let hint = self.hint;
715        // A base element whose subtree and the element after it
716        // lie in its run steps by the base arrays, as in an unedited tree
717        // (see `SyntaxTree::nav_next_hinted`).
718        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
741// The iterators' `Debug` shows only their index range, never the tree
742// (whose own `Debug` prints every element).
743impl 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/// The ancestors of an element ([`Node::ancestors`]).
753#[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/// A subtree in preorder ([`Node::descendants`]).
771#[derive(Clone)]
772pub struct Descendants<'t> {
773    tree: &'t SyntaxTree,
774    next: usize,
775    /// The hint of `next` and one past the last slot of its run
776    /// (edited trees).
777    hint: u32,
778    run_end: u32,
779    end: usize,
780    /// See [`Children`].
781    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            // Inside a run, the same increment as unedited.
792            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    /// An edited tree's step: `next` is a slot, `end` the count still to
820    /// yield (out of line, see [`Children`]).
821    #[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        // An increment inside a run, a treap step to the next
830        // run; the element after the last one is not looked for.
831        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    /// Moves to the run after the current one (`slot` its last element).
841    fn cross(&mut self, slot: u32) {
842        let next = if self.hint == super::NONE {
843            // (A hint is always set; a lookup keeps a broken one exact.)
844            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/// A step of a [`Walk`].
870#[non_exhaustive]
871#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
872pub enum WalkEvent<T> {
873    /// Entering an element (before its children).
874    Enter(T),
875    /// Leaving an element (after its children).
876    Leave(T),
877}
878
879/// A preorder walk with enter and leave steps ([`Node::walk`]). Holds no
880/// stack: the element to leave next is found through parent links.
881#[derive(Clone)]
882pub struct Walk<'t> {
883    tree: &'t SyntaxTree,
884    next: usize,
885    end: usize,
886    /// The innermost element entered and not yet left (`NO_CURRENT`: none).
887    current: usize,
888    root: u32,
889    /// The hint of `next` and the slots `run_start..run_end` of
890    /// its run, and the hint of `current` (edited trees). With `current`
891    /// and `root` narrowed, the walk is as large as before them (56 bytes:
892    /// a walk is moved around with its readers, as measured).
893    hint: u32,
894    run_start: u32,
895    run_end: u32,
896    current_hint: u32,
897    /// See [`Children`].
898    edited: bool,
899}
900
901/// `Walk::current` when no element is entered and not yet left.
902const 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    /// An edited tree's walk: `next` is the slot to enter, `end` the count
940    /// still to enter; an element is left once the next one to enter is
941    /// not its child. Inside one base run, entering a child and
942    /// leaving an element are the base arrays' steps, as unedited.
943    #[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            // `next` is a base element of `next`'s run: its parent is the
950            // base arrays'.
951            let parent = tree.parent_of(n);
952            if parent == Some(c) && self.end > 1 && n.saturating_add(1) < self.run_end as usize {
953                // Entering a child of `current`, the run going on.
954                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                // Leaving a base `current` of the same run.
970                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            // Parents from the base arrays, or through hints.
987            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                    // A base parent keeps the run's hint when it lies in
994                    // `next`'s run.
995                    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                        // (Without a hint, the step finds one: one run
1022                        // lookup. `run_start` is then where `next` is,
1023                        // which only costs the parents' hints.)
1024                        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", &current)
1052            .finish()
1053    }
1054}