Non-Lexical Lifetimesって？

Rust 2018 Edition の最初のリリース、Rust 1.31.0でstabilizeされた新しいリージョン推論システムの名前。

または、Rustの借用システムにおけるノンレキシカル・ライフタイム（レキシカルスコープではなく制御フローグラフに基づくライフタイム）対応への拡張。

これにより、（主に式をまたいだライフタイムの）より柔軟なリージョン推論が可能になりました。

Announcing Rust 1.31 and Rust 2018を読むと、「エラーメッセージがわかりやすくなってデバッグが簡単になりました」と書いてありますが、実際はできること自体が増えています。

今回ちょっと時間が無かったため、RFCで例に上がっているコードをコンパイルしてみて確認してみました程度になってしまいました。

追記:コメントで将来的にRust 2015 EditionでもNLL(Non-Lexical Lifetimes)が有効になる予定との情報をいただきました、遡及的な修正だ。ありがとうございました。

ライフタイムについて

RFC 2094 (non-lexical lifetime) に使われている用語を使うことにします。

RFCによると、Rustのライフタイムは2つの意味で使われている。

参照が使用される期間に対応する、「参照のライフタイム」
値が解放されるまで（別の言い方をすると、値のデストラクタが呼ばれるまで）の期間に対応する「値のライフタイム」

この2つを区別するために「値のライフタイム」を**「スコープ」**と呼ぶことにします。

当たり前だが重要なこととして、「値の参照が作成されるとき、その参照のライフタイムはそれの指す値のスコープより長くなることはない」という事実があります。
そうでなければ、その参照は解放されたメモリを指すことになるためです。

RFCに説明されているいくつかの例を見て理解を深めていきましょう。

今までの何がダメだったのか

レキシカル・ライフタイムは無駄にスコープがでかく推論されすぎ
そのせいで余計な回避策に翻弄される
そのせいでエラーメッセージもわかりにくい

ケース1 変数に代入された参照

次のコードを見てください。
scoreは参照である。
Rust 2015 Editionでは、この変数のライフタイムは変数の存在するブロックと同じスコープであることが要求されます。

fn main() {
    let mut scores = vec![1, 2, 3]; // --+ 'scope
    let score = &scores[0];         //   |
//  ^~~~~~~~~~~~~~~~~~~~~ 'lifetime //   |
    println!("{}", score);          //   |
    scores.push(4);                 //   |
} // <-----------------------------------+

Rust 2015 Editionでは、pushがscoreの生存期間中に呼ばれるため、エラーとなります。
これはブロックを導入し、scoreのライフタイムを小さくすることで解決できます。

fn main() {
    let mut scores = vec![1, 2, 3]; // -------------+ 'scope
    { //                                            | 
        let score = &scores[0]; // <-+ 'lifetime    |
        println!("{}", score);  //   |              |
    } // <---------------------------+              |
    scores.push(4); // OK!                          |
} // <----------------------------------------------+

これは美しくない解決策です。
変数scoreはprintln!の以降使われることはありません！
そのことをプログラマが明示的にいちいち示さなければならないのです。
Rust 2018 Editionのリージョン推論ではscoreの持つ参照のライフタイムがscoreの使用期間と同程度に小さくなるように推論されます。

ケース2 条件付きの制御フロー

次のケースはmatch式です。
これはマップまわりでよく現れます。
制御フローのある腕で参照が用いられているが、match式全体でmapが借用されているためエラーになるパターンです。

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

残念ながらこれもRust 2015 Editionではコンパルエラーです。
しかし、これも比較的簡単にエラーを回避できます。

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

mapの変更部分を制御フローから分離します、するとマップが借用中ではなくなるのでコンパイルが通るようになります。
これも非常に美しくない解決策です。
Rust 2018 Editionではこれもコンパイルできるようになりました。
実行可能なコードをplaygroundで書いておいたのでAdvanced optionsからEditionを変えてコンパイルして見てください！

ケース3 関数をまたいだ条件付き制御フロー

これはコンパイル可能ではありませんが、エラーメッセージは劇的にわかりやすくなったと思います。
コードはいい感じのエラーメッセージになるように多少いじってあります（~~多少とは言っていません~~）。

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

fn main() {
    let mut map: HashMap<&str, i32> =
        [("Norway", 100),
         ("Denmark", 50),
         ("Iceland", 10)]
         .iter().cloned().collect();

    {
        let key = "Norway";
        let v = get_default(&mut map, key); // -+ 'r
          // +-- get_default() -----------+ //  |
          // | match map.get_mut(&key) {  | //  |
          // |   Some(value) => value,    | //  |
          // |   None => {                | //  |
          // |     ..                     | //  |
          // |   }                        | //  |
          // +----------------------------+ //  |
        println!("{}", v);                  //  |
    } // <--------------------------------------+

}

Rust 2015 Edition でのコンパイルエラーは次のようになります。

error[E0499]: cannot borrow `*map` as mutable more than once at a time
  --> src/main.rs:10:13
   |
7  |     match map.get_mut(&key) {
   |           --- first mutable borrow occurs here
...
10 |             map.insert(key, V::default());
   |             ^^^ second mutable borrow occurs here
...
14 | }
   | - first borrow ends here

error[E0499]: cannot borrow `*map` as mutable more than once at a time
  --> src/main.rs:11:13
   |
7  |     match map.get_mut(&key) {
   |           --- first mutable borrow occurs here
...
11 |             map.get_mut(&key).unwrap()
   |             ^^^ second mutable borrow occurs here
...
14 | }
   | - first borrow ends here

対して、Rust 2018 Edition でのコンパイルエラーは次のようになります:

error[E0499]: cannot borrow `*map` as mutable more than once at a time
  --> src/main.rs:10:13
   |
2  |   fn get_default<'r,K,V:Default>(map: &'r mut HashMap<K,V>,
   |                  -- lifetime `'r` defined here
...
7  |       match map.get_mut(&key) {
   |       -     --- first mutable borrow occurs here
   |  _____|
   | |
8  | |         Some(value) => value,
9  | |         None => {
10 | |             map.insert(key, V::default());
   | |             ^^^ second mutable borrow occurs here
11 | |             map.get_mut(&key).unwrap()
12 | |         }
13 | |     }
   | |_____- returning this value requires that `*map` is borrowed for `'r`

error[E0499]: cannot borrow `*map` as mutable more than once at a time
  --> src/main.rs:11:13
   |
2  |   fn get_default<'r,K,V:Default>(map: &'r mut HashMap<K,V>,
   |                  -- lifetime `'r` defined here
...
7  |       match map.get_mut(&key) {
   |       -     --- first mutable borrow occurs here
   |  _____|
   | |
8  | |         Some(value) => value,
9  | |         None => {
10 | |             map.insert(key, V::default());
11 | |             map.get_mut(&key).unwrap()
   | |             ^^^ second mutable borrow occurs here
12 | |         }
13 | |     }
   | |_____- returning this value requires that `*map` is borrowed for `'r`

最後のエラーメッセージで

 returning this value requires that `*map` is borrowed for `'r`

と教えてくれるようになりました！

ケース4 &mut 参照の変更

とりあえず、Some(n)が間違っているような気がするのでSome(mut n)に変更。
これもコンパイルが通りません。

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(mut n) = list.next.as_mut() {
            list = &mut n;
        } else {
            return result;
        }
    }
}

Rust 2015 Edition でのエラーメッセージです。
無駄にメッセージが多いですが、わかりにくいことこの上ない感じですね。

error[E0597]: `n` does not live long enough
  --> src/main.rs:11:25
   |
11 |             list = &mut n;
   |                         ^ borrowed value does not live long enough
...
14 |         }
   |         - borrowed value only lives until here
   |
note: borrowed value must be valid for the anonymous lifetime #1 defined on the function body at 6:1...
  --> src/main.rs:6:1
   |
6  | / fn to_refs<T>(mut list: &mut List<T>) -> Vec<&mut T> {
7  | |     let mut result = vec![];
8  | |     loop {
9  | |         result.push(&mut list.value);
...  |
15 | |     }
16 | | }
   | |_^

error[E0499]: cannot borrow `list.value` as mutable more than once at a time
  --> src/main.rs:9:26
   |
9  |         result.push(&mut list.value);
   |                          ^^^^^^^^^^ mutable borrow starts here in previous iteration of loop
...
16 | }
   | - mutable borrow ends here

error[E0499]: cannot borrow `list.next` as mutable more than once at a time
  --> src/main.rs:10:30
   |
10 |         if let Some(mut n) = list.next.as_mut() {
   |                              ^^^^^^^^^ mutable borrow starts here in previous iteration of loop
...
16 | }
   | - mutable borrow ends here

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

warning: variable does not need to be mutable
  --> src/main.rs:10:21
   |
10 |         if let Some(mut n) = list.next.as_mut() {
   |                     ----^
   |                     |
   |                     help: remove this `mut`
   |
   = note: #[warn(unused_mut)] on by default

次に、Rust 2018 Editionでのエラーメッセージでございます。
非常に簡潔でわかりやすいですね。

error[E0597]: `n` does not live long enough
  --> src/main.rs:11:20
   |
6  | fn to_refs<T>(mut list: &mut List<T>) -> Vec<&mut T> {
   |                         - let's call the lifetime of this reference `'1`
...
11 |             list = &mut n;
   |             -------^^^^^^
   |             |      |
   |             |      borrowed value does not live long enough
   |             assignment requires that `n` is borrowed for `'1`
...
14 |         }
   |         - `n` dropped here while still borrowed

おわりに

冒頭で若干用語を使ってしまいましたが、今までレキシカル・ライフタイムだったのがノンレキシカルになって何になったのかというと、制御フローグラフです。

直感的には、新しい提案では、参照のライフタイムはその参照が後に使用される可能性のある関数の一部分（コンパイラの記述における、参照が生存している部分）に対してのみ有効となります。

制御フローグラフをベースにするということ以外に、「部分型をチェックする際に位置情報を考慮する必要もある」という事情も発生する。

Rust 2015 Editionは 'a が 'b よりライフタイムが長い場合（'a: 'b）&'a () は常に &'b () の派生型となる。これはすなわち、 'a は関数のより大きな一部分に対応することを意味します。
Rust 2018 Editionでは、部分型付けは特定の点 P に対し設定される．このような場合，ライフタイム 'a は点 P から到達可能な 'b 内のある部分に対してのみ長く生存 (outlive) すれば良いということになりました。

この話はこの後延々と続けることができるのですが、Non-Lexical Lifetimesの唯一の欠点として詳細の理解が普通のプログラマには著しく困難になったということがあり、このあたりでお茶を濁したいと思います。