Skip to main content

big_code_analysis_ast/
node.rs

1// Metric counts (token, function, branch, argument, etc.) are stored as
2// `usize` and crossed with `f64` averages, ratios, and Halstead scores
3// across the cyclomatic / MI / Halstead computations. The `usize as f64`
4// and `f64 as usize` casts are intentional and snapshot-anchored — every
5// site is bounded by the count it came from. Allowing the lints at the
6// module level keeps the metric arithmetic legible.
7#![allow(
8    clippy::cast_precision_loss,
9    clippy::cast_possible_truncation,
10    clippy::cast_sign_loss
11)]
12
13//! Tree-sitter wrappers: `Tree`, [`Node`], [`Ancestors`], and the cursors.
14
15mod ancestors;
16mod parser_cache;
17
18pub use ancestors::{AncestorIter, Ancestors, ChildAncestors, FoldCache, SiblingCache};
19pub(crate) use ancestors::{FoldLane, MemoQuestion, NodeMemo, WordSlot};
20#[doc(hidden)]
21pub use ancestors::{
22    GateLane, KindLane, LevelQuestion, NodeQuestion, WIDE_PARENT, child_chains_derived,
23    fold_slot_probes, fold_steps, sibling_cache_reads, sibling_seeks,
24};
25
26use tree_sitter::Node as OtherNode;
27use tree_sitter::Tree as OtherTree;
28use tree_sitter::TreeCursor;
29
30use crate::checker::Checker;
31use crate::traits::{LanguageInfo, Search};
32
33use parser_cache::parse_on_scratch_parser;
34
35// Sibling lookups that resolved the parent from the node, on this
36// thread.
37//
38// [`Node::previous_sibling`] answers exactly what the chain-based
39// [`Ancestors::previous_sibling`] does, so no assertion on a metric
40// value can tell a walk that uses one from a walk that uses the
41// other — only the cost differs, and only on a deep tree. #1096 took
42// the last of these out of the metric bodies and #1447 out of the
43// `exclude_tests` prune, which #1100 had left calling one past a width
44// budget; the counter is what makes putting one back a test failure
45// rather than a silent quadratic.
46crate::observation::counter!(
47    node_resolved_sibling_lookups,
48    cfg(any(test, feature = "test-support"))
49);
50
51// Parent lookups that climbed from the node, on this thread.
52//
53// [`Node::parent`] answers what a chain's `last()` does, so a row gate
54// declared `no_chain` — no chain parameter to read — that climbs
55// with it answers identically under any chain its caller held, and no
56// comparison of the row's answers can see the climb (#1793). The
57// counter is what makes one a test failure: the derived suite asks
58// every `!CHAIN_GATED` row of every corpus candidate and asserts this
59// and the sibling counter above stay still.
60crate::observation::counter!(
61    node_resolved_parent_lookups,
62    cfg(any(test, feature = "test-support"))
63);
64
65// Child scans that built their own `TreeCursor`, on this thread.
66//
67// [`Node::children_with`] yields exactly what [`Node::children`] yields
68// — it exists to reuse one cursor across a traversal instead of
69// heap-allocating and freeing one per visited node, and no assertion on
70// a metric value can tell the two apart. #1112 moved the per-node
71// traversals that could hoist a cursor onto it; the counter is what
72// makes moving one back a test failure rather than a silent allocation
73// per node.
74//
75// All five consumers are guarded: `preorder` and `act_on_node` here,
76// `metrics::npa::python` and the suppression DFS through a `metrics()`
77// / `suppression_markers` call, and `output::dump`'s renderer from that
78// module's own tests. The accessor is `pub` (not `pub(super)`)
79// precisely so the last one can be asserted from where it lives — see
80// `crate::observation`.
81crate::observation::counter!(child_scan_cursors, cfg(any(test, feature = "test-support")));
82
83/// A parsed source tree wrapping a [`tree_sitter::Tree`].
84///
85/// The "open parse seam" (see issue #251) is reached by external
86/// callers through `big_code_analysis::Ast::from_tree_sitter`, which accepts a
87/// caller-built `tree_sitter::Tree` directly; this wrapper stays
88/// internal so the metric walker is the only thing that observes it.
89#[derive(Clone, Debug)]
90pub(crate) struct Tree(OtherTree);
91
92impl Tree {
93    /// # Panics
94    ///
95    /// When `T`'s per-language Cargo feature is disabled in this build.
96    ///
97    /// [`AnyParser::parse`](crate::langs::AnyParser::parse) and
98    /// [`AnyParser::from_tree`](crate::langs::AnyParser::from_tree)
99    /// cfg-gate each `LANG::*` arm and return
100    /// `Err(MetricsError::LanguageDisabled)` before reaching here, so
101    /// every path through `big_code_analysis::Ast` is safe. Since
102    /// #1376, though, `Parser<T>` and [`ParserTrait::new`] are `pub` in
103    /// this crate, so a caller that names a `*Parser` alias directly
104    /// bypasses that gate — check
105    /// [`LANG::is_enabled`](crate::LANG::is_enabled) first, or go
106    /// through `AnyParser` and match on the error.
107    pub(crate) fn new<T: LanguageInfo>(code: &[u8]) -> Self {
108        let language = T::lang().get_ts_language().expect(
109            "invariant: the caller checked LANG::is_enabled, or reached this through AnyParser",
110        );
111        Self(parse_on_scratch_parser(&language, code))
112    }
113
114    pub(crate) fn from_ts_tree(tree: OtherTree) -> Self {
115        Self(tree)
116    }
117
118    pub(crate) fn get_root(&self) -> Node<'_> {
119        Node(self.0.root_node())
120    }
121
122    pub(crate) fn as_ts_tree(&self) -> &OtherTree {
123        &self.0
124    }
125}
126
127/// An `AST` node.
128///
129/// The inner [`tree_sitter::Node`] is reached through
130/// [`Node::as_tree_sitter`] for advanced use cases that need direct
131/// access to the underlying tree-sitter API; the field itself is
132/// private so a `tree-sitter` version bump cannot silently reshape
133/// this struct's public layout.
134#[derive(Clone, Copy, Debug)]
135pub struct Node<'a>(OtherNode<'a>);
136
137impl<'a> Node<'a> {
138    /// Returns the underlying [`tree_sitter::Node`] for callers that
139    /// want to drive their own traversal alongside the metric walker.
140    ///
141    /// `tree_sitter::Node` is [`Copy`], so the node is returned by
142    /// value. The returned node borrows the same source-tree lifetime
143    /// as `self`.
144    ///
145    /// The `tree-sitter` re-export this exposes is *value-not-stable*:
146    /// the underlying pin may bump in any minor release, so node shape
147    /// and node-kind ids are not part of this crate's stability
148    /// contract (see the [`tree_sitter`] re-export
149    /// note in the crate root).
150    #[must_use]
151    #[inline]
152    pub fn as_tree_sitter(&self) -> OtherNode<'a> {
153        self.0
154    }
155
156    /// Checks if a node represents a syntax error or contains any syntax errors
157    /// anywhere within it.
158    ///
159    /// Transitive, which is the trap: asking it of a construct to decide
160    /// whether that construct's *own* shape is readable also answers `true`
161    /// for an error arbitrarily deep inside one of its children. Where the
162    /// question is about a node's own slot sequence, ask [`is_error`] /
163    /// [`is_missing`] of each slot instead (#1381).
164    ///
165    /// [`is_error`]: Self::is_error
166    /// [`is_missing`]: Self::is_missing
167    #[must_use]
168    pub fn has_error(&self) -> bool {
169        self.0.has_error()
170    }
171
172    /// Whether this node *is* the `ERROR` node, as opposed to
173    /// [`has_error`](Self::has_error)'s "is, or contains one".
174    #[must_use]
175    #[inline]
176    pub fn is_error(&self) -> bool {
177        self.0.is_error()
178    }
179
180    /// Whether the parser inserted this node during error recovery: a
181    /// zero-width token the source does not contain, standing in for one
182    /// the grammar required.
183    ///
184    /// A sibling of [`is_error`](Self::is_error) rather than a synonym —
185    /// a MISSING token is not an `ERROR` node, but it occupies a child
186    /// slot just the same, so a rule reading a child's *index* has to
187    /// account for both.
188    #[must_use]
189    #[inline]
190    pub fn is_missing(&self) -> bool {
191        self.0.is_missing()
192    }
193
194    /// Whether tree-sitter marks this node as an *extra*: one that may
195    /// appear anywhere, such as a comment in most grammars, or Python's
196    /// line continuation.
197    ///
198    /// Error recovery marks some `ERROR` nodes as extras too, and such a
199    /// node can wrap a token the author wrote, as the `,` of Perl's
200    /// `(name, => 1)` is. A scan that steps over extras must still stop
201    /// at one of those: skip `is_extra() && !is_error()`.
202    #[must_use]
203    #[inline]
204    pub fn is_extra(&self) -> bool {
205        self.0.is_extra()
206    }
207
208    /// An id unique to this node within its tree, stable for the tree's
209    /// lifetime. Suitable as a map key for per-node walk state.
210    #[inline]
211    #[must_use]
212    pub fn id(&self) -> usize {
213        self.0.id()
214    }
215
216    /// The grammar's name for this node's kind (`"function_item"`,
217    /// `"identifier"`, …). Several distinct [`kind_id`](Self::kind_id)s
218    /// can share one name — see the aliasing note on `kind_id`.
219    #[inline]
220    #[must_use]
221    pub fn kind(&self) -> &'static str {
222        self.0.kind()
223    }
224
225    /// The numeric kind of this node in its grammar's symbol table.
226    ///
227    /// This is what the per-language token enums in [`languages`]
228    /// (`Rust::FunctionItem as u16`, …) and every classifier match on.
229    /// The value is an index into the pinned grammar and moves whenever
230    /// that grammar is bumped; it is not stable across versions.
231    ///
232    /// [`languages`]: crate::languages
233    #[inline]
234    #[must_use]
235    pub fn kind_id(&self) -> u16 {
236        self.0.kind_id()
237    }
238
239    /// The source text this node spans, or `None` when the span falls
240    /// outside `data` or those bytes are not valid UTF-8.
241    ///
242    /// Indexed with `data.get(..)` rather than delegating to
243    /// [`tree_sitter::Node::utf8_text`], which is
244    /// `str::from_utf8(&source[start..end])` — the slice panics on a span
245    /// reaching past `source`, before the `Result` its signature offers
246    /// ever exists, so `.ok()` cannot catch it. Every caller today passes
247    /// the same buffer the tree was parsed from and so cannot produce
248    /// that span, but the guarantee is one refactor from false: this
249    /// crate already runs passes that parse one buffer and read another
250    /// (`preproc`, `comment_rm`), and `panic!` is banned in non-test code
251    /// whether or not the branch is currently reachable. `data.get(..)`
252    /// is also what `docs/development/grammar_dispatch.md` §10 prescribes
253    /// for reading a node's bytes.
254    #[inline]
255    #[must_use]
256    pub fn utf8_text(&self, data: &'a [u8]) -> Option<&'a str> {
257        let bytes = data.get(self.0.start_byte()..self.0.end_byte())?;
258        std::str::from_utf8(bytes).ok()
259    }
260
261    /// The 0-based byte offset where this node starts.
262    #[inline]
263    #[must_use]
264    pub fn start_byte(&self) -> usize {
265        self.0.start_byte()
266    }
267
268    /// The 0-based byte offset one past this node's last byte.
269    #[inline]
270    #[must_use]
271    pub fn end_byte(&self) -> usize {
272        self.0.end_byte()
273    }
274
275    /// The 0-based `(row, column)` where this node starts.
276    #[inline]
277    #[must_use]
278    pub fn start_position(&self) -> (usize, usize) {
279        let temp = self.0.start_position();
280        (temp.row, temp.column)
281    }
282
283    /// The 0-based `(row, column)` one past this node's end.
284    #[inline]
285    #[must_use]
286    pub fn end_position(&self) -> (usize, usize) {
287        let temp = self.0.end_position();
288        (temp.row, temp.column)
289    }
290
291    /// The 0-based row this node starts on.
292    #[inline]
293    #[must_use]
294    pub fn start_row(&self) -> usize {
295        self.0.start_position().row
296    }
297
298    /// The 0-based row of this node's end position. A node ending at
299    /// column 0 does not occupy that row; see [`end_line`](Self::end_line).
300    #[inline]
301    #[must_use]
302    pub fn end_row(&self) -> usize {
303        self.0.end_position().row
304    }
305
306    /// The 1-based **last line this node occupies** — the inclusive end
307    /// of its line span.
308    ///
309    /// Converting tree-sitter's 0-based end row needs a `+ 1` only when
310    /// the node actually occupies the row it ends on. A node whose end
311    /// column is 0 finished at the *start* of the row below its last
312    /// content row, having absorbed the preceding newline, so that row
313    /// is not part of its span.
314    ///
315    /// Getting this wrong is invisible in almost every grammar, because
316    /// almost every function node ends just past its closing delimiter
317    /// and therefore at a column above 0. Perl's trailing `sub` does
318    /// not: it ends at column 0 of the row below its `}`, exactly where
319    /// the file root ends, and a blanket `+ 1` then reported it ending a
320    /// line past both its enclosing space and EOF (#1163) — the shape
321    /// behind the release `usize` underflow in #1051.
322    #[inline]
323    #[must_use]
324    pub fn end_line(&self) -> usize {
325        let end = self.0.end_position();
326        if end.column == 0 {
327            end.row
328        } else {
329            end.row + 1
330        }
331    }
332
333    /// Returns this node's parent.
334    ///
335    /// **`O(depth)`, not `O(1)`.** tree-sitter stores no parent pointer:
336    /// `ts_node_parent` restarts at the tree root and descends. A single
337    /// call in a per-node metric therefore costs `O(nodes × depth)` over a
338    /// walk, and an ancestor *loop* built on it costs `O(depth²)` per call.
339    ///
340    /// This has bitten the analyzer for real: #1052 was a per-leaf
341    /// `successors(node, Node::parent)` walk in `Tokens` that made the
342    /// metric `O(leaves × depth²)`, so a 2 KB file of nested parentheses
343    /// took ~19 s. Prefer inheriting state downward through the
344    /// traversal (see `Walk` in `spaces::compute`) over rediscovering it
345    /// upward, and where a predicate genuinely needs an ancestor, take
346    /// an [`Ancestors`] rather than calling this (#1084).
347    ///
348    /// As of #1096 no code the metric, `ops`, `bca function`, or
349    /// comment-removal walks reach calls this; the remaining callers are
350    /// `Ancestors` itself (the no-chain fallback), the one-off start node
351    /// of a `dump`, and tests. `rg '\.parent\(\)' src/` re-checks that.
352    ///
353    /// **Not on a deep zero-width node.** On a zero-width node, such as a
354    /// `MISSING` one, tree-sitter's lookup calls itself once per tree
355    /// level, so far enough down it overflows the stack (#1941). The
356    /// Python bindings answer that case by walking down from the root
357    /// (#1937); this type cannot reach the root without this lookup.
358    #[inline]
359    pub fn parent(&self) -> Option<Node<'a>> {
360        node_resolved_parent_lookups::record();
361        self.0.parent().map(Node)
362    }
363
364    /// Returns `true` if this node's parent has any direct child with
365    /// the given grammar `kind_id` (the parent's children include this
366    /// node itself, so a self-match counts). Delegates to [`wraps_any`]
367    /// on the parent. The JS/TS arrow-function closure classification
368    /// (`bound_arrow` in `roles/js_family.rs`) asked this per arrow until
369    /// the scan was memoised per parent; see #521.
370    ///
371    /// `ancestors` supplies the parent, for [`Node::parent`]'s
372    /// `O(depth)` reason (#1088).
373    ///
374    /// [`wraps_any`]: Self::wraps_any
375    #[inline]
376    #[must_use]
377    pub fn has_sibling(&self, ancestors: Ancestors<'a, '_>, id: u16) -> bool {
378        ancestors
379            .parent(self)
380            .is_some_and(|parent| parent.is_child(id))
381    }
382
383    /// The sibling immediately before this node.
384    ///
385    /// **`O(depth)`, not `O(1)`**, for [`Node::parent`]'s reason:
386    /// `ts_node__prev_sibling` opens with `ts_node_parent`. Callers on a
387    /// walk should use [`Ancestors::previous_sibling`] instead (#1096).
388    #[inline]
389    pub fn previous_sibling(&self) -> Option<Node<'a>> {
390        node_resolved_sibling_lookups::record();
391        self.0.prev_sibling().map(Node)
392    }
393
394    /// The sibling immediately after this node.
395    ///
396    /// **`O(depth)`, not `O(1)`**, for [`previous_sibling`]'s reason:
397    /// `ts_node_next_sibling` opens with `ts_node_parent`. Test-only: a
398    /// walk reads forward with [`Ancestors::siblings_after`], and the
399    /// last production caller, the `exclude_tests` attribute lookahead,
400    /// moved there in #1447. The tests keep it as an oracle that shares
401    /// no lookup with the code it checks.
402    ///
403    /// [`previous_sibling`]: Self::previous_sibling
404    #[cfg(test)]
405    #[inline]
406    pub(crate) fn next_sibling(&self) -> Option<Node<'a>> {
407        node_resolved_sibling_lookups::record();
408        self.0.next_sibling().map(Node)
409    }
410
411    /// Returns `true` if any direct child has the given grammar
412    /// `kind_id`. See #217 for the motivating perf finding from the
413    /// JS/TS template-literal hot path.
414    #[inline]
415    #[must_use]
416    pub fn is_child(&self, id: u16) -> bool {
417        self.wraps_any(&[id])
418    }
419
420    /// Returns `true` if any direct child matches one of the given
421    /// grammar `kind_id`s. The single-id [`is_child`] delegates here, so
422    /// both share one child scan (the `#[inline]` makes the
423    /// single-element `contains` collapse to an equality check).
424    /// Generalizing the check to a set lets the shared
425    /// string-interpolation operand skip declare its rule once (issue
426    /// #420).
427    ///
428    /// # Why a cursor rather than `child(0)` + `next_sibling()`
429    ///
430    /// #217 replaced the cursor walk with a `next_sibling()` chain to
431    /// dodge the `TreeCursor` heap allocation, on the premise that a
432    /// sibling step is `O(1)`. It is not: `ts_node_next_sibling`
433    /// resolves the parent first, and `tree_sitter` stores no parent
434    /// pointer — it descends from the root — so each step cost
435    /// `O(depth)` and the scan `O(children × depth)`. That made every
436    /// caller of this method `O(depth)` per node, which is the same
437    /// defect #1084 removed from the predicates that ask for an
438    /// ancestor outright. The cursor iterator is `O(children)` after one
439    /// allocation, and measured faster on real input as well as on the
440    /// pathological one: the `nom/nested-arrow` probe went from
441    /// quadratic (17.6 s at depth 4000) to linear (6.3 ms), and a walk
442    /// over the 384-file `pdf.js` corpus dropped from ~443 ms to
443    /// ~370 ms (#1088).
444    ///
445    /// [`is_child`]: Self::is_child
446    #[inline]
447    #[must_use]
448    pub fn wraps_any(&self, ids: &[u16]) -> bool {
449        self.children().any(|c| ids.contains(&c.kind_id()))
450    }
451
452    /// The number of direct children, named and anonymous alike.
453    #[inline]
454    #[must_use]
455    pub fn child_count(&self) -> usize {
456        self.0.child_count()
457    }
458
459    /// Whether this node is a named grammar production, as opposed to an
460    /// anonymous token such as a punctuation or keyword literal. Walks
461    /// use it to skip tokens like the leading `|` in an or-pattern.
462    #[inline]
463    #[must_use]
464    pub fn is_named(&self) -> bool {
465        self.0.is_named()
466    }
467
468    /// Returns the direct child reached through the grammar `field_name`,
469    /// if any. The child carries the underlying tree lifetime `'a` (the
470    /// `tree_sitter::Node` it wraps is [`Copy`] and valid for the whole
471    /// tree), so callers may hold it past the borrow of `&self` — matching
472    /// the sibling accessors ([`child`], [`parent`], [`children`], …) rather
473    /// than over-narrowing to the method-call borrow (see issue #786).
474    ///
475    /// [`child`]: Self::child
476    /// [`parent`]: Self::parent
477    /// [`children`]: Self::children
478    #[inline]
479    pub fn child_by_field_name(&self, name: &str) -> Option<Node<'a>> {
480        self.0.child_by_field_name(name).map(Node)
481    }
482
483    /// [`child_by_field_name`](Self::child_by_field_name) through the
484    /// field's grammar id, which `tree_sitter` resolves from the name by
485    /// a linear string compare over the grammar's field table on every
486    /// call. A caller asking the same field of many nodes resolves it
487    /// once with [`field_id`](Self::field_id) and reads through this.
488    ///
489    /// `pub` only because the `#[macro_export]`ed `role_table!` reads it
490    /// from its expansion; the id is the pinned grammar's and not part
491    /// of the stable surface, so this is hidden from the docs.
492    #[doc(hidden)]
493    #[inline]
494    pub fn child_by_field_id(&self, field: u16) -> Option<Node<'a>> {
495        self.0.child_by_field_id(field).map(Node)
496    }
497
498    /// The grammar's id for `name` in the language this node was parsed
499    /// with, or `None` where that grammar names no such field. Hidden
500    /// for the reason [`child_by_field_id`](Self::child_by_field_id) is.
501    #[doc(hidden)]
502    #[inline]
503    pub fn field_id(&self, name: &str) -> Option<u16> {
504        self.0.language().field_id_for_name(name).map(u16::from)
505    }
506
507    /// The direct child at index `pos`, counting named and anonymous
508    /// children alike. Prefer [`child_by_field_name`](Self::child_by_field_name)
509    /// for any slot the grammar can precede with an optional preamble.
510    ///
511    /// # Cost
512    ///
513    /// Not constant: tree-sitter scans the child array from the front,
514    /// skipping each hidden subtree by its cached child count. That is
515    /// `O(log n)` into a list the grammar stores as a `repeat()` — a
516    /// balanced tree of hidden nodes — and `O(pos)` into one whose
517    /// children sit in a single raw array. Whether an `ERROR` is flat
518    /// depends on how recovery assembled it, not on where it sits: the
519    /// Perl `my @r = ({…` root with every skipped token as a direct
520    /// child is the measured flat case, while a root whose skipped run
521    /// stayed under a hidden `_ERROR` repeat is balanced and a nested
522    /// `ERROR` wrapping a few popped tokens is flat. Indexing every
523    /// child of a flat node in turn is quadratic in its width (#1684).
524    /// Use [`children`](Self::children) or
525    /// [`children_with`](Self::children_with) to enumerate; this is
526    /// for picking one slot. A loop that needs repeated random access
527    /// to a wide list should collect the children once and index the
528    /// `Vec`.
529    #[inline]
530    #[must_use]
531    pub fn child(&self, pos: usize) -> Option<Node<'a>> {
532        self.0.child(pos as u32).map(Node)
533    }
534
535    /// Returns the tree-sitter grammar field name through which this
536    /// node reaches the child at `child_index`, if any.
537    ///
538    /// # Cost
539    ///
540    /// What [`child`](Self::child) costs: the same scan to the index,
541    /// so enumerating a flat node's fields this way is quadratic in
542    /// its width. A traversal takes the field off the cursor it is
543    /// already holding ([`Cursor::field_name`]) instead, which is how
544    /// the default AST export does it (#1684).
545    #[inline]
546    #[must_use]
547    pub fn field_name_for_child(&self, child_index: u32) -> Option<&'static str> {
548        self.0.field_name_for_child(child_index)
549    }
550
551    /// Iterator over this node's direct children.
552    ///
553    /// Builds a [`Cursor`], which heap-allocates. A loop that visits
554    /// many nodes should hoist one cursor and use [`children_with`]
555    /// instead; see its note for when the difference is worth the
556    /// plumbing.
557    ///
558    /// [`children_with`]: Self::children_with
559    #[inline]
560    #[must_use]
561    pub fn children(&self) -> Children<'a> {
562        child_scan_cursors::record();
563        // `descend`, not `seed`: `ts_node_walk` already ran the
564        // `ts_tree_cursor_init` that `Cursor::reset` would run again.
565        let mut cursor = self.cursor();
566        let scan = ChildScan::descend(self, &mut cursor);
567        Children { cursor, scan }
568    }
569
570    /// [`children`], over a cursor the caller owns.
571    ///
572    /// `tree_sitter::TreeCursor` heap-allocates its stack when built and
573    /// frees it when dropped, so a traversal that calls [`children`]
574    /// once per visited node pays a `malloc`/`free` pair per node.
575    /// `ts_tree_cursor_reset` keeps the allocation, so a loop that can
576    /// hoist one cursor pays for it once however many nodes it visits
577    /// (#1112).
578    ///
579    /// Worth the plumbing only where a loop visits many nodes. Measured
580    /// on the corpus slice, a full metric walk reaches [`children`] on
581    /// 3-6 % of nodes in C++, Rust, JavaScript, and Java, 16 % in C#,
582    /// and 60 % in Python, where one scan — the instance-attribute walk
583    /// in `metrics::npa::python` — was 92 % of the total, and
584    /// [`preorder`] plus the suppression DFS are the rest. Crate-wide
585    /// there is one more per-node consumer, `output::dump`'s renderer,
586    /// which no metric walk runs and so is absent from that total.
587    /// Predicates
588    /// that hold a bare `&Node` and scan one node's children keep
589    /// [`children`]: threading a cursor to them would cross the
590    /// `Checker` / `Getter` trait surface for one allocation per call.
591    ///
592    /// [`preorder`]: Self::preorder
593    ///
594    /// [`children`]: Self::children
595    #[inline]
596    pub fn children_with<'c>(&self, cursor: &'c mut Cursor<'a>) -> ChildrenWith<'c, 'a> {
597        let scan = ChildScan::seed(self, cursor);
598        ChildrenWith { cursor, scan }
599    }
600
601    /// The children after `child`, nearest first: what
602    /// `children().skip_while(|c| c.id() != child.id()).skip(1)` yields,
603    /// and nothing when `child` is not one of this node's children.
604    ///
605    /// That scan costs `child`'s index, so a walk that asks it of every
606    /// child of a wide list is quadratic in the list (#1545). This seeks
607    /// `child` by byte instead, which is `O(log n)` in a list the grammar
608    /// stores as a `repeat()` and still `O(index)` in a flat one, an
609    /// `ERROR` above all; see [`Cursor::goto_first_child_for_byte`]. The
610    /// children ahead of a `repeat()` are flat as well: a run of
611    /// comments between a list's `(` and its first element is stepped
612    /// over one by one (#1868). A walk that asks of every child of a
613    /// node that may be flat goes through
614    /// [`Ancestors::siblings_after`] (#1584).
615    pub fn children_after(&self, child: &Node<'a>) -> impl Iterator<Item = Node<'a>> + use<'a> {
616        let mut cursor = self.cursor();
617        let mut more =
618            self.seat_on_child(child, &mut cursor).is_some() && cursor.goto_next_sibling();
619        std::iter::from_fn(move || {
620            let next = more.then(|| cursor.node())?;
621            more = cursor.goto_next_sibling();
622            Some(next)
623        })
624    }
625
626    /// The children before `child`, nearest first, and nothing when
627    /// `child` is not one of this node's children.
628    ///
629    /// `child`'s index comes from [`Cursor::goto_first_child_for_byte`]
630    /// and each sibling from [`Node::child`], both `O(log n)` in the
631    /// child count where the list is a `repeat()`, stored as a balanced
632    /// tree of hidden nodes, and both `O(index)` where it is flat, as an
633    /// `ERROR` built by skipping tokens is, and as a run of extras ahead
634    /// of a `repeat()` is. Reading back over a flat run of `n` siblings
635    /// therefore costs `n² / 2`, from one call (#1868). A walk that asks
636    /// of every child of such a node goes through
637    /// [`Ancestors::siblings_before`] (#1584).
638    pub fn children_before(&self, child: &Node<'a>) -> impl Iterator<Item = Node<'a>> + use<'a> {
639        let node = *self;
640        let index = self.seat_on_child(child, &mut self.cursor()).unwrap_or(0);
641        (0..index).rev().filter_map(move |i| node.child(i))
642    }
643
644    // Seats `cursor`, which sits on this node, on `child` and returns its
645    // index, or `None` when `child` is not one of this node's children.
646    fn seat_on_child(&self, child: &Node<'a>, cursor: &mut Cursor<'a>) -> Option<usize> {
647        if let Some(index) = cursor.goto_first_child_for_byte(child.start_byte())
648            && cursor.node().id() == child.id()
649        {
650            return Some(index);
651        }
652        // The lookup passes over a zero-width child, which ends at the
653        // byte it starts at; only error recovery inserts one.
654        cursor.reset(self);
655        let mut index = 0;
656        let mut found = cursor.goto_first_child();
657        while found && cursor.node().id() != child.id() {
658            found = cursor.goto_next_sibling();
659            index += 1;
660        }
661        found.then_some(index)
662    }
663
664    /// A fresh cursor positioned on this node, for the traversals that
665    /// reuse one cursor across many child scans
666    /// ([`children_with`](Self::children_with)).
667    #[inline]
668    #[must_use]
669    pub fn cursor(&self) -> Cursor<'a> {
670        Cursor(self.0.walk())
671    }
672
673    /// Counts this node's ancestors satisfying `check`, walking upward
674    /// from the parent and stopping at (and excluding) the first
675    /// ancestor satisfying `stop`. An ancestor that is the `if` of an
676    /// `else if` chain never counts — it is a continuation of the
677    /// branch above it, not a new enclosing one.
678    ///
679    /// `ancestors` is the chain the caller descended through. Passing
680    /// [`Ancestors::unknown`] is always correct and answers identically;
681    /// it just pays `O(depth)` per step instead of `O(1)`.
682    pub fn count_specific_ancestors<C: Checker>(
683        &self,
684        ancestors: Ancestors<'a, '_>,
685        check: impl Fn(&Node) -> bool,
686        stop: fn(&Node) -> bool,
687    ) -> usize {
688        let mut count = 0;
689        for (parent, above_parent) in ancestors.iter(self) {
690            if stop(&parent) {
691                break;
692            }
693            if check(&parent) && !C::is_else_if(&parent, above_parent) {
694                count += 1;
695            }
696        }
697        count
698    }
699
700    /// Returns `true` iff this node's parent satisfies `parent_pred`
701    /// AND that parent's own parent (this node's grandparent)
702    /// satisfies `grand_pred`. Returns `false` as soon as either link
703    /// is absent or its predicate fails, so a misordered predicate
704    /// cannot silently degrade to a single-predicate check.
705    ///
706    /// `ancestors` is the chain the caller descended through. Passing
707    /// [`Ancestors::unknown`] is always correct and answers
708    /// identically; it just pays [`Node::parent`]'s `O(depth)` for each
709    /// of the two links, which on a per-node metric arm is quadratic in
710    /// nesting depth (#1096).
711    pub fn parent_grandparent_match(
712        &self,
713        ancestors: Ancestors<'a, '_>,
714        parent_pred: fn(&Node) -> bool,
715        grand_pred: fn(&Node) -> bool,
716    ) -> bool {
717        let mut climb = ancestors.iter(self);
718        let Some((parent, _)) = climb.next() else {
719            return false;
720        };
721        if !parent_pred(&parent) {
722            return false;
723        }
724        let Some((grand, _)) = climb.next() else {
725            return false;
726        };
727        grand_pred(&grand)
728    }
729
730    /// Returns a pre-order iterator over this node and all of its
731    /// descendants (this node first, then each child subtree left to
732    /// right).
733    ///
734    /// The traversal is allocation-light: it reuses one work stack *and
735    /// one cursor*, and visits each node exactly once, so a full walk is
736    /// O(n) in the subtree size and allocates only the stack's growth.
737    /// Building a fresh cursor per visited node instead would cost a
738    /// `malloc`/`free` pair per node (#1112). Every yielded [`Node`]
739    /// carries the underlying tree lifetime `'a`, so callers may collect
740    /// or retain the handles.
741    ///
742    /// This is the Rust counterpart of the Python `Node.walk()` binding
743    /// (issue #728): the binding wraps each yielded node, so Rust and
744    /// Python share one traversal order.
745    #[must_use]
746    pub fn preorder(&self) -> Preorder<'a> {
747        Preorder {
748            stack: vec![*self],
749            cursor: self.cursor(),
750        }
751    }
752
753    /// Collects every node in this subtree (this node included) whose
754    /// [`kind`](tree_sitter::Node::kind) is listed in `kinds`, in
755    /// pre-order.
756    ///
757    /// Membership is an exact match against the raw grammar kind — the
758    /// same unaltered vocabulary `big_code_analysis::Ast::root_node` exposes, not
759    /// the `Alterator`-curated kinds `big_code_analysis::Ast::dump` emits. This is
760    /// the Rust counterpart of the Python `Node.descendants_by_kind()`
761    /// binding (issue #728).
762    #[must_use]
763    pub fn descendants_by_kind(&self, kinds: &[&str]) -> Vec<Node<'a>> {
764        self.preorder()
765            .filter(|node| kinds.contains(&node.kind()))
766            .collect()
767    }
768}
769
770/// Pre-order iterator over a node and its descendants, returned by
771/// [`Node::preorder`].
772///
773/// Holds a single work stack of not-yet-visited nodes, and a single
774/// cursor to enumerate each node's children with. Each step pops the
775/// next node, pushes its children so the leftmost is visited first, and
776/// yields the popped node — so the sequence is the node, then each child
777/// subtree in order. Both are reused across steps (children are pushed
778/// then the freshly-pushed slice is reversed in place), so the walk
779/// allocates only the stack's growth: no fresh buffer per node, and no
780/// fresh `TreeCursor` either (#1112).
781pub struct Preorder<'a> {
782    stack: Vec<Node<'a>>,
783    cursor: Cursor<'a>,
784}
785
786impl<'a> Iterator for Preorder<'a> {
787    type Item = Node<'a>;
788
789    fn next(&mut self) -> Option<Self::Item> {
790        let node = self.stack.pop()?;
791        // Push children in document order, then reverse just the slice we
792        // appended so the leftmost child ends up on top of the stack and
793        // is visited next — pre-order without a per-node temporary.
794        let first_child = self.stack.len();
795        // Destructured so the stack and the cursor are borrowed as the
796        // disjoint fields they are.
797        let Self { stack, cursor } = self;
798        stack.extend(node.children_with(cursor));
799        stack[first_child..].reverse();
800        Some(node)
801    }
802}
803
804/// An `AST` cursor.
805#[derive(Clone)]
806pub struct Cursor<'a>(TreeCursor<'a>);
807
808impl<'a> Cursor<'a> {
809    /// Re-seats the cursor on `node`.
810    #[inline]
811    pub fn reset(&mut self, node: &Node<'a>) {
812        self.0.reset(node.0);
813    }
814
815    /// Moves to the next sibling; `false` when there is none.
816    #[inline]
817    pub fn goto_next_sibling(&mut self) -> bool {
818        self.0.goto_next_sibling()
819    }
820
821    /// Moves to the first child; `false` when there is none.
822    #[inline]
823    pub fn goto_first_child(&mut self) -> bool {
824        self.0.goto_first_child()
825    }
826
827    /// Moves to the first child that ends after `byte` and returns its
828    /// index in [`Node::children`] order, or `None` when no child does.
829    ///
830    /// "Ends after" is strict, so a **zero-width** child at `byte` — a
831    /// MISSING token the parser inserted during error recovery — is
832    /// skipped and the cursor lands on its successor. That is the one way
833    /// this differs from `children().position(..)`, which finds such a
834    /// node; a caller resolving a node's own index must therefore check
835    /// [`Cursor::node`] against it, as both call sites here do.
836    ///
837    /// The index is what makes this worth having over a sibling scan:
838    /// tree-sitter stores a `repeat()` child list under balanced hidden
839    /// nodes and skips each by its cached visible-child count, so this
840    /// is `O(log n)` in the sibling count where `children().position(..)`
841    /// is `O(n)` — the difference between a linear and a quadratic walk
842    /// when every child of a wide list asks for its own index.
843    ///
844    /// Only for such a list. The seek steps through the children in
845    /// order and can skip only a *hidden* subtree, so over a flat child
846    /// array — an `ERROR` that recovery built by skipping tokens has no
847    /// hidden levels — it is the same `O(index)` scan (#1584). So it is
848    /// over whatever precedes a `repeat()` in a node that parsed: the
849    /// comments between a list's opening token and its first element
850    /// are the list's own children, not the repeat's (#1868).
851    #[inline]
852    pub fn goto_first_child_for_byte(&mut self, byte: usize) -> Option<usize> {
853        self.0.goto_first_child_for_byte(byte)
854    }
855
856    /// Moves to the parent; `false` when there is none.
857    ///
858    /// The node the cursor was built on ([`Node::cursor`]) or last
859    /// [`reset`](Self::reset) to is the ceiling: from there this returns
860    /// `false` and leaves the cursor where it is, even when the node has
861    /// a parent in the tree. A traversal that descends and climbs back
862    /// through one cursor therefore cannot wander above its subtree.
863    #[inline]
864    pub fn goto_parent(&mut self) -> bool {
865        self.0.goto_parent()
866    }
867
868    /// The grammar field through which the parent reaches the node the
869    /// cursor currently sits on, or `None` when it occupies no field —
870    /// most punctuation, an `extra` such as a comment, or the node the
871    /// cursor started on, whose parent it cannot see. Anonymous tokens
872    /// can sit in a field: a `binary_expression`'s `+` is its
873    /// `operator`.
874    ///
875    /// Reflects the cursor's *position*: it is answered from the path
876    /// the cursor descended, so a field inherited through a hidden
877    /// grammar node is resolved the same way [`Node::field_name_for_child`]
878    /// resolves it — both stop at the nearest visible ancestor and
879    /// both answer `None` for an `extra`. The two are different
880    /// algorithms, though: this one climbs the cursor's stack and
881    /// stops at the first `extra` entry, while the index lookup
882    /// descends and reads the field map at each hidden level. They
883    /// agree wherever every `extra` is a leaf or a visible rule, which
884    /// holds for every pinned grammar; a hidden `extra` wrapper with
885    /// visible children is the one shape that could split them.
886    #[inline]
887    #[must_use]
888    pub fn field_name(&self) -> Option<&'static str> {
889        self.0.field_name()
890    }
891
892    /// The node the cursor currently sits on.
893    #[inline]
894    #[must_use]
895    pub fn node(&self) -> Node<'a> {
896        Node(self.0.node())
897    }
898}
899
900/// Position of a child scan, independent of who owns the cursor driving
901/// it.
902///
903/// [`Children`] and [`ChildrenWith`] differ only in that — one owns its
904/// cursor, the other borrows the caller's — and `children_with` exists
905/// to save an allocation, not to answer differently. Keeping the
906/// termination rule here rather than in each iterator is what stops the
907/// two from drifting.
908struct ChildScan {
909    done: bool,
910    remaining: usize,
911}
912
913impl ChildScan {
914    /// Seats `cursor` on `node`'s first child.
915    ///
916    /// `goto_first_child` returns false when the node has no children,
917    /// in which case the scan is exhausted from the outset. Termination
918    /// is then driven entirely by the cursor (see [`ChildScan::step`]),
919    /// so the iterator stops exactly when the tree reports no further
920    /// siblings — it can never pad the sequence with duplicate nodes if
921    /// `child_count` and the cursor walk ever disagree.
922    ///
923    /// `child_count` is the authoritative length for the
924    /// `ExactSizeIterator` contract; for well-formed trees it equals the
925    /// cursor sibling walk, so the reported length and the emitted data
926    /// agree. A childless node reports `0` so the empty iterator's
927    /// length matches its (lack of) data.
928    fn seed<'a>(node: &Node<'a>, cursor: &mut Cursor<'a>) -> Self {
929        cursor.reset(node);
930        Self::descend(node, cursor)
931    }
932
933    /// [`ChildScan::seed`], for a cursor already seated on `node` —
934    /// which is what [`Node::cursor`] hands back, and `ts_node_walk` and
935    /// `ts_tree_cursor_reset` run the same `ts_tree_cursor_init`. Only
936    /// [`Node::children`] may skip the reset; every other caller reuses
937    /// a cursor left wherever the previous scan ended.
938    fn descend<'a>(node: &Node<'a>, cursor: &mut Cursor<'a>) -> Self {
939        let done = !cursor.goto_first_child();
940        Self {
941            done,
942            remaining: if done { 0 } else { node.child_count() },
943        }
944    }
945
946    /// Yields the cursor's current child and advances past it.
947    fn step<'a>(&mut self, cursor: &mut Cursor<'a>) -> Option<Node<'a>> {
948        if self.done {
949            return None;
950        }
951        let result = cursor.node();
952        // The cursor is the single source of truth for termination:
953        // once there is no next sibling this yield is the last one.
954        self.done = !cursor.goto_next_sibling();
955        // Keep the advertised length consistent with termination: when
956        // the cursor stops, nothing remains. For well-formed trees this
957        // equals `child_count - emitted`; if the cursor walk and
958        // `child_count` ever disagree, this still honors the
959        // `ExactSizeIterator` contract (`len() == 0` exactly at
960        // exhaustion) rather than reporting a phantom remainder.
961        self.remaining = if self.done {
962            0
963        } else {
964            self.remaining.saturating_sub(1)
965        };
966        Some(result)
967    }
968
969    fn size_hint(&self) -> (usize, Option<usize>) {
970        (self.remaining, Some(self.remaining))
971    }
972}
973
974/// Iterator over a node's direct children, returned by
975/// [`Node::children`]. Owns the cursor it walks with.
976///
977/// Termination is driven by the cursor alone: each step yields the
978/// cursor's current node, then advances with `goto_next_sibling`,
979/// stopping the moment that returns false. This makes the cursor the
980/// single source of truth for both the emitted data and when to stop, so
981/// the sequence can never be padded with duplicates if `child_count` and
982/// the actual sibling walk disagree.
983///
984/// The `ExactSizeIterator` length is reported from `child_count` (tracked
985/// in `ChildScan`). For well-formed trees the cursor walk and
986/// `child_count` agree, so the advertised length matches the data.
987pub struct Children<'a> {
988    cursor: Cursor<'a>,
989    scan: ChildScan,
990}
991
992impl<'a> Iterator for Children<'a> {
993    type Item = Node<'a>;
994
995    fn next(&mut self) -> Option<Self::Item> {
996        self.scan.step(&mut self.cursor)
997    }
998
999    fn size_hint(&self) -> (usize, Option<usize>) {
1000        self.scan.size_hint()
1001    }
1002}
1003
1004impl ExactSizeIterator for Children<'_> {}
1005
1006/// Iterator over a node's direct children, returned by
1007/// [`Node::children_with`]. Borrows the caller's cursor rather than
1008/// building one, which is the whole of the difference: it yields exactly
1009/// what [`Children`] yields, through the same `ChildScan`.
1010pub struct ChildrenWith<'c, 'a> {
1011    cursor: &'c mut Cursor<'a>,
1012    scan: ChildScan,
1013}
1014
1015impl<'a> Iterator for ChildrenWith<'_, 'a> {
1016    type Item = Node<'a>;
1017
1018    fn next(&mut self) -> Option<Self::Item> {
1019        self.scan.step(self.cursor)
1020    }
1021
1022    fn size_hint(&self) -> (usize, Option<usize>) {
1023        self.scan.size_hint()
1024    }
1025}
1026
1027impl ExactSizeIterator for ChildrenWith<'_, '_> {}
1028
1029impl<'a> Search<'a> for Node<'a> {
1030    fn act_on_node(&self, action: &mut dyn FnMut(&Node<'a>, Ancestors<'a, '_>)) {
1031        let mut cursor = self.cursor();
1032        let mut stack = Vec::new();
1033        // Ancestor chain of the node being visited, root first. Kept by
1034        // the same truncate/push rule as the metric walk, so a predicate
1035        // the action applies can read an ancestor as a slice index
1036        // rather than through the `O(depth)` `Node::parent` (#1088).
1037        //
1038        // Seeded with this subtree root's own ancestry rather than left
1039        // empty: `Ancestors` reads an empty chain as "this node is the
1040        // tree root", so on a subtree an empty seed would report no
1041        // parent for `*self` — silently costing e.g. the JS getters the
1042        // binding a `function_expression` takes its name from. One
1043        // climb, and none at all for the tree root this is called on
1044        // today.
1045        let mut chain: Vec<Node<'a>> = std::iter::successors(self.parent(), Node::parent).collect();
1046        chain.reverse();
1047        let depth = chain.len();
1048        // As in the metric walk: the children of each wide node on
1049        // `chain`, so a sibling lookup in a flat `ERROR` is a binary
1050        // search rather than a seek from its start (#1584). Perl's
1051        // `call` filter reads the token after every bareword (#1580).
1052        // The seeded ancestors are recorded too, since the walk never
1053        // pushes them.
1054        let mut siblings = SiblingCache::default();
1055        for (at, ancestor) in chain.iter().enumerate() {
1056            siblings.record(ancestor, at, ancestor.children());
1057        }
1058        // And the walk's memo, so the `string` filter's Tcl-family role
1059        // question is answered once per argument list rather than once
1060        // per braced word in it (#1686).
1061        let folds = FoldCache::default();
1062
1063        stack.push((*self, depth));
1064
1065        while let Some((node, depth)) = stack.pop() {
1066            chain.truncate(depth);
1067            action(&node, Ancestors::for_walk(&chain, &node, &folds, &siblings));
1068            chain.push(node);
1069            // Source order in, tail reversed in place, so the LIFO
1070            // `stack` yields the leftmost child first — pre-order with
1071            // no staging buffer.
1072            let first_child = stack.len();
1073            stack.extend(
1074                node.children_with(&mut cursor)
1075                    .map(|child| (child, depth + 1)),
1076            );
1077            siblings.record(
1078                &node,
1079                depth,
1080                stack[first_child..].iter().map(|(child, _)| *child),
1081            );
1082            stack[first_child..].reverse();
1083        }
1084    }
1085
1086    fn first_child(&self, pred: fn(u16) -> bool) -> Option<Node<'a>> {
1087        self.children().find(|&child| pred(child.kind_id()))
1088    }
1089
1090    fn act_on_child(&self, action: &mut dyn FnMut(&Node<'a>)) {
1091        for child in self.children() {
1092            action(&child);
1093        }
1094    }
1095}
1096
1097#[cfg(test)]
1098mod tests {
1099    use super::*;
1100    use crate::langs::MozjsCode;
1101    use crate::test_support::for_each_node_with_chain;
1102
1103    /// The `child(0)` + `next_sibling()` chain [`Node::wraps_any`] used
1104    /// between #217 and #1088, kept here as the reference the cursor
1105    /// walk that replaced it is checked against.
1106    ///
1107    /// The swap was made for cost, not for behaviour: a sibling step
1108    /// resolves its parent, and `tree_sitter` resolves a parent by
1109    /// descending from the root, so the chain was `O(children × depth)`
1110    /// where the cursor is `O(children)`. Nothing about the *set* of
1111    /// children was supposed to change, and this is what says so —
1112    /// node-by-node over a real tree, same order and same short-circuit,
1113    /// without hardcoding grammar `kind_id`s.
1114    #[cfg(feature = "mozjs")]
1115    fn sibling_chain_has_sibling(node: OtherNode, id: u16) -> bool {
1116        node.parent().is_some_and(|parent| {
1117            let mut cur = parent.child(0);
1118            while let Some(c) = cur {
1119                if c.kind_id() == id {
1120                    return true;
1121                }
1122                cur = c.next_sibling();
1123            }
1124            false
1125        })
1126    }
1127
1128    /// `utf8_text` answers `None` for a span outside the buffer instead
1129    /// of aborting the process.
1130    ///
1131    /// The only way to reach that branch is to read against a buffer
1132    /// other than the one the tree was parsed from, which no caller does
1133    /// today — so this is the whole coverage the guard can have, and it
1134    /// is a real one: against the delegating implementation
1135    /// (`self.0.utf8_text(data).ok()`) this test panics at
1136    /// `str::from_utf8(&source[start..end])` rather than failing, which
1137    /// is precisely the behaviour the guard removes. Verified by revert.
1138    #[test]
1139    #[cfg(feature = "rust")]
1140    fn utf8_text_is_none_for_a_span_past_the_buffer() {
1141        let code = b"fn f() {}\n";
1142        let tree = Tree::new::<crate::langs::RustCode>(code);
1143        let root = tree.get_root();
1144
1145        // Sanity: the span is in range against its own buffer, so a
1146        // `None` below means the bound fired and not that the node is
1147        // empty or the text is not UTF-8.
1148        assert_eq!(root.utf8_text(code), Some("fn f() {}\n"));
1149
1150        // The same node, read against a buffer that ends mid-span.
1151        assert_eq!(root.utf8_text(&code[..4]), None);
1152    }
1153
1154    #[cfg(feature = "mozjs")]
1155    #[test]
1156    fn has_sibling_matches_the_retired_sibling_chain() {
1157        // Arrow functions exercise the binding-gate question that
1158        // motivated #521 (PropertyIdentifier siblings on the JS/TS
1159        // closure-classification hot path).
1160        let code = b"const o = { m: (a) => a + 1, n: function () {} }; foo.bar();";
1161        let tree = Tree::new::<MozjsCode>(code);
1162        let ts_tree = tree.as_ts_tree();
1163
1164        // Collect the grammar kinds that actually occur, so the
1165        // equivalence check covers present-sibling (true) cases.
1166        let mut kinds = std::collections::BTreeSet::new();
1167        let mut stack = vec![ts_tree.root_node()];
1168        while let Some(n) = stack.pop() {
1169            kinds.insert(n.kind_id());
1170            let mut child = n.child(0);
1171            while let Some(c) = child {
1172                stack.push(c);
1173                child = c.next_sibling();
1174            }
1175        }
1176        // Include an id that does not occur anywhere for absent-sibling
1177        // (false) coverage.
1178        let absent_id = u16::MAX;
1179
1180        let mut stack = vec![ts_tree.root_node()];
1181        let mut matched = 0;
1182        while let Some(n) = stack.pop() {
1183            let wrapped = Node(n);
1184            for &id in kinds.iter().chain(std::iter::once(&absent_id)) {
1185                let found = wrapped.has_sibling(Ancestors::unknown(), id);
1186                assert_eq!(
1187                    found,
1188                    sibling_chain_has_sibling(n, id),
1189                    "has_sibling diverged from the retired sibling chain at node kind {} for id {id}",
1190                    n.kind(),
1191                );
1192                matched += usize::from(found);
1193            }
1194            let mut child = n.child(0);
1195            while let Some(c) = child {
1196                stack.push(c);
1197                child = c.next_sibling();
1198            }
1199        }
1200        // The comment above claims the collected kinds cover the
1201        // present-sibling case; this enforces it. Both sides answering
1202        // `false` everywhere would agree without either scan ever
1203        // running to a match.
1204        assert!(
1205            matched > 0,
1206            "every answer was `false`, so the sibling scan was never exercised"
1207        );
1208
1209        // No-parent node (root) always reports no sibling.
1210        let root = Node(ts_tree.root_node());
1211        assert!(!root.has_sibling(Ancestors::unknown(), absent_id));
1212        for &id in &kinds {
1213            assert!(
1214                !root.has_sibling(Ancestors::unknown(), id),
1215                "root node has no parent → no sibling"
1216            );
1217        }
1218    }
1219
1220    /// `children()` must yield exactly the node's direct children, in
1221    /// order, for every node in a real tree — including the empty
1222    /// (leaf) and single-child cases. Termination is cursor-driven, so
1223    /// the emitted set is compared node-by-node against the raw
1224    /// tree-sitter `child(i)` walk (the ground truth for both order and
1225    /// count). This pins the no-duplicate-padding property: a desync
1226    /// between `child_count` and the cursor walk would surface here as
1227    /// extra trailing duplicates or a length mismatch.
1228    #[cfg(feature = "mozjs")]
1229    #[test]
1230    fn children_matches_tree_sitter_child_walk() {
1231        // Mix of leaf nodes (no children), single-child wrappers, and
1232        // multi-child constructs to cover all arities.
1233        let code = b"const o = { m: (a) => a + 1 }; foo(); ;";
1234        let tree = Tree::new::<MozjsCode>(code);
1235        let ts_tree = tree.as_ts_tree();
1236
1237        let mut stack = vec![ts_tree.root_node()];
1238        while let Some(n) = stack.pop() {
1239            let wrapped = Node(n);
1240
1241            // Ground truth: walk children by index off the raw node.
1242            let expected: Vec<_> = (0..n.child_count() as u32)
1243                .filter_map(|i| n.child(i))
1244                .map(|c| (c.id(), c.kind_id()))
1245                .collect();
1246
1247            let actual =
1248                drain_checking_exact_size(wrapped.children(), expected.len(), "children", n.kind());
1249            assert_eq!(
1250                actual,
1251                expected,
1252                "children() diverged from child(i) walk at kind {}",
1253                n.kind(),
1254            );
1255
1256            for i in 0..n.child_count() as u32 {
1257                if let Some(c) = n.child(i) {
1258                    stack.push(c);
1259                }
1260            }
1261        }
1262    }
1263
1264    /// `child_by_field_name` (issue #786) must return the child at the
1265    /// underlying tree lifetime `'a`, not the method-call borrow of
1266    /// `&self`. The proof is a helper whose return type *requires* the
1267    /// child to outlive an intermediate `&Node` borrow: under the old
1268    /// `Option<Node<'_>>` signature the returned node would be tied to
1269    /// `parent`'s borrow and this would fail to compile. Binding the
1270    /// child to a variable that outlives the `&parent` reborrow inside
1271    /// the helper exercises the widened lifetime.
1272    #[cfg(feature = "cpp")]
1273    #[test]
1274    fn child_by_field_name_outlives_self_borrow() {
1275        // `find_named_child` takes the parent by value, reborrows it
1276        // through a `&` reference to call `child_by_field_name`, and
1277        // returns the child. The returned `Node<'a>` must survive past
1278        // that inner `&parent` borrow — only possible because the child
1279        // carries the tree lifetime, not the borrow of `&parent`.
1280        fn find_named_child<'a>(parent: Node<'a>) -> Option<Node<'a>> {
1281            let borrowed: &Node<'a> = &parent;
1282            borrowed.child_by_field_name("declarator")
1283        }
1284
1285        let code = b"int answer = 42;";
1286        let tree = Tree::new::<crate::langs::CppCode>(code);
1287        let root = tree.get_root();
1288
1289        // Walk to the `declaration` node, then pull its `declarator`
1290        // child out and hold it after the producing borrow has ended.
1291        let mut held: Option<Node> = None;
1292        let mut stack = vec![root];
1293        while let Some(n) = stack.pop() {
1294            if n.kind() == "declaration" {
1295                // `find_named_child` consumes a copy of `n`; the result
1296                // must remain valid here, well past the inner borrow.
1297                held = find_named_child(n);
1298                break;
1299            }
1300            for child in n.children() {
1301                stack.push(child);
1302            }
1303        }
1304
1305        let declarator = held.expect("C declaration has a `declarator` field");
1306        // The held node is still usable: it kept its tree linkage rather
1307        // than dangling at the end of the producing borrow.
1308        assert_eq!(declarator.kind(), "init_declarator");
1309    }
1310
1311    /// `Node::as_tree_sitter` (issue #556) must hand back the *same*
1312    /// underlying `tree_sitter::Node` the wrapper holds: identical
1313    /// `kind()` / `kind_id()` and a usable tree-sitter API. Obtaining
1314    /// the wrapper through the public `CppParser` + `ParserTrait::root`
1315    /// path (rather than the in-module `Tree::new`) proves the accessor
1316    /// is the public seam that replaced the former `pub` `.0` field.
1317    #[cfg(feature = "cpp")]
1318    #[test]
1319    fn as_tree_sitter_round_trips_wrapper_kind() {
1320        use crate::{CppParser, ParserTrait};
1321        use std::path::Path;
1322
1323        let source = b"int main() { return 0; }";
1324        let parser = CppParser::new(source.to_vec(), Path::new("example.cpp"), None);
1325        let root = parser.root();
1326
1327        let ts_root = root.as_tree_sitter();
1328
1329        // A well-formed C++ translation unit roots at `translation_unit`.
1330        assert_eq!(ts_root.kind(), "translation_unit");
1331        // The accessor must agree with the wrapper's own kind views.
1332        assert_eq!(ts_root.kind(), root.kind());
1333        assert_eq!(ts_root.kind_id(), root.kind_id());
1334        // The returned node is usable as a tree-sitter node, not a copy
1335        // that has lost its tree linkage: the parse is error-free and
1336        // the root has children.
1337        assert!(!ts_root.has_error());
1338        assert!(ts_root.child_count() > 0);
1339    }
1340
1341    /// Ground-truth pre-order walk over the raw tree-sitter node, by
1342    /// document order (`child(0..child_count)`). [`Node::preorder`] must
1343    /// emit exactly this sequence of node ids — node first, then each
1344    /// child subtree left to right.
1345    #[cfg(feature = "cpp")]
1346    fn ground_truth_preorder(node: OtherNode) -> Vec<usize> {
1347        let mut out = vec![node.id()];
1348        for i in 0..node.child_count() as u32 {
1349            if let Some(child) = node.child(i) {
1350                out.extend(ground_truth_preorder(child));
1351            }
1352        }
1353        out
1354    }
1355
1356    #[cfg(feature = "cpp")]
1357    #[test]
1358    fn preorder_matches_recursive_document_order() {
1359        // A nested construct (function holding a declaration and a call)
1360        // gives the walk real depth and sibling fan-out to order.
1361        let code = b"int main() { int x = 1; foo(x); return 0; }";
1362        let tree = Tree::new::<crate::langs::CppCode>(code);
1363        let root = tree.get_root();
1364
1365        let actual: Vec<usize> = root.preorder().map(|n| n.id()).collect();
1366        let expected = ground_truth_preorder(root.as_tree_sitter());
1367
1368        assert_eq!(
1369            actual, expected,
1370            "preorder diverged from recursive child(0..n) document order"
1371        );
1372        // Sanity: a non-trivial tree, and the root is visited first.
1373        assert!(actual.len() > 5, "expected a multi-node tree");
1374        assert_eq!(actual[0], root.id(), "root must be yielded first");
1375    }
1376
1377    #[cfg(feature = "cpp")]
1378    #[test]
1379    fn descendants_by_kind_collects_matching_subtree_nodes() {
1380        // `x` is declared once and used twice, so three `identifier`
1381        // nodes exist under the function; `main` is an identifier too.
1382        let code = b"int main() { int x = 1; return x + x; }";
1383        let tree = Tree::new::<crate::langs::CppCode>(code);
1384        let root = tree.get_root();
1385
1386        let found = root.descendants_by_kind(&["identifier"]);
1387        // Cross-check against an independent pre-order count so the helper
1388        // cannot pass by matching everything or nothing.
1389        let expected: Vec<usize> = root
1390            .preorder()
1391            .filter(|n| n.kind() == "identifier")
1392            .map(|n| n.id())
1393            .collect();
1394        let actual: Vec<usize> = found.iter().map(Node::id).collect();
1395        assert_eq!(actual, expected);
1396        assert!(
1397            found.len() >= 3,
1398            "expected at least the `main`, `x` decl, and `x` uses"
1399        );
1400        assert!(
1401            found.iter().all(|n| n.kind() == "identifier"),
1402            "every collected node must match the requested kind"
1403        );
1404
1405        // An absent kind yields nothing; a multi-kind filter unions.
1406        assert!(root.descendants_by_kind(&["no_such_kind"]).is_empty());
1407        assert!(
1408            root.descendants_by_kind(&["identifier", "number_literal"])
1409                .len()
1410                > found.len(),
1411            "adding `number_literal` must widen the match set"
1412        );
1413    }
1414
1415    /// Drains `iter`, holding it to the `ExactSizeIterator` contract at
1416    /// every step, and returns the `(id, kind_id)` of each child yielded.
1417    ///
1418    /// `len()` must equal the node's `child_count` before the first step,
1419    /// fall by exactly one per yield, and be zero at exhaustion. Both
1420    /// child iterators are checked against it, so the contract is stated
1421    /// once — `children_with` exists to save an allocation, and a
1422    /// separate copy of this is how the two would come to disagree.
1423    #[cfg(feature = "mozjs")]
1424    fn drain_checking_exact_size<'a>(
1425        mut iter: impl ExactSizeIterator<Item = Node<'a>>,
1426        child_count: usize,
1427        what: &str,
1428        kind: &str,
1429    ) -> Vec<(usize, u16)> {
1430        assert_eq!(
1431            iter.len(),
1432            child_count,
1433            "{what}().len() disagreed with child_count at kind {kind}"
1434        );
1435        let mut remaining = child_count;
1436        let mut drained = Vec::with_capacity(remaining);
1437        while let Some(child) = iter.next() {
1438            remaining -= 1;
1439            assert_eq!(
1440                iter.len(),
1441                remaining,
1442                "{what}() size_hint drifted mid-iteration at kind {kind}"
1443            );
1444            drained.push((child.id(), child.kind_id()));
1445        }
1446        assert_eq!(
1447            iter.len(),
1448            0,
1449            "{what}() was not drained to zero len at kind {kind}"
1450        );
1451        drained
1452    }
1453
1454    /// Ancestor ids yielded by `ancestors`, nearest first.
1455    #[cfg(any(
1456        feature = "c",
1457        feature = "elixir",
1458        feature = "java",
1459        feature = "javascript",
1460        feature = "kotlin",
1461        feature = "python",
1462        feature = "ruby",
1463        feature = "rust",
1464    ))]
1465    fn ancestor_ids(ancestors: Ancestors<'_, '_>, node: &Node<'_>) -> Vec<usize> {
1466        ancestors.iter(node).map(|(a, _)| a.id()).collect()
1467    }
1468
1469    /// A known chain must answer every ancestor question exactly as
1470    /// climbing with `Node::parent` does — that equivalence is the whole
1471    /// premise of #1084, and it is what lets the predicates keep their
1472    /// original logic while dropping the `O(depth)` lookup.
1473    ///
1474    /// Checked node-by-node over one fixture per grammar family that
1475    /// actually consults an ancestor: C-family (`is_else_if` via the
1476    /// parent clause, `loc`'s declaration gate), JVM-family
1477    /// (`is_else_if` via the preceding `else` token), Python (the
1478    /// grandparent shape), and Elixir (`quote` templates).
1479    #[cfg(all(
1480        feature = "c",
1481        feature = "elixir",
1482        feature = "java",
1483        feature = "javascript",
1484        feature = "kotlin",
1485        feature = "python",
1486        feature = "ruby",
1487        feature = "rust",
1488    ))]
1489    #[test]
1490    fn a_known_chain_answers_exactly_what_climbing_answers() {
1491        /// `must_nest` names kinds that have to appear *inside another
1492        /// node of the same kind* in the fixture. `visited > 20` alone
1493        /// does not keep a fixture honest: a grammar bump that flattened
1494        /// the nesting a row was added for would leave a large,
1495        /// clean-parsing tree that no longer exercises the shape, and
1496        /// the parity assertions would keep passing over it.
1497        #[cfg(any(
1498            feature = "c",
1499            feature = "elixir",
1500            feature = "java",
1501            feature = "javascript",
1502            feature = "kotlin",
1503            feature = "python",
1504            feature = "ruby",
1505            feature = "rust",
1506        ))]
1507        fn assert_parity<L: LanguageInfo>(label: &str, code: &[u8], must_nest: &[&str]) {
1508            let mut nested_seen = vec![false; must_nest.len()];
1509            let visited = for_each_node_with_chain::<L>(code, |node, chain| {
1510                for (slot, kind) in nested_seen.iter_mut().zip(must_nest) {
1511                    *slot |= node.kind() == *kind
1512                        && chain.iter().any(|ancestor| ancestor.kind() == *kind);
1513                }
1514                let known = Ancestors::known(chain);
1515                let climbing = Ancestors::unknown();
1516                assert_eq!(
1517                    known.parent(node).map(|p| p.id()),
1518                    climbing.parent(node).map(|p| p.id()),
1519                    "{label}: parent of {} disagrees",
1520                    node.kind()
1521                );
1522                assert_eq!(
1523                    known.previous_sibling(node).map(|p| p.id()),
1524                    climbing.previous_sibling(node).map(|p| p.id()),
1525                    "{label}: previous sibling of {} disagrees",
1526                    node.kind()
1527                );
1528                assert_eq!(
1529                    ancestor_ids(known, node),
1530                    ancestor_ids(climbing, node),
1531                    "{label}: ancestor chain of {} disagrees",
1532                    node.kind()
1533                );
1534                // Each ancestor is handed *its* own chain, so a
1535                // predicate applied one level up stays as cheap and as
1536                // correct as one applied to the node itself.
1537                for (ancestor, above) in known.iter(node) {
1538                    assert_eq!(
1539                        above.parent(&ancestor).map(|p| p.id()),
1540                        ancestor.parent().map(|p| p.id()),
1541                        "{label}: sub-chain handed to {} is not its own",
1542                        ancestor.kind()
1543                    );
1544                }
1545            });
1546            assert!(visited > 20, "{label}: fixture is too small to prove much");
1547            for (found, kind) in nested_seen.iter().zip(must_nest) {
1548                assert!(
1549                    found,
1550                    "{label}: no `{kind}` sits inside another `{kind}`, so the \
1551                     fixture no longer exercises the nesting it was added for"
1552                );
1553            }
1554        }
1555
1556        assert_parity::<crate::langs::CCode>(
1557            "c",
1558            b"int main() { if (a) { int x; } else if (b) { for (int i = 0; i < 2; i++) x; } }",
1559            &[],
1560        );
1561        assert_parity::<crate::langs::JavaCode>(
1562            "java",
1563            b"class A { void m() { if (a) {} else if (b) {} else {} for (int i = 0; i < 2; i++) {} } }",
1564            &[],
1565        );
1566        assert_parity::<crate::langs::PythonCode>(
1567            "python",
1568            b"def f(a, b):\n    if a:\n        pass\n    else:\n        if b:\n            pass\n    return a and b or a\n",
1569            &[],
1570        );
1571        assert_parity::<crate::langs::ElixirCode>(
1572            "elixir",
1573            b"defmodule M do\n  def g do\n    :ok\n  end\n  quote do\n    def f do\n      :ok\n    end\n  end\nend\n",
1574            &["call"],
1575        );
1576
1577        // The shapes #1062 added as consumers, which the four fixtures
1578        // above do not contain: a function nested inside a function
1579        // (every language's `increment_function_depth` arm asks the
1580        // chain for one) and the two default-arm checks that
1581        // now read `Ancestors::parent` — Kotlin's `else ->` inside a
1582        // `when` and Ruby's `else` inside a `case`. Parity over the
1583        // machinery is not parity over the shape a caller asks about.
1584        assert_parity::<crate::langs::RustCode>(
1585            "rust",
1586            b"fn f(a: bool) { if a { } else if a { } fn g(b: bool) { if b { } } }\n",
1587            &["function_item"],
1588        );
1589        assert_parity::<crate::langs::KotlinCode>(
1590            "kotlin",
1591            b"fun f(x: Int) {\n    when (x) {\n        1 -> {}\n        else -> {}\n    }\n    fun g() {\n        if (x > 0) {}\n    }\n}\n",
1592            &["function_declaration"],
1593        );
1594        assert_parity::<crate::langs::RubyCode>(
1595            "ruby",
1596            b"def f(x)\n  case x\n  when 1 then 1\n  else 2\n  end\n  def g\n    if x\n    end\n  end\nend\n",
1597            &["method"],
1598        );
1599
1600        // The shape #1088 added as a consumer: the JS-family
1601        // callable and closure tests walk upward from an
1602        // `arrow_function` / `function_expression` looking for the
1603        // binding that names it, and end on `Ancestors::previous_sibling`
1604        // through `has_sibling`. None of the fixtures above contains
1605        // either node.
1606        assert_parity::<crate::langs::JavascriptCode>(
1607            "javascript",
1608            b"const f = a => { a => { g(() => 1); }; };\nconst o = { m: function () { return 1; } };\n",
1609            &["arrow_function"],
1610        );
1611    }
1612
1613    /// The traversals #1112 moved onto [`Node::children_with`] must scan
1614    /// a whole tree on one cursor, not one per node.
1615    ///
1616    /// Nothing in the output says so: `children_with` yields exactly
1617    /// what `children` yields, so every metric, marker, and pre-order
1618    /// assertion in the suite holds just as well with a fresh
1619    /// `TreeCursor` built and freed per visited node. The counter is the
1620    /// only observable, which is why reverting one of these loops has to
1621    /// be a test failure rather than a silent allocation per node. The
1622    /// metric and suppression walks are guarded the same way from
1623    /// `big-code-analysis`, where they live.
1624    ///
1625    /// Seeding a real scan first is what makes it falsifiable: compared
1626    /// against zero these assertions would also pass with `record()`
1627    /// never wired up at all.
1628    // `python` and `rust` were stale: the body builds only `CCode` and
1629    // `MozjsCode`, so naming them kept the test out of builds that could
1630    // run it.
1631    #[cfg(all(feature = "c", feature = "mozjs"))]
1632    #[test]
1633    fn the_converted_traversals_scan_a_tree_on_one_cursor() {
1634        let seed_tree = Tree::new::<crate::langs::CCode>(b"int main() { int a; }");
1635        let _ = seed_tree.get_root().children().count();
1636        assert!(
1637            child_scan_cursors::observed() > 0,
1638            "the seed scan must be counted"
1639        );
1640
1641        // `preorder` over a tree far larger than any per-call constant,
1642        // so "one per node" and "one per walk" cannot be confused.
1643        let tree = Tree::new::<MozjsCode>(
1644            b"const o = { m: (a) => a + 1, n: function () { return [1, 2, 3]; } };\nfoo(o);\n",
1645        );
1646        let before = child_scan_cursors::observed();
1647        let visited = tree.get_root().preorder().count();
1648        assert!(visited > 40, "fixture is too small to prove much");
1649        assert_eq!(
1650            child_scan_cursors::observed(),
1651            before,
1652            "preorder built a cursor per node; it holds one for the walk (#1112)"
1653        );
1654
1655        // The `Search` walk, `act_on_node`. The counter records in
1656        // `children()`, the allocating form, so a walk that hoists its
1657        // cursor records nothing at all and a per-node one records once
1658        // per interior node. Asserting the exact zero is what tells a
1659        // hoisted cursor from a per-node one; a bound like `< nodes / 2`
1660        // would hold for either on a small fixture.
1661        let tree = Tree::new::<MozjsCode>(
1662            b"function f(a) { return { g: (b) => b + 1, h: [1, 2, 3] }; }\nf(2);\n",
1663        );
1664        let root = tree.get_root();
1665        let nodes = root.preorder().count();
1666        assert!(nodes > 30, "fixture is too small to prove much");
1667
1668        let before = child_scan_cursors::observed();
1669        let mut seen = 0_usize;
1670        root.act_on_node(&mut |_, _| seen += 1);
1671        let scans = child_scan_cursors::observed() - before;
1672        assert_eq!(seen, nodes, "act_on_node must visit every node");
1673        assert_eq!(
1674            scans, 0,
1675            "act_on_node built {scans} cursors over {nodes} nodes; it holds one \
1676             for the walk (#1112)"
1677        );
1678    }
1679
1680    /// `act_on_node` lends a `FoldCache`, so the `string` filter's Tcl
1681    /// role question scans a wide erroring `eval` line once per walk
1682    /// rather than once per braced word (#1686). The filter answers the
1683    /// same either way — none of the words is a string, since an
1684    /// unreadable list keeps the script answer — so the scan count is
1685    /// what sees the cache; rebuilding the walk's chain with
1686    /// `Ancestors::for_walk_chain_only`, the cache unlent, takes it to
1687    /// `width`.
1688    #[cfg(feature = "tcl")]
1689    #[test]
1690    fn act_on_node_scans_an_erroring_argument_list_once() {
1691        use crate::lang_helpers::argument_slot_scans;
1692        use crate::langs::TclCode;
1693
1694        let width = 200;
1695        let code = crate::test_support::tcl_wide_erroring_eval(width);
1696        let code = code.as_bytes();
1697        let tree = Tree::new::<TclCode>(code);
1698        let root = tree.get_root();
1699        let before = argument_slot_scans::observed();
1700        let (mut strings, mut words) = (0_usize, 0_usize);
1701        root.act_on_node(&mut |node, ancestors| {
1702            words += usize::from(node.kind_id() == crate::Tcl::BracedWord as u16);
1703            strings += usize::from(TclCode::is_string_with_code(node, code, ancestors));
1704        });
1705        assert_eq!(
1706            argument_slot_scans::observed() - before,
1707            1,
1708            "the walk lends one cache for the whole tree"
1709        );
1710        assert_eq!(words, width, "the fixture must reach every braced word");
1711        assert_eq!(
1712            strings, 0,
1713            "an unreadable `eval` list keeps every word a script"
1714        );
1715    }
1716
1717    /// [`Node::parent_grandparent_match`] must answer `false` when
1718    /// either link is missing, rather than degrading to a
1719    /// single-predicate check.
1720    ///
1721    /// Its doc states that invariant and Python's `Cyclomatic` `else`
1722    /// arm depends on it, but nothing exercised either absent-link
1723    /// return: every call in the suite runs on a node that has both a
1724    /// parent and a grandparent. Both predicates answer `true` here, so
1725    /// a `false` result can only come from the missing link — an
1726    /// implementation that skipped the second `climb.next()` and
1727    /// returned `parent_pred`'s answer would pass every other test and
1728    /// fail this one.
1729    ///
1730    /// Checked through both `Ancestors` constructors: the chain and the
1731    /// climb reach the end by different code paths (`split_last` on an
1732    /// empty slice, versus `Node::parent` returning `None`).
1733    #[cfg(feature = "c")]
1734    #[test]
1735    fn parent_grandparent_match_is_false_when_either_link_is_absent() {
1736        let tree = Tree::new::<crate::langs::CCode>(b"int main() { int a; }");
1737        let root = tree.get_root();
1738        let child = root.children().next().expect("the file has an item");
1739        let grandchild = child
1740            .children()
1741            .next()
1742            .expect("the function definition has children");
1743        let yes: fn(&Node) -> bool = |_| true;
1744
1745        // No parent at all: the root, reached either way.
1746        assert!(!root.parent_grandparent_match(Ancestors::unknown(), yes, yes));
1747        assert!(!root.parent_grandparent_match(Ancestors::known(&[]), yes, yes));
1748
1749        // A parent but no grandparent: a direct child of the root.
1750        assert!(!child.parent_grandparent_match(Ancestors::unknown(), yes, yes));
1751        assert!(!child.parent_grandparent_match(Ancestors::known(&[root]), yes, yes));
1752
1753        // Both links present, so the same predicates now answer `true`.
1754        // Without this the assertions above would also hold for a
1755        // function that always returned `false`.
1756        assert!(grandchild.parent_grandparent_match(Ancestors::unknown(), yes, yes));
1757        assert!(grandchild.parent_grandparent_match(Ancestors::known(&[root, child]), yes, yes));
1758    }
1759
1760    /// [`Node::children_with`] must yield exactly what
1761    /// [`Node::children`] yields — same nodes, same order, same
1762    /// `ExactSizeIterator` length at every step — for every node of a
1763    /// real tree.
1764    ///
1765    /// Checked against the raw `child(i)` walk rather than against
1766    /// `children()`: the two iterators share `ChildScan`, so a
1767    /// comparison between them would pass just as happily if the shared
1768    /// step were wrong. It also covers the reuse itself — one cursor
1769    /// drives every node's scan here, so a `reset` that failed to rewind
1770    /// would show as the second node inheriting the first's position.
1771    #[cfg(feature = "mozjs")]
1772    #[test]
1773    fn children_with_yields_exactly_what_children_does() {
1774        let code = b"const o = { m: (a) => a + 1, n: function () {} }; foo(); ;";
1775        let tree = Tree::new::<MozjsCode>(code);
1776        let root = tree.get_root();
1777
1778        let mut cursor = root.cursor();
1779        let mut leaves = 0;
1780        let mut widest = 0;
1781        for node in root.preorder() {
1782            // Ground truth is the raw `child(i)` walk, not `children()`.
1783            // The two iterators share `ChildScan`, so checking one
1784            // against the other would pass just as happily if the shared
1785            // step were wrong.
1786            let raw = node.as_tree_sitter();
1787            let expected: Vec<_> = (0..raw.child_count() as u32)
1788                .filter_map(|i| raw.child(i))
1789                .map(|c| (c.id(), c.kind_id()))
1790                .collect();
1791
1792            let actual = drain_checking_exact_size(
1793                node.children_with(&mut cursor),
1794                expected.len(),
1795                "children_with",
1796                node.kind(),
1797            );
1798            assert_eq!(
1799                actual,
1800                expected,
1801                "children_with diverged from the child(i) walk at kind {}",
1802                node.kind()
1803            );
1804
1805            leaves += usize::from(expected.is_empty());
1806            widest = widest.max(expected.len());
1807        }
1808        // Both ends of the arity range, else the comparison could hold
1809        // over nothing but one-child wrappers.
1810        assert!(leaves > 0, "fixture must contain childless nodes");
1811        assert!(widest > 2, "fixture must contain a multi-child node");
1812    }
1813
1814    /// `children_after` and `children_before` must yield, for every child
1815    /// of every node, the raw `child(i)` walk on either side of it — and
1816    /// nothing for a node that is not a child.
1817    ///
1818    /// The Kotlin fixture's recovery inserts a zero-width parameter name
1819    /// (`vararg: Int`), which `goto_first_child_for_byte` passes over, so
1820    /// it is the only input that reaches the scan fallback in
1821    /// `seat_on_child`; the count of such children pins that it does.
1822    #[cfg(feature = "kotlin")]
1823    #[test]
1824    fn children_after_and_before_match_the_child_walk() {
1825        let code = b"fun f(vararg: Int, /* c */ b: Int) { g(1, 2, 3) }";
1826        let tree = Tree::new::<crate::langs::KotlinCode>(code);
1827        let root = tree.get_root();
1828
1829        // Each row is (parent kind, child index, after ids, before ids), and
1830        // a non-child row is (kind, after count, before count) against the
1831        // root, so a failing diff names the node without a message argument.
1832        let mut zero_width = 0;
1833        let (mut observed, mut expected) = (Vec::new(), Vec::new());
1834        let (mut stray_observed, mut stray_expected) = (Vec::new(), Vec::new());
1835        for node in root.preorder() {
1836            let raw = node.as_tree_sitter();
1837            let ids: Vec<_> = (0..raw.child_count() as u32)
1838                .filter_map(|i| raw.child(i))
1839                .map(|c| c.id())
1840                .collect();
1841            for (index, child) in node.children().enumerate() {
1842                zero_width += usize::from(child.start_byte() == child.end_byte());
1843                observed.push((
1844                    node.kind(),
1845                    index,
1846                    node.children_after(&child)
1847                        .map(|c| c.id())
1848                        .collect::<Vec<_>>(),
1849                    node.children_before(&child)
1850                        .map(|c| c.id())
1851                        .collect::<Vec<_>>(),
1852                ));
1853                expected.push((
1854                    node.kind(),
1855                    index,
1856                    ids[index + 1..].to_vec(),
1857                    ids[..index].iter().rev().copied().collect(),
1858                ));
1859            }
1860            if node.id() != root.id() {
1861                stray_observed.push((
1862                    node.kind(),
1863                    root.children_after(&node).count(),
1864                    root.children_before(&node).count(),
1865                ));
1866                stray_expected.push((node.kind(), 0, 0));
1867            }
1868        }
1869        assert_eq!(observed, expected);
1870        assert_eq!(stray_observed, stray_expected);
1871        assert!(
1872            zero_width > 0,
1873            "fixture must hold an inserted zero-width child"
1874        );
1875    }
1876
1877    /// The `O(1)` guard the walk constructors keep on by default, asked
1878    /// here through [`Ancestors::for_walk_chain_only`], must accept
1879    /// every chain a walker really builds — over several grammar
1880    /// families, not just the one fixture a failure would surface in.
1881    ///
1882    /// The assertion that an equal-span pair was seen is what makes the
1883    /// containment non-strict on purpose rather than by luck: a
1884    /// single-child wrapper (`expression_statement` over its expression,
1885    /// say) spans exactly what its child spans, so tightening either
1886    /// bound to `<` would reject a correct chain on most real input.
1887    #[cfg(all(feature = "c", feature = "javascript", feature = "python"))]
1888    #[test]
1889    fn the_chain_check_accepts_the_chains_the_walkers_build() {
1890        let mut equal_span_pairs = 0;
1891        let mut check = |node: &Node<'_>, chain: &[Node<'_>]| {
1892            let _ = Ancestors::for_walk_chain_only(chain, node);
1893            if let Some(parent) = chain.last()
1894                && parent.start_byte() == node.start_byte()
1895                && parent.end_byte() == node.end_byte()
1896            {
1897                equal_span_pairs += 1;
1898            }
1899        };
1900        let visited = for_each_node_with_chain::<crate::langs::CCode>(
1901            b"int main() { if (a) { int x; } else { f(a, b); } }",
1902            &mut check,
1903        ) + for_each_node_with_chain::<crate::langs::JavascriptCode>(
1904            b"const o = { m: (a) => a + 1 };\nfoo.bar();\n",
1905            &mut check,
1906        ) + for_each_node_with_chain::<crate::langs::PythonCode>(
1907            b"def f(a):\n    if a:\n        return [x for x in a]\n",
1908            &mut check,
1909        );
1910
1911        assert!(visited > 60, "fixtures are too small to prove much");
1912        assert!(
1913            equal_span_pairs > 0,
1914            "no parent spans exactly what its child does, so this fixture set \
1915             cannot tell non-strict containment from strict"
1916        );
1917    }
1918
1919    /// A `push` moved ahead of the per-node computes leaves the node
1920    /// itself as `chain.last()`. Spans alone cannot see that — a node
1921    /// contains itself — so the identity half of the guard is what
1922    /// catches it.
1923    ///
1924    /// Debug-gated because the check is a `debug_assert!`, which
1925    /// `--release` compiles out by design.
1926    #[cfg(feature = "c")]
1927    #[test]
1928    #[cfg(debug_assertions)]
1929    #[should_panic(expected = "ancestor chain desynchronised")]
1930    fn the_chain_check_rejects_a_chain_ending_in_the_node_itself() {
1931        let tree = Tree::new::<crate::langs::CCode>(b"int main() { int a; }");
1932        let body = tree
1933            .get_root()
1934            .preorder()
1935            .find(|n| n.kind() == "compound_statement")
1936            .expect("fixture has a function body");
1937        let _ = Ancestors::for_walk_chain_only(std::slice::from_ref(&body), &body);
1938    }
1939
1940    /// A dropped `truncate` leaves the previous subtree's path in place,
1941    /// so the next node up gets a `chain.last()` from a sibling subtree —
1942    /// disjoint from it in bytes. That is the containment half.
1943    #[cfg(feature = "c")]
1944    #[test]
1945    #[cfg(debug_assertions)]
1946    #[should_panic(expected = "ancestor chain desynchronised")]
1947    fn the_chain_check_rejects_a_chain_from_a_disjoint_subtree() {
1948        let tree = Tree::new::<crate::langs::CCode>(b"int main() { int a; int b; }");
1949        let body = tree
1950            .get_root()
1951            .preorder()
1952            .find(|n| n.kind() == "compound_statement")
1953            .expect("fixture has a function body");
1954        let declarations: Vec<Node<'_>> = body
1955            .children()
1956            .filter(|n| n.kind() == "declaration")
1957            .collect();
1958        assert_eq!(declarations.len(), 2, "fixture has two declarations");
1959        // `int a;` neither contains nor equals `int b;`.
1960        let _ = Ancestors::for_walk_chain_only(&declarations[..1], &declarations[1]);
1961    }
1962
1963    /// [`Node::has_sibling`] must answer the same whether its parent
1964    /// comes off a known chain or from `Node::parent`.
1965    ///
1966    /// The parent lookup is the only thing #1088 changed here, and it is
1967    /// the half a caller cannot see: the JS binding gate folds the
1968    /// answer into a disjunction, so a wrong parent would silently
1969    /// reclassify an arrow function rather than fail. Checked for every
1970    /// node against every kind the fixture contains, plus one that never
1971    /// occurs so the absent-sibling answer is covered too.
1972    #[cfg(feature = "javascript")]
1973    #[test]
1974    fn has_sibling_agrees_between_known_and_climbing() {
1975        // Object-literal methods and an arrow bound to a property are
1976        // the shapes whose `PropertyIdentifier` sibling the JS closure
1977        // check asks about.
1978        let code = b"const o = { m: (a) => a + 1, n: function () {} };\nconst p = a => a;\n";
1979        let mut kinds = std::collections::BTreeSet::new();
1980        for_each_node_with_chain::<crate::langs::JavascriptCode>(code, |node, _| {
1981            kinds.insert(node.kind_id());
1982        });
1983        // An id no node in the fixture carries, so the `false` answer is
1984        // exercised as well as the `true` one.
1985        let absent = u16::MAX;
1986        let mut agreed_true = 0;
1987        let visited =
1988            for_each_node_with_chain::<crate::langs::JavascriptCode>(code, |node, chain| {
1989                for &id in kinds.iter().chain(std::iter::once(&absent)) {
1990                    let known = node.has_sibling(Ancestors::known(chain), id);
1991                    let climbing = node.has_sibling(Ancestors::unknown(), id);
1992                    assert_eq!(
1993                        known,
1994                        climbing,
1995                        "has_sibling({id}) on {} disagrees between chain and climb",
1996                        node.kind()
1997                    );
1998                    agreed_true += usize::from(known);
1999                }
2000            });
2001        assert!(visited > 20, "fixture is too small to prove much");
2002        assert!(
2003            agreed_true > 0,
2004            "every answer was `false`, so the sibling scan never ran to a match"
2005        );
2006    }
2007
2008    /// [`Search::act_on_node`] must hand each node its true ancestry
2009    /// even when the walk starts below the tree root.
2010    ///
2011    /// The seed is what decides this. [`Ancestors`] reads an empty chain
2012    /// as "this node is the root", so seeding empty — which is correct
2013    /// for every caller today (`bca function`, `find` and `count`, whose
2014    /// walks all start at the root) — would report no parent for the
2015    /// subtree root and shift every answer beneath it. For the JS getters
2016    /// that means
2017    /// losing the `variable_declarator` a `function_expression` takes
2018    /// its name from, so the space would silently be named
2019    /// `<anonymous>`.
2020    ///
2021    /// No caller passes a subtree yet, so nothing else would catch this;
2022    /// the fixture below is the guard. It fails against an empty seed
2023    /// here, and under `make chain-audit` through the walk constructors'
2024    /// exact parent check; their default `O(1)` check passes an empty
2025    /// chain.
2026    #[cfg(feature = "mozjs")]
2027    #[test]
2028    fn act_on_node_hands_a_subtree_its_real_ancestry() {
2029        let code = b"var outer = function () { return 1; };\n";
2030        let tree = Tree::new::<MozjsCode>(code);
2031        let root = tree.get_root();
2032        let subtree = root
2033            .preorder()
2034            .find(|n| n.kind() == "variable_declarator")
2035            .expect("fixture has a variable_declarator");
2036        assert!(
2037            subtree.parent().is_some(),
2038            "the walk must start below the root, else the seed is vacuous"
2039        );
2040
2041        let mut visited = 0;
2042        subtree.act_on_node(&mut |node, ancestors| {
2043            assert_eq!(
2044                ancestors.parent(node).map(|p| p.id()),
2045                node.parent().map(|p| p.id()),
2046                "parent of {} disagrees with the tree",
2047                node.kind()
2048            );
2049            visited += 1;
2050        });
2051        assert!(visited > 3, "subtree is too small to prove much");
2052    }
2053
2054    /// A walk started below the root records its seeded ancestors'
2055    /// children too, so a sibling lookup off a wide one is answered from
2056    /// the cache. Without them the lookup's debug assertion fails: the
2057    /// cache is lent, and the wide parent on the chain was never pushed
2058    /// by this walk (#1580).
2059    #[cfg(feature = "mozjs")]
2060    #[test]
2061    fn act_on_node_records_a_wide_seeded_ancestor() {
2062        // Discriminates only through `Ancestors::lookup`'s `debug_assert!`:
2063        // meaningful under `make pre-commit`'s debug build, vacuous under
2064        // `--release` (lesson #80).
2065        let code = "var a = 1;\n".repeat(WIDE_PARENT + 6);
2066        let tree = Tree::new::<MozjsCode>(code.as_bytes());
2067        let root = tree.get_root();
2068        assert!(root.child_count() > WIDE_PARENT, "the root must be wide");
2069        let subtree = root.child(3).expect("fixture has a fourth statement");
2070
2071        let mut after = None;
2072        subtree.act_on_node(&mut |node, ancestors| {
2073            if node.id() == subtree.id() {
2074                after = Some(ancestors.siblings_after(node).count());
2075            }
2076        });
2077        assert_eq!(after, Some(root.child_count() - 4));
2078    }
2079
2080    /// `previous_sibling` must not answer "no previous sibling" when the
2081    /// chain it was handed belongs to a different node.
2082    ///
2083    /// The known path finds the answer by scanning the chain's last
2084    /// entry for `node`; a miss means the caller paired the two wrongly.
2085    /// Reporting `None` there would be a wrong answer dressed as a
2086    /// legitimate one, so the fallback re-asks the tree.
2087    #[cfg(feature = "c")]
2088    #[test]
2089    fn previous_sibling_falls_back_on_a_chain_that_is_not_this_nodes() {
2090        let code = b"int main() { int a; int b; }";
2091        let tree = Tree::new::<crate::langs::CCode>(code);
2092        let root = tree.get_root();
2093        let body = root
2094            .preorder()
2095            .find(|n| n.kind() == "compound_statement")
2096            .expect("fixture has a function body");
2097        let declarations: Vec<Node<'_>> = body
2098            .children()
2099            .filter(|n| n.kind() == "declaration")
2100            .collect();
2101        assert_eq!(declarations.len(), 2, "fixture has two declarations");
2102
2103        let second = declarations[1];
2104        let expected = second
2105            .previous_sibling()
2106            .map(|p| p.id())
2107            .expect("the second declaration has a previous sibling");
2108        // A chain ending in the *root* does not describe `second`, whose
2109        // parent is the function body.
2110        let foreign = [root];
2111        assert_eq!(
2112            Ancestors::known(&foreign)
2113                .previous_sibling(&second)
2114                .map(|p| p.id()),
2115            Some(expected),
2116            "a mismatched chain must fall back, not report `None`"
2117        );
2118        assert!(
2119            Ancestors::known(&[]).previous_sibling(&second).is_none(),
2120            "an empty chain means `second` is the root, which has no siblings"
2121        );
2122    }
2123
2124    /// `count_specific_ancestors` must return the same count whichever
2125    /// way it reaches the ancestors. Uses `loc`'s real C predicate pair
2126    /// (`while`/`for`/`if` header, stopping at the enclosing block), so
2127    /// the fixture exercises both the counted case (the `for`-header
2128    /// declaration) and the stopped case (the block-scoped ones).
2129    #[cfg(feature = "c")]
2130    #[test]
2131    fn count_specific_ancestors_agrees_between_known_and_climbing() {
2132        let code =
2133            b"int main() { int a; if (x) { int b; } for (int i = 0; i < 2; i++) { int c; } }";
2134        let mut counted = 0;
2135        let mut nonzero = 0;
2136        let visited = for_each_node_with_chain::<crate::langs::CCode>(code, |node, chain| {
2137            if node.kind() != "declaration" {
2138                return;
2139            }
2140            let check: fn(&Node) -> bool = |n| {
2141                matches!(
2142                    n.kind(),
2143                    "while_statement" | "for_statement" | "if_statement"
2144                )
2145            };
2146            let stop: fn(&Node) -> bool = |n| n.kind() == "compound_statement";
2147            let known = node.count_specific_ancestors::<crate::langs::CCode>(
2148                Ancestors::known(chain),
2149                check,
2150                stop,
2151            );
2152            let climbing = node.count_specific_ancestors::<crate::langs::CCode>(
2153                Ancestors::unknown(),
2154                check,
2155                stop,
2156            );
2157            assert_eq!(
2158                known,
2159                climbing,
2160                "declaration at row {}: known chain counted {known}, climbing counted {climbing}",
2161                node.start_row()
2162            );
2163            counted += 1;
2164            nonzero += usize::from(known > 0);
2165        });
2166        assert!(visited > 20);
2167        assert_eq!(counted, 4, "fixture must hold four declarations");
2168        assert_eq!(
2169            nonzero, 1,
2170            "only the `for`-header declaration sits under a header with no block between"
2171        );
2172    }
2173
2174    /// A `check` / `stop` predicate pair for the ancestor-gate tests below.
2175    #[cfg(any(feature = "c", feature = "typescript"))]
2176    type Pair = (fn(&Node) -> bool, fn(&Node) -> bool);
2177
2178    /// `Ancestors::has_ancestor_before_stop` answers `count > 0` for every
2179    /// node, whether it folds through a walk's cache, climbs a known chain
2180    /// with none, or climbs with no chain at all (#1767).
2181    ///
2182    /// Two predicate pairs, each built so a broken step changes answers.
2183    /// `loc`'s own (`while`/`for`/`if`, stop at a block) cannot see the
2184    /// `else if` exclusion: an excluded inner `if` always has its outer
2185    /// `if` adjacent above. So the second pair stops at the `else` clause
2186    /// itself — `y` under `else if (b) y;` then has only the excluded
2187    /// inner `if` below the stop — and a node that is both `stop` and
2188    /// `check` (`if_statement` in the third pair) pins stop-wins
2189    /// precedence. Each pair asserts both answers occur.
2190    #[cfg(feature = "c")]
2191    #[test]
2192    fn has_ancestor_before_stop_answers_count_above_zero_on_every_path() {
2193        use crate::node::{FoldCache, GateLane};
2194        let pairs: [(&str, Pair); 3] = [
2195            (
2196                "loc",
2197                (
2198                    |n| {
2199                        matches!(
2200                            n.kind(),
2201                            "while_statement" | "for_statement" | "if_statement"
2202                        )
2203                    },
2204                    |n| n.kind() == "compound_statement",
2205                ),
2206            ),
2207            (
2208                "else-clause stop",
2209                (
2210                    |n| n.kind() == "if_statement",
2211                    |n| n.kind() == "else_clause",
2212                ),
2213            ),
2214            (
2215                "stop and check overlap",
2216                (
2217                    |n| matches!(n.kind(), "if_statement" | "for_statement"),
2218                    |n| matches!(n.kind(), "if_statement" | "compound_statement"),
2219                ),
2220            ),
2221        ];
2222        let code =
2223            b"int main() { int a; if (x) { int b; } for (int i = 0; i < 2; i++) { int c; }\n\
2224                     if (a) x; else if (b) y; else z;\n\
2225                     for (;;) if (c) { int d; } else w; }";
2226        for (label, (check, stop)) in pairs {
2227            let cache = FoldCache::default();
2228            let (mut yes, mut no) = (0_usize, 0_usize);
2229            for_each_node_with_chain::<crate::langs::CCode>(code, |node, chain| {
2230                let expected = node.count_specific_ancestors::<crate::langs::CCode>(
2231                    Ancestors::known(chain),
2232                    check,
2233                    stop,
2234                ) > 0;
2235                let lane = GateLane::InsideHeader;
2236                let folded = Ancestors::known(chain)
2237                    .with_folds(&cache)
2238                    .has_ancestor_before_stop::<crate::langs::CCode>(node, lane, check, stop);
2239                let chained = Ancestors::known(chain)
2240                    .has_ancestor_before_stop::<crate::langs::CCode>(node, lane, check, stop);
2241                let climbed = Ancestors::unknown()
2242                    .has_ancestor_before_stop::<crate::langs::CCode>(node, lane, check, stop);
2243                assert_eq!(
2244                    (folded, chained, climbed),
2245                    (expected, expected, expected),
2246                    "{label}: (folded, chained, climbed) must all be the count's answer"
2247                );
2248                if expected {
2249                    yes += 1;
2250                } else {
2251                    no += 1;
2252                }
2253            });
2254            assert!(
2255                yes > 0 && no > 0,
2256                "{label}: both answers must occur ({yes} / {no})"
2257            );
2258        }
2259    }
2260
2261    /// Two lanes asked of the same nodes in one walk keep their own
2262    /// answers: TypeScript asks every declaration both whether it is
2263    /// exported (stop at a block) and whether it is ambient (no stop),
2264    /// and a lane mix-up would hand one question the other's memo. `lloc`
2265    /// cannot see that — either answer suppresses the line — so the
2266    /// answers are asserted here, per declaration (#1767).
2267    #[cfg(feature = "typescript")]
2268    #[test]
2269    fn two_lanes_asked_of_one_node_keep_their_own_answers() {
2270        use crate::languages::Typescript;
2271        use crate::node::{FoldCache, GateLane};
2272        let exported: Pair = (
2273            |n| n.kind_id() == Typescript::ExportStatement,
2274            |n| n.kind_id() == Typescript::StatementBlock,
2275        );
2276        let ambient: Pair = (|n| n.kind_id() == Typescript::AmbientDeclaration, |_| false);
2277        let code = b"export const a = 1;\n\
2278                     declare const b: number;\n\
2279                     export declare const c: string;\n\
2280                     export declare namespace N { const d: number; }\n\
2281                     declare namespace M { const e: number; }\n\
2282                     const f = 1;\n";
2283        let cache = FoldCache::default();
2284        let mut seen = Vec::new();
2285        for_each_node_with_chain::<crate::langs::TypescriptCode>(code, |node, chain| {
2286            if node.kind() != "lexical_declaration" {
2287                return;
2288            }
2289            let ask = |lane, (check, stop): Pair| {
2290                Ancestors::known(chain)
2291                    .with_folds(&cache)
2292                    .has_ancestor_before_stop::<crate::langs::TypescriptCode>(
2293                        node, lane, check, stop,
2294                    )
2295            };
2296            seen.push((
2297                ask(GateLane::InsideExport, exported),
2298                ask(GateLane::InsideAmbient, ambient),
2299            ));
2300        });
2301        assert_eq!(
2302            seen,
2303            [
2304                (true, false),
2305                (false, true),
2306                (true, true),
2307                // A `statement_block` stands between `d` and the export.
2308                (false, true),
2309                // Ambient, never exported: the export lane stores `false`
2310                // at every depth of `e`'s chain, so a shared lane answers
2311                // the ambient question `false` too. The shallower rows
2312                // cannot show that — their stored states are the root's,
2313                // the same for either question.
2314                (false, true),
2315                (false, false),
2316            ],
2317            "(exported, ambient) per declaration, in source order"
2318        );
2319    }
2320
2321    /// `Ancestors::has_ancestor_of_kind` answers what a climb with
2322    /// `Node::parent` does on each of its three paths — folded through a
2323    /// walk's cache, scanned off a bare chain, climbed with no chain —
2324    /// for every node of the fixture (#1864).
2325    ///
2326    /// `h` is the row a memo keyed on depth alone gets wrong: it sits as
2327    /// deep as `g` under a different parent, which the depths asserted
2328    /// below pin. The second cache is asked
2329    /// only at functions, as the cognitive walk asks, so when `h` asks,
2330    /// the slots still hold what `g`'s chain left: "inside a function",
2331    /// for ancestors that are not `h`'s.
2332    #[cfg(feature = "rust")]
2333    #[test]
2334    fn has_ancestor_of_kind_answers_the_climb_on_every_path() {
2335        use crate::languages::Rust;
2336        use crate::node::{FoldCache, KindLane};
2337        const KINDS: &[u16] = &[Rust::FunctionItem as u16, Rust::ClosureExpression as u16];
2338        let kinds = KINDS;
2339        let code = b"mod a { fn f() { fn g() { let c = || 1; } } }\n\
2340                     mod m { mod n { fn h() {} } }\n\
2341                     fn i() {}\n";
2342        let cache = FoldCache::default();
2343        let asked_at_functions = FoldCache::default();
2344        let lane = KindLane::InsideFunction;
2345        let mut functions = Vec::new();
2346        let mut depths = Vec::new();
2347        let (mut yes, mut no) = (0_usize, 0_usize);
2348        for_each_node_with_chain::<crate::langs::RustCode>(code, |node, chain| {
2349            let expected = std::iter::successors(node.parent(), Node::parent)
2350                .any(|ancestor| kinds.contains(&ancestor.kind_id()));
2351            let folded = Ancestors::known(chain)
2352                .with_folds(&cache)
2353                .has_ancestor_of_kind(node, lane, kinds);
2354            let chained = Ancestors::known(chain).has_ancestor_of_kind(node, lane, kinds);
2355            let climbed = Ancestors::unknown().has_ancestor_of_kind(node, lane, kinds);
2356            let (kind, start) = (node.kind(), node.start_byte());
2357            assert_eq!(
2358                (folded, chained, climbed),
2359                (expected, expected, expected),
2360                "{kind} at byte {start}: (folded, chained, climbed) must all be the climb's answer"
2361            );
2362            if kind == "function_item" {
2363                functions.push(
2364                    Ancestors::known(chain)
2365                        .with_folds(&asked_at_functions)
2366                        .has_ancestor_of_kind(node, lane, kinds),
2367                );
2368                depths.push(chain.len());
2369            }
2370            if expected {
2371                yes += 1;
2372            } else {
2373                no += 1;
2374            }
2375        });
2376        assert_eq!(
2377            functions,
2378            [false, true, false, false],
2379            "f, g, h, i in source order: only g is inside a function"
2380        );
2381        assert_eq!(
2382            depths,
2383            [3, 5, 5, 1],
2384            "h must sit as deep as g to meet the slots g's chain left"
2385        );
2386        assert!(yes > 0 && no > 0, "both answers must occur ({yes} / {no})");
2387    }
2388
2389    /// `nearest_level_answer` answers what the climb answers through
2390    /// all three of its paths — the walk's memo, a known chain with no
2391    /// cache, the chainless climb — for every node of the fixture
2392    /// (#1863).
2393    ///
2394    /// The answer fn says "yes" at a function and "no" at a closure, so
2395    /// a node inside a closure inside a function reads the closure's
2396    /// "no": the nearer answer wins. A node under neither reads `false`,
2397    /// and the answering node itself is not asked: a function's own
2398    /// answer is its ancestors'.
2399    ///
2400    /// The second cache is asked only at integer literals, and the
2401    /// answer fn's calls are counted per ask, which is the memo's whole
2402    /// effect: the answers cannot tell it from the climb. `2` meets the
2403    /// answer `1` left on their shared `binary_expression`; `4` reads
2404    /// its own `let` and meets the one `3` left on the block they
2405    /// share, a level `3` passed without an answer; `7` meets the one
2406    /// `6` left on the closure itself, the level that answered. `3`
2407    /// sits in the tuple after the closure: a memo that handed `1`'s
2408    /// "no" to a level above the closure would answer "no" for it.
2409    #[cfg(feature = "rust")]
2410    #[test]
2411    fn nearest_level_answer_answers_the_climb_on_every_path() {
2412        use crate::node::{FoldCache, LevelQuestion};
2413        use std::cell::Cell;
2414        thread_local! {
2415            static LEVELS_ASKED: Cell<usize> = const { Cell::new(0) };
2416        }
2417        fn level(_code: &[u8], node: &Node, _chain: Ancestors) -> Option<bool> {
2418            LEVELS_ASKED.set(LEVELS_ASKED.get() + 1);
2419            match node.kind() {
2420                "function_item" => Some(true),
2421                "closure_expression" => Some(false),
2422                _ => None,
2423            }
2424        }
2425        let code = b"fn f() { let c = (|| { let d = (1 + 2); }, 3); let e = 4; }\n\
2426                     const K: u8 = 5;\n\
2427                     mod m { fn g() { let h = |_: [u8; 6]| 7; } fn i() { 8; } }\n";
2428        let cache = FoldCache::default();
2429        let asked_at_literals = FoldCache::default();
2430        let question = LevelQuestion::CodeBeforeOnLine;
2431        let mut literals = Vec::new();
2432        let (mut yes, mut no) = (0_usize, 0_usize);
2433        for_each_node_with_chain::<crate::langs::RustCode>(code, |node, chain| {
2434            let expected = std::iter::successors(node.parent(), Node::parent)
2435                .find_map(|ancestor| level(code, &ancestor, Ancestors::unknown()))
2436                .unwrap_or(false);
2437            let memoised = Ancestors::known(chain)
2438                .with_folds(&cache)
2439                .nearest_level_answer(node, question, code, level);
2440            let chained = Ancestors::known(chain).nearest_level_answer(node, question, code, level);
2441            let climbed = Ancestors::unknown().nearest_level_answer(node, question, code, level);
2442            let (kind, start) = (node.kind(), node.start_byte());
2443            assert_eq!(
2444                (memoised, chained, climbed),
2445                (expected, expected, expected),
2446                "{kind} at byte {start}: (memoised, chained, climbed) must all be the climb's answer"
2447            );
2448            if kind == "integer_literal" {
2449                let before = LEVELS_ASKED.get();
2450                let answer = Ancestors::known(chain)
2451                    .with_folds(&asked_at_literals)
2452                    .nearest_level_answer(node, question, code, level);
2453                literals.push((answer, LEVELS_ASKED.get() - before));
2454            }
2455            if expected {
2456                yes += 1;
2457            } else {
2458                no += 1;
2459            }
2460        });
2461        let (answers, asked): (Vec<_>, Vec<_>) = literals.into_iter().unzip();
2462        assert_eq!(
2463            answers,
2464            [false, false, true, true, false, false, false, true],
2465            "1 and 2 in f's closure, 3 and 4 in f, 5 under neither, 6 and 7 in g's closure, 8 in i"
2466        );
2467        // expected: `1` climbs binary, parenthesis, `let`, block and the
2468        // closure; `2` meets the memo on the binary; `3` climbs tuple,
2469        // `let`, block and `f`; `4` its `let`, then the memo on the
2470        // block; `5` the const and the file; `6` the array type, the
2471        // parameter, the parameter list and the closure; `7` meets the
2472        // memo on the closure; `8` the statement, the block and `i`.
2473        // The unmemoised climb asks every level up to the one that
2474        // answers: 5 for `2`, 3 for `4` and 1 for `7`, the rest as
2475        // memoised. `make chain-audit` runs that climb beside every ask,
2476        // so there each count is the two together.
2477        let memoised = [5, 0, 4, 1, 2, 4, 0, 3];
2478        let climbed = [5, 5, 4, 3, 2, 4, 1, 3];
2479        let audited = usize::from(cfg!(chain_audit));
2480        let expected: Vec<usize> = memoised
2481            .iter()
2482            .zip(climbed)
2483            .map(|(memo, climb)| memo + audited * climb)
2484            .collect();
2485        assert_eq!(asked, expected);
2486        assert!(yes > 0 && no > 0, "both answers must occur ({yes} / {no})");
2487    }
2488
2489    /// `is_extra` marks a comment, and it marks the `ERROR` recovery
2490    /// wraps a stray token in, which is why a scan that steps over
2491    /// comments must not skip on it alone (lesson 95). `(name, => 1)` is
2492    /// the shape #1572 met: valid Perl, whose `,` the grammar wraps in
2493    /// an extra `ERROR`.
2494    #[cfg(feature = "perl")]
2495    #[test]
2496    fn is_extra_marks_a_comment_and_a_recovered_token_alike() {
2497        let tree = Tree::new::<crate::langs::PerlCode>(b"my %h = (name, => 1); # c\n");
2498        let extras: Vec<(&str, bool)> = tree
2499            .get_root()
2500            .preorder()
2501            .filter(Node::is_extra)
2502            .map(|node| (node.kind(), node.is_error()))
2503            .collect();
2504        assert_eq!(extras, [("ERROR", true), ("comments", false)]);
2505    }
2506}