Skip to content

Latest commit

 

History

History
2186 lines (1807 loc) · 82.1 KB

0000-nonlexical-lifetimes.md

File metadata and controls

2186 lines (1807 loc) · 82.1 KB
Raw
  • Feature Name: (fill me in with a unique ident, my_awesome_feature)
  • Start Date: (fill me in with today's date, YYYY-MM-DD)
  • RFC PR: (leave this empty)
  • Rust Issue: (leave this empty)

Summary

Extend Rust's borrow system to support non-lexical lifetimes -- these are lifetimes that are based on the control-flow graph, rather than lexical scopes. The RFC describes in detail how to infer these new, more flexible regions, and also describes how to adjust our error messages. The RFC also describes a few other extensions to the borrow checker, the total effect of which is to eliminate many common cases where small, function-local code modifications would be required to pass the borrow check. (The appendix describes some of the remaining borrow-checker limitations that are not addressed by this RFC.)

Motivation

What is a lifetime?

The basic idea of the borrow checker is that values may not be mutated or moved while they are borrowed, but how do we know whether a value is borrowed? The idea is quite simple: whenever you create a borrow, the compiler assigns the resulting reference a lifetime. This lifetime corresponds to the span of the code where the reference may be used. The compiler will infer this lifetime to be the smallest lifetime that it can have that still encompasses all the uses of the reference.

Note that Rust uses the term lifetime in a very particular way. In everyday speech, the word lifetime can be used in two distinct -- but similar -- ways:

  1. The lifetime of a reference, corresponding to the span of time in which that reference is used.
  2. The lifetime of a value, corresponding to the span of time before that value gets freed (or, put another way, before the destructor for the value runs).

This second span of time, which describes how long a value is valid, is very important. To distinguish the two, we refer to that second span of time as the value's scope. Naturally, lifetimes and scopes are linked to one another. Specifically, if you make a reference to a value, the lifetime of that reference cannot outlive the scope of that value. Otherwise, your reference would be pointing into freed memory.

To better see the distinction between lifetime and scope, let's consider a simple example. In this example, the vector data is borrowed (mutably) and the resulting reference is passed to a function capitalize. Since capitalize does not return the reference back, the lifetime of this borrow will be confined to just that call. The scope of data, in contrast, is much larger, and corresponds to a suffix of the fn body, stretching from the let until the end of the enclosing scope.

fn foo() {
    let mut data = vec!['a', 'b', 'c']; // --+ 'scope
    capitalize(&mut data[..]);          //   |
//  ^~~~~~~~~~~~~~~~~~~~~~~~~ 'lifetime //   |
    data.push('d');                     //   |
    data.push('e');                     //   |
    data.push('f');                     //   |
} // <---------------------------------------+

fn capitalize(data: &mut [char]) {
    // do something
}

This example also demonstrates something else. Lifetimes in Rust today are quite a bit more flexible than scopes (if not as flexible as we might like, hence this RFC):

  • A scope generally corresponds to some block (or, more specifically, a suffix of a block that stretches from the let until the end of the enclosing block) [1].
  • A lifetime, in contrast, can also span an individual expression, as this example demonstrates. The lifetime of the borrow in the example is confined to just the call to capitalize, and doesn't extend into the rest of the block. This is why the calls to data.push that come below are legal.

So long as a reference is only used within one statement, today's lifetimes are typically adequate. Problems arise however when you have a reference that spans multiple statements. In that case, the compiler requires the lifetime to be the innermost expression (which is often a block) that encloses both statements, and that is typically much bigger than is really necessary or desired. Let's look at some example problem cases. Later on, we'll see how non-lexical lifetimes fix these cases.

Problem case #1: references assigned into a variable

One common problem case is when a reference is assigned into a variable. Consider this trivial variation of the previous example, where the &mut data[..] slice is not passed directly to capitalize, but is instead stored into a local variable:

fn bar() {
    let mut data = vec!['a', 'b', 'c'];
    let slice = &mut data[..]; // <-+ 'lifetime
    capitalize(slice);         //   |
    data.push('d'); // ERROR!  //   |
    data.push('e'); // ERROR!  //   |
    data.push('f'); // ERROR!  //   |
} // <------------------------------+

The way that the compiler currently works, assigning a reference into a variable means that its lifetime must be as large as the entire scope of that variable. In this case, that means the lifetime is now extended all the way until the end of the block. This in turn means that the calls to data.push are now in error, because they occur during the lifetime of slice. It's logical, but it's annoying.

In this particular case, you could resolve the problem by putting slice into its own block:

fn bar() {
    let mut data = vec!['a', 'b', 'c'];
    {
        let slice = &mut data[..]; // <-+ 'lifetime
        capitalize(slice);         //   |
    } // <------------------------------+
    data.push('d'); // OK
    data.push('e'); // OK
    data.push('f'); // OK
}

Since we introduced a new block, the scope of slice is now smaller, and hence the resulting lifetime is smaller. Introducing a block like this is kind of artificial and also not an entirely obvious solution.

Problem case #2: conditional control flow

Another common problem case is when references are used in only one given match arm (or, more generally, one control-flow path). This most commonly arises around maps. Consider this function, which, given some key, processes the value found in map[key] if it exists, or else inserts a default value:

fn process_or_default() {
    let mut map = ...;
    let key = ...;
    match map.get_mut(&key) { // -------------+ 'lifetime
        Some(value) => process(value),     // |
        None => {                          // |
            map.insert(key, V::default()); // |
            //  ^~~~~~ ERROR.              // |
        }                                  // |
    } // <------------------------------------+
}

This code will not compile today. The reason is that the map is borrowed as part of the call to get_mut, and that borrow must encompass not only the call to get_mut, but also the Some branch of the match. The innermost expression that encloses both of these expressions is the match itself (as depicted above), and hence the borrow is considered to extend until the end of the match. Unfortunately, the match encloses not only the Some branch, but also the None branch, and hence when we go to insert into the map in the None branch, we get an error that the map is still borrowed.

This particular example is relatively easy to workaround. In many cases, one can move the code for None out from the match like so:

fn process_or_default1() {
    let mut map = ...;
    let key = ...;
    match map.get_mut(&key) { // -------------+ 'lifetime
        Some(value) => {                   // |
            process(value);                // |
            return;                        // |
        }                                  // |
        None => {                          // |
        }                                  // |
    } // <------------------------------------+
    map.insert(key, V::default());
}

When the code is adjusted this way, the call to map.insert is not part of the match, and hence it is not part of the borrow. While this works, it is unfortunate to require these sorts of manipulations, just as it was when we introduced an artificial block in the previous example.

Problem case #3: conditional control flow across functions

While we were able to work around problem case #2 in a relatively simple, if irritating, fashion, there are other variations of conditional control flow that cannot be so easily resolved. This is particularly true when you are returning a reference out of a function. Consider the following function, which returns the value for a key if it exists, and inserts a new value otherwise (for the purposes of this section, assume that the entry API for maps does not exist):

fn get_default<'r,K,V:Default>(map: &'r mut HashMap<K,V>,
                               key: K)
                               -> &'r mut V {
    match map.get_mut(&key) { // -------------+ 'r
        Some(value) => value,              // |
        None => {                          // |
            map.insert(key, V::default()); // |
            //  ^~~~~~ ERROR               // |
            map.get_mut(&key).unwrap()     // |
        }                                  // |
    }                                      // |
}                                          // v

At first glance, this code appears quite similar to the code we saw before, and indeed, just as before, it will not compile. In fact, the lifetimes at play are quite different. The reason is that, in the Some branch, the value is being returned out to the caller. Since value is a reference into the map, this implies that the map will remain borrowed until some point in the caller (the point 'r, to be exact). To get a better intuition for what this lifetime parameter 'r represents, consider some hypothetical caller of get_default: the lifetime 'r then represents the span of code in which that caller will use the resulting reference:

fn caller() {
    let mut map = HashMap::new();
    ...
    {
        let v = get_default(&mut map, key); // -+ 'r
          // +-- get_default() -----------+ //  |
          // | match map.get_mut(&key) {  | //  |
          // |   Some(value) => value,    | //  |
          // |   None => {                | //  |
          // |     ..                     | //  |
          // |   }                        | //  |
          // +----------------------------+ //  |
        process(v);                         //  |
    } // <--------------------------------------+
    ...
}

If we attempt the same workaround for this case that we tried in the previous example, we will find that it does not work:

fn get_default1<'r,K,V:Default>(map: &'r mut HashMap<K,V>,
                                key: K)
                                -> &'r mut V {
    match map.get_mut(&key) { // -------------+ 'r
        Some(value) => return value,       // |
        None => { }                        // |
    }                                      // |
    map.insert(key, V::default());         // |
    //  ^~~~~~ ERROR (still)                  |
    map.get_mut(&key).unwrap()             // |
}                                          // v

Whereas before the lifetime of value was confined to the match, this new lifetime extends out into the caller, and therefore the borrow does not end just because we exited the match. Hence it is still in scope when we attempt to call insert after the match.

The workaround for this problem is a bit more involved. It relies on the fact that the borrow checker uses the precise control-flow of the function to determine which borrows are in scope.

fn get_default2<'r,K,V:Default>(map: &'r mut HashMap<K,V>,
                                key: K)
                                -> &'r mut V {
    if map.contains(&key) {
    // ^~~~~~~~~~~~~~~~~~ 'n
        return match map.get_mut(&key) { // + 'r
            Some(value) => value,        // |
            None => unreachable!()       // |
        };                               // v
    }

    // At this point, `map.get_mut` was never
    // called! (As opposed to having been called,
    // but its result no longer being in use.)
    map.insert(key, V::default()); // OK now.
    map.get_mut(&key).unwrap()
}

What has changed here is that we moved the call to map.get_mut inside of an if, and we have set things up so that the if body unconditionally returns. What this means is that a borrow begins at the point of get_mut, and that borrow lasts until the point 'r in the caller, but the borrow checker can see that this borrow will not have even started outside of the if. It does not consider the borrow in scope at the point where we call map.insert.

This workaround is more troublesome than the others, because the resulting code is actually less efficient at runtime, since it must do multiple lookups.

It's worth noting that Rust's hashmaps include an entry API that one could use to implement this function today. The resulting code is both nicer to read and more efficient even than the original version, since it avoids extra lookups on the "not present" path as well:

fn get_default3<'r,K,V:Default>(map: &'r mut HashMap<K,V>,
                                key: K)
                                -> &'r mut V {
    map.entry(key)
       .or_insert_with(|| V::default())
}

Regardless, the problem exists for other data structures besides HashMap, so it would be nice if the original code passed the borrow checker, even if in practice using the entry API would be preferable. (Interestingly, the limitation of the borrow checker here was one of the motivations for developing the entry API in the first place!)

Problem case #4: mutating &mut references

The current borrow checker forbids reassigning an &mut variable x when the referent (*x) has been borrowed. This most commonly arises when writing a loop that progressively "walks down" a data structure. Consider this function, which converts a linked list &mut List<T> into a Vec<&mut T>:

struct List<T> {
    value: T,
    next: Option<Box<List<T>>>,
}

fn to_refs<T>(mut list: &mut List<T>) -> Vec<&mut T> {
    let mut result = vec![];
    loop {
        result.push(&mut list.value);
        if let Some(n) = list.next.as_mut() {
            list = &mut n;
        } else {
            return result;
        }
    }
}

If we attempt to compile this, we get an error (actually, we get multiple errors):

error[E0506]: cannot assign to `list` because it is borrowed
  --> /Users/nmatsakis/tmp/x.rs:11:13
   |
9  |         result.push(&mut list.value);
   |                          ---------- borrow of `list` occurs here
10 |         if let Some(n) = list.next.as_mut() {
11 |             list = n;
   |             ^^^^^^^^ assignment to borrowed `list` occurs here

Specifically, what's gone wrong is that we borrowed list.value (or, more explicitly, (*list).value). The current borrow checker enforces the rule that when you borrow a path, you cannot assign to that path or any prefix of that path. In this case, that means you cannot assign to any of the following:

  • (*list).value
  • *list
  • list

As a result, the list = n assignment is forbidden. These rules make sense in some cases (for example, if list were of type List<T>, and not &mut List<T>, then overwriting list would also overwrite list.value), but not in the case where we cross a mutable reference.

As described in Issue #10520, there exist various workarounds for this problem. One trick is to move the &mut reference into a temporary variable that you won't have to modify:

fn to_refs<T>(mut list: &mut List<T>) -> Vec<&mut T> {
    let mut result = vec![];
    loop {
        let list1 = list;
        result.push(&mut list1.value);
        if let Some(n) = list1.next.as_mut() {
            list = &mut n;
        } else {
            return result;
        }
    }
}

When you frame the program this way, the borrow checker sees that (*list1).value is borrowed (not list). This does not prevent us from later assigning to list.

Clearly this workaround is annoying. The problem here, it turns out, is not specific to non-lexical lifetimes per se. Rather, it is that the rules which the borrow checker enforces when a path is borrowed are too strict and do not account for the indirection inherent in a borrowed reference. This RFC proposes a tweak to address that.

The rough outline of our solution

This RFC proposes a more flexible model for lifetimes. Whereas previously lifetimes were based on the abstract syntax tree, we now propose lifetimes that are defined via the control-flow graph. More specifically, lifetimes will be derived based on the MIR used internally in the compiler.

Intuitively, in the new proposal, the lifetime of a reference lasts only for those portions of the function in which the reference may later be used (where the reference is live, in compiler speak). This can range from a few sequential statements (as in problem case #1) to something more complex, such as covering one arm in a match but not the others (problem case #2).

However, in order to sucessfully type the full range of examples that we would like, we have to go a bit further than just changing lifetimes to a portion of the control-flow graph. We also have to take program location into account when defining subtyping. This is in contrast to how the compiler works today, where subtyping relations are "absolute". That is, in the current compiler, the type &'a () is a subtype of the type &'b () whenever 'a outlives 'b ('a: 'b), which means that 'a corresponds to a bigger portion of the function. Under this proposal, subtyping can instead be established at a particular point P. In that case, the lifetime 'a must only outlive those portions of 'b that are reachable from P.

The ideas in this RFC have been implemented in prototype form. This prototype includes a simplified control-flow graph that allows one to create the various kinds of region constraints that can arise and implements the region inference algorithm which then solves those constraints.

Detailed design

Layering the design

We describe the design in "layers":

  1. Initially, we will describe a basic design focused on control-flow within one function.
  2. Next, we extend the control-flow graph to better handle infinite loops.
  3. Next, we extend the design to handle dropck, and specifically the #[may_dangle] attribute introduced by RFC 1327.
  4. Next, we will extend the design to consider named lifetime parameters, like those in problem case 3.
  5. Finally, we give a brief description of the new version of the borrow checker.

Layer 0: Definitions

Before we can describe the design, we have to define the terms that we will be using. The RFC is defined in terms of a simplified version of MIR, eliding various details that don't introduce fundamental complexity.

Lvalues. A MIR "lvalue" is a path that leads to a memory location. The full MIR Lvalues are defined via a Rust enum and contain a number of knobs, most of which are not relevant for this RFC. We will present a simplified form of lvalues for now:

LV = x       // local variable
   | LV.f    // field access
   | *LV     // deref

The precedence of * is low, so *a.b.c will deref a.b.c; to deref just a, one would write (*a).b.c.

Prefixes. We say that the prefixes of an lvalue are all the lvalues you get by stripping away fields and derefs. The prefixes of *a.b would be *a.b, a.b, and a.

Control-flow graph. MIR is organized into a control-flow graph rather than an abstract syntax tree. It is created in the compiler by transforming the "HIR" (high-level IR). The MIR CFG consists of a set of basic blocks. Each basic block has a series of statements and a terminator. Statements that concern us in this RFC fall into three categories:

  • assignments like x = y; the RHS of such an assignment is called an rvalue. There are no compound rvalues, and hence each statement is a discrete action that executes instantaneously. For example, the Rust expression a = b + c + d would be compiled into two MIR instructions, like tmp0 = b + c; a = tmp0 + d;.
  • drop(lvalue) deallocates an lvalue, if there is a value in it; in the limit, this requires runtime checks (a pass in mir, called elaborate drops, performs this transformation).
  • StorageDead(x) deallocates the stack storage for x. These are used by LLVM to allow stack-allocated values to use the same stack slot (if their live storage ranges are disjoint). Ralf Jung's recent blog post has more details.

Layer 1: Control-flow within a function

Running Example

We will explain the design with reference to a running example, called Example 4. After presenting the design, we will apply it to the three problem cases, as well as a number of other interesting examples.

let mut foo: T = ...;
let mut bar: T = ...;
let p: &T;

p = &foo;
// (0)
if condition {
    print(*p);
    // (1)
    p = &bar;
    // (2)
}
// (3)
print(*p);
// (4)

The key point of this example is that the variable foo should only be considered borrowed at points 0 and 3, but not point 1. bar, in contrast, should be considered borrowed at points 2 and 3. Neither of them need to be considered borrowed at point 4, as the reference p is not used there.

We can convert this example into the control-flow graph that follows. Recall that a control-flow graph in MIR consists of basic blocks containing a list of discrete statements and a trailing terminator:

// let mut foo: i32;
// let mut bar: i32;
// let p: &i32;

A
[ p = &foo     ]
[ if condition ] ----\ (true)
       |             |
       |     B       v
       |     [ print(*p)     ]
       |     [ ...           ]
       |     [ p = &bar      ]
       |     [ ...           ]
       |     [ goto C        ]
       |             |
       +-------------/
       |
C      v
[ print(*p)    ]
[ return       ]

We will use a notation like Block/Index to refer to a specific statement or terminate in the control-flow graph. A/0 and B/4 refer to p = &foo and goto C, respectively.

What is a lifetime and how does it interact with the borrow checker

To start with, we will consider lifetimes as a set of points in the control-flow graph; later in the RFC we will extend the domain of these sets to include "skolemized" lifetimes, which correspond to named lifetime parameters declared on a function. If a lifetime contains the point P, that implies that references with that lifetime are valid on entry to P. Lifetimes appear in various places in the MIR representation:

  • The types of variables (and temporaries, etc) may contain lifetimes.
  • Every borrow expression has a designated lifetime.

We can extend our example 4 to include explicit lifetime names. There are three lifetimes that result. We will call them 'p, 'foo, and 'bar:

let mut foo: T = ...;
let mut bar: T = ...;
let p: &'p T;
//      --
p = &'foo foo;
//   ----
if condition {
    print(*p);
    p = &'bar bar;
    //   ----
}
print(*p);

As you can see, the lifetime 'p is part of the type of the variable p. It indicates the portions of the control-flow graph where p can safely be dereferenced. The lifetimes 'foo and 'bar are different: they refer to the lifetimes for which foo and bar are borrowed, respectively.

Lifetimes attached to a borrow expression, like 'foo and 'bar, are important to the borrow checker. Those correspond to the portions of the control-flow graph in which the borrow checker will enforce its restrictions. In this case, since both borrows are shared borrows (&), the borrow checker will prevent foo from being modified during 'foo and it will prevent bar from being modified during 'bar. If these had been mutable borrows (&mut), the borrow checker would have prevented all access to foo and bar during those lifetimes.

There are many valid choices one could make for 'foo and 'bar. This RFC however describes an inference algorithm that aims to pick the minimal lifetimes for each borrow which could possibly work. This corresponds to imposing the fewest restrictions we can.

In the case of example 4, therefore, we wish our algorithm to compute that 'foo is {A/1, B/0, C/0}, which notably excludes the points B/1 through B/4. 'bar should be inferred to the set {B/3, B/4, C/0}. The lifetime 'p will be the union of 'foo and 'bar, since it contains all the points where the variable p is valid.

Lifetime inference constraints

The inference algorithm works by analyzing the MIR and creating a series of constraints. These constraints obey the following grammar:

// A constraint set C:
C = true
  | C, (L1: L2) @ P    // Lifetime L1 will outlive Lifetime L2 from point P

// A lifetime L:
L = 'a
  | {P}

Here the terminal P represents a point in the control-flow graph, and the notation 'a refers to some named lifetime inference variable (e.g., 'p, 'foo or 'bar).

Once the constraints are created, the inference algorithm solves the constraints. This is done via fixed-point iteration: each lifetime variable begins as an empty set and we iterate over the constaints, repeatedly growing the lifetimes until they are big enough to satisfy all constraints.

(If you'd like to compare this to the prototype code, the file regionck.rs is responsible for creating the constraints, and infer.rs is responsible for solving them.)

Liveness

One key ingredient to understanding how NLL should work is understanding liveness. The term "liveness" derives from compiler analysis, but it's fairly intuitive. We say that a variable is live if the current value that it holds may be used later. This is very important to Example 4:

let mut foo: T = ...;
let mut bar: T = ...;
let p: &'p T = &foo;
// `p` is live here: its value may be used on the next line.
if condition {
    // `p` is live here: its value will be used on the next line.
    print(*p);
    // `p` is DEAD here: its value will not be used.
    p = &bar;
    // `p` is live here: its value will be used later.
}
// `p` is live here: its value may be used on the next line.
print(*p);
// `p` is DEAD here: its value will not be used.

Here you see a variable p that is assigned in the beginning of the program, and then maybe re-assigned during the if. The key point is that p becomes dead (not live) in the span before it is reassigned. This is true even though the variable p will be used again, because the value that is in p will not be used.

Traditional compiler compute liveness based on variables, but as a starting point for our lifetime inference algorithm, we wish to compute liveness for lifetimes. We can extend a variable-based analysis to lifetimes by saying that a lifetime L is live at a point P if there is some variable p which is live at P, and L appears in the type of p. (Later on, when we cover the dropck, we will use a more selective notion of liveness for lifetimes in which some of the lifetimes in a variable's type may be live while others are not.) So, in our running example, the lifetime 'p would be live at precisely the same points that p is live. The lifetimes 'foo and 'bar have no points where they are (directly) live, since they do not appear in the types of any variables.

  • However, this does not mean these lifetimes are irrelevant; as shown below, subtyping constraints introduced by subsequent analyses will eventually require 'foo and 'bar to outlive 'p.

Liveness-based constraints for lifetimes

The first set of constraints that we generate are derived from liveness. Specifically, if a lifetime L is live at the point P, then we will introduce a constraint like:

(L: {P}) @ P

(As we'll see later when we cover solving constraints, this constraint effectively just inserts P into the set for L. In fact, the prototype doesn't bother to materialize such constraints, instead just immediately inserting P into L.)

For our running example, this means that we would introduce the following liveness constraints:

('p: {A/1}) @ A/1
('p: {B/0}) @ B/0
('p: {B/3}) @ B/3
('p: {B/4}) @ B/4
('p: {C/0}) @ C/0

Subtyping

Whenever references are copied from one location to another, the Rust subtyping rules require that the lifetime of the source reference outlives the lifetime of the target location. As discussed earlier, in this RFC, we extend the notion of subtyping to be location-aware, meaning that we take into account the point where the value is being copied.

For example, at the point A/0, our running example contains a borrow expression p = &'foo foo. In this case, the borrow expression will produce a reference of type &'foo T, where T is the type of foo. This value is then assigned to p, which has the type &'p T. Therefore, we wish to require that &'foo T be a subtype of &'p T. Moreover, this relation needs to hold at the point A/1 -- the successor of the point A/0 where the assignment occurs (this is because the new value of p is first visible in A/1). We write that subtyping constraint as follows:

(&'foo T <: &'p T) @ A/1

The standard Rust subtyping rules (two examples of which are given below) can then "break down" this subtyping rule into the lifetime constraints we need for inference:

(T_a <: T_b) @ P
('a: 'b) @ P      // <-- a constraint for our inference algorithm
------------------------
(&'a T_a <: &'b T_b) @ P

(T_a <: T_b) @ P
(T_b <: T_a) @ P  // (&mut T is invariant)
('a: 'b) @ P      // <-- another constraint
------------------------
(&'a mut T_a <: &'b mut T_b) @ P

In the case of our running example, we generate the following subtyping constraints:

(&'foo T <: &'p T) @ A/1
(&'bar T <: &'p T) @ B/3

These can be converted into the following lifetime constraints:

('foo: 'p) @ A/1
('bar: 'p) @ B/3

Reborrow constraints

There is one final source of constraints. It frequently happens that we have a borrow expression that "reborrows" the referent of an existing reference:

let x: &'x i32 = ...;
let y: &'y i32 = &*x;

In such cases, there is a connection between the lifetime 'y of the borrow and the lifetime 'x of the original reference. In particular, 'x must outlive 'y ('x: 'y). In simple cases like this, the relationship is the same regardless of whether the original reference x is a shared (&) or mutable (&mut) reference. However, in more complex cases that involve multiple dereferences, the treatment is different. In particular, for any subsequent chain of dereferenced mutable references, it is important that all of these references must outlive the borrow; in general, this requires generating multiple reborrow constraints.

Supporting prefixes. To define the reborrow constraints, we first introduce the idea of supporting prefixes -- this definition will be useful in a few places. The supporting prefixes for an lvalue are formed by stripping away fields and derefs, except that we stop when we reach the deref of a shared reference. Inituitively, shared references are different because they are Copy -- and hence one could always copy the shared reference into a temporary and get an equivalent path from which to start the remainder of the chain of fields and derefs. In particular, there is no need for the derefs used to obtain the shared reference to outlive the resulting borrow. Here are some examples of supporting prefixes:

let r: (&(i32, i64), (f32, f64));

// The path (*r.0).1 has type `i64` and supporting prefixes:
// - (*r.0).1
// - *r.0

// The path r.1.0 has type `f32` and supporting prefixes:
// - r.1.0
// - r.1
// - r

let m: (&mut (i32, i64), (f32, f64));

// The path (*m.0).1 has type `i64` and supporting prefixes:
// - (*m.0).1
// - *m.0
// - *m
// - m

Reborrow constraints. Consider the case where we have a borrow (shared or mutable) of some lvalue lv_b for the lifetime 'b:

lv_l = &'b lv_b      // or:
lv_l = &'b mut lv_b

In that case, we compute the supporting prefixes of lv_b, and find every deref lvalue *lv in the set where lv is a reference with lifetime 'a. We then add a constraint ('a: 'b) @ P, where P is the point following the borrow (that's the point where the borrow takes effect).

Let's look at some examples. In each case, we will link to the corresponding test from the prototype implementation.

Example 1. To see why this rule is needed, let's first consider a simple example involving a single reference:

let mut foo: i32     = 22;
let r_a: &'a mut i32 = &'a mut foo;
let r_b: &'b mut i32 = &'b mut *r_a;
...
use(r_b);

In this case, the supporting prefixes of *r_a are *r_a and r_a (because r_a is a mutable reference, we recurse). Only one of those, *r_a, is a deref lvalue, and the reference r_a being dereferenced has the lifetime 'a. We would add the constraint that 'a: 'b, thus ensuring that foo is considered borrowed so long as r_b is in use. Without this constraint, the lifetime 'a would end after the second borrow, and hence foo would be considered unborrowed, even though *r_b could still be used to access foo.

Example 2. Consider now a case with a double indirection:

let mut foo: i32     = 22;
let mut r_a: &'a i32 = &'a foo;
let r_b: &'b &'a i32 = &'b r_a;
let r_c: &'c i32     = &'c **r_b;
// What is considered borrowed here?
use(r_c);

Just as before, it is important that, so long as r_c is in use, foo is considered borrowed. However, what about the variable r_a: should it considered borrowed? The answer is no: once r_c is initialized, the value of r_a is no longer important, and it would be fine to (for example) overwrite r_a with a new value, even as foo is still considered borrowed. This result falls out from our reborrowing rules: the supporting paths of **r_b is just **r_b. We do not add any more paths because this path is already a dereference of *r_b, and *r_b has has (shared reference) type &'a i32. Therefore, we would add one reborrow constraint: that 'a: 'c. This constraint ensures that as long as r_c is in use, the borrow of foo remains in force, but the borrow of r_a (which has the lifetime 'b) can expire.

Example 3. The previous example showed how a borrow of a shared reference can expire once it has been dereferenced. With mutable references, however, this is not safe. Consider the following example:

let foo = Foo { ... };
let p: &'p mut Foo = &mut foo;
let q: &'q mut &'p mut Foo = &mut p;
let r: &'r mut Foo = &mut **q;
use(*p); // <-- This line should result in an ERROR
use(r);

The key point here is that we create a reference r by reborrowing **q; r is then later used in the final line of the program. This use of r must extend the lifetime of the borrows used to create both p and q. Otherwise, one could access (and mutate) the same memory through both *r and *p. (In fact, the real rustc did in its early days have a soundness bug much like this one.)

Because dereferencing a mutable reference does not stop the supporting prefixes from being enumerated, the supporting prefixes of **q are **q, *q, and q. Therefore, we add two reborrow constraints: 'q: 'r and 'p: 'r, and hence both borrows are indeed considered in scope at the line in question.

As an alternate way of looking at the previous example, consider it like this. To create the mutable reference p, we get a "lock" on foo (that lasts so long as p is in use). We then take a lock on the mutable reference p to create q; this lock must last for as long as q is in use. When we create r by borrowing **q, that is the last direct use of q -- so you might think we can release the lock on p, since q is no longer in (direct) use. However, that would be unsound, since then r and *p could both be used to access the same memory. The key is to recognize that r represents an indirect use of q (and q in turn is an indirect use of p), and hence so long as r is in use, p and q must also be considered "in use" (and hence their "locks" still enforced).

Solving constraints

Once the constraints are created, the inference algorithm solves the constraints. This is done via fixed-point iteration: each lifetime variable begins as an empty set and we iterate over the constaints, repeatedly growing the lifetimes until they are big enough to satisfy all constraints.

The meaning of a constraint like ('a: 'b) @ P is that, starting from the point P, the lifetime 'a must include all points that are reachable without leaving the lifetime 'b. The implementation does a depth-first search starting from P; the search stops if we exit the lifetime 'b. Otherwise, for each point we find, we add it to 'a.

In our example, the full set of constraints is:

('foo: 'p) @ A/1
('bar: 'p) @ B/3
('p: {A/1}) @ A/1
('p: {B/0}) @ B/0
('p: {B/3}) @ B/3
('p: {B/4}) @ B/4
('p: {C/0}) @ C/0

Solving these constraints results in the following lifetimes, which are precisely the answers we expected:

'p   = {A/1, B/0, B/3, B/4, C/0}
'foo = {A/1, B/0, C/0}
'bar = {B/3, B/4, C/0}

Intuition for why this algorithm is correct

For the algorithm to be correct, there is a critical invariant that we must maintain. Consider some path H that is borrowed with lifetime L at a point P to create a reference R; this reference R (or some copy/move of it) is then later dereferenced at some point Q.

We must ensure that the reference has not been invalidated: this means that the memory which was borrowed must not have been freed by the time we reach Q. If the reference R is a shared reference (&T), then the memory must also not have been written (modulo UnsafeCell). If the reference R is a mutable reference (&mut T), then the memory must not have been accessed at all, except through the reference R. To guarantee these properties, we must prevent actions that might affect the borrowed memory for all of the points between P (the borrow) and Q (the use).

This means that L must at least include all the points between P and Q. There are two cases to consider. First, the case where the access at point Q occurs through the same reference R that was created by the borrow:

R = &H; // point P
...
use(R); // point Q

In this case, the variable R will be live on all the points between P and Q. The liveness-based rules suffice for this case: specifically, because the type of R includes the lifetime L, we know that L must include all the points between P and Q, since R is live there.

The second case is when the memory referenced by R is accessed, but through an alias (or move):

R = &H;  // point P
R2 = R;  // last use of R, point A
...
use(R2); // point Q

In this case, the liveness rules alone do not suffice. The problem is that the R2 = R assignment may well be the last use of R, and so the variable R is dead at this point. However, the value in R will still be dereferenced later (through R2), and hence we want the lifetime L to include those points. This is where the subtyping constraints come into play: the type of R2 includes a lifetime L2, and the assignment R2 = R will establish an outlives constraint (L: L2) @ A between L and L2. Moreover, this new variable R2 must be live between the assignment and the ultimate use (that is, along the path A...Q). Putting these two facts together, we see that L will ultimately include the points from P to A (because of the liveness of R) and the points from A to Q (because the subtyping requirement propagates the liveness of R2).

Note that it is possible for these lifetimes to have gaps. This can occur when the same variable is used and overwritten multiple times:

let R: &L i32;
let R2: &L2 i32;

R = &H1; // point P1
R2 = R;  // point A1
use(R2); // point Q1
...
R2 = &H2; // point P2
use(R2);  // point Q2

In this example, the liveness constraints on R2 will ensure that L2 (the lifetime in its type) includes Q1 and Q2 (because R2 is live at those two points), but not the "..." nor the points P1 or P2. Note that the subtyping relationship ((L: L2) @ A1)) at A1 here ensures that L also includes Q1, but doesn't require that L includes Q2 (even though L2 has point Q2). This is because the value in R2 at Q2 cannot have come from the assignment at A1; if it could have done, then either R2 would have to be live between A1 and Q2 or else there would be a subtyping constraint.

Other examples

Let us work through some more examples. We begin with problem cases #1 and #2 (problem case #3 will be covered after we cover named lifetimes in a later section).

Problem case #1.

Translated into MIR, the example will look roughly as follows:

let mut data: Vec<i32>;
let slice: &'slice mut i32;
START {
    data = ...;
    slice = &'borrow mut data;
    capitalize(slice);
    data.push('d');
    data.push('e');
    data.push('f');
}

The constraints generated will be as follows:

('slice: {START/2}) @ START/2
('borrow: 'slice) @ START/2

Both 'slice and 'borrow will therefore be inferred to START/2, and hence the accesses to data in START/3 and the following statements are permitted.

Problem case #2.

Translated into MIR, the example will look roughly as follows (some irrelevant details are elided). Note that the match statement is translated into a SWITCH, which tests the variant, and a "downcast", which lets us extract the contents out from the Some variant (this operation is specific to MIR and has no Rust equivalent, other than as part of a match).

let map: HashMap<K,V>;
let key: K;
let tmp0: &'tmp0 mut HashMap<K,V>;
let tmp1: &K;
let tmp2: Option<&'tmp2 mut V>;
let value: &'value mut V;

START {
/*0*/ map = ...;
/*1*/ key = ...;
/*2*/ tmp0 = &'map mut map;
/*3*/ tmp1 = &key;
/*4*/ tmp2 = HashMap::get_mut(tmp0, tmp1);
/*5*/ SWITCH tmp2 { None => NONE, Some => SOME }
}

NONE {
/*0*/ ...
/*1*/ goto EXIT;
}

SOME {
/*0*/ value = tmp2.downcast<Some>.0;
/*1*/ process(value);
/*2*/ goto EXIT;
}

EXIT {
}

The following liveness constraints are generated:

('tmp0: {START/3}) @ START/3
('tmp0: {START/4}) @ START/4
('tmp2: {SOME/0}) @ SOME/0
('value: {SOME/1}) @ SOME/1

The following subtyping-based constraints are generated:

('map: 'tmp0) @ START/3
('tmp0: 'tmp2) @ START/5
('tmp2: 'value) @ SOME/1

Ultimately, the lifetime we are most interested in is 'map, which indicates the duration for which map is borrowed. If we solve the constraints above, we will get:

'map == {START/3, START/4, SOME/0, SOME/1}
'tmp0 == {START/3, START/4, SOME/0, SOME/1}
'tmp2 == {SOME/0, SOME/1}
'value == {SOME/1}

These results indicate that map can be mutated in the None arm; map could also be mutated in the Some arm, but only after process() is called (i.e., starting at SOME/2). This is the desired result.

Example 4, invariant

It's worth looking at a variant of our running example ("Example 4"). This is the same pattern as before, but instead of using &'a T references, we use Foo<'a> references, which are invariant with respect to 'a. This means that the 'a lifetime in a Foo<'a> value cannot be approximated (i.e., you can't make it shorter, as you can with a normal reference). Usually invariance arises because of mutability (e.g., Foo<'a> might have a field of type Cell<&'a ()>). The key point here is that invariance actually makes no difference at all the outcome. This is true because of location-based subtyping.

let mut foo: T = ...;
let mut bar: T = ...;
let p: Foo<'a>;

p = Foo::new(&foo);
if condition {
    print(*p);
    p = Foo::new(&bar);
}
print(*p);

Effectively, we wind up with the same constraints as before, but where we only had 'foo: 'p/'bar: 'p constraints before (due to subtyping), we now also have 'p: 'foo and 'p: 'bar constraints:

('foo: 'p) @ A/1
('p: 'foo) @ A/1
('bar: 'p) @ B/3
('p: 'bar) @ B/3
('p: {A/1}) @ A/1
('p: {B/0}) @ B/0
('p: {B/3}) @ B/3
('p: {B/4}) @ B/4
('p: {C/0}) @ C/0

The key point is that the new constraints don't affect the final answer: the new constraints were already satisfied with the older answer.

vec-push-ref

In previous iterations of this proposal, the location-aware subtyping rules were replaced with transformations such as SSA form. The vec-push-ref example demonstrates the value of location-aware subtyping in contrast to these approaches.

let foo: i32;
let vec: Vec<&'vec i32>;
let p: &'p i32;

foo = ...;
vec = Vec::new();
p = &'foo foo;
if true {
    vec.push(p);
} else {
    // Key point: `foo` not borrowed here.
    use(vec);
}

This can be converted to control-flow graph form:

block START {
    v = Vec::new();
    p = &'foo foo;
    goto B C;
}

block B {
    vec.push(p);
    goto EXIT;
}

block C {
    // Key point: `foo` not borrowed here
    use(vec);
    goto EXIT;
}

block EXIT {
}

Here the relations from liveness are:

('vec: {START/1}) @ START/1
('vec: {START/2}) @ START/2
('vec: {B/0}) @ B/0
('vec: {C/0}) @ C/0
('p: {START/2}) @ START/2
('p: {B/0}) @ B/0

Meanwhile, the call to vec.push(p) establishes this subtyping relation:

('p: 'vec) @ B/1
('foo: 'p) @ START/2

The solution is:

'vec = {START/1, START/2, B/0, C/0}
'p = {START/2, B/0}
'foo = {START/2, B/0}

What makes this example interesting is that the lifetime 'vec must include both halves of the if -- because it is used in both branches -- but 'vec only becomes "entangled" with the lifetime 'p on one path. Thus even though 'vec has to outlive 'p, 'p never winds up including the "else" branch thanks to location-aware subtyping.

Layer 2: Avoiding infinite loops

The previous design was described in terms of the "pure" MIR control-flow graph. However, using the raw graph has some undesirable properties around infinite loops. In such cases, the graph has no exit, which undermines the traditional definition of reverse analyses like liveness. To address this, when we build the control-flow graph for our functions, we will augment it with additional edges -- in particular, for every infinite loop (loop { }), we will add false "unwind" edges. This ensures that the control-flow graph has a final exit node (the success of the RETURN and RESUME nodes) that postdominates all other nodes in the graph.

If we did not add such edges, the result would also allow a number of surprising programs to type-check. For example, it would be possible to borrow local variables with 'static lifetime, so long as the function never returned:

fn main() {
    let x: usize;
    let y: &'static x = &x;
    loop { }
}

This would work because (as covered in detail under the borrow check section) the StorageDead(x) instruction would never be reachable, and hence any lifetime of borrow would be acceptable. This further leads to other surprising programs that still type-check, such as this example which uses an (incorrect, but declared as unsafe) API for spawning threads:

let scope = Scope::new();
let mut foo = 22;

unsafe {
    // dtor joins the thread
    let _guard = scope.spawn(&mut foo);
    loop {
        foo += 1;
    }
    // drop of `_guard` joins the thread
}

Without the unwind edges, this code would pass the borrowck, since the drop of _guard (and StorageDead instruction) is not reachable, and hence _guard is not considered live (after all, its destructor will indeed never run). However, this would permit the foo variable to be modified both during the infinite loop and by the thread launched by scope.spawn(), which was given access to an &mut foo reference (albeit one with a theoretically short lifetime).

With the false unwind edge, the compiler essentially always assumes that a destructor may run, since every scope may theoretically execute. This extends the &mut foo borrow given to scope.spawn() to cover the body of the loop, resulting in a borrowck error.

Layer 3: Accommodating dropck

MIR includes an action that corresponds to "dropping" a variable:

DROP(variable)

Note that while MIR supports general drops of any lvalue, at the point where this analysis is running, we are always dropping entire variables at a time. This operation executes the destructor for variable, effectively "de-initializing" the memory in which the value resides (if the variable -- or parts of the variable -- have already been dropped, then drop has no effect; this is not relevant to the current analysis).

Interestingly, in many cases dropping a value does not require that the lifetimes in the dropped value be valid. After all, dropping a reference of type &'a T or &'a mut T is defined as a no-op, so it does not matter if the reference points at valid memory. In cases like this, we say that the lifetime 'a may dangle. This is inspired by the C term "dangling pointer" which means a pointer to freed or invalid memory.

However, if that same reference is stored in the field of a struct which implements the Drop trait, when the struct may, during its destructor, access the referenced value, so it's very important that the reference be valid in that case. Put another way, if you have a value v of type Foo<'a> that implements Drop, then 'a typically cannot dangle when v is dropped (just as 'a would not be allowed to dangle for any other operation).

More generally, RFC 1327 defined specific rules for which lifetimes in a type may dangle during drop and which may not. We integrate those rules into our liveness analysis as follows: the MIR instruction DROP(variable) is not treated like other MIR instructions when it comes to liveness. In a sense, conceptually we run two distinct liveness analyses (in practice, the prototype uses two bits per variable):

  1. The first, which we've already seen, indicates when a variable's current value may be used in the future. This corresponds to "non-drop" uses of the variable in the MIR. Whenever a variable is live by this definition, all of the lifetimes in its type are live.
  2. The second, which we are adding now, indicates when a variable's current value may be dropped in the future. This corresponds to "drop" uses of the variable in the MIR. Whenever a variable is live in this sense, all of the lifetimes in its type except those marked as may-dangle are live.

Permitting lifetimes to dangle during drop is very important! In fact, it is essential to even the most basic non-lexical lifetime examples, such as Problem Case #1. After all, if we translate Problem Case #1 into MIR, we see that the reference slice will wind up being dropped at the end of the block:

let mut data: Vec<i32>;
let slice: &'slice mut i32;
START {
    ...
    slice = &'borrow mut data;
    capitalize(slice);
    data.push('d');
    data.push('e');
    data.push('f');
    DROP(slice);
    DROP(data);
}

This poses no problem for our analysis, however, because 'slice "may dangle" during the drop, and hence is not considered live.

Layer 4: Named lifetimes

Until now, we've only considered lifetimes that are confined to the extent of a function. Often, we want to reason about lifetimes that begin or end after the current function has ended. More subtly, we sometimes want to have lifetimes that sometimes begin and end in the current function, but which may (along some paths) extend into the caller. Consider Problem Case #3 (the corresponding test case in the prototype is the [get-default][] test):

fn get_default<'r,K,V:Default>(map: &'r mut HashMap<K,V>,
                               key: K)
                               -> &'r mut V {
    match map.get_mut(&key) { // -------------+ 'r
        Some(value) => value,              // |
        None => {                          // |
            map.insert(key, V::default()); // |
            //  ^~~~~~ ERROR               // |
            map.get_mut(&key).unwrap()     // |
        }                                  // |
    }                                      // |
}                                          // v

The get_mut function takes a mutable borrow on map; its return value in the Some(value) case is also a mutable borrow. When we translate this code into MIR, we get something like the following (this is "pseudo-MIR"):

block START {
  m1 = &'m1 mut *map;  // temporary created for `map.get_mut()` call
  v = Map::get_mut(m1, &key);
  switch v { SOME NONE };
}

block SOME {
  return = v.as<Some>.0; // assign to return value slot
  goto END;
}

block NONE {
  Map::insert(&*map, key, ...);
  m2 = &'m2 mut *map;  // temporary created for `map.get_mut()` call
  v = Map::get_mut(m2, &key);
  return = ... // "unwrap" of `v`
  goto END;
}

block END {
  return;
}

The key to this example is that the first borrow of map, with the lifetime 'm1, must extend to the end of the 'r, but only if we branch to SOME. Otherwise, it should end once we enter the NONE block.

To accommodate cases like this, we will extend the notion of a region so that it includes not only points in the control-flow graph, but also includes a (possibly empty) set of "end regions" for various named lifetimes. The end region for named lifetime 'r is denoted end('r). Such an end region can be understood semantically as referring to some portion of the caller's control-flow graph (actually, they could extend beyond the end of the caller, into the caller's caller, and so forth, but that doesn't concern us). Our extended notion of region might then be represented using the following struct (in pseudocode form):

struct Region {
  points: Set<Point>,
  end_regions: Set<NamedLifetime>,
}

In this case, when a type mentions a named lifetime, such as 'r, that can be represented by a region that includes:

  • the entire CFG,
  • and, the end region for that named lifetime (end('r)).

Furthermore, we can elaborate the set to include end('x) for every named lifetime 'x such that 'r: 'x. This is because, if 'r: 'x, then we know that 'r doesn't end up until 'x has already ended.

Finally, we must adjust our definition of subtyping to accommodate this amended definition of a region, which we do as follows. When we have an outlives relation

'b: 'a @ P

where the end point of the CFG is reachable from P without leaving 'a, the existing inference algorithm would simply add the end-point to 'b and stop. The new algorithm would also add any end regions that are included in 'a to 'b at that time. (Expressed less operationally, 'b only outlives 'a if it also includes the end-regions that 'a includes, presuming that the end point of the CFG is reachable from P). The reason that we require the end point of the CFG to be reachable is because otherwise the data never escapes the current function, and hence end('r) is not reachable (since end('r) only covers the code in callers that executes after the return).

NB: This part of the prototype is partially implemented. Issue #12 describes the current status and links to the in-progress PRs.

Layer 5: How the borrow check works

For the most part, the focus of this RFC is on the structure of lifetimes, but it's worth talking a bit about how to integrate these non-lexical lifetimes into the borrow checker. In particular, along the way, we'd like to fix two shortcomings of the borrow checker:

First, support nested method calls like vec.push(vec.len()). Here, the plan is to continue with the mut2 borrow solution proposed in RFC 2025. This RFC does not (yet) propose one of the type-based solutions described in RFC 2025, such as "borrowing for the future" or Ref2. The reasons why are discussed in the Alternatives section. For simplicity, this description of the borrow checker ignores RFC 2025. The extensions described here are fairly orthogonal to the changes proposed in RFC 2025, which in effect cause the start of a borrow to be delayed.

Second, permit variables containing mutable references to be modified, even if their referent is borrowed. This refers to the "Problem Case #4" described in the introduction; we wish to accept the original program.

Borrow checker phase 1: computing loans in scope

The first phase of the borrow checker computes, at each point in the CFG, the set of in-scope loans. A "loan" is represented as a tuple ('a, shared|uniq|mut, lvalue) indicating:

  1. the lifetime 'a for which the value was borrowed;
  2. whether this was a shared, unique, or mutable loan;
    • "unique" loans are exactly like mutable loans, but they do not permit mutation of their referents. They are used only in closure desugarings and are not part of Rust's surface syntax.
  3. the lvalue that was borrowed (e.g., x or (*x).foo).

The set of in-scope loans at each point is found via a fixed-point dataflow computation. We create a loan tuple from each borrow rvalue in the MIR (that is, every assignment statement like tmp = &'a b.c.d), giving each tuple a unique index i. We can then represent the set of loans that are in scope at a particular point using a bit-set and do a standard forward data-flow propagation.

For a statement at point P in the graph, we define the "transfer function" -- that is, which loans it brings into or out of scope -- as follows:

  • any loans whose region does not include P are killed;
  • if this is a borrow statement, the corresponding loan is generated;
  • if this is an assignment lv = <rvalue>, then any loan for some path P of which lv is a prefix is killed.

The last point bears some elaboration. This rule is what allows us to support cases like the one in Problem Case #4:

let list: &mut List<T> = ...;
let v = &mut (*list).value;
list = ...; // <-- assignment

At the point of the marked assignment, the loan of (*list).value is in-scope, but it does not have to be considered in-scope afterwards. This is because the variable list now holds a fresh value, and that new value has not yet been borrowed (or else we could not have produced it). Specifically, whenever we see an assignment lv = <rvalue> in MIR, we can clear all loans where the borrowed path lv_loan has lv as a prefix. (In our example, the assignment is to list, and the loan path (*list).value has list as a prefix.)

NB. In this phase, when there is an assignment, we always clear all loans that applied to the overwritten path; however, in some cases the assignment itself may be illegal due to those very loans. In our example, this would be the case if the type of list had been List<T> and not &mut List<T>. In such cases, errors will be reported by the next portion of the borrowck, described in the next section.

Borrow checker phase 2: reporting errors

At this point, we have computed which loans are in scope at each point. Next, we traverse the MIR and identify actions that are illegal given the loans in scope. Rather than go through every kind of MIR statement, we can break things down into two kinds of actions that can be performed:

  • Accessing an lvalue, which we categorize along two axes (shallow vs deep, read vs write)
  • Dropping an lvalue

For each of these kinds of actions, we will specify below the rules that determine when they are legal, given the set of loans L in scope at the start of the action. The second phase of the borrow check therefore consists of iterating over each statement in the MIR and checking, given the in-scope loans, whether the actions it performs are legal. Translating MIR statements into actions is mostly straightforward:

  • A StorageDead statement counts as a shallow write.
  • An assignment statement LV = RV is a shallow write to LV;
  • and, within the rvalue RV:
    • Each lvalue operand is either a deep read or a deep write action, depending on whether or not the type of the lvalue implements Copy.
      • Note that moves count as "deep writes".
    • A shared borrow &LV counts as a deep read.
    • A mutable borrow &mut LV counts as deep write.

There are a few interesting cases to keep in mind:

  • MIR models discriminants more precisely. They should be thought of as a distinct field when it comes to borrows.
  • In the compiler today, Box is still "built-in" to MIR. This RFC ignores that possibility and instead acts as though borrowed references (& and &mut) and raw pointers (*const and *mut) were the only sorts of pointers. It should be straight-forward to extend the text here to cover Box, though some questions arise around the handling of drop (see the section on drops for details).

Accessing an lvalue LV. When accessing an lvalue LV, there are two axes to consider:

  • The access can be SHALLOW or DEEP:
    • A shallow access means that the immediate fields reached at LV are accessed, but references or pointers found within are not dereferenced. Right now, the only access that is shallow is an assignment like x = ..., which would be a shallow write of x.
    • A deep access means that all data reachable through a given lvalue may be invalidated or accessed by this action.
  • The access can be a READ or WRITE:
    • A read means that the existing data may be read, but will not be changed.
    • A write means that the data may be mutated to new values or otherwise invalidated (for example, it could be de-initialized, as in a move operation).

"Deep" accesses are often deep because they create and release an alias, in which case the "deep" qualifier reflects what might happen through that alias. For example, if you have let x = &mut y, that is considered a deep write of y, even though the actual borrow doesn't do anything at all, we create a mutable alias x that can be used to mutate anything reachable from y. A move let x = y is similar: it writes to the shallow content of y, but then -- via the new name x -- we can access all other content accessible through y.

The pseudocode for deciding when an access is legal looks like this:

fn access_legal(lvalue, is_shallow, is_read) {
    let relevant_borrows = select_relevant_borrows(lvalue, is_shallow);

    for borrow in relevant_borrows {
        // shared borrows like `&x` still permit reads from `x` (but not writes)
        if is_read && borrow.is_read { continue; }
        
        // otherwise, report an error, because we have an access
        // that conflicts with an in-scope borrow
        report_error();
    }
}

As you can see, it works in two steps. First, we enumerate a set of in-scope borrows that are relevant to lvalue -- this set is affected by whether this is a "shallow" or "deep" action, as will be described shortly. Then, for each such borrow, we check if it conflicts with the action (i.e.,, if at least one of them is potentially writing), and, if so, we report an error.

For shallow accesses to the path lvalue, we consider borrows relevant if they meet one of the following criteria:

  • there is a loan for the path lvalue;
    • so: writing a path like a.b.c is illegal if a.b.c is borrowed
  • there is a loan for some prefix of the path lvalue;
    • so: writing a path like a.b.c is illegal if a or a.b is borrowed
  • lvalue is a shallow prefix of the loan path
    • shallow prefixes are found by stripping away fields, but stop at any dereference
    • so: writing a path like a is illegal if a.b is borrowed
    • but: writing a is legal if *a is borrowed, whether or not a is a shared or mutable reference

For deep accesses to the path lvalue, we consider borrows relevant if they meet one of the following criteria:

  • there is a loan for the path lvalue;
    • so: reading a path like a.b.c is illegal if a.b.c is mutably borrowed
  • there is a loan for some prefix of the path lvalue;
    • so: reading a path like a.b.c is illegal if a or a.b is mutably borrowed
  • lvalue is a supporting prefix of the loan path
    • supporting prefixes were defined earlier
    • so: reading a path like a is illegal if a.b is mutably borrowed, but -- in contrast with shallow accesses -- reading a is also illegal if *a is mutably borrowed

Dropping an lvalue LV. Dropping an lvalue can be treated as a DEEP WRITE, like a move, but this is overly conservative. The rules here are under active development, see #40.

How We Teach This

Terminology

In this RFC, I've opted to continue using the term "lifetime" to refer to the portion of the program in which a reference is in active use (or, alternatively, to the "duration of a borrow"). As the intro to the RFC makes clear, this terminology somewhat conflicts with an alternative usage, in which lifetime refers to the dynamic extent of a value (what we call the "scope"). I think that -- if we were starting over -- it might have been preferable to find an alternative term that is more specific. However, it would be rather difficult to try and change the term "lifetime" at this point, and hence this RFC does not attempt do so. To avoid confusion, however, it seems best if the error messages result from the region and borrow check avoid the term lifetime where possible, or use qualification to make the meaning more clear.

Leveraging intuition: framing errors in terms of points

Part of the reason that Rust currently uses lexical scopes to determine lifetimes is that it was thought that they would be simpler for users to reason about. Time and experience have not borne this hypothesis out: for many users, the fact that borrows are "artificially" extended to the end of the block is more surprising than not. Furthermore, most users have a pretty intuitive understanding of control flow (which makes sense: you have to, in order to understand what your program will do).

We therefore propose to leverage this intution when explaining borrow and lifetime errors. To the extent possible, we will try to explain all errors in terms of three points:

  • The point where the borrow occurred (B).
  • The point where the resulting reference is used (U).
  • An intervening point that might have invalidated the reference (A).

We should select three points such that B can reach A and A can reach U. In general, the approach is to describe the errors in "narrative" form:

  • First, value is borrowed occurs.
  • Next, the action occurs, invalidating the reference.
  • Finally, the next use occcurs, after the reference has been invalidated.

This approach is similar to what we do today, but we often neglect to mention this third point, where the next use occurs. Note that the "point of error" remains the second action -- that is, the error, conceptually, is to perform an invalidating action in between two uses of the reference (rather than, say, to use the reference after an invalidating action). This actually reflects the definition of undefined behavior more accurately (that is, performing an illegal write is what causes undefined behavior, but the write is illegal because of the latter use).

To see the difference, consider this erroneous program:

fn main() {
    let mut i = 3;
    let x = &i;
    i += 1;
    println!("{}", x);
}

Currently, we emit the following error:

error[E0506]: cannot assign to `i` because it is borrowed
 --> <anon>:4:5
   |
 3 |     let x = &i;
   |              - borrow of `i` occurs here
 4 |     i += 1;
   |     ^^^^^^ assignment to borrowed `i` occurs here

Here, the points B and A are highlighted, but not the point of use U. Moreover, the "blame" is placed on the assignment. Under this RFC, we would display the error as follows:

error[E0506]: cannot write to `i` while borrowed
 --> <anon>:4:5
   |
 3 |     let x = &i;
   |              - (shared) borrow of `i` occurs here
 4 |     i += 1;
   |     ^^^^^^ write to `i` occurs here, while borrow is still active
 5 |     println!("{}", x);
   |                    - borrow is later used here

Another example, this time using a match:

fn main() {
    let mut x = Some(3);
    match &mut x {
        Some(i) => {
            x = None;
            *i += 1;
        }
        None => {
            x = Some(0); // OK
        }
    }
}

The error might be:

error[E0506]: cannot write to `x` while borrowed
 --> <anon>:4:5
   |
 3 |     match &mut x {
   |           ------ (mutable) borrow of `x` occurs here
 4 |         Some(i) => {
 5 |              x = None;
   |              ^^^^^^^^ write to `x` occurs here, while borrow is still active
 6 |              *i += 1;
   |              -- borrow is later used here
   |

(Note that the assignment in the None arm is not an error, since the borrow is never used again.)

Some special cases

There are some cases where the three points are not all visible in the user syntax where we may need some careful treatment.

Drop as last use

There are times when the last use of a variable will in fact be its destructor. Consider an example like this:

struct Foo<'a> { field: &'a u32 }
impl<'a> Drop for Foo<'a> { .. }

fn main() {
    let mut x = 22;
    let y = Foo { field: &x };
    x += 1;
}

This code would be legal, but for the destructor on y, which will implicitly execute at the end of the enclosing scope. The error message might be shown as follows:

error[E0506]: cannot write to `x` while borrowed
 --> <anon>:4:5
   |
 6 |     let y = Foo { field: &x };
   |                          -- borrow of `x` occurs here
 7 |     x += 1;
   |     ^ write to `x` occurs here, while borrow is still active
 8 | }
   | - borrow is later used here, when `y` is dropped

Method calls

One example would be method calls:

fn main() {
    let mut x = vec![1];
    x.push(x.pop().unwrap());
}

We propose the following error for this sort of scenario:

error[E0506]: cannot write to `x` while borrowed
 --> <anon>:4:5
   |
 3 |     x.push(x.pop().unwrap());
   |     - ---- ^^^^^^^^^^^^^^^^
   |     | |    write to `x` occurs here, while borrow is still in active use
   |     | borrow is later used here, during the call
   |     `x` borrowed here

If you are not using a method, the error would look slightly different, but be similar in concept:

error[E0506]: cannot assign to `x` because it is borrowed
 --> <anon>:4:5
   |
 3 |     Vec::push(&mut x, x.pop().unwrap());
   |     --------- ------  ^^^^^^^^^^^^^^^^
   |     |         |       write to `x` occurs here, while borrow is still in active use
   |     |         `x` borrowed here
   |     borrow is later used here, during the call

We can detect this scenario in MIR readily enough by checking when the point of use turns out to be a "call" terminator. We'll have to tweak the spans to get everything to look correct, but that is easy enough.

Closures

As today, when the initial borrow is part of constructing a closure, we wish to highlight not only the point where the closure is constructed, but the point within the closure where the variable in question is used.

Borrowing a variable for longer than its scope

Consider this example:

let p;
{
    let x = 3;
    p = &x;
}
println!("{}", p);

In this example, the reference p refers to x with a lifetime that exceeds the scope of x. In short, that portion of the stack will be popped with p still in active use. In today's compiler, this is detected during the borrow checker by a special check that computes the "maximal scope" of the path being borrowed (x, here). This makes sense in the existing system since lifetimes and scopes are expressed in the same units (portions of the AST). In the newer, non-lexical formulation, this error would be detected somewhat differently. As described earlier, we would see that a StorageDead instruction frees the slot for x while p is still in use. We can thus present the error in the same "three-point style":

error[E0506]: variable goes out of scope while still borrowed
 --> <anon>:4:5
   |
 3 |     p = &x;
   |          - `x` borrowed here
 4 | }
   | ^ `x` goes out of scope here, while borrow is still in active use
 5 | println!("{}", p);
   |                - borrow used here, after invalidation

Errors during inference

The remaining set of lifetime-related errors come about primarily due to the interaction with function signatures. For example:

impl Foo {
    fn foo(&self, y: &u8) -> &u8 {
        x
    }
}

We already have work-in-progress on presenting these sorts of errors in a better way (see issue 42516 for numerous examples and details), all of which should be applicable here. In short, the name of the game is to identify patterns and suggest changes to improve the function signature to match the body (or at least diagnose the problem more clearly).

Whenever possible, we should leverage points in the control-flow and try to explain errors in "narrative" form.

Drawbacks

There are very few drawbacks to this proposal. The primary one is that the rules for the system become more complex. However, this permits us to accept a large number of more programs, and so we expect that using Rust will feel simpler. Moreover, experience has shown that -- for many users -- the current scheme of tying reference lifetimes to lexical scoping is confusing and surprising.

Alternatives

Alternative formulations of NLL

During the runup to this RFC, a number of alternate schemes and approaches to describing NLL were tried and discarded.

RFC 396. RFC 396 defined lifetimes to be a "prefix" of the dominator tree -- roughly speaking, a single-entry, multiple-exit region of the control-flow graph. Unlike our system, this definition did not permit gaps or holes in a lifetime. Ensuring continuous lifetimes was meant to guarantee soundness; in this RFC, we use the liveness constraints to achieve a similar effect. This more flexible setup allows us to handle cases like Problem Case #3, which RFC 396 would not have accepted. RFC 396 also did not cover dropck and a number of other complications.

SSA or SSI transformation. Rather than incorporating the "current location" into the subtype check, we also considered formulations that first applied an SSA transformation to the input program, and then gave each of those variables a distinct type. This does allow some examples to type-check that wouldn't otherwise, but it is not flexible enough for the vec-push-ref example covered earlier.

Using SSA also introduces other complications. Among other things, Rust permits variables and temporaries to be borrowed and mutated indirectly (e.g., via &mut). If we were to apply SSA to MIR in a naive fashion, then, it would ignore these assignments when creating numberings. For example:

let mut x = 1;      // x0, has value 1
let mut p = &mut x; // p0
*p += 1;
use(x);             // uses `x0`, but it now has value 2

Here, the value of x0 changed due to a write from p. Thus this is not a true SSA form. Normally, SSA transformations achieve this by making local variables like x and p be pointers into stack slots, and then lifting those stack slots into locals when safe. MIR was intentionally not done using SSA form precisely to avoid the need for such contortions (we can leave that to the optimizing backend).

Type per program point. Going further than SSA, one can accommodate vec-push-ref through a scheme that gives each variable a distinct type at each point in the CFG (similar to what Ericson2314 describes in the stateful MIR for Rust) and applies transformations to the lifetimes on every edge. During the rustc design sprint, the compiler team also enumerated such a design. The author believes this RFC to be a roughly equivalent analysis, but with an alternative, more familiar formulation that still uses one type per variable (rather than one type per variable per point).

There are several advantages to the design enumerated here. For one thing, it involves far fewer inference variables (if each variable has many types, each of those types needs distinct inference variables at each point) and far fewer constraints (we don't need constraints just for connecting the type of a variable between distinct points). It is also a more natural fit for the surface language, in which variables have a single type.

Different "lifetime roles"

In the discussion about nested method calls (RFC 2025, and the discussions that led up to it), there were various proposals that were aimed at accepting the naive desugaring of a call like vec.push(vec.len()):

let tmp0 = &mut vec;
let tmp1 = vec.len(); // does a shared borrow of vec
Vec::push(tmp0, tmp1);

The alternatives to RFC 2025 were focused on augmenting the type of references to have distinct "roles" -- the most prominent such proposal was Ref2<'r, 'w>, in which mutable references change to have two distinct lifetimes, a "read" lifetime ('r) and a "write" lifetime ('w), where read encompasses the entire span of the reference, but write only contains those points where writes are occuring. This RFC does not attempt to change the approach to nested method calls, rather continuing with the RFC 2025 approach (which affects only the borrowck handling). However, if we did wish to adopt a Ref2-style approach in the future, it could be done backwards compatibly, but it would require modifying (for example) the liveness requirements. For example, currently, if a variable x is live at some point P, then all lifetimes in the type of x must contain P -- but in the Ref2 approach, only the read lifetime would have to contain P. This implies that lifetimes are treated differently depending on their "role". It seems like a good idea to isolate such a change into a distinct RFC.

Unresolved questions

None at present.

Appendix: What this proposal will not fix

It is worth discussing a few kinds of borrow check errors that the current RFC will not eliminate. These are generally errors that cross procedural boundaries in some form or another.

Closure desugaring. The first kind of error has to do with the closure desugaring. Right now, closures always capture local variables, even if the closure only uses some sub-path of the variable internally:

let get_len = || self.vec.len(); // borrows `self`, not `self.vec`
self.vec2.push(...); // error: self is borrowed

This was discussed on an internals thread. It is possible to fix this by making the closure desugaring smarter.

Disjoint fields across functions. Another kind of error is when you have one method that only uses a field a and another that only uses some field b; right now, you can't express that, and hence these two methods cannot be used "in parallel" with one another:

impl Foo {
    fn get_a(&self) -> &A { &self.a }
    fn inc_b(&mut self) { self.b.value += 1; }
    fn bar(&mut self) {
        let a = self.get_a();
        self.inc_b(); // Error: self is already borrowed
        use(a);
    }
}

The fix for this is to refactor so as to expose the fact that the methods operate on disjoint data. For example, one can factor out the methods into methods on the fields themselves:

fn bar(&mut self) {
    let a = self.a.get();
    self.b.inc();
    use(a);
}

This way, when looking at bar() alone, we see borrows of self.a and self.b, rather than two borrows of self. Another technique is to introduce "free functions" (e.g., get(&self.a) and inc(&mut self.b)) that expose more clearly which fields are operated upon, or to inline the method bodies. This is a non-trivial bit of design and is out of scope for this RFC. See this comment on an internals thread for further thoughts.

Self-referential structs. The final limitation we are not fixing yet is the inability to have "self-referential structs". That is, you cannot have a struct that stores, within itself, an arena and pointers into that arena, and then move that struct around. This comes up in a number of settings. There are various workarounds: sometimes you can use a vector with indices, for example, or the owning_ref crate. The latter, when combined with associated type constructors, might be an adequate solution for some uses cases, actually (it's basically a way of modeling "existential lifetimes" in library code). For the case of futures especially, the ?Move RFC proposes another lightweight and interesting approach.

Endnotes

1. Scopes always correspond to blocks with one exception: the scope of a temporary value is sometimes the enclosing statement.