引入線索約束的設計模式變體挖掘研究*

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

(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]機制等熱點問題的研究。