Unnamed repository; edit this file 'description' to name the repository.
Diffstat (limited to 'crates/intern/src/intern_slice.rs')
| -rw-r--r-- | crates/intern/src/intern_slice.rs | 325 |
1 files changed, 325 insertions, 0 deletions
diff --git a/crates/intern/src/intern_slice.rs b/crates/intern/src/intern_slice.rs new file mode 100644 index 0000000000..58de6e17bd --- /dev/null +++ b/crates/intern/src/intern_slice.rs @@ -0,0 +1,325 @@ +//! Interning of slices, potentially with a header. +//! +//! See [`crate::intern`] for an explanation of interning modes. Note that slice interning is currently +//! available only in GC mode (there is no other need). +//! +//! [`InternedSlice`] and [`InternedSliceRef`] are essentially [`Interned<(Header, Box<[SliceType]>)>`][crate::Interned] +//! and [`InternedRef`][crate::InternedRef] with the same types, but more optimized. There is only one +//! allocation and the pointer is thin. + +use std::{ + ffi::c_void, + fmt::{self, Debug}, + hash::{BuildHasher, Hash, Hasher}, + marker::PhantomData, + mem::ManuallyDrop, + ops::Deref, + ptr::{self, NonNull}, + sync::OnceLock, +}; + +use dashmap::{DashMap, SharedValue}; +use hashbrown::raw::RawTable; +use rustc_hash::FxBuildHasher; +use triomphe::{HeaderSlice, HeaderWithLength, ThinArc}; + +type InternMap<T> = DashMap< + ThinArc<<T as SliceInternable>::Header, <T as SliceInternable>::SliceType>, + (), + FxBuildHasher, +>; +type Guard<T> = dashmap::RwLockWriteGuard< + 'static, + RawTable<( + ThinArc<<T as SliceInternable>::Header, <T as SliceInternable>::SliceType>, + SharedValue<()>, + )>, +>; +type Pointee<T> = HeaderSlice< + HeaderWithLength<<T as SliceInternable>::Header>, + [<T as SliceInternable>::SliceType], +>; + +pub struct InternedSlice<T: SliceInternable> { + arc: ThinArc<T::Header, T::SliceType>, +} + +impl<T: SliceInternable> InternedSlice<T> { + #[inline] + pub fn from_header_and_slice<'a>( + header: T::Header, + slice: &[T::SliceType], + ) -> InternedSliceRef<'a, T> { + const { assert!(T::USE_GC) }; + + let storage = T::storage().get(); + let (mut shard, hash) = Self::select(storage, &header, slice); + // Atomically, + // - check if `obj` is already in the map + // - if so, clone its `Arc` and return it + // - if not, box it up, insert it, and return a clone + // This needs to be atomic (locking the shard) to avoid races with other thread, which could + // insert the same object between us looking it up and inserting it. + let bucket = match shard.find_or_find_insert_slot( + hash, + |(other, _)| other.header.header == header && other.slice == *slice, + |(x, _)| storage.hasher().hash_one(x), + ) { + Ok(bucket) => bucket, + // SAFETY: The slot came from `find_or_find_insert_slot()`, and the table wasn't modified since then. + Err(insert_slot) => unsafe { + shard.insert_in_slot( + hash, + insert_slot, + (ThinArc::from_header_and_slice(header, slice), SharedValue::new(())), + ) + }, + }; + // SAFETY: We just retrieved/inserted this bucket. + // `NonNull::new_unchecked()` is safe because the pointer originates from a `ThinArc`. + unsafe { + InternedSliceRef { + // INVARIANT: We create it from a `ThinArc`. + ptr: NonNull::new_unchecked(ThinArc::as_ptr(&bucket.as_ref().0).cast_mut()), + _marker: PhantomData, + } + } + } + + #[inline] + fn select( + storage: &'static InternMap<T>, + header: &T::Header, + slice: &[T::SliceType], + ) -> (Guard<T>, u64) { + let hash = Self::hash(storage, header, slice); + let shard_idx = storage.determine_shard(hash as usize); + let shard = &storage.shards()[shard_idx]; + (shard.write(), hash) + } + + #[inline] + fn hash(storage: &'static InternMap<T>, header: &T::Header, slice: &[T::SliceType]) -> u64 { + storage.hasher().hash_one(HeaderSlice { + header: HeaderWithLength { header, length: slice.len() }, + slice, + }) + } + + #[inline(always)] + fn ptr(&self) -> *const c_void { + self.arc.as_ptr() + } + + #[inline] + pub fn as_ref(&self) -> InternedSliceRef<'_, T> { + InternedSliceRef { + // SAFETY: `self.ptr` comes from a valid `ThinArc`, so non null. + // INVARIANT: We create it from a `ThinArc`. + ptr: unsafe { NonNull::new_unchecked(self.ptr().cast_mut()) }, + _marker: PhantomData, + } + } +} + +/// Compares interned `Ref`s using pointer equality. +impl<T: SliceInternable> PartialEq for InternedSlice<T> { + // NOTE: No `?Sized` because `ptr_eq` doesn't work right with trait objects. + + #[inline] + fn eq(&self, other: &Self) -> bool { + self.arc.as_ptr() == other.arc.as_ptr() + } +} + +impl<T: SliceInternable> Eq for InternedSlice<T> {} + +impl<T: SliceInternable> Hash for InternedSlice<T> { + #[inline] + fn hash<H: Hasher>(&self, state: &mut H) { + state.write_usize(self.ptr().addr()) + } +} + +impl<T: SliceInternable> Deref for InternedSlice<T> { + type Target = Pointee<T>; + + #[inline] + fn deref(&self) -> &Self::Target { + &self.arc + } +} + +impl<T: SliceInternable> Clone for InternedSlice<T> { + #[inline] + fn clone(&self) -> Self { + Self { arc: self.arc.clone() } + } +} + +impl<T> Debug for InternedSlice<T> +where + T: SliceInternable, + T::SliceType: Debug, + T::Header: Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + (*self.arc).fmt(f) + } +} + +#[repr(transparent)] +pub struct InternedSliceRef<'a, T> { + /// # Invariant + /// + /// There is no `ThinArcBorrow` unfortunately, so this is basically a `ManuallyDrop<ThinArc>`, + /// except that can't be `Copy`, so we store a raw pointer instead. + ptr: NonNull<c_void>, + _marker: PhantomData<&'a T>, +} + +// SAFETY: This is essentially a `ThinArc`, implemented as a raw pointer because there is no `ThinArcBorrowed`. +unsafe impl<T: Send + Sync> Send for InternedSliceRef<'_, T> {} +unsafe impl<T: Send + Sync> Sync for InternedSliceRef<'_, T> {} + +impl<'a, T: SliceInternable> InternedSliceRef<'a, T> { + #[inline(always)] + fn arc(self) -> ManuallyDrop<ThinArc<T::Header, T::SliceType>> { + // SAFETY: `self.ptr`'s invariant. + unsafe { ManuallyDrop::new(ThinArc::from_raw(self.ptr.as_ptr())) } + } + + #[inline] + pub fn to_owned(self) -> InternedSlice<T> { + InternedSlice { arc: (*self.arc()).clone() } + } + + #[inline] + pub fn get(self) -> &'a Pointee<T> { + // SAFETY: This is a lifetime extension, valid because we live for `'a`. + unsafe { &*ptr::from_ref::<Pointee<T>>(&*self.arc()) } + } + + /// # Safety + /// + /// You have to make sure the data is not referenced after the refcount reaches zero; beware the interning + /// map also keeps a reference to the value. + #[inline] + pub unsafe fn decrement_refcount(self) { + drop(ManuallyDrop::into_inner(self.arc())); + } + + #[inline] + pub(crate) fn strong_count(self) -> usize { + ThinArc::strong_count(&self.arc()) + } + + #[inline] + pub(crate) fn as_raw(self) -> *const c_void { + self.arc().as_ptr() + } + + /// **Available only on GC mode**. + /// + /// Changes the attached lifetime, as in GC mode, the lifetime is more kind of a lint to prevent misuse + /// than actual soundness check. + #[inline] + pub fn change_lifetime<'b>(self) -> InternedSliceRef<'b, T> { + const { assert!(T::USE_GC) }; + // SAFETY: The lifetime on `InternedSliceRef` is essentially advisory only for GCed types. + unsafe { std::mem::transmute::<InternedSliceRef<'a, T>, InternedSliceRef<'b, T>>(self) } + } +} + +impl<T> Clone for InternedSliceRef<'_, T> { + #[inline] + fn clone(&self) -> Self { + *self + } +} + +impl<T> Copy for InternedSliceRef<'_, T> {} + +impl<T: SliceInternable> Hash for InternedSliceRef<'_, T> { + #[inline] + fn hash<H: Hasher>(&self, state: &mut H) { + state.write_usize(self.ptr.as_ptr().addr()); + } +} + +impl<T: SliceInternable> PartialEq for InternedSliceRef<'_, T> { + #[inline] + fn eq(&self, other: &Self) -> bool { + self.ptr == other.ptr + } +} + +impl<T: SliceInternable> Eq for InternedSliceRef<'_, T> {} + +impl<T: SliceInternable> Deref for InternedSliceRef<'_, T> { + type Target = Pointee<T>; + + #[inline] + fn deref(&self) -> &Self::Target { + self.get() + } +} + +impl<T> Debug for InternedSliceRef<'_, T> +where + T: SliceInternable, + T::SliceType: Debug, + T::Header: Debug, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + (**self).fmt(f) + } +} + +pub struct InternSliceStorage<T: SliceInternable> { + map: OnceLock<InternMap<T>>, +} + +#[allow( + clippy::new_without_default, + reason = "this a const fn, so it can't be default yet. See <https://github.com/rust-lang/rust/issues/63065>" +)] +impl<T: SliceInternable> InternSliceStorage<T> { + pub const fn new() -> Self { + Self { map: OnceLock::new() } + } +} + +impl<T: SliceInternable> InternSliceStorage<T> { + pub(crate) fn get(&self) -> &InternMap<T> { + self.map.get_or_init(DashMap::default) + } +} + +pub trait SliceInternable: Sized + 'static { + const USE_GC: bool; + type Header: Eq + Hash + Send + Sync; + type SliceType: Eq + Hash + Send + Sync + Copy + 'static; + fn storage() -> &'static InternSliceStorage<Self>; +} + +/// Implements `SliceInternable` for a given list of types, making them usable with `InternedSlice`. +#[macro_export] +#[doc(hidden)] +macro_rules! _impl_slice_internable { + ( gc; $tag:ident, $h:ty, $t:ty $(,)? ) => { + #[allow(unreachable_pub)] + pub struct $tag; + impl $crate::SliceInternable for $tag { + const USE_GC: bool = true; + type Header = $h; + type SliceType = $t; + fn storage() -> &'static $crate::InternSliceStorage<Self> { + static STORAGE: $crate::InternSliceStorage<$tag> = + $crate::InternSliceStorage::new(); + &STORAGE + } + } + }; +} +pub use crate::_impl_slice_internable as impl_slice_internable; |