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")));