Now, let's consider one last single-item container before we get into a multi-item container. We'll look into Rc<T>, described by the Rust documentation as being a single-threaded reference-counting pointer. Reference counting pointers are distinct from the usual Rust references in that, while they are allocated on the heap as a Box<T>, cloning a reference counter pointer does not cause a new heap allocation, bitwise copy. Instead, a counter inside the Rc<T> is incremented, somewhat analogously as to the way RefCell<T> works. The drop of an Rc<T> reduces that internal counter and when the counter's value is equal to zero, the heap allocation is released. Let's take a peek inside src/liballoc/rc.s:
pub struct Rc<T: ?Sized> {
ptr: Shared<RcBox<T>>,
phantom: PhantomData<T>,
}
We've already encountered PhantomData<T> in this chapter, so we know that Rc<T> will not directly hold the allocation of T, but the compiler will behave as if it does. Also, we know that T may or may not be sized. The pieces we need to catch up on then are RcBox<T> and Shared<T>. Let's inspect Shared<T> first. Its full name is std::ptr::Shared<T> and it's the same kind of pointer as *mut X except that it is non-zero. There are two variants for creating a new Shared<T>, const unsafe fn new_unchecked(ptr: *mut X) -> Self and fn new(ptr: *mut X) -> Option<Self>. In the first variant, the caller is responsible for ensuring that the pointer is non-null, and in the second the nulled nature of the pointer is checked, like so:
pub fn new(ptr: *mut T) -> Option<Self> {
NonZero::new(ptr as *const T).map(|nz| Shared { pointer: nz })
}
We find the definition and implementation of NonZero<T> in src/libcore/nonzero.rs like so:
pub struct NonZero<T: Zeroable>(T);
impl<T: Zeroable> NonZero<T> {
/// Creates an instance of NonZero with the provided value.
/// You must indeed ensure that the value is actually "non-zero".
#[unstable(feature = "nonzero",
reason = "needs an RFC to flesh out the design",
issue = "27730")]
#[inline]
pub const unsafe fn new_unchecked(inner: T) -> Self {
NonZero(inner)
}
/// Creates an instance of NonZero with the provided value.
#[inline]
pub fn new(inner: T) -> Option<Self> {
if inner.is_zero() {
None
} else {
Some(NonZero(inner))
}
}
/// Gets the inner value.
pub fn get(self) -> T {
self.0
}
}
Zeroable is an unstable trait, which is pretty straightforward:
pub unsafe trait Zeroable {
fn is_zero(&self) -> bool;
}
Every pointer type implements an is_null() -> bool and this trait defers to that function, and NonZero::new defers to Zeroable::is_zero. The presence of a Shared<T>, then, gives the programmer the same freedom as *mut T but with added guarantees about the pointer's nullable situation. Jumping back up to Rc::new:
pub fn new(value: T) -> Rc<T> {
Rc {
// there is an implicit weak pointer owned by all the strong
// pointers, which ensures that the weak destructor never frees
// the allocation while the strong destructor is running, even
// if the weak pointer is stored inside the strong one.
ptr: Shared::from(Box::into_unique(box RcBox {
strong: Cell::new(1),
weak: Cell::new(1),
value,
})),
phantom: PhantomData,
}
}
Box::into_unique converts a Box<T> into a Unique<T>—discussed previously in this chapter—which is then converted into a Shared<T>. This chain preserves the non-null guarantee needed and ensures uniqueness. Now, what about strong and weak in RcBox? Rc<T> provides a method, Self::downgrade(&self) -> Weak<T>, that produces a non-owning pointer, a pointer which does not guarantee the liveness of the referenced data and does not extend its lifetime. This is called a weak reference. Dropping a Weak<T>, likewise, does not imply that T is dropped. The trick here is that a strong reference does extend the liveness of the underlying T—the drop of T is only called when the internal counter of Rc<T> hits zero. For the most part, things rarely require a weak reference, except when a cycle of references exist. Suppose a graph structure were to be constructed where each node holds an Rc<T> to its connected nodes and a cycle exists in the graph. Calling drop on the current node will recursively call drop on the connected nodes, which will recurse again onto the current node and so forth. Were the graph to store a vector of all nodes and have each node store weak references to connections, then a drop of the vector would cause a drop of all nodes, cycles or not. We can see how this works in practice by inspecting the Drop implementation of Rc<T>:
unsafe impl<#[may_dangle] T: ?Sized> Drop for Rc<T> {
fn drop(&mut self) {
unsafe {
let ptr = self.ptr.as_ptr();
self.dec_strong();
if self.strong() == 0 {
// destroy the contained object
ptr::drop_in_place(self.ptr.as_mut());
// remove the implicit "strong weak" pointer
// now that we've destroyed the contents.
self.dec_weak();
if self.weak() == 0 {
Heap.dealloc(ptr as *mut u8,
Layout::for_value(&*ptr));
}
}
}
}
}
This is trimmed some for clarity but the notion is as we've described—when the total number of strong references is zero, a full deallocation occurs. The referenced Heap and Layout are compiler internals and won't be discussed further here, but the interested reader is warmly encouraged to go spelunking on their own. Recall that in Rc<T>::new, both strong and weak counters started at 1. To avoid invalidating the weak pointers, the actual T is only deallocated if there are no strong or weak pointers available. Let's have a look at Drop for Weak<T>, again trimmed some for clarity:
impl<T: ?Sized> Drop for Weak<T> {
fn drop(&mut self) {
unsafe {
let ptr = self.ptr.as_ptr();
self.dec_weak();
// the weak count starts at 1, and will only go to
// zero if all the strong pointers have disappeared.
if self.weak() == 0 {
Heap.dealloc(ptr as *mut u8, Layout::for_value(&*ptr));
}
}
}
}
As expected, the T can only be deallocated when the weak pointer total falls to zero, which is only possible if there are no strong pointers left. That's Rc<T>—a handful of important traits, a specialized box, and a few compiler internals.