Lifetime Experiment: Can the Borrow Checker Be Lied to?

#1

It has been said that the Borrow Checker has only a limited ability to analyse code and therefore needs hints in the form of lifetime parameters. So, I had a play with this simple piece of code.

fn pick_first(x: &i32, y: &i32) -> &i32 {
    println!("first parameter {}; second parameter {}", x, y);
    x
}

fn main() {
    let x = 42;
    let y = 43;

    let r = pick_first(&x, &y);
    println!("the first number was {}", r);
}

For obvious reasons I get a compiler error:

error[E0106]: missing lifetime specifier
 --> src/main.rs:1:36
  |
1 | fn pick_first(x: &i32, y: &i32) -> &i32 {
  |                  ----     ----     ^ expected named lifetime parameter
  |
  = help: this function's return type contains a borrowed value, but the signature does not say whether it is borrowed from `x` or `y`

So, I introduce lifetime parameters for both input parameters and the output; I pick different lifetimes 'x and 'y for both x and y, respectively. As you would expect that compiles and runs just fine.

fn pick_first<'x, 'y>(x: &'x i32, y: &'y i32) -> &'x i32 { ... }

However, then I got curious and wondered whether I could lie to the Borrow Checker and pretend that the result was borrowed from y rather than x...

fn pick_first<'x, 'y>(x: &'x i32, y: &'y i32) -> &'y i32 {
    println!("first parameter {}; second parameter {}", x, y);
    x
}

...and as it turns out, I cannot:

error[E0623]: lifetime mismatch
 --> src/main.rs:3:5
  |
1 | fn pick_first<'x, 'y>(x: &'x i32, y: &'y i32) -> &'y i32 {
  |                          -------                 -------
  |                          |
  |                          this parameter and the return type are declared with different lifetimes...
2 |     println!("first parameter {}; second parameter {}", x, y);
3 |     x
  |     ^ ...but data from `x` is returned here

So, somehow the Borrow Checker does analyse the code and can tell me that I am lying. Given that, why do I need the lifetime parameters at all in this case? It seems like the Burrow Checker is fully aware of what's going on here.

I guess more generally, I am wondering: Can the Borrow Checker be lied to? That is, can I specify lifetimes that pass the Borrow Checker that will ultimately lead to a dangling pointer?

#2

No (except for compiler bugs).

It's easier to verify than it is to infer. The borrow checker does not compute all the correct lifetimes from the function body, it instead checks that the implementation is correct with respect to the lifetimes specified in the signature.

(As I have said repeatedly during the last couple of days, inferring lifetimes from the body would be a Bad Idea™ because it would make lifetimes a leaky abstraction, silently changing interfaces depending on their concrete implementation.)

To give a slightly more mathematical explanation: if I give you a large number (~the function body) and I tell you that it's the product of two large primes (~the lifetimes), it'll take a long time for you to come up with the correct factors (~lifetime inference). However, if I tell you the two factors in advance, you'll be able to multiply them together and check if the result is the same as the initial big number (~borrow checking).

11 Likes
#3

There are three possible situations that can result when you assign lifetimes:

  1. The lifetimes are too weak, and if it compiled, would allow unsoundness such as dangling pointers.
  2. The lifetimes have appropriate strength and allow exactly code that is valid to compile.
  3. The lifetimes are too strict, and reject code that is sound.

The compiler will never accept code that lies in category 1, but it will usually accept code in both category 2 and 3. For example, your pick_first is in category 1 and is hence rejected, but consider this:

fn pick_first<'x>(x: &'x i32, y: &'x i32) -> &'x i32 {
    println!("first parameter {}; second parameter {}", x, y);
    x
}

These lifetimes say that pick_first might return y, and hence any code that uses pick_first will only compile if they allow this to happen. Hence this fails to compile:

fn pick_first<'x>(x: &'x i32, y: &'x i32) -> &'x i32 {
    println!("first parameter {}; second parameter {}", x, y);
    x
}

fn main() {
    let x = 10;
    let first;
    
    {
        let y = 20;
        first = pick_first(&x, &y);
    }
    
    println!("{}", first);
}

error[E0597]: `y` does not live long enough
  --> src/main.rs:12:32
   |
12 |         first = pick_first(&x, &y);
   |                                ^^ borrowed value does not live long enough
13 |     }
   |     - `y` dropped here while still borrowed
14 |     
15 |     println!("{}", first);
   |                    ----- borrow later used here

However the main function doesn't do anything wrong. The function is guaranteed to return x, so first is definitely valid at the println!. This puts this assignment of lifetimes in category 3.

If we change the lifetimes to be "more correct", it does compile:

fn pick_first<'x, 'y>(x: &'x i32, y: &'y i32) -> &'x i32 {
    println!("first parameter {}; second parameter {}", x, y);
    x
}

fn main() {
    let x = 10;
    let first;
    
    {
        let y = 20;
        first = pick_first(&x, &y);
    }
    
    println!("{}", first);
}

first parameter 10; second parameter 20
10

So this version is in category 2.

Did we lie to the compiler here? We said that we might return y, and then we didn't. Whether this is a lie is up to interpretation, and is discussed in more depth in if it compiles then my lifetime annotations are correct from Common Rust Lifetime Misconceptions.

8 Likes
#4

There is a qualitative difference between checking if the lifetime you provided are correct and coming up with “the correct” lifetime annotations on its own (if they exist).

A good comparison might be mathematical proof. It is way harder to come up with a proof that the square root of 2 is irrational yourself than to check if such a proof is correct when it is presented to you. Of course lifetime annotations are a bit more simple than mathematical proofs and in principle it should be possible to “magically infer” more about lifetime parameters than what the compiler currently does. However Rust is designed in a way where function type signatures always have to be explicit for things like API stability, better documentation and more local error messages, so the main reason why you need to provide lifetimes in function signatures is: because Rust is designed that way.

In general, Rust is designed in a way that you should not be able to lie to the borrow checker; at least when you interpret “to lie” as in:

Of course there are “lies” that don’t lead to memory unsafety, in particular lifetime annotations can be too restrictive making a function hard or almost impossible to call. A good read about lifetimes is this post about “common lifetime misconceptions”.

Other ways to “lie” to the borrow checker are:

7 Likes
#5

I think it's important to understand that the compiler currently has the following property:

Any function's correctness can be verified without looking inside any other function in the codebase. All that is necessary is the signature of other functions.

This property is very nice, and has various nice consequences such as the fact that, if you leave a function's signature unchanged, any code that uses it will continue to compile even if you change the body of the function.

This property is absolutely vital for the ability to write backwards compatible code when designing libraries. If the lifetimes were "hidden", I would have to double-check that I didn't change the signature in any way whenever I changed the contents of any function in my library, and if they aren't explicit in the code, this might be quite hard.

Lifetimes are part of why I am not worried about breaking existing code when we publish new versions of Tokio. Just double-check that signatures didn't change, and poof, we have the guarantee that existing code will continue to compile.

14 Likes
#6

Slight caveat: This is - unfortunately - not entirely the case, in particular around auto traits such as Sync and Send. Those kinds of trait bounds can be implicit for return types of functions that return opaque impl Trait types or for async fns.

5 Likes
#7

Yes, unfortunately there are some newer additions to the language that do hide parts of the signature from the code. This has caused unintentional breaking changes in Tokio in the past, and we have a large file with tests that verify that these hidden parts of the signature are as we expect them.

In any case, I am very happy that lifetimes do not fall in this category of places where parts of the signature is hidden. That would be hell for the maintainability of Tokio.

4 Likes
#8

Additionally to all the good answers you've received, lifetimes are part of the interface you are providing to your users. If the compiler were able to adjust lifetimes by inference, you would not be able to provide semver guarantees about your code without hamstringing your ability to change the implementation with confidence.

1 Like
#9

Thank you all for those great answers. Yes, all of that makes sense. In particular, the notion that the lifetimes are part of the interface and thereby the guarantees that a library function makes to its clients is something I overlooked. Great discuss.