IterMut::next lifetime relation to iterated data

help
1

This toy example (whose purpose is to be minimal while still demonstrating the
relevant error, rather than doing anything meaningful at runtime)

struct Forever<T>(T);

impl<T> Forever<T> {
    fn iter_mut<'data>(&'data mut self) -> IterMut<'data, T> {
        IterMut(self)
    }
}

struct IterMut<'data, T>(&'data mut Forever<T>);

impl<'data, T> Iterator for IterMut<'data, T> {
    type Item = &'data mut T;
    fn next<'next>(&'next mut self) -> Option<Self::Item> {
        Some(&mut self.0.0)
    }
}

playground

generates the error

11 | impl<'data, T> Iterator for IterMut<'data, T> {
   |      ----- lifetime `'data` defined here
12 |     type Item = &'data mut T;
13 |     fn next<'next>(&'next mut self) -> Option<Self::Item> {
   |             ----- lifetime `'next` defined here
14 |         Some(&mut self.0.0)
   |         ^^^^^^^^^^^^^^^^^^^ associated function was supposed to return data with lifetime `'data` but it is returning data with lifetime `'next`
   |
   = help: consider adding the following bound: `'next: 'data`

There is no relationship between the lifetime of the ref returned by next()
('next) and the lifetime of the ref holding the data in the iterator itself
('data). We need a guarantee that 'next outlives 'data, which is why the
compiler helpfully suggests

help: consider adding the following bound: `'next: 'data`

Where can this bound be specified?

The only place I can think of, leads to the error

lifetime parameters or bounds on method `next` do not match the trait declaration
  --> src/bin/wtf.rs:16:12
   |
16 |     fn next<'next: 'data>(&'next mut self) -> Option<Self::Item> {
   |            ^^^^^^^^^^^^^^ lifetimes do not match method in trait
2

This isn't possible in general, without knowing the specifics of the inner type. In the typical case of mutable slices, you can do this by splitting borrows and clever use of mem::replace(), but the general scheme as you outlined isn't possible, exactly because the lifetimes need to be independent.

Consider for example, what would happen if you were to collect this iterator. Then you would generate multiple mutable borrows into the same value -> instant undefined behavior.

1 Like
3

Ignore the borrow checking for the moment and think about this code:

let f: Forever<i32> = Forever(1);
let i: IterMut<'_, i32> = f.iter_mut();
let a: &mut i32 = i.next();
let b: &mut i32 = i.next();

a and b are now two mutable references to the same data, which is undefined behavior. So, the borrow checker must reject this program, one way or another.

The definition of the Iterator trait is such that an implementor cannot return data which borrows from the iterator itself; this is expressed by the lack of relationship between the next's self lifetime and the trait as a whole.

(An alternative definition, a “lending iterator” could allow this borrowing — at the price of not being able to collect() the iterator's results.)

In practice, iter_mut() iterators are implemented using unsafe code, and that unsafe code must make sure (without any help from the borrow checker) that it never returns the same mutable reference twice, as your code currently does.

2 Likes
4

... sigh, that's the danger of minimal examples. So imagine that there is some extra code in there, which ensures that .next() yields Some only once. No multiple borrows into the same value, yet you get exactly the same error.

I guess that's what

lifetime parameters or bounds on method next do not match the trait declaration

means? But I don't see how it mismatches the trait declaration.

5

It doesn't change anything. The compiler cannot, in general, prove that you "ensured" that. That's why mutable iterators are mostly implemented using unsafe (or by wrapping other, already-implemented mutable iterators).

No.

The fully desugared trait declaration is

trait Iterator {
    type Item; // not 'data
    
    fn next<'self /* not 'data */>(&'self mut self) -> Self::Item /* still neither 'data nor 'self */;
}

From this, two things are apparent:

  1. The independence of self and Item. (This is what I was explaining above.)
  2. The fact that in the trait declaration, the implicitly introduced lifetime isn't constrained by anything. (This is what the compiler error is telling you.)
6

So it's a bit unfortunate that the compiler suggests that you establish such a relationship.

How does this lack of relationship prevent you from establishing one externally?

OK, this version

struct Forever<T>(T);

impl<T> Forever<T> {
    fn iter_mut<'d>(&'d mut self) -> IterMut<'d, T> {
        IterMut { data: self, done: false }
    }
}

struct IterMut<'d, T>{ data: &'d mut Forever<T>, done: bool }

impl<'d, T> Iterator for IterMut<'d, T> {
    type Item = &'d mut T;
    fn next<'next>(&'next mut self) -> Option<Self::Item> {
        if self.done { return None }
        self.done = true;
        Some(&mut self.data.0)
    }
}
  • contains no unsafe code
  • never returns the same mutable reference twice
  • and yet ... it gives exactly the same error as before.

But I guess that's the point: the compiler cannot tell the difference between this version and the previous one.

7

It causes the function signature not to match that in the trait declaration, as you observed.

Yes. How could it? Lifetime analysis is purely static, and type checking happens one function at a time. So, for all the compiler knows, someone else (e.g. another method on Self) could reset the done flag to false after every call. The kind of analysis required for disproving this would be very hard and slow (impractically so), or downright impossible (google "halting problem"), and it would also make the code extremely brittle and vulnerable to action at a distance, so it's intentionally not done to any extent, even though it would technically be possible in very, very limited cases.

8

Right, what I'm not getting is why this appears to have the corollary that no external constraints are allowed to be imposed. I see that the trait doesn't require it, but I don't see the mechanism by which it forbids it.

9

You can't put stronger constraints on a trait impl than the declaration implies. Just think about it, it doesn't make any sense: if a user were trying to call the trait impl for this particular type with the more relaxed constraints, then compiler would allow it based on the trait declaration, but the constraints wouldn't actually be met due to the impl. That would cause the code to be incorrect or even unsound.

Consider an analogy. Say you apply to NASA for being an astronaut. This requires passing a medical examination. The managers at NASA trust that the doctor knows what s/he is doing, and so they assume you will be tested for nausea in 0G, for example. Consequently, anyone who passes the medical examination will be allowed to go to space.

Now this is all and well, but what if the doctor doesn't check you for nausea in 0G? You pass the examination, you go to space, and then you start vomiting because you weren't tested for it on Earth.

In the analogy above, the doctor is the compiler, the assumption of being able to bear 0G without becoming nauseous is the trait bound in the trait impl, and the medical check for nausea is the constraint in the trait declaration. If the medical check and the assumption match, then all is well. But if the medical check is less strict than your actual/assumed ability of bearing 0G, then problems (and your lunch) arise.

1 Like
10

Another way to look at it: the only kind of additional constraint you can put on a trait is whether the type implements the trait (bounds on an impl Trait for Type as a whole).

If you could add more constraints to a single function of the trait, then the trait would be sort of “half-implemented” — and thus would have to be ineligible for passing to generic functions that demand a “fully implemented” trait.

1 Like
11

It's true that the compiler can't prove everything and that would apply to this code never handing out more than one reference...

...but there's another problem here, which is that the lifetimes are still independent and you can't get a &'d mut T out of a &'next mut &'d mut T (or &'next mut IterMut<'d, T>) without replacing the &'d mut T. That's what the borrow error is trying to say.

This works though.

But again, you may actually want a lending iterator (and there isn't such a trait in std yet).

trait LendingIterator {
    type Item<'i> where Self: 'i;
    fn next(&mut self) -> Option<Self::Item<'i>>;
}
12

Hmm, unfortunately this analogy is only causing me to juggle even more mappings in my already overloaded head. But let's try ...

The trait imposes no lifetime constraint on Item. This means that the medical exam does not check that my International Space Authority permit-to-work-in-space runs for more than a year. Consequently, NASA cannot send me to the ISS for 6 months, even if I show my 2 year permit to anyone who will listen. NASA only listened during the medical check and is deaf to all other incoming information.

Is that it?

Edit: and

lifetime parameters or bounds on method `next` do not match the trait declaration

is the equivalent of NASA not letting me into the medical exam if I'm carrying my permit, on the grounds of it being inadmissible evidence?

13

If we continue the analogy with lifetimes, then the equivalent would be that you can't go to the ISS for 2 years ('data in the trait impl) if your permit only allows 1 year (the implicit, temporary lifetime decorating &mut self in the trait declaration).

14

Sorry for jumping into a discussion without reading everything, so this might be something you know and/or besides the point:

The way to teach the compiler about a "done" flag for a single value that prevents any further access is to use an Option. Replace both fields with a single Option<&'d mut Forever<T>> and you can make the code compile using the Option::take method.

Edit: Ah, @quinedot already pointed this out.

15

I'm trying to understand why/how the compiler is not allowing me to say "we're only considering people whose permit lasts longer than the mission", which is what I tried to do with fn next<'next: 'data>(...).

This seems to be the minimal example needed to generate the error, with elided lifetimes added in:

trait    Foo            { fn meth<'m    >(&'m self);            }
impl<'i> Foo for &'i () { fn meth<'m: 'i>(&'m self) { todo!() } }

It seems that the error is saying

You are not allowed to put any bounds on lifetime 'm in the implementation because it has no bounds in the trait declaration.

(Which doesn't address why it is not allowed.)

My problem was that I was confusing it for putting bounds

impl<'a: RIGHT_HERE> Trait for ...

which is something completely different.

16

Yes, thanks, I know about how to use Option for this. This is very much not about that.

No worries: it's generally-useful information, concisely presented. Someone else might benefit in the future, even if it's not me right now.

17

Exactly, but I addressed just that. Maybe the analogy didn't help. Here's a code example. Let's substitute 'i with 'static, because it can be chosen by the caller to be arbitrarily long (or short). Let's also remove the same lifetime from the implemeting type for simplicity. Thus, your example is essentially

trait Foo {
    fn meth<'m>(&'m self);
}
impl Foo for () {
    fn meth<'m: 'static>(&'m self) {
        todo!()
    }
}

which is just a long-winded way of writing

trait Foo {
    fn meth<'m>(&'m self);
}
impl Foo for () {
    fn meth(&'static self) {
        thing_that_requires_static(self);
    }
}

And if you call it with something that doesn't live for 'static:

fn main() {
    let local = ();
    let not_static_ref = &local;
    not_static_ref.meth(); // BOOM! UB.
}
1 Like
18

... and we are [1] allowed to invoke .meth() on a non-'static because the compiler trusts the interface declared in the trait, which (contrary to the impl) does not require 'static.

The declared interface has weaker bounds than the implementation. BOOM.

Crystal clear. Thanks.

  1. would be, if the impl got past the compiler ↩︎

19

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.