An alternative to Rc::new_cyclic

[Kainaik1]

I posted this reddit thread and was referred here.

I'm wondering about natively supporting initialization of Weak at a later point, instead of inside Rc::new_cyclic's data_fn. I propose this to look something like the following.

use std::rc::{RcInit, Rc};
let init_a = RcInit::new();

// Get the weak pointer, points to allocated memory for type some type T
// Weak::upgrade will return None at this point.
let weak = init_a.weak().clone();

// Consumes init_a, preventing double initialization. Since no Rc exists to this instance, we are
// guaranteed that nothing is borrowing anything. UB is avoided.
let a: Rc<T> = init_a.init(T::new());

// Upgrading the weak now succeeds.
let _ = weak.upgrade().unwrap();

This makes it easier to create a bunch objects that need weak references, as we don't need to nest each construction inside of Rc::new_cyclic. It prevents potential stack overflows if large amounts of objects need to be created like a linked list with weak references to parents.

This also allows construction inside async functions, since Rc::new_cyclic is synchronous, we can't call await from within it (example use-case in the wild: here)

A similar pattern can be used for Arc.

Overall, this pattern is more flexible, and I believe it can be implemented behind a fully safe API.

[elidupree]

I don't see why this wouldn't work! Essentially using type-state to be able to give Rc s an additional "possible state" without having to store any more runtime data for them. And it's less magical-looking than new_cyclic, which is good.

Note that this CAN all be implemented in an external crate if you make your own copy of the Rc type, and several crates (like triomphe) implement versions of Rc/Arc with additional features, though I don't know of a crate implementing this one in particular.

[Vorpal]

@elidupree

Note that this CAN all be implemented in an external crate if you make your own copy of the Rc type

It will be limited because derive(CoercePointee) is not yet stable. This is true for all smart pointers outside std currently.

[elidupree]

ah, good to note!

[steffahn]

Just to make sure it isn’t overlooked here, the reply on reddit already mentioned this relevant issue:

Tracking Issue for `UniqueRc`/`UniqueArc`

and a good chunk of the discussion there is exactly around something like this RcInit (called UninitRc in that thread, most often).

(Feel free to keep talking about it here though, to avoid filling up that tracking issue too much.)

[Kainaik1]

I'm a bit confused as to why the tracking issue mentions RcUninit (Cyclic Arc and Rc Builder · Issue #90 · rust-lang/libs-team · GitHub), but instead implements UniqueRc which doesn't solve the problem in an optimal manner since it requires a value to be provided upon construction.

While UniqueRc does allow for cyclic data structures to be created, it must be done by mutating the UniqueRc. Mutation is prone to creating reference cycles. Construction-only assignment of fields, without any mutation to "set" the struct afterwards cannot generate reference cycles. It's also more cumbersome to work with.

For instance, if we have objects A, B, and C, and we want these to connect as A => B => C -> A (=> being strong, -> being weak), then we must do something along the following lines:

let mut a_uniq = UniqueRc::new(A::new());
let a_weak = UniqueRc::downgrade(&a_uniq);

let c = Rc::new(C::new(a_weak));
let b = Rc::new(B::new(c));

a_uniq.set_b(b);
let a = a_uniq.into_rc();

To implement A::set_b, the field A::b must either be

• Option<Rc<B>>: Requires unwrap/clone for each access.
• MaybeUninit<Rc<B>>: Requiring unsafe.
• Weak<B>: Requiring upgrade for every access.

The above also makes it easier to make mistakes in more complex programs where we don't have the full picture. It is not hard to change the above into Rc<RefCell<A>>, and then provide this pointer to C, which would cause a reference cycle to be created once a.borrow_mut().set_b(b) gets called.

On the other hand RcUninit doesn't have this problem, since initialization is deferred. The equivalent would look like the following.

let a_uninit = RcUninit::new();
let b_uninit = RcUninit::new();
let c_uninit = RcUninit::new();

let c = c_uninit.init(C::new(a_uninit.weak()));
let b = b_uninit.init(B::new(c));
let a = a_uninit.init(b);

This creates the structure (A => B => C -> A)

[197g]

One interesting point of RcUnique is that we can have RcUnique<MaybeUninit<T>>::write that returns the initialized RcUnique<T> similar to Box::write, which you called init. It's therefore not clear if we need the uninitialized state as a separate type or if that is not a clean representation already.

[steffahn]

@197g

we can have RcUnique<MaybeUninit<T>>::write that returns the initialized RcUnique<T>

IMO, it’s worth trying to avoid re-iterating too many of points that were already discussed on the linked tracking issue. E.g. this is a relevant existing response to the point having been made there:

For UninitRc<T>, how about using UniqueRc<MaybeUninit<T>> instead?

We can add a similar method write like Box::<MaybeUninit<T>>::write which fits the function of Uninit::<T>::init:

impl<T> UniqueRc<MaybeUninit<T>> {
    pub fn write(rc: UniqueRc<MaybeUninit<T>>, value: T) -> UniqueRc<T> { /* ... */ }
}

While this is a good start it does not remove the need for UninitRc<T>. This is because UninitRc<T>::init is only half the API of UninitRc<T>, where the other half is UninitRc<T>::downgrade. UninitRc<T>::downgrade has type fn(&UninitRc<T>) -> Weak<T> and is only sound because the UninitRc<T> has to be initialized before its weak reference can be upgraded. This is why implementing fn(&UniqueRc<MaybeUninit<T>>) -> Weak<T> would be unsound.

Here is what I think is a sound implementation of UninitRc<T> on top of UniqueRc<MaybeUninit<T>>. It uses unsafe twice and inner is private to make the public API sound. UniqueRc<MaybeUninit<T>>::write would remove one of the two unsafe blocks.

pub struct UninitRc<T> {
    inner: UniqueRc<MaybeUninit<T>>,
}

impl<T> UninitRc<T> {
    pub fn new() -> Self {
        UninitRc {
            inner: UniqueRc::new(MaybeUninit::uninit()),
        }
    }

    pub fn downgrade(&self) -> Weak<T> {
        let weak = UniqueRc::downgrade(&self.inner);
        // SAFETY: the weak reference can only be upgraded after initialization
        unsafe { transmute(weak) }
    }

    pub fn init(mut self, val: T) -> Rc<T> {
        self.inner.write(val);
        let rc = UniqueRc::into_rc(self.inner);
        // SAFETY: the rc has been initialized
        unsafe { transmute(rc) }
    }
}

[197g]

Quite sorry for the situation here and just repeating wasn't the intention but that tracking issue isn't tracking all it should. That comment is somewhere in the unexpanded items by default and the open questions list no indication of UninitRc at all. Would you mind updating it to appropriately?

[Kainaik1]

Filed a PR under the unique_rc_arc feature flag: Implement RcUninit (#112566) by kstrafe · Pull Request #140640 · rust-lang/rust · GitHub

Here's a crate I published implementing RcUninit: https://crates.io/crates/rcuninit