Boost Advent Calendar 2011 4日目 - Boost.Foreachの裏側
Boost Advent Calndar 2011 の4日目です。
ネタがないので既知のことかもしれないですが、いろいろテクニックが使われてるBoost.Foreachの実装について紐解いてみたいと思います。
Boost.Foreachとは
C++11でrange-based forという構文が追加されたのはみなさんご存知かもしれないですが、これと同じような構文でrangeを舐めるということをC++03の範囲で行なおうというのがBoost.Foreachです。
rangeがどうとかrange-based forがどうとかってのは多分C++11 Advent Calendar 2011で紹介されると期待しているので省きます。
boost/foreach.hpp をインクルードするとBOOST_FOREACHマクロが使えるようになります。
このgrammarは
BOOST_FOREACH( for-range-declaration, for-range-initializer ) statement
になるはずです。多分。
簡単な例を挙げると
vector< int > v; BOOST_FOREACH( int e, v ) { cout << e << endl; }
とかです。これでvの中身を先頭から舐められます。
std::for_eachとかboost::for_eachとか使えばいいじゃんと思われるかもしれないですが、これらは関数であり、break文で処理を抜けるということができません。
breakで抜ける処理が必要になるがために従来のfor文を用いるのはバグを生むきっかけになります。そのiteratorほんとに終端しますか？
安全にrangeを舐めるためにもやはりiteratorを使うのはナンセンスです。
それでは外側から順に見ていきます。いくつか重要でない部分は省略しています。
BOOST_FOREACHマクロ
#define BOOST_FOREACH(VAR, COL) \ if (boost::foreach_detail_::auto_any_t _foreach_col = BOOST_FOREACH_CONTAIN(COL)) {} else \ if (boost::foreach_detail_::auto_any_t _foreach_cur = BOOST_FOREACH_BEGIN(COL)) {} else \ if (boost::foreach_detail_::auto_any_t _foreach_end = BOOST_FOREACH_END(COL)) {} else \ for (bool _foreach_continue = true; \ _foreach_continue && !BOOST_FOREACH_DONE(COL); \ _foreach_continue ? BOOST_FOREACH_NEXT(COL) : (void)0) \ if (boost::foreach_detail_::set_false(_foreach_continue)) {} else \ for (VAR = BOOST_FOREACH_DEREF(COL); !_foreach_continue; _foreach_continue = true)
まず知らない人は驚くかもしれないですが、C(90,99,1X共に)ではn1578 6.8.4/1によるとifやswitchは
selection-statement: if ( expression ) statement switch ( expression ) statement
となっており、expression -> ... と辿っていくとその中にはdeclaratorが存在しません。
一方C++(03,11)のn3290 6.4/1では
selection-statement: if ( condition ) statement switch ( condition ) statement
となっており、conditionがn3290 6.4/1で
condition: expression attribute-specifier-seqopt decl-specifier-seq declarator = initializer-clause attribute-specifier-seqopt decl-specifier-seq declarator braced-init-list
です!!!!!!なんとdeclaratorがif文中で使える!!!!
あ、declaratorというのは有り体に言えば変数宣言です。
また、declraratorを使用した場合、
if ( T v ) { ... } else { ... }
というコードは
{
T v;
if ( static_cast< bool >( v ) ) { ... }
else { ... }
}
と等価に置き換えられます。よって _foreach_col / _foreach_cur / _foreach_endはこのマクロの最後まで存在することができます。
boost::foreach_detail_::auto_any_t はBoost.Anyと同じようにType Erasureを用いて型情報を隠蔽する型です。なぜこんな事をするのかというと、rangeがprvalueなのかlvalueなのかconst性がどうなのかという部分があり、単一のdeclaratorではこれを実現できないからです。
C++11で導入されたautoを使うとここは
if (auto && _foreach_col = COL) {} else
と書けるわけですが、C++03の範疇で対応したいのでType Erasureを用いています。
また、boost::foreach_detail_::auto_any_t はconversion-operatorを持っており、これは常にfalseを返します。
これにより、前述のif文中ではconditionは常に不成立になり、else中が評価されますが、次のifが待ち受けているので{}で囲わずともローカル変数を安全に定義することができます。
次は外側のfor文、実際にループを行う部分です。
for (bool _foreach_continue = true; \ _foreach_continue && !BOOST_FOREACH_DONE(COL); \ _foreach_continue ? BOOST_FOREACH_NEXT(COL) : (void)0) \ if (boost::foreach_detail_::set_false(_foreach_continue)) {} else \
_foreach_continueがtrueかつrangeが終端に達していない限り繰り返されます。
最後に_foreach_continueをfalseにしていますが、これがbreakするためのﾐｿなのです。
そして最後のfor文がユーザーが書いたstatementを食います。
これはfor文ですが式を見ればわかるとおり1回しか通りません。ユーザーが渡したstatementがbreakした場合、このforから抜けることになりますが、これにより_foreach_continueがfalseのまま外側のfor文に戻ります。そうすると外側のfor文でもconditionがfalseになるため、全体としてもbreakしBOOST_FOREACHが終了するというトリックになっています。
for (VAR = BOOST_FOREACH_DEREF(COL); !_foreach_continue; _foreach_continue = true)
BOOT_FOREACH_(CONTAIN | BEGIN | END | DONE | NEXT | DEREF)
#define BOOST_FOREACH_CONTAIN(COL) \ boost::foreach_detail_::contain( COL, BOOST_FOREACH_SHOULD_COPY(COL) ) #define BOOST_FOREACH_BEGIN(COL) \ boost::foreach_detail_::begin( _foreach_col, BOOST_FOREACH_TYPEOF(COL), BOOST_FOREACH_SHOULD_COPY(COL) ) #define BOOST_FOREACH_END(COL) \ boost::foreach_detail_::end( _foreach_col, BOOST_FOREACH_TYPEOF(COL), BOOST_FOREACH_SHOULD_COPY(COL) ) #define BOOST_FOREACH_DONE(COL) \ boost::foreach_detail_::done( _foreach_cur, _foreach_end, BOOST_FOREACH_TYPEOF(COL) ) #define BOOST_FOREACH_NEXT(COL) \ boost::foreach_detail_::next( _foreach_cur, BOOST_FOREACH_TYPEOF(COL) ) #define BOOST_FOREACH_DEREF(COL) \ boost::foreach_detail_::deref( _foreach_cur, BOOST_FOREACH_TYPEOF(COL) )
_foreach_なんたらはBOOST_FOREACHの中で定義されている変数そのものです。
これらはboost::foreach_detail_::auto_any_tに格納されている変数に対して侵入的に操作します。詳細はType Erasureの説明をしている人とかに投げます。
containはrangeをコピーすべきか参照でいいのかを判定してauto_any_tの型の向こう側に格納します。
begin / end はrangeのbeginとendのiteratorを引っ張ってきます。
doneは現在の要素を指すiteratorがendと等しかったらtrueを、そうでなければfalseを返すだけです。ループの終了判定に使います。
nextは現在のイテレータを進めるだけです。
derefはイテレータをderefします。
これらは実際に演算する型がType Erasureの向こう側に隠れているので、iteratorの型などをrangeから得る必要があります。そのためにBOOST_FOREACH_TYPEOFを使って式の型を取得しています。
BOOST_FOREACH_SHOULD_COPYはrangeがlvalueなのかrvalueなのかを判定して、コピーする必要があるのかどうかを判定するために使用されます。
これらヘルパ関数を使用するためにrangeの式を渡していますが、ヘルパ関数を呼ぶたびに評価されてしまっては困ります。例えば破壊的操作を行うアダプタを通されたりした場合、評価毎にrangeの中身が変更されてしまいます。
また、標準入力をrangeとする場合、20文字入力して欲しいのに、何回もrangeが評価されるので何100文字も要求されたりしてしまって困ります。
そのため、BOOST_FOREACH_TYPEOFやBOOST_FOREACH_SHOULD_COPYは式を評価しないで型を得られるようにラップされています。
BOOST_FOREACH_TYPEOF
rangeの型を得るマクロです。
#define BOOST_FOREACH_TYPEOF(COL) \ (true ? 0 : boost::foreach_detail_::encode_type(COL, boost::foreach_detail_::is_const_(COL)))
ここで先程言った式を評価しないで型を得るテクニックが使われています。三項条件演算子*1にはCとC++共に面白い性質があります。
n3290 5.16/1に
Only one of the second and third expressions is evaluated.
つまり第二項または第三項しか評価しないと書いてあります。評価です。評価。はい。
true ? expression : assignment-expression
と書くと第三項は絶対に評価されないわけです。
しかし、この三項条件演算子全体の型は第二項と第三項で同一である必要があります。同一でない場合、暗黙の型変換を0回以上くりかえし、共通の型になるように変換します。
つまりBOOST_FOREACH_TYPEOFの書き方だと、第二項の 0 は暗黙の型変換で第三項の型に変換されます。
これによりrangeを評価しないでrangeの型を得ることができます。C++11だと
decltype( range )
です。ヌルゲーですね。
ところでここまでの説明だと必ず疑問が出てくるはずです。
0 をrangeの型に型変換できるはずないと。
その通りです。0が暗黙の型変換できる型はn3290 4.7/1によると
A prvalue of an integer type can be converted to a prvalue of another integer type.
と規定されています。
つまり他のinteger typeになら変換可能ということです。おお？これは？？？と思うのは早急です。n3290 4.10/1には
A null pointer constant is an integral constant expression (5.19) prvalue of integer type that evaluates to zero or a prvalue of type std::nullptr_t. A null pointer constant can be converted to a pointer type; ...
とあります。これはn3290の文ですが03でも0はnull pointer constantです。かつ、null pointer constantは任意の型へのポインタ型となることができます。
つまりこれを使うと先程のBOOST_FOREACH_TYPEOFは任意の型へのポインタに、つまりrangeの型へのポインタにすることで型を得ることができます。
これを実現するのが
boost::foreach_detail_::encode_type(COL, boost::foreach_detail_::is_const_(COL))
の部分です。次はこれを見ます。
型の判定
boost::foreach_detail_::encode_typeの前にboost::foreach_detail_::is_const_を見たいと思います。
template<typename T> inline boost::is_const<T> *is_const_(T &) { return 0; } template<typename T> inline boost::mpl::true_ *is_const_(T const &) { return 0; }
non-const lvalueがis_const_に渡されるとこれはboost::is_const
一方const lvalueもしくはrvalueが渡されるとboost::mpl::true_ *を返します。
これにより渡された式のconst性を検証します。
このポインタ型を元に今度はencode_typeへと移ります。
template<typename T, typename C = boost::mpl::false_> struct type2type : boost::mpl::if_<C, T const, T> { }; template<typename T> inline type2type<T> *encode_type(T &, boost::mpl::false_ *) { return 0; } template<typename T> inline type2type<T, const_> *encode_type(T const &, boost::mpl::true_ *) { return 0; }
大体察してください。戻ったポインタ型について::typeを取るとconstが付いてたり付いてなかったりする型を得られます。
こうすることでrangeの(non-)const non-reference typeを得られます。
BOOST_FOREACH_SHOULD_COPY
BOOST_FOREACH_SHOULD_COPYはBoost.ConfigのフラグやWAによって1.48.0の時点で4バリエーション存在しますが、今回はそのうちのジェネリックなバリエーションのみ紹介します。それ以外はrvalueのサポートの有無などの違いがあります。
template<typename T> inline boost::mpl::false_ *is_rvalue_(T &, int) { return 0; } template<typename T> inline boost::mpl::true_ *is_rvalue_(T const &, ...) { return 0; } # define BOOST_FOREACH_IS_RVALUE(COL) \ boost::foreach_detail_::is_rvalue_((COL), 0) # define BOOST_FOREACH_SHOULD_COPY(COL) \ (true ? 0 : boost::foreach_detail_::or_( \ BOOST_FOREACH_IS_RVALUE(COL) \ , BOOST_FOREACH_IS_LIGHTWEIGHT_PROXY(COL)))
BOOST_FOREACH_IS_LIGHTWEIGHT_PROXYは与えられたrangeがどのような種類なのかを検査するマクロです。
具体的にはiteratorのpairでrangeを表現しているのかなどを確かめています。特に重要なものではないので説明は省略します。
このマクロの肝はis_rvalue_です。これはSFINAEのお供であるvariadic argumentsを用いることで明示的にoverload resolutionの順位を変更しています。
このため、rangeがconstであろうとnon-constであろうとlvalueであれば上のオーバーロードがマッチすることになります。しかしrvalueはnon-const lvalue referenceに束縛することができないので上のoverloadはinstantiationに失敗し下のoverloadにマッチします。rvalueはconst lvalue referenceであれば束縛することができるので、下のoverloadは失敗しないのです。
上にマッチするとboost::mpl::false_ *が、下にマッチするとboost:mpl::true_ *が戻り値の型になります。
もちろん三項条件演算子の仕様により第3引数であるこの式は評価されずに、BOOST_FOREACH_SHOULD_COPYの型のみがうまくrvalueなのかlvalueなのかを判定する材料になるのです。
containにBOOST_FOREACH_SHOULD_COPYの型が渡るとコピーすべき(rvalue)のときはコピーした値をType Erasureでauto_any_tの向こう側に、lvalueの時は参照をauto_any_tの向こう側に置くことができます。
これでdangling pointerの心配がなくなりました。
ということで
とりあえず重要なところは一通りめぐったと思います。それほど変なことはしてないですね。でもifを使ったローカル変数の定義は初めて見たとき感動しました。
マクロでどうしても必要になった場合とかは使ってみるといいと思います。
あ、auto_any_tがtrueを返すようにしないでなんでわざわざ {} else を後ろに付けるんだと思ってる人がいるかもしれないですが、auto_any_tがtrueを返すようにしてしまうと
BOOST_FOREACH( v, r )
{
...
}
else ...
else ...
else ...
みたいな文が書けてしまい、range-based forのような構文を正確に得ることができません。elseの本体は評価されないですが、バグの温床になりかねません。また、elseの代わりに ; を置くことも出来てしまいます。こういった変なパターンを許さないようにするマクロの設計は重要です。
少し話がそれましたが、Boost.Foreachはしっかりと読取いてみると非常に勉強になることが多いです。
Boost.Foreachに限らずBoostのライブラリは設計が非常に美しいものが多いので、今までただ使ってたという人は少し時間をとって中身を探ってみるといいと思います。
わからないことがあったら @kikairoya とか id:kikairoya をつついてみると教えてくれると思います。あと @Cryolite とか id:Cryolite とか。C(ryはそのまえにbjam Advent Calendar書いてください。
明日はでちまるさんのお兄さんこと id:DigitalGhost さんです。お兄さんは魔界の人らしいですがでちまるさんは人界の方なのでしょうか。気になります。
