如何在编译期进行拓扑排序，自动处理模块初始化依赖顺序。

　　模块之间的初始化和清理的顺序是很重要的。这个顺序应该可以根据各个模块之间的依赖关系求出。而且在绝大部分情况下，链接进工程的各个模块之间的依赖关系在编译期就可以确定出来。下面我们来讨论一下如何通过模板元编程构造一套方便的机制，让编译器自动帮你完成初始化和清理的排序工作。

　　为了方便大家理解这部分工作到底能够用于处理什么情况，这里先将实现后的用法说明一下：

　　假设我们有6个模块，分别叫做ModuleA，ModuleB，ModuleC，ModuleD，ModuleE，ModuleF。这6个模块各自有自己的初始化和清理函数(Init和Shutdown)。在使用这些模块的功能之前必须按照依赖关系进行排序然后初始化，在使用完成之后需要按照相反的顺序进行清理。如果这些顺序都由程序员自己手工控制无疑是容易出错的，为此可以利用模板元的帮助实现一个模块管理器帮助自动完成这项排序工作。

　　首先我们来看一下如何描述各个模块之间的依赖关系。在模块管理器中存在如下定义：

template<typename Module> struct ModuleDescriptor;

　　这是一个没有定义的模板结构，该结构的特化可以用于描述每个模块的初始化清理函数以及依赖关系。每个模块都必须各自根据自己的标签特化该结构，并写入自己的内容。

　　比如在模块A的头文件ModuleA.h中的模块描述代码如下：

template<> struct ModuleDescriptor<struct ModuleA> { typedef TYPELIST_1(struct ModuleD) dependencies; static void Init() { printf("Init ModuleA/n"); } static void Shutdown() { printf("Shutdown ModuleA/n"); } };

　　模板特化利用了一个模块A的标签类(struct ModuleA)进行特化，并且由于模块A依赖于模块D，在dependencies中加入模块D的标签。注意标签是没有必要写出定义的，因为它只是用给编译器在编译器的一个标识，这样编译器根本不会为标签生成任何代码。

dependencies是一个类型链表(TypeList,详见下文)。该类型链表中就保存了A模块的依赖关系。后面两个静态函数Init和Shutdown分别描述了A模块的初始化和清理函数。

　　其他的5个模块都按这种方式在各自的头文件中写下自己的依赖项以及初始化和清理函数。

这样在使用的时候就可以方便的利用模板元的模块管理器进行排序，操作代码如下：

/// 全部模块的标签列表 typedef TYPELIST_6(ModuleA,ModuleB,ModuleC,ModuleD,ModuleE,ModuleF) ModuleList; /// 对模块链表进行依赖排序,排序的结果保存在SortedModuleList typedef meta::SortModuleList<ModuleList>::Result SortedModuleList; int main() { // 这里是按照未排序的顺序进行初始化和清理工作 meta::DoModule<ModuleList>::Init(); meta::DoModule<ModuleList>::Shutdown(); // 这里是按照依赖排序的顺序进行初始化和清理工作 meta::DoModule<SortedModuleList>::Init(); meta::DoModule<SortedModuleList>::Shutdown(); return 0; }

　　可以看到，这样就可以很方便在利用编译器帮你指定依赖顺序了。而且如果在依赖顺序关系中出现了依赖循环的情况，模板元也可以检测出来，并产生编译错误。这样就是一种很好的机制保证了初始化的清理工作的正确进行。

　　下面将详细描述一下整个依赖关系的拓扑排序是如何进行的：

　　首先建议参考下Modern C++ Design中对模板元编程的描述，特别是关于类型链表TypeList的实现，因为后面的内容需要对模板元编程有一定的认识。下面我会罗列实现编译期拓扑排序需要用到的东西。一些基本的部分和Modern C++ Design中的内容是相似的，但有一些地方不太相同。代码中的注释上对各个功能函数和结构的用途和算法都写得清楚。因此只在必要的地方进行解释。

　　为了方便模板元编程，我们首先需要一些基本的组件。这里用到的基本组件有：

　　将bool值映射成类型的模板：BoolToType

/** * 将一个bool值映射成一个类型,并且通过该类型的value * 静态成员可以取得该bool的值. * @author songfeiyu */ template<bool v> struct BoolToType { static const bool value = v; };

　　描述将一个空类型NullType，和判断一个类型是否为空类型的模板：IsNullType

/** * 空类型,不能构造实例.一般用于在元程序中代表一些无 * 内容的信息,比如类型链表的边界. * @author songfeiyu */ struct NullType; /** * 判断类,用于判断某个类型是否是NullType. */ template<typename T> struct IsNullType { static const bool value = false; }; template<> struct IsNullType<NullType> { static const bool value = true; };

　　根据一个编译期的bool值进行类型选择的结构Select:

/** * 根据一个bool类型的flag值对后两个模板参数的类型进行选择. * 如果flag为true,在Result中记录的是T的类型,如果为false,则 * 在Result中记录的是U的类型. * @note 参考Modern C++ Design实现. * @author songfeiyu */ template<bool flag,typename T,typename U> struct Select { typedef T Result; }; template<typename T,typename U> struct Select<false,T,U> { typedef U Result; };

　然后就是最关键的部分，TypeList。下面拓扑排序中需要用到TypeList功能的代码：

/** * 类型链表. * 编译期的链表格式,用于保存一组类型值.以及在该链表上实现的 * 一套增添删改和排序等操作. * @note 参考Modern C++ Design实现. * @author songfeiyu */ template<typename T,typename U> struct TypeList { // 保存当前节点的类型 typedef T Head; // 当前节点之后的TypeList,如果为NullType则表示链表结束. typedef U Tail; }; 　　为了保护名字空间，对TypeList的操作都是放在TL名字空间之下的： namespace TL { /** * 计算类型链表的长度. * @param TL 待计算长度的TypeList. * @return Length<TL>::value TL链表的长度. */ template<typename TL> struct Length; // 递归终止条件:当碰到NullType的时候就到达链表尾了. template<> struct Length<NullType> { // 一个空链表的长度为0 static const int value = 0; }; // 当前节点还没有到链表尾. // 下面的模板类型中Head代表当前节点的类型,Tail代表后面剩下的类型链表. template<typename Head,typename Tail> struct Length< TypeList<Head,Tail> > { // 类型链表的长度 = 1 + 除去当前节点外后面节点的长度值. static const int value = 1 + Length<Tail>::value; }; /** * 取得指定位置的类型. * @param TL 类型链表. * @param i 索引的位置. * @return TypeAt<TL,i>::Result TL链表的第i个节点的类型. */ template<typename TL,int i> struct TypeAt; // 递归终止条件. template<typename Head,typename Tail> struct TypeAt<TypeList<Head,Tail>,0> { // i的值为0的时候类型就是当前节点的类型. typedef Head Result; }; // 当前节点还没有到第i个节点的位置. template<typename Head,typename Tail,int i> struct TypeAt<TypeList<Head,i> { // 如果i还不为0,那么将i减一并在向后继续查找. typedef typename TypeAt<Tail,i-1>::Result Result; }; /** * 查找指定类型所在的索引位置. * @param TL 类型链表. * @param T 待查找的类型. * @return IndexOf<TL,T>::value 索引所在的位置,-1表示不存在该类型. */ template<typename TL,typename T> struct IndexOf; // 递归终止条件:如果查找到链表末尾都还没有找到,则返回-1. template<typename T> struct IndexOf<NullType,T> { static const int value = -1; }; // 递归终止条件:如果指定类型相匹配了,则在该节点终止. template<typename Tail,typename T> struct IndexOf<TypeList<T,T> { static const int value = 0; }; // 当前节点既不末尾,也不是匹配节点 template<typename Head,typename T> struct IndexOf<TypeList<Head,T> { private: // 先判断尾链表中查找的索引值. static const int temp = IndexOf<Tail,T>::value; public: // 如果当前节点不是,尾链表中又没有查到(temp == -1的情况) // 则放回的值也为-1. // 如果在尾链表中查到了temp,则反向将返回值加一,以计算出最 // 终匹配的节点所在的位置. static const int value = (temp == -1) ? -1 : 1 + temp; }; /** * 向TypeList中添加元素. * @param TL 类型链表. * @param T 将T插入到TL的结尾处. * @return Append<TL,T>::Result 插入T后的类型链表结构. */ template<typename TL,typename T> struct Append; // 特殊情况:如果待插入链表为空,插入的值也为空,则返回空类型. template<> struct Append<NullType,NullType> { typedef NullType Result; }; // 特殊情况:如果待插入链表为空,插入类型为T,则返回一个包含类型T的链表. template<typename T> struct Append<NullType,T> { typedef TypeList<T,NullType> Result; }; // 特殊情况:如果待插入链表为空,插入的类型是个TypeList,则返回该TypeList template<typename Head,typename Tail> struct Append< NullType,TypeList<Head,Tail> > { typedef TypeList<Head,Tail> Result; }; // 当前节点都不是以上情况的时候. template<typename Head,typename T> struct Append<TypeList<Head,T> { // 取出Head节点,将T添加到Tail上面后组合成一个TypeList返回. // 这样会一直递归到TL为NullType的情况,然后根据T的类型调用 // 上面三种特殊情况. typedef TypeList<Head,typename Append<Tail,T>::Result> Result; }; /** * 从TypeList中移除一个指定元素. * @param TL 类型链表. * @param T 待移除元素的类型. * @return Remove::Result 移除了一个T后的类型链表结构. */ template<typename TypeList,typename T> struct Remove; // 递归终止情况:走到末尾都没有发现指定元素. template<typename T> struct Remove<NullType,T> { typedef NullType Result; }; // 递归终止情况:发现指定类型的节点. template<typename T,typename Tail> struct Remove<TypeList<T,T> { // 直接将Tail返回,就相当于删除了当前节点. typedef Tail Result; }; // 当前节点既不是结尾,又不是指定节点的情况. template<typename Head,typename T> struct Remove<TypeList<Head,T> { // 递归调用. typedef TypeList<Head,typename Remove<Tail,T>::Result> Result; }; /** * 从TypeList中将某种类型的元素全部移除. * @param TL 类型链表. * @param T 待移除元素的类型. * @return RemoveAll::Result 移除了全部的T后的类型链表结构. */ template<typename TL,typename T> struct RemoveAll; // 递归终止情况:走到末尾都没有发现指定元素. template<typename T> struct RemoveAll<NullType,typename Tail> struct RemoveAll<TypeList<T,T> { // 跳过当前节点,并继续递归遍历Tail之后的所有节点. typedef typename RemoveAll<Tail,T>::Result Result; }; // 当前节点既不是结尾,typename T> struct RemoveAll<TypeList<Head,typename RemoveAll<Tail,T>::Result> Result; }; /** * 移除重复的元素. * @param TL 类型链表. * @return RemoveDuplicates::Result 移除所有的重复类型之后的链表结构. */ template<typename TL> struct RemoveDuplicates; // 移除重复元素的处理过程,只接受TypeList的类型 template<typename Head,typename Tail> struct RemoveDuplicates< TypeList<Head,Tail> > { private: // 递归调用Tail之后的RemoveDuplicates操作,并存放在L1中. typedef typename RemoveDuplicates<Tail>::Result L1; // 从L1中删除掉所有当前节点的类型,并存放在L2中. typedef typename Remove<L1,Head>::Result L2; public: // 将当前节点和L2组合起来构成最终的结果. typedef TypeList<Head,L2> Result; }; /** * 替换指定类型的一个元素. * @param TL 类型链表. * @param T 待替换的类型. * @param U 替换成的类型. * @return Replace<TL,U>::Result 将TL中的第一个T类型元素替换成U类型后的链表结构. */ template<typename TL,typename U> struct Replace; // 递归终止情况:执行到了链表尾. template<typename T,typename U> struct Replace<NullType,U> { typedef NullType Result; }; // 递归终止情况:发现类型T的节点. template<typename T,typename U> struct Replace<TypeList<T,U> { // 将T换成U后返回. typedef TypeList<U,Tail> Result; }; // 当前节点既不是结尾,typename U> struct Replace<TypeList<Head,U> { // 递归调用. typedef TypeList<Head,typename Replace<Tail,U>::Result> Result; }; /** * 替换指定类型的全部元素. * @param TL 类型链表. * @param T 待替换的类型. * @param U 替换成的类型. * @return ReplaceAll<TL,U>::Result 将TL中全部的T类型元素替换成U类型后的链表结构. */ template<typename TL,typename U> struct ReplaceAll; // 递归终止情况:执行到了链表尾. template<typename T,typename U> struct ReplaceAll<NullType,typename U> struct ReplaceAll<TypeList<T,U> { // 将T换成U,并继续递归遍历Tail之后的所有节点. typedef TypeList<U,typename ReplaceAll<Tail,U>::Result> Result; }; // 当前节点既不是结尾,typename U> struct ReplaceAll<TypeList<Head,U>::Result> Result; }; /** * 判断TL1是否是TL2的一个子串,即TL1中的所有元素都在TL2中. * @param TL1 待检验的子串. * @param TL2 待检验的父串. * @return IsSubList<TL1,TL2>::value TL1是否是TL2的子串 */ template<typename TL1,typename TL2> struct IsSubList; // 递归终止情况:执行到了链表尾. template<typename TL2> struct IsSubList<NullType,TL2> { // 如果遍历完了都没有发现TL1中有节点不在TL2中,则返回true. static const bool value = true; }; // 当前节点不是尾节点. template<typename Head,typename TL2> struct IsSubList<TypeList<Head,TL2> { private: // 在TL2中查询当前节点在TL2中的索引,并保存在idx中.如果为-1则表示不存在. static const int idx = IndexOf<TL2,Head>::value; public: // 如果当前节点不再TL2中,则直接返回false.否则继续递归. static const bool value = Select<idx == -1,BoolToType<false>,IsSubList<Tail,TL2>>::Result::value; }; }

　　值得注意的是其中实现了一些功能例如ReplaceAll和IsSubList是在Modern C++ Design中没有实现的。而IsSubList在拓扑排序中被用于检查某一项的所有依赖项是否都被解决了。

　　基础部分就是这些，下面将讲述拓扑排序的具体执行过程了。在拓扑排序的过程中，使用了两个类型链表：一个是排好序的类型链表，一个是还未排好序的类型链表。

　　排序流程是这样的：

　　1.遍历整个类型链表，找到第一个满足如下条件的节点i：对于节点i的类型，其依赖的类型链表属于排好序链表的子串（利用上文提出的IsSubList可以执行这个判断，并且如果某一项依赖类型链表为空，则它可以是任何类型链表的子串），记录下这个节点i。

　　2.如果i类型是排序链表的子串，则说明i类型所代表的模块之前的依赖项都被处理了，则将i从未排序链表中删除，并放到排序链表中，然后重复1，这个过程将一直持续到未排序链表为空才结束。

　　3.如果过程1在遍历整个链表都没有发现任何一个满足条件的节点，说明出现了循环依赖关系，这时候直接返回一个NullType作为错误报告。

　　下面是实现该算法的具体代码：

/** * 在未解决的模块列表中查询一个可用项,其依赖列表中的元素要么全部都 * 在SortedTL中,要么依赖链表为空. * @param UnsortedTL 未排序的模块链表. * @param SortedTL 已排序的模块链表. * @return FindNoDependencies<TL>::Result 查找到的项.如果返回NullType * 代表没有找到该项. */ template<typename UnsortedTL,typename SortedTL> struct FindAvailable; // 递归终止情况:执行到了链表尾. template<typename SortedTL> struct FindAvailable<NullType,SortedTL> { typedef NullType Result; }; // 当前节点不是尾节点. template<typename Head,typename SortedTL> struct FindAvailable<TypeList<Head,SortedTL> { private: // 判断当前节点是否可用. static const bool isAvailable = TL::IsSubList< typename ModuleDescriptor<Head>::dependencies,SortedTL>::value; public: // 如果可用则直接返回当前节点,否则继续递归. typedef typename Select<isAvailable,Head,typename FindAvailable<Tail,SortedTL>::Result>::Result Result; }; /** * 执行模块之间的依赖排序操作. * @param TL 保存模块标签的类型链表. */ template<typename UnsortedTL,typename SortedTL> struct SortModuleListImpl; // 递归终止情况:未排序链表为空 template<typename SortedTL> struct SortModuleListImpl<NullType,SortedTL> { typedef SortedTL Result; }; // 如果还没有处理完所有没有依赖到的项. template<typename Head,typename SortedTL> struct SortModuleListImpl<TypeList<Head,SortedTL> { private: // 查找可用的节点,保存在L1中. typedef typename FindAvailable<TypeList<Head,SortedTL>::Result L1; // 从未排序链表中删除该项,并将结果保存在L2中. typedef typename TL::Remove<TypeList<Head,L1>::Result L2; // 向排序链表中添加该项,并将结果保存在L3中. typedef typename TL::Append<SortedTL,L1>::Result L3; public: // 递归继续执行排序操作,直到没有找到任何一个为止. typedef typename Select<IsNullType<L1>::value,NullType,typename SortModuleListImpl<L2,L3>::Result>::Result Result; }; template<typename TL> struct SortModuleList { private: typedef TYPELIST_0() SortedTypeList; public: typedef typename SortModuleListImpl<TL,SortedTypeList>::Result Result; };

　　只要将各个模块的标签放入类型链表中，并调用SortModuleList，它就会自动帮你完成编译期的拓扑排序工作。

　　还剩下一个简单的问题是如何根据这个排好序的类型列表正向地执行初始化的工作以及逆向地执行清理工作。如果你上面的都看懂了，那利用模板特化循环一个TypeList实在是太简单了：

/** * 按照模块链表的顺序执行初始化操作,* 按照模块链表的逆序执行清理操作. */ template<typename ModuleList> struct DoModule; // 循环的终止条件 template<> struct DoModule<NullType> { static void Init(){} static void Shutdown(){} }; // 执行循环 template<typename Head,typename Tail> struct DoModule< TypeList<Head,Tail> > { public: static void Init() { ModuleDescriptor<Head>::Init(); DoModule<Tail>::Init(); } static void Shutdown() { DoModule<Tail>::Shutdown(); ModuleDescriptor<Head>::Shutdown(); } };

这样就实现了编译期拓扑排序.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!