2010-03-05

Candidate functions [temp.dep.candidate]の異常な制限

以下のコードは、規格では、undefined behaviorである。ill-formedかもしれない。

template < typename T>
void f(T x) { g(x) ; }

void g(int) { }

int main()
{// undefined behavior
// g(int)は見つからないかもしれない。
    f(0) ;
}

なぜ、undefined behaviorであり、ill-formedかもしれないのか。undefined behaviorなら、ill-formedになっても問題はない。しかし、あえてill-formedかもしれないというのは、このundefined behaviorの定義によるものだ。曰く、「ill-formedの場合、undefined behaviorである」と。つまり、本来ならill-formedであるプログラムが、undefined behaviorに変わってしまうのだ。

該当部分の規格は、簡単な文面であるが、これを説明するのは難しい。これには、テンプレートとオーバーロード解決とADLが絡んでいるからだ。これを正しく実装しているコンパイラを、私は知らない。

なぜg(int)が見つからないのか。まず、関数テンプレートf()の中の、g(x)という式は、type dependent expressionである。ならば、gはpoint of instantiationに解決されるはずではないのか。確かにその通りだ。しかし、point of instantiationに解決されるとはいえ、point of instantiationのコンテキストから見える名前が使われるとは、限らない。

14.7.4.2 Candidate functions [temp.dep.candidate]によれば、

For a function call that depends on a template parameter, if the function name is an unqualified-id but not a template-id, or if the function is called using operator notation, the candidate functions are found using the usual lookup rules (3.4.1, 3.4.2) except that:

— For the part of the lookup using unqualified name lookup (3.4.1), only function declarations with external linkage from the template definition context are found.

— For the part of the lookup using associated namespaces (3.4.2), only function declarations with external linkage found in either the template definition context or the template instantiation context are found.

If the call would be ill-formed or would find a better match had the lookup within the associated namespaces considered all the function declarations with external linkage introduced in those namespaces in all translation units, not just considering those declarations found in the template definition and template instantiation contexts, then the program has undefined behavior.

関数呼び出しが、テンプレート仮引数に依存していた場合で、関数名が、unqualified-idで、しかもtemplate-idではないとき、lookupには、特別なルールが適用される。

通常のunqualified lookupでは、template definition contextから探される。つまり、point of instantiationでlookupされるにも関わらず、fのpoint of definitionでlookupされるのだ。

つまり、上記のコードの場合、g(int)は、通常のunqualified lookupでは、見つからない。

unqualified lookupで、何も見つけられなかった場合、ADLが発動する。これは、point of definitionとpoint of instantiationの両方のコンテキストで、associated namespaceが決定される。しかし、あくまでADLである。通常のlookupではない。

さて、int型のassociated namespaceとは何か。fundamental typeには、associated namespaceはない。つまり、ADLを行うべき、associated namespaceは、存在しない。そこで、ADLでも、g(int)を見つけることはできない。

呼び出すべき関数が見つからなければ、ill-formedのはずだ。しかし、問題は、さらに続きがあるということだ。呼び出しがill-formedの場合、undefined behaviorになるのである。したがって、もし、g(int)が呼び出せたとしても、規格上、何の問題もないということになる。鼻から悪魔が出ても、問題はない。

では、なぜこれが問題になるのか。というのも、本の虫: gcc4.5がVariadic TemplateのDependant name resolutionに対応していないで紹介した、あのコードも、undefined behaviorになってしまう。

template < typename T, typename ... Args >
T max( T const & a, T const & b, Args ... rest)
{
        return max( max(a, b), rest ... ) ;
}

template < typename T >
T max( T const & a, T const & b )
{
        return a < b ? b : a ;
}

int main()
{
        max(1, 2, 3) ;
}

さらに、point of instantiationで行われるlookupは、ADLだけだということに、注意が必要だ。以下のコードも、undefined behaviorである。

// point of definition
template < typename T>
void f(T x)
{ g(x) ; }

namespace A { class Foo {} ; }
void g( A::Foo ) { }

int main()
{// point of instantiation
    f( A::Foo() ) ;
}

なぜなら、point of instantiationからのADLでは、g()は見つからないからである。通常のunqualified lookupなら見つかるが、それは、point of definitionからしか行われない。

この問題は、2000年に指摘されている。DR197がそれだ。これを受けて、DR225で、解決案を模索することにした。そして、10年たった今もなお、提案はない。

個人的には、14.7.4.2 Candidate functions [temp.dep.candidate]の存在自体が信じられない。削除するべきだと思う。

それにしても、この本当の問題を、即答できるgccの開発者達には、頭が下がる。dupeであるとしてmergeされたbug reportを読むと、なぜか皆、ADLについて論じていた。最初は、訳が分からなかった。なぜADLなのだと。まさか、規格内に14.7.4.2 Candidate functions [temp.dep.candidate]のような文面があるとは。

6 comments:

Anonymous said...

「削除するべき」ということですが、この制限がないと困ることが
あるためにやむなく undefined behavior としているのだと思うので、
代案が必要になると思います。

たとえば DR 175 で修正された example のうち enum E と f(E) の
宣言がそれぞれ独立したヘッダに記述されていたとして、 enum E を
インクルードしながら f(E) のインクルードをしない状態での
g(e) の呼び出しでは f(char) が 3 回呼び出されることになります。
このような呼び出しを UB としない場合、コンパイル単位ごとに f(E) の
インクルードの有無によって f(e) の動作が分かれることを認めることに
なってしまいそうです。

江添亮 said...

しかしそれなら、最後の記述である、「すべての翻訳単位のexternal linkageな関数で、別の関数がbest viable functionとなったときは、プログラムはundefined behaviorである」という一文だけで十分だと思うのです。

Anonymous said...

"If the call would be ill-formed" は "would find a better
match" と似たようなケースで、同等の暗黙変換を通して呼び出し
可能な関数が複数になる場合(あるいはその場合だけ?)をカバー
しているものと思います。

この記事にあるように「ill-formedの場合、undefined behavior
である」と読めなくもないですが、 "is ill-formed" ではなく
"would be ill-formed" となっていることから、これも後に続く
"would find ..." と同じく他の翻訳単位を含めた場合の結果に
ついて言っていると読むのが正しいのではないかと。

冒頭のコードは、現行のとおり組み込み型について ADL での
検索対象が無いとすれば、 ill-formed でコンパイルできないと
するのが望ましいでしょうし。

14.7.4.2 についてはもうひとつ issue #561 が挙がっている
ようです。 ODR があるのだから名前検索に linkage の制限を
つけなくってもいいじゃないか、ということですが、エラーと
ならない未定義動作を増やすことになりそうで、ほんとうに
それでいいのか疑問なところです。

江添亮 said...

561は知らなかった。

Anonymous said...

規格の記述について疑問があるときは Index by Section を確認するのが
おすすめです。

江添亮 said...

おお、これは便利だ。