dynamic_cast From Scratch
这篇文章总结自Arthur O’Dwyer在CppCon上的演讲dynamic_cast From Scratch，主要是先介绍运行时多态的相关基础知识，以及如何自己实现一个dynamic_cast。
dynamic_cast
一个正确实现的dynamic_cast应该能完成以下功能，为了简单，我们只用指针之间的转换为例，引用之间的转换类似。给定a类型为A：
- 同类型指针的转换，比如
dynamic_cast<A*>(a)应该返回a。 - up-cast，即子类指针向基类指针的转换，这种场景可以用隐式转换或者
static_cast也能完成。比如dynamic_cast<B*>(a)，如果B是A的Base subobject，那么返回A中的B对象的指针，否则返回nullptr。 - down-cast，即基类指针向子类指针的转换。比如
dynamic_cast<B*>(a)，如果a指向的对象类型中有且只有一个B对象，那就会返回这个B对象的指针，否则返回nullptr。 - side-cast，多继承情况下，会向“兄弟类型“转换。比如
dynamic_cast<B*>(a)，假设C同时public继承自A和B，此时C是A的most-derived类型，且因为C有一个unambiguous且public的基类B，此时会能完成side-cast，返回a中的C对象中的B对象指针。如果不能进行side-cast，会返回nullptr。 - cast to most-derived object，
dynamic_cast<void*>(a)会返回A的most-derived类型的指针
以上情况中，只有后三个case涉及到RTTI(run-time type identification)。想要实现一个dynamic_cast，我们需要回顾一些运行时多态的知识。
单继承多态
class Animal {
int legs;
virtual void speak() {
puts("hi");
}
virtual ~Animal();
};
class Cat : public Animal {
int tails;
void speak() override {
printf("Ouch, my %d tails!", tails);
}
};
我们首先简要回顾下多态的原理。基类和子类都有自己的虚函数表，每个对象的都有一个隐藏的数据成员vptr，它指向自己类的虚函数表。通过虚函数表，Animal和Cat都会有各自不同的虚函数调用，比如speak方法。
Animal和Cat的layout如下所示，本质上Cat is-a Animal。通过一个基类指针Animal*，我们就可以实现运行时多态。
多继承多态
引入多继承之后，就会出现所谓的菱形继承问题：
class Animal {
virtual ~Animal();
};
class Cat : public Animal {};
class Dog : public Animal {};
class CatDog : public Cat, public Dog {};
各个类的layout如下所示。Cat和Dog本身都是单继承，其layout都很容易理解。对于CataDog，它会拥有多继承中每一个父类对象，最后是CatDog自身的成员。
菱形继承的问题在于，对于一个CatDog对象，我们无法直接使用其中的Animal，或者说无法区分用的是Cat中的Animal还是Dog中的Animal。本质上CatDog是两个Animal，而不仅是一个Animal。
虚继承
要解决菱形继承的问题，C++引入了虚继承。通过Cat和Dog虚继承自Animal，CatDog中的Animal就被去重了。但需要注意的是，去重后的Animal在CatDog的layout中位置变了，它不再是Cat或者Dog中的一部分，而是在CatDog的最后。
所以，一但继承关系中出现虚继承之后，在运行时给定一个指针，我们就无法确认其基类在layout中的位置。比如下面的三种情况：
Cat虚继承自Animal，此时layout中Cat和Animal相邻Cat虚继承自Animal，而CatDog继承自Cat，此时layout中依次为Cat，CatDog，Animal- 如果引入更多继承关系，那么
Cat和Animal之间的间隔大小在运行时就不可知了。
注意我们这里强调的是运行时
在静态时，给定一个类型，其layout是根据ABI和编译器等在编译期就确定了的。但引入虚继承后，在运行时，给定一个指针，这个指针指向的对象layout可能完全不同（参照下图）。如果此时我们想通过dynamic_cast获取这个对象的虚基类，如果无法确定其layout，也就无法确定虚基类指针位置，那么该如何正确实现dynamic_cast呢？
我们现在已知：
- most-derived类型的layout是确定的
- 在运行时，对于任何不是most-drived类型的对象，我们无法确定其中虚基类在layout中偏移量
那如果要通过dynamic_cast获取任意对象中的虚基类，我们先要进行向下转型，先转成most-derived类型。由于其layout是确定的，也就能正确获取虚基类。所以问题就转换成，我们该如何确定most-derived类型？
虚函数表
根据上面的描述，我们可以得到以下结论：在虚继承关系下，想获取一个对象的虚基类对象，需要先获取到这个对象的most-derived类型，而确定most-derived类型的方法就是虚函数表。
假定给定一个Cat对象，它虚继承自Animal。它实际有两个虚函数表vtpr，一个是Cat的vtpr，一个是Anmical的vptr。可以看到两个虚函数表中都有Cat::speak这个方法，只不过Animal虚函数表中的Cat::speak方法接受的是一个Animal*的调用。
可以看到两个虚函数表中都有Cat::speak这个方法。当一个实际指向Cat的Animal指针a调用speak方法时，实际会发生如下事情：
- 通过Animal的虚函数表，找到
Cat::speak这个方法（图中带红色*的那个） - 由于
Cat::speak方法实际需要接受一个Cat*作为参数，所以需要从Animal*转换成一个Cat*（转换的方式我们一会再说） - 最终通过获取到的这个
Cat*，调用Cat::speak方法
如何在这个对象中进行Animal和Cat之间的转换呢？给定一个Cat对象c，它其中有几个变量：
- 指向
Cat的vptr，Cat的成员变量tails - 指向
Animal的vptr，Animal的成员变量legs
如果我们想进行转换，肯定不能直接在c这个变量中加减一个偏移量来获取类型。这是因为Cat这个类型可能还有其他子类，所以c的layout中的Cat和Animal这两部分之间还有其他成员。
而在虚函数表中我们额外保存了一些信息：
Animal-offset则是Cat到Animal的偏移量md-offset是当前vtpr到most-derived类，也就是Cat的偏移量
通过c找到Cat的虚函数表，发现Cat到Animal之前的偏移量Animal-offset为16，所以只需要将Cat的vptr加16就可以得到Animal的vptr。进而也就完成了Cat到Animal的向上转型，即获取虚基类。
同理，如果给定一个Animal指针a，可以通过a找到Animal的虚函数表，如果想获取其most-derived类型，可以根据md-offset为-16，通过Animal的vptr就可以得到Cat的vptr。进而也就完成了Animal到Cat的向下转型，即获取most-derived类型。
对于上图中的代码，现在想获取c->legs的汇编代码解释如下：
movq (%rdi), %rax将c指针保存到rax中-
movq -24(%rax), %rdx将%rax - 24内存地址中的值，也就是Animal-offset，保存到rdx中c指针指向的首地址就是Cat的vptr地址，也就是(%rax)，它指向Cat的第一个方法Cat::speak，而-24(%rax)指向Animal-offset。 movl 8(%rdx, %rdi), %eax将%rdx + %rdi + 8中的值保存到eax中，也就是legs的值
TLDR
最后我们总结一下虚函数表中的内容：
- 虚基类的偏移量（只在most-derived type的虚函数表中存在）
- most-derived type的偏移量
- type_info，用于RTTI
- 各种虚函数
以及几种常见的真正的dynamic_cast：
dynamic_cast<void*>to the most-derived classdynamic_castacross the hierarchy, to a sibling basedynamic_castfrom base to derived
