Blocktree/crates/btlib/src/block_path.rs

pub use private::{BlockPath, BlockPathError};

mod private {
    use crate::{crypto::Hash, Principal};
    use serde::{Deserialize, Serialize};
    use std::fmt::Display;

    /// An identifier for a block in a tree.
    #[derive(Debug, PartialEq, Eq, Serialize, Deserialize, Clone, Default)]
    pub struct BlockPath {
        root: Principal,
        components: Vec<String>,
    }

    impl BlockPath {
        /// The character that is used to separate path components.
        const SEP: char = '/';
        /// The limit, in bytes, of a path's length.
        const BYTE_LIMIT: usize = 4096;

        pub fn new(root: Principal, components: Vec<String>) -> BlockPath {
            BlockPath { root, components }
        }

        /// Returns a result which, when successful, contains the index after the last character in
        /// the current path component.
        fn component_end<I: Iterator<Item = (usize, char)>>(
            start: usize,
            first: char,
            pairs: &mut I,
        ) -> std::result::Result<usize, BlockPathError> {
            if first == BlockPath::SEP {
                return Err(BlockPathError::EmptyComponent);
            }
            let end;
            let mut last = start;
            loop {
                match pairs.next() {
                    Some((index, BlockPath::SEP)) => {
                        end = index;
                        break;
                    }
                    Some((index, _)) => last = index,
                    None => {
                        end = last + 1;
                        break;
                    }
                }
            }
            if end == start {
                Err(BlockPathError::EmptyComponent)
            } else {
                Ok(end)
            }
        }

        /// Asserts that the number of bytes in the given string is no more than `Path::BYTE_LIMIT`.
        fn assert_not_too_long(string: &str) -> std::result::Result<(), BlockPathError> {
            let len = string.len();
            if len > BlockPath::BYTE_LIMIT {
                return Err(BlockPathError::PathTooLong(len));
            }
            Ok(())
        }

        /// Returns true if `other` is a subpath of this `Path`.
        pub fn contains(&self, other: &BlockPath) -> bool {
            if self.root != other.root {
                return false;
            };
            // This path must be no longer than the other path.
            if self.components.len() > other.components.len() {
                return false;
            }
            // Skip the component containing the owner.
            let self_iter = self.components.iter().skip(1);
            let other_iter = other.components.iter().skip(1);
            for pair in self_iter.zip(other_iter) {
                if pair.0 != pair.1 {
                    return false;
                }
            }
            true
        }

        pub fn root(&self) -> &Principal {
            &self.root
        }

        pub fn mut_root(&mut self) -> &mut Principal {
            &mut self.root
        }

        pub fn components(&self) -> impl Iterator<Item = &str> {
            self.components.iter().map(|e| e.as_str())
        }

        pub fn mut_components(&mut self) -> impl Iterator<Item = &mut String> {
            self.components.iter_mut()
        }

        pub fn push_component(&mut self, component: String) {
            self.components.push(component)
        }

        pub fn pop_component(&mut self) -> Option<String> {
            self.components.pop()
        }
    }

    impl<'s> TryFrom<&'s str> for BlockPath {
        type Error = BlockPathError;

        fn try_from(string: &'s str) -> std::result::Result<BlockPath, BlockPathError> {
            BlockPath::assert_not_too_long(string)?;
            let mut pairs = string.char_indices();
            let mut components = Vec::new();
            let mut last_end = 0;
            while let Some((start, c)) = pairs.next() {
                let end = BlockPath::component_end(start, c, &mut pairs)?;
                last_end = end;
                let slice = &string[start..end];
                components.push(slice.to_string());
            }
            // An empty component is added to the end to indicate if there was a trailing slash.
            if string.len() - 1 == last_end {
                components.push("".to_string());
            }
            let leading = components
                .get(0)
                .ok_or(BlockPathError::InvalidLeadingComponent)?;
            let hash = Hash::try_from(leading.as_str())
                .map_err(|_| BlockPathError::InvalidLeadingComponent)?;
            Ok(BlockPath {
                root: Principal(hash),
                components,
            })
        }
    }

    impl Display for BlockPath {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            if self.components.is_empty() {
                return write!(f, "");
            };
            let mut iter = self.components.iter();
            let first = iter.next().unwrap();
            let mut output = write!(f, "{}", first);
            for component in iter {
                output = write!(f, "{}{}", BlockPath::SEP, component)
            }
            output
        }
    }

    /// Errors which can occur when converting a string to a `Path`.
    #[derive(Debug, PartialEq, Eq)]
    pub enum BlockPathError {
        /// Occurs when the number of bytes in a string is greater than `Path::BYTE_LIMIT`.
        PathTooLong(usize),
        /// Indicates that a path string was empty.
        Empty,
        /// Occurs when a component in a path string was empty.
        EmptyComponent,
        /// Occurs when the leading component of a path is not in the correct format.
        InvalidLeadingComponent,
    }

    impl Display for BlockPathError {
        fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            match self {
                BlockPathError::PathTooLong(length) => formatter.write_fmt(format_args!(
                    "path contained {} bytes, which is over the {} byte limit",
                    length,
                    BlockPath::BYTE_LIMIT
                )),
                BlockPathError::Empty => formatter.write_str("path was empty"),
                BlockPathError::EmptyComponent => {
                    formatter.write_str("component of path was empty")
                }
                BlockPathError::InvalidLeadingComponent => {
                    formatter.write_str("invalid leading path component")
                }
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::{
        crypto::Hash,
        test_helpers::{make_path, make_principal, PRINCIPAL2},
        Principal,
    };

    use super::*;

    fn path_from_str_test_case(
        expected: std::result::Result<BlockPath, BlockPathError>,
        input: &str,
    ) -> std::result::Result<(), BlockPathError> {
        let result = BlockPath::try_from(input);
        assert_eq!(expected, result);
        Ok(())
    }

    #[test]
    fn path_from_str_multiple_components_ok() -> std::result::Result<(), BlockPathError> {
        let expected = make_path(vec!["red", "green", "blue"]);
        let input = format!("{}/red/green/blue", expected.root());
        path_from_str_test_case(Ok(expected), input.as_str())?;
        Ok(())
    }

    #[test]
    fn path_from_str_one_component_ok() -> std::result::Result<(), BlockPathError> {
        let expected = make_path(vec![]);
        let input = expected.root().to_string();
        path_from_str_test_case(Ok(expected), input.as_str())?;
        Ok(())
    }

    #[test]
    fn path_from_str_trailing_slash_ok() -> std::result::Result<(), BlockPathError> {
        // Notice the empty component at the end of this path due to the trailing slash.
        let expected = make_path(vec!["orange", "banana", "shotgun", ""]);
        let input = format!("{}/orange/banana/shotgun/", expected.root());
        path_from_str_test_case(Ok(expected), input.as_str())?;
        Ok(())
    }

    #[test]
    fn path_from_str_path_too_long_fail() -> std::result::Result<(), BlockPathError> {
        let principal = make_principal();
        let input = format!("{}/{}", principal.0, "*".repeat(4097));
        let expected = Err(BlockPathError::PathTooLong(input.len()));
        path_from_str_test_case(expected, input.as_str())?;
        Ok(())
    }

    #[test]
    fn path_from_str_multiple_slashes_fail() -> std::result::Result<(), BlockPathError> {
        let expected = Err(BlockPathError::EmptyComponent);
        let input = format!("{}//orange", make_principal().0);
        path_from_str_test_case(expected, input.as_str())?;
        Ok(())
    }

    #[test]
    fn path_from_str_leading_slash_fail() -> std::result::Result<(), BlockPathError> {
        let expected = Err(BlockPathError::EmptyComponent);
        let input = format!("/{}/orange/banana/shotgun", make_principal().0);
        path_from_str_test_case(expected, input.as_str())?;
        Ok(())
    }

    #[test]
    fn path_round_trip() -> std::result::Result<(), BlockPathError> {
        let expected = make_path(vec!["interstitial", "inter-related", "intersections"]);
        let actual = BlockPath::try_from(expected.to_string().as_str())?;
        assert_eq!(expected, actual);
        Ok(())
    }

    #[test]
    fn path_contains_true() {
        let larger = make_path(vec!["apps"]);
        let smaller = make_path(vec!["apps", "bohdi"]);
        assert!(larger.contains(&smaller));
    }

    #[test]
    fn path_contains_true_only_owner() {
        let larger = make_path(vec![]);
        let smaller = make_path(vec![]);
        assert!(larger.contains(&smaller));
    }

    #[test]
    fn path_contains_false_self_is_longer() {
        let first = make_path(vec!["apps", "bohdi"]);
        let second = make_path(vec!["apps"]);
        assert!(!first.contains(&second));
    }

    #[test]
    fn path_contains_false_same_owners() {
        let first = make_path(vec!["apps"]);
        let second = make_path(vec!["nodes"]);
        assert!(!first.contains(&second));
    }

    #[test]
    fn path_contains_false_different_owners() {
        let first = make_path(vec!["apps"]);
        let mut second = make_path(vec!["apps"]);
        *second.mut_root() = Principal(Hash::Sha2_256(PRINCIPAL2));
        assert!(!first.contains(&second));
    }
}