Reference loop problem

I got two structs:

struct Foo {
    bar: Arc<Bar>,
}

struct Bar {
    foos: Vec<Foo>,
}

I don't know if it is a bad design, the reference loop make it an "egg or chicken" problem:
If I want to create an Arc<Bar>, I need to create Foo's first, but if when create Foo's, I need an Arc<Bar>.

Here's my solution:


impl Bar {
    pub fn new() -> Arc<Bar> {
        // create a Bar with an empty vector
        let arc_bar = Arc::new(Bar {
            foos: Vec::new()
        });
        // so createion of `Foo`s will works fine
        let mut vec = Vec::with_capacity(10);
        for i in 0..10 {
            vec.push(Foo {
                bar: arc_bar.clone(),
            });
        }
        // set the vector back to the `Arc<Foo>`
       // since the arc is not exposed yet, only currenty thread owns it, it's safe to modify it
        unsafe {
            let i: *mut Bar = std::mem::transmute(&*arc_bar as *const _);
            (*i).foos = vec;
        }
        arc_bar
    }
}

But I really really don't like it. Is there any better design, which do not use unsafe codes?

Generally speaking, breaking ownership loops is what Weak is for.

struct Foo {
    bar: Weak<Bar>,
}

impl Bar {
    pub fn new() -> Arc<Bar> {
        Arc::new_cyclic(|weak| {
            let foos = std::iter::repeat_with(|| Foo { bar: weak.clone() })
                .take(10)
                .collect();
            Bar { foos }
        })
    }
}

Unfortunately new_cyclic isn't stable in 1.59, but it is scheduled for stabilization in 1.60, so you can use it on nightly without a feature flag.

Full playground


As for your proposed solution, it is unsound because it converts a & to &mut. But the basic idea is sound, if you are careful to avoid aliasing problems. Here's a corrected version:

impl Bar {
    pub fn new() -> Arc<Bar> {
        let mut arc_bar = Arc::new(Bar { foos: Vec::new() });
        let vec = std::iter::repeat_with(|| Foo {
            bar: arc_bar.clone(),
        })
        .take(10)
        .collect();

        // SAFETY: none of the other Arcs are dereferenced while i is in scope
        unsafe {
            let i: &mut Bar = Arc::get_mut_unchecked(&mut arc_bar);
            i.foos = vec;
        }
        arc_bar
    }
}

Again, though, get_mut_unchecked is only on nightly (and this time only with a feature flag). Rewriting it without that feature requires a bit more unsafe but ought to still work if done carefully.

Note that "only current thread owns it" is not sufficient proof of soundness; you have to actually guarantee no live references to the Bar exist. "Aliasing XOR mutation" is a guarantee that must be upheld in all code, not just multi-threaded stuff.

5 Likes

you could use Default derive maybe:

use std::sync::Arc;

#[derive(Default, Debug)]
struct Foo {
    bar: Arc<Bar>,
}

#[derive(Default, Debug)]
struct Bar {
    foos: Vec<Foo>,
}

I used this pattern in a similar situation. You must call self.foos.clear() before dropping the free Arc<Bar> if you don't want to leak it.

In addition, you may need an Mutex encapsulating the Foo::bar if you would like to modify it.

2 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.