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

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

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

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

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/124813/eb5caa81-b678-6c80-f9b9-c7abc7a1b6b0.png)

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

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

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

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

[The Grand C++ Error Explosion Competition 2014](https://tgceec.tumblr.com/post/74534916370/results-of-the-grand-c-error-explosion)

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

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

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

でした。

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

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

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

…

…

![Dec-15-2020 22-51-31.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/124813/89f02bd9-11b2-7c51-6485-853f4ff658fb.gif)

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

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

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

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

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

と。

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

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

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

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

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

## 関数で再帰ジェネリクス

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

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

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

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

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

```sh
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で教えてくれました。優しい。

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

```rs
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. 以下同様ループ

となるはずです。

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

```sh
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](https://github.com/rust-lang/rust/pull/76843) により導入されており、正しそうです。

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/124813/805dfcec-3f6f-935a-9f58-389fc2155dc2.png)

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

その数、129個。

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

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

```rs
#![recursion_limit = "10"]
```

なるほど。

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

## まだチャンスはある

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

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

## enumで再帰ジェネリクス

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

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

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

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

```rs
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. 以下同様ループ

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

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/124813/b7bc4eea-6bcc-09ae-6da0-a53dbb952e85.png)

！！！

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

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)>`に変えれば良いはず。

コードはこうなります。

```rs
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. 以下同様ループ

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

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

…

…

…

…

…

…

…

…

…
　
![Dec-15-2020 22-36-20.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/124813/390aea5f-9a0d-f510-02ec-6ea00986993b.gif)


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


出来ました！！！

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

```sh
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エラーの型名の出力が見事に爆発しています。

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

```sh
, ((((((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`を変更すれば爆発することは無くなりました。

```rs
#![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`がある限り、ここらが限界のようです。

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

```rs
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](https://en.wikipedia.org/wiki/Polymorphic_recursion)と言います。型注釈なしのpolymorphic recursionの型推論は不可能らしいです。

## おわりに

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

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

おしまい。


## 付録
Rustのバージョン

```sh
$ 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
```