blazinterner 0.4.1

#[cfg(feature = "serde")]
use super::U32Visitor;
use appendvec::AppendVec;
use dashtable::DashTable;
#[cfg(feature = "get-size2")]
use get_size2::{GetSize, GetSizeTracker};
use hashbrown::DefaultHashBuilder;
#[cfg(feature = "serde")]
use serde::de::{Error, SeqAccess, Visitor};
#[cfg(feature = "serde")]
use serde::ser::{SerializeSeq, SerializeTuple};
#[cfg(feature = "serde")]
use serde::{Deserialize, Deserializer, Serialize, Serializer};
#[cfg(feature = "serde")]
use serde_tuple::{Deserialize_tuple, Serialize_tuple};
use std::borrow::Borrow;
#[cfg(feature = "serde")]
use std::cell::Cell;
use std::cmp::Ordering;
use std::fmt::Debug;
use std::hash::{BuildHasher, Hash, Hasher};
use std::marker::PhantomData;
use std::ops::Range;
#[cfg(feature = "debug")]
use std::sync::atomic::{self, AtomicUsize};

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[cfg_attr(feature = "serde", derive(Serialize_tuple, Deserialize_tuple))]
pub struct CopyRangeU32 {
    pub start: u32,
    pub end: u32,
}

impl From<Range<u32>> for CopyRangeU32 {
    fn from(other: Range<u32>) -> Self {
        CopyRangeU32 {
            start: other.start,
            end: other.end,
        }
    }
}

impl From<CopyRangeU32> for Range<u32> {
    fn from(other: CopyRangeU32) -> Self {
        other.start..other.end
    }
}

/// A handle to an interned value in an [`ArenaSlice`].
pub struct InternedSlice<T> {
    id: u32,
    _phantom: PhantomData<fn() -> *const T>,
}

impl<T> Default for InternedSlice<T> {
    fn default() -> Self {
        Self::new(u32::MAX)
    }
}

impl<T> Debug for InternedSlice<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_tuple("I").field(&self.id).finish()
    }
}

impl<T> Clone for InternedSlice<T> {
    fn clone(&self) -> Self {
        *self
    }
}

impl<T> Copy for InternedSlice<T> {}

impl<T> PartialEq for InternedSlice<T> {
    fn eq(&self, other: &Self) -> bool {
        self.id.eq(&other.id)
    }
}

impl<T> Eq for InternedSlice<T> {}

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

impl<T> Ord for InternedSlice<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.id.cmp(&other.id)
    }
}

impl<T> Hash for InternedSlice<T> {
    fn hash<H>(&self, state: &mut H)
    where
        H: Hasher,
    {
        self.id.hash(state);
    }
}

#[cfg(feature = "get-size2")]
impl<T> GetSize for InternedSlice<T> {
    // There is nothing on the heap, so the default implementation works out of the
    // box.
}

#[cfg(feature = "raw")]
impl<T> InternedSlice<T> {
    /// Creates an interned value for the given index.
    ///
    /// This is a low-level function. You should instead use the
    /// [`ArenaSlice::intern()`] API to intern a value, unless you really know
    /// what you're doing.
    pub fn from_id(id: u32) -> Self {
        Self::new(id)
    }

    /// Obtains the underlying interning index.
    ///
    /// This is a low-level function. You should instead use the
    /// [`ArenaSlice::lookup()`] API, unless you really know what you're doing.
    pub fn id(&self) -> u32 {
        self.id
    }
}

impl<T> InternedSlice<T> {
    pub(crate) fn new(id: u32) -> Self {
        Self {
            id,
            _phantom: PhantomData,
        }
    }

    pub(crate) fn id_(&self) -> u32 {
        self.id
    }
}

#[cfg(feature = "serde")]
impl<T> Serialize for InternedSlice<T> {
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        serializer.serialize_u32(self.id)
    }
}

#[cfg(feature = "serde")]
impl<'de, T> Deserialize<'de> for InternedSlice<T> {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: Deserializer<'de>,
    {
        let id = deserializer.deserialize_u32(U32Visitor)?;
        Ok(Self {
            id,
            _phantom: PhantomData,
        })
    }
}

struct RangeVec<T> {
    vec: AppendVec<T>,
    ranges: AppendVec<CopyRangeU32>,
}

impl<T> RangeVec<T> {
    fn lookup_slice(&self, id: u32) -> &[T] {
        let range = self.ranges[id as usize];
        let range = range.start as usize..range.end as usize;
        &self.vec[range]
    }

    fn iter(&self) -> impl ExactSizeIterator<Item = &[T]> {
        self.ranges
            .iter()
            .map(|&range| &self.vec[range.start as usize..range.end as usize])
    }

    fn push_range(&self, range: Range<usize>) -> u32 {
        assert!(range.start <= u32::MAX as usize);
        assert!(range.end <= u32::MAX as usize);
        let range = range.start as u32..range.end as u32;

        let id = self.ranges.push(range.into());
        assert!(id <= u32::MAX as usize);
        id as u32
    }

    fn push_range_mut(&mut self, range: Range<usize>) -> u32 {
        assert!(range.start <= u32::MAX as usize);
        assert!(range.end <= u32::MAX as usize);
        let range = range.start as u32..range.end as u32;

        let id = self.ranges.push_mut(range.into());
        assert!(id <= u32::MAX as usize);
        id as u32
    }
}

/// Interning arena for slices of type `T`.
pub struct ArenaSlice<T> {
    rangevec: RangeVec<T>,
    map: DashTable<u32>,
    hasher: DefaultHashBuilder,
    #[cfg(feature = "debug")]
    references: AtomicUsize,
}

impl<T> Clone for ArenaSlice<T>
where
    T: Default + Clone + Eq + Hash,
{
    fn clone(&self) -> Self {
        let iter = self.iter_();
        let mut arena = Self::with_capacity(iter.len(), self.items());
        for slice in iter {
            arena.push(slice);
        }
        arena
    }
}

impl<T> ArenaSlice<T> {
    /// Creates a new arena with pre-allocated space to store at least the given
    /// number of slices, totalling the given number of items of type `T`.
    pub fn with_capacity(slices: usize, items: usize) -> Self {
        Self {
            rangevec: RangeVec {
                vec: AppendVec::with_capacity(items),
                ranges: AppendVec::with_capacity(slices),
            },
            map: DashTable::with_capacity(slices),
            hasher: DefaultHashBuilder::default(),
            #[cfg(feature = "debug")]
            references: AtomicUsize::new(0),
        }
    }

    /// Returns the number of slices in this arena.
    ///
    /// Note that because [`ArenaSlice`] is a concurrent data structure, this is
    /// only a snapshot as viewed by this thread, and the result may change
    /// if other threads are inserting values.
    pub fn slices(&self) -> usize {
        self.rangevec.ranges.len()
    }

    /// Returns the total number of items of type `T` in this arena.
    ///
    /// Note that because [`ArenaSlice`] is a concurrent data structure, this is
    /// only a snapshot as viewed by this thread, and the result may change
    /// if other threads are inserting values.
    pub fn items(&self) -> usize {
        self.rangevec.vec.len()
    }

    /// Checks if this arena is empty.
    ///
    /// Note that because [`ArenaSlice`] is a concurrent data structure, this is
    /// only a snapshot as viewed by this thread, and the result may change
    /// if other threads are inserting values.
    pub fn is_empty(&self) -> bool {
        self.slices() == 0
    }

    /// Returns an iterator over all slices in this arena, in indexing order.
    ///
    /// Note that because [`ArenaSlice`] is a concurrent data structure, this is
    /// only a snapshot. Once this iterator has been created, for performance
    /// reasons it will not iterate over items added afterwards, even on the
    /// same thread.
    #[cfg(feature = "raw")]
    pub fn iter(&self) -> impl ExactSizeIterator<Item = &[T]> {
        self.rangevec.iter()
    }

    fn iter_(&self) -> impl ExactSizeIterator<Item = &[T]> {
        self.rangevec.iter()
    }
}

impl<T> ArenaSlice<T>
where
    T: Eq + Hash,
{
    /// Returns the given value's [`InternedSlice`] handle if it is already
    /// interned.
    ///
    /// Otherwise, this simply returns [`None`] without adding the value to this
    /// arena.
    pub fn find(&self, value: &[T]) -> Option<InternedSlice<T>> {
        let hash = self.hash_slice(value);
        self.map
            .find(hash, |&i| self.lookup_slice(i) == value)
            .map(|id| InternedSlice {
                id: *id,
                _phantom: PhantomData,
            })
    }
}

impl<T> ArenaSlice<T>
where
    T: Hash,
{
    fn hash_slice(&self, slice: &[T]) -> u64 {
        Self::hash_iter(&self.hasher, slice)
    }

    fn hash_iter(
        hasher: &DefaultHashBuilder,
        iter: impl IntoIterator<Item = impl Borrow<T>>,
    ) -> u64 {
        let mut hasher = hasher.build_hasher();
        for t in iter.into_iter() {
            t.borrow().hash(&mut hasher);
        }
        hasher.finish()
    }
}

impl<T> Default for ArenaSlice<T> {
    fn default() -> Self {
        Self {
            rangevec: RangeVec {
                vec: AppendVec::new(),
                ranges: AppendVec::new(),
            },
            map: DashTable::new(),
            hasher: DefaultHashBuilder::default(),
            #[cfg(feature = "debug")]
            references: AtomicUsize::new(0),
        }
    }
}

impl<T> Debug for ArenaSlice<T>
where
    T: Debug,
{
    fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        fmt.debug_list().entries(self.iter_()).finish()
    }
}

impl<T> PartialEq for ArenaSlice<T>
where
    T: Eq,
{
    fn eq(&self, other: &Self) -> bool {
        self.iter_().eq(other.iter_())
    }
}

impl<T> Eq for ArenaSlice<T> where T: Eq {}

#[cfg(feature = "get-size2")]
impl<T> GetSize for ArenaSlice<T>
where
    T: GetSize,
{
    fn get_heap_size_with_tracker<Tr: GetSizeTracker>(&self, tracker: Tr) -> (usize, Tr) {
        let heap_size = self
            .rangevec
            .vec
            .iter()
            .map(|x| x.get_size())
            .sum::<usize>()
            + self.rangevec.ranges.len() * (size_of::<CopyRangeU32>() + size_of::<u32>());
        (heap_size, tracker)
    }
}

#[cfg(feature = "debug")]
impl<T> ArenaSlice<T>
where
    T: GetSize,
{
    /// Prints a summary of the storage used by this arena to stdout.
    pub fn print_summary(&self, prefix: &str, title: &str, total_bytes: usize) {
        let slices = self.rangevec.ranges.len();
        let items = self.rangevec.vec.len();
        let references = self.references();
        let estimated_bytes = self.get_size();
        println!(
            "{}[{:.02}%] {} interner: {} objects | {} items ({:.02} items/object) | {} bytes ({:.02} bytes/object) | {} references ({:.02} refs/object)",
            prefix,
            estimated_bytes as f64 * 100.0 / total_bytes as f64,
            title,
            slices,
            items,
            items as f64 / slices as f64,
            estimated_bytes,
            estimated_bytes as f64 / slices as f64,
            references,
            references as f64 / slices as f64,
        );
    }
}

#[cfg(feature = "debug")]
impl<T> ArenaSlice<T> {
    fn references(&self) -> usize {
        self.references.load(atomic::Ordering::Relaxed)
    }
}

impl<T> ArenaSlice<T>
where
    T: Eq,
{
    // TODO: use Iterator::eq_by when feature(iter_order_by) becomes stable.
    fn iter_eq<'a>(
        mut lhs: impl ExactSizeIterator<Item = &'a T>,
        mut rhs: impl ExactSizeIterator<Item = T>,
    ) -> bool
    where
        T: 'a,
    {
        if lhs.len() != rhs.len() {
            return false;
        }
        loop {
            match (lhs.next(), rhs.next()) {
                (None, None) => return true,
                (Some(_), None) | (None, Some(_)) => return false,
                (Some(x), Some(y)) => {
                    if *x != y {
                        return false;
                    }
                }
            }
        }
    }
}

impl<T> ArenaSlice<T>
where
    T: Default + Eq + Hash,
{
    /// Interns the given value in this arena.
    ///
    /// If the value was already interned in this arena, its interning index
    /// will simply be returned. Otherwise it will be stored into the arena.
    ///
    /// See also [`intern_owned_mut()`](Self::intern_owned_mut), which is more
    /// efficient if you hold a mutable reference to this arena as it avoids
    /// acquiring locks.
    pub fn intern_owned(&self, value: Vec<T>) -> InternedSlice<T> {
        #[cfg(feature = "debug")]
        self.references.fetch_add(1, atomic::Ordering::Relaxed);

        let hash = self.hash_slice(&value);
        let id = *self
            .map
            .entry(
                hash,
                |&i| self.lookup_slice(i) == value,
                |&i| self.hash_slice(self.lookup_slice(i)),
            )
            .or_insert_with(|| {
                let range = self.rangevec.vec.push_owned_slice(value);
                self.rangevec.push_range(range)
            })
            .get();
        InternedSlice::new(id)
    }

    /// Interns the given value in this arena.
    ///
    /// If the value was already interned in this arena, its interning index
    /// will simply be returned. Otherwise it will be stored into the arena.
    ///
    /// Contrary to [`intern_owned()`](Self::intern_owned), no locks are held
    /// internally because this function already takes an exclusive mutable
    /// reference to this arena.
    pub fn intern_owned_mut(&mut self, value: Vec<T>) -> InternedSlice<T> {
        #[cfg(feature = "debug")]
        self.references.fetch_add(1, atomic::Ordering::Relaxed);

        let hash = self.hash_slice(&value);
        let id = *self
            .map
            .entry_mut(
                hash,
                |&i| self.rangevec.lookup_slice(i) == value,
                |&i| Self::hash_iter(&self.hasher, self.rangevec.lookup_slice(i)),
            )
            .or_insert_with(|| {
                let range = self.rangevec.vec.push_owned_slice_mut(value);
                self.rangevec.push_range_mut(range)
            })
            .get();
        InternedSlice::new(id)
    }

    /// Interns the given value in this arena.
    ///
    /// If the value was already interned in this arena, its interning index
    /// will simply be returned. Otherwise it will be stored into the arena.
    ///
    /// See also [`intern_array_mut()`](Self::intern_array_mut), which is more
    /// efficient if you hold a mutable reference to this arena as it avoids
    /// acquiring locks.
    pub fn intern_array<const N: usize>(&self, value: [T; N]) -> InternedSlice<T> {
        #[cfg(feature = "debug")]
        self.references.fetch_add(1, atomic::Ordering::Relaxed);

        let hash = self.hash_slice(&value);
        let id = *self
            .map
            .entry(
                hash,
                |&i| self.lookup_slice(i) == value,
                |&i| self.hash_slice(self.lookup_slice(i)),
            )
            .or_insert_with(|| {
                let range = self.rangevec.vec.push_array(value);
                self.rangevec.push_range(range)
            })
            .get();
        InternedSlice::new(id)
    }

    /// Interns the given value in this arena.
    ///
    /// If the value was already interned in this arena, its interning index
    /// will simply be returned. Otherwise it will be stored into the arena.
    ///
    /// Contrary to [`intern_array()`](Self::intern_array), no locks are held
    /// internally because this function already takes an exclusive mutable
    /// reference to this arena.
    pub fn intern_array_mut<const N: usize>(&mut self, value: [T; N]) -> InternedSlice<T> {
        #[cfg(feature = "debug")]
        self.references.fetch_add(1, atomic::Ordering::Relaxed);

        let hash = self.hash_slice(&value);
        let id = *self
            .map
            .entry_mut(
                hash,
                |&i| self.rangevec.lookup_slice(i) == value,
                |&i| Self::hash_iter(&self.hasher, self.rangevec.lookup_slice(i)),
            )
            .or_insert_with(|| {
                let range = self.rangevec.vec.push_array_mut(value);
                self.rangevec.push_range_mut(range)
            })
            .get();
        InternedSlice::new(id)
    }

    /// Interns the given iterator (collected as a slice) in this arena.
    ///
    /// If the value was already interned in this arena, its interning index
    /// will simply be returned. Otherwise it will be stored into the arena.
    ///
    /// See also [`intern_iter_mut()`](Self::intern_iter_mut), which is more
    /// efficient if you hold a mutable reference to this arena as it avoids
    /// acquiring locks.
    ///
    /// # Safety
    ///
    /// This function requires the iterator length to be correct (and not to
    /// change upon cloning). This is akin to the nightly-only
    /// [`TrustedLen`](std::iter::TrustedLen) trait.
    pub unsafe fn intern_iter(
        &self,
        value: impl ExactSizeIterator<Item = T> + Clone,
    ) -> InternedSlice<T> {
        #[cfg(feature = "debug")]
        self.references.fetch_add(1, atomic::Ordering::Relaxed);

        let hash = Self::hash_iter(&self.hasher, value.clone());

        let id = *self
            .map
            .entry(
                hash,
                |&i| {
                    let lhs = self.lookup_slice(i).iter();
                    let rhs = value.clone();
                    Self::iter_eq(lhs, rhs)
                },
                |&i| self.hash_slice(self.lookup_slice(i)),
            )
            .or_insert_with(|| {
                // SAFETY: The caller ensures that the iterator length is correct.
                let range = unsafe { self.rangevec.vec.push_contiguous(value) };
                self.rangevec.push_range(range)
            })
            .get();
        InternedSlice::new(id)
    }

    /// Interns the given iterator (collected as a slice) in this arena.
    ///
    /// If the value was already interned in this arena, its interning index
    /// will simply be returned. Otherwise it will be stored into the arena.
    ///
    /// Contrary to [`intern_iter()`](Self::intern_iter), no locks are held
    /// internally because this function already takes an exclusive mutable
    /// reference to this arena.
    ///
    /// # Safety
    ///
    /// This function requires the iterator length to be correct (and not to
    /// change upon cloning). This is akin to the nightly-only
    /// [`TrustedLen`](std::iter::TrustedLen) trait.
    pub unsafe fn intern_iter_mut(
        &mut self,
        value: impl ExactSizeIterator<Item = T> + Clone,
    ) -> InternedSlice<T> {
        #[cfg(feature = "debug")]
        self.references.fetch_add(1, atomic::Ordering::Relaxed);

        let hash = Self::hash_iter(&self.hasher, value.clone());

        let id = *self
            .map
            .entry_mut(
                hash,
                |&i| {
                    let lhs = self.rangevec.lookup_slice(i).iter();
                    let rhs = value.clone();
                    Self::iter_eq(lhs, rhs)
                },
                |&i| Self::hash_iter(&self.hasher, self.rangevec.lookup_slice(i)),
            )
            .or_insert_with(|| {
                // SAFETY: The caller ensures that the iterator length is correct.
                let range = unsafe { self.rangevec.vec.push_contiguous_mut(value) };
                self.rangevec.push_range_mut(range)
            })
            .get();
        InternedSlice::new(id)
    }

    /// Unconditionally push a value, without validating that it's already
    /// interned.
    #[cfg(feature = "raw")]
    pub fn push_owned_mut(&mut self, value: Vec<T>) -> InternedSlice<T> {
        #[cfg(feature = "debug")]
        self.references.fetch_add(1, atomic::Ordering::Relaxed);

        let hash = self.hash_slice(&value);

        let range = self.rangevec.vec.push_owned_slice_mut(value);
        let id = self.rangevec.push_range_mut(range);

        self.map.insert_unique_mut(hash, id, |&i| {
            Self::hash_iter(&self.hasher, self.rangevec.lookup_slice(i))
        });
        InternedSlice::new(id)
    }

    /// Unconditionally push a value, without validating that it's already
    /// interned.
    #[cfg(feature = "raw")]
    pub fn push_array_mut<const N: usize>(&mut self, value: [T; N]) -> InternedSlice<T> {
        #[cfg(feature = "debug")]
        self.references.fetch_add(1, atomic::Ordering::Relaxed);

        let hash = self.hash_slice(&value);

        let range = self.rangevec.vec.push_array_mut(value);
        let id = self.rangevec.push_range_mut(range);

        self.map.insert_unique_mut(hash, id, |&i| {
            Self::hash_iter(&self.hasher, self.rangevec.lookup_slice(i))
        });
        InternedSlice::new(id)
    }

    /// Unconditionally push an iterator as a single contiguous value, without
    /// validating that it's already interned.
    ///
    /// # Safety
    ///
    /// This function requires the iterator length to be correct. This is akin
    /// to the nightly-only [`TrustedLen`](std::iter::TrustedLen) trait.
    #[cfg(feature = "raw")]
    pub unsafe fn push_iter_mut(
        &mut self,
        value: impl ExactSizeIterator<Item = T>,
    ) -> InternedSlice<T> {
        // SAFETY: Simply forwarding to the crate-internal version.
        unsafe { self.push_iter_mut_(value) }
    }

    /// Unconditionally push an iterator as a single contiguous value, without
    /// validating that it's already interned.
    ///
    /// # Safety
    ///
    /// This function requires the iterator length to be correct. This is akin
    /// to the nightly-only [`TrustedLen`](std::iter::TrustedLen) trait.
    pub(crate) unsafe fn push_iter_mut_(
        &mut self,
        value: impl ExactSizeIterator<Item = T>,
    ) -> InternedSlice<T> {
        #[cfg(feature = "debug")]
        self.references.fetch_add(1, atomic::Ordering::Relaxed);

        // SAFETY: The caller ensures that the iterator length is correct.
        let range = unsafe { self.rangevec.vec.push_contiguous_mut(value) };
        let id = self.rangevec.push_range_mut(range.clone());

        let hash = self.hash_slice(&self.rangevec.vec[range]);

        self.map.insert_unique_mut(hash, id, |&i| {
            Self::hash_iter(&self.hasher, self.rangevec.lookup_slice(i))
        });
        InternedSlice::new(id)
    }
}

impl<T> ArenaSlice<T>
where
    T: Default + Clone + Eq + Hash,
{
    /// Interns the given value in this arena.
    ///
    /// If the value was already interned in this arena, its interning index
    /// will simply be returned. Otherwise it will be stored into the arena.
    ///
    /// If `T` is [`Copy`], it may be more efficient to call
    /// [`intern_copy()`](Self::intern_copy) instead.
    ///
    /// See also [`intern_mut()`](Self::intern_mut), which is more efficient if
    /// you hold a mutable reference to this arena as it avoids acquiring locks.
    pub fn intern(&self, value: &[T]) -> InternedSlice<T> {
        #[cfg(feature = "debug")]
        self.references.fetch_add(1, atomic::Ordering::Relaxed);

        let hash = self.hash_slice(value);
        let id = *self
            .map
            .entry(
                hash,
                |&i| self.lookup_slice(i) == value,
                |&i| self.hash_slice(self.lookup_slice(i)),
            )
            .or_insert_with(|| {
                let range = self.rangevec.vec.push_slice(value);
                self.rangevec.push_range(range)
            })
            .get();
        InternedSlice::new(id)
    }

    /// Interns the given value in this arena.
    ///
    /// If the value was already interned in this arena, its interning index
    /// will simply be returned. Otherwise it will be stored into the arena.
    ///
    /// If `T` is [`Copy`], it may be more efficient to call
    /// [`intern_copy_mut()`](Self::intern_copy_mut) instead.
    ///
    /// Contrary to [`intern()`](Self::intern), no locks are held internally
    /// because this function already takes an exclusive mutable reference to
    /// this arena.
    pub fn intern_mut(&mut self, value: &[T]) -> InternedSlice<T> {
        #[cfg(feature = "debug")]
        self.references.fetch_add(1, atomic::Ordering::Relaxed);

        let hash = self.hash_slice(value);
        let id = *self
            .map
            .entry_mut(
                hash,
                |&i| self.rangevec.lookup_slice(i) == value,
                |&i| Self::hash_iter(&self.hasher, self.rangevec.lookup_slice(i)),
            )
            .or_insert_with(|| {
                let range = self.rangevec.vec.push_slice_mut(value);
                self.rangevec.push_range_mut(range)
            })
            .get();
        InternedSlice::new(id)
    }

    /// Unconditionally push a value, without validating that it's already
    /// interned.
    ///
    /// If `T` is [`Copy`], calling [`push_copy_mut()`](Self::push_copy_mut) may
    /// be more efficient.
    #[cfg(feature = "raw")]
    pub fn push_mut(&mut self, value: &[T]) -> u32 {
        self.push(value)
    }

    /// Unconditionally push a value, without validating that it's already
    /// interned.
    pub(crate) fn push(&mut self, value: &[T]) -> u32 {
        #[cfg(feature = "debug")]
        self.references.fetch_add(1, atomic::Ordering::Relaxed);

        let hash = self.hash_slice(value);

        let range = self.rangevec.vec.push_slice_mut(value);
        let id = self.rangevec.push_range_mut(range);

        self.map.insert_unique_mut(hash, id, |&i| {
            Self::hash_iter(&self.hasher, self.rangevec.lookup_slice(i))
        });
        id
    }
}

impl<T> ArenaSlice<T>
where
    T: Default + Copy + Eq + Hash,
{
    /// Interns the given value in this arena.
    ///
    /// If the value was already interned in this arena, its interning index
    /// will simply be returned. Otherwise it will be stored into the arena.
    ///
    /// If `T` is only [`Clone`], you can call [`intern()`](Self::intern)
    /// instead. If `T` is also not [`Clone`], you can call
    /// [`intern_owned()`](Self::intern_owned) or
    /// [`intern_array()`](Self::intern_array).
    ///
    /// See also [`intern_copy_mut()`](Self::intern_copy_mut), which is more
    /// efficient if you hold a mutable reference to this arena as it avoids
    /// acquiring locks.
    pub fn intern_copy(&self, value: &[T]) -> InternedSlice<T> {
        #[cfg(feature = "debug")]
        self.references.fetch_add(1, atomic::Ordering::Relaxed);

        let hash = self.hash_slice(value);
        let id = *self
            .map
            .entry(
                hash,
                |&i| self.lookup_slice(i) == value,
                |&i| self.hash_slice(self.lookup_slice(i)),
            )
            .or_insert_with(|| {
                let range = self.rangevec.vec.push_slice_copy(value);
                self.rangevec.push_range(range)
            })
            .get();
        InternedSlice::new(id)
    }

    /// Interns the given value in this arena.
    ///
    /// If the value was already interned in this arena, its interning index
    /// will simply be returned. Otherwise it will be stored into the arena.
    ///
    /// If `T` is only [`Clone`], you can call
    /// [`intern_mut()`](Self::intern_mut) instead. If `T` is also not
    /// [`Clone`], you can call [`intern_owned_mut()`](Self::intern_owned_mut)
    /// or [`intern_array_mut()`](Self::intern_array_mut).
    ///
    /// Contrary to [`intern_copy()`](Self::intern_copy), no locks are held
    /// internally because this function already takes an exclusive mutable
    /// reference to this arena.
    pub fn intern_copy_mut(&mut self, value: &[T]) -> InternedSlice<T> {
        #[cfg(feature = "debug")]
        self.references.fetch_add(1, atomic::Ordering::Relaxed);

        let hash = self.hash_slice(value);
        let id = *self
            .map
            .entry(
                hash,
                |&i| self.rangevec.lookup_slice(i) == value,
                |&i| Self::hash_iter(&self.hasher, self.rangevec.lookup_slice(i)),
            )
            .or_insert_with(|| {
                let range = self.rangevec.vec.push_slice_copy_mut(value);
                self.rangevec.push_range_mut(range)
            })
            .get();
        InternedSlice::new(id)
    }

    /// Unconditionally push a value, without validating that it's already
    /// interned.
    ///
    /// If `T` is only [`Clone`], you can call [`push_mut()`](Self::push_mut)
    /// instead.
    #[cfg(feature = "raw")]
    pub fn push_copy_mut(&mut self, value: &[T]) -> u32 {
        #[cfg(feature = "debug")]
        self.references.fetch_add(1, atomic::Ordering::Relaxed);

        let hash = self.hash_slice(value);

        let range = self.rangevec.vec.push_slice_copy_mut(value);
        let id = self.rangevec.push_range_mut(range);

        self.map.insert_unique_mut(hash, id, |&i| {
            Self::hash_iter(&self.hasher, self.rangevec.lookup_slice(i))
        });
        id
    }
}

impl<T> ArenaSlice<T> {
    /// Retrieves the given [`InternedSlice`] value from this arena.
    ///
    /// The caller is responsible for ensuring that the same arena was used to
    /// intern this value, otherwise an arbitrary value will be returned or
    /// a panic will happen.
    pub fn lookup(&self, interned: InternedSlice<T>) -> &[T] {
        self.lookup_slice(interned.id)
    }

    fn lookup_slice(&self, id: u32) -> &[T] {
        self.rangevec.lookup_slice(id)
    }
}

#[cfg(feature = "serde")]
impl<T> Serialize for ArenaSlice<T>
where
    T: Serialize,
{
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        let mut tuple = serializer.serialize_tuple(2)?;

        let ranges = RangeWrapper {
            ranges: &self.rangevec.ranges,
            ranges_len: Cell::new(0),
            total_len: Cell::new(0),
        };
        tuple.serialize_element(&ranges)?;

        tuple.serialize_element(&ArenaSliceWrapper {
            ranges_len: ranges.ranges_len.into_inner(),
            total_len: ranges.total_len.into_inner(),
            rangevec: &self.rangevec,
        })?;

        tuple.end()
    }
}

#[cfg(feature = "serde")]
struct RangeWrapper<'a> {
    ranges: &'a AppendVec<CopyRangeU32>,
    ranges_len: Cell<u32>,
    total_len: Cell<u32>,
}

#[cfg(feature = "serde")]
impl<'a> Serialize for RangeWrapper<'a> {
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        let mut ranges_len: u32 = 0;
        let mut total_len: u32 = 0;
        let result = serializer.collect_seq(self.ranges.iter().map(|range| {
            ranges_len += 1;
            let this_len = range.end - range.start;
            total_len = total_len.strict_add(this_len);
            this_len
        }));

        self.ranges_len.set(ranges_len);
        self.total_len.set(total_len);

        result
    }
}

#[cfg(feature = "serde")]
struct ArenaSliceWrapper<'a, T> {
    ranges_len: u32,
    total_len: u32,
    rangevec: &'a RangeVec<T>,
}

#[cfg(feature = "serde")]
impl<'a, T> Serialize for ArenaSliceWrapper<'a, T>
where
    T: Serialize,
{
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        let mut seq = serializer.serialize_seq(Some(self.total_len as usize))?;

        for range in self.rangevec.ranges.iter().take(self.ranges_len as usize) {
            let slice = &self.rangevec.vec[range.start as usize..range.end as usize];
            for t in slice {
                seq.serialize_element(t)?;
            }
        }

        seq.end()
    }
}

#[cfg(feature = "serde")]
impl<'de, T> Deserialize<'de> for ArenaSlice<T>
where
    T: Default + Clone + Eq + Hash + Deserialize<'de>,
{
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: Deserializer<'de>,
    {
        deserializer.deserialize_tuple(2, ArenaSliceVisitor::new())
    }
}

#[cfg(feature = "serde")]
struct ArenaSliceVisitor<T> {
    _phantom: PhantomData<fn() -> ArenaSlice<T>>,
}

#[cfg(feature = "serde")]
impl<T> ArenaSliceVisitor<T> {
    fn new() -> Self {
        Self {
            _phantom: PhantomData,
        }
    }
}

#[cfg(feature = "serde")]
impl<'de, T> Visitor<'de> for ArenaSliceVisitor<T>
where
    T: Default + Clone + Eq + Hash + Deserialize<'de>,
{
    type Value = ArenaSlice<T>;

    fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
        formatter.write_str("a pair of values")
    }

    fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
    where
        A: SeqAccess<'de>,
    {
        let sizes: Vec<u32> = seq
            .next_element()?
            .ok_or_else(|| A::Error::invalid_length(0, &self))?;
        let values: Vec<T> = seq
            .next_element()?
            .ok_or_else(|| A::Error::invalid_length(1, &self))?;

        let mut arena = ArenaSlice {
            rangevec: RangeVec {
                vec: AppendVec::with_capacity(values.len()),
                ranges: AppendVec::with_capacity(sizes.len()),
            },
            map: DashTable::with_capacity(sizes.len()),
            hasher: DefaultHashBuilder::default(),
            #[cfg(feature = "debug")]
            references: AtomicUsize::new(0),
        };

        let mut start = 0;
        for size in sizes {
            let size = size as usize;
            arena.push(&values[start..start + size]);
            start += size;
        }

        Ok(arena)
    }
}

#[cfg(all(feature = "delta", feature = "serde"))]
mod delta {
    use super::*;
    use crate::{Accumulator, DeltaEncoding};

    impl<T, Delta, Accum> Serialize for DeltaEncoding<&ArenaSlice<T>, Accum>
    where
        Delta: Serialize,
        Accum: Accumulator<Value = [T], Storage = Box<[T]>, DeltaStorage = Box<[Delta]>>,
    {
        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
        where
            S: Serializer,
        {
            let mut tuple = serializer.serialize_tuple(2)?;

            let ranges = RangeWrapper {
                ranges: &self.rangevec.ranges,
                ranges_len: Cell::new(0),
                total_len: Cell::new(0),
            };
            tuple.serialize_element(&ranges)?;

            tuple.serialize_element(&ArenaSliceWrapper {
                ranges_len: ranges.ranges_len.into_inner(),
                total_len: ranges.total_len.into_inner(),
                rangevec: &self.map_ref(|arena| &arena.rangevec),
            })?;

            tuple.end()
        }
    }

    struct ArenaSliceWrapper<'a, T, Accum> {
        ranges_len: u32,
        total_len: u32,
        rangevec: &'a DeltaEncoding<&'a RangeVec<T>, Accum>,
    }

    impl<'a, T, Delta, Accum> Serialize for ArenaSliceWrapper<'a, T, Accum>
    where
        Delta: Serialize,
        Accum: Accumulator<Value = [T], Storage = Box<[T]>, DeltaStorage = Box<[Delta]>>,
    {
        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
        where
            S: Serializer,
        {
            let mut seq = serializer.serialize_seq(Some(self.total_len as usize))?;

            let mut acc = Accum::default();
            for range in self.rangevec.ranges.iter().take(self.ranges_len as usize) {
                let slice = &self.rangevec.vec[range.start as usize..range.end as usize];
                let delta = acc.fold(slice);
                assert_eq!(
                    delta.len(),
                    slice.len(),
                    "Invalid Accumulator implementation for DeltaEncoding of ArenaSlice: delta length must match source slice length"
                );
                for d in delta {
                    seq.serialize_element(&d)?;
                }
            }

            seq.end()
        }
    }

    impl<'de, T, Delta, Accum> Deserialize<'de> for DeltaEncoding<ArenaSlice<T>, Accum>
    where
        T: Default + Copy + Eq + Hash,
        Delta: Deserialize<'de>,
        Accum: Accumulator<Value = [T], Storage = Box<[T]>, Delta = [Delta]>,
    {
        fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
        where
            D: Deserializer<'de>,
        {
            deserializer.deserialize_tuple(2, DeltaArenaSliceVisitor::new())
        }
    }

    struct DeltaArenaSliceVisitor<T, Accum> {
        _phantom: PhantomData<fn() -> ArenaSlice<T>>,
        _accum: PhantomData<Accum>,
    }

    impl<T, Accum> DeltaArenaSliceVisitor<T, Accum> {
        fn new() -> Self {
            Self {
                _phantom: PhantomData,
                _accum: PhantomData,
            }
        }
    }

    impl<'de, T, Delta, Accum> Visitor<'de> for DeltaArenaSliceVisitor<T, Accum>
    where
        T: Default + Copy + Eq + Hash,
        Delta: Deserialize<'de>,
        Accum: Accumulator<Value = [T], Storage = Box<[T]>, Delta = [Delta]>,
    {
        type Value = DeltaEncoding<ArenaSlice<T>, Accum>;

        fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
            formatter.write_str("a pair of values")
        }

        fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
        where
            A: SeqAccess<'de>,
        {
            let sizes: Vec<u32> = seq
                .next_element()?
                .ok_or_else(|| A::Error::invalid_length(0, &self))?;
            let values: Vec<Delta> = seq
                .next_element()?
                .ok_or_else(|| A::Error::invalid_length(1, &self))?;

            let mut arena = ArenaSlice {
                rangevec: RangeVec {
                    vec: AppendVec::with_capacity(values.len()),
                    ranges: AppendVec::with_capacity(sizes.len()),
                },
                map: DashTable::with_capacity(sizes.len()),
                hasher: DefaultHashBuilder::default(),
                #[cfg(feature = "debug")]
                references: AtomicUsize::new(0),
            };

            let mut acc = Accum::default();
            let mut start = 0;
            for size in sizes {
                let size = size as usize;
                let delta = &values[start..start + size];
                let slice = acc.unfold(delta);
                assert_eq!(
                    delta.len(),
                    slice.len(),
                    "Invalid Accumulator implementation for DeltaEncoding of ArenaSlice: delta length must match destination slice length"
                );
                arena.push(&slice);
                start += size;
            }

            Ok(DeltaEncoding {
                inner: arena,
                _phantom: PhantomData,
            })
        }
    }
}