I am trying to implement a simple bucketed hash table in Rust (just for practice). The hash table struct is defined as:
pub struct BucketedHashTable<K: Hash, V> {
buckets: Vec<Bucket<K, V>>,
size: usize,
}
where Bucket is my simple implementation of a singly linked stack.
In pretty much every method of the table (put, remove, get) I will be getting the bucket where the key is to be inserted into (removed from, looked up in), so I extracted a method for just that:
fn pick_bucket(&mut self, key: K) -> &mut Bucket<K, V> {
let mut hasher = DefaultHasher::new();
key.hash(&mut hasher);
let hash = hasher.finish() as usize;
let index = hash % self.buckets.len();
&mut self.buckets[index]
}
I return a reference to the bucket because I don't want to move it out of the buckets Vec of the hash table. And I return a mutable reference because I am going to mutate the returned bucket (for example, when inserting a new entry (key-value pair) into it).
The above code does compile.
But if I get rid of the intermediate variable index and calculate the index right inside the [] brackets, like so:
fn pick_bucket(&mut self, key: K) -> &mut Bucket<K, V> {
let mut hasher = DefaultHasher::new();
key.hash(&mut hasher);
let hash = hasher.finish() as usize;
&mut self.buckets[hash % self.buckets.len()]
}
I will get this borrow error:
error[E0502]: cannot borrow `self.buckets` as immutable because it is also borrowed as mutable
--> src\lib.rs:30:34
|
26 | fn pick_bucket(&mut self, key: K) -> &mut Bucket<K, V> {
| - let's call the lifetime of this reference `'1`
...
30 | &mut self.buckets[hash % self.buckets.len()]
| -------------------------^^^^^^^^^^^^^^^^^^-
| | | |
| | | immutable borrow occurs here
| | mutable borrow occurs here
| returning this value requires that `self.buckets` is borrowed for `'1`
I thought the two code snippets above are equivalent. How do they differ, why does the first one compile, and why the second one does not?
Edit: I suppose the immutable borrow of self.buckets in the first code snippet goes out of scope and gets "invalidated" right at the end of the line with let index = ...;, so when the method returns, there's no shared references to self.buckets left; and in the second snippet, the immutable borrow of self.buckets lives right until the method returns (so at that moment both a shared and a mutable reference co-exist). If this is correct, why is this the case? Why doesn't the immutable borrow of self.buckets get "invalidated" when reaching the ] bracket in the second case, but instead live for the entire expression (the whole return line)?
I believe you've exactly figured out the problem in your Edit. In the first example, self.buckets is immutably borrowed, and then the borrow ends at the end of the statement. In the second example, self.buckets is mutably borrowed and then immutably borrowed in the same statement. That's not allowed.
self.buckets.len() is a temporary, and its lifetime rules (drop scope) are explained in Temporary Scopes:
Apart from lifetime extension, the temporary scope of an expression is the smallest scope that contains the expression and is one of the following:
- The entire function body.
- A statement.
- The body of a if, while or loop expression.
- The else block of an if expression.
- The condition expression of an if or while expression, or a match guard.
- The expression for a match arm.
- The second operand of a lazy boolean expression.
This is explained even further in the note:
Temporaries that are created in the final expression of a function body are dropped after any named variables bound in the function body, as there is no smaller enclosing temporary scope.
So the self.buckets.len() borrow lasts all the way to the end of the function (after the function body, after even the statement has completed). But it's easier to think about it as lasting to the end of the statement (which it would in any case).
There are no "sub-expression" drop scopes created inside of a single statement. In theory it's probably possible, but Rust is not that aggressive.