a1mersnow/2094-nll

a1mersnow · 2021-11-18T03:09:34Z

摘要

扩展 Rust 的借用（检查）系统，使它支持 非词法生命周期。这种全新的生命周期基于 控制流图 而不是 词法域，所以更加灵活。这篇 RFC 详细描述了如何推断出它的作用范围，以及如何相应地调整编译器给出的错误信息。另外这篇 RFC 也提到了借用检查系统的其他几个扩展，所有这些扩展唯一的目标就是尽量减少我们与借用检查系统的斗争。（尽管如此，还是有一些借用检查系统的局限尚未被解决，详见附录）

目的

生命周期是什么

借用检查系统的基本思路是：当值被借用时，就不能再被修改或移动。但是我们怎么知道一个值被借用了呢？很简单，当你创建一个引用时，编译器会赋予这个引用一个生命周期，所谓生命周期，你可以把它看作一个 代码区域，编译器会让这个区域尽量小但包裹住所有使用这个引用的代码。

请注意，这里所说的 生命周期（lifetime） 这个词，可能与你的理解有所不同。日常交流中，我们会提到两种生命周期：

引用的生命周期：引用被使用的代码区域
值的生命周期：值从创建到被销毁（通常是花括号的末端）的代码区域

第二种生命周期很重要，它描述了这个值能活多久（或者说有效期有多长）。为了区分这俩生命周期，我们把第二种值的生命周期叫做值的 作用域（scope）。当然，生命周期和作用域是彼此关联的。进一步讲，如果你创建了一个值的引用，那么这个引用的生命周期不能大于值的作用域，否则这个引用可能会指向已经被释放掉的内存。

为了更好地理解两者的区别，让我们来看一个例子。在下面这个例子中，我们创建了一个指向向量 data 的（可变）引用，然后把这个引用传递给函数 capitalize。因为函数 capitalize 并没有返回任何引用，所以我们创建的引用就被这个函数吞噬了。下面的代码中详细标出了值的作用域（'scope）和引用的生命周期（'lifetime），我们可以清楚地看到，作用域要大于生命周期。

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
}

从上面这个例子我们也能看出，生命周期要比作用域灵活（这篇 RFC 就是为了让它更加灵活），主要体现在：

作用域一般来说就是从 let 声明开始，到最近的花括号 } 结束
生命周期则可以只包含单个表达式，在上面的例子中，我们所创建的引用的生命周期被限制在 captitalize 的调用内，而没有扩散到剩下的代码区域。这也是下边 data.push 没报错的原因。

如果一个引用只在单个语句内使用，那么旧有的生命周期也足够了。问题是引用很可能同时出现在多个语句中，这时编译器会推断出一个最小生命周期来包含所有使用引用的语句。在旧有的生命周期定义下，这个推断出来的区域很可能比我们预期的要大。让我们通过例子来看一些旧生命周期的问题，然后再看看新的生命周期如何解决这些问题。

问题示例 #1：把引用赋值给一个变量

把引用赋值给一个变量，是一个很常见的情况。思考一下下面的例子，它是由上面那个例子修改来的。在这个例子中，我们没有把引用直接传给函数 capitalize，而是赋值给了变量 slice：

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!  //   |
} // <------------------------------+

如果使用现在的编译器，把一个引用赋值给一个变量意味着这个引用的生命周期会变得跟这个变量的作用域一样长。也就是说，生命周期被拉长到这个 block 结束的地方。那么显而易见，data.push 会报错，因为它们处于这个引用的生命周期内还对值进行了修改（还记得前面说过的原则：当值被借用时，就不能再被修改或移动）。这真的很烦啊，明明代码在逻辑上其实没问题。

当然，有一个丑陋的解决方案是这样：

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
}

我们引入了一个新的 block，因此 slice 的作用域被限制在了这对新的花括号内，那么相应的引用的生命周期也被限制在这对花括号内。问题就这么解决了，这显然不是一个明智的办法，毕竟开发体验很不好。

问题示例 #2：条件控制流

另外一个常见的情况是，引用只在条件控制流的一个分支中被使用（简单说就是只在多个if/else分支中的一个里被使用）。map 最容易出现这种情况。看下面这个例子，这个函数所做的事情是，对于一个 key，如果 map 中能找到这个 key，就调用 process 处理 key 对应的值，找不到就为这个 key 插入一个默认值：

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.              // |
        }                                  // |
    } // <------------------------------------+
}

如果使用现在的编译器，就会如上面代码中的注释所示报错。原因是，map 在 get_mut 调用中被借用了，这个借用的生命周期，不仅要包含 get_mut 调用，还要包含 match 的 Some 分支^*，编译器推断包含这两者的最小代码区域就是整个 match 代码块（如上图所示），即这个借用的生命周期。不幸的是，None 分支也在这个生命周期内，当我们在 None 分支中调用 map.insert 时就会报错，因为编译器认为 map 依然正在被借用。

*：可以从 get_mut 的函数签名看出，Some(value) 中 value 的生命周期跟 map 这次借用的生命周期是绑定的。

咳咳，那么此时又有一个很丑陋的解决方案，我们只需要把 None 分支内的语句移出 match：

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());
}

这样，map.insert 就不在 match 的区域内了，也就不在 map.get_mut 这次借用的生命周期里了。当然，跟前边的那个例子一样，太丑陋了，开发体验太差了。

问题示例 #3：穿过函数的条件控制流

虽然我们“巧妙”地解决了刚才那个条件控制流的问题，但不是所有的条件控制流的问题都这么简单，尤其是当你把一个引用从一个函数里返回的时候。看看下面这个例子，key 存在就返回对应的值的引用，不存在就先插入一个默认值，再返回这个默认值的引用（为了说明这个问题，我们先假装 entry API 不存在）：

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

打眼一看，这段代码跟之前 问题示例 #2 的代码很像，确实它也没法通过编译。但实际上，从生命周期角度看却完全不同。原因是这样，在 Some 分支，value 被函数返回给了调用处，而 value 实际上是一个对 map 的借用，这也就是说 map 会保持被借用的状态一直到调用处之后的某一点（取决于调用代码对返回值的处理），可以参考上图标示的 'r。为了进一步直观地感受生命周期 'r，想象 get_default 被调用的情景，可以看到 'r 一直延续到了被返回的引用 v 最后一次使用的地方：

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);                         //  |
    } // <--------------------------------------+
    ...
}

如果我们尝试 问题示例 #2 中的解决方案，会发现并不行：

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

之前那个例子，value 的生命周期被限制在 match 内，但在这个例子中，value 的生命周期突破了函数 get_default1 一直延伸到了调用代码，因此对 map 的借用也一路延伸到了调用代码，而不仅仅是整个 match 区域。那么当然，我们调用 map.insert 的地方，还处于 map.get_mut 所产生借用的生命周期里呢。

解决办法也不是没有，我们可以通过更加明确的控制流来帮助编译器判断借用是否结束：

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
    }

    // 如果执行到这里，说明 `map.get_mut` 肯定没有被调用
    map.insert(key, V::default()); // OK now.
    map.get_mut(&key).unwrap()
}

我们这里是把 map.get_mut 移到了一个 if 块中，只要程序执行到 if 块内，就会直接 return。也就是说，map.get_mut 的借用虽然会一直延伸到调用代码，但是借用检查系统看到这个借用在 if 块之外是不可能存在的，就可以推断出 map.insert 不在 map.get_mut 产生的借用的生命周期里。

这个解决方案最大的缺点是，map.contains 和 map.get_mut 实际上做了重复的工作。

值得注意的是，Rust 的 HashMap 有一个 entry API，我们可以用它来实现相同的功能，但更加简洁高效易维护：

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())
}

但是无论如何，这个问题不仅存在于 HashMap，许多其他数据结构也有这个问题。所以最好是我们最初的代码不经修改就能通过编译器的借用检查。（有趣的是，entry API 开发的初衷就是为了绕过这个问题）

问题示例 #4：修改 &mut 引用

对于一个存储可变引用的变量，如果它所引用的值或值的一部分被重新借用（所谓的 reborrow），那么当前编译器下是禁止为这个变量赋值的。通常我们会在遍历一个数据结构的时候碰到这个问题。看下面这个例子，函数 to_refs 把一个链表转换成向量：

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;
        }
    }
}

在当前编译器下会报错:

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

原因是我们借用了 list.value （更确切地说是 (*list).value）。当前编译器下，如果你借用了值的一部分，你就不能再对那部分或者那部分的任何前缀赋值了。对上面这个例子来说，你不能对以下这些表达式赋值：

(*list).value
*list
list

因此，list = n 是不行的。编译器的这个规则在某些情况下确实是有必要的（比如，如果 list 不是 List 的引用，而就是 List，那么对 list 赋值就会让我们对 list.value 的引用失效），但在我们这个例子中完全没有必要。

正如 Issue #10520 中讨论的那样，有一些绕过这个问题的解决方案。其中一个是：把 &mut 引用，移动到一个你无需修改的临时变量中：

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;
        }
    }
}

这样，编译器看到的是 (*list1).value 被借用，而不是 (*list).value 被借用。所以，我们就可以给 list 赋值了。

当然这个方案不太好（译者注：有点脱裤子放屁的感觉）。事实上，这个问题并非是我们新的生命周期方案本身要解决的。实际上是编译器在部分借用时的规则限制过于严格了，因为引用本身是一个间接指向的东西（译者注：就上边的例子来说，参数 list 是间接指向一个 List，所以就算 list.value 被借用，对 list 重新赋值也没什么问题。恩，它大概是想说这么个意思……）。我们在这个 RFC 中提出了解决这个问题的调整方案。

我们解决方案的大体轮廓

这篇 RFC 提出了一个更灵活的生命周期模型。之前的生命周期模型基于 AST（译者注：即语法树。还记得开头说的是基于词法域，恩，我感觉差不多是一个意思，只不过这里的表述更侧重于编译器实现的角度），新的生命周期则基于控制流图。更确切地说是基于一种叫做 MIR 的编译器中间产物（译者注：Rust playground 可以方便地查看代码对应的 MIR 哦，虽然我没怎么看过……）。

简单说，新的方案下，引用的生命周期基本等同于这个引用的使用范围。它可能只包含一个或几个连续的语句（对应 问题示例 #1），或者也可能更复杂一点，比如仅包含 match 的一个分支而不包含其他分支（对应 问题示例 #2）。

然而，为了能更随心所欲地书写我们的代码，仅仅有这个新的生命周期模型是不够的，我们还得在做 子类型检查 的时候把位置也考虑进去。在当前的编译器下，子类型关系是跟位置无关的，或者说是”绝对的“。举例来说，在当前的编译器下，如果 'a 所代表的生命周期比 'b 长（或者说 'a 生命周期包含的代码区域比 'b 大），我们就说 &'a () 是 &'b () 的子类，一般我们用符号 a: b 来表明这种关系（译者注：可以看到这里没有位置的概念）。在新的编译器下，我们称子类型关系是创建于某一点的（这里的某一点可以大致理解为某行代码），假设这一点叫点P（用下文的符号可以这样表示 a: b @ P），这样生命周期 'a 只需要包含 'b 所包含的代码区域中从点P能够到达的那一部分（译者注：有点绕，可以从后边的例子中慢慢体会）。

这篇 RFC 中的想法已经实现了一个原型。这个原型包含了一个简化版本的控制流图分析，它允许你创建可能出现的代码区域之间的各种约束；并且实现了满足这些约束的算法。（译者：看不懂先往后看）

设计细节

设计分层

我们一层一层地来讲解这个新设计：

首先，我们会介绍一个基本的设计，它只关心单一函数内的控制流。
然后，我们会扩展这个设计，来更好地处理循环这种控制流。
然后，我们会扩展这个设计，来处理 dropck（如果你不知道 dropck 是什么，请先看这篇），尤其是 RFC 1327 引入的 #[may_dangle] 属性。
然后，我们会扩展这个设计，来处理像 问题示例 #3 中那样的显式标注的生命周期参数。
最后，我们会简短地描述编译器是如何执行借用检查的。

第 0 层：定义

在我们开始描述整个设计之前，我们得定义一些下面会用到的术语。简单起见，这篇 RFC 基于一个简化版本的 MIR。

左值在 MIR 中，左值是一个代表内存位置的表达式。它的完整定义无关紧要，就不提了。我们现在就只关注核心含义：

LV = x       // 本地变量
   | LV.f    // 获取字段
   | *LV     // 解引用

译者：从上面这个简单的定义来看，大致上是这么一种感觉（虽然不准确）：左值能够被赋值。

* 的优先级比较低，所以 *a.b.c 实际上是对 a.b.c 解引用，如果你想解引用的是 a，得这么写：*(a).b.c。

前缀这里我们定义的是左值的 prefix：假设有一个左值表达式，你要得出它的所有 prefix，你就得一点一点地剥去这个表达式的字段和解引用，这个过程中得到的所有左值表达式就是原来那个左值表达式的 prefix。举个例子，*a.b 的前缀是 *a.b，a.b，a。
控制流图 MIR 被组织成控制流图（译者：建议好好看看这篇 wiki 的前半部分）而不是 AST。编译器通过转换 HIR（一种更高级的中间编译产物）来创造 MIR。MIR 控制流图由一系列基础块组成。每一个基础块包含一系列语句和一个终结指令。我们这篇 RFC 主要用到了三种语句（译者：MIR 中的语句跟我们代码中的语句并不是一一对应的，可能我们代码中的一个语句会被编译成 MIR 中的多个语句）：
- 赋值语句比如 x = y 等号右侧叫做右值，注意在 MIR 中是没有复合右值的，每一个语句就是一个完整的立即执行的操作。举例来说，源码中的 a = b + c + d 会被编译成 MIR 中的两个语句，就像 tmp0 = b + c; a = tmp0 + d;。
- drop(lvalue) 如果 lvalue 代表的位置存在一个值，就释放它；虽然由于某些限制，这个操作需要运行时检测，但在 MIR 中依然只需要一个语句来完成整个操作（检测 + 释放）。
- StorageDead(x) 释放 x 的栈上空间。当然还有一个语句叫 StorageLive(x)，用来分配 x 的栈上空间。 LLVM 可以使用这些语句来优化栈帧的大小。详情可以阅读这篇博文（译者：可以只读前半部分）。

第 1 层：函数内的控制流

运行示例

我们将参考一个名为 示例4 的运行示例来解释我们的设计。然后，我们会将其应用于之前那三个问题示例，以及其他一些有趣的例子。

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)

这个示例的关键在于，foo 只在 0 和 3 处被借用，在 1 处没被借用。bar 则是在 2 和 3 处被借用。foo 和 bar 在 4 处都没有被借用，因为在 4 处 p 并没有被使用。

我们可以把个示例转换成下面的控制流图。之前说过，MIR 中的控制流图由基础块组成，而基础块则由一些独立的语句后跟一个终结指令构成：

// 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       ]

接下来我们用 基础块/索引 形式来指向控制流图中的某个语句或者终结指令。举个例子，A/0 指向的是 p = &foo，B/4 指向的是 goto C。

什么是生命周期以及它在编译器的借用检查中发挥着什么作用

我们暂时用一系列控制流图中的点来描述生命周期，之后我们会采用更精准的描述方式来包含函数签名中的命名生命周期。如果一个生命周期包含点 P，那就意味着具有该生命周期的引用一直到 P 点都是有效（存活）的。 生命周期出现在 MIR 的多个地方：

变量（包括临时变量）的类型可能会包含生命周期
每个借用表达式都有一个特定的生命周期

我们可以给上边这个例子标上明确的生命周期：

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);

如你所见，生命周期 'p 是变量 p 类型的一部分。在控制流图中，只要在 'p 所覆盖的范围内 p 就可以被安全地解引用。而生命周期 'foo 和 'bar 则不同，它们是 foo 和 bar 被借用的范围。

像 'foo 和 'bar 这种跟借用表达式绑定的生命周期，对编译器的借用检查来说非常重要。它们代表了控制流图中的某些区域，这这些区域中，编译器会严格执行借用检查相关的规则。在这个例子中，由于 'foo 和 'bar 两处借用都是不可变借用/共享借用（&），编译器会在 'foo 有效范围内阻止 foo 被修改，在 'bar 有效范围内阻止 bar 被修改。反之，如果这两个借用都是可变借用（&mut），编译器会在 'foo 的有效范围内阻止对 foo 的访问，在 'bar 的有效范围内阻止对 bar 的访问。

关于 'foo 和 'bar 的有效范围，有很多合法的推断。然而这篇 RFC 所描述的推断算法，旨在为每次借用推断出最小的生命周期范围，从而对开发者施加尽量少的限制。

在上面的示例中，我们希望我们的算法推断出 'foo 的范围是 {A/1, B/0, C/0}，注意它并不包含 B/1 和 B/4（译者：这里为什么不包含 B/1？我猜是因为 p 在下一行被重新赋值，因此这里 p 不是存活的（有关存活请往下看）。这只是个无关紧要的小细节，所以不用太纠结。）。'bar 的范围是 {B/3, B/4, C/0}。'p 的范围则是 'foo 和 'bar 的并集，因为它包含变量 p 有效（存活）的所有范围。

生命周期推断创建约束

这个推断算法通过分析 MIR 创建出一系列约束，这些约束可以用下面的语法来表示：

// 一个约束集合 C:
C = true
  | C, (L1: L2) @ P    // 点 P 之后生命周期 L1 大于等于生命周期 L2

// 一个生命周期 L:
L = 'a
  | {P}

这里 P 代表控制流图中的点（对应 MIR 中的语句），'a 表示被命名的生命周期（比如上面的 'p 'foo 'bar）。（译者：上面的语法定义了两个东西，首先，生命周期要么是某个被命名的生命周期，要么是控制流图中的某个点；然后，约束集合要么是永远成立的（也就是没有约束）要么是一个小的约束集合加上新的约束组成（所以这是个递归定义））

一旦约束创建好了，我们的推断算法就会尝试满足这些约束。具体来说，每一个生命周期都会初始化为一个空集，然后我们不断遍历所有的约束，在这个过程中不断扩大这些生命周期，直到满足所有的约束。

(你可能想看看原型是如何实现这个部分的, 这个文件 regionck.rs 是负责创建约束的，这个文件 infer.rs 是负责满足约束的。)

存活

理解 NLL 如何工作的关键是理解存活。这个词虽然来源于编译器分析，但也相当符合人的直觉。如果一个变量现在所持有的值可能在之后被用到，我们就说这个变量是存活的。对于 示例 4 来说这非常重要：

let mut foo: T = ...;
let mut bar: T = ...;
let mut p: &'p T = &foo;
// `p` 在这里是存活的，因为它的值之后可能会被用到
if condition {
    // `p` 在这里是存活的，因为它的值之后可能会被用到
    print(*p);
    // `p` 在这里不是存活的，因为它现在所持有的值不会再被用到
    p = &bar;
    // `p` 在这里是存活的，因为它的值（刚刚赋予的）之后可能会被用到
}
// `p` 在这里是存活的，因为它的值之后可能会被用到
print(*p);
// `p` 在这里不是存活的，因为它的值不会再被用到

p 在程序的开始被赋值，然后可能会在 if 中被重新赋值。关键在于，p 在它被重新赋值之前的一小段空隙里不是存活的。尽管变量 p 之后还会被用到，但 p 当前所持有的值不会再被用到了。

传统的编译器只（根据作用域）推断变量的存活，而我们希望进一步推断出生命周期的存活。我们可以这样定义，如果存在某个变量 p 在点 P 存活，而生命周期 L 是 p 类型的一部分，我们就说生命周期 L 在点 P 存活。（介绍 dropck 的时候我们会看到，存活变量的类型中的生命周期，有些是存活的，有些不是存活的，因此这里的定义并不是很准确，我们会在后面完善它）在我们的 示例 4 中，生命周期 'p 的存活范围跟变量 p 是完全一致的；而生命周期 'foo 和 'bar 则无法直接判断是否存活，因为它们并没有出现在任何变量的类型中。当然，这并不意味着这些生命周期之间（指 'foo 'bar 和 'p 之间）没有关联；还记得前面提过（在 解决方案的大体轮廓 那里）的子类型检查，接下来我们会介绍它是如何保证 'foo 和 'bar （合起来）一定大于等于 'p 的。

生命周期基于存活的约束

我们首先讨论基于存活的约束。我们用下面的式子表示生命周期 L 在点 P 是存活的：

(L: {P}) @ P

这种基于存活的约束很简单，只需要把 P 插入 L 的集合中。

对于 示例 4 来说，意味着我们得到了以下约束：

('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

子类型约束

当引用从 A 处被拷贝到 B 处的时候，A 的生命周期一定要大于等于 B。正如前面所说，在这篇 RFC 我们扩展了子类型的定义，增加了位置的概念，也就是说我们把拷贝发生的位置考虑了进去。

举个例子，我们的 示例 4 在点 A/0 有一个借用 p = &'foo foo。在这种情况下，借用表达式会产生一个类型为 &'foo T 的引用（这里 T 是 foo 的类型）。然后这个引用被赋值给了 p，而 p 的类型是 &'p T。因此，我们说 &'foo T 是 &'p T 的子类型。更确切地说，这个子类型约束需要从点 A/1 开始有效，也就是赋值语句所在的 A/0 的下一个点（这是因为 p 的这个新值最早在 A/1 才能被使用）。我们用下面的式子表示这个子类型约束：

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

编译器会根据子类型相关的规则（下面给出了两个例子）把子类型约束分解，我们就得到了我们想要的生命周期约束：
（译者注：这里的规则可以看这篇）

(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

我们的 示例 4中，会得到如下子类型约束：

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

然后被转换成生命周期约束：

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

重借用约束

这是最后一种约束类型了，重借用指的是我们对已经存在的引用，解引用之后重新借用：

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

这样，就会在新生命周期 'y 和原来的生命周期 'x 之间存在一个关联。确切说，'x 必须大于等于 'y（'x: 'y）。在类似上面这种简单的情况下，这个关联跟原来的引用是 & 还是 &mut 没什么关系；但在更复杂的情况下，比如存在多个解引用，就另当别论了。

支撑前缀（但愿这个翻译还凑合）。（还记得我们在 第0层：定义 中提到的前缀吗，这里是在那个的基础上定义的）为了定义重借用约束，首先我们要引入支撑前缀的概念。一个左值的支撑前缀就是在解析前缀的过程中，当我们遇到一个共享引用的解引用就停下，不再继续往下解析（这就是支撑前缀和前缀的区别，前缀会解析到底）。那么为什么我们要在遇到共享引用的解引用时停下呢？为什么是共享引用，而不是可变引用呢？因为他们实现了 Copy trait，因此我们总是可以把共享引用拷贝到一个临时变量里，从而得到一个等价的表达式路径（比如下面的 r.0 就是一个共享引用，我们可以把它拷贝到临时变量 r_0 中，然后我们就可以用 (*r_0).1 来代替 (*r.0).1 了）。下面是支撑前缀的几个例子：

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

重借用约束。考虑下面的例子，我们有一个对左值 lv_b 的借用，它的生命周期是 'b：

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

我们首先计算出 lv_b 的所有支撑前缀，然后在其中找到所有的解引用表达式，对于每一个被解的引用的生命周期 'a，我们都产生一条约束 ('a: 'b) @ P，点 P 就是这次重借用的下一行（也就是重借用生效的地方）。

让我们看一些例子。每一个例子，我们都会链接到原型的测试代码：

示例 1 为了明白我们为什么需要这类约束，先看一个简单的例子，它只包含一层引用：

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);

在这个示例中，*r_a 的支撑前缀是 *r_a 和 r_a（因为 r_a 是可变引用，所以我们解析下去）。这俩前缀只有 *r_a 是一个解引用，引用 r_a 的生命周期是 'a。我们创建约束 'a: 'b，保证只要 r_b 被使用 foo 就是被借用的状态。没有这条约束的话，生命周期 'a 在第二个借用后就终止了，那么 foo 就会被认为没有被借用，但我们明明可以通过 *r_b 来访问 foo。

示例 2 现在考虑两层的情况:

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);

就像前面那个例子一样，只要 r_c 在使用中，foo 就是被借用的状态。但是 r_a 呢？它是被借用的状态吗？答案是不：一旦 r_c 初始化完，r_a 的值就不重要了，对它重新赋值也无所谓了，尽管 foo 还被借用着。意外吗？这其实完全是根据我们的重借用规则来的：**r_b 的支撑前缀就只有 **r_b，因为这已经是一个对共享引用的解引用了。因此，我们只有一条重借用约束：'a: 'c。这条约束保证了只要 r_c 在使用中，foo 就是被借用的，但是对 r_a 的借用（'b）是可以失效的。

示例 3 前一个例子展示了，一旦共享引用被解引用，它就不再有效了。然而对于可变引用来说，这是不安全的，考虑下面的例子：

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);

这里的关键在于，我们通过重借用 **q 创建了引用 r；r 在程序的最后一行被使用。这行对 r 的使用会把生命周期 'p 和 'q 延长（因为 'p 和 'q 必须比 'r 活得久），否则开发者就有可能同时通过 *r 和 *p 访问（修改）同一块内存。

因为对一个可变引用解引用不会让支撑前缀的解析停下（对共享引用解引用才会），所以 **q 的支撑前缀是 **q *q 和 q。因此，我们创建了两条约束 'q: 'r 和 'p: 'r。因此，不管是 'p 还是 'q 在图中箭头处都是存活的（因为不能同时持有两个可变引用，所以上面会报错）。

换个角度看，我们可以这样想。创建可变引用 p 的时候，我们得到了一把对 foo 的锁（只要 p 被使用，这个锁就保持有效）。然后我们创建 q 的时候，又得到了一把对 p 的锁（只要 q 被使用，这把锁就保持有效）。当我们通过借用 **p 创建 r 的时候，那是最后一次对 q 的直接使用，所以你可能想我们可以释放对 p 的锁了，因为 q 不再被（直接）使用了。然而这是不安全的，因为在那之后 r 和 *p 都可以被用来访问相同的内存。关键是要认识到 r 其实是对 q 的间接使用，而 q 是对 p 的间接使用，所以只要 r 是存活的（被使用），p 和 q 也必须是存活的（它们的锁依然要保持有效）。

满足约束

一旦约束创建好了，我们的推断算法就会尝试满足这些约束。具体来说，每一个生命周期都会初始化为一个空集，然后我们不断遍历所有的约束，在这个过程中不断扩大这些生命周期，直到满足所有的约束。（咦，前边说过一样的话╮(￣▽￣"")╭ 这里其实也是使用的下文提到的“不动点”算法，只不过细节略有不同）

像 ('a: 'b) @ P 这样一个约束的意义是，从点 P 开始，生命周期 'a 必须包含 'b 中从点 P 开始能够到达的所有点。这个实现从点 P 开始深度优先搜索，超出 'b 则停止搜索，过程中遇到的所有 'b 中的点（注意，在 B/2 处 p 被重新赋值，因此那之后一直到 if 结束都是从 A/1 开始所无法到达的），我们都把它加到 'a 中。

在上面的 示例 4 中，全部约束如下：

('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

为了满足这些约束，我们得到了如下的生命周期，就跟我们之前预期的结果一样：

'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}

从直觉上讲为什么这个算法是对的

为了让这个算法正确，我们必须遵循一个关键原则。考虑一个表达式 H 在点 P 被借用从而得到生命周期为 L 的引用 R；这个引用 R（或者它的拷贝或者转移）之后在某一点 Q 被解引用。

我们必须保证这个引用直到 Q 都是有效的，也就是说被借用的那一块内存直到 Q 都不能被释放。如果引用 R 是一个共享引用，那么那块内存不能被写（类似 UnsafeCell）。如果 R 是可变引用，那么那块内存不能被除 R 之外的途径访问。为了保证这些，我们必须在 P（借用）和 Q（使用）之间阻止一切可能影响那块内存的行为。

这意味着 L 必须至少包含 P 和 Q 之间的所有点。有两种情况需要考虑。第一种情况，Q 点的访问是直接通过 R 来完成的：

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

这种情况下，R 在 P 和 Q 之间的所有点都是存活的。基于存活的约束可以应对这种情况：确切说，因为 R 的类型包含生命周期 L，而 R 在 P 和 Q 之间的所有点都是存活的，所以我们知道 L 必须包含 P 和 Q 之间的所有点。

第二种情况，Q 点的访问是通过一个别名（或者转移）：

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

这种情况下，基于存活的约束已经不足以应对了。问题是 R2 = R 这条赋值语句是对 R 的最后一次使用，所以如果只有基于存活的约束，R 在这一点之后就不再存活了。然而 R 中的值依然可以通过解引用 R2 访问到，所以我们想让生命周期 L 包含 R2 = R 之后的点。这就是子类型约束发挥作用的地方了，R2 的类型包含一个生命周期 L2，赋值语句 R2 = R 会为 L 和 L2 创建约束 (L: L2) @ A。同时，新变量 R2 必须在赋值语句和最后的使用语句之间保持存活（上图中的 A..Q）。把这两个约束结合使用，我们就能看到 L 最终会包含从 P 到 A 到所有点（变量 R 的存活约束）以及从 A 到 Q 的所有点（子类型约束传递了变量 R2 的存活约束）。

注意，生命周期是可以有间隙的。相同的变量被使用和覆写多次就会出现这种情况：

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

在这个示例中，R2 的存活约束会保证 L2 包含点 Q1 和 Q2（因为 R2 在这两点间是存活的），但不包含 "..." 也不包含 P1 和 P2。注意子类型约束 (L: L2) @ A1) 保证了 L 也包含 Q1 但不包含 Q2（尽管 L2 包含 Q2）。这是因为 R2 中的值在 Q2 不可能来自在 A1 的赋值。（译者：这里后边还有一句，感觉很让人困惑而且没什么卵用，就删掉了）

其他几个示例

让我们多看几个例子。我们先看看前边见过的 问题示例 #1 和 问题示例 #2 （问题示例 #3 等我们介绍命名生命周期之后再说）。

问题示例 #1.

（译者：为了看得方便，这里重新贴一下）

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!  //   |
} // <------------------------------+

编译成 MIR：

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');
}

约束：

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

'slice 和 'borrow 都会被推断成 {START/2}，因此 START/3 对 data 的访问以及它下边的语句都是合法的。

问题示例 #2.

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.              // |
        }                                  // |
    } // <------------------------------------+
}

编译成 MIR，就像下面这样（一些无关的细节被省略了）。注意 match 语句被编译成一个 SWITCH 和一个 downcast，SWITCH 测试 tmp2 看看是走哪个分支，downcast 把 Some 包含的内容提取出来（这个操作是 MIR 独有的，作为 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 {
}

基于存活的约束：

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

子类型约束：

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

最后，我们最感兴趣的生命周期就是 'map，也就是 map 被借用的范围。满足上面的约束我们得到：

'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}

结果说明 map 在 None 分支可以被修改；map 在 Some 分支也可以被修改，但必须在 process() 之后（即：从 SOME/2 开始）。这正是我们想要的。

示例 4 的另一个版本（invariant）

我们应该看看 示例 4 的另一个版本。和之前一样，但这次不是 &'a T，而是 Foo<'a>，假设 Foo 对 'a 是抗变的（invariant）。这意味着 Foo<'a> 中的生命周期 'a 不能被近似（即你不能像缩短其他普通引用的生命周期一样缩短它）。通常抗变（invariance）是由可变性引起的（比如说，Foo<'a> 可能有一个类型为 Cell<&'a ()> 的字段）。这里关键在于抗变（invariance）实际上对结果没有任何影响，这是因为我们的子类型约束考虑了位置因素。

译者：这里大概让人有点懵圈，主要是抗变（invariance）这个词让人有点搞不懂。举个例子吧，假如有 SomeStruct<T> 这样一个带泛型的结构体，然后有类型 T1 和类型 T2，其中 T1: T2（也就是 T1 是 T2 的子类型）。那么如果 SomeStruct<T1>: SomeStruct<T2>，我们就说 SomeStruct<T> 对 T 是协变的（covariant）；如果 SomeStruct<T2>: SomeStruct<T1>，我们就说 SomeStruct<T> 对 T 是逆变的（contravariant）；如果 SomeStruct<T1> 和 SomeStruct<T2> 不存在子类型关系，我们就说 SomeStruct<T> 对 T 是抗变的（invariant）。那假如反过来，我们有 SomeStruct<T1>: SomeStruct<T2>，那么 T1 和 T2 是什么关系呢？仔细想想就会知道，T1 和 T2 必须完全相同（否则这个子类型关系不可能成立）。那么对于上边的 Foo<'a> 来说，Foo 对 'a 抗变也就是说，假如有 Foo<'a1>: Foo<'a2>，那么 'a1 必须和 'a2 完全相同。我们可以用 'a1: 'a2 & 'a2: 'a1 来表示这种关系。那不能被缩短又是什么意思呢？假如我们有一个类型为 &'a T 的变量和一个类型为 &'b T 的变量，然后我们把 &'b T 赋值给 &'a T，那么可以得到 'b: 'a，是不是也就相当于赋值或者说子类型约束把 'b 缩短成了 'a。而在抗变的情况下，也就是把 Foo<'b> 赋值给 Foo<'a>，那么 'a 和 'b 必须完全相同，也就是说无法缩短。

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);

实际上，我们得到了跟之前一样的约束，只不过又加了两条 'p: 'foo 和 'p: 'bar：

('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

关键在于，新增加的约束并没有影响最终的结果，原来的答案（生命周期集合）已经能满足新的约束了。

vec-push-ref

在这篇 RFC 的上一个版本中，我们并没有使用带位置的子类型约束，而是使用了 SSA 形式的转换（译者：讲真我也不知道这是什么玩意儿，就当没看见吧）。下面这个例子展示了带位置的子类型约束的优势所在。

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);
}

转换成控制流图：

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 {
}

基于存活的约束：

('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

同时，vec.push(p) 建立了子类型约束：

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

推断出生命周期是：

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

这个例子有趣的地方在于，生命周期 'vec 必须包含 if 的两个分支 - 因为 vec 在两个分支都被用到了 -- 但是 'vec 只在第一个分支跟生命周期 'p 绑定。所以尽管 'p 必须比 'vec 活得长，但那是在第一个分支范围内的约束，而在 else 分支 'p 不会跟 'vec 有所关联。这多亏了带位置的子类型约束。

第 2 层：避免无限循环

前面的设计是使用纯 MIR 控制流图来描述的。然而，仅仅使用控制流图可能无法描述无限循环的情况。因为在无限循环的情况下，控制流图没有退出点，这样的话类似存活这样的逆向分析就无法正常工作了。为了解决这个问题，我们在为函数构建控制流图时，使用额外的边来增强它，确切说，对于每个无限循环（loop {}），我们都会增加一个 false unwind 边。这就保证了控制流图有一个最终的退出点（RETURN 和 RESUME 的后一个节点）来终结整个执行。

（译者：这个QA或许能让你更明白一些……）

如果我们没有增加这样的边，结果就是会允许很多本不应该通过编译的程序通过编译器的检查。下面这个例子中，只要函数永远不返回，我们就能以 'static 的生命周期借用本地变量：

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

这是因为（细节在下面的借用检查章节会介绍）StorageDead(x) 指令永远也执行不到，所以任何生命周期都是可以接受的。这进一步导致了其他有问题的程序通过编译检查，比如这个例子中使用了一个（错误但声明为不安全的）API 来创建线程：

#![allow(unused)]
fn main() {
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
}
}

没有 unwind 边，这段代码能够通过编译器的借用检查，因为 _guard 的销毁（以及 StroageDead 指令）是不会执行到的，因此 _guard （在 loop 之后）被认为不是存活的（毕竟，它的析构函数永远也不会执行）。然而这样的话，
foo 就既可以在无限循环中被修改也可以在 scope.spawn() 创建的线程中被修改，因为 scope.spawn 能够访问到 &mut foo 引用（尽管理论上这个引用的生命周期很短）。

有了 unwind 边，编译器实际上总是假设析构函数会执行到，因为每个作用域理论上都有可能执行到。这就扩展了传递给 scope.spawn() 的 &mut foo 借用，使它的生命周期覆盖了 loop 循环体，从而产生了我们期望的借用检查错误。

第 3 层：适配 dropck

MIR 中有一个销毁变量的操作：

DROP(variable)

注意虽然 MIR 支持任何左值的销毁，但是在这一层设计里，我们总是一次性销毁整个变量。上面的 DROP 执行 variable 的析构函数，将 variable 的值所在的内存去初始化（即回到未初始化状态）（如果 variable 或者它的一部分已经被销毁了，那么 DROP 不会有任何效果；我们当前的分析并不涉及这种情况）。

有趣的是，很多时候销毁一个值并不要求被销毁的值所包含的生命周期是有效的。毕竟，销毁一个 &'a T 或者 &'a mut T 这样的引用并没有什么实际上的操作，所以即使引用指向了非法的内存也没关系。这种情况下，我们说生命周期 'a 可以垂悬。这跟 C 语言里的“垂悬指针”（指针指向了已经被释放的内存或不合法的内存）异曲同工。

然而，如果引用是存储在某个实现了 Drop trait 的结构体的字段中，结构体就有可能在运行析构函数的过程中获取被引用的值，所以在这种情况下引用合法就非常重要了。不过另一方面来说，这种垂悬很少发生。如果你有一个值 v 的类型是 Foo<'a>，并且这个类型实现了 Drop Trait，那么 v 被销毁的时候 'a 一般不太可能垂悬（因为任何其他操作也不允许 'a 垂悬）。

更一般的说，RFC 1327 定义了几个规则，规则阐明了类型中的哪些生命周期可以在销毁期间垂悬（译者：比如标记了#[may_dangle]或者类型本身就是引用），哪些不行。我们把这些规则整合进我们的存活分析中：在做存活分析时，MIR 指令 DROP(variable) 跟其他 MIR 指令区别对待。所以某种意义上，我们同时运行两套独立的存活分析（实际上，原型中是使用两个位来标记每个变量的存活状态）：

第一套分析表示变量中的当前值可能在将来被使用。这对应于 MIR 中对变量的非 drop 使用。当变量在这个意义下是存活的，它类型中的所有生命周期都是有效的。
第二套分析表示变量中的当前值可能在将来被销毁。这对应于 MIR 中对变量的 drop 使用。当变量在这个意义下是存活的，它类型中的所有生命周期中除了那些被标记为可以垂悬的都是有效的。

在销毁中允许生命周期垂悬是很重要的。就拿 问题示例 #1 来说，如果我们把它编译成 MIR，引用 slice 会在块的末尾被销毁：

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);
}

因为 'slice 在销毁期间可以垂悬，所以 'slice 在 DROP(slice) 处不是存活的。

第 4 层：命名的生命周期

之前，我们仅仅讨论了函数范围内的生命周期。然而，我们有时想表示那些在当前函数之外的生命周期。再来看看 问题示例 #3（原型相应的测试用例）：

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

把它转换成 MIR，我们得到（注意这是伪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;
}

这个例子的关键是 map 的第一次借用，它的生命周期是 'm1，在 SOME 分支 'm1 必须大于等于 'r 。而一旦我们进入 NONE 分支，'m1 就结束了。（很遗憾，虽然道理是这么个道理，目前 Rust 还并不支持这个例子原样编译通过。）

为了处理函数签名中的命名生命周期，我们得扩展区域的概念，让它不仅包含函数控制流图中的点，还包含一系列（可能为空）“邻接区域”，这些区域代表由命名生命周期扩展到的调用代码。假设 'r 是某个命名生命周期，我们以 end('r) 来表示它所对应的“邻接区域”。end('r) 在语义上可以被理解为指向调用代码控制流图的一部分（实际上，它可以一直扩展到调用代码的调用代码，无限扩展下去）。新的区域概念可以如下表示（伪代码）：

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

这样，当一个类型中含有一个命名生命周期，比如 'r，那么 'r 可以被表示为一个包含如下部分的区域：

函数控制流图中的所有点
以及，命名生命周期对应的邻接区域（end('r)）

如果 'r: 'x，我们进一步让这个区域包含 end('x)。

最后，我们必须相应地调整我们子类型约束的定义。当我们有一个生命周期约束：

'b: 'a @ P

在我们之前的设计中，如果函数控制流图的末端能从点 P 到达并且 'a 包含这个末端，我们就简单地把这个末端加到 'b 中就完事了。现在，我们还要把 'a 包含的“邻接区域”也加到 'b 中。（也就是说，'b 要比 'a 活得长，那么 'b 就得包含 'a 包含的邻接区域）那么为什么我们要求函数控制流图的末端必须能从点 P 到达呢？因为如果从点 P 不能到达函数控制流图的末端，数据就不可能离开这个函数，也就不可能到达 end('r)（因为 end('r) 只覆盖调用代码中返回之后的部分）。

特别注意：原型只实现了这一层设计的一部分。Issue #12描述了当前进展和进行中的 PR 的链接。

第 5 层：借用检查如何工作

大多数情况下，这篇 RFC 所关注的是生命周期的结构，但值得一提的是，我们如何把新的生命周期设计接入到编译器的借用检查中。顺便我们还想修复当前编译器借用检查的两个缺点。

第一，对嵌套方法调用的支持，比如 vec.push(vec.len())。这里，我们的计划是继续采用 RFC 2025 提出的 mut2 借用方案。这篇 RFC 暂时没有偏向 RFC 2025 中基于类型的几个解决方案中的任何一个，比如 "borrowing for the future" 或者 Ref2。至于为什么请看替代方案部分（那部分没有翻译）。简单起见，这里我们就假装没有 RFC 2025。这里我们讨论的扩展与 RFC 2025 中的提议是完全正交的（就是说相互独立的）。在 RFC 2025 中，实际上推迟了借用的起始位置。

第二，允许包含可变引用的变量被修改，即使它所借用的值被重新借用。我们希望 问题示例 #4 那样的程序通过编译器检查。

借用检查第 1 阶段：计算“作用内”借用

第 1 阶段是要计算出控制流图每个点的所有“作用内”借用（所谓作用内就是说借用的生命周期包含这个点）。每个借用都可以被表示为一个元组 ('a, shared|uniq|mut, lvalue)，它的含义是：

生命周期 'a 表示值被借用的范围
shared|uniq|mut 表示这是一个共享引用还是可变引用还是独占引用
- 独占引用和可变引用类似，但不允许通过独占引用修改值。它仅仅在对闭包的处理中使用，并非 Rust 语法的一部分。
lvalue 表示被借用的值

（译者：这里的借用是怎么来的呢）

那么如何计算呢？我们可以通过一种叫“不动点”的算法来完成。

首先，我们为 MIR 中的每一处借用（类似 tmp = &'a b.c.d 的赋值语句）创建一个元组，并且给它一个独一无二的索引 i。这样我们就可以用二进制位的方式表示某一点的所有“作用内”借用（其实就是一个借用的集合）。

（译者：举个例子，假如一段代码一共有三处借用，那么就可以用三个二进制位来表示某一点的“作用内”借用集合。比如，010 @ P 就表示点 P 的“作用内”借用集合包含第二处借用，不包含第一和第三处借用。）

其次，对于一个位于点 P 的语句，我们可以把它看成一个“转换函数”。这个“转换函数”对点 P 的“作用内”借用集合进行增删（其实就是对上面说的二进制进行置 0 和置 1 操作）。具体规则如下：

任何生命周期不包含点 P 的借用都被删除
如果这是一个借用语句，就增加这个借用到集合中
如果这是一个赋值语句 lv = <rvalue>，那么对以 lv 为前缀（还记得前边对前缀的定义吗？）的任何表达式的借用都被删除

最后一条规则需要解释一下。它允许我们支持类似 问题示例 #4 的情况：

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

在箭头所指的赋值语句这一点，对 (*list).value 的借用是“作用内”的，但在这条语句之后就不是“作用内”的了。这是因为变量 list 被赋予了新值，而新值还没被借用。更确切地说，一旦在 MIR 中看到赋值语句 lv = <rvalue>，我们就可以删除那些对以 lv 为前缀的表达式的借用。（在这个例子中，赋值语句是 list = ...，以 list 为前缀的表达式为 (*list).value）

特别注意：同样的借用，某些情况下赋值语句本身就是不合法的。比如下面的例子，list 是 List 而不是 &mut List：

fn main() {
    struct List<T> {
        value: T,
        next: Option<Box<List<T>>>,
    }

    let mut list = List { value: 1, next: None};
    let v = &mut list.value; // 借用发生在这里
    list = List {value: 2, next: None}; // 错误，不能给 list 赋值，因为 list 已经被借用了
    use_it(v); // 借用的使用在这里
}

fn use_it<T>(x: T) {}

（译者：最后，这个算法主体过程就是通过不断迭代求解每一点的“作用内”借用集合（下面用集合代替）。开始时，每一点的集合都是空集。然后开始第一轮迭代，迭代是从前向后的顺序，也就是代码的执行顺序，对于每一个点，先找到前置的点（前置的点可能有多个，因为控制流会有分支），取这些前置的点上一轮迭代的集合的并集（这作为输入集合），然后执行上面提到的“转换函数”，执行完就得到了这一点的集合（这是输出集合）。每一轮迭代都会更新每一点的集合（输入集合和输出集合），直到集合不再变动，也就是不动了，求解也就完成了。总的来说，这一切都是为了求出每一点的集合。）

借用检查第 2 阶段：报错

这一阶段，我们遍历 MIR，标记出不合法的操作，然后报错。我们只需要关注两种操作：

访问一个左值，可以进一步以两个维度进行区分（深还是浅，读还是写）
销毁（drop）一个左值

首先，我们看看如何提取 MIR 语句中包含的操作，这很简单直接：

StorageDead 语句，算是浅写
赋值语句 LV = RV 为对 LV 的浅写
还是赋值语句 LV = RV，在右值 RV 内：
- 每一个左值操作数不是深读就是深写，取决于左值的类型是否实现了 Copy trait（实现了就是深读）
  - 注意 move 是深写
- 共享引用 &LV 算是深读
- 可变引用 &mut LV 算是深写

要记住几点：

MIR 对枚举的判别式会特别对待，当你仅仅是检查判别式时，甚至不会产生借用（大概是这个意思，可以看看这个）。
对现在的编译器来说 Box 是内置在 MIR 中的。这篇 RFC 忽略这一点，假装只有引用(& &mut)和原生指针(*const *mut)这两种指针。尽管我们可以直截了当地扩展这里的论述来兼容 Box，但会引出一些关于 drop 如何处理的问题。

对于一个 MIR 语句，按照上面的方法提取出了操作，同时也知道了该语句开始处的“输入集合”（见上文），就可以按照下面的规则来决定是否需要报错了。

首先，介绍访问左值的规则。

等等，还得先说一下。当访问一个左值 LV 时，有两个维度去思考：

访问可能是深访问或者浅访问。
- 浅访问就是说 LV 本身被直接访问，但其中的引用或者指针不会被解引用。当前唯一的浅访问就是赋值语句，比如 x = ... 就是对 x 的浅写。
- 深访问就是说通过 LV 能够触达的一切数据都有可能被这次访问修改或者读取。
访问可能是读或者写。
- 读就是说已有数据被读取，但不会被修改
- 写就是说数据可能会被修改成新的值或者失效（比如说，move 导致的变量去初始化）

深访问通常是因为创建了一个别名，“深”反映了通过这个别名可能发生的一切。举例来说，如果有 let x = &mut y，这被认为是对于 y 的深写，尽管这次借用实际上还没被使用。这是因为我们创建了一个可变引用 x，它可以被用来修改 y 的一切。一个 move 比如 let x = y 也是一样的：它看上去貌似是对 y 的浅写，但我们可以通过 x 访问 y 之前能访问到的一切（所以它依然是对 y 的深写）。

判断一个访问操作是否合法的伪代码就像这样：

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();
    }
}

如你所见，它分为两步。首先，我们遍历“作用内”借用集合（输入集合）的一个和左值（lvalue）相关的子集，选取过程跟访问的深浅有关（具体选取规则见下文）。然后，对于每一个被选取的“作用内”借用，我们检查它是否和这次访问操作冲突（其实看代码很好懂。就是说，如果这次访问操作是读，但有可变的“作用内”借用，就冲突了。如果这次访问操作是写，那么只要有相关的“作用内”借用，就冲突，不管借用是可变还是不可变。），如果是我们就报一个错误。

（译者：下面是子集的选取规则）
在对 lvalue 浅访问的情况下，如果借用满足下面标准中的一条，我们就认为它是和 lvalue 相关的：

它是一个对 lvalue 的借用
- 因此：如果 a.b.c 被借用，那么对 a.b.c 赋值是非法的
它是一个对 lvalue 前缀的借用
- 因此：如果 a.b 被借用，那么对 a.b.c 赋值是非法的
lvalue 是被借用值的一个浅前缀
- 什么是浅前缀呢？就是在解析前缀的过程中，碰到解引用就停
- 因此：如果 a.b 被借用，那么对 a 赋值是非法的
- 但是：如果 *a 被借用，对 a 赋值是合法的，不管 a 是共享引用还是可变引用。（这里对应之前的 问题示例 #4）

在对 lvalue 深访问的情况下，如果借用满足下面标准中的一条，我们就认为它是和 lvalue 相关的：

它是一个对 lvalue 的借用
- 因此：如果 a.b.c 被可变借用，读取 a.b.c 是非法的
它是一个对 lvalue 前缀的借用
- 因此：如果 a 或者 a.b 被可变借用，读取 a.b.c 是非法的
lvalue 是被借用值的一个支撑前缀
- 支撑前缀前边说过了哈
- 因此：如果 a.b 被可变借用，读取 a 是非法的。但是，跟浅访问不同的是，如果 *a 被可变借用，读取 a 也是非法的。

其次，介绍销毁左值的规则。
销毁一个左值可以看作是一次深写，就像 move 那样，不过这是比较保守的做法。相关的规则还在积极地开发中，见#40。

	在我刚学习 `Rust` 的时候，我看过一遍 nll 的原文，那时候大概只能看懂一小部分。

	古语说，书读百遍其义自现，真的是一句真理。
	为什么通过反复读，有些不理解的地方就能理解就能想通了呢？
	我觉得很大一部分原因是，你对它越来越熟悉了，你对它里面提到的概念越来越熟悉了。
	你读第一遍的时候，一个概念是什么，你还要费力地想一想，
	读第二三遍的时候，你已经对这个概念建立了一种直觉，
	因此你的思考能量（类似于精力吧，是有限的）就可以用在其他更关键的地方。

	我之所以想翻译这篇 RFC，原因之一是想锻炼一下自己的英文；
	原因之二是这篇 RFC 经常被引用（比如 Rust 社区的回帖）；
	原因之三是我读过很多翻译的技术文章，都感觉翻译得还不如不翻译。
	我认为真正的翻译，你就得做到尽量本土化，让一点不会英文的人也能够理解你在说些什么。
	但这确实很难，首先你自己都不一定完全理解原文表达的是什么，
	其次是本土化可能会丢失某些不易察觉的细节（比如语气、态度之类的东西，有时候这些东西对理解也是有很大影响的）。

	我的翻译不保证 100% 准确，极少数地方甚至不能保证是正确的，还请专业人士斧正。
	总之我尽力了，尽可能让更多人能看懂它。
	另外，我只翻译了 RFC 的主体部分，剩下的实在是没什么精力继续了，
	只能说学好英文真的很重要，还是看原文好。