Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Returning iterator of a Vec in a RefCell

Given the following struct and impl:

use std::slice::Iter;
use std::cell::RefCell;

struct Foo {
    bar: RefCell<Vec<u32>>,
}

impl Foo {
    pub fn iter(&self) -> Iter<u32> {
        self.bar.borrow().iter()
    }
}

fn main() {}

I get an error message about a lifetime issue:

error: borrowed value does not live long enough
  --> src/main.rs:9:9
   |
9  |         self.bar.borrow().iter()
   |         ^^^^^^^^^^^^^^^^^ does not live long enough
10 |     }
   |     - temporary value only lives until here
   |
note: borrowed value must be valid for the anonymous lifetime #1 defined on the body at 8:36...
  --> src/main.rs:8:37
   |
8  |       pub fn iter(&self) -> Iter<u32> {
   |  _____________________________________^ starting here...
9  | |         self.bar.borrow().iter()
10 | |     }
   | |_____^ ...ending here

How am I able to return and use bars iterator?

like image 698
NobbZ Avatar asked Nov 05 '15 09:11

NobbZ


Video Answer


3 Answers

Alternate Solution

Here is an alternate solution that uses interior mutability as it was intended. Instead of creating an iterator for &T values, we should create an iterator for Ref<T> values, which deference automatically.

struct Iter<'a, T> {
    inner: Option<Ref<'a, [T]>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = Ref<'a, T>;

    fn next(&mut self) -> Option<Self::Item> {
        match self.inner.take() {
            Some(borrow) => match *borrow {
                [] => None,
                [_, ..] => {
                    let (head, tail) = Ref::map_split(borrow, |slice| {
                        (&slice[0], &slice[1..])
                    });
                    self.inner.replace(tail);
                    Some(head)
                }
            },
            None => None,
        }
    }
}

Playground

Explanation

The accepted answer has a few significant drawbacks that may confuse those new to Rust. I will explain how, in my personal experience, the accepted answer might actually be harmful to a beginner, and why I believe this alternative uses interior mutability and iterators as they were intended.

As the previous answer importantly highlights, using RefCell creates a divergent type hierarchy that isolates mutable and immutable access to a shared value, but you do not have to worry about lifetimes to solve the iteration problem:

  RefCell<T>       .borrow()  ->     Ref<T>      .deref()  ->       &T
  RefCell<T>   .borrow_mut()  ->  RefMut<T>  .deref_mut()  ->   &mut T

The key to solving this without lifetimes is the Ref::map method, which is critically missed in the book. Ref::map "makes a new reference to a component of the borrowed data", or in other words converts a Ref<T> of the outer type to a Ref<U> of some inner value:

Ref::map(Ref<T>, ...)  ->  Ref<U>

Ref::map and its counterpart RefMut::map are the real stars of the interior mutability pattern, not borrow() and borrow_mut().

Why? Because unlike borrow() and borrow_mut(), Ref::mut and RefMut::map, allow you to create references to interior values that can be "returned".

Consider adding a first() method to the Foo struct described in the question:

fn first(&self) -> &u32 {
      &self.bar.borrow()[0]
}

Nope, .borrow() makes a temporary Ref that only lives until the method returns:

error[E0515]: cannot return value referencing temporary value
 --> src/main.rs:9:11
  |
9 |           &self.bar.borrow()[0]
  |           ^-----------------^^^
  |           ||
  |           |temporary value created here
  |           returns a value referencing data owned by the current function

error: aborting due to previous error; 1 warning emitted

We can make it more obvious what is happening if we break it up and make the implicit deference explicit:

fn first(&self) -> &u32 {
    let borrow: Ref<_> = self.bar.borrow();
    let bar: &Vec<u32> = borrow.deref();
    &bar[0]
}

Now we can see that .borrow() creates a Ref<T> that is owned by the method's scope, and isn't returned and therefore dropped even before the reference it provided can be used. So, what we really need is to return an owned type instead of a reference. We want to return a Ref<T>, as it implements Deref for us!

Ref::map will help us do just that for component (internal) values:

fn first(&self) -> Ref<u32> {
    Ref::map(self.bar.borrow(), |bar| &bar[0])
}

Of course, the .deref() will still happen automatically, and Ref<u32> will be mostly be referentially transparent as &u32.

Gotcha. One easy mistake to make when using Ref::map is to try to create an owned value in the closure, which is not possible as when we tried to use borrow(). Consider the type signature of the second parameter, the function: FnOnce(&T) -> &U,. It returns a reference, not an owned type!

This is why we use a slice in the answer &v[..] instead of trying to use the vector's .iter() method, which returns an owned std::slice::Iter<'a, T>. Slices are a reference type.

Additional Thoughts

Alright, so now I will attempt to justify why this solution is better than the accepted answer.

First, the use of IntoIterator is inconsistent with the Rust standard library, and arguably the purpose and intent of the trait. The trait method consumes self: fn into_iter(self) -> ....

let v = vec![1,2,3,4];
let i = v.into_iter();
// v is no longer valid, it was moved into the iterator

Using IntoIterator indirectly for a wrapper is inconsistent as you consume the wrapper and not the collection. In my experience, beginners will benefit from sticking with the conventions. We should use a regular Iterator.

Next, the IntoIterator trait is implemented for the reference &VecRefWrapper and not the owned type VecRefWrapper.

Suppose you are implementing a library. The consumers of your API will have to seemingly arbitrarily decorate owned values with reference operators, as is demonstrated in the example on the playground:

for &i in &foo.iter() {
    println!("{}", i);
}

This is a subtle and confusing distinction if you are new to Rust. Why do we have to take a reference to the value when it is anonymously owned by - and should only exist for - the scope of the loop?

Finally, the solution above shows how it is possible to drill all they way into your data with interior mutability, and makes the path forward for implementing a mutable iterator clear as well. Use RefMut.

like image 61
kwarrick Avatar answered Oct 19 '22 06:10

kwarrick


You cannot do this because it would allow you to circumvent runtime checks for uniqueness violations.

RefCell provides you a way to "defer" mutability exclusiveness checks to runtime, in exchange allowing mutation of the data it holds inside through shared references. This is done using RAII guards: you can obtain a guard object using a shared reference to RefCell, and then access the data inside RefCell using this guard object:

&'a RefCell<T>        -> Ref<'a, T> (with borrow) or RefMut<'a, T> (with borrow_mut)
&'b Ref<'a, T>        -> &'b T
&'b mut RefMut<'a, T> -> &'b mut T

The key point here is that 'b is different from 'a, which allows one to obtain &mut T references without having a &mut reference to the RefCell. However, these references will be linked to the guard instead and can't live longer than the guard. This is done intentionally: Ref and RefMut destructors toggle various flags inside their RefCell to force mutability checks and to force borrow() and borrow_mut() panic if these checks fail.

The simplest thing you can do is to return a wrapper around Ref, a reference to which would implement IntoIterator:

use std::cell::Ref;

struct VecRefWrapper<'a, T: 'a> {
    r: Ref<'a, Vec<T>>
}

impl<'a, 'b: 'a, T: 'a> IntoIterator for &'b VecRefWrapper<'a, T> {
    type IntoIter = Iter<'a, T>;
    type Item = &'a T;

    fn into_iter(self) -> Iter<'a, T> {
        self.r.iter()
    }
}

(try it on playground)

You can't implement IntoIterator for VecRefWrapper directly because then the internal Ref will be consumed by into_iter(), giving you essentially the same situation you're in now.

like image 28
Vladimir Matveev Avatar answered Oct 19 '22 06:10

Vladimir Matveev


From my research there is currently no solution to this problem. The biggest problem here is self-referentiality and the fact that rust cannot prove your code to be safe. Or at least not in the generic fashion.

I think it's safe to assume that crates like ouroboros, self-cell and owning_ref are solution if you know that your struct (T in Ref<T>) does not contain any smart pointers nor anything which could invalidate any pointers you might obtain in your "dependent" struct.

Note that self-cell does this safely with extra heap allocation which might be ok in some cases.

There was also RFC for adding map_value to Ref<T> but as you can see, there is always some way to invalidate pointers in general (which does not mean your specific case is wrong it's just that it probably will never be added to the core library/language because it cannot be guaranteed for any T)

Yeah, so no answer, sorry. impl IntoIterator for &T works but I think it's rather hack and it forces you to write for x in &iter instead of for x in iter

like image 1
Kamil Tomšík Avatar answered Oct 19 '22 05:10

Kamil Tomšík