Мутабельный заем от HashMap и пожизненное решение

Question

Глава 13 книги Rust (2-е издание) содержит пример простого кеша вычислений. Cacher принимает функцию вычисления в качестве параметра конструктора и кэширует результат - после первого вызова она больше не будет вызывать функцию, а просто вернет кэшированный результат:

struct Cacher<T>
where
    T: Fn(u32) -> u32,
{
    calculation: T,
    value: Option<u32>,
}

impl<T> Cacher<T>
where
    T: Fn(u32) -> u32,
{
    fn new(calculation: T) -> Cacher<T> {
        Cacher {
            calculation,
            value: None,
        }
    }

    fn value(&mut self, arg: u32) -> u32 {
        match self.value {
            Some(v) => v,
            None => {
                let v = (self.calculation)(arg);
                self.value = Some(v);
                v
            }
        }
    }
}

Он очень ограничен, и в книге есть пара предложений по улучшению, оставленных в качестве упражнения для читателя.

Так что я пытаюсь заставить его кэшировать несколько значений. Cacher содержит HashMap со значениями результата, а не только одно значение. Когда будет запрошено значение, если оно есть в карте (кеше), верните его. В противном случае рассчитайте его, сохраните в кеше, а затем верните.

Кешер берет ссылки, потому что он не хочет владеть входами. При его использовании (см. Модульный тест) я заимствую, потому что результаты хранятся в кэше.

Вот моя попытка:

use std::collections::HashMap;

struct Cacher<T>
where
    T: Fn(&u32) -> u32,
{
    calculation: T,
    values: HashMap<u32, u32>,
}

impl<T> Cacher<T>
where
    T: Fn(&u32) -> u32,
{
    fn new(calculation: T) -> Cacher<T> {
        Cacher {
            calculation,
            values: HashMap::new(),
        }
    }

    fn value(&mut self, arg: u32) -> &u32 {
        let values = &mut self.values;
        match values.get(&arg) {
            Some(v) => &v,
            None => {
                let v = (self.calculation)(&arg);
                values.insert(arg, v);
                &values.get(&arg).unwrap()
            }
        }
    }
}

#[test]
fn call_with_different_values() {
    let mut c = Cacher::new(|a| a + 1);
    let v1 = c.value(1);
    assert_eq!(*v1, 2);
    let v2 = c.value(2);
    assert_eq!(*v2, 3);
}

Выход компилятора:

22 |     fn value(&mut self, arg: u32) -> &u32 {
   |              - let's call the lifetime of this reference `'1`
23 |         let values = &mut self.values;
24 |         match values.get(&arg) {
   |               ------ immutable borrow occurs here
25 |             Some(v) => &v,
   |                        -- returning this value requires that `*values` is borrowed for `'1`
...
28 |                 values.insert(arg, v);
   |                 ^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

Я заимствую self.values как изменяемый в строке 23. Тем не менее, когда я пытаюсь использовать его в следующей строке, я получаю ошибку «неизменный заем». Как match values.get(arg) неизменный заем values? Разве заимствование уже не произошло?

Также есть ошибка для строки 25. Исходя из моего понимания правил исключения из жизни , здесь должен применяться третий принцип - у нас есть &mut self в качестве параметра метода, поэтому его время жизни должно автоматически присваиваться возвращаемому значению?

Answer 1

Я не думаю, что вы будете счастливы с этой подписью:

fn value(&mut self, arg: u32) -> &u32

Без учета пожизненного права это читается как:

fn value(&'a mut self, arg: u32) -> &'a u32

Даже если вы реализуете это правильно, это имеет огромное значение. Например, вы не можете снова вызвать value, если старые результаты все еще используются. И это правильно, ведь ничто не мешает телу функции удалять старые значения из кэша.

Лучше последовать совету @hellow и сделать тип возврата u32.

Еще одно недоразумение: то, что вы уже позаимствовали ценности, не означает, что вы не можете снова позаимствовать их.

Теперь, чтобы ответить на ваш оригинальный вопрос: Компилятор вам не врет values.get(arg) действительно неизменный заем values. Техническое объяснение состоит в том, что подпись этого вызова метода (упрощенно) get(&self, k: &Q) -> Option<&V>. Таким образом, заем self (он же values) действителен до тех пор, пока на &V все еще можно ссылаться. Однако & V должен быть действителен как минимум для всего тела функции (чтобы его можно было вернуть). Теперь вы пытались заимствовать ссуды в случае None, что означает, что &V вообще никогда не существовало. Поэтому, если компилятор становится умнее, он может позволить вашему коду работать, но сейчас (1.34.0) это не так.