1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
/*
 * Copyright (C) 2021 taylor.fish <contact@taylor.fish>
 *
 * This file is part of tagged-pointer.
 *
 * tagged-pointer is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * tagged-pointer is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with tagged-pointer. If not, see <https://www.gnu.org/licenses/>.
 */

#![no_std]
#![warn(clippy::pedantic)]
#![allow(clippy::default_trait_access)]
#![allow(clippy::module_name_repetitions)]
#![allow(clippy::must_use_candidate)]
#![allow(clippy::non_ascii_literal)]

//! This crate provides an implementation of [tagged pointers]: pointers that
//! also contain an integer tag in a space-efficient manner.
//!
//! [tagged pointers]: https://en.wikipedia.org/wiki/Tagged_pointer
//!
//! Unless the fallback implementation is used (see the
//! [Assumptions](#assumptions) section below), both [`TaggedPtr`] and
//! [`Option<TaggedPtr>`] are guaranteed to be the size of a 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;
//! use typenum::U2;
//!
//! #[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, U2>>(), size_of::<usize>());
//! assert_eq!(size_of::<Option<TaggedPtr<Item, U2>>>(), size_of::<usize>());
//! # }
//!
//! 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::<_, U2>::new(NonNull::from(&item1), 1);
//! let tp2 = TaggedPtr::<_, U2>::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));
//! ```
//!
//! Assumptions
//! -----------
//!
//! This crate relies on [`pointer::align_offset`][`align_offset`] not failing
//! under certain circumstances. Specifically, [`align_offset`] must succeed
//! when the desired alignment is less than or equal to the alignment of the
//! allocation pointed to by the provided pointer. In practice, this is true,
//! even in [Miri] with the `-Zmiri-symbolic-alignment-check` flag, but the
//! specifications of [`align_offset`] technically allow an implementation not
//! to follow this behavior. If you experience issues due to this, please file
//! an issue in the [Git repository]. As a workaround, you can enable the
//! `"fallback"` feature, which avoids relying on [`align_offset`] at the cost
//! of making [`TaggedPtr`] twice as large.
//!
//! [Miri]: https://github.com/rust-lang/miri
//!
//! Note that this crate is always sound: an implementation of [`align_offset`]
//! that doesn’t follow the required behavior may cause panics, but not
//! undefined behavior.
//!
//! [`align_offset`]:
//! https://doc.rust-lang.org/std/primitive.pointer.html#method.align_offset
//! [Git repository]: https://github.com/taylordotfish/tagged-pointer
//!
//! Unfortunately, there’s currently no way to implement space-efficient tagged
//! pointers in Rust without making some assumptions. However, this approach
//! has some advantages over the usual method of casting the pointer to a
//! [`usize`] and reusing the lower bits: the usual approach makes
//! platform-specific assumptions about the representation of pointers (which
//! currently apply to all platforms supported by rustc but could be
//! invalidated if support for new architectures is added, and there are
//! real architectures which do not allow reusing the lower bits of aligned
//! pointers), whereas this crate’s assumptions are platform-independent (aside
//! from the requirements already imposed by Rust, like having 8-bit bytes) and
//! are satisfied by all known implementations of Rust, including Miri with
//! `-Zmiri-symbolic-alignment-check`.

use core::cmp::Ordering;
use core::fmt;
use core::hash::{Hash, Hasher};
use core::mem;
use core::ptr::NonNull;
use typenum::Unsigned;

/// Calculates 2 to the power of [`Bits::USIZE`](Unsigned::USIZE), and panics
/// if the result wouldn't fit in a `usize`.
fn alignment<Bits: Unsigned>() -> usize {
    use core::convert::TryFrom;
    u32::try_from(Bits::USIZE)
        .ok()
        .and_then(|n| 1_usize.checked_shl(n))
        .expect("`Bits::USIZE` is too large")
}

/// Returns the bitmask that should be applied to the tag to ensure that it is
/// smaller than the alignment ([`alignment::<Bits>()`](alignment)). Since
/// the alignment is always a power of 2, this function simply subtracts 1
/// from the alignment.
fn mask<Bits: Unsigned>() -> usize {
    alignment::<Bits>() - 1
}

#[cfg_attr(feature = "fallback", path = "fallback.rs")]
mod ptr;
use ptr::PtrImpl;

#[cfg(test)]
mod tests;

impl<T, Bits> Copy for PtrImpl<T, Bits> {}

impl<T, Bits> Eq for PtrImpl<T, Bits> {}

impl<T, Bits> PartialOrd for PtrImpl<T, Bits> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

/// A tagged pointer: a space-efficient representation of a pointer and integer
/// tag.
///
/// This type stores a pointer and an integer tag without taking up more
/// space than a normal pointer (unless the fallback implementation is used;
/// see the [module documentation](crate)).
///
/// The tagged pointer conceptually holds a [`NonNull<T>`](NonNull) and a
/// certain number of bits of an integer tag.
///
/// `Bits` should be a [type-level unsigned integer](Unsigned) from the
/// [typenum] crate. It specifies how many bits are used for the tag. The
/// alignment of `T` must be large enough to store this many bits; see
/// [`Self::new`].
#[repr(transparent)]
pub struct TaggedPtr<T, Bits>(PtrImpl<T, Bits>);

const BAD_TYPE_ALIGNMENT_MSG: &str = "\
alignment of `T` must be at least 2 to the power of `Bits::USIZE`";

impl<T, Bits: Unsigned> TaggedPtr<T, Bits> {
    /// Creates a new tagged pointer. Only the lower
    /// [`Bits::USIZE`](Unsigned::USIZE) bits of `tag` are stored.
    ///
    /// # Panics
    ///
    /// This method panics if the alignment of `T` is less than 2 to the power
    /// of [`Bits::USIZE`](Unsigned::USIZE). This ensures that all properly
    /// aligned pointers to `T` will be aligned enough to store the specified
    /// number of bits of the tag.
    ///
    /// `ptr` should be “dereferencable” in the sense defined by
    /// [`core::ptr`](core::ptr#safety). If it is not, this method or other
    /// methods of [`TaggedPtr`] may panic.
    ///
    /// It is recommended that `ptr` be properly aligned (i.e., aligned to at
    /// least [`mem::align_of::<T>()`](mem::align_of)), but it may have a
    /// smaller alignment. However, if its alignment is not at least
    /// 2 to the power of [`Bits::USIZE`](Unsigned::USIZE), this method may
    /// panic.
    pub fn new(ptr: NonNull<T>, tag: usize) -> Self {
        // This should always be true.
        assert!(mem::align_of::<T>().is_power_of_two());
        assert!(
            mem::align_of::<T>().trailing_zeros() as usize >= Bits::USIZE,
            "{}",
            BAD_TYPE_ALIGNMENT_MSG,
        );
        // This should always be true.
        assert!(mem::size_of::<T>().max(1) >= mem::align_of::<T>());
        Self(PtrImpl::new(ptr, tag))
    }

    /// Gets the pointer and tag stored by the tagged pointer. If you need
    /// both the pointer and tag, this method may be more efficient than
    /// calling [`Self::ptr`] and [`Self::tag`] separately.
    ///
    /// # Panics
    ///
    /// If the pointer provided to [`Self::new`] wasn't
    /// [“dereferencable”](core::ptr#safety), this method may panic.
    pub fn get(self) -> (NonNull<T>, usize) {
        self.0.get()
    }

    /// Gets the pointer stored by the tagged pointer, without the tag.
    /// Equivalent to [`self.get().0`](Self::get).
    ///
    /// # Panics
    ///
    /// If the pointer provided to [`Self::new`] wasn't
    /// [“dereferencable”](core::ptr#safety), this method may panic.
    pub fn ptr(self) -> NonNull<T> {
        self.get().0
    }

    /// Gets the tag stored by the tagged pointer. Equivalent to
    /// [`self.get().1`](Self::get).
    ///
    /// # Panics
    ///
    /// If the pointer provided to [`Self::new`] wasn't
    /// [“dereferencable”](core::ptr#safety), this method may panic.
    pub fn tag(self) -> usize {
        self.get().1
    }
}

impl<T, Bits> Clone for TaggedPtr<T, Bits> {
    fn clone(&self) -> Self {
        Self(self.0)
    }
}

impl<T, Bits> Copy for TaggedPtr<T, Bits> {}

impl<T, Bits> PartialEq for TaggedPtr<T, Bits> {
    fn eq(&self, other: &Self) -> bool {
        self.0 == other.0
    }
}

impl<T, Bits> Eq for TaggedPtr<T, Bits> {}

impl<T, Bits> PartialOrd for TaggedPtr<T, Bits> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<T, Bits> Ord for TaggedPtr<T, Bits> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.cmp(&other.0)
    }
}

impl<T, Bits> Hash for TaggedPtr<T, Bits> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.0.hash(state);
    }
}

impl<T, Bits: Unsigned> fmt::Debug for TaggedPtr<T, Bits> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let (ptr, tag) = self.get();
        f.debug_struct("TaggedPtr")
            .field("ptr", &ptr)
            .field("tag", &tag)
            .finish()
    }
}