Wrong inferred lifetime due to associated type

Question

The following code sample is a minified version of a problem I have.

trait Offset: Default {}

trait Reader {
    type Offset: Offset;
}

impl Offset for usize {}

impl<'a> Reader for &'a [u8] {
    type Offset = usize;
}

// OK
// struct Header<R: Reader>(R, usize);

// Bad
struct Header<R: Reader>(R, R::Offset);

impl <R: Reader<Offset=usize>> Header<R> {
    fn new(r: R) -> Self {
        Header(r, 0)
    }
}

fn test<R: Reader>(_: Header<R>, _: Header<R>) {}

fn main() {
    let buf1 = [0u8];
    let slice1 = &buf1[..];
    let header1 = Header::new(slice1);

    let buf2 = [0u8];
    let slice2 = &buf2[..];
    let header2 = Header::new(slice2);

    test(header1, header2);
}

I currently have the code working using usize instead of the Offset associated type. I'm trying to generalize my code so it can work with other types for offset. However, adding this associated type has caused lots of existing code to stop compiling with errors like this:

error[E0597]: `buf2` does not live long enough
  --> src/main.rs:37:1
   |
33 |     let slice2 = &buf2[..];
   |                   ---- borrow occurs here
...
37 | }
   | ^ `buf2` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

Reversing the order of header1 and buf2 fixes the problem for this example, but I don't want to have to make this change everywhere (and may not be able to), and I don't understand why it is a problem.

Answer 1

Cause

Variance is the cause of the problem.

• In struct Header<R: Reader>(R, usize);, Header<R> is covariant w.r.t. R.
• However, in struct Header<R: Reader>(R, R::Offset);, Header<R> is invariant w.r.t. R.

Subtyping is a safe conversion of lifetimes. For example, &'static [u8] can be converted to &'a [u8].

Variance describes how subtyping is lifted to complex types. For example, if Header<_> is covariant and R is a subtype of S, Header<R> is a subtype of Header<S>. This is not the case with invariant structs.

In current Rust, traits are always invariant, because trait variance can't be inferred nor specified in the current syntax. Same restrictions apply to projected types like R::Offset.

In your code, since Header is invariant, Header<&'a [u8]> can't be upcasted to Header<&'b [u8]> even if 'a: 'b. Since fn test requires the same type for both arguments, the compiler required the same lifetime for slice1 and slice2.

Solution

One possible ad-hoc solution is to generalize the signature for fn test, if it is feasible.

fn test<R: Reader, S: Reader>(_: Header<R>, _: Header<S>) {}

Another solution is to make Header covariant somehow.

Maybe it is safe to assume Header to be covariant if type Offset has 'static bound, but the current compiler doesn't do such a clever inference.

Perhaps you can split out lifetimes as a parameter for Header. This recovers covariance.

trait Offset: Default {}

trait Reader {
    type Offset: Offset;
}

impl Offset for usize {}

impl Reader for [u8] {
    type Offset = usize;
}

struct Header<'a, R: Reader + ?Sized + 'a>(&'a R, R::Offset);

impl <'a, R: Reader<Offset=usize> + ?Sized> Header<'a, R> {
    fn new(r: &'a R) -> Self {
        Header(r, 0)
    }
}

fn test<R: Reader + ?Sized>(_: Header<R>, _: Header<R>) {}

fn main() {
    let buf1 = [0u8];
    let slice1 = &buf1[..];
    let header1 = Header::new(slice1);

    let buf2 = [0u8];
    let slice2 = &buf2[..];
    let header2 = Header::new(slice2);

    test(header1, header2);
}