How do you write a trait that returns an iterator?

Question

Broadly speaking my goal is this:

For some known type Bar...
Have a trait Foo with a function: get_iterator<T>() -> T where T: Iterator<Item = Bar>
The instance of the iterator borrows the original object Foo is implemented on.

I imagine it working like this:

let mut foo = Foo;
let bar = foo.get_iterator();

foo.mutable_call(); // <-- This fails, because foo is borrowed in bar

for x in bar { 
  ...
}

So, that's the goal, and here's my attempt, which I can't seem to get working:

struct ValsFromT<'a, T: 'a> {
  parent:&'a T,
  offset: usize,
}

struct Val;

trait HasValsIterator<T> {
  fn val_iterator(&self) -> T where T: Iterator<Item = Val>;
}

struct Foo;

impl<'a> Iterator for ValsFromT<'a, Foo> {
  type Item = Val;
  fn next(&mut self) -> Option<Val> {
    return None;
  }
}

impl<'a> HasValsIterator<ValsFromT<'a, Foo>> for Foo {
  fn val_iterator(&'a self) -> ValsFromT<'a, Foo> { 
    return ValsFromT {
      offset: 0usize,
      parent: self
    };
  }
}

fn takes_vals<T>(instance:T) where T: HasValsIterator<T> {
  // ...
}

#[test] 
fn test_foo() {
  let x = Foo;
  takes_vals(x);
}

(playpen: http://is.gd/wys3fx)

We're getting the dreaded concrete/bound lifetime error here, because of trying to return an iterator instance that references self from the trait function:

<anon>:22:3: 27:4 error: method `val_iterator` has an incompatible type for trait:
 expected bound lifetime parameter ,
    found concrete lifetime [E0053]
<anon>:22   fn val_iterator(&'a self) -> ValsFromT<'a, Foo> { 
<anon>:23     return ValsFromT {
<anon>:24       offset: 0usize,
<anon>:25       parent: self
<anon>:26     };
<anon>:27   }
<anon>:22:3: 27:4 help: see the detailed explanation for E0053

Is there some way of doing this?

@Veedrac oh, it was just semantics, not actually a problem with borrowing self. If you want to turn that into an answer, I'll accept it~ — Doug

Vladimir Matveev Vladimir Matveev · Accepted Answer · 2015-11-09T07:43:54

Unfortunately, Veedrac's suggestion doesn't work directly. You will get the following error if you'd try to use val_iterator() method on instance inside takes_vals():

<anon>:31:25: 31:39 error: the trait `core::iter::Iterator` is not implemented for the type `U` [E0277]
<anon>:31     let iter = instance.val_iterator();
                                  ^~~~~~~~~~~~~~
<anon>:31:25: 31:39 help: see the detailed explanation for E0277
<anon>:31:25: 31:39 note: `U` is not an iterator; maybe try calling `.iter()` or a similar method
error: aborting due to previous error
playpen: application terminated with error code 101

This (and some other further errors) requires changing the signature of the function to this one:

fn takes_vals<'a, T: 'a, U: Iterator<Item=Val>+'a>(instance: T) where T: HasValsIterator<'a, U>

However, even this doesn't work yet:

<anon>:31:16: 31:24 error: `instance` does not live long enough
<anon>:31     let iter = instance.val_iterator();
                         ^~~~~~~~
<anon>:30:97: 32:2 note: reference must be valid for the lifetime 'a as defined on the block at 30:96...
<anon>:30 fn takes_vals<'a, T: 'a, U: Iterator<Item=Val>+'a>(instance: T) where T: HasValsIterator<'a, U> {
<anon>:31     let iter = instance.val_iterator();
<anon>:32 }
<anon>:30:97: 32:2 note: ...but borrowed value is only valid for the scope of parameters for function at 30:96
<anon>:30 fn takes_vals<'a, T: 'a, U: Iterator<Item=Val>+'a>(instance: T) where T: HasValsIterator<'a, U> {
<anon>:31     let iter = instance.val_iterator();
<anon>:32 }

Remember that the trait requires that val_iterator() accepts the target by reference with lifetime 'a. This lifetime in this function is an input parameter. However, when val_iterator() is called on instance, the only lifetime which can be specified for the reference is the one of instance which is strictly smaller than any possible 'a as a parameter, because it is a local variable. Therefore, it is not possible to pass instance by value; you can only pass it by reference for lifetimes to match:

fn takes_vals<'a, T: 'a, U: Iterator<Item=Val>+'a>(instance: &'a T) where T: HasValsIterator<'a, U> {
    let iter = instance.val_iterator();
}

This works.

I'd like to add that using associated types instead of type parameters would be more correct semantically:

trait HasValsIterator<'a> {
    type Iter: Iterator<Item=Val> + 'a;
    fn val_iterator(&'a self) -> Self::Iter;
}

impl<'a> HasValsIterator<'a> for Foo {
    type Iter = ValsFromT<'a, Foo>;
    fn val_iterator(&'a self) -> ValsFromT<'a, Foo> { ... }
}

fn takes_vals<'a, T: 'a>(instance: &'a T) where T: HasValsIterator<'a> {
    ...
}

I say that this is more correct because the type of the iterator is determined by the implementor, that is, it is "output" type, which are modeled by associated types. As you can see, takes_vals() signature also shrank considerably.

Ideally, HasValsIterator trait should have been defined like this:

trait HasValsIterator {
    type Iter<'a>: Iterator<Item=Val> + 'a
    fn val_iterator<'a>(&'a self) -> Iter<'a>;
}

This way, val_iterator() would in any situation, including when HasValsIterator implementor is passed by value. However, Rust is not there yet.

How do you write a trait that returns an iterator?

1 Answers