- Feature Name: nll
- Start Date: 2017-08-02
- RFC PR: rust-lang/rfcs#2094
- Rust Issue: rust-lang/rust#43234
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:
- The lifetime of a reference, corresponding to the span of time in which that reference is used.
- 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 todata.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:Hash+Eq+Copy,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:Hash+Eq+Copy,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:Hash+Eq+Copy,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:Hash+Eq,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 = 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 = 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 successfully 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 location into account when doing subtyping checks. 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”:
- Initially, we will describe a basic design focused on control-flow within one function.
- Next, we extend the control-flow graph to better handle infinite loops.
- Next, we extend the design to handle dropck, and specifically the
#[may_dangle]
attribute introduced by RFC 1327. - Next, we will extend the design to consider named lifetime parameters, like those in problem case 3.
- Finally, we give a brief description 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 expressiona = b + c + d
would be compiled into two MIR instructions, liketmp0 = 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 forx
. 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 mut 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 mut 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 terminator 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 mut 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 outlives Lifetime L2 at 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 constraints, 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 mut 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 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.
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. 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.0
// - 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 (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 constraints, 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 in 'b
that
are reachable from the point P. 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 'p
has to outlive 'vec
, '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):
- 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.
- 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
When we translate this 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. We denote these as end('r)
for some named region
'r
. The region end('r)
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). This new region might then
be denoted as the following (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:
- the lifetime
'a
for which the value was borrowed; - 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.
- 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 whichlv
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 toLV
; - 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.
- Each lvalue operand is either a deep read or a deep write action, depending
on whether or not the type of the lvalue implements
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 coverBox
, 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 ofx
. - A deep access means that all data reachable through a given lvalue may be invalidated or accessed by this action.
- 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
- 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 ifa.b.c
is borrowed
- so: writing a path like
- there is a loan for some prefix of the path
lvalue
;- so: writing a path like
a.b.c
is illegal ifa
ora.b
is borrowed
- so: writing a path like
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 ifa.b
is borrowed - but: writing
a
is legal if*a
is borrowed, whether or nota
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 ifa.b.c
is mutably borrowed
- so: reading a path like
- there is a loan for some prefix of the path
lvalue
;- so: reading a path like
a.b.c
is illegal ifa
ora.b
is mutably borrowed
- so: reading a path like
lvalue
is a supporting prefix of the loan path- supporting prefixes were defined earlier
- so: reading a path like
a
is illegal ifa.b
is mutably borrowed, but – in contrast with shallow accesses – readinga
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 occurs, 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 larger number of 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
occurring. 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.