如何编写可以同时读取和写入缓存的rust函数？ [英] How do I write a rust function that can both read and write to a cache?

问题描述

原始问题陈述

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

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

 使用std :: collections :: HashMap; 
 
结构CacheForMoves {
 set_of_moves：Vec< usize> ;, 
缓存：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）->选项& Vec< Vec< usize>> {
 self.cache.get（& n）
} 
 
 fn insert_for_n（& mut self，n：使用，值：Vec< Vec< usize>> ）{
 self.cache.insert（n，value）; 
} 
} 
 
 fn楼梯（缓存：& mut CacheForMoves，n：使用）-> & Vec< Vec< usize>> {
返回匹配cache.get_for_n（n）{
 Some（result）=>结果，
无=>楼梯（缓存，n-1），
}; 
} 
 
 fn main（）{
让mut cache = CacheForMoves :: new（vec！[1、2]）; 
 cache.insert_for_n（1，vec！[]）; 
 let result =楼梯（& mut缓存，4）; 
 println！（找到{}可能的解决方案：，result.len（））; 
作为结果中的解决方案{
 println！（ {:?}，解决方案）; 
} 
} 
  

这会产生以下编译错误：

 错误[E0502]：无法借用* cache作为可变变量，因为它也被借为不可变的
->楼梯2.rs:28:18 
 | 
 26 |返回匹配cache.get_for_n（n）{
 | -----这里发生不动产借贷
 27 | Some（result）=>结果，
 28 |无=>楼梯（快取，n-1）
 | 
 29 | ^^^^^发生可变借款} 
 30 | } 
 | -不可变的借贷在这里结束
 
错误：由于先前的错误而中止
 
有关此错误的更多信息，请尝试`rustc --explain E0502`。 
  

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

我尚不了解的答案

这是否是使用进入模式时，如何对HashMap的其他元素进行变异？？

在此SO问题中，OP希望对缓存中一个键的更新取决于缓存中另一个键的值。我最终确实想这样做，但是在达到这一点之前，我遇到了一个问题。我不会在缓存中查看其他条目以计算此条目。该问题的答案表明，他们需要像这样从缓存中拆分插入缓存：

  fn compute（cache：& mut HashMap< u32，u32> ;，输入：u32）-> u32 {
如果让Some（entry）= cache.get（& input）{
 return * entry; 
} 
 
 let res =如果输入> 2 {
 //琐碎的占位符，用于昂贵的计算。 
compute（缓存，输入-1）+ compute（缓存，输入-2）
} else {
 0 
}; 
 cache.insert（input，res）; 
 res 
} 
  

但是，我相信我的代码已经无法插入，但仍然出现编译错误。

即使我修改了上面的示例以匹配我的API：

< pre $ = lang-rust prettyprint-override> fn阶梯（缓存：& mut CacheForMoves，n：使用）-> & Vec< Vec< usize>> {
如果让Some（entry）= cache.get_for_n（n）{
返回条目；
}
let res =楼梯（cache，n-1）;
cache.insert_for_n（n，res.clone（））;
res
}


我仍然遇到相同的错误：

 错误[E0502]：无法借用* Cache作为可变变量，因为它也借作不可变的
-> src / main.rs：29：15 
 | 
 25 | fn楼梯（缓存：& mut CacheForMoves，n：使用）-> & Vec< Vec< usize>> {
 | -将此参考的有效期称为’1 
 26 |如果让Some（entry）= cache.get_for_n（n）{
 | -----这里发生不动产借贷
 27 |返回条目
 | -----返回此值需要将`* cache`借给`'1` 
 28 | } 
 29 |让res =楼梯（cache，n-1）; 
 | 
 
错误发生[E0499]：在同一时间不能多次借用* cache作为可变变量时间
-> src / main.rs：30：5 
 | 
 25 | fn楼梯（缓存：& mut CacheForMoves，n：使用）-> & Vec< Vec< usize>> {
 | -我们将此参考称为’1的生命周期
 ... 
 29 |让res =楼梯（cache，n-1）; 
 | -----第一笔可变借款发生在这里
 30 | cache.insert_for_n（n，res.clone（））; 
 | 
 31 | ^^^^^在这里发生第二次可变借用res 
 | ---返回此值需要为'1`借用`* cache` 
 
错误：由于先前的2个错误而中止
 
发生了一些错误：E0499，E0502 。 
有关错误的更多信息，请尝试`rustc --explain E0499`。 
  

这是否是在不是结构的函数上实现缓存的惯用方式是什么方法？？

在那个SO问题中，OP表示他们不愿意使用 struct ，并且提供的答案使用不安全，互斥量， lazy_static！， RefCell 等。

我遇到了相反的问题。我非常愿意使用 struct （实际上，我在原始问题陈述中使用了一个），但是使用了不安全， mutex ， lazy_static！等，对我来说似乎更危险或更复杂。

该问题的操作意味着如果我们可以使用结构，则解决方案将显而易见。我想学习一个明显的解决方案。

您无法改变地借用它-运行get_for_n方法，该方法从自身借用并在返回值退出时释放该借用范围（即比赛结束时）。您不希望楼梯函数对缓存执行任何操作都会使匹配的值无效。

stairs 函数。在原始问题陈述所示的实现中：

  fn楼梯（缓存：& mut CacheForMoves ，n：usize）-> & Vec< Vec< usize>> {
返回匹配cache.get_for_n（n）{
 Some（result）=>结果，
无=>楼梯（缓存，n-1），
}; 
} 
  

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

要真正把这一点讲清楚，请考虑阶梯函数的以下替代实现：

  fn楼梯（缓存：& mut CacheForMoves，n：使用）-> & Vec< Vec< usize>> {
 {
 let might_result = cache.get_for_n（n）; 
 if if may_result.is_some（）{
 returnmay_result.unwrap（）; 
} 
} 
返回楼梯（快取，n-1）； 
} 
  

在这里，我使用了一对花括号来限制一成不变的借款。我执行不可变借位以填充 maybe_result ，并检查它是否为 Some 。如果是这样，我将解开内部值并返回它。如果没有，我就结束我的范围，因此所有借用都超出范围，现在无效。

然后，我尝试可变地借用缓存递归调用楼梯。这应该是此时唯一发生的借用，因此我希望这种借用能够成功，但是编译器告诉我：

 错误[E0502]：无法借用* cache作为可变变量，因为它也借作不可变的
-> src / main.rs：32：12 
 | 
 25 | fn楼梯（缓存：& mut CacheForMoves，n：使用）-> & Vec< Vec< usize>> {
 | -将此参考的有效期称为’1 
 26 | {
 27 |让maybe_result = cache.get_for_n（n）; 
 | -----这里发生不动产借贷
 28 |如果maybe_result.is_some（）{
 29 |返回maybe_result.unwrap（）; 
 | ---------------------返回此值需要为* 1借用`* cache` 
 ... 
 32 |返回楼梯（缓存，n-1）; 
 | ^^^^^^^^^^^^^^^^^^^^^这里发生可变借位
 
错误：由于先前的错误而中止
 
有关更多信息关于此错误，请尝试使用 rustc --explain E0502。 
  

解决方案

我想我已经弄清楚了，所以记录我的答案，以防其他人陷入同一问题。编译并运行：

  use std :: collections :: HashMap; 
 
结构CacheForMoves {
 set_of_moves：Vec< usize> ;, 
缓存：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）->选项& Vec< Vec< usize>> {
 self.cache.get（&n）
} 
 
 fn insert_for_n（& mut self，n：使用，值：Vec< Vec< usize>> ）{
 self.cache.insert（n，value）; 
} 
} 
 
 fn楼梯（缓存：& mut CacheForMoves，n：使用）-> Vec< Vec" useize> {
返回匹配cache.get_for_n（n）{
 Some（result）=> result.clone（），
 None =>楼梯（cache，n-1）
} 
} 
 
 fn main（）{
 let mut cache = CacheForMoves :: new（vec！[1，2 ]）; 
 cache.insert_for_n（1，vec！[]）; 
 let result =楼梯（& mut缓存，4）; 
 println！（找到{}可能的解决方案：，result.len（））; 
作为结果中的解决方案{
 println！（ {:?}，解决方案）; 
} 
} 
  

有2个主要更改：

1. 楼梯不再返回&Vec< Vec< usize>> 并返回 Vec< Vec< usize>>


2. 在某些（结果）的情况下，我们返回 result.clone（）而不是 result 。

2是1的结果，所以让我们集中讨论为什么1是必要的以及为什么它可以解决问题。 HashMap 拥有 Vec< Vec< usize>> ，因此当原始实现返回& Vec< Vec< usize>> ，它返回对 HashMap 拥有的存储位置的引用。如果有人要更改 HashMap ，请删除一个条目，因为 HashMap 拥有 Vec< Vec< usize>> ， HashMap 会得出结论，可以安全地释放 Vec< Vec< usize>> ，最后我得到一个悬挂的引用。

我只能返回& Vec< Vec< usize>> ，只要我可以保证在以下情况下没有人会变异 HashMap & Vec< Vec< usize>> 引用存在，并且由于我返回了& Vec< Vec< Vec< usize> 引用我的调用者，这实际上意味着我需要保证 HashMap 永远是不可变的（因为我不知道调用者会做什么）

Original Problem Statement

I'm trying to write a function that can both read and write from a cache, but I'm running into a problem where the compiler says I can't both mutably and immutably borrow the cache.

I've read through https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html , https://naftuli.wtf/2019/03/20/rust-the-hard-parts/ and random stack overflow/Reddit posts, but I can't see how to apply what they say to this code.

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);
    }
}

This produces the following compile error:

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

I don't understand why it thinks I'm immutably borrowing cache on line 26. My understanding is main creates an instance of CacheForMove and owns that value. It's mutably-lending the value to the stairs function, and so now stairs has mutably borrowed the value. I expected to be able to invoke both get_for_n and insert_for_n on that mutably-borrowed reference.

Answers that I don't understand yet

Is this a duplicate of How can I mutate other elements of a HashMap when using the entry pattern? ?

In this SO question, the OP wants to have their update for one key in the cache depend on the value of a different key in the cache. I do eventually want to do that to, but I'm running into a problem before I get to that point. I'm not looking at other entries in the cache in order to compute "this" entry. The answers in that question says that they would need to split getting from the cache from inserting into the cache like so:

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
}

However, I believe my code already splits getting from inserting, and yet I still get a compile error.

Even if I adapt the above example to match my 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
}

I still get the same error:

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

Is this a duplicate of What is the idiomatic way to implement caching on a function that is not a struct method? ?

In that SO question, the OP states they are unwilling to use a struct, and the answers provided use some combination of unsafe, mutex, lazy_static!, RefCell, and so on.

I have the opposite issue. I am perfectly willing to use a struct (and in fact, I am using one in my original problem statement), but using unsafe, mutex, lazy_static!, and so on sound much more dangerous or complex to me.

The OP of that question implies that if we could use a struct, the solution would be obvious. I would like to learn that obvious solution.

you are immutable borrowing it - to run get_for_n method, which borrows from self and releases this borrow, when returned value gets out of scope (that is, at the end of the match). You don't want the matched value to be invalidated by whatever the stairs function do to the cache.

The matched value is not used by whatever the stairs function does. In the implementation shown in the original problem statement:

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

I immutably borrow cache to get a cached value out of it. If there is a value available, I return it (without recursively calling stairs again). If there is no value, I expect None to be copyable (i.e. I can have my own copy of None on my stack; I no longer need to reference any data in cache at all). At this point, I expect to be able to safely mutably borrow cache to invoke stairs(cache, n-1), because there are no other borrows (mutable or immutable) to cache.

To really drive this point home, consider this alternative implementation of the stairs function:

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);
}

Here I've used a pair of curly braces to limit the scope of the immutable borrow. I perform an immutable borrow to populate maybe_result, and check whether it is a Some. If it is, I unwrap the internal value and return it. If not, I end my scope, and thus all borrows have gone out of scope and are now invalid. There are no borrows happening anymore.

Then, I try to mutably borrow cache to recursively invoke stairs. This should be the only borrow happening at this point, and so I expect this borrow to succeed, but the compiler tells me:

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

解决方案

I think I've got this figured out, so recording my answer in case someone else gets stuck with the same problem. This compiles and runs:

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);
    }
}

There are 2 main changes:

1. stairs no longer returns &Vec<Vec<usize>> and instead returns Vec<Vec<usize>>
2. In the Some(result) case, we return result.clone() instead of result.

2 is a consequence of 1, so let's focus on why 1 is necessary and why it fixes the problem. The HashMap owns the Vec<Vec<usize>>, and so when the original implementation returned a &Vec<Vec<usize>>, it was returning a reference to a memory location owned by the HashMap. If someone were to mutate the HashMap, say by deleting an entry, since the HashMap owns the Vec<Vec<usize>>, the HashMap would conclude that it's safe to deallocate the memory being used by the Vec<Vec<usize>>, and I'd end up with a dangling reference.

I can only return a &Vec<Vec<usize>> as long as I can guarantee no one will mutate the HashMap for as long as the &Vec<Vec<usize>> reference exists, and since I'm returning the &Vec<Vec<usize>> reference to my caller, that essentially means I need to guarantee that the HashMap is immutable forever (since I have no idea what the caller might do).

这篇关于如何编写可以同时读取和写入缓存的rust函数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！