Associated type lifetime bounds are underconstrained

[aturon]

The following code:

use std::ops::Deref;

pub trait ToOwned {
    type Owned: Borrow<Self>;
    fn to_owned(&self) -> Self::Owned;
}

pub enum Cow<'a, B: ?Sized + 'a> where B: ToOwned {
    Borrowed(&'a B),
    Owned(<B as ToOwned>::Owned)
}

impl<'a, B: ?Sized> Deref for Cow<'a, B> where B: ToOwned {
    type Target = B;

    fn deref(&self) -> &B {
        match *self {
            Cow::Borrowed(borrowed) => borrowed,
            Cow::Owned(ref owned) => owned.borrow()
        }
    }
}

pub trait Borrow<Borrowed: ?Sized> {
    fn borrow(&self) -> &Borrowed;
}

fails with:

<anon>:19:24: 19:33 error: the associated type `<B as ToOwned>::Owned` may not live long enough [E0311]
<anon>:19             Cow::Owned(ref owned) => owned.borrow()
                                 ^~~~~~~~~
<anon>:19:24: 19:33 help: consider adding an explicit lifetime bound for `<B as ToOwned>::Owned`
<anon>:19             Cow::Owned(ref owned) => owned.borrow()
                                 ^~~~~~~~~
<anon>:16:27: 21:6 note: the associated type `<B as ToOwned>::Owned` must be valid for the anonymous lifetime #1 defined on the block at 16:26...
<anon>:16     fn deref(&self) -> &B {
<anon>:17         match *self {
<anon>:18             Cow::Borrowed(borrowed) => borrowed,
<anon>:19             Cow::Owned(ref owned) => owned.borrow()
<anon>:20         }
<anon>:21     }
<anon>:19:24: 19:33 note: ...so that the reference type `&<B as ToOwned>::Owned` does not outlive the data it points at
<anon>:19             Cow::Owned(ref owned) => owned.borrow()

The same code not using associated types does not have this problem.

[aturon]

cc @japaric

[nikomatsakis]

The problem arises from the "implied region bounds" rules. In the older formulation (or an equivalent one, like http://is.gd/L4uIcH), you wind up with the owned type O as a type parameter. Therefore, the type of self is &'a Cow<B,O>, from which we infer that B:'a and O:'a holds. This determination is based on rules that consider the variance of each type parameter (here, B and O). Unfortunately, when O is moved to an associated type, the type is just &'a Cow<B>, from which we derive that B:'a but not B::Owned : 'a.

I see a couple of ways to fix this:

1. We could modify the WF rules to trawl the contents of the enum/structure, potentially. This would allow us to determine that &'a Cow<B> implies B::Owned : 'a because B::Owned is contained within one of the variants.
2. We could modify the WF rules so that if you have a type parameter B with the bound B:Borrow, then we ensure that all associated types of Borrow must also outlive the surrounding region. Hence &'a Cow<B> would be imply B:'a and B::Owned : 'a.

The difference between 1 and 2 is that 2 doesn't require inspecting the contents of the struct, just the where-clauses declared on the struct. I have a mild preference for this -- I originally designed the rules to use variance for the same reason, basically that trawling through the contents feels like it exposes more of the guts than I would like, and raises other questions.

The downside of option 2 is that if there are associated types that don't represent data reachable from Self, then they will wind up with stricter lifetime requirements than necessary. Lacking variance information on associated types, we can't really make this determination. It's unclear how big a problem this would be in practice; conceivably we could eventually add some keyword (like in type X) to declare "input" types that don't represent data reachable from self.

Anyway, just some in-progress thoughts. I think mocking up option 2 wouldn't be all that hard.

[nikomatsakis]

Somewhat simplified test case:

use std::ops::Deref;

pub trait ToOwned {
    type Owned: Borrow<Self>;
    fn to_owned(&self) -> Self::Owned;
}

pub trait Borrow<Borrowed> {
    fn borrow(&self) -> &Borrowed;
}

pub struct Foo<B:ToOwned> {
    owned: B::Owned
}

fn foo<B:ToOwned>(this: &Foo<B>) -> &B {
    this.owned.borrow()
}

fn main() { }

[nikomatsakis]

I've implemented option 2, which I think is the right call. Basically the idea is that if you have a struct with where clauses, we will require that any associated types of traits that appear in those where clauses must outlive the struct itself (as they could potentially be embedded within the struct).

So if you have:

trait Foo { type T; ... }
struct Bar<U:Foo> { ... }

then if some instance of Bar<U> which appears in an location with lifetime 'a, U::T must outlive 'a. Similarly &'a Bar<U> is only legal if U::T : 'a (and, most importantly, a function that takes &'a Bar<U> can assume that U::T : 'a).

[edwardw]

This can be closed since #22436 has fixed it.

[alexcrichton]

Thanks @edwardw!