amonoid/

borrowed.rs

use std::borrow::{Borrow, Cow};
use std::ffi::{OsStr, OsString};

use crate::Monoid;

/// A [`Borrow`] of a [`Monoid`].
///
/// This is a precursor to [`MonoidBorrowed`], hence the name.
///
/// This trait can be implemented when the assignment `Self -> Self::MonoidOwned` is unique,
/// but it doesn't require `Self: ToOwned`, so it can be implemented for every monoid
/// (not just for `M: Clone`).
///
/// Note that the `Self` type for this is what's _inside_ a reference,
/// not the reference itself. For example, this is implemented on `str`, not `&'a str`.
pub trait PreMonoidBorrowed {
	/// The owned equivalent of `Self`.
	type MonoidOwned: Monoid + Borrow<Self>;
}

/// The [`Borrow`]ed version of a [`Monoid`].
///
/// This has no `fn ident()` since that would return a new value,
/// which can't be borrowed from anywhere.
///
/// # Caution
/// The values `x: Self::MonoidOwned` and `x.borrow(): &Self` should behave identically,
/// as explained in the documentation of [`Borrow`].
///
/// In particular, this means that `combine_borrowed(a.borrow(), b.borrow()) == combine(a, b)` for all `a, b: Self::MonoidOwned`
/// and the analogous equalities for the other methods need to hold.
pub trait MonoidBorrowed: PreMonoidBorrowed {
	/// An implementation of [`Self::MonoidOwned::combine`](Monoid::combine) with borrowed values as inputs instead.
	fn combine_borrowed(&self, rhs: &Self) -> Self::MonoidOwned;

	/// An overridable method to provide some optimization based on knowledge of `Self::MonoidOwned`.
	///
	/// The default implementation just [`borrow`](Borrow::borrow)s `rhs`.
	#[inline]
	fn combine_left_borrowed(&self, rhs: Self::MonoidOwned) -> Self::MonoidOwned {
		self.combine_borrowed(rhs.borrow())
	}

	/// An overridable method to provide some optimization based on knowledge of `Self::MonoidOwned`.
	///
	/// The default implementation just [`borrow`](Borrow::borrow)s `lhs`.
	#[inline]
	fn combine_right_borrowed(lhs: Self::MonoidOwned, rhs: &Self) -> Self::MonoidOwned {
		lhs.borrow().combine_borrowed(rhs)
	}

	/// Like [`combine_left_borrowed`](Self::combine_left_borrowed), but assigns the result to `rhs`.
	fn combine_left_borrowed_assign_to(lhs: &Self, rhs: &mut Self::MonoidOwned) {
		*rhs = Self::combine_borrowed(lhs, (*rhs).borrow());
	}

	/// Like [`combine_right_borrowed`](Self::combine_right_borrowed), but assigns the result to `lhs`.
	fn combine_right_borrowed_assign(lhs: &mut Self::MonoidOwned, rhs: &Self) {
		*lhs = Self::combine_borrowed((*lhs).borrow(), rhs);
	}

	/// An overridable method to provide some optimization
	/// based on the fact that [`combine`](Monoid::combine) is associative.
	fn combine_iter_borrowed<'a, I: Iterator<Item = &'a Self>>(iter: I) -> Self::MonoidOwned
	where
		Self: 'a,
	{
		iter.fold(Monoid::ident(), Self::combine_right_borrowed)
	}

	/// An overridable method to provide some optimization based on
	/// (a) the fact that [`combine`](Monoid::combine) is associative
	/// and (b) knowledge of `Self::MonoidOwned`.
	fn combine_iter_cow<'a, I: Iterator<Item = Cow<'a, Self>>>(iter: I) -> Self::MonoidOwned
	where
		Self: 'a + ToOwned<Owned = Self::MonoidOwned>,
	{
		iter.reduce(Cow::combine)
			.map_or_else(Monoid::ident, Cow::into_owned)
	}
}

impl<M: Monoid> PreMonoidBorrowed for M {
	type MonoidOwned = Self;
}

impl<M: Monoid + Clone> MonoidBorrowed for M {
	fn combine_borrowed(&self, rhs: &Self) -> Self::MonoidOwned {
		self.clone().combine(rhs.clone())
	}

	fn combine_right_borrowed_assign(lhs: &mut Self::MonoidOwned, rhs: &Self) {
		lhs.combine_assign(rhs.clone())
	}

	fn combine_left_borrowed_assign_to(lhs: &Self, rhs: &mut Self::MonoidOwned) {
		lhs.clone().combine_assign_to(rhs)
	}
}

/// `Cow<M>` is essentially the same thing as `M`, just with a different memory representation.
impl<'a, M: 'a + ?Sized + MonoidBorrowed + ToOwned<Owned = M::MonoidOwned>> Monoid for Cow<'a, M> {
	#[inline]
	fn ident() -> Self {
		Cow::Owned(M::MonoidOwned::ident())
	}

	fn combine(self, rhs: Self) -> Self {
		Cow::Owned(match (self, rhs) {
			(Cow::Owned(lhs), Cow::Owned(rhs)) => lhs.combine(rhs),
			(Cow::Borrowed(lhs), Cow::Owned(rhs)) => lhs.combine_left_borrowed(rhs),
			(Cow::Owned(lhs), Cow::Borrowed(rhs)) => M::combine_right_borrowed(lhs, rhs),
			(Cow::Borrowed(lhs), Cow::Borrowed(rhs)) => lhs.combine_borrowed(rhs),
		})
	}

	fn combine_assign(&mut self, rhs: Self) {
		match (&mut *self, rhs) {
			(Cow::Owned(lhs), Cow::Owned(rhs)) => lhs.combine_assign(rhs),
			(Cow::Owned(lhs), Cow::Borrowed(rhs)) => M::combine_right_borrowed_assign(lhs, rhs),
			(Cow::Borrowed(lhs), rhs) => {
				*self = Cow::Owned(match rhs {
					Cow::Owned(rhs) => lhs.combine_left_borrowed(rhs),
					Cow::Borrowed(rhs) => lhs.combine_borrowed(rhs),
				});
			}
		}
	}

	fn combine_assign_to(self, rhs: &mut Self) {
		match (self, &mut *rhs) {
			(Cow::Owned(lhs), Cow::Owned(rhs)) => lhs.combine_assign_to(rhs),
			(Cow::Borrowed(lhs), Cow::Owned(rhs)) => M::combine_left_borrowed_assign_to(lhs, rhs),
			(lhs, Cow::Borrowed(r)) => {
				*rhs = Cow::Owned(match lhs {
					Cow::Owned(lhs) => M::combine_right_borrowed(lhs, r),
					Cow::Borrowed(lhs) => lhs.combine_borrowed(r),
				});
			}
		}
	}

	#[inline]
	fn combine_iter<I: Iterator<Item = Self>>(iter: I) -> Self {
		Cow::Owned(M::combine_iter_cow(iter))
	}
}

impl<T> PreMonoidBorrowed for [T] {
	type MonoidOwned = Vec<T>;
}

impl<T: Clone> MonoidBorrowed for [T] {
	#[inline]
	fn combine_borrowed(&self, rhs: &Self) -> Self::MonoidOwned {
		Self::combine_right_borrowed(self.to_vec(), rhs)
	}

	#[inline]
	fn combine_right_borrowed(mut lhs: Self::MonoidOwned, rhs: &Self) -> Self::MonoidOwned {
		lhs.extend_from_slice(rhs);
		lhs
	}

	#[inline]
	fn combine_right_borrowed_assign(lhs: &mut Self::MonoidOwned, rhs: &Self) {
		lhs.extend_from_slice(rhs);
	}
}

impl PreMonoidBorrowed for str {
	type MonoidOwned = String;
}

impl MonoidBorrowed for str {
	#[inline]
	fn combine_borrowed(&self, rhs: &Self) -> Self::MonoidOwned {
		self.to_string() + rhs
	}

	#[inline]
	fn combine_right_borrowed(lhs: Self::MonoidOwned, rhs: &Self) -> Self::MonoidOwned {
		lhs + rhs
	}

	#[inline]
	fn combine_right_borrowed_assign(lhs: &mut Self::MonoidOwned, rhs: &Self) {
		lhs.push_str(rhs);
	}

	#[inline]
	fn combine_iter_borrowed<'a, I: Iterator<Item = &'a Self>>(iter: I) -> Self::MonoidOwned {
		iter.collect()
	}

	#[inline]
	fn combine_iter_cow<'a, I: Iterator<Item = Cow<'a, Self>>>(iter: I) -> Self::MonoidOwned {
		iter.collect()
	}
}

impl PreMonoidBorrowed for OsStr {
	type MonoidOwned = OsString;
}

impl MonoidBorrowed for OsStr {
	#[inline]
	fn combine_borrowed(&self, rhs: &Self) -> Self::MonoidOwned {
		Self::combine_right_borrowed(self.to_os_string(), rhs)
	}

	#[inline]
	fn combine_right_borrowed(mut lhs: Self::MonoidOwned, rhs: &Self) -> Self::MonoidOwned {
		lhs.push(rhs);
		lhs
	}

	#[inline]
	fn combine_right_borrowed_assign(lhs: &mut Self::MonoidOwned, rhs: &Self) {
		lhs.push(rhs);
	}

	#[inline]
	fn combine_iter_borrowed<'a, I: Iterator<Item = &'a Self>>(iter: I) -> Self::MonoidOwned {
		iter.collect()
	}

	#[inline]
	fn combine_iter_cow<'a, I: Iterator<Item = Cow<'a, Self>>>(iter: I) -> Self::MonoidOwned {
		iter.collect()
	}
}