Perplexing borrow checker message: "lifetime mismatch"

Question

I've recently come across a borrow checker message I've never seen before which I'm trying to understand. Here is the code to reproduce it (simplified, real-life example was more complex) - playground:

fn foo(v1: &mut Vec<u8>, v2: &mut Vec<u8>, which: bool) {
    let dest = if which { &mut v1 } else { &mut v2 };
    dest.push(1);
}

It fails to compile with the following error:

error[E0623]: lifetime mismatch
 --> src/main.rs:2:44
  |
1 | fn foo(v1: &mut Vec<u8>, v2: &mut Vec<u8>, which: bool) {
  |            ------------      ------------ these two types are declared with different lifetimes...
2 |     let dest = if which { &mut v1 } else { &mut v2 };
  |                                            ^^^^^^^ ...but data from `v2` flows into `v1` here

...followed by another one about data flowing from v1 into v2.

My question is: what does this error mean? What is data flow and how does it occur between the two variables, given that the code is only pushing Copy data to one of them?

If I follow the compiler and force the lifetimes of v1 and v2 to match, the function compiles (playground):

fn foo<'a>(mut v1: &'a mut Vec<u8>, mut v2: &'a mut Vec<u8>, which: bool) {
    let dest = if which { &mut v1 } else { &mut v2 };
    dest.push(1);
}

However, on further inspection it turned out that the original code was needlessly complex, left over from when v1 and v2 were actual Vecs, and not references. A simpler and more natural variant is to set dest not to &mut v1 and &mut v2, but to the simpler v1 and v2, which are references to begin with. And that compiles too (playground):

fn foo(v1: &mut Vec<u8>, v2: &mut Vec<u8>, which: bool) {
    let dest = if which { v1 } else { v2 };
    dest.push(1);
}

In this seemingly equivalent formulation lifetimes of v1 and v2 matching are no longer a requirement.

Cabalism

&mut v1 is very different from v1, "given that the code is only pushing Copy data to one of them?" that not the problem, the borrow checker see you want to put two variable with different lifetime into dest. "...but data from v2 flows into v1 here" that only the compiler side that see it that way, lifetime should be the same from v1. You already solve the problem so I don't understand what trouble you – Ea

@Ea You already solve the problem so I don't understand what trouble you Sure, I solved the problem, but I still didn't understand the error reported in the original code! Specifically why the compiler is able to find a common lifetime for dest in the last snippet, but not in the first one. This is all superbly explained in Francis's answer. – Cabalism

Answer 1

The problem is that &'a mut T is invariant over T.

First, let's look at the working code:

fn foo(v1: &mut Vec<u8>, v2: &mut Vec<u8>, which: bool) {
    let dest = if which { v1 } else { v2 };
    dest.push(1);
}

The types of v1 and v2 have elided lifetime parameters. Let's make them explicit:

fn foo<'a, 'b>(v1: &'a mut Vec<u8>, v2: &'b mut Vec<u8>, which: bool) {
    let dest = if which { v1 } else { v2 };
    dest.push(1);
}

The compiler has to figure out the type of dest. The two branches of the if expression produce values of different types: &'a mut Vec<u8> and &'b mut Vec<u8>. Despite that, the compiler is able to figure out a type that is compatible with both types; let's call this type &'c mut Vec<u8>, where 'a: 'c, 'b: 'c. &'c mut Vec<u8> here is a common supertype of both &'a mut Vec<u8> and &'b mut Vec<u8>, because both 'a and 'b outlive 'c (i.e. 'c is a shorter/smaller lifetime than either 'a or 'b).

Now, let's examine the erroneous code:

fn foo<'a, 'b>(v1: &'a mut Vec<u8>, v2: &'b mut Vec<u8>, which: bool) {
    let dest = if which { &mut v1 } else { &mut v2 };
    dest.push(1);
}

Again, the compiler has to figure out the type of dest. The two branches of the if expression produce values of types: &'c mut &'a mut Vec<u8> and &'d mut &'b mut Vec<u8> respectively (where 'c and 'd are fresh lifetimes).

I said earlier that &'a mut T is invariant over T. What this means is that we can't change the T in &'a mut T such that we can produce a subtype or supertype of &'a mut T. Here, the T types are &'a mut Vec<u8> and &'b mut Vec<u8>. They are not the same type, so we must conclude that the types &'c mut &'a mut Vec<u8> and &'d mut &'b mut Vec<u8> are unrelated. Therefore, there is no valid type for dest.

Lumberyard

Thanks for the detailed answer, you nailed the issue! I was unclear why the compiler would have problems figuring out the lifetime of dest in the erroneous example, since we are capturing variables v1 and v2, which obviously have the same lifetime. But the problem is that the lifetimes of the underlying references are incompatible, which becomes an issue when constructing a mut reference that points to either. The "figure out a supertype" trick from the previous example wouldn't work because sub/supertyping doesn't propagate to the mut reference. – Cabalism

And indeed, omitting mut makes the assignment to dest compile. I suppose the reason for the different type requirement between exclusive and shared references is that the former must support both reading and writing, so allowing anything other than invariance would break the guarantees in one case. – Cabalism

Answer 2

What you have here is a variation of this erroneous program:

fn foo(x: &mut Vec<&u32>, y: &u32) {
  x.push(y);
}

The error messages used to be a bit more vague but were changed with this pull request. This is a case of Variance, which you can read more about in the nomicon if you are interested. It is a complex subject but I will try my best to explain the quick and short of it.

Unless you specify the lifetimes, when you return &mut v1 or &mut v2 from your if statement, the types are determined by the compiler to have different lifetimes, thus returning a different type. Therefore the compiler can't determine the correct lifetime (or type) for dest. When you explicitly set all lifetimes to be the same, the compiler now understands that both branches of the if statement return the same lifetime and it can figure out the type of dest.

In the example above x has a different lifetime from y and thus a different type.

Lamontlamontagne