src/tools/rust-analyzer/crates/intern/src/intern_slice.rs - rust - Git at Google

 //! 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::with_capacity_and_hasher(
                 (64 * 1024) / std::mem::size_of::<T::SliceType>(),
                 Default::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;
	//! 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::with_capacity_and_hasher(
	(64 * 1024) / std::mem::size_of::<T::SliceType>(),
	Default::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;