willow25 0.7.9

use core::cmp::Ordering;
use core::fmt::Debug;
use core::hash::Hash;
use core::ops::RangeBounds;

#[cfg(feature = "dev")]
use arbitrary::{Arbitrary, size_hint};

use compact_u64::*;
use ufotofu::codec_prelude::*;

use order_theory::GreatestElement;

use crate::{is_bitflagged, prelude::*};

/// An arbitrary non-empty box in three-dimensional willow space, consisting of a [`SubspaceRange`](super::SubspaceRange), a [`PathRange`](super::PathRange), and a [`TimeRange`](super::TimeRange).
///
/// As an application developer, you probably do not need to interact with 3d ranges, you should prefer [`Areas`](super::Area) — the latter work well with encrypted data, whereas 3d ranges do not define human-meaningful subsets of data when working with encryption.
///
/// ```
/// use willow25::prelude::*;
///
/// let r = Range3d::new(
///     SubspaceRange::full(),
///     PathRange::full(),
///     TimeRange::new_closed(0.into(), 17.into()),
/// );
///
/// assert!(r.includes(&([5; 32].into(), Path::new(), Timestamp::from(9))));
/// assert_eq!(r.subspaces(), &SubspaceRange::full());
///
/// let r2 = Range3d::new(
///     SubspaceRange::full(),
///     PathRange::full(),
///     TimeRange::new_open(15.into()),
/// );
/// assert_eq!(
///     r.intersection(&r2),
///     Ok(Range3d::new(
///         SubspaceRange::full(),
///         PathRange::full(),
///         TimeRange::new_closed(15.into(), 17.into()),
///     )),
/// );
/// ```
///
/// [Specification](https://willowprotocol.org/specs/grouping-entries/index.html#D3Range)
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Range3d {
    subspaces: SubspaceRange,
    paths: PathRange,
    times: TimeRange,
}

#[cfg(feature = "dev")]
impl<'a> Arbitrary<'a> for Range3d {
    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
        let subspaces = SubspaceRange::arbitrary(u)?;
        let paths = PathRange::arbitrary(u)?;
        let times = TimeRange::arbitrary(u)?;

        Ok(Self {
            subspaces,
            paths,
            times,
        })
    }

    fn try_size_hint(
        depth: usize,
    ) -> arbitrary::Result<(usize, Option<usize>), arbitrary::MaxRecursionReached> {
        Ok(size_hint::and_all(&[
            SubspaceRange::try_size_hint(depth)?,
            PathRange::try_size_hint(depth)?,
            TimeRange::try_size_hint(depth)?,
        ]))
    }
}

impl Grouping for Range3d {
    fn includes<Coord>(&self, coord: &Coord) -> bool
    where
        Coord: Coordinatelike + ?Sized,
    {
        self.times().includes_value(&coord.timestamp())
            && self.subspaces().includes_value(coord.subspace_id())
            && self.paths().includes_value(coord.path())
    }

    fn intersection(&self, other: &Self) -> Result<Self, EmptyGrouping> {
        Ok(Self {
            subspaces: self
                .subspaces()
                .intersection_willow_range(other.subspaces())?,
            paths: self.paths().intersection_willow_range(other.paths())?,
            times: self.times().intersection_willow_range(other.times())?,
        })
    }
}

/// A 3d-range is less than another iff all values included in the first are also included in the other.
impl PartialOrd<Self> for Range3d {
    /// A 3d-range is less than another iff all values included in the first are also included in the other.
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        let cmp_subspaces = self.subspaces().partial_cmp(other.subspaces())?;
        let cmp_paths = self.paths().partial_cmp(other.paths())?;
        let cmp_times = self.times().partial_cmp(other.times())?;

        if cmp_subspaces == Ordering::Equal
            && cmp_paths == Ordering::Equal
            && cmp_times == Ordering::Equal
        {
            Some(Ordering::Equal)
        } else if cmp_subspaces.is_le() && cmp_paths.is_le() && cmp_times.is_le() {
            Some(Ordering::Less)
        } else if cmp_subspaces.is_ge() && cmp_paths.is_ge() && cmp_times.is_ge() {
            Some(Ordering::Greater)
        } else {
            None
        }
    }
}

impl GreatestElement for Range3d {
    fn greatest() -> Self {
        Self::new(SubspaceRange::full(), PathRange::full(), TimeRange::full())
    }

    fn is_greatest(&self) -> bool {
        self.times().is_full() && self.subspaces().is_full() && self.paths().is_full()
    }
}

impl From<Area> for Range3d {
    fn from(value: Area) -> Self {
        let subspaces = match value.subspace() {
            None => WillowRange::full(),
            Some(s) => WillowRange::singleton(s.clone()),
        };

        let paths = match value.path().greater_but_not_prefixed() {
            Some(succ) => WillowRange::new_closed(value.path().clone(), succ),
            None => WillowRange::new_open(value.path().clone()),
        };

        Self::new(subspaces, paths, *value.times())
    }
}

impl RangeBounds<SubspaceId> for Range3d {
    fn start_bound(&self) -> core::ops::Bound<&SubspaceId> {
        self.subspaces().start_bound()
    }

    fn end_bound(&self) -> core::ops::Bound<&SubspaceId> {
        self.subspaces().end_bound()
    }
}

impl RangeBounds<Path> for Range3d {
    fn start_bound(&self) -> core::ops::Bound<&Path> {
        self.paths().start_bound().map(Into::into)
    }

    fn end_bound(&self) -> core::ops::Bound<&Path> {
        self.paths().end_bound().map(Into::into)
    }
}

impl RangeBounds<Timestamp> for Range3d {
    fn start_bound(&self) -> core::ops::Bound<&Timestamp> {
        self.times().start_bound()
    }

    fn end_bound(&self) -> core::ops::Bound<&Timestamp> {
        self.times().end_bound()
    }
}

impl Range3d {
    /// Creates a new `Range3d` from its constituent [`SubspaceRange`](super::SubspaceRange), [`PathRange`](super::PathRange), and [`TimeRange`](super::TimeRange).
    ///
    /// ```
    /// use willow25::prelude::*;
    ///
    /// let r = Range3d::new(
    ///     SubspaceRange::new_open([5; 32].into()),
    ///     PathRange::full(),
    ///     TimeRange::new_closed(0.into(), 17.into()),
    /// );
    ///
    /// assert!(r.includes(&([6; 32].into(), Path::new(), Timestamp::from(9))));
    /// assert_eq!(r.subspaces(), &SubspaceRange::new_open([5; 32].into()));
    /// ```
    pub fn new<SR, PR, TR>(subspaces: SR, paths: PR, times: TR) -> Self
    where
        SR: Into<SubspaceRange>,
        PR: Into<PathRange>,
        TR: Into<TimeRange>,
    {
        Self {
            subspaces: subspaces.into(),
            paths: paths.into(),
            times: times.into(),
        }
    }

    /// Returns a reference to the inner [`SubspaceRange`](super::SubspaceRange).
    ///
    /// ```
    /// use willow25::prelude::*;
    ///
    /// let r = Range3d::new(
    ///     SubspaceRange::new_open([5; 32].into()),
    ///     PathRange::full(),
    ///     TimeRange::new_closed(0.into(), 17.into()),
    /// );
    /// assert_eq!(r.subspaces(), &SubspaceRange::new_open([5; 32].into()));
    /// ```
    ///
    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#D3RangeSubspace).
    pub fn subspaces(&self) -> &SubspaceRange {
        &self.subspaces
    }

    /// Returns a reference to the inner [`PathRange`](super::PathRange).
    ///
    /// ```
    /// use willow25::prelude::*;
    ///
    /// let r = Range3d::new(
    ///     SubspaceRange::new_open([5; 32].into()),
    ///     PathRange::full(),
    ///     TimeRange::new_closed(0.into(), 17.into()),
    /// );
    /// assert_eq!(r.paths(), &WillowRange::full());
    /// ```
    ///
    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#D3RangePath).
    pub fn paths(&self) -> &PathRange {
        &self.paths
    }

    /// Returns a reference to the inner [`TimeRange`](super::TimeRange).
    ///
    /// ```
    /// use willow25::prelude::*;
    ///
    /// let r = Range3d::new(
    ///     SubspaceRange::new_open([5; 32].into()),
    ///     PathRange::full(),
    ///     TimeRange::new_closed(0.into(), 17.into()),
    /// );
    /// assert_eq!(r.times(), &TimeRange::new_closed(0.into(), 17.into()));
    /// ```
    ///
    /// [Definition](https://willowprotocol.org/specs/grouping-entries/index.html#D3RangeTime).
    pub fn times(&self) -> &TimeRange {
        &self.times
    }

    /// Sets the inner [`SubspaceRange`](super::SubspaceRange).
    pub fn set_subspaces<SR>(&mut self, new_range: SR)
    where
        SR: Into<SubspaceRange>,
    {
        self.subspaces = new_range.into();
    }

    /// Sets the inner [`PathRange`](super::PathRange).
    pub fn set_paths<PR>(&mut self, new_range: PR)
    where
        PR: Into<PathRange>,
    {
        self.paths = new_range.into();
    }

    /// Sets the inner [`TimeRange`](super::TimeRange).
    pub fn set_times<TR>(&mut self, new_range: TR)
    where
        TR: Into<TimeRange>,
    {
        self.times = new_range.into();
    }

    /// Returns the [`Range3d`] which [includes](Range3d::includes) `coord` but no other value.
    ///
    /// ```
    /// use willow25::prelude::*;
    ///
    /// let r = Range3d::singleton(&([5; 32].into(), Path::new(), Timestamp::from(9)));
    ///
    /// assert!(r.includes(&([5; 32].into(), Path::new(), Timestamp::from(9))));
    /// assert!(!r.includes(&([5; 32].into(), Path::new(), Timestamp::from(10))));
    /// ```
    pub fn singleton<Coord>(coord: &Coord) -> Self
    where
        Coord: Coordinatelike,
    {
        Self::new(
            SubspaceRange::singleton(coord.subspace_id().clone()),
            PathRange::singleton(coord.path().clone()),
            TimeRange::singleton(coord.timestamp()),
        )
    }

    /// Returns the `Range3d` which [includes](Range3d::includes) every [coordinate](Coordinatelike).
    ///
    /// ```
    /// use willow25::prelude::*;
    ///
    /// let r = Range3d::full();
    ///
    /// assert!(r.includes(&([5; 32].into(), Path::new(), Timestamp::from(9))));
    /// assert!(r.includes(&([5; 32].into(), Path::new(), Timestamp::from(10))));
    /// ```
    pub fn full() -> Self {
        Self::greatest()
    }

    /// Returns whether `self` is the full 3d range, i.e., the 3d range which [includes](Range3d::includes) every [coordinate](Coordinatelike).
    ///
    /// ```
    /// use willow25::prelude::*;
    ///
    /// assert!(Range3d::full().is_full());
    /// assert!(!Range3d::new(
    ///     SubspaceRange::full(),
    ///     PathRange::full(),
    ///     TimeRange::new_closed(0.into(), 17.into()),
    /// ).is_full());
    /// ```
    pub fn is_full(&self) -> bool {
        self.is_greatest()
    }
}

/// Implements [encode_3d_range](https://willowprotocol.org/specs/encodings/index.html#encode_3d_range).
impl Encodable for Range3d {
    async fn encode<C>(&self, consumer: &mut C) -> Result<(), C::Error>
    where
        C: BulkConsumer<Item = u8> + ?Sized,
    {
        let mut header = 0u8;

        write_tag(&mut header, 5, 3, u64::from(*self.times().start()));

        if self.subspaces().is_open() {
            header |= 0b1000_0000;
        }
        if self.paths().is_open() {
            header |= 0b0100_0000;
        }
        if self.times().is_open() {
            header |= 0b0010_0000;
        }

        consumer.consume_item(header).await?;

        consumer.consume_encoded(self.subspaces().start()).await?;
        if let Some(end) = self.subspaces().end() {
            consumer.consume_encoded(end).await?;
        }

        consumer.consume_encoded(self.paths().start()).await?;
        if let Some(end) = self.paths().end() {
            consumer
                .consume_relative_encoded(end, self.paths().start())
                .await?;
        }

        cu64_encode(u64::from(*self.times().start()), 5, consumer).await?;

        if let Some(end) = self.times().end() {
            cu64_encode_standalone(
                u64::from(*end) - (1 + u64::from(*self.times().start())),
                consumer,
            )
            .await?;
        }

        Ok(())
    }
}

/// Implements [encode_3d_range](https://willowprotocol.org/specs/encodings/index.html#encode_3d_range).
impl EncodableKnownLength for Range3d {
    fn len_of_encoding(&self) -> usize {
        let time_end_len = match self.times().end() {
            Some(end) => {
                1 + cu64_len_of_encoding(
                    8,
                    u64::from(*end) - (1 + u64::from(*self.times().start())),
                )
            }
            None => 0,
        };

        1 + self.subspaces.start().len_of_encoding()
            + self
                .subspaces
                .end()
                .map(|val| val.len_of_encoding())
                .unwrap_or(0)
            + self.paths.start().len_of_encoding()
            + self
                .paths
                .end()
                .map(|val| val.len_of_relative_encoding(self.paths.start()))
                .unwrap_or(0)
            + cu64_len_of_encoding(5, u64::from(*self.times().start()))
            + time_end_len
    }
}

/// Implements [Encode3dRange](https://willowprotocol.org/specs/encodings/index.html#Encode3dRange).
impl Decodable for Range3d {
    type ErrorReason = Blame;

    async fn decode<P>(
        producer: &mut P,
    ) -> Result<Self, DecodeError<P::Final, P::Error, Self::ErrorReason>>
    where
        P: BulkProducer<Item = u8> + ?Sized,
        Self: Sized,
    {
        let header = producer.produce_item().await?;

        // Skip end value of subspaces?
        let is_subspaces_end_open = is_bitflagged(header, 0);

        // Skip end value of paths?
        let is_paths_end_open = is_bitflagged(header, 1);

        // Skip end value of times?
        let is_times_end_open = is_bitflagged(header, 2);

        let subspaces_start = producer
            .produce_decoded()
            .await
            .map_err(|err| err.map_other_infallible())?;

        let subspaces_end: Option<SubspaceId> = if is_subspaces_end_open {
            None
        } else {
            Some(
                producer
                    .produce_decoded()
                    .await
                    .map_err(|err| err.map_other_infallible())?,
            )
        };

        let paths_start = producer.produce_decoded().await?;

        let paths_end: Option<Path> = if is_paths_end_open {
            None
        } else {
            Some(producer.produce_relative_decoded(&paths_start).await?)
        };

        let times_start = cu64_decode(header, 5, 3, producer)
            .await
            .map_err(|err| err.map_other_infallible())?;

        let times_end: Option<u64> = if is_times_end_open {
            None
        } else {
            let raw_end: u64 = cu64_decode_standalone(producer)
                .await
                .map_err(|err| err.map_other_infallible())?;

            Some(
                times_start
                    .checked_add(1)
                    .ok_or(DecodeError::Other(Blame::TheirFault))?
                    .checked_add(raw_end)
                    .ok_or(DecodeError::Other(Blame::TheirFault))?,
            )
        };

        Ok(Self {
            subspaces: SubspaceRange::try_new(subspaces_start, subspaces_end)
                .map_err(|_| DecodeError::Other(Blame::TheirFault))?,
            paths: PathRange::try_new(paths_start, paths_end)
                .map_err(|_| DecodeError::Other(Blame::TheirFault))?,
            times: TimeRange::try_new(Timestamp::from(times_start), times_end.map(Timestamp::from))
                .expect("decoding ensures range is nonempty"),
        })
    }
}

/// Implements [encode_3d_range](https://willowprotocol.org/specs/encodings/index.html#encode_3d_range).
impl DecodableCanonic for Range3d {
    type ErrorCanonic = Blame;

    async fn decode_canonic<P>(
        producer: &mut P,
    ) -> Result<Self, DecodeError<P::Final, P::Error, Self::ErrorCanonic>>
    where
        P: BulkProducer<Item = u8> + ?Sized,
        Self: Sized,
    {
        let header = producer.produce_item().await?;

        // Skip end value of subspaces?
        let is_subspaces_end_open = is_bitflagged(header, 0);

        // Skip end value of paths?
        let is_paths_end_open = is_bitflagged(header, 1);

        // Skip end value of times?
        let is_times_end_open = is_bitflagged(header, 2);

        let subspaces_start = producer
            .produce_decoded_canonic()
            .await
            .map_err(|err| err.map_other_infallible())?;

        let subspaces_end: Option<SubspaceId> = if is_subspaces_end_open {
            None
        } else {
            Some(
                producer
                    .produce_decoded_canonic()
                    .await
                    .map_err(|err| err.map_other_infallible())?,
            )
        };

        let paths_start = producer.produce_decoded_canonic().await?;

        let paths_end: Option<Path> = if is_paths_end_open {
            None
        } else {
            Some(
                producer
                    .produce_relative_decoded_canonic(&paths_start)
                    .await?,
            )
        };

        let times_start: u64 = cu64_decode_canonic(header, 5, 3, producer)
            .await
            .map_err(|err| err.map_other(|_| Blame::TheirFault))?;

        let times_end: Option<u64> = if is_times_end_open {
            None
        } else {
            let raw_end: u64 = cu64_decode_canonic_standalone(producer)
                .await
                .map_err(|err| err.map_other(|_| Blame::TheirFault))?;

            Some(
                times_start
                    .checked_add(1)
                    .ok_or(DecodeError::Other(Blame::TheirFault))?
                    .checked_add(raw_end)
                    .ok_or(DecodeError::Other(Blame::TheirFault))?,
            )
        };

        Ok(Self {
            subspaces: SubspaceRange::try_new(subspaces_start, subspaces_end)
                .map_err(|_| DecodeError::Other(Blame::TheirFault))?,
            paths: PathRange::try_new(paths_start, paths_end)
                .map_err(|_| DecodeError::Other(Blame::TheirFault))?,
            times: TimeRange::try_new(Timestamp::from(times_start), times_end.map(Timestamp::from))
                .expect("decoding ensures range is nonempty"),
        })
    }
}