This is a usual "surprise" that happens when dealing with Mut iterators: many people have the mental model of Iterator::next() having the following signature:
trait StreamingIteratorGAT {
type Item<'next>;
fn next<'next> (self: &'next mut Self) -> Self::Item<'next>;
}
-
(this is currently an experimental syntax, but one can write an equivalent using:
trait StreamingIterator<'next> : 'next {
type Item;
fn next (self: &'next mut Self) -> Self::Item;
}
The difference with the classic:
trait Iterator {
type Item;
fn next<'next> (self: &'next mut Self) -> Self::Item;
}
may be hard to spot, but is actually quite crucial: it all relies on whether the yielded Items can depend on 'next, the lifetime of the &mut borrow of the iterator used for the .next() call.
This semantic difference is easier to understand by viewing exclusive borrows (&mut) as a compile-time Mutex::lock():
-
to call .next(), since it takes a &mut Self, receiver, we need to hold a .lock() during that .next() call at least. I've even given a name to that "duration" for which the lock is held: 'next.
-
In the classic Iterator trait, the type Item cannot depend on / know about 'next, since the type is defined before that "duration parameter" is ever introduced. This means that the following is a valid "sequence of actions":
-
obtain an exclusive lock on the iterator;
-
while the lock is held, call .next() and obtain a yielded Item.
-
release the exclusive lock.
-
keep using that Item even if the lock has been released (e.g., you can append it to some Vec; and rince and repeat these steps: once the iterator is exhausted, you will have .collect()ed all its items within that Vec).
In other terms, with the classic Iterator trait, the obtained items can escape the scope of the for loop block.
-
That's the main difference with the StreamingIteratorGAT and for<'next> StreamingIterator<'next> traits.
In both those patterns, the type Item is allowed to depend on 'next, which means the actual type may be infected with that lifetime, which in that case means that the obtained Item can only be used while the lock is held: the moment the lock is released, it's invalid to keep using the Item:
-
obtain an exclusive lock on the iterator;
-
while the lock is held, call .next() and obtain a yielded Item<'next>.
-
release the exclusive lock. _This ends 'next, and thus, allows the yielded Item<'next> to dangle.
-
That Item is thus unusable (e.g., if you want to call .next() a second time, since that requires that the lock for the next call have been released (otherwise it "would deadlock" / lead to a Rust complaining about attempting to obtain a &mut borrow while another one is held), it means that the moment you obtain the second item, the first item is unusable: you can only have access at one item at a time).
As you can see, the StreamingIterator API is far more limiting from a user-of-the-trait / user-of-the-iterator perspective, but that also means it is easier to implement / less restrictive for a an implementor-of-the-trait / producer-of-the-iterator.
Going back to your concrete example (which I will simplify to using a single lifetime for AppendIter):
pub struct AppendIter<'iter, T> {
target: &'iter mut Vec<T>,
source: &'iter [T],
cap: usize,
pos: usize,
}
impl<'iter, T: Clone> Iterator for AppendIter<'iter, T> {
type Item = &'iter [T];
// Tip: do not use `&self` /`&mut self` sugar if you are confused about
// lifetimes: force yourself to spelling out the full type signature.
fn next<'next> (self: &'next mut AppendIter<'iter, T>)
-> Option<&'iter [T]>
// ^^^^^^
// returned item must be borrowed as long as `'iter`.
{
…
// can only be borrowed for `'next`.
// vvvv
return Some(&self.target[..]);
}
}
So, as you can see, your implementation is making you return a &self.target… which is thus infected with the 'next lifetime (&'next &'iter mut Vec<T>; as @alice mentioned, Rust can "flatten" the borrows for you by using the shorter one: &'next Vec<T> and finally, &'next [T]).
And yet you have to return something with the 'iter lifetime because you are using the classic Iterator trait, which requires your yielded items to be allowed to coexist with each other and with other .next() calls (that's what returning &'iter [T] instead of &'next [T] implies).
And Rust has a problem with the latter point: during a follow-up .next() call, you may very well mutate the Vec, and even cause a reallocation: that would invalidate previous borrows / pointers to the backing heap-allocated buffer, so some implementations could cause dangling pointers. The fact that your implementation may not cause them because it checks for capacity etc. is ignored by Rust, since:
-
type / function signatures are implementation-agnostic (so that if you were to change the implementation later on, you can't cause compile-time breakage on code that depended on it).
-
you haven't "lied" / cheated in the type signature by telling Rust to trust your implementation above all other things, by using unsafe (and in case this is isn't clear: one should refrain from using unsafe to circumvent lifetime problems they don't understand; lifetimes and their compile-time errors are there to prevent bugs, and in this instance, it is very very easy to feature an incorrect / unsound / buggy API if you still try to yield &'iter [T] slices instead of &'next [T] slices).
So I'd advise for trying to implement the StreamingIterator API, although, for starters, let's get rid of the complex trait signature and generalization: these kind of traits with "associated types depending on lifetimes" are annoying and hard to write at best, and at worst the compiler bugs with them leading to false positives (compiler refusing to compile correct code) or even compiler crashes.
But without any trait abstraction, the signature is quite simple:
- impl<'iter, T: Clone> Iterator for AppendIter<'iter, T> {
+ impl<'iter, T: Clone> AppendIter<'iter, T> {
- type Item = &'next [T];
fn next<'next> (self: &'next mut AppendIter<'iter, T>)
- -> Option<&'iter [T]>
+ -> Option<&'next [T]>
{ … } // your implementation here
}
And you'll be able to use this smarter iterator by doing stuff like:
while let Some(item) = append_iter.next() {
…
} // <- `item` cannot be used outside this scope (that's the difference with classic `Iterator::next()`)
so, by the time we go back to another iteration of the loop and another call to .next(), Rust guarantees us that item will never be used again, so we are free to mutate the Vec and cause reallocations, without any dereferences of the dangling pointers ever happening.