天方夜谭VCL: 多态
天方夜谭VCL: 多态虫虫
我们中国人崇拜龙，所谓“龙生九种，九种各别”。哪九种？《西游记》里西海龙王对孙悟空说：“第一个小黄龙，见居淮渎；第二个小骊龙，见住济渎；第三个青背龙，占了江渎；第四个赤髯龙，镇守河渎；第五个徒劳龙，与佛祖司钟；第六个稳兽龙，与神官镇脊；第七个敬仲龙，与玉帝守擎天华表；第八个蜃龙，在大家兄处砥据太岳。此乃第九个鼍龙，因年幼无甚执事，自旧年才着他居黑水河养性，待成名，别迁调用，谁知他不遵吾旨，冲撞大圣也。”（注：鼍龙是文雅的说法，民间叫法是猪婆龙，也就是扬子鳄。）如果您冲着这九位说一声“Let’s go”，那场面可壮观了，有天上飞的，有水里游的，也有地上爬的。同样是“go”，“go”的具体形式却各不相同，这正是多态“一个接口，多种实现”的典型例子。
多态的实现方法很多，其中C++直接支持的方式有：通过关键字virtual提供虚函数进行迟后联编，以及通过模板（template）实现静态多态性，它们都各有用武之地。我们比较熟悉的是虚函数，这是建构类层次的重要手段，我们也已经分析过虚函数的原理[1]。然而在有些情况下，虚函数的性能并不是最优，故VCL还提供了一种动态（dynamic）函数，用法和虚函数一模一样，只要把virtual换成DYNAMIC就可以了。VCL的帮助文件里说，动态函数跟虚拟函数相比，空间效率占优，时间效率不行，真的吗？其实现原理又是如何呢？我们又应该如何权衡这两者的使用呢？我们将从一个相当一般的角度来讨论这些问题。
虚函数的苦恼
如下类层次来自一个图形绘制程序的一部分。为了方便管理，界面与具体的图形设计分离。各种图形以动态连接库的方式提供，作为插件的形式。这样可以在不重新编译主程序的情况，增加或减少各种图形。
图1Shape类层次
最初Shape的声明是 class Shape {
private:
int x0, y0;
protected:
Shape();
virtual ~Shape();
public:
int x() const;
int y() const;
virtual void draw(void *) = 0;
virtual int move(int, int);
};
后来因为功能扩充，添加了两个虚函数。 class Shape {
private:
int x0, y0;
protected:
Shape();
virtual ~Shape();
public:
int x() const;
int y() const;
virtual int move(int, int);
virtual void draw(void *) = 0;
virtual void save(void *) const = 0;
virtual void load(void *) = 0;
};
后来又作过一些修改，又添加了若干虚函数。问题就在于，虚函数一但增加，虚拟函数表VFT就会发生变化，这时候，主程序就必须重新编译。更糟糕的是，一旦版本升级，派生自不同版本Shape的图形绝对不可以混用[2]。所以我们可以看到硬盘里充斥着mfc20.dll、mfc40.dll、mfc42.dll……却一个也不能删除，这就是MFC升级所带来的DLL垃圾。怎么办？
初步解决
我在网上问过这样的问题，得到的答复主要有：
用COM；
预先多写一些无用的虚函数，留出扩充空间。
其实上面的方法都能很好地解决这个问题。但是推广看来，也有一定局限性。COM不适合解决类层次过深的情况，预留的空间则是不折不扣的“鸡肋”。
追根究底，这个局限性是因为父类和子类的虚拟函数表VFT之间过强的关联性：子类的VFT的前面一部分必须与父类相同。而当父类和子类不在同一个DLL或EXE中的时候，这个要求是很难满足的。父类一旦改变，子类如果不重新编译，就将导致错误。解决的方法，当然就是取消父类和子类VFT之间的关联性。我设计了一个很笨的解决办法，但可以取消这个关联性，使虚函数保证始终只有2个。 #define Dynamic // Dynamic什么都不是，只是好看一点
struct point
{
int x, y;
};
class dispatch_error{};
class Shape {
private:
int x0, y0;
protected:
Shape();
virtual ~Shape();
virtual void dispatch(int id, void* in, void* out);
// in和out是函数的输入输出参数，id是每个函数唯一的标记符号，即代号
// 实际运用中，id不一定是整数，也可以是128位UUID，或者字符串等等
public:
int x() const;
int y() const;
Dynamic int move(int dx, int dy)
{
int r;
point p = {dx, dy};
dispatch(-1, &p, &r);
return r;
}
Dynamic void draw(void *hdc){dispatch(-2, hdc, 0);}
Dynamic void save(void* o) const{dispatch(-3, o, 0);}
Dynamic void load(void* i){dispatch(-4, i, 0);}
};
void Shape::dispatch(int id, void* in, void* out)
{
switch(id)
{
case -1:
...
case -2:
...
...
default:
throw(dispatch_error()); // 若函数不存在则抛出异常
}
}
如果子类Triangle要改写Shape::draw，那么只需要 void Triangle::dispatch(int id, void* in, void* out)
{
switch(id)
{
...
case -2:// 改写Shape::draw
...
...
default:
Shape::dispatch(id, in, out); //函数不存在则向父类找
}
}
这样的“Dynamic函数”就解决了前面的问题，只有析构和dispatch这两个虚函数。父类和子类的VFT之间没有关联性，可以自由改动而不会互相影响。
评头论足
我们来对这种解决方案作了评价：的确解决了虚函数的问题，但是也付出了不小的代价：时间效率和可读性，由此也决定了该方案的应用面不广，一般用于
虚函数很少或几乎不需改写的情况。这样有助于减少VFT的大小。至于运行速度则没有什么提高，毕竟VFT的访问速度是常数级[3]；
父类需要经常更新而子类不方便同步更新，对效率要求又不高的情况。一般的应用程序都可以使用。
从模式（Patterns）的角度来看，这种方法是典型的职责链（Chain of Responsibility）模式[4]：调用请求从最低层子类开始一层层往上传递，直到被处理或者最后抛出异常。这种模式运用非常广泛，比如VCL消息映射[5]和COM中IDispatch接口[6]，与上述解决方案的形式都非常相似。
这个解决方案还可以作进一步的完善，以更好地适用于单根结构的框架。比如单根结构的类库，如MFC和VCL，通过RTTI可以找到唯一的父类，那么可以分离数据（函数代号和指针）和代码（调配部分），以简化结构。解决的方法就是典型的表格驱动，有不少书[7，8]都用此来优化COM中IUnkown接口的QueryInterface。我们引入类DMT来储存函数的代号和指针。 #include
using namespace std;
class DMT {
char* const ptr;
const DMT* const parent;
public:
DMT(const DMT* const, const int, ...);
~DMT() {delete []ptr;}
short size() const {return *(short*)ptr;}
const void* find(int) const;
};
图2类DMT图解
需要特别注意的是DMT::ptr所分配的空间。在32位系统上，对于n个“Dynamic函数”，需要sizeof(short)字节储存n（红色部分），sizeof(void*)*n字节储存函数代号（黄色部分），以及sizeof(void*)*n字节储存函数指针（蓝色部分），一共是sizeof(short) + 2*n*sizeof(void*)字节。子类和父类的DMT可以通过链表形式连接起来。下面我们看看DMT::find和DMT::DMT的实现。 const void* DMT::find(int i) const
{
const int* begin = (int*)(ptr + sizeof(short)), *p;
for(p = begin; p < begin + size(); ++p)
if(*(int*)p == i)
return *(void**)(p+ size());
// 找到对应的函数代号后，向前跳DMT::size()则是相应的函数指针
return (parent)? parent->find(i): 0;
}
DMT::DMT(const DMT* const p, const int n, ...)
: parent(p), ptr(new char[sizeof(short)+2*n*sizeof(void*)])
// ptr分配的空间大小如前所述
{
int* i = (int*)(ptr + 2), c;
*(short*)ptr = n;// 往头sizeof(short)字节写入n（红色部分）
va_list ap;
va_start(ap, n);
for(c = 0; c < n; ++c)// 往黄色部分写入函数代号
*(i++) = va_arg(ap, int);
typedef void (DMT::*temp_type)();
temp_type temp;
for(c = 0; c < n; ++c)// 往蓝色部分写入函数指针
{
temp = va_arg(ap, temp_type);
*(i++) = *(int*)&temp;
}
va_end(ap);
}
下面我们在Shape类层次中应用DMT类。 class Shape {
private:
int x0, y0;
void int f_move(void* dx, void* dy) {...}
protected:
static const DMT dmt_Shape;// Shape类的DMT
const DMT* const dmt;// 指向该类DMT的指针
Shape() : dmt(&dmt_Shape) {...}
virtual ~Shape();
void dispatch(int id, void* in, void* out)// 这次不是虚函数！
{
void (A::*f)(void*, void*);
*(const void**)&f = dmt->find(id);
(this->*f)(in, out);
}
public:
int x() const;
int y() const;
Dynamic int move(int dx, int dy)
{
int r;
point p = {dx, dy};
dispatch(-1, &p, &r);
return r;
}
Dynamic void draw(void *hdc){dispatch(-2, hdc, 0);}
Dynamic void save(void* o) const{dispatch(-3, o, 0);}
Dynamic void load(void* i){dispatch(-4, i, 0);}
};
const DMT Shape::dmt_Shape =
DMT(0, 4, -1, -2, -3, -4, &Shape::f_move, 0, 0, 0);
背景突出部分就是有改动的地方。如果子类Triangle要改写Shape::draw，那么只需要 class Triangle {
private:
void f_draw(void*);
...
protected:
static const DMT dmt_Triangle;
...
public:
Triangle() {dmt = &dmt_Triangle; ...}
...
};
const DMT Triangle::dmt_Triangle =
DMT(Shape::dmt_Shape, ..., -2, ..., &Triangle::f_draw...);
这就是对“Dynamic函数”的另一种实现，这样可以分离数据和代码。当然这个示例并不具备实际应用价值，在静态成员初始化、调用约定、可读性等诸多设计上都有不少问题，仅仅起演示作用。
动态（dynamic）函数
Object Pascal提供了两种函数实现多态：一种是我们熟悉的虚拟（virtual）函数，另外一种则是动态（dynamic）函数，其实就是对前面的“Dynamic函数”提供的语言级别的支持。
可能有些用C++ Builder的朋友说，C++ Builder里怎么看到啊？在C++ Builder里，标识动态函数的宏（macro）是DYNAMIC，也就是__declspec(dynamic)，这是Borland对C++的扩充。像TControl::Click、TControl::MouseMove等等都是动态函数。DYNAMIC的用法和virtual基本一致，我所发现的不同仅仅是，当子类改写父类相应函数时，子类中virtual可以省略，而DYNAMIC则不行。
那么，每个类的动态函数的入口在哪里呢？上次，我们已经挖出了VMT的分布图，里面就有vmtDynamicTable = 0xffffffd0这么一句，字面就告诉我们，这是动态方法表DMT（Dynamic Method Table）的入口。不妨检验一下。 #include
#include
struct A: private TObject
{
DYNAMIC void f1() = 0;
void f3() {}
virtual void f4() {}
DYNAMIC void f2() = 0;
};
struct B: A
{
DYNAMIC void f1() {}
DYNAMIC void f2() {}
};
void main()
{
A* p = new B;
std::cout<<(void*)p<f1();
p->f2();
delete p;
}
这个程序会输出“0118095C”。当然不同的机器上这个数值可能有所不同，总之先记下了。
其中p->f1();的汇编代码是 push dword ptr [ebp-0x30]
or edx,-0x01;这句其实就相当于mov edx,0xffffffff
mov eax,[ebp-0x30]
call System::FindDynaInst(void *, int)
call eax
pop ecx
p->f2();的汇编代码是 push dword ptr [ebp-0x30]
mov edx,0xfffffffe
mov eax,[ebp-0x30]
call System::FindDynaInst(void *, int)
call eax
pop ecx
程序很简单，我们说明一下。
or edx,-0x01跟mov edx,0xffffffff的效果是完全一样的，任何数和0xffffffff进行“或”运算的结果当然都是0xffffffff；
这两段唯一的不同就是mov edx,0xffffffff（也就是or edx,-0x01）和mov edx,0xfffffffe，我们上次已经说过了补码表示法，这里其实就是分别传递的A::f1和A::f2的函数代号–1和–2；
执行过mov eax,[ebp-0x30]这一句后，我们可以发现eax的值就是刚才我们记下的数（0118095C），这里包含了指向VMT入口的指针；
向System::FindDynaInst传入的两个参数就分别是包含指向VMT入口的指针，以及相应函数的代号，分别在eax和edx里；
显然System::FindDynaInst把对应函数代号的函数指针放在eax里，call eax就调用相应的函数。 这就是整个大的流程。现在我们关心的是，System::FindDynaInst(void*, int)到底做了些什么。我们可以跟踪进去，再跳一层，我们来到了函数中，源代码就是Source\Vcl\system.pas中的_FindDynaInst。 procedure _FindDynaInst;
asm
PUSHEBX
MOVEBX,EDX;EBX储存了函数的代号
MOVEAX,[EAX];EAX获得VMT入口地址
CALLGetDynaMethod;调用GetDynaMethod
MOVEAX,EBX
POPEBX
JNE@@exit
POPECX
JMP_AbstractError
@@exit:
end;
那么我们还得看看GetDynaMethod的源代码。 procedure GetDynaMethod;
{function GetDynaMethod(vmt: TClass; selector: Smallint) : Pointer;}
asm
{ ->EAX vmt of class}
{BX dynamic method index}
{ <-EBX pointer to routine}
{ZF = 0 if found}
{trashes: EAX, ECX}
PUSHEDI
XCHGEAX,EBX;交换eax和ebx的值
JMP@@haveVMT;交换后ebx是VMT入口地址，eax是函数代号
@@outerLoop:
MOVEBX,[EBX];取地址
@@haveVMT:
MOVEDI,[EBX].vmtDynamicTable;EDI是DMT的入口
TESTEDI,EDI;测试是否存在DMT（EDI是否为0）
JE@@parent;若DMT不存在，在父类中继续找
MOVZXECX,word ptr [EDI];取头两个字节，即动态函数个数
PUSHECX
ADDEDI,2;跳至黄色部分（见后面的图）
REPNESCASW;查找eax
JE@@found;若找到则跳转
POPECX
@@parent:
MOVEBX,[EBX].vmtParent;在父类中继续
TESTEBX,EBX;是否有父类
JNE@@outerLoop;有则继续查找
JMP@@exit;无则跳转
@@found:
POPEAX
ADDEAX,EAX;以下两步是清除ZF，其中ECX值为0
SUBEAX,ECX { this will always clear the Z-flag ! }
MOVEBX,[EDI+EAX*2-4];edi-1是函数代号所在处
@@exit:
POPEDI
end;
看汇编头晕吧？嘿嘿，对着注释看看这个图就清楚了。vmtDynamicTable所指向的地址，就是一个DMT，而它的结构，我们前面已经分析过了。唯一需要说明的是 ADDEAX,EAX;EAX值为n，自加后为2*n
SUBEAX,ECX;ecx值已经递减为0，这句仅仅是清除ZF标志位
MOVEBX,[EDI+EAX*2-4];
清除ZF是因为_FindDynaInst要由此判断是否找到相应的函数。而edi-4为函数代号所在的地方，edi-4+4*n即为函数指针所在，也就是edi+eax*2-4。
其实不需要与汇编纠缠，在前面我们已经知道了其原理，大同小异罢了。
结束语
C++的重用性是对源代码级而言，而对二进制级重用性的支持则捉襟见肘。特别是动态连接库DLL的广泛运用，更显出解决这个问题的重要性。COM的口号之一正是COM as a Better C++7。讲COM的书中往往指出若干C++的不足，其实不少是可以解决的。比如
问题：不同编译器的名字粉碎机制不同，导致不同编译器编译的模块不能顺利连接。
解决：使用DEF文件。
代价：操作麻烦，增加维护负担，但对程序效率没有任何影响。
问题：不同版本的类大小不一样，主要原因是成员变量增加或减少，导致分配空间时出错。
解决：隐藏实现，成员变量仅保留一个指针void *，在运行时动态申请空间。
代价：可读性和性能均受影响。
添加普通成员函数没有什么大的问题，但是添加虚函数则影响VFT，可能导致程序错误甚至系统崩溃。解决的办法在前面已经说明，其中良好的设计是必不可少的。建议
根类的设计一定要慎重，VCL从开始至今，TObject类的变化始终很少，否则牵一发而动全身，维护性就大打折扣；
类层次应尽可能浅，尽量避免使用继承等耦合性很强的关系，严格遵循Liskov替换原则LSP[9]；
如果程序只在WINDOWS下运行，可以考虑使用COM；
如果始终使用Borland的编译器，并对性能要求不高，可以考虑使用动态（dynamic）函数；
多写几个无用的虚函数占位，也是个不错的方法。
动态函数应用在合适的地方，这一点可以参考VCL各个类中动态函数的使用情况。另外，动态函数所节约的VFT空间微不足道，在有的情况反而DMT的空间占得更多。总体来说，动态函数在时间上吃亏，空间上占的便宜也不大。在我看来，解除了父类和子类VFT之间的关联性，才是动态函数最大的好处。
不论是辨证唯物主义，还是道家思想，都强调事物的两面性。不论什么方法，都是一把双刃剑，所谓“祸兮福之所倚，福兮祸之所伏”。我们要做的，就是权衡利弊，结合具体的环境，扬长避短。
参考
1. 虫虫．《天方夜谭VCL：开门》．C++ View．2001，9．
2. George Shepherd, Brad King. Inside ATL. Microsoft Press. 1999.
3. Stanley Lippman. Inside the C++ Object Model. Addison-Wesley, Reading, MA. 1996
侯捷．《深度探索C++物件模型》．碁峰资讯股份有限公司．1998．
侯捷．《深度探索C++对象模型》．华中科技大学出版社．2001．
4. GoF. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, Reading, MA. 1995.
李英军等．《设计模式：可复用面向对象软件软件的基础》．机械工业出版社．2000．
5. CKER．《深入BCB理解VCL的消息机制》．C++ View第1期．
6. Dale Rogerson. Inside COM. Microsoft Press. 1997.
杨秀章．《COM技术内幕》．清华大学出版社．1999．
7. Don Box. Essential COM. Addison-Wesley, Reading, MA. 1998.
侯捷．《COM本质论》．碁峰资讯股份有限公司．1999．
潘爱民．《COM本质论》．中国电力出版社．2001．
8. Brent E. Rector and Chris Sells. ATL Internals. Addison-Wesley, Reading, MA. 1999.
潘爱民，新语．《ATL深入解析》．中国电力出版社．2001．
9. Robert C.Martin. “The Liskov Substitution Principle”. C++ Report. 1996, 3.
虫虫，plpliuly．《Liskov替换原则LSP》．C++ View．2001，9．
