Mutate a field of a Vec's element while looping over a field of another element in the same Vec

Question

I'm writing a Trie data structure in Rust to implement the Aho-Corasick algorithm. The TrieNode struct respresents a node and looks like this:

use std::collections::{HashMap, HashSet, VecDeque};

struct TrieNode {
    next_ids: HashMap<char, usize>,
    kw_indices: HashSet<usize>,
    fail_id: Option<usize>,
}

I use the same strategy as a generational arena to implement the trie, where all the nodes are stored in one Vec and reference each other using their indices. When building the automaton after creating the all the nodes, I'm trying to get the following code work without using the clone() method:

fn build_ac_automaton(nodes: &mut Vec<TrieNode>) {
    let mut q = VecDeque::new();
    for &i in nodes[0].next_ids.values() {
        q.push_back(i);
        nodes[i].fail_id = Some(0);
    }
    // ...
}

but the borrow checker is not very happy about it:

error[E0502]: cannot borrow `*nodes` as mutable because it is also borrowed as immutable
   |
   |             for &i in nodes[0].next_ids.values() {
   |                       -----                    - immutable borrow ends here
   |                       |
   |                       immutable borrow occurs here
   |                 q.push_back(i);
   |                 nodes[i].fail_id = Some(0);
   |                 ^^^^^ mutable borrow occurs here

What is another way (if any) to achieve the above without using the costly clone() method?

Answer 1

Split the slice:

fn build_ac_automaton(nodes: &mut Vec<TrieNode>) {
    let mut q = VecDeque::new();
    let (first, rest) = nodes.split_first_mut();
    for &i in first.next_ids.values() {
        q.push_back(i);
        if i == 0 {
            first.fail_id = Some(0);
        } else {
            rest[i-1].fail_id = Some(0);
        }
    }
    ...
}

However it might be less costly to simply clone only the next_ids:

fn build_ac_automaton(nodes: &mut Vec<TrieNode>) {
    let mut q = VecDeque::new();
    let ids: Vec<_> = nodes[0].next_ids.values().cloned().collect();
    for &i in ids {
        q.push_back(i);
        nodes[i].fail_id = Some(0);
    }
    ...
}