willow-data-model 0.4.1

use core::cmp::Ordering;

use crate::prelude::*;

/// A trait describing the metadata associated with each Willow [Payload](https://willowprotocol.org/specs/data-model/index.html#Payload) string.
///
/// [Entries](https://willowprotocol.org/specs/data-model/index.html#Entry) are the central concept in Willow. In order to make any bytestring of data accessible to Willow, you need to create an Entry describing its metadata. Specifically, an Entry consists of
///
/// - a [namespace_id](https://willowprotocol.org/specs/data-model/index.html#entry_namespace_id) (roughly, this addresses a universe of Willow data, fully independent from all data (i.e., Entries) of different namespace ids) of type `N`,
/// - a [subspace_id](https://willowprotocol.org/specs/data-model/index.html#entry_subspace_id) (roughly, a fully indendent part of a namespace, typically subspaces correspond to individual users) of type `S`,
/// - a [path](https://willowprotocol.org/specs/data-model/index.html#entry_path) (roughly, a file-system-like way of arranging payloads hierarchically within a subspace) of type [`Path`],
/// - a [timestamp](https://willowprotocol.org/specs/data-model/index.html#entry_timestamp) (newer Entries can overwrite certain older Entries),
/// - a [payload_length](https://willowprotocol.org/specs/data-model/index.html#entry_payload_length) (the length of the payload string), and
/// - a [payload_digest](https://willowprotocol.org/specs/data-model/index.html#entry_payload_digest) (a secure hash of the payload string being inserted into Willow).
///
/// This trait can be implemented by all types which provide at least this information. We use this trait in order to be able to abstract over specific implementations of entries. If you want a concrete type for representing entries, use the [`Entry`] struct.
pub trait Entrylike<const MCL: usize, const MCC: usize, const MPL: usize, N, S, PD>:
    Coordinatelike<MCL, MCC, MPL, S>
{
    /// Returns the [namespace_id](https://willowprotocol.org/specs/data-model/index.html#entry_namespace_id) of `self`.
    fn wdm_namespace_id(&self) -> &N;

    /// Returns the [payload_length](https://willowprotocol.org/specs/data-model/index.html#entry_payload_length) of `self`.
    fn wdm_payload_length(&self) -> u64;

    /// Returns the [payload_digest](https://willowprotocol.org/specs/data-model/index.html#entry_payload_digest) of `self`.
    fn wdm_payload_digest(&self) -> &PD;
}

/// Methods for working with [`Entrylikes`](Entrylike).
///
/// This trait is automatically implemented by all types implmenting [`Entrylike`].
pub trait EntrylikeExt<const MCL: usize, const MCC: usize, const MPL: usize, N, S, PD>:
    Entrylike<MCL, MCC, MPL, N, S, PD> + CoordinatelikeExt<MCL, MCC, MPL, S>
{
    /// Returns whether `self` and `other` describe equal entries.
    ///
    /// # Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let entry = Entry::builder()
    ///     .namespace_id("family")
    ///     .subspace_id("alfie")
    ///     .path(Path::<4, 4, 4>::new())
    ///     .timestamp(12345)
    ///     .payload_digest("b")
    ///     .payload_length(17)
    ///     .build().unwrap();
    ///
    /// assert!(entry.wdm_entry_eq(&entry));
    ///
    /// let changed = Entry::prefilled_builder(&entry).timestamp(999999).build().unwrap();
    /// assert!(!entry.wdm_entry_eq(&changed));
    ///
    /// ```
    fn wdm_entry_eq<OtherEntry>(&self, other: &OtherEntry) -> bool
    where
        OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
        N: PartialEq,
        S: PartialEq,
        PD: PartialEq,
    {
        self.wdm_namespace_id() == other.wdm_namespace_id()
            && self.wdm_coordinate_eq(other)
            && self.wdm_payload_digest() == other.wdm_payload_digest()
            && self.wdm_payload_length() == other.wdm_payload_length()
    }

    /// Returns whether `self` and `other` describe non-equal entries.
    ///
    /// # Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let entry = Entry::builder()
    ///     .namespace_id("family")
    ///     .subspace_id("alfie")
    ///     .path(Path::<4, 4, 4>::new())
    ///     .timestamp(12345)
    ///     .payload_digest("b")
    ///     .payload_length(17)
    ///     .build().unwrap();
    ///
    /// assert!(!entry.wdm_entry_ne(&entry));
    ///
    /// let changed = Entry::prefilled_builder(&entry).timestamp(999999).build().unwrap();
    /// assert!(entry.wdm_entry_ne(&changed));
    ///
    /// ```
    fn wdm_entry_ne<OtherEntry>(&self, other: &OtherEntry) -> bool
    where
        OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
        N: PartialEq,
        S: PartialEq,
        PD: PartialEq,
    {
        self.wdm_namespace_id() != other.wdm_namespace_id()
            || self.wdm_coordinate_ne(other)
            || self.wdm_payload_digest() != other.wdm_payload_digest()
            || self.wdm_payload_length() != other.wdm_payload_length()
    }

    /// Compares `self` to another entry by [timestamp](https://willowprotocol.org/specs/data-model/index.html#entry_timestamp), [payload_digest](https://willowprotocol.org/specs/data-model/index.html#entry_payload_digest) (in case of a tie), and [payload_length](https://willowprotocol.org/specs/data-model/index.html#entry_payload_length) third (in case of yet another tie). See also [`EntrylikeExt::wdm_is_newer_than`] and [`EntrylikeExt::wdm_is_older_than`].
    ///
    /// Comparing recency is primarily important to determine [which entries overwrite each other](https://willowprotocol.org/specs/data-model/index.html#prefix_pruning); the [`EntrylikeExt::wdm_prunes`] method checks for that directly.
    ///
    /// # Examples
    ///
    /// ```
    /// use core::cmp::Ordering;
    /// use willow_data_model::prelude::*;
    ///
    /// let entry = Entry::builder()
    ///     .namespace_id("family")
    ///     .subspace_id("alfie")
    ///     .path(Path::<4, 4, 4>::new())
    ///     .timestamp(12345)
    ///     .payload_digest("b")
    ///     .payload_length(17)
    ///     .build().unwrap();
    ///
    /// assert_eq!(entry.wdm_cmp_recency(&entry), Ordering::Equal);
    ///
    /// let lesser_timestamp = Entry::prefilled_builder(&entry).timestamp(5).build().unwrap();
    /// assert_eq!(entry.wdm_cmp_recency(&lesser_timestamp), Ordering::Greater);
    ///
    /// let lesser_digest = Entry::prefilled_builder(&entry).payload_digest("a").build().unwrap();
    /// assert_eq!(entry.wdm_cmp_recency(&lesser_digest), Ordering::Greater);
    ///
    /// let lesser_length = Entry::prefilled_builder(&entry).payload_length(0).build().unwrap();
    /// assert_eq!(entry.wdm_cmp_recency(&lesser_length), Ordering::Greater);
    ///
    /// let greater_timestamp = Entry::prefilled_builder(&entry).timestamp(999999).build().unwrap();
    /// assert_eq!(entry.wdm_cmp_recency(&greater_timestamp), Ordering::Less);
    ///
    /// let greater_digest = Entry::prefilled_builder(&entry).payload_digest("c").build().unwrap();
    /// assert_eq!(entry.wdm_cmp_recency(&greater_digest), Ordering::Less);
    ///
    /// let greater_length = Entry::prefilled_builder(&entry).payload_length(99).build().unwrap();
    /// assert_eq!(entry.wdm_cmp_recency(&greater_length), Ordering::Less);
    /// ```
    ///
    /// [Spec definition](https://willowprotocol.org/specs/data-model/index.html#entry_newer).
    fn wdm_cmp_recency<OtherEntry>(&self, other: &OtherEntry) -> Ordering
    where
        OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
        PD: Ord,
    {
        self.wdm_timestamp()
            .cmp(&other.wdm_timestamp())
            .then_with(|| {
                self.wdm_payload_digest()
                    .cmp(other.wdm_payload_digest())
                    .then_with(|| self.wdm_payload_length().cmp(&other.wdm_payload_length()))
            })
    }

    /// Returns whether this entry is strictly [newer](https://willowprotocol.org/specs/data-model/index.html#entry_newer) than another entry. See also [`EntrylikeExt::wdm_cmp_recency`] and [`EntrylikeExt::wdm_is_older_than`].
    ///
    /// Comparing recency is primarily important to determine [which entries overwrite each other](https://willowprotocol.org/specs/data-model/index.html#prefix_pruning); the [`EntrylikeExt::wdm_prunes`] method checks for that directly.
    ///
    /// # Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let entry = Entry::builder()
    ///     .namespace_id("family")
    ///     .subspace_id("alfie")
    ///     .path(Path::<4, 4, 4>::new())
    ///     .timestamp(12345)
    ///     .payload_digest("b")
    ///     .payload_length(17)
    ///     .build().unwrap();
    ///
    /// assert!(!entry.wdm_is_newer_than(&entry));
    ///
    /// let lesser_timestamp = Entry::prefilled_builder(&entry).timestamp(5).build().unwrap();
    /// assert!(entry.wdm_is_newer_than(&lesser_timestamp));
    ///
    /// let lesser_digest = Entry::prefilled_builder(&entry).payload_digest("a").build().unwrap();
    /// assert!(entry.wdm_is_newer_than(&lesser_digest));
    ///
    /// let lesser_length = Entry::prefilled_builder(&entry).payload_length(0).build().unwrap();
    /// assert!(entry.wdm_is_newer_than(&lesser_length));
    ///
    /// let greater_timestamp = Entry::prefilled_builder(&entry).timestamp(999999).build().unwrap();
    /// assert!(!entry.wdm_is_newer_than(&greater_timestamp));
    ///
    /// let greater_digest = Entry::prefilled_builder(&entry).payload_digest("c").build().unwrap();
    /// assert!(!entry.wdm_is_newer_than(&greater_digest));
    ///
    /// let greater_length = Entry::prefilled_builder(&entry).payload_length(99).build().unwrap();
    /// assert!(!entry.wdm_is_newer_than(&greater_length));
    /// ```
    fn wdm_is_newer_than<OtherEntry>(&self, other: &OtherEntry) -> bool
    where
        OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
        PD: Ord,
    {
        self.wdm_cmp_recency(other) == Ordering::Greater
    }

    /// Returns whether this entry is strictly [older](https://willowprotocol.org/specs/data-model/index.html#entry_newer) than another entry. See also [`EntrylikeExt::wdm_cmp_recency`] and [`EntrylikeExt::wdm_is_newer_than`].
    ///
    /// Comparing recency is primarily important to determine [which entries overwrite each other](https://willowprotocol.org/specs/data-model/index.html#prefix_pruning); the [`EntrylikeExt::wdm_prunes`] method checks for that directly.
    ///
    /// # Examples
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let entry = Entry::builder()
    ///     .namespace_id("family")
    ///     .subspace_id("alfie")
    ///     .path(Path::<4, 4, 4>::new())
    ///     .timestamp(12345)
    ///     .payload_digest("b")
    ///     .payload_length(17)
    ///     .build().unwrap();
    ///
    /// assert!(!entry.wdm_is_older_than(&entry));
    ///
    /// let lesser_timestamp = Entry::prefilled_builder(&entry).timestamp(5).build().unwrap();
    /// assert!(!entry.wdm_is_older_than(&lesser_timestamp));
    ///
    /// let lesser_digest = Entry::prefilled_builder(&entry).payload_digest("a").build().unwrap();
    /// assert!(!entry.wdm_is_older_than(&lesser_digest));
    ///
    /// let lesser_length = Entry::prefilled_builder(&entry).payload_length(0).build().unwrap();
    /// assert!(!entry.wdm_is_older_than(&lesser_length));
    ///
    /// let greater_timestamp = Entry::prefilled_builder(&entry).timestamp(999999).build().unwrap();
    /// assert!(entry.wdm_is_older_than(&greater_timestamp));
    ///
    /// let greater_digest = Entry::prefilled_builder(&entry).payload_digest("c").build().unwrap();
    /// assert!(entry.wdm_is_older_than(&greater_digest));
    ///
    /// let greater_length = Entry::prefilled_builder(&entry).payload_length(99).build().unwrap();
    /// assert!(entry.wdm_is_older_than(&greater_length));
    /// ```
    fn wdm_is_older_than<OtherEntry>(&self, other: &OtherEntry) -> bool
    where
        OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
        PD: Ord,
    {
        self.wdm_cmp_recency(other) == Ordering::Less
    }

    /// Returns whether this entry would [prefix prune](https://willowprotocol.org/specs/data-model/index.html#prefix_pruning) another entry.
    ///
    /// Prefix pruning powers deletion in Willow: whenever a data store would contain two entries, one of which pruens the other, the other is removed from the data store (or never inserted in the first place). Informally speaking, newer entries remove older entries, but only if they are in the same namespace and subspace, and only if the path of the newer entry is a prefix of the path of the older entry.
    ///
    /// More precisely: an entry `e1` prunes an entry `e2` if and only if
    ///
    /// - `e1.namespace_id() == e2.namespace_id()`,
    /// - `e1.subspace_id() == e2.subspace_id()`,
    /// - `e1.path().is_prefix_of(e2.path())`, and
    /// - `e1.wdm_is_newer_than(&e2)`.
    ///
    /// This method is the reciprocal of [`EntrylikeExt::wdm_is_pruned_by`].
    ///
    /// # Examples
    ///
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let entry = Entry::builder()
    ///     .namespace_id("family")
    ///     .subspace_id("alfie")
    ///     .path(Path::<4, 4, 4>::from_slices(&[b"a", b"b"])?)
    ///     .timestamp(12345)
    ///     .payload_digest("b")
    ///     .payload_length(17)
    ///     .build().unwrap();
    ///
    /// let newer = Entry::prefilled_builder(&entry).timestamp(99999).build().unwrap();
    /// assert!(!entry.wdm_prunes(&newer));
    /// assert!(newer.wdm_prunes(&entry));
    ///
    /// let newer_and_prefix = Entry::prefilled_builder(&newer)
    ///     .path(Path::<4, 4, 4>::from_slices(&[b"a"])?).build().unwrap();
    /// assert!(!entry.wdm_prunes(&newer_and_prefix));
    /// assert!(newer_and_prefix.wdm_prunes(&entry));
    ///
    /// let newer_and_extension = Entry::prefilled_builder(&newer)
    ///     .path(Path::<4, 4, 4>::from_slices(&[b"a", b"b", b"c"])?).build().unwrap();
    /// assert!(!entry.wdm_prunes(&newer_and_extension));
    /// assert!(!newer_and_extension.wdm_prunes(&entry));
    ///
    /// let newer_but_unrelated_namespace = Entry::prefilled_builder(&newer)
    ///     .namespace_id("bookclub").build().unwrap();
    /// assert!(!entry.wdm_prunes(&newer_but_unrelated_namespace));
    /// assert!(!newer_but_unrelated_namespace.wdm_prunes(&entry));
    ///
    /// let newer_but_unrelated_subspace = Entry::prefilled_builder(&newer)
    ///     .subspace_id("betty").build().unwrap();
    /// assert!(!entry.wdm_prunes(&newer_but_unrelated_subspace));
    /// assert!(!newer_but_unrelated_subspace.wdm_prunes(&entry));
    /// # Ok::<(), PathError>(())
    /// ```
    ///
    fn wdm_prunes<OtherEntry>(&self, other: &OtherEntry) -> bool
    where
        OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
        N: PartialEq,
        S: PartialEq,
        PD: Ord,
    {
        self.wdm_is_newer_than(other)
            && self.wdm_namespace_id() == other.wdm_namespace_id()
            && self.wdm_subspace_id() == other.wdm_subspace_id()
            && self.wdm_path().is_prefix_of(other.wdm_path())
    }

    /// Returns whether this entry would be [prefix pruned](https://willowprotocol.org/specs/data-model/index.html#prefix_pruning) by another entry.
    ///
    /// Prefix pruning powers deletion in Willow: whenever a data store would contain two entries, one of which pruens the other, the other is removed from the data store (or never inserted in the first place). Informally speaking, newer entries remove older entries, but only if they are in the same namespace and subspace, and only if the path of the newer entry is a prefix of the path of the older entry.
    ///
    /// More precisely: an entry `e1` prunes an entry `e2` if and only if
    ///
    /// - `e1.namespace_id() == e2.namespace_id()`,
    /// - `e1.subspace_id() == e2.subspace_id()`,
    /// - `e1.path().is_prefix_of(e2.path())`, and
    /// - `e1.wdm_is_newer_than(&e2)`.
    ///
    /// This method is the reciprocal of [`EntrylikeExt::wdm_prunes`].
    ///
    /// # Examples
    ///
    ///
    /// ```
    /// use willow_data_model::prelude::*;
    ///
    /// let entry = Entry::builder()
    ///     .namespace_id("family")
    ///     .subspace_id("alfie")
    ///     .path(Path::<4, 4, 4>::from_slices(&[b"a", b"b"])?)
    ///     .timestamp(12345)
    ///     .payload_digest("b")
    ///     .payload_length(17)
    ///     .build().unwrap();
    ///
    /// let newer = Entry::prefilled_builder(&entry).timestamp(99999).build().unwrap();
    /// assert!(entry.wdm_is_pruned_by(&newer));
    /// assert!(!newer.wdm_is_pruned_by(&entry));
    ///
    /// let newer_and_prefix = Entry::prefilled_builder(&newer)
    ///     .path(Path::<4, 4, 4>::from_slices(&[b"a"])?).build().unwrap();
    /// assert!(entry.wdm_is_pruned_by(&newer_and_prefix));
    /// assert!(!newer_and_prefix.wdm_is_pruned_by(&entry));
    ///
    /// let newer_and_extension = Entry::prefilled_builder(&newer)
    ///     .path(Path::<4, 4, 4>::from_slices(&[b"a", b"b", b"c"])?).build().unwrap();
    /// assert!(!entry.wdm_is_pruned_by(&newer_and_extension));
    /// assert!(!newer_and_extension.wdm_is_pruned_by(&entry));
    ///
    /// let newer_but_unrelated_namespace = Entry::prefilled_builder(&newer)
    ///     .namespace_id("bookclub").build().unwrap();
    /// assert!(!entry.wdm_is_pruned_by(&newer_but_unrelated_namespace));
    /// assert!(!newer_but_unrelated_namespace.wdm_is_pruned_by(&entry));
    ///
    /// let newer_but_unrelated_subspace = Entry::prefilled_builder(&newer)
    ///     .subspace_id("betty").build().unwrap();
    /// assert!(!entry.wdm_is_pruned_by(&newer_but_unrelated_subspace));
    /// assert!(!newer_but_unrelated_subspace.wdm_is_pruned_by(&entry));
    /// # Ok::<(), PathError>(())
    /// ```
    ///
    fn wdm_is_pruned_by<OtherEntry>(&self, other: &OtherEntry) -> bool
    where
        OtherEntry: Entrylike<MCL, MCC, MPL, N, S, PD>,
        N: PartialEq,
        S: PartialEq,
        PD: Ord,
        Self: Sized,
    {
        other.wdm_prunes(self)
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, N, S, PD, E>
    EntrylikeExt<MCL, MCC, MPL, N, S, PD> for E
where
    E: Entrylike<MCL, MCC, MPL, N, S, PD>,
{
}