Mercurial > repos > alg_tools / file revision

/*!
Helper traits to work with references or owned values of types and their subsets.
*/

#[derive(Clone, Copy)]
pub enum EitherDecomp<A, B> {
    Owned(A),
    Borrowed(B),
}

/// A very basic implementation of [`std::borrow::Cow`] without a [`Clone`] trait dependency.
pub type MyCow<'b, X> = EitherDecomp<X, &'b X>;

impl<'b, X> std::ops::Deref for MyCow<'b, X> {
    type Target = X;

    #[inline]
    fn deref(&self) -> &Self::Target {
        match self {
            EitherDecomp::Owned(x) => &x,
            EitherDecomp::Borrowed(x) => x,
        }
    }
}

/// Trait for ownable-by-consumption objects
pub trait Ownable {
    type OwnedVariant: Clone;

    /// Returns an owned instance, possibly consuming the original,
    /// avoiding cloning when possible.
    fn into_owned(self) -> Self::OwnedVariant;

    /// Returns an owned instance of a reference.
    fn clone_owned(&self) -> Self::OwnedVariant;
}

impl<'a, X: Ownable> Ownable for &'a X {
    type OwnedVariant = X::OwnedVariant;

    #[inline]
    /// Returns an owned instance.
    fn into_owned(self) -> Self::OwnedVariant {
        self.clone_owned()
    }

    #[inline]
    /// Returns an owned instance.
    fn clone_owned(&self) -> Self::OwnedVariant {
        (*self).into_owned()
    }
}

impl<'a, X: Ownable> Ownable for &'a mut X {
    type OwnedVariant = X::OwnedVariant;

    #[inline]
    /// Returns an owned instance.
    fn into_owned(self) -> Self::OwnedVariant {
        self.clone_owned()
    }

    #[inline]
    /// Returns an owned instance.
    fn clone_owned(&self) -> Self::OwnedVariant {
        (&**self).into_owned()
    }
}

impl<'a, X: Ownable> Ownable for MyCow<'a, X> {
    type OwnedVariant = X::OwnedVariant;

    #[inline]
    /// Returns an owned instance.
    fn into_owned(self) -> Self::OwnedVariant {
        match self {
            EitherDecomp::Owned(x) => x.into_owned(),
            EitherDecomp::Borrowed(x) => x.into_owned(),
        }
    }

    #[inline]
    /// Returns an owned instance.
    fn clone_owned(&self) -> Self::OwnedVariant {
        match self {
            EitherDecomp::Owned(x) => x.into_owned(),
            EitherDecomp::Borrowed(x) => x.into_owned(),
        }
    }
}

/// Trait for abitrary mathematical spaces.
pub trait Space: Ownable<OwnedVariant = Self::OwnedSpace> + Sized {
    type OwnedSpace: ClosedSpace;

    /// Default decomposition for the space
    type Decomp: Decomposition<Self>;
}

mod private {
    pub trait Sealed {}
}

/// Helper trait for working with own types.
pub trait Owned: Ownable<OwnedVariant = Self> + private::Sealed {}
impl<X: Ownable<OwnedVariant = X>> private::Sealed for X {}
impl<X: Ownable<OwnedVariant = X>> Owned for X {}

/// Helper trait for working with closed spaces, operations in which should
/// return members of the same space
pub trait ClosedSpace: Space<OwnedSpace = Self> + Owned + Instance<Self> {}
impl<X: Space<OwnedSpace = Self> + Owned + Instance<Self>> ClosedSpace for X {}

#[macro_export]
macro_rules! impl_basic_space {
    ($($type:ty)*) => {
        $( $crate::impl_basic_space!($type where ); )*
    };
    ($type:ty where $($where:tt)*) => {
        impl<$($where)*> $crate::instance::Space for $type {
            type OwnedSpace = Self;
            type Decomp = $crate::instance::BasicDecomposition;
        }

        impl<$($where)*> $crate::instance::Ownable for $type {
            type OwnedVariant = Self;

            #[inline]
            fn into_owned(self) -> Self::OwnedVariant {
                self
            }

            #[inline]
            fn clone_owned(&self) -> Self::OwnedVariant {
                *self
            }
        }
    };
}

impl_basic_space!(u8 u16 u32 u64 u128 usize
                  i8 i16 i32 i64 i128 isize
                  f32 f64);

/// Marker type for decompositions to be used with [`Instance`].
pub trait Decomposition<X: Space>: Sized {
    /// Owned instance
    type OwnedInstance: Instance<X, Self>;

    /// Possibly owned form of the decomposition
    type Decomposition<'b>: Instance<X, Self>
    where
        X: 'b;
    /// Unlikely owned form of the decomposition.
    /// Type for a lightweight intermediate conversion that does not own the original variable.
    /// Usually this is just a reference, but may also be a lightweight structure that
    /// contains references; see the implementation for [`crate::direct_product::Pair`].
    type Reference<'b>: Instance<X, Self> + Copy
    where
        X: 'b;

    /// Lift the lightweight reference type into a full decomposition type.
    fn lift<'b>(r: Self::Reference<'b>) -> Self::Decomposition<'b>;

    // /// Lift the lightweight reference type into a fully owned type
    // fn full_lift<'b>(r: Self::Reference<'b>) -> Self::OwnedInstance;
}

/// Most common [`Decomposition`] (into `Either<X, &'b X>`) that allows working with owned
/// values and all sorts of references.
#[derive(Copy, Clone, Debug)]
pub struct BasicDecomposition;

impl<X: Space + Clone> Decomposition<X> for BasicDecomposition {
    type OwnedInstance = X;

    type Decomposition<'b>
        = MyCow<'b, X>
    where
        X: 'b;
    type Reference<'b>
        = &'b X
    where
        X: 'b;

    #[inline]
    fn lift<'b>(r: Self::Reference<'b>) -> Self::Decomposition<'b> {
        MyCow::Borrowed(r)
    }
}

/// Helper trait for functions to work with either owned values or references to either the
/// “principal type” `X` or types some present a subset of `X`. In the latter sense, this
/// generalises [`std::borrow::ToOwned`], [`std::borrow::Borrow`], and [`std::borrow::Cow`].
///
/// This is used, for example, by [`crate::mapping::Mapping::apply`].
pub trait Instance<X, D = <X as Space>::Decomp>:
    Sized + Ownable<OwnedVariant = X::OwnedSpace>
where
    X: Space,
    D: Decomposition<X>,
{
    /// Decomposes self according to `decomposer`, and evaluate `f` on the result.
    /// Consumes self.
    fn eval_decompose<'b, R>(self, f: impl FnOnce(D::Decomposition<'b>) -> R) -> R
    where
        X: 'b,
        Self: 'b;

    /// Does a light decomposition of self `decomposer`, and evaluates `f` on the result.
    /// Does not consume self.
    fn eval_ref_decompose<'b, R>(&'b self, f: impl FnOnce(D::Reference<'b>) -> R) -> R
    where
        X: 'b,
        Self: 'b;

    /// Returns an owned instance of `X`, cloning or converting non-true instances when necessary.
    fn own(self) -> D::OwnedInstance;

    // ************** automatically implemented methods below from here **************

    /// Returns an owned instance or reference to `X`, converting non-true instances when necessary.
    ///
    /// Default implementation uses [`Self::own`]. Consumes the input.
    fn cow<'b>(self) -> MyCow<'b, D::OwnedInstance>
    where
        Self: 'b,
    {
        MyCow::Owned(self.own())
    }

    #[inline]
    /// Evaluates `f` on a reference to self.
    ///
    /// Default implementation uses [`Self::cow`]. Consumes the input.
    fn eval<'b, R>(self, f: impl FnOnce(&D::OwnedInstance) -> R) -> R
    where
        X: 'b,
        Self: 'b,
    {
        f(&*self.cow())
    }

    #[inline]
    /// Evaluates `f` or `g` depending on whether a reference or owned value is available.
    ///
    /// Default implementation uses [`Self::cow`]. Consumes the input.
    fn either<'b, R>(
        self,
        f: impl FnOnce(D::OwnedInstance) -> R,
        g: impl FnOnce(&D::OwnedInstance) -> R,
    ) -> R
    where
        Self: 'b,
    {
        match self.cow() {
            EitherDecomp::Owned(x) => f(x),
            EitherDecomp::Borrowed(x) => g(x),
        }
    }
}

impl<X: Space + Clone> Instance<X, BasicDecomposition> for X {
    #[inline]
    fn eval_decompose<'b, R>(self, f: impl FnOnce(MyCow<'b, X>) -> R) -> R
    where
        X: 'b,
        Self: 'b,
    {
        f(MyCow::Owned(self))
    }

    #[inline]
    fn eval_ref_decompose<'b, R>(&'b self, f: impl FnOnce(&'b X) -> R) -> R
    where
        X: 'b,
        Self: 'b,
    {
        f(self)
    }

    #[inline]
    fn own(self) -> X {
        self
    }

    #[inline]
    fn cow<'b>(self) -> MyCow<'b, X>
    where
        Self: 'b,
    {
        MyCow::Owned(self)
    }
}

impl<'a, X: Space + Clone> Instance<X, BasicDecomposition> for &'a X {
    #[inline]
    fn eval_decompose<'b, R>(self, f: impl FnOnce(MyCow<'b, X>) -> R) -> R
    where
        X: 'b,
        Self: 'b,
    {
        f(MyCow::Borrowed(self))
    }

    #[inline]
    fn eval_ref_decompose<'b, R>(&'b self, f: impl FnOnce(&'b X) -> R) -> R
    where
        X: 'b,
        Self: 'b,
    {
        f(*self)
    }

    #[inline]
    fn own(self) -> X {
        self.clone()
    }

    #[inline]
    fn cow<'b>(self) -> MyCow<'b, X>
    where
        Self: 'b,
    {
        MyCow::Borrowed(self)
    }
}

impl<'a, X: Space + Clone> Instance<X, BasicDecomposition> for &'a mut X {
    #[inline]
    fn eval_decompose<'b, R>(self, f: impl FnOnce(MyCow<'b, X>) -> R) -> R
    where
        X: 'b,
        Self: 'b,
    {
        f(EitherDecomp::Borrowed(self))
    }

    #[inline]
    fn eval_ref_decompose<'b, R>(&'b self, f: impl FnOnce(&'b X) -> R) -> R
    where
        X: 'b,
        Self: 'b,
    {
        f(*self)
    }

    #[inline]
    fn own(self) -> X {
        self.clone()
    }

    #[inline]
    fn cow<'b>(self) -> MyCow<'b, X>
    where
        Self: 'b,
    {
        EitherDecomp::Borrowed(self)
    }
}

impl<'a, X: Space + Clone> Instance<X, BasicDecomposition> for MyCow<'a, X> {
    #[inline]
    fn eval_decompose<'b, R>(self, f: impl FnOnce(MyCow<'b, X>) -> R) -> R
    where
        X: 'b,
        Self: 'b,
    {
        f(self)
    }

    #[inline]
    fn eval_ref_decompose<'b, R>(&'b self, f: impl FnOnce(&'b X) -> R) -> R
    where
        X: 'b,
        Self: 'b,
    {
        match self {
            MyCow::Borrowed(a) => f(a),
            MyCow::Owned(b) => f(&b),
        }
    }

    #[inline]
    fn own(self) -> X {
        match self {
            MyCow::Borrowed(a) => a.own(),
            MyCow::Owned(b) => b.own(),
        }
    }

    #[inline]
    fn cow<'b>(self) -> MyCow<'b, X>
    where
        Self: 'b,
    {
        match self {
            MyCow::Borrowed(a) => a.cow(),
            MyCow::Owned(b) => b.cow(),
        }
    }
}

/// Marker type for mutable decompositions to be used with [`InstanceMut`].
pub trait DecompositionMut<X: Space>: Sized {
    type ReferenceMut<'b>: InstanceMut<X, Self>
    where
        X: 'b;
}

/// Helper trait for functions to work with mutable references.
pub trait InstanceMut<X: Space, D = <X as Space>::Decomp>: Sized
where
    D: DecompositionMut<X>,
{
    /// Returns a mutable decomposition of self.
    fn ref_instance_mut(&mut self) -> D::ReferenceMut<'_>;
}

impl<X: Space> DecompositionMut<X> for BasicDecomposition {
    type ReferenceMut<'b>
        = &'b mut X
    where
        X: 'b;
}

/// This impl may seem pointless, but allows throwaway mutable scratch variables
impl<'a, X: Space> InstanceMut<X, BasicDecomposition> for X {
    #[inline]
    fn ref_instance_mut(
        &mut self,
    ) -> <BasicDecomposition as DecompositionMut<X>>::ReferenceMut<'_> {
        self
    }
}

impl<'a, X: Space> InstanceMut<X, BasicDecomposition> for &'a mut X {
    #[inline]
    fn ref_instance_mut(
        &mut self,
    ) -> <BasicDecomposition as DecompositionMut<X>>::ReferenceMut<'_> {
        self
    }
}