use std::collections::btree_map::{self, BTreeMap}; use crate::{errors::DirectoryError, path::PathComponent, proto, B3Digest, Node}; /// A Directory contains nodes, which can be Directory, File or Symlink nodes. /// It attaches names to these nodes, which is the basename in that directory. /// These names: /// - MUST not contain slashes or null bytes /// - MUST not be '.' or '..' /// - MUST be unique across all three lists #[derive(Default, Debug, Clone, PartialEq, Eq)] pub struct Directory { nodes: BTreeMap, } impl Directory { /// Constructs a new, empty Directory. pub fn new() -> Self { Directory { nodes: BTreeMap::new(), } } /// Construct a [Directory] from tuples of name and [Node]. /// /// Inserting multiple elements with the same name will yield an error, as /// well as exceeding the maximum size. pub fn try_from_iter>( iter: T, ) -> Result { let mut nodes = BTreeMap::new(); iter.into_iter().try_fold(0u64, |size, (name, node)| { check_insert_node(size, &mut nodes, name, node) })?; Ok(Self { nodes }) } /// The size of a directory is the number of all regular and symlink elements, /// the number of directory elements, and their size fields. pub fn size(&self) -> u64 { // It's impossible to create a Directory where the size overflows, because we // check before every add() that the size won't overflow. (self.nodes.len() as u64) + self .nodes() .map(|(_name, n)| match n { Node::Directory { size, .. } => 1 + size, Node::File { .. } | Node::Symlink { .. } => 1, }) .sum::() } /// Calculates the digest of a Directory, which is the blake3 hash of a /// Directory protobuf message, serialized in protobuf canonical form. pub fn digest(&self) -> B3Digest { proto::Directory::from(self.clone()).digest() } /// Allows iterating over all nodes (directories, files and symlinks) /// For each, it returns a tuple of its name and node. /// The elements are sorted by their names. pub fn nodes(&self) -> impl Iterator + Send + Sync + '_ { self.nodes.iter() } /// Dissolves a Directory into its individual names and nodes. /// The elements are sorted by their names. pub fn into_nodes(self) -> impl Iterator + Send + Sync { self.nodes.into_iter() } /// Adds the specified [Node] to the [Directory] with a given name. /// /// Inserting a node that already exists with the same name in the directory /// will yield an error, as well as exceeding the maximum size. /// /// In case you want to construct a [Directory] from multiple elements, use /// [from_iter] instead. pub fn add(&mut self, name: PathComponent, node: Node) -> Result<(), DirectoryError> { check_insert_node(self.size(), &mut self.nodes, name, node)?; Ok(()) } } fn checked_sum(iter: impl IntoIterator) -> Option { iter.into_iter().try_fold(0u64, |acc, i| acc.checked_add(i)) } /// Helper function dealing with inserting nodes into the nodes [BTreeMap], /// after ensuring the new size doesn't overlow and the key doesn't exist already. /// /// Returns the new total size, or an error. fn check_insert_node( current_size: u64, nodes: &mut BTreeMap, name: PathComponent, node: Node, ) -> Result { // Check that the even after adding this new directory entry, the size calculation will not // overflow let new_size = checked_sum([ current_size, 1, match node { Node::Directory { size, .. } => size, _ => 0, }, ]) .ok_or(DirectoryError::SizeOverflow)?; match nodes.entry(name) { btree_map::Entry::Vacant(e) => { e.insert(node); } btree_map::Entry::Occupied(occupied) => { return Err(DirectoryError::DuplicateName(occupied.key().to_owned())) } } Ok(new_size) } #[cfg(test)] mod test { use super::{Directory, Node}; use crate::fixtures::DUMMY_DIGEST; use crate::{DirectoryError, PathComponent}; #[test] fn from_iter_single() { Directory::try_from_iter([( PathComponent::try_from("b").unwrap(), Node::Directory { digest: DUMMY_DIGEST.clone(), size: 1, }, )]) .unwrap(); } #[test] fn from_iter_multiple() { let d = Directory::try_from_iter([ ( "b".try_into().unwrap(), Node::Directory { digest: DUMMY_DIGEST.clone(), size: 1, }, ), ( "a".try_into().unwrap(), Node::Directory { digest: DUMMY_DIGEST.clone(), size: 1, }, ), ( "z".try_into().unwrap(), Node::Directory { digest: DUMMY_DIGEST.clone(), size: 1, }, ), ( "f".try_into().unwrap(), Node::File { digest: DUMMY_DIGEST.clone(), size: 1, executable: true, }, ), ( "c".try_into().unwrap(), Node::File { digest: DUMMY_DIGEST.clone(), size: 1, executable: true, }, ), ( "g".try_into().unwrap(), Node::File { digest: DUMMY_DIGEST.clone(), size: 1, executable: true, }, ), ( "t".try_into().unwrap(), Node::Symlink { target: "a".try_into().unwrap(), }, ), ( "o".try_into().unwrap(), Node::Symlink { target: "a".try_into().unwrap(), }, ), ( "e".try_into().unwrap(), Node::Symlink { target: "a".try_into().unwrap(), }, ), ]) .unwrap(); // Convert to proto struct and back to ensure we are not generating any invalid structures crate::Directory::try_from(crate::proto::Directory::from(d)) .expect("directory should be valid"); } #[test] fn add_nodes_to_directory() { let mut d = Directory::new(); d.add( "b".try_into().unwrap(), Node::Directory { digest: DUMMY_DIGEST.clone(), size: 1, }, ) .unwrap(); d.add( "a".try_into().unwrap(), Node::Directory { digest: DUMMY_DIGEST.clone(), size: 1, }, ) .unwrap(); // Convert to proto struct and back to ensure we are not generating any invalid structures crate::Directory::try_from(crate::proto::Directory::from(d)) .expect("directory should be valid"); } #[test] fn validate_overflow() { let mut d = Directory::new(); assert_eq!( d.add( "foo".try_into().unwrap(), Node::Directory { digest: DUMMY_DIGEST.clone(), size: u64::MAX } ), Err(DirectoryError::SizeOverflow) ); } #[test] fn add_duplicate_node_to_directory() { let mut d = Directory::new(); d.add( "a".try_into().unwrap(), Node::Directory { digest: DUMMY_DIGEST.clone(), size: 1, }, ) .unwrap(); assert_eq!( format!( "{}", d.add( "a".try_into().unwrap(), Node::File { digest: DUMMY_DIGEST.clone(), size: 1, executable: true } ) .expect_err("adding duplicate dir entry must fail") ), "\"a\" is a duplicate name" ); } }