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