泛型<编程>：可识别联合(Discriminated Unions)（2）
Andrei Alexandrescu
你知道“语法作料”（译注：synbtactic suger，语言里用来提高可读性的部分，但对语言本身没有作用）吗？它导致了乱用分号的恶习？[1]好吧，玩笑开够了，今天我们有很多事情要做，让我们开始吧。
这个部分接着完善使用C++的可识别联合的实现。今天我们会结束关于对齐的讨论，并写一些Variant实现的实际代码。
在此之前，让我们回顾我们在上一部分“泛型<编程>”的进展。
上一节的重点
在把实现可识别联合的需求列表集中起来后，我们讨论了什么样的存储模型最佳。在遇到对齐问题的困难后，我们认为同时具备正确对齐，高效，能很好配合意外的（exception-friendly）存储模型应该是：
union
{
unsigned char buffer_[neededSize];
Align dummy_;
};
这里neededSize是联合中最大类型的大小，Align是一个能保证恰当对齐的POD[3]类型。
可识别联合的存储可能是最佳的，可能是过大的，也可能是有缺陷的，这取决于选择的Align好到什么程度。
甚至如果用最好的Align，上面的实现仍旧无法保证对所有类型百分百的通用。理论上，存在着编译器完全根据标准实现但仍然不能正确处理可识别联合。这是因为标准没有保证所有用户自定类型都有POD的对齐。但是这样的编译器更可能出现在变态的语言专家的假想中，而不是在现实中的语言编译器中。
实现一个对齐的计算
有几个有效的对齐计算算法可供选择。你可以在BOOST库[4]中看到几个实现。一个能很好计算一个类型T的对齐的算法应该是：
1、 从所有基本类型集合开始。
2、 从集合中去除大于T的类型。
3、 产生的Align是一个联合，它包含了第二步产生的集合中的所有类型。
这个算法的基本思想是，任何用户自定类型T最终只包含基本类型，T的对齐要求和那
些类型中的一个相同。较大的类型有较大的对齐要求；这样很自然地推论出T的对齐的上限是它最大成员的对齐。
这个算法可能会“过度对齐”结果。比如，如果T是char[5]，那么T的对齐要求可能是一。同时如果sizeof(int)是四。那么结果Align的对齐就会和一个int一样（极可能就是四）。
在多数情况下，过度对齐没太大害处（对齐不足才是灾难）。但另一方面，过度对齐浪费了空间。我们的步骤2保证了只有大小小于等于T的大小的类型才会被选中。
为了实现这个计算Align的算法，让我们回忆“泛型<编程>”的前个部分，我们有二个合适的工具可供支配：类型串和ConfigurableUnion。类型串让我们操作类型集合，让我们执行步骤1和2。ConfigurableUnion从一个类型串里产生一个C类型的集合，这样就能用在步骤3上。
非常重要的是，除了基本类型外，类型的初始集合还应该包括一些简单结构（structs）每个这样的结构只包含一个基本类型作为成员。我们用一个简单的模板来生成这些存根（stub）结构：
template
<typename U> struct Structify
{ U dummy_; };
引入这些小结构的原因很简单。一些编译器对包含一个int的结构比一个简单的int执行更高的对齐要求。这样，编译器作者就能确保所有用户定义类型有同样的对齐要求。这个在结构上的决定使编写编译器的不同部分都变的容易了。
这样我们就从包含有所有基本类型和所有“结构化”类型的类型串开始：
class Unknow;
typedef cons<
char,
short int,
int,
long int,
float,
double,
long double,
char*,
short int*,
int*,
long int*,
float*,
double*,
long double*,
void*,
Unknow (*)(Unknown),
Unknown* Unknown::*;
Unknown (Unknown::*)*Unknown),
Structify<char>,
StructifyMshort int>,
Structify<int>,
Structify<long int>,
Structify<float>,
Structify<double>,
Structify<long double>,
Structify<char*>,
Structify<short int*>,
Structify<int*>,
Structify<long int*>,
Structify<float*>,
Structify<double*>,
Structify<long double*>,
Structify<void*>,
Structify<Unknown (*)(Unknown)>,
Structify<Unknown* Unknown::*>,
Structify<Unknown (Unknown::*)(Unknown)>,
>::type
TypeOfAllAlignments;
行了，这样基本类型都有了；结构化的类型也有了——这正是我们要的。但上面类型串的一些行看上去好象是猫在键盘上跳舞的结果。这些行是：
Unknown (*)(Unknown)
Unknown* Unknown::*
Unknown (Unknown::*)(Unknown)
这些的结构化版本同时出现在类型串的底部。
这些是什么东西，他们从哪来的？为了让它们看上去更让人熟悉，我们来给它们名字：
Unknown (*T1)(Unknown);
Unknown* Unknown::* T2;
Unknown (Unknown::* T3)(Unknown);
啊哈！如果我们在上面每行前加typedef，它们用起来就象C的声明语法。T1是个带Unknown参数返回Unknown的函数指针；T2是个指向Unknown的成员，这个成员的类型是unknown*.。T3是一个指向Unknown的成员函数的指针，这个函数带一个unknown作为参数返回一个Unknown作为结果。
这里的技巧是，巧妙地命名一个实际上没有定义的Unknown 。这样，编译器会认为Unknown在其他地方定义并对其做出最坏的对齐需要的假设。（否则，编译器会对Unknown的内存布局作出优化。优化在这里是和通用性背道而驰的。）
好吧，有趣的部分来了，通过写下列模板，让我们从TypesOfAllAlignments去除所有大于给定大小的值。
Template <class Tlist, size_t size> struct ComputeAlignBound；
首先我们处理递归终止版本，就象任何好的递归算法应该做的：
template <size_t size>
struct ComputeAlignBound<null_typelist, size>
{
tyoedef null_typelist Result;
};
然后我们处理通用版本：
template <class head, class Tail, size_t size>
struct ComputeAlignBound<typelist<Head, Tail>, size>
{
typedef typename ComputeAlignBound<Tail, size>::result TailResult;
typedef typename select< //细节看下面
sizeof(head) <= size,
typelist<head, TailResult>,
TailResult>::result
Result;
};
首先，ComputeAlignBound产生类型串的尾部递归计算结果，放在TailResult。现在，如果Head大小小于等于size，结果是一个由Head和TailResult组成的类型串。否则，结果是类型串里只有TailResult——Head不再包括在里面。
这个类型选择通过一个小模板工具select来执行。为了节约专栏空间，我只好让你们看[5]来得到具体细节。这是个非常有用的小模板，如果你对用C++做泛型编程有兴趣，你应该自己去好好研究它。
我们需要做一些收尾工作来把所有这些整合在一起。我们来回忆一下我们有什么，我们需要什么。我们已经有了maxSize模板，它计算类型串中所有类型的最大尺寸。我们有ConfigurableUnion，它从类型串创建一个联合。最后我们有ComputeAlignBound，它计算一个类型的对齐需求，这个对齐需求可能等于或更严格于一个类型串中的所有类型的对齐需求。这里是具体怎样获得我们需要的代码。
Template <typename Tlist>
class AlignedPOD
{
enum { maxSize = MaxSize<Tlist>::result };
typedef ComputeAlignBound<TypeOfAllAlignments, maxSize>::Result
AlignTypes;
public:
typedef ConfigurableUnion<AlignTypes> Result;
};
你能通过把ComputeAlignBound, Unknown, Structify和ConfigurableUnion放在private的命名空间来完成封装。这样这些细节就能很好地隐藏起来。
可识别联合的实现：模拟的虚函数表(vtable)常用法
让我们回到可识别联合。到这一步为止，这篇文章的一半篇幅都在讨论怎样计算对齐。我希望这些努力没有白花；对齐在低层次的程序中非常重要，也对更高层次抽象的效率有帮助。
现在我们有在联合中存放对象的存储机制，我们需要识别器——存储在Variant中并能指出对象中的实际类型是什么的标志。识别器必须能对Variant的内容来执行某些类型相关的操作，比如类型辨认和类型安全的数据存取操作。
我们有许多设计的选择，最简单的是存储一个整型识别器：
template <class Tlist, class Align = AlignedPod<Tlist>::Result>
class Variant
{
union
{
char buffer_[size];
Align dummy_;
};
int discriminator_;
public:
...
};
这个方案的缺陷是整数不是很“聪明”。为了能通过这个识别器来完成各种任务，用switch的解决方案是逃不掉的。Switch意味着耦合。也许我们能够用int来作为一些表的索引，但为什么不直接用指向表内的指针呢？（我们下面会讨论这个方案）
第二个解决方案是使用代理(proxy)多态对象
template <class Tlist, class Align = AlignedPOD<Tlist>::Result>
class Variant
{
union
{
char buffer_[size];
Align dummy_;
};
struct ImplBase
{
virtual type_info& TypeId() = 0;
virtual Variant Clone(const Variant&) = 0;
virtual void Destroy(Variant&) = 0;;
...
};
implBase* pImpl_;
public:
...
};
这里的思想是通过一个指向多态对象的指针来对同样的数据来志向不同的操作。这样，基于buffer_里的实际数据是什么，这个指针指向不同的具体ImplBase，然后这个多态对象对其执行特定操作。
这个方法实际上非常清晰，除了一件事：效率。当调用一个函数比如Destroy时。访问步骤是：
* Variant对象。
* 提领（dereference）pImpl_。
* 提领pImpl_的虚函数表，就是所谓的“vtable”[6]。
* 通过索引在vtable找到正确的函数。
用常量作为索引访问vtable并存取一个对象的值域（最终也是通过索引访问）并不是问题，问题在于提领指针——在开始调用和得到函数之间有二个间接层次。但是，一个间接层次对分派正确的类型调用应该是足够了，但该怎么做呢？
（我来说明一下，如果你想知道为什么我忘记了关于优化的二项规定：（1）不要做优化。（2）还是不要做优化——我的确还记得。那么为什么Variant那么需要优化？答案很简单。这不是应用程序代码，这是库，另外，这是对一个语言特性的效率相当的模拟。Variant越是好用，你就越是多用它；相反它的实现效率越是差，它就越象是个玩具程序，这样你就不会把它用在真实的程序中。）
一个好的方法应该是模拟编译器的行为：仿造一个vtable并保证一个间接层次。这就引出下面代码：
template <class Tlist, class Align = AlignedPOD<Tlist>::Result>
class Variant
{
union
{
char buffer_[size];
Align dummy_;
};
struct Vtable
{
const std::type_info& (*typeId_)();
void (*destroy_)(const Variant&);
void (*clone_)(const Variant&, Variant&);
};
Vtable* vptr_;
Public:
...
};
Vtable结构包含了指向不同函数的指针，这些函数访问Variant对象（小心注意destroy_和clone_定义的语法；它们是存储在Vtable内的函数指针，就象一般的数据成员。这里C类型声明又有用武之处了。
以多付出些努力来实现代码的代价，模拟的vtable提供了只有一个间接层次和对Variant对象非常灵活的操作，让我们现在看看我们怎么初始化和使用这个模拟的vtable。
初始化一个Variant对象
在构造时，Variant需要初始化它的vptr_成员。另外，它需要正确初始化Vtable内的每个指针。为了达到这个目的，我们来定义一个模板VtableImpl<T>，。这个模板定义了一组静态函数，这些函数匹配Vtable内的函数指针的类型。
...在Variant内...
template <class T>
struct VtableImpl
{
static const std::type_info& TypeId()
{
return typeid(T);
}
static void Destroy(const Variant& var)
{
const T& data =
*reinterpret_cast<const T*>(&var.buffer_[0]);
data ~T();
}
static void Clone(const Variant& src, Variant& dest)
{
new (&dest.buffer_[0]) T(
reinterpret_cast<const T*>(&src.buffer_[0]));
dest.vptr_ = src.vptr_;
}
};
来看看VtableImpl实现的一些有趣的地方：
* 所有函数都是静态函数，Variant对象引用作为第一个参数。
* 当需要访问类型T的实际对象时，VtableImpl通过强制转换把&buffer_[0]转换到T*来拿到这个对象。换句话说，所有VtableImpl内的函数都假定有一个T对象在buffer_内。
把函数指针和buffer_内存储的类型做同步很简单——这是构造函数的工作
。
...在Variant内...
template <class T>
Variant(const T& val)
{
new (&buffer_[0]) T(val);
static VTable vtbl =
{
&VTableImpl<T>::TypeId,
&VTableImpl<T>::Destroy,
&VtableImpl<T>::Clone,
};
vptr_ = &vtbl;
}
没错，就这么简单。我们创建了一个传入的val的拷贝并很好地放在（通过使用placement new操作符）buffer_里，（我们前面很辛苦地保证了buffer_正确对齐以便存放一个T）然后，我们马上建立一个静态Vtable，用三个VtableImpl中的静态函数来初始化它。剩下来要做的就是用新建立的vtable的地址来初始化vptr_。这样，所有事情都做完了
慢着——不是真的“所有”，看看这个：
typedef Variant<cons<int, double>::type Number;
string s("Hello, World!");
Number weird{s};
上面代码能通过编译，因为能用string来实例化Variant的构造函数。然而，Number的本意很明显是只在构造函数里接受int和double。所以我们需要确保Variant的模板构造函数不能用在Variant的类型串以外的类型来实例化。
这里有两个辅助工具：类型串操作机制，它能在编译时计算出一个类型在类型串中的索引值；任何类型串库都带这样的功能。另一个工具是编译时断言——如果一个逻辑条件不满足能够产生不能通过编译的代码。我不想在这篇文章里重复细节，Boost[7]和loki[8]都有类型串操作机制和编译时断言，它们在语法上只有些微区别。
如果你想从根本上强制执行这个限制，那么你可以通过一个小工具做到：
template <class Tlist, typename T>
struct EnsureOccurence
{
typedef EnsureOccurence<typename Tlist::tail, T>::Result Result;
};
template <class T, class U>
struct EnsureOccurence<typelist<T, U>, T>
{
typedef T Result; //可能是T或任意类型
};
如果你这样初始化：
typedef EnsureOccurence<cons<int, double>::type, double>::Result Test
第一个特化版本实例化并用串尾递归实例化这个模板，在这个例子里，第二个特化版本最终被匹配并终止递归。
相反如果你想这样写：
typedef EnsureOccurence<cons<int, double>::type, long int>::Result Test;
第二个EnsureOccurence的特化版本永远不会被匹配；递归实例通过要求编译器实例化null_typelist::tail，一个不存在的类型，来表明类型串已被耗尽。
这样，Variant模板构造函数的修订版本是这样的：
...在Variant内...
template <class T>
Variant(const T& val)
{
typedef EnsureOccurence<Tlist, T>::Result Test;
new (&buffer_[0]) T(val);
static VTable vtbl =
{
&VTableImpl<T>::TypeId,
&VTableImpl<T>::Destroy
&VTableImpl<T>::Clone,
};
vptr_ = &vtble;
}
怎么处理默认构造函数？保守的做法是禁止它。但是一个不带恰当的构造函数的类是所谓的“最低限度的（minimalistic）”。至少你不能把Variants存储在STL容器里。
一个可行的决定是，把类型串的第一个类型作为默认构造对象来初始化Variant。你不能不初始化Variant，定义一个构造函数，让用户把“最容易初始化”的类型放在类型串首。
...在Variant里...
Variant()
{
typedef typename TList::Head T;
new (&buffer_[0]) T();
static Vtable vtbl =
{
&VTableImpl<T>::TypeId,
&VTableImpl<T>::Destroy,
&VTableImpl<T>::Clone,
};
vptr_ = &vtbl;
}
消除模板和默认构造函数间的重复代码就作为读者的练习。
使用模拟虚函数表
我们来看怎样让Variant的用户使用VTableImpl提供的功能。例如，得到一个Variant对象的类型标识就象这样：
template <class Tlist, class Align = AlignedPOD<Tlist>>::Result>
class Variant
{
...
public:
const std::type_info& TypeId() const
{
return (vptr_->typeId_)();
}
...
};
这些代码仅用一行代码来通过vptr_的typeId_函数指针来调用它指向的函数。现在返回一个指向Variant对象的类型化指针的函数只需要六行代码：
...在Variant中...
template <typename T> T* GetPtr()
{
return TypeId() == typeid()
? reinterpret_cast<T*>(&buffer_[0])
: 0;
}
（在实际应用中，你还需要写对应的const函数版本）
析构函数甚至还要简单：
...在Variant中...
~Variant()
{
(vptr_->destroy_)(*this);
}
到现在我们有一个漂亮的Variant模板类核心，可以正确地构造和销毁对象。用类型安全的方式来获得存储的数据。这个小小的类急需扩充，正如我们将在下个部分的“返型<编程>”中会看到的
总结
这篇文章有几处需要总结。一个是，象软件设计一样，关于软件的文章也可能会超出预算。我开始计划用一个专栏的篇幅来写可识别联合。在仔细地分析必须达到的细节水平后，我确定了（也公布了）两个专栏来完成任务。现在我不得不用三个专栏来写这个主题（或更多，现在不能保证）。
但是我相信这些非常重要，值得详细描述。
可移植地计算对齐是困难的，也是可行的。但无法保证百分之百可移植。这个工作是对语言特性的补充。对齐对想要进行自定义分配泛型类型内存（就象Varuabt所做的）或用其他方法处理内存的人是非常重要的。
模拟vtable常用法让你手写通常应该由编译器自动产生的代码——一个包含函数指针的结构。它也规定了要显式表示一个指针（vptr_）指向一个特定于你的对象的vtable，并让你正确地初始化这个指针。模板让自动生成vtable成为可能。
作为对你努力的回报，模拟的vtable常用法能让你对实际对象实现多态行为。
鸣谢
非常感谢Emily Winch提供了非常仔细和有帮助的检查。
注：
[1] Alan Perlis有名的玩笑话之一。
[2] A. Alexandrescu. "Generic<Programming>: Discriminated Unions (I)," C/C++ Users Journal C++ Experts Forum, <www.cuj.com/experts/2004/alexandr.htm>.
[3] POD 表示简单旧类型,一个包括基本类型和类似于C结构/联合的类型，就是说（细节上）：没有用户申明的构造函数，没有私有或保护非静态数据成员，没有基类，没有需函数，没有非静态指向成员的成员数据指针，没有非POD结构，非POD联合（或者这些类型的数组）或引用，没有用户定义拷贝赋值操作符，也没有用户定义析构函数。
[4]在boost的下载目录或开发邮件列表里搜索“对齐”。你可以从www.boost.org里获得这些。
[5] Select模板
[6] 不是必须要用虚函数表，但看上去所有的C++实现里都用到这个机制的变种
[7] <www.boost.org>
[8] A. Alexandrescu. Modern C++ Design (Addison-Wesley Longman, 2001), 第 2和第三3章。
Andrei Alexandrescu 是位于西雅图的华盛顿大学的博士生，也是受到好评的《Modern C++ Design》一书的作者。可以通过www.moderncppdesign.com. 来联系他。Andrei同时也是C++研讨会 (<www.gotw.ca/cpp_seminar>).的一名有号召力的讲师。
