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