2009-08-31

n2930: Range-based for loopについて

n2930: Range-Based For Loop Wording (Without Concepts)

今回、フランクフルト会議でconceptが廃止されたことにより、conceptに依存している機能は、すべてconceptに依存しないように変更しなければならなくなった。Range-based forは、conceptあってこその機能なのだ。concept mapがあるからこそ、既存の型にも、容易にRange-based forを適用できるようになるはずだったのだ。それが、conceptがない今、どうするのか。

答え:ADLを使う。

Range-based forは以下のような構文になっている。

for ( for-range-declaration : expression ) statement

これは、コンパイラによって、以下のように変換される。

{
 auto && __range = ( expression );
 for (auto __begin = begin-expr, __end = end-expr; __begin != __end; ++__begin ) {
  for-range-declaration = *__begin;
  statement
 }
}

このコード上の、begin-exprとend-exprは、渡される型によって、異なる。

まず、配列の場合は、普通に期待されるとおり、すべての配列の要素に対して巡回するようになる。__begin +1, __begin +2といった感じだ。

それ以外の型の場合、begin-exprは、begin(__range)、になり、end-exprは、end(__range)、になる。

説明しよう。これは、begin(), end()という関数を、unqualified-lookupで呼び出しているのだ。しかも、この場合は特別に、通常のlookupではなく、ADLが用いられる。また、associated namespaceには、特別に、std名前空間も追加される。

また、std名前空間には、<iterator>, <array>, <deque>, <forward_list>, <list>, <map>, <regex>, <set>, <string>, <unordered_map>, <unordered_set>, or <vector>をincludeした時に、以下のような関数が導入される。

template<typename C> auto begin(C& c) -> decltype(c.begin());
 template<typename C> auto begin(const C& c) -> decltype(c.begin());
 template<typename C> auto end(C& c) -> decltype(c.end());
 template<typename C> auto end(const C& c) -> decltype(c.end());
 template<typename T, size_t N> T* begin(T (&array)[N]);
 template<typename T, size_t N> T* end(T (&array)[N]);

言葉で説明しても、よく分からないと思う。実際にコードで示すことにする。

#include <iostream>
#include <iterator>
namespace foo
{
    template < typename T >
    class container
    {
    public :
        T * begin() ;// 最初のイテレーターを返す。
        T * end() ;// 最後のイテレーターを返す。
    }
}

int main()
{   
    foo::container< int > c ;
    for (auto value : c )
    {
        std::cout << value << std::endl ;
    }
}

上記のコードが、Range-based for loopの基本的な使い方だ。メンバにイテレーターを返す、begin(), end()という関数を持っていれば、何もしなくても動く。<iterator>をincludeすることによって、std名前空間に、begin()を呼び出して結果を返すだけのbegin()関数が追加されるからだ。end()も同様である。

しかしもし、foo::containerが以下のようになっていたらどうだろうか。

namespace foo
{
    template < typename T >
    class container
    {
    public :
        T * hazimari() ;// 最初のイテレーターを返す。
        T * owari() ;// 最後のイテレーターを返す。
    }
}

この場合は、動かない。なぜならば、コンパイラは、どのようにfoo::containerを巡回すればいいのか、分からないからだ。従って、やり方を定義してやる必要がある。そのためには、begin()とend()を、ADLによって見つかるように定義してやればよい。

namespace foo
{
    template < typename T >
    T * begin( container<T> & c ) { return c.hazimari() ; }
    template < typename T >
    T * end( container<T> & c ) { return c.owari() ; }
}

これによって、Range-based forが動くようになる。ここで注意すべき事がある。このbegin()/end()は、foo名前空間の中に書かなければならない。グローバル名前空間に書いても、Range-based forは動かない。なぜならば、Range-based forでは、通常のunqualified lookupは実行されないからだ。

正しく言うと、必ずしもfoo名前空間の中で定義しなければならないというわけでもない。ただし、それを説明するには、ADLについて詳細に説明しなければならない。それには余白が足りない。

ここで、ふと、「もしcontainerがグローバル名前空間で宣言されていたら、begin()/end()をどこで定義すればいいのか。ADLではグローバル名前空間はlookupされないじゃないか」、と思ったのだが、おそらく、心配はないだろう。というのも、規格を読む限り、associated namespaceは、グローバル名前空間も例外ではないはずだからだ。ADLでは、グローバル名前空間もlookupされる場合がある。現状では、ADLは、unqualified-lookupでは名前が見つからなかった場合のみ実行されるので、そんなことは起こらないだけだ。グローバル名前空間もassociated namespaceたりえるのだが、現行では、ADLが実行されるということは、グローバル名前空間からは見つからなかったということなので、意識しないだけなのだろう。

今さら言うまでもなく、ADLは邪悪である。n2930の提案では、既存のコードが壊れる可能性がある。例えば、

#include <iterator>
#include <utility>

namespace foo
{
    template < typename T >
    class container { public : void begin() {} } ;

    template < typename T >
    void begin(T &) { }
}

int main()
{
    foo::container< std::pair< int, int > > c ;
    begin( c ) ;
}

このコードは、C++03では問題なくコンパイルされるが、C++0xでは、コンパイルエラーになる。なぜなら、<iterator>を導入することによって、std名前空間内に、

template<typename C> auto begin(C& c) -> decltype(c.begin());

といった、汎用的極まりない関数が導入されるからだ。このbegin()関数は、通常のunqualified lookupでは見つからないので、ADLが用いられるのだが、foo::containerのテンプレート引数に、std名前空間内のクラスが用いられていることにより、foo名前空間の他に、std名前空間も、associated namespaceに入ってしまう。その結果、begin()の呼び出しは曖昧になり、コンパイルエラーになる。

問題は、既存のコードだけではない。例えば、以下のコードもコンパイルエラーになる。

namespace foo
{
    template < typename T >
    class container
    {
    public :
        T * hazimari() { return NULL ; }
        T * owari() { return NULL ; }
    } ;

    template < typename T >
    T * begin( container< T > & c) { return c.hazimari() ; }
    template < typename T >
    T * end( container< T > & c) { return c.owari() ; }
}

namespace bar
{
    struct element {} ;

    template < typename T >
    void begin( foo::container<T> & c){} ;
}

int main()
{
    foo::container< bar::element > c ;
    for( auto value : c ) // エラー、begin(c)の呼び出しが曖昧
    {
    // 処理
    }
}

これも、理由は同じだ。テンプレート引数もADLのassociated namespaceになるというのが、問題なのだ。fooとbarは、それぞれ違う人が書いているコードだとする。fooさんはコンテナを実装していて、barさんはそのコンテナに入れる要素の型を実装しているものとする。barさんは、たまたま名前がbeginで、foo::containerを引数にとる関数を書いただけなのだ。それが、極めて不可思議な理由でエラーになってしまう。理由を理解するためには、ADLを理解していなければならない。

それもこれも、conceptが廃止されたからなのだ。嗚呼、concept。何為れぞ廃止せらるるや。

追記:temporaryの寿命の問題については、12.2 p5に、例外事項として付け加えるべきだと思う。begin, endという名前が重複してしまう問題については、std名前空間の中に、さらに別の名前空間を定義して、そこにbegin()/end()を入れるべきだと思う。例えば、

namespace std { namespace range {
template<typename C> auto begin(C& c) -> decltype(c.begin());
 template<typename C> auto begin(const C& c) -> decltype(c.begin());
 template<typename C> auto end(C& c) -> decltype(c.end());
 template<typename C> auto end(const C& c) -> decltype(c.end());
 template<typename T, size_t N> T* begin(T (&array)[N]);
 template<typename T, size_t N> T* end(T (&array)[N]);
}}

1 comment:

Unknown said...

> それには余白が足りない。
フェルマーかっ!!

・・・古い記事にすみません。m(__)m
ちょっと面白かったので、思わず突っ込まずにはいられなくて。