引入特征机制的设计模式变体挖掘方法

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

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

0 引 言

基于设计模式挖掘的逆向工程有助于从遗产系统中获取有价值的信息，并能提升软件设计师对程序的理解[1,2]。为此，业内专家提出众多工具、方法对设计模式进行挖掘[3-5]，文献[6]提出一种软件设计模式分簇方法，方法有助于对参与者及存在的关系进行分类。文献[7]提出基于文法关系驱动的设计模式变体检测方法。文献[8]提出基于本体匹配的设计模式挖掘方法。文献[9]基于图论与语义提出两阶段的设计模式挖掘方法。文献[10]通过图论原理，以积分Matrix Grade评估原则检测设计模式。文献[11]基于子模式对特征信息进行机器学习，以提升设计模式挖掘评估指标的有效性。文献[12]描述与验证了8种Bridge设计模式变体。文献[13]归纳了设计模式变体的普遍性特征，为设计模式检测提供了理论支持。文献[14]关注了非标准设计模式，能较好解决设计模式实例重叠问题。

综上所述，主流设计模式挖掘方法存在几点问题：忽视了设计模式变体对评估结果的影响；对设计模式变体缺乏分类归纳；缺乏设计模式变体基准的归纳，基准库也不够完善；缺乏简明有效的设计模式变体挖掘方法。

Gamma将GOF设计模式分为结构型、行为型、创建型3类，被广泛推崇[4]。近些年，研发人员将标准GOF设计模式演化为不同的版本(即：变体[12])，并应用于不同的专业领域。变体遵循不改变软件设计意图的原则，虽有助于提升软件研发效率，但也给设计模式挖掘领域带来了新问题[13]。为此，提出引入特征规则的设计模式变体挖掘方法，通过大类图拆分方法[15]获取设计模式参与者及其关系，然后，依据设计模式的软件分簇方法[6]对设计模式参与者及关系进行分类，接着，在此分类基础上进一步引入特征规则信息到课题组前期工作[16]，进而实现对设计模式变体的挖掘。

研究主要贡献：提出引入特征规则的设计模式变体挖掘方法；基于GOF设计模式分类对变体挖掘的难易程度进行了深入研究；设计了单例与综合变体挖掘实验进行验证。

1 设计模式变体挖掘步骤

步骤1 依据逆向工程中的大类图拆分方法[15]对软件系统类图进行分解，获取参与者等信息；

步骤2 在步骤1基础上依据设计模式分簇方法[6]对参与者角色等信息分类；

步骤3 通过作者先前工作[16]对步骤2进行挖掘，并获取优化后的参与者集、关系集、约束集；

步骤4 引入特征规则信息至作者先前工作方法[16]；

步骤5 将步骤4取得结果与模式库特征匹配。

2 逆向工程中的大类图拆分方法

文献[15]提出逆向工程中的大类图拆分方法能一定程度上筛选类图中和其它角色不存在关系的参与者，降低算力成本。图1(a)给出用例类图实例，包括Subject等8个类参与者，但事实上Proxy类参与者起着重要的代理作用，从而导致AbstractSubject、RealSubjectA两个类和其余6个类不存在明显关系，通过逆向工程中的大类图拆分方法将图1(a)精简为只包含6个类的图1(b)，此时依据课题组先前工作[16]图1(b)方框中的标准的Proxy模式被成功挖掘。

图1 Proxy模式变体挖掘步骤

3 设计模式指导的软件分簇方法

王林章等[6]提出一种设计模式指导的软件分簇方法，该方法采用分而治之的策略指导对程序中蕴含的设计模式信息分簇。图1(b)中类RealSubjectB、RealSubjectC、RealSubjectD继承了RealSubject类，通过设计模式指导的软件分簇方法可将RealSubjectB、RealSubjectC、RealSubjectD这3个类归纳为同类参与者角色，因为三者的功能作用相近，如图1(c)所示。设计模式信息分簇可为后续特征机制的引入节约成本，并有助于提升设计模式变体挖掘的精确率。

4 引入特征机制的设计模式变体描述

项目组先前工作提出基于文法产生式优化的设计模式识别方法[16]，该方法优点在于能够较好识别标准的GOF设计模式，也能初步识别较典型的设计模式变体，缺点在于对变体识别的精确率较低。为此，提出一种引入特征机制的设计模式变体挖掘方法，旨在引入特征规则进行约束，并将之描述为文献[16]特征表示形式，以提高设计模式变体挖掘的精确率。

4.1 引入特征机制的变体定义

引入特征机制的主体包括设计模式参与者集(Participant，P)、参与者中存在的方法集(Method，M)、以及参与者集P或其方法集M间存在的约束集(Constraint，C)等特征信息。

定义1 类参与者定义

∀ParticipantClass∈DesignPattern.Classi.DesignPattern={Adapter∨Command∨Factory Method∨Proxy...}.

(1)

式(1)表示存在有价值的参与者ParticipantClass，后文皆简写为PC，PC扮演设计模式DesignPattern中的参与者类。DesignPattern属于一个集合，包含Adapter等23种典型的标准设计模式。i∈[0,max(DesignPattern.Class)]，i表示类的取值范围不小于0，不大于设计模式参与者类的总个数。

式(2)表示存在有价值的参与者方法ParticipantMethod，后文皆简写为PM，PM扮演设计模式DesignPattern的参与者类中存在的方法。DesignPattern为包含23种典型的标准设计模式集合。

定义2 方法参与者定义

∀ParticipantMethod∈DesignPattern.Classi.Methodj.Methodj⊂DesignPattern.Classi.DesignPattern={Adapter∨Command∨Factory Method∨Proxy...}.

(2)

i∈[0,max(DesignPattern.Class)]，i表示类的取值范围不小于0，不大于设计模式参与者类的总个数。j∈[0,Classi.Method]，j表示方法的取值不能大于方法所属类Classi的方法总数，也不能小于0。

定义3 参与者间联系的定义

Relationship:{Aggregation,Associate,Inherit,...}
PC×PC,PC∈{Class}
PC×PM,PC∈{Class},PM∈{Class.Method}
PM×PM,PM∈{Class.Method}

(3)

式中：Relationship表示参与者存在的关系，参与者之间的联系包括聚合，关联，继承等。参与者间的联系有3种情形，可以是两个类参与者PC×PC， 也可以是一个类参与者与一个方法参与者PC×PM， 也可为两个方法参与者PM×PM。

定义4 参与者角色多层继承关系的定义

∃Inhertance(Pi,Pj)∧∃Inhertance(Pj,Pk)
→∃Inhertance(Pi,Pk)
Pn∈[PCn∨PMn],n∈[0≤i,j,k≤n]

(4)

式中：Pn表示设计模式中的第n个参与者，P可以为类参与者PC，也可为类中存在的方法参与者PM，Inhertance(Pi,Pj) 表示类或方法Pi与Pj存在继承关系，Inhertance(Pj,Pk) 表示类或方法Pj与Pk也存在继承关系，故可以获取Pi与Pk也存在继承的特征信息，即Inhertance(Pi,Pk)。

定义5 存在继承与关联的复杂关系定义

∃Association(Pi,Pj)∧∃Inhertance(Pj,Pk)
→∃Association(Pi,Pk)
Pn∈[PCn∨PMn],n∈[0≤i,j,k≤n]

(5)

式中：Pn表示设计模式中的第n个参与者，P可以为类参与者PC，也可为类中存在的方法参与者PM，Association(Pi,Pj) 表示类或方法Pi与Pj存在关联，Inhertance(Pj,Pk) 表示类或方法Pj与Pk存在继承关系，故可以获取Pi与Pk存在关联的特征信息，即Association(Pi,Pk)。

4.2 实例描述

图1(d)在图1(c)的基础上引入了特征规则，其中RealSubjectB、RealSubjectC、RealSubjectD这3个类参与者与另一个类参与者RealSubject皆存在继承关系，先前工作[16]能够对RealSubjectB类遍历，进而检索到RealSubjectB类中所有的方法request()，此外，能挖掘出与RealSubjectB类存在继承关系的参与者，但这些特征信息不足以挖掘出Proxy变体。依据定义1、定义3及定义5，由于RealSubject类参与者为RealSubjectB的基类，而Proxy类参与者与RealSubject类参与者存在关联关系，故可在图1(d)中为RealSubjectB与Proxy类参与者间增加一条虚线，表示二者也存在关联关系，最终图1(e)中的Proxy变体1被成功挖掘。同理，通过王林章等[6]提出设计模式指导的软件分簇方法可知RealSubjectC、RealSubjectD两个类参与者职能与RealSubjectB相似，故也可为RealSubjectC、RealSubjectD两个类参与者分别与Proxy类参与者之间增加表示关联的虚线，如图1(d)所示，最终图1(e)中 Proxy变体2与Proxy变体3被成功挖掘。

4.3 设计模式特征信息的表示

课题组先前工作[16]将设计模式描述为可视化文法特征形式，图1(b)实线框中的标准Proxy可表示表1。

表1 标准Proxy特征

表1中01行GetAllClass特征可获取Proxy设计模式中的3个类参与者角色Proxy、RealSubject、Subject。02行可取得01行3个类参与者各自存在的方法参与者request。03与04行表示Proxy与Subject、RealSubject与Subject两组类参与者间存在继承关系，第05行描述Proxy的request方法与RealSubject的request方法存在关联，06行表示角色Subject、Proxy、RealSubject存在同名方法request。

而当通过引入特征机制后，结合图1(d)虚线中的特征表示，最终Subject、Proxy、RealSubjectB可被成功挖掘，形成图1(e)中Proxy变体1。表2以特征形式描述了Proxy变体1，与标准Proxy模式相比表2增加两条特征信息，第一条见05行，增加了Subject与RealSubjectB的继承关系；第二条见07行，增加了Proxy类参与者方法request与RealSubjectB类参与者方法request间的关联。

表2 Proxy变体1特征描述

5 实验设计

为验证方法的效果，设计了单例变体挖掘实验与综合变体挖掘实验。挖掘工具选用依据主要考虑：①支持Java语言；②业内认可度较高；③使用挖掘原理具有代表性，见表3。单例变体挖掘实验主要归纳文献[9,10,12,14]变体，并通过项目组初审，邀请业内专家复审，并最终确定了图2所示变体，包括3种结构型Proxy模式变体，两种创建型Command模式变体，4种Factory Method模式变体。实验环境操作系统为微软Windows10，CPU为Intel 7500，内存16 G。

表3 设计模式挖掘工具

5.1 单例变体挖掘实验

单例变体挖掘实验对象为图2所示的3类共计9个设计模式变体。表4中“Y”表示设计模式变体挖掘成功，“N”表示设计模式变体挖掘失败。

图2 3类设计模式变体

(1)主流工具对结构型设计模式变体挖掘精确率相对较好，DeMIMA[9]、F.T[8]、DPRE[17]3种工具对Proxy模式的挖掘成功率依次分别为66.7%、100%、66.7%，究其原因工具DeMIMA[9]主要采用静态分析机制，缺乏必要的动态分析。

(2)主流工具对结构型设计模式变体挖掘精确率优于行为型设计模式变体，由表4可知，DeMIMA[9]、F.T[8]、DPRE[17]这3种工具对两种Command模式的挖掘成功率依次分别为0%、50%、50%，深入研究发现，DeMIMA[9]由于仅采用静态分析机制，缺乏必要的动态分析，导致不能挖掘任意一种行为型Command模式，而F.T[8]能成功挖掘Command变体B，DPRE[17]能成功挖掘Command变体A，由于F.T[8]与DPRE[17]除开静态分析机制还具备一定的动态分析能力，故对行为型模式Command变体挖掘的精确率优于DeMIMA[9]，而新方法不仅关注动态、静态分析，还对动态与静态分析难以发现的规律，通过引入特征规则进行了有效补充，故能成功挖掘Command变体A与Command变体B，精确率达到100%。

(3)主流工具对结构型设计模式变体挖掘精确率优于创建型设计模式变体，由表4可知，DeMIMA[9]、F.T[8]、DPRE[17]这3种工具对两种Command模式的挖掘成功率依次分别为0%、50%、50%，深入研究发现，DeMIMA[9]由于仅采用静态分析机制，缺乏必要的动态分析，导致不能挖掘任意一种行为型Command模式，而F.T[8]能成功挖掘Command变体B，DPRE[17]能成功挖掘Command变体A，由于F.T[8]与DPRE[17]除开静态分析机制还具备一定的动态分析能力，故对创建型模式Command变体挖掘的精确率优于DeMIMA[9]，而新方法不仅关注动态、静态分析，还对动态与静态分析难以发现的规律，通过引入特征规则进行了有效补充，故能成功挖掘Command变体A与Command变体B，精确率达到100%。

(3)主流工具对创建型设计模式变体挖掘精确率优于行为型设计模式变体，创建型设计模式中存在大量的委托、代理等关系，这类关系对时序有较严格的要求，并存在前后约束，因此挖掘难度高于结构型与行为型设计模式变体。由表4可知，DeMIMA[9]、F.T[8]、DPRE[17]3种工具对4种Factory Method模式变体的挖掘成功率依次分别为0%、0%、25%，而本文方法能够挖掘Factory Method模式变体B与Factory Method模式变体C，但成功率仅为50%，虽然通过引入特征机制的模式变体挖掘方法能够一定程度上优化挖掘结果，但对一些动态且时序结合的特征仍缺乏归纳，后续工作将重点关注并完善这个问题。

表4 单例变体挖掘

表4(续)

5.2 综合变体挖掘实验

由于开源系统中的设计模式变体挖掘实验需要以人工形式验证设计模式变体数，为达到较好的效果与节约成本，待挖掘模式变体的开源系统选择见表5。此外，选取5.1节单例变体实验挖掘精确率相对理想的DPRE[17]、F.T[8]工具与本文方法一起对表5系统中设计模式变体进行开源系统挖掘实验。

表5 开源系统特征

表6中JRefactory 2.6.24系统被新方法、F.T[8]及DPRE[17]识别的Proxy变体数依次为7、2、1，究其原因发现，由于本文方法通过引入特征规则对结构型变体特征信息进行了针对性的挖掘，加之结构型模式特征没有涉及时序、代理等机制，故该类模式变体挖掘的难度相对较易。而对于最难以挖掘的创建型Factory Method变体，由于QuickUML2001中不存在变体，事实上JRefactory 2.6.24与ApacheAnt 1.6.2中的创建型Factory Method变体几乎无法成功被DPRE[17]工具挖掘。F.T[8]能够识别JRefactory 2.6.24中的1个创建型变体Factory Method，较DPRE[17]有所改进，而本文方法能够挖掘JRefactory 2.6.24中的2个创建型Factory Method变体，及ApacheAnt 1.6.2中的1个创建型变体Factory Method，挖掘结果优于F.T[8]及DPRE[17]两种工具。“/”表示变体不存在。

表6 综合变体挖掘

6 效度分析

设计模式变体挖掘是程序理解领域的一个难点，为提升变体挖掘的精确率需注意以下事项：①变体的归纳应具有普遍性；②变体特征的挖掘需继续不断的深入；③变体挖掘的案例需要有规模性和代表性；④变体基准知识库仍需不断丰富；⑤变体挖掘的假阳性与假阴性结需筛选。⑥设计模式参与者间附加关系[18]对变体的影响。

7 结束语

提出引入特征规则的设计模式变体挖掘方法，通过逆向工程中的大类图拆分方法[15]与设计模式指导的软件分簇方法[6]对设计模式变体参与者及其关系进行筛选，依据特征规则将定义的特征信息引入文法产生优化的设计模式识别方法[16]，设计模式变体挖掘工作取得了较好的效果。后续工作将致力于设计模式变体基准的完善、设计变体挖掘精确率的优化、设计模式推荐[19]、设计模式附加关系识别等。