Sound way to make &mut reborrow in Iterator work?

help
#1

This code here (A) works:

struct Object {
    x: u8
}

struct Iter<'a> {
    link: &'a Object
}

impl<'a> Iterator for Iter<'a> {
    type Item = u8;

    fn next(&mut self) -> Option<Self::Item> {
        let _: &'a Object = self.link;

        None
    }
}

(Playground)

However, changing link to become a mutable reference like so (B):

struct Iter<'a> {
    link: &'a mut Object
}

gives a compiler error:

error[E0312]: lifetime of reference outlives lifetime of borrowed content...
  --> src\lib.rs:14:29
   |
14 |         let _: &'a Object = self.link;
   |                             ^^^^^^^^^
   |
note: ...the reference is valid for the lifetime `'a` as defined here...
  --> src\lib.rs:10:6
   |
10 | impl<'a> Iterator for Iter<'a> {
   |      ^^
note: ...but the borrowed content is only valid for the anonymous lifetime defined here
  --> src\lib.rs:13:13
   |
13 |     fn next(&mut self) -> Option<Self::Item> {
   |             ^^^^^^^^^

(Playground)

If I understand things correctly, this is because in (A) the let _ ... line just creates another copy of the reference and is able to preserve 'a, while in (B) it has to do a reborrow with the anonymous next lifetime '1 of self, which prevents the let assignment from happening.

Three questions:

  • Is my understanding so far correct?
  • If I transmuted that lifetime would that be sound? I'd argue it should be, since link guarantees the pointer as exactly the lifetime I'm asking for, and self isn't being used anymore. Admittedly my real example is more complex, but even then, if I stopped using self after obtaining the link there should be no aliasing happening and lifetimes should be correct, right?
  • Is there a way to fix (B) without unsafe code?
#2

Obtaining &'a T from &'b mut &'a mut T (where 'b is actually shorter than 'a) is not possible… (unless you have some replacement &'a mut T and are willing to modify the target of the &'a mut T behind the &'b mut &'a mut T to take on the replacement value; via std::mem::replace).

It’s also generally not sound to use unsafe code to circumvent this limitation. Otherwise, you could, borrow a &'a mut T for a short lifetime 'b; them obtain a long-lived &'a T from that, and after the borrow with lifetime 'b ends, you’d have two references, one of them mutable, to the same target at your disposal. (This is never allowed in Rust, as live mutable references need to be exclusive.)

In (B), since Iter<'a> is essentially a &'a mut Object, the &mut next is essentially a &'b mut &'a mut Object and you’re asking about obtaining an &'a Object from it.

What you can get is a &'b Object (or in general a &'b T from &'b mut &'a mut T, or even from &'b &'a mut T).

struct Iter<'a> {
    link: &'a mut Object
}
impl<'a> Iterator for Iter<'a> {
    type Item = u8;

    fn next<'b>(&'b mut self) -> Option<Self::Item> {
        let _: &'b Object = self.link;

        None
    }
}

It’s usually not immediately undefined behavior to create a reference with the wrong lifetime, but depending on how you use it, it’s very, very easy to build an unsound API that can be used to cause undefined behavior. I.e. if you do nothing with your &'a Object, nothing bad will happen, but your use-case, whatever it may be, probably does include some reason why &'b Object isn’t enough, and that reason will likely also turns into a soundness issue when you circumvent the borrow checker.

I don’t fully understand what you’re saying about “I stop using self after obtaining the link”, and whether or not it includes usage outside of the call to next. If it does, i.e. you never want to call next a second time, then perhaps you can use some Option<&'a mut Object> field, and Option::take in order to get the reference with its full lifetime.

1 Like
#3

Thanks a bunch, I'll have to change something then.

I don’t fully understand what you’re saying about “I stop using self after obtaining the link”, and whether or not it includes usage outside of the call to next.

My thinking was if between _ and the return of the method I don't touch self anymore it counts as non-aliasing, and furthermore, since I returned .....

ah ... now I get it ...

I was about to write "since I returned something of lifetime 'a I'd also lock / prevent next from being called a 2nd time", but of course that would only work if I returned a &'a mut ...

Edit, hang on I'm confused. Wouldn't I be unable to do anything bad with Iter while I have a reference because one next returns I couod not call it again for as long as I hold on to the referenfe?

#4

That's how lending iterators work, which have a signature something like

fn next(&mut self) -> Option<& /* mut */ Item>;
// alternatively spelled
fn next<'a>(&'a mut self) -> Option<&'a /* mut */ Item>;

// Or more accurately, with Generic Associated Types (GATs)
type Item<'a> where Self: 'a;
fn next(&mut self) -> Option<Self::Item<'_>>;

Note how the borrow of self used to call next is connected to the returned value. That prevents you from calling next until after the scope of the returned value (as the iterator remains exclusively borrowed so long as you have the returned value).

But that's not how the Iterator trait works, instead the signature is

type Item; // A single type -- note &'a Foo is not the same type as &'b Foo
fn next(&mut self) -> Option<Self::Item>;

That is, the lifetimes returned by next (if any) are the same every time you call it, and they aren't related to the borrow of self you use to call next. Note that you can .collect() on an Iterator -- any Iterator -- and this means that you can hold all of the returned values at the same time, and that they have the same type (including lifetimes).

Incidentally, manipulating lifetimes with unsafe doesn't change the semantics of the trait or methods more generally, etc. I.e. the compiler isn't going to see you lengthening a lifetime and go "oh okay, so this is a lending iterator now" or anything like that. The method signature for Iterator::next says that the borrow of self is unrelated to the item returned, and that's the behavior that the compiler assumes (and enforces in safe code).

Lifetimes more generally are the result of a static analysis, not some property values carry around which you can manipulate.

1 Like