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