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.
A chain derived below the walk’s (of_children)
reads the walk’s chain in place and the entries it adds after it, as
one chain at the same depths (#1805).
A walk’s own chain states whether the walk records siblings: it is
built with for_walk, which requires the walk’s
SiblingCache, or with
for_walk_without_siblings or,
inside this crate, for_walk_chain_only, which say that it records
none. A walk can no longer leave the cache out by forgetting a
builder call (#1601).
Implementations§
Source§impl<'tree, 'chain> Ancestors<'tree, 'chain>
impl<'tree, 'chain> Ancestors<'tree, 'chain>
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
(#1785). The metric, ops and find / count walks call this and
lend one; on the suppression, dump and comment-removal walks,
which record no siblings, the assertion in lookup fires first
(#1601).
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), and so is one that asks of
every element of a list behind a long run of comments, which sit
outside the list’s repeat() (#1868). 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 the walk constructors
report (#1122), and “no siblings” is the conservative answer for
the exclude_tests prune that reads these (nothing is pruned).
It is not conservative for every reader: Perl ABC’s pattern-role
check would take a pattern with no sibling for a list’s first and
last operand, so its tests pin the chain it passes (#1868).
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.
Not for the chain a walk keeps: a walk constructs through
for_walk or
for_walk_without_siblings
(or, inside this crate, for_walk_chain_only), which check the
chain against the node and state whether the walk records
siblings. A chain built here seeks for a sibling under a wide
parent with no such check (#1601).
Sourcepub fn for_walk(
chain: &'chain [Node<'tree>],
node: &Node<'tree>,
folds: &'chain FoldCache,
siblings: &'chain SiblingCache<'tree>,
) -> Self
pub fn for_walk( chain: &'chain [Node<'tree>], node: &Node<'tree>, folds: &'chain FoldCache, siblings: &'chain SiblingCache<'tree>, ) -> Self
The chain a walk hands its predicates for node, the node it is
visiting: chain, checked against node as
for_walk_without_siblings
checks it, lending folds with the visit recorded on it (#1737)
and answering sibling lookups from siblings, the children the
walk recorded of every wide node on chain (#1584). Lending the
caches and naming the
visited node are one step that no walk can split: outside the
walk constructors, only the test-only with_folds and
with_siblings set either cache (#1601). A walk that records no
siblings says so with
for_walk_without_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, the outer a fold step is handed) carries
the same cache and so the same visit.
Sourcepub fn for_walk_without_siblings(
chain: &'chain [Node<'tree>],
node: &Node<'tree>,
folds: &'chain FoldCache,
) -> Self
pub fn for_walk_without_siblings( chain: &'chain [Node<'tree>], node: &Node<'tree>, folds: &'chain FoldCache, ) -> Self
for_walk for a walk that records no siblings:
the suppression scan and the dump. No predicate those walks call
asks for a sibling under any parent, which
the_walks_that_record_no_siblings_ask_for_none pins in the root
crate, since a predicate cannot know that its parent is narrow.
This chain enforces the costly half: a sibling asked under a
parent wider than [WIDE_PARENT] trips the assertion in lookup
in a debug build, because the seek is O(index) and a walk that
asks it of every child of a flat ERROR is quadratic (#1584).
When a predicate of such a walk needs a sibling, the walk records
each wide node’s children as it pushes them and constructs
through for_walk instead (#1601).
§Panics
When chain is not node’s ancestry, as a walk’s chain is after
a slip in its truncate/push bookkeeping. A debug build checks an
O(1) consequence: chain.last() is not node itself, and its
byte span contains node’s. That catches a push moved ahead of
the per-node work and a dropped truncate, and misses a chain
short by exactly one entry. Under --cfg chain_audit, which
make chain-audit sets, every profile asserts the exact
chain.last() == node.parent() instead, at Node::parent’s
O(depth) per node (#1122). for_walk builds
on this constructor and panics the same way.
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, a parse
error’s children asked whether they are doc targets — 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. Without a
known chain the result climbs, as Ancestors::unknown does.
Read it with ChildAncestors::get.
The walk’s chain is borrowed, not copied: from it this is one allocation of one entry, whatever the depth. From a chain itself derived it copies the entries that one added below the walk’s, which every caller bounds by a fixed structural nesting. A copy of the whole chain per container was quadratic in nested containers (#1805).
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 docs/development/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 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.