tagged_pointer/

lib.rs

/*
 * Copyright 2021-2024 taylor.fish <contact@taylor.fish>
 *
 * This file is part of tagged-pointer.
 *
 * tagged-pointer is licensed under the Apache License, Version 2.0
 * (the "License"); you may not use tagged-pointer except in compliance
 * with the License. You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#![no_std]
#![cfg_attr(has_unsafe_op_in_unsafe_fn, deny(unsafe_op_in_unsafe_fn))]
#![warn(clippy::undocumented_unsafe_blocks)]

//! This crate provides an implementation of [tagged pointers]: a
//! space-efficient representation of a pointer and integer tag. In particular,
//! both [`TaggedPtr`] and [`Option<TaggedPtr>`] are the size of a pointer
//! despite containing both a pointer and tag.
//!
//! [tagged pointers]: https://en.wikipedia.org/wiki/Tagged_pointer
//!
//! This crate depends only on [`core`], so it can be used in `no_std`
//! environments.
//!
//! [`core`]: https://doc.rust-lang.org/core/
//!
//! Example
//! -------
//!
//! ```rust
//! # #[cfg(not(feature = "fallback"))]
//! use core::mem::size_of;
//! use core::ptr::NonNull;
//! use tagged_pointer::TaggedPtr;
//!
//! #[repr(align(4))]
//! struct Item(u32, u32);
//!
//! # #[cfg(not(feature = "fallback"))]
//! # {
//! // `TaggedPtr` and `Option<TaggedPtr>` are both the size of a pointer:
//! assert_eq!(size_of::<TaggedPtr<Item, 2>>(), size_of::<*mut ()>());
//! assert_eq!(size_of::<Option<TaggedPtr<Item, 2>>>(), size_of::<*mut ()>());
//! # }
//!
//! let item1 = Item(1, 2);
//! let item2 = Item(3, 4);
//!
//! // We can store two bits of the tag, since `Item` has an alignment of 4.
//! let tp1 = TaggedPtr::<_, 2>::new(NonNull::from(&item1), 1);
//! let tp2 = TaggedPtr::<_, 2>::new(NonNull::from(&item2), 3);
//!
//! let (ptr1, tag1) = tp1.get();
//! let (ptr2, tag2) = tp2.get();
//!
//! assert_eq!((ptr1, tag1), (NonNull::from(&item1), 1));
//! assert_eq!((ptr2, tag2), (NonNull::from(&item2), 3));
//! ```
//!
//! Platform considerations
//! -----------------------
//!
//! The number of tag bits that can be stored in a pointer of a given type
//! depends on the type’s alignment. However, the alignment of many types is
//! [platform-specific][primitive-layout]: `u64`, for example, could have an
//! alignment of 8 on one platform and 4 on another.
//!
//! Therefore, it is highly recommended to use [`#[repr(align)]`][repr-align]
//! to guarantee a minimum alignment, defining a wrapper type if necessary:
//!
//! ```rust
//! # use core::ptr::NonNull;
//! # use tagged_pointer::TaggedPtr;
//! // This won't work on systems where `u64` has an alignment of 4!
//! # if false {
//! let x: u64 = 123;
//! let tp = TaggedPtr::<u64, 3>::new(NonNull::from(&x), 0b101);
//! # }
//!
//! // Instead, do this:
//! #[repr(align(8))]
//! struct MyU64(pub u64);
//!
//! let x = MyU64(123);
//! let tp = TaggedPtr::<MyU64, 3>::new(NonNull::from(&x), 0b101);
//! ```
//!
//! [primitive-layout]:
//!  https://doc.rust-lang.org/reference/type-layout.html#primitive-data-layout
//! [repr-align]:
#![doc = "https://doc.rust-lang.org/reference/type-layout.html\
    #the-alignment-modifiers"]
//!
//! Assumptions
//! -----------
//!
//! This crate avoids making assumptions about the representations of pointers.
//! In particular, it does not cast pointers to `usize` and assume that the
//! lower bits of that number can be used for tagging. There exist
//! architectures that do not allow reusing the lower bits of aligned pointers
//! in this manner, and even if none are currently supported by Rust, that
//! could change in the future. This crate’s approach also works better with
//! [strict provenance].
//!
//! [strict provenance]: https://github.com/rust-lang/rust/issues/95228
//!
//! Previously, this crate relied on assumptions about the behavior of
//! [`pointer::align_offset`][align_offset] in certain circumstances. These
//! assumptions were effectively always true, but were not strictly guaranteed,
//! so a fallback implementation was provided with the crate feature
//! `fallback`, which would avoid relying on this assumption at the cost of
//! space efficiency.
//!
//! However, as of Rust 1.78, this assumption is no longer necessary:
//! `align_offset` is [guaranteed to behave as required][121201].
//!
//! [align_offset]:
//!  https://doc.rust-lang.org/std/primitive.pointer.html#method.align_offset
//! [121201]: https://github.com/rust-lang/rust/pull/121201/

#[cfg(has_const_assert)]
macro_rules! const_assert {
    ($($tt:tt)*) => {
        ::core::assert!($($tt)*)
    };
}

/// NOTE: The assertions generated by this macro may be evaluated in code paths
/// that aren't taken. Therefore, `$cond` must contain *all* conditions
/// necessary and sufficient for the assertion to pass, independent of the flow
/// of code.
#[cfg(not(has_const_assert))]
macro_rules! const_assert {
    ($cond:expr $(,)?) => {
        const_assert!($cond, "assertion failed")
    };

    ($cond:expr, $msg:literal $(,)?) => {{
        let _ = [$msg][!$cond as usize];
    }};
}

/// Documentation for the const `BITS` parameter.
macro_rules! with_bits_doc {
    ($(#[$attr:meta])* pub $($tt:tt)+) => {
        $(#[$attr])*
        ///
        /// `BITS` specifies how many bits are used for the tag. The alignment
        /// of `T` must be large enough to store this many bits: if `BITS` is
        /// larger than the base-2 logarithm of the alignment of `T`[^bits],
        /// panics or compilation errors will occur.
        ///
        /// [^bits]: Because alignment is always a power of 2, this is equal to
        // Workaround for issues with links to Rust items in footnotes
        #[doc = "<code>\
            [align_of][core::mem::align_of]::\\<T>().\
            [trailing_zeros][usize::trailing_zeros]\\()\
            </code>."]
        pub $($tt)*
    };
}

mod ptr;
mod reference;
#[cfg(any(test, doctest))]
mod tests;

/// The type of the const `BITS` parameter. This could have been [`u32`], which
/// would match the `BITS` constants in primitive types (e.g., [`u8::BITS`]),
/// but [`usize`] is also suitable for storing any potential number of tag
/// bits: because the tag itself is stored in a [`usize`], it cannot possibly
/// consist of more than [`usize::MAX`] bits (or anywhere close to it).
type Bits = usize;

pub use ptr::TaggedPtr;
pub use reference::{TaggedMutRef, TaggedRef};

/// Alternate tagged pointer types without a `BITS` parameter.
///
/// The types in this module correspond to those in the [crate root][crate],
/// but instead of taking a `BITS` parameter to determine how many tag bits
/// are stored, they use the largest possible tag size for an aligned pointer
/// to `T`.
///
/// See each type's documentation for more information.
pub mod implied {
    pub use super::ptr::implied::*;
    pub use super::reference::implied::*;
}