Rustのコンパイルエラーを爆発させる技術

こんにちは。コンパイルが一発で成功しないminaminaoです。

突然ですが、皆さんはコンパイルエラー爆発をご存知でしょうか？

コンパイラは、私達プログラマーにコードの間違いを指摘し修正を促してくれる良き相棒です。

しかし、特定の条件下でとんでもなく大量のエラーメッセージを出力することがあります。

そのような、コードをコンパイルしたらエラーがべらぼうに出力されてしまう現象のことを、コンパイルエラー爆発と呼ぶことがあります。

コンパイルエラー爆発の遊び

昔から一部プログラマーの間で、コンパイルエラー爆発を使った遊びが行われてきました。

2014年には、C++のコンパイルエラー爆発コンテスト、なんてのも開かれています。

The Grand C++ Error Explosion Competition 2014

このコンテストは、短いサイズで大量のエラーメッセージを出すソースコードを作ることを競います。スコアは出力されたエラーの文字数をソースコードの文字数で割った値です。

いくつか部門がありますが、なんでもあり部門の優勝コードは、

jeh.cpp

#include ".//.//.//.//jeh.cpp"
#include "jeh.cpp"

でした。

そのスコアは約59億らしいです。コード文字数が約50なので、単純計算すると300GBほどのエラーが出力されることになります。

仕組みを簡単に解説すると、includeは、指定したファイルの内容をその場所に展開する機能です。コンパイラは、このコードをコンパイルしようとするとjeh.cppを再帰的に展開してしまうので、コンパイルエラー爆発が起きてしまうようです。

ちなみに、gcc version 9.3.0で動かしてみると、

…

…

今でも動きました。酔いそうです。

Rustでもコンパイルエラー爆発してみたい

さて、そこで疑問が浮かびます。

「RustもC++みたくコンパイルエラーを爆発できるのか？」

「もし爆発するなら、どれくらい小さなコードでどれくらい爆発するのだろうか？」

と。

Rustコンパイラは賢いことで有名です。何かしらの対策は打ってあり、C++のように一筋縄ではいかないでしょう。しかし、Rustコンパイラの賢さと仕組みを知る良い機会なので、試してみることにします。

とりあえずベーシックな手法を試してみる

コンパイルエラー爆発が起こる原因のほとんどは、コンパイル時の再帰的処理だと考えています。

C++であれば、上述したインクルードの再帰やテンプレートの再帰があります。テンプレートはRustのジェネリクスと似た機能です。

私の知る限りRustにC++のインクルードと同等の機能はないので、まずはジェネリクス系のテクニックで攻めてみます。

関数で再帰ジェネリクス

ジェネリクスの中でも真っ先に浮かんだ再帰関数でやってみます。

まずはベースとなる無限再帰関数を作ります。

fn f<T>(x:T){f(x);}fn main(){f(0);}

コードのサイズを小さくしたいので一行にしています。

この関数は明らかに無限ループを起こすのですが、コンパイルは通ります。コンパイラのバージョンは、最新のstableで1.48です。

warning: function cannot return without recursing
 --> a.rs:1:1
  |
1 | fn f<T>(x:T){f(x);}fn main(){f(0);}
  | ^^^^^^^^^^^^ ---- recursive call site
  | |
  | cannot return without recursing
  |
  = note: `#[warn(unconditional_recursion)]` on by default
  = help: a `loop` may express intention better if this is on purpose

warning: 1 warning emitted

「無限ループしてるよ」とwarningで教えてくれました。優しい。

それでは、コンパイルエラー爆発を起こすように、コードを次のように変えてみます。

fn f<T>(x:T){f(Some(x));}fn main(){f(0);}

先程と違うのは、関数f内で呼び出している関数fです。その引数xをSomeで囲っています。

これで、

1. main関数内のf(0)のためにf::<i32>を生成しようとする。
2. f::<i32>の生成のために、f::<i32>内にあるf::<Option<i32>>を生成しようとする。
3. f::<Option<i32>>の生成のために、f::<Option<i32>>内にあるf::<Option<Option<i32>>>を生成しようとする。
4. 以下同様ループ

となるはずです。

では、コンパイルしてどうなるか見てみましょう。

error: reached the recursion limit while instantiating `f::<Option<Option<Option<Option<...>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
 --> a.rs:1:14
  |
1 | fn f<T>(x:T){f(Some(x));}fn main(){f(0);}
  |              ^^^^^^^^^^
  |
note: `f` defined here
 --> a.rs:1:1
  |
1 | fn f<T>(x:T){f(Some(x));}fn main(){f(0);}
  | ^^^^^^^^^^^^
  = note: the full type name has been written to 'a.long-type.txt'

error: aborting due to previous error

？！

賢い！！！

「型生成は打ち切るだろうな」「エラー時点での型は表示しないかな」などとは予想していました。

まさか打ち切った時点の型を省略して表示し、さらに、エラー時点での型を全文で見たい人のためにテキストファイルを作成してくれるとは思いませんでした。

なんて親切なんだ…。

一方で、一抹の不安がよぎります。

「もしや、どうやっても全部こんな風に型名省略されちゃうのでは…？」

…

なんにせよ、結果です。

• コード: fn f<T>(x:T){f(Some(x));}fn main(){f(0);}
• コード文字数: 41
• エラー文字数: 401
• スコア: 9.78 (=401/41)

このスコアを基準に考えていきましょう。

そもそも、いつから型名が省略されているのか？

この省略機能が導入されたバージョンがあるはずです。何かしらコンパイルエラー爆発の糸口を見つけられるかもしれないので探ってみましょう。

とりあえず適当に選んだ昔のバージョンでは型名が省略せずに表示されました。バージョンは沢山あるので、バージョンの二分探索をしてコンパイルしていきます。

結果、バージョン1.46では型名が省略されませんでした。

つまり、このerror: reached the recursion limit while instantiatingエラーに対する型名の省略機能は、バージョン1.47で導入されたことになります。めちゃくちゃ最近です。

さらに、省略された型名がテキストファイルに保存されるようになったのはバージョン1.48でした。Rustリポジトリを調査してみたら Let user see the full type of type-length limit error by kornelski · Pull Request #76843 · rust-lang/rust により導入されており、正しそうです。

ちなみに先程のコードを古いバージョン1.46でコンパイルしてみると、

Optionが沢山表示された！！！！！

その数、129個。

これから推測できる事は、どうやらRustには再帰の制限がある、ということ。

調べてみると、Rustでは再帰の深さはrecursion_limitというアトリビュートで定めらていてデフォルトでは128だとわかりました。recursion_limitは、次のように変更できます。

#![recursion_limit = "10"]

なるほど。

ただ、recursion_limitを変えたら何でもありになってしまうので、今回は変えない縛りでいきます。

まだチャンスはある

型名の省略機能はまだ最近導入されたばかり。長い型名になると必ずこのエラーが発生してしまう可能性もありますが、まだ抜け穴があるかもしれません。

というわけで、他の手法を探ってみます。再帰関数のジェネリクスはコンパイルエラー爆発できませんでした。では、他のジェネリクスはどうでしょうか？

enumで再帰ジェネリクス

enumで再帰ジェネリクスをしてみます。

まず、enumと再帰で思い浮かべるのはリストです。

enum List {
    Nil,
    Cons(i32, Box<List>),
}

このコードを再帰ジェネリクスに書き換えてみます。

enum A<T>{B,C(T,Box<A<A<T>>>)}fn main(){A::<i32>::B;}

これをコンパイルするとどうなるでしょうか。

1. main関数内のA::<i32>::B;により、A<i32>を生成しようとする。
2. A<i32>の生成のために、A<A<i32>>を生成しようとする。
3. A<A<i32>>の生成のために、A<A<A<i32>>>を生成しようとする。
4. 以下同様ループ

となり、再帰関数のときと同様に爆発するはずです。

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

！！！

再帰関数のときと異なり型が省略されていません！

E0320エラーは、先程のerror: reached the recursion limit while instantiatingのエラーとは違うものです。これは使えそうです。

というわけで、一旦結果です。

• コード: enum A<T>{B,C(T,Box<A<A<T>>>)}fn main(){A::<i32>::B;}
• コード文字数: 53
• エラー文字数: 659
• スコア: 12.4 (=659/53)

無事、やりたいことを一つ成し遂げることができました。

しかし、これではちょっと長いエラー程度でしょう。爆発と呼ぶにはおこがましいレベルです。

なにか爆発させるためのもうひと工夫が必要です。

「指数コンパイルエラー爆発」

さて、視点を変えてコンパイルエラー爆発を計算量的に考えてみましょう。

recursion_limitは再帰できる最大回数です。この回数を$n$とします。すると、先程のエラーメッセージは$O(n)$サイズと言えます。いわば、線形コンパイルエラー爆発なわけです。

であれば自然な発想が浮かびます。

「$O(k^n)$サイズの指数コンパイルエラー爆発に発展できないだろうか？」

と。$k$は適当な定数です。つまり、

「再帰の深さごとに型の長さを指数関数的に増やすことはできないだろうか？」

と。

…

そう、ジェネリクスを$k$分木的に再帰させれば良いのです。

例えば二分木的に再帰させれば、$n=128$なので$2^{128}$個の型が表示されたコンパイルエラーが見れるはずです。$2^{128}$は天文学的数値です。ゴールが見えてきました。

二分木的に再帰するには、先程A<A<T>>と書いていたところをA<(T,T)>に変えれば良いはず。

コードはこうなります。

enum A<T>{B,C(T,Box<A<(T,T)>>)}fn main(){A::<i32>::B;}

コンパイルすれば次のようになるはずです。

1. main関数内のA::<i32>::B;により、A<i32>を生成しようとする。
2. A<i32>の生成のために、A<(i32,i32)>を生成しようとする。
3. A<(i32,i32)>の生成のために、A<((i32,i32),(i32,i32))>を生成しようとする。
4. 以下同様ループ

指数関数的に型名が大きくなりそうです。

それでは、コンパイルしてみましょう…

…

…

…

…

…

…

…

…

…
　

うおおおおおお！！！？！！！？！！！！！！！！！！！！！！

出来ました！！！

エラーの先頭は次のようになっていました。

error[E0320]: overflow while adding drop-check rules for A<i32>
 --> a.rs:1:42
  |
1 | enum A<T>{B,C(T,Box<A<(T,T)>>)}fn main(){A::<i32>::B;}
  |                                          ^^^^^^^^^^^
  |
  = note: overflowed on A<((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((

E0320エラーの型名の出力が見事に爆発しています。

しかし、わりとすぐにコンパイルが終わってしまいました。末尾は次のようになっています。

, ((((((i32, i32), (i32, i32)), ((i32, i32), (i32, i32))), ...), ...), ...)))))))))))))), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...), ...)>

error: aborting due to previous error

どうやら何かしらの制限が働いているようです。あと、微妙に型が省略されています。

エラーをファイルに書き出すと、エラーサイズは約3.7MBでした。

調べてみるとrecursion_limitと同じように、型の名前の長さはtype_length_limitアトリビュートによって制限されていました。デフォルトの値は、1048576です。

type_length_limitは次のように変更できます。type_length_limitを変更すれば爆発することは無くなりました。

#![type_length_limit = "100"]

ともあれ、無限に爆発とまではなりませんでしたが高いスコアを叩き出しました。

普通にプログラミングしていて突如3.7MBのエラーメッセージがターミナルに出力されたらトラウマになること間違いなしでしょう。

結果

• コード: enum A<T>{B,C(T,Box<A<(T,T)>>)}fn main(){A::<i32>::B;}
• コード文字数: 54
• エラー文字数: 3,670,682
• スコア: 67,975 (=3,670,682/54)

念の為、他のバージョンで実行してみる

上記コードを一応他のバージョンで実行してみました。

すると1.46では、エラー出力が表示されずにビジー状態になりました。どうやら無限ループを打ち切ってエラー出力できるようになったこと自体が最近なのかもしれません。

図らずも、コンパイルエラー爆発の表面化もコンパイルエラー爆発の対策が活発なのも最近のようです。

最終形

ジェネリクスを用いたコンパイルエラー爆発はtype_length_limitによって制限されてしまうことがわかりました。type_length_limitがある限り、ここらが限界のようです。

最後に、少し調整してスコアを伸ばします。

enum A<T>{B,C(T,Box<A<(T,T)>>)}fn main(){let a=A::<i32>::B;}

let a=を付けてエラーを倍増できました。

結果

• コード: enum A<T>{B,C(T,Box<A<(T,T)>>)}fn main(){let a=A::<i32>::B;}
• コード文字数: 60
• エラー文字数: 7,341,340
• スコア: 122,355 (=7,341,340/60)

というわけで、最終的に7.3MBのコンパイルエラー爆発を起こせました。コードサイズの12万倍です。

まだ細かな向上余地は沢山あります。ですが、これ以上は虚無になりそうなので止めておきます。

余談: Polymorphic Recursion

ちなみに、再帰的に型を構成することをpolymorphic recursionと言います。型注釈なしのpolymorphic recursionの型推論は不可能らしいです。

おわりに

今回はジェネリクスしか調べませんでしたが、他にもコンパイルエラー爆発が起こりそう機能（マクロなど）があるので、機会があれば遊んでみようと思います。super-exponentialなコンパイルエラー爆発を考えるのも面白いかもしれません。なにか見つかれば、minaminao/rust-error-explosion に追加します。もし私が紹介した以外にも面白いコンパイルエラー爆発をご存知の方は、ぜひ教えてください。

また、今回の発見はせっかくなので、イシューで報告してE0320エラーにも再帰関数と同じ型名省略機能があったほうが良いのではないかと提案して、修正プルリクを書いているところです。何かアドバイスやコメントあればイシューに頂けると嬉しいです。

おしまい。

付録

Rustのバージョン

$ rustc --version --verbose
rustc 1.48.0 (7eac88abb 2020-11-16)
binary: rustc
commit-hash: 7eac88abb2e57e752f3302f02be5f3ce3d7adfb4
commit-date: 2020-11-16
host: x86_64-apple-darwin
release: 1.48.0
LLVM version: 11.0