Rustプログラム解析入門

この記事は、KMCアドベントカレンダー2022の3日目(12/3)の記事です。(執筆時点で10日の大遅刻。ごめんなさい！)

2日目の記事はkypさんの「2022年のNuitaにやったこと」です。 4日目の記事はwassさんの「ショートカットでコマンドを入力すると、どんな環境でもそこそこ便利になる」です。

この記事の対象読者

• Rustやrustcに興味がある方
• 言語処理系, プログラム解析に興味がある方

はじめに

昨年夏にRustプログラムの解析方法について、KMC内でハンズオンを行いました。そこでRustプログラムの解析ツール minippy (GitHub) を自作し、参加者の方々にソースコードを改造して遊んでもらいました。この記事は、前半ではRustプログラムの解析方法について説明し、後半では解析ツール minippy のソースコードを解説します。

プログラムの解析とは？

まず、プログラムの解析とはどのようなことをするのでしょうか？

解析には、いろんな種類がありますが、すぐに思いつく応用例として以下のものが挙げられると思います。

• フォーマッティング
• Lint
• 型検査
• Rustコンパイラの借用検査 (borrow check)
• 逆コンパイル (decompile)
• 最適化のための解析 (DCE, peephole)

これらの例は、ソースコードをある形式へ変換し、それを用いて解析が行われます。

より具体的には、以下のような解析に対応しています。

• フォーマッティング、Lint、型検査 → AST上の解析を利用
• Rustコンパイラの借用検査 (borrow check) → 制御フローグラフ上の解析を利用
• 逆コンパイル、最適化のための解析 → 機械語(または低レベルな中間表現)上の解析を利用

これらの形式(AST、制御フローグラフ、機械語など)は、解析の行いやすさによって選択されます。

ソースコードからASTへ

この記事では、主にAST上の解析を扱います。 ASTとはAbstract Syntax Treeの略で、日本語では抽象構文木と呼ばれています。

簡単な例として、整数リテラル 1 と変数 foo の加算からなる式 1 + foo を考えてみます。 このソースコード 1 + foo のASTはRustでは以下のようになります。

ここでは、foo は変数名として適切でないので、この変数名を見つけて警告を行う処理を考えてみましょう。 ASTは木構造なので、根から深さ優先探索を行い、各ノードに対してパターンマッチを行うことで、簡単に foo を発見することができます。

こういったASTの各ノードに対する処理の実装には、visitorパターンがよく用いられます。 後から紹介するminippyでもvisitorパターンを利用しています。

今は簡単な足し算のASTを考えましたが、関数や文からなる一般のプログラミング言語でもASTを構築することができます。

minippy

minippyはRustのASTを解析するプログラムで、GitHub上で公開されています。 以下のコマンドですぐに利用することができます。

$ git clone https://github.com/tamaroning/minippy.git
$ cd minippy
$ cargo run tests/add_zero.rs

もともと、tests/add_zero.rs には簡単な足し算を計算するRustプログラムがあります。 $ cargo run ./tests/add_zero.rs を実行すると、 このソースコードに含まれるゼロ加算を警告してくれます。

ソースコード解説

つづいて、minippyのソースコードを見ていきます。

まず、minippyでは、unstableなRustコンパイラ (rustc) のAPIを利用しています。 そのため、rust-toolchain.tomlでは、以下のように利用するrustcのバージョンを指定しています。

rust-toolchain.toml:

[toolchain]
channel = "nightly-2022-07-02"
components = ["rustfmt", "rustc-dev", "rust-src", "llvm-tools-preview"]

次に、main関数です。

src/main.rs

fn main() {
    println!("{USAGE}");

    rustc_driver::init_rustc_env_logger();
    std::process::exit(rustc_driver::catch_with_exit_code(move || {
        let out = process::Command::new("rustc")
            .arg("--print=sysroot")
            .current_dir(".")
            .output()
            .unwrap();
        let sys_root = str::from_utf8(&out.stdout).unwrap().trim().to_string();

        let orig_args: Vec<String> = std::env::args().collect();
        let filepath = orig_args.last().unwrap().to_string();

        let args: Vec<String> = vec![
            "rustc".to_string(),
            filepath,
            "--sysroot".to_string(),
            sys_root,
        ];

        rustc_driver::RunCompiler::new(&args, &mut MinippyCallBacks).run()
    }));
}

まず、$ rustc --print=sysroot というコマンドを実行し、出力結果を変数 sys_root に格納します。

sysroot はrustcのバイナリや標準ライブラリが置かれているディレクトリへのパスを表しています。私の環境では、sysroot は C:\Users\tamaron\.rustup\toolchains\nightly-2022-07-02-x86_64-pc-windows-msvc でした。

次に、これとコマンドライン引数をファイルパスと見なして、$ rustc <ファイルパス> --sysroot <sys_root> を実行します。

ここではさらに、rustc API の機能を利用して MinippyCallBacks をrustcのコールバックとして指定しています。

MinippyCallBacks は rustc_driver::Callbacks トレイトを実装していて、ASTを解析するための Pass を登録しています。 今、ゼロ加算を検出する機能を実装したいので、ここで登録しているのはAddZeroという Pass です。

struct MinippyCallBacks;

impl rustc_driver::Callbacks for MinippyCallBacks {
    fn config(&mut self, config: &mut rustc_interface::Config) {
        config.register_lints = Some(Box::new(move |_sess, lint_store| {
            lint_store.register_late_pass(|| Box::new(AddZero));
        }));
    }
    // ... 
}

つづいて、コールバックによって登録された AddZero 構造体を見ていきます。

src/main.rs

struct AddZero;
// ...

fn is_lit_zero(expr: &Expr) -> bool {
    if let ExprKind::Lit(lit) = &expr.kind
        && let LitKind::Int(0, ..) = lit.node
    { true }
    else { false }
}

impl<'tcx> rustc_lint::LateLintPass<'tcx> for AddZero {
    fn check_expr(&mut self, cx: &LateContext<'tcx>, expr: &'tcx Expr<'tcx>) {
        if expr.span.from_expansion() {
            return;
        }
        if let ExprKind::Binary(binop, lhs, rhs) = expr.kind
            && BinOpKind::Add == binop.node
            && (is_lit_zero(lhs) || is_lit_zero(rhs))
        {
            cx.struct_span_lint(ADD_ZERO, expr.span, |diag| {
                let mut diag = diag.build("Ineffective operation");
                diag.emit();
            });
        }
    }
}

この構造体は、rustc_lint::LateLintPass トレイトを実装していて、 このトレイトはASTのノードに対して特定の処理を行うためのvisitorパターンが実装されています。

"0 + 1", "1 + 0 + a" といったコードはRustでは式として扱われるので、check_expr という関数にゼロ加算を検出するロジックを書きます。

式がゼロ加算となる条件は、「式が二項演算の足し算(BinOpKind::Add)である」かつ「 「左辺(lhs)または右辺(rhs)がリテラルの0である」となるため、if 文でこれを実装しています。 ここでは、さらにヘルパー関数として、整数リテラルかどうかを返す is_let_zero 関数を用意して使っています。

余力がある人向け

これまでの解説が簡単に感じた人は演習として、課題を用意しておきました。正解は無いですが、ぜひ取り組んでみてください。 以下の機能をminippyに実装してください。

• 課題1: 特定の変数名が宣言された場合に警告を行う (例えば foo, bar)
• 課題2: 特定のメソッドチェーンの並びが検出された場合に警告を行う (例えば .map(_).map(_))

おわりに

minippyはRust公式LinterであるClippyを参考にして作りました。 ClippyはASTだけでなく制御フローグラフベースの解析 (MIR lint) も実装されていて、とても面白いです。 興味があれば、ソースコードを読んで見ることをおすすめします。

• Rust
• Compiler