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
5use std::cell::{Cell, RefCell};
6use std::collections::HashMap;
7
8use super::Node;
9use crate::checker::Checker;
10
11/// The chain of a node's children, held by a consumer that reads them
12/// without descending: what [`Ancestors::of_children`] builds. A
13/// consumer that does descend, into wrappers whose statements it reads
14/// as the body's own, moves it with [`descend`](Self::descend) and
15/// [`ascend`](Self::ascend) rather than building one per level.
16#[derive(Debug)]
17pub struct ChildAncestors<'tree, 'chain> {
18    chain: Option<Vec<Node<'tree>>>,
19    /// The chain's length as built: the node's own ancestry plus the
20    /// node. [`ascend`](Self::ascend) never pops below it.
21    floor: usize,
22    above: Ancestors<'tree, 'chain>,
23}
24
25impl<'tree> ChildAncestors<'tree, '_> {
26    /// The children's [`Ancestors`], with the walk's fold cache carried
27    /// and its sibling cache deliberately not — the children are nodes
28    /// the walk has not recorded.
29    #[inline]
30    #[must_use]
31    pub fn get(&self) -> Ancestors<'tree, '_> {
32        match &self.chain {
33            Some(chain) => self.above.below(chain),
34            None => Ancestors::unknown(),
35        }
36    }
37
38    /// Descends into `child`, one of the nodes this chain describes, so
39    /// that [`get`](Self::get) answers for *its* children; undone by
40    /// [`ascend`](Self::ascend). A consumer that reads a body's
41    /// statements through the wrappers they sit in — Ruby's `npm` under
42    /// an `if`, a `begin`, a call's argument list — keeps one chain and
43    /// moves it, where building a fresh [`Ancestors::of_children`] at
44    /// each level copies the whole chain per level, `O(depth)` each and
45    /// all of them live at once (#1401 review). Without a known chain
46    /// there is nothing to move and the answers keep climbing.
47    #[inline]
48    pub fn descend(&mut self, child: &Node<'tree>) {
49        if let Some(chain) = &mut self.chain {
50            debug_assert!(
51                chain.last().is_none_or(|parent| {
52                    parent.id() != child.id()
53                        && parent.start_byte() <= child.start_byte()
54                        && child.end_byte() <= parent.end_byte()
55                }),
56                "descended into a {} node the chain's last entry does not contain",
57                child.kind()
58            );
59            chain.push(*child);
60        }
61    }
62
63    /// Undoes one [`descend`](Self::descend). The chain never shrinks
64    /// below the node it was built for, so a consumer that ascends once
65    /// too often reads the body's own chain rather than its parent's —
66    /// and trips the assertion in a debug build.
67    #[inline]
68    pub fn ascend(&mut self) {
69        if let Some(chain) = &mut self.chain {
70            debug_assert!(
71                chain.len() > self.floor,
72                "ascended above the node this chain was built for"
73            );
74            if chain.len() > self.floor {
75                chain.pop();
76            }
77        }
78    }
79}
80
81/// The chain of a node's ancestors, root first, as recorded by a walker
82/// that descended to that node.
83///
84/// A predicate that asks a node for its parent pays [`Node::parent`]'s
85/// `O(depth)` once per node, so `O(depth²)` over a deeply nested file,
86/// however few parent steps it takes (#1084). A walker that visits
87/// parents before children already holds the chain, and handing it down
88/// turns each step into a slice index — the upward counterpart of the
89/// downward flag propagation #1052 and #1062 used.
90///
91/// Callers that reached a node some other way pass
92/// [`Ancestors::unknown`], which climbs with [`Node::parent`]: the same
93/// answers at the original cost.
94#[derive(Clone, Copy, Debug)]
95pub struct Ancestors<'tree, 'chain> {
96    chain: Option<&'chain [Node<'tree>]>,
97    siblings: Option<&'chain SiblingCache<'tree>>,
98    folds: Option<&'chain FoldCache>,
99}
100
101impl<'tree, 'chain> Ancestors<'tree, 'chain> {
102    /// No chain is available; every query climbs with [`Node::parent`].
103    #[inline]
104    #[must_use]
105    pub const fn unknown() -> Self {
106        Self {
107            chain: None,
108            siblings: None,
109            folds: None,
110        }
111    }
112
113    /// `chain` lists every ancestor of the node about to be queried,
114    /// root first — so `chain.last()` is its parent and an empty chain
115    /// means the node is the root.
116    #[inline]
117    #[must_use]
118    pub const fn known(chain: &'chain [Node<'tree>]) -> Self {
119        Self {
120            chain: Some(chain),
121            siblings: None,
122            folds: None,
123        }
124    }
125
126    /// This chain, answering [`siblings_after`](Self::siblings_after) and
127    /// [`siblings_before`](Self::siblings_before) through `cache`, which
128    /// the walker that keeps the chain owns for the whole walk.
129    #[inline]
130    #[must_use]
131    pub const fn with_siblings(self, cache: &'chain SiblingCache<'tree>) -> Self {
132        Self {
133            siblings: Some(cache),
134            ..self
135        }
136    }
137
138    /// This chain, memoising `Ancestors::fold_down` and the per-node
139    /// memos through `cache`, without recording a visit: the word slots
140    /// serve only the node the cache was told is being visited, and
141    /// nothing tells it here. Test-only, for a test that drives a fold
142    /// or a memo directly: a walk lends its cache through
143    /// [`for_walk`](Self::for_walk), which is the only non-test
144    /// constructor that sets `folds`, so no lender can lend the cache
145    /// and skip the visit (#1737).
146    #[cfg(test)]
147    #[inline]
148    #[must_use]
149    pub(crate) const fn with_folds(self, cache: &'chain FoldCache) -> Self {
150        Self {
151            folds: Some(cache),
152            ..self
153        }
154    }
155
156    /// The chain a walk hands its predicates for `node`, the node it is
157    /// visiting: [`checked`](Self::checked) on `chain`, lending `folds`
158    /// with the visit recorded on it (#1737). Every walk that keeps a
159    /// [`FoldCache`] constructs through here, so lending the cache and
160    /// naming the visited node are one step that no lender can split —
161    /// by construction, since the test-only `with_folds` is the only
162    /// other way to set `folds` — the fold-cache half of what #1601 asks
163    /// for the [`SiblingCache`], which stays a separate
164    /// [`with_siblings`](Self::with_siblings) because the dump walk
165    /// records no siblings.
166    ///
167    /// The visit is what `Ancestors::classified` keys the word slots
168    /// on: an ask about `node` is served and stored, an ask about any
169    /// other node — an enclosing call read from a descendant, a module's
170    /// statements read while the module is visited — is computed and
171    /// not stored, so it cannot evict the visited node's answer. A
172    /// derived chain ([`of_children`](Self::of_children), `below`,
173    /// [`iter`](Self::iter)) carries the same cache and so the same
174    /// visit.
175    #[must_use]
176    pub fn for_walk(
177        chain: &'chain [Node<'tree>],
178        node: &Node<'tree>,
179        folds: &'chain FoldCache,
180    ) -> Self {
181        folds.visited.set(node.id());
182        Self {
183            folds: Some(folds),
184            ..Self::checked(chain, node)
185        }
186    }
187
188    /// The state of a fold of `step` down `node`'s ancestry, leaving out
189    /// the `skip` ancestors nearest `node`.
190    ///
191    /// The fold starts at `init` above the root and, for each ancestor
192    /// `a` from the root down, applies `step(state, a, a's chain, below)`,
193    /// where `below` is the next node on the path to `node` — the ancestor
194    /// under `a`, or `node` itself under its parent. A predicate that
195    /// would otherwise climb every ancestor of every candidate node, and
196    /// so cost `O(candidates × depth)`, asks this instead (#1597).
197    ///
198    /// Under a walk that lent a [`FoldCache`], the state at each ancestor
199    /// is stored per depth, keyed by the ancestor's id, so each one is
200    /// folded once per walk and a query costs amortised `O(1)`. A node
201    /// fixes its own ancestry, so a stored state whose id matches the
202    /// chain is exact; a slot left by a node the walk has moved past holds
203    /// another id and is refolded. `step` must answer the same for every
204    /// call on one `lane` within a walk. It may fold on another lane,
205    /// memoised; a fold on its own lane is answered unmemoised. The
206    /// state at `node` (`skip == 0`) depends on `node`, so it is folded
207    /// fresh. Without a known chain the ancestry is climbed with
208    /// [`Node::parent`] first, which is `O(depth²)` per query; only tests
209    /// and chainless callers reach that path, never the metrics walk.
210    pub(crate) fn fold_down(
211        self,
212        node: &Node<'tree>,
213        skip: usize,
214        lane: FoldLane,
215        init: u8,
216        step: impl Fn(u8, &Node<'tree>, Ancestors<'tree, 'chain>, &Node<'tree>) -> u8,
217    ) -> u8 {
218        let Some(chain) = self.chain else {
219            return fold_climbed(node, skip, init, step);
220        };
221        let end = chain.len().saturating_sub(skip);
222        // The cache travels into `outer`, as it does through
223        // `AncestorIter`, so a step that folds on another lane is
224        // memoised too. Each lane is its own cell, so that fold borrows
225        // nothing this one holds; a step folding on *this* lane finds it
226        // borrowed and runs unmemoised instead (`FoldCache::fold`).
227        let step_at = |state: u8, depth: usize| {
228            let outer = Ancestors {
229                chain: Some(&chain[..depth]),
230                siblings: self.siblings,
231                folds: self.folds,
232            };
233            step(
234                state,
235                &chain[depth],
236                outer,
237                chain.get(depth + 1).unwrap_or(node),
238            )
239        };
240        match self.folds {
241            Some(cache) => cache.fold(lane, chain, end, init, step_at),
242            None => (0..end).fold(init, step_at),
243        }
244    }
245
246    /// Whether an ancestor of `node` satisfies `check` before one
247    /// satisfies `stop`, nearest first, an `else if`'s inner `if` never
248    /// counting — what `node.count_specific_ancestors::<C>(self, check,
249    /// stop) > 0` answers.
250    ///
251    /// That climb stops at the nearest `stop`, which bounds it only where
252    /// one is near. A shape with none — a declaration in nested C++
253    /// namespaces, any TypeScript declaration asked whether it is
254    /// ambient — climbs to the root from every node and is quadratic in
255    /// depth (#1767). Under a walk that lent a [`FoldCache`] this folds
256    /// the answer down the chain on `lane` instead, each ancestor once
257    /// per walk: a `stop` resets it, a `check` sets it. Elsewhere the
258    /// climb is the cheaper of the two and is what runs, so a caller
259    /// with no cache keeps the climb's cost.
260    ///
261    /// A lane memoises whatever its first asker folded, so each
262    /// [`GateLane`] belongs to one question: one `check` / `stop` pair
263    /// and checker per walk. Both are plain `fn`s because the memo is
264    /// only sound for a pure function of the ancestor; a closure that
265    /// captured the asking node would hand every later node the first
266    /// one's answer. The `else if` exclusion is kept for parity with the
267    /// climb; no current asker can observe it.
268    #[doc(hidden)]
269    pub fn has_ancestor_before_stop<C: Checker>(
270        self,
271        node: &Node<'tree>,
272        lane: GateLane,
273        check: fn(&Node) -> bool,
274        stop: fn(&Node) -> bool,
275    ) -> bool {
276        self.ancestor_before_stop::<C>(node, lane.fold_lane(), check, stop)
277    }
278
279    /// [`has_ancestor_before_stop`](Self::has_ancestor_before_stop) on any
280    /// lane, for this crate's own questions.
281    pub(crate) fn ancestor_before_stop<C: Checker>(
282        self,
283        node: &Node<'tree>,
284        lane: FoldLane,
285        check: fn(&Node) -> bool,
286        stop: fn(&Node) -> bool,
287    ) -> bool {
288        if !self.memoises_folds() {
289            return node.count_specific_ancestors::<C>(self, check, stop) > 0;
290        }
291        self.fold_down(node, 0, lane, 0, |held, ancestor, outer, _| {
292            if stop(ancestor) {
293                0
294            } else if check(ancestor) && !C::is_else_if(ancestor, outer) {
295                1
296            } else {
297                held
298            }
299        }) == 1
300    }
301
302    /// The walk's memo for `question`, when it lent a [`FoldCache`].
303    pub(crate) fn node_memo(self, question: MemoQuestion) -> Option<&'chain NodeMemo> {
304        self.folds.map(|cache| &cache.nodes[question as usize])
305    }
306
307    /// `answer` for `node` under `question`, read from the walk's memo
308    /// where it lent one and recorded there after the first ask; computed
309    /// every time on a chain with no cache.
310    pub(crate) fn memoised(
311        self,
312        question: MemoQuestion,
313        node: &Node<'_>,
314        answer: impl FnOnce() -> bool,
315    ) -> bool {
316        let memo = self.node_memo(question);
317        if let Some(known) = memo.and_then(|memo| memo.get(node)) {
318            return known;
319        }
320        let answer = answer();
321        if let Some(memo) = memo {
322            memo.set(node, answer);
323        }
324        answer
325    }
326
327    /// [`memoised`](Self::memoised) on a [`NodeQuestion`], for the metric
328    /// crate's own per-node questions. `answer` must be a pure function
329    /// of `node` and the source for one walk: the memo hands every later
330    /// asker the first one's answer.
331    #[doc(hidden)]
332    pub fn memoised_answer(
333        self,
334        question: NodeQuestion,
335        node: &Node<'_>,
336        answer: impl FnOnce() -> bool,
337    ) -> bool {
338        self.memoised(question.memo_question(), node, answer)
339    }
340
341    /// `classify(node)`'s discriminant under `slot`. When `node` is the
342    /// one the walk is visiting ([`for_walk`](Self::for_walk)), the
343    /// answer is read from the walk's word slot after the first ask and
344    /// recorded there by it; an ask about any other node is computed and
345    /// not stored, so it never evicts the visited node's answer (#1737).
346    /// Computed every time on a chain with no cache, or one lent without
347    /// a visit. The caller converts the `u8` back to its enum; `classify`
348    /// must be a pure function of the node and the source for one walk.
349    pub(crate) fn classified(
350        self,
351        slot: WordSlot,
352        node: &Node<'_>,
353        classify: impl FnOnce() -> u8,
354    ) -> u8 {
355        let Some(cache) = self.folds.filter(|cache| cache.visited.get() == node.id()) else {
356            return classify();
357        };
358        let cell = &cache.words[slot as usize];
359        let (id, answer) = cell.get();
360        // Id 0 marks an empty slot: a tree-sitter node id is its address,
361        // never 0.
362        if id == node.id() {
363            return answer;
364        }
365        let answer = classify();
366        cell.set((node.id(), answer));
367        answer
368    }
369
370    /// Whether the chain is known — a walk handed it in — rather than
371    /// the climbing [`Ancestors::unknown`]. A caller that would derive a
372    /// chain for a node's children ([`below`](Self::below)) has nothing
373    /// to derive from otherwise, and the climb is already exact.
374    pub(crate) const fn is_known(self) -> bool {
375        self.chain.is_some()
376    }
377
378    /// Whether [`fold_down`](Self::fold_down) is memoised on this chain:
379    /// one a walk lent a [`FoldCache`] with. Otherwise every fold runs
380    /// from the root, so a predicate whose own climb is bounded takes that
381    /// instead.
382    pub(crate) fn memoises_folds(self) -> bool {
383        self.folds.is_some() && self.chain.is_some()
384    }
385
386    /// [`Ancestors::known`], but first checks that `chain` really is
387    /// `node`'s ancestry.
388    ///
389    /// The parity test below proves the walker's truncate/push rule on a
390    /// *replica* walker, so it cannot see `metrics_inner` itself
391    /// desynchronising — a `chain.push` moved ahead of the per-node
392    /// computes, say, or a `continue` inserted above the truncate.
393    /// [`Ancestors::parent`] trusts `chain.last()` unvalidated, so such a
394    /// drift would feed every predicate a wrong ancestor silently rather
395    /// than fail. Walkers that maintain a chain should construct through
396    /// here — through [`for_walk`](Self::for_walk) when they lend a
397    /// [`FoldCache`]; [`Ancestors::known`] stays unchecked for the
398    /// callers that deliberately pair a chain with a foreign node.
399    ///
400    /// # Two checks, because the exact one is not affordable by default
401    ///
402    /// The invariant is "`chain.last()` **is** `node.parent()`", and
403    /// asking that outright costs [`Node::parent`]'s `O(depth)` — the
404    /// very lookup #1084 exists to remove. Per node, on every walk that
405    /// constructs a checked chain, it made every debug-build walk
406    /// `O(nodes × depth)` while the shipped walk is `O(nodes)`: a tax on
407    /// every `cargo test`, worst on the deep-nesting regression tests
408    /// that exist to pin the shipped walk's linearity (#1122). It now
409    /// runs only under `--cfg chain_audit`, which `make chain-audit` and
410    /// the CI lane of the same name set — and there as a plain
411    /// `assert_eq!`, so the audit has teeth in a release profile too.
412    ///
413    /// What stays on in every debug build is an `O(1)` *consequence* of
414    /// that invariant: a parent's byte span contains its child's, and no
415    /// node is its own parent. Strictly weaker — a grandparent contains
416    /// the node as well — but it is shaped to the two ways a walker
417    /// desynchronises. A `push` moved ahead of the per-node computes
418    /// leaves `chain.last() == node`; a dropped `truncate` leaves the
419    /// previous subtree's path, whose last entry is disjoint from the
420    /// node that follows it. Both trip here, on the first node that
421    /// shows them, at four integer comparisons.
422    #[must_use]
423    pub fn checked(chain: &'chain [Node<'tree>], node: &Node<'tree>) -> Self {
424        // Opt-in only: `Node::parent` restarts at the root, so this is
425        // the `O(nodes × depth)` walk described above.
426        #[cfg(chain_audit)]
427        assert_eq!(
428            chain.last().map(Node::id),
429            node.parent().map(|parent| parent.id()),
430            "ancestor chain desynchronised on a {} node",
431            node.kind()
432        );
433        debug_assert!(
434            chain.last().is_none_or(|parent| {
435                parent.id() != node.id()
436                    && parent.start_byte() <= node.start_byte()
437                    && node.end_byte() <= parent.end_byte()
438            }),
439            "ancestor chain desynchronised on a {} node: chain.last() neither \
440             contains it nor differs from it",
441            node.kind()
442        );
443        Self::known(chain)
444    }
445
446    /// How far the node this chain describes sits from the root, or
447    /// `None` when no chain is known — deriving it then would cost the
448    /// [`Node::parent`] climb the chain exists to remove.
449    #[inline]
450    pub fn depth(self) -> Option<usize> {
451        self.chain.map(<[Node<'tree>]>::len)
452    }
453
454    /// The chain of `node`'s children, `self` being `node`'s own: a copy
455    /// extended by `node`, for a predicate that looks into a node the walk
456    /// has not descended into yet. `None` without a known chain, where
457    /// [`Ancestors::unknown`] gives the same answers by climbing. Pair it
458    /// with [`Ancestors::below`], which keeps the walk's caches on the
459    /// derived chain.
460    pub(crate) fn children_chain(self, node: &Node<'tree>) -> Option<Vec<Node<'tree>>> {
461        self.chain
462            .map(|chain| [chain, std::slice::from_ref(node)].concat())
463    }
464
465    /// The chain of `node`'s children, held: `self` extended by `node`,
466    /// for a consumer that holds a body's chain and asks a row about the
467    /// body's *members* — `npa` and `npm` over a class body — and, where
468    /// it reads through a member's own children, moves the chain with
469    /// [`ChildAncestors::descend`] rather than building another. A row's gate reads the chain it is handed as
470    /// the queried node's own, so handing it the body's instead answers
471    /// from the wrong parent the moment a `Member` or `FuncOpener` row
472    /// grows a gate; the comment "the row reads no chain" was the only
473    /// guard before this. The one allocation is per body, `O(depth)`,
474    /// never per node; without a known chain the result climbs, as
475    /// [`Ancestors::unknown`] does. Read it with
476    /// [`ChildAncestors::get`].
477    #[must_use]
478    pub fn of_children(self, node: &Node<'tree>) -> ChildAncestors<'tree, 'chain> {
479        let chain = self.children_chain(node);
480        ChildAncestors {
481            floor: chain.as_ref().map_or(0, Vec::len),
482            chain,
483            above: self,
484        }
485    }
486
487    /// `self` re-rooted on `chain`, a [`children_chain`](Self::children_chain)
488    /// the caller holds, with the walk's [`FoldCache`] carried over and
489    /// its [`SiblingCache`] deliberately not.
490    ///
491    /// The fold cache is per walk, not per chain, so a derived chain
492    /// reads and stores through the same one. Rebuilding with
493    /// [`Ancestors::known`] instead dropped it silently — the shape
494    /// lesson 101 is about — and left Doxygen's conditionals inside an
495    /// `ERROR` child unmemoised (#1686 review).
496    ///
497    /// The sibling cache is keyed by depth and holds only the nodes the
498    /// walk has pushed; the node this chain descends into is one the walk
499    /// has *not* reached, so its slot is empty and a lookup through it
500    /// would trip the walk-must-record assertion in [`lookup`](Self::lookup)
501    /// on a wide one. Java's `is_doc_target` asks for a sibling, and a
502    /// `class {` with a hundred stray `@` after it made exactly that
503    /// `ERROR` (#1686 review). Without the cache the lookup seeks, which
504    /// is what it did before and all an unrecorded node can offer.
505    #[inline]
506    #[must_use]
507    pub(crate) const fn below<'below>(
508        self,
509        chain: &'below [Node<'tree>],
510    ) -> Ancestors<'tree, 'below>
511    where
512        'chain: 'below,
513    {
514        Ancestors {
515            chain: Some(chain),
516            siblings: None,
517            folds: self.folds,
518        }
519    }
520
521    /// `node`'s parent.
522    #[inline]
523    #[must_use]
524    pub fn parent(self, node: &Node<'tree>) -> Option<Node<'tree>> {
525        match self.chain {
526            Some(chain) => chain.last().copied(),
527            None => node.parent(),
528        }
529    }
530
531    /// Whether `node`'s parent has kind id `kind`.
532    ///
533    /// The compound-leaf guard of `.claude/rules/grammar-dispatch.md`
534    /// section 5 asks this and nothing else: a delimiter or keyword
535    /// token is suppressed *only* directly under the construct that
536    /// owns it, never under an arbitrary ancestor. Eleven dispatch
537    /// arms across `getter`, `checker` and the metric walkers spelled
538    /// it out as `.parent(node).is_some_and(|p| p.kind_id() == X as
539    /// u16)`, which wraps onto four rustfmt lines inside a match guard
540    /// and buries the question under the plumbing; #1314 added six more
541    /// and folded all seventeen onto this, and #1697 the `ElseIf`
542    /// gates. Two sites spelling their binding `|parent|` were left
543    /// alone and would each fit:
544    /// `is_stabby_lambda_body` (`src/lang_helpers/ruby.rs`) and
545    /// `is_useful_comment` (`src/checker/rust.rs`, a let-chain).
546    ///
547    /// A `false` when `node` has no parent is the answer every one of
548    /// those call sites wants: a root node's token is not inside the
549    /// construct, so it is not suppressed.
550    #[inline]
551    #[must_use]
552    pub fn parent_has_kind(self, node: &Node<'tree>, kind: u16) -> bool {
553        self.parent(node).is_some_and(|p| p.kind_id() == kind)
554    }
555
556    /// Whether the sibling immediately before `node` has `kind`: the
557    /// `ElseIf` gate of the grammars that spell `else if` as a bare
558    /// `else` token followed by a nested `if` with no clause wrapper
559    /// (Java, Groovy, C#, Kotlin — #1697), through [`previous_sibling`]
560    /// and so at its cost. `false` when `node` is its parent's first
561    /// child or has no parent: a root's `if` continues nothing.
562    ///
563    /// [`previous_sibling`]: Self::previous_sibling
564    #[inline]
565    #[must_use]
566    pub(crate) fn previous_sibling_has_kind(self, node: &Node<'tree>, kind: u16) -> bool {
567        self.previous_sibling(node)
568            .is_some_and(|prev| prev.kind_id() == kind)
569    }
570
571    /// The sibling immediately before `node`, or `None` when `node` is
572    /// its parent's first child or has no parent.
573    ///
574    /// `tree_sitter`'s own `prev_sibling` resolves the parent first
575    /// (`ts_node__prev_sibling` opens with `ts_node_parent`), so it
576    /// carries the same `O(depth)` cost [`Node::parent`] does. With a
577    /// known chain the parent is free and what remains is a cursor walk
578    /// over the siblings — or, for a wide parent the walk recorded in its
579    /// [`SiblingCache`], a binary search, since a walk over every child
580    /// of a Kotlin string's `$name` run was quadratic in it (#1584).
581    /// A debug build rejects that cursor walk over a parent wider than
582    /// [`WIDE_PARENT`], which only a chain lending no cache can reach.
583    /// The metric, ops and `find` / `count` walks call this and lend one;
584    /// the suppression, dump and comment-removal walks lend none, so a
585    /// predicate added to one of those must lend one before calling it
586    /// (#1785).
587    #[inline]
588    #[must_use]
589    pub fn previous_sibling(self, node: &Node<'tree>) -> Option<Node<'tree>> {
590        let Some(chain) = self.chain else {
591            return node.previous_sibling();
592        };
593        let parent = chain.last()?;
594        if let Lookup::Wide(children, index) = self.lookup(node) {
595            return match index {
596                Some(index) => children[..index].last().copied(),
597                None => node.previous_sibling(),
598            };
599        }
600        let mut previous = None;
601        for child in parent.children() {
602            if child.id() == node.id() {
603                // The scan is `O(index)`, so only a chain that lends no
604                // cache can reach it under a wide parent, and no caller
605                // does (#1785). One that starts to would be quadratic
606                // over the parent's children and answer the same, so
607                // make it loud. Asserted once the scan has found `node`:
608                // a chain that does not describe it is a different
609                // caller error, the one the fallback below answers.
610                debug_assert!(
611                    parent.child_count() <= WIDE_PARENT,
612                    "previous_sibling scanned a {}-child {} with no SiblingCache (#1785)",
613                    parent.child_count(),
614                    parent.kind()
615                );
616                return previous;
617            }
618            previous = Some(child);
619        }
620        // `node` is not among `parent.children()`, so this chain does
621        // not describe `node`. Answering `None` would claim "no
622        // previous sibling", which is a different (and wrong) answer;
623        // fall back to the authoritative lookup instead.
624        node.previous_sibling()
625    }
626
627    /// `node`'s ancestors, nearest first, each paired with *its* own
628    /// ancestry so a predicate applied to an ancestor stays as cheap as
629    /// one applied to `node`.
630    #[inline]
631    #[must_use]
632    pub fn iter(self, node: &Node<'tree>) -> AncestorIter<'tree, 'chain> {
633        AncestorIter(match self.chain {
634            Some(chain) => AncestorSource::Chain(chain, self.siblings, self.folds),
635            None => AncestorSource::Climb(node.parent()),
636        })
637    }
638
639    /// The siblings after `node`, nearest first: what
640    /// [`Node::children_after`] yields on `node`'s parent, and nothing
641    /// for the root. `self` is `node`'s chain.
642    ///
643    /// The seek [`Node::children_after`] runs is `O(index)` over a flat
644    /// child array, so a walk that asks of every child of a wide
645    /// `ERROR` is quadratic in it (#1584). A walk that lends a
646    /// [`SiblingCache`] has already collected a wide parent's children,
647    /// and the lookup is a binary search among them.
648    pub fn siblings_after(
649        self,
650        node: &Node<'tree>,
651    ) -> impl Iterator<Item = Node<'tree>> + use<'tree, 'chain> {
652        let (wide, narrow) = match self.lookup(node) {
653            Lookup::Wide(children, index) => (index.map(|index| &children[index + 1..]), None),
654            Lookup::Narrow(parent) => (None, parent.map(|parent| parent.children_after(node))),
655        };
656        let wide = wide.into_iter().flatten().copied();
657        wide.chain(narrow.into_iter().flatten())
658    }
659
660    /// The siblings before `node`, nearest first: what
661    /// [`Node::children_before`] yields on `node`'s parent, and nothing
662    /// for the root. `self` is `node`'s chain; see
663    /// [`siblings_after`](Self::siblings_after).
664    ///
665    /// When the chain does not describe `node`, so `node` is not among the
666    /// parent's children, both this and `siblings_after` yield nothing on
667    /// either lookup, where [`previous_sibling`](Self::previous_sibling)
668    /// falls back to [`Node::previous_sibling`]. The asymmetry is
669    /// deliberate: the mismatch is a caller error `Ancestors::checked`
670    /// reports (#1122), and "no siblings" is the conservative answer for
671    /// the `exclude_tests` prune that reads these (nothing is pruned).
672    pub fn siblings_before(
673        self,
674        node: &Node<'tree>,
675    ) -> impl Iterator<Item = Node<'tree>> + use<'tree, 'chain> {
676        let (wide, narrow) = match self.lookup(node) {
677            Lookup::Wide(children, index) => (index.map(|index| &children[..index]), None),
678            Lookup::Narrow(parent) => (None, parent.map(|parent| parent.children_before(node))),
679        };
680        let wide = wide.into_iter().flatten().rev().copied();
681        wide.chain(narrow.into_iter().flatten())
682    }
683
684    // Where `node`'s siblings are read from: its parent's children as the
685    // walk recorded them and `node`'s index among them, or the parent to
686    // seek in when the walk recorded none.
687    fn lookup(self, node: &Node<'tree>) -> Lookup<'tree, 'chain> {
688        let parent = self.parent(node);
689        let recorded = match (self.siblings, self.chain, parent) {
690            (Some(cache), Some(chain), Some(parent)) => {
691                let recorded = cache.children(&parent, chain.len() - 1);
692                // A walk that stopped recording would answer the same,
693                // only quadratically, which no metric value shows.
694                debug_assert!(
695                    recorded.is_some() || parent.child_count() <= WIDE_PARENT,
696                    "a walk lending a SiblingCache must record every wide node on its \
697                     chain (#1584), but not this {}",
698                    parent.kind()
699                );
700                recorded
701            }
702            _ => None,
703        };
704        match recorded {
705            Some(children) => {
706                sibling_cache_reads::record();
707                Lookup::Wide(children, position_by_start(children, node))
708            }
709            None => Lookup::Narrow(parent),
710        }
711    }
712}
713
714enum Lookup<'tree, 'chain> {
715    Wide(&'chain [Node<'tree>], Option<usize>),
716    Narrow(Option<Node<'tree>>),
717}
718
719/// Children past which a walk records a node's children for sibling
720/// lookups. A seek over this many is a short scan however the grammar
721/// stores them, so recording a narrower node would copy it for nothing.
722///
723/// `pub` and `#[doc(hidden)]` only so the wide-parent fixtures in this
724/// crate's and `big-code-analysis`'s tests size themselves from it: a
725/// hand-copied width would silently go narrow if this were raised.
726#[doc(hidden)]
727pub const WIDE_PARENT: usize = 64;
728
729// `node`'s index in `children`, a parent's children in order. Their start
730// bytes never decrease, so a binary search lands on the first child
731// starting where `node` does; only zero-width children, which recovery
732// inserts, can share that byte with it.
733fn position_by_start(children: &[Node], node: &Node) -> Option<usize> {
734    let first = children.partition_point(|child| child.start_byte() < node.start_byte());
735    children[first..]
736        .iter()
737        .take_while(|child| child.start_byte() == node.start_byte())
738        .position(|child| child.id() == node.id())
739        .map(|offset| first + offset)
740}
741
742/// The children of each wide node on a walk's chain, recorded as the
743/// walk pushes them, so that [`Ancestors::siblings_after`] and
744/// [`Ancestors::siblings_before`] find a sibling in a flat `ERROR`
745/// without a scan from its start (#1584).
746///
747/// One slot per depth, keyed by the node's id. A walk descends into a
748/// node only after pushing its children, so every wide node on the
749/// chain has its slot; a slot left behind by a node the walk has moved
750/// past holds another id and is not read. Recording copies what the
751/// walk already holds, once per wide node.
752#[derive(Debug, Default)]
753pub struct SiblingCache<'tree>(Vec<(usize, Vec<Node<'tree>>)>);
754
755impl<'tree> SiblingCache<'tree> {
756    /// Records `children`, in order, as the children of `node`, which
757    /// sits at `depth` in the walk's chain. A node of no more than a
758    /// short scan's children is not recorded.
759    pub fn record(
760        &mut self,
761        node: &Node<'tree>,
762        depth: usize,
763        children: impl IntoIterator<Item = Node<'tree>>,
764    ) {
765        if node.child_count() <= WIDE_PARENT {
766            return;
767        }
768        if self.0.len() <= depth {
769            self.0.resize_with(depth + 1, Default::default);
770        }
771        // An unused slot's id is 0, which no node has: tree-sitter's id
772        // is the address of the node's subtree.
773        let (id, recorded) = &mut self.0[depth];
774        *id = node.id();
775        recorded.clear();
776        recorded.extend(children);
777    }
778
779    // `parent`'s children, when the walk recorded them at `depth`.
780    fn children(&self, parent: &Node<'tree>, depth: usize) -> Option<&[Node<'tree>]> {
781        self.0
782            .get(depth)
783            .filter(|(id, _)| *id == parent.id())
784            .map(|(_, children)| children.as_slice())
785    }
786}
787
788// The deepest depth at or above `from` whose slot still holds the state of
789// the ancestor the chain has there, or 0 when none does: a node fixes its
790// ancestry, so a matching id is an exact state.
791fn deepest_stored(slots: &[(usize, u8)], chain: &[Node<'_>], from: usize) -> usize {
792    (1..=from)
793        .rev()
794        .find(|&depth| slots[depth].0 == chain[depth].id())
795        .unwrap_or(0)
796}
797
798// `Ancestors::fold_down` for a caller that holds no chain: the ancestry is
799// climbed first and folded unmemoised.
800fn fold_climbed<'tree, 'chain>(
801    node: &Node<'tree>,
802    skip: usize,
803    init: u8,
804    step: impl Fn(u8, &Node<'tree>, Ancestors<'tree, 'chain>, &Node<'tree>) -> u8,
805) -> u8
806where
807    'tree: 'chain,
808{
809    let climbed = climbed_chain(node);
810    let end = climbed.len().saturating_sub(skip);
811    (0..end).fold(init, |state, depth| {
812        let below = climbed.get(depth + 1).unwrap_or(node);
813        step(state, &climbed[depth], Ancestors::unknown(), below)
814    })
815}
816
817// `node`'s ancestors, root first, climbed with `Node::parent` for a caller
818// that holds no chain. tree-sitter finds a parent by descending from the
819// root, so the climb is `O(depth²)`.
820fn climbed_chain<'tree>(node: &Node<'tree>) -> Vec<Node<'tree>> {
821    let mut climbed: Vec<_> = std::iter::successors(node.parent(), Node::parent).collect();
822    climbed.reverse();
823    climbed
824}
825
826/// The ancestor questions the metric crate asks through
827/// [`Ancestors::has_ancestor_before_stop`], one per lane of the walk's
828/// [`FoldCache`]. A subset of [`FoldLane`], so a caller outside this
829/// crate cannot name a lane another fold owns.
830#[doc(hidden)]
831#[non_exhaustive]
832#[derive(Clone, Copy, Debug, PartialEq, Eq)]
833pub enum GateLane {
834    /// Whether a declaration sits in a loop or `if` header — a `for`
835    /// initializer — with no statement block between: the C family,
836    /// C#, Go, Groovy and Java. One lane serves all because a walk
837    /// parses one language.
838    InsideHeader,
839    /// JS family: whether a declaration sits in an `export` statement
840    /// with no statement block between.
841    InsideExport,
842    /// TypeScript: whether a declaration sits anywhere inside an
843    /// ambient `declare`.
844    InsideAmbient,
845    /// Python: whether a boolean operator sits inside another before a
846    /// `lambda`, so a chain is paid for once, at its outermost operator.
847    InsideBooleanChain,
848}
849
850impl GateLane {
851    const fn fold_lane(self) -> FoldLane {
852        match self {
853            Self::InsideHeader => FoldLane::InsideHeader,
854            Self::InsideExport => FoldLane::InsideExport,
855            Self::InsideAmbient => FoldLane::InsideAmbient,
856            Self::InsideBooleanChain => FoldLane::InsideBooleanChain,
857        }
858    }
859}
860
861/// Which memoised fold a [`FoldCache`] slot holds. A language may run
862/// more than one fold over the same walk, and two folds' states must not
863/// share a slot.
864#[derive(Clone, Copy, Debug, PartialEq, Eq)]
865pub(crate) enum FoldLane {
866    /// Whether an ancestor holds a doc comment in a function body.
867    DocInBody,
868    /// A positional language's declaration scope: Go's package level,
869    /// Ruby's YARD namespace. One lane serves both because a walk parses
870    /// one language.
871    DocScope,
872    /// Python: the climb from a node through the parentheses above it to
873    /// a bare string statement (#1610).
874    BareStringClimb,
875    /// Elixir: whether an ancestor is a `quote do … end` call, under
876    /// which a `def` is a template rather than a definition.
877    InsideQuote,
878    /// [`GateLane::InsideHeader`].
879    InsideHeader,
880    /// [`GateLane::InsideExport`].
881    InsideExport,
882    /// [`GateLane::InsideAmbient`].
883    InsideAmbient,
884    /// [`GateLane::InsideBooleanChain`].
885    InsideBooleanChain,
886    /// JS family: whether a function expression or arrow meets a name
887    /// binding before a positional frame.
888    NamedBinding,
889    /// Python: how many `lambda`s enclose a node before the nearest
890    /// statement boundary, saturating (#1767).
891    LambdaDepth,
892}
893
894impl FoldLane {
895    /// How many lanes a [`FoldCache`] holds; one per variant above.
896    const COUNT: usize = 10;
897}
898
899// A lane past `COUNT` would index out of the array at run time, on the
900// first walk that folds on it; this makes a variant added without the
901// bump a build error instead.
902const _: () = assert!(FoldLane::LambdaDepth as usize + 1 == FoldLane::COUNT);
903
904/// Which memoised per-node question a [`FoldCache`] [`NodeMemo`] holds.
905/// Two questions asked of the same node must not share a slot, so each
906/// has a memo of its own.
907#[derive(Clone, Copy, Debug, PartialEq, Eq)]
908pub(crate) enum MemoQuestion {
909    /// Doxygen: whether a preprocessor conditional holds an entry, in
910    /// any branch and at any depth (#1613).
911    ConditionalDeclares,
912    /// Tcl family: whether a `word_list`'s own slot sequence can be read
913    /// positionally — no `ERROR` or MISSING child of its own (#1686).
914    ArgumentSlotsReadable,
915    /// Tcl: whether a `word_list` is a brace-list `switch`'s — holds
916    /// exactly one `braced_word`, the arm list — asked once per arm by
917    /// the `CaseArm` row (#1695).
918    SwitchArmList,
919    /// Elixir: whether a `when` operator sits in a guard position — the
920    /// outermost of a repeated-guard chain decides for every nested one,
921    /// so each is asked once rather than climbing the chain per token
922    /// (#1695).
923    GuardOperator,
924    /// JS family: whether an arrow's *parent* holds a `property_identifier`
925    /// child — the name an unbound arrow is bound to. Asked of the parent
926    /// once per arrow under it, and the scan is `O(width)` over the
927    /// parent's children, so `run(() => 1, …, () => n)` asked it `n`
928    /// times of one `arguments` and was quadratic (#1696 review).
929    NamesAnArrow,
930    /// Elixir: whether a `keywords` list holds a `do:` pair — what makes
931    /// its `else:` / `rescue:` / `catch:` siblings a block-equivalent
932    /// section. Asked of the list once per pair in it, and the scan is
933    /// `O(width)` over the list (#1602).
934    KeywordListHasDo,
935    /// Elixir: whether a Call argument is followed by no operand — the
936    /// position a keyword list must hold to be the Call's sections.
937    /// Asked of the argument once per pair in it, and the scan is
938    /// `O(siblings)` over whatever trails it, comments included (#1602
939    /// review).
940    ArgumentIsTrailing,
941    /// Elixir: whether a bracketed argument's keyword list is the first
942    /// operand in its brackets — `[do: 1, else: 2]` holds pairs alone,
943    /// `[1, do: 1]` is a plain list. Asked of the list once per pair in
944    /// it, and the scan is `O(siblings)` over what precedes the pairs,
945    /// comments included (#1697 cost audit).
946    KeywordsLeadTheirList,
947    /// [`NodeQuestion::BareStringParenthesisLine`].
948    BareStringParenthesisLine,
949}
950
951impl MemoQuestion {
952    /// How many memos a [`FoldCache`] holds; one per variant above.
953    const COUNT: usize = 9;
954}
955
956const _: () = assert!(MemoQuestion::BareStringParenthesisLine as usize + 1 == MemoQuestion::COUNT);
957
958/// The per-node questions the metric crate memoises through
959/// [`Ancestors::memoised_answer`], one per [`MemoQuestion`] memo of the
960/// walk's [`FoldCache`]. A subset of [`MemoQuestion`], as [`GateLane`]
961/// is of [`FoldLane`], so a caller outside this crate cannot name a memo
962/// another question owns.
963#[doc(hidden)]
964#[non_exhaustive]
965#[derive(Clone, Copy, Debug, PartialEq, Eq)]
966pub enum NodeQuestion {
967    /// Python: whether a bare `\` run that starts a logical line inside
968    /// a parenthesised bare string's parentheses is the string's line
969    /// with no code before the string on it. A function of the
970    /// parenthesis alone, asked once per run it holds; each ask climbed
971    /// from the run past every earlier run and comment in the
972    /// parenthesis, quadratic in them (fourth re-review of #1819).
973    BareStringParenthesisLine,
974}
975
976impl NodeQuestion {
977    const fn memo_question(self) -> MemoQuestion {
978        match self {
979            Self::BareStringParenthesisLine => MemoQuestion::BareStringParenthesisLine,
980        }
981    }
982}
983
984/// The per-depth states of the walk's memoised folds, for
985/// `Ancestors::fold_down` (#1597), the per-node memos for
986/// `Ancestors::node_memo`, and the word slots keyed on the node the
987/// walk is visiting (`Ancestors::classified`).
988///
989/// One slot per depth and lane, keyed by the id of the ancestor at that
990/// depth: the state folded over every ancestor above it. Interior
991/// mutability, because [`Ancestors`] lends it shared, as it lends a
992/// [`SiblingCache`]. One cell per lane, because a fold's step may ask a
993/// question another lane memoises — the JS family's doc-in-body fold
994/// asks whether each ancestor is a function — and that fold must not
995/// find its lane borrowed by the one in progress.
996#[derive(Debug, Default)]
997pub struct FoldCache {
998    lanes: [RefCell<Vec<(usize, u8)>>; FoldLane::COUNT],
999    nodes: [NodeMemo; MemoQuestion::COUNT],
1000    words: [Cell<(usize, u8)>; WordSlot::COUNT],
1001    /// The id of the node the walk is visiting, as [`Ancestors::for_walk`]
1002    /// last recorded it; 0 — no node's id — until a walk records one.
1003    visited: Cell<usize>,
1004}
1005
1006/// The text-classified constructs whose answer for the visited node a
1007/// walk keeps (#1697, #1737). A grammar that spells `if`, `switch` or
1008/// `return` as a generic `call` / `command` told apart only by its
1009/// target text is asked the same question of the same node by every
1010/// metric that runs on it — four reads of one field and one text
1011/// compare where a kind-based language pays none. One slot holding the
1012/// visited node's id and its answer serves them all, however many asks
1013/// about *other* nodes arrive in between: an ask about a node the walk
1014/// is not visiting (a consumer reading the enclosing call, a module
1015/// reading its statements) is computed and not stored, so it costs its
1016/// one read and nothing else. Keying on the visit, which
1017/// [`Ancestors::for_walk`] records, is what makes that so — before
1018/// #1737 the slot held the *last node asked* and such an ask evicted
1019/// the visited node's answer, which made "may this site use the cached
1020/// read" a judgement per call site. No map, no allocation, `O(1)`
1021/// memory, dropped with the walk.
1022///
1023/// The bound is one read per (consumer, target) per visit. The
1024/// last-asked slot served two cross-visit shapes for free that this
1025/// one does not — a keyword pair's enclosing call asked by each of its
1026/// sections, an `else` token's `if` — so a file of `N` keyword
1027/// sections or `N` if-else blocks pays `N` more reads than it did,
1028/// linear either way (`cognitive/elixir-keyword-sections` prices it:
1029/// 1.03 → 1.12, within noise on every fixture measured). That is
1030/// accepted because the visited path dominates: an Elixir `call` is
1031/// asked four to seven times while visited, and the typed
1032/// `NodeMemo<T>` fold #1737 offered as its second option would put a
1033/// `HashMap` probe on every one of those asks to save the tens of
1034/// nanoseconds the two cross-visit shapes re-read — measured on the
1035/// #1737 branch, not assumed, which is why the slot stays a `Cell`.
1036///
1037/// The slot holds the classification's `#[repr(u8)]` discriminant; the
1038/// enum is the language helper's (`ElixirCallTarget`, `TclCommandWord`),
1039/// which also owns the conversion back.
1040#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1041pub(crate) enum WordSlot {
1042    /// Elixir: what a `call`'s `target` identifier spells.
1043    ElixirCallTarget,
1044    /// Tcl: what a `command`'s leading `simple_word` spells.
1045    TclCommandWord,
1046}
1047
1048impl WordSlot {
1049    /// How many slots a [`FoldCache`] holds; one per variant above.
1050    const COUNT: usize = 2;
1051}
1052
1053const _: () = assert!(WordSlot::TclCommandWord as usize + 1 == WordSlot::COUNT);
1054
1055/// Answers about a node's own subtree, memoised for one walk and keyed
1056/// by node id, which is unique within a tree: Doxygen's "does this
1057/// preprocessor conditional hold an entry", asked of every conditional
1058/// a doc comment's stretch meets; the Tcl family's "can this argument
1059/// list be read by position", asked by every braced word in it. Unlike
1060/// a [`FoldLane`] it is not tied to the chain, so an answer stored for
1061/// one sibling subtree serves every later question about it (#1613).
1062/// Each holds one [`MemoQuestion`].
1063#[derive(Debug, Default)]
1064pub(crate) struct NodeMemo(RefCell<HashMap<usize, bool>>);
1065
1066impl NodeMemo {
1067    /// The stored answer for `node`, if any.
1068    pub(crate) fn get(&self, node: &Node<'_>) -> Option<bool> {
1069        self.0.borrow().get(&node.id()).copied()
1070    }
1071
1072    /// Stores `answer` for `node`.
1073    pub(crate) fn set(&self, node: &Node<'_>, answer: bool) {
1074        self.0.borrow_mut().insert(node.id(), answer);
1075    }
1076}
1077
1078impl FoldCache {
1079    // The state after folding `step(state, depth)` over `chain[..end]`,
1080    // reusing and storing the per-depth states on `lane`.
1081    //
1082    // The lane stays borrowed while `step` runs, so a step that folds on
1083    // the same lane would otherwise panic on the second borrow; it folds
1084    // unmemoised instead, which answers the same. No step does today, and
1085    // the cost of one that did is the step's own: a step that re-enters
1086    // at one ancestor pays a plain fold of that prefix, one that re-enters
1087    // at every ancestor pays `2^depth`, since nothing a re-entered lane
1088    // can store cuts the recursion short. Neither shows as a wrong answer,
1089    // so debug builds refuse the shape: the whole test corpus then guards
1090    // the contract.
1091    fn fold(
1092        &self,
1093        lane: FoldLane,
1094        chain: &[Node<'_>],
1095        end: usize,
1096        init: u8,
1097        step: impl Fn(u8, usize) -> u8,
1098    ) -> u8 {
1099        let Ok(mut slots) = self.lanes[lane as usize].try_borrow_mut() else {
1100            debug_assert!(
1101                same_lane_reentry::allowed(),
1102                "a fold step re-entered its own lane {lane:?}"
1103            );
1104            return (0..end).fold(init, step);
1105        };
1106        // `slots[d]` is the state at `chain[d]`: folded over `chain[..d]`.
1107        // Depth 0 is `init`; the state at `node` itself is never stored.
1108        let memo_end = end.min(chain.len().saturating_sub(1));
1109        if slots.len() <= memo_end {
1110            // Id 0 marks an empty slot: a tree-sitter node id is its
1111            // address, never 0.
1112            slots.resize(memo_end + 1, (0, 0));
1113        }
1114        let mut depth = deepest_stored(&slots, chain, memo_end);
1115        let mut state = if depth == 0 { init } else { slots[depth].1 };
1116        while depth < memo_end {
1117            fold_steps::record();
1118            state = step(state, depth);
1119            depth += 1;
1120            slots[depth] = (chain[depth].id(), state);
1121        }
1122        if end > memo_end {
1123            state = step(state, memo_end);
1124        }
1125        state
1126    }
1127}
1128
1129// Ancestor states a memoised fold computes and stores, so a test can see
1130// a walk fold each ancestor once rather than once per asking node: the
1131// answers are identical either way (#1767). Readable from the root
1132// crate's tests through `test-support`, since most walks that lend the
1133// cache live there.
1134crate::observation::counter!(fold_steps, cfg(any(test, feature = "test-support")));
1135
1136// Sibling lookups answered from a walk's `SiblingCache` rather than by a
1137// seek. The two answer identically, so only this tells a walk that lends
1138// the cache from one that dropped it (#1447 review); a seek on a wide
1139// flat parent is the quadratic #1584 fixed.
1140crate::observation::counter!(
1141    sibling_cache_reads,
1142    cfg(any(test, feature = "test-support"))
1143);
1144
1145/// Whether a fold may re-enter its own lane: refused everywhere, except
1146/// on a thread where the one test that pins the fallback has opted in.
1147/// A flag in every build rather than a `cfg(test)` branch, because the
1148/// root crate's tests compile this crate without `cfg(test)`, and a
1149/// branch they can never take reads as a line no test reaches.
1150mod same_lane_reentry {
1151    use std::cell::Cell;
1152
1153    thread_local! {
1154        static ALLOWED: Cell<bool> = const { Cell::new(false) };
1155    }
1156
1157    pub(super) fn allowed() -> bool {
1158        ALLOWED.get()
1159    }
1160
1161    /// Opts the current thread in (`true`) or back out.
1162    #[cfg(test)]
1163    pub(super) fn allow(allowed: bool) {
1164        ALLOWED.set(allowed);
1165    }
1166}
1167
1168/// Ancestor iterator returned by [`Ancestors::iter`], nearest first.
1169///
1170/// The representation is private so that [`Ancestors::iter`] is its
1171/// only constructor: every chain it yields carries the caches of the
1172/// `Ancestors` it was made from, and nothing else can pair a
1173/// [`FoldCache`] with a chain. That is what lets
1174/// [`Ancestors::for_walk`] be the one place a visit is recorded
1175/// (#1737) — a public variant holding `Option<&FoldCache>` would have
1176/// let any caller lend a cache without one.
1177pub struct AncestorIter<'tree, 'chain>(AncestorSource<'tree, 'chain>);
1178
1179enum AncestorSource<'tree, 'chain> {
1180    /// The not-yet-yielded prefix of a known chain, and the walk's
1181    /// [`SiblingCache`] and [`FoldCache`] if it lent them. The prefix's
1182    /// last element is the next ancestor, and the prefix before it is
1183    /// that ancestor's own chain — so splitting from the back hands out
1184    /// both at once.
1185    ///
1186    /// The caches travel with each yielded chain, so a predicate asked
1187    /// of an ancestor is memoised exactly as one asked of the node
1188    /// itself. A braced Tcl word's role is asked of its *parent* through
1189    /// this iterator, and dropping the [`FoldCache`] here left that
1190    /// question unmemoised on every walk that lent one (#1686).
1191    Chain(
1192        &'chain [Node<'tree>],
1193        Option<&'chain SiblingCache<'tree>>,
1194        Option<&'chain FoldCache>,
1195    ),
1196    /// The next ancestor to yield, reached by climbing.
1197    Climb(Option<Node<'tree>>),
1198}
1199
1200impl<'tree, 'chain> Iterator for AncestorIter<'tree, 'chain> {
1201    type Item = (Node<'tree>, Ancestors<'tree, 'chain>);
1202
1203    fn next(&mut self) -> Option<Self::Item> {
1204        match &mut self.0 {
1205            AncestorSource::Chain(remaining, siblings, folds) => {
1206                let (&nearest, above) = remaining.split_last()?;
1207                *remaining = above;
1208                let ancestors = Ancestors {
1209                    chain: Some(above),
1210                    siblings: *siblings,
1211                    folds: *folds,
1212                };
1213                Some((nearest, ancestors))
1214            }
1215            AncestorSource::Climb(next) => {
1216                let nearest = (*next)?;
1217                *next = nearest.parent();
1218                Some((nearest, Ancestors::unknown()))
1219            }
1220        }
1221    }
1222}
1223
1224#[cfg(test)]
1225mod tests {
1226    use super::*;
1227    use crate::node::Tree;
1228
1229    /// A chain that lends no `SiblingCache` reaching `previous_sibling`'s
1230    /// scan under a wide parent trips the debug assertion there, rather
1231    /// than going quadratic in silence (#1785). No production walk does;
1232    /// this is what shows the assertion can fire at all, so its silence
1233    /// across the suite means something.
1234    #[cfg(all(feature = "rust", debug_assertions))]
1235    #[test]
1236    #[should_panic(expected = "with no SiblingCache (#1785)")]
1237    fn previous_sibling_rejects_a_wide_parent_without_its_cache() {
1238        let source = "fn a() {}\n".repeat(WIDE_PARENT + 1);
1239        let tree = Tree::new::<crate::langs::RustCode>(source.as_bytes());
1240        let root = tree.get_root();
1241        let last = root.children().last().expect("the file has items");
1242        let _ = Ancestors::known(&[root]).previous_sibling(&last);
1243    }
1244
1245    /// A chain that does not describe the node still falls back to the
1246    /// tree under a wide parent, as it does under a narrow one
1247    /// (`previous_sibling_falls_back_on_a_chain_that_is_not_this_nodes`):
1248    /// the #1785 assertion is about a scan that found the node, and a
1249    /// mismatched chain is the caller error the fallback answers.
1250    /// Discriminates only under a debug build, where the assertion is
1251    /// compiled in.
1252    #[cfg(feature = "rust")]
1253    #[test]
1254    fn previous_sibling_falls_back_on_a_wide_chain_that_is_not_this_nodes() {
1255        let source = format!(
1256            "fn a() {{ let x = 1; }}\n{}",
1257            "fn b() {}\n".repeat(WIDE_PARENT)
1258        );
1259        let tree = Tree::new::<crate::langs::RustCode>(source.as_bytes());
1260        let root = tree.get_root();
1261        assert!(root.child_count() > WIDE_PARENT, "the root must be wide");
1262        let statement = root
1263            .preorder()
1264            .find(|node| node.kind() == "let_declaration")
1265            .expect("fixture has a statement");
1266        let expected = statement
1267            .previous_sibling()
1268            .map(|node| node.id())
1269            .expect("the statement follows the body's `{`");
1270        // The root is not the statement's parent, which is the body.
1271        assert_eq!(
1272            Ancestors::known(&[root])
1273                .previous_sibling(&statement)
1274                .map(|node| node.id()),
1275            Some(expected),
1276            "a mismatched chain must fall back, not panic or report `None`"
1277        );
1278    }
1279
1280    // The ids of `nodes`, so a failing comparison prints which differ.
1281    #[cfg(feature = "perl")]
1282    fn ids<'a>(nodes: impl Iterator<Item = Node<'a>>) -> Vec<usize> {
1283        nodes.map(|node| node.id()).collect()
1284    }
1285
1286    // `parent`'s children through `child(i)`, the raw walk that neither
1287    // the seek nor the recorded array is built on.
1288    #[cfg(feature = "perl")]
1289    fn raw_children(parent: &Node) -> Vec<usize> {
1290        let raw = parent.as_tree_sitter();
1291        (0..raw.child_count() as u32)
1292            .filter_map(|i| raw.child(i))
1293            .map(|child| child.id())
1294            .collect()
1295    }
1296
1297    // `my @r = (` and a body never closed: recovery makes the root an
1298    // `ERROR` whose children are the body's tokens, one flat array of
1299    // well over `WIDE_PARENT` of them.
1300    #[cfg(feature = "perl")]
1301    fn flat_error() -> Tree {
1302        let source = format!("my @r = ({}", "{\nlast,\n$a && $b,\n".repeat(20));
1303        Tree::new::<crate::langs::PerlCode>(source.as_bytes())
1304    }
1305
1306    /// `fold_down` answers the same through all three of its paths: the
1307    /// walk's memoised [`FoldCache`], a known chain with no cache, and the
1308    /// chainless climb. Queried in walk order, as the metrics walk queries
1309    /// it, and twice per node so the second query is answered from the
1310    /// stored slots (#1597). The step depends on order, on `below` and on
1311    /// the parent its `outer` chain names, so a slot read at the wrong
1312    /// depth, a climb in the wrong direction or an `outer` cut at the wrong
1313    /// place changes the answer. The climb hands `Ancestors::unknown()`,
1314    /// whose `parent` falls back to `Node::parent`, so all three agree only
1315    /// when the chains are right.
1316    #[cfg(feature = "rust")]
1317    #[test]
1318    fn fold_down_agrees_across_its_cache_chain_and_climb_paths() {
1319        let tree = Tree::new::<crate::langs::RustCode>(
1320            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",
1321        );
1322        let step = |state: u8, ancestor: &Node, outer: Ancestors, below: &Node| {
1323            let parent = outer
1324                .parent(ancestor)
1325                .map_or(0, |parent| parent.kind_id().to_le_bytes()[0]);
1326            state
1327                .wrapping_mul(31)
1328                .wrapping_add(ancestor.kind_id().to_le_bytes()[0])
1329                .wrapping_add(below.kind_id().to_le_bytes()[0].rotate_left(3))
1330                .wrapping_add(parent.rotate_left(5))
1331        };
1332        let cache = FoldCache::default();
1333        let mut stack = vec![(tree.get_root(), 0_usize)];
1334        let mut chain: Vec<Node> = Vec::new();
1335        let mut queried = 0_usize;
1336        while let Some((node, depth)) = stack.pop() {
1337            chain.truncate(depth);
1338            for skip in 0..=3 {
1339                let cached = |c: &[Node<'_>]| {
1340                    Ancestors::known(c).with_folds(&cache).fold_down(
1341                        &node,
1342                        skip,
1343                        FoldLane::DocInBody,
1344                        7,
1345                        step,
1346                    )
1347                };
1348                let first = cached(&chain);
1349                let again = cached(&chain);
1350                let uncached =
1351                    Ancestors::known(&chain).fold_down(&node, skip, FoldLane::DocInBody, 7, step);
1352                let climbed =
1353                    Ancestors::unknown().fold_down(&node, skip, FoldLane::DocInBody, 7, step);
1354                assert_eq!(
1355                    (first, again, uncached),
1356                    (climbed, climbed, climbed),
1357                    "{} at depth {depth}, skip {skip}",
1358                    node.kind()
1359                );
1360                queried += 1;
1361            }
1362            chain.push(node);
1363            let children: Vec<_> = node.children().collect();
1364            stack.extend(children.into_iter().rev().map(|child| (child, depth + 1)));
1365        }
1366        assert!(
1367            queried > 100,
1368            "the fixture must exercise a real walk: {queried}"
1369        );
1370    }
1371
1372    /// A fold's step may fold on another lane, and that inner fold is
1373    /// memoised through the same cache: each lane is its own cell, so the
1374    /// outer fold's borrow does not block it. A step that folds on its
1375    /// *own* lane finds that lane borrowed and runs unmemoised, answering
1376    /// what the plain fold does rather than panicking on a second borrow,
1377    /// at the plain fold's cost.
1378    ///
1379    /// The inner fold counts its own steps, so memoisation is observed
1380    /// rather than inferred: walked in order, each inner fold costs one
1381    /// step per new depth, so the total stays near the node count, where
1382    /// an unmemoised inner fold costs the whole depth every time.
1383    #[cfg(feature = "rust")]
1384    #[test]
1385    fn a_step_folds_another_lane_memoised_and_its_own_lane_unmemoised() {
1386        use crate::test_support::for_each_node_with_chain;
1387        use std::cell::Cell;
1388        // Every level opens a block, so depth grows with the fixture and
1389        // an unmemoised inner fold is visibly quadratic in step count.
1390        let source = format!("fn f() {{ {} }}\n", "{ ".repeat(60) + &"} ".repeat(60));
1391        let inner_steps = Cell::new(0_usize);
1392        let inner = |state: u8, ancestor: &Node, _: Ancestors, _: &Node| {
1393            inner_steps.set(inner_steps.get() + 1);
1394            state
1395                .wrapping_mul(7)
1396                .wrapping_add(ancestor.kind_id().to_le_bytes()[0])
1397        };
1398        let outer_on = |lane: FoldLane| {
1399            move |state: u8, ancestor: &Node, outer: Ancestors, _: &Node| {
1400                state.wrapping_add(outer.fold_down(ancestor, 0, lane, 3, inner))
1401            }
1402        };
1403        let fold = |chain: &[Node], node: &Node, cache: Option<&FoldCache>, lane, inner_lane| {
1404            let ancestors = Ancestors::known(chain);
1405            let ancestors = cache.map_or(ancestors, |cache| ancestors.with_folds(cache));
1406            ancestors.fold_down(node, 0, lane, 0, outer_on(inner_lane))
1407        };
1408
1409        let cache = FoldCache::default();
1410        same_lane_reentry::allow(true);
1411        let nodes =
1412            for_each_node_with_chain::<crate::langs::RustCode>(source.as_bytes(), |node, chain| {
1413                let (other, own) = (FoldLane::DocInBody, FoldLane::BareStringClimb);
1414                assert_eq!(
1415                    fold(chain, node, Some(&cache), other, FoldLane::DocScope),
1416                    fold(chain, node, None, other, FoldLane::DocScope),
1417                    "another lane must answer what the plain fold does"
1418                );
1419                let before = inner_steps.get();
1420                let own_lane = fold(chain, node, Some(&cache), own, own);
1421                let own_steps = inner_steps.get() - before;
1422                assert_eq!(
1423                    own_lane,
1424                    fold(chain, node, None, own, own),
1425                    "its own lane must answer what the plain fold does"
1426                );
1427                // One plain fold of the prefix per query: `inner` folds
1428                // its own lane once, at the node, and re-enters nowhere.
1429                let depth = chain.len();
1430                assert!(
1431                    own_steps <= depth * (depth + 1) / 2,
1432                    "its own lane must cost one plain fold of the prefix"
1433                );
1434            });
1435        same_lane_reentry::allow(false);
1436        assert!(nodes > 200, "the fixture must nest deeply: {nodes}");
1437
1438        // The other-lane fold alone on a fresh cache, counting only its
1439        // inner steps.
1440        let cache = FoldCache::default();
1441        inner_steps.set(0);
1442        for_each_node_with_chain::<crate::langs::RustCode>(source.as_bytes(), |node, chain| {
1443            fold(
1444                chain,
1445                node,
1446                Some(&cache),
1447                FoldLane::DocInBody,
1448                FoldLane::DocScope,
1449            );
1450        });
1451        // Memoised, the inner folds cost a small constant per node;
1452        // unmemoised, each outer step's inner fold runs the whole prefix,
1453        // `Σ depth` along the spine — quadratic in it, far past this
1454        // bound.
1455        assert!(
1456            inner_steps.get() <= 4 * nodes,
1457            "the other lane is not memoised"
1458        );
1459    }
1460
1461    /// A recorded wide parent answers every child's siblings, and its
1462    /// previous sibling, from the recorded array, and answers exactly
1463    /// what the raw walk does on either side of it — the `ERROR` whose
1464    /// flat array made the seek `O(index)` (#1584). A node that is no
1465    /// child of it gets nothing.
1466    #[cfg(feature = "perl")]
1467    #[test]
1468    fn siblings_of_a_recorded_wide_parent_match_the_child_walk() {
1469        let tree = flat_error();
1470        let root = tree.get_root();
1471        assert!(root.is_error(), "the fixture's tail must fail to parse");
1472        assert!(root.child_count() > WIDE_PARENT, "the ERROR must be wide");
1473
1474        let mut cache = SiblingCache::default();
1475        cache.record(&root, 0, root.children());
1476        let chain = [root];
1477        let ancestors = Ancestors::known(&chain).with_siblings(&cache);
1478        let all = raw_children(&root);
1479
1480        let (mut observed, mut expected) = (Vec::new(), Vec::new());
1481        for (index, child) in root.children().enumerate() {
1482            let recorded_index = match ancestors.lookup(&child) {
1483                Lookup::Wide(_, index) => index,
1484                Lookup::Narrow(_) => None,
1485            };
1486            observed.push((
1487                index,
1488                recorded_index,
1489                ids(ancestors.siblings_after(&child)),
1490                ids(ancestors.siblings_before(&child)),
1491                ancestors.previous_sibling(&child).map(|node| node.id()),
1492            ));
1493            expected.push((
1494                index,
1495                Some(index),
1496                all[index + 1..].to_vec(),
1497                all[..index].iter().rev().copied().collect(),
1498                index.checked_sub(1).map(|previous| all[previous]),
1499            ));
1500        }
1501        assert_eq!(observed, expected);
1502
1503        // A grandchild starting where its parent does, so the search
1504        // reaches it and only the id comparison turns it away.
1505        let stray = root
1506            .children()
1507            .find_map(|child| {
1508                child
1509                    .child(0)
1510                    .filter(|g| g.start_byte() == child.start_byte())
1511            })
1512            .expect("the fixture nests a node at its parent's start");
1513        assert!(matches!(ancestors.lookup(&stray), Lookup::Wide(_, None)));
1514        assert_eq!(ancestors.siblings_after(&stray).count(), 0);
1515        assert_eq!(ancestors.siblings_before(&stray).count(), 0);
1516        // `previous_sibling` falls back to the node's own lookup instead,
1517        // which finds a stray's real previous sibling: `$b`'s is the `&&`
1518        // of its own chain, not anything in the root.
1519        let operand = root
1520            .children()
1521            .find_map(|child| child.child(2))
1522            .expect("the fixture holds `$a && $b`");
1523        let previous = ancestors
1524            .previous_sibling(&operand)
1525            .expect("the fallback finds the `&&`");
1526        assert_eq!(previous.kind(), "&&");
1527    }
1528
1529    /// A narrow parent is never recorded, and its siblings come from
1530    /// the seek — with or without a cache lent.
1531    #[cfg(feature = "perl")]
1532    #[test]
1533    fn a_narrow_parent_is_sought_not_recorded() {
1534        let tree = flat_error();
1535        let root = tree.get_root();
1536        let chain = [root];
1537        let narrow = root
1538            .children()
1539            .find(|child| (2..=WIDE_PARENT).contains(&child.child_count()))
1540            .expect("the fixture holds a narrow node with several children");
1541        let mut cache = SiblingCache::default();
1542        cache.record(&narrow, 1, narrow.children());
1543        assert!(cache.0.is_empty(), "a narrow node must not be recorded");
1544
1545        let narrow_chain = [root, narrow];
1546        let all = raw_children(&narrow);
1547        for ancestors in [
1548            Ancestors::known(&narrow_chain).with_siblings(&cache),
1549            Ancestors::known(&narrow_chain),
1550        ] {
1551            let first = narrow.child(0).expect("narrow node has children");
1552            assert!(matches!(ancestors.lookup(&first), Lookup::Narrow(Some(_))));
1553            assert_eq!(ids(ancestors.siblings_after(&first)), all[1..]);
1554        }
1555        // Without a cache a wide parent is sought too.
1556        let first = root.child(0).expect("root has children");
1557        assert!(matches!(
1558            Ancestors::known(&chain).lookup(&first),
1559            Lookup::Narrow(Some(_))
1560        ));
1561    }
1562
1563    /// A walk that lends a cache but did not record a wide node on its
1564    /// chain would answer correctly and quadratically; the assertion is
1565    /// what makes that visible to every test that walks one.
1566    #[cfg(all(feature = "perl", debug_assertions))]
1567    #[test]
1568    #[should_panic(expected = "must record every wide node on its chain")]
1569    fn an_unrecorded_wide_parent_trips_the_walk_assertion() {
1570        let tree = flat_error();
1571        let root = tree.get_root();
1572        let cache = SiblingCache::default();
1573        let chain = [root];
1574        let first = root.child(0).expect("root has children");
1575        let _ = Ancestors::known(&chain)
1576            .with_siblings(&cache)
1577            .lookup(&first);
1578    }
1579
1580    /// The binary search finds every child at its index, including a
1581    /// zero-width one: recovery inserts it at the byte its successor
1582    /// starts at, so only the id tells the two apart. The Kotlin
1583    /// fixture's `vararg: Int` holds one.
1584    #[cfg(feature = "kotlin")]
1585    #[test]
1586    fn position_by_start_finds_a_zero_width_child() {
1587        let tree = Tree::new::<crate::langs::KotlinCode>(b"fun f(vararg: Int, b: Int) {}");
1588        let mut zero_width = 0;
1589        for node in tree.get_root().preorder() {
1590            let children: Vec<_> = node.children().collect();
1591            for (index, child) in children.iter().enumerate() {
1592                zero_width += usize::from(child.start_byte() == child.end_byte());
1593                assert_eq!(position_by_start(&children, child), Some(index));
1594            }
1595        }
1596        assert!(
1597            zero_width > 0,
1598            "fixture must hold an inserted zero-width child"
1599        );
1600    }
1601
1602    /// A chain yielded by [`Ancestors::iter`] carries the walk's
1603    /// [`FoldCache`], so a memo stored through the node's own chain is
1604    /// read back through an ancestor's. The Tcl-family role question is
1605    /// asked of a braced word's *parent* through this iterator, and an
1606    /// iterator that dropped the cache left it unmemoised on every walk
1607    /// that lent one (#1686). Restoring `folds: None` in
1608    /// `AncestorIter::next` fails the last assertion.
1609    #[cfg(feature = "rust")]
1610    #[test]
1611    fn an_iterated_ancestor_keeps_the_walk_s_memo() {
1612        let tree = Tree::new::<crate::langs::RustCode>(b"fn f() { g(1); }\n");
1613        let root = tree.get_root();
1614        // Root first, then the `function_item`, its block, and the
1615        // expression statement in it: the parent of `g(1)`.
1616        let mut chain = vec![root];
1617        for kind in ["function_item", "block", "expression_statement"] {
1618            let last = *chain.last().expect("the chain starts non-empty");
1619            let child = last
1620                .children()
1621                .find(|child| child.kind() == kind)
1622                .unwrap_or_else(|| panic!("the fixture nests a {kind}"));
1623            chain.push(child);
1624        }
1625        let leaf = chain
1626            .last()
1627            .expect("the chain has a parent")
1628            .child(0)
1629            .expect("the statement holds the call");
1630        assert_eq!(leaf.kind(), "call_expression");
1631
1632        let cache = FoldCache::default();
1633        let walk = Ancestors::known(&chain).with_folds(&cache);
1634        walk.node_memo(MemoQuestion::ArgumentSlotsReadable)
1635            .expect("the chain lent a cache")
1636            .set(&leaf, true);
1637        assert!(
1638            Ancestors::known(&chain)
1639                .node_memo(MemoQuestion::ArgumentSlotsReadable)
1640                .is_none(),
1641            "a chain lent no cache has no memo"
1642        );
1643
1644        let (_, above) = walk.iter(&leaf).next().expect("the leaf has a parent");
1645        let memo = above
1646            .node_memo(MemoQuestion::ArgumentSlotsReadable)
1647            .expect("an iterated ancestor's chain keeps the lent cache");
1648        assert_eq!(memo.get(&leaf), Some(true));
1649
1650        // The other derivation: a chain extended *downward* for a node
1651        // the walk has not reached, re-rooted with `below`, reads the
1652        // same memo. Rebuilding it with `Ancestors::known` instead
1653        // answers `None` here, which is what `error_holds_target` did
1654        // before #1686.
1655        let children = walk
1656            .children_chain(&leaf)
1657            .expect("a known chain extends downward");
1658        assert_eq!(children.len(), chain.len() + 1);
1659        let below = walk.below(&children);
1660        assert_eq!(below.depth(), Some(chain.len() + 1));
1661        let memo = below
1662            .node_memo(MemoQuestion::ArgumentSlotsReadable)
1663            .expect("a chain re-rooted with `below` keeps the lent cache");
1664        assert_eq!(memo.get(&leaf), Some(true));
1665        assert!(
1666            Ancestors::known(&children)
1667                .node_memo(MemoQuestion::ArgumentSlotsReadable)
1668                .is_none(),
1669            "a chain rebuilt with `known` carries nothing, which is why `below` exists"
1670        );
1671    }
1672
1673    /// The word slot serves the node the walk is visiting and no other
1674    /// (#1737). Through a chain built with `for_walk` for `a`, the first
1675    /// ask about `a` computes and every later one is served — across
1676    /// asks about another node `b` through the walk's own chain, a chain
1677    /// derived from it with `of_children`, `below` and `iter`, and the
1678    /// fold-free chain `fold_down` hands its step, each of which computes
1679    /// `b`'s answer and stores nothing. Restoring the last-node-asked
1680    /// slot, which stored every ask, fails at the second ask about `a`:
1681    /// the ask about `b` in between evicted it. A chain lent the cache
1682    /// without a visit computes every ask, and a later `for_walk` for `b`
1683    /// retires `a`'s entry.
1684    #[cfg(feature = "rust")]
1685    #[test]
1686    fn the_word_slot_serves_only_the_visited_node() {
1687        use std::cell::Cell;
1688        let tree = Tree::new::<crate::langs::RustCode>(b"fn f() { g(1); }\n");
1689        let root = tree.get_root();
1690        let a = root.child(0).expect("the fn item");
1691        let body = a
1692            .children()
1693            .find(|child| child.kind() == "block")
1694            .expect("the body");
1695        let b = body.child(1).expect("the call statement");
1696        assert_ne!(a.id(), b.id());
1697
1698        let runs = Cell::new(0_usize);
1699        let computes = |answer: u8| {
1700            let runs = &runs;
1701            move || {
1702                runs.set(runs.get() + 1);
1703                answer
1704            }
1705        };
1706        let cache = FoldCache::default();
1707        let chain = [root];
1708        let walk = Ancestors::for_walk(&chain, &a, &cache);
1709        let slot = WordSlot::ElixirCallTarget;
1710
1711        assert_eq!(walk.classified(slot, &a, computes(1)), 1);
1712        assert_eq!(runs.get(), 1, "the first ask computes");
1713        assert_eq!(walk.classified(slot, &a, computes(9)), 1);
1714        assert_eq!(runs.get(), 1, "the second ask is served");
1715
1716        assert_eq!(walk.classified(slot, &b, computes(2)), 2);
1717        assert_eq!(walk.classified(slot, &b, computes(2)), 2);
1718        assert_eq!(
1719            runs.get(),
1720            3,
1721            "an ask about another node computes every time"
1722        );
1723        assert_eq!(walk.classified(slot, &a, computes(9)), 1);
1724        assert_eq!(
1725            runs.get(),
1726            3,
1727            "and does not evict the visited node's answer"
1728        );
1729
1730        let under = walk.of_children(&a);
1731        assert_eq!(under.get().classified(slot, &b, computes(2)), 2);
1732        let children = walk.children_chain(&a).expect("a known chain extends");
1733        assert_eq!(walk.below(&children).classified(slot, &b, computes(2)), 2);
1734        let (_, above) = walk.iter(&b).next().expect("b has a parent");
1735        assert_eq!(above.classified(slot, &b, computes(2)), 2);
1736        let folded = walk.fold_down(&a, 0, FoldLane::DocInBody, 0, |_, _, outer, _| {
1737            outer.classified(slot, &b, computes(2))
1738        });
1739        assert_eq!(folded, 2);
1740        assert_eq!(runs.get(), 7, "each derived chain's ask computes");
1741        assert_eq!(walk.classified(slot, &a, computes(9)), 1);
1742        assert_eq!(runs.get(), 7, "and none of them evicts");
1743        assert_eq!(under.get().classified(slot, &a, computes(9)), 1);
1744        assert_eq!(runs.get(), 7, "a derived chain serves the visited node too");
1745
1746        let never_visited = FoldCache::default();
1747        let unvisited = Ancestors::known(&chain).with_folds(&never_visited);
1748        assert_eq!(unvisited.classified(slot, &a, computes(1)), 1);
1749        assert_eq!(unvisited.classified(slot, &a, computes(1)), 1);
1750        assert_eq!(
1751            runs.get(),
1752            9,
1753            "a cache lent without a visit computes every ask"
1754        );
1755
1756        let chain_b = [root, a, body];
1757        let walk_b = Ancestors::for_walk(&chain_b, &b, &cache);
1758        assert_eq!(walk_b.classified(slot, &b, computes(2)), 2);
1759        assert_eq!(walk_b.classified(slot, &b, computes(9)), 2);
1760        assert_eq!(
1761            runs.get(),
1762            10,
1763            "the new visit's first ask computes, the next is served"
1764        );
1765        assert_eq!(walk_b.classified(slot, &a, computes(1)), 1);
1766        assert_eq!(runs.get(), 11, "the retired node is computed again");
1767    }
1768
1769    /// `of_children` hands a body's members the chain that is their own:
1770    /// `parent` on a member is the body, where the body's chain would
1771    /// name the body's parent instead — the shape `npa` / `npm` ask a
1772    /// row about every member under. The derived chain keeps the walk's
1773    /// fold cache, as `below` does, and without a known chain it climbs.
1774    #[cfg(feature = "rust")]
1775    #[test]
1776    fn of_children_names_the_body_as_each_member_s_parent() {
1777        let tree = Tree::new::<crate::langs::RustCode>(b"struct S { a: i32, b: i32 }\n");
1778        let root = tree.get_root();
1779        let item = root.child(0).expect("the struct item");
1780        let body = item
1781            .children()
1782            .find(|child| child.kind() == "field_declaration_list")
1783            .expect("the field list");
1784        let field = body
1785            .children()
1786            .find(|child| child.kind() == "field_declaration")
1787            .expect("a field");
1788
1789        let chain = [root, item];
1790        let cache = FoldCache::default();
1791        let walk = Ancestors::known(&chain).with_folds(&cache);
1792        assert_eq!(
1793            walk.parent(&body).map(|p| p.id()),
1794            Some(item.id()),
1795            "the body's own chain names the item"
1796        );
1797        let under = walk.of_children(&body);
1798        let members = under.get();
1799        assert_eq!(
1800            members.parent(&field).map(|p| p.id()),
1801            Some(body.id()),
1802            "a member's chain names the body"
1803        );
1804        assert_eq!(members.depth(), Some(3), "root, item, body");
1805        assert!(
1806            members.memoises_folds(),
1807            "the derived chain keeps the walk's fold cache"
1808        );
1809        assert_eq!(
1810            Ancestors::unknown()
1811                .of_children(&body)
1812                .get()
1813                .parent(&field)
1814                .map(|p| p.id()),
1815            Some(body.id()),
1816            "without a chain the derived one climbs to the same parent"
1817        );
1818    }
1819
1820    /// `descend` / `ascend` move a held chain into a child and back
1821    /// (#1401): under the child, the child's children name it as their
1822    /// parent at one more depth; after ascending, the body's own
1823    /// members do again. Without a known chain there is no chain to
1824    /// move, so the depth stays unknown and the answers keep climbing.
1825    /// The floor's debug assertion is `ascending_past_the_floor_is_caught`;
1826    /// the release-build clamp behind it runs only where that
1827    /// assertion is compiled out, so no test in the gate observes it.
1828    #[cfg(feature = "rust")]
1829    #[test]
1830    fn descend_and_ascend_move_the_held_chain_within_its_floor() {
1831        let tree = Tree::new::<crate::langs::RustCode>(b"fn f() { if a { g(); } }\n");
1832        let root = tree.get_root();
1833        let item = root.child(0).expect("the fn item");
1834        let body = item
1835            .children()
1836            .find(|child| child.kind() == "block")
1837            .expect("the body");
1838        let conditional = body
1839            .children()
1840            .find(|child| child.kind() == "expression_statement")
1841            .and_then(|stmt| stmt.child(0))
1842            .expect("the if");
1843        let consequence = conditional
1844            .children()
1845            .find(|child| child.kind() == "block")
1846            .expect("the consequence");
1847        let call = consequence
1848            .children()
1849            .find(|child| child.kind() == "expression_statement")
1850            .expect("the call statement");
1851
1852        let chain = [root, item];
1853        let mut under = Ancestors::known(&chain).of_children(&body);
1854        assert_eq!(under.get().depth(), Some(3), "root, item, body");
1855
1856        under.descend(&conditional);
1857        under.descend(&consequence);
1858        assert_eq!(under.get().depth(), Some(5), "root, item, body, if, block");
1859        assert_eq!(
1860            under.get().parent(&call).map(|p| p.id()),
1861            Some(consequence.id()),
1862            "under the consequence, its statements name it as their parent"
1863        );
1864
1865        under.ascend();
1866        under.ascend();
1867        assert_eq!(under.get().depth(), Some(3), "back at the body");
1868        assert_eq!(
1869            under.get().parent(&conditional).map(|p| p.id()),
1870            Some(body.id()),
1871            "the body's members name the body again"
1872        );
1873
1874        let mut unknown = Ancestors::unknown().of_children(&body);
1875        unknown.descend(&conditional);
1876        assert_eq!(
1877            unknown.get().depth(),
1878            None,
1879            "without a chain a descent records nothing"
1880        );
1881        unknown.ascend();
1882        assert_eq!(
1883            unknown.get().parent(&call).map(|p| p.id()),
1884            Some(consequence.id()),
1885            "and the answer still climbs"
1886        );
1887    }
1888
1889    /// The floor is the chain as built: an `ascend` with nothing to undo
1890    /// leaves the body's chain in place rather than popping the body —
1891    /// a debug build trips the assertion, which is what this pins.
1892    /// `descend` takes the chain into a child of its last entry and
1893    /// nothing else: a walker that descends into a sibling, or into the
1894    /// node already on top, would have every later gate read a parent
1895    /// the node does not have. A debug build trips the containment
1896    /// assertion, which names the offending kind.
1897    #[cfg(all(feature = "rust", debug_assertions))]
1898    #[test]
1899    #[should_panic(
1900        expected = "descended into a function_item node the chain's last entry does not contain"
1901    )]
1902    fn descending_outside_the_last_entry_is_caught() {
1903        let tree = Tree::new::<crate::langs::RustCode>(b"fn f() {}\nfn g() {}\n");
1904        let root = tree.get_root();
1905        let f = root.child(0).expect("the first fn item");
1906        let g = root.child(1).expect("the second fn item");
1907        let chain = [root];
1908        let mut under = Ancestors::known(&chain).of_children(&f);
1909        under.descend(&g);
1910    }
1911
1912    #[cfg(all(feature = "rust", debug_assertions))]
1913    #[test]
1914    #[should_panic(expected = "ascended above the node this chain was built for")]
1915    fn ascending_past_the_floor_is_caught() {
1916        let tree = Tree::new::<crate::langs::RustCode>(b"fn f() {}\n");
1917        let root = tree.get_root();
1918        let item = root.child(0).expect("the fn item");
1919        let chain = [root];
1920        let mut under = Ancestors::known(&chain).of_children(&item);
1921        under.ascend();
1922    }
1923}