Trait implementation accepts wrong lifetime in method signature with associated type

[tomjakubowski]

(Sorry for the bad title)

trait Fun {
    type Output;
    fn call<'x>(&'x self) -> Self::Output;
}

struct Holder { x: String }

impl<'a> Fun for Holder {
    type Output = &'a str;
    fn call<'b>(&'b self) -> &'b str {
        &self.x[]
    }
}

This compiles even though the trait's definition should require call's signature in the impl to be fn call<'b>(&'b self) -> &'a str.

[huonw]

This seems to be a problem with associated types, converting Fun to Fun<Output> correctly fails to compile:

trait Fun<Output> {
    fn call<'x>(&'x self) -> Output;
}

struct Holder { x: String }

impl<'a> Fun<&'a str> for Holder {
    fn call<'b>(&'b self) -> &'b str {
        &self.x[]
    }
}

<anon>:8:5: 10:6 error: method `call` has an incompatible type for trait: expected bound lifetime parameter 'x, found concrete lifetime [E0053]
<anon>:8     fn call<'b>(&'b self) -> &'b str {
<anon>:9         &self.x[]
<anon>:10     }

cc @nikomatsakis

[edwardw]

cc me. It feels very closely related to #21750, although on the surface they are quite the opposite. Also, @nikomatsakis may have something in the making for #21974.

[pnkfelix]

P-backcompat-lang, 1.0 beta.

[huonw]

Possibly related to #21259.

[edwardw]

Have an fix in the same vein of #22338. But, it also reports an error

error: method index_mut has an incompatible type for trait: expected type parameter, found a different type parameter [E0053]

for libstd/collections/hash/map.rs:

impl<K, Q: ?Sized, V, S, H> Index<Q> for HashMap<K, V, S>
    where K: Eq + Hash<H>,
          Q: Eq + Hash<H> + BorrowFrom<K>,
          S: HashState<Hasher=H>,
          H: hash::Hasher<Output=u64>
{
    type Output = V;

    #[inline]
    fn index<'a>(&'a self, index: &Q) -> &'a V {
        self.get(index).expect("no entry found for key")
    }
}

impl<K, V, S, H, Q: ?Sized> IndexMut<Q> for HashMap<K, V, S>
    where K: Eq + Hash<H>,
          Q: Eq + Hash<H> + BorrowFrom<K>,
          S: HashState<Hasher=H>,
          H: hash::Hasher<Output=u64>
{
    #[inline]
    fn index_mut<'a>(&'a mut self, index: &Q) -> &'a mut V {
        self.get_mut(index).expect("no entry found for key")
    }
}

Notice, the order of the type parameters is different. So is the error legit or does the fix simply have a regression?

[nikomatsakis]

Ah, I see. The problem is that the 'a variable on the impl is unconstrained. That is, this impl promises that it can make an Output for any 'a, but 'a does no appear in the input type nor in the trait reference. I decided to allow such "unused" lifetimes even though, probably, they ought to be prohibited by RFC 447 because it wasn't clear to me what harm they could do. Given only methods, I don't think they really can do harm, though they are kind of pointless. In particular, if the lifetime does not appear in the trait reference, it cannot appear in the signature of any of the methods that the trait defines, so when someone calls fns defined in the trait, they can use any lifetime they want for that impl parameter without affecting the signature they see.

But this logic does not hold with associated types. They allow us to create links between a projected type and the return type of a method. In that case, it is harmful if there are lifetimes that are not constrained by the trait reference or the input types, since every instantiation of Self::Output is then free to choose a distinct 'a with no constraints. Even this is not bad, except that when we call a trait fn, we assume that every use of <X as Trait>::Output will be the same type if the inputs to the trait (X, in this case) are the same, but that is not the case here.

We should prohibit these unconstrainted lifetime parameters, either completely, or at minimum from appearing in the value of an associated type.

[emberian]

Example illustrating soundness hole:

struct Foo<'a> {
    inner: &'a mut [u8]
}

impl<'a, 'b> Iterator for Foo<'a> {
    type Item = &'b mut u8;

    fn next(&mut self) -> Option<&mut u8> {
        Some(&mut self.inner[0])
    }
}

fn main() {
    let mut fun = [1,2,3,4,5];
    let mut foo = Foo {
        inner: &mut fun
    };
    {
        let a = foo.next().unwrap();
        let b = foo.next().unwrap();
        *a = 1;
        *b = 2;
        println!("{}", a);
    }
}

[pnkfelix]

This is "just a bug", but one we would really like to fix.

Nonetheless, not a beta-blocker. But we want to fix for 1.0; so reclassifying as such.