Rustコンパイラのソースコードリーディング

これはKMC(京大マイコンクラブ)アドベントカレンダー2021 の3日目の記事です。

昨日の記事はうたがわききさんの「List::Utilのpairs関数がPythonで欲しくなって」でした。

はじめに

こんにちは。一回生のたまろんです。最近は言語処理系を読んだり書いたりしています。

この記事では、コンパイラを読んだことがない人を対象に、Rustコンパイラ(rustc)のソースコードを解説します。 Rustは性能、メモリ安全性、安全な並行性を目指して設計されたマルチパラダイムプログラミング言語です。近年注目を集めている言語でLinux, npm, Dropboxなどに採用されています。

コンパイラの処理

rustcはバックエンドにLLVMを使っています。rustcはソースコードLLVM-IRになるまでに以下の5つの形に変換します。

そして、次の過程によって変換 (+解析) が行われます。

  1. トークナイズ (ソースコードトークン列)
  2. パース (トークン列 → AST)
  3. マクロ展開, ASTの検証、型検査 (AST → THIR/HIR)
  4. Lowering (HIR → MIR)
  5. コード生成 (MIR → LLVM-IR)

rustcのソースコードは以下にあります。

github.com

ディレクトリは以下の通り

  • compiler : rustc本体
  • library : 標準ライブラリ
  • src : テストスイート、rustdocなど

この記事ではcompilerフォルダ以下のコンパイラドライバ、レクサー、パーサーを中心に見ていきます。

DriverとInterfaceまわり

rustcの実質的なエントリーポイントはコンパイラドライバのクレート (/compiler/rustc_driver) のmain関数です。 main関数から、RunCompiler.run関数が呼び出され、その内部で以下のinterface::run_compiler関数が呼び出されます。

rustc_interfaceクレートはrustcをライブラリとして使うときのコンパイラのエントリーポイントになります。(理由は外部からサードパーティ製の解析や最適化をかけるため)

pub fn main() -> ! {
    ...
    let exit_code = catch_with_exit_code(|| {
        let args = env::args_os()
            .enumerate()... ;
        // run内部で以下のrun_compiler関数が呼び出される
        RunCompiler::new(&args, &mut callbacks).run()
    });
    ...
    process::exit(exit_code)
}
pub fn run_compiler<R: Send>(mut config: Config, f: impl FnOnce(&Compiler) -> R + Send) -> R {
    tracing::trace!("run_compiler");
    ...
    // configからCompiler構造体を作りクロージャ内に渡す
    interface::run_compiler(config, |compiler| {
        ...
        let linker = compiler.enter(|queries| {
            let early_exit = || sess.compile_status().map(|_| None);
            // パースを行うクエリを起動する
            queries.parse()?;
            ...
        })
    ...
}

このrustc_driver::run_compiler関数では第一引数のconfigからCompiler構造体を作り、第二引数のクロージャに渡しています。configにはコマンドライン引数や出力ファイル名といったコンパイラの設定情報が入っています。

また、注目すべき箇所はqueries.parse()?の行です。これは要求駆動コンパイルの処理の一部になっています。この関数を追っていくと、rustc_parser::parse_crate_from_file関数にたどり着きますが、ここで実際にソースコードのパースが行われます。

要求駆動コンパイル

要求駆動コンパイルは、メモ化を利用した高速なコンパイル方法です。クエリを使うことで差分に注目するインクリメンタルなコンパイルが可能になります。

クエリは入力に対して、何かを計算して出力します。 例えば type_of クエリはあるアイテムの def_id が与えられるとそのアイテムの型を計算します。

例えば、実際のコンパイル全体はクエリ駆動になります。

  1. トップレベルの compile クエリがコード生成の必要があるモジュールのリスト (codegen-units)を取得する
  2. codegen-units のリストを計算する際に、ソースコードで定義されているすべてのモジュールのリストを返すクエリがさらに呼び出される
  3. 呼び出されたクエリによって、さらにクエリを呼び出される
  4. 以下繰り返し

ParserとLexer

パーサー (/compiler/rustc_parser/src/parser) では、Parser構造体に対して実装されているparse_xxxxの名前の関数がxxxxをパースします。(例えばparse_stmt, parse_exprはそれぞれ文と式をパースします。)

レクサー (/compiler/rustc_parser/src/lexer) は内部で別のrustc_lexerクレートを使っていて、このクレートで文字列のパターンマッチを行います。 (以前は同じクレートだったけど、ライブラリ化するために分けたそうです。)

次のcook_lexer_token関数はrustc_lexerクレートのトークンをrustc_parserで扱うためのトークンに変換しています。

fn cook_lexer_token(&self, token: rustc_lexer::TokenKind, start: BytePos) -> Option<TokenKind> {
        Some(match token {
            ....
            rustc_lexer::TokenKind::Semi => token::Semi, // ;
            rustc_lexer::TokenKind::Comma => token::Comma, // ,
            rustc_lexer::TokenKind::Dot => token::Dot, // .
            ...
            rustc_lexer::TokenKind::Lifetime { starts_with_number } => {
                let lifetime_name = self.str_from(start);
                if starts_with_number {
                    self.err_span_(start, self.pos, "lifetimes cannot start with a number");
                }
                // String Interningを行う
                let ident = Symbol::intern(lifetime_name);
                token::Lifetime(ident)
            }
            ...
    })
}

また、レクサーは同時にString Interningを行います。これは、コンパイル時のメモリを節約するためのテクニックです。 一つの文字列に対して一つのポインタを対応させます。同じ文字列が同じ場所を指し、異なる文字列が異なる場所を指すようにすることで、文字列の長さの分だけメモリの使用量が削減できます。

先ほどのコードではlet ident = Symbol::intern(lifetime_name);の行でライフタイム名を対象にしたString Interningが行われています。

パースが終了したら、interface::run_compiler関数で新たなクエリが呼び出され、次のステップへと進みます。

おわりに

rustcのソースコードは巨大でざっくり読もうとするだけでも時間がかかりました。僕はまだ読み始めたばかりですが、rustc dev guideなどドキュメントが充実していてとても読みかったです。これからは、ASTや型まわりを中心に読んでいって、時間があれば記事にまとめたいと思います。

明日のカレンダーの記事はそすうぽよさんの「数え上げお姉さんよ永遠なれ」です