Published: 2019-06-05

The Lifetimes in this post is based on the 2018 edition, neither 2015 edition nor the new Borrow checker will be applied in the furture1.

In fact, you can just go to read the RFC to understand how the borrowck work currently. And in this post, I want to describe the Lifetimes in a different way that what I’m learned from the RFC.

Audience: You may already have read the Rust Book. Nice if you took a compiler course.

By the way, I have speaked on this topic in two meetups; Cat system workshop and Rust taiwan meetup, you can find these two presentation at slide1 and slide2, respectively.

## Overview of Borrow checker

The whole borrowck can divided into these four steps.

1. Building Liveness2
2. Solving Constraints
3. Compute Loans in Scope

In the first two steps, it will compute the Lifetimes. Then bring this information to construct the Loan and compute which Loans are live at which points in CFG in the third step. In the forth, it will traverse through the CFG to check whether each action is legal or not, just depend on the Loans we computed before, but this step is not mentioned in this post, you can read it in Reporting Erros in RFC, however, it’s quite intuitive for us.

Before continuing, I need to bring some background knowledge in advance.

A Lifetimes is a set of program points on CFG(Control Flow Graph).

For instance, the let r:&i32 = &x; can be expanded to let r: &'0 i32 = &'1 x; by the compiler, then we can get some fact from this borrow expression:

• Generate a Region '1 (region variable).
• Create a Constraints: ('1 : '0) @ P. A Subtyping relation3 with location(program point) information; It’s mean the region '1 must include all points in '0 which are rechable from location $P$.

The reason why it’s just generate a region is because you should decompose this borrow expression into the two statements. One is declarative of r, and another is an assignment.

let r: &'0 i32;
r = &'1 x;


### Borrow

Each Borrow expression is corresponding to a Loan which is a struct for recording some information about this borrow.

Such like p = &foo; may create a Loan as shown below.

Loan L0 {
point: A/0
path: { foo },
kind: shared
region: '1 { A/1, B/0, C/0 }
}


That’s mean a borrow expression happen at A/0 (the 0th statement of Basic Block A), foo is borrowed, create a shared reference tagged with a Lifetimes '1 (a set of program points computed in the first two steps in borrowck).

### Data Flow Analysis

The process of building liveness in the first step and determine which Loans are live at which points in the third step, are actually the data flow problems4.

The Data flow problem come into two flavors: forward or backward direction. Take forward as an exmaple, in Figure 1, we can formulate it with

$Out[s] = gen_s \, \cup \, ( \, In[s] \, \cap \, \overline {kill_s} \,)$

#### Definition

• Input of node s: $In[s]$.
• Output: $Out[s]$.
• Transfer function: $gen$ and $kill$.

If p is a predecessors of s, then $Out[p] = In[s]$

#### Behavior

The result of $Out[s]$ is { $In[s]$ substract the $kill_s$ set and then union with the $gen_s$ set }.

And it will be implemented in a fixed-point iteration alogrithm; That’s mean, it will try to recompute it, until the whole states are fixed. In other words, the $In[s], \, \forall s \in domain\,V$ will not changed anymore.

## Step1. Building Liveness

• Liveness: a variable $v$ is live at point $P$ if there exists a path in CFG from $P$ to a use of $v$ along which $v$ is not defined.

### Liveness analysis (Backward data flow problem)

Data flow equation

$Live_{in}[exit]=\emptyset$

$Live_{in}[s] = use_s \, \cup \, ( \, Live_{out}[s] \, \cap \, \overline {def_s} \,)$

$Live_{out}[t] = \bigcup_{s \in succ(t)}\, Live_{in}[s]$

When we meet a statement like: a = b + c, then $def_s$ is { a }, $use_s$ is {b, c}. If the $Live_{out}[s]$ is {a, d} then

$Live_{in}[s] = \{\{a, d\} - \{ a \}\} \cup \{b,c\} = \{d, b, c\}$

For the variable b, we can say that b is live at location s (in $live_{in}[s]$), but not live anymore after the location s. So the liveness of b include points s ($s \in liveness(b)$).

### Note

But here is a little different is we only compute the liveness of variable if it has a region associated. For instance, we only care about the p that assoicated with region '0 in the code below. But the liveness of variable foo and bar just doesn’t matter.

let foo = 10;
let bar = 20;

let p:&'0 T;
p = &'1 foo;


And the liveness of p will be assigned to region '0. That we say: '0 = liveness(p).

## Step2. Solving Contraints

In Step2, we need to sovle the contraints; In other words, complete the requirements of constraints. After we sovled the constraints, we can get another regions.

• Constraints: a form of ('a : 'b) @ P; Lifetimes 'a must include all points in 'b which are rechable from the location $P$.

For instance, in Figure 2, you may already have region 'b = {n1, n3, n4} which is computed in Step1, and after solved the constraint ('a : 'b) @ P, you will get the region 'a which is include {n1, n4}.

## Step3. Compute Loans in Scope

Each Borrow expression is corresponding to a Loan, that we already talked in Borrow.

Determine which Loans are live at which points is also a data flow problem, but unlike the liveness is a backward analysis, it’s a forward.

Data flow equation

$Loan_{out}[entry]=\emptyset$

$Loan_{out}[s] = gen_s \, \cup \, ( \, Loan_{in}[s] \, \cap \, \overline {kill_s} \,)$

$Loan_{in}[s] = \bigcup_{p \in pred(s)}\, Loan_{out}[p]$

• Transfer functions:

$gen$ if the statement at location s is a borrow expression.

$kill$ if the $LV$ of the assignment is in path ($LV \in path$), or the location s in not live here ($s \notin region$).

It is like having lots of flyer(Loans) in your hand, you will copy these flyers and transfer to the next people. If you encounter a branch, just give them to all branches. The next people will check if they should discard some flyers because of the reason above, and then check if they should generate a new flyer because they are a borrow expression, and then transfer to the next people again.

Until the whole Loans at each locatoin are fixed, not changed anymore, then the job is completed.

## Examples

The code below cannot compiled, because even the L1 be killed on the true path of if-branch, but it’s still live on the other path. So when you borrow the list at line-11, it will invalidate the L1. Some other examples I present in this slide.

  0 1 2 3 4 5 6 7 8 9 10 11 12  let mut list: &mut List = &mut a; // gen L0 let r = &mut (*list).value; // gen L1 if (*list).len > 0 { list = &mut b; // kill L1 // gen L2 } // L0, L1, L2 are live here println!("{:?}", list); // Invalidate L1 println!("{:?}", r); 

You may wondering why the line-11 will invalidate the L1, that because L1 is just the fact of Borrow expression at line-2, what is it mutable borrow are (*list).value, (*list), list by Supporting Prefixes5. So you can not immutable borrow list at line-11.

However, the following code can be allowed by the Compiler, and the reason is quite intuitive.

  0 1 2 3 4 5 6 7 8 9 10 11 12 13  let mut list: &mut List = &mut a; // gen L0 let r = &mut (*list).value; // gen L1 list = &mut b; // kill L1 // gen L2 // L0, L2 are live here println!("{:?}", list); // kill L0 and L2, because these region not include here println!("{:?}", r); 

## Reference

1. The new Borrowck called Polonius; use RUSTFLAGS=-Zpolonius cargo +nightly run to play this new design.
2. Liveness analysis; Also called live variable analysis, mostly used before register allocation in compiler, wiki.
3. Subtyping relation. https://doc.rust-lang.org/nomicon/subtyping.html, the outlive relation between lifetimes, but it will become subset relation in the furture(Polonius).
4. Data Flow Analysis; The details of this technique can be found in chapter 9 of Compilers : principles, techniques, and tool(2nd), wiki.
5. Supporting Prefixes; https://github.com/rust-lang/rfcs/blob/master/text/2094-nll.md#reborrow-constraints