+972 52-548-6969
Building a low level trie with Rust: Part I
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 complex, just have a lot of details. It also require us to do a lot of lot 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:
This is responsible for searching on the trie for a value, and I like that the find_match function traverse the tree and allow me to return both an enum value and a 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.
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 pass it to a method that expects a 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. But 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 kinda want the find method to remain immutable, since it is also used on 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.
Comments
I think that the problem is that when callin find(), rust "binds" the same lifetime for
resultandself. Sinceresultlifetime ends at the end of scope ofdelete, it prevents the mutable borrow fordelete_internal.If you specify different lifetimes in
find()forselfand its returned reference&Nodethenselfborrow's lifetime will be limited at the end offind(),lifetime will be the end ofdelete`.I tried it and it compiles, but i am not sure it can not cause problems... is it really safe to allow a readable reference to a node if we can modify the Trie ?
Guillaume, That is a good point, we are effectively lying to the compiler here, which is interesting. The idea is that I know that I'm invalidating the reference here, so I won't be using it. And this is fairly unsafe code, anyway.
But yes, it is strange.
Yeah, this is why the D programming language has
inoutas an option for constness:```D struct Trie(T) { inout(Node!T) find(T[] key) inout {} } ~~~ If you call
findon aconst Trie, you get aconst Node!Tback. If you call it on a mutableTrie, you get a mutableNode!Tinstead.Comment preview