Skip to main content

big_code_analysis_ast/node/ancestors/
folds.rs

1//! The folds and memos an [`Ancestors`] chain answers through, and the
2//! [`FoldCache`] a walk lends for them. A fold answers a question about
3//! a node's whole ancestry down the chain once per walk, where a climb
4//! from every node that asks is quadratic in depth (#1597). A memo
5//! keeps one node's answer for the walk, and a word slot the visited
6//! node's. Tested in the parent module's `tests`.
7
8use std::cell::{Cell, RefCell};
9use std::collections::HashMap;
10
11use super::Ancestors;
12use super::chain::Chain;
13use crate::checker::Checker;
14use crate::node::Node;
15
16impl<'tree, 'chain> Ancestors<'tree, 'chain> {
17    /// The state of a fold of `step` down `node`'s ancestry, leaving out
18    /// the `skip` ancestors nearest `node`.
19    ///
20    /// The fold starts at `init` above the root and, for each ancestor
21    /// `a` from the root down, applies `step(state, a, a's chain, below)`,
22    /// where `below` is the next node on the path to `node` — the ancestor
23    /// under `a`, or `node` itself under its parent. A predicate that
24    /// would otherwise climb every ancestor of every candidate node, and
25    /// so cost `O(candidates × depth)`, asks this instead (#1597).
26    ///
27    /// Under a walk that lent a [`FoldCache`], the state at each ancestor
28    /// is stored per depth, keyed by the ancestor's id, so each one is
29    /// folded once per walk and a query costs amortised `O(1)` steps. A
30    /// state is the fold over the ancestors *above* its key, so `step`
31    /// runs for an ancestor once per child of it the walk asks from, and
32    /// for every ancestor on the chain whatever it answers. A step that
33    /// scans is therefore rescanned per child; a question the nearest
34    /// ancestor settles belongs on
35    /// [`nearest_level_answer`](Self::nearest_level_answer) (#1863).
36    ///
37    /// A node fixes its own ancestry, so a stored state whose id matches
38    /// the chain is exact; a slot left by a node the walk has moved past
39    /// holds another id and is refolded. `step` must answer the same for
40    /// every call on one `lane` within a walk. It may fold on another
41    /// lane, memoised; a fold on its own lane is answered unmemoised.
42    /// The state at `node` (`skip == 0`) depends on `node`, so it is
43    /// folded fresh. Without a known chain the ancestry is climbed with
44    /// [`Node::parent`] first, which is `O(depth²)` per query; only tests
45    /// and chainless callers reach that path, never the metrics walk.
46    pub(crate) fn fold_down(
47        self,
48        node: &Node<'tree>,
49        skip: usize,
50        lane: FoldLane,
51        init: u8,
52        step: impl Fn(u8, &Node<'tree>, Ancestors<'tree, 'chain>, &Node<'tree>) -> u8,
53    ) -> u8 {
54        let Some(chain) = self.chain else {
55            return fold_climbed(node, skip, init, step);
56        };
57        let end = chain.len().saturating_sub(skip);
58        // The cache travels into `outer`, as it does through
59        // `AncestorIter`, so a step that folds on another lane is
60        // memoised too. Each lane is its own cell, so that fold borrows
61        // nothing this one holds; a step folding on *this* lane finds it
62        // borrowed and runs unmemoised instead (`FoldCache::fold`).
63        let step_at = |state: u8, depth: usize| {
64            step(
65                state,
66                &chain[depth],
67                self.above(depth),
68                chain.get(depth + 1).unwrap_or(node),
69            )
70        };
71        match self.folds {
72            Some(cache) => cache.fold(lane, chain, end, init, step_at),
73            None => (0..end).fold(init, step_at),
74        }
75    }
76
77    /// Whether an ancestor of `node` satisfies `check` before one
78    /// satisfies `stop`, nearest first, an `else if`'s inner `if` never
79    /// counting — what `node.count_specific_ancestors::<C>(self, check,
80    /// stop) > 0` answers.
81    ///
82    /// That climb stops at the nearest `stop`, which bounds it only where
83    /// one is near. A shape with none — a declaration in nested C++
84    /// namespaces, any TypeScript declaration asked whether it is
85    /// ambient — climbs to the root from every node and is quadratic in
86    /// depth (#1767). Under a walk that lent a [`FoldCache`] this folds
87    /// the answer down the chain on `lane` instead, each ancestor once
88    /// per child the walk asks under: a `stop` resets it, a `check` sets
89    /// it, and both are kind tests. Elsewhere the
90    /// climb is the cheaper of the two and is what runs, so a caller
91    /// with no cache keeps the climb's cost.
92    ///
93    /// A lane memoises whatever its first asker folded, so each
94    /// [`GateLane`] belongs to one question: one `check` / `stop` pair
95    /// and checker per walk. Both are plain `fn`s because the memo is
96    /// only sound for a pure function of the ancestor; a closure that
97    /// captured the asking node would hand every later node the first
98    /// one's answer. The `else if` exclusion is kept for parity with the
99    /// climb; no current asker can observe it.
100    #[doc(hidden)]
101    pub fn has_ancestor_before_stop<C: Checker>(
102        self,
103        node: &Node<'tree>,
104        lane: GateLane,
105        check: fn(&Node) -> bool,
106        stop: fn(&Node) -> bool,
107    ) -> bool {
108        self.ancestor_before_stop::<C>(node, lane.fold_lane(), check, stop)
109    }
110
111    /// [`has_ancestor_before_stop`](Self::has_ancestor_before_stop) on any
112    /// lane, for this crate's own questions.
113    pub(crate) fn ancestor_before_stop<C: Checker>(
114        self,
115        node: &Node<'tree>,
116        lane: FoldLane,
117        check: fn(&Node) -> bool,
118        stop: fn(&Node) -> bool,
119    ) -> bool {
120        if !self.memoises_folds() {
121            return node.count_specific_ancestors::<C>(self, check, stop) > 0;
122        }
123        self.fold_down(node, 0, lane, 0, |held, ancestor, outer, _| {
124            if stop(ancestor) {
125                0
126            } else if check(ancestor) && !C::is_else_if(ancestor, outer) {
127                1
128            } else {
129                held
130            }
131        }) == 1
132    }
133
134    /// Whether any ancestor of `node` has one of `kinds` — the question
135    /// with no stop at all, which a nearest-first scan answers in a step
136    /// or two where such an ancestor is near and by reading the whole
137    /// chain where there is none: a function in each of `n` nested
138    /// containers scanned `n²` entries (#1864). Under a walk that lent a
139    /// [`FoldCache`] the answer is folded down the chain on `lane`, each
140    /// ancestor's kind once per child the walk asks under; elsewhere the
141    /// scan is what runs, since an unmemoised fold would start at the
142    /// root for every ask.
143    ///
144    /// A lane memoises whatever its first asker folded, so every ask on
145    /// `lane` within one walk must pass the same `kinds`: each
146    /// [`KindLane`] belongs to one question and one list. The list is
147    /// `'static` data rather than a predicate so that no ask can build
148    /// it from the asking node; choosing between two lists per node is
149    /// still the caller's to avoid. `make chain-audit` checks every
150    /// folded answer against the scan, which is what catches a lane
151    /// asked with a second list wherever the two answer differently.
152    #[doc(hidden)]
153    #[must_use]
154    pub fn has_ancestor_of_kind(
155        self,
156        node: &Node<'tree>,
157        lane: KindLane,
158        kinds: &'static [u16],
159    ) -> bool {
160        let scan = || {
161            self.iter(node)
162                .any(|(ancestor, _)| kinds.contains(&ancestor.kind_id()))
163        };
164        if !self.memoises_folds() {
165            return scan();
166        }
167        let folded = self.fold_down(node, 0, lane.fold_lane(), 0, |held, ancestor, _, _| {
168            u8::from(held == 1 || kinds.contains(&ancestor.kind_id()))
169        }) == 1;
170        // Opt-in only, as the exact check in `for_walk_chain_only` is:
171        // the scan is the `O(depth)` per ask the fold exists to remove.
172        #[cfg(chain_audit)]
173        assert_eq!(
174            folded,
175            scan(),
176            "the {lane:?} fold disagrees with the scan on a {} node: a lane \
177             holds one kind list per walk",
178            node.kind()
179        );
180        folded
181    }
182
183    /// The answer of the nearest ancestor of `node` that has one, or
184    /// `false` where none does: what
185    /// `self.iter(node).find_map(|(level, chain)| answer(code, &level,
186    /// chain)).unwrap_or(false)` answers. `node` itself is not asked.
187    ///
188    /// That climb stops at the first ancestor that answers, which bounds
189    /// it only where one is near. A node asked from each level of a nest
190    /// whose levels answer nothing — a parenthesis in each of `n`
191    /// parentheses around a Python docstring, each asking whether code
192    /// precedes it on its logical line — climbs the nest from every
193    /// level and is quadratic in its depth (#1863). Under a walk that
194    /// lent a [`FoldCache`] the climb is memoised per level on
195    /// `question`: it stops at the first level that answers or already
196    /// holds an answer, and hands what it found to every level it
197    /// passed. So `answer` runs at most once per level per walk, and
198    /// never on a level above the nearest one that answers.
199    ///
200    /// A fold ([`fold_down`](Self::fold_down)) does not fit this
201    /// question: it evaluates every ancestor, the ones above the nearest
202    /// answer included, and stores an ancestor's state under the child
203    /// on the path, so a level whose answer is a long scan is scanned
204    /// again for each child asked from.
205    ///
206    /// The memo is keyed by the level alone and hands every later asker
207    /// the first one's answer. Three things follow. Each
208    /// [`LevelQuestion`] belongs to one `answer` per walk. `answer` is a
209    /// plain `fn` of the source, the ancestor and the ancestor's own
210    /// chain: a closure that captured the asking node would answer for
211    /// it at every level. And `self` must be `node`'s whole ancestry: a
212    /// chain re-rooted part-way (`below`) runs off its top early, and
213    /// "no level answers" would be stored on levels whose real ancestors
214    /// do answer. Nothing checks that last one, since the audit's climb
215    /// reads the same chain; no caller asks from a re-rooted chain.
216    /// `make chain-audit` checks every memoised answer against the
217    /// climb.
218    #[doc(hidden)]
219    #[must_use]
220    pub fn nearest_level_answer(
221        self,
222        node: &Node<'tree>,
223        question: LevelQuestion,
224        code: &[u8],
225        answer: fn(&[u8], &Node<'tree>, Ancestors<'tree, 'chain>) -> Option<bool>,
226    ) -> bool {
227        let climb = || {
228            self.iter(node)
229                .find_map(|(level, chain)| answer(code, &level, chain))
230                .unwrap_or(false)
231        };
232        let Some(memo) = self.node_memo(question.memo_question()) else {
233            return climb();
234        };
235        // The levels passed without an answer are counted, not listed:
236        // they are the first `deferred` of the same iteration.
237        let mut deferred = 0;
238        let mut found = false;
239        for (level, chain) in self.iter(node) {
240            if let Some(known) = memo.get(&level) {
241                found = known;
242                break;
243            }
244            if let Some(own) = answer(code, &level, chain) {
245                memo.set(&level, own);
246                found = own;
247                break;
248            }
249            deferred += 1;
250        }
251        for (level, _) in self.iter(node).take(deferred) {
252            memo.set(&level, found);
253        }
254        // Opt-in only: the climb is the `O(depth)` per ask the memo
255        // exists to remove.
256        #[cfg(chain_audit)]
257        assert_eq!(
258            found,
259            climb(),
260            "the {question:?} memo disagrees with the climb on a {} node: a \
261             question holds one answer fn per walk",
262            node.kind()
263        );
264        found
265    }
266
267    /// The walk's memo for `question`, when it lent a [`FoldCache`].
268    pub(crate) fn node_memo(self, question: MemoQuestion) -> Option<&'chain NodeMemo> {
269        self.folds.map(|cache| &cache.nodes[question as usize])
270    }
271
272    /// `answer` for `node` under `question`, read from the walk's memo
273    /// where it lent one and recorded there after the first ask; computed
274    /// every time on a chain with no cache.
275    pub(crate) fn memoised(
276        self,
277        question: MemoQuestion,
278        node: &Node<'_>,
279        answer: impl FnOnce() -> bool,
280    ) -> bool {
281        let memo = self.node_memo(question);
282        if let Some(known) = memo.and_then(|memo| memo.get(node)) {
283            return known;
284        }
285        let answer = answer();
286        if let Some(memo) = memo {
287            memo.set(node, answer);
288        }
289        answer
290    }
291
292    /// [`memoised`](Self::memoised) on a [`NodeQuestion`], for the metric
293    /// crate's own per-node questions. `answer` must be a pure function
294    /// of `node` and the source for one walk: the memo hands every later
295    /// asker the first one's answer.
296    #[doc(hidden)]
297    pub fn memoised_answer(
298        self,
299        question: NodeQuestion,
300        node: &Node<'_>,
301        answer: impl FnOnce() -> bool,
302    ) -> bool {
303        self.memoised(question.memo_question(), node, answer)
304    }
305
306    /// `classify(node)`'s discriminant under `slot`. When `node` is the
307    /// one the walk is visiting, as its constructor recorded
308    /// ([`for_walk`](Self::for_walk),
309    /// [`for_walk_without_siblings`](Self::for_walk_without_siblings)), the
310    /// answer is read from the walk's word slot after the first ask and
311    /// recorded there by it; an ask about any other node is computed and
312    /// not stored, so it never evicts the visited node's answer (#1737).
313    /// Computed every time on a chain with no cache, or one lent without
314    /// a visit. The caller converts the `u8` back to its enum; `classify`
315    /// must be a pure function of the node and the source for one walk.
316    pub(crate) fn classified(
317        self,
318        slot: WordSlot,
319        node: &Node<'_>,
320        classify: impl FnOnce() -> u8,
321    ) -> u8 {
322        let Some(cache) = self.folds.filter(|cache| cache.visited.get() == node.id()) else {
323            return classify();
324        };
325        let cell = &cache.words[slot as usize];
326        let (id, answer) = cell.get();
327        // Id 0 marks an empty slot: a tree-sitter node id is its address,
328        // never 0.
329        if id == node.id() {
330            return answer;
331        }
332        let answer = classify();
333        cell.set((node.id(), answer));
334        answer
335    }
336
337    /// Whether [`fold_down`](Self::fold_down) is memoised on this chain:
338    /// one a walk lent a [`FoldCache`] with. Otherwise every fold runs
339    /// from the root, so a predicate whose own climb is bounded takes that
340    /// instead.
341    pub(crate) fn memoises_folds(self) -> bool {
342        self.folds.is_some() && self.chain.is_some()
343    }
344}
345
346// The deepest depth at or above `from` whose slot still holds the state of
347// the ancestor the chain has there, or 0 when none does: a node fixes its
348// ancestry, so a matching id is an exact state.
349fn deepest_stored(slots: &[(usize, u8)], chain: Chain<'_, '_>, from: usize) -> usize {
350    (1..=from)
351        .rev()
352        .find(|&depth| {
353            fold_slot_probes::record();
354            slots[depth].0 == chain[depth].id()
355        })
356        .unwrap_or(0)
357}
358
359// `Ancestors::fold_down` for a caller that holds no chain: the ancestry is
360// climbed first and folded unmemoised.
361fn fold_climbed<'tree, 'chain>(
362    node: &Node<'tree>,
363    skip: usize,
364    init: u8,
365    step: impl Fn(u8, &Node<'tree>, Ancestors<'tree, 'chain>, &Node<'tree>) -> u8,
366) -> u8
367where
368    'tree: 'chain,
369{
370    let climbed = climbed_chain(node);
371    let end = climbed.len().saturating_sub(skip);
372    (0..end).fold(init, |state, depth| {
373        let below = climbed.get(depth + 1).unwrap_or(node);
374        step(state, &climbed[depth], Ancestors::unknown(), below)
375    })
376}
377
378// `node`'s ancestors, root first, climbed with `Node::parent` for a caller
379// that holds no chain. tree-sitter finds a parent by descending from the
380// root, so the climb is `O(depth²)`.
381pub(super) fn climbed_chain<'tree>(node: &Node<'tree>) -> Vec<Node<'tree>> {
382    let mut climbed: Vec<_> = std::iter::successors(node.parent(), Node::parent).collect();
383    climbed.reverse();
384    climbed
385}
386
387/// The ancestor questions the metric crate asks through
388/// [`Ancestors::has_ancestor_before_stop`], one per lane of the walk's
389/// [`FoldCache`]. A subset of [`FoldLane`], so a caller outside this
390/// crate cannot name a lane another fold owns.
391#[doc(hidden)]
392#[non_exhaustive]
393#[derive(Clone, Copy, Debug, PartialEq, Eq)]
394pub enum GateLane {
395    /// Whether a declaration sits in a loop or `if` header — a `for`
396    /// initializer — with no statement block between: the C family
397    /// and Go. One lane serves all because a walk parses one language.
398    InsideHeader,
399    /// JS family: whether a declaration sits in an `export` statement
400    /// with no statement block between.
401    InsideExport,
402    /// TypeScript: whether a declaration sits anywhere inside an
403    /// ambient `declare`.
404    InsideAmbient,
405    /// Python: whether a boolean operator sits inside another before a
406    /// `lambda`, so a chain is paid for once, at its outermost operator.
407    InsideBooleanChain,
408}
409
410impl GateLane {
411    const fn fold_lane(self) -> FoldLane {
412        match self {
413            Self::InsideHeader => FoldLane::InsideHeader,
414            Self::InsideExport => FoldLane::InsideExport,
415            Self::InsideAmbient => FoldLane::InsideAmbient,
416            Self::InsideBooleanChain => FoldLane::InsideBooleanChain,
417        }
418    }
419}
420
421/// The ancestor questions the metric crate asks through
422/// [`Ancestors::has_ancestor_of_kind`], one per lane of the walk's
423/// [`FoldCache`]. Its own enum rather than more [`GateLane`] variants:
424/// both entry points store the same two states, so a lane passed to the
425/// wrong one would hand each question the other's memo.
426#[doc(hidden)]
427#[non_exhaustive]
428#[derive(Clone, Copy, Debug, PartialEq, Eq)]
429pub enum KindLane {
430    /// Whether a function definition sits inside another function, at
431    /// any distance: the cognitive depth surcharge of every language
432    /// with a function-definition kind. One lane serves all because a
433    /// walk parses one language, and each passes one list.
434    InsideFunction,
435}
436
437impl KindLane {
438    const fn fold_lane(self) -> FoldLane {
439        match self {
440            Self::InsideFunction => FoldLane::InsideFunction,
441        }
442    }
443}
444
445/// Which memoised fold a [`FoldCache`] slot holds. A language may run
446/// more than one fold over the same walk, and two folds' states must not
447/// share a slot.
448#[derive(Clone, Copy, Debug, PartialEq, Eq)]
449pub(crate) enum FoldLane {
450    /// Whether an ancestor holds a doc comment in a function body.
451    DocInBody,
452    /// A positional language's declaration scope: Go's package level,
453    /// Ruby's YARD namespace. One lane serves both because a walk parses
454    /// one language.
455    DocScope,
456    /// Python: the climb from a node through the parentheses above it to
457    /// a bare string statement (#1610).
458    BareStringClimb,
459    /// Elixir: whether an ancestor is a `quote do … end` call, under
460    /// which a `def` is a template rather than a definition.
461    InsideQuote,
462    /// [`GateLane::InsideHeader`].
463    InsideHeader,
464    /// [`GateLane::InsideExport`].
465    InsideExport,
466    /// [`GateLane::InsideAmbient`].
467    InsideAmbient,
468    /// [`GateLane::InsideBooleanChain`].
469    InsideBooleanChain,
470    /// JS family: whether a function expression or arrow meets a name
471    /// binding before a positional frame.
472    NamedBinding,
473    /// Python: how many `lambda`s enclose a node before the nearest
474    /// statement boundary, saturating (#1767).
475    LambdaDepth,
476    /// [`KindLane::InsideFunction`].
477    InsideFunction,
478}
479
480impl FoldLane {
481    /// How many lanes a [`FoldCache`] holds; one per variant above.
482    const COUNT: usize = 11;
483}
484
485// A lane past `COUNT` would index out of the array at run time, on the
486// first walk that folds on it; this makes a variant added without the
487// bump a build error instead.
488const _: () = assert!(FoldLane::InsideFunction as usize + 1 == FoldLane::COUNT);
489
490/// Which memoised per-node question a [`FoldCache`] [`NodeMemo`] holds.
491/// Two questions asked of the same node must not share a slot, so each
492/// has a memo of its own. A [`NodeQuestion`] or one of this crate's own
493/// stores the node's answer; a [`LevelQuestion`] the nearest answer at
494/// or above it.
495#[derive(Clone, Copy, Debug, PartialEq, Eq)]
496pub(crate) enum MemoQuestion {
497    /// Doxygen: whether a preprocessor conditional holds an entry, in
498    /// any branch and at any depth (#1613).
499    ConditionalDeclares,
500    /// Tcl family: whether a `word_list`'s own slot sequence can be read
501    /// positionally — no `ERROR` or MISSING child of its own (#1686).
502    ArgumentSlotsReadable,
503    /// Tcl: whether a `word_list` is a brace-list `switch`'s — holds
504    /// exactly one `braced_word`, the arm list — asked once per arm by
505    /// the `CaseArm` row (#1695).
506    SwitchArmList,
507    /// Elixir: whether a `when` operator sits in a guard position — the
508    /// outermost of a repeated-guard chain decides for every nested one,
509    /// so each is asked once rather than climbing the chain per token
510    /// (#1695).
511    GuardOperator,
512    /// JS family: whether an arrow's *parent* holds a `property_identifier`
513    /// child — the name an unbound arrow is bound to. Asked of the parent
514    /// once per arrow under it, and the scan is `O(width)` over the
515    /// parent's children, so `run(() => 1, …, () => n)` asked it `n`
516    /// times of one `arguments` and was quadratic (#1696 review).
517    NamesAnArrow,
518    /// Elixir: whether a `keywords` list holds a `do:` pair — what makes
519    /// its `else:` / `rescue:` / `catch:` siblings a block-equivalent
520    /// section. Asked of the list once per pair in it, and the scan is
521    /// `O(width)` over the list (#1602).
522    KeywordListHasDo,
523    /// Elixir: whether a Call argument is followed by no operand — the
524    /// position a keyword list must hold to be the Call's sections.
525    /// Asked of the argument once per pair in it, and the scan is
526    /// `O(siblings)` over whatever trails it, comments included (#1602
527    /// review).
528    ArgumentIsTrailing,
529    /// Elixir: whether a bracketed argument's keyword list is the first
530    /// operand in its brackets — `[do: 1, else: 2]` holds pairs alone,
531    /// `[1, do: 1]` is a plain list. Asked of the list once per pair in
532    /// it, and the scan is `O(siblings)` over what precedes the pairs,
533    /// comments included (#1697 cost audit).
534    KeywordsLeadTheirList,
535    /// [`NodeQuestion::BareStringParenthesisLine`].
536    BareStringParenthesisLine,
537    /// [`LevelQuestion::CodeBeforeOnLine`].
538    CodeBeforeOnLine,
539    /// [`LevelQuestion::InConstBinding`].
540    InConstBinding,
541}
542
543impl MemoQuestion {
544    /// How many memos a [`FoldCache`] holds; one per variant above.
545    const COUNT: usize = 11;
546}
547
548const _: () = assert!(MemoQuestion::InConstBinding as usize + 1 == MemoQuestion::COUNT);
549
550/// The per-node questions the metric crate memoises through
551/// [`Ancestors::memoised_answer`], one per [`MemoQuestion`] memo of the
552/// walk's [`FoldCache`]. A subset of [`MemoQuestion`], as [`GateLane`]
553/// is of [`FoldLane`], so a caller outside this crate cannot name a memo
554/// another question owns.
555#[doc(hidden)]
556#[non_exhaustive]
557#[derive(Clone, Copy, Debug, PartialEq, Eq)]
558pub enum NodeQuestion {
559    /// Python: whether a bare `\` run that starts a logical line inside
560    /// a parenthesised bare string's parentheses is the string's line
561    /// with no code before the string on it. A function of the
562    /// parenthesis alone, asked once per run it holds; each ask climbed
563    /// from the run past every earlier run and comment in the
564    /// parenthesis, quadratic in them (fourth re-review of #1819).
565    BareStringParenthesisLine,
566}
567
568impl NodeQuestion {
569    const fn memo_question(self) -> MemoQuestion {
570        match self {
571            Self::BareStringParenthesisLine => MemoQuestion::BareStringParenthesisLine,
572        }
573    }
574}
575
576/// The "nearest ancestor that answers" questions the metric crate asks
577/// through [`Ancestors::nearest_level_answer`], one per [`MemoQuestion`]
578/// memo of the walk's [`FoldCache`]. Its own enum, apart from
579/// [`NodeQuestion`]: that entry point stores a node's own answer and
580/// this one the nearest answer at or above it, so a question passed to
581/// the wrong one would hand each the other's memo.
582#[doc(hidden)]
583#[non_exhaustive]
584#[derive(Clone, Copy, Debug, PartialEq, Eq)]
585pub enum LevelQuestion {
586    /// Python: whether code precedes a node on its logical line, read
587    /// at the nearest level above it that has a token before its node.
588    CodeBeforeOnLine,
589    /// JS family: whether a destructuring pattern belongs to a `const`
590    /// binding, read at the nearest ancestor that is no pattern layer.
591    /// A default's `=` at each of `n` nested patterns climbed to the
592    /// declarator from every level (#1868). One question serves the
593    /// four grammars because a walk parses one language.
594    InConstBinding,
595}
596
597impl LevelQuestion {
598    const fn memo_question(self) -> MemoQuestion {
599        match self {
600            Self::CodeBeforeOnLine => MemoQuestion::CodeBeforeOnLine,
601            Self::InConstBinding => MemoQuestion::InConstBinding,
602        }
603    }
604}
605
606/// The per-depth states of the walk's memoised folds, for
607/// `Ancestors::fold_down` (#1597), the per-node memos for
608/// `Ancestors::node_memo`, and the word slots keyed on the node the
609/// walk is visiting (`Ancestors::classified`).
610///
611/// One slot per depth and lane, keyed by the id of the ancestor at that
612/// depth: the state folded over every ancestor above it. Interior
613/// mutability, because [`Ancestors`] lends it shared, as it lends a
614/// [`SiblingCache`]. One cell per lane, because a fold's step may ask a
615/// question another lane memoises — the JS family's doc-in-body fold
616/// asks whether each ancestor is a function — and that fold must not
617/// find its lane borrowed by the one in progress.
618///
619/// [`SiblingCache`]: super::SiblingCache
620#[derive(Debug, Default)]
621pub struct FoldCache {
622    lanes: [RefCell<Vec<(usize, u8)>>; FoldLane::COUNT],
623    nodes: [NodeMemo; MemoQuestion::COUNT],
624    words: [Cell<(usize, u8)>; WordSlot::COUNT],
625    /// The id of the node the walk is visiting, as [`Ancestors::for_walk`]
626    /// or [`Ancestors::for_walk_without_siblings`] last recorded it; 0 —
627    /// no node's id — until a walk records one.
628    visited: Cell<usize>,
629}
630
631/// The text-classified constructs whose answer for the visited node a
632/// walk keeps (#1697, #1737). A grammar that spells `if`, `switch` or
633/// `return` as a generic `call` / `command` told apart only by its
634/// target text is asked the same question of the same node by every
635/// metric that runs on it — four reads of one field and one text
636/// compare where a kind-based language pays none. One slot holding the
637/// visited node's id and its answer serves them all, however many asks
638/// about *other* nodes arrive in between: an ask about a node the walk
639/// is not visiting (a consumer reading the enclosing call, a module
640/// reading its statements) is computed and not stored, so it costs its
641/// one read and nothing else. Keying on the visit, which
642/// [`Ancestors::for_walk`] and [`Ancestors::for_walk_without_siblings`]
643/// record, is what makes that so — before
644/// #1737 the slot held the *last node asked* and such an ask evicted
645/// the visited node's answer, which made "may this site use the cached
646/// read" a judgement per call site. No map, no allocation, `O(1)`
647/// memory, dropped with the walk.
648///
649/// The bound is one read per (consumer, target) per visit. The
650/// last-asked slot served two cross-visit shapes for free that this
651/// one does not — a keyword pair's enclosing call asked by each of its
652/// sections, an `else` token's `if` — so a file of `N` keyword
653/// sections or `N` if-else blocks pays `N` more reads than it did,
654/// linear either way (`cognitive/elixir-keyword-sections` prices it:
655/// 1.03 → 1.12, within noise on every fixture measured). That is
656/// accepted because the visited path dominates: an Elixir `call` is
657/// asked four to seven times while visited, and the typed
658/// `NodeMemo<T>` fold #1737 offered as its second option would put a
659/// `HashMap` probe on every one of those asks to save the tens of
660/// nanoseconds the two cross-visit shapes re-read — measured on the
661/// #1737 branch, not assumed, which is why the slot stays a `Cell`.
662///
663/// The slot holds the classification's `#[repr(u8)]` discriminant; the
664/// enum is the language helper's (`ElixirCallTarget`, `TclCommandWord`),
665/// which also owns the conversion back.
666#[derive(Clone, Copy, Debug, PartialEq, Eq)]
667pub(crate) enum WordSlot {
668    /// Elixir: what a `call`'s `target` identifier spells.
669    ElixirCallTarget,
670    /// Tcl: what a `command`'s leading `simple_word` spells.
671    TclCommandWord,
672}
673
674impl WordSlot {
675    /// How many slots a [`FoldCache`] holds; one per variant above.
676    const COUNT: usize = 2;
677}
678
679const _: () = assert!(WordSlot::TclCommandWord as usize + 1 == WordSlot::COUNT);
680
681/// Answers that are a fact of one node, memoised for one walk and keyed
682/// by node id, which is unique within a tree. Most are about the node's
683/// own subtree: Doxygen's "does this preprocessor conditional hold an
684/// entry", asked of every conditional a doc comment's stretch meets;
685/// the Tcl family's "can this argument list be read by position", asked
686/// by every braced word in it. A [`LevelQuestion`]'s is about the
687/// node's ancestry instead: the nearest answer at or above it, which
688/// [`Ancestors::nearest_level_answer`] stores only from a whole chain.
689/// Unlike a [`FoldLane`] slot the entry is not keyed by depth, so an
690/// answer stored for one sibling subtree serves every later question
691/// about it (#1613). Each holds one [`MemoQuestion`].
692#[derive(Debug, Default)]
693pub(crate) struct NodeMemo(RefCell<HashMap<usize, bool>>);
694
695impl NodeMemo {
696    /// The stored answer for `node`, if any.
697    pub(crate) fn get(&self, node: &Node<'_>) -> Option<bool> {
698        self.0.borrow().get(&node.id()).copied()
699    }
700
701    /// Stores `answer` for `node`.
702    pub(crate) fn set(&self, node: &Node<'_>, answer: bool) {
703        self.0.borrow_mut().insert(node.id(), answer);
704    }
705}
706
707impl FoldCache {
708    /// Records `node` as the one the walk is visiting, which the word
709    /// slots serve. The walk constructors call it, and nothing else
710    /// writes the visit (#1737).
711    pub(super) fn record_visit(&self, node: &Node<'_>) {
712        self.visited.set(node.id());
713    }
714
715    // The state after folding `step(state, depth)` over `chain[..end]`,
716    // reusing and storing the per-depth states on `lane`.
717    //
718    // The lane stays borrowed while `step` runs, so a step that folds on
719    // the same lane would otherwise panic on the second borrow; it folds
720    // unmemoised instead, which answers the same. No step does today, and
721    // the cost of one that did is the step's own: a step that re-enters
722    // at one ancestor pays a plain fold of that prefix, one that re-enters
723    // at every ancestor pays `2^depth`, since nothing a re-entered lane
724    // can store cuts the recursion short. Neither shows as a wrong answer,
725    // so debug builds refuse the shape: the whole test corpus then guards
726    // the contract.
727    fn fold(
728        &self,
729        lane: FoldLane,
730        chain: Chain<'_, '_>,
731        end: usize,
732        init: u8,
733        step: impl Fn(u8, usize) -> u8,
734    ) -> u8 {
735        let Ok(mut slots) = self.lanes[lane as usize].try_borrow_mut() else {
736            debug_assert!(
737                same_lane_reentry::allowed(),
738                "a fold step re-entered its own lane {lane:?}"
739            );
740            return (0..end).fold(init, step);
741        };
742        // `slots[d]` is the state at `chain[d]`: folded over `chain[..d]`.
743        // Depth 0 is `init`; the state at `node` itself is never stored.
744        let memo_end = end.min(chain.len().saturating_sub(1));
745        if slots.len() <= memo_end {
746            // Id 0 marks an empty slot: a tree-sitter node id is its
747            // address, never 0.
748            slots.resize(memo_end + 1, (0, 0));
749        }
750        let mut depth = deepest_stored(&slots, chain, memo_end);
751        let mut state = if depth == 0 { init } else { slots[depth].1 };
752        while depth < memo_end {
753            fold_steps::record();
754            state = step(state, depth);
755            depth += 1;
756            slots[depth] = (chain[depth].id(), state);
757        }
758        if end > memo_end {
759            state = step(state, memo_end);
760        }
761        state
762    }
763}
764
765// Ancestor states a memoised fold computes and stores, so a test can see
766// a walk fold each ancestor once rather than once per asking node: the
767// answers are identical either way (#1767). Readable from the root
768// crate's tests through `test-support`, since most walks that lend the
769// cache live there.
770crate::observation::counter!(fold_steps, cfg(any(test, feature = "test-support")));
771
772// Stored states a memoised fold compares against the chain to find where
773// to resume. `fold_steps` cannot see a search that reads more slots than
774// it then refolds — one started at the root, say — which costs `O(depth)`
775// per ask with every state still stored once (#1864 review).
776crate::observation::counter!(fold_slot_probes, cfg(any(test, feature = "test-support")));
777
778/// Whether a fold may re-enter its own lane: refused everywhere, except
779/// on a thread where the one test that pins the fallback has opted in.
780/// A flag in every build rather than a `cfg(test)` branch, because the
781/// root crate's tests compile this crate without `cfg(test)`, and a
782/// branch they can never take reads as a line no test reaches.
783pub(super) mod same_lane_reentry {
784    use std::cell::Cell;
785
786    thread_local! {
787        static ALLOWED: Cell<bool> = const { Cell::new(false) };
788    }
789
790    pub(super) fn allowed() -> bool {
791        ALLOWED.get()
792    }
793
794    /// Opts the current thread in (`true`) or back out.
795    #[cfg(test)]
796    pub(in crate::node::ancestors) fn allow(allowed: bool) {
797        ALLOWED.set(allowed);
798    }
799}