Rc

Reference Video | Rust docs rc module , Rc struct

  • Rc: sigle threaded reference counting pointers

  • not Sync, not Send. ie: not thread-safe

  • Rc keeps count of the references. when the last reference is dropped, the value inside is also dropped

  • cannot get a mutable reference to the inside unless we use a Cell or RefCell inside Rc

  • so Rc doesnt provide mutability, only provides a way to have multiple references to the same thing

  • its a pointer to some type T, stored on the heap (cant be in a stack because if we have multiple references, whoose stack will have it?)

  • Useful when somethin need to be in multiple places. but who should have the ownership is not really clear. (eg: a config blob in a program)

  • The implementation, conceptually lokks something like:

    
    #![allow(unused_variables)]
    
    fn main() {
    // we create this inner value because the Rc itself should not hold the
    // refcount if it did, each reference to Rc would have its own count
    struct RcInner<T> {
        value: T,
        // here we wrap the usize in a cell because we need to
        // increment/decrement it withou having an exclusive reference
        // this is similar to how RefCell is made
        refcount: Cell<usize>,
    }
    
    // this is a pointer to a location on the heap. we use the RcInner type
    // here the initial thought woulbe be to use a Box to hold the value but
    // Cloning a box will also clone the thing inside it which we dont want
    struct Rc<T> {
        // note that *const is a raw pointer
        // *mut and *const dont have the gurantees that & and &mut have; that
        // & -> noone has exclusive ref. &mut -> noone has shared reference
        // but that non-gurantee allows us to create what Rc provides ( multiple
        // things can have reference to the same thing )
    
        // but when using raw pointers, you can only dereference it using
        // an unsafe block and there is nothing much that you can do with it 
        // besides that
        // [CHANGED] inner: *const RcInner<T>, : use NonNull
        inner: NonNull<RcInner<T>>,
    
        // This marker relates to the dropcheck issue (see point below)
        // This is needed for the completeness of an Rc implementation
        // but dropcheck is a bit complicated and I need more time :)
        // so I have not included it in this code snippet
        // _marker: PhantomData<RcInner<T>>
    
    
        // *const and *mut differs in that fot *mut, you _might_ be able to
        // get an exclusive reference and mutate it. but for *conts, its not
        // okay to mutate. so in general, its not possible to go from 
        // a *const to an exclusive reference
    }
    
    impl<T> Rc<T> {
        pub fn new(v: T) -> Self {
            let inner = Box::new(RcInner {
                value: v,
                refcount: 1,
            });
    
            Rc {
                // notice that here we are not simple dereferencing the Box
                // like inner: &*inner. This is because the Box will get
                // dropped at the end of this scope. but we need the pointer
                // to still be valid. so we cast it into a raw pointer
                // [CHANGED] inner: Box::into_raw(inner), : use NonNull
    
                // SAFETY: Box gives a heap allocation, not a null pointer
                inner: unsafe{ NonNull::new_unchecked(Box::into_raw(inner)) },
            }
        }
    }
    
    // note that we don't require the type T to be Clone. because we dont
    // actually Clone, we only want to increase the RefCount
    impl<T> Clone for Rc<T> {
        fn clone(&self) -> Self {
            // [CHANGED] let inner = unsafe { &*self.inner }; : because NonNull
            // CHANGENOTE: NonNull gives us a as_ref method to dereference
            let inner = unsafe { self.inner.as_ref() };
            // inner.refcount += 1; this is essentially we want to do
            let c = inner.refcount.get();
            inner.refcount.set(c + 1);
            Rc { inner: self.inner  }
        }
    }
    
    // We also need to impl Deref so that methods on inner can be accessed
    // transparently
    impl Deref for Rc<T> {
        type Target = T;
        fn deref(&self) -> &Self::Target {
            // SAFETY: self.inner is a Box that is only deallocated when the
            // Rc goes away. here we _have_ an Rc, therefore the Box has not
            // been deallocated. so dereferencing here is fine
            // [CHANGED] &unsafe { &*self.inner }.value : because NonNull
            // CHANGENOTE: NonNull gives us a as_ref method to dereference
            &unsafe { self.inner.as_ref() }.value
    
        }
    }
    
    impl Drop<T> for Rc<T> {
        fn drop(&mut self) {
            // [CHANGED] let inner = unsafe { &*self.inner }; : because NonNull
            // CHANGENOTE: NonNull gives us a as_ref method to dereference
            let inner = unsafe { self.inner.as_ref() };
            let c = inner.refcount.get();
            if c == 1 {
                // we are dropping inner here because inner lives till the end
                // of this drop function. but when we drop the Box in the
                // following line, this pointer gets invalidated. this is just
                // to make sure that we dont accidently use it again.
                drop(inner);
                // here we get back a box from the pointer, which gets dropped
                // immediately
    
                // [CHANGED] let _ = Box::from_raw(self::inner);
    
                // CHANGENOTE but we cant just do this with a *const pointer.
                // because as mentioned above, *cont can have multiple
                // references. so the compiler doesnt know if its okay to drop.
                // the actual details are a bit subtle. the concept of
                // _Varience_ in rust ties into it(look into it). Therefore we
                // need to use a NonNull to get a *mut from a Box::from_raw()
                // this caused CHANGEs above, wrapping our box in NonNull
    
                // Now, NonNull gives us a method as_ptr() to get a *mut
    
                // SAFETY: at this point, we are the _only_ Rc that is left
                // and we are getting dropped. after this, there wont be any
                // Rcs and no references to T
                let _ = unsafe { Box::from_raw(self::inner.as_ptr()) };
            } else {
                // there are other Rcs. so we do not drop the Box
                inner.refcount.set(c - 1);
            }
        }
    }
    }
    

Limitations of this implementation of Rc

  • Note that there are still issues in this implementations regarding dropcheck Jon did cover it a little in his stream but Its better to look more into it before writing. It would also make this example less complicated. Learch more about dropcheck in rust in thenomicon
  • Note that in the std lib implementation od Rc, it allows the T to be unsized: pub struct Rc<T> where T: ?Sized {}. Rust normally requires all generic arguments to be Sized. This requires some unstable features to implement ourselves and gets a bit complicated. So its is not covered here. Lookup "Coerced unsized trait" for more info on supporting dynamically sized types
  • We dont explicitly mark Rc as not Send and Sync because NonNull is not Send