use super::Ancestors;
use crate::node::Node;
impl<'tree, 'chain> Ancestors<'tree, 'chain> {
#[inline]
#[must_use]
pub(crate) fn previous_sibling_has_kind(self, node: &Node<'tree>, kind: u16) -> bool {
self.previous_sibling(node)
.is_some_and(|prev| prev.kind_id() == kind)
}
#[inline]
#[must_use]
pub fn previous_sibling(self, node: &Node<'tree>) -> Option<Node<'tree>> {
let Some(chain) = self.chain else {
return node.previous_sibling();
};
let parent = chain.last()?;
if let Lookup::Wide(children, index) = self.lookup(node) {
return match index {
Some(index) => children[..index].last().copied(),
None => node.previous_sibling(),
};
}
let mut previous = None;
for child in parent.children() {
if child.id() == node.id() {
debug_assert!(
parent.child_count() <= WIDE_PARENT,
"previous_sibling scanned a {}-child {} with no SiblingCache (#1785)",
parent.child_count(),
parent.kind()
);
return previous;
}
previous = Some(child);
}
node.previous_sibling()
}
pub fn siblings_after(
self,
node: &Node<'tree>,
) -> impl Iterator<Item = Node<'tree>> + use<'tree, 'chain> {
let (wide, narrow) = match self.lookup(node) {
Lookup::Wide(children, index) => (index.map(|index| &children[index + 1..]), None),
Lookup::Narrow(parent) => (None, parent.map(|parent| parent.children_after(node))),
};
let wide = wide.into_iter().flatten().copied();
wide.chain(narrow.into_iter().flatten())
}
pub fn siblings_before(
self,
node: &Node<'tree>,
) -> impl Iterator<Item = Node<'tree>> + use<'tree, 'chain> {
let (wide, narrow) = match self.lookup(node) {
Lookup::Wide(children, index) => (index.map(|index| &children[..index]), None),
Lookup::Narrow(parent) => (None, parent.map(|parent| parent.children_before(node))),
};
let wide = wide.into_iter().flatten().rev().copied();
wide.chain(narrow.into_iter().flatten())
}
pub(super) fn lookup(self, node: &Node<'tree>) -> Lookup<'tree, 'chain> {
let parent = self.parent(node);
let recorded = match (self.siblings, self.chain, parent) {
(Some(cache), Some(chain), Some(parent)) => {
let recorded = cache.children(&parent, chain.len() - 1);
debug_assert!(
recorded.is_some() || parent.child_count() <= WIDE_PARENT,
"a walk must record every wide node on its chain before a \
sibling is asked for under it (#1584), and lend that record \
(#1601), but not this {}-child {}",
parent.child_count(),
parent.kind()
);
recorded
}
_ => None,
};
if let Some(children) = recorded {
sibling_cache_reads::record();
return Lookup::Wide(children, position_by_start(children, node));
}
if self.chain.is_some() && parent.is_some() {
sibling_seeks::record();
}
Lookup::Narrow(parent)
}
}
pub(super) enum Lookup<'tree, 'chain> {
Wide(&'chain [Node<'tree>], Option<usize>),
Narrow(Option<Node<'tree>>),
}
#[doc(hidden)]
pub const WIDE_PARENT: usize = 64;
pub(super) fn position_by_start(children: &[Node], node: &Node) -> Option<usize> {
let first = children.partition_point(|child| child.start_byte() < node.start_byte());
children[first..]
.iter()
.take_while(|child| child.start_byte() == node.start_byte())
.position(|child| child.id() == node.id())
.map(|offset| first + offset)
}
#[derive(Debug, Default)]
pub struct SiblingCache<'tree>(Vec<(usize, Vec<Node<'tree>>)>);
pub(super) const NOTHING_RECORDED: &SiblingCache<'static> = &SiblingCache(Vec::new());
impl<'tree> SiblingCache<'tree> {
pub fn record(
&mut self,
node: &Node<'tree>,
depth: usize,
children: impl IntoIterator<Item = Node<'tree>>,
) {
if node.child_count() <= WIDE_PARENT {
return;
}
if self.0.len() <= depth {
self.0.resize_with(depth + 1, Default::default);
}
let (id, recorded) = &mut self.0[depth];
*id = node.id();
recorded.clear();
recorded.extend(children);
debug_assert_eq!(
recorded.len(),
node.child_count(),
"a walk must record every child of a wide {}, in one batch (#1871)",
node.kind()
);
}
#[cfg(test)]
pub(super) fn is_empty(&self) -> bool {
self.0.is_empty()
}
fn children(&self, parent: &Node<'tree>, depth: usize) -> Option<&[Node<'tree>]> {
self.0
.get(depth)
.filter(|(id, _)| *id == parent.id())
.map(|(_, children)| children.as_slice())
}
}
crate::observation::counter!(
sibling_cache_reads,
cfg(any(test, feature = "test-support"))
);
crate::observation::counter!(sibling_seeks, cfg(any(test, feature = "test-support")));