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;