Impressum unique_arena.rs

//! The [`UniqueArena`] type and supporting definitions.

use crate::{FastIndexSet, Span};

use super::handle::{BadHandle, Handle, Index};

use std::{fmt, hash, ops};

/// An arena whose elements are guaranteed to be unique.
///
/// A `UniqueArena` holds a set of unique values of type `T`, each with an
/// associated [`Span`]. Inserting a value returns a `Handle<T>`, which can be
/// used to index the `UniqueArena` and obtain shared access to the `T` element.
/// Access via a `Handle` is an array lookup - no hash lookup is necessary.
///
/// The element type must implement `Eq` and `Hash`. Insertions of equivalent
/// elements, according to `Eq`, all return the same `Handle`.
///
/// Once inserted, elements may not be mutated.
///
/// `UniqueArena` is similar to [`Arena`]: If `Arena` is vector-like,
/// `UniqueArena` is `HashSet`-like.
///
/// [`Arena`]: super::Arena
#[derive(Clone)]
pub struct UniqueArena<T> {
    set: FastIndexSet<T>,

    /// Spans for the elements, indexed by handle.
    ///
    /// The length of this vector is always equal to `set.len()`. `FastIndexSet`
    /// promises that its elements "are indexed in a compact range, without
    /// holes in the range 0..set.len()", so we can always use the indices
    /// returned by insertion as indices into this vector.
    span_info: Vec<Span>,
}

impl<T> UniqueArena<T> {
    /// Create a new arena with no initial capacity allocated.
    pub fn new() -> Self {
        UniqueArena {
            set: FastIndexSet::default(),
            span_info: Vec::new(),
        }
    }

    /// Return the current number of items stored in this arena.
    pub fn len(&self) -> usize {
        self.set.len()
    }

    /// Return `true` if the arena contains no elements.
    pub fn is_empty(&self) -> bool {
        self.set.is_empty()
    }

    /// Clears the arena, keeping all allocations.
    pub fn clear(&mut self) {
        self.set.clear();
        self.span_info.clear();
    }

    /// Return the span associated with `handle`.
    ///
    /// If a value has been inserted multiple times, the span returned is the
    /// one provided with the first insertion.
    pub fn get_span(&self, handle: Handle<T>) -> Span {
        *self
            .span_info
            .get(handle.index())
            .unwrap_or(&Span::default())
    }

    #[cfg(feature = "compact")]
    pub(crate) fn drain_all(&mut self) -> UniqueArenaDrain<T> {
        UniqueArenaDrain {
            inner_elts: self.set.drain(..),
            inner_spans: self.span_info.drain(..),
            index: Index::new(0).unwrap(),
        }
    }
}

#[cfg(feature = "compact")]
pub struct UniqueArenaDrain<'a, T> {
    inner_elts: indexmap::set::Drain<'a, T>,
    inner_spans: std::vec::Drain<'a, Span>,
    index: Index,
}

#[cfg(feature = "compact")]
impl<T> Iterator for UniqueArenaDrain<'_, T> {
    type Item = (Handle<T>, T, Span);

    fn next(&mut self) -> Option<Self::Item> {
        match self.inner_elts.next() {
            Some(elt) => {
                let handle = Handle::new(self.index);
                self.index = self.index.checked_add(1).unwrap();
                let span = self.inner_spans.next().unwrap();
                Some((handle, elt, span))
            }
            None => None,
        }
    }
}

impl<T: Eq + hash::Hash> UniqueArena<T> {
    /// Returns an iterator over the items stored in this arena, returning both
    /// the item's handle and a reference to it.
    pub fn iter(&self) -> impl DoubleEndedIterator<Item = (Handle<T>, &T)> {
        self.set.iter().enumerate().map(|(i, v)| {
            let index = unsafe { Index::new_unchecked(i as u32) };
            (Handle::new(index), v)
        })
    }

    /// Insert a new value into the arena.
    ///
    /// Return a [`Handle<T>`], which can be used to index this arena to get a
    /// shared reference to the element.
    ///
    /// If this arena already contains an element that is `Eq` to `value`,
    /// return a `Handle` to the existing element, and drop `value`.
    ///
    /// If `value` is inserted into the arena, associate `span` with
    /// it. An element's span can be retrieved with the [`get_span`]
    /// method.
    ///
    /// [`Handle<T>`]: Handle
    /// [`get_span`]: UniqueArena::get_span
    pub fn insert(&mut self, value: T, span: Span) -> Handle<T> {
        let (index, added) = self.set.insert_full(value);

        if added {
            debug_assert!(index == self.span_info.len());
            self.span_info.push(span);
        }

        debug_assert!(self.set.len() == self.span_info.len());

        Handle::from_usize(index)
    }

    /// Replace an old value with a new value.
    ///
    /// # Panics
    ///
    /// - if the old value is not in the arena
    /// - if the new value already exists in the arena
    pub fn replace(&mut self, old: Handle<T>, new: T) {
        let (index, added) = self.set.insert_full(new);
        assert!(added && index == self.set.len() - 1);

        self.set.swap_remove_index(old.index()).unwrap();
    }

    /// Return this arena's handle for `value`, if present.
    ///
    /// If this arena already contains an element equal to `value`,
    /// return its handle. Otherwise, return `None`.
    pub fn get(&self, value: &T) -> Option<Handle<T>> {
        self.set
            .get_index_of(value)
            .map(|index| unsafe { Handle::from_usize_unchecked(index) })
    }

    /// Return this arena's value at `handle`, if that is a valid handle.
    pub fn get_handle(&self, handle: Handle<T>) -> Result<&T, BadHandle> {
        self.set
            .get_index(handle.index())
            .ok_or_else(|| BadHandle::new(handle))
    }

    /// Assert that `handle` is valid for this arena.
    pub fn check_contains_handle(&self, handle: Handle<T>) -> Result<(), BadHandle> {
        if handle.index() < self.set.len() {
            Ok(())
        } else {
            Err(BadHandle::new(handle))
        }
    }
}

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

impl<T: fmt::Debug + Eq + hash::Hash> fmt::Debug for UniqueArena<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.debug_map().entries(self.iter()).finish()
    }
}

impl<T> ops::Index<Handle<T>> for UniqueArena<T> {
    type Output = T;
    fn index(&self, handle: Handle<T>) -> &T {
        &self.set[handle.index()]
    }
}

#[cfg(feature = "serialize")]
impl<T> serde::Serialize for UniqueArena<T>
where
    T: Eq + hash::Hash + serde::Serialize,
{
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: serde::Serializer,
    {
        self.set.serialize(serializer)
    }
}

#[cfg(feature = "deserialize")]
impl<'de, T> serde::Deserialize<'de> for UniqueArena<T>
where
    T: Eq + hash::Hash + serde::Deserialize<'de>,
{
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        let set = FastIndexSet::deserialize(deserializer)?;
        let span_info = std::iter::repeat(Span::default()).take(set.len()).collect();

        Ok(Self { set, span_info })
    }
}

//Note: largely borrowed from `HashSet` implementation
#[cfg(feature = "arbitrary")]
impl<'a, T> arbitrary::Arbitrary<'a> for UniqueArena<T>
where
    T: Eq + hash::Hash + arbitrary::Arbitrary<'a>,
{
    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
        let mut arena = Self::default();
        for elem in u.arbitrary_iter()? {
            arena.set.insert(elem?);
            arena.span_info.push(Span::UNDEFINED);
        }
        Ok(arena)
    }

    fn arbitrary_take_rest(u: arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
        let mut arena = Self::default();
        for elem in u.arbitrary_take_rest_iter()? {
            arena.set.insert(elem?);
            arena.span_info.push(Span::UNDEFINED);
        }
        Ok(arena)
    }

    #[inline]
    fn size_hint(depth: usize) -> (usize, Option<usize>) {
        let depth_hint = <usize as arbitrary::Arbitrary>::size_hint(depth);
        arbitrary::size_hint::and(depth_hint, (0, None))
    }
}