token_ref_cell/
token.rs

1//! Implementations of [`Token`] used with [`TokenRefCell`](crate::TokenRefCell).
2//!
3//! The recommended token implementation is [`BoxToken`].
4
5use core::{
6    fmt,
7    marker::PhantomData,
8    ops::{Deref, DerefMut},
9    pin::Pin,
10    ptr,
11    sync::atomic::{AtomicUsize, Ordering},
12};
13
14#[doc(hidden)]
15pub use crate::repr_hack::TokenId;
16
17/// Token type to be used with [`TokenRefCell`](crate::TokenRefCell).
18///
19/// It defines an `Id` type, which is stored in the cell and used to check its accesses.
20///
21/// `TokenId` bound is a hidden trait used to hack Rust type system in order to allow
22/// `TokenRefCell` being defined with `#[repr(transparent)]` when `Id` is `()`.
23/// It can be implemented using hidden `impl_token_id!` macro, for example
24/// `impl_token_id!(PtrId<T: ?Sized>)`.
25/// <br>
26/// This bound is temporary and will be removed when Rust type system will allow
27/// const expressions like `size_of::<Tk>() == 0` to be used as generic parameter.
28///
29/// # Safety
30///
31/// If [`Token::is_unique`] returns true, then there must be no other instances of the same token
32/// type with [`Token::id`] returning the same id as the current "unique" instance;
33/// if the token type is neither `Send` nor `Sync`, this unicity constraint is relaxed to the
34/// current thread.
35/// <br>
36/// Token implementations can rely on the fact that [`TokenRefCell`](crate::TokenRefCell),
37/// [`Ref`](crate::Ref), [`RefMut`](crate::RefMut), [`Reborrow`](crate::Reborrow),
38/// and [`ReborrowMut`](crate::ReborrowMut) are invariant on their `Tk: Token` generic parameter.
39pub unsafe trait Token {
40    /// Id of the token.
41    type Id: Clone + Eq + TokenId;
42    /// Returns the token id.
43    fn id(&self) -> Self::Id;
44    /// Returns true if the token is "unique", see [safety](Self#safety)
45    fn is_unique(&mut self) -> bool;
46}
47
48/// Wrapper for pointer used as [`Token::Id`] .
49///
50/// The pointer is only used for comparison, so `PtrId` can implement
51/// `Send`/`Sync` because the pointee is never accessed.
52pub struct PtrId<T: ?Sized>(*const T);
53
54impl<T: ?Sized> PtrId<T> {
55    /// Wrap a pointer.
56    #[inline]
57    pub fn new(ptr: *const T) -> Self {
58        Self(ptr)
59    }
60}
61
62impl<T: ?Sized> From<*const T> for PtrId<T> {
63    #[inline]
64    fn from(value: *const T) -> Self {
65        Self(value)
66    }
67}
68
69impl<T: ?Sized> From<*mut T> for PtrId<T> {
70    #[inline]
71    fn from(value: *mut T) -> Self {
72        Self(value)
73    }
74}
75
76impl<T: ?Sized> From<&T> for PtrId<T> {
77    #[inline]
78    fn from(value: &T) -> Self {
79        Self(value)
80    }
81}
82
83impl<T: ?Sized> From<&mut T> for PtrId<T> {
84    #[inline]
85    fn from(value: &mut T) -> Self {
86        Self(value)
87    }
88}
89
90// SAFETY: the pointee is never accessed
91unsafe impl<T: ?Sized> Send for PtrId<T> {}
92// SAFETY: the pointee is never accessed
93unsafe impl<T: ?Sized> Sync for PtrId<T> {}
94
95impl<T: ?Sized> fmt::Debug for PtrId<T> {
96    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
97        write!(f, "{:?}", self.0)
98    }
99}
100
101impl<T: ?Sized> Copy for PtrId<T> {}
102impl<T: ?Sized> Clone for PtrId<T> {
103    #[inline]
104    fn clone(&self) -> Self {
105        *self
106    }
107}
108
109impl<T: ?Sized> PartialEq for PtrId<T> {
110    #[inline]
111    fn eq(&self, other: &Self) -> bool {
112        ptr::eq(self.0, other.0)
113    }
114}
115impl<T: ?Sized> Eq for PtrId<T> {}
116
117/// Generate a zero-sized singleton token type.
118///
119/// The generated type provides a `new` method, as well as a fallible
120/// `try_new` version. These methods ensure there is only a single
121/// instance of the singleton at a time; singleton can still be dropped
122/// and re-instantiated.
123#[macro_export]
124macro_rules! singleton_token {
125    ($name:ident) => {
126        $crate::singleton_token!(pub(self) struct $name;);
127    };
128    ($(#[$($attr:meta)*])* struct $name:ident;) => {
129        $crate::singleton_token!($(#[$($attr)*])* pub(self) struct $name;);
130    };
131    ($(#[$($attr:meta)*])* $vis:vis struct $name:ident;) => {
132        $(#[$($attr)*])*
133        #[allow(clippy::needless_pub_self)]
134        $vis struct $name;
135        #[allow(unused, clippy::needless_pub_self)]
136        const _: () = {
137            static INITIALIZED: ::core::sync::atomic::AtomicBool = ::core::sync::atomic::AtomicBool::new(false);
138            impl $name {
139                /// Instantiate the singleton token.
140                ///
141                /// # Panics
142                ///
143                /// Panics if the singleton token is already instantiated.
144                #[allow(clippy::new_without_default)]
145                $vis fn new() -> Self {
146                    Self::try_new().unwrap()
147                }
148
149                /// Try to nstantiate the singleton token.
150                $vis fn try_new() -> Result<Self, $crate::error::AlreadyInitialized> {
151                    match INITIALIZED.compare_exchange(false, true, Ordering::Acquire, Ordering::Relaxed) {
152                        Ok(_) => Ok(Self),
153                        Err(_) => Err($crate::error::AlreadyInitialized),
154                    }
155                }
156            }
157
158            impl Drop for $name {
159                fn drop(&mut self) {
160                    INITIALIZED.store(false, ::core::sync::atomic::Ordering::Release);
161                }
162            }
163
164            // SAFETY: forged token initialization guarantees there is only one single instance
165            unsafe impl $crate::token::Token for $name {
166                type Id = ();
167
168                #[inline]
169                fn id(&self) -> Self::Id {}
170
171                #[inline]
172                fn is_unique(&mut self) -> bool {
173                    true
174                }
175            }
176        };
177    };
178}
179
180static DYNAMIC_COUNTER: AtomicUsize = AtomicUsize::new(0);
181
182/// Dynamic token, equivalent to an `usize` in memory.
183///
184/// Each token instantiated with [`DynamicToken::new`] is unique,
185/// but the number of instantiated token in all the program lifetime
186/// **must** not overflow `isize::MAX`.
187///
188/// This constraint comes from the trivial unicity implementation,
189/// an `AtomicUsize`, with no possible reuse of dropped tokens.
190/// You should use smart-pointer based token instead, as they use
191/// non-trivial unicity algorithm named "memory allocator".
192#[derive(Debug, Eq, PartialEq)]
193pub struct DynamicToken(usize);
194
195impl DynamicToken {
196    /// Create a unique token.
197    ///
198    /// # Panics
199    ///
200    /// Panics when `usize::MAX` tokens has already been created.
201    pub fn new() -> Self {
202        let incr = |c| (c != usize::MAX).then(|| c + 1);
203        match DYNAMIC_COUNTER.fetch_update(Ordering::Relaxed, Ordering::Relaxed, incr) {
204            Ok(c) => Self(c + 1),
205            Err(_) => panic!("No more dynamic token available"),
206        }
207    }
208}
209
210impl Default for DynamicToken {
211    fn default() -> Self {
212        Self::new()
213    }
214}
215
216// SAFETY: Each `DynamicToken` has a different inner token and cannot be cloned
217unsafe impl Token for DynamicToken {
218    type Id = usize;
219
220    #[inline]
221    fn id(&self) -> Self::Id {
222        self.0
223    }
224
225    #[inline]
226    fn is_unique(&mut self) -> bool {
227        true
228    }
229}
230
231/// Abstraction of a reference as a token.
232///
233/// The reference should point to a pinned object, otherwise moving the object
234/// will "invalidate" the cells initialized with the previous reference.
235#[derive(Debug)]
236#[repr(transparent)]
237pub struct RefToken<T: ?Sized>(T);
238
239impl<T: ?Sized> RefToken<T> {
240    /// Convert an immutable reference into an immutable `RefToken` reference.
241    #[inline]
242    pub fn from_ref(t: &T) -> &Self
243    where
244        T: Unpin,
245    {
246        // SAFETY: `RefToken` is `repr(transparent)`
247        unsafe { &*(t as *const T as *const Self) }
248    }
249
250    /// Convert a mutable reference into a mutable `RefToken` reference.
251    #[inline]
252    pub fn from_mut(t: &mut T) -> &mut Self
253    where
254        T: Unpin,
255    {
256        // SAFETY: `RefToken` is `repr(transparent)`
257        unsafe { &mut *(t as *mut T as *mut Self) }
258    }
259
260    /// Convert a pinned immutable reference into an immutable `RefToken` reference.
261    #[inline]
262    pub fn from_pin(t: Pin<&T>) -> &Self {
263        // SAFETY: `RefToken` is `repr(transparent)`
264        unsafe { &*(t.get_ref() as *const T as *const Self) }
265    }
266
267    /// Convert a pinned mutable reference into a mutable `RefToken` reference.
268    #[inline]
269    pub fn from_pin_mut(t: Pin<&mut T>) -> &mut Self {
270        // SAFETY: mutable ref is never accessed if `T` is not `Unpin`,
271        // and `RefToken` is `repr(transparent)`
272        unsafe { &mut *(t.get_unchecked_mut() as *mut T as *mut Self) }
273    }
274
275    /// Get a pinned immutable reference.
276    #[inline]
277    pub fn as_pin(&self) -> Pin<&T> {
278        // SAFETY: `RefToken` was initialized with pinned reference unless `T: Unpin`
279        unsafe { Pin::new_unchecked(&self.0) }
280    }
281
282    /// Get a pinned mutable reference.
283    #[inline]
284    pub fn as_pin_mut(&mut self) -> Pin<&mut T> {
285        // SAFETY: `PinToken` was initialized with pinned reference unless `T: Unpin`
286        unsafe { Pin::new_unchecked(&mut self.0) }
287    }
288}
289
290impl<T: ?Sized> Deref for RefToken<T> {
291    type Target = T;
292
293    #[inline]
294    fn deref(&self) -> &Self::Target {
295        &self.0
296    }
297}
298
299impl<T: Unpin + ?Sized> DerefMut for RefToken<T> {
300    #[inline]
301    fn deref_mut(&mut self) -> &mut Self::Target {
302        &mut self.0
303    }
304}
305
306impl<T: ?Sized> AsRef<T> for RefToken<T> {
307    #[inline]
308    fn as_ref(&self) -> &T {
309        &self.0
310    }
311}
312
313impl<T: Unpin + ?Sized> AsMut<T> for RefToken<T> {
314    #[inline]
315    fn as_mut(&mut self) -> &mut T {
316        &mut self.0
317    }
318}
319
320impl<'a, T: Unpin + ?Sized> From<&'a T> for &'a RefToken<T> {
321    #[inline]
322    fn from(value: &'a T) -> Self {
323        RefToken::from_ref(value)
324    }
325}
326
327impl<'a, T: Unpin + ?Sized> From<&'a mut T> for &'a mut RefToken<T> {
328    #[inline]
329    fn from(value: &'a mut T) -> Self {
330        RefToken::from_mut(value)
331    }
332}
333
334impl<'a, T: ?Sized> From<Pin<&'a T>> for &'a RefToken<T> {
335    #[inline]
336    fn from(value: Pin<&'a T>) -> Self {
337        RefToken::from_pin(value)
338    }
339}
340
341impl<'a, T: ?Sized> From<Pin<&'a mut T>> for &'a mut RefToken<T> {
342    #[inline]
343    fn from(value: Pin<&'a mut T>) -> Self {
344        RefToken::from_pin_mut(value)
345    }
346}
347
348// SAFETY: token uniqueness is guaranteed by mutable reference properties
349unsafe impl<T: ?Sized> Token for RefToken<T> {
350    type Id = PtrId<T>;
351
352    #[inline]
353    fn id(&self) -> Self::Id {
354        (&self.0).into()
355    }
356
357    #[inline]
358    fn is_unique(&mut self) -> bool {
359        true
360    }
361}
362
363#[cfg(feature = "alloc")]
364mod with_alloc {
365    extern crate alloc;
366    use alloc::{boxed::Box, rc::Rc, sync::Arc};
367
368    use crate::token::{PtrId, Token};
369
370    /// Dummy struct which can be used with smart-pointer-based token implementations.
371    ///
372    /// Smart-pointer requires a non-zero-sized type parameter to be used as token.
373    /// Use it if, like me, you don't like finding names for dummy objects;
374    /// `Box<AllocatedToken>` is still better than `Box<u8>`.
375    #[allow(dead_code)]
376    #[derive(Debug, Default)]
377    pub struct AllocatedToken(u8);
378
379    /// A wrapper for `Box<AllocatedToken>`.
380    ///
381    /// This is the recommended token implementation.
382    #[derive(Debug, Default)]
383    pub struct BoxToken(Box<AllocatedToken>);
384
385    impl BoxToken {
386        /// Allocate a `BoxToken`.
387        pub fn new() -> Self {
388            Self::default()
389        }
390    }
391
392    // SAFETY: `BoxToken` is a wrapper around `Box` which implements `Token`
393    unsafe impl Token for BoxToken {
394        type Id = <Box<AllocatedToken> as Token>::Id;
395
396        #[inline]
397        fn id(&self) -> Self::Id {
398            self.0.id()
399        }
400
401        #[inline]
402        fn is_unique(&mut self) -> bool {
403            self.0.is_unique()
404        }
405    }
406
407    trait NotZeroSized<T> {
408        const ASSERT_SIZE_IS_NOT_ZERO: () = assert!(size_of::<T>() > 0);
409    }
410
411    impl<T> NotZeroSized<T> for T {}
412
413    macro_rules! check_not_zero_sized {
414        ($T:ty) => {
415            #[allow(path_statements)]
416            {
417                <$T>::ASSERT_SIZE_IS_NOT_ZERO;
418            }
419        };
420    }
421
422    // SAFETY: It's not possible to have simultaneously two boxes with the same pointer/token id,
423    // as long as `T` is not zero-sized (ensured by a compile-time check)
424    /// `T` must not be zero-sized.
425    unsafe impl<T> Token for Box<T> {
426        type Id = PtrId<T>;
427
428        #[inline]
429        fn id(&self) -> Self::Id {
430            check_not_zero_sized!(T);
431            self.as_ref().into()
432        }
433
434        #[inline]
435        fn is_unique(&mut self) -> bool {
436            check_not_zero_sized!(T);
437            true
438        }
439    }
440
441    // SAFETY: `Rc::get_mut` ensures the unicity of the `Rc` instance "owning" its inner pointer,
442    // as long as `T` is not zero-sized (ensured by a compile-time check)
443    /// `T` must not be zero-sized.
444    unsafe impl<T> Token for Rc<T> {
445        type Id = PtrId<T>;
446
447        #[inline]
448        fn id(&self) -> Self::Id {
449            check_not_zero_sized!(T);
450            self.as_ref().into()
451        }
452
453        #[inline]
454        fn is_unique(&mut self) -> bool {
455            check_not_zero_sized!(T);
456            Rc::get_mut(self).is_some()
457        }
458    }
459
460    // SAFETY: `Arc::get_mut` ensures the unicity of the `Rc` instance "owning" its inner pointer,
461    // as long as `T` is not zero-sized (ensured by a compile-time check)
462    /// `T` must not be zero-sized.
463    unsafe impl<T> Token for Arc<T> {
464        type Id = PtrId<T>;
465
466        #[inline]
467        fn id(&self) -> Self::Id {
468            check_not_zero_sized!(T);
469            self.as_ref().into()
470        }
471
472        #[inline]
473        fn is_unique(&mut self) -> bool {
474            check_not_zero_sized!(T);
475            Arc::get_mut(self).is_some()
476        }
477    }
478}
479#[cfg(feature = "alloc")]
480pub use with_alloc::*;
481
482#[cfg(feature = "std")]
483mod with_std {
484    use std::{
485        any::TypeId, cell::RefCell, collections::BTreeSet, fmt, fmt::Formatter,
486        marker::PhantomData, sync::Mutex,
487    };
488
489    use crate::{error::AlreadyInitialized, token::Token};
490
491    static TYPE_TOKENS: Mutex<BTreeSet<TypeId>> = Mutex::new(BTreeSet::new());
492
493    /// Zero-sized token implementation which use a type as unicity marker.
494    pub struct TypeToken<T: ?Sized + 'static>(PhantomData<fn(T) -> T>);
495
496    impl<T: ?Sized + 'static> fmt::Debug for TypeToken<T> {
497        fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
498            f.debug_struct("TypeToken").finish()
499        }
500    }
501
502    impl<T: ?Sized + 'static> TypeToken<T> {
503        /// Initializes a `TypeToken`.
504        pub fn new() -> Self {
505            Self::try_new().unwrap()
506        }
507
508        /// Initializes `TypeToken`, fails if it has already been initialized.
509        pub fn try_new() -> Result<Self, AlreadyInitialized> {
510            if TYPE_TOKENS.lock().unwrap().insert(TypeId::of::<Self>()) {
511                Ok(Self(PhantomData))
512            } else {
513                Err(AlreadyInitialized)
514            }
515        }
516    }
517
518    impl<T: ?Sized + 'static> Drop for TypeToken<T> {
519        fn drop(&mut self) {
520            TYPE_TOKENS.lock().unwrap().remove(&TypeId::of::<Self>());
521        }
522    }
523
524    impl<T: ?Sized + 'static> Default for TypeToken<T> {
525        fn default() -> Self {
526            Self::new()
527        }
528    }
529
530    // SAFETY: `TypeToken` initialization guarantees there is only one single instance,
531    // taking into account that it's invariant on `T`
532    unsafe impl<T: ?Sized + 'static> Token for TypeToken<T> {
533        type Id = ();
534
535        fn id(&self) -> Self::Id {}
536
537        fn is_unique(&mut self) -> bool {
538            true
539        }
540    }
541
542    std::thread_local! {
543        static LOCAL_TYPE_TOKENS: RefCell<BTreeSet<TypeId>> = const { RefCell::new(BTreeSet::new()) };
544    }
545
546    /// Zero-sized thread-local token implementation which use a type as unicity marker.
547    pub struct LocalTypeToken<T: ?Sized + 'static>(PhantomData<*mut T>);
548
549    impl<T: ?Sized + 'static> fmt::Debug for LocalTypeToken<T> {
550        fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
551            f.debug_struct("LocalTypeToken").finish()
552        }
553    }
554
555    impl<T: ?Sized + 'static> LocalTypeToken<T> {
556        /// Initializes a `LocalTypeToken`.
557        pub fn new() -> Self {
558            Self::try_new().unwrap()
559        }
560
561        /// Initializes a `LocalTypeToken`, fails if it has already been initialized in the thread.
562        pub fn try_new() -> Result<Self, AlreadyInitialized> {
563            if LOCAL_TYPE_TOKENS.with_borrow_mut(|types| types.insert(TypeId::of::<Self>())) {
564                Ok(Self(PhantomData))
565            } else {
566                Err(AlreadyInitialized)
567            }
568        }
569    }
570
571    impl<T: ?Sized + 'static> Drop for LocalTypeToken<T> {
572        fn drop(&mut self) {
573            LOCAL_TYPE_TOKENS.with_borrow_mut(|types| types.remove(&TypeId::of::<Self>()));
574        }
575    }
576
577    impl<T: ?Sized + 'static> Default for LocalTypeToken<T> {
578        fn default() -> Self {
579            Self::new()
580        }
581    }
582
583    // SAFETY: `LocalTypeToken` initialization guarantees there is only one single instance
584    // in the thread, taking into account that it's invariant on `T`
585    unsafe impl<T: ?Sized + 'static> Token for LocalTypeToken<T> {
586        type Id = ();
587
588        fn id(&self) -> Self::Id {}
589
590        fn is_unique(&mut self) -> bool {
591            true
592        }
593    }
594}
595
596#[cfg(feature = "std")]
597pub use with_std::*;
598
599/// Lifetime-based token implementation.
600#[derive(Debug, PartialEq, Eq)]
601pub struct LifetimeToken<'id>(PhantomData<fn(&'id ()) -> &'id ()>);
602
603impl LifetimeToken<'_> {
604    /// Creates a `LifetimeToken` with a unique lifetime, only valid for the scope of
605    /// the provided closure.
606    pub fn scope<R>(f: impl FnOnce(LifetimeToken) -> R) -> R {
607        f(Self(PhantomData))
608    }
609}
610
611// SAFETY: The only way to instantiate a `LifetimeToken` is using `LifetimeToken::scope`, as
612// well as generativity, and both ensures that the unicity of the token by the unicity of its
613// lifetime.
614unsafe impl Token for LifetimeToken<'_> {
615    type Id = ();
616
617    fn id(&self) -> Self::Id {}
618
619    fn is_unique(&mut self) -> bool {
620        true
621    }
622}
623
624#[cfg(feature = "generativity")]
625impl<'id> From<generativity::Guard<'id>> for LifetimeToken<'id> {
626    fn from(_: generativity::Guard<'id>) -> Self {
627        Self(PhantomData)
628    }
629}
token_ref_cell/token.rs

token_ref_cell/
token.rs
