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}