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