C++初心者会で話題になったClangの相互再帰バグについて

中３女子です。

歌舞伎座.tech#8「C++初心者会」という勉強会が先日あり、自称初心者やクソザコによるさまざまな発表がおこなわれた。自分は参加できなかったので、いくつかの発表をニコ生で視聴した。

その中に、@wx257osn2 氏による constexpr ラムダライブラリを実装したという発表があった。実装にあたっては Clang のバグに対処するワークアラウンドを書くのに苦労したという。さもありなん。Clang は全体的な規格準拠度ではおおむね GCC 以上といってよいが、constexpr 関係ではいまだに致命的なバグを残している。それがどのようなバグなのか応答で齟齬があったようなので、脇からの補足をここに記しておく。

Clang の constexpr 関係の致命的なバグとは、相互再帰におけるバグである。相互再帰する constexpr 関数テンプレートを実体化すると、テンプレートインスタンス化が無限再帰してコンパイルエラーになる。具体的には以下のようなコードがエラーとなる。

template<typename T>
constexpr T f(T const&);
template<typename T>
constexpr T g(T const&);
 
template<typename T>
constexpr T f(T const& val) { return g(val); }
template<typename T>
constexpr T g(T const& val) { return val >= 10 ? val : f(val + 1); }
 
int main() {
  constexpr auto x = f(0);
  // [clang version 3.2]
  // fatal error: recursive template instantiation exceeded maximum depth of 512
}

犬小屋でのコンパイル結果→ [Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ http://melpon.org/wandbox/permlink/KabKOkFRecUo1eD1

f() は g() を呼び出し、g() は f() を呼び出すため相互再帰となる。しかしインスタンス化されるシグネチャはそれぞれ f(int const&) と g(int const&) であり、再帰によって変化しない。そのためこのコードは規格的にもインスタンス化において問題はない。GCC でも問題なくコンパイルが通る。にもかかわらず Clang ではテンプレートインスタンス化の処理が無限に再帰して停止していないためエラーになっている。これは明確に処理系のバグであり、Clang 3.2 から 3.7(trunk) 現在にいたるまで修正されていない。

この相互再帰バグに対してどのようなワークアラウンドを書くか。もっとも単純な手は、テンプレートインスタンス化の深さをカウントして、あらかじめ決めた回数に達したら SFINAE でインスタンス化を打ち切ることだ。例えば上記コードは以下のようにワークアラウンドを書くことができる。

#include <type_traits>
#include <stdexcept>

#define LIMIT 256
extern void* enabler;

template<int D = 16, typename T, typename std::enable_if<(D < LIMIT - 1)>::type*& = enabler>
constexpr T f(T const&);
template<int D = 16, typename T, typename std::enable_if<!(D < LIMIT - 1)>::type*& = enabler>
constexpr T f(T const&) {
  return std::runtime_error("recursive template instantiation exceeded maximum depth"), T();
}
template<int D = 16, typename T, typename std::enable_if<(D < LIMIT - 1)>::type*& = enabler>
constexpr T g(T const&);
template<int D = 16, typename T, typename std::enable_if<!(D < LIMIT - 1)>::type*& = enabler>
constexpr T g(T const&) {
  return std::runtime_error("recursive template instantiation exceeded maximum depth"), T();
}

template<int D, typename T, typename std::enable_if<(D < LIMIT - 1)>::type*&>
constexpr T f(T const& val) { return g<D + 1>(val); }
template<int D, typename T, typename std::enable_if<(D < LIMIT - 1)>::type*&>
constexpr T g(T const& val) { return val >= 10 ? val : f<D + 1>(val + 1); }

int main() {
  constexpr auto x = f(0);
}

犬小屋でのコンパイル結果→ [Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ http://melpon.org/wandbox/permlink/kePnBBddZLlZQcxo

テンプレート引数 D は深さのカウンタである。インスタンス化の深さがリミットに達すると、SFINAE によってランタイムエラー例外を投げる版が選択される。この版は f() または g() をそれ以上呼び出さないため、インスタンス化はここで停止する。「実際の」呼び出しが深さ制限を越えないかぎりはコンパイルエラーにならない。このようにして Clang の相互再帰バグを回避できる。

（なお、もし深さ制限を超えて「実際の」呼び出しがおこなわれた場合、それがコンパイル時であれば throw 式（定数式でない）が評価されコンパイルエラーになり、実行時であれば例外が投げられる）

このワークアラウンドの問題点は見てのとおりコードが非常に長く醜くなることだ。関数を分けるだけでなく、それぞれにカウンタと enable_if を埋め込まなければならない。相互再帰が f() → g() → f() のふたつの間だけでなく f() → g() → h() → i() → f() のように多くの中間関数を介するならば、そのすべてに同様のワークアラウンドを仕込む必要がある。例えば次のように。
Github: → https://github.com/bolero-MURAKAMI/Sprout/blob/master/sprout/random/uniform_int_distribution.hpp#L134
これは悪夢でしかない。

醜いワークアラウンドを書かない方法

もし可能であれば、相互再帰を避けるような実装がもっとも望ましい。設計上回避できない場合もあるがそうでない場合もある。constexpr 関数の実装で相互再帰が出現するのは、C++11 constexpr の制限下で複雑なループを記述するときに多い。そのようなケースで相互再帰そのものを回避できる実装のアイディアを最近思いついた。

sprout::while_loop がそれだ。
Github: → https://github.com/bolero-MURAKAMI/Sprout/blob/master/sprout/utility/while_loop.hpp

while_loop() は引数として（状態の初期値、ループ終了を判定する叙述関数、次の状態を返す単項オペレータ）をとる。名前は while_loop だが挙動においては for 文に近い。処理の内部ではループが二分探索的な分割統治として行われ（このイディオムを倍分再帰と呼ぶ）、相互再帰は現れない。多重ループもオペレータ内からの更なる while_loop 呼び出しとして記述され、これも相互再帰を必要としない。最近実装したものなので使用例は少ないが、以下のように使う。
Github: → https://github.com/bolero-MURAKAMI/Sprout/blob/master/sprout/random/linear_congruential.hpp#L148

また、相互再帰を避けるためだけでなく、constexpr でのループの実装のために fun_impl_1(), fun_impl_2(), ... といった実装用関数が乱立するのを防ぐ意味でも効果があると思われる。

コンパイラ毎の constexpr 関係のバグとワークアラウンドについて

以下に書き留めておくことにしている。
Sprout C++ Library Wiki: コンパイラ性能比較 http://www.boleros.x0.com/doc/sproutwiki/index.php?%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%A9%E6%80%A7%E8%83%BD%E6%AF%94%E8%BC%83

が、筆無精なので主要ないくつかしか記していないし最新の VC++ 等の検証は進んでいない。そのうち充実したいがいつになるかわからない。constexpr に明るい有志には加筆を願いたい。