Reputation: 1080
I'm building a recursive trie structure in Rust and have a routine that returns the child node given a symbol id. To complicate this, my trie node is implemented as an enum to optimize for the sparseness of the node as nodes near the root tend to be dense but with long strings of sparse nodes following. This starts off as Inline, which can hold a small fixed number of child links, or is upgraded to Sparse when the limits of Inline are exceeded.
Total symbol count is large, in the tens of thousands.
Playground link here.
My helper routine should return Ok(&mut child)
on success or Err(&mut self)
if no space was found in the current Inline node:
impl TrieNode
/// return the child node on Ok, or Err with self if room can't be found in
/// current node variant
fn maybe_get_child_mut(&mut self, symbol: u16) -> Result<&mut Self, &mut Self> {
match self {
TrieNode::Inline(inline) => {
if let Some(child) = inline.maybe_get_child_mut(symbol) {
return Ok(child);
}
}
TrieNode::Sparse(sparse) => return Ok(sparse.get_child_mut(symbol)),
}
Err(self)
}
}
But I get this borrow error:
Compiling playground v0.0.1 (/playground)
error[E0499]: cannot borrow `*self` as mutable more than once at a time
--> src/main.rs:85:13
|
75 | fn maybe_get_child_mut(&mut self, symbol: u16) -> Result<&mut Self, &mut Self> {
| - let's call the lifetime of this reference `'1`
76 | match self {
77 | TrieNode::Inline(inline) => {
| ------ first mutable borrow occurs here
78 | if let Some(child) = inline.maybe_get_child_mut(symbol) {
79 | return Ok(child);
| --------- returning this value requires that `self.0` is borrowed for `'1`
...
85 | Err(self)
| ^^^^ second mutable borrow occurs here
It appears that the &mut
borrow is held for the duration of the routine even when inner function call returns None and falls out of scope. The code compiles if I comment out the return on line 79. This is a bit surprising to me since only one or the other &mut
references are held and their lifetimes are compatible as one is a subset of the other.
Any help on how to cure this code is appreciated. Ugly hacks are also acceptable as long as safety is not compromised ;-).
Upvotes: 1
Views: 55