肖卓宇，何 锫，陳 果，徐運標，郭 杰

(1.湖南工業(yè)職業(yè)技術學院 信息工程學院，湖南 長沙 410208；2.廣州大學 計算機科學與網(wǎng)絡工程學院，廣東 廣州 510006)

0 引 言

基于設計模式挖掘的逆向工程有助于從遺產(chǎn)系統(tǒng)中獲取有價值的信息，并能提升軟件設計師對程序的理解[1,2]。為此，業(yè)內(nèi)專家提出眾多工具、方法對設計模式進行挖掘[3-5]，文獻[6]提出一種軟件設計模式分簇方法，方法有助于對參與者及存在的關系進行分類。文獻[7]提出基于文法關系驅(qū)動的設計模式變體檢測方法。文獻[8]提出基于本體匹配的設計模式挖掘方法。文獻[9]基于圖論與語義提出兩階段的設計模式挖掘方法。文獻[10]通過圖論原理，以積分Matrix Grade評估原則檢測設計模式。文獻[11]基于子模式對特征信息進行機器學習，以提升設計模式挖掘評估指標的有效性。文獻[12]描述與驗證了8種Bridge設計模式變體。文獻[13]歸納了設計模式變體的普遍性特征，為設計模式檢測提供了理論支持。文獻[14]關注了非標準設計模式，能較好解決設計模式實例重疊問題。

綜上所述，主流設計模式挖掘方法存在幾點問題：忽視了設計模式變體對評估結(jié)果的影響；對設計模式變體缺乏分類歸納；缺乏設計模式變體基準的歸納，基準庫也不夠完善；缺乏簡明有效的設計模式變體挖掘方法。

Gamma將GOF設計模式分為結(jié)構(gòu)型、行為型、創(chuàng)建型3類，被廣泛推崇[4]。近些年，研發(fā)人員將標準GOF設計模式演化為不同的版本(即：變體[12])，并應用于不同的專業(yè)領域。變體遵循不改變軟件設計意圖的原則，雖有助于提升軟件研發(fā)效率，但也給設計模式挖掘領域帶來了新問題[13]。為此，提出引入特征規(guī)則的設計模式變體挖掘方法，通過大類圖拆分方法[15]獲取設計模式參與者及其關系，然后，依據(jù)設計模式的軟件分簇方法[6]對設計模式參與者及關系進行分類，接著，在此分類基礎上進一步引入特征規(guī)則信息到課題組前期工作[16]，進而實現(xiàn)對設計模式變體的挖掘。

研究主要貢獻：提出引入特征規(guī)則的設計模式變體挖掘方法；基于GOF設計模式分類對變體挖掘的難易程度進行了深入研究；設計了單例與綜合變體挖掘?qū)嶒炦M行驗證。

1 設計模式變體挖掘步驟

步驟1 依據(jù)逆向工程中的大類圖拆分方法[15]對軟件系統(tǒng)類圖進行分解，獲取參與者等信息；

步驟2 在步驟1基礎上依據(jù)設計模式分簇方法[6]對參與者角色等信息分類；

步驟3 通過作者先前工作[16]對步驟2進行挖掘，并獲取優(yōu)化后的參與者集、關系集、約束集；

步驟4 引入特征規(guī)則信息至作者先前工作方法[16]；

步驟5 將步驟4取得結(jié)果與模式庫特征匹配。

2 逆向工程中的大類圖拆分方法

文獻[15]提出逆向工程中的大類圖拆分方法能一定程度上篩選類圖中和其它角色不存在關系的參與者，降低算力成本。圖1(a)給出用例類圖實例，包括Subject等8個類參與者，但事實上Proxy類參與者起著重要的代理作用，從而導致AbstractSubject、RealSubjectA兩個類和其余6個類不存在明顯關系，通過逆向工程中的大類圖拆分方法將圖1(a)精簡為只包含6個類的圖1(b)，此時依據(jù)課題組先前工作[16]圖1(b)方框中的標準的Proxy模式被成功挖掘。

圖1 Proxy模式變體挖掘步驟

3 設計模式指導的軟件分簇方法

王林章等[6]提出一種設計模式指導的軟件分簇方法，該方法采用分而治之的策略指導對程序中蘊含的設計模式信息分簇。圖1(b)中類RealSubjectB、RealSubjectC、RealSubjectD繼承了RealSubject類，通過設計模式指導的軟件分簇方法可將RealSubjectB、RealSubjectC、RealSubjectD這3個類歸納為同類參與者角色，因為三者的功能作用相近，如圖1(c)所示。設計模式信息分簇可為后續(xù)特征機制的引入節(jié)約成本，并有助于提升設計模式變體挖掘的精確率。

4 引入特征機制的設計模式變體描述

項目組先前工作提出基于文法產(chǎn)生式優(yōu)化的設計模式識別方法[16]，該方法優(yōu)點在于能夠較好識別標準的GOF設計模式，也能初步識別較典型的設計模式變體，缺點在于對變體識別的精確率較低。為此，提出一種引入特征機制的設計模式變體挖掘方法，旨在引入特征規(guī)則進行約束，并將之描述為文獻[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，不大于設計模式參與者類的總個數(shù)。

式(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，不大于設計模式參與者類的總個數(shù)。j∈[0,Classi.Method]，j表示方法的取值不能大于方法所屬類Classi的方法總數(shù)，也不能小于0。

定義3 參與者間聯(lián)系的定義

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

(3)

式中：Relationship表示參與者存在的關系，參與者之間的聯(lián)系包括聚合，關聯(lián)，繼承等。參與者間的聯(lián)系有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 存在繼承與關聯(lián)的復雜關系定義

?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存在關聯(lián)，Inhertance(Pj,Pk) 表示類或方法Pj與Pk存在繼承關系，故可以獲取Pi與Pk存在關聯(lián)的特征信息，即Association(Pi,Pk)。

4.2 實例描述

圖1(d)在圖1(c)的基礎上引入了特征規(guī)則，其中RealSubjectB、RealSubjectC、RealSubjectD這3個類參與者與另一個類參與者RealSubject皆存在繼承關系，先前工作[16]能夠?qū)ealSubjectB類遍歷，進而檢索到RealSubjectB類中所有的方法request()，此外，能挖掘出與RealSubjectB類存在繼承關系的參與者，但這些特征信息不足以挖掘出Proxy變體。依據(jù)定義1、定義3及定義5，由于RealSubject類參與者為RealSubjectB的基類，而Proxy類參與者與RealSubject類參與者存在關聯(lián)關系，故可在圖1(d)中為RealSubjectB與Proxy類參與者間增加一條虛線，表示二者也存在關聯(lián)關系，最終圖1(e)中的Proxy變體1被成功挖掘。同理，通過王林章等[6]提出設計模式指導的軟件分簇方法可知RealSubjectC、RealSubjectD兩個類參與者職能與RealSubjectB相似，故也可為RealSubjectC、RealSubjectD兩個類參與者分別與Proxy類參與者之間增加表示關聯(lián)的虛線，如圖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方法存在關聯(lián)，06行表示角色Subject、Proxy、RealSubject存在同名方法request。

而當通過引入特征機制后，結(jié)合圖1(d)虛線中的特征表示，最終Subject、Proxy、RealSubjectB可被成功挖掘，形成圖1(e)中Proxy變體1。表2以特征形式描述了Proxy變體1，與標準Proxy模式相比表2增加兩條特征信息，第一條見05行，增加了Subject與RealSubjectB的繼承關系；第二條見07行，增加了Proxy類參與者方法request與RealSubjectB類參與者方法request間的關聯(lián)。

表2 Proxy變體1特征描述

5 實驗設計

為驗證方法的效果，設計了單例變體挖掘?qū)嶒炁c綜合變體挖掘?qū)嶒?。挖掘工具選用依據(jù)主要考慮：①支持Java語言；②業(yè)內(nèi)認可度較高；③使用挖掘原理具有代表性，見表3。單例變體挖掘?qū)嶒炛饕獨w納文獻[9,10,12,14]變體，并通過項目組初審，邀請業(yè)內(nèi)專家復審，并最終確定了圖2所示變體，包括3種結(jié)構(gòu)型Proxy模式變體，兩種創(chuàng)建型Command模式變體，4種Factory Method模式變體。實驗環(huán)境操作系統(tǒng)為微軟Windows10，CPU為Intel 7500，內(nèi)存16 G。

表3 設計模式挖掘工具

5.1 單例變體挖掘?qū)嶒?/h3>

單例變體挖掘?qū)嶒瀸ο鬄閳D2所示的3類共計9個設計模式變體。表4中“Y”表示設計模式變體挖掘成功，“N”表示設計模式變體挖掘失敗。

圖2 3類設計模式變體

(1)主流工具對結(jié)構(gòu)型設計模式變體挖掘精確率相對較好，DeMIMA[9]、F.T[8]、DPRE[17]3種工具對Proxy模式的挖掘成功率依次分別為66.7%、100%、66.7%，究其原因工具DeMIMA[9]主要采用靜態(tài)分析機制，缺乏必要的動態(tài)分析。

(2)主流工具對結(jié)構(gòu)型設計模式變體挖掘精確率優(yōu)于行為型設計模式變體，由表4可知，DeMIMA[9]、F.T[8]、DPRE[17]這3種工具對兩種Command模式的挖掘成功率依次分別為0%、50%、50%，深入研究發(fā)現(xiàn)，DeMIMA[9]由于僅采用靜態(tài)分析機制，缺乏必要的動態(tài)分析，導致不能挖掘任意一種行為型Command模式，而F.T[8]能成功挖掘Command變體B，DPRE[17]能成功挖掘Command變體A，由于F.T[8]與DPRE[17]除開靜態(tài)分析機制還具備一定的動態(tài)分析能力，故對行為型模式Command變體挖掘的精確率優(yōu)于DeMIMA[9]，而新方法不僅關注動態(tài)、靜態(tài)分析，還對動態(tài)與靜態(tài)分析難以發(fā)現(xiàn)的規(guī)律，通過引入特征規(guī)則進行了有效補充，故能成功挖掘Command變體A與Command變體B，精確率達到100%。

(3)主流工具對結(jié)構(gòu)型設計模式變體挖掘精確率優(yōu)于創(chuàng)建型設計模式變體，由表4可知，DeMIMA[9]、F.T[8]、DPRE[17]這3種工具對兩種Command模式的挖掘成功率依次分別為0%、50%、50%，深入研究發(fā)現(xiàn)，DeMIMA[9]由于僅采用靜態(tài)分析機制，缺乏必要的動態(tài)分析，導致不能挖掘任意一種行為型Command模式，而F.T[8]能成功挖掘Command變體B，DPRE[17]能成功挖掘Command變體A，由于F.T[8]與DPRE[17]除開靜態(tài)分析機制還具備一定的動態(tài)分析能力，故對創(chuàng)建型模式Command變體挖掘的精確率優(yōu)于DeMIMA[9]，而新方法不僅關注動態(tài)、靜態(tài)分析，還對動態(tài)與靜態(tài)分析難以發(fā)現(xiàn)的規(guī)律，通過引入特征規(guī)則進行了有效補充，故能成功挖掘Command變體A與Command變體B，精確率達到100%。

(3)主流工具對創(chuàng)建型設計模式變體挖掘精確率優(yōu)于行為型設計模式變體，創(chuàng)建型設計模式中存在大量的委托、代理等關系，這類關系對時序有較嚴格的要求，并存在前后約束，因此挖掘難度高于結(jié)構(gòu)型與行為型設計模式變體。由表4可知，DeMIMA[9]、F.T[8]、DPRE[17]3種工具對4種Factory Method模式變體的挖掘成功率依次分別為0%、0%、25%，而本文方法能夠挖掘Factory Method模式變體B與Factory Method模式變體C，但成功率僅為50%，雖然通過引入特征機制的模式變體挖掘方法能夠一定程度上優(yōu)化挖掘結(jié)果，但對一些動態(tài)且時序結(jié)合的特征仍缺乏歸納，后續(xù)工作將重點關注并完善這個問題。

表4 單例變體挖掘

表4(續(xù))

5.2 綜合變體挖掘?qū)嶒?/h3>

由于開源系統(tǒng)中的設計模式變體挖掘?qū)嶒炐枰匀斯ば问津炞C設計模式變體數(shù)，為達到較好的效果與節(jié)約成本，待挖掘模式變體的開源系統(tǒng)選擇見表5。此外，選取5.1節(jié)單例變體實驗挖掘精確率相對理想的DPRE[17]、F.T[8]工具與本文方法一起對表5系統(tǒng)中設計模式變體進行開源系統(tǒng)挖掘?qū)嶒灐?/p>

表5 開源系統(tǒng)特征

表6中JRefactory 2.6.24系統(tǒng)被新方法、F.T[8]及DPRE[17]識別的Proxy變體數(shù)依次為7、2、1，究其原因發(fā)現(xiàn)，由于本文方法通過引入特征規(guī)則對結(jié)構(gòu)型變體特征信息進行了針對性的挖掘，加之結(jié)構(gòu)型模式特征沒有涉及時序、代理等機制，故該類模式變體挖掘的難度相對較易。而對于最難以挖掘的創(chuàng)建型Factory Method變體，由于QuickUML2001中不存在變體，事實上JRefactory 2.6.24與ApacheAnt 1.6.2中的創(chuàng)建型Factory Method變體幾乎無法成功被DPRE[17]工具挖掘。F.T[8]能夠識別JRefactory 2.6.24中的1個創(chuàng)建型變體Factory Method，較DPRE[17]有所改進，而本文方法能夠挖掘JRefactory 2.6.24中的2個創(chuàng)建型Factory Method變體，及ApacheAnt 1.6.2中的1個創(chuàng)建型變體Factory Method，挖掘結(jié)果優(yōu)于F.T[8]及DPRE[17]兩種工具?！?”表示變體不存在。

表6 綜合變體挖掘

6 效度分析

設計模式變體挖掘是程序理解領域的一個難點，為提升變體挖掘的精確率需注意以下事項：①變體的歸納應具有普遍性；②變體特征的挖掘需繼續(xù)不斷的深入；③變體挖掘的案例需要有規(guī)模性和代表性；④變體基準知識庫仍需不斷豐富；⑤變體挖掘的假陽性與假陰性結(jié)需篩選。⑥設計模式參與者間附加關系[18]對變體的影響。

7 結(jié)束語

提出引入特征規(guī)則的設計模式變體挖掘方法，通過逆向工程中的大類圖拆分方法[15]與設計模式指導的軟件分簇方法[6]對設計模式變體參與者及其關系進行篩選，依據(jù)特征規(guī)則將定義的特征信息引入文法產(chǎn)生優(yōu)化的設計模式識別方法[16]，設計模式變體挖掘工作取得了較好的效果。后續(xù)工作將致力于設計模式變體基準的完善、設計變體挖掘精確率的優(yōu)化、設計模式推薦[19]、設計模式附加關系識別等。