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}