Cyclic Arc and Rc Builder

[eholk]

Proposal

Problem statement

It can be helpful to build cyclic ARC structures. Currently there is Arc::new_cyclic, but this does not work if the supplied data_fn returns a Result or is an async fn.

Motivation, use-cases

Consider the following example that creates a cyclic Arc structure using Arc::new_cyclic:

use std::sync::{Arc, Weak};

struct Gadget {
    me: Weak<Gadget>,
}

impl Gadget {
    fn new(me: Weak<Gadget>) -> Self {
        Gadget { me }
    }
}

fn create_gadget() -> Arc<Gadget> {
    Arc::new_cyclic(|gadget| Gadget::new(gadget.clone()))
}

We may want to make Gadget::new be an async function that returns a Result indicating it might fail. We might be tempted to replace the Arc::new_cyclic(|gadget| Gadget::new(gadget.clone())) with Arc::new_cyclic(|gadget| async { Gadget::new(gadget.clone()).await? }), but doing so gives the following errors:

error[E0277]: the trait bound `Gadget: FromResidual<Result<Infallible, std::io::Error>>` is not satisfied
  --> src/lib.rs:15:36
   |
15 |     Arc::new_cyclic(|gadget| async { Gadget::new(gadget.clone()).await? })
   |                                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |                                    |
   |                                    the trait `FromResidual<Result<Infallible, std::io::Error>>` is not implemented for `Gadget`
   |                                    required by a bound introduced by this call

error[E0308]: mismatched types
  --> src/lib.rs:15:30
   |
15 |     Arc::new_cyclic(|gadget| async { Gadget::new(gadget.clone()).await? })
   |                              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `Gadget`, found opaque type
   |
   = note:   expected struct `Gadget`
           found opaque type `impl Future<Output = Gadget>`

Some errors have detailed explanations: E0277, E0308.
For more information about an error, try `rustc --explain E0277`.
error: could not compile `playground` due to 2 previous errors

There is currently no obvious way to make this work using Rust, and many if not all of the non-obvious ways involve unsafely depending on Arc implementation details.

Solution sketches

We propose adding a new CyclicArcBuilder and corresponding CyclicRcBuilder with roughly the following API:

pub struct CyclicArcBuilder<T> { /* details omitted */ }

impl<T> CyclicArcBuilder<T> {
    pub fn new() -> Self { /* details omitted */ }
    
    /// Obtain a `Weak<T>` to the allocation. Attempting to
    // `upgrade` the weak reference prior to invoking `build`
    // will fail and result in a `None` value.
    pub fn weak(&self) -> Weak<T> { /* details omitted */ }
    
    // Finish construction of the `Arc<T>`.
    pub fn build(self, data: T) -> Arc<T> { /* details omitted */ }
}

As an alternative (or in addition) to CyclicArcBuilder::new, we could also add a new_cyclic_builder() method to Arc.

Using this API would allow us to solve the problem in the previous section as follows:

use std::io;
use std::sync::{Arc, Weak};

struct Gadget {
    me: Weak<Gadget>,
}

impl Gadget {
    async fn new(me: Weak<Gadget>) -> io::Result<Self> {
        Ok(Gadget { me })
    }
}

async fn create_gadget() -> io::Result<Arc<Gadget>> {
    let builder = Arc::new_cyclic_builder();
    let gadget = Gadget::new(builder.weak()).await?;
    Ok(builder.build(gadget))
}

Alternative: More cyclic Constructors

An alternative we considered was adding a collection of new_cyclic variants, like try_new_cyclic, async_new_cyclic, and async_try_new_cyclic. This approach adds a lot of API surface while CyclicArcBuilder subsumes all of these use cases and more (for example, the original arc_new_cyclic issue mentioned multiple arity variants).

Alternative: Keyword Generics

The Keyword Generics Initiative would make it possible to use the existing Arc::new_cyclic constructor in fallible and async contexts by sharing a single implementation. The initiative is still in the early stages though, while adding CyclicArcBuilder would allow making incremental progress sooner. CyclicArcBuilder is also strictly more general, since it can enable the multi-arity use case mentioned above while keyword generics would not.

One advantage of both of these alternatives is that they are likely to present a simpler API. CyclicArcBuilder is quite general, but arguably not as ergonomic. However, the kind of code that requires something like new_cyclic would likely already in a situation that would benefit from an even more flexible API.

Alternative: Multi-phase Construction

One option is to split the construction of the object into a fallible and infallible portion, like this example take from this comment:

let mut obj = try_obj()?;
let rc = Rc::new_cyclic(move |this| {
    obj.this = Weak::clone(this);
    obj
});

This approach does work, but there are some downsides. It requires constructing the object in an invalid state and then patching it up afterwards, which is likely more error-prone than being able to make the object correct-by-construction using the builder API.

One issue this this approach is that it can either expose implementation details that should be private, or require factoring the code differently. Suppose we wanted to have a ServiceManager that managed multiple objects that implement the Service trait. Using CyclicArcBuilder, we might write something like this:

struct ServiceManager {
    foo_service: Arc<dyn Service>,
    bar_service: Arc<dyn Service>,
}

impl ServiceManager {
    fn new() -> Arc<Self> {
        let this = Arc::builder();
        this.build(Self {
            foo_service: FooService::create(this.weak()),
            bar_service: BarService::create(this.weak()),
        })
    }
    
    fn get_foo_service(&self) -> Arc<dyn Service> { ... },
    fn get_bar_service(&self) -> Arc<dyn Service> { ... },
}

Without CyclicArcBuilder, ServiceManager::new would either need access to the service internals, or we'd need to add a method to the Service trait to finalize construction. The first option would look like this:

impl ServiceManager {
    fn new() -> Arc<Self> {
        let mut obj = Self {
            foo_service: FooService::create(),
            bar_service: BarService::create(),
        };
        Arc::new_cyclic(move |this| {
            obj.foo_service.service_manager = this.clone();
            obj.bar_service.service_manager = this.clone();
            obj
        })
    }
}

We can work around needing direct access to the service_manager field by using something like an activate method:

impl ServiceManager {
    fn new() -> Arc<Self> {
        let mut obj = Self {
            foo_service: FooService::create(),
            bar_service: BarService::create(),
        };
        Arc::new_cyclic(move |this| {
            obj.foo_service.activate(this.clone());
            obj.bar_service.activate(this.clone());
            obj
        })
    }
}

This avoids leaking internal details of the service implementation, but it still less than ideal. One, it requires complicating the Service trait with an activate method. More significantly though, this approach is a maintenance hazard. If in the future we added baz_service to ServiceManager, the compiler would guarantee that we call BazService::create() but it would be easy to forget to call obj.baz_service.activate(this.clone()). On the other hand, the builder pattern makes this mistake impossible.

Links and related work

This proposal builds upon and generalizes some of the alternatives discussed in Tracking Issue for arc_new_cyclic (#75861). Some specific comments have been linked above, but the whole thread is relevant.

What happens now?

This issue is part of the libs-api team API change proposal process. Once this issue is filed the libs-api team will review open proposals in its weekly meeting. You should receive feedback within a week or two.

[programmerjake]

example of why CyclicArcBuilder would be useful but wouldn't easily work with other alternatives:

struct Node<N, E> {
    edges: Box<[Arc<Edge<N, E>>]>,
    data: N,
}

struct Edge<N, E> {
    nodes: [Weak<Node<N, E>>; 2],
    data: E,
}

struct Graph<N, E> {
    nodes: Box<[Arc<Node<N, E>>]>,
}

impl<N, E> Graph<N, E> {
    fn new(
        nodes: impl IntoIterator<Item = N>,
        edges: impl IntoIterator<Item = (usize, usize, E)>,
    ) -> Self {
        struct NodeBuilder<N, E> {
            node: CyclicArcBuilder<Node<N, E>>,
            data: N,
            edges: Vec<Arc<Edge<N, E>>>,
        }
        let builders: Vec<_> = nodes
            .map(|data| NodeBuilder {
                node: CyclicArcBuilder::new(),
                data,
                edges: Vec::new(),
            })
            .collect();

        for (n1, n2, data) in edges {
            let edge = Arc::new(Edge {
                nodes: [builders[n1].node.weak(), builders[n2].node.weak()],
                data,
            });
            builders[n1].edges.push(edge.clone());
            builders[n2].edges.push(edge.clone());
        }

        Graph {
            nodes: builders
                .map(|b| {
                    b.node.build(Node {
                        edges: b.edges.into(),
                        data: b.data,
                    })
                })
                .collect(),
        }
    }
}

[wada314]

I really want this feature in my project so I'm super interested into this!

BTW, I found there is an another alternative safe solution which is possible under limited conditions.
I'm using this solution for my project currently:

• T is Default and it's implementation is acceptably simple (so that you can accept an extra ::default() call)
• T: Sized

let mut maybe_error = None;
let rc = Rc::new_cyclic(|weak| {
  match T::try_obj(weak) {
    Ok(obj) => obj,
    Err(e) => {
      maybe_error = Some(e);
      T::default()
    }
  }
});
match maybe_error {
  Some(e): Err(e),
  None: Ok(rc),
}

[ZhennanWu]

Would really like to see the support for async. Since this specific pattern is not bounded to sync or async context. The current lack of cyclic builder for async context actually creates a feature disparity.

Recently I tried to refactor some of my code from using threadpool into async executors. And there is simply no replacement for Arc::new_cyclic. In the end I have to introduce an additional uninitialized state into the shared states to somehow create the Arc first, but the impact of this refactor is widespread with panic! everywhere in the code.

[ChayimFriedman2]

@ZhennanWu Just like with fallible variant, why can't you await the async stuff before the initialization closure and keep it only for assigning the fields?

[ZhennanWu]

Just like with fallible variant, why can't you await the async stuff before the initialization closure and keep it only for assigning the fields?

There are authentic cyclic reference scenarios that a late assignment is too difficult to implement. Like registering a callback on another notification source. A late assignment would require tracking all touched sources.

On top of that, since it is about parallel async runtime, compromising thread safety is a no go. A "late assignment" is just semantically different to the "interior mutability" semantics provided by Arc::new_cyclic. It breaks atomicity and synchronization guarantees. Apart from that, there is also dead lock concerns caused by the additional assignment.

[m-ou-se]

Thanks for your ACP. We discussed this in the libs meetup. Instead of calling this a 'builder' with a 'build' method, we'd much rather see something like a UniqueArc that represents an uniquely owned Arc. Weak pointers to an UniqueArc can exist, but cannot be upgraded. It's basically the same thing this ACP proposes, but with different naming, generalizing it to make it a bit more useful.

Feel free to open a new ACP for that if you want feedback on the API, or open a PR to rust-lang/rust directly if you feel like implementing it.

[programmerjake]

i'd expect to also have a UniqueRc type that behaves analogously to UniqueArc

[eholk]

Thank you for the feedback. I will put together a PR to implement this and we can do any needed API iteration on the PR. I'll make sure to include both UniqueArc and UniqueRc.

[eholk]

I just posted a PR implementing UniqueRc at rust-lang/rust#111849. I figured rather than do it all at once it makes sense to get feedback on UniqueRc first, since UniqueArc should be basically the same.

[RalfJung]

Comparing rust-lang/rust#112566 with the original proposal, there seems to be one downside: with UniqueRc, one has to first set up the Gadget in an invalid state, and then close the loop. Doesn't that share the downsides of what was described in the "Multi-phase Construction" proposal in this issue?

[steffahn]

With MaybeUninit it should at least be trivial for a third-party crate to implement the CyclicArcBuilder<T> using a UniqueArc<MaybeUninit<T>>, right? (In particular the resulting Weak<MaybeUninit<T>> and eventual Arc<MaybeUninit<T>> can be converted into Weak<T> and Rc<T> through into_raw+from_raw.)

[ShayDamir]

There could be a different way to simplify creating of cyclic Arcs - first you create a Weak reference with zero strong count, which is clone-able, but upgrading it will give None. The proposal is to call it Weak::uninit.

Then this weak reference is upgraded to full-fledged Arc by providing a initializing value that would be moved inside.

Something like this (API intentionally resembles of MaybeUninit API):

let mut weak: Weak<Gadget> = Weak::uninit();

let gadget = Gadget::new(weak.clone()).await?;

weak.write(gadget);

let strong: Arc<Gadget> = weak.assume_init().unwrap();

Ok(strong);

Weak::assume_init() could check that strong count is 0 and atomically increase it to 1.

The downside of such approach is that there would be a store-store race condition if multiple threads would try to call Weak::write() on the same weak reference.

This could be avoided by following the OnceLock API instead of MaybeUninit API, something like:

let weak: Weak<Gadget> = Weak::new();

let gadget = Gadget::new(weak.clone()).await?;

let strong: Arc<Gadget> = weak.upgrade_or_init(|| gadget);

Ok(strong);

But since Weak::new currently doesn't allocate, and just contain a dangling pointer, this wouldn't work. Maybe create a new constructor for Weak that actually does allocate? Something like Weak::new_alloc

[ShayDamir]

I ended up with an API which looks like this:

let uninit = ArcUninit::uninit();
let weak = uninit.downgrade();

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

// if ArcUninit is dropped before initializing (for example, in case of fallible constructor), 
// the storage will be deallocated after weak is dropped
// this also, of course, works across await boundaries, since ArcUninit is Send + Sync.

let arc = uninit.init(Gadget{ me: weak.clone() });

let arc_from_weak = weak.upgrade().unwrap();
assert!(Arc::ptr_eq(&arc, &arc_from_weak);

This API works well with async and fallible constructors, and also allows things like creating multiple Arcs simultaneously with weak cross-references like:

struct CrossLink {
    other: Weak<CrossLink>,
}

let link1 = ArcUninit::uninit();
let link2 = ArcUninit::uninit();

let weak1 = link1.downgrade();
let weak2 = link2.downgrade();

let arc1 = link1.init(Gadget{ other: weak2 });
let arc2 = link2.init(Gadget{ other: weak1 });

assert!(Arc::ptr_eq(&arc1, &arc2.other.upgrade().unwrap()));