2013-12-24

テンプレートの実体化の実装方法とODR違反について

問題

以下のC++コードを考える。 

int plus( int a, int b )
{
    return a + b ;
}

double plus( double a, double b )
{
    return a + b ;
}

このC++コードは、int型とdouble型以外、コードはほぼ同じである。

しかし、ほとんどのコンピューターではint型とdouble型は操作方法が異なるため、この2つの関数は、全く別のコンピューターが処理できるコードに変換される。

ところで、古典的なC言語やC++コンパイラーの実装方法として、ソースコードのファイルをそれぞれ、一つ一つの翻訳単位としてコンパイルし、翻訳単位ごとにオブジェクトファイルを生成し、リンカーで複数のオブジェクトファイルを結合（リンク）して、単一のプログラムを生成するというものがある。

よくある実装では、オブジェクトファイルは、その翻訳単位では定義されていないの関数や変数などを、その名前を「シンボル名」として、未解決のまま参照しておき、リンカーがすべてのオブジェクトファイルが揃った時点で解決する。 

// f.cpp

// 定義
void f() { }

// main.cpp

// 宣言
void f() ;

int main()
{
    f() ; // fは定義されていない
}

C++規格では、単にソースファイルとか翻訳単位とか、複数の翻訳単位を合わせて単一のプログラムにするなどと規定されているだけでが、典型的な実装では、このようなソースファイルを分けて、別々にコンパイルして、オブジェクトファイルを生成し、後でリンクして単一のプログラムにすることを、俗に、「分割コンパイル」と呼んでいる。

またC++では、仮引数の型が違うが同じ名前の関数を、複数定義できる。そして、呼び出す際に、型の一致度の優先度を判定して、最適なものを呼び出す。これをオーバーロード解決(Overload resolution)という。 

// 別の翻訳単位で定義されている
void f( int x ) ; // #1
void f( double x ) ; // $2

int main()
{
    f( 0 ) ; // オーバーロード解決、#1
    f( 0.0 ) ; // オーバーロード解決、#2
}

しかし、これは古典的なコンパイルしてリンクという実装では、どのように実現すればいいのだろうか。どちらも同じ名前である。

C++の典型的な実装では、シンボル名に関数のシグネチャを埋め込む。これを、名前マングリング(name mangling)という。 

// 名前マングリングの例
void f_int_( int x ) ;
void f_double_( double x ) ; 

int main()
{
    // オーバーロード解決済み
    f_int_( 0 ) ;
    f_double_( 0.0 ) ;
}

このように、シンボル名にシグネチャを埋め込んでしまえば、賢くない古典的なリンカーでも、単にシンボル名の一致だけでリンクできる。C++では、名前マングリングの詳細は規定されていない。シンボル名が規定されていないのと同じだ。

さて、テンプレートの場合はどうか。 

template < typename T >
T plus( T a, T b )
{
    return a + b ;
}

int main()
{
    f( 1, 2 ) ;
    f( 1.0, 2.0 ) ;
}

関数テンプレートは、実引数推定(Argument Deduction)という機能により、テンプレート実引数を推定できる。これはつまり、以下のように呼ぶのと同じ意味である。 

int main()
{
    f<int>( 1, 2 ) ;
    f<double>( 1.0, 2.0 ) ;
}

テンプレート実引数は、< >という文法で指定する。関数の実引数が( )という文法で指定することと比較すれば、わかりやすいだろう。

テンプレート自体は、オブジェクトコードを生成しない。テンプレートは、コンパイル時に具体的なテンプレート実引数を与えられて、その実引数に対して、実体化する。テンプレートが実体化すると、あたかもコードを手で書いたかのように、実態が生成されて、使われる。もちろん、これにも名前マングリングが使われる。

さて、テンプレートも分割コンパイルしたいと思うだろうが・・・残念ながら、実装上の都合で、色々と難しいのだ。

テンプレートは、コンパイル時に実体化する必要がある。しかし、翻訳単位ごとに分割されていると、その実体化ができないのだ。 

// plus.cpp

// 定義
template < typename T >
T plus ( T a, T b )
{
    return a + b ;
}

// main.cpp

// 宣言
template < typename T >
T plus( T a, T b ) ;


int main()
{
    plus( 1, 1 ) ; // 実体化の生成が必要
}

今、plus.cpp、main.cppが、それぞれ別の翻訳単位であるとする。main.cppは、テンプレートplusの宣言から、テンプレートを実体化しなければならない。しかし、実体化するには、テンプレートの定義が必要だ。

実装方法

翻訳単位を超えたテンプレートの実体化を、どのように実装するかというのは、とても難しい問題だ。とくに、古典的な翻訳単位ごとにコンパイルしてリンクするというコンパイラーの場合、翻訳単位ごとに完全な定義が与えられていなければ、コードの実体化ができないという問題がある。

CFrontの実装

Bjarne StroustrupによるC++のリファレンス実装は、Cコードを出力して、Cコンパイラーでコンパイルする都合上、当時の古典的なコンパイラー技術で実装する必要があった。

名前マングリングは、そのために考案された。古典的なリンカーは、単にシンボル名の文字列一致だけをみてリンクするので、シンボル名にテンプレート実引数を埋め込んでおけば、その実体化へのリンクができる。

CFrontの実装は以下の通り

  • シンボルに名前マングリングする
  • テンプレートを実体化せずにコンパイル
  • 実体化していないために発生するリンクエラーメッセージをパース
  • 実体化の必要のあるテンプレートの特殊化を抽出
  • テンプレートの実体化を行う

この処理は、リンクエラーを吐かなくなるまで、繰り返し実行する必要がある、なぜならば、テンプレートを実体化した結果、別のテンプレートの実体化が必要になるからだ。 

template < typename T >
struct A { } ;

template < typename T >
struct B
{
    A<T> a ;
} ;

CFrontの、リンクエラーを用いたテンプレートの実体化の実装は、とてつもなく遅かった。ある大学は、他の方法で実装されたコンパイラーならば数時間でコンパイルできるコードが、CFrontでは一週間もかかると報告した。

SunのC++コンパイラーの実装

SunのC++コンパイラーは、いかにもSunらしい実装をしている。

  • プログラムを構成するすべての翻訳単位で共通のデータベースを用意
  • ある翻訳単位でテンプレートの実体化が必要ならば、データベースを参照
  • もし、すでに最新版の実体化が存在すればそのまま利用
  • もし、データベースに実体化が存在しなかったり、最新のソースコードより古く生成されたものであれば、実体化してデータベースに格納

いかにもSunらしいデータベースを活用した実装だ。この実装は、技術的には極めて自然であり、並列コンパイルによるコンパイル時間のスケールも特に問題はない。

問題といえば、実装が難しいことと、Makefileのような単純にファイルスタンプだけ比較するような古典的なビルドシステムを使うのが難しいということだ。

BorlandのC++コンパイラーの実装

この中で、彗星の如く現れたのがBorlandのC++コンパイラーだ。

  • テンプレートの定義をヘッダーファイルに書く
  • テンプレートの実体化を必要とするすべての翻訳単位から#include
  • 翻訳単位ごとに独立してテンプレートを実体化
  • リンク時に重複を取り除く

この実装では、リンカーが単にシンボル名の一致で参照を解決するものから、重複を取り除くということまでやるようになったので、古典的なリンカーとは言えないかも知れない。しかし、当時もリンカーはすでに相当複雑になっていたわけだ。

どうせリンク時に重複を取り除かれるのに、同じテンプレートを翻訳単位ごとに実体化するのは、一見すると非効率的のように思われるが、パフォーマンスは全く問題なかった。

そして何よりも、実装が簡単だった。

しかし問題になるのは、ODR(One Definition Rule)[§3.2]だ。単一定義の原則だ。C++では、定義はひとつしか存在できないのだ。 

// file1.cpp

template < typename T >
struct S { } ;

// file2.cpp

// 定義の重複
template < typename T >
struct S { } ;

int main()
{
    S<int> s ;
}

いま、file1.cppとfile2.cppがひとつのプログラムを構成するソースファイルであり、ソースファイルごとに翻訳単位が存在するとすると、当時のドラフト規格では、このコードは違法となる。

Borlandが最初に考えだしたこの実装方法を、規格上許容すべきかどうかは、標準化委員会でもかなり揉めた。ある者は、Borlandの実装方法はODRに明確に違反しており、本質的に汚いので、規格で禁止すべきだと主張した。また、この実装では、テンプレート定義はすべてヘッダーファイルに書いて、ソースファイルに字句的に取り込まなければならない。非テンプレートコードのように、宣言と定義を分けることができない。実体化を必要とするテンプレートであっても、宣言と定義を分けられるべきだという主張もされた。

とはいえ、Borland式の実装はとても実装が簡単で、多くのC++コンパイラーがBorland式の実装を使い始めた。そのため、さすがに現実を無視することもできず、規格で特別に、主にテンプレートに限り、別の翻訳単位に現れるまったく同じトークン列、全く同じ意味の定義を、特別にODR違反から除外することを許可した[§3.2 paragraph 6](実際にはもっと複雑に規定されている)

全く同じトークン列を保証するには、ヘッダーファイルとして書いて、#includeで取り込めばよい。まったく同じ意味とは、テンプレートの特殊化で呼び出す関数などが、テンプレートの実体化やオーバーロード解決を経た後でも、すべての翻訳単位で、同じでなければならない。 

// file1.cpp

void f( int ) { }

// 同じトークン列
template < typename T >
void g()
{
    f( 0 ) ;
}

// file2.cpp

void f( long ) { }

// 同じトークン列
tempalate < typename T >
void g()
{
    f( 0 ) ;
}

このような複数の翻訳単位からなるプログラムは、違法である。

先週、この問題を解説する必要があったが、なかなかこのような問題は口頭で解説するのが難しく、おそらく正しく理解してもらえなかったと思うので、ブログに書いておくことにした。

実は、これと似たような歴史的経緯を、株式会社ロングゲート - プログラミングの魔導書 ～Programmers’ Grimoire～ vol.1で書いた「C++の歴史」でも解説している。そういえば、私は魔導書のVol.3には関わっていない。今回、C++色は薄かったようだ。Vol.4はどうなるのだろうか。

at 16:10 Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)