本家Rustコンパイラのソースを読もうとしてみる（1）

はじめに

Rustの本家コンパイラであるrust-lang/rustのソースコードを読んでみたい。巨大なソースを道しるべなしで読んでいくのはだいぶ厳しいのだが、Guide to Rustc Developmentという便利なガイドがあるので、これをベースに見ていこうと思う。最初は記録などを残さずチマチマ読んでいたが、モチベーション向上と後で思い返せるように記録を取る意味で記事として残しておくことにしてみた。

個人的に必要な情報を中心に見ていくため、現時点で興味の薄い部分は読み飛ばしたりもしているので、そのあたりはご了承下さい。また、ソースもドキュメントも日々更新されているため、最新とは異なる可能性があります。読み始めたのが2020年7月くらいからです。

目次

• 本家Rustコンパイラのソースを読もうとしてみる（1）
  　rustcのビルド方法、プロジェクト運用、ソースの概観など。
• 本家Rustコンパイラのソースを読もうとしてみる（2）
  　ソースコードからtoken列、ASTへの変換。
• 本家Rustコンパイラのソースを読もうとしてみる（3）
  　単純なASTからHIRへの変換、Visitorトレイト。
• 本家Rustコンパイラのソースを読もうとしてみる（4）
  　MIRの説明、HIRからTHIR、MIRへの変換
• 本家Rustコンパイラのソースを読もうとしてみる（5）
  　型チェックと、型推論の触り。
• 本家Rustコンパイラのソースを読もうとしてみる（6）
  　トレイト解決と借用チェックの概要。
• 本家Rustコンパイラのソースを読もうとしてみる（7）
  　MIRの最適化とコード生成。なんとか完結。

Building and debugging rustc

主にRustコンパイラをソースからビルドする方法が記載されている。

中心となるツールはリポジトリのトップディレクトリにあるx.pyというPythonスクリプトになる。様々な操作はこのスクリプトにサブコマンドを与えて実行していくようだ。一番シンプルにビルドするならこんな感じだろう。

$ git clone https://github.com/rust-lang/rust.git
$ cd rust
$ cp config.toml.example config.toml
$ ./x.py build

Bootstrapping

コンパイラのソースをコンパイルするコンパイラはどうなってるの？とかの説明が記載されている。Rustコンパイラのビルドは大きな流れとして、Stage 0→Stage 1→Stage 2と進んでいき、それぞれのStageでコンパイラが生成される。

• Stage 0は、現在のBetaだ。なのでバイナリをダウンロードしてくるのみになっている。
• Stage 1は、Stage 0のコンパイラを用いてソースをビルドしたものだ。
• Stage 2は、Stage 1のコンパイラを用いてソースをビルドしたものだ。

Stage 1とStage 2はほとんど違いがなく、大抵の確認ではStage 1で十分とのこと。Stage 2はリリース時や最終チェックなどで使われるようだ。ビルドもデフォルトではStage 1までを生成するようになっている。
（私がこのガイドを読み始めたときはStage 2までビルドするのがデフォルトだったが、つい最近Stage 1までに変更されたようだ。ドキュメントの変更は2020/07/29。）

かなりざっくり解釈したが、実際は標準ライブラリのビルドとかも絡むためもう少し複雑になる。基本的にビルドには結構時間がかかるため、部分コンパイルだったり、いろいろとノウハウも書いてある。

必要スペック

ビルドにはそれなりのスペックが必要になる。

• 15GBのディスクスペース
• 8GB以上のメモリ
• 4コア以上のCPU
• インターネットアクセス

そんなにスペックを与えていない仮想マシンでビルドしようとしたら、ビルドできないことも多々あった。特にrustc_middleのビルドに相当のメモリが必要のようで、ビルド中にメモリが足りなくなってマシンがハングしてしまったりした。

その他

ドキュメント関連の説明も書いてあるが、ここでは飛ばす。他にはおすすめの環境設定などが記載されている。

Contributing to Rust

※2020/12/11追記
私が知る中で日本で一番Rustコンパイラに貢献しているJohnTitorさんがcode contributionについての記事を投稿してくれました！私の記述は不勉強もあり正確でない可能性がありますので、貢献方法に関してはそちらの記事を確認するのがいいと思います。
※追記ここまで

Rustの本家ソースにコントリビュートする際の流れが書いてある。開発体制や、開発の流れのようなことも書いてある。現状ではあくまでソースコードを読むのが目的なので、いくつか拾って見ていこう。

メンバーシップ

Rustにたくさん貢献すると、r+という権限が与えられるようだ。この権限があるとRustのプロジェクトで活躍するborsというbotに指示を飛ばすことができる。また、r+の権限が与えられると同時にhigh-fiveという枠組みにも追加される。ここに追加されるとソースのPRのレビュアーとしてランダムに選ばれたりするらしい。
メンバーシップに興味があるなら、まずはE-easyとかE-mentorのタグがついたissueから始めていきましょうとのこと。

安定化プロセス

Rustのfeatureはまずunstableとして実装され、問題なければstableに昇格される。安定化は大まかに以下のプロセスで行われる。

1. Documentation PRを作成する。安定化されていないfeatureは多くの場合Unstable Bookにドキュメントが記載されているが、これは正式な仕様としてReferenceなどに書き移すためのPR。
2. Stabilization reportと呼ばれる、安定化の要点をまとめたレポートを作成する。
3. FCP（Final Comment Period）と呼ばれる期間を設け、チームメンバーがレビューを行う。
4. Stabilization PRを作成する。安定化されていないfeatureをコード内で使うには#![feature(XXX)]を付ける必要がある（feature-gate）が、これはそれを外すための変更と、リポジトリのコード内でそれらが使われている場合に削除するためのPR。

Notification groups

Notification groupsと呼ばれる、Rustに貢献したいけど大きいプロジェクトにいきなりcommitするのはちょっと、、という人のための気軽な貢献ができるような仕組みがある。

グループはいくつかあるが、例えばCleanup Crewではbug reportに対して、再現のための最低限の条件を見つけたり、関連するバグのリンクを追加したり、情報の精度を高めるような作業による貢献が可能になっている。ICEBreaker-Cleanup-Crewというタグが付いているissueがこれにあたる。

High-level Compiler Architecture

コンパイラの大まかな方針と、他のコンパイラにはない特徴などが解説されている。このあたりからはコンパイラというものに対する基礎知識が多少必要になってきそうだ。（ASTとは何か？みたいな説明はない。）

内部表現

コンパイルの流れについて、データの内部表現に着目しながら追っていこう。

• Token stream: ソースコードはまずlexerによりtoken列に変換される。
• AST(Abstract Syntax Tree): 単純なtoken列から木構造であるASTに変換される。ここでマクロの展開や、一部のsyntax checkなどが行われる。
• HIR(High-level IR): ASTと構造的には変わらないがsyntax sugarがdesugarされ、型なども明示的に示されるようになる。ここでtype checkやprivacy checkが行われる。
• MIR(Middle-level IR): これまでの木構造からCFG（Control-Flow Graph）という形式に変換される。単純なstatementからなるbasic blockと、その間をつなぐcontrol flow edgeで構成されている。ここではborrow checkや様々な最適化が行われる。
• LLVM IR: RustはバックエンドにLLVMを用いているため、最後にLLVM IRを出力して、コンパイラの仕事としては完了となる。

MIRとLLVM IRはrustcにオプションを指定すれば出力できる。

$ rustc main.rs --emit=mir,llvm-ir

HIRはnightlyのみで使えるオプションを指定すれば出力できる。

$ rustc main.rs -Z unpretty=hir

Query system

Rustコンパイラは戦略として、query systemというものを採用している。世の中の大抵のコンパイラは、複数のパスを常に決められた順序でシーケンシャルに実行していく流れになっているが、query systemでは用意されたいくつものqueryを必要に応じて呼び出すことを繰り返して実行していく。例えば、あるコードのLLVM IRを要求するqueryを発行すると、LLVM IRを生成するには最適化されたMIRが必要になり、最適化されたMIRのためにはborrow checkが必要になり、borrow checkにはさらに、、というように連鎖的にqueryが発行され、最終的な結果にたどり着いていく。

query systemにおいて各queryの結果はディスクに保存され、それを適切に参照することによりincremental compilation、つまりソースを修正して再コンパイルする場合に無駄なくコンパイルできるようにしている。

しかし、Rustコンパイラは最初からこのquery systemの戦略をとっていたわけではなく、まだ全ての処理に対しての適用はできていないようだ。この記事を書いている時点では、HIRからLLVM IRの間のプロセスはquery systemとして提供されているとのこと。

ソースの構成

タイトルなどでもRustコンパイラと書いているが、rust-lang/rustにはコンパイラだけでなく、標準ライブラリ（std、coreなど）や各種ドキュメント、テストコードなどが含まれている。ディレクトリ構成などは、ちゃんとソースを読むところで確認していきたい。

その他

他にもメモリ管理や並列コンパイルの話題も記載されているが、ちょっとまだ理解しきれていないので置いておく、、

つづく

本来の目的であるソースコードにまだたどり着いていないのだが、キリがいいのでこのあたりで一旦終わろうと思う。次回からはソースコードをどんどん見ていきたい。

本家Rustコンパイラのソースを読もうとしてみる（2）←次回