fayalite 0.2.0

// SPDX-License-Identifier: LGPL-3.0-or-later
// See Notices.txt for copyright information
#![allow(clippy::type_complexity)]
use crate::intern::type_map::TypeIdMap;
use bitvec::{ptr::BitPtr, slice::BitSlice, vec::BitVec};
use hashbrown::{hash_map::RawEntryMut, HashMap, HashTable};
use serde::{Deserialize, Serialize};
use std::{
    any::{Any, TypeId},
    borrow::{Borrow, Cow},
    cmp::Ordering,
    fmt,
    hash::{BuildHasher, Hash, Hasher},
    iter::FusedIterator,
    marker::PhantomData,
    ops::Deref,
    sync::{Mutex, RwLock},
};

pub mod type_map;

pub trait LazyInternedTrait<T: ?Sized + Send + Sync + 'static>: Send + Sync + Any {
    fn get(&self) -> Interned<T>;
}

impl<T: ?Sized + Send + Sync + 'static, F: ?Sized + Fn() -> Interned<T> + Send + Sync + Any>
    LazyInternedTrait<T> for F
{
    fn get(&self) -> Interned<T> {
        self()
    }
}

#[repr(transparent)]
pub struct LazyInternedFn<T: ?Sized + Send + Sync + 'static>(pub &'static dyn LazyInternedTrait<T>);

impl<T: ?Sized + Send + Sync + 'static> Copy for LazyInternedFn<T> {}

impl<T: ?Sized + Send + Sync + 'static> Clone for LazyInternedFn<T> {
    fn clone(&self) -> Self {
        *self
    }
}

impl<T: ?Sized + Send + Sync + 'static> Hash for LazyInternedFn<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.0.get_ptr_eq_with_type_id().hash(state);
    }
}

impl<T: ?Sized + Send + Sync + 'static> Eq for LazyInternedFn<T> {}

impl<T: ?Sized + Send + Sync + 'static> PartialEq for LazyInternedFn<T> {
    fn eq(&self, other: &Self) -> bool {
        self.0.get_ptr_eq_with_type_id() == other.0.get_ptr_eq_with_type_id()
    }
}

pub enum LazyInterned<T: ?Sized + Send + Sync + 'static> {
    Interned(Interned<T>),
    Lazy(LazyInternedFn<T>),
}

impl<T: ?Sized + Send + Sync + 'static> LazyInterned<T> {
    pub const fn new_lazy(v: &'static dyn LazyInternedTrait<T>) -> Self {
        Self::Lazy(LazyInternedFn(v))
    }
}

impl<T: ?Sized + Sync + Send + 'static> Clone for LazyInterned<T> {
    fn clone(&self) -> Self {
        *self
    }
}

impl<T: ?Sized + Sync + Send + 'static> Copy for LazyInterned<T> {}

impl<T: ?Sized + Sync + Send + 'static + Intern> Deref for LazyInterned<T> {
    type Target = T;

    fn deref(&self) -> &Self::Target {
        Interned::into_inner(self.interned())
    }
}

impl<T: ?Sized + Sync + Send + 'static + Intern> Eq for LazyInterned<T> where Interned<T>: Eq {}

impl<T: ?Sized + Sync + Send + 'static + Intern> PartialEq for LazyInterned<T>
where
    Interned<T>: PartialEq,
{
    fn eq(&self, other: &Self) -> bool {
        self.interned() == other.interned()
    }
}

impl<T: ?Sized + Sync + Send + 'static + Intern> Ord for LazyInterned<T>
where
    Interned<T>: Ord,
{
    fn cmp(&self, other: &Self) -> Ordering {
        self.interned().cmp(&other.interned())
    }
}

impl<T: ?Sized + Sync + Send + 'static + Intern> PartialOrd for LazyInterned<T>
where
    Interned<T>: PartialOrd,
{
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        self.interned().partial_cmp(&other.interned())
    }
}

impl<T: ?Sized + Sync + Send + 'static + Intern> Hash for LazyInterned<T>
where
    Interned<T>: Hash,
{
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.interned().hash(state);
    }
}

impl<T: ?Sized + Sync + Send + 'static> LazyInterned<T> {
    pub fn interned(self) -> Interned<T>
    where
        T: Intern,
    {
        struct MemoizeInterned<T: ?Sized + Intern>(PhantomData<T>);

        impl<T: ?Sized + Intern> Hash for MemoizeInterned<T> {
            fn hash<H: Hasher>(&self, _state: &mut H) {}
        }

        impl<T: ?Sized + Intern> PartialEq for MemoizeInterned<T> {
            fn eq(&self, _other: &Self) -> bool {
                true
            }
        }

        impl<T: ?Sized + Intern> Eq for MemoizeInterned<T> {}

        impl<T: ?Sized + Intern> Clone for MemoizeInterned<T> {
            fn clone(&self) -> Self {
                *self
            }
        }

        impl<T: ?Sized + Intern> Copy for MemoizeInterned<T> {}

        impl<T: ?Sized + Intern> MemoizeGeneric for MemoizeInterned<T> {
            type InputRef<'a> = LazyInternedFn<T>;

            type InputOwned = LazyInternedFn<T>;

            type InputCow<'a> = LazyInternedFn<T>;

            type Output = Interned<T>;

            fn input_eq(a: Self::InputRef<'_>, b: Self::InputRef<'_>) -> bool {
                a == b
            }

            fn input_borrow(input: &Self::InputOwned) -> Self::InputRef<'_> {
                *input
            }

            fn input_cow_into_owned(input: Self::InputCow<'_>) -> Self::InputOwned {
                input
            }

            fn input_cow_borrow<'a>(input: &'a Self::InputCow<'_>) -> Self::InputRef<'a> {
                *input
            }

            fn input_cow_from_owned<'a>(input: Self::InputOwned) -> Self::InputCow<'a> {
                input
            }

            fn input_cow_from_ref(input: Self::InputRef<'_>) -> Self::InputCow<'_> {
                input
            }

            fn inner(self, input: Self::InputRef<'_>) -> Self::Output {
                input.0.get()
            }
        }
        match self {
            Self::Interned(retval) => retval,
            Self::Lazy(retval) => MemoizeInterned(PhantomData).get(retval),
        }
    }
}

pub trait InternedCompare {
    type InternedCompareKey: Ord + Hash;
    fn interned_compare_key_ref(this: &Self) -> Self::InternedCompareKey;
}

/// Warning: doesn't do what you want with `T = dyn Trait`,
/// since it compares pointers, but pointers can be unequal due do
/// different copies of the same vtable
pub struct PtrEqWithMetadata<T: ?Sized>(pub *const T);

impl<T: ?Sized> Copy for PtrEqWithMetadata<T> {}

impl<T: ?Sized> Clone for PtrEqWithMetadata<T> {
    fn clone(&self) -> Self {
        *self
    }
}

impl<T: ?Sized> PartialEq for PtrEqWithMetadata<T> {
    fn eq(&self, other: &Self) -> bool {
        std::ptr::eq(self.0, other.0)
    }
}

impl<T: ?Sized> Eq for PtrEqWithMetadata<T> {}

impl<T: ?Sized> PartialOrd for PtrEqWithMetadata<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<T: ?Sized> Ord for PtrEqWithMetadata<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        #[allow(ambiguous_wide_pointer_comparisons)]
        self.0.cmp(&other.0)
    }
}

impl<T: ?Sized> Hash for PtrEqWithMetadata<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.0.hash(state);
    }
}

impl<T: ?Sized> fmt::Debug for PtrEqWithMetadata<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_tuple("PtrEqWithMetadata").field(&self.0).finish()
    }
}

/// Warning: doesn't do what you want for `[T]` or `str`, since it ignores length
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
pub struct PtrEqWithTypeId(pub *const (), pub TypeId);

mod sealed {
    pub trait SupportsPtrEqWithTypeIdSealed {}
}

pub trait SupportsPtrEqWithTypeId: 'static + sealed::SupportsPtrEqWithTypeIdSealed {
    fn get_ptr_eq_with_type_id(&self) -> PtrEqWithTypeId;
}

impl<T: 'static> sealed::SupportsPtrEqWithTypeIdSealed for T {}

impl<T: 'static> SupportsPtrEqWithTypeId for T {
    fn get_ptr_eq_with_type_id(&self) -> PtrEqWithTypeId {
        PtrEqWithTypeId(self as *const Self as *const (), TypeId::of::<Self>())
    }
}

impl<T> InternedCompare for T {
    type InternedCompareKey = PtrEqWithMetadata<Self>;
    fn interned_compare_key_ref(this: &Self) -> Self::InternedCompareKey {
        PtrEqWithMetadata(this)
    }
}

impl<T> InternedCompare for [T] {
    type InternedCompareKey = PtrEqWithMetadata<Self>;
    fn interned_compare_key_ref(this: &Self) -> Self::InternedCompareKey {
        PtrEqWithMetadata(this)
    }
}

#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct BitSlicePtrEq(BitPtr, usize);

impl InternedCompare for BitSlice {
    type InternedCompareKey = BitSlicePtrEq;
    fn interned_compare_key_ref(this: &Self) -> Self::InternedCompareKey {
        BitSlicePtrEq(this.as_bitptr(), this.len())
    }
}

impl InternedCompare for str {
    type InternedCompareKey = PtrEqWithMetadata<Self>;
    fn interned_compare_key_ref(this: &Self) -> Self::InternedCompareKey {
        PtrEqWithMetadata(this)
    }
}

pub trait Intern: Any + Send + Sync {
    fn intern(&self) -> Interned<Self>;
    fn intern_sized(self) -> Interned<Self>
    where
        Self: Clone,
    {
        Self::intern_owned(self)
    }
    fn intern_owned(this: <Self as ToOwned>::Owned) -> Interned<Self>
    where
        Self: ToOwned,
    {
        Self::intern_cow(Cow::Owned(this))
    }
    fn intern_cow(this: Cow<'_, Self>) -> Interned<Self>
    where
        Self: ToOwned,
    {
        this.intern()
    }
}

pub struct Interner<T: ?Sized + 'static + Send + Sync> {
    map: Mutex<HashMap<&'static T, ()>>,
}

impl<T: ?Sized + 'static + Send + Sync> Interner<T> {
    fn get() -> &'static Interner<T> {
        static TYPE_ID_MAP: TypeIdMap = TypeIdMap::new();
        TYPE_ID_MAP.get_or_insert_default()
    }
}

impl<T: ?Sized + 'static + Send + Sync> Default for Interner<T> {
    fn default() -> Self {
        Self {
            map: Default::default(),
        }
    }
}

impl<T: ?Sized + 'static + Send + Sync + Hash + Eq + ToOwned> Interner<T> {
    fn intern<F: FnOnce(Cow<'_, T>) -> &'static T>(
        &self,
        alloc: F,
        value: Cow<'_, T>,
    ) -> Interned<T> {
        let mut map = self.map.lock().unwrap();
        let hasher = map.hasher().clone();
        let hash = hasher.hash_one(&*value);
        let inner = match map.raw_entry_mut().from_hash(hash, |k| **k == *value) {
            RawEntryMut::Occupied(entry) => *entry.key(),
            RawEntryMut::Vacant(entry) => {
                *entry
                    .insert_with_hasher(hash, alloc(value), (), |k| hasher.hash_one(&**k))
                    .0
            }
        };
        Interned { inner }
    }
}

impl<T: Clone + 'static + Send + Sync + Hash + Eq> Interner<T> {
    fn intern_sized(&self, value: Cow<'_, T>) -> Interned<T> {
        self.intern(|value| Box::leak(Box::new(value.into_owned())), value)
    }
}

impl<T: Clone + 'static + Send + Sync + Hash + Eq> Interner<[T]> {
    fn intern_slice(&self, value: Cow<'_, [T]>) -> Interned<[T]> {
        self.intern(|value| value.into_owned().leak(), value)
    }
}

impl Interner<BitSlice> {
    fn intern_bit_slice(&self, value: Cow<'_, BitSlice>) -> Interned<BitSlice> {
        self.intern(|value| value.into_owned().leak(), value)
    }
}

impl Interner<str> {
    fn intern_str(&self, value: Cow<'_, str>) -> Interned<str> {
        self.intern(|value| value.into_owned().leak(), value)
    }
}

pub struct Interned<T: ?Sized + 'static + Send + Sync> {
    inner: &'static T,
}

macro_rules! forward_fmt_trait {
    ($Tr:ident) => {
        impl<T: ?Sized + Intern + fmt::$Tr> fmt::$Tr for LazyInterned<T> {
            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
                T::fmt(&**self, f)
            }
        }

        impl<T: ?Sized + 'static + Send + Sync + fmt::$Tr> fmt::$Tr for Interned<T> {
            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
                self.inner.fmt(f)
            }
        }
    };
}

forward_fmt_trait!(Debug);
forward_fmt_trait!(Display);
forward_fmt_trait!(LowerExp);
forward_fmt_trait!(LowerHex);
forward_fmt_trait!(Octal);
forward_fmt_trait!(Pointer);
forward_fmt_trait!(UpperExp);
forward_fmt_trait!(UpperHex);

#[derive(Clone, Debug)]
pub struct InternedSliceIter<T: Clone + 'static + Send + Sync> {
    slice: Interned<[T]>,
    index: std::ops::Range<usize>,
}

impl<T: Clone + 'static + Send + Sync> Iterator for InternedSliceIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.index.next().map(|index| self.slice[index].clone())
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.index.size_hint()
    }
}

impl<T: Clone + 'static + Send + Sync> DoubleEndedIterator for InternedSliceIter<T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.index
            .next_back()
            .map(|index| self.slice[index].clone())
    }
}

impl<T: Clone + 'static + Send + Sync> FusedIterator for InternedSliceIter<T> {}

impl<T: Clone + 'static + Send + Sync> ExactSizeIterator for InternedSliceIter<T> {}

impl<T: Clone + 'static + Send + Sync> IntoIterator for Interned<[T]> {
    type Item = T;
    type IntoIter = InternedSliceIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        InternedSliceIter {
            index: 0..self.len(),
            slice: self,
        }
    }
}

impl<'a, T: 'static + Send + Sync> IntoIterator for &'a Interned<[T]> {
    type Item = &'a T;
    type IntoIter = std::slice::Iter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.inner.iter()
    }
}

impl<'a, T: 'static + Send + Sync> IntoIterator for &'a mut Interned<[T]> {
    type Item = &'a T;
    type IntoIter = std::slice::Iter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.inner.iter()
    }
}

impl<I: Clone> FromIterator<I> for Interned<[I]>
where
    [I]: Intern,
{
    fn from_iter<T: IntoIterator<Item = I>>(iter: T) -> Self {
        Intern::intern_owned(Vec::from_iter(iter))
    }
}

impl<T: 'static + Clone + Send + Sync> From<Interned<[T]>> for Vec<T> {
    fn from(value: Interned<[T]>) -> Self {
        Vec::from(&*value)
    }
}

impl<T: 'static + Clone + Send + Sync> From<Interned<[T]>> for Box<[T]> {
    fn from(value: Interned<[T]>) -> Self {
        Box::from(&*value)
    }
}

impl From<Interned<str>> for String {
    fn from(value: Interned<str>) -> Self {
        String::from(&*value)
    }
}

impl<I> Default for Interned<[I]>
where
    [I]: Intern,
{
    fn default() -> Self {
        [][..].intern()
    }
}

impl Default for Interned<str> {
    fn default() -> Self {
        "".intern()
    }
}

impl Default for Interned<BitSlice> {
    fn default() -> Self {
        <&BitSlice>::default().intern()
    }
}

impl<I: Clone + Default> Default for Interned<I>
where
    I: Intern,
{
    fn default() -> Self {
        I::default().intern()
    }
}

impl<T: ?Sized + 'static + Send + Sync> Interned<T> {
    pub fn cast_unchecked<U: ?Sized + 'static + Send + Sync>(
        this: Self,
        f: impl FnOnce(&'static T) -> &'static U,
    ) -> Interned<U> {
        Interned {
            inner: f(this.inner),
        }
    }
    pub fn try_cast_unchecked<U: ?Sized + 'static + Send + Sync, E>(
        this: Self,
        f: impl FnOnce(&'static T) -> Result<&'static U, E>,
    ) -> Result<Interned<U>, E> {
        Ok(Interned {
            inner: f(this.inner)?,
        })
    }
    pub fn into_inner(this: Self) -> &'static T {
        this.inner
    }
    pub fn get_ref(this: &Self) -> &&'static T {
        &this.inner
    }
}

impl<T: ?Sized + 'static + Send + Sync> Clone for Interned<T> {
    fn clone(&self) -> Self {
        *self
    }
}

impl<T: ?Sized + 'static + Send + Sync> Copy for Interned<T> where &'static T: Copy {}

impl<T: ?Sized + 'static + Send + Sync> Deref for Interned<T>
where
    &'static T: Borrow<T>,
{
    type Target = T;

    fn deref(&self) -> &Self::Target {
        self.inner
    }
}

impl<T: ?Sized + 'static + Send + Sync + InternedCompare> PartialEq for Interned<T> {
    fn eq(&self, other: &Self) -> bool {
        T::interned_compare_key_ref(self.inner) == T::interned_compare_key_ref(other.inner)
    }
}

impl<T: ?Sized + 'static + Send + Sync + InternedCompare> Eq for Interned<T> {}

impl<T: ?Sized + 'static + Send + Sync + InternedCompare> PartialOrd for Interned<T> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<T: ?Sized + 'static + Send + Sync + InternedCompare> Ord for Interned<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        T::interned_compare_key_ref(self.inner).cmp(&T::interned_compare_key_ref(other.inner))
    }
}

impl<T: ?Sized + 'static + Send + Sync + InternedCompare> Hash for Interned<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        T::interned_compare_key_ref(self.inner).hash(state);
    }
}

impl<T: ?Sized + 'static + Send + Sync + Serialize> Serialize for Interned<T> {
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: serde::Serializer,
    {
        T::serialize(self, serializer)
    }
}

impl<'de, T: 'static + Send + Sync + Deserialize<'de> + Clone + Intern> Deserialize<'de>
    for Interned<T>
{
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        T::deserialize(deserializer).map(Intern::intern_sized)
    }
}

impl<'de, T: 'static + Send + Sync + Clone> Deserialize<'de> for Interned<[T]>
where
    [T]: Intern,
    Vec<T>: Deserialize<'de>,
{
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        Vec::<T>::deserialize(deserializer).map(Intern::intern_owned)
    }
}

impl<'de> Deserialize<'de> for Interned<BitSlice> {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        BitVec::deserialize(deserializer).map(Intern::intern_owned)
    }
}

impl<'de> Deserialize<'de> for Interned<str> {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        String::deserialize(deserializer).map(Intern::intern_owned)
    }
}

impl<T: Clone + Send + Sync + 'static + Hash + Eq> Intern for T {
    fn intern(&self) -> Interned<Self> {
        Self::intern_cow(Cow::Borrowed(self))
    }

    fn intern_owned(this: <Self as ToOwned>::Owned) -> Interned<Self>
    where
        Self: ToOwned,
    {
        Self::intern_cow(Cow::Owned(this))
    }

    fn intern_cow(this: Cow<'_, Self>) -> Interned<Self>
    where
        Self: ToOwned,
    {
        Interner::get().intern_sized(this)
    }
}

impl<T: Clone + Send + Sync + 'static + Hash + Eq> Intern for [T] {
    fn intern(&self) -> Interned<Self> {
        Self::intern_cow(Cow::Borrowed(self))
    }

    fn intern_owned(this: <Self as ToOwned>::Owned) -> Interned<Self>
    where
        Self: ToOwned,
    {
        Self::intern_cow(Cow::Owned(this))
    }

    fn intern_cow(this: Cow<'_, Self>) -> Interned<Self>
    where
        Self: ToOwned,
    {
        Interner::get().intern_slice(this)
    }
}

impl Intern for BitSlice {
    fn intern(&self) -> Interned<Self> {
        Self::intern_cow(Cow::Borrowed(self))
    }

    fn intern_owned(this: <Self as ToOwned>::Owned) -> Interned<Self>
    where
        Self: ToOwned,
    {
        Self::intern_cow(Cow::Owned(this))
    }

    fn intern_cow(this: Cow<'_, Self>) -> Interned<Self>
    where
        Self: ToOwned,
    {
        Interner::get().intern_bit_slice(this)
    }
}

impl Intern for str {
    fn intern(&self) -> Interned<Self> {
        Self::intern_cow(Cow::Borrowed(self))
    }

    fn intern_owned(this: <Self as ToOwned>::Owned) -> Interned<Self>
    where
        Self: ToOwned,
    {
        Self::intern_cow(Cow::Owned(this))
    }

    fn intern_cow(this: Cow<'_, Self>) -> Interned<Self>
    where
        Self: ToOwned,
    {
        Interner::get().intern_str(this)
    }
}

pub trait MemoizeGeneric: 'static + Send + Sync + Hash + Eq + Copy {
    type InputRef<'a>: 'a + Send + Sync + Hash + Copy;
    type InputOwned: 'static + Send + Sync;
    type InputCow<'a>: 'a;
    type Output: 'static + Send + Sync + Clone;
    fn input_eq(a: Self::InputRef<'_>, b: Self::InputRef<'_>) -> bool;
    fn input_borrow(input: &Self::InputOwned) -> Self::InputRef<'_>;
    fn input_cow_into_owned(input: Self::InputCow<'_>) -> Self::InputOwned;
    fn input_cow_borrow<'a>(input: &'a Self::InputCow<'_>) -> Self::InputRef<'a>;
    fn input_cow_from_owned<'a>(input: Self::InputOwned) -> Self::InputCow<'a>;
    fn input_cow_from_ref(input: Self::InputRef<'_>) -> Self::InputCow<'_>;
    fn inner(self, input: Self::InputRef<'_>) -> Self::Output;
    fn get_cow(self, input: Self::InputCow<'_>) -> Self::Output {
        static TYPE_ID_MAP: TypeIdMap = TypeIdMap::new();
        let map: &RwLock<(
            hashbrown::hash_map::DefaultHashBuilder,
            HashTable<(Self, Self::InputOwned, Self::Output)>,
        )> = TYPE_ID_MAP.get_or_insert_default();
        fn hash_eq_key<'a, 'b, T: MemoizeGeneric>(
            this: &'a T,
            input: T::InputRef<'b>,
        ) -> (&'a T, T::InputRef<'b>) {
            (this, input)
        }
        fn hash_eq_key_eq<T: MemoizeGeneric>(
            key: (&T, T::InputRef<'_>),
            this: &T,
            input: T::InputRef<'_>,
        ) -> bool {
            let other = hash_eq_key(this, input);
            key.0 == other.0 && T::input_eq(key.1, other.1)
        }
        let key = hash_eq_key(&self, Self::input_cow_borrow(&input));
        let hash;
        {
            let read = map.read().unwrap();
            let (hasher, map) = &*read;
            hash = hasher.hash_one(key);
            if let Some((_, _, output)) = map.find(hash, |(this2, input2, _)| {
                hash_eq_key_eq(key, this2, Self::input_borrow(input2))
            }) {
                return output.clone();
            }
            drop(read);
        }
        // make sure to call inner while map isn't locked since inner may call get_cow again
        let output = self.inner(Self::input_cow_borrow(&input));
        let mut write = map.write().unwrap();
        let (hasher, map) = &mut *write;
        map.entry(
            hash,
            |(this2, input2, _)| hash_eq_key_eq(key, this2, Self::input_borrow(input2)),
            |(this2, input2, _)| hasher.hash_one(hash_eq_key(this2, Self::input_borrow(input2))),
        )
        .or_insert_with(|| (self, Self::input_cow_into_owned(input), output))
        .get()
        .2
        .clone()
    }
    fn get_owned(self, input: Self::InputOwned) -> Self::Output {
        self.get_cow(Self::input_cow_from_owned(input))
    }
    fn get(self, input: Self::InputRef<'_>) -> Self::Output {
        self.get_cow(Self::input_cow_from_ref(input))
    }
}

pub trait Memoize: 'static + Send + Sync + Hash + Eq + Copy {
    type Input: ?Sized + 'static + Send + Sync + ToOwned<Owned = Self::InputOwned> + Hash + Eq;
    type InputOwned: 'static + Send + Sync + Borrow<Self::Input>;
    type Output: 'static + Send + Sync + Clone;
    fn inner(self, input: &Self::Input) -> Self::Output;
    fn get_cow(self, input: Cow<'_, Self::Input>) -> Self::Output {
        #[derive(Hash, Eq, PartialEq, Copy, Clone)]
        struct MemoizeGenericWrapper<T: Memoize>(T);
        impl<T: Memoize> MemoizeGeneric for MemoizeGenericWrapper<T> {
            type InputRef<'a> = &'a T::Input;
            type InputOwned = T::InputOwned;
            type InputCow<'a> = Cow<'a, T::Input>;
            type Output = T::Output;

            fn input_borrow(input: &Self::InputOwned) -> Self::InputRef<'_> {
                input.borrow()
            }

            fn input_eq(a: Self::InputRef<'_>, b: Self::InputRef<'_>) -> bool {
                a == b
            }

            fn input_cow_into_owned(input: Self::InputCow<'_>) -> Self::InputOwned {
                input.into_owned()
            }

            fn input_cow_borrow<'a>(input: &'a Self::InputCow<'_>) -> Self::InputRef<'a> {
                &**input
            }

            fn input_cow_from_owned<'a>(input: Self::InputOwned) -> Self::InputCow<'a> {
                Cow::Owned(input)
            }

            fn input_cow_from_ref(input: Self::InputRef<'_>) -> Self::InputCow<'_> {
                Cow::Borrowed(input)
            }

            fn inner(self, input: Self::InputRef<'_>) -> Self::Output {
                self.0.inner(input)
            }
        }

        MemoizeGenericWrapper(self).get_cow(input)
    }
    fn get_owned(self, input: Self::InputOwned) -> Self::Output {
        self.get_cow(Cow::Owned(input))
    }
    fn get(self, input: &Self::Input) -> Self::Output {
        self.get_cow(Cow::Borrowed(input))
    }
}