RcUninit

Cyclic Rc without new_cyclic.

Only works with nightly due to usage of #[feature(alloc_layout_extra)].

lib.rs:

Defines RcUninit, an Rc with deferred initialization.

[RcUninit] solves two problems with Rc::new_cyclic, namely:

1. Inability to use across await points - new_cyclic takes a closure that is not async.
2. Instantiation of complex cyclic structures is cumbersome and has a high mental overhead.

Examples

use rcuninit::RcUninit;
use std::rc::Rc;

// Must be called at least once per program invocation.
unsafe {
    rcuninit::check_sanity();
}

let rcuninit = RcUninit::new();

// Acquire a weak pointer.
let weak = rcuninit.weak();

assert!(weak.upgrade().is_none());

// Now initialize, returns an Rc and makes associated Weaks upgradable.
let strong = rcuninit.init(String::from("lorem ipsum"));

assert_eq!(*weak.upgrade().unwrap(), "lorem ipsum");
assert!(Rc::ptr_eq(&strong, &weak.upgrade().unwrap()));

Here's an example of initialization across an await point. This is not possible with Rc::new_cyclic.

use rcuninit::RcUninit;
use std::{future::poll_fn, rc::Rc, task::Poll};

async fn f() {
    let rcuninit = RcUninit::new();
    let weak = rcuninit.weak();

    poll_fn(|_| Poll::Ready(())).await;

    let strong = rcuninit.init(String::from("lorem ipsum"));
    assert_eq!(*weak.upgrade().unwrap(), "lorem ipsum");
}

Complex Cyclic Structures

The other issue mentioned regarding Rc::new_cyclic is its cumbersome nature when attempting to declare complex cyclic structures. Suppose we want to construct a structure A => B => C -> A, where => and -> denote a strong and weak pointer, respectively. The following two examples show the difference between [RcUninit] and Rc::new_cyclic.

use rcuninit::RcUninit;
use std::rc::{Rc, Weak};

unsafe {
    rcuninit::check_sanity();
}

let a_un = RcUninit::new();
let b_un = RcUninit::new();
let c_un = RcUninit::new();

let c = c_un.init(C { a: a_un.weak() });
let b = b_un.init(B { c });
let a = a_un.init(A { b });

assert!(Rc::ptr_eq(&a.b.c.a.upgrade().unwrap(), &a));

struct A {
    b: Rc<B>,
}
struct B {
    c: Rc<C>,
}
struct C {
    a: Weak<A>,
}

Now compare this to the construction of the same structure using Rc::new_cyclic. Structure definitions hidden for brevity, but they are identical as above.

use std::rc::{Rc, Weak};

let mut b: Option<Rc<B>> = None;
let mut c: Option<Rc<C>> = None;

let a = Rc::new_cyclic(|a_weak| {
    let b_rc = Rc::new_cyclic(|b_weak| {
        let c_rc = Rc::new(C { a: a_weak.clone() });
        c = Some(c_rc.clone());
        B { c: c_rc }
    });

    b = Some(b_rc.clone());
    A { b: b_rc }
});

let b = b.unwrap();
let c = c.unwrap();

assert!(Rc::ptr_eq(&a.b.c.a.upgrade().unwrap(), &a));

Note that we store a, b, and c into variables because we imagine the code having some use for them later on.

One alternative in the last example is to implement get methods on the structs to get the values out, but that is still noisy and cumbersome. This example only grows more difficult to mentally process when there are more pointers, eventually becoming unwieldy to deal with.

Another option here is to use interior mutability and use set_weak_pointer on these structs to get the desired effect, but that requires us to set pointers after initialization which is prone to the inadvertent creation of reference cycles.

Sanity Checking

This crate makes assumptions about how data inside [Rc] is laid out. As of writing this documentation, Rc holds a pointer to RcInner.

#[repr(C)]
struct RcInner<T: ?Sized> {
    strong: Cell<usize>,
    weak: Cell<usize>,
    value: T,
}

Internally, we consume an Rc<MaybeUninit<T>> via Rc::into_raw, which gives us a pointer to value field. We then calculate the offsets manually (accounting for padding) to reach strong and weak such that these fields can be manipulated directly to serve the purposes of [RcUninit].

To guard against future changes in the standard library, we must perform a sanity check every time the program is run. This is to test whether the values we are reaching into are actually located where we believe they should be located.

This sanity checking is performed by calling:

use rcuninit::check_sanity;

unsafe {
    check_sanity();
}

See [check_sanity] for more details.

Native Rust Support

There are ongoing discussions on getting RcUninit and related features (UniqueRc) into std. This crate will be superceded once RcUninit is natively supported.

• https://github.com/rust-lang/libs-team/issues/90
• https://github.com/rust-lang/rust/issues/112566