tagged_pointer/reference/
mod.rs

1/*
2 * Copyright 2023-2024 Jonáš Fiala <jonas.fiala@inf.ethz.ch>
3 * Copyright 2023-2024 taylor.fish <contact@taylor.fish>
4 *
5 * This file is part of tagged-pointer.
6 *
7 * tagged-pointer is licensed under the Apache License, Version 2.0
8 * (the "License"); you may not use tagged-pointer except in compliance
9 * with the License. You may obtain a copy of the License at
10 *
11 *     http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 */
19
20use crate::{Bits, TaggedPtr};
21use core::marker::PhantomData;
22
23/// Common code for [`self::TaggedRef`] and [`self::TaggedMutRef`].
24macro_rules! impl_explicit_tagged_ref_common {
25    ($name:ident $(,)?) => {
26        impl<T, const BITS: Bits> $name<'_, T, BITS> {
27            /// The number of tag bits that this tagged reference can store.
28            pub const BITS: u32 = BITS as _;
29
30            /// The maximum tag (inclusive) that this tagged reference can
31            /// store. Equal to `(1 << BITS) - 1` (i.e., one less than 2 to the
32            /// power of `BITS`).
33            pub const MAX_TAG: usize = max_tag::<T, BITS>();
34        }
35    };
36}
37
38const fn max_tag<T, const BITS: Bits>() -> usize {
39    TaggedPtr::<T, BITS>::MAX_TAG
40}
41
42/// Common code for [`TaggedRef`] and [`TaggedMutRef`], as well as the versions
43/// in [`implicit`].
44macro_rules! impl_tagged_ref_shared_mut_common {
45    (
46        $name:ident,
47        [$($ty_params:tt)*],
48        [$($ty_args:tt)*] $(,)?
49    ) => { const _: () = {
50        use core::cmp::Ordering;
51        use core::fmt::{self, Debug};
52        use core::hash::{Hash, Hasher};
53
54        impl<$($ty_params)*> Eq for $name<'_, $($ty_args)*>
55        where
56            T: Eq,
57        {
58        }
59
60        impl<$($ty_params)*> PartialEq for $name<'_, $($ty_args)*>
61        where
62            T: PartialEq,
63        {
64            /// Returns <code>self.[get]\() == other.[get]\()</code>.
65            ///
66            /// [get]: Self::get
67            fn eq(&self, other: &Self) -> bool {
68                self.get() == other.get()
69            }
70        }
71
72        impl<$($ty_params)*> Ord for $name<'_, $($ty_args)*>
73        where
74            T: Ord,
75        {
76            /// Returns <code>self.[get]\().cmp(&other.[get]\())</code>.
77            ///
78            /// [get]: Self::get
79            fn cmp(&self, other: &Self) -> Ordering {
80                self.get().cmp(&other.get())
81            }
82        }
83
84        impl<$($ty_params)*> PartialOrd for $name<'_, $($ty_args)*>
85        where
86            T: PartialOrd,
87        {
88            /// Returns
89            /// <code>self.[get]\().partial_cmp(&other.[get]\())</code>.
90            ///
91            /// [get]: Self::get
92            fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
93                self.get().partial_cmp(&other.get())
94            }
95        }
96
97        impl<$($ty_params)*> Hash for $name<'_, $($ty_args)*>
98        where
99            T: Hash,
100        {
101            /// Hashes [`self.get()`](Self::get).
102            fn hash<H: Hasher>(&self, state: &mut H) {
103                self.get().hash(state)
104            }
105        }
106
107        // Note: we can't implement `Borrow<T>` because `Eq`, `Ord`, and `Hash`
108        // on tagged references don't behave the same as their implementations
109        // for `&T`.
110        //
111        // `Deref<Target = T>` isn't implemented because this type is intended
112        // to be conceptually equivalent to a struct with individual
113        // `reference: &T` and `tag: usize` fields, which would typically
114        // require explicit accessing of the `reference` field. This also
115        // avoids conflicts with the inherent `TaggedRef` methods and makes it
116        // easier to add new methods in the future without worrying about
117        // compatibility.
118        impl<$($ty_params)*> AsRef<T> for $name<'_, $($ty_args)*> {
119            fn as_ref(&self) -> &T {
120                self.get_ref()
121            }
122        }
123
124        impl<$($ty_params)*> Debug for $name<'_, $($ty_args)*>
125        where
126            T: Debug,
127        {
128            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
129                let (r, tag) = self.get();
130                f.debug_struct(stringify!($name))
131                    .field("data", r)
132                    .field("tag", &tag)
133                    .finish()
134            }
135        }
136
137        impl<$($ty_params)*> fmt::Pointer for $name<'_, $($ty_args)*> {
138            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
139                write!(f, "{:p}", self.get_ref())
140            }
141        }
142    }; };
143}
144
145with_bits_doc! {
146    /// A tagged reference: a space-efficient representation of a reference and
147    /// integer tag.
148    ///
149    /// This type behaves like [`TaggedPtr`] but with a [reference] instead of
150    /// a raw pointer.
151    #[repr(transparent)]
152    pub struct TaggedRef<'a, T, const BITS: Bits>(
153        TaggedPtr<T, BITS>,
154        PhantomData<&'a T>,
155    );
156}
157
158impl<'a, T, const BITS: Bits> TaggedRef<'a, T, BITS> {
159    /// Creates a new tagged reference. Only the lower `BITS` bits of `tag` are
160    /// stored.
161    pub fn new(reference: &'a T, tag: usize) -> Self {
162        Self::new_impl(reference, tag)
163    }
164}
165
166/// Common code for [`TaggedRef`] and [`implied::TaggedRef`].
167macro_rules! impl_tagged_ref_common {
168    (
169        [$($ty_params:tt)*],
170        [$($ty_args:tt)*],
171        $doctest_context:literal $(,)?
172    ) => {
173        const _: () = {
174            use core::marker::PhantomData;
175
176            impl<'a, $($ty_params)*> TaggedRef<'a, $($ty_args)*> {
177                impl_tagged_ref_common!(
178                    impl methods,
179                    [$($ty_args)*],
180                    $doctest_context,
181                );
182            }
183        };
184
185        impl<$($ty_params)*> Clone for TaggedRef<'_, $($ty_args)*> {
186            fn clone(&self) -> Self {
187                *self
188            }
189        }
190
191        impl<$($ty_params)*> Copy for TaggedRef<'_, $($ty_args)*> {}
192
193        // SAFETY: `TaggedRef` conceptually holds a `&T` and behaves as such
194        // with respect to aliasing and lifetimes. Accordingly, because
195        // `T: Sync` implies `&T: Sync`, it is safe for `TaggedRef` to
196        // implement `Sync` when the same condition of `T: Sync` holds.
197        unsafe impl<$($ty_params)*> Sync for TaggedRef<'_, $($ty_args)*>
198        where
199            T: Sync,
200        {
201        }
202
203        // SAFETY: `TaggedRef` conceptually holds a `&T` and behaves as such
204        // with respect to aliasing and lifetimes. Accordingly, because
205        // `T: Sync` implies `&T: Send`, it is safe for `TaggedRef` to
206        // implement `Send` when the same condition of `T: Sync` holds.
207        unsafe impl<$($ty_params)*> Send for TaggedRef<'_, $($ty_args)*>
208        where
209            T: Sync,
210        {
211        }
212
213        impl_tagged_ref_shared_mut_common!(
214            TaggedRef,
215            [$($ty_params)*],
216            [$($ty_args)*],
217        );
218    };
219
220    (impl methods, [$($ty_args:tt)*], $doctest_context:literal $(,)?) => {
221        // `Self::new` is defined separately for each `TaggedRef` type in order
222        // to customize the docstring. This function contains the shared
223        // implementation of the function body and is called by `Self::new`.
224        fn new_impl(reference: &'a T, tag: usize) -> Self {
225            let tag = tag & Self::MAX_TAG;
226            // SAFETY: `tag` cannot be greater than `MAX_TAG` after the
227            // bitwise-and.
228            unsafe { Self::new_unchecked(reference, tag) }
229        }
230
231        /// Equivalent to [`Self::new`] but without some runtime checks.
232        ///
233        /// # Safety
234        ///
235        /// `tag` cannot be greater than [`Self::MAX_TAG`].
236        pub unsafe fn new_unchecked(reference: &'a T, tag: usize) -> Self {
237            let ptr = reference.into();
238            // SAFETY: References are necessarily aligned and dereferenceable.
239            // The validity of `tag` is ensured by the caller.
240            let tp = unsafe {
241                TaggedPtr::new_unchecked_dereferenceable(ptr, tag)
242            };
243            Self(tp, PhantomData)
244        }
245
246        /// Gets the reference and tag stored by the tagged reference.
247        pub fn get(self) -> (&'a T, usize) {
248            let (ptr, tag) = self.0.get();
249            // SAFETY: `ptr` came from the valid reference passed to
250            // `Self::new`. The `PhantomData` in `self.1` has the appropriate
251            // lifetime to ensure the reference is still valid.
252            (unsafe { &*ptr.as_ptr() }, tag)
253        }
254
255        /// Gets the reference stored by the tagged reference, without the tag.
256        ///
257        /// Equivalent to [`self.get().0`](Self::get).
258        pub fn get_ref(self) -> &'a T {
259            self.get().0
260        }
261
262        /// Sets the reference without modifying the tag.
263        ///
264        /// This method is equivalent to:
265        ///
266        /// ```
267        #[doc = $doctest_context]
268        /// # trait Ext<'a, T> { fn f(&mut self, reference: &'a T); }
269        /// # impl<'a, T> Ext<'a, T> for TaggedRef<'a, T> {
270        /// # fn f(&mut self, reference: &'a T) {
271        /// *self = self.with_ref(reference);
272        /// # }}
273        /// ```
274        ///
275        /// Because this method mutates the tagged reference in-place, the new
276        /// reference must have the exact same lifetime, `'a`. As a
277        /// consequence, any data currently borrowed for `'a` by the old
278        /// reference will remain borrowed even once the reference is updated.
279        ///
280        /// [`Self::with_ref`] may be more flexible in some situations, as it
281        /// returns a new tagged reference that can have a different lifetime.
282        pub fn set_ref(&mut self, reference: &'a T) {
283            *self = self.with_ref(reference);
284        }
285
286        /// Creates a new tagged reference with the same tag but a different
287        /// reference.
288        ///
289        /// This method is equivalent to:
290        ///
291        /// ```
292        #[doc = $doctest_context]
293        /// # trait Ext<T> { fn f(self, reference: &T) -> TaggedRef<'_, T>; }
294        /// # impl<T> Ext<T> for TaggedRef<'_, T> {
295        /// # fn f(self, reference: &T) -> TaggedRef<'_, T> {
296        /// TaggedRef::new(reference, self.tag())
297        /// # }}
298        /// ```
299        pub fn with_ref(
300            self,
301            reference: &T,
302        ) -> TaggedRef<'_, $($ty_args)*> {
303            TaggedRef::new(reference, self.tag())
304        }
305
306        /// Gets the tag stored by the tagged reference. Equivalent to
307        /// [`self.get().1`](Self::get).
308        pub fn tag(self) -> usize {
309            self.get().1
310        }
311
312        /// Sets the tag without modifying the reference.
313        ///
314        /// This method is equivalent to:
315        ///
316        /// ```
317        #[doc = $doctest_context]
318        /// # trait Ext { fn f(&mut self, tag: usize); }
319        /// # impl<T> Ext for TaggedRef<'_, T> {
320        /// # fn f(&mut self, tag: usize) {
321        /// *self = Self::new(self.get_ref(), tag);
322        /// # }}
323        /// ```
324        pub fn set_tag(&mut self, tag: usize) {
325            *self = Self::new(self.get_ref(), tag);
326        }
327    };
328}
329
330impl_explicit_tagged_ref_common!(TaggedRef);
331impl_tagged_ref_common!(
332    [T, const BITS: Bits],
333    [T, BITS],
334    "# type TaggedRef<'a, T> = tagged_pointer::TaggedRef<'a, T, 0>;",
335);
336
337with_bits_doc! {
338    /// Mutable version of [`TaggedRef`].
339    ///
340    /// Like [`TaggedRef`], this type stores a reference and an integer tag,
341    /// but the reference in this type is mutable.
342    #[repr(transparent)]
343    pub struct TaggedMutRef<'a, T, const BITS: Bits>(
344        TaggedPtr<T, BITS>,
345        PhantomData<&'a mut T>,
346    );
347}
348
349impl<'a, T, const BITS: Bits> TaggedMutRef<'a, T, BITS> {
350    /// Creates a new tagged mutable reference. Only the lower `BITS` bits of
351    /// `tag` are stored.
352    pub fn new(reference: &'a mut T, tag: usize) -> Self {
353        Self::new_impl(reference, tag)
354    }
355}
356
357/// Common code for [`TaggedMutRef`] and [`implicit::TaggedMutRef`].
358macro_rules! impl_tagged_mut_ref_common {
359    (
360        [$($ty_params:tt)*],
361        [$($ty_args:tt)*],
362        $doctest_context:literal $(,)?
363    ) => {
364        const _: () = {
365            use core::marker::PhantomData;
366            use core::ptr;
367
368            impl<'a, $($ty_params)*> TaggedMutRef<'a, $($ty_args)*> {
369                impl_tagged_mut_ref_common!(
370                    impl methods,
371                    [$($ty_args)*],
372                    $doctest_context,
373                );
374            }
375        };
376
377        impl<$($ty_params)*> AsMut<T> for TaggedMutRef<'_, $($ty_args)*> {
378            fn as_mut(&mut self) -> &mut T {
379                self.get_mut_ref()
380            }
381        }
382
383        // SAFETY: `TaggedMutRef` conceptually holds a `&mut T` and behaves as
384        // such with respect to aliasing and lifetimes. Accordingly, because
385        // `T: Sync` implies `&mut T: Sync`, it is safe for `TaggedMutRef` to
386        // implement `Sync` when the same condition of `T: Sync` holds.
387        unsafe impl<$($ty_params)*> Sync for TaggedMutRef<'_, $($ty_args)*>
388        where
389            T: Sync,
390        {
391        }
392
393        // SAFETY: `TaggedMutRef` conceptually holds a `&mut T` and behaves as
394        // such with respect to aliasing and lifetimes. Accordingly, because
395        // `T: Send` implies `&mut T: Send`, it is safe for `TaggedRef` to
396        // implement `Send` when the same condition of `T: Send` holds.
397        unsafe impl<$($ty_params)*> Send for TaggedMutRef<'_, $($ty_args)*>
398        where
399            T: Send,
400        {
401        }
402
403        impl_tagged_ref_shared_mut_common!(
404            TaggedMutRef,
405            [$($ty_params)*],
406            [$($ty_args)*],
407        );
408    };
409
410    (impl methods, [$($ty_args:tt)*], $doctest_context:literal $(,)?) => {
411        // `Self::new` is defined separately for each `TaggedMutRef` type in
412        // order to customize the docstring. This function contains the shared
413        // implementation of the function body and is called by `Self::new`.
414        fn new_impl(reference: &'a mut T, tag: usize) -> Self {
415            let tag = tag & Self::MAX_TAG;
416            // SAFETY: `tag` cannot be greater than `MAX_TAG` after the
417            // bitwise-and.
418            unsafe { Self::new_unchecked(reference, tag) }
419        }
420
421        /// Equivalent to [`Self::new`] but without some runtime checks.
422        ///
423        /// # Safety
424        ///
425        /// `tag` cannot be greater than [`Self::MAX_TAG`].
426        pub unsafe fn new_unchecked(reference: &'a mut T, tag: usize) -> Self {
427            let ptr = reference.into();
428            // SAFETY: References are necessarily aligned and dereferenceable.
429            // The validity of `tag` is ensured by the caller.
430            let tp = unsafe {
431                TaggedPtr::new_unchecked_dereferenceable(ptr, tag)
432            };
433            Self(tp, PhantomData)
434        }
435
436        /// Creates an immutable [`TaggedRef`] with the same reference and tag.
437        ///
438        /// This method reborrows the reference; see also
439        /// [`Self::into_tagged_ref`], which preserves the lifetime.
440        pub fn to_tagged_ref(&self) -> TaggedRef<'_, $($ty_args)*> {
441            // The return type of this method ensures that Rust's standard
442            // borrowing rules will guarantee soundness. The `TaggedRef` can't
443            // outlive `'a` (its lifetime is that of `self`) , and the data
444            // can't be mutated while the `TaggedRef` is active, since this
445            // method borrows the `TaggedMutRef` immutably.
446            TaggedRef(self.0, PhantomData)
447        }
448
449        /// Converts the tagged reference into an immutable [`TaggedRef`].
450        ///
451        /// [`Self::to_tagged_ref`] reborrows the reference instead of
452        /// consuming the [`TaggedMutRef`].
453        pub fn into_tagged_ref(self) -> TaggedRef<'a, $($ty_args)*> {
454            // The `TaggedMutRef` is consumed, preventing future mutable
455            // access, so it's safe to return a `TaggedRef` with the same
456            // lifetime.
457            TaggedRef(self.0, PhantomData)
458        }
459
460        /// Returns an immutable reborrow of the reference stored by the tagged
461        /// reference, along with a copy of the tag.
462        ///
463        /// See [`Self::get_mut`] if you need a mutable reference.
464        pub fn get(&self) -> (&T, usize) {
465            self.to_tagged_ref().get()
466        }
467
468        /// Returns a mutable reborrow of the reference stored by the tagged
469        /// reference, along with a copy of the tag.
470        pub fn get_mut(&mut self) -> (&mut T, usize) {
471            let (ptr, tag) = self.0.get();
472            // SAFETY: `ptr` came from the valid reference passed to
473            // `Self::new`. The `PhantomData` in `self.1` has the appropriate
474            // lifetime to ensure the reference is still valid, and the return
475            // type of this method has the correct lifetime to ensure the data
476            // cannot be aliased.
477            (unsafe { &mut *ptr.as_ptr() }, tag)
478        }
479
480        /// Deconstructs the tagged reference into its constituent parts: the
481        /// reference (with the original lifetime `'a`) and the tag.
482        pub fn into_inner(self) -> (&'a mut T, usize) {
483            let (ptr, tag) = self.0.get();
484            // SAFETY: `ptr` came from the valid reference passed to
485            // `Self::new`. The `PhantomData` in `self.1` has the appropriate
486            // lifetime to ensure the reference is still valid, and this method
487            // takes ownership of `self` to ensure the data cannot be aliased.
488            (unsafe { &mut *ptr.as_ptr() }, tag)
489        }
490
491        /// Returns an immutable reborrow of the reference stored by the tagged
492        /// reference.
493        ///
494        /// See [`Self::get_mut_ref`] if you need a mutable reference.
495        pub fn get_ref(&self) -> &T {
496            self.get().0
497        }
498
499        /// Returns a mutable reborrow of the reference stored by the tagged
500        /// reference.
501        pub fn get_mut_ref(&mut self) -> &mut T {
502            self.get_mut().0
503        }
504
505        /// Gets the reference stored by the tagged reference with its original
506        /// lifetime (`'a`), consuming the tagged reference in the process.
507        ///
508        /// Equivalent to <code>[Self::into_inner]\().0</code>.
509        pub fn into_ref(self) -> &'a mut T {
510            self.into_inner().0
511        }
512
513        /// Sets the reference without modifying the tag.
514        ///
515        /// This method is equivalent to:
516        ///
517        /// ```
518        #[doc = $doctest_context]
519        /// # trait Ext<'a, T> { fn f(&mut self, reference: &'a mut T); }
520        /// # impl<'a, T> Ext<'a, T> for TaggedMutRef<'a, T> {
521        /// # fn f(&mut self, reference: &'a mut T) {
522        /// *self = self.with_ref(reference);
523        /// # }}
524        /// ```
525        ///
526        /// Because this method mutates the tagged reference in-place, the new
527        /// reference must have the exact same lifetime, `'a`. As a
528        /// consequence, any data currently borrowed for `'a` by the old
529        /// reference will remain borrowed even once the reference is updated.
530        ///
531        /// [`Self::with_ref`] may be more flexible in some situations, as it
532        /// returns a new tagged reference that can have a different lifetime.
533        pub fn set_ref(&mut self, reference: &'a mut T) {
534            *self = self.with_ref(reference);
535        }
536
537        /// Creates a new tagged reference with the same tag but a different
538        /// reference.
539        ///
540        /// This method is equivalent to:
541        ///
542        /// ```
543        #[doc = $doctest_context]
544        /// # trait Ext<T> {
545        /// #     fn f<'b>(&mut self, r: &'b mut T) -> TaggedMutRef<'b, T>;
546        /// # }
547        /// # impl<T> Ext<T> for TaggedMutRef<'_, T> {
548        /// # fn f<'b>(
549        /// #     &mut self, reference: &'b mut T,
550        /// # ) -> TaggedMutRef<'b, T> {
551        /// TaggedMutRef::new(reference, self.tag())
552        /// # }}
553        /// ```
554        pub fn with_ref<'b>(
555            &self,
556            reference: &'b mut T,
557        ) -> TaggedMutRef<'b, $($ty_args)*> {
558            TaggedMutRef::new(reference, self.tag())
559        }
560
561        /// Gets the tag stored by the tagged reference. Equivalent to
562        /// [`self.get().1`](Self::get).
563        pub fn tag(&self) -> usize {
564            self.get().1
565        }
566
567        /// Sets the tag without modifying the reference.
568        ///
569        /// This method behaves like the following, but it doesn't require
570        /// ownership of the tagged reference:
571        ///
572        /// ```compile_fail
573        #[doc = $doctest_context]
574        /// # trait Ext { fn f(&mut self, tag: usize); }
575        /// # impl<T> Ext for TaggedMutRef<'_, T> {
576        /// # fn f(&mut self, tag: usize) {
577        /// // Error: can't call `into_ref` on `&mut Self`.
578        /// *self = Self::new(self.into_ref(), tag);
579        /// # }}
580        /// ```
581        pub fn set_tag(&mut self, tag: usize) {
582            // SAFETY: `self` is a valid reference, so it's safe to read from
583            // it, but because `Self` is not `Copy`, we must ensure it isn't
584            // accessed until another value is written to it with `ptr::write`.
585            // (Conceptually, we're temporarily taking ownership of `*self`.)
586            let this = unsafe { ptr::read(self) };
587            let this = Self::new(this.into_ref(), tag);
588            // SAFETY: `self` is a mutable reference, so it is necessarily
589            // aligned and valid for writes.
590            unsafe {
591                ptr::write(self, this);
592            }
593        }
594
595        /// Creates a new tagged reference that reborrows the referenced data
596        /// with a different lifetime.
597        ///
598        /// This method is equivalent to:
599        ///
600        /// ```
601        #[doc = $doctest_context]
602        /// # trait Ext<T> { fn f(&mut self) -> TaggedMutRef<'_, T>; }
603        /// # impl<T> Ext<T> for TaggedMutRef<'_, T> {
604        /// # fn f(&mut self) -> TaggedMutRef<'_, T> {
605        /// let (reference, tag) = self.get_mut();
606        /// TaggedMutRef::new(reference, tag)
607        /// # }}
608        /// ```
609        pub fn reborrow(&mut self) -> TaggedMutRef<'_, $($ty_args)*> {
610            let (reference, tag) = self.get_mut();
611            TaggedMutRef::new(reference, tag)
612        }
613    };
614}
615
616impl_explicit_tagged_ref_common!(TaggedMutRef);
617impl_tagged_mut_ref_common!(
618    [T, const BITS: Bits],
619    [T, BITS],
620    "# type TaggedMutRef<'a, T> = tagged_pointer::TaggedMutRef<'a, T, 0>;",
621);
622
623pub mod implied;