The definition of Index is:
pub trait Index<Index: ?Sized> {
type Output: ?Sized;
/// The method for the indexing (`Foo[Bar]`) operation
fn index<'a>(&'a self, index: &Index) -> &'a Self::Output;
}
Specifically, index returns a reference to an element where the reference has the same lifetime as self. That is, it borrows self.
In your case, the self of the index call (which could be &self.items[idx] btw) is self.items, so the compiler sees that the return value has to be restricted to be borrowed from self.items, but items is owned by next's self, so a borrow from self.items is a borrow from self itself.
That is to say, the compiler can only guarantee the return value of index is valid for as long as self lives (and various concerns about mutation), so the lifetimes of &mut self and the returned &... have to be linked.
If one compiles it, to see the error, linking the references is what the compiler suggests:
<anon>:23:29: 23:40 error: cannot infer an appropriate lifetime for autoref due to conflicting requirements
<anon>:23 Some(self.items.index(&idx))
^~~~~~~~~~~
<anon>:17:5: 25:6 help: consider using an explicit lifetime parameter as shown: fn next(&'a mut self) -> Option<&'a <I as Index<uint>>::Output>
<anon>:17 fn next(&mut self) -> Option<&'a <I as Index<uint>>::Output> {
<anon>:18 if (self.current_idx >= self.len) {
<anon>:19 None
<anon>:20 } else {
<anon>:21 let idx = self.current_idx;
<anon>:22 self.current_idx += self.stride;
...
However, the suggested signature fn next(&'a mut self) -> Option<&'a <I as Index<uint>>::Output> is more restrictive than signature of the Iterator trait, and so is illegal. (Iterators with this arrangement of lifetimes may be useful, but they do not work with many common consumers, like .collect.)
The problem the compiler is protecting against is demonstrated by a type like:
struct IndexablePair<T> {
x: T, y: T
}
impl Index<uint> for IndexablePair<T> {
type Output = T;
fn index(&self, index: &uint) -> &T {
match *index {
0 => &self.x,
1 => &self.y,
_ => panic!("out of bounds")
}
}
}
This stores two Ts inline (e.g. straight on the stack) and allows for indexing them pair[0] and pair[1]. The index method returns a pointer straight into that memory (e.g. the stack), so if an IndexablePair value moves in memory, those pointers will become invalid, e.g. (assume Stride::new(items: I, len: uint, stride: uint)):
let pair = IndexablePair { x: "foo".to_string(), y: "bar".to_string() };
let mut stride = Stride::new(pair, 2, 1);
let value = stride.next();
// allocate some memory and move stride into, changing its address
let mut moved = box stride;
println!("value is {}", value);
That penultimate line is bad! It invalidates value because the stride, and it's field items (the pair) is moved in memory so the reference inside value is then pointing to moved data; which is highly unsafe and very bad.
The suggested lifetimes stop this problem (and several other problematic ones) by borrowing stride and disallowing the move, but, as we saw above we can't use that.
A technique to resole this is to separate the memory storing the elements from the iterator itself, that is, change the definition of Stride to:
pub struct Stride<'a, I: Index<uint> + 'a> {
items: &'a I,
len: uint,
current_idx: uint,
stride: uint,
}
(Adding a reference to items.)
The compiler then has the guarantee that the memory storing the elements is independent of the Stride value (that is, moving Stride around in memory won't invalidate the old elements) because there's a non-owning pointer separating them. This version compiles fine:
use std::ops::Index;
#[derive(Clone)]
pub struct Stride<'a, I: Index<uint> + 'a> {
items: &'a I,
len: uint,
current_idx: uint,
stride: uint,
}
impl<'a, I> Iterator for Stride<'a, I> where I: Index<uint> {
type Item = &'a <I as Index<uint>>::Output;
#[inline]
fn next(&mut self) -> Option<&'a <I as Index<uint>>::Output> {
if (self.current_idx >= self.len) {
None
} else {
let idx = self.current_idx;
self.current_idx += self.stride;
Some(self.items.index(&idx))
}
}
}
(Theoretically one could add a ?Sized bound in there, probably by manually implementing Clone instead of deriveing it, so that Stride can be used directly with a &[T], i.e. Stride::new(items: &I, ...) Stride::new(&[1, 2, 3], ...) would work, rather than having to have a double layer of Stride::new(&&[1, 2, 3], ...) as the default Sized bound requires.)
playpen
