How to implement Iterator for a Rc> chain?

Question

When implementing a skip list in Rust, I got stuck when trying to implement Iterator for a Rc<RefCell<T>> chain.

pub struct SkipList<K, V> {
    head: Rc<RefCell<SkipNode<K, V>>>,
    rng: rand::rngs::ThreadRng,
    len: usize,
}

impl<K: Ord, V> SkipList<K, V> {
    pub fn iter(&self) -> Iter<K, V> {
        let next = &RefCell::borrow(&self.head).next_by_height[0];
        Iter {
            ptr: next.as_ref().map(|ref cell|Rc::clone(cell)),
            _marker: Default::default(),
        }
    }
}

struct SkipNode<K, V> {
    entry: Entry<K, V>,
    next_by_height: [Option<Rc<RefCell<SkipNode>>>; MAX_HEIGHT],
}

pub struct Entry<K, V> {
    key: K,
    value: V,
}

struct SkipNode<K, V> {
    entry: Option<Entry<K, V>>,
    next_by_height: SkipTrack<K, V>,
}

pub struct Iter<'a, K: Ord, V> {
    ptr: Option<Rc<RefCell<SkipNode<K, V>>>>,
    _marker: marker::PhantomData<&'a K>,
}

impl<'a, K, V: 'a> Iterator for Iter<'a, K, V>
where K: Ord
{
    type Item = Ref<'a, Entry<K, V>>;

    fn next(&mut self) -> Option<Self::Item> {
        self.ptr.take().map(|node| {
            let current = RefCell::borrow(&node);
            self.ptr = current.next_by_height[0].as_ref().map(|ref node| Rc::clone(node));
            Ref::map(current, |ref wrapped| {
                &wrapped.entry.unwrap()
            })
        })
    }
}

and the error is:

   Compiling RclessRefCelllessTgreatergreater-Rust v0.1.0 (/home/runner/RclessRefCelllessTgreatergreater-Rust)
error[E0515]: cannot return reference to temporary value
   --> main.rs:138:15
    |
138 |               &wrapped.entry.unwrap()
    |               ^----------------------
    |               ||
    |               |temporary value created here
    |               returns a reference to data owned by the current function

error[E0507]: cannot move out of `wrapped.entry` which is behind a shared reference
   --> main.rs:138:16
    |
138 |               &wrapped.entry.unwrap()
    |                ^^^^^^^^^^^^^
    |                |
    |                move occurs because `wrapped.entry` has type `std::option::Option<Entry<K, V>>`, which does not implement the `Copy` trait
    |                help: consider borrowing the `Option`'s content: `wrapped.entry.as_ref()`

error[E0515]: cannot return value referencing function parameter `node`
   --> main.rs:137:13
    |
135 |               let current = RefCell::borrow(&node);
    |                                             ----- `node` is borrowed here
136 |               self.ptr = current.next_by_height[0].as_ref().map(|ref node| Rc::clone(node));
137 | /             Ref::map(current, |ref wrapped| {
138 | |                 &wrapped.entry.unwrap()
139 | |             })
    | |______________^ returns a value referencing data owned by the current function

error: aborting due to 3 previous errors

Some errors have detailed explanations: E0507, E0515.
For more information about an error, try `rustc --explain E0507`.
error: could not compile `RclessRefCelllessTgreatergreater-Rust`.

the full code is available at Repl.it.

I attempted to take the Ref<T> as the Item returned by Iterator, but the compiler complained that next could not return a temporary variable. Is there an elegant way to implement Iterator for Rc<RefCell>?

Answer 1

Is there an elegant way to implement Iterator for Rc<RefCell>?

Not particularly. There's two big things in your way.

---

One limitation when building an Iterator is that the output type cannot reference the iterator itself. It can either return an owned value (no lifetimes involved) or return references bound to the lifetime of some other object.

I see you've tried to communicate that you want to return Refs bound to the lifetime of the orignal SkipList by using PhantomData<&'a K> and also using 'a in your Iterator::Item. However, since your iterator can only source values from ptr, an owned value with no lifetime-linkage to 'a, the compiler will complain about mismatched lifetimes at one point or another.

In order to do this, your iterator would have to use something bound to 'a, probably some form of Option<Ref<'a, _>>.

---

However, another limitation is when you have nested RefCells, with each level that you iterate, you need to keep around an additional Ref. The reason being that borrows from a Ref don't keep the lifetime of the RefCell, but from the Ref itself.

let refc = RefCell::new(RefCell::new(RefCell::new(42)));
let ref1 = refc.borrow(); // these all need
let ref2 = ref1.borrow(); // to be preserved
let ref3 = ref2.borrow(); // to access `v`
let v = &*ref3;

So if you try to keep only one Ref chained from another, its going to encounter a "returns a value referencing data owned by the current function" error in one form or another. If you instead try to keep all those Refs within the iterator, well then it creates a self-referential struct. Not nice.

You can only get out of this issue by cloning the Rcs at each level (which you've already done) to to get an owned value and escape the lifetime of the previous Ref.

---

So you cannot return a reference type for your iterator. Your only option is to return an owned value, which in this case wouldn't be ideal since it'd either have to be a cloned Entry, or an Rc<RefCell<SkipNode<K, V>>>, or a wrapper around an Rc that exposes the Entry properly.

Here's a working version. The EntryRef wrapper I added could probably be better but it works and demonstrates the point.

pub struct EntryRef<K, V> {
    ptr: Rc<RefCell<SkipNode<K, V>>>,
}

impl<K, V> EntryRef<K, V> {
    pub fn get_entry(&self) -> Ref<'_, Entry<K, V>> {
        Ref::map(self.ptr.borrow(), |node| node.entry.as_ref().unwrap())
    }
}

pub struct Iter<K: Ord, V> {
    ptr: Option<Rc<RefCell<SkipNode<K, V>>>>,
}

impl<K, V> Iterator for Iter<K, V>
where
    K: Ord,
{
    type Item = EntryRef<K, V>;

    fn next(&mut self) -> Option<Self::Item> {
        self.ptr.take().map(|node| {
            self.ptr = node.borrow().next_by_height[0]
                .as_ref()
                .map(|ref node| Rc::clone(node));
            EntryRef { ptr: node }
        })
    }
}

See also:

• How do I write an iterator that returns references to itself?
• Why can't I store a value and a reference to that value in the same struct?
• Borrowed RefCell does not last long enough when iterating over a list