willow-data-model 0.7.0

//! Provides abstractions for [privately encoding areas relative to other areas](https://willowprotocol.org/specs/encodings/index.html#enc_private_areas) and [private interests](https://willowprotocol.org/specs/pio/index.html#pio_private_interests).
//!
//! You probably don't need to interact with this unless you are building your own private encoding scheme.

#[cfg(feature = "dev")]
use arbitrary::Arbitrary;
use compact_u64::{cu64_decode, cu64_encode, write_tag};
use derive_more::{Display, Error};
use ufotofu::ProducerExt;

use crate::entry::Entry;
use crate::groupings::{Area, TimeRange, subspace_includes_subspace};
use crate::is_bitflagged;
use crate::paths::Path;
use crate::paths::private::PrivatePathContext;
use crate::prelude::{Keylike, Namespaced};
use either::Either::Left;
use ufotofu::{
    codec::{Blame, Decodable, DecodeError, Encodable},
    codec_relative::{RelativeDecodable, RelativeEncodable},
};

/// Confidential data that relates to determining the [`AreaOfInterest`](crate::groupings::AreaOfInterest) that peers might be interested in synchronising.
/// 
/// [`AreaOfInterest`]: crate::groupings::AreaOfInterest
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
#[cfg_attr(feature = "dev", derive(Arbitrary))]
pub struct PrivateInterest<const MCL: usize, const MCC: usize, const MPL: usize, N, S> {
    namespace: N,
    subspace: Option<S>,
    path: Path<MCL, MCC, MPL>,
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, N, S>
    PrivateInterest<MCL, MCC, MPL, N, S>
{
    /// Returns a new [`PrivateInterest`] with the gives attributes.
    pub fn new(namespace_id: N, subspace_id: Option<S>, path: Path<MCL, MCC, MPL>) -> Self {
        Self {
            namespace: namespace_id,
            subspace: subspace_id,
            path,
        }
    }

    /// Returns the Namespace ID of this [`PrivateInterest`].
    pub fn namespace(&self) -> &N {
        &self.namespace
    }

    /// Returns the specific SubspaceId of this [`PrivateInterest`], if present. `None` denotes interest in all subspaces of the namespace.
    pub fn subspace(&self) -> Option<&S> {
        self.subspace.as_ref()
    }

    /// Returns the path of this [`PrivateInterest`].
    pub fn path(&self) -> &Path<MCL, MCC, MPL> {
        &self.path
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, N: PartialEq, S: PartialEq + Clone>
    PrivateInterest<MCL, MCC, MPL, N, S>
{
    /// Returns `true` is this [`PrivateInterest`] is [more specific](https://willowprotocol.org/specs/pio/index.html#pi_more_specific) than `other`.
    pub fn is_more_specific(&self, other: &Self) -> bool {
        self.namespace == other.namespace
            && subspace_includes_subspace(other.subspace(), self.subspace())
            && self.path.is_prefixed_by(&other.path)
    }

    /// Returns `true` is this [`PrivateInterest`] is [disjoint](https://willowprotocol.org/specs/pio/index.html#pi_disjoint) from `other`, namely that there is no [`Entry`] which can be included in both.
    pub fn is_disjoint(&self, other: &Self) -> bool {
        if self.namespace != other.namespace {
            return true;
        }

        if !subspace_includes_subspace(self.subspace(), other.subspace()) {
            return true;
        }

        if !self.path.is_related_to(&other.path) {
            return true;
        }

        false
    }

    /// Returns `true` is this [`PrivateInterest`] is [less specific](https://willowprotocol.org/specs/pio/index.html#pi_less_specific) than `other`.
    pub fn is_less_specific(&self, other: &Self) -> bool {
        other.is_more_specific(self)
    }

    /// Returns `true` is this [`PrivateInterest`] is [comparable](https://willowprotocol.org/specs/pio/index.html#pi_comparable) to `other`.
    pub fn is_comparable(&self, other: &Self) -> bool {
        self.is_more_specific(other) || self.is_less_specific(other)
    }

    /// Returns true if `self` and `other` are [awkward](https://willowprotocol.org/specs/pio/index.html#pi_awkward), meaning they are neither [comparable](https://willowprotocol.org/specs/pio/index.html#pi_comparable) nor [disjoint](https://willowprotocol.org/specs/pio/index.html#pi_disjoint).
    pub fn are_awkward(&self, other: &Self) -> bool {
        !self.is_comparable(other) && !self.is_disjoint(other)
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, N: PartialEq, S: PartialEq + Clone>
    PrivateInterest<MCL, MCC, MPL, N, S>
{
    /// Returns `true` if the given [`Entry`] is [included](https://willowprotocol.org/specs/pio/index.html#pi_include_entry) by `self`.
    pub fn includes_entry<PD>(&self, entry: &Entry<MCL, MCC, MPL, N, S, PD>) -> bool {
        &self.namespace == entry.wdm_namespace_id()
            && self
                .subspace()
                .map(|subspace_id| subspace_id == entry.wdm_subspace_id())
                .unwrap_or(true)
            && self.path.is_prefix_of(entry.wdm_path())
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, N, S: PartialEq + Clone>
    PrivateInterest<MCL, MCC, MPL, N, S>
{
    /// Returns `true` if the given [`Area`] in [included](https://willowprotocol.org/specs/pio/index.html#pi_include_area) by `self`.
    pub fn includes_area(&self, area: &Area<MCL, MCC, MPL, S>) -> bool {
        subspace_includes_subspace(self.subspace(), area.subspace())
            && self.path.is_prefix_of(area.path())
    }

    /// Returns `true` if the given [`Area`] is related to `self`, that is:
    ///
    /// - the path of `self` and the path of the `area` are [related](Path::is_related_to), and
    /// - either `self.subspace()` is `None` or `self.subspace() == area.subspace()`.
    pub fn is_related_to_area(&self, area: &Area<MCL, MCC, MPL, S>) -> bool {
        subspace_includes_subspace(self.subspace(), area.subspace())
            && self.path.is_related_to(area.path())
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, N, S: PartialEq>
    PrivateInterest<MCL, MCC, MPL, N, S>
{
    /// Returns `true` if `self` [almost includes](https://willowprotocol.org/specs/encodings/index.html#almost_include) the given [`Area`].
    pub fn almost_includes_area(&self, area: &Area<MCL, MCC, MPL, S>) -> bool {
        let subspace_is_fine = match (self.subspace(), area.subspace()) {
            (Some(self_id), Some(other_id)) => self_id == other_id,
            _ => true,
        };

        subspace_is_fine && self.path.is_related_to(area.path())
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, N: Clone, S: Clone>
    PrivateInterest<MCL, MCC, MPL, N, S>
{
    /// Clones self, but replaces the subspace id with `None`.
    pub fn relax(&self) -> Self {
        let mut cloned = self.clone();

        if self.subspace.is_some() {
            cloned.subspace = None;
        }

        cloned
    }
}

/// The immutable [`PrivateAreaContext`](https://willowprotocol.org/specs/encodings/index.html#PrivateAreaContext) necessary to privately encode an [`Area`] relative to another ][`Area`] which [almost includes](https://willowprotocol.org/specs/encodings/index.html#pi_amost_include) it.
#[derive(Clone, PartialEq, Eq, PartialOrd, Hash, Debug)]
#[cfg_attr(feature = "dev", derive(Arbitrary))]
pub struct PrivateAreaContext<const MCL: usize, const MCC: usize, const MPL: usize, N, S> {
    /// The [`PrivateInterest`] to be kept private.
    private: PrivateInterest<MCL, MCC, MPL, N, S>,
    /// The [almost including](https://willowprotocol.org/specs/encodings/index.html#almost_include) Area relative to which we encode.
    rel: Area<MCL, MCC, MPL, S>,
}

/// An error arising from trying to construct an invalid [`PrivateAreaContext`].
#[derive(Debug, Display, Clone, Copy, Error)]
#[display("area is not almost included")]
pub struct AreaNotAlmostIncludedError;

impl<const MCL: usize, const MCC: usize, const MPL: usize, N, S>
    PrivateAreaContext<MCL, MCC, MPL, N, S>
{
    /// Returns a new [`PrivateAreaContext`] with the given `private` and `rel` attributes. Will fail if the given [`PrivateInterest`]'s path is not a prefix of `rel`'s path.
    pub fn new(
        private: PrivateInterest<MCL, MCC, MPL, N, S>,
        rel: Area<MCL, MCC, MPL, S>,
    ) -> Result<Self, AreaNotAlmostIncludedError> {
        if !private.path.is_related_to(rel.path()) {
            return Err(AreaNotAlmostIncludedError);
        }

        Ok(Self { private, rel })
    }

    /// Returns the [`PrivateInterest`] of this [`PrivateAreaContext`].
    pub fn private(&self) -> &PrivateInterest<MCL, MCC, MPL, N, S> {
        &self.private
    }

    /// Returns the relative [`Area`] of this [`PrivateAreaContext`].
    pub fn rel(&self) -> &Area<MCL, MCC, MPL, S> {
        &self.rel
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, N, S: PartialEq>
    PrivateAreaContext<MCL, MCC, MPL, N, S>
{
    /// Returns whether an [`Area`] _almost includes_ another area, that is if the other [`Area`] would be included by this [`Area] if it had the same [`SubspaceId`].
    pub fn almost_includes_area(&self, other: &Area<MCL, MCC, MPL, S>) -> bool {
        let subspace_is_fine = match (self.rel.subspace(), other.subspace()) {
            (Some(self_id), Some(other_id)) => self_id == other_id,
            _ => true,
        };
        subspace_is_fine
            && self.rel.path().is_prefix_of(other.path())
            && self.rel.times().includes_willow_range(other.times())
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, N, S>
    RelativeEncodable<PrivateAreaContext<MCL, MCC, MPL, N, S>> for Area<MCL, MCC, MPL, S>
where
    S: PartialEq + Encodable,
{
    async fn relative_encode<C>(
        &self,
        rel: &PrivateAreaContext<MCL, MCC, MPL, N, S>,
        consumer: &mut C,
    ) -> Result<(), C::Error>
    where
        C: ufotofu::BulkConsumer<Item = u8> + ?Sized,
    {
        let (start_from_start, end_from_start) = match (rel.rel.times().end(), self.times().end()) {
            (None, None) => (true, false),
            (None, Some(_)) => (true, true),
            (Some(rel_end), None) => {
                let start_from_start = *self.times().start() - *rel.rel().times().start()
                    <= *rel_end - *self.times().start();

                (start_from_start, false)
            }
            (Some(rel_end), Some(val_end)) => {
                let start_from_start = *self.times().start() - *rel.rel().times().start()
                    <= *rel_end - *self.times().start();

                let end_from_start = *val_end - *rel.rel().times().start() <= *rel_end - *val_end;

                (start_from_start, end_from_start)
            }
        };

        let mut header: u8 = 0b0000_0000;

        if self.subspace() != rel.rel().subspace() {
            header |= 0b1000_0000;
        }

        if self.subspace().is_none() {
            header |= 0b0100_0000
        }

        if start_from_start {
            header |= 0b0010_0000
        }

        if end_from_start {
            header |= 0b0001_0000
        }

        let start_diff = match (rel.rel.times().end(), self.times().end()) {
            (None, None) => *self.times().start() - *rel.rel.times().start(),
            (None, Some(_)) => *self.times().start() - *rel.rel.times().start(),
            (Some(rel_end), None) => {
                let start_from_start_diff = *self.times().start() - *rel.rel().times().start();

                let start_from_end_diff = *rel_end - *self.times().start();

                if start_from_start_diff <= start_from_end_diff {
                    start_from_start_diff
                } else {
                    start_from_end_diff
                }
            }
            (Some(rel_end), Some(_)) => {
                let start_from_start_diff = *self.times().start() - *rel.rel().times().start();
                let start_from_end_diff = *rel_end - *self.times().start();

                if start_from_start_diff <= start_from_end_diff {
                    start_from_start_diff
                } else {
                    start_from_end_diff
                }
            }
        };

        compact_u64::write_tag(&mut header, 2, 4, start_diff.into());

        let end_diff = match (rel.rel.times().end(), self.times().end()) {
            (None, None) | (Some(_), None) => None,
            (None, Some(val_end)) => {
                let diff = *val_end - *rel.rel.times().start();
                compact_u64::write_tag(&mut header, 2, 6, diff.into());
                Some(diff)
            }
            (Some(rel_end), Some(val_end)) => {
                let end_from_start = *val_end - *rel.rel().times().start() <= *rel_end - *val_end;

                let diff = if end_from_start {
                    *val_end - *rel.rel.times().start()
                } else {
                    *rel_end - *val_end
                };

                write_tag(&mut header, 2, 6, diff.into());

                Some(diff)
            }
        };

        consumer.consume(Left(header)).await?;

        match (rel.rel().subspace(), self.subspace()) {
            (None, Some(id)) => {
                id.encode(consumer).await?;
            }
            (Some(rel_id), Some(id)) => {
                if rel_id != id {
                    id.encode(consumer).await?;
                }
            }
            _ => {}
        }

        cu64_encode(start_diff.into(), 2, consumer).await?;

        if let Some(end_diff) = end_diff {
            cu64_encode(end_diff.into(), 2, consumer).await?;
        }

        // We can use new_unchecked because we know the paths from the context is related to the area's path.
        debug_assert!(rel.private().path().is_related_to(rel.rel().path()));

        let private_path_context = unsafe {
            PrivatePathContext::new_unchecked(
                rel.private().path().clone(),
                rel.rel().path().clone(),
            )
        };

        self.path()
            .relative_encode(&private_path_context, consumer)
            .await?;

        Ok(())
    }

    /// Returns `false` when `self` is not [almost included by](https://willowprotocol.org/specs/encodings/index.html#almost_include) the relative [`PrivateAreaContext`].
    fn can_be_encoded_relative_to(&self, rel: &PrivateAreaContext<MCL, MCC, MPL, N, S>) -> bool {
        rel.almost_includes_area(self) && rel.private.almost_includes_area(self)
    }
}

impl<const MCL: usize, const MCC: usize, const MPL: usize, N, S>
    RelativeDecodable<PrivateAreaContext<MCL, MCC, MPL, N, S>> for Area<MCL, MCC, MPL, S>
where
    S: Clone + Decodable,
{
    type ErrorReason = Blame;

    async fn relative_decode<P>(
        rel: &PrivateAreaContext<MCL, MCC, MPL, N, S>,
        producer: &mut P,
    ) -> Result<Self, DecodeError<P::Final, P::Error, Self::ErrorReason>>
    where
        P: ufotofu::BulkProducer<Item = u8> + ?Sized,
        Self: Sized,
    {
        let header = producer.produce_item().await?;

        let is_subspace_not_equal = is_bitflagged(header, 0);
        let is_subspace_any = is_bitflagged(header, 1);
        let is_start_from_start = is_bitflagged(header, 2);
        let is_end_from_start = is_bitflagged(header, 3);

        let subspace = if !is_subspace_any && is_subspace_not_equal {
            let id = S::decode(producer)
                .await
                .map_err(|err| err.map_other(|_| Blame::TheirFault))?;

            Some(id)
        } else if is_subspace_any {
            None
        } else {
            rel.rel().subspace().cloned()
        };

        let start_diff = cu64_decode(header, 2, 4, producer)
            .await
            .map_err(|err| err.map_other(|_| Blame::TheirFault))?;

        let time_start = if is_start_from_start {
            start_diff
                .checked_add(u64::from(*rel.rel().times().start()))
                .ok_or(DecodeError::Other(Blame::TheirFault))?
        } else {
            match rel.rel().times().end() {
                Some(end) => u64::from(*end)
                    .checked_sub(start_diff)
                    .ok_or(DecodeError::Other(Blame::TheirFault))?,
                None => {
                    return Err(DecodeError::Other(Blame::TheirFault));
                }
            }
        };

        let is_time_end_open = match rel.rel.times().end() {
            Some(_) => false,
            None => !is_end_from_start,
        };

        let time_end = if is_time_end_open {
            None
        } else {
            let end_diff = cu64_decode(header, 2, 6, producer)
                .await
                .map_err(|err| err.map_other(|_| Blame::TheirFault))?;

            let end = if is_end_from_start {
                end_diff
                    .checked_add(u64::from(*rel.rel.times().start()))
                    .ok_or(DecodeError::Other(Blame::TheirFault))?
            } else {
                match rel.rel.times().end() {
                    Some(end) => u64::from(*end)
                        .checked_sub(end_diff)
                        .ok_or(DecodeError::Other(Blame::TheirFault))?,
                    None => {
                        return Err(DecodeError::Other(Blame::TheirFault));
                    }
                }
            };

            Some(end)
        };

        // We can use new_unchecked because we know the paths from the context is related to the area's path.
        debug_assert!(rel.private().path().is_related_to(rel.rel.path()));

        let private_path_context = unsafe {
            PrivatePathContext::new_unchecked(
                rel.private().path().clone(),
                rel.rel().path().clone(),
            )
        };

        let path = Path::relative_decode(&private_path_context, producer).await?;

        match time_end {
            Some(end) => {
                if time_start > end {
                    return Err(DecodeError::Other(Blame::TheirFault));
                }
                // We can do this we just rejected any case where time_start is strictly greater than end.
                let times =
                    unsafe { TimeRange::new_closed_unchecked(time_start.into(), end.into()) };

                Ok(Area::new(subspace, path, times))
            }
            None => {
                let times = TimeRange::new_open(time_start.into());

                Ok(Area::new(subspace, path, times))
            }
        }
    }
}