Lifetime sub-typing and impl-trait

I bumped into an interesting form of lifetime sub-typing, which I think is valid, but the compiler is skeptical of.

Consider the following function, which computes the dot-product of two sequences of references.

fn dot_prod<'a>(xs: impl IntoIterator<Item = &'a usize>, ys: impl IntoIterator<Item = &'a usize>) -> usize {
    let mut acc = 0;
    for (x, y) in xs.into_iter().zip(ys.into_iter()) {
        acc += *x * *y;
    }
    acc
}

The signature ascribes the same lifetime to the references in both sequences. The "a single lifetime for both inputs" pattern is common, because sub-typing allows the function to be used on references of different lifetimes. However, something here (perhaps impl trait?) blocks this. Let's look at a example of a blocked use (playground link):

fn dot_prod_wrap<'a>(xs: impl IntoIterator<Item = &'a usize>, ys: impl IntoIterator<Item = &'a usize>) -> usize {
    let xs: Vec<usize> = xs.into_iter().cloned().collect();
    let ys = ys.into_iter();
    dot_prod(&xs, ys)
}

Rustc rejects this, observing that the local xs is not valid for 'a, from which we can infer that it has plugged in 'a for the function call's lifetime parameter. However, I think this should type-check, by plugging in the local scope's lifetime (call it 'b), and deducing that ys has a type which is a sub-typed of something that implements IntoIterator<Item = &'b usize>, where 'b is the local scope.

A few variations of this do work, such as changing the impl traits to slices and using two lifetime paramters, but I'm curious about there is a way of getting the Rust compiler to accept a wapper like dot_prod_wrap without changing the signature of dot_prod.

I'm also aware that both sub-typing and impl trait are complex, so perhaps the validity argument I'm presenting above is wrong. The claim "ys has a type which is a sub-typed of something that implements IntoIterator<Item = &'b usize>" is particularly suspect.

Solution

Traits are invariant over their generic parameters. Once the borrow checker has deduced impl IntoIterator<Item = &'a usize> a proper lifetime 'a it cannot be changed, not even to a shorter lifetime.

The reason is because trait objects are black boxes; they can do anything they want within the bounds of their constraints. This includes things like iterior mutability which cannot use a shorter lifetime (otherwise you'd be able to assign a value with a shorter lifetime to an object expecting a longer one). It works for slices because the borrow checker knows the lifetime is covariant; so it can be made shorter when required.

You should make dot_prod use two independent lifetimes.