Can anyone help explain a lifetime question for this code snippet on HashMap? Appreciate it!

    fn is_cyclic(target: i32, pre: i32,  cur: i32, graph: &mut HashMap<i32, HashSet::<i32>>) -> bool {
        let next_jumps = graph.get(&cur).unwrap();
        for item in next_jumps.iter() {
            if *item == pre  /* rule out come-from-itself case */{
                continue;
            } else if *item == target /* if (*item) node is target, it's cyclic*/{
                return true
            }
            // continue checking (*item) node is cyclic, if not, move to next node.
            if Self::is_cyclic(target, cur, *item, graph) {
                return true
            }
        }
        false
    }
Line 22, Char 16: cannot borrow `*graph` as mutable because it is also borrowed as immutable (solution.rs)
   |
14 |         let next_jumps = graph.get(&cur).unwrap();
   |                          ----- immutable borrow occurs here
15 |         for item in next_jumps.iter() {
   |                     ----------------- immutable borrow later used here
...
22 |             if Self::is_cyclic(target, cur, *item, graph) {
   |                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here
error: aborting due to previous error

but if I change to

fn is_cyclic(target: i32, pre: i32,  cur: i32, graph: &mut HashMap<i32, HashSet::<i32>>) -> bool {
        let next_jumps = graph.get(&cur).unwrap();
        for item in next_jumps.iter() {
            if *item == pre  /* rule out come-from-itself case */{
                continue;
            } else if *item == target /* if (*item) node is target, it's cyclic*/{
                return true
            }
            // continue checking (*item) node is cyclic, if not, move to next node.
            return Self::is_cyclic(target, cur, *item, graph) /* <----- DIRECT RETRUN ------>*/
        }
        false
    }

will work fine. Why? I assumed there is lifetime concept I didn't fully get it.
Is there any compiler decorator to tell compiler this-is-fine without changing function signature ?

No, this is not fine: by doing .get().iter(), you have references to the interior of the map inside the loop. Thus, you are not allowed to mutate the map, which is what the recursive call to the same function is allowed to do (due to the &mut in its signature).

Note that your second code snippet is not equivalent with the first one: you unconditionally return from the function at the end of the first iteration, so the loop body will never execute more than once. Hence, NLL kicks in, realizes you won't reach the next iteration, and ends the lifetime of the immutable borrow early, so the subsequent mutable borrow remains valid.


Why do you want to take a mutable reference to the map anyway? You don't seem to need it.

Thanks for reply. In second snippet, The loop body can still continue if matching first case which can loop more than once, right? But YES, recursive caller is_cyclic will be execute once if reach. So I assume the condition of NLL would be execute-only-once, then what's the idiomatic way to handle for recursive looping on function encompass &mut HashMap parameter?

But if you continue at that point, you don't reach the recursive call that mutably borrows. Once you ever reach that call, you return immediately.

The idiomatic way is not to require mutable references when you don't need them. I don't see any easy or obvious way to make your function work – mutable borrows can't alias with anything, period. You really should get rid of the mutable reference and use an immutable one instead.

If you really insist on keeping the mutability, you'll have to clone the set of neighbors, like this:

fn is_cyclic(target: i32, pre: i32, cur: i32, graph: &mut HashMap<i32, HashSet::<i32>>) -> bool {
    for item in graph[&cur].clone() {
        // rule out come-from-itself case
        if item == pre {
            continue;
        }
        
        // if item node is target, it's cyclic
        if item == target {
            return true;
        }
        
        // continue checking if item node is cyclic, if not, move to next node.
        if is_cyclic(target, cur, item, graph) {
            return true;
        }
    }
    
    false
}

(I also made your code more idiomatic by removing spurious .get().unwrap()s, .iter()s, conditionals, and cleaning up formatting.)

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.