#![warn(missing_docs)]
use codec::{Decode, Encode};
use std::{cmp::Reverse, fmt};
#[derive(Clone, Debug, PartialEq)]
pub enum Error<E> {
Duplicate,
UnfinalizedAncestor,
Revert,
Client(E),
}
impl<E: std::error::Error> fmt::Display for Error<E> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let message = match *self {
Error::Duplicate => "Hash already exists in Tree".into(),
Error::UnfinalizedAncestor => "Finalized descendent of Tree node without finalizing its ancestor(s) first".into(),
Error::Revert => "Tried to import or finalize node that is an ancestor of a previously finalized node".into(),
Error::Client(ref err) => format!("Client error: {}", err),
};
write!(f, "{}", message)
}
}
impl<E: std::error::Error> std::error::Error for Error<E> {}
impl<E: std::error::Error> From<E> for Error<E> {
fn from(err: E) -> Error<E> {
Error::Client(err)
}
}
#[derive(Debug, PartialEq)]
pub enum FinalizationResult<V> {
Changed(Option<V>),
Unchanged,
}
#[derive(Debug, PartialEq)]
pub enum FilterAction {
Remove,
KeepNode,
KeepTree,
}
#[derive(Clone, Debug, Decode, Encode, PartialEq)]
pub struct ForkTree<H, N, V> {
roots: Vec<Node<H, N, V>>,
best_finalized_number: Option<N>,
}
impl<H, N, V> ForkTree<H, N, V>
where
H: PartialEq,
N: Ord,
{
pub fn new() -> ForkTree<H, N, V> {
ForkTree { roots: Vec::new(), best_finalized_number: None }
}
pub fn rebalance(&mut self) {
self.roots.sort_by_key(|n| Reverse(n.max_depth()));
let mut stack: Vec<_> = self.roots.iter_mut().collect();
while let Some(node) = stack.pop() {
node.children.sort_by_key(|n| Reverse(n.max_depth()));
stack.extend(node.children.iter_mut());
}
}
pub fn import<F, E>(
&mut self,
hash: H,
number: N,
data: V,
is_descendent_of: &F,
) -> Result<bool, Error<E>>
where
E: std::error::Error,
F: Fn(&H, &H) -> Result<bool, E>,
{
if let Some(ref best_finalized_number) = self.best_finalized_number {
if number <= *best_finalized_number {
return Err(Error::Revert)
}
}
let (children, is_root) =
match self.find_node_where_mut(&hash, &number, is_descendent_of, &|_| true)? {
Some(parent) => (&mut parent.children, false),
None => (&mut self.roots, true),
};
if children.iter().any(|elem| elem.hash == hash) {
return Err(Error::Duplicate)
}
children.push(Node { data, hash, number, children: Default::default() });
if children.len() == 1 {
self.rebalance();
}
Ok(is_root)
}
pub fn roots(&self) -> impl Iterator<Item = (&H, &N, &V)> {
self.roots.iter().map(|node| (&node.hash, &node.number, &node.data))
}
fn node_iter(&self) -> impl Iterator<Item = &Node<H, N, V>> {
ForkTreeIterator { stack: self.roots.iter().rev().collect() }
}
pub fn iter(&self) -> impl Iterator<Item = (&H, &N, &V)> {
self.node_iter().map(|node| (&node.hash, &node.number, &node.data))
}
pub fn map<VT, F>(self, f: &mut F) -> ForkTree<H, N, VT>
where
F: FnMut(&H, &N, V) -> VT,
{
let mut queue: Vec<_> =
self.roots.into_iter().rev().map(|node| (usize::MAX, node)).collect();
let mut next_queue = Vec::new();
let mut output = Vec::new();
while !queue.is_empty() {
for (parent_index, node) in queue.drain(..) {
let new_data = f(&node.hash, &node.number, node.data);
let new_node = Node {
hash: node.hash,
number: node.number,
data: new_data,
children: Vec::with_capacity(node.children.len()),
};
let node_id = output.len();
output.push((parent_index, new_node));
for child in node.children.into_iter().rev() {
next_queue.push((node_id, child));
}
}
std::mem::swap(&mut queue, &mut next_queue);
}
let mut roots = Vec::new();
while let Some((parent_index, new_node)) = output.pop() {
if parent_index == usize::MAX {
roots.push(new_node);
} else {
output[parent_index].1.children.push(new_node);
}
}
ForkTree { roots, best_finalized_number: self.best_finalized_number }
}
pub fn find_node_where<F, E, P>(
&self,
hash: &H,
number: &N,
is_descendent_of: &F,
predicate: &P,
) -> Result<Option<&Node<H, N, V>>, Error<E>>
where
E: std::error::Error,
F: Fn(&H, &H) -> Result<bool, E>,
P: Fn(&V) -> bool,
{
let maybe_path = self.find_node_index_where(hash, number, is_descendent_of, predicate)?;
Ok(maybe_path.map(|path| {
let children =
path.iter().take(path.len() - 1).fold(&self.roots, |curr, &i| &curr[i].children);
&children[path[path.len() - 1]]
}))
}
pub fn find_node_where_mut<F, E, P>(
&mut self,
hash: &H,
number: &N,
is_descendent_of: &F,
predicate: &P,
) -> Result<Option<&mut Node<H, N, V>>, Error<E>>
where
E: std::error::Error,
F: Fn(&H, &H) -> Result<bool, E>,
P: Fn(&V) -> bool,
{
let maybe_path = self.find_node_index_where(hash, number, is_descendent_of, predicate)?;
Ok(maybe_path.map(|path| {
let children = path
.iter()
.take(path.len() - 1)
.fold(&mut self.roots, |curr, &i| &mut curr[i].children);
&mut children[path[path.len() - 1]]
}))
}
pub fn find_node_index_where<F, E, P>(
&self,
hash: &H,
number: &N,
is_descendent_of: &F,
predicate: &P,
) -> Result<Option<Vec<usize>>, Error<E>>
where
E: std::error::Error,
F: Fn(&H, &H) -> Result<bool, E>,
P: Fn(&V) -> bool,
{
let mut stack = vec![];
let mut root_idx = 0;
let mut found = false;
let mut is_descendent = false;
while root_idx < self.roots.len() {
if *number <= self.roots[root_idx].number {
root_idx += 1;
continue
}
stack.push((&self.roots[root_idx], 0));
while let Some((node, i)) = stack.pop() {
if i < node.children.len() && !is_descendent {
stack.push((node, i + 1));
if node.children[i].number < *number {
stack.push((&node.children[i], 0));
}
} else if is_descendent || is_descendent_of(&node.hash, hash)? {
is_descendent = true;
if predicate(&node.data) {
found = true;
break
}
}
}
if is_descendent {
break
}
root_idx += 1;
}
Ok(if found {
let path: Vec<_> =
std::iter::once(root_idx).chain(stack.iter().map(|(_, i)| *i - 1)).collect();
Some(path)
} else {
None
})
}
pub fn prune<F, E, P>(
&mut self,
hash: &H,
number: &N,
is_descendent_of: &F,
predicate: &P,
) -> Result<impl Iterator<Item = (H, N, V)>, Error<E>>
where
E: std::error::Error,
F: Fn(&H, &H) -> Result<bool, E>,
P: Fn(&V) -> bool,
{
let new_root_path =
match self.find_node_index_where(hash, number, is_descendent_of, predicate)? {
Some(path) => path,
None => return Ok(RemovedIterator { stack: Vec::new() }),
};
let mut removed = std::mem::take(&mut self.roots);
let root_siblings = new_root_path
.iter()
.take(new_root_path.len() - 1)
.fold(&mut removed, |curr, idx| &mut curr[*idx].children);
let root = root_siblings.remove(new_root_path[new_root_path.len() - 1]);
self.roots = vec![root];
let mut curr = &mut self.roots[0];
loop {
let mut maybe_ancestor_idx = None;
for (idx, child) in curr.children.iter().enumerate() {
if child.number < *number && is_descendent_of(&child.hash, hash)? {
maybe_ancestor_idx = Some(idx);
break
}
}
let Some(ancestor_idx) = maybe_ancestor_idx else {
break
};
let mut next_siblings = std::mem::take(&mut curr.children);
let next = next_siblings.remove(ancestor_idx);
curr.children = vec![next];
removed.append(&mut next_siblings);
curr = &mut curr.children[0];
}
let children = std::mem::take(&mut curr.children);
for child in children {
if child.number == *number && child.hash == *hash ||
*number < child.number && is_descendent_of(hash, &child.hash)?
{
curr.children.push(child);
} else {
removed.push(child);
}
}
self.rebalance();
Ok(RemovedIterator { stack: removed })
}
pub fn finalize_root(&mut self, hash: &H) -> Option<V> {
self.roots
.iter()
.position(|node| node.hash == *hash)
.map(|position| self.finalize_root_at(position))
}
fn finalize_root_at(&mut self, position: usize) -> V {
let node = self.roots.swap_remove(position);
self.roots = node.children;
self.best_finalized_number = Some(node.number);
node.data
}
pub fn finalize<F, E>(
&mut self,
hash: &H,
number: N,
is_descendent_of: &F,
) -> Result<FinalizationResult<V>, Error<E>>
where
E: std::error::Error,
F: Fn(&H, &H) -> Result<bool, E>,
{
if let Some(ref best_finalized_number) = self.best_finalized_number {
if number <= *best_finalized_number {
return Err(Error::Revert)
}
}
if let Some(root) = self.finalize_root(hash) {
return Ok(FinalizationResult::Changed(Some(root)))
}
for root in self.roots.iter() {
if number > root.number && is_descendent_of(&root.hash, hash)? {
return Err(Error::UnfinalizedAncestor)
}
}
let mut changed = false;
let roots = std::mem::take(&mut self.roots);
for root in roots {
if root.number > number && is_descendent_of(hash, &root.hash)? {
self.roots.push(root);
} else {
changed = true;
}
}
self.best_finalized_number = Some(number);
if changed {
Ok(FinalizationResult::Changed(None))
} else {
Ok(FinalizationResult::Unchanged)
}
}
pub fn finalize_with_ancestors<F, E>(
&mut self,
hash: &H,
number: N,
is_descendent_of: &F,
) -> Result<FinalizationResult<V>, Error<E>>
where
E: std::error::Error,
F: Fn(&H, &H) -> Result<bool, E>,
{
if let Some(ref best_finalized_number) = self.best_finalized_number {
if number <= *best_finalized_number {
return Err(Error::Revert)
}
}
if let Some(root) = self.finalize_root(hash) {
return Ok(FinalizationResult::Changed(Some(root)))
}
let mut changed = false;
let mut idx = 0;
while idx != self.roots.len() {
let (is_finalized, is_descendant, is_ancestor) = {
let root = &self.roots[idx];
let is_finalized = root.hash == *hash;
let is_descendant =
!is_finalized && root.number > number && is_descendent_of(hash, &root.hash)?;
let is_ancestor = !is_finalized &&
!is_descendant && root.number < number &&
is_descendent_of(&root.hash, hash)?;
(is_finalized, is_descendant, is_ancestor)
};
if is_finalized {
return Ok(FinalizationResult::Changed(Some(self.finalize_root_at(idx))))
}
if is_descendant {
idx += 1;
continue
}
if is_ancestor {
let root = self.roots.swap_remove(idx);
self.roots.extend(root.children);
changed = true;
continue
}
self.roots.swap_remove(idx);
changed = true;
}
self.best_finalized_number = Some(number);
if changed {
Ok(FinalizationResult::Changed(None))
} else {
Ok(FinalizationResult::Unchanged)
}
}
pub fn finalizes_any_with_descendent_if<F, P, E>(
&self,
hash: &H,
number: N,
is_descendent_of: &F,
predicate: P,
) -> Result<Option<bool>, Error<E>>
where
E: std::error::Error,
F: Fn(&H, &H) -> Result<bool, E>,
P: Fn(&V) -> bool,
{
if let Some(ref best_finalized_number) = self.best_finalized_number {
if number <= *best_finalized_number {
return Err(Error::Revert)
}
}
for node in self.node_iter() {
if predicate(&node.data) && (node.hash == *hash || is_descendent_of(&node.hash, hash)?)
{
for child in node.children.iter() {
if child.number <= number &&
(child.hash == *hash || is_descendent_of(&child.hash, hash)?)
{
return Err(Error::UnfinalizedAncestor)
}
}
return Ok(Some(self.roots.iter().any(|root| root.hash == node.hash)))
}
}
Ok(None)
}
pub fn finalize_with_descendent_if<F, P, E>(
&mut self,
hash: &H,
number: N,
is_descendent_of: &F,
predicate: P,
) -> Result<FinalizationResult<V>, Error<E>>
where
E: std::error::Error,
F: Fn(&H, &H) -> Result<bool, E>,
P: Fn(&V) -> bool,
{
if let Some(ref best_finalized_number) = self.best_finalized_number {
if number <= *best_finalized_number {
return Err(Error::Revert)
}
}
let mut position = None;
for (i, root) in self.roots.iter().enumerate() {
if predicate(&root.data) && (root.hash == *hash || is_descendent_of(&root.hash, hash)?)
{
for child in root.children.iter() {
if child.number <= number &&
(child.hash == *hash || is_descendent_of(&child.hash, hash)?)
{
return Err(Error::UnfinalizedAncestor)
}
}
position = Some(i);
break
}
}
let node_data = position.map(|i| {
let node = self.roots.swap_remove(i);
self.roots = node.children;
self.best_finalized_number = Some(node.number);
node.data
});
let mut changed = false;
let roots = std::mem::take(&mut self.roots);
for root in roots {
let retain = root.number > number && is_descendent_of(hash, &root.hash)? ||
root.number == number && root.hash == *hash ||
is_descendent_of(&root.hash, hash)?;
if retain {
self.roots.push(root);
} else {
changed = true;
}
}
self.best_finalized_number = Some(number);
match (node_data, changed) {
(Some(data), _) => Ok(FinalizationResult::Changed(Some(data))),
(None, true) => Ok(FinalizationResult::Changed(None)),
(None, false) => Ok(FinalizationResult::Unchanged),
}
}
pub fn drain_filter<F>(&mut self, filter: F) -> impl Iterator<Item = (H, N, V)>
where
F: Fn(&H, &N, &V) -> FilterAction,
{
let mut removed = vec![];
let mut retained = Vec::new();
let mut queue: Vec<_> = std::mem::take(&mut self.roots)
.into_iter()
.rev()
.map(|node| (usize::MAX, node))
.collect();
let mut next_queue = Vec::new();
while !queue.is_empty() {
for (parent_idx, mut node) in queue.drain(..) {
match filter(&node.hash, &node.number, &node.data) {
FilterAction::KeepNode => {
let node_idx = retained.len();
let children = std::mem::take(&mut node.children);
retained.push((parent_idx, node));
for child in children.into_iter().rev() {
next_queue.push((node_idx, child));
}
},
FilterAction::KeepTree => {
retained.push((parent_idx, node));
},
FilterAction::Remove => {
removed.push(node);
},
}
}
std::mem::swap(&mut queue, &mut next_queue);
}
while let Some((parent_idx, node)) = retained.pop() {
if parent_idx == usize::MAX {
self.roots.push(node);
} else {
retained[parent_idx].1.children.push(node);
}
}
if !removed.is_empty() {
self.rebalance();
}
RemovedIterator { stack: removed }
}
}
use node_implementation::Node;
mod node_implementation {
use super::*;
#[derive(Clone, Debug, Decode, Encode, PartialEq)]
pub struct Node<H, N, V> {
pub hash: H,
pub number: N,
pub data: V,
pub children: Vec<Node<H, N, V>>,
}
impl<H: PartialEq, N: Ord, V> Node<H, N, V> {
pub fn max_depth(&self) -> usize {
let mut max: usize = 0;
let mut stack = vec![(self, 0)];
while let Some((node, height)) = stack.pop() {
if height > max {
max = height;
}
node.children.iter().for_each(|n| stack.push((n, height + 1)));
}
max
}
}
}
struct ForkTreeIterator<'a, H, N, V> {
stack: Vec<&'a Node<H, N, V>>,
}
impl<'a, H, N, V> Iterator for ForkTreeIterator<'a, H, N, V> {
type Item = &'a Node<H, N, V>;
fn next(&mut self) -> Option<Self::Item> {
self.stack.pop().inspect(|node| {
self.stack.extend(node.children.iter().rev());
})
}
}
struct RemovedIterator<H, N, V> {
stack: Vec<Node<H, N, V>>,
}
impl<H, N, V> Iterator for RemovedIterator<H, N, V> {
type Item = (H, N, V);
fn next(&mut self) -> Option<Self::Item> {
self.stack.pop().map(|mut node| {
let children = std::mem::take(&mut node.children);
self.stack.extend(children.into_iter().rev());
(node.hash, node.number, node.data)
})
}
}
#[cfg(test)]
mod test {
use crate::FilterAction;
use super::{Error, FinalizationResult, ForkTree};
#[derive(Debug, PartialEq)]
struct TestError;
impl std::fmt::Display for TestError {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(f, "TestError")
}
}
impl std::error::Error for TestError {}
fn test_fork_tree<'a>(
) -> (ForkTree<&'a str, u64, u32>, impl Fn(&&str, &&str) -> Result<bool, TestError>) {
let mut tree = ForkTree::new();
#[rustfmt::skip]
let is_descendent_of = |base: &&str, block: &&str| -> Result<bool, TestError> {
let letters = vec!["B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"];
let block = block.to_uppercase();
match (*base, block) {
("A", b) => Ok(letters.into_iter().any(|n| n == b)),
("B" | "c", b) => Ok(b == "C" || b == "D" || b == "E"),
("C", b) => Ok(b == "D" || b == "E"),
("D", b) => Ok(b == "E"),
("E", _) => Ok(false),
("F", b) =>
Ok(b == "G" || b == "H" || b == "I" || b == "L" || b == "M" || b == "N" || b == "O"),
("G", _) => Ok(false),
("H", b) => Ok(b == "I" || b == "L" || b == "M" || b == "N" || b == "O"),
("I", _) => Ok(false),
("J", b) => Ok(b == "K"),
("K", _) => Ok(false),
("L", b) => Ok(b == "M" || b == "N" || b == "O"),
("m", b) => Ok(b == "M" || b == "N"),
("M", b) => Ok(b == "N"),
("O", _) => Ok(false),
("0", _) => Ok(true),
_ => Ok(false),
}
};
tree.import("A", 10, 1, &is_descendent_of).unwrap();
tree.import("B", 20, 2, &is_descendent_of).unwrap();
tree.import("C", 30, 3, &is_descendent_of).unwrap();
tree.import("D", 40, 4, &is_descendent_of).unwrap();
tree.import("E", 50, 5, &is_descendent_of).unwrap();
tree.import("F", 20, 2, &is_descendent_of).unwrap();
tree.import("G", 30, 3, &is_descendent_of).unwrap();
tree.import("H", 30, 3, &is_descendent_of).unwrap();
tree.import("I", 40, 4, &is_descendent_of).unwrap();
tree.import("L", 40, 4, &is_descendent_of).unwrap();
tree.import("M", 50, 5, &is_descendent_of).unwrap();
tree.import("O", 50, 5, &is_descendent_of).unwrap();
tree.import("J", 20, 2, &is_descendent_of).unwrap();
tree.import("K", 30, 3, &is_descendent_of).unwrap();
(tree, is_descendent_of)
}
#[test]
fn import_doesnt_revert() {
let (mut tree, is_descendent_of) = test_fork_tree();
tree.finalize_root(&"A");
assert_eq!(tree.best_finalized_number, Some(10));
assert_eq!(tree.import("A", 10, 1, &is_descendent_of), Err(Error::Revert));
}
#[test]
fn import_doesnt_add_duplicates() {
let (mut tree, is_descendent_of) = test_fork_tree();
assert_eq!(tree.import("A", 10, 1, &is_descendent_of), Err(Error::Duplicate));
assert_eq!(tree.import("I", 40, 4, &is_descendent_of), Err(Error::Duplicate));
assert_eq!(tree.import("G", 30, 3, &is_descendent_of), Err(Error::Duplicate));
assert_eq!(tree.import("K", 30, 3, &is_descendent_of), Err(Error::Duplicate));
}
#[test]
fn finalize_root_works() {
let finalize_a = || {
let (mut tree, ..) = test_fork_tree();
assert_eq!(tree.roots().map(|(h, n, _)| (*h, *n)).collect::<Vec<_>>(), vec![("A", 10)]);
tree.finalize_root(&"A");
assert_eq!(
tree.roots().map(|(h, n, _)| (*h, *n)).collect::<Vec<_>>(),
vec![("B", 20), ("F", 20), ("J", 20)],
);
tree
};
{
let mut tree = finalize_a();
tree.finalize_root(&"B");
assert_eq!(tree.roots().map(|(h, n, _)| (*h, *n)).collect::<Vec<_>>(), vec![("C", 30)],);
assert!(tree.roots.len() == 1);
}
{
let mut tree = finalize_a();
tree.finalize_root(&"J");
assert_eq!(tree.roots().map(|(h, n, _)| (*h, *n)).collect::<Vec<_>>(), vec![("K", 30)],);
assert!(tree.roots.len() == 1);
}
}
#[test]
fn finalize_works() {
let (mut tree, is_descendent_of) = test_fork_tree();
let original_roots = tree.roots.clone();
assert_eq!(tree.finalize(&"0", 0, &is_descendent_of), Ok(FinalizationResult::Unchanged));
assert_eq!(tree.roots, original_roots);
assert_eq!(
tree.finalize(&"A", 10, &is_descendent_of),
Ok(FinalizationResult::Changed(Some(1))),
);
assert_eq!(
tree.roots().map(|(h, n, _)| (*h, *n)).collect::<Vec<_>>(),
vec![("B", 20), ("F", 20), ("J", 20)],
);
assert_eq!(tree.best_finalized_number, Some(10));
assert_eq!(tree.finalize(&"Z", 10, &is_descendent_of), Err(Error::Revert));
assert_eq!(tree.finalize(&"H", 30, &is_descendent_of), Err(Error::UnfinalizedAncestor));
assert_eq!(
tree.finalize(&"F", 20, &is_descendent_of),
Ok(FinalizationResult::Changed(Some(2))),
);
assert_eq!(
tree.finalize(&"H", 30, &is_descendent_of),
Ok(FinalizationResult::Changed(Some(3))),
);
assert_eq!(
tree.roots().map(|(h, n, _)| (*h, *n)).collect::<Vec<_>>(),
vec![("L", 40), ("I", 40)],
);
assert_eq!(
tree.finalize(&"Z", 50, &is_descendent_of),
Ok(FinalizationResult::Changed(None)),
);
assert!(tree.roots.is_empty());
}
#[test]
fn finalize_with_ancestor_works() {
let (mut tree, is_descendent_of) = test_fork_tree();
let original_roots = tree.roots.clone();
assert_eq!(
tree.finalize_with_ancestors(&"0", 0, &is_descendent_of),
Ok(FinalizationResult::Unchanged),
);
assert_eq!(tree.roots, original_roots);
assert_eq!(
tree.finalize_with_ancestors(&"A", 10, &is_descendent_of),
Ok(FinalizationResult::Changed(Some(1))),
);
assert_eq!(
tree.roots().map(|(h, n, _)| (*h, *n)).collect::<Vec<_>>(),
vec![("B", 20), ("F", 20), ("J", 20)],
);
assert_eq!(
tree.finalize_with_ancestors(&"H", 30, &is_descendent_of),
Ok(FinalizationResult::Changed(Some(3))),
);
assert_eq!(
tree.roots().map(|(h, n, _)| (*h, *n)).collect::<Vec<_>>(),
vec![("L", 40), ("I", 40)],
);
assert_eq!(tree.best_finalized_number, Some(30));
assert_eq!(
tree.finalize_with_ancestors(&"N", 60, &is_descendent_of),
Ok(FinalizationResult::Changed(None)),
);
assert_eq!(tree.roots().map(|(h, n, _)| (*h, *n)).collect::<Vec<_>>(), vec![],);
assert_eq!(tree.best_finalized_number, Some(60));
}
#[test]
fn finalize_with_descendent_works() {
#[derive(Debug, PartialEq)]
struct Change {
effective: u64,
}
let (mut tree, is_descendent_of) = {
let mut tree = ForkTree::new();
let is_descendent_of = |base: &&str, block: &&str| -> Result<bool, TestError> {
match (*base, *block) {
("A0", b) => Ok(b == "B" || b == "C" || b == "D" || b == "E" || b == "G"),
("A1", _) => Ok(false),
("C", b) => Ok(b == "D"),
("D", b) => Ok(b == "E" || b == "F" || b == "G"),
("E", b) => Ok(b == "F"),
_ => Ok(false),
}
};
let is_root = tree.import("A0", 1, Change { effective: 5 }, &is_descendent_of).unwrap();
assert!(is_root);
let is_root = tree.import("A1", 1, Change { effective: 5 }, &is_descendent_of).unwrap();
assert!(is_root);
let is_root =
tree.import("D", 10, Change { effective: 10 }, &is_descendent_of).unwrap();
assert!(!is_root);
let is_root =
tree.import("E", 15, Change { effective: 50 }, &is_descendent_of).unwrap();
assert!(!is_root);
(tree, is_descendent_of)
};
assert_eq!(
tree.finalizes_any_with_descendent_if(
&"B",
2,
&is_descendent_of,
|c| c.effective <= 2,
),
Ok(None),
);
assert_eq!(
tree.finalize_with_descendent_if(&"D", 10, &is_descendent_of, |c| c.effective <= 10),
Err(Error::UnfinalizedAncestor)
);
assert_eq!(
tree.finalizes_any_with_descendent_if(&"D", 10, &is_descendent_of, |c| c.effective ==
10),
Ok(Some(false)),
);
assert_eq!(
tree.finalizes_any_with_descendent_if(&"E", 15, &is_descendent_of, |c| c.effective ==
10),
Err(Error::UnfinalizedAncestor)
);
assert_eq!(
tree.finalize_with_descendent_if(&"B", 2, &is_descendent_of, |c| c.effective <= 2),
Ok(FinalizationResult::Changed(None)),
);
assert_eq!(tree.roots().map(|(h, n, _)| (*h, *n)).collect::<Vec<_>>(), vec![("A0", 1)],);
assert_eq!(
tree.finalizes_any_with_descendent_if(
&"C",
5,
&is_descendent_of,
|c| c.effective <= 5,
),
Ok(Some(true)),
);
assert_eq!(
tree.finalize_with_descendent_if(&"C", 5, &is_descendent_of, |c| c.effective <= 5),
Ok(FinalizationResult::Changed(Some(Change { effective: 5 }))),
);
assert_eq!(tree.roots().map(|(h, n, _)| (*h, *n)).collect::<Vec<_>>(), vec![("D", 10)],);
assert_eq!(
tree.finalizes_any_with_descendent_if(&"F", 100, &is_descendent_of, |c| c.effective <=
100,),
Err(Error::UnfinalizedAncestor),
);
assert_eq!(
tree.finalizes_any_with_descendent_if(&"G", 100, &is_descendent_of, |c| c.effective <=
100),
Ok(Some(true)),
);
assert_eq!(
tree.finalize_with_descendent_if(&"G", 100, &is_descendent_of, |c| c.effective <= 100),
Ok(FinalizationResult::Changed(Some(Change { effective: 10 }))),
);
assert_eq!(tree.roots().count(), 0);
}
#[test]
fn iter_iterates_in_preorder() {
let (tree, ..) = test_fork_tree();
assert_eq!(
tree.iter().map(|(h, n, _)| (*h, *n)).collect::<Vec<_>>(),
vec![
("A", 10),
("B", 20),
("C", 30),
("D", 40),
("E", 50),
("F", 20),
("H", 30),
("L", 40),
("M", 50),
("O", 50),
("I", 40),
("G", 30),
("J", 20),
("K", 30),
],
);
}
#[test]
fn minimizes_calls_to_is_descendent_of() {
use std::sync::atomic::{AtomicUsize, Ordering};
let n_is_descendent_of_calls = AtomicUsize::new(0);
let is_descendent_of = |_: &&str, _: &&str| -> Result<bool, TestError> {
n_is_descendent_of_calls.fetch_add(1, Ordering::SeqCst);
Ok(true)
};
{
let mut tree = ForkTree::new();
let letters = vec!["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"];
for (i, letter) in letters.iter().enumerate() {
tree.import::<_, TestError>(*letter, i, i, &|_, _| Ok(true)).unwrap();
}
assert_eq!(
tree.finalizes_any_with_descendent_if(&"L", 11, &is_descendent_of, |i| *i == 10,),
Ok(Some(false)),
);
assert_eq!(n_is_descendent_of_calls.load(Ordering::SeqCst), 1);
}
n_is_descendent_of_calls.store(0, Ordering::SeqCst);
{
let mut tree = ForkTree::new();
let letters = vec!["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"];
for (i, letter) in letters.iter().enumerate() {
tree.import::<_, TestError>(*letter, i, i, &|_, _| Ok(false)).unwrap();
}
assert_eq!(
tree.finalize_with_descendent_if(&"L", 11, &is_descendent_of, |i| *i == 10,),
Ok(FinalizationResult::Changed(Some(10))),
);
assert_eq!(n_is_descendent_of_calls.load(Ordering::SeqCst), 1);
}
}
#[test]
fn map_works() {
let (mut tree, _) = test_fork_tree();
let is_descendent_of = |_: &&str, _: &&str| -> Result<bool, TestError> { Ok(false) };
let is_root = tree.import("A1", 10, 1, &is_descendent_of).unwrap();
assert!(is_root);
let is_root = tree.import("A2", 10, 1, &is_descendent_of).unwrap();
assert!(is_root);
let old_tree = tree.clone();
let new_tree = tree.map(&mut |hash, _, _| hash.to_owned());
assert!(new_tree.iter().all(|(hash, _, data)| hash == data));
assert_eq!(
old_tree.iter().map(|(hash, _, _)| *hash).collect::<Vec<_>>(),
new_tree.iter().map(|(hash, _, _)| *hash).collect::<Vec<_>>(),
);
}
#[test]
fn prune_works_for_in_tree_hashes() {
let (mut tree, is_descendent_of) = test_fork_tree();
let removed = tree.prune(&"C", &30, &is_descendent_of, &|_| true).unwrap();
assert_eq!(tree.roots.iter().map(|node| node.hash).collect::<Vec<_>>(), vec!["B"]);
assert_eq!(
tree.iter().map(|(hash, _, _)| *hash).collect::<Vec<_>>(),
vec!["B", "C", "D", "E"],
);
assert_eq!(
removed.map(|(hash, _, _)| hash).collect::<Vec<_>>(),
vec!["A", "F", "H", "L", "M", "O", "I", "G", "J", "K"]
);
let removed = tree.prune(&"E", &50, &is_descendent_of, &|_| true).unwrap();
assert_eq!(tree.roots.iter().map(|node| node.hash).collect::<Vec<_>>(), vec!["D"]);
assert_eq!(tree.iter().map(|(hash, _, _)| *hash).collect::<Vec<_>>(), vec!["D", "E"]);
assert_eq!(removed.map(|(hash, _, _)| hash).collect::<Vec<_>>(), vec!["B", "C"]);
}
#[test]
fn prune_works_for_out_of_tree_hashes() {
let (mut tree, is_descendent_of) = test_fork_tree();
let removed = tree.prune(&"c", &25, &is_descendent_of, &|_| true).unwrap();
assert_eq!(tree.roots.iter().map(|node| node.hash).collect::<Vec<_>>(), vec!["B"]);
assert_eq!(
tree.iter().map(|(hash, _, _)| *hash).collect::<Vec<_>>(),
vec!["B", "C", "D", "E"],
);
assert_eq!(
removed.map(|(hash, _, _)| hash).collect::<Vec<_>>(),
vec!["A", "F", "H", "L", "M", "O", "I", "G", "J", "K"]
);
}
#[test]
fn prune_works_for_not_direct_ancestor() {
let (mut tree, is_descendent_of) = test_fork_tree();
let removed = tree.prune(&"m", &45, &is_descendent_of, &|height| *height == 3).unwrap();
assert_eq!(tree.roots.iter().map(|node| node.hash).collect::<Vec<_>>(), vec!["H"]);
assert_eq!(tree.iter().map(|(hash, _, _)| *hash).collect::<Vec<_>>(), vec!["H", "L", "M"],);
assert_eq!(
removed.map(|(hash, _, _)| hash).collect::<Vec<_>>(),
vec!["O", "I", "A", "B", "C", "D", "E", "F", "G", "J", "K"]
);
}
#[test]
fn prune_works_for_far_away_ancestor() {
let (mut tree, is_descendent_of) = test_fork_tree();
let removed = tree.prune(&"m", &45, &is_descendent_of, &|height| *height == 2).unwrap();
assert_eq!(tree.roots.iter().map(|node| node.hash).collect::<Vec<_>>(), vec!["F"]);
assert_eq!(
tree.iter().map(|(hash, _, _)| *hash).collect::<Vec<_>>(),
vec!["F", "H", "L", "M"],
);
assert_eq!(
removed.map(|(hash, _, _)| hash).collect::<Vec<_>>(),
vec!["O", "I", "G", "A", "B", "C", "D", "E", "J", "K"]
);
}
#[test]
fn find_node_backtracks_after_finding_highest_descending_node() {
let mut tree = ForkTree::new();
let is_descendent_of = |base: &&str, block: &&str| -> Result<bool, TestError> {
match (*base, *block) {
("A", b) => Ok(b == "B" || b == "C" || b == "D"),
("B", b) | ("C", b) => Ok(b == "D"),
("0", _) => Ok(true),
_ => Ok(false),
}
};
tree.import("A", 1, 1, &is_descendent_of).unwrap();
tree.import("B", 2, 2, &is_descendent_of).unwrap();
tree.import("C", 2, 4, &is_descendent_of).unwrap();
let node = tree.find_node_where(&"D", &3, &is_descendent_of, &|data| *data < 3).unwrap();
assert_eq!(node.unwrap().hash, "B");
}
#[test]
fn rebalance_works() {
let (mut tree, _) = test_fork_tree();
assert_eq!(
tree.iter().map(|(h, _, _)| *h).collect::<Vec<_>>(),
vec!["A", "B", "C", "D", "E", "F", "H", "L", "M", "O", "I", "G", "J", "K"],
);
let is_descendent_of = |base: &&str, block: &&str| -> Result<bool, TestError> {
match (*base, *block) {
(b, "P") => Ok(vec!["A", "F", "H", "L", "O"].into_iter().any(|n| n == b)),
_ => Ok(false),
}
};
tree.import("P", 60, 6, &is_descendent_of).unwrap();
assert_eq!(
tree.iter().map(|(h, _, _)| *h).collect::<Vec<_>>(),
["A", "F", "H", "L", "O", "P", "M", "I", "G", "B", "C", "D", "E", "J", "K"]
);
}
#[test]
fn drain_filter_works() {
let (mut tree, _) = test_fork_tree();
let filter = |h: &&str, _: &u64, _: &u32| match *h {
"A" | "B" | "F" | "G" => FilterAction::KeepNode,
"C" => FilterAction::KeepTree,
"H" | "J" => FilterAction::Remove,
_ => panic!("Unexpected filtering for node: {}", *h),
};
let removed = tree.drain_filter(filter);
assert_eq!(
tree.iter().map(|(h, _, _)| *h).collect::<Vec<_>>(),
["A", "B", "C", "D", "E", "F", "G"]
);
assert_eq!(
removed.map(|(h, _, _)| h).collect::<Vec<_>>(),
["H", "L", "M", "O", "I", "J", "K"]
);
}
#[test]
fn find_node_index_works() {
let (tree, is_descendent_of) = test_fork_tree();
let path = tree
.find_node_index_where(&"D", &40, &is_descendent_of, &|_| true)
.unwrap()
.unwrap();
assert_eq!(path, [0, 0, 0]);
let path = tree
.find_node_index_where(&"O", &50, &is_descendent_of, &|_| true)
.unwrap()
.unwrap();
assert_eq!(path, [0, 1, 0, 0]);
let path = tree
.find_node_index_where(&"N", &60, &is_descendent_of, &|_| true)
.unwrap()
.unwrap();
assert_eq!(path, [0, 1, 0, 0, 0]);
}
#[test]
fn find_node_index_with_predicate_works() {
let is_descendent_of = |parent: &char, child: &char| match *parent {
'A' => Ok(['B', 'C', 'D', 'E', 'F'].contains(child)),
'B' => Ok(['C', 'D'].contains(child)),
'C' => Ok(['D'].contains(child)),
'E' => Ok(['F'].contains(child)),
'D' | 'F' => Ok(false),
_ => Err(TestError),
};
let mut tree: ForkTree<char, u8, bool> = ForkTree::new();
tree.import('A', 1, true, &is_descendent_of).unwrap();
tree.import('B', 2, false, &is_descendent_of).unwrap();
tree.import('C', 3, true, &is_descendent_of).unwrap();
tree.import('D', 4, false, &is_descendent_of).unwrap();
tree.import('E', 2, true, &is_descendent_of).unwrap();
tree.import('F', 3, false, &is_descendent_of).unwrap();
let path = tree
.find_node_index_where(&'D', &4, &is_descendent_of, &|&value| !value)
.unwrap()
.unwrap();
assert_eq!(path, [0, 0]);
let path = tree
.find_node_index_where(&'D', &4, &is_descendent_of, &|&value| value)
.unwrap()
.unwrap();
assert_eq!(path, [0, 0, 0]);
let path = tree
.find_node_index_where(&'F', &3, &is_descendent_of, &|&value| !value)
.unwrap();
assert_eq!(path, None);
let path = tree
.find_node_index_where(&'F', &3, &is_descendent_of, &|&value| value)
.unwrap()
.unwrap();
assert_eq!(path, [0, 1]);
}
#[test]
fn find_node_works() {
let (tree, is_descendent_of) = test_fork_tree();
let node = tree.find_node_where(&"B", &20, &is_descendent_of, &|_| true).unwrap().unwrap();
assert_eq!((node.hash, node.number), ("A", 10));
let node = tree.find_node_where(&"D", &40, &is_descendent_of, &|_| true).unwrap().unwrap();
assert_eq!((node.hash, node.number), ("C", 30));
let node = tree.find_node_where(&"O", &50, &is_descendent_of, &|_| true).unwrap().unwrap();
assert_eq!((node.hash, node.number), ("L", 40));
let node = tree.find_node_where(&"N", &60, &is_descendent_of, &|_| true).unwrap().unwrap();
assert_eq!((node.hash, node.number), ("M", 50));
}
#[test]
fn post_order_traversal_requirement() {
let (mut tree, is_descendent_of) = test_fork_tree();
let is_descendent_of_for_post_order = |parent: &&str, child: &&str| match *parent {
"A" => Err(TestError),
"K" if *child == "Z" => Ok(true),
_ => is_descendent_of(parent, child),
};
let path = tree
.find_node_index_where(&"N", &60, &is_descendent_of_for_post_order, &|_| true)
.unwrap()
.unwrap();
assert_eq!(path, [0, 1, 0, 0, 0]);
let res = tree.import(&"Z", 100, 10, &is_descendent_of_for_post_order);
assert_eq!(res, Ok(false));
assert_eq!(
tree.iter().map(|node| *node.0).collect::<Vec<_>>(),
vec!["A", "B", "C", "D", "E", "F", "H", "L", "M", "O", "I", "G", "J", "K", "Z"],
);
}
}