読者です 読者をやめる 読者になる 読者になる

ボレロ村上 - ENiyGmaA Code

中3女子です。

関数パラメータパックと無限再帰の問題

Variadic Templates は強力なC++11 の新機能である。
これを関数の可変長引数に適用したものを関数パラメータパック(function parameter pack)と呼ぶ。


もちろん constexpr でも関数パラメータパックは重宝する。


ところで、これを再帰と組み合わせた場合、予期せず無限再帰を引き起こすケースがある。
下がそのサンプルコードである。
なお、検証は gcc-4.7-20110903 上で行っている。

    • サンプル
#include <vector>
#include <type_traits>

typedef std::vector<unsigned> vec_t;

//
// [初期値 .. 10) の連続した数値の vector を返す関数
//
template<typename... Args>
vec_t make_vec(unsigned v, Args... args) {
    // 10 回の再帰で終わるはずだが、評価されない場合でも make_vec が無限にインスタンス化されてエラー
    // template instantiation depth exceeds maximum
    return v >= 10 ? vec_t{args...} : make_vec(v + 1, args..., v);
}

//
// 番兵あり版
//
template<typename... Args>
typename std::enable_if<(sizeof...(Args) >= 10), vec_t>::type
make_vec2(unsigned v, Args... args) {
    // 番兵的な SFINAE
    // インスタンス化はここで止まる
    return vec_t{args...};
}
template<typename... Args>
typename std::enable_if<(sizeof...(Args) < 10), vec_t>::type
make_vec2(unsigned v, Args... args) {
    // 番兵がいるのでおk
    return v >= 10 ? vec_t{args...} : make_vec2(v + 1, args..., v);
}

int main() {
    //vec_t v = make_vec(0);    // !!!コンパイルエラー!!!
    vec_t v2 = make_vec2(0);    // おk
}
エラー: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) substituting ‘template<class ... Args> vec_t make_vec(unsigned int, Args ...) [with Args = {unsigned int, unsigned int, ..(中略/unsigned intが900個).., unsigned int}]’
recursively required from ‘vec_t make_vec(unsigned int, Args ...) [with Args = {unsigned int}, vec_t = std::vector<unsigned int>]’
required from ‘vec_t make_vec(unsigned int, Args ...) [with Args = {}, vec_t = std::vector<unsigned int>]’


make_vec は、[初期値 .. 10) の連続した数値の vector を返す関数である。
make_vec は再帰で実装されている。


普通こうした場合にはループを使うだろうが、例えば constexpr 関数ではループは再帰で置き換えるため、
こうしたコードは constexpr 関数を書くときなどに頻出する。

    return v >= 10 ? vec_t{args...} : make_vec(v + 1, args..., v);

この行では v が 10 以上ならば vector を生成して返し、そうでなければ値をパラメータ列の末尾に追加して再帰する。
すなわち、再帰のたびにパラメータパックも 1 個増加する。


もちろん make_vec は、多くとも 10 回の再帰で終わる。
ということは、パラメータパックも同様に多くとも 10 個になるはずである。


ところがエラーメッセージを見ると、パラメータパックが何と 900 個、制限の限界まで行ってエラーで停止している。
つまり無限再帰になっているらしい。
どうしてだろうか?


v == 10 の場合、つまり再帰が終了すべき時点を考えてみる。
条件式 v >= 10 は真になるから、vec_t{args...} が評価される。
つまり make_vec(v + 1, args..., v) は評価されない。
評価されないから、再帰もここで終わるように思われる。


ところが、評価はされなくとも、テンプレートのインスタンス化は行われるのである。
こうして、「実行パス上では評価されない」 make_vec がインスタンス化される。


更には、インスタンス化された先でも(実際には評価されないにもかかわらず)再帰的にインスタンス化が続けられるようだ。
再帰が終了すべき条件で停止せず、結果的に「コンパイル時の無限再帰インスタンス化」が行われているらしい。


これは困ったことである。
こうして考えてみると妥当な仕様のようにも思えるが、直感に反するし、何よりこれでは可変長引数による再帰を書けない。


さて、ではどうやって解決するか。
それもサンプルコード中に書いてある。
make_vec2 の実装がそれである。


パラメータパックを使った SFINAE で、特定の条件で再帰インスタンス化が終了するようにしている。
ここでは仮にこれを「番兵的な SFINAE」と呼ぶことにする。


なお、この「番兵」は実際に評価される必要はない。
ようは実行時の再帰でなくコンパイル時のインスタンス化を抑制すればそれでよいからだ。
評価されない場合は、番兵の本体は well-formed でありさえすればよい。


しかしながら、番兵で解決しきれないケースもある。
make_vec の例では最大値が 10 の決め打ちだったので SFINAE に出来たが、
例えば最大値を実行時引数として渡す仕様の場合、「必ず再帰を抜ける」条件がコンパイル時には決定できないからだ。


ところで、このような無限再帰インスタンス化が行われうるような仕様は、果たして C++11 の規格に沿ったものなのだろうか。
実際のところよく分からない。
何か情報があれば教えていただきたいです。