conceptで爆発するC++20

はじめに

　ちょっとしたネタです。C++20でconceptという機能が追加されましたが、これを悪用するとコンパイルに指数オーダの時間計算量・空間計算量がかかるコードを書けるという話です。

concept

　conceptはC++20で追加された機能です。ここでは簡単にしか説明しないので、詳しい話はこちらの記事を参照していただければと思います。
　conceptでは論理式の包含関係に基づいてオーバーロードの優先順位を決定します。どういうことかは以下の例を用いて説明しましょう。

#include <type_traits>
#include <concepts>
#include <iostream>

template<typename T> concept A1 = std::is_convertible_v<T, int>;
template<typename T> concept A2 = std::is_convertible_v<T, int>;
template<typename T> concept A3 = std::is_convertible_v<T, int>;

template<typename T> concept B1 = A1<T> && (A2<T> || A3<T>);
template<typename T> concept B2 = A1<T> && A2<T> && A3<T>; 

void func(B1 auto) {
  std::cout << "func(B1 auto)\n"; 
}

void func(B2 auto) {
  std::cout << "func(B2 auto)\n";
}

int main() {
  func(42);   // func(B2 auto) が選ばれる
  return 0;
}

　上のコード例において、
　$ B_1 = A_1 \wedge (A_2 \vee A_3) $
　$ B_2 = A_1 \wedge A_2 \wedge A_3 $
となっているわけですが、$B_1$と$B_2$の間には$B_1 \subset B_2$（すなわち$B_2$ならば$B_1$）という関係が成り立っていることは簡単にわかると思います（真理値表を書くと簡単に確認できます）。つまり$B_2$の方が厳しい条件式であるということです。
　ここで、Tにintを入れてあげると、B1<T>もB2<T>も共にtrueになるので、オーバーロードされた関数func(B1 auto)とfunc(B2 auto)の両方の制約を満たすことになりますが、ここではより条件の厳しいfunc(B2 auto)が優先されます。

本題

　さて、もう薄々感づいている方もいるかもしれませんが、論理和と論理積で構成された、2つの論理関数の論理包含関係を調べるのはNP-completeです。多分。間違っていたら教えてください。これはどういうことかというと、（P != NPならば）指数時間の計算量がかかるという意味になります。
　というわけでコンパイルに指数時間かかるコードの例を挙げてみましょう。

#include <type_traits>
#include <concepts>
#include <iostream>

template<typename T> concept A01 = std::is_convertible_v<T, int>;
template<typename T> concept A02 = std::is_convertible_v<T, int>;
template<typename T> concept A03 = std::is_convertible_v<T, int>;
// ... 省略
template<typename T> concept A60 = std::is_convertible_v<T, int>;

template<typename T> concept B1 = (A01<T> || A02<T>) && (A03<T> || A04<T>) && /* ... 省略 */ && (A59<T> || A60<T>);
template<typename T> concept B2 = A01<T> && A02<T> && A03<T> && A04<T> && /* ... 省略 */ && A59<T> && A60<T>; 

void func(B1 auto) {
    std::cout << "func(B1 auto)\n";
}

void func(B2 auto) {
    std::cout << "func(B2 auto)\n";
}

int main() {
    func(42);   // func(B2 auto) が選ばれるはずだが...
    return 0;
}

　何か所か省略しているのでコード全文を見たい方はこちらからどうぞ。
　さて、この例においても$B_1 \subset B_2$なのでfunc(B2 auto)が優先されるはずで、またコード自体も完全に合法ですが、コンパイルには失敗します。MSVCはヒープ領域を使い果たしてエラーになります。Clangは何も出力せずに異常終了しますが、おそらく同じ理由でヒープ領域を使い果たしてエラーになります。GCCは少し頭がよくて、conceptの複雑度が既定値を超えたという旨のエラーを吐いて即座に終了します。
　正直コンパイラ内部でどのような計算を行っているかは知らないのですが、おそらく真理値表を書くか何かしているのだと思います。そしてその真理値表に指数オーダの空間計算量がかかるのでMSVC/Clangはメモリ不足になるのでしょう。

終わりに

　今後より複雑なconceptが標準ライブラリに組み込まれていくと思われますが、いつかこの壁にぶつかりそうですね。C++標準化委員会がこの問題をどう解決していくのか楽しみです。

おしまい。