如何使用 Arc 和 Weak 创建循环引用？

Question

我有两个结构：

struct A { 
    map: HashMap<u32, Vec<B>>,
}

struct B {
    weak: Weak<A>
}

构造A时，会拥有多个B，每个B都链接回刚刚构造的A，类似这样：

let a = Arc::new(A { map: HashMap::new() });

let b1 = B { weak: Arc::downgrade(&a) };
let b3 = B { weak: Arc::downgrade(&a) };
let b2 = B { weak: Arc::downgrade(&a) };

a.map.insert(5, vec![b1, b2]);
a.map.insert(10, vec![b3]);

Playground

这不起作用，因为 Arc 不提供修改地图的方法。 Arc::get_mut 不起作用，因为 Weak 已经构造为该值。

如何用一些 B 构建一个 A？我试图在访问 map 时避免运行时检查，因为在构建之后它永远不会被再次修改。我可以使用不安全代码或批准的夜间功能。

Answer 1

Arc::get_mut() 如果你甚至有现有的 Weak 引用也会失败，所以你需要考虑使用 interior mutability 来代替。由于您使用的是 Arc，我假设您处于多线程环境中，因此我将使用线程安全的 RwLock。

use std::sync::{Arc, Weak, RwLock};
use std::collections::HashMap;

struct A { 
    map: RwLock<HashMap<u32, Vec<B>>>,
}

struct B {
    weak: Weak<A>
}

现在您可以像这样构建这些对象：

fn init_a(a: Arc<A>) -> Arc<A> {
    let b1 = B { weak: Arc::downgrade(&a) };
    let b2 = B { weak: Arc::downgrade(&a) };
    // extra block is required so that the Mutex's write lock is dropped 
    // before we return a
    {
        let mut map = a.map.write().unwrap();
        let vec = map.entry(0).or_insert(Vec::new());
        vec.push(b1);
        vec.push(b2);
    }
    a
}

fn main() {
    let mut a = Arc::new(A { map: RwLock::new(HashMap::new()) });
    a = init_a(a);
}

如果您真的想要摆脱 Mutex 的所有运行时开销，并且您不介意使用 unsafe 代码，您可以使用 UnsafeCell。它的开销为零，但它的接口需要一个 unsafe 块，并且它是代码中的一个额外的解包层。另外 UnsafeCell 不是 Sync，所以你不能在线程之间共享它。

要解决这些问题，通过确保在构造期间只需要考虑 UnsafeCell，您可以利用 UnsafeCell 具有零尺寸成本且不影响布局的事实.而不是 A，使用不同的类型来构造，除了 UnsafeCell 之外，它与 A 相同。这些类型可以与 mem::transmute.

互换使用

use std::collections::HashMap;
use std::sync::{Arc, Weak};
use std::cell::UnsafeCell;
use std::mem;

struct A { 
    map: HashMap<u32, Vec<B>>,
}

struct B {
    weak: Weak<A>
}

impl A {
    fn new() -> Arc<A> {
        let a = A { map: HashMap:: new() };
        Self::init_a(Arc::new(a))
    }

    fn init_a(a: Arc<A>) -> Arc<A> {
        // Important: The layout is identical to A
        struct AConstruct {
            map: UnsafeCell<HashMap<u32, Vec<B>>>,
        }
        // Treat the object as if was an AConstruct instead
        let a: Arc<AConstruct> = unsafe { mem::transmute(a) };
        let map = unsafe { &mut *a.map.get() };
        // B's weak references are to Arc<A> not to Arc<AConstruct> 
        let weak_a: Weak<A> = unsafe { mem::transmute(Arc::downgrade(&a)) };

        // Actual initialization here
        let vec = map.entry(0).or_insert(Vec::new());
        let b1 = B { weak: weak_a.clone() };
        let b2 = B { weak: weak_a.clone() };
        vec.push(b1);
        vec.push(b2);

        // We're done. Pretend the UnsafeCells never existed
        unsafe { mem::transmute(a) }
    }
}

你也可以用裸指针来做，但是我觉得"safer"用UnsafeCell有点！当 LLVM 保证某些数据是不可变的时，它会进行一些优化，而 UnsafeCell 在打破这些保证时会施展魔法来保护你。所以我不能 100% 确定这样做的安全性：

fn init_a(a: Arc<A>) -> Arc<A> {
    // Raw IMMUTABLE pointer to the HashMap 
    let ptr = &a.map as *const HashMap<_, _>;
    // Unsafely coerce it to MUTABLE
    let map: &mut HashMap<_, _> = unsafe { mem::transmute(ptr) };
    let weak_a: Weak<A> = Arc::downgrade(&a);

    // Actual initialization here
    let vec = map.entry(0).or_insert(Vec::new());
    let b1 = B { weak: weak_a.clone() };
    let b2 = B { weak: weak_a.clone() };
    vec.push(b1);
    vec.push(b2);

    a
}

Answer 2

实际上，我会从相反的方向来处理这个问题。

HashMap 比 Weak<T: Sized> 复杂得多，因此事后交换 Weak 更容易。因此，我的做法是：

使用虚拟引用创建 B。
创建 A，转让 B 的所有权。
迭代 B，将 A 换成真实的。

AFAIK，标准库不提供任何方法来 (1) 创建 null Weak 和 (2) 原子地交换它们。 Crossbeam 有一个 ArcCell 的例子：简单地 search/replacing all Arc by Weak 给我们一个 WeakCell!

有了 WeakCell<T> 供我们使用：

#[derive(Default)]
struct A { 
    map: HashMap<u32, Vec<B>>,
}

struct B {
    weak: WeakCell<A>,
}

impl A {
    pub fn new(map: HashMap<u32, Vec<B>>) -> Arc<A> {
        let a = Arc::new(A { map });
        let weak = Arc::downgrade(&a);
        for (_, bs) in &a.map {
            for b in bs {
                b.weak.set(weak.clone());
            }
        }
        a
    }
}

impl B {
    pub fn new(a: &Arc<A>) -> B { B { weak: WeakCell::new(Arc::downgrade(a)), } }
}

fn main() {
    let dummy = Arc::new(A::default());

    let (b1, b2, b3) = (B::new(&dummy), B::new(&dummy), B::new(&dummy));

    let mut map = HashMap::new();
    map.insert(5, vec![b1, b2]);
    map.insert(10, vec![b3]);

    let _a = A::new(map);

    //  Do something!
}

您可以在实际操作中看到 on the playground。

应该可以修改 WeakCell 以从 0 构造它（保证它稍后会被初始化），从而避免对虚拟引用的需要。这是留给 reader ;)

的练习

如何使用 Arc 和 Weak 创建循环引用？

How to create a cyclic reference with Arc and Weak?

reference

smart-pointers

rust