Изменить конкретное значение в объекте HashMap на случай, если право собственности на его объект может быть перемещено позже

Question

Я реализую поиск по глубине.

В его структуре данных реализовано HashMap, например, "текущий узел" -> "следующие узлы".

Чтобы избежать циклав циклическом графе моя программа пытается удалить узел из значения HashMap s (Vec вершин следующей глубины) при его штамповке.

При манипулировании значением HashMap объекта с помощью get_mut, язаметил, что право собственности на весь объект HashMap нельзя переместить позже.

#[derive(Debug, PartialEq, Eq, Hash, Copy, Clone)]
pub enum Vertex<A> {
    Start,
    Goal,
    Vertex(A),
}

pub fn search(
    curr: &Vertex<i32>,
    mut acc: Vec<Vertex<i32>>,
    mut field: HashMap<Vertex<i32>, Vec<Vertex<i32>>>,
    goal: &Vertex<i32>,
) -> Vec<Vertex<i32>> {
    match field.get_mut(&curr) {
        // when reached goal
        _ if *curr == *goal => {
            acc.push(*curr);
            acc
        }

        // when vertices found
        Some(ns) => {
            if let Some(next) = ns.pop() {
                // go to next depth
                acc.push(*curr);
                // trying to move "field"'s ownership to next recursive call here but it fails because "field.get_mut(&curr)" is done at match expression
                search(&next, acc, field, goal)
            } else if let Some(prev) = acc.pop() {
                // backtrack
                search(&prev, acc, field, goal) // ditto
            } else {
                // no answer
                vec![]
            }
        }

        // when next is not registered
        None => vec![],
    }
}

Как написано в комментарии, в рекурсивном вызове есть недопустимое перемещение.

Итак, япри компиляции вы получите следующее сообщение:

18 |     let result: Vec<Vertex<i32>> = match field.get_mut(&curr) {  
   |                                          ----- borrow of `field` occurs here  
...  
29 |                 _search(&next, acc, field, goal) // to be fixed  
   |                                     ^^^^^ move out of `field` occurs here  

error[E0505]: cannot move out of `field` because it is borrowed  
  --> src/algorithm/search/graph/depth_first.rs:31:37  
   |  
18 |     let result: Vec<Vertex<i32>> = match field.get_mut(&curr) {  
   |                                          ----- borrow of `field` occurs here  
...  
31 |                 _search(&prev, acc, field, goal) // to be fixed  
   |                                     ^^^^^ move out of `field` occurs here  

Не могли бы вы предложить хороший способ решить эту проблему или переработать весь код?

Answer 1

Ваш код компилируется как написано в стабильном Rust 2018 (или в ночной Rust 2015 с #![feature(nll)]).

Чтобы он работал в стабильной версии Rust 2015, вы можете переместить рекурсивные вызовы за пределы области, где заимствовано field. Один из способов сделать это заключается в следующем:

pub fn _search(
    curr: &Vertex<i32>,
    mut acc: Vec<Vertex<i32>>,
    mut field: HashMap<Vertex<i32>, Vec<Vertex<i32>>>,
    goal: &Vertex<i32>,
) -> Vec<Vertex<i32>> {
    let v = match field.get_mut(&curr) {
        // when reached goal
        _ if *curr == *goal => {
            acc.push(*curr);
            return acc;
        }

        // when vertices found
        Some(ns) => {
            if let Some(next) = ns.pop() {
                // go to next depth
                acc.push(*curr);
                next
            } else if let Some(prev) = acc.pop() {
                // backtrack
                prev // ditto
            } else {
                // no answer
                return vec![];
            }
        }

        // when next is not registered
        None => return vec![],
    };
    _search(&v, acc, field, goal)
}