use std::ops::Index;
use crate::node::Node;
#[derive(Clone, Copy, Debug)]
pub(super) struct Chain<'tree, 'chain> {
pub(super) upper: &'chain [Node<'tree>],
pub(super) lower: &'chain [Node<'tree>],
}
impl<'tree, 'chain> Chain<'tree, 'chain> {
pub(super) const fn flat(nodes: &'chain [Node<'tree>]) -> Self {
Self {
upper: nodes,
lower: &[],
}
}
#[inline]
pub(super) const fn len(self) -> usize {
self.upper.len() + self.lower.len()
}
#[inline]
pub(super) fn get(self, depth: usize) -> Option<&'chain Node<'tree>> {
match depth.checked_sub(self.upper.len()) {
Some(below) => self.lower.get(below),
None => self.upper.get(depth),
}
}
#[inline]
pub(super) fn last(self) -> Option<&'chain Node<'tree>> {
self.lower.last().or_else(|| self.upper.last())
}
#[inline]
pub(super) fn above(self, depth: usize) -> Self {
match depth.checked_sub(self.upper.len()) {
Some(below) => Self {
upper: self.upper,
lower: &self.lower[..below],
},
None => Self::flat(&self.upper[..depth]),
}
}
#[inline]
pub(super) fn split_last(self) -> Option<(&'chain Node<'tree>, Self)> {
self.lower
.split_last()
.map(|(last, lower)| (last, Self { lower, ..self }))
.or_else(|| {
self.upper
.split_last()
.map(|(last, upper)| (last, Self::flat(upper)))
})
}
}
impl<'tree> Index<usize> for Chain<'tree, '_> {
type Output = Node<'tree>;
#[inline]
fn index(&self, depth: usize) -> &Node<'tree> {
match depth.checked_sub(self.upper.len()) {
Some(below) => &self.lower[below],
None => &self.upper[depth],
}
}
}
#[derive(Debug)]
pub(super) struct HeldChain<'tree, 'chain> {
upper: &'chain [Node<'tree>],
lower: Vec<Node<'tree>>,
floor: usize,
}
const MAX_INHERITED_RUN: usize = 2;
impl<'tree, 'chain> HeldChain<'tree, 'chain> {
pub(super) fn below(chain: Chain<'tree, 'chain>, node: Node<'tree>) -> Self {
#[cfg(chain_audit)]
assert_eq!(
chain.last().map(Node::id),
node.parent().map(|parent| parent.id()),
"derived a chain for the children of a {} node that is not its own",
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()
}),
"derived a chain for the children of a {} node its last entry does not contain",
node.kind()
);
debug_assert!(
chain.lower.len() <= MAX_INHERITED_RUN,
"derived from a chain {} levels below the walk's: derive once and descend, \
not once per level (#1805)",
chain.lower.len()
);
let lower = [chain.lower, std::slice::from_ref(&node)].concat();
Self {
upper: chain.upper,
floor: lower.len(),
lower,
}
}
pub(super) fn view(&self) -> Chain<'tree, '_> {
Chain {
upper: self.upper,
lower: &self.lower,
}
}
pub(super) fn descend(&mut self, child: &Node<'tree>) {
debug_assert!(
self.lower.last().is_some_and(|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()
);
self.lower.push(*child);
}
pub(super) fn ascend(&mut self) {
debug_assert!(
self.lower.len() > self.floor,
"ascended above the node this chain was built for"
);
if self.lower.len() > self.floor {
self.lower.pop();
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::node::Tree;
#[cfg(feature = "rust")]
#[test]
fn a_split_chain_reads_as_its_flat_slice() {
let tree = Tree::new::<crate::langs::RustCode>(b"mod a { mod b { fn f() { g(1); } } }\n");
let nodes: Vec<Node> = tree.get_root().preorder().take(7).collect();
assert_eq!(nodes.len(), 7, "the fixture holds seven nodes");
let ids = |nodes: &[Node]| nodes.iter().map(Node::id).collect::<Vec<_>>();
let unsplit = |chain: Chain| {
let mut entries = Vec::new();
let mut rest = chain;
while let Some((last, above)) = rest.split_last() {
entries.push(last.id());
rest = above;
}
entries.reverse();
entries
};
for split in 0..=nodes.len() {
let (upper, lower) = nodes.split_at(split);
let chain = Chain { upper, lower };
assert_eq!(chain.len(), nodes.len(), "split {split}");
assert_eq!(chain.last().map(Node::id), nodes.last().map(Node::id));
assert_eq!(unsplit(chain), ids(&nodes), "split {split}");
for depth in 0..=nodes.len() {
assert_eq!(
chain.get(depth).map(Node::id),
nodes.get(depth).map(Node::id),
"split {split}, depth {depth}"
);
if let Some(node) = nodes.get(depth) {
assert_eq!(chain[depth].id(), node.id(), "split {split}, depth {depth}");
}
assert_eq!(
unsplit(chain.above(depth)),
ids(&nodes[..depth]),
"split {split}, above {depth}"
);
}
}
}
#[cfg(feature = "rust")]
fn seven_nodes(tree: &Tree) -> Vec<Node<'_>> {
let nodes: Vec<Node> = tree.get_root().preorder().take(7).collect();
assert_eq!(nodes.len(), 7, "the fixture holds seven nodes");
nodes
}
#[cfg(feature = "rust")]
const SPLIT_FIXTURE: &[u8] = b"mod a { mod b { fn f() { g(1); } } }\n";
#[cfg(feature = "rust")]
#[test]
#[should_panic(expected = "range end index 4 out of range for slice of length 3")]
fn above_past_the_end_panics_as_a_slice_does() {
let tree = Tree::new::<crate::langs::RustCode>(SPLIT_FIXTURE);
let nodes = seven_nodes(&tree);
let (upper, lower) = nodes.split_at(4);
let _ = Chain { upper, lower }.above(nodes.len() + 1);
}
#[cfg(feature = "rust")]
#[test]
#[should_panic(expected = "index out of bounds: the len is 3 but the index is 3")]
fn index_at_the_end_panics_as_a_slice_does() {
let tree = Tree::new::<crate::langs::RustCode>(SPLIT_FIXTURE);
let nodes = seven_nodes(&tree);
let (upper, lower) = nodes.split_at(4);
let _ = &Chain { upper, lower }[nodes.len()];
}
}