How do I specify lifetime parameters in an associated type?

Question

I have this trait and simple structure:

use std::path::{Path, PathBuf};

trait Foo {
    type Item: AsRef<Path>;
    type Iter: Iterator<Item = Self::Item>;

    fn get(&self) -> Self::Iter;
}

struct Bar {
    v: Vec<PathBuf>,
}

I would like to implement the Foo trait for Bar:

impl Foo for Bar {
    type Item = PathBuf;
    type Iter = std::slice::Iter<PathBuf>;

    fn get(&self) -> Self::Iter {
        self.v.iter()
    }
}

However I'm getting this error:

error[E0106]: missing lifetime specifier
  --> src/main.rs:16:17
   |
16 |     type Iter = std::slice::Iter<PathBuf>;
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^ expected lifetime parameter

I found no way to specify lifetimes inside that associated type. In particular I want to express that the iterator cannot outlive the self lifetime.

How do I have to modify the Foo trait, or the Bar trait implementation, to make this work?

Rust playground

Solution 1

There are a two solutions to your problem. Let's start with the simplest one:

Add a lifetime to your trait

trait Foo<'a> {
    type Item: AsRef<Path>;
    type Iter: Iterator<Item = Self::Item>;
    
    fn get(&'a self) -> Self::Iter;
}

This requires you to annotate the lifetime everywhere you use the trait. When you implement the trait, you need to do a generic implementation:

impl<'a> Foo<'a> for Bar {
    type Item = &'a PathBuf;
    type Iter = std::slice::Iter<'a, PathBuf>;
    
    fn get(&'a self) -> Self::Iter {
        self.v.iter()
    }
}

When you require the trait for a generic argument, you also need to make sure that any references to your trait object have the same lifetime:

fn fooget<'a, T: Foo<'a>>(foo: &'a T) {}

Implement the trait for a reference to your type

Instead of implementing the trait for your type, implement it for a reference to your type. The trait never needs to know anything about lifetimes this way.

The trait function then must take its argument by value. In your case you will implement the trait for a reference:

trait Foo {
    type Item: AsRef<Path>;
    type Iter: Iterator<Item = Self::Item>;
    
    fn get(self) -> Self::Iter;
}

impl<'a> Foo for &'a Bar {
    type Item = &'a PathBuf;
    type Iter = std::slice::Iter<'a, PathBuf>;
    
    fn get(self) -> Self::Iter {
        self.v.iter()
    }
}

Your fooget function now simply becomes

fn fooget<T: Foo>(foo: T) {}

The problem with this is that the fooget function doesn't know T is in reality a &Bar. When you call the get function, you are actually moving out of the foo variable. You don't move out of the object, you just move the reference. If your fooget function tries to call get twice, the function won't compile.

If you want your fooget function to only accept arguments where the Foo trait is implemented for references, you need to explicitly state this bound:

fn fooget_twice<'a, T>(foo: &'a T)
where
    &'a T: Foo,
{}

The where clause makes sure that you only call this function for references where Foo was implemented for the reference instead of the type. It may also be implemented for both.

Technically, the compiler could automatically infer the lifetime in fooget_twice so you could write it as

fn fooget_twice<T>(foo: &T)
where
    &T: Foo,
{}

but it's not smart enough yet.

---

For more complicated cases, you can use a Rust feature which is not yet implemented: Generic Associated Types (GATs). Work for that is being tracked in issue 44265.

Solution 2

Use a wrapper type

If the trait and all its implementations are defined in one crate, a helper type can be useful:

trait Foo {
    fn get<'a>(&'a self) -> IterableFoo<'a, Self> {
        IterableFoo(self)
    }
}

struct IterableFoo<'a, T: ?Sized + Foo>(pub &'a T);

For a concrete type that implements Foo, implement the iterator conversion on the IterableFoo wrapping it:

impl Foo for Bar {}

impl<'a> IntoIterator for IterableFoo<'a, Bar> {
    type Item = &'a PathBuf;
    type IntoIter = std::slice::Iter<'a, PathBuf>;
    fn into_iter(self) -> Self::IntoIter {
        self.0.v.iter()
    }
}

This solution does not allow implementations in a different crate. Another disadvantage is that an IntoIterator bound cannot be encoded into the definition of the trait, so it will need to be specified as an additional (and higher-rank) bound for generic code that wants to iterate over the result of Foo::get:

fn use_foo_get<T>(foo: &T)
where
    T: Foo,
    for<'a> IterableFoo<'a, T>: IntoIterator,
    for<'a> <IterableFoo<'a, T> as IntoIterator>::Item: AsRef<Path>
{
    for p in foo.get() {
        println!("{}", p.as_ref().to_string_lossy());
    }
}

Associated type for an internal object providing desired functionality

The trait can define an associated type that gives access to a part of the object that, bound in a reference, provides the necessary access traits.

trait Foo {
    type Iterable: ?Sized;

    fn get(&self) -> &Self::Iterable;
}

This requires that any implementation type contains a part that can be so exposed:

impl Foo for Bar {
    type Iterable = [PathBuf];

    fn get(&self) -> &Self::Iterable {
        &self.v
    }
}

Put bounds on the reference to the associated type in generic code that uses the the result of get:

fn use_foo_get<'a, T>(foo: &'a T)
where
    T: Foo,
    &'a T::Iterable: IntoIterator,
    <&'a T::Iterable as IntoIterator>::Item: AsRef<Path>
{
    for p in foo.get() {
        println!("{}", p.as_ref().to_string_lossy());
    }
}

This solution permits implementations outside of the trait definition crate. The bound work at generic use sites is as annoying as with the previous solution. An implementing type may need an internal shell struct with the only purpose of providing the associated type, in case when the use-site bounds are not as readily satisfied as with Vec and IntoIterator in the example discussed.

Solution 3

In future, you'll want an associated type constructor for your lifetime 'a but Rust does not support that yet. See RFC 1598