Skip to main content

Ancestors

Struct Ancestors 

Source
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>

Source

pub const fn unknown() -> Self

No chain is available; every query climbs with Node::parent.

Source

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.

Source

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.

Source

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.

Source

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.

Source

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.

Source

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.

Source

pub fn parent(self, node: &Node<'tree>) -> Option<Node<'tree>>

node’s parent.

Source

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.

Source

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).

Source

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.

Source

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.

Source

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).

Trait Implementations§

Source§

impl<'tree, 'chain> Clone for Ancestors<'tree, 'chain>

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl<'tree, 'chain> Copy for Ancestors<'tree, 'chain>

Source§

impl<'tree, 'chain> Debug for Ancestors<'tree, 'chain>

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl<'tree, 'chain> !RefUnwindSafe for Ancestors<'tree, 'chain>

§

impl<'tree, 'chain> !Send for Ancestors<'tree, 'chain>

§

impl<'tree, 'chain> !Sync for Ancestors<'tree, 'chain>

§

impl<'tree, 'chain> !UnwindSafe for Ancestors<'tree, 'chain>

§

impl<'tree, 'chain> Forget for Ancestors<'tree, 'chain>

§

impl<'tree, 'chain> Freeze for Ancestors<'tree, 'chain>

§

impl<'tree, 'chain> Unpin for Ancestors<'tree, 'chain>

§

impl<'tree, 'chain> UnsafeUnpin for Ancestors<'tree, 'chain>

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.