pub struct Ancestors<'tree, 'chain> { /* private fields */ }Expand description
The chain of a node’s ancestors, root first, as recorded by a walker that descended to that node.
A predicate that asks a node for its parent pays Node::parent’s
O(depth) once per node, so O(depth²) over a deeply nested file,
however few parent steps it takes (#1084). A walker that visits
parents before children already holds the chain, and handing it down
turns each step into a slice index — the upward counterpart of the
downward flag propagation #1052 and #1062 used.
Callers that reached a node some other way pass
Ancestors::unknown, which climbs with Node::parent: the same
answers at the original cost.
Implementations§
Source§impl<'tree, 'chain> Ancestors<'tree, 'chain>
impl<'tree, 'chain> Ancestors<'tree, 'chain>
Sourcepub const fn unknown() -> Self
pub const fn unknown() -> Self
No chain is available; every query climbs with Node::parent.
Sourcepub const fn known(chain: &'chain [Node<'tree>]) -> Self
pub const fn known(chain: &'chain [Node<'tree>]) -> Self
chain lists every ancestor of the node about to be queried,
root first — so chain.last() is its parent and an empty chain
means the node is the root.
Sourcepub const fn with_siblings(self, cache: &'chain SiblingCache<'tree>) -> Self
pub const fn with_siblings(self, cache: &'chain SiblingCache<'tree>) -> Self
This chain, answering siblings_after and
siblings_before through cache, which
the walker that keeps the chain owns for the whole walk.
Sourcepub fn for_walk(
chain: &'chain [Node<'tree>],
node: &Node<'tree>,
folds: &'chain FoldCache,
) -> Self
pub fn for_walk( chain: &'chain [Node<'tree>], node: &Node<'tree>, folds: &'chain FoldCache, ) -> Self
The chain a walk hands its predicates for node, the node it is
visiting: checked on chain, lending folds
with the visit recorded on it (#1737). Every walk that keeps a
FoldCache constructs through here, so lending the cache and
naming the visited node are one step that no lender can split —
by construction, since the test-only with_folds is the only
other way to set folds — the fold-cache half of what #1601 asks
for the SiblingCache, which stays a separate
with_siblings because the dump walk
records no siblings.
The visit is what Ancestors::classified keys the word slots
on: an ask about node is served and stored, an ask about any
other node — an enclosing call read from a descendant, a module’s
statements read while the module is visited — is computed and
not stored, so it cannot evict the visited node’s answer. A
derived chain (of_children, below,
iter) carries the same cache and so the same
visit.
Sourcepub fn checked(chain: &'chain [Node<'tree>], node: &Node<'tree>) -> Self
pub fn checked(chain: &'chain [Node<'tree>], node: &Node<'tree>) -> Self
Ancestors::known, but first checks that chain really is
node’s ancestry.
The parity test below proves the walker’s truncate/push rule on a
replica walker, so it cannot see metrics_inner itself
desynchronising — a chain.push moved ahead of the per-node
computes, say, or a continue inserted above the truncate.
Ancestors::parent trusts chain.last() unvalidated, so such a
drift would feed every predicate a wrong ancestor silently rather
than fail. Walkers that maintain a chain should construct through
here — through for_walk when they lend a
FoldCache; Ancestors::known stays unchecked for the
callers that deliberately pair a chain with a foreign node.
§Two checks, because the exact one is not affordable by default
The invariant is “chain.last() is node.parent()”, and
asking that outright costs Node::parent’s O(depth) — the
very lookup #1084 exists to remove. Per node, on every walk that
constructs a checked chain, it made every debug-build walk
O(nodes × depth) while the shipped walk is O(nodes): a tax on
every cargo test, worst on the deep-nesting regression tests
that exist to pin the shipped walk’s linearity (#1122). It now
runs only under --cfg chain_audit, which make chain-audit and
the CI lane of the same name set — and there as a plain
assert_eq!, so the audit has teeth in a release profile too.
What stays on in every debug build is an O(1) consequence of
that invariant: a parent’s byte span contains its child’s, and no
node is its own parent. Strictly weaker — a grandparent contains
the node as well — but it is shaped to the two ways a walker
desynchronises. A push moved ahead of the per-node computes
leaves chain.last() == node; a dropped truncate leaves the
previous subtree’s path, whose last entry is disjoint from the
node that follows it. Both trip here, on the first node that
shows them, at four integer comparisons.
Sourcepub fn depth(self) -> Option<usize>
pub fn depth(self) -> Option<usize>
How far the node this chain describes sits from the root, or
None when no chain is known — deriving it then would cost the
Node::parent climb the chain exists to remove.
Sourcepub fn of_children(self, node: &Node<'tree>) -> ChildAncestors<'tree, 'chain>
pub fn of_children(self, node: &Node<'tree>) -> ChildAncestors<'tree, 'chain>
The chain of node’s children, held: self extended by node,
for a consumer that holds a body’s chain and asks a row about the
body’s members — npa and npm over a class body — and, where
it reads through a member’s own children, moves the chain with
ChildAncestors::descend rather than building another. A row’s gate reads the chain it is handed as
the queried node’s own, so handing it the body’s instead answers
from the wrong parent the moment a Member or FuncOpener row
grows a gate; the comment “the row reads no chain” was the only
guard before this. The one allocation is per body, O(depth),
never per node; without a known chain the result climbs, as
Ancestors::unknown does. Read it with
ChildAncestors::get.
Sourcepub fn parent_has_kind(self, node: &Node<'tree>, kind: u16) -> bool
pub fn parent_has_kind(self, node: &Node<'tree>, kind: u16) -> bool
Whether node’s parent has kind id kind.
The compound-leaf guard of .claude/rules/grammar-dispatch.md
section 5 asks this and nothing else: a delimiter or keyword
token is suppressed only directly under the construct that
owns it, never under an arbitrary ancestor. Eleven dispatch
arms across getter, checker and the metric walkers spelled
it out as .parent(node).is_some_and(|p| p.kind_id() == X as u16), which wraps onto four rustfmt lines inside a match guard
and buries the question under the plumbing; #1314 added six more
and folded all seventeen onto this, and #1697 the ElseIf
gates. Two sites spelling their binding |parent| were left
alone and would each fit:
is_stabby_lambda_body (src/lang_helpers/ruby.rs) and
is_useful_comment (src/checker/rust.rs, a let-chain).
A false when node has no parent is the answer every one of
those call sites wants: a root node’s token is not inside the
construct, so it is not suppressed.
Sourcepub fn previous_sibling(self, node: &Node<'tree>) -> Option<Node<'tree>>
pub fn previous_sibling(self, node: &Node<'tree>) -> Option<Node<'tree>>
The sibling immediately before node, or None when node is
its parent’s first child or has no parent.
tree_sitter’s own prev_sibling resolves the parent first
(ts_node__prev_sibling opens with ts_node_parent), so it
carries the same O(depth) cost Node::parent does. With a
known chain the parent is free and what remains is a cursor walk
over the siblings — or, for a wide parent the walk recorded in its
SiblingCache, a binary search, since a walk over every child
of a Kotlin string’s $name run was quadratic in it (#1584).
A debug build rejects that cursor walk over a parent wider than
[WIDE_PARENT], which only a chain lending no cache can reach.
The metric, ops and find / count walks call this and lend one;
the suppression, dump and comment-removal walks lend none, so a
predicate added to one of those must lend one before calling it
(#1785).
Sourcepub fn iter(self, node: &Node<'tree>) -> AncestorIter<'tree, 'chain> ⓘ
pub fn iter(self, node: &Node<'tree>) -> AncestorIter<'tree, 'chain> ⓘ
node’s ancestors, nearest first, each paired with its own
ancestry so a predicate applied to an ancestor stays as cheap as
one applied to node.
Sourcepub fn siblings_after(
self,
node: &Node<'tree>,
) -> impl Iterator<Item = Node<'tree>> + use<'tree, 'chain>
pub fn siblings_after( self, node: &Node<'tree>, ) -> impl Iterator<Item = Node<'tree>> + use<'tree, 'chain>
The siblings after node, nearest first: what
Node::children_after yields on node’s parent, and nothing
for the root. self is node’s chain.
The seek Node::children_after runs is O(index) over a flat
child array, so a walk that asks of every child of a wide
ERROR is quadratic in it (#1584). A walk that lends a
SiblingCache has already collected a wide parent’s children,
and the lookup is a binary search among them.
Sourcepub fn siblings_before(
self,
node: &Node<'tree>,
) -> impl Iterator<Item = Node<'tree>> + use<'tree, 'chain>
pub fn siblings_before( self, node: &Node<'tree>, ) -> impl Iterator<Item = Node<'tree>> + use<'tree, 'chain>
The siblings before node, nearest first: what
Node::children_before yields on node’s parent, and nothing
for the root. self is node’s chain; see
siblings_after.
When the chain does not describe node, so node is not among the
parent’s children, both this and siblings_after yield nothing on
either lookup, where previous_sibling
falls back to Node::previous_sibling. The asymmetry is
deliberate: the mismatch is a caller error Ancestors::checked
reports (#1122), and “no siblings” is the conservative answer for
the exclude_tests prune that reads these (nothing is pruned).