Rustの型システムの恩恵：言語処理系としての観点から

この記事は、Rust Advent Calendar 2020の11日目の記事です。昨日は@tasshiさんによる、公開APIのインターフェースで利用している外部クレートはRe-exportする（と良さそう） でした。

この記事では、Rustの型システムがなぜ素晴らしいかということを、多分他の人はあまりしていなかったであろう変わった観点から考えてます。まず、Rustの型システムについて非常に簡単におさらいをした上で、

• iterator invalidation
• match-guardのmutable reference

という2つの例から、Rustの型システムのおかげで、処理系が効率性を維持しつつ安全性を担保することができる様子を眺めます。

Rustの型システムにより得られるinvariant

簡単にRustがどういうシステムを与えているのかを紹介します。ご存知の方も多いと思うのでスキップしてもらって問題ありません。そもそも、ここではかなり端折っておさらいするので、適切な理解のためには、The Rust Bookなどを参照するべきだとは思います。

Rustはownership systemにより各値が誰にownされているかを厳格に管理しています。例えば、次のようなプログラムを考えると、

fn printer(s: String) {
    println!("{}", s);
}

fn main() {
    let s = String::from("hoge");
    printer(s);
    printer(s); // invalid
}

このプログラムはコンパイルできません。というのも、sのonwershipは一度目のprinter(s)で既に放棄しているのにも関わらず、再びその値の利用しているからです。

error[E0382]: use of moved value: `s`
 --> own.rs:8:13
  |
6 |     let s = String::from("hoge");
  |         - move occurs because `s` has type `String`, which does not implement the `Copy` trait
7 |     printer(s);
  |             - value moved here
8 |     printer(s); // invalid
  |             ^ value used here after move

error: aborting due to previous error

For more information about this error, try `rustc --explain E0382`.

このシステムを採用することで、誤った値の利用を防げたり、適切なメモリ管理やリソース管理等が行えるようになります。ただし、この仕組みだけでは基本的にプログラミング言語としての利便性に支障があります。例えば、上の関数で、同じ文字列の値を二度printしたいときに、毎度printerがownershipを受け取って返して、をしなければならないと思うと、不便さが明らかでしょう（チューリング完全だからといって、それだけでいいわけじゃない）。

そこで、ownershipを「一時的に」借用するという概念が生まれます。
Rustには二種類の借用があります。&と&mutです。通常は、&mutとあるように、mutつきの借用はmutableな借用、&は読み込みしかできない借用であるなどと説明され、その後で&mutの生存期間中(今回lifetimeという概念を飛ばしますが、「参照が有効である時間」を生存期間といいます)、他のいかなる借用も存在しないもので、&の借用は同時に別に&の借用が共存できるというような説明をすると思います。

これは個人的な気持ちですが、特に後者の部分をinvariantだと思うのが気持ちが良いと思っています。つまり、Rustの型システムは

• &mutは生きている間はuniqueであることが保証されている
• &はそうではない

というinvariantを保証します、と思うと個人的に気持ちがいいです。そして、このinvariantがいかに処理系にとって嬉しいかを論じるのが本稿になっています。

（や、保証するのは本当にそうなので、気持ちがいいとかいう話とは本来無縁なんですが、どちらを頭に置くか、という問題で、&mutはuniqueが保証された借用です、と思ってしまえば、

• &mutの参照の値を書き換えてもいかなるレースコンディションも引き起こさないし、
• CellやMutexを"interior mutability"みたいな言い方をしなくても、単に複数shareしても安全に変更できることが保証されている"モノ"

というふうに理解ができて、自然だと思っています、という話です）

システムの"ありがたみ"を、処理系の観点で

このような型システムにより""制約""を与えることにより得られるユーザーサイドのありがたみは、既にたくさん語られていると思います。今回この記事では、少し"奇妙"な観点として、システムにより与えられるinvariantによりコンパイラを効率的かつ安全に実装できるということを、興味深い２つの例を通して説明します。

iterator invalidation

C++のような言語では「あるイテレータを回す間に、それを変更するような操作を加えてはいけない」というルールがあることはご存知でしょうか。
例えば以下のようなプログラムを考えてみましょう。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v {100, 200};
    for (const auto &x : v) {
        v.emplace_back(300);
        cout << x << endl; // vの最初の要素....100だな！
        break;
    }
}

このプログラムを私の環境でコンパイルして実行すると次のようになります。

$ g++ invalid.cpp -o invalid && ./invalid
0

なぜでしょう？std::vectorのreferenceを見に行くと次のようなことが書いてあります。

上の例ではemplace_backしたタイミングでcapacityに変化が起きたので、iteratorのinvalidationが起きたのだとわかります（察することができると思いますが、invalidなiteratorはsingular（どのコンテナにも属していないiterator）な可能性があって、singularなiteratorをdereferenceするのはundefined behaviorです)。

vectorを普通に使ってるだけなのに！ と少し思いませんか？実際のところこういうコードを書いてはいけないというのはC++を書く人にとっては当たり前だと思いますし、注意して書いていれば引っかかることはないかもしれませんが、注意してプログラムを書かないと、プログラムが脆弱になってしまうと思うと私は少し嫌な気持ちになります。

本題です。Rustを書いているとき、このようなことを気にする必要があるでしょうか？

fn main() {
    let mut v = vec![100, 200];
    for x in v.iter() {
        v.push(300);
        println!("{}", x);
    }
}

このプログラムをコンパイルしてみると、

$ rustc valid.rs
error[E0502]: cannot borrow `v` as mutable because it is also borrowed as immutable
 --> valid.rs:4:9
  |
3 |     for x in v.iter() {
  |              --------
  |              |
  |              immutable borrow occurs here
  |              immutable borrow later used here
4 |         v.push(300);
  |         ^^^^^^^^^^^ mutable borrow occurs here

error: aborting due to previous error

For more information about this error, try `rustc --explain E0502`.

怒られます。当然iteratorを回しているときには、元のcollectionは変更できないわけです。もちろん、上述したstd::vectorのemplace_backでiteratorがinvalidateされる条件を考えると、これは少し保守的です。というのも、capacityに余裕があるということが分かっているときならば、上のプログラムはundefined behaviorにはならないからです（もっとも違う言語間で比較するのは少し乱暴ですが）。しかし、デメリットがそういったプログラムを書けなくなるという点だけであると考えればiterator invalidationの文脈では、Rustの型システムは非常に良く状況を捉えていると言えます。

このような理由で、Vectorのpushという操作は「&mut借用がその生存期間ではunique」という性質をフルに仮定することで、効率性と安全性を（非常に少ないデメリットで）実現している例、と見ることができると思います。こういったところからもRustの型システムがきつすぎず弱すぎない良い感じの制約をユーザーに課していると思っています（最後は感想です）。

余談

余談ですが、iterator invalidationは案外根深い問題で、上のようにC++だとundefined behaviorになりますし、Javaなどで似たようなことをすると、

import java.util.*;

class Test {
    public static void main(String[] args) {
	ArrayList<Integer> array = new ArrayList<Integer>();
	array.add(1);
	array.add(2);
	Iterator iter = array.iterator();
	while(iter.hasNext()) {
		array.add(3);
		System.out.println(iter.next());
		break;
	}
    }
}

Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1042)
	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:996)
	at Test.main(Main.java:12)

実行時に例外を吐かれます。この挙動って、結構気持ち悪いと思いませんか？（気持ちがいいという人は教えて下さい）

余談2: TSGCTF 2 std::vector

C++のiterator invalidationそんなに悪いことでしょうか？ 100と表示されるべきときに0と表示されるくらいでは？

結論としてはそれにとどまらない問題です。もちろん最後は処理系依存の話になりますが、多くの処理系においてはこのバグはUse After Free(UAF)という脆弱性につながります。今私が利用している環境では、大雑把に言えば、vectorというのは内部的にはmallocで確保されたバッファを必要に応じて伸び縮みさせる構造で、イテレーターはそのバッファ中のどこかを指しているポインタです。emplace_backをする際、capacityが変わればiteratorがinvalidateされる、というのは、基本的には、追加しようとしたバッファが小さかったのでreallocして新しいバッファにしたら、元のバッファのポインタを指していたiteratorは無効になるということを指しています。つまりそのiteratorを介した処理は全てUAFになります。

私の趣味はCTF(Capture The Flag）というゲームをすることで、今年は私が所属するチームとしてTSGCTFという大会を開催したのですが、そこではこのネタをベースにした問題を出題しました。内容は、「C++のstd::vector及びiteratorのPythonラッパライブラリがあったとき、このPythonライブラリを通してシェルが起動できるか」という問題です。興味があったら、GitHubで問題が公開されているので考えてみてください。

match guardにおける「条件書き換え」

iterator invalidationは現実でも起こりうるタイプのミスでしたが、今度はもっとマニアックな話に移りたいと思います。

現代的なプログラミング言語で提供されている言語機能であるパターンマッチについて細かく考えてみましょう。一番典型的な使い方の一例は次のようなものになるんじゃないでしょうか。

enum T {
    X,
    Y(u32),
    Z(u32, u32),
}

use T::*;

fn f(x: T) -> u32 {
    match x {
        X => 0,
        Y(x) if x < 100 => 1 + x,
        Y(_) => panic!("too big"),
        Z(x, y) => 101 + x + y,
    }
}

fn main() {
    let x = X;
    let y = Y(1);
    let z = Z(1, 2);
    println!("{}, {}, {}", f(x), f(y), f(z));
}

関数fの中では、パターンマッチをして、何らかの非負整数を返していますね。ところで、気になるところがありますね。

match x {
        X => 0,
        Y(x) if x < 100 => 1 + x,
        ...
}        

このif x < 100 の部分ってどういう式が書けるんでしょう？The Rust Referenceによれば、この部分には構文的には任意の式が許されているようです。Rustでは、殆どのものが式です。例えばこんなことができます。

fn main() {
    match 1 {
        _ if {loop{}; false} => println!("hey"),
        _ => panic!("not x"),
    }
}

こんなことして何の得があるでしょう？実は、コンパイラの観点で考えると、ここに好きな式が書けるという事実は、結構厄介な問題をはらんでいます。iterator invalidationでは、C++を引き合いに出しましたが、今度はもっと安全そうな言語、OCamlを例に出しましょう。次のプログラムを考えます。（これは、issue7241のコメントから取ってきたものです）

type u = {a: bool; mutable b: int option}

let f x =
  match x with
    {a=false} -> 0
  | {b=None} -> 1
  | _ when (x.b <- None; false) -> 2
  | {a=true; b=Some y} -> y

let _ = f {a=true; b=Some 5}

これをコンパイルして実行してみましょう

$ ocamlopt broken.ml -o broken
$ ./broken
Segmentation fault (core dumped)

なんということでしょう。あのOCamlを、Obj.magicを使わずとも、プログラムごとcrashさせることができました。実際のところこれはかなり同情できる余地があります。OCamlのパターンマッチにおいて、（基本的には）不必要な条件分岐を最適化として削除しているからです。つまり、最後のパターンマッチにおいて、xの中身はSome _になっているはずで、当然dereferenceしていいはず（と錯覚している）ですが、それが条件部の書き換えによって、その仮定が壊されているのです。正直な話、match guardでmutable cellの書き換えをするようなプログラムは正気の沙汰ではないと思いますが、しかしコーナーケースはコーナーケースです。これをOCamlで上手に（効率を今と比べて落とさずに）解決する方法はまだ良く分からないという状況だと思います。

では、Rustではどうなるでしょう。近いコードを以下のようにかいてみました。

fn f(x: &mut (bool, Option<i32>)) -> i32 {
    match x {
        (false, _) => 0,
        (_, None) => 1,
        _ if ( {*x=(true,None); false} ) => 2,
        (true, Some(y)) => *y,
    }
}

fn main() {
   let mut x = (true, Some(5));
   println!("{}", f(&mut x));
}

コンパイルしてみましょう。

error[E0510]: cannot assign `*x` in match guard
 --> guard.rs:5:17
  |
2 |     match x {
  |           - value is immutable in match guard
...
5 |         _ if ( {*x=(true,None); false} ) => 2,
  |                 ^^^^^^^^^^^^^^ cannot assign

error: aborting due to previous error

For more information about this error, try `rustc --explain E0510`.

失敗しましたね。しかし不思議なエラーが出ました。このエラーは何でしょう。Rust Compiler Error Indexによれば、ある変数についてのmatchを行っているときに、match guardの中でその変数を書き換えてはいけない、と言われています。

これは、上述のmatch guardにおける「ちょうどよい制約（不必要に強すぎない制約で効率の良いmatchingを安全に可能にしている）」だと思いますが、これもRustの型システムが一役買っていることにお気づきでしょうか。これと同様の制約をOCamlでやろうとしても、同じ変数への参照を複数持ちうるので、match guardしている変数に着目しているのでは当然足りません。

しかも、Rustの制約は本当に最小限であることは次のプログラムを考えれば分かります

fn f(x: &mut (bool, Option<i32>)) -> i32 {
    let y = &mut (true, Some(1));
    match x {
        (false, _) => 0,
        (_, None) => 1,
        _ if ( {*y=(true,None); false} ) => 2,
        (true, Some(y)) => *y,
    }
}

fn main() {
   let mut x = (true, Some(5));
   println!("{}", f(&mut x));
}

match-guardの中で書き換える変数を、今matchしている変数とは関係のないyに変えただけですが、このプログラムのコンパイルは通ります。guardの中でmutationを行うこと自体珍しいと思いますが、しかしだからといってそれら全てを捨て去るのではなく、安全性・効率性・利便性を担保する、とても良くできていると思いませんか。

SECCON CTF 2020 mlml

先程のiterator invalidationに関連させた問題をCTFに出したという話もしました。実はこのOCamlに関連したunsound holeに関連した問題も今年のSECCON 2020 Qualsで出題しました。実際OCamlで、Obj.magic（やunsound features、当然processを起動する関数など）を使わずにシェルを起動してみたいと思いませんか？こちらも問題が公開されているのでぜひ考えてみてください。

2つの例を通して

実際のところどちらの問題も、効率さを犠牲にしたり、構文を強く制約すれば、memory corruption等につながらずに処理系を設計することは可能だと思いますが、しかしこのようなコーナーケースのために、他の多くの"普通の"場合においても影響を受けるような仕様にしてしまうことはあまり好ましいことではないでしょう。
Rustはそういった観点では、その型システムのおかげで、過度に安全サイドに傾けすぎることはなく、一方で効率さを維持したままプログラムを処理することが可能になっています。これはまさに型システムの恩恵を預かっていると言ってよいのはないでしょうか。

余談

さらなる余談ですが、Rust自体にsoundness holeが無いかと言えばそういうわけではなく、結構興味深いsoundness holeがいくつかあります。
有名なものとしては次のようなものがあります

• issue28728: LLVMが副作用のない無限ループを削除してしまう問題
  • uenokuさんの解説
• issue25860: lifetime推論のバグ
  • 私の解説
• issue57893
  • Bataさんの解説

明日は、tomoyuki-nakabayashiさんが「何か組込みっぽいことを…」を書いてくださるそうです。楽しみですね。