Building a trie from a vector of strings in Rust

Question

I'm learning rust (coming from C++) and playing around with different small algorithms to understand the ownership & borrowing concepts better. Currently, I'm having difficulties finding the idiomatic way to reuse a Vector after iterating over it in a for-loop. This is the (very verbose) code I currently have:

fn build_trie(paths: &Vec<String>) -> TreeNode {
        let mut root = TreeNode::new('\0');
        for path in paths {
            // start at the root node
            let mut current_node = &mut root;
            for ch in path.as_bytes() {
                let ch = *ch as char;
                println!("Current char: {}", ch);
                let length: i32 = current_node.children.len() as i32;
                let mut found_child = false;
                // for each child of the current node, check if the current character matches
                for i in 0..length as usize {
                    // found a match, descend into the tree
                    if current_node.children[i].get_value() == ch {
                        println!("Found matching char: {}", ch);
                        found_child = true; // avoid adding a new child later
                        current_node.children[i].increment_count();
                        current_node = &mut current_node.children[i];
                        break;
                    }
                    found_child = false;
                }
                // no matching child found, add a new child
                // and descend into the tree
                if !found_child {
                    let new_node = TreeNode::new(ch);
                    current_node.children.push(new_node);
                    current_node = current_node.children.last_mut().unwrap();
                }
            }
        }
        root
    }

While this does seem to work, I wanted to replace the for i in 0..length header with for child in current_node.children.iter_mut(). The problem is that this does a mutable borrow of current_node.children which also happens in the last if-statement, which obviously isn't allowed twice. I have the feeling that I'm missing some simple detail. I did a lot of googling but couldn't find anything that answered my question.

PS: I'm not sure if this question is for Code Review or StackOverflow. But since it might be opinion-based (and those get closed immediately...) I thought I'd try here first.

Answer 1

welcome to the Rust community.

Rust's borrow checker analyzes the control flow of your code. However, it does not take into account the state of your variables (current_node and found_child in your example). That would be something like symbolic execution.

Instead, the borrow checker is pessimistic and it checks your if !found_child for conflicts with the part that sets found_child = true.

I suggest you use an iterator to find a child that the current character matches, and then work with indices to manipulate the trie. This way, you still get the performance benefits of iterators:

#[derive(Debug)]
struct TreeNode {
    ch: char,
    count: u32,
    children: Vec<TreeNode>,
}

impl TreeNode {
    fn new(ch: char) -> Self {
        Self {
            ch,
            count: 0,
            children: vec![],
        }
    }

    fn get_value(&self) -> char { self.ch }

    fn increment_count(&mut self) { self.count += 1; }
}

fn build_trie(paths: &Vec<String>) -> TreeNode {
    let mut root = TreeNode::new('\0');
    for path in paths {
        // start at the root node
        let mut current_node = &mut root;
        for ch in path.as_bytes() {
            let ch = *ch as char;
            println!("Current char: {}", ch);
            // for each child of the current node, check if the current character matches
            let maybe_found = current_node.children.iter_mut().position(|child|
                child.get_value() == ch
            );
            match maybe_found {
                Some(index) => {
                    println!("Found matching char: {}", ch);
                    current_node.children[index].increment_count();
                    current_node = &mut current_node.children[index];
                }
                None => {
                    let new_node = TreeNode::new(ch);
                    current_node.children.push(new_node);
                    current_node = current_node.children.last_mut().unwrap();
                }
            }
        }
    }
    root
}

fn main() {
    let paths = vec!["abc".to_string(), "abd".to_string()];
    let trie = build_trie(&paths);
    println!("{:?}", trie);
}