use std::cell::{Cell, RefCell};
use std::collections::HashMap;
use super::Node;
use crate::checker::Checker;
#[derive(Debug)]
pub struct ChildAncestors<'tree, 'chain> {
chain: Option<Vec<Node<'tree>>>,
floor: usize,
above: Ancestors<'tree, 'chain>,
}
impl<'tree> ChildAncestors<'tree, '_> {
#[inline]
#[must_use]
pub fn get(&self) -> Ancestors<'tree, '_> {
match &self.chain {
Some(chain) => self.above.below(chain),
None => Ancestors::unknown(),
}
}
#[inline]
pub fn descend(&mut self, child: &Node<'tree>) {
if let Some(chain) = &mut self.chain {
debug_assert!(
chain.last().is_none_or(|parent| {
parent.id() != child.id()
&& parent.start_byte() <= child.start_byte()
&& child.end_byte() <= parent.end_byte()
}),
"descended into a {} node the chain's last entry does not contain",
child.kind()
);
chain.push(*child);
}
}
#[inline]
pub fn ascend(&mut self) {
if let Some(chain) = &mut self.chain {
debug_assert!(
chain.len() > self.floor,
"ascended above the node this chain was built for"
);
if chain.len() > self.floor {
chain.pop();
}
}
}
}
#[derive(Clone, Copy, Debug)]
pub struct Ancestors<'tree, 'chain> {
chain: Option<&'chain [Node<'tree>]>,
siblings: Option<&'chain SiblingCache<'tree>>,
folds: Option<&'chain FoldCache>,
}
impl<'tree, 'chain> Ancestors<'tree, 'chain> {
#[inline]
#[must_use]
pub const fn unknown() -> Self {
Self {
chain: None,
siblings: None,
folds: None,
}
}
#[inline]
#[must_use]
pub const fn known(chain: &'chain [Node<'tree>]) -> Self {
Self {
chain: Some(chain),
siblings: None,
folds: None,
}
}
#[inline]
#[must_use]
pub const fn with_siblings(self, cache: &'chain SiblingCache<'tree>) -> Self {
Self {
siblings: Some(cache),
..self
}
}
#[cfg(test)]
#[inline]
#[must_use]
pub(crate) const fn with_folds(self, cache: &'chain FoldCache) -> Self {
Self {
folds: Some(cache),
..self
}
}
#[must_use]
pub fn for_walk(
chain: &'chain [Node<'tree>],
node: &Node<'tree>,
folds: &'chain FoldCache,
) -> Self {
folds.visited.set(node.id());
Self {
folds: Some(folds),
..Self::checked(chain, node)
}
}
pub(crate) fn fold_down(
self,
node: &Node<'tree>,
skip: usize,
lane: FoldLane,
init: u8,
step: impl Fn(u8, &Node<'tree>, Ancestors<'tree, 'chain>, &Node<'tree>) -> u8,
) -> u8 {
let Some(chain) = self.chain else {
return fold_climbed(node, skip, init, step);
};
let end = chain.len().saturating_sub(skip);
let step_at = |state: u8, depth: usize| {
let outer = Ancestors {
chain: Some(&chain[..depth]),
siblings: self.siblings,
folds: self.folds,
};
step(
state,
&chain[depth],
outer,
chain.get(depth + 1).unwrap_or(node),
)
};
match self.folds {
Some(cache) => cache.fold(lane, chain, end, init, step_at),
None => (0..end).fold(init, step_at),
}
}
#[doc(hidden)]
pub fn has_ancestor_before_stop<C: Checker>(
self,
node: &Node<'tree>,
lane: GateLane,
check: fn(&Node) -> bool,
stop: fn(&Node) -> bool,
) -> bool {
self.ancestor_before_stop::<C>(node, lane.fold_lane(), check, stop)
}
pub(crate) fn ancestor_before_stop<C: Checker>(
self,
node: &Node<'tree>,
lane: FoldLane,
check: fn(&Node) -> bool,
stop: fn(&Node) -> bool,
) -> bool {
if !self.memoises_folds() {
return node.count_specific_ancestors::<C>(self, check, stop) > 0;
}
self.fold_down(node, 0, lane, 0, |held, ancestor, outer, _| {
if stop(ancestor) {
0
} else if check(ancestor) && !C::is_else_if(ancestor, outer) {
1
} else {
held
}
}) == 1
}
pub(crate) fn node_memo(self, question: MemoQuestion) -> Option<&'chain NodeMemo> {
self.folds.map(|cache| &cache.nodes[question as usize])
}
pub(crate) fn memoised(
self,
question: MemoQuestion,
node: &Node<'_>,
answer: impl FnOnce() -> bool,
) -> bool {
let memo = self.node_memo(question);
if let Some(known) = memo.and_then(|memo| memo.get(node)) {
return known;
}
let answer = answer();
if let Some(memo) = memo {
memo.set(node, answer);
}
answer
}
#[doc(hidden)]
pub fn memoised_answer(
self,
question: NodeQuestion,
node: &Node<'_>,
answer: impl FnOnce() -> bool,
) -> bool {
self.memoised(question.memo_question(), node, answer)
}
pub(crate) fn classified(
self,
slot: WordSlot,
node: &Node<'_>,
classify: impl FnOnce() -> u8,
) -> u8 {
let Some(cache) = self.folds.filter(|cache| cache.visited.get() == node.id()) else {
return classify();
};
let cell = &cache.words[slot as usize];
let (id, answer) = cell.get();
if id == node.id() {
return answer;
}
let answer = classify();
cell.set((node.id(), answer));
answer
}
pub(crate) const fn is_known(self) -> bool {
self.chain.is_some()
}
pub(crate) fn memoises_folds(self) -> bool {
self.folds.is_some() && self.chain.is_some()
}
#[must_use]
pub fn checked(chain: &'chain [Node<'tree>], node: &Node<'tree>) -> Self {
#[cfg(chain_audit)]
assert_eq!(
chain.last().map(Node::id),
node.parent().map(|parent| parent.id()),
"ancestor chain desynchronised on a {} node",
node.kind()
);
debug_assert!(
chain.last().is_none_or(|parent| {
parent.id() != node.id()
&& parent.start_byte() <= node.start_byte()
&& node.end_byte() <= parent.end_byte()
}),
"ancestor chain desynchronised on a {} node: chain.last() neither \
contains it nor differs from it",
node.kind()
);
Self::known(chain)
}
#[inline]
pub fn depth(self) -> Option<usize> {
self.chain.map(<[Node<'tree>]>::len)
}
pub(crate) fn children_chain(self, node: &Node<'tree>) -> Option<Vec<Node<'tree>>> {
self.chain
.map(|chain| [chain, std::slice::from_ref(node)].concat())
}
#[must_use]
pub fn of_children(self, node: &Node<'tree>) -> ChildAncestors<'tree, 'chain> {
let chain = self.children_chain(node);
ChildAncestors {
floor: chain.as_ref().map_or(0, Vec::len),
chain,
above: self,
}
}
#[inline]
#[must_use]
pub(crate) const fn below<'below>(
self,
chain: &'below [Node<'tree>],
) -> Ancestors<'tree, 'below>
where
'chain: 'below,
{
Ancestors {
chain: Some(chain),
siblings: None,
folds: self.folds,
}
}
#[inline]
#[must_use]
pub fn parent(self, node: &Node<'tree>) -> Option<Node<'tree>> {
match self.chain {
Some(chain) => chain.last().copied(),
None => node.parent(),
}
}
#[inline]
#[must_use]
pub fn parent_has_kind(self, node: &Node<'tree>, kind: u16) -> bool {
self.parent(node).is_some_and(|p| p.kind_id() == kind)
}
#[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()
}
#[inline]
#[must_use]
pub fn iter(self, node: &Node<'tree>) -> AncestorIter<'tree, 'chain> {
AncestorIter(match self.chain {
Some(chain) => AncestorSource::Chain(chain, self.siblings, self.folds),
None => AncestorSource::Climb(node.parent()),
})
}
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())
}
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 lending a SiblingCache must record every wide node on its \
chain (#1584), but not this {}",
parent.kind()
);
recorded
}
_ => None,
};
match recorded {
Some(children) => {
sibling_cache_reads::record();
Lookup::Wide(children, position_by_start(children, node))
}
None => Lookup::Narrow(parent),
}
}
}
enum Lookup<'tree, 'chain> {
Wide(&'chain [Node<'tree>], Option<usize>),
Narrow(Option<Node<'tree>>),
}
#[doc(hidden)]
pub const WIDE_PARENT: usize = 64;
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>>)>);
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);
}
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())
}
}
fn deepest_stored(slots: &[(usize, u8)], chain: &[Node<'_>], from: usize) -> usize {
(1..=from)
.rev()
.find(|&depth| slots[depth].0 == chain[depth].id())
.unwrap_or(0)
}
fn fold_climbed<'tree, 'chain>(
node: &Node<'tree>,
skip: usize,
init: u8,
step: impl Fn(u8, &Node<'tree>, Ancestors<'tree, 'chain>, &Node<'tree>) -> u8,
) -> u8
where
'tree: 'chain,
{
let climbed = climbed_chain(node);
let end = climbed.len().saturating_sub(skip);
(0..end).fold(init, |state, depth| {
let below = climbed.get(depth + 1).unwrap_or(node);
step(state, &climbed[depth], Ancestors::unknown(), below)
})
}
fn climbed_chain<'tree>(node: &Node<'tree>) -> Vec<Node<'tree>> {
let mut climbed: Vec<_> = std::iter::successors(node.parent(), Node::parent).collect();
climbed.reverse();
climbed
}
#[doc(hidden)]
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum GateLane {
InsideHeader,
InsideExport,
InsideAmbient,
InsideBooleanChain,
}
impl GateLane {
const fn fold_lane(self) -> FoldLane {
match self {
Self::InsideHeader => FoldLane::InsideHeader,
Self::InsideExport => FoldLane::InsideExport,
Self::InsideAmbient => FoldLane::InsideAmbient,
Self::InsideBooleanChain => FoldLane::InsideBooleanChain,
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum FoldLane {
DocInBody,
DocScope,
BareStringClimb,
InsideQuote,
InsideHeader,
InsideExport,
InsideAmbient,
InsideBooleanChain,
NamedBinding,
LambdaDepth,
}
impl FoldLane {
const COUNT: usize = 10;
}
const _: () = assert!(FoldLane::LambdaDepth as usize + 1 == FoldLane::COUNT);
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum MemoQuestion {
ConditionalDeclares,
ArgumentSlotsReadable,
SwitchArmList,
GuardOperator,
NamesAnArrow,
KeywordListHasDo,
ArgumentIsTrailing,
KeywordsLeadTheirList,
BareStringParenthesisLine,
}
impl MemoQuestion {
const COUNT: usize = 9;
}
const _: () = assert!(MemoQuestion::BareStringParenthesisLine as usize + 1 == MemoQuestion::COUNT);
#[doc(hidden)]
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum NodeQuestion {
BareStringParenthesisLine,
}
impl NodeQuestion {
const fn memo_question(self) -> MemoQuestion {
match self {
Self::BareStringParenthesisLine => MemoQuestion::BareStringParenthesisLine,
}
}
}
#[derive(Debug, Default)]
pub struct FoldCache {
lanes: [RefCell<Vec<(usize, u8)>>; FoldLane::COUNT],
nodes: [NodeMemo; MemoQuestion::COUNT],
words: [Cell<(usize, u8)>; WordSlot::COUNT],
visited: Cell<usize>,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum WordSlot {
ElixirCallTarget,
TclCommandWord,
}
impl WordSlot {
const COUNT: usize = 2;
}
const _: () = assert!(WordSlot::TclCommandWord as usize + 1 == WordSlot::COUNT);
#[derive(Debug, Default)]
pub(crate) struct NodeMemo(RefCell<HashMap<usize, bool>>);
impl NodeMemo {
pub(crate) fn get(&self, node: &Node<'_>) -> Option<bool> {
self.0.borrow().get(&node.id()).copied()
}
pub(crate) fn set(&self, node: &Node<'_>, answer: bool) {
self.0.borrow_mut().insert(node.id(), answer);
}
}
impl FoldCache {
fn fold(
&self,
lane: FoldLane,
chain: &[Node<'_>],
end: usize,
init: u8,
step: impl Fn(u8, usize) -> u8,
) -> u8 {
let Ok(mut slots) = self.lanes[lane as usize].try_borrow_mut() else {
debug_assert!(
same_lane_reentry::allowed(),
"a fold step re-entered its own lane {lane:?}"
);
return (0..end).fold(init, step);
};
let memo_end = end.min(chain.len().saturating_sub(1));
if slots.len() <= memo_end {
slots.resize(memo_end + 1, (0, 0));
}
let mut depth = deepest_stored(&slots, chain, memo_end);
let mut state = if depth == 0 { init } else { slots[depth].1 };
while depth < memo_end {
fold_steps::record();
state = step(state, depth);
depth += 1;
slots[depth] = (chain[depth].id(), state);
}
if end > memo_end {
state = step(state, memo_end);
}
state
}
}
crate::observation::counter!(fold_steps, cfg(any(test, feature = "test-support")));
crate::observation::counter!(
sibling_cache_reads,
cfg(any(test, feature = "test-support"))
);
mod same_lane_reentry {
use std::cell::Cell;
thread_local! {
static ALLOWED: Cell<bool> = const { Cell::new(false) };
}
pub(super) fn allowed() -> bool {
ALLOWED.get()
}
#[cfg(test)]
pub(super) fn allow(allowed: bool) {
ALLOWED.set(allowed);
}
}
pub struct AncestorIter<'tree, 'chain>(AncestorSource<'tree, 'chain>);
enum AncestorSource<'tree, 'chain> {
Chain(
&'chain [Node<'tree>],
Option<&'chain SiblingCache<'tree>>,
Option<&'chain FoldCache>,
),
Climb(Option<Node<'tree>>),
}
impl<'tree, 'chain> Iterator for AncestorIter<'tree, 'chain> {
type Item = (Node<'tree>, Ancestors<'tree, 'chain>);
fn next(&mut self) -> Option<Self::Item> {
match &mut self.0 {
AncestorSource::Chain(remaining, siblings, folds) => {
let (&nearest, above) = remaining.split_last()?;
*remaining = above;
let ancestors = Ancestors {
chain: Some(above),
siblings: *siblings,
folds: *folds,
};
Some((nearest, ancestors))
}
AncestorSource::Climb(next) => {
let nearest = (*next)?;
*next = nearest.parent();
Some((nearest, Ancestors::unknown()))
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::node::Tree;
#[cfg(all(feature = "rust", debug_assertions))]
#[test]
#[should_panic(expected = "with no SiblingCache (#1785)")]
fn previous_sibling_rejects_a_wide_parent_without_its_cache() {
let source = "fn a() {}\n".repeat(WIDE_PARENT + 1);
let tree = Tree::new::<crate::langs::RustCode>(source.as_bytes());
let root = tree.get_root();
let last = root.children().last().expect("the file has items");
let _ = Ancestors::known(&[root]).previous_sibling(&last);
}
#[cfg(feature = "rust")]
#[test]
fn previous_sibling_falls_back_on_a_wide_chain_that_is_not_this_nodes() {
let source = format!(
"fn a() {{ let x = 1; }}\n{}",
"fn b() {}\n".repeat(WIDE_PARENT)
);
let tree = Tree::new::<crate::langs::RustCode>(source.as_bytes());
let root = tree.get_root();
assert!(root.child_count() > WIDE_PARENT, "the root must be wide");
let statement = root
.preorder()
.find(|node| node.kind() == "let_declaration")
.expect("fixture has a statement");
let expected = statement
.previous_sibling()
.map(|node| node.id())
.expect("the statement follows the body's `{`");
assert_eq!(
Ancestors::known(&[root])
.previous_sibling(&statement)
.map(|node| node.id()),
Some(expected),
"a mismatched chain must fall back, not panic or report `None`"
);
}
#[cfg(feature = "perl")]
fn ids<'a>(nodes: impl Iterator<Item = Node<'a>>) -> Vec<usize> {
nodes.map(|node| node.id()).collect()
}
#[cfg(feature = "perl")]
fn raw_children(parent: &Node) -> Vec<usize> {
let raw = parent.as_tree_sitter();
(0..raw.child_count() as u32)
.filter_map(|i| raw.child(i))
.map(|child| child.id())
.collect()
}
#[cfg(feature = "perl")]
fn flat_error() -> Tree {
let source = format!("my @r = ({}", "{\nlast,\n$a && $b,\n".repeat(20));
Tree::new::<crate::langs::PerlCode>(source.as_bytes())
}
#[cfg(feature = "rust")]
#[test]
fn fold_down_agrees_across_its_cache_chain_and_climb_paths() {
let tree = Tree::new::<crate::langs::RustCode>(
b"mod a {\n mod b {\n fn f() { let x = (1 + 2) * 3; }\n }\n fn g() {}\n}\nfn h() { if true { 4 } else { 5 }; }\n",
);
let step = |state: u8, ancestor: &Node, outer: Ancestors, below: &Node| {
let parent = outer
.parent(ancestor)
.map_or(0, |parent| parent.kind_id().to_le_bytes()[0]);
state
.wrapping_mul(31)
.wrapping_add(ancestor.kind_id().to_le_bytes()[0])
.wrapping_add(below.kind_id().to_le_bytes()[0].rotate_left(3))
.wrapping_add(parent.rotate_left(5))
};
let cache = FoldCache::default();
let mut stack = vec![(tree.get_root(), 0_usize)];
let mut chain: Vec<Node> = Vec::new();
let mut queried = 0_usize;
while let Some((node, depth)) = stack.pop() {
chain.truncate(depth);
for skip in 0..=3 {
let cached = |c: &[Node<'_>]| {
Ancestors::known(c).with_folds(&cache).fold_down(
&node,
skip,
FoldLane::DocInBody,
7,
step,
)
};
let first = cached(&chain);
let again = cached(&chain);
let uncached =
Ancestors::known(&chain).fold_down(&node, skip, FoldLane::DocInBody, 7, step);
let climbed =
Ancestors::unknown().fold_down(&node, skip, FoldLane::DocInBody, 7, step);
assert_eq!(
(first, again, uncached),
(climbed, climbed, climbed),
"{} at depth {depth}, skip {skip}",
node.kind()
);
queried += 1;
}
chain.push(node);
let children: Vec<_> = node.children().collect();
stack.extend(children.into_iter().rev().map(|child| (child, depth + 1)));
}
assert!(
queried > 100,
"the fixture must exercise a real walk: {queried}"
);
}
#[cfg(feature = "rust")]
#[test]
fn a_step_folds_another_lane_memoised_and_its_own_lane_unmemoised() {
use crate::test_support::for_each_node_with_chain;
use std::cell::Cell;
let source = format!("fn f() {{ {} }}\n", "{ ".repeat(60) + &"} ".repeat(60));
let inner_steps = Cell::new(0_usize);
let inner = |state: u8, ancestor: &Node, _: Ancestors, _: &Node| {
inner_steps.set(inner_steps.get() + 1);
state
.wrapping_mul(7)
.wrapping_add(ancestor.kind_id().to_le_bytes()[0])
};
let outer_on = |lane: FoldLane| {
move |state: u8, ancestor: &Node, outer: Ancestors, _: &Node| {
state.wrapping_add(outer.fold_down(ancestor, 0, lane, 3, inner))
}
};
let fold = |chain: &[Node], node: &Node, cache: Option<&FoldCache>, lane, inner_lane| {
let ancestors = Ancestors::known(chain);
let ancestors = cache.map_or(ancestors, |cache| ancestors.with_folds(cache));
ancestors.fold_down(node, 0, lane, 0, outer_on(inner_lane))
};
let cache = FoldCache::default();
same_lane_reentry::allow(true);
let nodes =
for_each_node_with_chain::<crate::langs::RustCode>(source.as_bytes(), |node, chain| {
let (other, own) = (FoldLane::DocInBody, FoldLane::BareStringClimb);
assert_eq!(
fold(chain, node, Some(&cache), other, FoldLane::DocScope),
fold(chain, node, None, other, FoldLane::DocScope),
"another lane must answer what the plain fold does"
);
let before = inner_steps.get();
let own_lane = fold(chain, node, Some(&cache), own, own);
let own_steps = inner_steps.get() - before;
assert_eq!(
own_lane,
fold(chain, node, None, own, own),
"its own lane must answer what the plain fold does"
);
let depth = chain.len();
assert!(
own_steps <= depth * (depth + 1) / 2,
"its own lane must cost one plain fold of the prefix"
);
});
same_lane_reentry::allow(false);
assert!(nodes > 200, "the fixture must nest deeply: {nodes}");
let cache = FoldCache::default();
inner_steps.set(0);
for_each_node_with_chain::<crate::langs::RustCode>(source.as_bytes(), |node, chain| {
fold(
chain,
node,
Some(&cache),
FoldLane::DocInBody,
FoldLane::DocScope,
);
});
assert!(
inner_steps.get() <= 4 * nodes,
"the other lane is not memoised"
);
}
#[cfg(feature = "perl")]
#[test]
fn siblings_of_a_recorded_wide_parent_match_the_child_walk() {
let tree = flat_error();
let root = tree.get_root();
assert!(root.is_error(), "the fixture's tail must fail to parse");
assert!(root.child_count() > WIDE_PARENT, "the ERROR must be wide");
let mut cache = SiblingCache::default();
cache.record(&root, 0, root.children());
let chain = [root];
let ancestors = Ancestors::known(&chain).with_siblings(&cache);
let all = raw_children(&root);
let (mut observed, mut expected) = (Vec::new(), Vec::new());
for (index, child) in root.children().enumerate() {
let recorded_index = match ancestors.lookup(&child) {
Lookup::Wide(_, index) => index,
Lookup::Narrow(_) => None,
};
observed.push((
index,
recorded_index,
ids(ancestors.siblings_after(&child)),
ids(ancestors.siblings_before(&child)),
ancestors.previous_sibling(&child).map(|node| node.id()),
));
expected.push((
index,
Some(index),
all[index + 1..].to_vec(),
all[..index].iter().rev().copied().collect(),
index.checked_sub(1).map(|previous| all[previous]),
));
}
assert_eq!(observed, expected);
let stray = root
.children()
.find_map(|child| {
child
.child(0)
.filter(|g| g.start_byte() == child.start_byte())
})
.expect("the fixture nests a node at its parent's start");
assert!(matches!(ancestors.lookup(&stray), Lookup::Wide(_, None)));
assert_eq!(ancestors.siblings_after(&stray).count(), 0);
assert_eq!(ancestors.siblings_before(&stray).count(), 0);
let operand = root
.children()
.find_map(|child| child.child(2))
.expect("the fixture holds `$a && $b`");
let previous = ancestors
.previous_sibling(&operand)
.expect("the fallback finds the `&&`");
assert_eq!(previous.kind(), "&&");
}
#[cfg(feature = "perl")]
#[test]
fn a_narrow_parent_is_sought_not_recorded() {
let tree = flat_error();
let root = tree.get_root();
let chain = [root];
let narrow = root
.children()
.find(|child| (2..=WIDE_PARENT).contains(&child.child_count()))
.expect("the fixture holds a narrow node with several children");
let mut cache = SiblingCache::default();
cache.record(&narrow, 1, narrow.children());
assert!(cache.0.is_empty(), "a narrow node must not be recorded");
let narrow_chain = [root, narrow];
let all = raw_children(&narrow);
for ancestors in [
Ancestors::known(&narrow_chain).with_siblings(&cache),
Ancestors::known(&narrow_chain),
] {
let first = narrow.child(0).expect("narrow node has children");
assert!(matches!(ancestors.lookup(&first), Lookup::Narrow(Some(_))));
assert_eq!(ids(ancestors.siblings_after(&first)), all[1..]);
}
let first = root.child(0).expect("root has children");
assert!(matches!(
Ancestors::known(&chain).lookup(&first),
Lookup::Narrow(Some(_))
));
}
#[cfg(all(feature = "perl", debug_assertions))]
#[test]
#[should_panic(expected = "must record every wide node on its chain")]
fn an_unrecorded_wide_parent_trips_the_walk_assertion() {
let tree = flat_error();
let root = tree.get_root();
let cache = SiblingCache::default();
let chain = [root];
let first = root.child(0).expect("root has children");
let _ = Ancestors::known(&chain)
.with_siblings(&cache)
.lookup(&first);
}
#[cfg(feature = "kotlin")]
#[test]
fn position_by_start_finds_a_zero_width_child() {
let tree = Tree::new::<crate::langs::KotlinCode>(b"fun f(vararg: Int, b: Int) {}");
let mut zero_width = 0;
for node in tree.get_root().preorder() {
let children: Vec<_> = node.children().collect();
for (index, child) in children.iter().enumerate() {
zero_width += usize::from(child.start_byte() == child.end_byte());
assert_eq!(position_by_start(&children, child), Some(index));
}
}
assert!(
zero_width > 0,
"fixture must hold an inserted zero-width child"
);
}
#[cfg(feature = "rust")]
#[test]
fn an_iterated_ancestor_keeps_the_walk_s_memo() {
let tree = Tree::new::<crate::langs::RustCode>(b"fn f() { g(1); }\n");
let root = tree.get_root();
let mut chain = vec![root];
for kind in ["function_item", "block", "expression_statement"] {
let last = *chain.last().expect("the chain starts non-empty");
let child = last
.children()
.find(|child| child.kind() == kind)
.unwrap_or_else(|| panic!("the fixture nests a {kind}"));
chain.push(child);
}
let leaf = chain
.last()
.expect("the chain has a parent")
.child(0)
.expect("the statement holds the call");
assert_eq!(leaf.kind(), "call_expression");
let cache = FoldCache::default();
let walk = Ancestors::known(&chain).with_folds(&cache);
walk.node_memo(MemoQuestion::ArgumentSlotsReadable)
.expect("the chain lent a cache")
.set(&leaf, true);
assert!(
Ancestors::known(&chain)
.node_memo(MemoQuestion::ArgumentSlotsReadable)
.is_none(),
"a chain lent no cache has no memo"
);
let (_, above) = walk.iter(&leaf).next().expect("the leaf has a parent");
let memo = above
.node_memo(MemoQuestion::ArgumentSlotsReadable)
.expect("an iterated ancestor's chain keeps the lent cache");
assert_eq!(memo.get(&leaf), Some(true));
let children = walk
.children_chain(&leaf)
.expect("a known chain extends downward");
assert_eq!(children.len(), chain.len() + 1);
let below = walk.below(&children);
assert_eq!(below.depth(), Some(chain.len() + 1));
let memo = below
.node_memo(MemoQuestion::ArgumentSlotsReadable)
.expect("a chain re-rooted with `below` keeps the lent cache");
assert_eq!(memo.get(&leaf), Some(true));
assert!(
Ancestors::known(&children)
.node_memo(MemoQuestion::ArgumentSlotsReadable)
.is_none(),
"a chain rebuilt with `known` carries nothing, which is why `below` exists"
);
}
#[cfg(feature = "rust")]
#[test]
fn the_word_slot_serves_only_the_visited_node() {
use std::cell::Cell;
let tree = Tree::new::<crate::langs::RustCode>(b"fn f() { g(1); }\n");
let root = tree.get_root();
let a = root.child(0).expect("the fn item");
let body = a
.children()
.find(|child| child.kind() == "block")
.expect("the body");
let b = body.child(1).expect("the call statement");
assert_ne!(a.id(), b.id());
let runs = Cell::new(0_usize);
let computes = |answer: u8| {
let runs = &runs;
move || {
runs.set(runs.get() + 1);
answer
}
};
let cache = FoldCache::default();
let chain = [root];
let walk = Ancestors::for_walk(&chain, &a, &cache);
let slot = WordSlot::ElixirCallTarget;
assert_eq!(walk.classified(slot, &a, computes(1)), 1);
assert_eq!(runs.get(), 1, "the first ask computes");
assert_eq!(walk.classified(slot, &a, computes(9)), 1);
assert_eq!(runs.get(), 1, "the second ask is served");
assert_eq!(walk.classified(slot, &b, computes(2)), 2);
assert_eq!(walk.classified(slot, &b, computes(2)), 2);
assert_eq!(
runs.get(),
3,
"an ask about another node computes every time"
);
assert_eq!(walk.classified(slot, &a, computes(9)), 1);
assert_eq!(
runs.get(),
3,
"and does not evict the visited node's answer"
);
let under = walk.of_children(&a);
assert_eq!(under.get().classified(slot, &b, computes(2)), 2);
let children = walk.children_chain(&a).expect("a known chain extends");
assert_eq!(walk.below(&children).classified(slot, &b, computes(2)), 2);
let (_, above) = walk.iter(&b).next().expect("b has a parent");
assert_eq!(above.classified(slot, &b, computes(2)), 2);
let folded = walk.fold_down(&a, 0, FoldLane::DocInBody, 0, |_, _, outer, _| {
outer.classified(slot, &b, computes(2))
});
assert_eq!(folded, 2);
assert_eq!(runs.get(), 7, "each derived chain's ask computes");
assert_eq!(walk.classified(slot, &a, computes(9)), 1);
assert_eq!(runs.get(), 7, "and none of them evicts");
assert_eq!(under.get().classified(slot, &a, computes(9)), 1);
assert_eq!(runs.get(), 7, "a derived chain serves the visited node too");
let never_visited = FoldCache::default();
let unvisited = Ancestors::known(&chain).with_folds(&never_visited);
assert_eq!(unvisited.classified(slot, &a, computes(1)), 1);
assert_eq!(unvisited.classified(slot, &a, computes(1)), 1);
assert_eq!(
runs.get(),
9,
"a cache lent without a visit computes every ask"
);
let chain_b = [root, a, body];
let walk_b = Ancestors::for_walk(&chain_b, &b, &cache);
assert_eq!(walk_b.classified(slot, &b, computes(2)), 2);
assert_eq!(walk_b.classified(slot, &b, computes(9)), 2);
assert_eq!(
runs.get(),
10,
"the new visit's first ask computes, the next is served"
);
assert_eq!(walk_b.classified(slot, &a, computes(1)), 1);
assert_eq!(runs.get(), 11, "the retired node is computed again");
}
#[cfg(feature = "rust")]
#[test]
fn of_children_names_the_body_as_each_member_s_parent() {
let tree = Tree::new::<crate::langs::RustCode>(b"struct S { a: i32, b: i32 }\n");
let root = tree.get_root();
let item = root.child(0).expect("the struct item");
let body = item
.children()
.find(|child| child.kind() == "field_declaration_list")
.expect("the field list");
let field = body
.children()
.find(|child| child.kind() == "field_declaration")
.expect("a field");
let chain = [root, item];
let cache = FoldCache::default();
let walk = Ancestors::known(&chain).with_folds(&cache);
assert_eq!(
walk.parent(&body).map(|p| p.id()),
Some(item.id()),
"the body's own chain names the item"
);
let under = walk.of_children(&body);
let members = under.get();
assert_eq!(
members.parent(&field).map(|p| p.id()),
Some(body.id()),
"a member's chain names the body"
);
assert_eq!(members.depth(), Some(3), "root, item, body");
assert!(
members.memoises_folds(),
"the derived chain keeps the walk's fold cache"
);
assert_eq!(
Ancestors::unknown()
.of_children(&body)
.get()
.parent(&field)
.map(|p| p.id()),
Some(body.id()),
"without a chain the derived one climbs to the same parent"
);
}
#[cfg(feature = "rust")]
#[test]
fn descend_and_ascend_move_the_held_chain_within_its_floor() {
let tree = Tree::new::<crate::langs::RustCode>(b"fn f() { if a { g(); } }\n");
let root = tree.get_root();
let item = root.child(0).expect("the fn item");
let body = item
.children()
.find(|child| child.kind() == "block")
.expect("the body");
let conditional = body
.children()
.find(|child| child.kind() == "expression_statement")
.and_then(|stmt| stmt.child(0))
.expect("the if");
let consequence = conditional
.children()
.find(|child| child.kind() == "block")
.expect("the consequence");
let call = consequence
.children()
.find(|child| child.kind() == "expression_statement")
.expect("the call statement");
let chain = [root, item];
let mut under = Ancestors::known(&chain).of_children(&body);
assert_eq!(under.get().depth(), Some(3), "root, item, body");
under.descend(&conditional);
under.descend(&consequence);
assert_eq!(under.get().depth(), Some(5), "root, item, body, if, block");
assert_eq!(
under.get().parent(&call).map(|p| p.id()),
Some(consequence.id()),
"under the consequence, its statements name it as their parent"
);
under.ascend();
under.ascend();
assert_eq!(under.get().depth(), Some(3), "back at the body");
assert_eq!(
under.get().parent(&conditional).map(|p| p.id()),
Some(body.id()),
"the body's members name the body again"
);
let mut unknown = Ancestors::unknown().of_children(&body);
unknown.descend(&conditional);
assert_eq!(
unknown.get().depth(),
None,
"without a chain a descent records nothing"
);
unknown.ascend();
assert_eq!(
unknown.get().parent(&call).map(|p| p.id()),
Some(consequence.id()),
"and the answer still climbs"
);
}
#[cfg(all(feature = "rust", debug_assertions))]
#[test]
#[should_panic(
expected = "descended into a function_item node the chain's last entry does not contain"
)]
fn descending_outside_the_last_entry_is_caught() {
let tree = Tree::new::<crate::langs::RustCode>(b"fn f() {}\nfn g() {}\n");
let root = tree.get_root();
let f = root.child(0).expect("the first fn item");
let g = root.child(1).expect("the second fn item");
let chain = [root];
let mut under = Ancestors::known(&chain).of_children(&f);
under.descend(&g);
}
#[cfg(all(feature = "rust", debug_assertions))]
#[test]
#[should_panic(expected = "ascended above the node this chain was built for")]
fn ascending_past_the_floor_is_caught() {
let tree = Tree::new::<crate::langs::RustCode>(b"fn f() {}\n");
let root = tree.get_root();
let item = root.child(0).expect("the fn item");
let chain = [root];
let mut under = Ancestors::known(&chain).of_children(&item);
under.ascend();
}
}