ここは匣

C++ Advent Calender 2014(http://qiita.com/advent-calendar/2014/cpp) 11日目の記事です．

はじめに

今年はこれまでコンパイル時の話について沢山記事にしてきたので，たまにはリンク時に関連することを記事にしてみようと思います．把握している人にとっては当たり前の内容ですが，日本語情報としてまとまっている記事は案外少ない気がするので初学者等に少しでもお役に立てば幸いです．

この記事を執筆するにあたっては最新のWorking draftであるN4140(https://github.com/cplusplus/draft/blob/master/papers/n4140.pdf)を参考にしています．本記事の内容は主に，3 Basic concepts内の3.1 Declarations and definitions，3.2 One definition rule及び3.5 Program and Linkageに関連するものです．本記事では重箱の隅をつつくことはやめ，ルールの厳密な解説より，ある程度ざっくり話すことで分かりやすさを重視することにします．より詳細な情報を求める場合は，N4140等を参照して下さい．

Declarations and definitions

C++においては，宣言(declaration)と定義(definition)ははっきりと区別されます．宣言とは翻訳単位にある名前を導入する行為です．宣言が特定の条件を満たす場合に，それが定義にもなります．

例えば，次のコードの各行をそれぞれ分類するとコメントのようになります．

int a;  // defines a
extern int b1 = 1; // defines b1
extern int b2;  // declares, but doesn't defines b2
void f() {}  // defines f
void g();  // declares, but doesn't defines g
struct S1 {};  // defines S1
struct S2 {  // defines S2
    static int c;  // declares, but doesn't defines c
};
int S2::c = 0;  // defines S2::c
struct S3;  // declares, but doesn't defines S3

宣言のうち，定義とならないものの条件は細かく定義されていますが，頻出する具体的としては

実装を伴わない関数
実装を伴わないクラス
extern修飾され，初期化を伴わない変数
クラスの静的メンバ

辺りを把握しておけば良いと思います．クラスの静的メンバを定義し忘れてリンカエラーを引き起こした経験がある人も多いと思います．

では，何故宣言と定義は厳密に区別されているのでしょうか．理由の一つは，ある名前を使う場合に宣言のみで良い使用と定義を必要とする使用があるからです．この話をするためには，One definition ruleとodr-useについて知らなければなりません．

One definition rule

One definition rule (ODR)は，大雑把に説明すれば，いかなる翻訳単位もあらゆる変数，関数，クラス型，enum型，テンプレートについて基本的に複数の定義を持つことは出来ないというルールです．

One definition ruleがない場合例えば以下の関数fの呼出しは，上で定義したどちらの関数fを呼び出していいのか分からなくなってしまいます．

int f() { return 0; }
int f() { return 1; }

f();

実際には，One definition ruleがあるため，コンパイラは次のようなエラーメッセージを出力し，コンパイルを中断します．

a.cpp:2:5: error: redefinition of 'f'
int f() { return 1; }
    ^
a.cpp:1:5: note: previous definition is here
int f() { return 0; }

関数fの定義はただ1つだけであり，重複定義は認めないのです．

odr-use

次にodr-useについて述べます．odr-useは，これまた大雑把に説明すれば，定義を要する名前の使用です．逆に言えば，ある名前がodr-usedとなるということは，その使用には定義が必要となると読み替えても良いでしょう．odr-useはフォーマルにはpotentially evaluatedや，potential resultsのような語を用いて説明されますが，あまり深く掘り下げると理解を損ねてしまいかねません．名前の使用の多くはodr-useに当てはまるので，ここではodr-useでない具体例のうち分かりやすいものを取り上げることにします．

odr-useとならない具体例

定数式となる場合の変数やそれを含む式である場合
結果が捨てられる式(discarded-value expression)である場合
完全型を必要としない型名の使用の場合

完全型というのは，簡単にここでは定義を持つ型と考えます．以下は例です．

struct X;  // 定義を持たない型

struct S {
    static const bool b = true;
    static int i;
    X* ptr;  // XのポインタはXの定義を必要としないので問題無い
};

int main() {
    static_assert(S::b, "");  // S::bは定数式になるので問題ない
    S::i;  // discarded-value expressionなので問題ない
    S::i = 0;  // i is odr-used この操作にはiの定義が必要であり，リンカエラーが発生する．
}

重要なのは，静的メンバ定数でしょう．これはメタ関数で極めて頻繁に現れるケースです．

さて，先ほど変数や関数等は基本的に複数の定義を持つことは出来ないと述べましたが，基本的にということはやはり例外があります．具体例が，テンプレートとインライン関数です．

テンプレートは，コンパイル時に実体化する必要がありますが，翻訳単位ごとにその定義が分割されているとその実体化を行うことが困難であるため，それぞれの翻訳単位ごとに定義を持つ事が認められています．また，インライン関数も同様にしてインライン展開をする為にはそれがodr-useされるすべての翻訳単位に定義を持つ必要があり，それが認められています．ただし，それらは全ての翻訳単位においてまったく同じトークン列、全く同じ意味の定義でなければなりません．One definition ruleを違反するとそのプログラムの振る舞いは未定義になります，また処理系はこの違反を警告しなくても良いことになっています．この辺りの話は，本の虫 - テンプレートの実体化の実装方法とODR違反について(http://cpplover.blogspot.jp/2013/12/odr.html)などで言及されています．

1つ，参考記事(http://qiita.com/kktk-KO/items/075ce9a784d5d8296d53)からODR違反の例を拝借してきましょう．

a.cpp

#include <iostream>

inline int f() { return 0; }
void g() { std::cout << f() << std::endl; }

int main() {
  g();
}

b.cpp

inline int f() { return 1; }
void h() { f(); }

このプログラムは，a.cpp及びb.cpp単体をコンパイルする分には問題ありませんが，リンクする際にODR違反があるため問題になります．このプログラムの挙動は未定義となるため，例えばリンクの順番に依存して変化してしまったりします．処理系はこれを検出し警告してくれはしないのできちんとルールを理解しておく必要があります．

Program and Linkage

翻訳単位の話なども出たので，プログラム(Program)とリンケージ(Linkage)の項についても書くことにします．

C++において，プログラムとは1つ以上の翻訳単位をリンクしたものです．名前が，別のスコープで宣言によって導入された名前と同じオブジェクト，リファレンス，機能，タイプ，テンプレート，名前空間または値を表すであろう場合にリンケージを持っているといいます．表すであろう，というのは先ほどの違反例のように，処理系はある名前が同じ関数を表していると思っているが実際には違ってしまっているケースもあることを暗に意味しています．

異なる翻訳単位である名前が同じ実体(entity)を表しているかどうかを決定づける点で，リンケージは重要です．

ある名前が持つリンケージの状態は3種類あります．

名前が外部リンケージ(external linkage)を持つ
名前が内部リンケージ(internal linkage)を持つ
名前はリンケージを持たない(no linkage)

外部リンケージ

名前が外部リンケージを持つ場合，それが表す実体は他の翻訳単位のスコープ或いは同じ翻訳単位の他のスコープから名前によって参照することが出来ます．これは，つまるところ異なる翻訳単位において同じ1つの実体を共有するということです．

この外部リンケージを持つものは具体的には

"無名名前空間或いは，その中にある名前空間や無名名前空間"を除く名前空間

などがあります．

内部リンケージ

名前が内部リンケージを持つ場合，それが表す実体は同じ翻訳単位の他のスコープから名前によって参照することが出来ます．

この内部リンケージを持つものは具体的には

static修飾された変数，関数，関数テンプレート
明示的にconstかconstexprと宣言され、externと宣言されておらず、前方で外部リンケージをもつと宣言されていない非volatile変数
無名unionのデータメンバ
無名名前空間或いは，その中にある名前空間や無名名前空間

などがあります．

namespace {
    /* この中の要素はinternal linkage */
}

属する名前空間等のリンケージに従うもの

多くの要素は，それが属する名前空間等のリンケージと同じリンケージを持ちます．以下はそのような例です．

変数，関数，名前付きクラス/enum，typedef宣言によって定義された名前を持つ無名クラス/enum
列挙子は属するenumのリンケージに従う
テンプレート

メンバ関数や静的データメンバ，クラス等はそれが属するクラス名が外部リンケージを持つ場合，外部リンケージを持ちます．

ブロックスコープでextern修飾され宣言された関数名や変数名は外部リンケージを持ちます．ただし，ブロックスコープ外に同じ名前と型を持つリンケージを持つ実体が存在する場合，前回の宣言に従います．マッチするそのような実体が複数存在した場合は，ill-formedとなります．そのような実体が存在しなければ，ブロックスコープ内のextern指定された名前は外部リンケージを持ちます．

static void f(); // internal linkage
{
    extern void f(); // internal linkage
}

ブロックスコープで宣言されたリンケージを持つ名前が，前方宣言されているものでない場合，その名前はそのブロックスコープを包む直前の名前空間のメンバになります．

上記の条件に当てはまらなかったものはリンケージを持ちません．

次に型がリンケージを持つといえる場合です．それは以下の状況に限られます．

クラス或いはenum(或いはtypedef名のある無名のクラスやenum)でその名前がリンケージを持つもの
無名クラスや無名enumで，リンケージを持つクラスのメンバであるもの
クラステンプレートの特殊化
基本型
複合型
リンケージを持つ型がcv修飾されたもの

リンケージを持たない型は，次の場合を除いて外部リンケージを持つ関数やクラスとして使うことが出来ません．

実体がC言語のリンケージを持つ場合
無名名前空間内で宣言されている場合
実体がodr-usedでない場合，或いは同じ翻訳単位で定義されている場合

異なるスコープで宣言された同じ2つの名前は次の条件を満たす場合に，同じ変数，関数，型，enum，テンプレート，名前空間を表します．

両方の名前が外部リンケージを持つか，内部リンケージを持ち尚且つ同じ翻訳単位で宣言されている場合
継承でなく，同じ名前空間/クラスのメンバを参照している場合
関数を指すとき，仮引数リストが一致している場合
関数テンプレートを指すとき，シグネチャが一致している場合

ひと通りルールの整理が終わったので実際にサンプルコードで様子を見ることにします．次のようなコードで内部リンケージを実感してみます．

a.cpp

#include <iostream>

static const int i = 0;  // defines i

void f() { std::cout << &i << std::endl; }
void g();

int main() {
  f();
  g();
}

b.cpp

#include <iostream>

static const int i = 0;  // defines i

void g() { std::cout << &i << std::endl; }

コンパイル, リンクして実行してみると以下のようになりました．

0x10a95aeec
0x10a95aef0

翻訳単位ごとに実体が異なる事が分かります． nmを実行するとiはa.oでは

s __ZL1i

b.oでは

S _i

となっていました．

次に外部リンケージを試してみます．

a.cpp

#include <iostream>

extern const int i;  // declares, but doesn't define i

void f() { std::cout << &i << std::endl; }
void g();

int main() {
  f();
  g();
}

b.cpp

#include <iostream>

extern const int i = 0;  // defines i

void g() { std::cout << &i << std::endl; }

コンパイル, リンクして実行してみると以下のようになりました．

0x102210eec
0x102210eec

今度は異なる翻訳単位で同一の実体を指している事が分かります．

この場合nmを実行するとiはa.oでは

U _i

b.oでは

S _i

となっていました．a.oでは未定義のシンボルという扱いですね．

関数についても例を挙げてシンボルを見比べてみます．

void f() {}

int main() { f(); }

0000000000000060 s EH_frame0
0000000000000000 T __Z1fv
0000000000000078 S __Z1fv.eh
0000000000000010 T _main
00000000000000a0 S _main.eh

namespace {  // この中で宣言された関数は内部リンケージを持つ
    void f(){}
}

int main() { f(); }

0000000000000058 s EH_frame0
0000000000000010 t __ZN12_GLOBAL__N_11fEv
0000000000000098 s __ZN12_GLOBAL__N_11fEv.eh
0000000000000000 T _main
0000000000000070 S _main.eh

シンボルが実際にどのような扱いになっているのか見てみるのは良いですね．

リンケージの最後として，試しに内部リンケージで宣言した変数の実体を別の翻訳単位から参照してみることにします．

a.cpp

static const int i = 0;  // defines i as internal linkage
void f();

int main() {
  f();
}

b.cpp

#include <iostream>

extern const int i;  // declares, but doesn't define i
void f() { std::cout << i << std::endl; }

コンパイル, リンクしてみます．

Undefined symbols for architecture x86_64:
  "_i", referenced from:
      f() in b.o
ld: symbol(s) not found for architecture x86_64

b.cppからは内部リンケージを持つa.cpp内のiを参照する事は出来ないので，リンクの際にiの実体も定義も見つけることが出来ず，(期待通り)リンカエラーとなりました．

おわりに

規格における，3 Basic concepts内の3.1 Declarations and definitions，3.2 One definition rule及び3.5 Program and Linkageに関連する内容を大雑把に例を挙げながら記事にしてみました．これといって面白みもなければ凄みもないごく当たり前の内容ですし，詳細を省いたので厳密に知りたい人には不十分，といった感じかもしれませんが少しでも参考になれば幸いです．

当初はname manglingの話やweak symbolの話などを書いてみようかとも思ったのですが，さほど詳しいわけでもなければ，既に十分な長さになってしまったので控えておきます．

[プリプロセッサ, 再帰]などで検索して来られる方が居ますがCプリプロセッサで再帰は出来ません。プリプロセッサメタプログラミングにおける要素の走査は、再帰っぽく見えるだけで実際にはただの連番マクロを用いた展開によって実装されています。

少し実用的な可変長引数を順番に展開する例を掲載しておきます。

[Wandbox]三へ( へ՞ਊ ՞)へﾊｯﾊｯ

#define CAT_I(x, y) x ## y
#define CAT(x, y) CAT_I(x, y)

#define INC0 1
#define INC1 2
#define INC2 3
#define INC3 4
#define INC4 5
#define INC5 6
#define INC6 7
#define INC7 8
#define INC8 9
#define INC(i) CAT(INC, i)

#define EMPTY(...)
#define DEF_COMMA0 _,1 EMPTY
#define COMMA0() ,0
#define IS_EMPTY_III(f, s) s
#define IS_EMPTY_II(t) IS_EMPTY_III t
#define IS_EMPTY_I(x) IS_EMPTY_II((DEF_ ## x()))
#define IS_EMPTY(x, ...) IS_EMPTY_I(x COMMA0)

#define IF_0(x, y) y
#define IF_1(x, y) x
#define IF(cond, x, y) CAT(IF_, cond)(x, y)

#define FOR_EACH_I9(i, F, x, ...) F(x) IF(IS_EMPTY(__VA_ARGS__), EMPTY, CAT(FOR_EACH_I, i))(INC(i), F, __VA_ARGS__)
#define FOR_EACH_I8(i, F, x, ...) F(x) IF(IS_EMPTY(__VA_ARGS__), EMPTY, CAT(FOR_EACH_I, i))(INC(i), F, __VA_ARGS__)
#define FOR_EACH_I7(i, F, x, ...) F(x) IF(IS_EMPTY(__VA_ARGS__), EMPTY, CAT(FOR_EACH_I, i))(INC(i), F, __VA_ARGS__)
#define FOR_EACH_I6(i, F, x, ...) F(x) IF(IS_EMPTY(__VA_ARGS__), EMPTY, CAT(FOR_EACH_I, i))(INC(i), F, __VA_ARGS__)
#define FOR_EACH_I5(i, F, x, ...) F(x) IF(IS_EMPTY(__VA_ARGS__), EMPTY, CAT(FOR_EACH_I, i))(INC(i), F, __VA_ARGS__)
#define FOR_EACH_I4(i, F, x, ...) F(x) IF(IS_EMPTY(__VA_ARGS__), EMPTY, CAT(FOR_EACH_I, i))(INC(i), F, __VA_ARGS__)
#define FOR_EACH_I3(i, F, x, ...) F(x) IF(IS_EMPTY(__VA_ARGS__), EMPTY, CAT(FOR_EACH_I, i))(INC(i), F, __VA_ARGS__)
#define FOR_EACH_I2(i, F, x, ...) F(x) IF(IS_EMPTY(__VA_ARGS__), EMPTY, CAT(FOR_EACH_I, i))(INC(i), F, __VA_ARGS__)
#define FOR_EACH_I1(i, F, x, ...) F(x) IF(IS_EMPTY(__VA_ARGS__), EMPTY, CAT(FOR_EACH_I, i))(INC(i), F, __VA_ARGS__)
#define FOR_EACH_I0(i, F, x, ...) F(x) IF(IS_EMPTY(__VA_ARGS__), EMPTY, CAT(FOR_EACH_I, i))(INC(i), F, __VA_ARGS__)
#define FOR_EACH_I(i, F, ...) IF(IS_EMPTY(__VA_ARGS__), EMPTY, CAT(FOR_EACH_I, i))(INC(i), F, __VA_ARGS__)
#define FOR_EACH(F, ...) FOR_EACH_I(0, F, __VA_ARGS__)

#define HELLO(x) Hello, x!

FOR_EACH(HELLO, a, b, c, d, e, f, g)

Output:

Hello, a! Hello, b! Hello, c! Hello, d! Hello, e! Hello, f! Hello, g!

ここは匣

tupleの実装解説記事

リンク時に関連するルールの話

はじめに

Declarations and definitions

One definition rule

odr-use

Program and Linkage

外部リンケージ

内部リンケージ

属する名前空間等のリンケージに従うもの

おわりに

99 bottles of beer

TMPでboolの計算 (memo)

Template Parameter Packの要素へのアクセス

プリプロセッサでFOR_EACHを実現する

何故noexceptの方がthrow()より高速なコードを生成出来るのか?