Building a Low-Level Trie With Rust

Before getting to grips with a distributed gossip system in Rust, I decided that it would be better to look at something a bit more challenging, but smaller in scope. I decided to implement the low-level trie challenge in Rust.

This is interesting because it is complex enough problem to require thinking even for experienced developers, but at the same time, it isn’t that complex — it just has a lot of details. It also requires us to do a lot of low-level stuff and manipulate memory directly, so that is something that would be an interesting test for a system level programming language.

On the one hand, even with just a few hours with Rust, I can see some elegance coming out of certain pieces. For example, take a look at the following code:

fn find_node(self: &Trie, key: &str) -> Result<NodeAndParent, TrieErrors> {
let header = self.trie_header();
if header.items == 0 {
return Err(TrieErrors::ValNotFound);
}
​
let node = self.node_header(mem::size_of::<TrieHeader>() as isize);
​
match node.find_match(None, 0, key) {
Err(NodeErrors::ValNotFound) |
Err(NodeErrors::PartialMatch{ closest: _})
=> Err(TrieErrors::ValNotFound),
Ok(matching_node) => Ok(matching_node)
}
}

This is responsible for searching on the trie for a value, and I like that the find_match function traverses the tree and allow me to return both an enum value and the closest match to this when it fails (so I can continue the process directly from there).

On the other hand, we have pieces of code like this:

And any line that has four casts in it is already suspect. And as I’m dealing with the raw memory, I have quite a bit of this.

And I certainly feeling the pain of the borrow checker. Here is where I’m currently stumped.

struct MyTrie{
/* fields */
}
​
struct Node {
/* fields */
}
​
impl MyTrie {
fn find(self: &MyTrie, key: &str) -> Option<&Node> {
unimplemented!()
}
​
fn delete(self: &mut MyTrie, key: &str) {
let result = self.find(key);
​
match result {
None => {}, // not there, nothing to do
Some(node) => {
self.delete_internal(node);
}
}
}
​
fn delete_internal(self: &mut MyTrie, node: &Node) {
unimplemented!()
}
}

This is a small and simple example that shows the issue. It fails to compile:

I have a method that takes a mutable MyTrie reference and passes it to a method that expects an immutable reference. This is fine and would work, but I need to use the value from the find method in the delete_internal method, which again needs a mutable instance. However, this fails with error[E0502]: cannot borrow `*self` as mutable because it is also borrowed as immutable.

I understand the problem, but I am not really sure how to solve it. The problem is that I kind of want the find method to remain immutable since it is also used in the read method, which can run on immutable instances.

Technically speaking, I could copy the values that I want out of the node reference and do a lexical scope that would force the immutable borrow to end, but I’m unsure yet what would be the best option.

It seems like a lot of work to get what I want in spite, and not with the help, of the compiler.