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.

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>

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

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

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

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.

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

Source

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.

Source

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.

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

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

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.

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