I've devised an iterator struct for iterating keys stored in a file. This struct implements seek and next methods. The seek method takes in a lookup key and positions the iterator to the first key that is equal or greater than the lookup key. The next method simply advances the iterator by one position. Since they both involve modifying the buffered file reader field in the struct, I choose to declare both of them as mutable self methods.
My codes do not compile as the borrow checking fails. I understand why the error occurs as the *self, aka. the iterator instance is mutably borrowed in a scope more than once. But I do not know how to work around this problem while still preserving the semantics of the seek and next methods.
pub struct SSTableIterator {
/// a buffered reader for reading the sstable file.
sstable_file_reader: BufReader<File>,
curr_table_key: Option<TableKey>,
}
impl TableKeyIterator for SSTableIterator {
fn seek(&mut self, lookup_key: &LookupKey) -> Option<&TableKey> {
while let Some(table_key) = self.next() {
if table_key >= &lookup_key.as_table_key() {
return Some(table_key);
}
}
None
}
fn next(&mut self) -> Option<&TableKey> {
let mut buf = Vec::new();
if let Ok(_) = self.sstable_file_reader.read_exact(&mut buf) {
if let Ok(table_key) = TableKey::decode_from_bytes(&buf) {
self.curr_table_key = Some(table_key);
return self.curr_table_key.as_ref();
}
}
None
}
fn curr(&self) -> Option<&TableKey> {
self.curr_table_key.as_ref()
}
}
error[E0499]: cannot borrow `*self` as mutable more than once at a time
--> src/storage/sstable.rs:52:37
|
51 | fn seek(&mut self, lookup_key: &LookupKey) -> Option<&TableKey> {
| - let's call the lifetime of this reference `'1`
52 | while let Some(table_key) = self.next() {
| ^^^^^^^^^^^ `*self` was mutably borrowed here in the previous iteration of the loop
53 | if table_key >= &lookup_key.as_table_key() {
54 | return Some(table_key);
| --------------- returning this value requires that `*self` is borrowed for `'1`
I believe there's nothing inherently wrong with what you're trying to do, and this is only rejected due to a limitation of the borrow checker. The issue is that in order to return table_key, its lifetime must be the lifetime of the &mut self receiver. But if the first key isn't sufficient and we go to the next iteration of the loop, we need to call .next() again... but the previous iteration borrowed self for the full lifetime in order to get a long enough lifetime to potentially return it, so self is still borrowed.
In theory, we could only borrow the last successful iteration for the full lifetime, and each prior iteration only long enough to check it. The borrow checker isn't sophisticated enough to prove that doing so is sound yet, though; it only knows that the value could be required to live for the lifetime.
That said, you can get it this to function by returning self.curr() instead, as then the mutable reborrow for next will always be short, and only the .curr() reborrow will need to cover the full receiver lifetime.
But that said, you don't need to return a borrow from next at all. Instead, just implement Iterator<Item=TableKey> and return the owned TableKey directly.
Except it's not limitation of the borrow checker, but “limitation” of iterator definition.
No, we can not do that. Iterator definition needs to guarantee that borrow would last till iterator itself is valid, otherwise collect couldn't work. And collect is kinda important method for iterators, it's used pretty often.
The desire to have an iterator which can lend elements for a limited time is perfectly valid and, in fact, lending iterator is the very first example that GATs stabilization blog post refers, but it can not created by subtly changing rules for the iterator.
It's different interface with different properties: LendingIterator is an iterator, too (and I really hope when LendingIterator would be added to std there would be a blanket implementation), but the opposite is not true.
It's limitation of iterator interface (made necessary by the lack of GATs in Rust 1.0), not limitation of borrow checker.
