引入线索约束的设计模式变体挖掘研究*

肖卓宇，何 锫，徐运标，陈 果，郭 杰，黄 俊

(1.湖南工业职业技术学院信息工程学院,湖南 长沙 410208;2.广州大学计算机科学与网络工程学院，广东 广州 510006;3.湖南工业职业技术学院机械工程学院,湖南 长沙 410208)

1 引言

Erich等[1]提出了3类共计23种经典设计模式，并被广泛应用于软件设计。设计模式挖掘有助于理解、维护和重构大中型复杂软件系统，能有效减少软件项目研发成本，缩短软件系统研发周期，故在逆向工程领域有着重要的意义[2,3]。为此，众多国内外学者的研究工作围绕设计模式挖掘展开[4 - 6]。

Chihada等[7，8]将C4.5、SVM等机器学习算法引入到设计模式挖掘领域。Yu等[9]关注了结构型设计模式特征序列。肖卓宇等[10]提出了基于可视化文法约束的设计模式识别方法。Mayvan等[11]基于图论原理，并通过多阶段语义约束实现设计模式挖掘。Petterson等[12]提出设计模式变体是影响工具挖掘有效性的重要因素。文献[13]总结了8种标准Bridge设计模式演化后的典型变体。文献[14]依据GOF(Gang Of Four)设计模式分类原则，分3类总结了4种结构型Proxy设计模式变体、4种行为型Command设计模式变体和7种创建型Factory Method设计模式变体。文献[11,12,15]初步归纳了设计模式变体的普遍性规则，并对设计模式演化后的变体挖掘及其主要影响因素进行了前期研究。文献[16]基于谓词逻辑对设计模式进行了描述。

Figure 1 Steps of variant mining of design pattern with clue constraint

总体而言，目前研究工作对设计模式变体的关注比较缺乏，尚未形成全面、清晰的认识。主要问题归纳为以下3点：

(1)缺乏对设计模式变体的进一步研究。

(2)设计模式案例库缺乏对设计模式变体挖掘的支持。

(3)现有工具或方法对设计模式变体挖掘的结果不够精确。

为此，本文提出引入线索约束的设计模式变体挖掘方法，基于约束满足问题CSP(Constraint Satisfaction Problem)[17]的设计模式表示形式，分结构特征约束与时序特征约束2个阶段引入线索，实现对设计模式变体的挖掘。此外，通过精选的4种主流设计模式挖掘工具与4种基准系统进行了设计模式挖掘实验。

本文主要贡献：

(1)区别于以往仅关注标准设计模式挖掘的方法，本文以设计模式变体为专题，提出引入线索约束的设计模式变体挖掘方法。

(2)提出分结构特征约束、时序特征约束2阶段引入特征线索的思路。

(3)实验设计阶段提出单个变体挖掘实验与集成变体挖掘实验，以提升本文研究的信度与效度。

文章余下部分组织如下：第2节给出了设计模式变体挖掘主要步骤；第3节对特征归纳阶段进行了深入的阐述；第4节描述了特征约束阶段中结构特征约束与时序特征约束的CSP表示与存储；第5节描述了源码挖掘的主要步骤；第6节设计了单个变体挖掘实验与集成变体挖掘实验；第7节对本文工作进行总结，并探讨了未来的主要工作。

2 设计模式变体挖掘步骤

本文研究分为特征归纳、特征约束和源码挖掘3个阶段，如图1所示。

(1) 特征归纳阶段工作包括对Erich等提出的创建型、行为型及结构型3类共计23种标准设计模式进行CSP[17]的中间结果表示；此外，需要依据文献[11,12,15]对设计模式变体挖掘结果进行分析归纳，进而映射为CSP中间结果表示。

(2)特征约束阶段工作包括结构特征约束、时序特征约束及改进P-mart[18]案例库。结构特征约束主要分析与归纳设计模式变体的参与者、属性和方法等非动态的普遍性特征；时序特征约束主要分析设计模式变体参与者间的委托和时序等普遍性动态特征；改进P-mart[18]案例库主要实现结构特征约束和时序特征约束后的特征线索存储。

(3)源码挖掘阶段主要通过文献[17]的工作获取设计模式变体的候选参与者，接着使用工具DEMIMA(DEsign Motif Identification Multilayered Approach)[19]将设计模式变体的候选参与者映射为CSP中间表示，通过DPVMC(Design Pattern Variant Mining with Clue)算法分结构特征约束、时序特征约束2个阶段对参与者及其之间的关系特征进行筛选，进而与改进后的设计模式案例库P-mart[18]进行匹配，从而实现对标准设计模式及其变体的挖掘。

3 特征归纳阶段

文献[17]提出CSP约束集概念，CSP可通过特征约束对传统的23种标准设计模式进行有效表示[12,17]。此外，由于软件研发规模的扩大及应用场景的多元化，标准设计模式在处理特定场景问题时的局限性逐渐显露。为此，领域专家与研发人员为更方便地实现软件系统设计，对标准设计模式在不改变设计意图的原则下进行演化，衍生出了设计模式变体。设计模式变体能够更加高效地解决特定场景问题，但传统设计模式挖掘方法难以有效识别设计模式变体，因此，设计模式变体挖掘成为了领域研究的热点之一。表1给出了其中部分主要的约束集符号。本文以表1的CSP约束集符号为基础，进行设计模式线索约束表示。

Table 1 CSP constraints of notations

3.1 标准设计模式的CSP表示

Erich 等提出创建型、行为型和结构型3类共计23种标准设计模式，每种设计模式都具有不同的意图、动机和结构等。Guéhéneuc 等[19]提出基于约束满足问题CSP的设计模式约束集表示符号。本文以Command模式为例，对其进行CSP中间结果表示。图2为标准的Command模式，包括Command、Invoker等4个设计模式类参与者及其之间的关系。通过文献[17]变量集、约束集和域集等步骤的处理，其中，变量集可获取设计模式参与者类、属性和接口等信息；约束集关注不同设计模式参与者之间的关系特征；域集可将筛选后的设计模式参与者及其关系归纳成设计模式挖掘的候选参与者，最终，可将图2中标准设计模式描述为表2所示内容。

Figure 2 Standard command design pattern

Table 2 Constraints representation of standard Command pattern

3.2 设计模式变体的CSP表示

设计模式变体可理解为标准设计模式在不改变设计意图的前提下进行了演化，即一个设计模式的多个版本[12]。部分国内外研究团队对设计模式变体有初步研究，并对设计模式变体的规则和特征等进行了初步分析与归纳[11,12,16]，但仍需进一步多元、全面和系统的研究。

图3给出了一个典型的Command设计模式变体，与图2中标准Command设计模式相比，图3a虚线框中增加了Receiver1和Receiver2 2个设计模式类参与者，事实上由于子类Receiver1、子类Receiver2与父类Receiver存在继承关系，故Receiver1和Receiver2中的方法action可以复写其父类Receiver中的action方法，即增加图3b中的子类Receiver1与父类Receiver及Receiver2与父类Receiver间的2条虚线，进而形成与类ConcreteCommand的关联关系。

Figure 3 Command design pattern variant

传统设计模式挖掘工具或方法处理这类变体问题略显不足，而本文通过增加这些有价值的特征线索能够有效实现图3c与图3d中的Command设计模式变体的挖掘。

DPVMC算法描述了具体的设计模式变体挖掘思路，该算法以面向对象源码为输入，通过移除不存在关系的参与者缩减计算空间，进而分结构特征约束和时序特征约束2个阶段引入特征线索，最终实现设计模式变体挖掘结果的输出，如算法1所示。

算法1DPVMC

Input:Java source code of object-oriented software/*输入面向对象的Java程序源码*/

Output:instances of design pattern//输出设计模式实例

1:Extract participants containing pattern instances by CSP//抽取设计模式参与者信息，并用CSP表示

2:{class,interface,attribute,method}→participants/*参与者集包含了类、接口、属性和方法等信息*/

3:{Inheritance,Realization,dependency,association,aggregation,composition}→relationships/*参与者间关系集，包括继承、实现、依赖、关联、聚合和组合关系*/

4:If(participants not exist relationships)/*参与者间不存在任何关系*/

5: Remove participants/*移除不存在关系的参与者信息*/

6:ElseIf(participants exist multilayer relationship)//参与者是否存在多层关系

7:Foreach participant in relationshipsdo/*遍历优化后参与者集中的每个参与者*/

8:If(clue is static)//如果是静态线索

9: Adding structural feature constraint clues by CSP/*增加结构特征约束线索，并用CSP表示*/

10:Else//如果是动态线索

11: Adding temporal feature constraints clues by CSP/*增加时序特征约束线索，并用CSP表示*/

12:endIF

13: Matching repository of P-mart/*匹配P-mart设计模式案例库*/

14:EndFor

15:EndIF

16:returninstances of design pattern/*实现设计模式变体挖掘，给出返回值*/

表3对图3中的Command设计模式变体进行了CSP中间结果表示，表3中加粗部分为Command设计模式变体特征线索的CSP表示。如第11和第12行表示Receiver类派生出了Receiver1与Receiver2 2个子类，第14行和第16行分别表示子类中存在一个action方法，第15行和第17行表示子类中的action可复写父类中的action方法。

Table 3 Constraints representation of Command pattern variant

4 特征约束阶段

在特征归纳阶段首先将Erich 等提出的23种标准设计模式和设计模式变体通过工具DEMIMA[19]映射为CSP中间表示。该阶段已初步具备一定的设计模式变体挖掘能力，但总体而言具有局限性与主观性。为此，特征约束阶段将依据文献[11,12,15,16]归纳的普遍性特征，并通过线上线下调研行业专家进行多轮次论证，将本阶段分为结构特征约束和时序特征约束2个子阶段。结构型特征约束阶段关注参与者等基本静态特征信息的挖掘；时序特征约束阶段侧重于处理存在有严格时间节点约束的参与者间的动态特征信息挖掘。

4.1 结构特征约束

结构特征约束主要负责处理设计模式包含的参与者类、接口和方法等扮演的角色映射关系。此外，这些角色间的关系也是关注的重点。本文对主流设计模式工具的挖掘结果进行了详细的分析，并结合文献[11,12,15]的研究成果，通过文献[17]中提出的候选者特征线索选取方法，归纳了20条特征线索，并选取其中出现频次较高的10条特征线索进行了CSP中间结果表示，如表4中的S1至S10所示。

4.2 时序特征约束

结构特征约束侧重于静态信息的归纳，有助于结构型设计模式变体挖掘，但行为型与创建型设计模式变体由于存在方法或参数调用的前后关系、前置与后置等条件的时序限制，故仅关注静态信息，存在不足之处。为此，时序特征约束阶段将侧重关注动态信息的特征线索表示。该项工作有助于行为型和创建型设计模式变体挖掘。本文对主流设计模式工具的挖掘结果进行了详细的分析，结合文献[11,12,15]研究成果，也通过文献[17]中的候选者特征线索选取方法，归纳了16条特征线索，并选取其中出现频次较高的9条特征线索进行了CSP中间结果表示，如表5中的D1～D9所示。

4.3 P-mart设计模式基准案例库

Guéhéneuc等[18]通过手工形式对Jhotdraw,Junit和QuickUML等经典设计模式基准系统中的设计模式案例增加标签，从而形成P-mart设计模式基准案例库[18]。本文研究将结构特征约束阶段归纳的10种CSP特征线索表示和时序特征约束阶段归纳的9种CSP特征线索表示存储到P-mart案例库。

Table 4 Structural feature constraints

Table 5 Temporal feature constraints

5 源码挖掘阶段

源码挖掘阶段以面向对象的源程序为输入，通过文献[17]进行设计模式候选参与者筛选，以期删除与其余参与者类或接口不存在关系或关系不重要的参与者，从而减少CSP中间结果表示的转换时间成本，并生成设计模式参与者与扮演角色的映射关系。最后，通过与P-mart[18]案例库匹配实现设计模式变体挖掘。

6 实验设计

本文实验设计在单个设计模式变体和集成设计模式变体2个层面展开。其中，单个变体实验主要对典型单一结构型、行为型与创建型设计模式变体进行逐个挖掘；集成变体实验主要针对ApacheAnt等基准系统中的设计模式变体进行挖掘。

表6给出了本文进行实验比较的设计模式挖掘工具，工具选择依据为：(1)行业具有广泛影响力；(2)支持面向对象的Java程序源码；(3)使用了主流的基准系统进行挖掘实验，便于数据的交叉比较。实验环境计算机CPU选择6核Intel i7-8700K处理器，主频为3.8 GHz，内存为32 GB，操作系统为Windows 10。

Table 6 Parameters of design pattern mining tool

6.1 单个设计模式变体挖掘实验

文献[13,14]按结构型、行为型与创建型分类归纳了4种结构型Proxy变体、8种Bridge结构型变体、4种行为型Command变体和7种创建型Factory Method变体[14]。单个设计模式变体挖掘实验将对这3类共计23种变体进行挖掘。表7中“√”表示变体挖掘成功，“×”表示变体挖掘失败。由表7可知：

Table 7 Mining individual design pattern variant

(1)5种方法或工具对Proxy变体、Bridge变体、Command变体与Factory Method变体的平均挖掘准确率依次为60%,55%,45%和25.71%。经过分析发现Proxy变体与Bridge变体属于结构型设计模式变体，由于结构型变体没有复杂的动态时序约束，故挖掘难度要小于行为型Command变体与创建型Factory Method变体的挖掘难度。

(2)本文方法和PINOT、DPJF、F.T.、DPRE工具对3类共计23个变体的平均挖掘准确率依次为86.96%,4.35%,43.48%,47.8%和47.8%。经过分析发现，由于本文不仅关注了静态线索，同时也关注了动态线索，并在实现上通过结构特征约束和时序特征约束阶段进行特征线索的引入，故取得了相对较好的设计模式变体挖掘结果。

(3) 本文方法对行为型模式Command变体的平均挖掘准确率为75%，低于本文方法的综合平均挖掘准确率(86.96%)，甚至要低于创建型Factory Method变体的平均挖掘准确率(85.71%)。通过研究发现，创建型模式不仅要考虑到时序机制，甚至要关注设计模式参与者间的委托机制，故原则上挖掘难度更大。虽然本文方法取得了较好的效果，但仍需更多的实例及更大的数据集进行实验验证。

(4) 5种方法对创建型Factory Method变体3的平均挖掘准确率为0%。通过研究发现Factory Method变体3返回选定的 product 类时，被设计模式参与者角色间的附加关系[23,24]影响，易导致挖掘失败。后续工作考虑将附加关系作为主题，厘析其与结构型、行为型与创建型设计模式的关系，并归纳变体特征线索。

6.2 集成设计模式变体挖掘实验

为了验证本文方法对软件系统的挖掘效果，选用行业内具有代表性的ApacheAnt等4个经典开源系统(如表8所示，其中KLOC(Thousand Lines Of Code)表示代码千行数)进行集成设计模式变体挖掘实验。选用ApacheAnt等经典系统的原因为：(1)众多课题相关研究皆使用这些系统，便于挖掘结果的交叉验证；(2)课题组邀请行业专家多轮次交流与验证发现，这4个经典系统中不仅存在较为丰富的3类标准设计模式案例，同时也存在验证所需的变体案例；(3)课题组熟悉设计模式案例所在的位置与目录，如表9给出了JHotDraw7.0中4个Command设计模式参与者的目录位置信息。

Table 8 Parameters of open source systems

在6.1节单个设计模式变体实验中，设计模式挖掘工具F.T[22]和DPRE[1]由于可一定程度上支持静态与动态机制，故取得了相对较好的挖掘效果。为此，集成设计模式变体挖掘实验将进一步将本文方法与这2种效果较好的主流经典设计模式挖掘工具进行比较。

表10中NA表示不存在该类模式，分析表10结果可知：

(1)本文方法在单个设计模式变体挖掘实验和集成设计模式变体挖掘实验的拟合度较好；

(2)设计模式参与者角色间存在的附加关系是影响设计模式变体挖掘成功主要因素之一；

(3)设计模式参与者扮演多个角色易导致设计模式变体挖掘失败；

(4)部分未考虑到的设计模式特征线索约束表示问题，需要通过更大的数据集进行归纳。

6.3 设计模式变体挖掘主要影响因素

通过单个设计模式变体挖掘实验与集成设计模式变体挖掘实验分析发现一些共性问题，归纳如下：

(1)3类设计模式变体挖掘的难易程度依次为创建型最大，行为型次之，结构型较易；

Table 9 Directory location of Command design patterns in JHotDraw 7.0

Table 10 Experiment on mining variant of integrated design patterns

(2)设计模式参与者间的关系挖掘受时序机制影响，对创建型模式挖掘的影响尤为明显；

(3)设计模式参与者间的某些附加关系可能改变设计意图，易导致假阴性变体挖掘结果产生；

(4)多个设计模式实例间可能存在共享同一个参与者角色的现象，也易导致挖掘结果准确率出现偏差。

7 结束语

本文提出引入线索约束的设计模式变体挖掘方法，分结构特征约束与时序特征约束2个阶段引入线索，给出了DPVMC算法，并通过4个经典设计模式挖掘工具与4个开源系统进行了单个设计模式变体挖掘实验和集成设计模式变体挖掘实验。未来工作将致力于探究设计模式附加关系对设计模式变体挖掘的影响、设计模式变体基准案例库的建构、设计模式参与者间时序机制的进一步分类归纳[25]、设计模式推荐[26]机制等热点问题的研究。