use crate::hash::Hash;
use crate::{Error, Result};
use sha2::{Digest as _, Sha256};
pub const MAX_LIST_ITEMS: u64 = 1 << 40;
const FILE_FORK: u8 = 0x01;
const FOLDER_FORK: u8 = 0x03;
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum ListKind {
File,
Folder,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct Node {
pub hash: Hash,
pub size: u64,
}
pub const EMPTY_LIST: Node = Node {
hash: Hash::ZERO,
size: 0,
};
#[derive(Clone, Copy, Debug)]
pub struct Leaf<'a> {
pub node: Node,
pub name: &'a [u8],
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Carried {
pub node: Node,
pub first_name: Vec<u8>,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct Shown {
pub top: Node,
pub offset: u64,
}
fn invalid(detail: &str) -> Error {
Error::InvalidData {
detail: detail.to_owned(),
}
}
fn split(width: u64) -> u64 {
debug_assert!(width >= 2);
1 << (63 - (width - 1).leading_zeros())
}
fn fork(
kind: ListKind,
left: Node,
left_items: u64,
right: Node,
right_items: u64,
right_first_name: &[u8],
) -> Result<Node> {
let size = left
.size
.checked_add(right.size)
.ok_or(Error::SizeOverflow { field: "list size" })?;
let mut hasher = Sha256::new();
hasher.update([match kind {
ListKind::File => FILE_FORK,
ListKind::Folder => FOLDER_FORK,
}]);
hasher.update(left.hash.as_bytes());
hasher.update(left.size.to_be_bytes());
hasher.update(left_items.to_be_bytes());
hasher.update(right.hash.as_bytes());
hasher.update(right.size.to_be_bytes());
hasher.update(right_items.to_be_bytes());
if kind == ListKind::Folder {
hasher.update(right_first_name);
}
Ok(Node {
hash: Hash::from_bytes(hasher.finalize().into()),
size,
})
}
fn check_list(kind: ListKind, leaves: &[Leaf<'_>]) -> Result<()> {
if leaves.len() as u64 > MAX_LIST_ITEMS {
return Err(invalid("a list holds more items than the format allows"));
}
if kind == ListKind::Folder && !names_ascend(leaves) {
return Err(invalid(
"a folder's entries are not sorted by name, or a name is there twice",
));
}
Ok(())
}
fn names_ascend(leaves: &[Leaf<'_>]) -> bool {
leaves.windows(2).all(|pair| pair[0].name < pair[1].name)
}
pub fn top_of(kind: ListKind, leaves: &[Leaf<'_>]) -> Result<Node> {
check_list(kind, leaves)?;
top_unchecked(kind, leaves)
}
fn top_unchecked(kind: ListKind, leaves: &[Leaf<'_>]) -> Result<Node> {
let mut stack: Vec<(Node, usize, usize)> = Vec::new();
for (index, leaf) in leaves.iter().enumerate() {
let mut right = (leaf.node, index, 1_usize);
while let Some(&(left, left_first, left_width)) = stack.last() {
if left_width != right.2 {
break;
}
stack.pop();
let name = leaves[right.1].name;
right = (
fork(kind, left, left_width as u64, right.0, right.2 as u64, name)?,
left_first,
left_width * 2,
);
}
stack.push(right);
}
let Some(mut top) = stack.pop() else {
return Ok(EMPTY_LIST);
};
while let Some((left, left_first, left_width)) = stack.pop() {
let name = leaves[top.1].name;
top = (
fork(kind, left, left_width as u64, top.0, top.2 as u64, name)?,
left_first,
left_width + top.2,
);
}
Ok(top.0)
}
#[derive(Clone, Debug)]
pub struct ListTree {
kind: ListKind,
leaves: Vec<Node>,
names: Vec<Box<[u8]>>,
levels: Vec<Vec<Node>>,
}
impl ListTree {
pub fn build(kind: ListKind, leaves: &[Leaf<'_>]) -> Result<Self> {
check_list(kind, leaves)?;
Self::build_unchecked(kind, leaves)
}
fn build_unchecked(kind: ListKind, leaves: &[Leaf<'_>]) -> Result<Self> {
let mut levels: Vec<Vec<Node>> = Vec::new();
let mut below_width = 1_usize;
loop {
let below_len = levels.last().map_or(leaves.len(), Vec::len);
if below_len < 2 {
break;
}
let mut level = Vec::with_capacity(below_len / 2);
for pair in 0..below_len / 2 {
let (left, right) = match levels.last() {
None => (leaves[pair * 2].node, leaves[pair * 2 + 1].node),
Some(below) => (below[pair * 2], below[pair * 2 + 1]),
};
let name = leaves[(pair * 2 + 1) * below_width].name;
let items = below_width as u64;
level.push(fork(kind, left, items, right, items, name)?);
}
levels.push(level);
below_width *= 2;
}
Ok(Self {
kind,
leaves: leaves.iter().map(|leaf| leaf.node).collect(),
names: match kind {
ListKind::File => Vec::new(),
ListKind::Folder => leaves.iter().map(|leaf| leaf.name.into()).collect(),
},
levels,
})
}
fn name(&self, index: usize) -> &[u8] {
match self.kind {
ListKind::File => &[],
ListKind::Folder => &self.names[index],
}
}
pub fn count(&self) -> u64 {
self.leaves.len() as u64
}
pub fn top(&self) -> Result<Node> {
if self.leaves.is_empty() {
return Ok(EMPTY_LIST);
}
self.node(0, self.leaves.len())
}
fn node(&self, offset: usize, width: usize) -> Result<Node> {
if width.is_power_of_two() {
debug_assert_eq!(offset % width, 0);
let level = width.trailing_zeros() as usize;
return Ok(if level == 0 {
self.leaves[offset]
} else {
self.levels[level - 1][offset >> level]
});
}
let left_width = split(width as u64) as usize;
let left = self.node(offset, left_width)?;
let right = self.node(offset + left_width, width - left_width)?;
fork(
self.kind,
left,
left_width as u64,
right,
(width - left_width) as u64,
self.name(offset + left_width),
)
}
pub fn open(&self, start: u64, end: u64) -> Result<Vec<Carried>> {
if start >= end || end > self.count() {
return Err(invalid("the items to open are outside the list"));
}
let mut carried = Vec::new();
self.collect(
0,
self.leaves.len(),
start as usize,
end as usize,
&mut carried,
)?;
Ok(carried)
}
fn collect(
&self,
offset: usize,
width: usize,
start: usize,
end: usize,
carried: &mut Vec<Carried>,
) -> Result<()> {
let after = offset + width;
if after <= start || end <= offset {
let first_name = if offset == 0 {
Vec::new()
} else {
self.name(offset).to_vec()
};
carried.push(Carried {
node: self.node(offset, width)?,
first_name,
});
return Ok(());
}
if start <= offset && after <= end {
return Ok(());
}
let left_width = split(width as u64) as usize;
self.collect(offset, left_width, start, end, carried)?;
self.collect(offset + left_width, width - left_width, start, end, carried)
}
}
pub fn check_branch(
kind: ListKind,
count: u64,
start: u64,
opened: &[Leaf<'_>],
carried: &[Carried],
) -> Result<Shown> {
Walk::run(kind, count, start, opened, carried, None)
}
pub fn check_lookup(
count: u64,
index: u64,
entry: Leaf<'_>,
name: &[u8],
carried: &[Carried],
) -> Result<(Shown, bool)> {
let opened = [entry];
let shown = Walk::run(ListKind::Folder, count, index, &opened, carried, Some(name))?;
Ok((shown, entry.name == name))
}
struct Walk<'a> {
kind: ListKind,
start: u64,
end: u64,
opened: &'a [Leaf<'a>],
carried: std::slice::Iter<'a, Carried>,
before: u64,
lookup: Option<&'a [u8]>,
}
impl<'a> Walk<'a> {
fn run(
kind: ListKind,
count: u64,
start: u64,
opened: &'a [Leaf<'a>],
carried: &'a [Carried],
lookup: Option<&'a [u8]>,
) -> Result<Shown> {
if count > MAX_LIST_ITEMS {
return Err(invalid("a list holds more items than the format allows"));
}
let length = opened.len() as u64;
let end = start
.checked_add(length)
.filter(|end| length > 0 && *end <= count)
.ok_or_else(|| invalid("the opened items are outside the list"))?;
match kind {
ListKind::File => {
if carried.iter().any(|node| !node.first_name.is_empty()) {
return Err(invalid("a node of a file's tree carries a name"));
}
}
ListKind::Folder => {
if !names_ascend(opened) {
return Err(invalid(
"opened entries are not sorted by name, or a name is there twice",
));
}
}
}
let mut walk = Self {
kind,
start,
end,
opened,
carried: carried.iter(),
before: 0,
lookup,
};
let (top, _) = walk.node(0, count)?;
if walk.carried.next().is_some() {
return Err(invalid("a branch carries more nodes than it needs"));
}
Ok(Shown {
top,
offset: walk.before,
})
}
fn item(&self, index: u64) -> &Leaf<'a> {
&self.opened[(index - self.start) as usize]
}
fn node(&mut self, offset: u64, width: u64) -> Result<(Node, &'a [u8])> {
let after = offset + width;
if after <= self.start || self.end <= offset {
let carried = self
.carried
.next()
.ok_or_else(|| invalid("a branch carries fewer nodes than it needs"))?;
if self.kind == ListKind::Folder && (offset == 0) != carried.first_name.is_empty() {
return Err(invalid(if offset == 0 {
"the carried node that begins a folder's list has a name"
} else {
"a carried node of a folder's tree has no name"
}));
}
if after <= self.start {
self.before = self
.before
.checked_add(carried.node.size)
.ok_or(Error::SizeOverflow { field: "list size" })?;
}
return Ok((carried.node, carried.first_name.as_slice()));
}
if width == 1 {
let leaf = self.item(offset);
return Ok((leaf.node, leaf.name));
}
let middle = offset + split(width);
let (left, first_name) = self.node(offset, middle - offset)?;
let (right, fork_name) = self.node(middle, after - middle)?;
if self.kind == ListKind::Folder {
self.check_names(offset, middle, after, fork_name)?;
}
let node = fork(
self.kind,
left,
middle - offset,
right,
after - middle,
fork_name,
)?;
Ok((node, first_name))
}
fn check_names(&self, offset: u64, middle: u64, after: u64, fork_name: &[u8]) -> Result<()> {
let left_end = self.end.min(middle);
if self.start.max(offset) < left_end && self.item(left_end - 1).name >= fork_name {
return Err(invalid(
"an entry is left of a fork whose name it does not sort before",
));
}
let right_start = self.start.max(middle);
if right_start > middle
&& right_start < self.end.min(after)
&& self.item(right_start).name <= fork_name
{
return Err(invalid(
"an entry is right of a fork whose name it does not sort after",
));
}
if let Some(name) = self.lookup {
let name_goes_left = name < fork_name;
let entry_is_left = self.start < middle;
if name_goes_left != entry_is_left {
return Err(invalid("the opened entry is not where the name would be"));
}
}
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
type Owned = Vec<(Node, Vec<u8>)>;
fn leaf_node(seed: usize) -> Node {
Node {
hash: Hash::of(&(seed as u64).to_be_bytes()),
size: (seed as u64 % 7) + 1,
}
}
fn file_list(count: usize) -> Owned {
(0..count)
.map(|index| (leaf_node(index), Vec::new()))
.collect()
}
fn folder_list(names: &[&str]) -> Owned {
names
.iter()
.enumerate()
.map(|(index, name)| (leaf_node(index), name.as_bytes().to_vec()))
.collect()
}
fn sorted_folder(count: usize) -> Owned {
(0..count)
.map(|index| (leaf_node(index), format!("name-{index:04}").into_bytes()))
.collect()
}
fn leaves(owned: &Owned) -> Vec<Leaf<'_>> {
owned
.iter()
.map(|(node, name)| Leaf { node: *node, name })
.collect()
}
fn by_the_rule(kind: ListKind, leaves: &[Leaf<'_>], offset: usize, width: usize) -> Node {
if width == 1 {
return leaves[offset].node;
}
let mut left_width = 1;
while left_width * 2 < width {
left_width *= 2;
}
let left = by_the_rule(kind, leaves, offset, left_width);
let right = by_the_rule(kind, leaves, offset + left_width, width - left_width);
fork(
kind,
left,
left_width as u64,
right,
(width - left_width) as u64,
leaves[offset + left_width].name,
)
.unwrap()
}
struct Numbers(u64);
impl Numbers {
fn next(&mut self, below: usize) -> usize {
self.0 ^= self.0 << 13;
self.0 ^= self.0 >> 7;
self.0 ^= self.0 << 17;
(self.0 % below as u64) as usize
}
}
#[test]
fn a_list_is_halved_at_the_largest_power_of_two_below_its_length() {
for (width, left) in [(2, 1), (3, 2), (4, 2), (5, 4), (6, 4), (8, 4), (9, 8)] {
assert_eq!(split(width), left, "a list of {width}");
}
assert_eq!(split(MAX_LIST_ITEMS), MAX_LIST_ITEMS / 2);
assert_eq!(split(MAX_LIST_ITEMS + 1), MAX_LIST_ITEMS);
}
#[test]
fn a_fork_hashes_exactly_the_bytes_the_format_names() {
let left = leaf_node(1);
let right = leaf_node(2);
let mut bytes = vec![0x01];
bytes.extend_from_slice(left.hash.as_bytes());
bytes.extend_from_slice(&left.size.to_be_bytes());
bytes.extend_from_slice(&4_u64.to_be_bytes());
bytes.extend_from_slice(right.hash.as_bytes());
bytes.extend_from_slice(&right.size.to_be_bytes());
bytes.extend_from_slice(&3_u64.to_be_bytes());
assert_eq!(bytes.len(), 97);
let file = fork(ListKind::File, left, 4, right, 3, b"ignored").unwrap();
assert_eq!(file.hash, Hash::of(&bytes));
assert_eq!(file.size, left.size + right.size);
let other = fork(ListKind::File, left, 4, right, 2, b"ignored").unwrap();
assert_ne!(other.hash, file.hash);
bytes[0] = 0x03;
bytes.extend_from_slice(b"right-half");
let folder = fork(ListKind::Folder, left, 4, right, 3, b"right-half").unwrap();
assert_eq!(folder.hash, Hash::of(&bytes));
assert_ne!(folder.hash, file.hash);
}
#[test]
fn the_top_of_a_list_follows_the_rule_at_every_length() {
assert_eq!(top_of(ListKind::File, &[]).unwrap(), EMPTY_LIST);
assert_eq!(top_of(ListKind::Folder, &[]).unwrap(), EMPTY_LIST);
for count in 1..=70 {
for (kind, owned) in [
(ListKind::File, file_list(count)),
(ListKind::Folder, sorted_folder(count)),
] {
let leaves = leaves(&owned);
let expected = by_the_rule(kind, &leaves, 0, count);
assert_eq!(
top_of(kind, &leaves).unwrap(),
expected,
"{kind:?} of {count}"
);
let tree = ListTree::build(kind, &leaves).unwrap();
assert_eq!(tree.top().unwrap(), expected, "kept {kind:?} of {count}");
}
}
}
#[test]
fn a_list_of_one_is_its_leaf_and_a_longer_list_is_never_one_of_its_leaves() {
let owned = file_list(3);
let leaves = leaves(&owned);
assert_eq!(
top_of(ListKind::File, &leaves[..1]).unwrap(),
leaves[0].node
);
let top = top_of(ListKind::File, &leaves).unwrap();
assert!(leaves.iter().all(|leaf| leaf.node.hash != top.hash));
assert_eq!(
top.size,
leaves.iter().map(|leaf| leaf.node.size).sum::<u64>()
);
}
#[test]
fn the_same_items_in_another_order_or_number_give_another_top() {
let owned = file_list(6);
let mut leaves = leaves(&owned);
let top = top_of(ListKind::File, &leaves).unwrap();
let mut repeated = leaves.clone();
repeated.push(leaves[5]);
assert_ne!(top_of(ListKind::File, &repeated).unwrap().hash, top.hash);
assert_ne!(top_of(ListKind::File, &leaves[..5]).unwrap().hash, top.hash);
leaves.swap(1, 2);
assert_ne!(top_of(ListKind::File, &leaves).unwrap().hash, top.hash);
}
#[test]
fn a_folder_list_out_of_order_or_with_a_name_twice_has_no_hash() {
for names in [&["b", "a"][..], &["a", "a"], &["a", "c", "b"]] {
let owned = folder_list(names);
let leaves = leaves(&owned);
assert!(top_of(ListKind::Folder, &leaves).is_err(), "{names:?}");
assert!(
ListTree::build(ListKind::Folder, &leaves).is_err(),
"{names:?}"
);
}
}
#[test]
fn every_branch_of_every_list_opens_and_rebuilds_to_the_top() {
for count in 1..=33_usize {
for (kind, owned) in [
(ListKind::File, file_list(count)),
(ListKind::Folder, sorted_folder(count)),
] {
let leaves = leaves(&owned);
let tree = ListTree::build(kind, &leaves).unwrap();
let top = tree.top().unwrap();
for start in 0..count {
for end in start + 1..=count {
let carried = tree.open(start as u64, end as u64).unwrap();
let shown = check_branch(
kind,
count as u64,
start as u64,
&leaves[start..end],
&carried,
)
.unwrap_or_else(|error| {
panic!("{kind:?} of {count}, {start}..{end}: {error}")
});
assert_eq!(shown.top, top, "{kind:?} of {count}, {start}..{end}");
let before: u64 = leaves[..start].iter().map(|leaf| leaf.node.size).sum();
assert_eq!(shown.offset, before, "{kind:?} of {count}, {start}..{end}");
assert!(carried.len() <= 2 * 6, "{} nodes", carried.len());
if start == 0 && end == count {
assert!(carried.is_empty());
}
}
}
}
}
}
#[test]
fn a_branch_that_is_changed_does_not_rebuild_to_the_top() {
let owned = file_list(11);
let leaves = leaves(&owned);
let tree = ListTree::build(ListKind::File, &leaves).unwrap();
let top = tree.top().unwrap();
let carried = tree.open(4, 6).unwrap();
let rebuilt = |start: u64, opened: &[Leaf<'_>], carried: &[Carried]| {
check_branch(ListKind::File, 11, start, opened, carried).map(|shown| shown.top)
};
assert_eq!(rebuilt(4, &leaves[4..6], &carried).unwrap(), top);
assert_ne!(
rebuilt(4, &[leaves[4], leaves[7]], &carried).ok(),
Some(top)
);
assert_ne!(rebuilt(5, &leaves[4..6], &carried).ok(), Some(top));
let mut resized = leaves[4];
resized.node.size += 1;
assert_ne!(rebuilt(4, &[resized, leaves[5]], &carried).ok(), Some(top));
let mut wrong_size = carried.clone();
wrong_size[0].node.size += 1;
assert_ne!(rebuilt(4, &leaves[4..6], &wrong_size).ok(), Some(top));
let mut swapped = carried.clone();
swapped.swap(0, 1);
assert_ne!(rebuilt(4, &leaves[4..6], &swapped).ok(), Some(top));
assert!(rebuilt(4, &leaves[4..6], &carried[1..]).is_err());
let mut extra = carried.clone();
extra.push(carried[0].clone());
assert!(rebuilt(4, &leaves[4..6], &extra).is_err());
for count in [10, 12] {
let result = check_branch(ListKind::File, count, 4, &leaves[4..6], &carried);
assert_ne!(
result.map(|shown| shown.top).ok(),
Some(top),
"as {count} items"
);
}
assert!(rebuilt(10, &leaves[4..6], &carried).is_err());
assert!(rebuilt(4, &[], &carried).is_err());
assert!(rebuilt(u64::MAX, &leaves[4..6], &carried).is_err());
}
#[test]
fn no_place_exists_beyond_the_count() {
for count in [1_usize, 3, 5, 7] {
let owned = file_list(count);
let leaves = leaves(&owned);
let tree = ListTree::build(ListKind::File, &leaves).unwrap();
let carried = tree.open(count as u64 - 1, count as u64).unwrap();
let last = &leaves[count - 1..];
assert!(
check_branch(ListKind::File, count as u64, count as u64, last, &carried).is_err()
);
assert!(tree.open(count as u64, count as u64 + 1).is_err());
}
}
#[test]
fn sizes_that_do_not_fit_are_an_error() {
let mut owned = file_list(2);
owned[0].0.size = u64::MAX;
let leaves = leaves(&owned);
assert!(top_of(ListKind::File, &leaves).is_err());
assert!(ListTree::build(ListKind::File, &leaves).is_err());
}
#[test]
fn a_name_in_a_sorted_folder_is_found_at_its_one_place_or_shown_missing() {
for count in 1..=20_usize {
let owned = sorted_folder(count);
let leaves = leaves(&owned);
let tree = ListTree::build(ListKind::Folder, &leaves).unwrap();
let top = tree.top().unwrap();
let verdict = |name: &[u8], index: usize| {
let carried = tree.open(index as u64, index as u64 + 1).unwrap();
check_lookup(count as u64, index as u64, leaves[index], name, &carried)
.ok()
.filter(|(shown, _)| shown.top == top)
.map(|(_, present)| present)
};
for (place, leaf) in leaves.iter().enumerate() {
for index in 0..count {
let expected = (index == place).then_some(true);
assert_eq!(
verdict(leaf.name, index),
expected,
"{count}: {place} at {index}"
);
}
let mut later = leaf.name.to_vec();
later.push(b'!');
for index in 0..count {
let expected = (index == place).then_some(false);
assert_eq!(
verdict(&later, index),
expected,
"{count}: after {place} at {index}"
);
}
}
for index in 0..count {
let expected = (index == 0).then_some(false);
assert_eq!(
verdict(b"a", index),
expected,
"{count}: before all at {index}"
);
}
}
}
#[test]
fn a_folder_built_out_of_order_cannot_show_one_name_at_two_places() {
let mut numbers = Numbers(0x5c10_71c5_eed5_eed5);
let alphabet = ["a", "b", "c", "d", "e", "f"];
for _ in 0..400 {
let count = 2 + numbers.next(16);
let names: Vec<&str> = (0..count)
.map(|_| alphabet[numbers.next(alphabet.len())])
.collect();
let owned = folder_list(&names);
let leaves = leaves(&owned);
let tree = ListTree::build_unchecked(ListKind::Folder, &leaves).unwrap();
let top = tree.top().unwrap();
for name in alphabet {
let mut answers = Vec::new();
for (index, entry) in leaves.iter().copied().enumerate() {
let carried = tree.open(index as u64, index as u64 + 1).unwrap();
if let Ok((shown, present)) =
check_lookup(count as u64, index as u64, entry, name.as_bytes(), &carried)
{
if shown.top == top {
answers.push((index, present));
}
}
if entry.name == name.as_bytes() {
let plain = check_branch(
ListKind::Folder,
count as u64,
index as u64,
&[entry],
&carried,
);
let found_here = answers.last() == Some(&(index, true));
assert_eq!(
plain.is_ok_and(|shown| shown.top == top),
found_here,
"{names:?}: {name} at {index}"
);
}
}
assert!(
answers.len() <= 1,
"{names:?}: {name} answered at {answers:?}"
);
}
}
}
#[test]
fn branches_of_a_folder_built_out_of_order_open_only_where_a_search_agrees() {
let owned = folder_list(&["a", "c", "b", "d"]);
let leaves = leaves(&owned);
let tree = ListTree::build_unchecked(ListKind::Folder, &leaves).unwrap();
let top = tree.top().unwrap();
let opens = |start: usize, end: usize| {
let carried = tree.open(start as u64, end as u64).unwrap();
check_branch(
ListKind::Folder,
4,
start as u64,
&leaves[start..end],
&carried,
)
.is_ok_and(|shown| shown.top == top)
};
assert!(opens(0, 1), "a");
assert!(!opens(1, 2), "c, alone");
assert!(!opens(0, 2), "a and c");
assert!(!opens(1, 3), "c and b");
assert!(opens(2, 3), "b");
assert!(opens(2, 4), "b and d");
assert!(!opens(0, 4), "the whole list");
let carried = tree.open(2, 3).unwrap();
let (shown, present) = check_lookup(4, 2, leaves[2], b"c", &carried).unwrap();
assert_eq!((shown.top, present), (top, false));
}
#[test]
fn a_carried_name_is_held_to_the_fork_it_enters() {
let owned = sorted_folder(8);
let leaves = leaves(&owned);
let tree = ListTree::build(ListKind::Folder, &leaves).unwrap();
let top = tree.top().unwrap();
let mut carried = tree.open(1, 2).unwrap();
let honest = check_branch(ListKind::Folder, 8, 1, &leaves[1..2], &carried).unwrap();
assert_eq!(honest.top, top);
let last = carried.len() - 1;
carried[last].first_name = b"name-9999".to_vec();
let forged = check_branch(ListKind::Folder, 8, 1, &leaves[1..2], &carried);
assert_ne!(forged.map(|shown| shown.top).ok(), Some(top));
}
#[test]
fn a_files_tree_carries_no_names() {
let owned = file_list(4);
let leaves = leaves(&owned);
let tree = ListTree::build(ListKind::File, &leaves).unwrap();
let mut carried = tree.open(0, 1).unwrap();
carried[0].first_name = b"x".to_vec();
assert!(check_branch(ListKind::File, 4, 0, &leaves[..1], &carried).is_err());
}
#[test]
fn the_carried_node_that_begins_a_folders_list_has_no_name() {
for count in 2..=20_usize {
let owned = sorted_folder(count);
let leaves = leaves(&owned);
let tree = ListTree::build(ListKind::Folder, &leaves).unwrap();
let top = tree.top().unwrap();
for start in 0..count {
for end in start + 1..=count {
let carried = tree.open(start as u64, end as u64).unwrap();
let rebuilds = |carried: &[Carried]| {
check_branch(
ListKind::Folder,
count as u64,
start as u64,
&leaves[start..end],
carried,
)
.is_ok_and(|shown| shown.top == top)
};
assert!(rebuilds(&carried), "{count}: {start}..{end}");
for (index, node) in carried.iter().enumerate() {
let what = format!("{count}: {start}..{end}, carried node {index}");
let begins_the_list = index == 0 && start > 0;
assert_eq!(node.first_name.is_empty(), begins_the_list, "{what}");
let mut renamed = carried.clone();
renamed[index].first_name = b"name-9999".to_vec();
assert!(!rebuilds(&renamed), "{what}, under another name");
let mut nameless = carried.clone();
nameless[index].first_name.clear();
assert_eq!(rebuilds(&nameless), begins_the_list, "{what}, nameless");
}
}
}
}
}
}