CODEWITHSUNDEEP
rustownership
jang
jang

Reputation: 13

Modify specific value in HashMap object in case ownership of its object can be moved later

I'm implementing a Depth-First-Search.

Its data structure is implemented with HashMap like "current node" -> "next nodes".

To avoid loop in cyclic graph, my program tries to remove a node from HashMaps value(Vec of next depth Vertices) when it is stamped.

When manipulating HashMap object's value by get_mut, I noticed that ownership of its whole HashMap object can't be moved later.

#[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![],
    }
}

As written in the comment, there is an illegal move in the recursive call.

So I get the following message while compiling.

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

Could you suggest a nice way to solve this or redesign the whole code?

Upvotes: 1

Views: 94

Answers (1)

Anders Kaseorg
Anders Kaseorg

Reputation: 3875

Your code compiles as written in stable Rust 2018 (or nightly Rust 2015 with #![feature(nll)]).

To make it work on stable Rust 2015, you can move the recursive calls outside of the scope where field is borrowed. One way to do that is as follows:

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

Upvotes: 1

Related Questions