Implement an Iterator on Ref<'a, Vec<T>>?

Is it possible to implement an Iterator on

Ref<'a, Vec<T>>

where the iterator returns

Some(&'a T)

?

Because of Deref coercions, calling .iter() on the Ref should already work.

If you're creating your own Iterator, the Ref needs to live elsewhere so the Item can borrow from it. The simplest way is to have the iterator hold a borrowed &'a Vec<T> or &'a [T].

The solutions proposed so far don't actually return references with the lifetime 'a, but instead they are borrows of the Ref itself. Now, actually returning references with the lifetime 'a is not possible because it would allow them to outlive the Ref, but you can make an iterator of Ref<'a, T>. One such implementation would be the following:

struct RefIter<'a, T: 'a> {
    inner: Ref<'a, [T]>,
}
impl<'a, T: 'a> Iterator for RefIter<'a, T> {
    type Item = Ref<'a, T>;
    fn next(&mut self) -> Option<Ref<'a, T>> {
        if self.inner.len() == 0 { return None; }
        let item = Ref::map(Ref::clone(&self.inner), |inner| &inner[0]);
        self.inner = Ref::map(Ref::clone(&self.inner), |inner| &inner[1..]);
        Some(item)
    }
}
impl<'a, T: 'a> RefIter<'a, T> {
    pub fn new<V: Borrow<[T]>>(slice: Ref<'a, V>) -> Self {
        RefIter {
            inner: Ref::map(slice, |v| v.borrow())
        }
    }
}

playground

4 Likes

oh right, I missed the fact that the question is about the lifetimes.

@alice : Thanks! This looks like the solution I wanted to ask for (but couldn't properly formulate the question.)

Can you please explain detail why we have
type Item = Ref<'a, T> but can't have type Item = &'a T ?

Compiler errors I have been getting clearly agree with you, but I still don't understand why.

The lifetime 'a refers to the lifetime of the RefCell, so if you were able to get a &'a T from a Ref<'a, T>, then you could do the following,

let ref_cell = RefCell::new(0);

let ref_: Ref<'a, _> = ref_cell.borrow();
let shr_ref: &'a _ = ref_.into_ref();
drop(ref_);

assert_eq!(*shr_ref, 0);

let mut ref_mut: RefMut<'a, _> = ref_cell.borrow_mut();

*ref_mut = 10;

assert_eq!(*shr_ref, 10);

But this is undefined behavior, because you are aliasing an exclusive reference (from the ref_mut). Note: Ref::into_ref doesn't exist.

To prevent this, you instead borrow the Ref<'_, T>, and this will prevent the drop(ref_) in the code above. (and you will need to change the ref_.into_ref() to &*ref)..

2 Likes
  1. I can see how if ref_.into_ref() were to exist, the above code causes problem. In particular, we are doing a borrow_mut on a refcell, but we also have a & ref to it.

let ref_cell = RefCell::new(0);

let ref_: Ref<'a, _> = ref_cell.borrow();
let shr_ref: ??? = &*ref;
drop(ref_);

After we change the ref_.into_ref() to a &* ref_ ... what is the lifetime on shr_ref ?

It is bound to ref_ because of Deref

Basically in short, the RefCell must keep track of all borrows, and it is unable to keep track of a &'a T.

There's one more thing I don't understand:

In

1 let ref_cell = RefCell::new(0);

2 let ref_: Ref<'a, _> = ref_cell.borrow();
3 let shr_ref: ??? = &*ref;
4 drop(ref_);

the actual lifetime of ref_ is SHORER than 'a right? Namely, the actual lifetime of ref_ starts on line 2 and ends at line 4. So ref_ is a struct, which holds some refs with lifetime 'a, but ref_ itself has a much shorter lifetime. Is that correct?

Yes, this is again because 'a represents the lifetime of the RefCell, which must necessarily be longer than the lifetime of Ref<'a, _>

This is going to sound redundant, but given all the effort everyone has put into answering my questions, I just want to make sure I fully get this:

  1. We have a RefCell, with lifetime 'a

  2. This 'a can be divided into many non-overlapping parts, where each part is either (1) a single RefMut<'a, T> exists or (2) 0, 1, or more Ref<'a, T> exists

  3. The RefMut<'a, T> and Ref<'a, T>, when they exist, clearly have a life time that is a "subset" of 'a

  4. Therefore, any attempt to get a &'a T from Ref<'a, T> is silly because Ref<'a, T> itself lives for shorter than 'a

Are all four statements above correct?

2 Likes

Yes, this is correct

No, I don't think the fourth statement is correct. For example getting a Ref<'a, T> from another Ref<'a, T> is perfectly possible, and this other reference can outlive the original Ref<'a, T>:

fn main() {
    let cell = RefCell::new(1);
    
    let ref1: Ref<i32> = cell.borrow();
    
    let ref2: Ref<i32> = Ref::clone(&ref1);
    drop(ref1);
    
    // ref2 is still valid
    println!("{}", *ref2);
}

playground

Additionally if we insert elided lifetimes in the definition of RefCell::borrow we get

pub fn borrow<'a>(&'a self) -> Ref<'a, T>;

And if we define our own reference type with an analogous reference type we can turn the MyRef<'a, T> type into a &'a T:

struct MyContainer<T> {
    t: T
}
struct MyRef<'a, T> {
    r: &'a T,
}

impl<T> MyContainer<T> {
    pub fn new(t: T) -> Self {
        Self { t }
    }
    pub fn borrow<'a>(&'a self) -> MyRef<'a, T> {
        MyRef { r: &self.t }
    }
}
impl<'a, T> MyRef<'a, T> {
    pub fn as_ref(&self) -> &'a T {
        &self.r
    }
}

fn main() {
    let cont = MyContainer::new(10);
    
    let myref = cont.borrow();
    let r: &i32 = myref.as_ref();
    drop(myref);
    
    println!("{}", *r);
}

playground

The reason that you cannot get a &'a T from a Ref<'a, T> is that a &'a T would borrow from the RefCell, not from the Ref<'a, T>. This is okay in the sense that the data is stored in the RefCell, and the reference only remains valid for this lifetime, but the problem is that RefCell provides a RefCell::borrow_mut method, which also immutably borrows the RefCell, allowing you to create such a borrow while the previous borrow that created the &'a T still exists.

Normally a RefCell prevents you from actually creating a RefMut while a Ref exists by counting the number of Refs and panicing if there are any when you called borrow_mut. However this count is done by the destructor of the Ref, so the count would be invalid if the &'a T outlived the Ref<'a T>.

So the issue is that unsafe code inside RefCell assumes that no &'a T can be created. It's not that the reference would point to freed memory or any of such considerations.

2 Likes

Original Statement 4:

The statement I meant to make is:

For every x of type Ref<'a, T>, x lives shorter than 'a, and therefore we can not derive a &'a T from x.

If I understand your argument correctly, you seem to be arguing against an interpretation of the above statement by considering the union of the lifetimes of all Ref<'a, T>.

No, the issue is that had it not been for the unsafe code inside borrow_mut, it would have been perfectly fine to create a &'a T from a Ref<'a, T>, and I even posted an example with a simpler type that does allow creating a &'a T. It's just that some unsafe code inside borrow_mut assumes that you can't, so the api is designed to not allow it.

1 Like

I'm still trying to understand the statement you are proving. Is the following a correct interpretation:

It is possible construct a type MyRef<'a, T> such that we can have:

  • x has type MyRef<'a, T>
  • x has life type shorter than 'a
  • we can derive a &'a T from x

Is the above a correct interpretation of the point you are proving?

Assuming the above is correct, is the link back to the Ref<'a, T> question as follows:

Me: We can not construct a &'a T from a (x: Ref<'a, T>) because x has lifetime shorter than 'a

You: No, the reason we can not construct a &'a T from a (x: Ref<'a, T>) is due to the API design of Ref<'a, T>. Here is an example of a MyRef<'a, T> where you can have a (x: MyRef<'a, T>) with lifetime shorter than 'a, yet still derive a &'a T from x.

Is the above the clarification point you are making?

Yes.