Cannot infer appropriate lifetime with custom iterator trait

I read a bunch of seemingly duplicate questions but either didn't know how to use that to resolve my issue or the suggested answers didn't seem to work.

I am trying to implement a custom, cursor like iterator for a skip list. I am getting the following error and have pulled out all my hair and nails trying to resolve it:

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
  --> src/memtable.rs:87:40
   |
87 |         self.current_node = self.store.find_greater_or_equal_node(target);
   |                                        ^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime defined on the method body at 86:13...
  --> src/memtable.rs:86:13
   |
86 |     fn seek(&mut self, target: &Self::Key) -> Result<(), Self::Error> {
   |             ^^^^^^^^^
note: ...so that reference does not outlive borrowed content
  --> src/memtable.rs:87:29
   |
87 |         self.current_node = self.store.find_greater_or_equal_node(target);
   |                             ^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 78:6...
  --> src/memtable.rs:78:6
   |
78 | impl<'a> DbIterator<'a> for SkipListMemTableIter<'a> {
   |      ^^
note: ...so that the expression is assignable
  --> src/memtable.rs:87:29
   |
87 |         self.current_node = self.store.find_greater_or_equal_node(target);
   |                             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: expected `Option<&'a SkipNode<InternalKey, Vec<u8>>>`
              found `Option<&SkipNode<InternalKey, Vec<u8>>>`

The code is:

use nerdondon_hopscotch::concurrent_skiplist::{ConcurrentSkipList, SkipNode};

impl SkipListMemTable {
    fn iter(&self) -> Box<dyn DbIterator<Key = InternalKey, Error = DbError> + '_> {
        Box::new(SkipListMemTableIter {
            store: Arc::clone(&self.store),
            current_node: self.store.first_node(),
        })
    }
}

struct SkipListMemTableIter<'a> {
    store: Arc<ConcurrentSkipList<InternalKey, Vec<u8>>>,

    current_node: Option<&'a SkipNode<InternalKey, Vec<u8>>>,
}

impl<'a> DbIterator<'a> for SkipListMemTableIter<'a> {
    type Key = InternalKey;
    type Error = DbError;

    fn seek(&mut self, target: &Self::Key) -> Result<(), Self::Error> {
        self.current_node = self.store.find_greater_or_equal_node(target);

        Ok(())
    }
}

/// Iterator trait
pub trait DbIterator<'i>
{
    type Key;
    type Error;

    fn seek(&mut self, target: &Self::Key) -> Result<(), Self::Error>;

    // also tried but this isn't what i want since it make it borrow for the lifetime of the iterator
    // but i need to be able to call other methods on the iterator
    // fn seek(&'i mut self, target: &Self::Key) -> Result<(), Self::Error>;

    fn next(&mut self) -> Option<(&Self::Key, &Vec<u8>)>;
}

I have tried various kind of lifetime annotations, one of which i commented on above. I'm confused at what exactly is wrong. I have an Arc of the backing collection so it seems that the reference in self.current_node should live just fine. Is that true? If so i'm not sure how to tell Rust.

There's a lot of missing context here, so it's a bit hard for me to be certain. But does this work?

 struct SkipListMemTableIter<'a> {
-    store: Arc<ConcurrentSkipList<InternalKey, Vec<u8>>>,
+    store: &'a ConcurrentSkipList<InternalKey, Vec<u8>>,
     current_node: Option<&'a SkipNode<InternalKey, Vec<u8>>>,
 }

 impl SkipListMemTable {
     fn iter(&self) -> Box<dyn DbIterator<Key = InternalKey, Error = DbError> + '_> {
         Box::new(SkipListMemTableIter {
-            store: Arc::clone(&self.store),
+            store: &*self.store,
             current_node: self.store.first_node(),
         })
     }
 }

-impl<'a> DbIterator<'a> for SkipListMemTableIter<'a> { /* ... */ }
+impl<'a> DbIterator for SkipListMemTableIter<'a> { /* ... */ }

-pub trait DbIterator<'i> { /* ... */ }
+pub trait DbIterator { /* ... */ }

Playground with a lot of guessing.

(Disclaimer: There's so much guessing I didn't put much work into understanding the overall structure of things; I just addressed the compiler errors until it compiled.)

1 Like

Thanks for taking a look. I suppose that I can try to work around it so that I don't keep an Arc on the backing store but it's curious (and frustrating) that this is not something that Rust doesn't have an intuitive fix or inference for especially if keeping the Arc usually relaxes lifetime concerns. I wonder if someone knows how I can keep the Arc?

Why do you need the Arc specifically? If I'm understanding correctly (I may not be), the iterator structure is already borrowing the underlying data in the current_node field. Moreover, it's a private field and the API of your SkipListMemTable didn't change.

Fundamentally the problem is that you're trying to create a struct that both owns and borrows some data, also knowns as a self-referential struct, and this plays horrendously with the ownership and borrowing rules. Currently you can only refactor your program to avoid these type of structs or you can use unsafe to get around it. Note that the latter is pretty tricky and hard to get right but there are crates that can do that for you, like ouroboros.

It's only a self-referential struct if you insist on using an Arc rather than a reference in the iterator. Otherwise the struct just has two references to the same external value.

thanks all for the continued explanations. looks like i have more reading to do on self-referential structs. I guess the only reason I put an Arc into the iterator was because i didnt trust myself and wanted a security blanket with Arc (however dumb that sounds).

appreciate the explanations.