基于DPS表达式类图的设计模式检测

肖卓宇，何 锫，黎 妍

（1.中南林业科技大学 涉外学院，湖南 长沙410042；2.广州大学 计算机科学与教育软件学院，广东 广州510006；3.湖南高速公路管理局，湖南 长沙410209）

0 引 言

目前存在多种检测设计模式［1］的技术与方法，周晓宇等提出了一套以准确和通用的设计模式识别技术为目标，以层次化特征及静态分析为基础的语义特征识别技术，并形成了一个兼顾语义特征及排除性约束的软件框架［2］；文献［3］提出一种对设计模式检测结果的精度进行评估的方法；文献 ［4］使用了抽象的建筑思维语言来记录设计模式的选择，但其主体的描述和代码分离，以至于很难被自动检测。

文献 ［5，6］提出对设计模式中主要角色的特征进行注释，该方法侧重了类结构，但对类关系的检测缺乏约束机制；文献 ［7］中允许开发者依据源码，通过面向方面的Java注释来对所开发软件进行不同设计模式的选择，提出了切点的概念，对类所承担不同职责的角色进行了细化，但缺乏对角色间变异关系的识别。

文献 ［8］基于Gamma的GOF模式分类，提出一种自动检测设计模式的方法，但该方法存在局限性，结构型模式检测效果较好，但很多创建型模式难以识别；文献 ［9］中指出的多种方法能够对文献 ［8］的不足之处进行改进，但缺乏对设计模式关系变异的考虑；作者先前的工作实现了对23种基于GOF 设计模式中不同角色间附加关系的研究，并对JhotDraw 系统中设计模式关系变异规则进行了检测与分析［10］。

文献 ［11］利用UML 类图对设计模式的抽取结构进行了表示，并评估其效果；Dong Jing等给出了基于模板的匹配方法，通过评估不同图形之间子图的相似性取代顶点相似性，但是在检测设计模式的变异方面效果较弱，仅适合标准化的设计模式［12］。

综上所述，这些设计模式检测方法或多或少存在如下问题：①缺乏对设计模式中变异关系的检测；②进行设计模式检测时，对于匹配算法的复杂度缺乏考虑；③检测中没有分情况对二者匹配的程度进行分析。为此，提出了一个基于DPS （design pattern string）表达式的设计模式检测方法。主要思路是将设计模式中的UML 类图模型转换为DPS表达式的字符串形式，同时引入子图同构匹配算法的思想来判断设计模式是否存在于原型设计系统中。

1 设计模式的DPS表示

如果将设计模式中的UML类图转换为一种图形，那么在其转换前需要对UML类图进行相关的处理，这是因为软件系统中的设计模式不会完全合乎GOF的23种典型模式，大多数情况下，甚至会出现设计模式中关系的变异，这将导致系统实现与功能目标的不一致［10］。这些关系的变异主要表现为类之间附加的关系（如：关联、泛化、聚合等）。

本文给出了2组图，一组是所研究系统的部分设计图，如图1所示，另外一组是其对应的设计模式关系图。这样做的优点在于减少了二者匹配的时间复杂度，并能在一定程度上检测出其它文献中所介绍方法不能识别的设计模式实例。所采用的软件系统用UML类图来设计，侧重关注3种关系 （即：关联、泛化、聚合），图1中相应的3种关系如图2～图4所示。

图1 软件系统UML类 （部分）

图2 系统中类的关联表示

图3 系统中类的泛化表示

图4 系统中类的聚合表示

其中图2～图4分别对应的邻接矩阵如下所示。

在进行系统设计的时候，设计模式的关系图可以用类似的方法被抽取出来，第3节中Singleton模式、Facade模式及Mediator模式有典型的应用。所有的关系图可以转换为DPS表达式字符串的形式，其定义如下

其中，R 表示类图之间的关系，a表示图中终节点，Ai表示非终结点 （即：存在迭代的节点），R 主要表示节点之间的关系 （association、generalization、aggregation）。转换算法见表1。

通过将表1算法应用到关系邻接矩阵，可以得出DPS表达式，其邻接矩阵系统设计关系图（如图2～图4所示），这3者DPS形式将对应关联、泛化、聚合关系，如式 （1）～式（3）所示

表1 Graph＿to＿DPS转换算法思想

设计模式的关系图可以用类似的方法提取，Singleton模式、Mediator模式、Facade 模式的关系图在第3 节中描述。

2 设计模式检测方法

2.1 基于子图同构的关系图检测

子图同构是一种常用的设计模式抽取匹配方法，它能够发现所给定图形的问题原型，称之为模式，另一个需要匹配的图形，谓之目标。在此，模式与目标分别对应设计模式的UML关系图与系统设计图。

如满足条件式 （4）与式 （5），关系R（R∈V1×V）表示G1＝G＝（V1，E1）是G＝（V，E）的一个子图。写作R：G1→G

条件式 （4）保证R 是V1 到V 的内射函数，条件式（5）确保R 中存在G1 的结构。在满足 （u1，v1）∈E1，（R（u1），R（v1））∈E，所有的u1，v1∈V1 的条件下，可以理解为内射函数R：V1→V 表示为G1→G 的子图同构。

所有图G1＝（V1，E1）到图G＝（V，E）的子图同构集可以表示为N 元关系S Vn其中｜V1｜＝n。所有子图同构的关系S定义如下： （v1，…vn）∈S，可推导出子图同构关系R：G1→G。R（）＝v1，R（）＝v2…R（）＝vn，其中∈G1，vn∈G，i＝1，2…n。

给出了两个图G1＝（V1，E1）和G＝（V，E）与｜V1｜＝n，Eij＝Vn表示基于V 的n元关系，即基于V 的互不相交的顶点，其中，这些顶点被加入一些G 中的弧

子图同构的关系S能够由式 （6）得出

上述将对子图同构的每种关系 （关联，泛化，聚合）各自单独进行检测，因此，需要了解对各种关系是否完全或者是部分存在于系统设计中，为此，引入一种匹配算法。算法中S1，S2，S3分贝对应泛化，关联，聚合3 种关系，文中主要关注这3种关系，其它关系也可通过类似方法进行编号。

design＿pattern＿detection算法思想见表2。

表2 design＿pattern＿detection算法思想

上述算法考虑到了3种关系的子图同构的检测，并给出设计模式到系统设计图的各种关系的映射值Fi，i的取值分别为1、2、3，其中F1对应泛化关系，F2对应关联关系，F3对应聚合关系，若Fi覆盖图中所有节点，可以理解为设计模式完全存在于系统中，即完全匹配；若Fi覆盖图中部分图中节点，理解为部分存在与系统，即局部匹配；否则，为不匹配。

2.2 基于子图同构的设计模式检测分类

GOF四人帮提出了23种经典设计模式，每种设计模式之间的关系能够通过UML 图表示出来，在检测了设计模式关系模型图的子图同构之后，可得出3种主要的情形：

（1）设计模式的关系图不是子图同构的模式图，这属于设计模式不存在的情形。

（2）设计模式的关系图到模型图是子图同构。这是设计模式存在下的情形。

（3）设计模式的关系图到模型图是部分子图同构。这是存在设计模式关系变异下的情形。

设计模式常用于软件的复用，第1节中介绍了设计模式转换为关系图的规则，进而形成了DPS 表达式形式。DPS表达式将被其相应的软件系统设计中对应的字符串搜索到。子字符串实质是一种子图同构的检测，其中要搜索的字符串对应于子图或更大的字符串，在此，搜索整个图形中较小的一个。图形匹配技术是非常重要且常用的一种模式匹配方法，所讨论的算法可以发现设计模式或存在变异关系的设计模式。

在上述情形 （2）中，设计模式的关系图部分存在于相应的系统设计关系图，更进一步说，关系图可以存在多个映射，这使得在系统设计中除了可以多次出现一个完整的设计模式之外，也可能出现设计模式中关系的变异。

值得注意的是，即使存在于设计模式中的DPS表达式已经对应了系统设计中DPS表达式，设计模式也无法完全与设计系统中的子图匹配，而导致其产生的原因是变异关系的保存条件不能够满足搜索。

3 设计模式实例检测

3.1 设计模式是否存在

这种方法的局限性在于它不能从类的角度出发，来判断并识别一些自身是否存在联系的设计模式，Singleton模式就是典型的代表，其UML图以及相应的关系如图5，图6所示。因为存在有一个自循环，所以不能被写成基于DPS表达式形式的字符串，以至于该检测方法不适合于这类设计模式。

图5 Singleton关联关系

图6 Singleton模式关系

3.2 设计模式完全匹配

如匹配到设计模式中的每个关系，设计模式被认为是完全匹配系统设计的一部分。在此，选择Facade模式来描述这个情形。UML 类如图7 所示，只有关联关系 （无聚合，泛化关系），其对应的关系如图8所示。

在搜索系统设计中的设计模式前，需要找出Facade模式的PDS表达式形式。通过应用基于邻接矩阵的Graph＿to＿DPS算法 （见表1），得到关系图 （如图8所示），其对应的DPS表达式如式 （7）、式 （8）所示

图7 Facade（装饰）模式

图8 Facade的关联关系

要了解它是否存在于系统设计中，首先考虑使用式（1），式 （7），式 （8）来得到系统设计中基于DPS表达式形式的关联关系。为此，对Facade模式的所有子图同构的关联关系进行计算。模式中的关系图 （如图8所示）作为G1，系统设计中的关系图 （如图2所示）作为G，G1中存在2条边，即：（a，b）与 （a，c）。因此，N 元关系包括了Ea，b＝ ｛（4，3，＊），（4，2，＊）｝，Ea，c＝ ｛（4，＊，3），（4，＊，2）｝，根据式 （6），S2＝Ea，b∩Ea，c＝ ｛（4，3，2），（4，2，3）｝。因此S2，1＝｛（a，4），（b，3），（c，2）｝，S2，2＝｛（a，4），（b，2），（c，3）｝，S2，3＝｛（a，4），（c，3），（b，2）｝，S2，4＝｛（a，4），（c，2），（b，3）｝。

同时，该模式没有涉及其它的关系，所以无需检测系统中其它关系的DPS表达式形式 （如泛化，聚合）。因此，依据表2算法，只需检测S2.对于每个S2i，可以得出Fi，因此F1＝ ｛（a，4），（b，3）， （c，2）｝，F2＝ ｛（a，4），（b，2），（c，3）｝，F3＝ ｛（a，4），（c，3），（b，2）｝，F4＝｛（a，4），（c，2），（b，3）｝。这样可以理解为Facade模式的4个关联关系实例存在于系统设计图中。同时，仅有的关联关系将减低设计模式变异发生的概率，从而使得检测工作的难度降低。

3.3 设计模式检测的部分匹配

如果没有匹配到设计模式中的每个关系，设计模式被认为是部分匹配到软件系统设计的子部分。而代表性的例子是中介者模式，其直接关联的关系图是系统设计相应的子图，但是其余的关系不是这种情况。如设计模式中的泛化关系图是断开的，当设计模式连接的时候，此时需要对系统设计的部分存在进行检测。

检测系统设计中的中介者模式 （如图9 所示）之前，需要挖掘基于DPS表达式形式的中介者模式，通过应用基于邻接矩阵的表1 算法，得到相应的两个图形 （如图10，图11所示），其对应的两个DPS 表达式 （如式 （9），式（10）所示）

图9 Mediator（中介者）模式

图10 Mediator模式泛化表示

图11 Mediator模式关联表示

为此，首先对Mediator模式的所有子图同构泛化关系进行计算。模式中的关系图 （如图10 所示）作为G1，系统设计中的泛化关系图 （如图3所示）作为G，G1中存在3条边，即：（e，a），［（d，b），（d，c）］。因此，N 元关系包括了Ed，b＝ ｛（1，2，＊），（1，3，＊）｝，Ed，c＝ ｛（1，＊，2），（1，＊，3）｝，根 据 式 （6），S1＝Eb，d∩Ec，d＝｛（1，2，3），（1，3，2）｝。因此S1，1＝ ｛（d，1），（b，2），（c，3）｝，S1，2＝ ｛（d，1），（b，3），（c，2）｝，S1，3＝ ｛（d，1），（c，2），（b，3）｝，S1，4＝ ｛（d，1），（c，3），（b，2）｝。

依据表2算法，检测S1.对于每个S1i，可以得出Fi，F1＝ ｛（d，1），（b，2）， （c，3）｝，F2＝ ｛（d，1）， （b，3），（c，2）｝，F3＝ ｛（d，1）， （c，2）， （b，3）｝，F4＝｛（d，1），（c，3），（b，2）｝。

这样可以理解为Mediator模式目前4个可能的泛化关系实例存在于系统设计模型图中，但是Ee，a＝ ｛（1，2），（1，3）｝，无继承分支，可理解为无共同的基类，导致不能匹配。依据式 （2）与式 （9），两个基于泛化的DPS表达式将映射成如下形式 ｛［（d，1），（b，2），（c，3）］，［（d，1），（b，3），（c，2）］，［（d，1），（c，2），（b，3）］，［（d，1），（c，3），（b，2）］｝，而 ［（e，＊），（a，＊）］映射不能对应起来。这是因为该映射不包含该设计模式泛化关系图的所有顶点，因此可以认为泛化关系是局部的匹配。

除此之外，同样需要关注Mediator模式的所有子图同构的关联关系。模式中的关系图 （如图11所示）作为G1，系统设计中的关联关系图 （如图2所示）作为G，G1中存在3条边，即：（d，e），［（a，b），（a，c）］。因此，N 元关系包括了Ea，b＝ ｛（4，2，＊），（4，3，＊）｝，Ea，c＝ ｛（4，＊，2）， （4，＊，3）｝，根 据 式 （6），S1＝Ea，b∩Ea，c＝｛（4，2，3），（4，3，2）｝因此S2，1＝ ｛（a，1），（b，2），（c，3）｝，S2，2＝ ｛（a，1），（b，3），（c，2）｝，S2，3＝ ｛（a，1），（c，2），（b，3）｝，S2，4＝ ｛（a，1），（c，3），（b，2）｝，依据表2算法，检测S2.对于每个S2i，可以得出Fi，F1＝｛（a，1），（b，2），（c，3）｝，F2＝ ｛（a，1），（b，3），（c，2）｝，F3＝ ｛（a，1），（c，2），（b，3）｝，F4＝ ｛（a，1），（c，3），（b，2）｝。

可以理解为Mediator模式4个关联关系实例存在于系统设计模型图中，另外，Ed，e＝ ｛（5，4）｝，其对应的系统设计图的映射是节点5到节点1，并未存在关联关系，这使得和图2只是部分映射，根据式 （6），得出S2，5＝Φ （表示为空），因此，Mediator模式中的关联关系和系统设计的关联关系是局部的匹配，最终映射没有覆盖设计模式中的所有顶点，也可理解为中介者模式存在关系的变异［10］。

聚合关系在Mediator模式中未有体现，所以也不能和图4的基于DPS的聚合关系映射起来，暂不作考虑。

4 结束语

文章提出了一种检测设计模式的算法，通过把类之间的关系有向图转换为基于DPS表达式形式的字符串，而后利用基于子图同构的DPS表达式形式子串的组合与经典的GOF设计模式匹配，在此基础上依据目标类与模式类匹配的不同程度分3种情况来检测设计模式。工作取得了一定的效果，但是该方法不能检测存在自循环关系的设计模式，今后的工作中将不断的完善原型系统，并通过JHOTDraw、ArgoUML、Junit等经典的设计模式测试系统对这3种不同的情况进行验证，并为大型遗产系统的重构提供有力支持。

［1］Rasool G，Philippow I，Ader PM.Design pattern recovery based on annotations［J］.Adv Eng Softw，2010，34 （4）：519－526.

［2］ZHOU Xiaoyu，XU Baowen.New research framework for au－tomatic recovery of design pattern ［J］.Computer Science，2009，36 （5）：124－128 （in Chinese）. ［周晓宇，徐宝文.一个设计模式自动识别技术研究框架 ［J］.计算机科学，2009，36 （5）：124－128.］

［3］Pettersson N，L we W，Nivre J.Evaluation of accuracy in design pattern occurrence detection ［J］.IEEE Transactions on Software Engineering，2010，36 （4）：575－590.

［4］Garlan D，Monroe R，Wile D.Acme：An architecture description interchange language ［C］／／CASCON 1st Decade High Impact Papers，IBM，2010：159－173.

［5］Rasool G，Philippow I.Design pattern recovery based on annotations［J］.Adv Eng Softw，2010，41 （4）：519－526.

［6］Sabo M，Poruban J.Preserving design patterns using source code annotations［J］.Journal of Computer Science and Control Systems，2009，32 （2）：53－56.

［7］Calvagn A，Tramontana E.Delivering dependable reusable components by expressing and enforcing design decisions［C］／／Proceedings of Computer Software and Applications Conference Workshop QUORS，2013：493－498.

［8］Gueheneuc YG，Antoniol G.DeMIMA：A multilayered approach for design pattern Identication ［J］.IEEE Transactions on Software Engineering，2008，34 （5）：667－684.

［9］Dong J，Zhao Y，Peng T.A review of design pattern mining techniques［J］.International Journal of Software Engineering and Knowledge Engineering，2009，16 （6）：823－855.

［10］XIAO Zhuoyu，HE Pei，LI Yan.Study on the extra relationships based on design pattens’s roles ［J］.Application Research of Computers，2015，32 （7）：2042－2045 （in Chinese）.［肖卓宇，何锫，黎妍.基于设计模式角色的附加关系 检 测 研 究 ［J］.计 算 机 应 用 研 究，2015，32 （7）：2042－2045.］

［11］Porras GC，Gueheneuc YG.An empirical study on the efficiencey of different design pattern representations in UML class diagrams ［J］.Empirical Software Engineering，2010，15（5）：493－522.

［12］Dong J，Sun Y，Zhao Y.Design pattern detection by template matching ［C］／／Proceedings of the 23rd Annual ACM，Symposium on Applied Computing，2008：765－769.