肖卓宇，何 锫，陳 果，徐運(yùn)標(biāo)，郭 杰

(1.湖南工業(yè)職業(yè)技術(shù)學(xué)院 信息工程學(xué)院，湖南 長(zhǎng)沙 410208；2.廣州大學(xué) 計(jì)算機(jī)科學(xué)與網(wǎng)絡(luò)工程學(xué)院，廣東 廣州 510006)

0 引 言

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

綜上所述，主流設(shè)計(jì)模式挖掘方法存在幾點(diǎn)問(wèn)題：忽視了設(shè)計(jì)模式變體對(duì)評(píng)估結(jié)果的影響；對(duì)設(shè)計(jì)模式變體缺乏分類(lèi)歸納；缺乏設(shè)計(jì)模式變體基準(zhǔn)的歸納，基準(zhǔn)庫(kù)也不夠完善；缺乏簡(jiǎn)明有效的設(shè)計(jì)模式變體挖掘方法。

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

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

1 設(shè)計(jì)模式變體挖掘步驟

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

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

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

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

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

2 逆向工程中的大類(lèi)圖拆分方法

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

圖1 Proxy模式變體挖掘步驟

3 設(shè)計(jì)模式指導(dǎo)的軟件分簇方法

王林章等[6]提出一種設(shè)計(jì)模式指導(dǎo)的軟件分簇方法，該方法采用分而治之的策略指導(dǎo)對(duì)程序中蘊(yùn)含的設(shè)計(jì)模式信息分簇。圖1(b)中類(lèi)RealSubjectB、RealSubjectC、RealSubjectD繼承了RealSubject類(lèi)，通過(guò)設(shè)計(jì)模式指導(dǎo)的軟件分簇方法可將RealSubjectB、RealSubjectC、RealSubjectD這3個(gè)類(lèi)歸納為同類(lèi)參與者角色，因?yàn)槿叩墓δ茏饔孟嘟鐖D1(c)所示。設(shè)計(jì)模式信息分簇可為后續(xù)特征機(jī)制的引入節(jié)約成本，并有助于提升設(shè)計(jì)模式變體挖掘的精確率。

4 引入特征機(jī)制的設(shè)計(jì)模式變體描述

項(xiàng)目組先前工作提出基于文法產(chǎn)生式優(yōu)化的設(shè)計(jì)模式識(shí)別方法[16]，該方法優(yōu)點(diǎn)在于能夠較好識(shí)別標(biāo)準(zhǔn)的GOF設(shè)計(jì)模式，也能初步識(shí)別較典型的設(shè)計(jì)模式變體，缺點(diǎn)在于對(duì)變體識(shí)別的精確率較低。為此，提出一種引入特征機(jī)制的設(shè)計(jì)模式變體挖掘方法，旨在引入特征規(guī)則進(jìn)行約束，并將之描述為文獻(xiàn)[16]特征表示形式，以提高設(shè)計(jì)模式變體挖掘的精確率。

4.1 引入特征機(jī)制的變體定義

引入特征機(jī)制的主體包括設(shè)計(jì)模式參與者集(Participant，P)、參與者中存在的方法集(Method，M)、以及參與者集P或其方法集M間存在的約束集(Constraint，C)等特征信息。

定義1 類(lèi)參與者定義

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

(1)

式(1)表示存在有價(jià)值的參與者ParticipantClass，后文皆簡(jiǎn)寫(xiě)為PC，PC扮演設(shè)計(jì)模式DesignPattern中的參與者類(lèi)。DesignPattern屬于一個(gè)集合，包含Adapter等23種典型的標(biāo)準(zhǔn)設(shè)計(jì)模式。i∈[0,max(DesignPattern.Class)]，i表示類(lèi)的取值范圍不小于0，不大于設(shè)計(jì)模式參與者類(lèi)的總個(gè)數(shù)。

式(2)表示存在有價(jià)值的參與者方法ParticipantMethod，后文皆簡(jiǎn)寫(xiě)為PM，PM扮演設(shè)計(jì)模式DesignPattern的參與者類(lèi)中存在的方法。DesignPattern為包含23種典型的標(biāo)準(zhǔn)設(shè)計(jì)模式集合。

定義2 方法參與者定義

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

(2)

i∈[0,max(DesignPattern.Class)]，i表示類(lèi)的取值范圍不小于0，不大于設(shè)計(jì)模式參與者類(lèi)的總個(gè)數(shù)。j∈[0,Classi.Method]，j表示方法的取值不能大于方法所屬類(lèi)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表示參與者存在的關(guān)系，參與者之間的聯(lián)系包括聚合，關(guān)聯(lián)，繼承等。參與者間的聯(lián)系有3種情形，可以是兩個(gè)類(lèi)參與者PC×PC， 也可以是一個(gè)類(lèi)參與者與一個(gè)方法參與者PC×PM， 也可為兩個(gè)方法參與者PM×PM。

定義4 參與者角色多層繼承關(guān)系的定義

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

(4)

式中：Pn表示設(shè)計(jì)模式中的第n個(gè)參與者，P可以為類(lèi)參與者PC，也可為類(lèi)中存在的方法參與者PM，Inhertance(Pi,Pj) 表示類(lèi)或方法Pi與Pj存在繼承關(guān)系，Inhertance(Pj,Pk) 表示類(lèi)或方法Pj與Pk也存在繼承關(guān)系，故可以獲取Pi與Pk也存在繼承的特征信息，即Inhertance(Pi,Pk)。

定義5 存在繼承與關(guān)聯(lián)的復(fù)雜關(guān)系定義

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

(5)

式中：Pn表示設(shè)計(jì)模式中的第n個(gè)參與者，P可以為類(lèi)參與者PC，也可為類(lèi)中存在的方法參與者PM，Association(Pi,Pj) 表示類(lèi)或方法Pi與Pj存在關(guān)聯(lián)，Inhertance(Pj,Pk) 表示類(lèi)或方法Pj與Pk存在繼承關(guān)系，故可以獲取Pi與Pk存在關(guān)聯(lián)的特征信息，即Association(Pi,Pk)。

4.2 實(shí)例描述

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

4.3 設(shè)計(jì)模式特征信息的表示

課題組先前工作[16]將設(shè)計(jì)模式描述為可視化文法特征形式，圖1(b)實(shí)線框中的標(biāo)準(zhǔn)Proxy可表示表1。

表1 標(biāo)準(zhǔn)Proxy特征

表1中01行GetAllClass特征可獲取Proxy設(shè)計(jì)模式中的3個(gè)類(lèi)參與者角色Proxy、RealSubject、Subject。02行可取得01行3個(gè)類(lèi)參與者各自存在的方法參與者request。03與04行表示Proxy與Subject、RealSubject與Subject兩組類(lèi)參與者間存在繼承關(guān)系，第05行描述Proxy的request方法與RealSubject的request方法存在關(guān)聯(lián)，06行表示角色Subject、Proxy、RealSubject存在同名方法request。

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

表2 Proxy變體1特征描述

5 實(shí)驗(yàn)設(shè)計(jì)

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

表3 設(shè)計(jì)模式挖掘工具

5.1 單例變體挖掘?qū)嶒?yàn)

單例變體挖掘?qū)嶒?yàn)對(duì)象為圖2所示的3類(lèi)共計(jì)9個(gè)設(shè)計(jì)模式變體。表4中“Y”表示設(shè)計(jì)模式變體挖掘成功，“N”表示設(shè)計(jì)模式變體挖掘失敗。

圖2 3類(lèi)設(shè)計(jì)模式變體

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

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

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

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

表4 單例變體挖掘

表4(續(xù))

5.2 綜合變體挖掘?qū)嶒?yàn)

由于開(kāi)源系統(tǒng)中的設(shè)計(jì)模式變體挖掘?qū)嶒?yàn)需要以人工形式驗(yàn)證設(shè)計(jì)模式變體數(shù)，為達(dá)到較好的效果與節(jié)約成本，待挖掘模式變體的開(kāi)源系統(tǒng)選擇見(jiàn)表5。此外，選取5.1節(jié)單例變體實(shí)驗(yàn)挖掘精確率相對(duì)理想的DPRE[17]、F.T[8]工具與本文方法一起對(duì)表5系統(tǒng)中設(shè)計(jì)模式變體進(jìn)行開(kāi)源系統(tǒng)挖掘?qū)嶒?yàn)。

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

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

表6 綜合變體挖掘

6 效度分析

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

7 結(jié)束語(yǔ)

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