Lifetime sub-typing and impl-trait

Question

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.

score 3 · Accepted Answer · answered Apr 22 '21 at 00:37

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.

score 0 · Answer 2 · answered Apr 29 '22 at 14:08

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.

kmdreko's answer is correct about the reasons Rust behaves this way: knowing only that ys's IntoIterator::IntoIter type has a certain lifetime isn't enough for it to know whether it can shorten that lifetime. However, that Iterator<Item=&'a usize> isn't an opaque black box to us programmers:

let ys = ys.into_iter().map(|y| y);

By mapping all the values in the iterator to themselves, we allow Rust to pick an appropriate return type for the closure. After a bit of thinking, rustc determines that in order to make the dot_prod call type check, it needs to shorten the lifetime of the returned borrow to match xs.

.map(|y| y) doesn't do anything beyond the type system, so rustc will optimise it out entirely in release builds. (It can do this in all circumstances, since this closure is a zero-sized opaque type. I'm not entirely sure it does in all circumstances, but I can't think of a reason it wouldn't.)

Lifetime sub-typing and impl-trait

2 Answers2