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}