Skip to main content

big_code_analysis_ast/node/ancestors/
siblings.rs

1//! Sibling lookups on an [`Ancestors`] chain, and the [`SiblingCache`] a
2//! walk records its wide nodes' children in, so that a lookup under one
3//! is a search rather than a seek from the parent's first child (#1584).
4//! Tested in the parent module's `tests`.
5
6use super::Ancestors;
7use crate::node::Node;
8
9impl<'tree, 'chain> Ancestors<'tree, 'chain> {
10    /// Whether the sibling immediately before `node` has `kind`: the
11    /// `ElseIf` gate of the grammars that spell `else if` as a bare
12    /// `else` token followed by a nested `if` with no clause wrapper
13    /// (Java, Groovy, C#, Kotlin — #1697), through [`previous_sibling`]
14    /// and so at its cost. `false` when `node` is its parent's first
15    /// child or has no parent: a root's `if` continues nothing.
16    ///
17    /// [`previous_sibling`]: Self::previous_sibling
18    #[inline]
19    #[must_use]
20    pub(crate) fn previous_sibling_has_kind(self, node: &Node<'tree>, kind: u16) -> bool {
21        self.previous_sibling(node)
22            .is_some_and(|prev| prev.kind_id() == kind)
23    }
24
25    /// The sibling immediately before `node`, or `None` when `node` is
26    /// its parent's first child or has no parent.
27    ///
28    /// `tree_sitter`'s own `prev_sibling` resolves the parent first
29    /// (`ts_node__prev_sibling` opens with `ts_node_parent`), so it
30    /// carries the same `O(depth)` cost [`Node::parent`] does. With a
31    /// known chain the parent is free and what remains is a cursor walk
32    /// over the siblings — or, for a wide parent the walk recorded in its
33    /// [`SiblingCache`], a binary search, since a walk over every child
34    /// of a Kotlin string's `$name` run was quadratic in it (#1584).
35    /// A debug build rejects that cursor walk over a parent wider than
36    /// [`WIDE_PARENT`], which only a chain lending no cache can reach
37    /// (#1785). The metric, ops and `find` / `count` walks call this and
38    /// lend one; on the suppression, dump and comment-removal walks,
39    /// which record no siblings, the assertion in `lookup` fires first
40    /// (#1601).
41    #[inline]
42    #[must_use]
43    pub fn previous_sibling(self, node: &Node<'tree>) -> Option<Node<'tree>> {
44        let Some(chain) = self.chain else {
45            return node.previous_sibling();
46        };
47        let parent = chain.last()?;
48        if let Lookup::Wide(children, index) = self.lookup(node) {
49            return match index {
50                Some(index) => children[..index].last().copied(),
51                None => node.previous_sibling(),
52            };
53        }
54        let mut previous = None;
55        for child in parent.children() {
56            if child.id() == node.id() {
57                // The scan is `O(index)`, so only a chain that lends no
58                // cache can reach it under a wide parent, and no caller
59                // does (#1785). One that starts to would be quadratic
60                // over the parent's children and answer the same, so
61                // make it loud. Asserted once the scan has found `node`:
62                // a chain that does not describe it is a different
63                // caller error, the one the fallback below answers.
64                debug_assert!(
65                    parent.child_count() <= WIDE_PARENT,
66                    "previous_sibling scanned a {}-child {} with no SiblingCache (#1785)",
67                    parent.child_count(),
68                    parent.kind()
69                );
70                return previous;
71            }
72            previous = Some(child);
73        }
74        // `node` is not among `parent.children()`, so this chain does
75        // not describe `node`. Answering `None` would claim "no
76        // previous sibling", which is a different (and wrong) answer;
77        // fall back to the authoritative lookup instead.
78        node.previous_sibling()
79    }
80
81    /// The siblings after `node`, nearest first: what
82    /// [`Node::children_after`] yields on `node`'s parent, and nothing
83    /// for the root. `self` is `node`'s chain.
84    ///
85    /// The seek [`Node::children_after`] runs is `O(index)` over a flat
86    /// child array, so a walk that asks of every child of a wide
87    /// `ERROR` is quadratic in it (#1584), and so is one that asks of
88    /// every element of a list behind a long run of comments, which sit
89    /// outside the list's `repeat()` (#1868). A walk that lends a
90    /// [`SiblingCache`] has already collected a wide parent's children,
91    /// and the lookup is a binary search among them.
92    pub fn siblings_after(
93        self,
94        node: &Node<'tree>,
95    ) -> impl Iterator<Item = Node<'tree>> + use<'tree, 'chain> {
96        let (wide, narrow) = match self.lookup(node) {
97            Lookup::Wide(children, index) => (index.map(|index| &children[index + 1..]), None),
98            Lookup::Narrow(parent) => (None, parent.map(|parent| parent.children_after(node))),
99        };
100        let wide = wide.into_iter().flatten().copied();
101        wide.chain(narrow.into_iter().flatten())
102    }
103
104    /// The siblings before `node`, nearest first: what
105    /// [`Node::children_before`] yields on `node`'s parent, and nothing
106    /// for the root. `self` is `node`'s chain; see
107    /// [`siblings_after`](Self::siblings_after).
108    ///
109    /// When the chain does not describe `node`, so `node` is not among the
110    /// parent's children, both this and `siblings_after` yield nothing on
111    /// either lookup, where [`previous_sibling`](Self::previous_sibling)
112    /// falls back to [`Node::previous_sibling`]. The asymmetry is
113    /// deliberate: the mismatch is a caller error the walk constructors
114    /// report (#1122), and "no siblings" is the conservative answer for
115    /// the `exclude_tests` prune that reads these (nothing is pruned).
116    /// It is not conservative for every reader: Perl ABC's pattern-role
117    /// check would take a pattern with no sibling for a list's first and
118    /// last operand, so its tests pin the chain it passes (#1868).
119    pub fn siblings_before(
120        self,
121        node: &Node<'tree>,
122    ) -> impl Iterator<Item = Node<'tree>> + use<'tree, 'chain> {
123        let (wide, narrow) = match self.lookup(node) {
124            Lookup::Wide(children, index) => (index.map(|index| &children[..index]), None),
125            Lookup::Narrow(parent) => (None, parent.map(|parent| parent.children_before(node))),
126        };
127        let wide = wide.into_iter().flatten().rev().copied();
128        wide.chain(narrow.into_iter().flatten())
129    }
130
131    // Where `node`'s siblings are read from: its parent's children as the
132    // walk recorded them and `node`'s index among them, or the parent to
133    // seek in when the walk recorded none.
134    pub(super) fn lookup(self, node: &Node<'tree>) -> Lookup<'tree, 'chain> {
135        let parent = self.parent(node);
136        let recorded = match (self.siblings, self.chain, parent) {
137            (Some(cache), Some(chain), Some(parent)) => {
138                let recorded = cache.children(&parent, chain.len() - 1);
139                // A walk that stopped recording, or one that records
140                // nothing and started asking, would answer the same, only
141                // quadratically, which no metric value shows.
142                debug_assert!(
143                    recorded.is_some() || parent.child_count() <= WIDE_PARENT,
144                    "a walk must record every wide node on its chain before a \
145                     sibling is asked for under it (#1584), and lend that record \
146                     (#1601), but not this {}-child {}",
147                    parent.child_count(),
148                    parent.kind()
149                );
150                recorded
151            }
152            _ => None,
153        };
154        if let Some(children) = recorded {
155            sibling_cache_reads::record();
156            return Lookup::Wide(children, position_by_start(children, node));
157        }
158        if self.chain.is_some() && parent.is_some() {
159            sibling_seeks::record();
160        }
161        Lookup::Narrow(parent)
162    }
163}
164
165pub(super) enum Lookup<'tree, 'chain> {
166    Wide(&'chain [Node<'tree>], Option<usize>),
167    Narrow(Option<Node<'tree>>),
168}
169
170/// Children past which a walk records a node's children for sibling
171/// lookups. A seek over this many is a short scan however the grammar
172/// stores them, so recording a narrower node would copy it for nothing.
173///
174/// `pub` and `#[doc(hidden)]` only so the wide-parent fixtures in this
175/// crate's and `big-code-analysis`'s tests size themselves from it: a
176/// hand-copied width would silently go narrow if this were raised.
177#[doc(hidden)]
178pub const WIDE_PARENT: usize = 64;
179
180// `node`'s index in `children`, a parent's children in order. Their start
181// bytes never decrease, so a binary search lands on the first child
182// starting where `node` does; only zero-width children, which recovery
183// inserts, can share that byte with it.
184pub(super) fn position_by_start(children: &[Node], node: &Node) -> Option<usize> {
185    let first = children.partition_point(|child| child.start_byte() < node.start_byte());
186    children[first..]
187        .iter()
188        .take_while(|child| child.start_byte() == node.start_byte())
189        .position(|child| child.id() == node.id())
190        .map(|offset| first + offset)
191}
192
193/// The children of each wide node on a walk's chain, recorded as the
194/// walk pushes them, so that [`Ancestors::siblings_after`] and
195/// [`Ancestors::siblings_before`] find a sibling in a flat `ERROR`, or
196/// past a run of extras ahead of a list's elements, without a scan from
197/// its start (#1584, #1868).
198///
199/// One slot per depth, keyed by the node's id. A walk descends into a
200/// node only after pushing its children, so every wide node on the
201/// chain has its slot; a slot left behind by a node the walk has moved
202/// past holds another id and is not read. Recording copies what the
203/// walk already holds, once per wide node.
204///
205/// A walk lends it through [`Ancestors::for_walk`] (#1601).
206#[derive(Debug, Default)]
207pub struct SiblingCache<'tree>(Vec<(usize, Vec<Node<'tree>>)>);
208
209/// The record a walk that records no siblings lends: empty, so a sibling
210/// asked under a wide parent finds no record and trips the walk
211/// assertion in [`Ancestors::lookup`], while one under a narrow parent
212/// seeks as it would through no cache at all. Nothing can write to it:
213/// recording takes `&mut`.
214pub(super) const NOTHING_RECORDED: &SiblingCache<'static> = &SiblingCache(Vec::new());
215
216impl<'tree> SiblingCache<'tree> {
217    /// Records `children`, in order, as the children of `node`, which
218    /// sits at `depth` in the walk's chain. A node of no more than a
219    /// short scan's children is not recorded, and its batch is not read.
220    ///
221    /// `children` is every child of `node`: a lookup indexes into the
222    /// record, so a batch that left one out would answer with the wrong
223    /// sibling. A debug build rejects a batch of any other length.
224    pub fn record(
225        &mut self,
226        node: &Node<'tree>,
227        depth: usize,
228        children: impl IntoIterator<Item = Node<'tree>>,
229    ) {
230        if node.child_count() <= WIDE_PARENT {
231            return;
232        }
233        if self.0.len() <= depth {
234            self.0.resize_with(depth + 1, Default::default);
235        }
236        // An unused slot's id is 0, which no node has: tree-sitter's id
237        // is the address of the node's subtree.
238        let (id, recorded) = &mut self.0[depth];
239        *id = node.id();
240        recorded.clear();
241        recorded.extend(children);
242        debug_assert_eq!(
243            recorded.len(),
244            node.child_count(),
245            "a walk must record every child of a wide {}, in one batch (#1871)",
246            node.kind()
247        );
248    }
249
250    /// Whether no node is recorded. Test-only: the record is otherwise
251    /// read through a lookup.
252    #[cfg(test)]
253    pub(super) fn is_empty(&self) -> bool {
254        self.0.is_empty()
255    }
256
257    // `parent`'s children, when the walk recorded them at `depth`.
258    fn children(&self, parent: &Node<'tree>, depth: usize) -> Option<&[Node<'tree>]> {
259        self.0
260            .get(depth)
261            .filter(|(id, _)| *id == parent.id())
262            .map(|(_, children)| children.as_slice())
263    }
264}
265
266// Sibling lookups answered from a walk's `SiblingCache` rather than by a
267// seek. The two answer identically, so only this tells a walk that lends
268// the cache from one that dropped it (#1447 review); a seek on a wide
269// flat parent is the quadratic #1584 fixed.
270crate::observation::counter!(
271    sibling_cache_reads,
272    cfg(any(test, feature = "test-support"))
273);
274
275// Sibling lookups on a known chain that take the uncached path: no
276// record of the parent, so the lookup seeks (or, for `previous_sibling`,
277// scans) it. A walk that records no siblings must make none under a wide
278// parent, which the walk assertion in `Ancestors::lookup` catches in a
279// debug build; this counts them in every build and under narrow parents
280// too, so a test can pin that such a walk asks for no sibling at all
281// (#1601). It does not see a chainless `Ancestors::unknown()`, nor a scan
282// of `parent.children()` or a cursor seek made outside `Ancestors`.
283crate::observation::counter!(sibling_seeks, cfg(any(test, feature = "test-support")));