Adding unrelated generic parameter triggers strange lifetime error

Question

I have a trait and I want to implement it for all types that implement std::ops::Index. This code works (as I would expect):

use std::ops::Index;
use std::fmt::Display;


trait Foo {
    fn foo(&self, i: usize) -> &Display;
}

impl<C> Foo for C 
where
    C: Index<usize>,
    C::Output: Display + Sized,
{
    fn foo(&self, i: usize) -> &Display {
        &self[i]
    }
}

(Playground)

However, once I introduce a generic parameter to my trait, I get a strange lifetime error. This is the code (Playground):

trait Foo<T> {
    fn foo(&self, i: T) -> &Display;
}

impl<C, T> Foo<T> for C 
where
    C: Index<T>,
    C::Output: Display + Sized,
{
    fn foo(&self, i: T) -> &Display {
        &self[i]
    }
}

And the strange error (apparently it's one error repeated three times in slightly different versions):

  error[E0311]: the associated type `<C as std::ops::Index<T>>::Output` may not live long enough
  --> src/main.rs:15:9
   |
15 |         &self[i]
   |         ^^^^^^^^
   |
   = help: consider adding an explicit lifetime bound for `<C as std::ops::Index<T>>::Output`
note: the associated type `<C as std::ops::Index<T>>::Output` must be valid for the anonymous lifetime #1 defined on the method body at 14:5...
  --> src/main.rs:14:5
   |
14 | /     fn foo(&self, i: T) -> &Display {
15 | |         &self[i]
16 | |     }
   | |_____^
note: ...so that the type `<C as std::ops::Index<T>>::Output` is not borrowed for too long
  --> src/main.rs:15:9
   |
15 |         &self[i]
   |         ^^^^^^^^

error[E0311]: the associated type `<C as std::ops::Index<T>>::Output` may not live long enough
  --> src/main.rs:15:9
   |
15 |         &self[i]
   |         ^^^^^^^^
   |
   = help: consider adding an explicit lifetime bound for `<C as std::ops::Index<T>>::Output`
note: the associated type `<C as std::ops::Index<T>>::Output` must be valid for the anonymous lifetime #1 defined on the method body at 14:5...
  --> src/main.rs:14:5
   |
14 | /     fn foo(&self, i: T) -> &Display {
15 | |         &self[i]
16 | |     }
   | |_____^
note: ...so that the type `<C as std::ops::Index<T>>::Output` will meet its required lifetime bounds
  --> src/main.rs:15:9
   |
15 |         &self[i]
   |         ^^^^^^^^

error[E0311]: the associated type `<C as std::ops::Index<T>>::Output` may not live long enough
  --> src/main.rs:15:10
   |
15 |         &self[i]
   |          ^^^^^^^
   |
   = help: consider adding an explicit lifetime bound for `<C as std::ops::Index<T>>::Output`
note: the associated type `<C as std::ops::Index<T>>::Output` must be valid for the anonymous lifetime #1 defined on the method body at 14:5...
  --> src/main.rs:14:5
   |
14 | /     fn foo(&self, i: T) -> &Display {
15 | |         &self[i]
16 | |     }
   | |_____^
note: ...so that the reference type `&<C as std::ops::Index<T>>::Output` does not outlive the data it points at
  --> src/main.rs:15:10
   |
15 |         &self[i]
   |          ^^^^^^^

I don't understand the error at all. Especially since the error talks about the lifetime of C::Output which (as I understand it) has nothing to do with the additional parameter K.

Interestingly, not returning the trait object &Display, but adding an associated type to Foo which is returned, makes the lifetime error go away (Playground). However, this is not a solution for me.

---

What does this error mean? Does it make sense? Is it a compiler bug? What does the parameter K has to do with the lifetime of C::Output?

Answer 1

It makes sense, and is not a compiler bug, but it is somewhat inconvenient.

Full Explanation

It's possible to implement Index<T> for a type C such that C::Output has a type that must outlive some lifetime that is internal to T. Here's a silly example:

struct IntRef<'a>(&'a i32);

impl<'a, 'b: 'a> Index<IntRef<'a>> for IntRef<'b> {
    type Output = IntRef<'a>;
    fn index(&self, _: IntRef<'a>) -> &Self::Output {
        self
    }
}

The blanket impl would try to implement Foo<IntRef<'a>> for IntRef<'b>, which is unsound. To understand why, take a look at this non-compiling example:

let b = 2i32; // 'b begins here:
let b_ref = IntRef(&b);
let o: &Display;  // a reference that outlives 'a but not 'b
{
    let a = 1i32; // 'a begins here:
    let a_ref = IntRef(&a);

    o = &b_ref[a_ref]; // <-- this errors: "a doesn't live long enough"
                       //     which is correct!
    o = b_ref.foo(a_ref); // <-- this wouldn't error, because the returned
                          //     value is `&'x (Display + 'x)` where 'x is
                          //     the lifetime of `b_ref`
}
println!("{:?}", o);

o = &b_ref[a_ref]; will not compile because Index is implemented such that b_ref[a_ref] cannot outlive a_ref. But o = b_ref.foo(a_ref) must compile, since the definition of Foo<T>::foo...

fn foo(&self, i: T) -> &Display                   // what you wrote
fn foo<'a>(&'a self, i: T) -> &'a ('a + Display)  // what the compiler inferred

... enforces that the lifetime of the output depends only on the lifetime of &self (see this question). The compiler rejects the blanket implementation of Foo because if it were allowed, you could use it to "enlarge" a lifetime like that of a_ref in the above example.

(I couldn't come up with a way to make IntRef practical, but the fact remains that you could do it. Possibly, with internal mutability, a sufficiently clever person could introduce unsoundness were this allowed.)

---

Solution 0: Quick & dirty

Just require that T never contain any (non-'static) references and your job is done.

impl<C, T> Foo<T> for C
where
    T: 'static,
    C: Index<T>,
    C::Output: Display + Sized,

This is probably the case for most common uses of the Index trait, but if you want to be able to implement Foo<&T> (which is not unreasonable), you'll want to try something a little less restrictive.

Another possibility is requiring C::Output to be 'static, but this is again more conservative than necessary.

Solution 1: The Best Way

Let's go back to the desugaring of Foo::foo:

fn foo<'a>(&'a self, i: T) -> &'a ('a + Display)

Notice the two 'as in &'a ('a + Display). Although they are the same, they represent different things: the (maximum) lifetime of the reference being returned, and the (maximum) lifetime of any references contained inside the thing that is being referenced.

In Index, which is what we're using to implement Foo, the lifetime of the reference being returned is always connected to the borrow of &self. But Self::Output may contain other references with different (possibly shorter) lifetimes, which is the whole problem. So what we'd really like to write is...

fn foo(&self, i: T) -> &('a + Display)            // what you write
fn foo<'b>(&'b self, i: T) -> &'b ('a + Display)  // what the compiler infers

... which decouples the lifetime of &self from any lifetimes that could be internal to Self::Output.

Of course the problem now is that 'a isn't defined in the trait anywhere, so we have to add it as a parameter:

trait Foo<'a, T> {
    fn foo(&self, i: T) -> &('a + Display);
}

Now you can tell Rust that C::Output must outlive 'a for the impl to apply, and all will be fine (playground):

impl<'a, C, T> Foo<'a, T> for C
where
    C: Index<T>,
    C::Output: 'a + Display + Sized,
{
    fn foo(&self, i: T) -> &('a + Display) {
        &self[i]
    }
}

Solution 2: Put the bound on the method

Solution 1 requires you to add a lifetime parameter to Foo, which might be undesirable. Another possibility is to add a where clause to foo that requires T to outlive the returned &Display.

trait Foo<T> {
    fn foo<'a>(&'a self, i: T) -> &'a Display where T: 'a;
}

It's a bit clunky, but effectively it lets you move the requirement to the function rather than the trait itself. The disadvantage is that this also precludes certain implementations of Foo by insisting that the return value never outlive any reference in T.