dynamic_cast の実装を読み解く

# はじめに

[前回](http://qiita.com/msmania/items/452d4fb4dec76207df87) に引き続き、VTable シリーズ第二弾です。前回の記事で仮想継承について書くとか言っておきながら dynamic_cast についてです。補足として追記する予定だったのですが、それどころではない長さになったので記事を分けました。

dynamic_cast だけではなく、静的キャストついても調べました。キャストの挙動を理解したくてたまらない暇な人、ぜひ読んでください。

# C++ のキャスト演算子についておさらい

dynamic_cast は、型情報を使うことで up/down/side 方向の型変換をそれなりに安全にやってくれる機能です。型情報は VTable のエントリの一つであるため、dynamic_cast を使うためにはクラスが VTable を持っていないといけません。よって、クラスに仮想関数が少なくとも一つ必要です。そのようなクラスのオブジェクトを Polymorphic objects と呼びます。

Object - cppreference.com
http://en.cppreference.com/w/cpp/language/object#Polymorphic_objects

さらに Visual C++ の場合、型情報の生成を無効にする /GR- オプションが付加されていると、Polymorphic objects に対する dynamic_cast であってもコンパイルすることはできません。

Polymorphic なクラス間の関係に対する各キャスト演算子の使用可否を調べるため、前回の記事で使ったプログラムに手を加えて以下のコードを書きました。ここではコンパイルが通るかどうかを確認できればよいので、cast_test という関数の定義を追加するに留め、呼び出しは行なっていません。キャストで使うポインターは全部 nullptr にしています。Makefile は前回と同じです。

前回は g++ 5.4.0 でしたが、今回は g++ 6.2.0 を使っています。結果は変わらないと思いますが念のため。

```C++:01.cpp
class B1 {
public:
  void f0() {}
  virtual void f1() {}
  int int_in_b1;
};

class B2 {
public:
  virtual void f2() {}
  int int_in_b2;
};

class D : public B1, public B2 {
public:
  void d() {}
  void f2() {}  // override B2::f2()
  int int_in_d;
};

void cast_test() {
  D *d = nullptr;
  B1 *b1 = nullptr;
  B2 *b2 = nullptr;
  void *p = nullptr;

  // upcast: D* --> B2*
  b2 = d;
  b2 = static_cast<B2*>(d);
  b2 = dynamic_cast<B2*>(d);
  b2 = reinterpret_cast<B2*>(d);

  // upcast: B2* --> void*
  p = b2;
  p = static_cast<void*>(b2);
  p = dynamic_cast<void*>(b2);
  p = reinterpret_cast<void*>(b2);

  // downcast: void* --> B2*
  b2 = p;                       // invalid conversion
  b2 = static_cast<B2*>(p);
  b2 = dynamic_cast<B2*>(p);    // cannot dynamic_cast
  b2 = reinterpret_cast<B2*>(p);

  // downcast: B2* --> D*
  d = b2;                       // invalid conversion
  d = static_cast<D*>(b2);
  d = dynamic_cast<D*>(b2);
  d = reinterpret_cast<D*>(b2);

  // sidecast: B1* --> B2*
  b2 = b1;                      // cannot convert
  b2 = static_cast<B2*>(b1);    // invalid static_cast
  b2 = dynamic_cast<B2*>(b1);
  b2 = reinterpret_cast<B2*>(b1);
}

int main() {
  return 0;
}
```

```Make:Makefile
CC=g++
RM=rm -f
TARGET=t
SRCS=$(wildcard *.cpp)
OBJS=$(SRCS:.cpp=.o)

override CFLAGS+=\
	-Wall\
	-O0\
	-g\
	-fPIC\
	-std=c++14\
	-fdump-class-hierarchy\

LFLAGS=\

INCLUDES=\

LIBDIRS=\

LIBS=\
	-lpthread\

all: $(TARGET)

$(TARGET): $(OBJS)
	$(CC) $(LFLAGS) $(LIBDIRS) $^ -o $@ $(LIBS)

.cpp.o:
	$(CC) $(INCLUDES) $(CFLAGS) -c $<

clean:
	$(RM) $(OBJS) $(TARGET)
```

make すると、cast_test 関数の中でコメントを入れた 5 箇所がコンパイル エラーになります。結果を分かりやすくするため、表にまとめました。表中の no error はコンパイル エラーが出ないという意味で、安全に使えるという意味ではありません。望まない型変換が行われると、それがそのまま Type confusion と呼ばれる脆弱性に繋がるため注意が必要です。エラー メッセージは g++ のものです。

| |implicit conversion|static_cast|dynamic_cast|reinterpret_cast|
|:--|:--|:--|:--|:--|:--|
|**upcast:**<br />D* --> B2*|no error|no error|no error|no error|
|**upcast:**<br />B2* --> void*|no error|no error|no error|no error|
|**downcast:**<br />void* --> B2*|error:<br />invalid conversion|no error|error:<br />cannot dynamic_cast|no error|
|**downcast:**<br />B2* --> D*|error:<br />invalid conversion|no error|no error|no error|
|**sidecast:**<br />B1* --> B2*|error:<br /> cannot convert|error:<br />invalid static_cast|no error|no error|

表から以下の動作を読み取ることができます。

* 暗黙の型変換は upcast のみに対応
* static_cast は upcast と downcast に対応
* dynamic_cast は upcast、downcast、sidecast すべてに対応<br />ただし変換元が void* である場合を除く
* reinterpret_cast は常に成功

# 静的キャストの動作を確認する

Polymorphic objects の型変換において、静的だとか動的だとかの区別があるのはなぜでしょうか。この点が記事のテーマである VTable に関連する部分で、Polymorphic objects の場合、同じオブジェクトを示すポインターであっても、そのポインターの型によって指すべきアドレス値が変わるからです。

上に挙げた 01.cpp では、Makefile のレシピに -fdump-class-hierarchy オプションを加えているので、make するとクラスの内部構造がダンプされます。そのファイルからクラス D に該当する部分を抜き出しました。

```
Class D
   size=32 align=8
   base size=32 base align=8
D (0x0x7f9e092c8460) 0
    vptr=((& D::_ZTV1D) + 16u)
  B1 (0x0x7f9e093f8780) 0
      primary-for D (0x0x7f9e092c8460)
  B2 (0x0x7f9e093f87e0) 16
      vptr=((& D::_ZTV1D) + 48u)

Vtable for D
D::_ZTV1D: 7u entries
0     (int (*)(...))0
8     (int (*)(...))(& _ZTI1D)
16    (int (*)(...))B1::f1
24    (int (*)(...))D::f2
32    (int (*)(...))-16
40    (int (*)(...))(& _ZTI1D)
48    (int (*)(...))D::_ZThn16_N1D2f2Ev
```

前回の記事では、上記出力が示す構造を実際に gdb を使って確認しました。例えば Class D 配下の "D (0x0x7f9e092c8460) 0" という記載は、D のオブジェクトはオフセット 0 から見ると D や B1 として振る舞うという意味で、"B2 (0x0x7f9e093f87e0) 16" は、オフセット 16 から見ると B2 として振る舞う、と解釈します。それぞれのオフセットの位置には D の VTable の中の適切なオフセット (+16 と +48) を示すアドレスが配置されており、これがポリモーフィズムを実現します。

同じオブジェクトを指すポインターでも型によって値が変わる、という動作を確認するのは簡単で、キャスト前後でのアドレスを実際に見るだけで済みます。01.cpp を今度は以下のように書き替えた 02.cpp を作りました。cast_test の代わりに cast_test_static 関数を追加して main から呼び出すようにしています。キャストするポインターは、01.cpp で使った nullptr の代わりに 0x100 という適当な値を reinterpret_cast して使うことにしました。後でアセンブリを確認しますが、static_cast は変換元アドレスが 0 である場合は常に 0 を返すため、今回の用途では使えません。0 でなければ何でもいいので、0x100 の代わりに 1 や -1 でも欲しい結果は得られます。

```C++:02.cpp
#include <iostream>

class B1 {
public:
  void f0() {}
  virtual void f1() {}
  int int_in_b1;
};

class B2 {
public:
  virtual void f2() {}
  int int_in_b2;
};

class D : public B1, public B2 {
public:
  void d() {}
  void f2() {}  // override B2::f2()
  int int_in_d;
};

void cast_test_static() {
  D *d = reinterpret_cast<D*>(0x100);
  B1 *b1 = reinterpret_cast<B1*>(0x100);
  B2 *b2 = reinterpret_cast<B2*>(0x100);
  void *p = reinterpret_cast<void*>(0x100);

  std::cout
    << "# original values" << std::endl
    << "  d = " << d << std::endl
    << " b1 = " << b1 << std::endl
    << " b2 = " << b2 << std::endl
    << "  p = " << p << std::endl
    << "# upcast: D* -> B2*" << std::endl
    << "         static_cast<B2*>(d) = " << static_cast<B2*>(d) << std::endl
    << "    reinterpret_cast<B2*>(d) = " << reinterpret_cast<B2*>(d) << std::endl
    << "# upcast: B2* -> void*" << std::endl
    << "      static_cast<void*>(b2) = " << static_cast<void*>(b2) << std::endl
    << " reinterpret_cast<void*>(b2) = " << reinterpret_cast<void*>(b2) << std::endl
    << "# downcast: void* -> B2*" << std::endl
    << "         static_cast<B2*>(p) = " << static_cast<B2*>(p) << std::endl
    << "    reinterpret_cast<B2*>(p) = " << reinterpret_cast<B2*>(p) << std::endl
    << "# downcast: B2* -> D*" << std::endl
    << "         static_cast<D*>(b2) = " << static_cast<D*>(b2) << std::endl
    << "    reinterpret_cast<D*>(b2) = " << reinterpret_cast<D*>(b2) << std::endl
    << "# sidecast: B1* -> B2*" << std::endl
    << "   reinterpret_cast<B2*>(b1) = " << reinterpret_cast<B2*>(b1) << std::endl;
}

int main() {
  cast_test_static();
  return 0;
}
```

出力結果は以下のようになりました。

```
$ ./t
# original values
  d = 0x100
 b1 = 0x100
 b2 = 0x100
  p = 0x100
# upcast: D* -> B2*
         static_cast<B2*>(d) = 0x110
    reinterpret_cast<B2*>(d) = 0x100
# upcast: B2* -> void*
      static_cast<void*>(b2) = 0x100
 reinterpret_cast<void*>(b2) = 0x100
# downcast: void* -> B2*
         static_cast<B2*>(p) = 0x100
    reinterpret_cast<B2*>(p) = 0x100
# downcast: B2* -> D*
         static_cast<D*>(b2) = 0xf0
    reinterpret_cast<D*>(b2) = 0x100
# sidecast: B1* -> B2*
   reinterpret_cast<B2*>(b1) = 0x100
```

この結果を元に、それぞれのキャストがポインターに行なった演算について表にまとめました。

| |static_cast|reinterpret_cast|
|:--|:-:|:-:|
|upcast: D* --> B2*|+0x10|&plusmn;0|
|upcast: B2* --> void*|&plusmn;0|&plusmn;0|
|downcast: void* --> B2*|&plusmn;0|&plusmn;0|
|downcast: B2* --> D*|-0x10|&plusmn;0|
|sidecast: B1* --> B2*|N/A|&plusmn;0|

reinterpret_cast はポインターの値を変化させません。reinterpret という名前から考えてもこれは自然な動作です。見落としがちですが、static_cast も void* が絡むときは reinterpret_cast と同様に値を変化させません。このため、Polymorphic な型を void* にキャストするときは気を付けないといけません。本来なら +0x10 すべき D* --> B2* の変換も、`static_cast<B2*>(static_cast<void*>(d))` のように void* を経由して static_cast するとアドレスの調整が行われないからです。

static_cast と reinterpret_cast、そして暗黙の型変換は静的なキャストと言えます。コンパイル時にキャストの動作が一意に決定され、アセンブリ上ではポインターを定数バイト分加減算しているだけになるからです。上記の例で言えば、B2 と D には差が 16 バイトあることがコンパイル時に分かるので、static_cast はそれを単純に足したり引いたりするだけです。したがって static_cast に VTable は必要ありません。0x100 という適当なアドレスをキャストする際、0x100 の近傍に VTable は存在しないにも関わらず 0xf0 や 0x110 といった値が返ってきていることからも、キャストが静的に行なわれていることが分かります。

対する dynamic_cast は、VTable の内容に応じてキャストの挙動が実行時に動的に決まるため、動的キャストと呼ばれます。

本題の dynamic_cast に移る前に、static_cast のアセンブリを見ておきましょう。上記の 02.cpp における cast_test_static 関数を逆アセンブルした結果を以下に示します。static_cast の動作を把握しやすいように注釈を入れました。

```
(gdb) disas $rip
Dump of assembler code for function cast_test_static():
   0x0000555555554bc0 <+0>:     push   %rbp
   0x0000555555554bc1 <+1>:     mov    %rsp,%rbp
   0x0000555555554bc4 <+4>:     push   %r12
   0x0000555555554bc6 <+6>:     push   %rbx
   0x0000555555554bc7 <+7>:     sub    $0x20,%rsp
=> 0x0000555555554bcb <+11>:    movq   $0x100,-0x30(%rbp) ; d
   0x0000555555554bd3 <+19>:    movq   $0x100,-0x28(%rbp) ; b1
   0x0000555555554bdb <+27>:    movq   $0x100,-0x20(%rbp) ; b2
   0x0000555555554be3 <+35>:    movq   $0x100,-0x18(%rbp) ; p

   0x0000555555554beb <+43>:    cmpq   $0x0,-0x20(%rbp)
   0x0000555555554bf0 <+48>:    je     0x555555554bfc <cast_test_static()+60>
   0x0000555555554bf2 <+50>:    mov    -0x20(%rbp),%rax   ; rax = b2
   0x0000555555554bf6 <+54>:    lea    -0x10(%rax),%rbx   ; rbx = static_cast<D*>(b2) = b2 - 0x10
   0x0000555555554bfa <+58>:    jmp    0x555555554c01 <cast_test_static()+65>
   0x0000555555554bfc <+60>:    mov    $0x0,%ebx          ; rbx = static_cast<D*>(b2) = 0

   0x0000555555554c01 <+65>:    cmpq   $0x0,-0x30(%rbp)
   0x0000555555554c06 <+70>:    je     0x555555554c12 <cast_test_static()+82>
   0x0000555555554c08 <+72>:    mov    -0x30(%rbp),%rax   ; rax = d
   0x0000555555554c0c <+76>:    lea    0x10(%rax),%r12    ; r12 = static_cast<B2*>(d) = d + 0x10
   0x0000555555554c10 <+80>:    jmp    0x555555554c18 <cast_test_static()+88>
   0x0000555555554c12 <+82>:    mov    $0x0,%r12d         ; r12 = static_cast<B2*>(d) = 0
   0x0000555555554c18 <+88>:    lea    0x5ba(%rip),%rsi

   0x0000555555554c1f <+95>:    mov    0x2013ba(%rip),%rax
   0x0000555555554c26 <+102>:   mov    %rax,%rdi
   0x0000555555554c29 <+105>:   callq  0x555555554a60

(...この間、条件分岐なしで mov, lea, call 命令が延々と続くので省略...)

   0x0000555555554fa2 <+994>:   callq  0x555555554a78
   0x0000555555554fa7 <+999>:   nop
   0x0000555555554fa8 <+1000>:  add    $0x20,%rsp
   0x0000555555554fac <+1004>:  pop    %rbx
   0x0000555555554fad <+1005>:  pop    %r12
   0x0000555555554faf <+1007>:  pop    %rbp;
   0x0000555555554fb0 <+1008>:  retq
End of assembler dump.
```

キャスト演算子による加減算を先に済ませてから、cout への出力を条件分岐なしで一気に行う流れになっています。アセンブリの中でキャストの痕跡が残っているのは、ポインターの調整が必要な `static_cast<B2*>(d)` と `static_cast<D*>(b2)` だけです。他のキャストの痕跡はなく、スタック上に保存したオリジナルの変数である d/b1/b2/p の値をそのまま cout の << 演算子に渡しています。

前述のように、static_cast は変換元のアドレスが 0 かどうかを申し訳程度にチェックしていて、もし 0 であった場合はポインターを加減算せずに 0 を返す処理になっていることも確認できます。

このようにアセンブリを見ると、static_cast や reinterpret_cast が静的なキャストであるイメージを掴みやすいと思います。

# dynamic_cast の動作を確認する

ようやく dynamic_cast の順番が来ました。まずは静的キャストのときにまとめたような表を作ることにします。ここでは以下のコードを用意しました。cast_test_static の代わりに cast_test_dynamic という関数テンプレートを追加します。

```C++:03.cpp
#include <iostream>
#include <typeinfo>

class B1 {
public:
  void f0() {}
  virtual void f1() {}
  int int_in_b1;
};

class B2 {
public:
  virtual void f2() {}
  int int_in_b2;
};

class D : public B1, public B2 {
public:
  void d() {}
  void f2() {}  // override B2::f2()
  int int_in_d;
};

#define DIFF(T, P) \
  dynamic_cast<T>(P) << " (diff= 0x" \
  << std::hex \
  << (reinterpret_cast<char*>(dynamic_cast<T>(P)) \
      - reinterpret_cast<char*>(P)) << ")"

template <class T>
void cast_test_dynamic(T t) {
    std::cout
      << typeid(T).name()
      << " t = " << t << std::endl
      << "     dynamic_cast<D*>(t) = " << DIFF(D*, t) << std::endl
      << "    dynamic_cast<B1*>(t) = " << DIFF(B1*, t) << std::endl
      << "    dynamic_cast<B2*>(t) = " << DIFF(B2*, t) << std::endl
      << "  dynamic_cast<void*>(t) = " << DIFF(void*, t) << std::endl
      ;
}

int main() {
  D  *d  = new D();
  B1 *b1 = new B1();
  B2 *b2 = new B2();
  cast_test_dynamic(reinterpret_cast<D*>(0));
  cast_test_dynamic(reinterpret_cast<B1*>(0));
  cast_test_dynamic(reinterpret_cast<B2*>(0));
  cast_test_dynamic(reinterpret_cast<D*>(0x100));
  cast_test_dynamic(reinterpret_cast<B1*>(0x100));
  cast_test_dynamic(reinterpret_cast<B2*>(0x100));
  cast_test_dynamic(d);
  cast_test_dynamic(static_cast<B1*>(d));
  cast_test_dynamic(static_cast<B2*>(d));
  cast_test_dynamic(b1);
  cast_test_dynamic(b2);
  return 0;
}
```

用意した 5 種類のアドレス (0, 0x100, new D(), new B1(), new B2()) それぞれに対して、可能な dynamic_cast の全ての組み合わせを試しています。単にキャスト後のアドレスを表示するだけでなく、キャスト前との差分のバイト数を一緒に表示するための DIFF というマクロを定義しました。以下が出力例です。

```
$ ./t
P1D t = 0
     dynamic_cast<D*>(t) = 0 (diff= 0x0)
    dynamic_cast<B1*>(t) = 0 (diff= 0x0)
    dynamic_cast<B2*>(t) = 0 (diff= 0x0)
  dynamic_cast<void*>(t) = 0 (diff= 0x0)
P2B1 t = 0
     dynamic_cast<D*>(t) = 0 (diff= 0x0)
    dynamic_cast<B1*>(t) = 0 (diff= 0x0)
    dynamic_cast<B2*>(t) = 0 (diff= 0x0)
  dynamic_cast<void*>(t) = 0 (diff= 0x0)
P2B2 t = 0
     dynamic_cast<D*>(t) = 0 (diff= 0x0)
    dynamic_cast<B1*>(t) = 0 (diff= 0x0)
    dynamic_cast<B2*>(t) = 0 (diff= 0x0)
  dynamic_cast<void*>(t) = 0 (diff= 0x0)
Segmentation fault (core dumped)
```

おっと、ついにクラッシュしました。慌てず騒がず、gdb で見てみましょう。

```
Program received signal SIGSEGV, Segmentation fault.
0x0000555555555154 in cast_test_dynamic<D*> (t=0x100) at 03.cpp:38
38            << "  dynamic_cast<void*>(t) = " << DIFF(void*, t) << std::endl
   0x000055555555514b <cast_test_dynamic<D*>(D*)+19>:   48 8b 45 d8     mov    -0x28(%rbp),%rax
   0x000055555555514f <cast_test_dynamic<D*>(D*)+23>:   48 85 c0        test   %rax,%rax
   0x0000555555555152 <cast_test_dynamic<D*>(D*)+26>:   74 12   je     0x555555555166 <cast_test_dynamic<D*>(D*)+46>
=> 0x0000555555555154 <cast_test_dynamic<D*>(D*)+28>:   48 8b 10        mov    (%rax),%rdx
(..snip..)
(gdb) p/x $rax
$1 = 0x100
(gdb)
```

SIGSEGV の原因は、`mov (%rax),%rdx` 命令で、アクセス不能なアドレス 0x100 からデータを読み出そうとしたからです。0x100 という数値は、03.cpp の中で dynamic_cast に渡すために選んだ数値の一つです。本来であればオブジェクトの先頭に VTable を示すアドレスがあるはずで、そのアドレスを読み取ろうとしてる処理だと考えられます。

0x100 に対する処理を全部コメントアウトすると以下の出力が得られました。

```
$ ./t
P1D t = 0
     dynamic_cast<D*>(t) = 0 (diff= 0x0)
    dynamic_cast<B1*>(t) = 0 (diff= 0x0)
    dynamic_cast<B2*>(t) = 0 (diff= 0x0)
  dynamic_cast<void*>(t) = 0 (diff= 0x0)
P2B1 t = 0
     dynamic_cast<D*>(t) = 0 (diff= 0x0)
    dynamic_cast<B1*>(t) = 0 (diff= 0x0)
    dynamic_cast<B2*>(t) = 0 (diff= 0x0)
  dynamic_cast<void*>(t) = 0 (diff= 0x0)
P2B2 t = 0
     dynamic_cast<D*>(t) = 0 (diff= 0x0)
    dynamic_cast<B1*>(t) = 0 (diff= 0x0)
    dynamic_cast<B2*>(t) = 0 (diff= 0x0)
  dynamic_cast<void*>(t) = 0 (diff= 0x0)
P1D t = 0x55d6e4ebec20
     dynamic_cast<D*>(t) = 0x55d6e4ebec20 (diff= 0x0)
    dynamic_cast<B1*>(t) = 0x55d6e4ebec20 (diff= 0x0)
    dynamic_cast<B2*>(t) = 0x55d6e4ebec30 (diff= 0x10)
  dynamic_cast<void*>(t) = 0x55d6e4ebec20 (diff= 0x0)
P2B1 t = 0x55d6e4ebec20
     dynamic_cast<D*>(t) = 0x55d6e4ebec20 (diff= 0x0)
    dynamic_cast<B1*>(t) = 0x55d6e4ebec20 (diff= 0x0)
    dynamic_cast<B2*>(t) = 0x55d6e4ebec30 (diff= 0x10)
  dynamic_cast<void*>(t) = 0x55d6e4ebec20 (diff= 0x0)
P2B2 t = 0x55d6e4ebec30
     dynamic_cast<D*>(t) = 0x55d6e4ebec20 (diff= 0xfffffffffffffff0)
    dynamic_cast<B1*>(t) = 0x55d6e4ebec20 (diff= 0xfffffffffffffff0)
    dynamic_cast<B2*>(t) = 0x55d6e4ebec30 (diff= 0x0)
  dynamic_cast<void*>(t) = 0x55d6e4ebec20 (diff= 0xfffffffffffffff0)
P2B1 t = 0x55d6e4ebec50
     dynamic_cast<D*>(t) = 0 (diff= 0xffffaa291b1413b0)
    dynamic_cast<B1*>(t) = 0x55d6e4ebec50 (diff= 0x0)
    dynamic_cast<B2*>(t) = 0 (diff= 0xffffaa291b1413b0)
  dynamic_cast<void*>(t) = 0x55d6e4ebec50 (diff= 0x0)
P2B2 t = 0x55d6e4ebec70
     dynamic_cast<D*>(t) = 0 (diff= 0xffffaa291b141390)
    dynamic_cast<B1*>(t) = 0 (diff= 0xffffaa291b141390)
    dynamic_cast<B2*>(t) = 0x55d6e4ebec70 (diff= 0x0)
  dynamic_cast<void*>(t) = 0x55d6e4ebec70 (diff= 0x0)
```

実は 0x100 を渡してもクラッシュしない dynamic_cast のパターンが存在するので、0x100 に対するキャストを全部コメントアウトするのは悪手です。どのパターンの dynamic_cast がクラッシュするのかを細かく確認し、得られた出力を表にまとめると以下のようになりました。

| |nullptr|0x100|new D()|new B1()|new B2()|
|---|---|---|---|---|---|
|D* --> D*|&plusmn;0|&plusmn;0|&plusmn;0|N/A|N/A|
|D* --> B1*|&plusmn;0|&plusmn;0|&plusmn;0|N/A|N/A|
|D* --> B2*|&plusmn;0|+0x10|+0x10|N/A|N/A|
|D* --> void*|&plusmn;0|SIGSEGV|&plusmn;0|N/A|N/A|
|B1* --> D*|&plusmn;0|SIGSEGV|&plusmn;0|return 0|N/A|
|B1* --> B1*|&plusmn;0|&plusmn;0|&plusmn;0|&plusmn;0|N/A|
|B1* --> B2*|&plusmn;0|SIGSEGV|+0x10|return 0|N/A|
|B1* --> void*|&plusmn;0|SIGSEGV|&plusmn;0|&plusmn;0|N/A|
|B2* --> D*|&plusmn;0|SIGSEGV|-0x10|N/A|return 0|
|B2* --> B1*|&plusmn;0|SIGSEGV|-0x10|N/A|return 0|
|B2* --> B2*|&plusmn;0|&plusmn;0|&plusmn;0|N/A|&plusmn;0|
|B2* --> void*|&plusmn;0|SIGSEGV|-0x10|N/A|&plusmn;0|

B1 のインスタンスを D や B2 のポインターとして保持することはできないため、そういった無効な組み合わせは N/A として記載しています。sidecast も含め、期待通りの結果が得られたと思います。ようやく本題に移ります。

# dynamic_cast の実装

前のセクションで表にまとめたように dynamic_cast の包括的な結果は得られました。しかし明らかにしたいのは、「キャストできない (0 を返す) かどうかを判断する方法」と、「キャスト時に調整するオフセットの算出方法」です。

g++ における dynamic_cast のほとんどは、libstdc++ の中で &#95;&#95;dynamic_cast 関数として実装されているため、簡単にソースを見ることができます。

gcc/dyncast.cc at master - gcc-mirror/gcc
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/libsupc%2B%2B/dyncast.cc

ただし、演算子の dynamic_cast と &#95;&#95;dynamic_cast 関数は別物です。例えば &#95;&#95;dynamic_cast は引数を 4 つ取りますが、演算子に渡すのはポインター 1 つだけです。残りの 3 つはどこから来るのでしょうか。

キャスト演算子と関数の関係を知るには、アセンブリを見るのが一番簡単です。

## dynamic_cast のコンパイル結果

デバッグ用途では 03.cpp は長いので、簡略化したコードを 04.cpp を用意しました。

```C++:04.cpp
class B1 {
public:
  void f0() {}
  virtual void f1() {}
  int int_in_b1;
};

class B2 {
public:
  virtual void f2() {}
  int int_in_b2;
};

class D : public B1, public B2 {
public:
  void d() {}
  void f2() {}  // override B2::f2()
  int int_in_d;
};

template <class T>
int check_type(T t) {
  int n = 0;
  if (dynamic_cast<D*>(t)) n |= 1;
  if (dynamic_cast<B1*>(t)) n |= 2;
  if (dynamic_cast<B2*>(t)) n |= 4;
  if (dynamic_cast<void*>(t)) n |= 8;
  return n;
}

int main() {
  D  *d  = new D();
  B1 *b1 = new B1();
  B2 *b2 = new B2();
  check_type(d);
  check_type(b1);
  check_type(b2);
  return 0;
}
```

実行結果は出力しませんが、デバッグして結果を確かめると check_type からの戻り値は順番に 15, 10, 12 となります。

04.cpp をコンパイルすると、テンプレートから 3 つの関数が生成されます。相変わらず -O0 オプションで最適化を無効にしていますが、T が D のときと B1/B2 のときとではロジックが大幅に異なります。それぞれ順番に見ていきましょう。

まず check_type&lt;D*&gt;(D*) です。見やすくなるように、空行と注釈を入れました。

```
(gdb) disas check_type<D*>
Dump of assembler code for function check_type<D*>(D*):
   0x0000000000000cfe <+0>:     push   %rbp
   0x0000000000000cff <+1>:     mov    %rsp,%rbp
   0x0000000000000d02 <+4>:     mov    %rdi,-0x18(%rbp)
   0x0000000000000d06 <+8>:     movl   $0x0,-0x4(%rbp)

   0x0000000000000d0d <+15>:    cmpq   $0x0,-0x18(%rbp)
   0x0000000000000d12 <+20>:    je     0xd18 <check_type<D*>(D*)+26>
   0x0000000000000d14 <+22>:    orl    $0x1,-0x4(%rbp)  ; if t != nullptr

   0x0000000000000d18 <+26>:    cmpq   $0x0,-0x18(%rbp)
   0x0000000000000d1d <+31>:    je     0xd23 <check_type<D*>(D*)+37>
   0x0000000000000d1f <+33>:    orl    $0x2,-0x4(%rbp)  ; if t != nullptr

   0x0000000000000d23 <+37>:    cmpq   $0x0,-0x18(%rbp)
   0x0000000000000d28 <+42>:    je     0xd3b <check_type<D*>(D*)+61>
   0x0000000000000d2a <+44>:    mov    -0x18(%rbp),%rax
   0x0000000000000d2e <+48>:    add    $0x10,%rax
   0x0000000000000d32 <+52>:    test   %rax,%rax
   0x0000000000000d35 <+55>:    je     0xd3b <check_type<D*>(D*)+61>
   0x0000000000000d37 <+57>:    orl    $0x4,-0x4(%rbp)  ; if t != nullptr && t + 0x10 != nullptr

   0x0000000000000d3b <+61>:    mov    -0x18(%rbp),%rax; rax = t
   0x0000000000000d3f <+65>:    test   %rax,%rax
   0x0000000000000d42 <+68>:    je     0xd5d <check_type<D*>(D*)+95>
   0x0000000000000d44 <+70>:    mov    (%rax),%rdx  ; rdx = vtable
   0x0000000000000d47 <+73>:    sub    $0x10,%rdx   ; rdx = vtable - 0x10
   0x0000000000000d4b <+77>:    mov    (%rdx),%rdx  ; rdx = *(vtable - 0x10) = offset_to_top
   0x0000000000000d4e <+80>:    add    %rdx,%rax    ; rax = t + offset_to_top = dynamic_cast<void*>(t)
   0x0000000000000d51 <+83>:    test   %rax,%rax
   0x0000000000000d54 <+86>:    je     0xd5d <check_type<D*>(D*)+95>
   0x0000000000000d56 <+88>:    mov    $0x1,%eax
   0x0000000000000d5b <+93>:    jmp    0xd62 <check_type<D*>(D*)+100>
   0x0000000000000d5d <+95>:    mov    $0x0,%eax
   0x0000000000000d62 <+100>:   test   %al,%al      ; al = boolify(dynamic_cast<void*>(t))
   0x0000000000000d64 <+102>:   je     0xd6a <check_type<D*>(D*)+108>
   0x0000000000000d66 <+104>:   orl    $0x8,-0x4(%rbp)
   0x0000000000000d6a <+108>:   mov    -0x4(%rbp),%eax
   0x0000000000000d6d <+111>:   pop    %rbp
   0x0000000000000d6e <+112>:   retq
End of assembler dump.
```

全体を見て気が付く点は、&#95;&#95;dynamic_cast のような外部関数を呼び出す命令が見つからないことです。最初の 2 つの orl 命令が実行される条件を見ると、「t が 0 ではないとき」だけです。3 番目の orl 命令 の実行条件は、「t が 0 ではなく、かつ、<+48> の add 命令で t に +0x10 を足した結果が 0 ではないとき」です。

これらの動作は D のオブジェクト内の 3 種類のオフセット (B1/D = +0, B2 = +0x10) を思い出すと分かりますが、静的キャストです。最初の 2 つの dynamic_cast は D* --> D* と D* --> B1* で、ともにポインターの調整が必要ないため、t の値がそのまま dynamic_cast の戻り値として check_type の if 文で使われています。3 つ目の D* --> B2* の変換では、アドレスを +0x10 することがコンパイル時に分かっているため、static_cast と同じく VTable なしで t+0x10 を計算した結果が dynamic_cast の戻り値となり、if 文で使われています。

最後の `dynamic_cast<void*>(t)` でようやく動的キャストが行われている様子を確認することができます。ほとんど注釈として書いてしまいましたが、ここでポイントになるのが offset_to_top という値です。

offset_to_top については前回の記事でも触れましたが、もう一度軽く説明しておきます。g++ が出力した VTable の内部構造は次のようになっていました。

```
Vtable for D
D::_ZTV1D: 7u entries
0     (int (*)(...))0
8     (int (*)(...))(& _ZTI1D)
16    (int (*)(...))B1::f1
24    (int (*)(...))D::f2
32    (int (*)(...))-16
40    (int (*)(...))(& _ZTI1D)
48    (int (*)(...))D::_ZThn16_N1D2f2Ev
```

実際にクラス オブジェクト内に格納されているのは、VTable の先頭ではなく、メンバー関数のアドレスが入っている +16 や +48 のアドレスでした。その上流にある &#95;ZTI1D というのは、RTTI とも呼ばれる型情報です。さらにその上流の +0 と +32 にある謎の数値は、オブジェクトの先頭へのオフセットを示す offset_to_top という値らしい、ということが ABI で説明されていました。実は、前回 ABI から引用した箇所に "This is necessary for dynamic_cast&lt;void*&gt; in particular." という記載があり、その適用例がまさに今回の `dynamic_cast<void*>(t)` です。

check_type&lt;D*&gt; のアセンブリに戻ると、<+77> で offset_to_top を取り出した後、<+80> の add 命令で offset_to_top を 元の t に加算しています。これでオブジェクトの先頭アドレスが計算でき、その結果が dynamic_cast の戻り値です。

一旦まとめます。

* D* --> B1* の upcast は静的キャストである
* dynamic_cast&lt;void*&gt; では offset_to_top が使われる

ところで、逆方向の B1* --> D* の downcast を静的キャストで済ませることはできるでしょうか。もちろん駄目ですね。なぜなら B1* が D ではなく本当に B1 のインスタンスを指しているときは D* へ変換すべきではないからです。そこを static_cast は気にせずやっちゃう単純な子で、対する dynamic_cast は少しアタマが良いから downcast も安全に変換できるよえっへん、というのが dynamic_cast の存在意義です。

キャスト前のポインターがそもそも間違っているという想定外の状況を除けば、upcast は必ず静的に処理できます。そもそも upcast で dynamic_cast という演算子を使うこと自体が無駄ですが、仮に使った場合でもコンパイル時に静的キャストで間に合うため、実行時の動作である &#95;&#95;dynamic_cast 関数は呼ばれずに済みます。

次に check_type&lt;B1*&gt;(B1*) のアセンブリと注釈を示します。

```
(gdb) disas check_type<B1*>
Dump of assembler code for function check_type<B1*>(B1*):
   0x0000000000000d6f <+0>:     push   %rbp
   0x0000000000000d70 <+1>:     mov    %rsp,%rbp
   0x0000000000000d73 <+4>:     sub    $0x20,%rsp
   0x0000000000000d77 <+8>:     mov    %rdi,-0x18(%rbp)
   0x0000000000000d7b <+12>:    movl   $0x0,-0x4(%rbp)

   0x0000000000000d82 <+19>:    mov    -0x18(%rbp),%rax
   0x0000000000000d86 <+23>:    test   %rax,%rax
   0x0000000000000d89 <+26>:    je     0xdb2 <check_type<B1*>(B1*)+67>
   0x0000000000000d8b <+28>:    mov    $0x0,%ecx                                ; src2dst = 0
   0x0000000000000d90 <+33>:    lea    0x200fd1(%rip),%rdx # 0x201d68 <_ZTI1D>  ; dst_type
   0x0000000000000d97 <+40>:    lea    0x201012(%rip),%rsi # 0x201db0 <_ZTI2B1> ; src_type
   0x0000000000000d9e <+47>:    mov    %rax,%rdi
   0x0000000000000da1 <+50>:    callq  0x918
   0x0000000000000da6 <+55>:    test   %rax,%rax
   0x0000000000000da9 <+58>:    je     0xdb2 <check_type<B1*>(B1*)+67>
   0x0000000000000dab <+60>:    mov    $0x1,%eax
   0x0000000000000db0 <+65>:    jmp    0xdb7 <check_type<B1*>(B1*)+72>
   0x0000000000000db2 <+67>:    mov    $0x0,%eax
   0x0000000000000db7 <+72>:    test   %al,%al
   0x0000000000000db9 <+74>:    je     0xdbf <check_type<B1*>(B1*)+80>
   0x0000000000000dbb <+76>:    orl    $0x1,-0x4(%rbp)

   0x0000000000000dbf <+80>:    cmpq   $0x0,-0x18(%rbp)
   0x0000000000000dc4 <+85>:    je     0xdca <check_type<B1*>(B1*)+91>
   0x0000000000000dc6 <+87>:    orl    $0x2,-0x4(%rbp)  ; if t != nullptr

   0x0000000000000dca <+91>:    mov    -0x18(%rbp),%rax
   0x0000000000000dce <+95>:    test   %rax,%rax
   0x0000000000000dd1 <+98>:    je     0xdfc <check_type<B1*>(B1*)+141>
   0x0000000000000dd3 <+100>:   mov    $0xfffffffffffffffe,%rcx                 ; src2dst = -2
   0x0000000000000dda <+107>:   lea    0x200fbf(%rip),%rdx # 0x201da0 <_ZTI2B2>
   0x0000000000000de1 <+114>:   lea    0x200fc8(%rip),%rsi # 0x201db0 <_ZTI2B1>
   0x0000000000000de8 <+121>:   mov    %rax,%rdi
   0x0000000000000deb <+124>:   callq  0x918
   0x0000000000000df0 <+129>:   test   %rax,%rax
   0x0000000000000df3 <+132>:   je     0xdfc <check_type<B1*>(B1*)+141>
   0x0000000000000df5 <+134>:   mov    $0x1,%eax
   0x0000000000000dfa <+139>:   jmp    0xe01 <check_type<B1*>(B1*)+146>

   0x0000000000000dfc <+141>:   mov    $0x0,%eax
   0x0000000000000e01 <+146>:   test   %al,%al
   0x0000000000000e03 <+148>:   je     0xe09 <check_type<B1*>(B1*)+154>
   0x0000000000000e05 <+150>:   orl    $0x4,-0x4(%rbp)
   0x0000000000000e09 <+154>:   mov    -0x18(%rbp),%rax
   0x0000000000000e0d <+158>:   test   %rax,%rax
   0x0000000000000e10 <+161>:   je     0xe2b <check_type<B1*>(B1*)+188>
   0x0000000000000e12 <+163>:   mov    (%rax),%rdx
   0x0000000000000e15 <+166>:   sub    $0x10,%rdx
   0x0000000000000e19 <+170>:   mov    (%rdx),%rdx  ; rdx = offset_to_top
   0x0000000000000e1c <+173>:   add    %rdx,%rax    ; rax = dynamic_cast<void*>(t)
   0x0000000000000e1f <+176>:   test   %rax,%rax
   0x0000000000000e22 <+179>:   je     0xe2b <check_type<B1*>(B1*)+188>
   0x0000000000000e24 <+181>:   mov    $0x1,%eax
   0x0000000000000e29 <+186>:   jmp    0xe30 <check_type<B1*>(B1*)+193>
   0x0000000000000e2b <+188>:   mov    $0x0,%eax
   0x0000000000000e30 <+193>:   test   %al,%al
   0x0000000000000e32 <+195>:   je     0xe38 <check_type<B1*>(B1*)+201>
   0x0000000000000e34 <+197>:   orl    $0x8,-0x4(%rbp)
   0x0000000000000e38 <+201>:   mov    -0x4(%rbp),%eax
   0x0000000000000e3b <+204>:   leaveq
   0x0000000000000e3c <+205>:   retq
End of assembler dump.
```

すぐに分かるのは、B1* --> B1* の dynamic_cast では何も変換が行われないことです。型が同じなので、ある意味当然です。check_type&lt;D*&gt; と同じく、B1* --> void* の変換で offset_to_top が使われていることもすぐに分かります。

B1* --> D* と B1* --> B2* のキャストにおいて call 命令が出てきました。パラメーターを 4 つ渡しているように見えるので、これが &#95;&#95;dynamic_cast の呼び出しとみて間違いなさそうです。第一引数の src_ptr 以外はどこから来るのかという先の疑問ですが、コンパイラーがコンパイル時に静的に決めるようです。

check_type&lt;B2*&gt; のアセンブリも check_type&lt;B1*&gt; とほぼ同じで、&#95;&#95;dynamic_cast へのパラメーターが異なるだけです。04.cpp から得られた全てのパターンでの引数をまとめました。

| |src_type|dst_type|src2dst|
|---|---|---|---|
|downcast: B1* --> D*:|_ZTI2B1|_ZTI1D|0|
|sidecast: B1* --> B2*:|_ZTI2B1|_ZTI2B2|-2|
|downcast: B2* --> D*:|_ZTI2B2|_ZTI1D|0x10|
|sidecast: B2* --> B1*:|_ZTI2B2|_ZTI2B1|-2|

上記パラメーターを渡して &#95;&#95;dynamic_cast 呼び出した後は簡単で、関数からの戻り値がそのまま dynamic_cast 演算子の戻り値になります。次に、表中のパラメーターの意味を見てみます。

## 関数 &#95;&#95;dynamic_cast のパラメーターの意味

第一引数の src_ptr には疑問の余地もありません。型情報である src_type と dst_type についても、まあ要るかもしれないね、ぐらいに考えていました。が、見落としがちなポイントがあるので書いておきます。例えば上で出てきた B1* --> D* の downcast、すなわち dynamic_cast&lt;D*&gt;(B1*) を考えましょう。表にもまとめたように、src_type には &#95;ZTI2B1 へのポインターが渡されます。当然です。

特に疑問を感じるところではないかもしれませんが、src_type の代わりに、src_ptr の VTable に入っている型情報を使っては駄目なのでしょうか。これももちろん駄目です。というのは、1 つの VTable が複数個の型情報を持っていたとしても、その型情報は全て同じ型を示すものだからです。

以下に D の内部構造のダンプを再掲します。+40 に入っている情報が _ZTI2B2 ではなく_ZTI1D になっていることに注目して下さい。

```
Vtable for D
D::_ZTV1D: 7u entries
0     (int (*)(...))0
8     (int (*)(...))(& _ZTI1D)
16    (int (*)(...))B1::f1
24    (int (*)(...))D::f2
32    (int (*)(...))-16
40    (int (*)(...))(& _ZTI1D)
48    (int (*)(...))D::_ZThn16_N1D2f2Ev
```

dynamic_cast&lt;D*&gt;(B1*) を呼ぶコードがあったとき、コンパイラーの能力をもってすれば、テンプレート引数の D* という型と、パラメーターの型情報である B1* という型は分かるので、その型に対応する型情報へのアドレスをアセンブリの中でハードコードすることができます。これが src_type と dst_type として &#95;&#95;dynamic_cast に渡されます。しかし src_type はあくまでも見かけの型情報で、本来のオブジェクトの型 (= most derived class) が何であるかという情報については、コンパイラーがどう頑張ってもコンパイル時に静的に得ることはできません。その不足を補う情報が、src_ptr の VTable から辿ることができる型情報です。&#95;&#95;dynamic_cast は、src_ptr と src_type というパラメーター経由で、本来の型と見かけの型の両方の情報を扱うことができるようになります。

残る src2dst については、コメントが微妙なため理解するのに苦労しました。コメントの解釈と併せて説明します。

最初に "a static hint about the location of the source subobject with respect to the complete object" という説明があります。(D のインスタンスを B* として見たときの B* のことを subobject と呼ぶようです。Polymorphic objects に続いて便利な用語なので今後はこの用語を使います。)

ここで引用したコメントには destination という記載がないため、そのままの意味だと src_ptr の offset_top と混同しかねません。さらに src2dst という名前も微妙で、これを src --> dst という方向で考えてそのオフセットだと解釈すると、"the location of the destination subobject with respect to the source subobject" となりますが、これも間違いです。

コメントを読み進めると、src2dst が -1, -2, -3 のときには特別な意味があると書かれています。

* -1: no hint
* -2: src is not a public base of dst
* -3: src is a multiple public base type but never a virtual base type

-2 は src が dst の public 基底クラスではない場合。sidecast や、全く無関係の場合はこれになります。-3 は src が (dst の) 複数の public 基底クラスで、かつ仮想基底クラスではない場合、つまり仮想継承を使わずに菱形継承している場合です。

その後の "otherwise" で始まる文で、ようやく一般的な意味が明かされます。強調するため日本語に訳すと、「src は dst の単一継承における基底クラスであり、そのオフセットが dst の起点から src2dst の位置にある」という意味になります。後半が気になっていた疑問への答えで、src2dst は dst から src へのオフセットということです。"the location of SRC with respect TO DST" の略のつもりかもしれませんが、私の感覚ではこれは dst2src と呼びたいものです。実際に前セクションの表を見ると、downcast: B2* --> D* のときに src2dst が 0x10 が渡されています。

最後にもう一点、upcast のときに &#95;&#95;dynamic_cast は呼ばれないため、src2dst が負のオフセットを持つことはありません。これは多重継承の場合でも同様です。もし src2dst が負のオフセットを持つような型の組み合わせの場合、src_ptr にその負のオフセットを加えて返してしまえばよいのです。なぜなら、多重継承であろうが何だろうが src_ptr の上流のその位置に subobject があることが保証されるからです。

dynamic_cast を用いるの一つの利点は、要求された downcast または sidecast が可能かどうかを判別できることです。コンパイラーは、dst の subobject が src の下流にあると仮定したときのオフセットは知っています。しかし上流にある時と違って、オブジェクトがそこまで続いているかどうかが分かりません。多重継承によって継承関係のルートが複数考えられる場合、そして public 継承と private 継承、仮想継承が入り乱れている場合にも、コンパイルが終わってみないと sidecast 可能なルートがあるかどうかが分かりません。これらの判別ロジックが &#95;&#95;dynamic_cast に隠されています。

## &#95;&#95;dynamic_cast の実装

ようやく &#95;&#95;dynamic_cast の実装を見る準備が整いました。関数の前半部分は、これまでの記事で書いてきた VTable の構造を把握していると簡単に理解することができるので、ぜひ見てほしいところです。

```C++
extern "C" void *
__dynamic_cast (const void *src_ptr,    // object started from
                const __class_type_info *src_type, // type of the starting object
                const __class_type_info *dst_type, // desired target type
                ptrdiff_t src2dst) // how src and dst are related
  {
  const void *vtable = *static_cast <const void *const *> (src_ptr);
  const vtable_prefix *prefix =
      adjust_pointer <vtable_prefix> (vtable,
              -offsetof (vtable_prefix, origin));
  const void *whole_ptr =
      adjust_pointer <void> (src_ptr, prefix->whole_object);
  const __class_type_info *whole_type = prefix->whole_type;
  __class_type_info::__dyncast_result result;

  // If the whole object vptr doesn't refer to the whole object type, we're
  // in the middle of constructing a primary base, and src is a separate
  // base.  This has undefined behavior and we can't find anything outside
  // of the base we're actually constructing, so fail now rather than
  // segfault later trying to use a vbase offset that doesn't exist.
  const void *whole_vtable = *static_cast <const void *const *> (whole_ptr);
  const vtable_prefix *whole_prefix =
    adjust_pointer <vtable_prefix> (whole_vtable,
            -offsetof (vtable_prefix, origin));
...
```

src_ptr を基にいくつかのローカル変数を初期化しています。どれも馴染みのある値です。

* **vtable** = VTable へのアドレス。src_ptr を deref したもの。メンバー関数のアドレスが入っている VTable の途中のアドレス。
* **vtable_prefix** = subobject の VTable の先頭アドレス。上記変数 vtable から型情報と offset_to_top のスペース分だけ遡ったもの。
* **whole_ptr** = src_ptr の most derived class のアドレス。src_ptr に offset_to_top バイトを加えた値。
* **whole_type** = most derived class の VTable に入っている型情報。
* **whole_vtable** = whole_ptr の VTable の途中のアドレス。
* **vtable_prefix** = whole_ptr の VTable の先頭アドレス。

この後 `whole_type->__do_dyncast` という関数呼び出しがあり、基本的にはその戻り値の中身をもとに結果を決めているだけです。&#95;&#95;do_dyncast から返ってくる &#95;&#95;class_type_info::&#95;&#95;dyncast_result 構造体のメンバーは以下の通りです。

```C++
struct __class_type_info::__dyncast_result
{
  const void *dst_ptr;        // pointer to target object or NULL
  __sub_kind whole2dst;       // path from most derived object to target
  __sub_kind whole2src;       // path from most derived object to sub object
  __sub_kind dst2src;         // path from target to sub object
  int whole_details;          // details of the whole class hierarchy
...
```

result のメンバーの意味も含めて、次のような図で考えると分かりやすいです。ローカル変数の名前に出てくるように、whole は src の most derived class です。

![three_classes.PNG](https://qiita-image-store.s3.amazonaws.com/0/165275/a364c793-bd70-dd18-adff-76eb9a649447.png)

src、dst、whole という 3 つのクラス型があり、&#95;&#95;do_dyncast の実行によって 2 クラス間の継承関係それぞれについての属性が得られます。図中の黒矢印に public や virtual といったラベルが付くイメージです。&#95;&#95;dynamic_cast はそのラベルをもとに戻り値を決めます。&#95;&#95;dynamic_cast が最終的に非 NULL の値を返すとき、すなわち dynamic_cast が成功するのは以下 3 つの場合に限られます。

* dst2src の継承関係が public<br /> &rarr; 有効な downcast。dynamic_cast 成功。
* dst と src は直接の継承関係にないが、whole2src、whole2dst がともに public<br /> &rarr; 有効な crosscast。dynamic_cast 成功。
* whole2src が public でない仮想継承で、dst2src が unknown<br /> &rarr; whole は使わずに dst と src の関係を洗い直し。

3 つ目の条件は正直よく分かっていません。仮想継承が絡んでくるので次回真面目に考えようと思いますが、分かる範囲では次のように理解しています。

`whole_type->__do_dyncast` は基本的に whole から dst へ継承関係を辿りながら属性を決定する処理です。もし whole から dst へ public な継承関係がない場合でも、代わりに dst から src に public な継承関係がある場合にはキャストできて然るべき、というのがこの条件だと思います。&#95;&#95;do_dyncast の実装をまだすべて理解していませんが、whole から dst へ辿るだけでは、dst と src との関係を調べたことにはならないため、&#95;&#95;do_find_public_src を使って改めて dst から src への探索を行なう必要があるのでしょう。

以上で dynamic_cast そのものの実装の確認は終わりです。&#95;&#95;do_dyncast の主な作業は、3 つの継承関係の属性を導出することだと分かりました。今度は型情報の構造を理解する必要があります。_ZTI1D や _ZTI2B2 の正体を解き明かさないといけません。

## C++ の型情報と &#95;&#95;do_dyncast の実装

前回の記事の一部が微妙に伏線になるのですが、&#95;ZTI2B2 の先頭のアドレスをダンプしたときに `<_ZTVN10__cxxabiv117__class_type_infoE+16>` というシンボルに解決されるアドレスが入っており、そのシンボルが型情報らしき名前のクラスの VTable になっていることから、&#95;ZTI2B2 は型情報であろうと推測しました。当時は知らなかったのですが、libstdc++ のコードを見て正体が分かりました。

結論から言うと、g++ はクラスの継承関係をグラフ構造として表現しており、そのノードが &#95;ZTI2B2 などのオブジェクトです。クラスの場合、ノードの型は以下の 3 種類です。型情報クラスの継承関係も分かるように書きました。

* &#95;&#95;cxxabiv1::&#95;&#95;class_type_info : public std::type_info
* &#95;&#95;cxxabiv1::&#95;&#95;si_class_type_info : public &#95;&#95;cxxabiv1::&#95;&#95;class_type_info
* &#95;&#95;cxxabiv1::&#95;&#95;vmi_class_type_info : public &#95;&#95;cxxabiv1::&#95;&#95;class_type_info

&#95;&#95;class_type_info は継承関係を持たないクラス、&#95;&#95;si_class_type_info は単一継承するクラス、&#95;&#95;vmi_class_type_info は多重継承、もしくは仮想継承しているクラスを表します。クラス名の頭にある si は single inheritance、vmi は virtual or multiple inheritance の略でしょう。

定義を確認すると、&#95;&#95;si_class_type_info は基底クラス型へのポインターを 1 つ、&#95;&#95;vmi_class_type_info は基底クラス型へのポインターの配列を保持しています。基底クラス型には、そのクラスの subobject の位置と基底クラスの種類 (public, virtual) が保存されています。

試しに &#95;ZTI1D、&#95;ZTI2B2、&#95;ZTI2B1 の関係を gdb で見てみましょう、&#95;&#95;offset_flags は継承の種類とオフセットの情報を両方含んでいます。

```
(gdb) x/2xg &_ZTI1D
0x555555755d80 <_ZTI1D>:        0x00007ffff7dca5d8      0x0000555555554d74
(gdb) x/2xg 0x00007ffff7dca5d8
0x7ffff7dca5d8 <_ZTVN10__cxxabiv121__vmi_class_type_infoE+16>:  0x00007ffff7ae0920      0x00007ffff7ae0940

(gdb) p *(__cxxabiv1::__vmi_class_type_info*)0x555555755d80
$2 = {
  <__cxxabiv1::__class_type_info> = {
    <std::type_info> = {
      _vptr.type_info = 0x7ffff7dca5d8 <vtable for __cxxabiv1::__vmi_class_type_info+16>,
      __name = 0x555555554d74 <typeinfo name for D> "1D"
    }, <No data fields>},
  members of __cxxabiv1::__vmi_class_type_info:
  __flags = 0,
  __base_count = 2,
  __base_info = {{
      __base_type = 0x555555755dc8 <typeinfo for B1>,
      __offset_flags = 2
    }}

(gdb) p (*(__cxxabiv1::__vmi_class_type_info*)0x555555755d80)->__base_info[0]
$4 = {
  __base_type = 0x555555755dc8 <typeinfo for B1>,
  __offset_flags = 2     <---- __public_mask(2) | offset:0x00
}
(gdb) p (*(__cxxabiv1::__vmi_class_type_info*)0x555555755d80)->__base_info[1]
$5 = {
  __base_type = 0x555555755db8 <typeinfo for B2>,
  __offset_flags = 4098  <---- __public_mask(2) | offset:0x10
}

(gdb) x/2xg 0x555555755dc8
0x555555755dc8 <_ZTI2B1>:       0x00007ffff7dc98d8      0x0000555555554d7b
(gdb) x/2xg 0x00007ffff7dc98d8
0x7ffff7dc98d8 <_ZTVN10__cxxabiv117__class_type_infoE+16>:      0x00007ffff7add930      0x00007ffff7add950

(gdb) x/2xg 0x555555755db8
0x555555755db8 <_ZTI2B2>:       0x00007ffff7dc98d8      0x0000555555554d77
(gdb) x/2xg 0x00007ffff7dc98d8
0x7ffff7dc98d8 <_ZTVN10__cxxabiv117__class_type_infoE+16>:      0x00007ffff7add930      0x00007ffff7add950

(gdb) p *(__cxxabiv1::__class_type_info*)0x555555755dc8
$6 = {
  <std::type_info> = {
    _vptr.type_info = 0x7ffff7dc98d8 <vtable for __cxxabiv1::__class_type_info+16>,
    __name = 0x555555554d7b <typeinfo name for B1> "2B1"
  }, <No data fields>}

(gdb) p *(__cxxabiv1::__class_type_info*)0x555555755db8
$7 = {
  <std::type_info> = {
    _vptr.type_info = 0x7ffff7dc98d8 <vtable for __cxxabiv1::__class_type_info+16>,
    __name = 0x555555554d77 <typeinfo name for B2> "2B2"
  }, <No data fields>}
```

&#95;ZTI1D は &#95;&#95;vmi_class_type_info のインスタンスで、基底クラスの配列は `{&_ZTI2B1, &_ZTI2B2}` となっていることが確認できます。

コードに戻り、基底クラスを持つクラスの &#95;&#95;do_dyncast を見ると、基底クラスの &#95;&#95;do_dyncast を再帰的に呼び出している箇所があります。&#95;&#95;dynamic_cast から `whole_type->__do_dyncast` を呼ぶと、キャスト元の most derived class の型情報から基底クラスを辿りながらキャスト先のクラス dst_type を見つける探索が始まるのです。

単一継承のみの場合の downcast は簡単です。&#95;&#95;do_dyncast を呼ぶ前に既に src の most derived クラスへのポインターを得ているため、残る作業は dst_type が見つかるまで基底クラスを順に辿ることだけで、もし dst_type が見つかればそこで downcast 成功です。このとき dst_ptr には obj_ptr をそのままセットしていることから、単一継承の場合には subobject のオフセットは常に 0 になることが分かります。

問題は多重継承と仮想継承が含まれる場合です。&#95;&#95;vmi_class_type_info::&#95;&#95;do_dyncast のリーディング コメントで心が折られそうになります。

> This is a big hairy function. Although the run-time behaviour of dynamic_cast is simple to describe, it gives rise to some non-obvious behaviour.

確かに想像以上に関数が複雑ですが、基本的な方針は dst_type を探すグラフの探索です。&#95;&#95;vmi_class_type_info::&#95;&#95;do_dyncast には、大きな for ループが一つあって基底クラスの配列の要素を列挙しているようなので、単純には深さ優先探索を使っていると言えます。

それに加えて効率よく探索するための工夫がなされており、その一つが上の方で意味を散々考えた src2dst の利用です。src2dst が非負のとき、その数値は dst から見た src の型のオフセットを示しています。この値を使うと、基底クラスの配列の要素をループするときにある程度の枝刈りが可能になります。とある subobject が VTable 上の +x にあったとして、もし src2dst の値が x より小さいのであれば、その subobject には目的の型が存在しないことが分かるのでスキップできるのです。そのロジックが for ループ内の最初にあります。

残りの &#95;&#95;do_dyncast の詳細はまだ読み込んでいないので省きますが、目的は単一継承のときと変わらず、dst の型を見つけて whole2dst をセットすることです。条件によっては whole2dst に加えて dst2src もセットしています。これは &#95;&#95;do_dyncast で確認した三つ目の条件を考慮してのことだと思います。

中途半端なところですが、dynamic_cast の仕組みと、キャストが可能な理由については大体わかったので、一旦まとめます。

* 型情報はグラフ構造で表現される
* 派生クラスが基本クラスの型をメンバーとして保持している
* &#95;&#95;do_dyncast と &#95;&#95;do_find_public_src はグラフ探索 (多重継承の場合は深さ優先)
* キャスト元のオブジェクトの most derived クラスから基底クラスに向かって探索し、キャスト先のクラスが見つかれば downcast 成功
* most derived から辿って目標が見つからない場合、今度はキャスト先のクラスからキャスト元に向かって探索

その他の考慮事項として、コンストラクター内で dynamic_cast が使われた場合の挙動があります。この場合、subobject の構造が未完成になる (VTable が入っていないなど) ので、出来る限りクラッシュを引き起こさないようなエラー判定が実装されています。

## dynamic_cast と文字列比較

dynamic_cast はグラフ探索を行っていることが分かりました。最後に、探索でノードを訪れたときの作業を見てみましょう。

例えば &#95;&#95;si_class_type_info::&#95;&#95;do_dyncast の冒頭で `*this == *dst_type` の比較を実行しています。この比較演算子を実装しているのは std::type_info で、STL のヘッダーにテンプレートとして実装されています。

gcc/typeinfo at master - gcc-mirror/gcc
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/libsupc%2B%2B/typeinfo

```C++
// Determine whether typeinfo names for the same type are merged (in which
// case comparison can just compare pointers) or not (in which case strings
// must be compared), and whether comparison is to be implemented inline or
// not.  We used to do inline pointer comparison by default if weak symbols
// are available, but even with weak symbols sometimes names are not merged
// when objects are loaded with RTLD_LOCAL, so now we always use strcmp by
// default.  For ABI compatibility, we do the strcmp inline if weak symbols
// are available, and out-of-line if not.  Out-of-line pointer comparison
// is used where the object files are to be portable to multiple systems,
// some of which may not be able to use pointer comparison, but the
// particular system for which libstdc++ is being built can use pointer
// comparison; in particular for most ARM EABI systems, where the ABI
// specifies out-of-line comparison.  The compiler's target configuration
// can override the defaults by defining __GXX_TYPEINFO_EQUALITY_INLINE to
// 1 or 0 to indicate whether or not comparison is inline, and
// __GXX_MERGED_TYPEINFO_NAMES to 1 or 0 to indicate whether or not pointer
// comparison can be used.

#ifndef __GXX_MERGED_TYPEINFO_NAMES
// By default, typeinfo names are not merged.
#define __GXX_MERGED_TYPEINFO_NAMES 0
#endif

// By default follow the old inline rules to avoid ABI changes.
#ifndef __GXX_TYPEINFO_EQUALITY_INLINE
  #if !__GXX_WEAK__
    #define __GXX_TYPEINFO_EQUALITY_INLINE 0
  #else
    #define __GXX_TYPEINFO_EQUALITY_INLINE 1
  #endif
#endif

(..snip..)

#if !__GXX_TYPEINFO_EQUALITY_INLINE
    // In old abi, or when weak symbols are not supported, there can
    // be multiple instances of a type_info object for one
    // type. Uniqueness must use the _name value, not object address.
    bool operator==(const type_info& __arg) const _GLIBCXX_NOEXCEPT;
#else
  #if !__GXX_MERGED_TYPEINFO_NAMES
    /** Returns true if @c *this precedes @c __arg in the implementation's
     *  collation order.  */
    // Even with the new abi, on systems that support dlopen
    // we can run into cases where type_info names aren't merged,
    // so we still need to do string comparison.
    bool operator==(const type_info& __arg) const _GLIBCXX_NOEXCEPT
    {
      return ((__name == __arg.__name)
	      || (__name[0] != '*' &&
		  __builtin_strcmp (__name, __arg.__name) == 0));
    }
  #else
    // On some targets we can rely on type_info's NTBS being unique,
    // and therefore address comparisons are sufficient.
    bool operator==(const type_info& __arg) const _GLIBCXX_NOEXCEPT
    { return __name == __arg.__name; }
  #endif
#endif
```

宣言のみのときの定義は tinfo.cc にあります。

gcc/tinfo.cc at master - gcc-mirror/gcc
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/libsupc%2B%2B/tinfo.cc

```C++
#if !__GXX_TYPEINFO_EQUALITY_INLINE

// We can't rely on common symbols being shared between shared objects.
bool std::type_info::
operator== (const std::type_info& arg) const _GLIBCXX_NOEXCEPT
{
#if __GXX_MERGED_TYPEINFO_NAMES
  return name () == arg.name ();
#else
  /* The name() method will strip any leading '*' prefix. Therefore
     take care to look at __name rather than name() when looking for
     the "pointer" prefix.  */
  return (&arg == this)
    || (__name[0] != '*' && (__builtin_strcmp (name (), arg.name ()) == 0));
#endif
}

#endif
```

&#95;&#95;GXX_TYPEINFO_EQUALITY_INLINE と &#95;&#95;GXX_MERGED_TYPEINFO_NAMES という 2 つのラベルの組み合わせによって 4 種類の実装が存在していることになります。

* __GXX_TYPEINFO_EQUALITY_INLINE == TRUE  and __GXX_MERGED_TYPEINFO_NAMES == FALSE<br /> &rarr; まずクラス名の文字列のアドレスを比較。次に左辺のクラス名の先頭が * であるかどうかを確認。そのあと文字列比較。
* __GXX_TYPEINFO_EQUALITY_INLINE == TRUE  and __GXX_MERGED_TYPEINFO_NAMES == TRUE<br /> &rarr; クラス名の文字列アドレスの比較のみ。
* __GXX_TYPEINFO_EQUALITY_INLINE == FALSE and __GXX_MERGED_TYPEINFO_NAMES == TRUE<br /> &rarr; 先頭が * だった場合はスキップして、クラス名の文字列アドレスの比較。
* __GXX_TYPEINFO_EQUALITY_INLINE == FALSE and __GXX_MERGED_TYPEINFO_NAMES == FALSE<br /> &rarr; まず型情報インスタンスのアドレスを比較。次に左辺のクラス名の先頭が * であるかどうかを確認。そのあと文字列比較。

&#95;&#95;GXX_TYPEINFO_EQUALITY_INLINE は、インスタンスのアドレスを比較するか、文字列のアドレスを比較するかの違いで、__GXX_MERGED_TYPEINFO_NAMES は、strcmp による文字列比較を行なうかどうかの違いです。

&#95;&#95;class_type_info::&#95;&#95;do_dyncast のアセンブリの冒頭を確認します。

```
(gdb) disas $rip
Dump of assembler code for function __cxxabiv1::__class_type_info::__do_dyncast(...) const:
=> 0x00007ffff7adda30 <+0>:     push   %r12
   0x00007ffff7adda32 <+2>:     push   %rbp
   0x00007ffff7adda33 <+3>:     mov    %edx,%r12d
   0x00007ffff7adda36 <+6>:     push   %rbx
   0x00007ffff7adda37 <+7>:     sub    $0x10,%rsp
   0x00007ffff7adda3b <+11>:    mov    0x8(%rdi),%rbx   ; rdi = this, rbx = this->_name

   0x00007ffff7adda3f <+15>:    cmp    0x30(%rsp),%r8   ; obj_ptr == src_ptr
   0x00007ffff7adda44 <+20>:    mov    0x38(%rsp),%rbp
   0x00007ffff7adda49 <+25>:    je     0x7ffff7adda90 <__cxxabiv1::__class_type_info::__do_dyncast(...) const+96>

   0x00007ffff7adda4b <+27>:    mov    0x8(%rcx),%rsi   ; rcx = dst_type, rsi = dst_type._name
   0x00007ffff7adda4f <+31>:    cmp    %rbx,%rsi
   0x00007ffff7adda52 <+34>:    je     0x7ffff7adda6d <__cxxabiv1::__class_type_info::__do_dyncast(...) const+61>

   0x00007ffff7adda54 <+36>:    cmpb   $0x2a,(%rbx)     ; this->_name[0] == '*'
   0x00007ffff7adda57 <+39>:    je     0x7ffff7adda7c <__cxxabiv1::__class_type_info::__do_dyncast(...) const+76>

   0x00007ffff7adda59 <+41>:    mov    %rbx,%rdi
   0x00007ffff7adda5c <+44>:    mov    %r8,(%rsp)
   0x00007ffff7adda60 <+48>:    callq  0x7ffff7ada820 <strcmp@plt>
```

<+31> で &#95;name のアドレスを比較し、その後に '*' との比較を <+36> で行っているので、&#95;&#95;GXX_TYPEINFO_EQUALITY_INLINE = TRUE and &#95;&#95;GXX_MERGED_TYPEINFO_NAMES = FALSE の環境でコンパイルされたコードであると分かります。

&#95;&#95;GXX_TYPEINFO_EQUALITY_INLINE については、上記コメントの "In old abi, or when weak symbols are not supported, there can be multiple instances of a type_info object for one type" という記述からある程度推測できます。

まず、古い ABI では同じ型を示す型情報のインスタンスが複数存在したことを示唆しています。このため、当時はインスタンスのアドレス同士を比較することはできず、中身の文字列が同じバッファーを共有しているかどうかで型の一致を判断していたようです。

新しい ABI に準拠すると、1 つの型を示す型情報インスタンスは 1 つであるため、インスタンス同士のアドレスを比較することができるようになりました。ただし互換性を維持するため、デフォルトではインライン実装 (= 文字列バッファーのアドレス比較) を使いましょう、というのが "By default follow the old inline rules to avoid ABI changes." の意味だと思います。どちらもアドレスの比較なので、何を比較しても同じように思えますが、文字列バッファーのアドレス比較に関して強いてデメリットを上げるとすれば、_name を参照するための deref が一回増えるパフォーマンスの低下でしょうか。微々たるものでしょうが。

ABI の他、weak symbol という言葉が出てきます。私はそもそもこの概念を知りませんでした。駄目ですね。[Wikipedia のページ](https://en.wikipedia.org/wiki/Weak_symbol) もありますが、分かりやすかった説明はこちら。

Winfred C. H. Lu: Understand Weak Symbols by Examples
http://winfred-lu.blogspot.com/2009/11/understand-weak-symbols-by-examples.html

簡潔に言うと weak symbol とは、リンカーがオブジェクト ファイルをリンクするときに名前が重複するシンボルを上書きしたりされたりする仕組みのようです。

なぜ weak symbol が関連してくるかといえば、型情報のインスタンスを示す &#95;ZTI1D が weak symbol だからです。今まで出てきたサンプルのオブジェクト ファイルを見てみると分かります。以下の出力において V と W は weak symbol です。もし weak symbol がサポートされていない場合、各ファイルをコンパイルする毎に新しい型情報のインスタンスを作るのかもしれません。


```
$ nm 04.o
                 U __dynamic_cast
                 U _GLOBAL_OFFSET_TABLE_
0000000000000000 T main
0000000000000000 W _Z10check_typeIP1DEiT_
0000000000000000 W _Z10check_typeIP2B1EiT_
0000000000000000 W _Z10check_typeIP2B2EiT_
0000000000000000 W _ZN1D2f2Ev
0000000000000000 W _ZN1DC1Ev
0000000000000000 W _ZN1DC2Ev
0000000000000000 n _ZN1DC5Ev
0000000000000000 W _ZN2B12f1Ev
0000000000000000 W _ZN2B1C1Ev
0000000000000000 W _ZN2B1C2Ev
0000000000000000 n _ZN2B1C5Ev
0000000000000000 W _ZN2B22f2Ev
0000000000000000 W _ZN2B2C1Ev
0000000000000000 W _ZN2B2C2Ev
0000000000000000 n _ZN2B2C5Ev
                 U _Znwm
000000000000000b W _ZThn16_N1D2f2Ev
0000000000000000 V _ZTI1D
0000000000000000 V _ZTI2B1
0000000000000000 V _ZTI2B2
0000000000000000 V _ZTS1D
0000000000000000 V _ZTS2B1
0000000000000000 V _ZTS2B2
0000000000000000 V _ZTV1D
0000000000000000 V _ZTV2B1
0000000000000000 V _ZTV2B2
                 U _ZTVN10__cxxabiv117__class_type_infoE
                 U _ZTVN10__cxxabiv121__vmi_class_type_infoE
```

次に &#95;&#95;GXX_MERGED_TYPEINFO_NAMES です。デフォルトは無効で、有効にすると strcmp による比較を行わなくなります。ヘッダーに書かれたコメントを雑に要約すると、「weak symbol が使える場合には基本的に型がマージされるので strcmp による文字列比較は不要だが、dlopen で RTLD_LOCAL フラグを使ってモジュールをロードした場合には型がマージされないため、デフォルトでは常に strcmp による文字列比較を行なう。」と言っている感じです。このデフォルト動作が気に入らないせっかちな人のために、文字列比較をスキップするための &#95;&#95;GXX_MERGED_TYPEINFO_NAMES というマクロを用意しているのだと思います。ただし、&#95;&#95;do_dyncast は libstdc++ に含まれているため、&#95;&#95;GXX_MERGED_TYPEINFO_NAMES を変更するにはライブラリをビルドし直す必要があるはずです。試していないので確証はありませんが、そのうちやってみるかもしれません。

というわけで型情報の比較についてまとめます。

* weak symbol をサポートしている最近のバージョンでは、リンク時に型情報が 1 つにマージされるため、本来であればアドレスの比較だけで十分で文字列比較は必要ない
* プログラム内で外部モジュールをロードすると、 weak symbol を使っていても型情報がマージされないので、g++ としてはこのことを考慮し、既定で文字列比較を行なうコードを生成せざるを得ない
* もし作っているプログラムが外部モジュールをロードしないと分かっているのであれば、&#95;&#95;GXX_MERGED_TYPEINFO_NAMES=1 を定義して libstdc++ をコンパイルすれば文字列比較はしなくて済む、はず

&#95;&#95;GXX_MERGED_TYPEINFO_NAMES が未定義の場合、`_ZTI2B1 == _ZTI2B2` みたいに結果が偽となるような比較では必ず文字列比較が発生します。ちょっと気持ち悪いですね。さらに言えば、クラス名を長くすると長くした分だけ比較が遅くなりそうです。誰か測ってくれないかな。

# おわりに

仮想継承の前に、前回の記事で触れた offset_top の実例をちょろっと調べておこう、と思い立って dynamic_cast について調べ始めました。まさかここまで長くなるとは。

書く前から分かっていたことですが、C++ の dynamic_cast って別に無くても困らないですよね。私は使ったことがないですし、巷でもむしろ使わないことが推奨されていると思います。なんてかわいそうな子！

もう終わった気分になっていますが、まだ最後の砦の仮想継承が残っているのが信じられません。本当にやるのか。果たして。