rust - 如何编写一个可以读写缓存的 rust 函数？

Question

原始问题陈述

我正在尝试编写一个可以从缓存中读取和写入的函数，但是我遇到了一个问题，编译器说我不能可变地和不可变地借用缓存。

我已通读 https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html , https://naftuli.wtf/2019/03/20/rust-the-hard-parts/和随机堆栈溢出/Reddit 帖子，但我不知道如何将他们所说的应用于此代码。

use std::collections::HashMap;

struct CacheForMoves {
    set_of_moves: Vec<usize>,
    cache: HashMap<usize, Vec<Vec<usize>>>,
}

impl CacheForMoves {
    fn new(set_of_moves: Vec<usize>) -> CacheForMoves {
        CacheForMoves {
            set_of_moves: set_of_moves,
            cache: HashMap::new(),
        }
    }

    fn get_for_n(&self, n: usize) -> Option<&Vec<Vec<usize>>> {
        self.cache.get(&n)
    }

    fn insert_for_n(&mut self, n: usize, value: Vec<Vec<usize>>) {
        self.cache.insert(n, value);
    }
}

fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
    return match cache.get_for_n(n) {
        Some(result) => result,
        None => stairs(cache, n - 1),
    };
}

fn main() {
    let mut cache = CacheForMoves::new(vec![1, 2]);
    cache.insert_for_n(1, vec![]);
    let result = stairs(&mut cache, 4);
    println!("Found {} possible solutions: ", result.len());
    for solution in result {
        println!("{:?}", solution);
    }
}

这会产生以下编译错误:

error[E0502]: cannot borrow `*cache` as mutable because it is also borrowed as immutable
  --> stairs2.rs:28:18
   |
26 |     return match cache.get_for_n(n) {
   |                  ----- immutable borrow occurs here
27 |         Some(result) => result,
28 |         None => stairs(cache, n - 1)
   |                        ^^^^^ mutable borrow occurs here
29 |     }
30 | }
   | - immutable borrow ends here

error: aborting due to previous error

For more information about this error, try `rustc --explain E0502`.

我不明白为什么它认为我一直在借钱 cache 26行。我的理解是 main创建 CacheForMove 的实例并拥有该值(value)。它可变地将值(value)借给 stairs函数，等等 stairs可变地借用了值(value)。我希望能够同时调用 get_for_n和 insert_for_n在那个可变借用的引用资料上。

还没看懂的回答

这是 How can I mutate other elements of a HashMap when using the entry pattern? 的副本吗？ ?

在这个 SO 问题中，OP 希望对缓存中的一个键进行更新，这取决于缓存中不同键的值。我最终确实想这样做，但在达到这一点之前我遇到了问题。我不是为了计算“这个”条目而查看缓存中的其他条目。该问题的答案说他们需要将从缓存中获取与插入缓存分开，如下所示:

fn compute(cache: &mut HashMap<u32, u32>, input: u32) -> u32 {
    if let Some(entry) = cache.get(&input) {
        return *entry;
    }

    let res = if input > 2 {
        // Trivial placeholder for an expensive computation.
        compute(cache, input - 1) + compute(cache, input - 2)
    } else {
        0
    };
    cache.insert(input, res);
    res
}

但是，我相信我的代码已经从插入中分离出来，但我仍然收到编译错误。

即使我调整了上面的例子来匹配我的 API:

fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
    if let Some(entry) = cache.get_for_n(n) {
        return entry;
    }
    let res = stairs(cache, n - 1);
    cache.insert_for_n(n, res.clone());
    res
}

我仍然收到相同的错误:

error[E0502]: cannot borrow `*cache` as mutable because it is also borrowed as immutable
  --> src/main.rs:29:15
   |
25 | fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
   |                  - let's call the lifetime of this reference `'1`
26 |     if let Some(entry) = cache.get_for_n(n) {
   |                          ----- immutable borrow occurs here
27 |         return entry;
   |                ----- returning this value requires that `*cache` is borrowed for `'1`
28 |     }
29 |     let res = stairs(cache, n - 1);
   |               ^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

error[E0499]: cannot borrow `*cache` as mutable more than once at a time
  --> src/main.rs:30:5
   |
25 | fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
   |                  - let's call the lifetime of this reference `'1`
...
29 |     let res = stairs(cache, n - 1);
   |                      ----- first mutable borrow occurs here
30 |     cache.insert_for_n(n, res.clone());
   |     ^^^^^ second mutable borrow occurs here
31 |     res
   |     --- returning this value requires that `*cache` is borrowed for `'1`

error: aborting due to 2 previous errors

Some errors occurred: E0499, E0502.
For more information about an error, try `rustc --explain E0499`.

这是 What is the idiomatic way to implement caching on a function that is not a struct method? 的副本吗？ ?

在那个 SO 问题中，OP 表示他们不愿意使用 struct ，并且提供的答案使用了 unsafe 的某种组合, mutex , lazy_static! , RefCell ， 等等。

我有相反的问题。我非常愿意使用 struct (事实上​​，我在我原来的问题陈述中使用了一个)，但使用了 unsafe , mutex , lazy_static! ，等等对我来说听起来更危险或更复杂。

该问题的 OP 暗示如果我们可以使用结构，那么解决方案将是显而易见的。我想学习那个显而易见的解决方案。

你是不可变的借用它 - 运行 get_for_n 方法，该方法从 self 借用并释放这个借用，当返回值超出范围时(即在匹配结束时)。您不希望楼梯函数对缓存所做的任何事情使匹配的值无效。
stairs 不使用匹配的值功能确实。在原始问题陈述中显示的实现中:

fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
    return match cache.get_for_n(n) {
        Some(result) => result,
        None => stairs(cache, n - 1),
    };
}

我一成不变地借用 cache从中获取缓存值。如果有可用值，我将其返回(不再递归调用 stairs)。如果没有值(value)，我期望 None可复制(即我可以在堆栈中拥有自己的 None 副本；我不再需要引用 cache 中的任何数据)。在这一点上，我希望能够安全地可变借用 cache调用 stairs(cache, n-1) ，因为没有其他借用(可变或不可变)要缓存。

为了真正插入这一点，请考虑楼梯功能的这种替代实现:

fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
    {
        let maybe_result = cache.get_for_n(n);
        if maybe_result.is_some() {
            return maybe_result.unwrap();
        }
    }
    return stairs(cache, n - 1);
}

在这里，我使用了一对花括号来限制不可变借用的范围。我执行一个不可变的借用来填充 maybe_result ，并检查它是否是 Some .如果是，我打开内部值并返回它。如果没有，我将结束我的范围，因此所有借用都已超出范围，现在无效。不再有借贷发生。

然后，我尝试可变地借用 cache递归调用 stairs .这应该是此时唯一发生的借用，所以我希望这个借用成功，但编译器告诉我:

error[E0502]: cannot borrow `*cache` as mutable because it is also borrowed as immutable
  --> src/main.rs:32:12
   |
25 | fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
   |                  - let's call the lifetime of this reference `'1`
26 |     {
27 |         let maybe_result = cache.get_for_n(n);
   |                            ----- immutable borrow occurs here
28 |         if maybe_result.is_some() {
29 |             return maybe_result.unwrap();
   |                    --------------------- returning this value requires that `*cache` is borrowed for `'1`
...
32 |     return stairs(cache, n - 1);
   |            ^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

error: aborting due to previous error

For more information about this error, try `rustc --explain E0502`.

Answer 1

检查 None在不可变借用工作之前显式并返回:

fn stairs(cache: &mut CacheForMoves, n: usize) -> &Vec<Vec<usize>> {
    if cache.get_for_n(n).is_none() {
        return stairs(cache, n - 1);
    } else {
        cache.get_for_n(n).unwrap()
    }
}

但是我不想调用 get_for_n()功能两次

Rust playground link