如何编写既可以读取也可以写入缓存的 Rust 函数？

Question

原始问题陈述

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

我通读了 https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html , https://naftuli.wtf/2019/03/20/rust-the-hard-parts/ 和随机堆栈 overflow/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`.

我不明白为什么它认为我在第 26 行不可变地借用了 cache。我的理解是 main 创建了 CacheForMove 的实例并拥有该值。它将值可变地借给 stairs 函数，所以现在 stairs 已经可变地借用了该值。我希望能够在那个可变借用的引用上调用 get_for_n 和 insert_for_n。

我还不明白的答案

这是的副本吗？

在这个 SO 问题中，OP 希望根据缓存中另一个键的值对缓存中的一个键进行更新。我最终确实想这样做，但在我到达那一点之前我运行遇到了一个问题。我没有查看缓存中的其他条目来计算 "this" 条目。该问题的答案说，他们需要像这样从缓存中获取数据和插入缓存数据中分离出来：

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`.

这是的副本吗？

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

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

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

你是不可变的借用它 - 运行 get_for_n 方法，当 returned 值超出范围时（即，在比赛结束）。您不希望 stairs 函数对缓存所做的任何操作使匹配值无效。

无论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 来从中获取缓存值。如果有可用值，我 return 它（无需再次递归调用 stairs ）。如果没有价值，我希望 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。如果是，我打开内部值并 return 它。如果不是，我将结束我的范围，因此所有借用都超出了范围并且现在是无效的。没有借用发生了。

然后，我尝试可变地借用 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

Answer 2

我想我已经弄明白了，所以记录我的回答以防其他人遇到同样的问题。编译并运行：

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.clone(),
        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);
    }
}

有两个主要变化：

stairs 不再是 returns &Vec<Vec<usize>> 而是 returns Vec<Vec<usize>>
在Some(result)的情况下，我们returnresult.clone()而不是result。

2 是 1 的结果，所以让我们关注为什么 1 是必要的以及为什么它可以解决问题。 HashMap 拥有 Vec<Vec<usize>>，因此当原始实现 return 编辑 &Vec<Vec<usize>> 时，它是 return 对由 Vec<Vec<usize>> 拥有的内存位置的引用HashMap。如果有人要改变 HashMap，比如删除一个条目，因为 HashMap 拥有 Vec<Vec<usize>>，HashMap 会得出结论，释放正在使用的内存是安全的通过 Vec<Vec<usize>>，我最终会得到一个悬空的引用。

我只能 return 一个 &Vec<Vec<usize>> 只要我能保证只要 &Vec<Vec<usize>> 引用存在就没有人会改变 HashMap，并且因为我正在 returning 对我的调用者的 &Vec<Vec<usize>> 引用，这实质上意味着我需要保证 HashMap 永远不可变（因为我不知道调用者可能会做什么）。

Answer 3

将其包装在 Rc 中是一种可能的解决方案。

Rc 是一个 "reference counted" 指针，使您能够将多个 "borrows" 指向相同的值。当您调用 "clone" 方法时，计数会增加。当值被销毁时，计数将减少。最后，如果引用计数达到 0，指针及其 "pointed" 值将被销毁。你可能想在并发环境中使用 Arc （它基本上是一个原子引用计数“指针）或者如果你正在制作一个板条箱，因为它提供了更大的灵活性。Arc 将做与 Rc 相同的工作，除了该计数将自动完成。

这样，您的所有权问题将得到解决，无需复制整个 Vec，而只需将另一个指针指向相同的 "value"。

我也用 Option::unwrap_or_else 代替，这是一种更惯用的解包 Option::Some(T) 的方法，或者在 Option::None 的情况下延迟计算默认值.

use std::collections::HashMap;
use std::rc::Rc;

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,
            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: &Rc<CacheForMoves>, n: usize) -> &Vec<Vec<usize>> {
    cache.get_for_n(n).unwrap_or_else(|| stairs(cache, n - 1))
}

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

如何编写既可以读取也可以写入缓存的 Rust 函数？

How do I write a rust function that can both read and write to a cache?

rust

borrow-checker

borrowing

原始问题陈述

我还不明白的答案

这是的副本吗？

这是的副本吗？

你是不可变的借用它 - 运行 get_for_n 方法，当 returned 值超出范围时（即，在比赛结束）。您不希望 stairs 函数对缓存所做的任何操作使匹配值无效。

如何编写既可以读取也可以写入缓存的 Rust 函数？

How do I write a rust function that can both read and write to a cache?

rust

borrow-checker

borrowing

原始问题陈述

我还不明白的答案

这是 的副本吗？

这是 的副本吗？

你是不可变的借用它 - 运行 get_for_n 方法，当 returned 值超出范围时（即，在比赛结束）。您不希望 stairs 函数对缓存所做的任何操作使匹配值无效。

这是的副本吗？

这是的副本吗？