在安全的 Rust 中,是否可以实现单线程零成本记忆而不具有可变性?

Bre*_*rby 5 rust

我有兴趣寻找或实现一个 Rust 数据结构,它提供了一种零成本的方式来记忆具有任意输出类型的单个计算T。具体来说,我想要一个通用类型Cache<T>,其内部数据占用的空间不超过Option<T>,并具有以下基本 API:

impl<T> Cache<T> {
    /// Return a new Cache with no value stored in it yet.
    pub fn new() -> Self {
        // ...
    }

    /// If the cache has a value stored in it, return a reference to the 
    /// stored value. Otherwise, compute `f()`, store its output
    /// in the cache, and then return a reference to the stored value.
    pub fn call<F: FnOnce() -> T>(&self, f: F) -> &T {
        // ...
    }
}
Run Code Online (Sandbox Code Playgroud)

这里的目标是能够Cache在单个线程内共享对 a 的多个不可变引用,并且此类引用的任何持有者都能够访问该值(如果是第一次,则触发计算)。由于我们只要求能够Cache在单个线程中共享 a,因此没有必要这样做Sync

unsafe这是一种在幕后安全地实现 API 的方法(或者至少我认为它是安全的) :

use std::cell::UnsafeCell;

pub struct Cache<T> {
    value: UnsafeCell<Option<T>>
}

impl<T> Cache<T> {
    pub fn new() -> Self {
        Cache { value: UnsafeCell::new(None) }
    }

    pub fn call<F: FnOnce() -> T>(&self, f: F) -> &T {
        let ptr = self.value.get();
        unsafe {
            if (*ptr).is_none() {
                let t = f();
                // Since `f` potentially could have invoked `call` on this
                // same cache, to be safe we must check again that *ptr
                // is still None, before setting the value.
                if (*ptr).is_none() {
                    *ptr = Some(t);
                }
            }
            (*ptr).as_ref().unwrap()
        }
    }
}
Run Code Online (Sandbox Code Playgroud)

是否有可能在安全的 Rust 中实现这样的类型(即不编写我们自己的unsafe代码,仅间接依赖unsafe标准库中的代码)?

显然,该call方法需要 mutating self,这意味着Cache必须使用某种形式的内部可变性。但是,似乎不可能使用 a 来执行此操作Cell,因为Cell无法按照上述所需 API 的要求检索对所包含值的引用call。这是有充分理由的,因为提供这样的引用是不合理的Cell,因为它无法确保引用的值在引用的生命周期内不会发生变化。另一方面,对于该Cache类型,在call调用一次之后,上面的 API 不提供任何方法让存储的值再次发生变化,因此它可以安全地分发一个生命周期很长的引用。就像它Cache本身一样。

如果Cell不能工作,我很好奇 Rust 标准库是否可以为内部可变性提供一些其他安全的构建块,可以用来实现这个Cache

既不RefCell实现Mutex这里的目标:

  1. 它们不是零成本的:它们涉及存储比 an 多的数据Option<T>,并添加不必要的运行时检查。
  2. 它们似乎没有提供任何方法来返回具有我们想要的生命周期的真实引用 - 相反,我们只能返回 aRef或 ,MutexGuard这不是同一件事。

仅使用 anOption不会提供相同的功能:如果我们共享对 的不可变引用Cache,则此类引用的任何持有者都可以调用call并获取所需的值(并在此过程中改变Cache,以便将来的调用将检索相同的值);然而,共享对 an 的不可变引用Option,则不可能改变Option,因此它无法工作。