Как мне построить Cacher в Rust, не полагаясь на черту Copy?

Question

Я пытаюсь реализовать Cacher, как упомянуто в главе 13 книги Rust, и сталкиваюсь с неприятностями.

Мой Cacher код выглядит следующим образом:

use std::collections::HashMap;
use std::hash::Hash;

pub struct Cacher<T, K, V>
where
    T: Fn(K) -> V,
{
    calculation: T,
    values: HashMap<K, V>,
}

impl<T, K: Eq + Hash, V> Cacher<T, K, V>
where
    T: Fn(K) -> V,
{
    pub fn new(calculation: T) -> Cacher<T, K, V> {
        Cacher {
            calculation,
            values: HashMap::new(),
        }
    }

    pub fn value(&mut self, k: K) -> &V {
        let result = self.values.get(&k);
        match result {
            Some(v) => {
                return v;
            }
            None => {
                let v = (self.calculation)(k);
                self.values.insert(k, v);
                &v
            }
        }
    }
}

и мой тестовый пример для этой библиотеки выглядит следующим образом:

mod cacher;

#[cfg(test)]
mod tests {
    use cacher::Cacher;

    #[test]
    fn repeated_runs_same() {
        let mut cacher = Cacher::new(|x| x);
        let run1 = cacher.value(5);
        let run2 = cacher.value(7);

        assert_ne!(run1, run2);
    }
}

Я столкнулся со следующими проблемами при запуске моего тестового примера:

1. error[E0499]: cannot borrow cacher as mutable more than once at a time Каждый разЯ делаю значение run1, run2, которое оно пытается заимствовать cacher как изменчивое заимствование.Я вообще не понимаю, почему это заимствование - я подумал, что cacher.value() должен возвращать ссылку на элемент, который хранится в cacher, который не является заимствованием.
2. error[E0597]: v does not live long enough, указывающий наv Я возвращаю в None случае value ().Как правильно переместить v в HashMap и дать ему то же время жизни, что и HashMap?Ясно, что время жизни истекает, когда он возвращается, но я хочу просто вернуть ссылку на него, чтобы использовать в качестве возврата из value ().
3. error[E0502]: cannot borrow self.values ​​as mutable because it is also borrowed as immutable in value ().self.values.get(&k) - это неизменный заем, а self.values.insert(k,v) - изменяемый заем, хотя я думал, что .get() - это неизменный заем, а .insert() - передача права собственности.

и некоторые другие ошибкисвязанные с перемещением, которые я должен быть в состоянии обрабатывать отдельно.Это гораздо более фундаментальные ошибки, которые указывают на то, что я неправильно понял идею владения в Rust, но перечитывание сегмента книги не дает мне понять, что я пропустил.

Answer 1

1. Возврат ссылки на значение - это то же самое, что и заимствование этого значения. Поскольку эта ценность принадлежит кешеру, она также косвенно заимствует и кешера. Это имеет смысл: если вы берете ссылку на значение в кэше, а затем уничтожаете его, что происходит с вашей ссылкой? Также обратите внимание, что если вы измените кэширование (например, вставив новый элемент), это может перераспределить хранилище, что сделает недействительными любые ссылки на значения, хранящиеся внутри.

   Ваши значения должны быть не менее Clone, чтобы Cacher::value мог возвращаться по значению, а не по ссылке. Вы можете использовать Rc, если ваши значения слишком дороги для клонирования, и вы согласны, что все вызывающие абоненты получают один и тот же экземпляр.

2. Наивный способ получить экземпляр, который был сохранен в HashMap, в отличие от временного, выделенного для его построения, - это вызвать self.values.get (k).unwrap() после вставки значения в карту. Чтобы избежать удвоения вычисления местоположения значения на карте, вы можете использовать интерфейс Entry:

   pub fn value(&mut self, k: K) -> Rc<V> {
       self.values.entry (&k).or_insert_with (|| Rc::new (self.calculation (k)))
   }
   

3. Я считаю, что мой ответ на пункт 2 также решает эту проблему.

Answer 2

Я думаю, что здесь есть несколько вопросов, которые нужно рассмотреть:

Во-первых, для определения функции value(&mut self, k: K) -> &V;компилятор вставит вам время жизни, чтобы оно стало value(&'a mut self, k: K) -> &'a V.Это означает, что время жизни self не может уменьшиться ради функции, потому что есть ссылка, выходящая из функции с тем же временем жизни, и будет жить столько же, сколько и область действия.Поскольку это изменчивая ссылка, вы не можете заимствовать ее снова.Следовательно, ошибка error[E0499]: cannot borrow cacher as mutable more than once at a time.

Во-вторых, вы вызываете функцию calculation, которая возвращает значение в некоторой внутренней области действия функции value(), а затем вы возвращаете ссылку на нее, что невозможно.Вы ожидаете, что ссылка будет жить дольше, чем референт.Отсюда ошибка error[E0597]: v does not live long enough

Третья ошибка немного связана.Как видите, let result = self.values.get(&k);, как упоминалось в первом утверждении, заставляет k оставаться неизменным до конца функции.Возвращаемое значение result будет действовать до тех пор, пока ваша функция value() означает, что вы не можете взять заем (изменяемый) в той же области действия, что приводит к ошибке error[E0502]: cannot borrow self.values as mutable because it is also borrowed as immutable in value() self.values.get(&k)

Ваш K должен бытьClone, причина k будет перемещена в функцию calculation, что сделает ее непригодной для использования во время insert.

Так что с K в качестве Clone реализация Cacher будетbe:

impl<T, K: Eq + Hash + Clone, V> Cacher<T, K, V>
where
    T: Fn(K) -> V,
{
    pub fn new(calculation: T) -> Cacher<T, K, V> {
        Cacher {
            calculation,
            values: hash_map::HashMap::new(),
        }
    }

    pub fn value(&mut self, k: K) -> &V {
        if self.values.contains_key(&k) {
            return &self.values[&k];
        }

        self.values.insert(k.clone(), (self.calculation)(k.clone()));
        self.values.get(&k).unwrap()
    }
}

Это время жизни здесь основано на потоке управления ветвлением.Блок if self.values.contains_key ... всегда возвращается, поэтому код после блока if может быть выполнен только тогда, когда if self.values.contains_key ... равен false.Крошечная область, созданная для условия if, будет жить только в рамках проверки условия, т.е. ссылка, полученная (и возвращенная) для if self.values.contains_key(..., исчезнет с этой крошечной областью.

Для получения дополнительной информации см. NLL RFC

Как отметил @jmb в своем ответе, чтобы ваш тест работал, V должен быть Clone (impl <... V:Clone> Cacher<T, K, V>) для возврата по значению или использования долевого владениянапример Rc, чтобы избежать затрат на клонирование.

например.

fn value(&mut self, k: K) -> V  { ..
fn value(&mut self, k: K) -> Rc<V> { ..