willow_data_model/paths/

mod.rs

//! Functionality around Willow [Paths](https://willowprotocol.org/specs/data-model/index.html#Path).
//!
//! The central type of this module is the [`Path`] struct, which represents a single willow Path. [`Paths`](Path) are *immutable*, which means any operation that would traditionally mutate paths (for example, appending a new component) returns a new, independent value instead.
//!
//! The [`Path`] struct is generic over three const generic parameters, corresponding to the Willow parameters which limit the size of paths:
//!
//! - the `MCL` parameter gives the ([**m**ax\_**c**omponent\_**l**ength](https://willowprotocol.org/specs/data-model/index.html#max_component_length)),
//! - the `MCC` parameter gives the ([**m**ax\_**c**omponent\_**c**ount](https://willowprotocol.org/specs/data-model/index.html#max_component_count)), and
//! - the `MPL` parameter gives the ([**m**ax\_**p**ath\_**l**ength](https://willowprotocol.org/specs/data-model/index.html#max_path_length)).
//!
//! All (safely created) [`Paths`](Path)respect those parameters. The functions in this module return [`PathErrors`](PathError) or [`PathFromComponentsErrors`](PathFromComponentsError) when those invariants would be violated.
//!
//! The type-level docs of [`Path`] list all the ways in which you can build up paths dynamically.
//!
//! The [`Path`] struct provides methods for checking various properties of paths: from simple properties ("[how many components does this have](Path::component_count)") to various comparisons ("[is this path a prefix of some other](Path::is_prefix_of)"), the methods should have you covered.
//!
//! Because [path prefixes](https://willowprotocol.org/specs/data-model/index.html#path_prefix) play such a [central role for deletion](https://willowprotocol.org/specs/data-model/index.html#prefix_pruning) in Willow, the functionality around prefixes is optimised. [Creating a prefix](Path::create_prefix) or even iterating over [all prefixes](Path::all_prefixes) performs no memory allocations.
//!
//! The [`Component`] type represents individual path [Components](https://willowprotocol.org/specs/data-model/index.html#Component). This type is a thin wrapper around `[u8]` (enforcing a maximal length of `MCL` bytes); like `[u8]` it must always be used as part of a pointer type — for example, `&Component<MCL>`. Alternatively, the [`OwnedComponent`] type can be used by itself — keeping an [`OwnedComponent`] alive will also keep around the heap allocation for the full [`Path`] from which it was constructed, though. Generally speaking, the more lightweight [`Component`] should be preferred over [`OwnedComponent`] where possible.

#[cfg(feature = "dev")]
use arbitrary::{Arbitrary, Error as ArbitraryError, Unstructured, size_hint::and_all};
use order_theory::{
    GreatestElement, LeastElement, LowerSemilattice, PredecessorExceptForLeast,
    SuccessorExceptForGreatest, TryPredecessor, TrySuccessor, UpperSemilattice,
};

// The `Path` struct is tested in `fuzz/path.rs`, `fuzz/path2.rs`, `fuzz/path3.rs`, `fuzz/path3.rs` by comparing against a non-optimised reference implementation.
// Further, the `successor` and `greater_but_not_prefixed` methods of that reference implementation are tested in `fuzz/path_successor.rs` and friends, and `fuzz/path_successor_of_prefix.rs` and friends.

use core::cmp::Ordering;
use core::fmt::Debug;
use core::hash::Hash;
use core::mem::size_of;
use core::{convert::AsRef, fmt};

use bytes::{BufMut, Bytes, BytesMut};

mod builder;
pub use builder::PathBuilder;

mod representation;
use representation::Representation;

mod component;
pub use component::*;

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
/// An error arising from trying to construct an invalid [`Path`] from valid [`Component`]s.
///
/// #### Examples
///
/// ```
/// use willow_data_model::prelude::*;
/// assert_eq!(
///     Path::<4, 4, 2>::from_component(Component::new(b"oops").unwrap()),
///     Err(PathFromComponentsError::PathTooLong),
/// );
/// assert_eq!(
///     Path::<4, 1, 9>::from_components(&[
///         Component::new(b"").unwrap(),
///         Component::new(b"").unwrap()
///     ]),
///     Err(PathFromComponentsError::TooManyComponents),
/// );
/// ```
pub enum PathFromComponentsError {
    /// The [`Path`]'s total length in bytes would have been greater than the [max\_path\_length](https://willowprotocol.org/specs/data-model/index.html#max_path_length).
    PathTooLong,
    /// The [`Path`] would have had more [`Component`] than the [max\_component\_count](https://willowprotocol.org/specs/data-model/index.html#max_component_count).
    TooManyComponents,
}

impl core::fmt::Display for PathFromComponentsError {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        match self {
            PathFromComponentsError::PathTooLong => {
                write!(
                    f,
                    "Total length of a path in bytes exceeded the maximum path length"
                )
            }
            PathFromComponentsError::TooManyComponents => {
                write!(
                    f,
                    "Number of components of a path exceeded the maximum component count"
                )
            }
        }
    }
}

impl core::error::Error for PathFromComponentsError {}

/// An error arising from trying to construct an invalid [`Path`].
///
/// #### Examples
///
/// ```
/// use willow_data_model::prelude::*;
/// assert_eq!(Path::<4, 4, 2>::from_slice(b"oops"), Err(PathError::PathTooLong));
/// assert_eq!(Path::<2, 2, 9>::from_slices(&[b"", b"", b""]), Err(PathError::TooManyComponents));
/// assert_eq!(Path::<4, 4, 9>::from_slice(b"oopsie"), Err(PathError::ComponentTooLong));
/// ```
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum PathError {
    /// The [`Path`]'s total length in bytes would have been greater than the [max\_path\_length](https://willowprotocol.org/specs/data-model/index.html#max_path_length).
    PathTooLong,
    /// The [`Path`] would have had more [`Component`] than the [max\_component\_count](https://willowprotocol.org/specs/data-model/index.html#max_component_count).
    TooManyComponents,
    /// The [`Path`] would have contained a [`Component`] of length greater than the [max\_component\_length](https://willowprotocol.org/specs/data-model/index.html#max_component_length)
    ComponentTooLong,
}

impl core::fmt::Display for PathError {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        match self {
            PathError::PathTooLong => {
                write!(
                    f,
                    "Total length of a path in bytes exceeded the maximum path length"
                )
            }
            PathError::TooManyComponents => {
                write!(
                    f,
                    "Number of components of a path exceeded the maximum component count"
                )
            }
            PathError::ComponentTooLong => {
                write!(
                    f,
                    "Length of a path component exceeded the maximum component length"
                )
            }
        }
    }
}

impl core::error::Error for PathError {}

impl From<PathFromComponentsError> for PathError {
    fn from(value: PathFromComponentsError) -> Self {
        match value {
            PathFromComponentsError::PathTooLong => Self::PathTooLong,
            PathFromComponentsError::TooManyComponents => Self::TooManyComponents,
        }
    }
}

impl From<InvalidComponentError> for PathError {
    fn from(_value: InvalidComponentError) -> Self {
        Self::ComponentTooLong
    }
}

/// An immutable Willow [Path](https://willowprotocol.org/specs/data-model/index.html#Path). Thread-safe, cheap to clone, cheap to take prefixes of, expensive to append to (linear time complexity).
///
/// A Willow Path is any sequence of bytestrings — called [Components](https://willowprotocol.org/specs/data-model/index.html#Component) — fulfilling certain constraints:
///
/// - each [`Component`] has a length of at most `MCL` ([**m**ax\_**c**omponent\_**l**ength](https://willowprotocol.org/specs/data-model/index.html#max_component_length)),
/// - each [`Path`] has at most `MCC` ([**m**ax\_**c**omponent\_**c**ount](https://willowprotocol.org/specs/data-model/index.html#max_component_count)) components, and
/// - the total size in bytes of all [`Component`]s is at most `MPL` ([**m**ax\_**p**ath\_**l**ength](https://willowprotocol.org/specs/data-model/index.html#max_path_length)).
///
/// This type statically enforces these invariants for all (safely) created instances.
///
/// Because appending [`Component`]s takes time linear in the length of the full [`Path`], you should not build up [`Path`]s this way. Instead, use [`Path::from_components`], [`Path::from_slices`], [`Path::from_components_iter`], [`Path::from_slices_iter`], or a [`PathBuilder`].
///
/// ```
/// use willow_data_model::prelude::*;
/// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
///
/// assert_eq!(p.component_count(), 2);
/// assert_eq!(p.component(1), Some(Component::new(b"ho")?));
/// assert_eq!(p.total_length(), 4);
/// assert!(p.is_prefixed_by(&Path::from_slice(b"hi")?));
/// assert_eq!(
///     p.longest_common_prefix(&Path::from_slices(&[b"hi", b"he"])?),
///     Path::from_slice(b"hi")?
/// );
/// # Ok::<(), PathError>(())
/// ```
#[derive(Clone)]
pub struct Path<const MCL: usize, const MCC: usize, const MPL: usize> {
    /// The data of the underlying path.
    data: Bytes,
    /// Number of components of the `data` to consider for this particular path (starting from the first component). Must be less than or equal to the total number of components.
    /// This field enables cheap prefix creation by cloning the heap data (which is reference counted) and adjusting the `component_count`.
    component_count: usize,
}

/// The default [`Path`] is the empty [`Path`].
impl<const MCL: usize, const MCC: usize, const MPL: usize> Default for Path<MCL, MCC, MPL> {
    /// Returns an empty [`Path`].
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// assert_eq!(Path::<4, 4, 4>::default().component_count(), 0);
    /// assert_eq!(Path::<4, 4, 4>::default(), Path::<4, 4, 4>::new());
    /// ```
    fn default() -> Self {
        Self::new()
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize> Path<MCL, MCC, MPL> {
    /// Returns an empty [`Path`], i.e., a [`Path`] of zero [`Component`]s.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(1)`.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// assert_eq!(Path::<4, 4, 4>::new().component_count(), 0);
    /// assert_eq!(Path::<4, 4, 4>::new(), Path::<4, 4, 4>::default());
    /// ```
    pub fn new() -> Self {
        PathBuilder::new(0, 0)
            .expect("The empty path is legal for every choice of of MCL, MCC, and MPL.")
            .build()
    }

    /// Creates a singleton [`Path`], consisting of exactly one [`Component`].
    ///
    /// Copies the bytes of the [`Component`] into an owned allocation on the heap.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(n)`, where `n` is the length of the [`Component`]. Performs a single allocation of `O(n)` bytes.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p = Path::<4, 4, 4>::from_component(Component::new(b"hi!")?)?;
    /// assert_eq!(p.component_count(), 1);
    ///
    /// assert_eq!(
    ///     Path::<4, 4, 2>::from_component(Component::new(b"hi!")?),
    ///     Err(PathFromComponentsError::PathTooLong),
    /// );
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn from_component(comp: &Component<MCL>) -> Result<Self, PathFromComponentsError> {
        let mut builder = PathBuilder::new(comp.as_ref().len(), 1)?;
        builder.append_component(comp);
        Ok(builder.build())
    }

    /// Creates a singleton [`Path`], consisting of exactly one [`Component`], from a raw slice of bytes.
    ///
    /// Copies the bytes into an owned allocation on the heap.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(n)`, where `n` is the length of the [`Component`]. Performs a single allocation of `O(n)` bytes.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p = Path::<4, 4, 4>::from_slice(b"hi!")?;
    /// assert_eq!(p.component_count(), 1);
    ///
    /// assert_eq!(
    ///     Path::<4, 4, 4>::from_slice(b"too_long_for_single_component"),
    ///     Err(PathError::ComponentTooLong),
    /// );
    /// assert_eq!(
    ///     Path::<4, 3, 1>::from_slice(b"nope"),
    ///     Err(PathError::PathTooLong),
    /// );
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn from_slice(comp: &[u8]) -> Result<Self, PathError> {
        Ok(Self::from_component(Component::new(comp)?)?)
    }

    /// Creates a [`Path`] from a slice of [`Component`]s.
    ///
    /// Copies the bytes of the [`Component`]s into an owned allocation on the heap.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(n + m)`, where `n` is the total length of the created [`Path`] in bytes, and `m` is the number of its [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let components: Vec<&Component<4>> = vec![
    ///     &Component::new(b"hi")?,
    ///     &Component::new(b"!")?,
    /// ];
    ///
    /// assert!(Path::<4, 4, 4>::from_components(&components[..]).is_ok());
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn from_components(
        components: &[&Component<MCL>],
    ) -> Result<Self, PathFromComponentsError> {
        let mut total_length = 0;
        for comp in components {
            total_length += comp.as_ref().len();
        }

        Self::from_components_iter(total_length, &mut components.iter().cloned())
    }

    /// Create a new [`Path`] from a slice of byte slices.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(n + m)`, where `n` is the total length of the created [`Path`] in bytes, and `m` is the number of its [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
    ///
    /// # Example
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// // Ok
    /// let path = Path::<12, 3, 30>::from_slices(&[b"alfie", b"notes"]).unwrap();
    ///
    /// // Err
    /// let result1 = Path::<12, 3, 30>::from_slices(&[b"themaxpath", b"lengthis30", b"thisislonger"]);
    /// assert_eq!(result1, Err(PathError::PathTooLong));
    ///
    /// // Err
    /// let result2 = Path::<12, 3, 30>::from_slices(&[b"too", b"many", b"components", b"error"]);
    /// assert_eq!(result2, Err(PathError::TooManyComponents));
    ///
    /// // Err
    /// let result3 = Path::<12, 3, 30>::from_slices(&[b"overencumbered"]);
    /// assert_eq!(result3, Err(PathError::ComponentTooLong));
    /// ```
    pub fn from_slices(slices: &[&[u8]]) -> Result<Self, PathError> {
        let total_length = slices.iter().map(|it| it.as_ref().len()).sum();
        let mut builder = PathBuilder::new(total_length, slices.len())?;

        for component_slice in slices {
            builder.append_slice(component_slice.as_ref())?;
        }

        Ok(builder.build())
    }

    /// Creates a [`Path`] of known total length from an [`ExactSizeIterator`] of [`Component`]s.
    ///
    /// Copies the bytes of the [`Component`]s into an owned allocation on the heap.
    ///
    /// Panics if the claimed `total_length` does not match the sum of the lengths of all the [`Component`]s.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(n + m)`, where `n` is the total length of the created [`Path`] in bytes, and `m` is the number of its [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let components: Vec<&Component<4>> = vec![
    ///     &Component::new(b"hi")?,
    ///     &Component::new(b"!")?,
    /// ];
    ///
    /// assert!(Path::<4, 4, 4>::from_components_iter(3, &mut components.into_iter()).is_ok());
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn from_components_iter<'c, I>(
        total_length: usize,
        iter: &mut I,
    ) -> Result<Self, PathFromComponentsError>
    where
        I: ExactSizeIterator<Item = &'c Component<MCL>>,
    {
        let mut builder = PathBuilder::new(total_length, iter.len())?;

        for component in iter {
            builder.append_component(component);
        }

        Ok(builder.build())
    }

    /// Creates a [`Path`] of known total length from an [`ExactSizeIterator`] of byte slices.
    ///
    /// Copies the bytes of the [`Component`]s into an owned allocation on the heap.
    ///
    /// Panics if the claimed `total_length` does not match the sum of the lengths of all the [`Component`]s.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(n + m)`, where `n` is the total length of the created [`Path`] in bytes, and `m` is the number of its [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let components: Vec<&[u8]> = vec![b"hi", b"!"];
    /// assert!(Path::<4, 4, 4>::from_slices_iter(3, &mut components.into_iter()).is_ok());
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn from_slices_iter<'a, I>(total_length: usize, iter: &mut I) -> Result<Self, PathError>
    where
        I: ExactSizeIterator<Item = &'a [u8]>,
    {
        let mut builder = PathBuilder::new(total_length, iter.len())?;

        for slice in iter {
            builder.append_slice(slice.as_ref())?;
        }

        Ok(builder.build())
    }

    /// Creates a new [`Path`] by appending a [`Component`] to `&self`.
    ///
    /// Creates a fully separate copy of the new data on the heap; which includes cloning all data in `&self`. To efficiently construct [`Path`]s, use [`Path::from_components`], [`Path::from_slices`], [`Path::from_components_iter`], [`Path::from_slices_iter`], or a [`PathBuilder`].
    ///
    /// #### Complexity
    ///
    /// Runs in `O(n + m)`, where `n` is the total length of the resulting [`Path`] in bytes, and `m` is the number of its [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p0: Path<4, 4, 4> = Path::new();
    /// let p1 = p0.append_component(Component::new(b"hi")?)?;
    /// let p2 = p1.append_component(Component::new(b"!")?)?;
    /// assert_eq!(
    ///     p2.append_component(Component::new(b"no!")?),
    ///     Err(PathFromComponentsError::PathTooLong),
    /// );
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn append_component(&self, comp: &Component<MCL>) -> Result<Self, PathFromComponentsError> {
        let mut builder = PathBuilder::new(
            self.total_length() + comp.as_ref().len(),
            self.component_count() + 1,
        )?;

        for component in self.components() {
            builder.append_component(component);
        }
        builder.append_component(comp);

        Ok(builder.build())
    }

    /// Creates a new [`Path`] by appending a [`Component`] to `&self`.
    ///
    /// Creates a fully separate copy of the new data on the heap; which includes cloning all data in `&self`. To efficiently construct [`Path`]s, use [`Path::from_components`], [`Path::from_slices`], [`Path::from_components_iter`], [`Path::from_slices_iter`], or a [`PathBuilder`].
    ///
    /// #### Complexity
    ///
    /// Runs in `O(n + m)`, where `n` is the total length of the resulting [`Path`] in bytes, and `m` is the number of its [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p0: Path<4, 4, 4> = Path::new();
    /// let p1 = p0.append_slice(b"hi")?;
    /// let p2 = p1.append_slice(b"!")?;
    /// assert_eq!(
    ///     p2.append_slice(b"no!"),
    ///     Err(PathError::PathTooLong),
    /// );
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn append_slice(&self, comp: &[u8]) -> Result<Self, PathError> {
        Ok(self.append_component(Component::new(comp)?)?)
    }

    /// Creates a new [`Path`] by appending a slice of [`Component`]s to `&self`.
    ///
    /// Creates a fully separate copy of the new data on the heap; which includes cloning all data in `&self`. To efficiently construct [`Path`]s, use [`Path::from_components`], [`Path::from_slices`], [`Path::from_components_iter`], [`Path::from_slices_iter`], or a [`PathBuilder`].
    ///
    /// #### Complexity
    ///
    /// Runs in `O(n + m)`, where `n` is the total length of the resulting [`Path`] in bytes, and `m` is the number of its [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p0: Path<4, 4, 4> = Path::new();
    /// let p1 = p0.append_components(&[Component::new(b"hi")?, Component::new(b"!")?])?;
    /// assert_eq!(
    ///     p1.append_components(&[Component::new(b"no!")?]),
    ///     Err(PathFromComponentsError::PathTooLong),
    /// );
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn append_components(
        &self,
        components: &[&Component<MCL>],
    ) -> Result<Self, PathFromComponentsError> {
        let mut total_length = self.total_length();
        for comp in components {
            total_length += comp.as_ref().len();
        }

        let mut builder = PathBuilder::new_from_prefix(
            total_length,
            self.component_count() + components.len(),
            self,
            self.component_count(),
        )?;

        for additional_component in components {
            builder.append_component(*additional_component);
        }

        Ok(builder.build())
    }

    /// Creates a new [`Path`] by appending a slice of [`Component`]s to `&self`.
    ///
    /// Creates a fully separate copy of the new data on the heap; which includes cloning all data in `&self`. To efficiently construct [`Path`]s, use [`Path::from_components`], [`Path::from_slices`], [`Path::from_components_iter`], [`Path::from_slices_iter`], or a [`PathBuilder`].
    ///
    /// #### Complexity
    ///
    /// Runs in `O(n + m)`, where `n` is the total length of the resulting [`Path`] in bytes, and `m` is the number of its [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p0: Path<4, 4, 4> = Path::new();
    /// let p1 = p0.append_slices(&[b"hi", b"ho"])?;
    /// assert_eq!(
    ///     p1.append_slices(&[b"no!"]),
    ///     Err(PathError::PathTooLong),
    /// );
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn append_slices(&self, components: &[&[u8]]) -> Result<Self, PathError> {
        let mut total_length = self.total_length();
        for comp in components {
            total_length += comp.as_ref().len();
        }

        let mut builder = PathBuilder::new_from_prefix(
            total_length,
            self.component_count() + components.len(),
            self,
            self.component_count(),
        )?;

        for additional_component in components {
            builder.append_slice(additional_component.as_ref())?;
        }

        Ok(builder.build())
    }

    /// Creates a new [`Path`] by appending another [`Path`] to `&self`.
    ///
    /// Creates a fully separate copy of the new data on the heap; which includes cloning all data in `&self` and in `&other`.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(n + m)`, where `n` is the total length of the resulting [`Path`] in bytes, and `m` is the number of its [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p0: Path<4, 4, 4> = Path::new();
    /// let p1 = p0.append_path(&Path::from_slices(&[b"hi", b"ho"])?)?;
    /// assert_eq!(
    ///     p1.append_path(&Path::from_slice(b"no!")?),
    ///     Err(PathFromComponentsError::PathTooLong),
    /// );
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn append_path(
        &self,
        other: &Path<MCL, MCC, MPL>,
    ) -> Result<Self, PathFromComponentsError> {
        let total_length = self.total_length() + other.total_length();

        let mut builder = PathBuilder::new_from_prefix(
            total_length,
            self.component_count() + other.component_count(),
            self,
            self.component_count(),
        )?;

        for additional_component in other.components() {
            builder.append_component(additional_component);
        }

        Ok(builder.build())
    }

    /// Returns the least [`Path`] which is strictly greater (lexicographically) than `self` and which is not [prefixed by](https://willowprotocol.org/specs/data-model/index.html#path_prefix) `self`; or [`None`] if no such [`Path`] exists.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(n + m)`, where `n` is the total length of the [`Path`] in bytes, and `m` is the number of [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
    pub fn greater_but_not_prefixed(&self) -> Option<Self> {
        // We iterate through all components in reverse order. For each component, we check whether we can replace it by another cmponent that is strictly greater but not prefixed by the original component. If that is possible, we do replace it with the least such component and drop all later components. If that is impossible, we try again with the previous component. If this impossible for all components, then this function returns `None`.

        for (i, component) in self.components().enumerate().rev() {
            // If it is possible to append a zero byte to a component, then doing so yields its successor.
            if component.len() < MCL
                && Representation::sum_of_lengths_for_component(self.data.as_ref(), i) < MPL
            {
                let mut buf = clone_prefix_and_lengthen_final_component(&self.data, i, 1);
                buf.put_u8(0);

                return Some(Path {
                    data: buf.freeze(),
                    component_count: i + 1,
                });
            }

            // Next, we check whether the i-th component can be changed into the least component that is greater but not prefixed by the original. If so, do that and cut off all later components.
            let mut next_component_length = None;
            for (j, comp_byte) in component.iter().enumerate().rev() {
                if *comp_byte < 255 {
                    next_component_length = Some(j + 1);
                    break;
                }
            }

            if let Some(next_component_length) = next_component_length {
                // Yay, we can replace the i-th comopnent and then we are done.

                let mut buf = clone_prefix_and_lengthen_final_component(&self.data, i, 0);
                let length_of_prefix = Representation::sum_of_lengths_for_component(&buf, i);

                // Update the length of the final component.
                buf_set_final_component_length(
                    buf.as_mut(),
                    i,
                    length_of_prefix - (component.len() - next_component_length),
                );

                // Increment the byte at position `next_component_length` of the final component.
                let offset = Representation::start_offset_of_component(buf.as_ref(), i)
                    + next_component_length
                    - 1;
                let byte = buf.as_ref()[offset]; // guaranteed < 255...
                buf.as_mut()[offset] = byte + 1; // ... hence no overflow here.

                return Some(Path {
                    data: buf.freeze(),
                    component_count: i + 1,
                });
            }
        }

        None
    }

    /// Returns the number of [`Component`]s in `&self`.
    ///
    /// Guaranteed to be at most `MCC`.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(1)`, performs no allocations.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
    /// assert_eq!(p.component_count(), 2);
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn component_count(&self) -> usize {
        self.component_count
    }

    /// Returns whether `&self` has zero [`Component`]s.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(1)`, performs no allocations.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// assert_eq!(Path::<4, 4, 4>::new().is_empty(), true);
    ///
    /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
    /// assert_eq!(p.is_empty(), false);
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn is_empty(&self) -> bool {
        self.component_count() == 0
    }

    /// Returns the sum of the lengths of all [`Component`]s in `&self`.
    ///
    /// Guaranteed to be at most `MCC`.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(1)`, performs no allocations.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
    /// assert_eq!(p.total_length(), 4);
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn total_length(&self) -> usize {
        self.total_length_of_prefix(self.component_count())
    }

    /// Returns the sum of the lengths of the first `i` [`Component`]s in `&self`; panics if `i >= self.component_count()`. More efficient than `path.create_prefix(i).path_length()`.
    ///
    /// Guaranteed to be at most `MCC`.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(1)`, performs no allocations.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
    /// assert_eq!(p.total_length_of_prefix(0), 0);
    /// assert_eq!(p.total_length_of_prefix(1), 2);
    /// assert_eq!(p.total_length_of_prefix(2), 4);
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn total_length_of_prefix(&self, i: usize) -> usize {
        Representation::total_length(&self.data, i)
    }

    /// Tests whether `&self` is a [prefix](https://willowprotocol.org/specs/data-model/index.html#path_prefix) of the given [`Path`].
    /// [`Path`]s are always a prefix of themselves, and the empty [`Path`] is a prefix of every [`Path`].
    ///
    /// #### Complexity
    ///
    /// Runs in `O(n + m)`, where `n` is the total length of the longer [`Path`] in bytes, and `m` is the greatest number of [`Component`]s.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
    /// assert!(Path::new().is_prefix_of(&p));
    /// assert!(Path::from_slice(b"hi")?.is_prefix_of(&p));
    /// assert!(Path::from_slices(&[b"hi", b"ho"])?.is_prefix_of(&p));
    /// assert!(!Path::from_slices(&[b"hi", b"gh"])?.is_prefix_of(&p));
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn is_prefix_of(&self, other: &Self) -> bool {
        self.prefix_cmp(other)
            .map(|ord| ord.is_le())
            .unwrap_or(false)
    }

    /// Tests whether `&self` is [prefixed by](https://willowprotocol.org/specs/data-model/index.html#path_prefix) the given [`Path`].
    /// [`Path`]s are always prefixed by themselves, and by the empty [`Path`].
    ///
    /// #### Complexity
    ///
    /// Runs in `O(n + m)`, where `n` is the total length of the longer [`Path`] in bytes, and `m` is the greatest number of [`Component`]s.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
    /// assert!(p.is_prefixed_by(&Path::new()));
    /// assert!(p.is_prefixed_by(&Path::from_slice(b"hi")?));
    /// assert!(p.is_prefixed_by(&Path::from_slices(&[b"hi", b"ho"])?));
    /// assert!(!p.is_prefixed_by(&Path::from_slices(&[b"hi", b"gh"])?));
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn is_prefixed_by(&self, other: &Self) -> bool {
        other.is_prefix_of(self)
    }

    /// Tests whether `&self` is [related](https://willowprotocol.org/specs/data-model/index.html#path_related) to the given [`Path`], that is, whether either one is a [prefix](https://willowprotocol.org/specs/data-model/index.html#path_prefix) of the other.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(n + m)`, where `n` is the total length of the longer [`Path`] in bytes, and `m` is the greatest number of [`Component`]s.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p: Path<4, 4, 4> = Path::from_slice(b"hi")?;
    /// assert!(p.is_related_to(&Path::new()));
    /// assert!(p.is_related_to(&Path::from_slice(b"hi")?));
    /// assert!(p.is_related_to(&Path::from_slices(&[b"hi", b"ho"])?));
    /// assert!(!p.is_related_to(&Path::from_slices(&[b"no"])?));
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn is_related_to(&self, other: &Self) -> bool {
        self.prefix_cmp(other).is_some()
    }

    /// Returns the [`Ordering`] describing the prefix relation between `self` and `other`.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(n + m)`, where `n` is the total length of the longer [`Path`] in bytes, and `m` is the greatest number of [`Component`]s.
    ///
    /// #### Examples
    ///
    /// ```
    /// use core::cmp::Ordering;
    /// use willow_data_model::prelude::*;
    /// let p: Path<4, 4, 4> = Path::from_slice(b"hi")?;
    /// assert_eq!(p.prefix_cmp(&Path::new()), Some(Ordering::Greater));
    /// assert_eq!(p.prefix_cmp(&Path::from_slice(b"hi")?), Some(Ordering::Equal));
    /// assert_eq!(p.prefix_cmp(&Path::from_slices(&[b"hi", b"ho"])?), Some(Ordering::Less));
    /// assert_eq!(p.prefix_cmp(&Path::from_slice(b"no")?), None);
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn prefix_cmp(&self, other: &Self) -> Option<Ordering> {
        for (comp_a, comp_b) in self.components().zip(other.components()) {
            if comp_a != comp_b {
                return None;
            }
        }

        self.component_count().partial_cmp(&other.component_count())
    }

    /// Returns the `i`-th [`Component`] of `&self`.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(1)`, performs no allocations.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
    /// assert_eq!(p.component(0), Some(Component::new(b"hi")?));
    /// assert_eq!(p.component(1), Some(Component::new(b"ho")?));
    /// assert_eq!(p.component(2), None);
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn component(&self, i: usize) -> Option<&Component<MCL>> {
        if i < self.component_count {
            Some(Representation::component(&self.data, i))
        } else {
            None
        }
    }

    /// Returns the `i`-th [`Component`] of `&self`, without checking whether `i < self.component_count()`.
    ///
    /// #### Safety
    ///
    /// Undefined behaviour if `i >= self.component_count()`.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(1)`, performs no allocations.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
    /// assert_eq!(unsafe { p.component_unchecked(0) }, Component::new(b"hi")?);
    /// assert_eq!(unsafe { p.component_unchecked(1) }, Component::new(b"ho")?);
    /// # Ok::<(), PathError>(())
    /// ```
    pub unsafe fn component_unchecked(&self, i: usize) -> &Component<MCL> {
        Representation::component(&self.data, i)
    }

    /// Returns an [owned handle](OwnedComponent) to the `i`-th component of `&self`.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(1)`, performs no allocations.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
    /// assert_eq!(p.owned_component(0), Some(OwnedComponent::new(b"hi")?));
    /// assert_eq!(p.owned_component(1), Some(OwnedComponent::new(b"ho")?));
    /// assert_eq!(p.owned_component(2), None);
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn owned_component(&self, i: usize) -> Option<OwnedComponent<MCL>> {
        if i < self.component_count {
            let start = Representation::start_offset_of_component(&self.data, i);
            let end = Representation::end_offset_of_component(&self.data, i);
            Some(OwnedComponent(self.data.slice(start..end)))
        } else {
            None
        }
    }

    /// Returns an [owned handle](OwnedComponent) to the `i`-th component of `&self`, without checking whether `i < self.component_count()`.
    ///
    /// #### Safety
    ///
    /// Undefined behaviour if `i >= self.component_count()`.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(1)`, performs no allocations.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
    /// assert_eq!(p.owned_component(0), Some(OwnedComponent::new(b"hi")?));
    /// assert_eq!(p.owned_component(1), Some(OwnedComponent::new(b"ho")?));
    /// assert_eq!(p.owned_component(2), None);
    /// # Ok::<(), PathError>(())
    /// ```
    pub unsafe fn owned_component_unchecked(&self, i: usize) -> OwnedComponent<MCL> {
        let start = Representation::start_offset_of_component(&self.data, i);
        let end = Representation::end_offset_of_component(&self.data, i);
        OwnedComponent(self.data.slice(start..end))
    }

    /// Creates an iterator over the [`Component`]s of `&self`.
    ///
    /// Stepping the iterator takes `O(1)` time and performs no memory allocations.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(1)`, performs no allocations.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
    /// let mut comps = p.components();
    /// assert_eq!(comps.next(), Some(Component::new(b"hi")?));
    /// assert_eq!(comps.next(), Some(Component::new(b"ho")?));
    /// assert_eq!(comps.next(), None);
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn components(
        &self,
    ) -> impl DoubleEndedIterator<Item = &Component<MCL>> + ExactSizeIterator<Item = &Component<MCL>>
    {
        self.suffix_components(0)
    }

    /// Creates an iterator over the [`Component`]s of `&self`, starting at the `i`-th [`Component`]. If `i` is greater than or equal to the number of [`Component`]s, the iterator yields zero items.
    ///
    /// Stepping the iterator takes `O(1)` time and performs no memory allocations.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(1)`, performs no allocations.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
    /// let mut comps = p.suffix_components(1);
    /// assert_eq!(comps.next(), Some(Component::new(b"ho")?));
    /// assert_eq!(comps.next(), None);
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn suffix_components(
        &'_ self,
        i: usize,
    ) -> impl DoubleEndedIterator<Item = &Component<MCL>> + ExactSizeIterator<Item = &Component<MCL>>
    {
        (i..self.component_count()).map(|i| {
            self.component(i).unwrap() // Only `None` if `i >= self.component_count()`
        })
    }

    /// Creates an iterator over [owned handles](OwnedComponent) to the components of `&self`.
    ///
    /// Stepping the iterator takes `O(1)` time and performs no memory allocations.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(1)`, performs no allocations.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
    /// let mut comps = p.owned_components();
    /// assert_eq!(comps.next(), Some(OwnedComponent::new(b"hi")?));
    /// assert_eq!(comps.next(), Some(OwnedComponent::new(b"ho")?));
    /// assert_eq!(comps.next(), None);
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn owned_components(
        &self,
    ) -> impl DoubleEndedIterator<Item = OwnedComponent<MCL>>
    + ExactSizeIterator<Item = OwnedComponent<MCL>>
    + '_ {
        self.suffix_owned_components(0)
    }

    /// Creates an iterator over [owned handles](OwnedComponent) to the components of `&self`, starting at the `i`-th [`OwnedComponent`]. If `i` is greater than or equal to the number of [`OwnedComponent`], the iterator yields zero items.
    ///
    /// Stepping the iterator takes `O(1)` time and performs no memory allocations.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(1)`, performs no allocations.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
    /// let mut comps = p.suffix_owned_components(1);
    /// assert_eq!(comps.next(), Some(OwnedComponent::new(b"ho")?));
    /// assert_eq!(comps.next(), None);
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn suffix_owned_components(
        &self,
        i: usize,
    ) -> impl DoubleEndedIterator<Item = OwnedComponent<MCL>>
    + ExactSizeIterator<Item = OwnedComponent<MCL>>
    + '_ {
        (i..self.component_count()).map(|i| {
            self.owned_component(i).unwrap() // Only `None` if `i >= self.component_count()`
        })
    }

    /// Creates a new [`Path`] that consists of the first `component_count` [`Component`]s of `&self`. More efficient than creating a new [`Path`] from scratch.
    ///
    /// Returns [`None`] if `component_count` is greater than `self.get_component_count()`.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(1)`, performs no allocations.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
    /// assert_eq!(p.create_prefix(0), Some(Path::new()));
    /// assert_eq!(p.create_prefix(1), Some(Path::from_slice(b"hi")?));
    /// assert_eq!(p.create_prefix(2), Some(Path::from_slices(&[b"hi", b"ho"])?));
    /// assert_eq!(p.create_prefix(3), None);
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn create_prefix(&self, component_count: usize) -> Option<Self> {
        if component_count > self.component_count() {
            None
        } else {
            Some(unsafe { self.create_prefix_unchecked(component_count) })
        }
    }

    /// Creates a new [`Path`] that consists of the first `component_count` [`Component`]s of `&self`. More efficient than creating a new [`Path`] from scratch.
    ///
    /// #### Safety
    ///
    /// Undefined behaviour if `component_count` is greater than `self.component_count()`. May manifest directly, or at any later
    /// function invocation that operates on the resulting [`Path`].
    ///
    /// #### Complexity
    ///
    /// Runs in `O(1)`, performs no allocations.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
    /// assert_eq!(unsafe { p.create_prefix_unchecked(0) }, Path::new());
    /// assert_eq!(unsafe { p.create_prefix_unchecked(1) }, Path::from_slice(b"hi")?);
    /// assert_eq!(unsafe { p.create_prefix_unchecked(2) }, Path::from_slices(&[b"hi", b"ho"])?);
    /// # Ok::<(), PathError>(())
    /// ```
    pub unsafe fn create_prefix_unchecked(&self, component_count: usize) -> Self {
        Self {
            data: self.data.clone(),
            component_count,
        }
    }

    /// Creates an iterator over all [prefixes](https://willowprotocol.org/specs/data-model/index.html#path_prefix) of `&self` (including the empty [`Path`] and `&self` itself).
    ///
    /// Stepping the iterator takes `O(1)` time and performs no memory allocations.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(1)`, performs no allocations.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
    /// let mut prefixes = p.all_prefixes();
    /// assert_eq!(prefixes.next(), Some(Path::new()));
    /// assert_eq!(prefixes.next(), Some(Path::from_slice(b"hi")?));
    /// assert_eq!(prefixes.next(), Some(Path::from_slices(&[b"hi", b"ho"])?));
    /// assert_eq!(prefixes.next(), None);
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn all_prefixes(&self) -> impl DoubleEndedIterator<Item = Self> + '_ {
        (0..=self.component_count()).map(|i| {
            unsafe {
                self.create_prefix_unchecked(i) // safe to call for i <= self.component_count()
            }
        })
    }

    /// Returns the longest common [prefix](https://willowprotocol.org/specs/data-model/index.html#path_prefix) of `&self` and the given [`Path`].
    ///
    /// #### Complexity
    ///
    /// Runs in `O(n + m)`, where `n` is the total length of the shorter of the two [`Path`]s, and `m` is the lesser number of [`Component`]s. Performs a single allocation of `O(n + m)` bytes to create the return value.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// let p1: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"ho"])?;
    /// let p2: Path<4, 4, 4> = Path::from_slices(&[b"hi", b"he"])?;
    /// assert_eq!(p1.longest_common_prefix(&p2), Path::from_slice(b"hi")?);
    /// # Ok::<(), PathError>(())
    /// ```
    pub fn longest_common_prefix(&self, other: &Self) -> Self {
        let mut lcp_len = 0;

        for (comp_a, comp_b) in self.components().zip(other.components()) {
            if comp_a != comp_b {
                break;
            }

            lcp_len += 1
        }

        self.create_prefix(lcp_len).unwrap() // zip ensures that lcp_len <= self.component_count()
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize> PartialEq for Path<MCL, MCC, MPL> {
    fn eq(&self, other: &Self) -> bool {
        if self.component_count != other.component_count {
            false
        } else {
            self.components().eq(other.components())
        }
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize> Eq for Path<MCL, MCC, MPL> {}

impl<const MCL: usize, const MCC: usize, const MPL: usize> Hash for Path<MCL, MCC, MPL> {
    fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
        self.component_count.hash(state);

        for comp in self.components() {
            comp.hash(state);
        }
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize> PartialOrd for Path<MCL, MCC, MPL> {
    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

/// Compares paths lexicographically, since that is the path ordering that the Willow spec always uses.
impl<const MCL: usize, const MCC: usize, const MPL: usize> Ord for Path<MCL, MCC, MPL> {
    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
        self.components().cmp(other.components())
    }
}

/// The least path is the empty path.
impl<const MCL: usize, const MCC: usize, const MPL: usize> LeastElement for Path<MCL, MCC, MPL> {
    /// Returns the least path.
    fn least() -> Self {
        Self::new()
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize> GreatestElement for Path<MCL, MCC, MPL> {
    /// Creates the greatest possible [`Path`] (with respect to lexicographical ordering, which is also the [`Ord`] implementation of [`Path`]).
    ///
    /// #### Complexity
    ///
    /// Runs in `O(MCC + MPL)`. Performs a single allocation of `O(MPL)` bytes.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// use order_theory::GreatestElement;
    ///
    /// let p = Path::<4, 4, 4>::greatest();
    /// assert_eq!(p.component_count(), 4);
    /// assert_eq!(p.component(0).unwrap().as_ref(), &[255, 255, 255, 255]);
    /// assert!(p.component(1).unwrap().is_empty());
    /// assert!(p.component(2).unwrap().is_empty());
    /// assert!(p.component(3).unwrap().is_empty());
    /// ```
    fn greatest() -> Self {
        let max_comp_bytes = [255; MCL];

        let mut num_comps = if MCL == 0 {
            MCC
        } else {
            core::cmp::min(MCC, MPL.div_ceil(MCL))
        };
        let mut path_builder = PathBuilder::new(MPL, MCC).unwrap();

        let mut len_so_far = 0;

        for _ in 0..num_comps {
            let comp_len = core::cmp::min(MCL, MPL - len_so_far);
            let component = unsafe { Component::new_unchecked(&max_comp_bytes[..comp_len]) };
            path_builder.append_component(component);

            len_so_far += comp_len;
        }

        while num_comps < MCC {
            path_builder.append_component(Component::new_empty());
            num_comps += 1;
        }

        path_builder.build()
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize> LowerSemilattice
    for Path<MCL, MCC, MPL>
{
    fn greatest_lower_bound(&self, other: &Self) -> Self {
        if self <= other {
            self.clone()
        } else {
            other.clone()
        }
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize> UpperSemilattice
    for Path<MCL, MCC, MPL>
{
    fn least_upper_bound(&self, other: &Self) -> Self {
        if self >= other {
            self.clone()
        } else {
            other.clone()
        }
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize> TryPredecessor for Path<MCL, MCC, MPL> {
    fn try_predecessor(&self) -> Option<Self> {
        if self.component_count() == 0 {
            // We are the empty path, so we do not have a predecessor.
            None
        } else {
            let final_component = self.component(self.component_count() - 1).unwrap();

            // We have a component. Our predecessor depends only on the final component, with several options depending on the final byte:
            if final_component.as_bytes().is_empty() {
                // If the final component is empty, we simply remove it to obtain the predecessor.
                Some(unsafe { self.create_prefix_unchecked(self.component_count() - 1) })
            } else {
                let final_byte = final_component.as_bytes()[final_component.len() - 1];

                // The final component was non-empty. We now decrement the final component, and then fill up the path with maximally many maximal components.

                // Create a builder for the new component, which will be of maximal length, maximal component count, and starting with `self` sans the final_component.
                let predecessor_total_len = core::cmp::min(
                    MPL,
                    self.total_length_of_prefix(self.component_count() - 1) // unchanged components
                        + if final_byte == 0 { final_component.len() - 1 } else { MCL } // replacement of self.final_comp
                        + ((MCC - self.component_count()) * MCL), // padding 255 bytes
                );
                let mut builder = PathBuilder::new_from_prefix(
                    predecessor_total_len,
                    MCC,
                    self,
                    self.component_count() - 1,
                )
                .unwrap();

                // The meaning of "decrement the final component" depends on the final byte.
                // In either case we do not actually construct a coponent, but merely apend the decremented component to the builder.
                if final_byte == 0 {
                    // If the final byte is zero, we simply remove it from the component.
                    builder.append_component(unsafe {
                        Component::<MCL>::new_unchecked(
                            &final_component[..final_component.len() - 1],
                        )
                    });
                } else {
                    // If the final byte is not zero, we decrement the final byte by one and then append 255 bytes until hitting the MCL or the MPL, whichever happens first..

                    // The way we actually implement this is by creating a mutable array of MCL many 255 bytes, overwriting the start of it, and then feeding the correct prefix into the builder.
                    let mut arr = [255; MCL];

                    arr[0..final_component.len()].copy_from_slice(&final_component[..]);
                    arr[final_component.len() - 1] = final_byte - 1;

                    builder.append_component(unsafe {
                        Component::<MCL>::new_unchecked(
                            &arr[..core::cmp::min(
                                MCL,
                                MPL - self.total_length_of_prefix(self.component_count() - 1),
                            )],
                        )
                    });
                }

                while builder.component_count() < MCC {
                    // We have decremented the final component. Now we append maximal components while we can.
                    let comp_len = core::cmp::min(MCL, MPL - builder.total_length());

                    let arr = [255; MCL];
                    builder.append_component(unsafe {
                        Component::<MCL>::new_unchecked(&arr[..comp_len])
                    });
                }

                Some(builder.build())
            }
        }
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize> PredecessorExceptForLeast
    for Path<MCL, MCC, MPL>
{
}

impl<const MCL: usize, const MCC: usize, const MPL: usize> TrySuccessor for Path<MCL, MCC, MPL> {
    /// Returns the least path which is strictly greater than `self`, or return `None` if `self` is the greatest possible path.
    ///
    /// #### Complexity
    ///
    /// Runs in `O(n + m)`, where `n` is the total length of the [`Path`] in bytes, and `m` is the number of [`Component`]s. Performs a single allocation of `O(n + m)` bytes.
    ///
    /// #### Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    /// use order_theory::TrySuccessor;
    ///
    /// let p: Path<3, 3, 3> = Path::from_slices(&[
    ///     [255].as_slice(),
    ///     [9, 255].as_slice(),
    ///     [].as_slice(),
    /// ])?;
    /// assert_eq!(p.try_successor(), Some(Path::from_slices(&[
    ///     [255].as_slice(),
    ///     [10].as_slice(),
    /// ])?));
    /// # Ok::<(), PathError>(())
    /// ```
    fn try_successor(&self) -> Option<Self> {
        // If it is possible to append an empty component, then doing so yields the successor.
        if let Ok(path) = self.append_component(Component::new_empty()) {
            return Some(path);
        }

        // Otherwise, we try incrementing the final component. If that fails,
        // we try to increment the second-to-final component, and so on.
        // All components that come after the incremented component are discarded.
        // If *no* component can be incremented, `self` is the maximal path and we return `None`.

        for (i, component) in self.components().enumerate().rev() {
            // It would be nice to call a `try_increment_component` function, but in order to avoid
            // memory allocations, we write some lower-level but more efficient code.

            // If it is possible to append a zero byte to a component, then doing so yields its successor.
            if component.len() < MCL
                && Representation::sum_of_lengths_for_component(self.data.as_ref(), i) < MPL
            {
                // We now know how to construct the path successor of `self`:
                // Take the first `i` components (this *excludes* the current `component`),
                // then append `component` with an additional zero byte at the end.
                let mut buf = clone_prefix_and_lengthen_final_component(&self.data, i, 1);
                buf.put_u8(0);

                return Some(Path {
                    data: buf.freeze(),
                    component_count: i + 1,
                });
            }

            // We **cannot** append a zero byte, so instead we check whether we can treat the component as a fixed-width integer and increment it. The only failure case is if that component consists of 255-bytes only.
            let can_increment = !component.iter().all(|byte| *byte == 255);

            // If we cannot increment, we go to the next iteration of the loop. But if we can, we can create a copy of the
            // prefix on the first `i + 1` components, and mutate its backing memory in-place.
            if can_increment {
                let mut buf = clone_prefix_and_lengthen_final_component(&self.data, i, 0);

                let start_component_offset =
                    Representation::start_offset_of_component(buf.as_ref(), i);
                let end_component_offset = Representation::end_offset_of_component(buf.as_ref(), i);

                let overflows = fixed_width_increment_reporting_overflows(
                    &mut buf.as_mut()[start_component_offset..end_component_offset],
                );
                let new_sum_of_lengths =
                    Representation::sum_of_lengths_for_component(buf.as_ref(), i) - overflows;
                buf_set_final_component_length(buf.as_mut(), i, new_sum_of_lengths);

                return Some(Path {
                    data: buf.freeze(),
                    component_count: i + 1,
                });
            }
        }

        // Failed to increment any component, so `self` is the maximal path.
        None
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize> SuccessorExceptForGreatest
    for Path<MCL, MCC, MPL>
{
}

impl<const MCL: usize, const MCC: usize, const MPL: usize> Debug for Path<MCL, MCC, MPL> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_tuple("Path").field(&FmtHelper(self)).finish()
    }
}

struct FmtHelper<'a, const MCL: usize, const MCC: usize, const MPL: usize>(&'a Path<MCL, MCC, MPL>);

impl<'a, const MCL: usize, const MCC: usize, const MPL: usize> fmt::Debug
    for FmtHelper<'a, MCL, MCC, MPL>
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if self.0.is_empty() {
            write!(f, "<empty>")
        } else {
            for comp in self.0.components() {
                write!(f, "/")?;
                write!(f, "{:?}", ComponentFmtHelper::new(&comp, false))?;
            }

            Ok(())
        }
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize> fmt::Display for Path<MCL, MCC, MPL> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        write!(f, "{:?}", FmtHelper(self))
    }
}

#[cfg(feature = "dev")]
impl<'a, const MCL: usize, const MCC: usize, const MPL: usize> Arbitrary<'a>
    for Path<MCL, MCC, MPL>
{
    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self, ArbitraryError> {
        let mut total_length_in_bytes: usize = Arbitrary::arbitrary(u)?;
        total_length_in_bytes %= MPL + 1;

        let data: Box<[u8]> = Arbitrary::arbitrary(u)?;
        total_length_in_bytes = core::cmp::min(total_length_in_bytes, data.len());

        let mut num_components: usize = Arbitrary::arbitrary(u)?;
        num_components %= MCC + 1;

        if num_components == 0 {
            total_length_in_bytes = 0;
        }

        let mut builder = PathBuilder::new(total_length_in_bytes, num_components).unwrap();

        let mut length_total_so_far = 0;
        for i in 0..num_components {
            // Determine the length of the i-th component: randomly within some constraints for all but the final one. The final length is chosen to match the total_length_in_bytes.
            let length_of_ith_component = if i + 1 == num_components {
                if total_length_in_bytes - length_total_so_far > MCL {
                    return Err(ArbitraryError::IncorrectFormat);
                } else {
                    total_length_in_bytes - length_total_so_far
                }
            } else {
                // Any non-final component can take on a random length, ...
                let mut component_length: usize = Arbitrary::arbitrary(u)?;
                // ... except it must be at most the MCL, and...
                component_length %= MCL + 1;
                // ... the total length of all components must not exceed the total path length.
                component_length = core::cmp::min(
                    component_length,
                    total_length_in_bytes - length_total_so_far,
                );
                component_length
            };

            builder.append_component(
                Component::new(
                    &data[length_total_so_far..length_total_so_far + length_of_ith_component],
                )
                .unwrap(),
            );
            length_total_so_far += length_of_ith_component;
        }

        Ok(builder.build())
    }

    #[inline]
    fn size_hint(depth: usize) -> (usize, Option<usize>) {
        (
            and_all(&[
                usize::size_hint(depth),
                usize::size_hint(depth),
                Box::<[u8]>::size_hint(depth),
            ])
            .0,
            None,
        )
    }
}

/////////////////////////////////////////////////////////////////////
// Helpers for efficiently creating successors.                    //
// Efficiency warrants some low-level fiddling around here, sorry. //
/////////////////////////////////////////////////////////////////////

/// Creates a new BufMut that stores the heap encoding of the first i components of `original`, but increasing the length of the final component by `extra_capacity`. No data to fill that extra capacity is written into the buffer.
fn clone_prefix_and_lengthen_final_component(
    representation: &[u8],
    i: usize,
    extra_capacity: usize,
) -> BytesMut {
    let successor_path_length =
        Representation::sum_of_lengths_for_component(representation, i) + extra_capacity;
    let buf_capacity = size_of::<usize>() * (i + 2) + successor_path_length;
    let mut buf = BytesMut::with_capacity(buf_capacity);

    // Write the length of the successor path as the first usize.
    buf.extend_from_slice(&(i + 1).to_ne_bytes());

    // Next, copy the total path lengths for the first i prefixes.
    buf.extend_from_slice(&representation[size_of::<usize>()..size_of::<usize>() * (i + 2)]);

    // Now, write the length of the final component, which is one greater than before.
    buf_set_final_component_length(buf.as_mut(), i, successor_path_length);

    // Finally, copy the raw bytes of the first i+1 components.
    buf.extend_from_slice(
        &representation[Representation::start_offset_of_component(representation, 0)
            ..Representation::start_offset_of_component(representation, i + 1)],
    );

    buf
}

// In a buffer that stores a path on the heap, set the sum of all component lengths for the i-th component, which must be the final component.
fn buf_set_final_component_length(buf: &mut [u8], i: usize, new_sum_of_lengths: usize) {
    let comp_len_start = Representation::start_offset_of_sum_of_lengths_for_component(i);
    let comp_len_end = comp_len_start + size_of::<usize>();
    buf[comp_len_start..comp_len_end].copy_from_slice(&new_sum_of_lengths.to_ne_bytes()[..]);
}

// Overflows to all zeroes if all bytes are 255. Returns the number of overflowing bytes.
fn fixed_width_increment_reporting_overflows(buf: &mut [u8]) -> usize {
    let mut overflows = 0;
    for byte_ref in buf.iter_mut().rev() {
        if *byte_ref == 255 {
            *byte_ref = 0;
            overflows += 1;
        } else {
            *byte_ref += 1;
            return overflows;
        }
    }

    overflows
}

#[test]
fn greatest() {
    let path1 = Path::<3, 3, 6>::greatest();

    assert!(path1.try_successor().is_none());

    let path2 = Path::<4, 4, 16>::greatest();
    assert!(path2.try_successor().is_none());

    let path3 = Path::<0, 4, 0>::greatest();
    assert!(path3.try_successor().is_none());

    let path4 = Path::<4, 2, 6>::greatest();
    assert!(path4.try_successor().is_none())
}