Skip to main content

big_code_analysis_ast/node/
ancestors.rs

1//! [`Ancestors`], the chain of a node's ancestors a walker threads down
2//! to its predicates, and the [`SiblingCache`] and [`FoldCache`] it can
3//! lend with it.
4//!
5//! The chain, its constructors and its plain reads (`parent`, `iter`,
6//! `of_children`) are here, with the tests of the whole module. Three
7//! submodules hold the rest: `chain`, the two runs a chain reads as one;
8//! `siblings`, the sibling lookups and the record a walk keeps for them;
9//! `folds`, the folds and memos and their cache.
10
11use super::Node;
12
13mod chain;
14mod folds;
15mod siblings;
16
17use chain::{Chain, HeldChain};
18pub use folds::{
19    FoldCache, GateLane, KindLane, LevelQuestion, NodeQuestion, fold_slot_probes, fold_steps,
20};
21pub(crate) use folds::{FoldLane, MemoQuestion, NodeMemo, WordSlot};
22use siblings::NOTHING_RECORDED;
23pub use siblings::{SiblingCache, WIDE_PARENT, sibling_cache_reads, sibling_seeks};
24
25/// The chain of a node's children, held by a consumer that reads them
26/// without descending: what [`Ancestors::of_children`] builds. A
27/// consumer that does descend, into wrappers whose statements it reads
28/// as the body's own, moves it with [`descend`](Self::descend) and
29/// [`ascend`](Self::ascend) rather than building one per level.
30///
31/// It borrows the walk's chain and owns only the entries below it, so
32/// it holds the walk's `Vec` immutably for as long as it lives (#1805).
33#[derive(Debug)]
34pub struct ChildAncestors<'tree, 'chain> {
35    /// `None` without a known chain, where every answer climbs.
36    chain: Option<HeldChain<'tree, 'chain>>,
37    folds: Option<&'chain FoldCache>,
38}
39
40impl<'tree> ChildAncestors<'tree, '_> {
41    /// The children's [`Ancestors`], with the walk's fold cache carried
42    /// — and with it the visited node its word slots serve — and its
43    /// sibling cache deliberately not: the children are nodes the walk
44    /// has not recorded. Neither does an [`iter`](Ancestors::iter) from
45    /// it regain the sibling cache once it climbs back into the walk's
46    /// own chain. Forwarding the record for that climb was measured and
47    /// left out: no walk asks for a sibling there, in the suite or the
48    /// repository corpora (#1871).
49    #[inline]
50    #[must_use]
51    pub fn get(&self) -> Ancestors<'tree, '_> {
52        match &self.chain {
53            Some(chain) => Ancestors {
54                chain: Some(chain.view()),
55                siblings: None,
56                folds: self.folds,
57            },
58            None => Ancestors::unknown(),
59        }
60    }
61
62    /// Descends into `child`, one of the nodes this chain describes, so
63    /// that [`get`](Self::get) answers for *its* children; undone by
64    /// [`ascend`](Self::ascend). A consumer that reads a body's
65    /// statements through the wrappers they sit in — Ruby's `npm` under
66    /// an `if`, a `begin`, a call's argument list — keeps one chain and
67    /// moves it, where deriving a fresh [`Ancestors::of_children`] from
68    /// the last at each level copies every level derived so far, all of
69    /// them live at once (#1401 review). Without a known chain there is
70    /// nothing to move and the answers keep climbing.
71    #[inline]
72    pub fn descend(&mut self, child: &Node<'tree>) {
73        if let Some(chain) = &mut self.chain {
74            chain.descend(child);
75        }
76    }
77
78    /// Undoes one [`descend`](Self::descend). The chain never shrinks
79    /// below the node it was built for, so a consumer that ascends once
80    /// too often reads the body's own chain rather than its parent's —
81    /// and trips the assertion in a debug build.
82    #[inline]
83    pub fn ascend(&mut self) {
84        if let Some(chain) = &mut self.chain {
85            chain.ascend();
86        }
87    }
88}
89
90/// The chain of a node's ancestors, root first, as recorded by a walker
91/// that descended to that node.
92///
93/// A predicate that asks a node for its parent pays [`Node::parent`]'s
94/// `O(depth)` once per node, so `O(depth²)` over a deeply nested file,
95/// however few parent steps it takes (#1084). A walker that visits
96/// parents before children already holds the chain, and handing it down
97/// turns each step into a slice index — the upward counterpart of the
98/// downward flag propagation #1052 and #1062 used.
99///
100/// Callers that reached a node some other way pass
101/// [`Ancestors::unknown`], which climbs with [`Node::parent`]: the same
102/// answers at the original cost.
103///
104/// A chain derived below the walk's ([`of_children`](Self::of_children))
105/// reads the walk's chain in place and the entries it adds after it, as
106/// one chain at the same depths (#1805).
107///
108/// A walk's own chain states whether the walk records siblings: it is
109/// built with [`for_walk`](Self::for_walk), which requires the walk's
110/// [`SiblingCache`], or with
111/// [`for_walk_without_siblings`](Self::for_walk_without_siblings) or,
112/// inside this crate, `for_walk_chain_only`, which say that it records
113/// none. A walk can no longer leave the cache out by forgetting a
114/// builder call (#1601).
115#[derive(Clone, Copy, Debug)]
116pub struct Ancestors<'tree, 'chain> {
117    chain: Option<Chain<'tree, 'chain>>,
118    /// Where a sibling lookup reads from. The constructor decides, and
119    /// [`iter`](Self::iter) and a fold step's `outer` chain keep what
120    /// they were derived from:
121    ///
122    /// - [`for_walk`](Self::for_walk): the walk's record of its wide
123    ///   parents. A lookup under one is a binary search, and a wide
124    ///   parent the record lacks trips the assertion in
125    ///   [`lookup`](Self::lookup).
126    /// - [`for_walk_without_siblings`](Self::for_walk_without_siblings)
127    ///   and [`for_walk_chain_only`](Self::for_walk_chain_only):
128    ///   [`NOTHING_RECORDED`], the record of a walk that records none,
129    ///   so every wide parent trips that assertion.
130    /// - [`known`](Self::known), [`below`](Self::below) and
131    ///   [`of_children`](Self::of_children): `None`, a chain that is
132    ///   not a walk's own. `siblings_before` and `siblings_after` seek a
133    ///   wide parent through it, and `previous_sibling` has its own
134    ///   assertion there (#1785). A chain iterated from a derived one
135    ///   stays `None` even where it climbs back into the walk's chain.
136    /// - [`unknown`](Self::unknown): `None` and no chain, so every
137    ///   lookup resolves the parent from the node and asserts nothing.
138    ///
139    /// Under a parent of at most [`WIDE_PARENT`] children every chain
140    /// seeks. `Some` therefore does not mean that the walk records
141    /// siblings.
142    siblings: Option<&'chain SiblingCache<'tree>>,
143    folds: Option<&'chain FoldCache>,
144}
145
146impl<'tree, 'chain> Ancestors<'tree, 'chain> {
147    /// No chain is available; every query climbs with [`Node::parent`].
148    #[inline]
149    #[must_use]
150    pub const fn unknown() -> Self {
151        Self {
152            chain: None,
153            siblings: None,
154            folds: None,
155        }
156    }
157
158    /// `chain` lists every ancestor of the node about to be queried,
159    /// root first — so `chain.last()` is its parent and an empty chain
160    /// means the node is the root.
161    ///
162    /// Not for the chain a walk keeps: a walk constructs through
163    /// [`for_walk`](Self::for_walk) or
164    /// [`for_walk_without_siblings`](Self::for_walk_without_siblings)
165    /// (or, inside this crate, `for_walk_chain_only`), which check the
166    /// chain against the node and state whether the walk records
167    /// siblings. A chain built here seeks for a sibling under a wide
168    /// parent with no such check (#1601).
169    #[inline]
170    #[must_use]
171    pub const fn known(chain: &'chain [Node<'tree>]) -> Self {
172        Self {
173            chain: Some(Chain::flat(chain)),
174            siblings: None,
175            folds: None,
176        }
177    }
178
179    /// This chain, answering [`siblings_after`](Self::siblings_after) and
180    /// [`siblings_before`](Self::siblings_before) through `cache`.
181    /// Test-only, for a test that drives a lookup directly: a walk lends
182    /// its cache through [`for_walk`](Self::for_walk), which requires it,
183    /// so no walk can leave the cache out by omission (#1601).
184    #[cfg(test)]
185    #[inline]
186    #[must_use]
187    pub(crate) const fn with_siblings(self, cache: &'chain SiblingCache<'tree>) -> Self {
188        Self {
189            siblings: Some(cache),
190            ..self
191        }
192    }
193
194    /// This chain, memoising `Ancestors::fold_down` and the per-node
195    /// memos through `cache`, without recording a visit: the word slots
196    /// serve only the node the cache was told is being visited, and
197    /// nothing tells it here. Test-only, for a test that drives a fold
198    /// or a memo directly: a walk lends its cache through
199    /// [`for_walk`](Self::for_walk) or
200    /// [`for_walk_without_siblings`](Self::for_walk_without_siblings),
201    /// the only non-test constructors that set `folds`, and both record
202    /// the visit, so no lender can lend the cache and skip it (#1737).
203    #[cfg(test)]
204    #[inline]
205    #[must_use]
206    pub(crate) const fn with_folds(self, cache: &'chain FoldCache) -> Self {
207        Self {
208            folds: Some(cache),
209            ..self
210        }
211    }
212
213    /// The chain a walk hands its predicates for `node`, the node it is
214    /// visiting: `chain`, checked against `node` as
215    /// [`for_walk_without_siblings`](Self::for_walk_without_siblings)
216    /// checks it, lending `folds` with the visit recorded on it (#1737)
217    /// and answering sibling lookups from `siblings`, the children the
218    /// walk recorded of every wide node on `chain` (#1584). Lending the
219    /// caches and naming the
220    /// visited node are one step that no walk can split: outside the
221    /// walk constructors, only the test-only `with_folds` and
222    /// `with_siblings` set either cache (#1601). A walk that records no
223    /// siblings says so with
224    /// [`for_walk_without_siblings`](Self::for_walk_without_siblings).
225    ///
226    /// The visit is what `Ancestors::classified` keys the word slots
227    /// on: an ask about `node` is served and stored, an ask about any
228    /// other node — an enclosing call read from a descendant, a module's
229    /// statements read while the module is visited — is computed and
230    /// not stored, so it cannot evict the visited node's answer. A
231    /// derived chain ([`of_children`](Self::of_children), `below`,
232    /// [`iter`](Self::iter), the `outer` a fold step is handed) carries
233    /// the same cache and so the same visit.
234    #[inline]
235    #[must_use]
236    pub fn for_walk(
237        chain: &'chain [Node<'tree>],
238        node: &Node<'tree>,
239        folds: &'chain FoldCache,
240        siblings: &'chain SiblingCache<'tree>,
241    ) -> Self {
242        Self {
243            siblings: Some(siblings),
244            ..Self::for_walk_without_siblings(chain, node, folds)
245        }
246    }
247
248    /// [`for_walk`](Self::for_walk) for a walk that records no siblings:
249    /// the suppression scan and the dump. No predicate those walks call
250    /// asks for a sibling under any parent, which
251    /// `the_walks_that_record_no_siblings_ask_for_none` pins in the root
252    /// crate, since a predicate cannot know that its parent is narrow.
253    /// This chain enforces the costly half: a sibling asked under a
254    /// parent wider than [`WIDE_PARENT`] trips the assertion in `lookup`
255    /// in a debug build, because the seek is `O(index)` and a walk that
256    /// asks it of every child of a flat `ERROR` is quadratic (#1584).
257    /// When a predicate of such a walk needs a sibling, the walk records
258    /// each wide node's children as it pushes them and constructs
259    /// through [`for_walk`](Self::for_walk) instead (#1601).
260    ///
261    /// # Panics
262    ///
263    /// When `chain` is not `node`'s ancestry, as a walk's chain is after
264    /// a slip in its truncate/push bookkeeping. A debug build checks an
265    /// `O(1)` consequence: `chain.last()` is not `node` itself, and its
266    /// byte span contains `node`'s. That catches a `push` moved ahead of
267    /// the per-node work and a dropped `truncate`, and misses a chain
268    /// short by exactly one entry. Under `--cfg chain_audit`, which
269    /// `make chain-audit` sets, every profile asserts the exact
270    /// `chain.last() == node.parent()` instead, at [`Node::parent`]'s
271    /// `O(depth)` per node (#1122). [`for_walk`](Self::for_walk) builds
272    /// on this constructor and panics the same way.
273    #[inline]
274    #[must_use]
275    pub fn for_walk_without_siblings(
276        chain: &'chain [Node<'tree>],
277        node: &Node<'tree>,
278        folds: &'chain FoldCache,
279    ) -> Self {
280        folds.record_visit(node);
281        Self {
282            folds: Some(folds),
283            ..Self::for_walk_chain_only(chain, node)
284        }
285    }
286
287    /// The chain of a walk that lends no cache, the comment-removal
288    /// walk: [`Ancestors::known`] for the chain a walk keeps. It first
289    /// checks that `chain` really is `node`'s ancestry, and it lends the
290    /// empty sibling record of a walk that records none. Every
291    /// `for_walk` constructor makes the check, and
292    /// [`for_walk_without_siblings`](Self::for_walk_without_siblings)
293    /// lends the same record; this one adds nothing to them, which is
294    /// its name.
295    ///
296    /// The parity test (`a_known_chain_answers_exactly_what_climbing_answers`
297    /// in `node.rs`) proves the walker's truncate/push rule on a
298    /// *replica* walker, so it cannot see `metrics_inner` itself
299    /// desynchronising — a `chain.push` moved ahead of the per-node
300    /// computes, say, or a `continue` inserted above the truncate.
301    /// [`Ancestors::parent`] trusts `chain.last()` unvalidated, so such a
302    /// drift would feed every predicate a wrong ancestor silently rather
303    /// than fail. Walkers that maintain a chain should construct through
304    /// here — through [`for_walk`](Self::for_walk) or
305    /// [`for_walk_without_siblings`](Self::for_walk_without_siblings),
306    /// which build on it, when they lend a [`FoldCache`];
307    /// [`Ancestors::known`] stays unchecked for the callers that
308    /// deliberately pair a chain with a foreign node.
309    ///
310    /// A checked chain is a walk's own, so a sibling asked through it
311    /// under a parent wider than [`WIDE_PARENT`] trips the assertion in
312    /// `lookup` (#1601).
313    ///
314    /// Crate-private: a walk outside this crate lends a [`FoldCache`]
315    /// and says so with [`for_walk`](Self::for_walk) or
316    /// [`for_walk_without_siblings`](Self::for_walk_without_siblings).
317    /// It was the public `checked` until #1871, a name that said only
318    /// the first of the two things it does.
319    ///
320    /// # Two checks, because the exact one is not affordable by default
321    ///
322    /// The invariant is "`chain.last()` **is** `node.parent()`", and
323    /// asking that outright costs [`Node::parent`]'s `O(depth)` — the
324    /// very lookup #1084 exists to remove. Per node, on every walk that
325    /// constructs a checked chain, it made every debug-build walk
326    /// `O(nodes × depth)` while the shipped walk is `O(nodes)`: a tax on
327    /// every `cargo test`, worst on the deep-nesting regression tests
328    /// that exist to pin the shipped walk's linearity (#1122). It now
329    /// runs only under `--cfg chain_audit`, which `make chain-audit` and
330    /// the CI lane of the same name set — and there as a plain
331    /// `assert_eq!`, so the audit has teeth in a release profile too.
332    ///
333    /// What stays on in every debug build is an `O(1)` *consequence* of
334    /// that invariant: a parent's byte span contains its child's, and no
335    /// node is its own parent. Strictly weaker — a grandparent contains
336    /// the node as well — but it is shaped to the two ways a walker
337    /// desynchronises. A `push` moved ahead of the per-node computes
338    /// leaves `chain.last() == node`; a dropped `truncate` leaves the
339    /// previous subtree's path, whose last entry is disjoint from the
340    /// node that follows it. Both trip here, on the first node that
341    /// shows them, at four integer comparisons.
342    #[inline]
343    #[must_use]
344    pub(crate) fn for_walk_chain_only(chain: &'chain [Node<'tree>], node: &Node<'tree>) -> Self {
345        // Opt-in only: `Node::parent` restarts at the root, so this is
346        // the `O(nodes × depth)` walk described above.
347        #[cfg(chain_audit)]
348        assert_eq!(
349            chain.last().map(Node::id),
350            node.parent().map(|parent| parent.id()),
351            "ancestor chain desynchronised on a {} node",
352            node.kind()
353        );
354        debug_assert!(
355            chain.last().is_none_or(|parent| {
356                parent.id() != node.id()
357                    && parent.start_byte() <= node.start_byte()
358                    && node.end_byte() <= parent.end_byte()
359            }),
360            "ancestor chain desynchronised on a {} node: chain.last() neither \
361             contains it nor differs from it",
362            node.kind()
363        );
364        Self {
365            siblings: Some(NOTHING_RECORDED),
366            ..Self::known(chain)
367        }
368    }
369
370    /// Whether the chain is known — a walk handed it in — rather than
371    /// the climbing [`Ancestors::unknown`]. A caller about to replace the
372    /// chain with [`below`](Self::below) checks it first: the climb is
373    /// already exact, where a replacing chain is exact only for what it
374    /// holds. [`of_children`](Self::of_children) needs no check, since it
375    /// derives an unknown chain from an unknown one.
376    pub(crate) const fn is_known(self) -> bool {
377        self.chain.is_some()
378    }
379
380    /// The chain of the ancestor at `depth` on this one: this chain cut
381    /// above it, with the same caches. What a fold step is handed for
382    /// the ancestor it judges, built here so that what a derived chain
383    /// keeps is decided in this file, as it is for [`iter`](Self::iter).
384    fn above(self, depth: usize) -> Self {
385        Self {
386            chain: self.chain.map(|chain| chain.above(depth)),
387            ..self
388        }
389    }
390
391    /// How far the node this chain describes sits from the root, or
392    /// `None` when no chain is known — deriving it then would cost the
393    /// [`Node::parent`] climb the chain exists to remove.
394    #[inline]
395    pub fn depth(self) -> Option<usize> {
396        self.chain.map(Chain::len)
397    }
398
399    /// The chain of `node`'s children, held: `self` extended by `node`,
400    /// for a consumer that holds a body's chain and asks a row about the
401    /// body's *members* — `npa` and `npm` over a class body, a parse
402    /// error's children asked whether they are doc targets — and, where
403    /// it reads through a member's own children, moves the chain with
404    /// [`ChildAncestors::descend`] rather than building another. A row's
405    /// gate reads the chain it is handed as the queried node's own, so
406    /// handing it the body's instead answers from the wrong parent the
407    /// moment a `Member` or `FuncOpener` row grows a gate; the comment
408    /// "the row reads no chain" was the only guard before this. Without a
409    /// known chain the result climbs, as [`Ancestors::unknown`] does.
410    /// Read it with [`ChildAncestors::get`].
411    ///
412    /// The walk's chain is borrowed, not copied: from it this is one
413    /// allocation of one entry, whatever the depth. From a chain itself
414    /// derived it copies the entries that one added below the walk's,
415    /// which every caller bounds by a fixed structural nesting. A copy of
416    /// the whole chain per container was quadratic in nested containers
417    /// (#1805).
418    #[must_use]
419    pub fn of_children(self, node: &Node<'tree>) -> ChildAncestors<'tree, 'chain> {
420        child_chains_derived::record();
421        ChildAncestors {
422            chain: self.chain.map(|chain| HeldChain::below(chain, *node)),
423            folds: self.folds,
424        }
425    }
426
427    /// `self` re-rooted on `chain`, which replaces its chain rather than
428    /// extending it, with the walk's [`FoldCache`] carried over and its
429    /// [`SiblingCache`] deliberately not. Doxygen hands a conditional's
430    /// children a chain of that one entry this way (`chain_below`).
431    ///
432    /// The fold cache is per walk, not per chain, so a derived chain
433    /// reads and stores through the same one. Rebuilding with
434    /// [`Ancestors::known`] instead dropped it silently — the shape
435    /// lesson 101 is about — and left Doxygen's conditionals inside an
436    /// `ERROR` child unmemoised (#1686 review). Sharing it is sound for
437    /// a fold lane, whose slots are keyed by depth and id, and for a
438    /// memo of a node's own subtree. It is not for
439    /// [`nearest_level_answer`](Self::nearest_level_answer), whose memo
440    /// holds an answer about the ancestry this chain cuts short: do not
441    /// ask one from a re-rooted chain.
442    ///
443    /// The sibling cache is keyed by depth and holds only the nodes the
444    /// walk has pushed; the node this chain descends into is one the walk
445    /// has *not* reached, so its slot is empty and a lookup through it
446    /// would trip the walk-must-record assertion in [`lookup`](Self::lookup)
447    /// on a wide one. Java's `is_doc_target` asks for a sibling, and a
448    /// `class {` with a hundred stray `@` after it made exactly that
449    /// `ERROR` (#1686 review). Without the cache the lookup seeks, which
450    /// is what it did before and all an unrecorded node can offer.
451    /// [`ChildAncestors::get`] drops it for the same reason.
452    #[inline]
453    #[must_use]
454    pub(crate) const fn below<'below>(
455        self,
456        chain: &'below [Node<'tree>],
457    ) -> Ancestors<'tree, 'below>
458    where
459        'chain: 'below,
460    {
461        Ancestors {
462            chain: Some(Chain::flat(chain)),
463            siblings: None,
464            folds: self.folds,
465        }
466    }
467
468    /// `node`'s parent.
469    #[inline]
470    #[must_use]
471    pub fn parent(self, node: &Node<'tree>) -> Option<Node<'tree>> {
472        match self.chain {
473            Some(chain) => chain.last().copied(),
474            None => node.parent(),
475        }
476    }
477
478    /// Whether `node`'s parent has kind id `kind`.
479    ///
480    /// The compound-leaf guard of `docs/development/grammar_dispatch.md`
481    /// section 5 asks this and nothing else: a delimiter or keyword
482    /// token is suppressed *only* directly under the construct that
483    /// owns it, never under an arbitrary ancestor. Eleven dispatch
484    /// arms across `getter`, `checker` and the metric walkers spelled
485    /// it out as `.parent(node).is_some_and(|p| p.kind_id() == X as
486    /// u16)`, which wraps onto four rustfmt lines inside a match guard
487    /// and buries the question under the plumbing; #1314 added six more
488    /// and folded all seventeen onto this, and #1697 the `ElseIf`
489    /// gates. Two sites spelling their binding `|parent|` were left
490    /// alone and would each fit:
491    /// `is_stabby_lambda_body` (`src/lang_helpers/ruby.rs`) and
492    /// `is_useful_comment` (`src/checker/rust.rs`, a let-chain).
493    ///
494    /// A `false` when `node` has no parent is the answer every one of
495    /// those call sites wants: a root node's token is not inside the
496    /// construct, so it is not suppressed.
497    #[inline]
498    #[must_use]
499    pub fn parent_has_kind(self, node: &Node<'tree>, kind: u16) -> bool {
500        self.parent(node).is_some_and(|p| p.kind_id() == kind)
501    }
502
503    /// `node`'s ancestors, nearest first, each paired with *its* own
504    /// ancestry so a predicate applied to an ancestor stays as cheap as
505    /// one applied to `node`.
506    #[inline]
507    #[must_use]
508    pub fn iter(self, node: &Node<'tree>) -> AncestorIter<'tree, 'chain> {
509        AncestorIter(match self.chain {
510            Some(chain) => AncestorSource::Chain(chain, self.siblings, self.folds),
511            None => AncestorSource::Climb(node.parent()),
512        })
513    }
514}
515
516// Chains derived with `Ancestors::of_children`, so a test can see a walk
517// derive one per container body rather than one per node it visits: a
518// derivation is one allocation since #1805, so a build hoisted ahead of
519// the body-kind test (lesson 103, #1696) is a constant factor the scaling
520// gate cannot price, and this counter is what tells the two apart.
521crate::observation::counter!(
522    child_chains_derived,
523    cfg(any(test, feature = "test-support"))
524);
525
526/// Ancestor iterator returned by [`Ancestors::iter`], nearest first.
527///
528/// The representation is private so that [`Ancestors::iter`] is its
529/// only constructor: every chain it yields carries the caches of the
530/// `Ancestors` it was made from, and nothing else can pair a
531/// [`FoldCache`] with a chain. That is what lets the walk constructors
532/// ([`Ancestors::for_walk`], which builds on
533/// [`Ancestors::for_walk_without_siblings`]) be the one place a visit is
534/// recorded (#1737) — a public variant holding `Option<&FoldCache>`
535/// would have let any caller lend a cache without one.
536pub struct AncestorIter<'tree, 'chain>(AncestorSource<'tree, 'chain>);
537
538enum AncestorSource<'tree, 'chain> {
539    /// The not-yet-yielded prefix of a known chain, and the walk's
540    /// [`SiblingCache`] and [`FoldCache`] if it lent them. The prefix's
541    /// last element is the next ancestor, and the prefix before it is
542    /// that ancestor's own chain — so splitting from the back hands out
543    /// both at once.
544    ///
545    /// The caches travel with each yielded chain, so a predicate asked
546    /// of an ancestor is memoised exactly as one asked of the node
547    /// itself. A braced Tcl word's role is asked of its *parent* through
548    /// this iterator, and dropping the [`FoldCache`] here left that
549    /// question unmemoised on every walk that lent one (#1686).
550    Chain(
551        Chain<'tree, 'chain>,
552        Option<&'chain SiblingCache<'tree>>,
553        Option<&'chain FoldCache>,
554    ),
555    /// The next ancestor to yield, reached by climbing.
556    Climb(Option<Node<'tree>>),
557}
558
559impl<'tree, 'chain> Iterator for AncestorIter<'tree, 'chain> {
560    type Item = (Node<'tree>, Ancestors<'tree, 'chain>);
561
562    fn next(&mut self) -> Option<Self::Item> {
563        match &mut self.0 {
564            AncestorSource::Chain(remaining, siblings, folds) => {
565                let (&nearest, above) = remaining.split_last()?;
566                *remaining = above;
567                let ancestors = Ancestors {
568                    chain: Some(above),
569                    siblings: *siblings,
570                    folds: *folds,
571                };
572                Some((nearest, ancestors))
573            }
574            AncestorSource::Climb(next) => {
575                let nearest = (*next)?;
576                *next = nearest.parent();
577                Some((nearest, Ancestors::unknown()))
578            }
579        }
580    }
581}
582
583#[cfg(test)]
584mod tests {
585    use std::panic::{AssertUnwindSafe, catch_unwind};
586
587    use super::folds::{climbed_chain, same_lane_reentry};
588    use super::siblings::{Lookup, position_by_start};
589    use super::*;
590    use crate::node::Tree;
591
592    // `node`'s ancestors' ids, nearest first, climbed with `Node::parent`:
593    // the reference every chain a holder derives must reproduce.
594    #[cfg(any(
595        feature = "cpp",
596        feature = "java",
597        feature = "kotlin",
598        feature = "ruby",
599        feature = "rust"
600    ))]
601    fn climbed_ids(node: &Node) -> Vec<usize> {
602        std::iter::successors(node.parent(), Node::parent)
603            .map(|ancestor| ancestor.id())
604            .collect()
605    }
606
607    // Asserts that `ancestors` describes `node`'s whole ancestry as the
608    // climb does: its depth, its parent, every ancestor `iter` yields
609    // and that ancestor's own chain, its previous sibling and both
610    // sibling runs.
611    #[cfg(any(
612        feature = "cpp",
613        feature = "java",
614        feature = "kotlin",
615        feature = "ruby",
616        feature = "rust"
617    ))]
618    fn assert_describes<'t>(ancestors: Ancestors<'t, '_>, node: &Node<'t>) {
619        let kind = node.kind();
620        let climbed = climbed_ids(node);
621        let id = |node: Option<Node>| node.map(|node| node.id());
622        assert_eq!(ancestors.depth(), Some(climbed.len()), "{kind}: depth");
623        assert_eq!(
624            id(ancestors.parent(node)),
625            id(node.parent()),
626            "{kind}: parent"
627        );
628        let mut iterated = Vec::new();
629        for (ancestor, above) in ancestors.iter(node) {
630            assert_eq!(
631                (id(above.parent(&ancestor)), above.depth()),
632                (
633                    id(ancestor.parent()),
634                    Some(climbed.len() - 1 - iterated.len())
635                ),
636                "{kind}: the chain `iter` yields with its {} ancestor",
637                ancestor.kind()
638            );
639            iterated.push(ancestor.id());
640        }
641        assert_eq!(iterated, climbed, "{kind}: ancestry");
642        assert_eq!(
643            id(ancestors.previous_sibling(node)),
644            id(node.previous_sibling()),
645            "{kind}: previous sibling"
646        );
647        let (before, after): (Vec<usize>, Vec<usize>) =
648            node.parent().map_or_else(Default::default, |parent| {
649                let siblings: Vec<usize> = parent.children().map(|child| child.id()).collect();
650                let at = siblings
651                    .iter()
652                    .position(|&sibling| sibling == node.id())
653                    .expect("a node is among its parent's children");
654                (
655                    siblings[..at].iter().rev().copied().collect(),
656                    siblings[at + 1..].to_vec(),
657                )
658            });
659        let ids = |nodes: &mut dyn Iterator<Item = Node>| nodes.map(|n| n.id()).collect::<Vec<_>>();
660        assert_eq!(
661            ids(&mut ancestors.siblings_before(node)),
662            before,
663            "{kind}: before"
664        );
665        assert_eq!(
666            ids(&mut ancestors.siblings_after(node)),
667            after,
668            "{kind}: after"
669        );
670    }
671
672    // Every chain a holder derives below the walk's, at every node of
673    // `source`, checked against the climb for each node it describes:
674    // one level (`of_children` of the walk's chain), two (`of_children`
675    // of a derived chain) and moved (`descend` into each child, then
676    // `ascend` back to the floor). Returns how many nodes two levels down
677    // were checked, so a caller can tell its fixture nests.
678    #[cfg(any(
679        feature = "cpp",
680        feature = "java",
681        feature = "kotlin",
682        feature = "ruby",
683        feature = "rust"
684    ))]
685    fn check_derived_ancestry<L: crate::traits::LanguageInfo>(
686        source: &[u8],
687        recovers: bool,
688    ) -> usize {
689        let mut checked = 0;
690        let check = |node: &Node<'_>, chain: &[Node<'_>]| {
691            let walk = Ancestors::known(chain);
692            let under = walk.of_children(node);
693            let mut held = walk.of_children(node);
694            for child in node.children() {
695                assert_describes(under.get(), &child);
696                let nested = under.get().of_children(&child);
697                held.descend(&child);
698                for grandchild in child.children() {
699                    assert_describes(nested.get(), &grandchild);
700                    assert_describes(held.get(), &grandchild);
701                    checked += 1;
702                }
703                held.ascend();
704                assert_describes(held.get(), &child);
705            }
706        };
707        if recovers {
708            crate::test_support::for_each_node_with_chain_tolerating_errors::<L>(source, check);
709        } else {
710            crate::test_support::for_each_node_with_chain::<L>(source, check);
711        }
712        checked
713    }
714
715    /// Every chain derived below a walk's — one level, two levels, and
716    /// moved with `descend` / `ascend` — answers every ancestry question
717    /// as climbing with `Node::parent` does: depth, parent, each ancestor
718    /// `iter` yields with that ancestor's own chain, the previous
719    /// sibling and both sibling runs (#1805). A view that misread the
720    /// seam between the walk's borrowed chain and the entries a holder
721    /// owns — an index off by one there, an `iter` that dropped or
722    /// repeated the entry either side — answers one of them wrong.
723    /// Rust, Ruby, C++ and Java nest the containers the member walks
724    /// derive chains for.
725    #[cfg(feature = "rust")]
726    #[test]
727    fn a_derived_chain_describes_the_whole_ancestry_in_rust() {
728        let source = b"mod a {\n    struct S { x: i32, y: (i32, u8) }\n    impl S {\n        fn f(&self, v: i32) -> i32 { if v > 0 { g(v) } else { h(1, 2) } }\n    }\n}\n";
729        let checked = check_derived_ancestry::<crate::langs::RustCode>(source, false);
730        assert!(checked > 50, "the fixture must nest: {checked}");
731    }
732
733    #[cfg(feature = "ruby")]
734    #[test]
735    fn a_derived_chain_describes_the_whole_ancestry_in_ruby() {
736        let source = b"class A\n  class B\n    attr_reader :x\n    # Doc.\n    def m(a)\n      if a then b end\n    end\n  end\nend\n";
737        let checked = check_derived_ancestry::<crate::langs::RubyCode>(source, false);
738        assert!(checked > 20, "the fixture must nest: {checked}");
739    }
740
741    #[cfg(feature = "cpp")]
742    #[test]
743    fn a_derived_chain_describes_the_whole_ancestry_in_cpp() {
744        let source = b"namespace n { struct A { struct B { int x; void f(); }; }; }\n";
745        let checked = check_derived_ancestry::<crate::langs::CppCode>(source, false);
746        assert!(checked > 20, "the fixture must nest: {checked}");
747    }
748
749    #[cfg(feature = "java")]
750    #[test]
751    fn a_derived_chain_describes_the_whole_ancestry_in_java() {
752        let source = b"class A { class B { int x; void f() { if (x > 0) { g(); } } } }\n";
753        let checked = check_derived_ancestry::<crate::langs::JavaCode>(source, false);
754        assert!(checked > 20, "the fixture must nest: {checked}");
755    }
756
757    // Whether `source` parses into a tree holding an `ERROR`, a zero-width
758    // node at its parent's start, and one at its parent's end: the
759    // recovery shapes the parity checks below need present. Only a
760    // zero-width child at an edge tells `descend`'s non-strict
761    // containment check from a strict one, so one inside its parent
762    // would not do.
763    #[cfg(any(feature = "kotlin", feature = "rust"))]
764    fn recovery_shapes<L: crate::traits::LanguageInfo>(source: &[u8]) -> (bool, bool, bool) {
765        let tree = Tree::new::<L>(source);
766        let nodes: Vec<Node> = tree.get_root().preorder().collect();
767        let zero_width_at = |edge: &dyn Fn(&Node, &Node) -> bool| {
768            nodes.iter().any(|node| {
769                node.start_byte() == node.end_byte()
770                    && node.parent().is_some_and(|parent| edge(node, &parent))
771            })
772        };
773        (
774            nodes.iter().any(Node::is_error),
775            zero_width_at(&|node, parent| node.start_byte() == parent.start_byte()),
776            zero_width_at(&|node, parent| node.end_byte() == parent.end_byte()),
777        )
778    }
779
780    /// The same parity under recovery: an `ERROR` the parser could not
781    /// place, and a `;` it inserted as a zero-width node at its parent's
782    /// end. `descend`'s containment check compares identity and
783    /// non-strict spans, so a zero-width child at either edge is still
784    /// contained.
785    #[cfg(feature = "rust")]
786    #[test]
787    fn a_derived_chain_describes_the_whole_ancestry_under_recovery() {
788        let source =
789            b"fn f() { let x = ; }\nfn g() { let y = 1 }\nmod m { struct S { a: (i32, u8) } }\n";
790        let (error, _, at_end) = recovery_shapes::<crate::langs::RustCode>(source);
791        assert!(
792            error && at_end,
793            "the fixture must hold an ERROR and a zero-width node at its parent's end"
794        );
795        let checked = check_derived_ancestry::<crate::langs::RustCode>(source, true);
796        assert!(checked > 20, "the fixture must nest: {checked}");
797    }
798
799    /// Kotlin's `vararg: Int` holds the other edge: an identifier the
800    /// parser inserted as a zero-width node at its parent's start.
801    #[cfg(feature = "kotlin")]
802    #[test]
803    fn a_derived_chain_describes_the_whole_ancestry_around_a_zero_width_start() {
804        let source = b"fun f(vararg: Int, b: Int) {}\n";
805        let (error, at_start, _) = recovery_shapes::<crate::langs::KotlinCode>(source);
806        assert!(
807            !error && at_start,
808            "the fixture must hold a zero-width node at its parent's start and no ERROR"
809        );
810        let checked = check_derived_ancestry::<crate::langs::KotlinCode>(source, true);
811        assert!(checked > 10, "the fixture must nest: {checked}");
812    }
813
814    /// A chain that lends no `SiblingCache` reaching `previous_sibling`'s
815    /// scan under a wide parent trips the debug assertion there, rather
816    /// than going quadratic in silence (#1785). No production walk does;
817    /// this is what shows the assertion can fire at all, so its silence
818    /// across the suite means something.
819    #[cfg(all(feature = "rust", debug_assertions))]
820    #[test]
821    #[should_panic(expected = "with no SiblingCache (#1785)")]
822    fn previous_sibling_rejects_a_wide_parent_without_its_cache() {
823        let source = "fn a() {}\n".repeat(WIDE_PARENT + 1);
824        let tree = Tree::new::<crate::langs::RustCode>(source.as_bytes());
825        let root = tree.get_root();
826        let last = root.children().last().expect("the file has items");
827        let _ = Ancestors::known(&[root]).previous_sibling(&last);
828    }
829
830    /// A chain that does not describe the node still falls back to the
831    /// tree under a wide parent, as it does under a narrow one
832    /// (`previous_sibling_falls_back_on_a_chain_that_is_not_this_nodes`):
833    /// the #1785 assertion is about a scan that found the node, and a
834    /// mismatched chain is the caller error the fallback answers.
835    /// Discriminates only under a debug build, where the assertion is
836    /// compiled in.
837    #[cfg(feature = "rust")]
838    #[test]
839    fn previous_sibling_falls_back_on_a_wide_chain_that_is_not_this_nodes() {
840        let source = format!(
841            "fn a() {{ let x = 1; }}\n{}",
842            "fn b() {}\n".repeat(WIDE_PARENT)
843        );
844        let tree = Tree::new::<crate::langs::RustCode>(source.as_bytes());
845        let root = tree.get_root();
846        assert!(root.child_count() > WIDE_PARENT, "the root must be wide");
847        let statement = root
848            .preorder()
849            .find(|node| node.kind() == "let_declaration")
850            .expect("fixture has a statement");
851        let expected = statement
852            .previous_sibling()
853            .map(|node| node.id())
854            .expect("the statement follows the body's `{`");
855        // The root is not the statement's parent, which is the body.
856        assert_eq!(
857            Ancestors::known(&[root])
858                .previous_sibling(&statement)
859                .map(|node| node.id()),
860            Some(expected),
861            "a mismatched chain must fall back, not panic or report `None`"
862        );
863    }
864
865    // The ids of `nodes`, so a failing comparison prints which differ.
866    #[cfg(feature = "perl")]
867    fn ids<'a>(nodes: impl Iterator<Item = Node<'a>>) -> Vec<usize> {
868        nodes.map(|node| node.id()).collect()
869    }
870
871    // `parent`'s children through `child(i)`, the raw walk that neither
872    // the seek nor the recorded array is built on.
873    #[cfg(feature = "perl")]
874    fn raw_children(parent: &Node) -> Vec<usize> {
875        let raw = parent.as_tree_sitter();
876        (0..raw.child_count() as u32)
877            .filter_map(|i| raw.child(i))
878            .map(|child| child.id())
879            .collect()
880    }
881
882    // `my @r = (` and a body never closed: recovery makes the root an
883    // `ERROR` whose children are the body's tokens, one flat array of
884    // well over `WIDE_PARENT` of them.
885    #[cfg(feature = "perl")]
886    fn flat_error() -> Tree {
887        let source = format!("my @r = ({}", "{\nlast,\n$a && $b,\n".repeat(20));
888        Tree::new::<crate::langs::PerlCode>(source.as_bytes())
889    }
890
891    /// `fold_down` answers the same through all three of its paths: the
892    /// walk's memoised [`FoldCache`], a known chain with no cache, and the
893    /// chainless climb. Queried in walk order, as the metrics walk queries
894    /// it, and twice per node so the second query is answered from the
895    /// stored slots (#1597). The step depends on order, on `below` and on
896    /// the parent its `outer` chain names, so a slot read at the wrong
897    /// depth, a climb in the wrong direction or an `outer` cut at the wrong
898    /// place changes the answer. The climb hands `Ancestors::unknown()`,
899    /// whose `parent` falls back to `Node::parent`, so all three agree only
900    /// when the chains are right.
901    #[cfg(feature = "rust")]
902    #[test]
903    fn fold_down_agrees_across_its_cache_chain_and_climb_paths() {
904        let tree = Tree::new::<crate::langs::RustCode>(
905            b"mod a {\n    mod b {\n        fn f() { let x = (1 + 2) * 3; }\n    }\n    fn g() {}\n}\nfn h() { if true { 4 } else { 5 }; }\n",
906        );
907        let step = |state: u8, ancestor: &Node, outer: Ancestors, below: &Node| {
908            let parent = outer
909                .parent(ancestor)
910                .map_or(0, |parent| parent.kind_id().to_le_bytes()[0]);
911            state
912                .wrapping_mul(31)
913                .wrapping_add(ancestor.kind_id().to_le_bytes()[0])
914                .wrapping_add(below.kind_id().to_le_bytes()[0].rotate_left(3))
915                .wrapping_add(parent.rotate_left(5))
916        };
917        let cache = FoldCache::default();
918        let mut stack = vec![(tree.get_root(), 0_usize)];
919        let mut chain: Vec<Node> = Vec::new();
920        let mut queried = 0_usize;
921        while let Some((node, depth)) = stack.pop() {
922            chain.truncate(depth);
923            for skip in 0..=3 {
924                let cached = |c: &[Node<'_>]| {
925                    Ancestors::known(c).with_folds(&cache).fold_down(
926                        &node,
927                        skip,
928                        FoldLane::DocInBody,
929                        7,
930                        step,
931                    )
932                };
933                let first = cached(&chain);
934                let again = cached(&chain);
935                let uncached =
936                    Ancestors::known(&chain).fold_down(&node, skip, FoldLane::DocInBody, 7, step);
937                let climbed =
938                    Ancestors::unknown().fold_down(&node, skip, FoldLane::DocInBody, 7, step);
939                assert_eq!(
940                    (first, again, uncached),
941                    (climbed, climbed, climbed),
942                    "{} at depth {depth}, skip {skip}",
943                    node.kind()
944                );
945                // The same chain as a derived one holds it, split between
946                // the walk's run and the run below it at every depth, so
947                // `skip` lands either side of the seam and on it. The
948                // cached fold reads the slots the flat folds above stored,
949                // so a depth read off by one across the seam changes the
950                // answer. The crossing step folds on another lane through
951                // its `outer`, a chain cut from the split one.
952                let crossing = |state: u8, ancestor: &Node, outer: Ancestors, below: &Node| {
953                    step(state, ancestor, outer, below).wrapping_add(outer.fold_down(
954                        ancestor,
955                        0,
956                        FoldLane::DocScope,
957                        3,
958                        step,
959                    ))
960                };
961                let crossed =
962                    Ancestors::unknown().fold_down(&node, skip, FoldLane::InsideQuote, 7, crossing);
963                for split in 0..=chain.len() {
964                    let (upper, lower) = chain.split_at(split);
965                    let segmented = Ancestors {
966                        chain: Some(Chain { upper, lower }),
967                        siblings: None,
968                        folds: Some(&cache),
969                    };
970                    assert_eq!(
971                        (
972                            segmented.fold_down(&node, skip, FoldLane::DocInBody, 7, step),
973                            segmented.fold_down(&node, skip, FoldLane::InsideQuote, 7, crossing),
974                        ),
975                        (climbed, crossed),
976                        "{} at depth {depth}, skip {skip}, split {split}",
977                        node.kind()
978                    );
979                }
980                queried += 1;
981            }
982            chain.push(node);
983            let children: Vec<_> = node.children().collect();
984            stack.extend(children.into_iter().rev().map(|child| (child, depth + 1)));
985        }
986        assert!(
987            queried > 100,
988            "the fixture must exercise a real walk: {queried}"
989        );
990    }
991
992    /// A node reached through a flat chain and through a derived one
993    /// folds through the same depth slots (#1805): a state stored
994    /// through either is read back through the other, so neither refolds
995    /// an ancestor the other folded. Counted from a cache seeded by a
996    /// cold fold of the whole ancestry, so a reused slot shows as steps
997    /// not taken rather than as a count that would read zero anyway. The
998    /// step at the queried node itself depends on that node and is never
999    /// stored, so every query still calls it once; `fold_steps` counts
1000    /// only the stored ones, which is why the two counts differ by one.
1001    #[cfg(feature = "rust")]
1002    #[test]
1003    fn a_flat_and_a_derived_chain_share_the_fold_slots() {
1004        use std::cell::Cell;
1005        let tree = Tree::new::<crate::langs::RustCode>(
1006            b"mod a { mod b { fn f() { let x = (1 + 2) * 3; } } }\n",
1007        );
1008        let node = tree
1009            .get_root()
1010            .preorder()
1011            .find(|node| {
1012                node.kind() == "binary_expression"
1013                    && node
1014                        .child(0)
1015                        .is_some_and(|lhs| lhs.kind() == "integer_literal")
1016            })
1017            .expect("the fixture holds `1 + 2`");
1018        let child = node.child(0).expect("the `1`");
1019        let chain = climbed_chain(&node);
1020        let depth = chain.len();
1021        assert!(depth > 6, "the fixture must nest: {depth}");
1022        let calls = Cell::new(0_usize);
1023        let step = |state: u8, ancestor: &Node, _: Ancestors, below: &Node| {
1024            calls.set(calls.get() + 1);
1025            state
1026                .wrapping_mul(31)
1027                .wrapping_add(ancestor.kind_id().to_le_bytes()[0])
1028                .wrapping_add(below.kind_id().to_le_bytes()[0].rotate_left(3))
1029        };
1030        let lane = FoldLane::DocInBody;
1031        let at_node = Ancestors::unknown().fold_down(&node, 0, lane, 7, step);
1032        let at_child = Ancestors::unknown().fold_down(&child, 0, lane, 7, step);
1033        // A fold's answer, the steps it stored and the step calls it made.
1034        let counted = |fold: &dyn Fn() -> u8| {
1035            let (steps, before) = (fold_steps::observed(), calls.get());
1036            let answer = fold();
1037            (answer, fold_steps::observed() - steps, calls.get() - before)
1038        };
1039
1040        let cache = FoldCache::default();
1041        let walk = Ancestors::known(&chain).with_folds(&cache);
1042        assert_eq!(
1043            counted(&|| walk.fold_down(&node, 0, lane, 7, step)),
1044            (at_node, depth - 1, depth),
1045            "cold, every ancestor below the root is folded and stored"
1046        );
1047        for split in 0..=depth {
1048            let (upper, lower) = chain.split_at(split);
1049            let segmented = Ancestors {
1050                chain: Some(Chain { upper, lower }),
1051                siblings: None,
1052                folds: Some(&cache),
1053            };
1054            assert_eq!(
1055                counted(&|| segmented.fold_down(&node, 0, lane, 7, step)),
1056                (at_node, 0, 1),
1057                "split at {split}, every stored state is read back"
1058            );
1059        }
1060        let under = walk.of_children(&node);
1061        assert_eq!(
1062            counted(&|| under.get().fold_down(&child, 0, lane, 7, step)),
1063            (at_child, 1, 2),
1064            "one level down, the node's own depth is folded and stored"
1065        );
1066        let flat: Vec<Node> = chain.iter().copied().chain([node]).collect();
1067        let flat_walk = Ancestors::known(&flat).with_folds(&cache);
1068        assert_eq!(
1069            counted(&|| flat_walk.fold_down(&child, 0, lane, 7, step)),
1070            (at_child, 0, 1),
1071            "and the walk's own chain at the child reads that slot back"
1072        );
1073    }
1074
1075    /// A fold's step may fold on another lane, and that inner fold is
1076    /// memoised through the same cache: each lane is its own cell, so the
1077    /// outer fold's borrow does not block it. A step that folds on its
1078    /// *own* lane finds that lane borrowed and runs unmemoised, answering
1079    /// what the plain fold does rather than panicking on a second borrow,
1080    /// at the plain fold's cost.
1081    ///
1082    /// The inner fold counts its own steps, so memoisation is observed
1083    /// rather than inferred: walked in order, each inner fold costs one
1084    /// step per new depth, so the total stays near the node count, where
1085    /// an unmemoised inner fold costs the whole depth every time.
1086    #[cfg(feature = "rust")]
1087    #[test]
1088    fn a_step_folds_another_lane_memoised_and_its_own_lane_unmemoised() {
1089        use crate::test_support::for_each_node_with_chain;
1090        use std::cell::Cell;
1091        // Every level opens a block, so depth grows with the fixture and
1092        // an unmemoised inner fold is visibly quadratic in step count.
1093        let source = format!("fn f() {{ {} }}\n", "{ ".repeat(60) + &"} ".repeat(60));
1094        let inner_steps = Cell::new(0_usize);
1095        let inner = |state: u8, ancestor: &Node, _: Ancestors, _: &Node| {
1096            inner_steps.set(inner_steps.get() + 1);
1097            state
1098                .wrapping_mul(7)
1099                .wrapping_add(ancestor.kind_id().to_le_bytes()[0])
1100        };
1101        let outer_on = |lane: FoldLane| {
1102            move |state: u8, ancestor: &Node, outer: Ancestors, _: &Node| {
1103                state.wrapping_add(outer.fold_down(ancestor, 0, lane, 3, inner))
1104            }
1105        };
1106        let fold = |chain: &[Node], node: &Node, cache: Option<&FoldCache>, lane, inner_lane| {
1107            let ancestors = Ancestors::known(chain);
1108            let ancestors = cache.map_or(ancestors, |cache| ancestors.with_folds(cache));
1109            ancestors.fold_down(node, 0, lane, 0, outer_on(inner_lane))
1110        };
1111
1112        let cache = FoldCache::default();
1113        same_lane_reentry::allow(true);
1114        let nodes =
1115            for_each_node_with_chain::<crate::langs::RustCode>(source.as_bytes(), |node, chain| {
1116                let (other, own) = (FoldLane::DocInBody, FoldLane::BareStringClimb);
1117                assert_eq!(
1118                    fold(chain, node, Some(&cache), other, FoldLane::DocScope),
1119                    fold(chain, node, None, other, FoldLane::DocScope),
1120                    "another lane must answer what the plain fold does"
1121                );
1122                let before = inner_steps.get();
1123                let own_lane = fold(chain, node, Some(&cache), own, own);
1124                let own_steps = inner_steps.get() - before;
1125                assert_eq!(
1126                    own_lane,
1127                    fold(chain, node, None, own, own),
1128                    "its own lane must answer what the plain fold does"
1129                );
1130                // One plain fold of the prefix per query: `inner` folds
1131                // its own lane once, at the node, and re-enters nowhere.
1132                let depth = chain.len();
1133                assert!(
1134                    own_steps <= depth * (depth + 1) / 2,
1135                    "its own lane must cost one plain fold of the prefix"
1136                );
1137            });
1138        same_lane_reentry::allow(false);
1139        assert!(nodes > 200, "the fixture must nest deeply: {nodes}");
1140
1141        // The other-lane fold alone on a fresh cache, counting only its
1142        // inner steps.
1143        let cache = FoldCache::default();
1144        inner_steps.set(0);
1145        for_each_node_with_chain::<crate::langs::RustCode>(source.as_bytes(), |node, chain| {
1146            fold(
1147                chain,
1148                node,
1149                Some(&cache),
1150                FoldLane::DocInBody,
1151                FoldLane::DocScope,
1152            );
1153        });
1154        // Memoised, the inner folds cost a small constant per node;
1155        // unmemoised, each outer step's inner fold runs the whole prefix,
1156        // `Σ depth` along the spine — quadratic in it, far past this
1157        // bound.
1158        assert!(
1159            inner_steps.get() <= 4 * nodes,
1160            "the other lane is not memoised"
1161        );
1162    }
1163
1164    /// A recorded wide parent answers every child's siblings, and its
1165    /// previous sibling, from the recorded array, and answers exactly
1166    /// what the raw walk does on either side of it — the `ERROR` whose
1167    /// flat array made the seek `O(index)` (#1584). A node that is no
1168    /// child of it gets nothing.
1169    #[cfg(feature = "perl")]
1170    #[test]
1171    fn siblings_of_a_recorded_wide_parent_match_the_child_walk() {
1172        let tree = flat_error();
1173        let root = tree.get_root();
1174        assert!(root.is_error(), "the fixture's tail must fail to parse");
1175        assert!(root.child_count() > WIDE_PARENT, "the ERROR must be wide");
1176
1177        let mut cache = SiblingCache::default();
1178        cache.record(&root, 0, root.children());
1179        let chain = [root];
1180        let ancestors = Ancestors::known(&chain).with_siblings(&cache);
1181        let all = raw_children(&root);
1182
1183        let (mut observed, mut expected) = (Vec::new(), Vec::new());
1184        for (index, child) in root.children().enumerate() {
1185            let recorded_index = match ancestors.lookup(&child) {
1186                Lookup::Wide(_, index) => index,
1187                Lookup::Narrow(_) => None,
1188            };
1189            observed.push((
1190                index,
1191                recorded_index,
1192                ids(ancestors.siblings_after(&child)),
1193                ids(ancestors.siblings_before(&child)),
1194                ancestors.previous_sibling(&child).map(|node| node.id()),
1195            ));
1196            expected.push((
1197                index,
1198                Some(index),
1199                all[index + 1..].to_vec(),
1200                all[..index].iter().rev().copied().collect(),
1201                index.checked_sub(1).map(|previous| all[previous]),
1202            ));
1203        }
1204        assert_eq!(observed, expected);
1205
1206        // A grandchild starting where its parent does, so the search
1207        // reaches it and only the id comparison turns it away.
1208        let stray = root
1209            .children()
1210            .find_map(|child| {
1211                child
1212                    .child(0)
1213                    .filter(|g| g.start_byte() == child.start_byte())
1214            })
1215            .expect("the fixture nests a node at its parent's start");
1216        assert!(matches!(ancestors.lookup(&stray), Lookup::Wide(_, None)));
1217        assert_eq!(ancestors.siblings_after(&stray).count(), 0);
1218        assert_eq!(ancestors.siblings_before(&stray).count(), 0);
1219        // `previous_sibling` falls back to the node's own lookup instead,
1220        // which finds a stray's real previous sibling: `$b`'s is the `&&`
1221        // of its own chain, not anything in the root.
1222        let operand = root
1223            .children()
1224            .find_map(|child| child.child(2))
1225            .expect("the fixture holds `$a && $b`");
1226        let previous = ancestors
1227            .previous_sibling(&operand)
1228            .expect("the fallback finds the `&&`");
1229        assert_eq!(previous.kind(), "&&");
1230    }
1231
1232    /// A narrow parent is never recorded, and its siblings come from
1233    /// the seek — with or without a cache lent.
1234    #[cfg(feature = "perl")]
1235    #[test]
1236    fn a_narrow_parent_is_sought_not_recorded() {
1237        let tree = flat_error();
1238        let root = tree.get_root();
1239        let chain = [root];
1240        let narrow = root
1241            .children()
1242            .find(|child| (2..=WIDE_PARENT).contains(&child.child_count()))
1243            .expect("the fixture holds a narrow node with several children");
1244        let mut cache = SiblingCache::default();
1245        cache.record(&narrow, 1, narrow.children());
1246        assert!(cache.is_empty(), "a narrow node must not be recorded");
1247
1248        let narrow_chain = [root, narrow];
1249        let all = raw_children(&narrow);
1250        for ancestors in [
1251            Ancestors::known(&narrow_chain).with_siblings(&cache),
1252            Ancestors::known(&narrow_chain),
1253        ] {
1254            let first = narrow.child(0).expect("narrow node has children");
1255            assert!(matches!(ancestors.lookup(&first), Lookup::Narrow(Some(_))));
1256            assert_eq!(ids(ancestors.siblings_after(&first)), all[1..]);
1257        }
1258        // Without a cache a wide parent is sought too.
1259        let first = root.child(0).expect("root has children");
1260        assert!(matches!(
1261            Ancestors::known(&chain).lookup(&first),
1262            Lookup::Narrow(Some(_))
1263        ));
1264    }
1265
1266    /// A walk that lends a cache but did not record a wide node on its
1267    /// chain would answer correctly and quadratically; the assertion is
1268    /// what makes that visible to every test that walks one.
1269    #[cfg(all(feature = "perl", debug_assertions))]
1270    #[test]
1271    #[should_panic(expected = "must record every wide node on its chain")]
1272    fn an_unrecorded_wide_parent_trips_the_walk_assertion() {
1273        let tree = flat_error();
1274        let root = tree.get_root();
1275        let cache = SiblingCache::default();
1276        let chain = [root];
1277        let first = root.child(0).expect("root has children");
1278        let _ = Ancestors::known(&chain)
1279            .with_siblings(&cache)
1280            .lookup(&first);
1281    }
1282
1283    /// A walk records every child of a wide node. A lookup indexes into
1284    /// the record, so a batch that drops a child shifts each answer
1285    /// after it rather than slowing it, and no cost probe shows that
1286    /// (#1871). The recording walks pass what `children_with` yields,
1287    /// whole; one that came to filter at the push would trip this on its
1288    /// first wide node. The setup cannot raise the message: it parses
1289    /// and builds an empty record.
1290    #[cfg(all(feature = "perl", debug_assertions))]
1291    #[test]
1292    #[should_panic(expected = "a walk must record every child of a wide ERROR")]
1293    fn recording_a_short_batch_is_caught() {
1294        let tree = flat_error();
1295        let root = tree.get_root();
1296        let mut cache = SiblingCache::default();
1297        cache.record(&root, 0, root.children().skip(1));
1298    }
1299
1300    /// And a batch that holds more than the node's children, as a slice
1301    /// of the walk's stack cut one entry too early would.
1302    #[cfg(all(feature = "perl", debug_assertions))]
1303    #[test]
1304    #[should_panic(expected = "a walk must record every child of a wide ERROR")]
1305    fn recording_a_padded_batch_is_caught() {
1306        let tree = flat_error();
1307        let root = tree.get_root();
1308        let mut cache = SiblingCache::default();
1309        cache.record(&root, 0, std::iter::once(root).chain(root.children()));
1310    }
1311
1312    // The walk's own chain for `node`, built by each constructor of a walk
1313    // that records no siblings (#1601).
1314    #[cfg(feature = "perl")]
1315    fn unrecorded_walks<'t, 'c>(
1316        chain: &'c [Node<'t>],
1317        node: &Node<'t>,
1318        folds: &'c FoldCache,
1319    ) -> [(&'static str, Ancestors<'t, 'c>); 2] {
1320        [
1321            (
1322                "for_walk_chain_only",
1323                Ancestors::for_walk_chain_only(chain, node),
1324            ),
1325            (
1326                "for_walk_without_siblings",
1327                Ancestors::for_walk_without_siblings(chain, node, folds),
1328            ),
1329        ]
1330    }
1331
1332    // How many siblings follow `target`, an ancestor of `node`, asked
1333    // through the `outer` chain `fold_down` hands its step at `target`.
1334    #[cfg(feature = "perl")]
1335    fn siblings_after_through_fold<'t>(
1336        walk: Ancestors<'t, '_>,
1337        node: &Node<'t>,
1338        target: &Node<'t>,
1339    ) -> usize {
1340        let step = |state, ancestor: &Node<'t>, outer: Ancestors<'t, '_>, _: &Node<'t>| {
1341            if ancestor.id() == target.id() {
1342                u8::try_from(outer.siblings_after(ancestor).count()).unwrap_or(u8::MAX)
1343            } else {
1344                state
1345            }
1346        };
1347        usize::from(walk.fold_down(node, 0, FoldLane::DocInBody, 0, step))
1348    }
1349
1350    // Asserts that `ask` panics with the walk assertion of `lookup`.
1351    fn assert_trips_the_walk_assertion(label: &str, ask: impl FnOnce() -> usize) {
1352        let message = match catch_unwind(AssertUnwindSafe(ask)) {
1353            Ok(count) => panic!("{label}: no assertion, {count} siblings"),
1354            Err(payload) => payload
1355                .downcast::<String>()
1356                .expect("a formatted panic message"),
1357        };
1358        assert!(
1359            message.contains("must record every wide node on its chain"),
1360            "{label}: {message}"
1361        );
1362    }
1363
1364    /// The check above can fail, in both of its ways: it rejects an ask
1365    /// that returns, and an ask that panics with another message. The
1366    /// two rejection tests below rest on it, and would pass for a check
1367    /// that accepted either. The control asks parse nothing, so this
1368    /// runs in every build.
1369    #[test]
1370    fn the_walk_assertion_check_rejects_a_quiet_ask_and_another_panic() {
1371        let rejection = |ask: fn() -> usize| {
1372            *catch_unwind(|| assert_trips_the_walk_assertion("control", ask))
1373                .expect_err("the check must reject this ask")
1374                .downcast::<String>()
1375                .expect("a formatted panic message")
1376        };
1377        assert_eq!(rejection(|| 0), "control: no assertion, 0 siblings");
1378        // A `String` payload, as a formatted assertion's is.
1379        let another = rejection(|| std::panic::panic_any(String::from("another panic")));
1380        assert_eq!(another, "control: another panic");
1381    }
1382
1383    /// A walk that records no siblings cannot ask for one under a wide
1384    /// parent: the walk assertion fires through each constructor that
1385    /// says so, as it does for a walk that skipped a node (#1601). Each
1386    /// ask runs on its own, so one constructor that lent no record — and
1387    /// so sought quietly — fails here however the other behaves.
1388    #[cfg(all(feature = "perl", debug_assertions))]
1389    #[test]
1390    fn a_walk_that_records_no_siblings_cannot_ask_under_a_wide_parent() {
1391        let tree = flat_error();
1392        let root = tree.get_root();
1393        assert!(root.child_count() > WIDE_PARENT, "the ERROR must be wide");
1394        let chain = [root];
1395        let first = root.child(0).expect("root has children");
1396        let folds = FoldCache::default();
1397        for (name, walk) in unrecorded_walks(&chain, &first, &folds) {
1398            assert_trips_the_walk_assertion(name, || walk.siblings_after(&first).count());
1399        }
1400    }
1401
1402    /// The record travels with the chains a predicate derives from the
1403    /// walk's own: an ancestor's chain from [`Ancestors::iter`] and the
1404    /// `outer` chain a fold step is handed are the walk's chains too, so
1405    /// a sibling asked through either under a wide parent fires the walk
1406    /// assertion. Dropping the record from `AncestorIter::next` or from
1407    /// `fold_down`'s `outer` fails the matching ask (#1601).
1408    #[cfg(all(feature = "perl", debug_assertions))]
1409    #[test]
1410    fn an_ancestor_or_fold_chain_of_such_a_walk_cannot_ask_either() {
1411        let tree = flat_error();
1412        let root = tree.get_root();
1413        assert!(root.child_count() > WIDE_PARENT, "the ERROR must be wide");
1414        let parent = root
1415            .children()
1416            .find(|child| child.child_count() > 0)
1417            .expect("the fixture holds a node with children");
1418        let leaf = parent.child(0).expect("it has a child");
1419        let chain = [root, parent];
1420        let folds = FoldCache::default();
1421        for (name, walk) in unrecorded_walks(&chain, &leaf, &folds) {
1422            let (ancestor, above) = walk.iter(&leaf).next().expect("leaf has a parent");
1423            assert_eq!(ancestor.id(), parent.id());
1424            assert_trips_the_walk_assertion(&format!("{name} through iter"), || {
1425                above.siblings_after(&ancestor).count()
1426            });
1427            assert_trips_the_walk_assertion(&format!("{name} through a fold"), || {
1428                siblings_after_through_fold(walk, &leaf, &parent)
1429            });
1430        }
1431    }
1432
1433    /// Under a narrow parent the same walks ask freely: the seek is a
1434    /// short scan, so the rule bars only the wide one. Each ask takes the
1435    /// uncached path once and is counted, through the walk's own chain,
1436    /// an iterated ancestor's and a fold step's `outer`.
1437    #[cfg(feature = "perl")]
1438    #[test]
1439    fn a_walk_that_records_no_siblings_asks_freely_under_a_narrow_parent() {
1440        let tree = flat_error();
1441        let root = tree.get_root();
1442        let parent = root
1443            .children()
1444            .find(|child| {
1445                (3..=WIDE_PARENT).contains(&child.child_count())
1446                    && child.child(0).is_some_and(|first| first.child_count() > 0)
1447            })
1448            .expect("the fixture holds a narrow node whose first child has children");
1449        let first = parent.child(0).expect("narrow node has children");
1450        let second = parent.child(1).expect("and at least three of them");
1451        let grandchild = first.child(0).expect("its first child has children");
1452        let chain = [root, parent];
1453        let below_first = [root, parent, first];
1454        let folds = FoldCache::default();
1455        let all = raw_children(&parent);
1456        for (name, walk) in unrecorded_walks(&chain, &first, &folds) {
1457            let before = sibling_seeks::observed();
1458            assert_eq!(ids(walk.siblings_after(&first)), all[1..], "{name}");
1459            assert_eq!(
1460                walk.previous_sibling(&second).map(|node| node.id()),
1461                Some(all[0]),
1462                "{name}"
1463            );
1464            // expected: 2, one uncached lookup per ask above.
1465            assert_eq!(sibling_seeks::observed() - before, 2, "{name}");
1466        }
1467        for (name, walk) in unrecorded_walks(&below_first, &grandchild, &folds) {
1468            let before = sibling_seeks::observed();
1469            let (_, above) = walk.iter(&grandchild).next().expect("it has a parent");
1470            assert_eq!(ids(above.siblings_after(&first)), all[1..], "{name}");
1471            let folded = siblings_after_through_fold(walk, &grandchild, &first);
1472            assert_eq!(folded, all.len() - 1, "{name}");
1473            // expected: 2, the iterated ancestor's ask and the fold's.
1474            assert_eq!(sibling_seeks::observed() - before, 2, "{name}");
1475        }
1476    }
1477
1478    /// A chain that is not a walk's own — derived below it, re-rooted,
1479    /// or foreign — seeks a wide parent quietly: no walk recorded the
1480    /// nodes below its own chain, so there is no record to require. Each
1481    /// of `siblings_before` and `siblings_after` takes the uncached path
1482    /// once per ask; `previous_sibling` stays loud there (#1785), so it
1483    /// is not asked.
1484    #[cfg(feature = "perl")]
1485    #[test]
1486    fn a_chain_that_is_not_a_walk_s_own_seeks_a_wide_parent() {
1487        let tree = flat_error();
1488        let root = tree.get_root();
1489        assert!(root.child_count() > WIDE_PARENT, "the ERROR must be wide");
1490        let all = raw_children(&root);
1491        let index = all.len() / 2;
1492        let child = root.child(index).expect("the middle child");
1493        let chain = [root];
1494        let folds = FoldCache::default();
1495        let siblings = SiblingCache::default();
1496        let walk = Ancestors::for_walk(&[], &root, &folds, &siblings);
1497        let held = walk.of_children(&root);
1498        let derived: [(&str, Ancestors<'_, '_>); 3] = [
1499            ("known", Ancestors::known(&chain)),
1500            ("below", walk.below(&chain)),
1501            ("of_children", held.get()),
1502        ];
1503        let expected_before: Vec<_> = all[..index].iter().rev().copied().collect();
1504        for (name, ancestors) in derived {
1505            let before = sibling_seeks::observed();
1506            assert_eq!(
1507                ids(ancestors.siblings_after(&child)),
1508                all[index + 1..],
1509                "{name}"
1510            );
1511            assert_eq!(
1512                ids(ancestors.siblings_before(&child)),
1513                expected_before,
1514                "{name}"
1515            );
1516            // expected: 2, one uncached lookup per ask above.
1517            assert_eq!(sibling_seeks::observed() - before, 2, "{name}");
1518        }
1519        let before = sibling_seeks::observed();
1520        assert_eq!(
1521            Ancestors::unknown().siblings_after(&child).count(),
1522            all.len() - index - 1
1523        );
1524        assert_eq!(
1525            sibling_seeks::observed(),
1526            before,
1527            "a chainless lookup is not counted"
1528        );
1529    }
1530
1531    /// The binary search finds every child at its index, including a
1532    /// zero-width one: recovery inserts it at the byte its successor
1533    /// starts at, so only the id tells the two apart. The Kotlin
1534    /// fixture's `vararg: Int` holds one.
1535    #[cfg(feature = "kotlin")]
1536    #[test]
1537    fn position_by_start_finds_a_zero_width_child() {
1538        let tree = Tree::new::<crate::langs::KotlinCode>(b"fun f(vararg: Int, b: Int) {}");
1539        let mut zero_width = 0;
1540        for node in tree.get_root().preorder() {
1541            let children: Vec<_> = node.children().collect();
1542            for (index, child) in children.iter().enumerate() {
1543                zero_width += usize::from(child.start_byte() == child.end_byte());
1544                assert_eq!(position_by_start(&children, child), Some(index));
1545            }
1546        }
1547        assert!(
1548            zero_width > 0,
1549            "fixture must hold an inserted zero-width child"
1550        );
1551    }
1552
1553    /// A chain yielded by [`Ancestors::iter`] carries the walk's
1554    /// [`FoldCache`], so a memo stored through the node's own chain is
1555    /// read back through an ancestor's. The Tcl-family role question is
1556    /// asked of a braced word's *parent* through this iterator, and an
1557    /// iterator that dropped the cache left it unmemoised on every walk
1558    /// that lent one (#1686). Restoring `folds: None` in
1559    /// `AncestorIter::next` fails the `expect` on the iterated ancestor's
1560    /// memo.
1561    #[cfg(feature = "rust")]
1562    #[test]
1563    fn an_iterated_ancestor_keeps_the_walk_s_memo() {
1564        let tree = Tree::new::<crate::langs::RustCode>(b"fn f() { g(1); }\n");
1565        let root = tree.get_root();
1566        // Root first, then the `function_item`, its block, and the
1567        // expression statement in it: the parent of `g(1)`.
1568        let mut chain = vec![root];
1569        for kind in ["function_item", "block", "expression_statement"] {
1570            let last = *chain.last().expect("the chain starts non-empty");
1571            let child = last
1572                .children()
1573                .find(|child| child.kind() == kind)
1574                .unwrap_or_else(|| panic!("the fixture nests a {kind}"));
1575            chain.push(child);
1576        }
1577        let leaf = chain
1578            .last()
1579            .expect("the chain has a parent")
1580            .child(0)
1581            .expect("the statement holds the call");
1582        assert_eq!(leaf.kind(), "call_expression");
1583
1584        let cache = FoldCache::default();
1585        let walk = Ancestors::known(&chain).with_folds(&cache);
1586        walk.node_memo(MemoQuestion::ArgumentSlotsReadable)
1587            .expect("the chain lent a cache")
1588            .set(&leaf, true);
1589        assert!(
1590            Ancestors::known(&chain)
1591                .node_memo(MemoQuestion::ArgumentSlotsReadable)
1592                .is_none(),
1593            "a chain lent no cache has no memo"
1594        );
1595
1596        let (_, above) = walk.iter(&leaf).next().expect("the leaf has a parent");
1597        let memo = above
1598            .node_memo(MemoQuestion::ArgumentSlotsReadable)
1599            .expect("an iterated ancestor's chain keeps the lent cache");
1600        assert_eq!(memo.get(&leaf), Some(true));
1601
1602        // The other derivations: a chain extended *downward* for a node
1603        // the walk has not reached, and one re-rooted with `below`, read
1604        // the same memo. Rebuilding with `Ancestors::known` instead
1605        // answers `None`, which is what `error_holds_target` did before
1606        // #1686.
1607        let under = walk.of_children(&leaf);
1608        let derived = under.get();
1609        assert_eq!(derived.depth(), Some(chain.len() + 1));
1610        let memo = derived
1611            .node_memo(MemoQuestion::ArgumentSlotsReadable)
1612            .expect("a chain derived with `of_children` keeps the lent cache");
1613        assert_eq!(memo.get(&leaf), Some(true));
1614        let memo = walk
1615            .below(&chain[..1])
1616            .node_memo(MemoQuestion::ArgumentSlotsReadable)
1617            .expect("a chain re-rooted with `below` keeps the lent cache");
1618        assert_eq!(memo.get(&leaf), Some(true));
1619    }
1620
1621    /// The word slot serves the node the walk is visiting and no other
1622    /// (#1737). Through a chain built with `for_walk` for `a`, the first
1623    /// ask about `a` computes and every later one is served — across
1624    /// asks about another node `b` through the walk's own chain, a chain
1625    /// derived from it with `of_children`, `below` and `iter`, and the
1626    /// fold-free chain `fold_down` hands its step, each of which computes
1627    /// `b`'s answer and stores nothing. Restoring the last-node-asked
1628    /// slot, which stored every ask, fails at the second ask about `a`:
1629    /// the ask about `b` in between evicted it. A chain lent the cache
1630    /// without a visit computes every ask, and a later `for_walk` for `b`
1631    /// retires `a`'s entry. Both walk constructors record the visit, so
1632    /// the same sequence runs through each (#1601).
1633    #[cfg(feature = "rust")]
1634    #[test]
1635    fn the_word_slot_serves_only_the_visited_node() {
1636        let tree = Tree::new::<crate::langs::RustCode>(b"fn f() { g(1); }\n");
1637        let root = tree.get_root();
1638        let a = root.child(0).expect("the fn item");
1639        let body = a
1640            .children()
1641            .find(|child| child.kind() == "block")
1642            .expect("the body");
1643        let b = body.child(1).expect("the call statement");
1644        assert_ne!(a.id(), b.id());
1645        word_slot_serves_only_the_visited_node(root, a, body, b, Some(&SiblingCache::default()));
1646        word_slot_serves_only_the_visited_node(root, a, body, b, None);
1647    }
1648
1649    // The walk's own chain for `node` through either walk constructor:
1650    // `for_walk` lending `siblings`, or `for_walk_without_siblings`.
1651    #[cfg(feature = "rust")]
1652    fn either_walk<'t, 'c>(
1653        chain: &'c [Node<'t>],
1654        node: &Node<'t>,
1655        folds: &'c FoldCache,
1656        siblings: Option<&'c SiblingCache<'t>>,
1657    ) -> Ancestors<'t, 'c> {
1658        match siblings {
1659            Some(siblings) => Ancestors::for_walk(chain, node, folds, siblings),
1660            None => Ancestors::for_walk_without_siblings(chain, node, folds),
1661        }
1662    }
1663
1664    // `the_word_slot_serves_only_the_visited_node` through one of the
1665    // two walk constructors.
1666    #[cfg(feature = "rust")]
1667    fn word_slot_serves_only_the_visited_node<'t>(
1668        root: Node<'t>,
1669        a: Node<'t>,
1670        body: Node<'t>,
1671        b: Node<'t>,
1672        siblings: Option<&SiblingCache<'t>>,
1673    ) {
1674        use std::cell::Cell;
1675        let runs = Cell::new(0_usize);
1676        let computes = |answer: u8| {
1677            let runs = &runs;
1678            move || {
1679                runs.set(runs.get() + 1);
1680                answer
1681            }
1682        };
1683        let cache = FoldCache::default();
1684        let chain = [root];
1685        let walk = either_walk(&chain, &a, &cache, siblings);
1686        let slot = WordSlot::ElixirCallTarget;
1687
1688        assert_eq!(walk.classified(slot, &a, computes(1)), 1);
1689        assert_eq!(runs.get(), 1, "the first ask computes");
1690        assert_eq!(walk.classified(slot, &a, computes(9)), 1);
1691        assert_eq!(runs.get(), 1, "the second ask is served");
1692
1693        assert_eq!(walk.classified(slot, &b, computes(2)), 2);
1694        assert_eq!(walk.classified(slot, &b, computes(2)), 2);
1695        assert_eq!(
1696            runs.get(),
1697            3,
1698            "an ask about another node computes every time"
1699        );
1700        assert_eq!(walk.classified(slot, &a, computes(9)), 1);
1701        assert_eq!(
1702            runs.get(),
1703            3,
1704            "and does not evict the visited node's answer"
1705        );
1706
1707        let under = walk.of_children(&a);
1708        assert_eq!(under.get().classified(slot, &b, computes(2)), 2);
1709        let replaced = [root, a];
1710        assert_eq!(walk.below(&replaced).classified(slot, &b, computes(2)), 2);
1711        let (_, above) = walk.iter(&b).next().expect("b has a parent");
1712        assert_eq!(above.classified(slot, &b, computes(2)), 2);
1713        let folded = walk.fold_down(&a, 0, FoldLane::DocInBody, 0, |_, _, outer, _| {
1714            outer.classified(slot, &b, computes(2))
1715        });
1716        assert_eq!(folded, 2);
1717        assert_eq!(runs.get(), 7, "each derived chain's ask computes");
1718        assert_eq!(walk.classified(slot, &a, computes(9)), 1);
1719        assert_eq!(runs.get(), 7, "and none of them evicts");
1720        assert_eq!(under.get().classified(slot, &a, computes(9)), 1);
1721        assert_eq!(runs.get(), 7, "a derived chain serves the visited node too");
1722
1723        let never_visited = FoldCache::default();
1724        let unvisited = Ancestors::known(&chain).with_folds(&never_visited);
1725        assert_eq!(unvisited.classified(slot, &a, computes(1)), 1);
1726        assert_eq!(unvisited.classified(slot, &a, computes(1)), 1);
1727        assert_eq!(
1728            runs.get(),
1729            9,
1730            "a cache lent without a visit computes every ask"
1731        );
1732
1733        let chain_b = [root, a, body];
1734        let walk_b = either_walk(&chain_b, &b, &cache, siblings);
1735        assert_eq!(walk_b.classified(slot, &b, computes(2)), 2);
1736        assert_eq!(walk_b.classified(slot, &b, computes(9)), 2);
1737        assert_eq!(
1738            runs.get(),
1739            10,
1740            "the new visit's first ask computes, the next is served"
1741        );
1742        assert_eq!(walk_b.classified(slot, &a, computes(1)), 1);
1743        assert_eq!(runs.get(), 11, "the retired node is computed again");
1744    }
1745
1746    /// `of_children` hands a body's members the chain that is their own:
1747    /// `parent` on a member is the body, where the body's chain would
1748    /// name the body's parent instead — the shape `npa` / `npm` ask a
1749    /// row about every member under. The derived chain keeps the walk's
1750    /// fold cache, as `below` does, and without a known chain it climbs.
1751    #[cfg(feature = "rust")]
1752    #[test]
1753    fn of_children_names_the_body_as_each_member_s_parent() {
1754        let tree = Tree::new::<crate::langs::RustCode>(b"struct S { a: i32, b: i32 }\n");
1755        let root = tree.get_root();
1756        let item = root.child(0).expect("the struct item");
1757        let body = item
1758            .children()
1759            .find(|child| child.kind() == "field_declaration_list")
1760            .expect("the field list");
1761        let field = body
1762            .children()
1763            .find(|child| child.kind() == "field_declaration")
1764            .expect("a field");
1765
1766        let chain = [root, item];
1767        let cache = FoldCache::default();
1768        let walk = Ancestors::known(&chain).with_folds(&cache);
1769        assert_eq!(
1770            walk.parent(&body).map(|p| p.id()),
1771            Some(item.id()),
1772            "the body's own chain names the item"
1773        );
1774        let under = walk.of_children(&body);
1775        let members = under.get();
1776        assert_eq!(
1777            members.parent(&field).map(|p| p.id()),
1778            Some(body.id()),
1779            "a member's chain names the body"
1780        );
1781        assert_eq!(members.depth(), Some(3), "root, item, body");
1782        assert!(
1783            members.memoises_folds(),
1784            "the derived chain keeps the walk's fold cache"
1785        );
1786        assert_eq!(
1787            Ancestors::unknown()
1788                .of_children(&body)
1789                .get()
1790                .parent(&field)
1791                .map(|p| p.id()),
1792            Some(body.id()),
1793            "without a chain the derived one climbs to the same parent"
1794        );
1795    }
1796
1797    /// A chain derived with `of_children` borrows the walk's chain in
1798    /// place — the same slice, not a copy of it — and owns only what it
1799    /// adds: the body, and below a derived chain the levels that one
1800    /// added. A copy of the walk's chain per container made `n` nested
1801    /// containers cost `Σ depth` (#1805); the scaling probes price that
1802    /// out of band, and this is the per-change guard. Reinstating the
1803    /// copy fails the first assertion. A root's children derive from the
1804    /// empty chain the walk holds there, and a leaf's from its own like
1805    /// any other node, describing nothing.
1806    #[cfg(feature = "rust")]
1807    #[test]
1808    fn of_children_borrows_the_walk_s_chain_and_owns_only_what_it_adds() {
1809        // Where a slice starts and how long it is: equal for two slices
1810        // only when one is the other, not a copy of it.
1811        fn at(nodes: &[Node]) -> (usize, usize) {
1812            (nodes.as_ptr().addr(), nodes.len())
1813        }
1814        // A derived chain's borrowed run, and the ids of the run it owns.
1815        fn view(under: &ChildAncestors<'_, '_>) -> ((usize, usize), Vec<usize>) {
1816            let chain = under
1817                .get()
1818                .chain
1819                .expect("a known chain derives a known one");
1820            (at(chain.upper), chain.lower.iter().map(Node::id).collect())
1821        }
1822        let tree = Tree::new::<crate::langs::RustCode>(b"struct S { a: (i32, u8) }\n");
1823        let root = tree.get_root();
1824        let item = root.child(0).expect("the struct item");
1825        let body = item
1826            .children()
1827            .find(|child| child.kind() == "field_declaration_list")
1828            .expect("the field list");
1829        let field = body
1830            .children()
1831            .find(|child| child.kind() == "field_declaration")
1832            .expect("a field");
1833
1834        let chain = [root, item];
1835        let walk = Ancestors::known(&chain);
1836        let under = walk.of_children(&body);
1837        assert_eq!(
1838            view(&under),
1839            (at(&chain), vec![body.id()]),
1840            "the walk's chain is borrowed in place and only the body is owned"
1841        );
1842        let nested = under.get().of_children(&field);
1843        assert_eq!(
1844            view(&nested),
1845            (at(&chain), vec![body.id(), field.id()]),
1846            "a nested derivation still borrows the walk's chain, copying what the first added"
1847        );
1848
1849        let empty: [Node; 0] = [];
1850        let at_root = Ancestors::known(&empty).of_children(&root);
1851        assert_eq!(view(&at_root), (at(&empty), vec![root.id()]));
1852        assert_eq!(at_root.get().parent(&item).map(|p| p.id()), Some(root.id()));
1853        let leaf = item.child(0).expect("the `struct` keyword");
1854        assert_eq!(leaf.child_count(), 0, "the keyword is a leaf");
1855        let under_leaf = walk.of_children(&leaf);
1856        assert_eq!(view(&under_leaf), (at(&chain), vec![leaf.id()]));
1857    }
1858
1859    /// A derived chain carries the walk's fold cache, one level down and
1860    /// two — its node memos, its folds and the visited node's word slot —
1861    /// and drops the walk's sibling cache, which never recorded the
1862    /// nodes it describes. The drop holds on the chains `iter` yields
1863    /// even once they climb back into the walk's own chain, where the
1864    /// cache did record the parent: those siblings are sought too. The
1865    /// root is the one wide parent, so a lookup through the walk's own
1866    /// chain reads the recorded array.
1867    #[cfg(feature = "rust")]
1868    #[test]
1869    fn a_derived_chain_keeps_the_fold_cache_and_drops_the_sibling_cache() {
1870        use std::cell::Cell;
1871        let source = "fn a() { b(); }\n".repeat(WIDE_PARENT + 1);
1872        let tree = Tree::new::<crate::langs::RustCode>(source.as_bytes());
1873        let root = tree.get_root();
1874        let member = root.child(0).expect("the first fn item");
1875        let block = member
1876            .children()
1877            .find(|child| child.kind() == "block")
1878            .expect("its body");
1879        let statement = block.child(1).expect("the call statement");
1880        let mut siblings = SiblingCache::default();
1881        siblings.record(&root, 0, root.children());
1882        let folds = FoldCache::default();
1883        let chain = [root];
1884        let walk = Ancestors::for_walk(&chain, &member, &folds, &siblings);
1885        assert!(
1886            matches!(walk.lookup(&member), Lookup::Wide(_, Some(0))),
1887            "the walk's own chain reads the recorded root"
1888        );
1889        let question = MemoQuestion::ArgumentSlotsReadable;
1890        walk.node_memo(question)
1891            .expect("the walk lent a cache")
1892            .set(&member, true);
1893        let runs = Cell::new(0_usize);
1894        let classify = || {
1895            runs.set(runs.get() + 1);
1896            4
1897        };
1898        assert_eq!(
1899            walk.classified(WordSlot::TclCommandWord, &member, classify),
1900            4
1901        );
1902
1903        let under = walk.of_children(&member);
1904        let nested = under.get().of_children(&block);
1905        for (depth, derived, child) in [(2, under.get(), block), (3, nested.get(), statement)] {
1906            assert_eq!(derived.depth(), Some(depth));
1907            assert!(derived.memoises_folds(), "at depth {depth}: folds");
1908            assert_eq!(
1909                derived
1910                    .node_memo(question)
1911                    .and_then(|memo| memo.get(&member)),
1912                Some(true),
1913                "at depth {depth}: the walk's node memo"
1914            );
1915            assert_eq!(
1916                derived.classified(WordSlot::TclCommandWord, &member, classify),
1917                4
1918            );
1919            assert!(
1920                derived.siblings.is_none(),
1921                "at depth {depth}: no sibling cache"
1922            );
1923            let (_, above) = derived
1924                .iter(&child)
1925                .find(|(ancestor, _)| ancestor.id() == member.id())
1926                .expect("the member is on every derived chain");
1927            assert_eq!(above.depth(), Some(1), "the walk's own chain, root alone");
1928            assert!(
1929                matches!(above.lookup(&member), Lookup::Narrow(Some(_))),
1930                "at depth {depth}: iterating back into the walk's chain regains no sibling cache"
1931            );
1932        }
1933        assert_eq!(
1934            runs.get(),
1935            1,
1936            "the visited node's word slot served every derived ask"
1937        );
1938    }
1939
1940    /// `descend` / `ascend` move a held chain into a child and back
1941    /// (#1401): under the child, the child's children read their whole
1942    /// ancestry from it, one more depth down; after ascending, the
1943    /// body's own members do again. The descent goes through every level
1944    /// the tree has, the `if`'s `expression_statement` included: a chain
1945    /// that skipped one passed the containment check `descend` makes and
1946    /// the depth-and-parent assertions this made before. A holder derived
1947    /// from a moved holder moves the same way within a floor of its own,
1948    /// what it inherited plus its node, and is back on the ancestry it
1949    /// was built with after one ascend: a floor counted too high would
1950    /// refuse that pop. Without a known chain there is no chain to move,
1951    /// so the depth stays unknown and the answers keep climbing. The
1952    /// floor's debug assertions are `ascending_past_the_floor_is_caught`
1953    /// and `ascending_past_an_inherited_floor_is_caught`; the
1954    /// release-build clamp behind them runs only where those assertions
1955    /// are compiled out, so no test in the gate observes it.
1956    #[cfg(feature = "rust")]
1957    #[test]
1958    fn descend_and_ascend_move_the_held_chain_within_its_floor() {
1959        let tree = Tree::new::<crate::langs::RustCode>(b"fn f() { if a { g(); } }\n");
1960        let root = tree.get_root();
1961        let item = root.child(0).expect("the fn item");
1962        let body = item
1963            .children()
1964            .find(|child| child.kind() == "block")
1965            .expect("the body");
1966        let statement = body
1967            .children()
1968            .find(|child| child.kind() == "expression_statement")
1969            .expect("the if's statement");
1970        let conditional = statement.child(0).expect("the if");
1971        let consequence = conditional
1972            .children()
1973            .find(|child| child.kind() == "block")
1974            .expect("the consequence");
1975        let call = consequence
1976            .children()
1977            .find(|child| child.kind() == "expression_statement")
1978            .expect("the call statement");
1979
1980        let chain = [root, item];
1981        let mut under = Ancestors::known(&chain).of_children(&body);
1982        assert_eq!(under.get().depth(), Some(3), "root, item, body");
1983
1984        under.descend(&statement);
1985        under.descend(&conditional);
1986        under.descend(&consequence);
1987        assert_describes(under.get(), &call);
1988
1989        under.ascend();
1990        under.ascend();
1991        under.ascend();
1992        assert_eq!(under.get().depth(), Some(3), "back at the body");
1993        assert_describes(under.get(), &statement);
1994
1995        let mut outer = Ancestors::known(&chain[..1]).of_children(&item);
1996        outer.descend(&body);
1997        let mut inner = outer.get().of_children(&statement);
1998        inner.descend(&conditional);
1999        assert_describes(inner.get(), &consequence);
2000        inner.ascend();
2001        assert_describes(inner.get(), &conditional);
2002
2003        let mut unknown = Ancestors::unknown().of_children(&body);
2004        unknown.descend(&statement);
2005        assert_eq!(
2006            unknown.get().depth(),
2007            None,
2008            "without a chain a descent records nothing"
2009        );
2010        unknown.ascend();
2011        assert_eq!(
2012            unknown.get().parent(&call).map(|p| p.id()),
2013            Some(consequence.id()),
2014            "and the answer still climbs"
2015        );
2016    }
2017
2018    /// `descend` takes the chain into a child of its last entry and
2019    /// nothing else: a walker that descends into a sibling, or into the
2020    /// node already on top, would have every later gate read a parent
2021    /// the node does not have. A debug build trips the containment
2022    /// assertion, which names the offending kind.
2023    #[cfg(all(feature = "rust", debug_assertions))]
2024    #[test]
2025    #[should_panic(
2026        expected = "descended into a function_item node the chain's last entry does not contain"
2027    )]
2028    fn descending_outside_the_last_entry_is_caught() {
2029        let tree = Tree::new::<crate::langs::RustCode>(b"fn f() {}\nfn g() {}\n");
2030        let root = tree.get_root();
2031        let f = root.child(0).expect("the first fn item");
2032        let g = root.child(1).expect("the second fn item");
2033        let chain = [root];
2034        let mut under = Ancestors::known(&chain).of_children(&f);
2035        under.descend(&g);
2036    }
2037
2038    /// `of_children` derives the children's chain of a node the chain
2039    /// describes and nothing else: asked of a grandchild under the root's
2040    /// chain — lesson 103's hazard, the derivation hoisted ahead of the
2041    /// test that names the body — every gate under it would read a parent
2042    /// the node does not have. A debug build trips the same containment
2043    /// check `descend` and `for_walk_chain_only` make, naming the kind;
2044    /// under `--cfg chain_audit` the exact parent check fires first,
2045    /// with its own message. Only the derivation can raise either;
2046    /// `Ancestors::known` checks nothing.
2047    #[cfg(all(feature = "rust", debug_assertions))]
2048    #[test]
2049    #[cfg_attr(
2050        chain_audit,
2051        should_panic(
2052            expected = "derived a chain for the children of a block node that is not its own"
2053        )
2054    )]
2055    #[cfg_attr(
2056        not(chain_audit),
2057        should_panic(
2058            expected = "derived a chain for the children of a block node its last entry does not contain"
2059        )
2060    )]
2061    fn deriving_below_a_chain_that_is_not_the_node_s_is_caught() {
2062        let tree = Tree::new::<crate::langs::RustCode>(b"fn f() {}\nfn g() {}\n");
2063        let root = tree.get_root();
2064        let g = root.child(1).expect("the second fn item");
2065        let f_body = root
2066            .child(0)
2067            .expect("the first fn item")
2068            .children()
2069            .find(|child| child.kind() == "block")
2070            .expect("its body");
2071        let chain = [root, g];
2072        let _ = Ancestors::known(&chain).of_children(&f_body);
2073    }
2074
2075    /// A derivation inherits at most two entries below the walk's chain
2076    /// (`MAX_INHERITED_RUN`): every production site derives through one
2077    /// level of fixed nesting, and two is the allowance for a parse
2078    /// error's children judged through a `then` wrapper. One derived per
2079    /// wrapper level from the last copies every level so far and is
2080    /// quadratic in the nest again (#1805); the fourth level trips the
2081    /// bound. The message carries the count, so only the last derivation
2082    /// here can raise the one expected.
2083    #[cfg(all(feature = "rust", debug_assertions))]
2084    #[test]
2085    #[should_panic(expected = "derived from a chain 3 levels below the walk's")]
2086    fn deriving_once_per_level_is_caught() {
2087        let tree = Tree::new::<crate::langs::RustCode>(b"fn f() { if a { g(); } }\n");
2088        let root = tree.get_root();
2089        let item = root.child(0).expect("the fn item");
2090        let body = item
2091            .children()
2092            .find(|child| child.kind() == "block")
2093            .expect("the body");
2094        let statement = body
2095            .children()
2096            .find(|child| child.kind() == "expression_statement")
2097            .expect("the if's statement");
2098        let conditional = statement.child(0).expect("the if");
2099        let chain = [root];
2100        let under_item = Ancestors::known(&chain).of_children(&item);
2101        let under_body = under_item.get().of_children(&body);
2102        let under_statement = under_body.get().of_children(&statement);
2103        let _ = under_statement.get().of_children(&conditional);
2104    }
2105
2106    /// In a release build the floor clamps instead of asserting: an
2107    /// `ascend` with nothing to undo leaves the body's chain in place, so
2108    /// a consumer that over-ascends still reads the ancestry of the
2109    /// body's children, never of the body's siblings, and every later
2110    /// `descend` / `ascend` pair still balances on it. The no-pop outcome
2111    /// at the floor is reachable only where the debug assertion is
2112    /// compiled out, so `cargo test --release` is what runs this; the two
2113    /// `ascending_past_*` tests are its debug-build counterpart, and the
2114    /// coverage job, a debug run, cannot see this branch by construction.
2115    #[cfg(feature = "rust")]
2116    #[cfg(not(debug_assertions))]
2117    #[test]
2118    fn ascending_past_the_floor_clamps_in_release() {
2119        let tree = Tree::new::<crate::langs::RustCode>(b"fn f() { if a { g(); } }\n");
2120        let root = tree.get_root();
2121        let item = root.child(0).expect("the fn item");
2122        let body = item
2123            .children()
2124            .find(|child| child.kind() == "block")
2125            .expect("the body");
2126        let statement = body
2127            .children()
2128            .find(|child| child.kind() == "expression_statement")
2129            .expect("the if's statement");
2130
2131        let chain = [root, item];
2132        let mut under = Ancestors::known(&chain).of_children(&body);
2133        under.ascend();
2134        under.ascend();
2135        assert_eq!(under.get().depth(), Some(3), "clamped at the body");
2136        assert_describes(under.get(), &statement);
2137
2138        under.descend(&statement);
2139        assert_eq!(under.get().depth(), Some(4), "and still moves");
2140        under.ascend();
2141        assert_describes(under.get(), &statement);
2142
2143        let mut outer = Ancestors::known(&chain[..1]).of_children(&item);
2144        outer.descend(&body);
2145        let mut inner = outer.get().of_children(&statement);
2146        inner.ascend();
2147        assert_describes(inner.get(), &statement.child(0).expect("the if"));
2148    }
2149
2150    /// The floor is the chain as built: an `ascend` with nothing to undo
2151    /// leaves the body's chain in place rather than popping the body —
2152    /// a debug build trips the assertion, which is what this pins on a
2153    /// holder derived from the walk's own chain, the shape every member
2154    /// walk holds.
2155    #[cfg(all(feature = "rust", debug_assertions))]
2156    #[test]
2157    #[should_panic(expected = "ascended above the node this chain was built for")]
2158    fn ascending_past_the_floor_is_caught() {
2159        let tree = Tree::new::<crate::langs::RustCode>(b"fn f() {}\n");
2160        let root = tree.get_root();
2161        let item = root.child(0).expect("the fn item");
2162        let chain = [root];
2163        let mut under = Ancestors::known(&chain).of_children(&item);
2164        under.ascend();
2165    }
2166
2167    /// A holder derived from a moved holder has a floor of its own: what
2168    /// it inherited plus its node. At that floor one ascend trips the
2169    /// assertion rather than popping into the levels it inherited — a
2170    /// floor of one entry, its node alone, would let that ascend take its
2171    /// node and the next answer come from the wrong parent. That it moves
2172    /// within the floor is `descend_and_ascend_move_the_held_chain_within_its_floor`,
2173    /// so the only ascend here is the one that must trip.
2174    #[cfg(all(feature = "rust", debug_assertions))]
2175    #[test]
2176    #[should_panic(expected = "ascended above the node this chain was built for")]
2177    fn ascending_past_an_inherited_floor_is_caught() {
2178        let tree = Tree::new::<crate::langs::RustCode>(b"fn f() { if a { g(); } }\n");
2179        let root = tree.get_root();
2180        let item = root.child(0).expect("the fn item");
2181        let body = item
2182            .children()
2183            .find(|child| child.kind() == "block")
2184            .expect("the body");
2185        let statement = body
2186            .children()
2187            .find(|child| child.kind() == "expression_statement")
2188            .expect("the if's statement");
2189
2190        let chain = [root];
2191        let mut outer = Ancestors::known(&chain).of_children(&item);
2192        outer.descend(&body);
2193        let mut inner = outer.get().of_children(&statement);
2194        inner.ascend();
2195    }
2196}