BOOST_PP_REPEATの仕組み

これは 高知工科大 Advent Calendar 2017 の13日目の記事です。

OBなのに書かされるマンです。
なぜだか知りませんが私はマイコンの処女を奪う仕事をしていることになっているようです。まぁこういう仕事をしているとC++が使えないのは当たり前としてC99ですら使えないだとか、なぜこの時代にXPのCygwinなんだとか、VB6って何者なん?とか、このコード俺と同い年やんとかのありとあらゆる拷問を受けることがあります。:innocent:

なので今回はCコンパイラが:poop:という拷問を受けた時にも味方してくれる心強いライブラリ Boost Preprocessor について書くことにします。

---

環境

• Boost Preprocessor 1.65.1
• gcc version 7.2.0 (x86_64-win32-seh-rev1, Built by MinGW-W64 project)

Boost PP とは

みんな大好きC++の標準ライブラリboostの中のプリプロセッサ用ライブラリです。プリプロセッサなので当然Cからも使えますし、最悪の場合、現代のコンパイラ付属のプリプロセッサで処理した後:poop:コンパイラに通すなんてこともできちゃいます。
http://www.boost.org/doc/libs/1_65_1/libs/preprocessor/doc/index.html

今回はBoost PPのなかでもよくお世話になるものをいくつか紹介します。

※ boost 1.60.0 からはVariadic Macro Data Library(VMD)なるものもあるようです。

BOOST_PP_IF(cond, t, f)

まずはウォーミングアップ。BOOST_PP_IF です。
これはマクロの展開を制御するものですがとりあえず以下のように使えます。

/* 展開前 */
printf(BOOST_PP_IF(10, "TRUE", "FALSE"));
printf(BOOST_PP_IF(0, "TRUE", "FALSE"));

/* 展開後 */
printf("TRUE");
printf("FALSE");

ちょっとよくわかりませんね。手動で順番に展開してみます。
BOOST_PP_IFはcontrol/if.hppで以下のように定義されてます。

#define BOOST_PP_IF(cond, t, f) BOOST_PP_IIF(BOOST_PP_BOOL(cond), t, f)

ここで BOOST_PP_IIF と BOOST_PP_BOOL がでてきました。

BOOST_PP_BOOL(x)

これは引数を判定して 1又は0に展開されるマクロで、logical/bool.hppで以下のように定義されてます。

#define BOOST_PP_BOOL(x)    BOOST_PP_BOOL_I(x)
#define BOOST_PP_BOOL_I(x)  BOOST_PP_BOOL_ ## x
#define BOOST_PP_BOOL_0     0
#define BOOST_PP_BOOL_1     1
#define BOOST_PP_BOOL_2     1
...
#define BOOST_PP_BOOL_256 1

恐ろしい定義ですね。しかしこれで0から256までの数字を以下のように0/1に展開できるようになります。

BOOST_PP_BOOL(10)
-> BOOST_PP_BOOL_I(10)
-> BOOST_PP_BOOL_ ## 10
-> BOOST_PP_BOOL_10
-> 1

BOOST_PP_IIF(bit, t, f)

これはbitが0ならfに、1ならtに展開されるマクロでBOOST_PP_IFの本体です。

control/iif.hppで定義されてます。

#define BOOST_PP_IIF(bit, t, f)    BOOST_PP_IIF_I(bit, t, f)
#define BOOST_PP_IIF_I(bit, t, f)  BOOST_PP_IIF_ ## bit(t, f)
#define BOOST_PP_IIF_0(t, f)       f
#define BOOST_PP_IIF_1(t, f)       t

展開は以下のようになります。

BOOST_PP_IIF(1, "TRUE", "FALSE")
-> BOOST_PP_IIF_I(1, "TRUE", "FALSE")
-> BOOST_PP_IIF_ ## 1("TRUE", "FALSE")
-> BOOST_PP_IIF_1("TRUE", "FALSE")
-> "TRUE"

---

これで BOOST_PP_IF が以下のように展開されることがわかりましたね。

BOOST_PP_IF(10, "TRUE", "FALSE")
-> BOOST_PP_IIF(BOOST_PP_BOOL(10), "TRUE", "FALSE")
-> BOOST_PP_IIF(1, "TRUE", "FALSE")
-> "TRUE"

BOOST_PPではこのようにトークンの結合##で展開の制御をしたり、大量の単調なdefineがあったりするのはごく当たり前のことになっていますのでこの機会にぜひ慣れてください。
あとトークンの結合にはBOOST_PP_CATを使ったりもします。

cat.hpp

#define BOOST_PP_CAT(a, b)    BOOST_PP_CAT_I(a, b)
#define BOOST_PP_CAT_I(a, b)  a ## b

なぜ BOOST_PP_CAT が必要なのかは以下の記事を参考にしてください。
字句の結合や文字列化を行う際のマクロ置換動作をよく理解する

BOOST_PP_REPEAT(count, macro, data)

さて本題 BOOST_PP_REPEAT です。
これはプリプロセッサで繰り返し処理をするためのマクロで以下のように展開されます。

/* 展開前 */
BOOST_PP_REPEAT(count, macro, data)

/* 展開後 */
macro(z, 0, data) macro(z, 1, data) ... macro(z, count - 1, data) 

なのでこれを使うと以下のようなことができます。(zは内部(ループの最適化)で使う値なので今は気にしなくで大丈夫です)

#define SUM(z, n, data)  BOOST_PP_EXPR_IF(n, +) BOOST_PP_INC(n)
// BOOST_PP_EXPR_IF(n, +)はn != 0 なら + に展開される
// BOOST_PP_INC(n)は n + 1 に展開される

BOOST_PP_REPEAT(10, SUM, _);
-> SUM(z, 0, _) SUM(z, 1, _) ... SUM(z, 9, _);
-> 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10;

これほんとにマクロなのか?
しかしBOOST_PP_REPEATの恐ろしさはこんなものではありません。なんと2重ループができるのです。

#define MUL(z, n, _)  BOOST_PP_EXPR_IF(n, *) (BOOST_PP_REPEAT(BOOST_PP_INC(n), SUM, _))
#define SUM(z, n, _)  BOOST_PP_EXPR_IF(n, +) BOOST_PP_INC(n)

BOOST_PP_REPEAT(10, MUL, _);
-> MUL(z, 0, _) MUL(z, 1, _) ... MUL(z, 9, _);
-> (BOOST_PP_REPEAT(1, SUM, _)) * (BOOST_PP_REPEAT(2, SUM, _)) * ... * (BOOST_PP_REPEAT(10, SUM, _));
-> (1) * (1 + 2) * (1 + 2 + 3) * ... * (1 + 2 + ... + 10);

あれ？おかしいですね。BOOST_PP_REPEATの展開中にまたBOOST_PP_REPEATが出てきています。プリプロセッサでは再帰できないはずなのに。

実際以下のようなマクロは正しく展開されません。

#define X(seq)            X_I seq
#define X_I(elem, isEnd)  X_ ## isEnd(elem)
#define X_0(elem)         elem + X_I
#define X_1(elem)         elem

X((a, 0)(b, 0)(c, 1))
-> a + X_I(b, 0)(c, 1)

これは

X((a, 0)(b, 0)(c, 1))
-> X_I(a, 0)(b, 0)(c, 1)
-> X_##0(a)(b, 0)(c, 1)
-> X_0(a)(b, 0)(c, 1)
-> a + X_I(b, 0)(c, 1)
-> a + b + X_I(c, 1)
-> a + b + c

と展開してほしいところですがX_Iの展開中にX_Iが再度出てきているため
a + X_I(b, 0)(c, 1)
までしか展開されません。※展開できるVerを記事の最後に書きました。

gccのドキュメントにもちゃんと書いてます。3.10.5 Self-Referential Macros

なぜBOOST_PP_REPEATは再帰できているのか。

repetition/repeat.hpp

#define BOOST_PP_REPEAT  BOOST_PP_CAT(BOOST_PP_REPEAT_, BOOST_PP_AUTO_REC(BOOST_PP_REPEAT_P, 4))

なるほど。関数マクロではないようです。
BOOST_PP_CATはトークンを結合するものなので BOOST_PP_REPEAT_ と BOOST_PP_AUTO_REC(BOOST_PP_REPEAT_P, 4) を結合しているのは分かりました。
でも BOOST_PP_AUTO_REC(BOOST_PP_REPEAT_P, 4) っていったい何者なんだ

BOOST_PP_AUTO_REC(pred, n)

これはあるマクロが展開済みかどうかを2分探索で判別し、その展開回数を返すマクロです。
ほんと何言ってるか訳が分からないと思いますが順番に見ていきましょう。
※ BOOST_PP_REPEATでは n == 4 なので4のやつだけ抜粋

detail/auto_rec.hpp

#define BOOST_PP_AUTO_REC(pred, n)  BOOST_PP_NODE_ENTRY_ ## n(pred)

#define BOOST_PP_NODE_ENTRY_4(p)    BOOST_PP_NODE_2(p)(p)

#define BOOST_PP_NODE_2(p)          BOOST_PP_IIF(p(2), BOOST_PP_NODE_1, BOOST_PP_NODE_3)
#define BOOST_PP_NODE_1(p)          BOOST_PP_IIF(p(1), 1, 2)
#define BOOST_PP_NODE_3(p)          BOOST_PP_IIF(p(3), 3, 4)

これは以下のように展開されます

BOOST_PP_AUTO_REC(BOOST_PP_REPEAT_P, 4)
-> BOOST_PP_NODE_ENTRY_4(BOOST_PP_REPEAT_P)
-> BOOST_PP_NODE_2(BOOST_PP_REPEAT_P)(BOOST_PP_REPEAT_P)
-> BOOST_PP_IIF(BOOST_PP_REPEAT_P(2), BOOST_PP_NODE_1, BOOST_PP_NODE_3)(BOOST_PP_REPEAT_P)

ここで BOOST_PP_IIF が出てきたので、これは BOOST_PP_NODE_1 又は BOOST_PP_NODE_3 に展開されます。

• BOOST_PP_NODE_1 のとき (BOOST_PP_REPEAT_P(2) == 1)

-> BOOST_PP_IIF(BOOST_PP_REPEAT_P(2), BOOST_PP_NODE_1, BOOST_PP_NODE_3)(BOOST_PP_REPEAT_P)
-> BOOST_PP_NODE_1(BOOST_PP_REPEAT_P)
-> BOOST_PP_IIF(BOOST_PP_REPEAT_P(1), 1, 2)

また BOOST_PP_IIF が出てきたので 1 又は 2 に展開されます。

• BOOST_PP_NODE_3 のとき (BOOST_PP_REPEAT_P(2) == 0)

これも同様に展開すると最終的に 3 又は 4 に展開されます。

表にすると以下のようになります。

		展開後
BOOST_PP_REPEAT_P(2) == 1	BOOST_PP_REPEAT_P(1) == 1	1
BOOST_PP_REPEAT_P(2) == 1	BOOST_PP_REPEAT_P(1) == 0	2
BOOST_PP_REPEAT_P(2) == 0	BOOST_PP_REPEAT_P(3) == 1	3
BOOST_PP_REPEAT_P(2) == 0	BOOST_PP_REPEAT_P(3) == 0	4

こういうやつどっかで見たことありませんか?
そう、これは BOOST_PP_REPEAT_P(n) が1を返す最小のnを2分探索で求めていたやつなんですね。
※ BOOST_PP_REPEAT_P(n) == 1 なら BOOST_PP_REPEAT_P(n + 1) == 1 も成り立つ

これで BOOST_PP_AUTO_REC(BOOST_PP_REPEAT_P, 4) が 1 ～ 4 のどれかに展開されることが判明したので、BOOST_PP_REPEAT は以下のように展開されます。

BOOST_PP_REPEAT
-> BOOST_PP_CAT(BOOST_PP_REPEAT_, BOOST_PP_AUTO_REC(BOOST_PP_REPEAT_P, 4))
-> BOOST_PP_REPEAT_ ## 1 // n == 1
-> BOOST_PP_REPEAT_1

なので先ほどの2重ループの例は次のようになります。

#define MUL(z, n, _)  BOOST_PP_EXPR_IF(n, *) (BOOST_PP_REPEAT(BOOST_PP_INC(n), SUM, _))
#define SUM(z, n, _)  BOOST_PP_EXPR_IF(n, +) BOOST_PP_INC(n)

BOOST_PP_REPEAT(10, MUL, _);
-> BOOST_PP_REPEAT_1(10, MUL, _);
-> MUL(z, 0, _) MUL(z, 1, _) ... MUL(z, 9, _);
-> (BOOST_PP_REPEAT(1, SUM, _)) * (BOOST_PP_REPEAT(2, SUM, _)) * ... * (BOOST_PP_REPEAT(10, SUM, _));

なるほど。ここで2回目に出てきたBOOST_PP_REPEATがBOOST_PP_REPEAT_2になってくれればBOOST_PP_REPEAT_1の再帰にならずに済みそうです。
※ BOOST_PP_REPEATの展開はBOOST_PP_REPEAT_1に展開された時点でいったん終わっているので再帰にはなっていません。

やっとここまで来ましたがまだ BOOST_PP_REPEAT_P(n) が残っています。もうしんどい :innocent:

BOOST_PP_REPEAT_P(n)

repetition/repeat.hpp

#define BOOST_PP_REPEAT_P(n)  BOOST_PP_CAT(BOOST_PP_REPEAT_CHECK_, BOOST_PP_REPEAT_ ## n(1, BOOST_PP_NIL BOOST_PP_TUPLE_EAT_3, BOOST_PP_NIL))

#define BOOST_PP_REPEAT_CHECK_BOOST_PP_NIL                1
#define BOOST_PP_REPEAT_CHECK_BOOST_PP_REPEAT_1(c, m, d)  0
#define BOOST_PP_REPEAT_CHECK_BOOST_PP_REPEAT_2(c, m, d)  0
#define BOOST_PP_REPEAT_CHECK_BOOST_PP_REPEAT_3(c, m, d)  0

/* tuple/eat.hpp */
#define BOOST_PP_TUPLE_EAT_3(e0, e1, e2)

とりあえず n == 2 を展開してみましょう。

BOOST_PP_REPEAT_P(2)
-> BOOST_PP_CAT(BOOST_PP_REPEAT_CHECK_, BOOST_PP_REPEAT_ ## 2(1, BOOST_PP_NIL BOOST_PP_TUPLE_EAT_3, BOOST_PP_NIL))
-> BOOST_PP_CAT(BOOST_PP_REPEAT_CHECK_, BOOST_PP_REPEAT_2(1, BOOST_PP_NIL BOOST_PP_TUPLE_EAT_3, BOOST_PP_NIL))
-> BOOST_PP_CAT(BOOST_PP_REPEAT_CHECK_, BOOST_PP_NIL BOOST_PP_TUPLE_EAT_3(z, 0, BOOST_PP_NIL))
-> BOOST_PP_CAT(BOOST_PP_REPEAT_CHECK_, BOOST_PP_NIL)
-> BOOST_PP_REPEAT_CHECK_ ## BOOST_PP_NIL
-> BOOST_PP_REPEAT_CHECK_BOOST_PP_NIL
-> 1

1に展開されました。次 n == 1 のとき。
これも同様に展開すると 1になります。
なるほど。BOOST_PP_REPEAT_P(2) == 1 && BOOST_PP_REPEAT_P(1) == 1 だから BOOST_PP_REPEAT_1 になるのか。

しかしちょっと待ってください。
BOOST_PP_REPEAT_P(1)の展開中にはBOOST_PP_REPEAT_1が出てきますよね。
これ2回目のループ(BOOST_PP_REPEAT_1の展開中)の場合展開できないはずです。
では展開できない場合をやってみましょう。

BOOST_PP_REPEAT_P(1)
-> BOOST_PP_CAT(BOOST_PP_REPEAT_CHECK_, BOOST_PP_REPEAT_ ## 1(1, BOOST_PP_NIL BOOST_PP_TUPLE_EAT_3, BOOST_PP_NIL))
-> BOOST_PP_CAT(BOOST_PP_REPEAT_CHECK_, BOOST_PP_REPEAT_1(1, BOOST_PP_NIL BOOST_PP_TUPLE_EAT_3, BOOST_PP_NIL))
-> BOOST_PP_REPEAT_CHECK_ ## BOOST_PP_REPEAT_1(1, BOOST_PP_NIL BOOST_PP_TUPLE_EAT_3, BOOST_PP_NIL)
-> BOOST_PP_REPEAT_CHECK_BOOST_PP_REPEAT_1(1, BOOST_PP_NIL BOOST_PP_TUPLE_EAT_3, BOOST_PP_NIL)
-> 0

なんとぉ!
0に展開されました。
n == 2, 3 の時も同様に BOOST_PP_REPEAT_n が展開できないとき BOOST_PP_REPEAT_P(n) は 0に展開されます。
なんて恐ろしいマクロなんだ。

でもまぁこれで2回目のループの時はBOOST_PP_REPEAT_P(2) == 1 && BOOST_PP_REPEAT_P(1) == 0 だから BOOST_PP_REPEAT_2 になりました。

2重ループの例は次のようになります。

#define MUL(z, n, _)    BOOST_PP_EXPR_IF(n, *) (BOOST_PP_REPEAT(BOOST_PP_INC(n), SUM, _))
#define SUM(z, n, _)    BOOST_PP_EXPR_IF(n, +) BOOST_PP_INC(n)

BOOST_PP_REPEAT(10, MUL, _);
-> BOOST_PP_REPEAT_1(10, MUL, _);
-> MUL(z, 0, _) MUL(z, 1, _) ... MUL(z, 9, _);
-> (BOOST_PP_REPEAT(1, SUM, _)) * (BOOST_PP_REPEAT(2, SUM, _)) * ... * (BOOST_PP_REPEAT(10, SUM, _));
-> (BOOST_PP_REPEAT_2(1, SUM, _)) * (BOOST_PP_REPEAT_2(2, SUM, _)) * ... * (BOOST_PP_REPEAT_2(10, SUM, _));
-> (1) * (1 + 2) * (1 + 2 + 3) * ... * (1 + 2 + ... + 10);

たしかに、これだと再帰してませんね。
※ ちなみに BOOST_PP_REPEAT は3重ループまで出来ます。がここまで読んだあなたなら4重目以降も実装できますよね :innocent:

BOOST_PP_REPEAT_n(count, macro, data)

最後の敵はこいつ BOOST_PP_REPEAT_n 。BOOST_PP_REPEAT の本体ですがこいつはそんなに強くないので大丈夫です。

repetition/repeat.hpp

#define BOOST_PP_REPEAT_1(c, m, d)    BOOST_PP_REPEAT_1_I(c, m, d)
#define BOOST_PP_REPEAT_1_I(c, m, d)  BOOST_PP_REPEAT_1_ ## c(m, d)

#define BOOST_PP_REPEAT_1_0(m, d)
#define BOOST_PP_REPEAT_1_1(m, d)     m(2, 0, d)
#define BOOST_PP_REPEAT_1_2(m, d)     BOOST_PP_REPEAT_1_1(m, d) m(2, 1, d)
#define BOOST_PP_REPEAT_1_3(m, d)     BOOST_PP_REPEAT_1_2(m, d) m(2, 2, d)
...
#define BOOST_PP_REPEAT_1_255(m, d)   BOOST_PP_REPEAT_1_254(m, d) m(2, 254, d)
#define BOOST_PP_REPEAT_1_256(m, d)   BOOST_PP_REPEAT_1_255(m, d) m(2, 255, d)

BOOST_PP_REPEAT_1は上記のようになってるので展開すると以下のようになります。

BOOST_PP_REPEAT_1(10, macro, data)
-> BOOST_PP_REPEAT_1_I(10, macro, data)
-> BOOST_PP_REPEAT_1_ ## 10(macro, data)
-> BOOST_PP_REPEAT_1_10(macro, data)
-> BOOST_PP_REPEAT_1_9(macro, data) macro(2, 9, data)
-> BOOST_PP_REPEAT_1_8(macro, data) macro(2, 8, data) macro(2, 9, data)
...
-> macro(2, 0, data) macro(2, 1, data) ... macro(2, 9, data) 

これまた圧倒的に単調な定義ですが、これで256まではループっぽいことが出来ました。

あと最初にzはループ最適化用だとか言ってましたがこれは次のループのnのことでした。
2重ループの例の MUL を

#define MUL(z, n, _)  BOOST_PP_EXPR_IF(n, *) (BOOST_PP_REPEAT_ ## z(BOOST_PP_INC(n), SUM, _))

のように定義すると BOOST_PP_AUTO_REC を使わずに BOOST_PP_REPEAT_2 を生成できるようになるのでプリプロセス時間が少し短縮されるようになります。

おわりに

どうでしたか?
これであなたもBOOST_PP大好き人間になりましたか?
BOOST_PP_FORとかのループ系のやつはほぼ同じような感じになっているのでもう読めるようになってると思います。:innocent:
あと特殊なのは BOOST_PP_ITERATE とか BOOST_PP_SLOT とかが残ってますがもうしんどいので勘弁してください。
この記事が読めたあなたならきっと自力で解読できるはずです。

あとBOOST_PPはPSoCととても相性がいいです。PSoCを使っている方は今すぐBOOST_PPを使うように。

---

展開できない例を展開できるようにしてみた

#define X(seq)             X_I0 seq
#define X_I0(elem, isEnd)  X_ ## isEnd(elem, 1)
#define X_I1(elem, isEnd)  X_ ## isEnd(elem, 0)
#define X_0(elem, next)    elem + X_I ## next
#define X_1(elem, next)    elem

X((a, 0)(b, 0)(c, 1))      // X開始
-> X_I0(a, 0)(b, 0)(c, 1)  // X_I0開始
-> X_0(a, 1)(b, 0)(c, 1)
-> a + X_I1(b, 0)(c, 1)    // X_I0終了, X_I1開始
-> a + X_0(b, 0)(c, 1)
-> a + b + X_I0(c, 1)      // X_I1終了, X_I0開始
-> a + b + X_1(c, 1)
-> a + b + c               // X_I0終了, X終了

X_I0, X_0は2回出てきてるけどX_I0の展開中にX_I0は出てきていない(途中で切れ目がある)のでOK