//! This module implements tagged pointers.
//!
//! In order to utilize the pointer packing, you must have two types: a pointer,
//! and a tag.
//!
//! The pointer must implement the [`Pointer`] trait, with the primary
//! requirement being convertible to and from a raw pointer. Note that the
//! pointer must be dereferenceable, so raw pointers generally cannot implement
//! the [`Pointer`] trait. This implies that the pointer must also be non-null.
//!
//! Many common pointer types already implement the [`Pointer`] trait.
//!
//! The tag must implement the [`Tag`] trait.
//!
//! We assert that the tag and the [`Pointer`] types are compatible at compile
//! time.
use std::ops::Deref;
use std::ptr::NonNull;
use std::rc::Rc;
use std::sync::Arc;
use crate::aligned::Aligned;
mod copy;
mod drop;
mod impl_tag;
pub use copy::CopyTaggedPtr;
pub use drop::TaggedPtr;
/// This describes the pointer type encapsulated by [`TaggedPtr`] and
/// [`CopyTaggedPtr`].
///
/// # Safety
///
/// The pointer returned from [`into_ptr`] must be a [valid], pointer to
/// [`<Self as Deref>::Target`].
///
/// Note that if `Self` implements [`DerefMut`] the pointer returned from
/// [`into_ptr`] must be valid for writes (and thus calling [`NonNull::as_mut`]
/// on it must be safe).
///
/// The [`BITS`] constant must be correct. [`BITS`] least-significant bits,
/// must be zero on all pointers returned from [`into_ptr`].
///
/// For example, if the alignment of [`Self::Target`] is 2, then `BITS` should be 1.
///
/// [`BITS`]: Pointer::BITS
/// [`into_ptr`]: Pointer::into_ptr
/// [valid]: std::ptr#safety
/// [`<Self as Deref>::Target`]: Deref::Target
/// [`Self::Target`]: Deref::Target
/// [`DerefMut`]: std::ops::DerefMut
pub unsafe trait Pointer: Deref {
/// Number of unused (always zero) **least-significant bits** in this
/// pointer, usually related to the pointees alignment.
///
/// For example if [`BITS`] = `2`, then given `ptr = Self::into_ptr(..)`,
/// `ptr.addr() & 0b11 == 0` must be true.
///
/// Most likely the value you want to use here is the following, unless
/// your [`Self::Target`] type is unsized (e.g., `ty::List<T>` in rustc)
/// or your pointer is over/under aligned, in which case you'll need to
/// manually figure out what the right type to pass to [`bits_for`] is, or
/// what the value to set here.
///
/// ```rust
/// # use std::ops::Deref;
/// # use rustc_data_structures::tagged_ptr::bits_for;
/// # struct T;
/// # impl Deref for T { type Target = u8; fn deref(&self) -> &u8 { &0 } }
/// # impl T {
/// const BITS: u32 = bits_for::<<Self as Deref>::Target>();
/// # }
/// ```
///
/// [`BITS`]: Pointer::BITS
/// [`Self::Target`]: Deref::Target
const BITS: u32;
/// Turns this pointer into a raw, non-null pointer.
///
/// The inverse of this function is [`from_ptr`].
///
/// This function guarantees that the least-significant [`Self::BITS`] bits
/// are zero.
///
/// [`from_ptr`]: Pointer::from_ptr
/// [`Self::BITS`]: Pointer::BITS
fn into_ptr(self) -> NonNull<Self::Target>;
/// Re-creates the original pointer, from a raw pointer returned by [`into_ptr`].
///
/// # Safety
///
/// The passed `ptr` must be returned from [`into_ptr`].
///
/// This acts as [`ptr::read::<Self>()`] semantically, it should not be called more than
/// once on non-[`Copy`] `Pointer`s.
///
/// [`into_ptr`]: Pointer::into_ptr
/// [`ptr::read::<Self>()`]: std::ptr::read
unsafe fn from_ptr(ptr: NonNull<Self::Target>) -> Self;
}
/// This describes tags that the [`TaggedPtr`] struct can hold.
///
/// # Safety
///
/// The [`BITS`] constant must be correct.
///
/// No more than [`BITS`] least-significant bits may be set in the returned usize.
///
/// [`BITS`]: Tag::BITS
pub unsafe trait Tag: Copy {
/// Number of least-significant bits in the return value of [`into_usize`]
/// which may be non-zero. In other words this is the bit width of the
/// value.
///
/// [`into_usize`]: Tag::into_usize
const BITS: u32;
/// Turns this tag into an integer.
///
/// The inverse of this function is [`from_usize`].
///
/// This function guarantees that only the least-significant [`Self::BITS`]
/// bits can be non-zero.
///
/// [`from_usize`]: Tag::from_usize
/// [`Self::BITS`]: Tag::BITS
fn into_usize(self) -> usize;
/// Re-creates the tag from the integer returned by [`into_usize`].
///
/// # Safety
///
/// The passed `tag` must be returned from [`into_usize`].
///
/// [`into_usize`]: Tag::into_usize
unsafe fn from_usize(tag: usize) -> Self;
}
/// Returns the number of bits available for use for tags in a pointer to `T`
/// (this is based on `T`'s alignment).
pub const fn bits_for<T: ?Sized + Aligned>() -> u32 {
crate::aligned::align_of::<T>().as_nonzero().trailing_zeros()
}
/// Returns the correct [`Tag::BITS`] constant for a set of tag values.
pub const fn bits_for_tags(mut tags: &[usize]) -> u32 {
let mut bits = 0;
while let &[tag, ref rest @ ..] = tags {
tags = rest;
// bits required to represent `tag`,
// position of the most significant 1
let b = usize::BITS - tag.leading_zeros();
if b > bits {
bits = b;
}
}
bits
}
unsafe impl<T: ?Sized + Aligned> Pointer for Box<T> {
const BITS: u32 = bits_for::<Self::Target>();
#[inline]
fn into_ptr(self) -> NonNull<T> {
// Safety: pointers from `Box::into_raw` are valid & non-null
unsafe { NonNull::new_unchecked(Box::into_raw(self)) }
}
#[inline]
unsafe fn from_ptr(ptr: NonNull<T>) -> Self {
// Safety: `ptr` comes from `into_ptr` which calls `Box::into_raw`
unsafe { Box::from_raw(ptr.as_ptr()) }
}
}
unsafe impl<T: ?Sized + Aligned> Pointer for Rc<T> {
const BITS: u32 = bits_for::<Self::Target>();
#[inline]
fn into_ptr(self) -> NonNull<T> {
// Safety: pointers from `Rc::into_raw` are valid & non-null
unsafe { NonNull::new_unchecked(Rc::into_raw(self).cast_mut()) }
}
#[inline]
unsafe fn from_ptr(ptr: NonNull<T>) -> Self {
// Safety: `ptr` comes from `into_ptr` which calls `Rc::into_raw`
unsafe { Rc::from_raw(ptr.as_ptr()) }
}
}
unsafe impl<T: ?Sized + Aligned> Pointer for Arc<T> {
const BITS: u32 = bits_for::<Self::Target>();
#[inline]
fn into_ptr(self) -> NonNull<T> {
// Safety: pointers from `Arc::into_raw` are valid & non-null
unsafe { NonNull::new_unchecked(Arc::into_raw(self).cast_mut()) }
}
#[inline]
unsafe fn from_ptr(ptr: NonNull<T>) -> Self {
// Safety: `ptr` comes from `into_ptr` which calls `Arc::into_raw`
unsafe { Arc::from_raw(ptr.as_ptr()) }
}
}
unsafe impl<'a, T: 'a + ?Sized + Aligned> Pointer for &'a T {
const BITS: u32 = bits_for::<Self::Target>();
#[inline]
fn into_ptr(self) -> NonNull<T> {
NonNull::from(self)
}
#[inline]
unsafe fn from_ptr(ptr: NonNull<T>) -> Self {
// Safety:
// `ptr` comes from `into_ptr` which gets the pointer from a reference
unsafe { ptr.as_ref() }
}
}
unsafe impl<'a, T: 'a + ?Sized + Aligned> Pointer for &'a mut T {
const BITS: u32 = bits_for::<Self::Target>();
#[inline]
fn into_ptr(self) -> NonNull<T> {
NonNull::from(self)
}
#[inline]
unsafe fn from_ptr(mut ptr: NonNull<T>) -> Self {
// Safety:
// `ptr` comes from `into_ptr` which gets the pointer from a reference
unsafe { ptr.as_mut() }
}
}
/// A tag type used in [`CopyTaggedPtr`] and [`TaggedPtr`] tests.
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
#[cfg(test)]
enum Tag2 {
B00 = 0b00,
B01 = 0b01,
B10 = 0b10,
B11 = 0b11,
}
#[cfg(test)]
unsafe impl Tag for Tag2 {
const BITS: u32 = 2;
fn into_usize(self) -> usize {
self as _
}
unsafe fn from_usize(tag: usize) -> Self {
match tag {
0b00 => Tag2::B00,
0b01 => Tag2::B01,
0b10 => Tag2::B10,
0b11 => Tag2::B11,
_ => unreachable!(),
}
}
}
#[cfg(test)]
impl<HCX> crate::stable_hasher::HashStable<HCX> for Tag2 {
fn hash_stable(&self, hcx: &mut HCX, hasher: &mut crate::stable_hasher::StableHasher) {
(*self as u8).hash_stable(hcx, hasher);
}
}