魏金津 任女爾 蔡建軍

摘要：現(xiàn)在軟件項(xiàng)目越來越龐大，歷史項(xiàng)目也因文檔缺失，結(jié)構(gòu)不清晰等原因很難被開發(fā)者理解。為了能讓軟件開發(fā)者深入了解系統(tǒng)結(jié)構(gòu)，增強(qiáng)開發(fā)者軟件重構(gòu)、復(fù)用的能力，我們研發(fā)設(shè)計(jì)模式檢測(cè)技術(shù)并作為插件集成進(jìn)SonarQube，和代碼質(zhì)量檢測(cè)、代碼克隆檢測(cè)、解耦檢測(cè)等一起作為技術(shù)債務(wù)進(jìn)行管理，對(duì)軟件開發(fā)過程具有重要的工程意義與實(shí)踐指導(dǎo)作用。

關(guān)鍵詞：UML圖 圖論；設(shè)計(jì)模式檢測(cè)；相似度算法

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）28-0165-03

1 概述

現(xiàn)在汽車行業(yè)軟件系統(tǒng)越來越復(fù)雜龐大，識(shí)別系統(tǒng)所用到的設(shè)計(jì)模式對(duì)于軟件設(shè)計(jì)者理解系統(tǒng)架構(gòu)非常重要，為進(jìn)一步改進(jìn)系統(tǒng)結(jié)構(gòu)，軟件復(fù)用提供基礎(chǔ)。普通的設(shè)計(jì)模式檢測(cè)算法只能識(shí)別基本模式而不能識(shí)別基本模式上的改進(jìn)模式，并且系統(tǒng)過于龐大時(shí)效率也不高，使用相似度算法可以識(shí)別改進(jìn)模式并且提高效率。

軟件行業(yè)內(nèi)常將Sonar作為技術(shù)債務(wù)【1】管控的主流工具，Sonar插件式模式，方便自身被其他平臺(tái)所引入，且有利于擴(kuò)展第三方插件。我們可以開發(fā)插件對(duì)檢測(cè)結(jié)果進(jìn)行再加工處理，除了增強(qiáng)代碼質(zhì)量檢測(cè)粒度，還可以在設(shè)計(jì)上對(duì)代碼進(jìn)行設(shè)計(jì)模式、解耦等檢測(cè)。

自動(dòng)檢測(cè)系統(tǒng)設(shè)計(jì)模式的過程叫作設(shè)計(jì)模式檢測(cè)，是從設(shè)計(jì)級(jí)別檢測(cè)軟件質(zhì)量，實(shí)現(xiàn)基于Sonar的設(shè)計(jì)模式自動(dòng)檢測(cè)技術(shù)，有利于軟件開發(fā)與設(shè)計(jì)人員理解系統(tǒng)設(shè)計(jì)，指導(dǎo)軟件項(xiàng)目設(shè)計(jì)改進(jìn)。

系統(tǒng)類之間的關(guān)系可以由UML類圖表示，類圖本質(zhì)上是有向圖，可以對(duì)應(yīng)到鄰接矩陣。我們基于相似度計(jì)算的UML圖匹配算法研發(fā)設(shè)計(jì)模式檢測(cè)技術(shù)，計(jì)算待檢測(cè)系統(tǒng)和設(shè)計(jì)模式所表示矩陣的相似度，生成檢測(cè)到的模式實(shí)例的列表。

我們將設(shè)計(jì)模式檢測(cè)軟件以插件的形式集成到SonarQube中，與其他技術(shù)債務(wù)一起進(jìn)行掃描，并將實(shí)時(shí)測(cè)試結(jié)果反映給開發(fā)人員，從而提高系統(tǒng)設(shè)計(jì)的質(zhì)量。

2 圖論和UML圖

圖（Graph）可以定義為一組稱為頂點(diǎn)（vertex）的對(duì)象，由稱為邊（edge）的鏈接所連接。圖幾乎可以用來表現(xiàn)所有類型的結(jié)構(gòu)和系統(tǒng)，從交通、通信網(wǎng)絡(luò)，社交、生物網(wǎng)絡(luò)到計(jì)算機(jī)科學(xué)中都有廣闊的用武之地。

圖論（Graph Theory）【2】是數(shù)學(xué)的一個(gè)分支，主要研究圖的屬性，對(duì)圖形屬性的研究對(duì)于理解底層軟件系統(tǒng)的特性在許多方面都很有價(jià)值。

面向?qū)ο笙到y(tǒng)使用類作為模塊分析，設(shè)計(jì)和實(shí)現(xiàn)系統(tǒng)，其體系結(jié)構(gòu)可以由一個(gè)或多個(gè)UML圖所表示。

UML（Unified Model Language） 【3】，中文叫作統(tǒng)一建模語言，可以用來對(duì)面向?qū)ο笙到y(tǒng)進(jìn)行可視化的說明、描述。包括用例圖、類圖、對(duì)象圖、序列圖、協(xié)作圖等等，其中最常見的是類圖，UML類圖不僅可以對(duì)系統(tǒng)中所有類的屬性和方法進(jìn)行描述，最重要的是能描述類之間的關(guān)系，常見的有依賴、泛化、關(guān)聯(lián)、聚合、組合、實(shí)現(xiàn)等關(guān)系。

UML類圖可以完美地映射到圖論的圖，圖的頂點(diǎn)（vertice）代表類，邊（edge）可以對(duì)應(yīng)到關(guān)聯(lián)、泛化、組合等UML類圖關(guān)系。

有向圖G=（V， E）可以表示面向?qū)ο笙到y(tǒng)的類圖，頂點(diǎn)集（V）對(duì)應(yīng)于系統(tǒng)中的所有類集合，邊集（E）對(duì)應(yīng)于這些類之間關(guān)系的集合，比如有向邊（p， q）∈E表示類p與q的關(guān)聯(lián)關(guān)系方向是從p到q。類的所有關(guān)系（包括泛化、關(guān)聯(lián)、組合）都可以表示成類圖，下圖是張簡(jiǎn)單的類圖：

我們可以用矩陣來完全地描述任何有向圖，這就是有向圖的鄰接矩陣，如下圖：

3 設(shè)計(jì)模式檢測(cè)

設(shè)計(jì)模式（Design Pattern）是特定情境下特定問題的一般解決方案。使用設(shè)計(jì)模式，可以建立一個(gè)結(jié)構(gòu)良好、可維護(hù)和可重用的軟件系統(tǒng)。現(xiàn)在汽車行業(yè)的軟件系統(tǒng)架構(gòu)非常復(fù)雜并且包含大量的組件，歷史項(xiàng)目也因文檔不齊以及結(jié)構(gòu)不清晰等問題，很難理解這些系統(tǒng)的軟件結(jié)構(gòu)。設(shè)計(jì)模式檢測(cè)【4】有益于理解這些系統(tǒng)的設(shè)計(jì)，并為進(jìn)一步的改進(jìn)提供基礎(chǔ)。

在設(shè)計(jì)模式檢測(cè)之前，我們需要對(duì)待檢測(cè)系統(tǒng)和設(shè)計(jì)模式結(jié)構(gòu)進(jìn)行建模，因?yàn)轭悎D是一種可以被完美映射到矩陣的有向圖，并且對(duì)矩陣的操縱也很容易，所以我們選擇矩陣對(duì)面向?qū)ο笤O(shè)計(jì)的類之間的關(guān)系進(jìn)行建模。

GoF提出了23種經(jīng)典的設(shè)計(jì)模式，如觀察者模式，代理模式，單例模式，抽象工廠模式等等，這些基本設(shè)計(jì)模式都有其基本結(jié)構(gòu)，但是在實(shí)際軟件開發(fā)中，設(shè)計(jì)模式并不經(jīng)常遵循于基本結(jié)構(gòu)（有時(shí)還會(huì)定義自己的設(shè)計(jì)模式），可以稱為改進(jìn)型設(shè)計(jì)模式。所以我們引入基于相似度計(jì)算的UML圖匹配算法（Graph Similarity Algorithm），將待檢測(cè)系統(tǒng)和模式圖作為輸入以計(jì)算其鄰接矩陣的相似度得分。這種方式的主要優(yōu)勢(shì)是不僅能檢測(cè)基本設(shè)計(jì)模式還能檢測(cè)在基本設(shè)計(jì)模式上改進(jìn)過的設(shè)計(jì)模式。

要表示的系統(tǒng)實(shí)體的關(guān)系或?qū)傩匀Q于設(shè)計(jì)者想檢測(cè)的模式的具體特征，我們想表示的有關(guān)聯(lián)，泛化，抽象類，抽象方法調(diào)用，對(duì)象創(chuàng)建。然而相似度算法并不取決于所使用的特定類型的矩陣，只要能將系統(tǒng)或模式描述為矩陣設(shè)計(jì)者可以將輸入?yún)?shù)設(shè)為任何類型。

我們使用Java語言開發(fā)了一個(gè)檢測(cè)程序，使用前需要選擇待檢測(cè)系統(tǒng)的classes文件根路徑和待檢測(cè)的設(shè)計(jì)模式，便可自動(dòng)化的使用上面提到的設(shè)計(jì)模式檢測(cè)算法（下面會(huì)說明），生成檢測(cè)到的模式實(shí)例的列表。該檢測(cè)程序以Sonar插件形式開發(fā)并集成進(jìn)SonarQube和代碼質(zhì)量、代碼克隆等技術(shù)債務(wù)一起進(jìn)行掃描檢測(cè)。

4 計(jì)算兩圖之間的相似度算法

1）兩個(gè)有向圖GA和GB分別具有NA和NB頂點(diǎn)，GA描述設(shè)計(jì)模式，GB描述系統(tǒng)。定義相似度矩陣S為一個(gè)NB*NA矩陣。S的每個(gè)元素s（i，j）表示的是GB中頂點(diǎn)i和GA中頂點(diǎn)j的相似度。

2）計(jì)算S的算法公式如下：

（1） 設(shè)Z0為一個(gè)元素均為1的NB*NA矩陣。

（2） 迭代：[Ζk+1=BZkAT+BTZkA∥BZkAT+BTZkA∥1]

其中，有向圖GA、GB的鄰接矩陣表示為A、B；分母表示矩陣的1-范式（矩陣的1范數(shù)，即：矩陣的每一列上的元素絕對(duì)值先求和，再從中取個(gè)最大的，（列和最大））；迭代的終止條件是矩陣Z收斂。[knAnBeAnA+eBnB]

3）算法復(fù)雜度：ea、eb代表的是有向圖的邊的數(shù)量。

4）選擇該算法的原因：在設(shè)計(jì)模式檢測(cè)的情景下，這個(gè)圖相似度計(jì)算算法，可以用來檢測(cè)圖GA和圖GB的頂點(diǎn)之間的相似度。為了保證最后檢測(cè)結(jié)果的準(zhǔn)確性，最后將矩陣歸一化來表示相似度（相似度取值范圍[0，1]）。

5 圖匹配算法

精確圖匹配算法（Exact Graph Matching Algorithm）：該算法就是尋找同構(gòu)圖，即具有相同節(jié)點(diǎn)數(shù)，相關(guān)邊緣也要一一對(duì)應(yīng)的圖。兩個(gè)同構(gòu)的圖其鄰接矩陣也相同。運(yùn)用設(shè)計(jì)模式檢測(cè)，就是檢測(cè)系統(tǒng)圖的所有和待檢測(cè)模式具有相同數(shù)量頂點(diǎn)的子圖。這是理想狀態(tài)下的算法，在實(shí)際軟件開發(fā)中，完全復(fù)制設(shè)計(jì)模式是不現(xiàn)實(shí)的，總要根據(jù)實(shí)際情況來進(jìn)行修改適應(yīng)，所以精確圖匹配算法在設(shè)計(jì)模式檢測(cè)領(lǐng)域并不適用。

非精確圖匹配算法（Inexact Graph Matching Algorithm）：當(dāng)無法找到兩個(gè)圖之間的同構(gòu)時(shí)可以應(yīng)用模糊匹配，即非精確圖匹配算法。該算法通過圖的編輯距離來計(jì)算圖與圖之間的相似程度。圖的編輯距離，大致可以理解為對(duì)匹配圖進(jìn)行多少次點(diǎn)、邊的操作可以與目標(biāo)圖一致。在設(shè)計(jì)模式匹配場(chǎng)景下，檢測(cè)結(jié)果將不準(zhǔn)確，如圖4。

SS1明顯是SS3設(shè)計(jì)模式的一種變種，但是編輯距離來講，SS2更小。

相似度算法（Similarity Scoring Algorithm）：以上兩種算法都不適用，所以我們使用基于相似度計(jì)算的UML圖匹配算法，該算法計(jì)算圖的鄰接矩陣的相似度。將UML圖拆分為泛化圖（Generalization Graph）和關(guān)聯(lián)圖（Association Graph），以下簡(jiǎn)稱g圖和a圖。g圖表示各類之間的繼承關(guān)系，a圖展示的是各類之間的聚集關(guān)系（如類A中有一個(gè)B類的實(shí)體，此時(shí)，a圖中A指向B）。

首先將上面圖3的UML按照a圖和g圖拆分開來：

然后分別計(jì)算出他們的鄰接矩陣：

之后將這個(gè)矩陣代入到1中的算法公式中，分別迭代獲得兩個(gè)片段的a/g圖對(duì)于待測(cè)設(shè)計(jì)模式的a/g圖的相似度：

[Genpattern，seg1=Similarity（Genpattern，Genseg1）=0.500.50.500.5]

[Assocpattern，seg1=Similarity（Assocpattern，Assocseg1）=100001]

[Genpattern，seg2=Similarity（Genpattern，Genseg2）=1001]

[Assocpattern，seg2=Similarity（Assocpattern，Assocseg2）=0000]

之后分別將每個(gè)片段的兩個(gè)相似度矩陣進(jìn)行相加，并且進(jìn)行歸一化，可以得到最終的相似度矩陣：

[NormScorespattern，seg2=Sumpattern，seg2?1k1001k2=1001?120012=0.5000.5]

[NormScorespattern，seg1=（Genpattern，seg1+Assocpattern，seg1）?1k1001k2=0.7500.250.2500.75]

之后我們可以看到，片段2中a，b兩個(gè)類（結(jié)點(diǎn)）和待測(cè)設(shè)計(jì)模式中的兩個(gè)類（結(jié)點(diǎn)）相似度均為0.5，在相對(duì)片段1中，A/C兩類的相似性和待測(cè)設(shè)計(jì)模式的相似性為0.75，所以得出結(jié)論，片段1相比片段2與待測(cè)設(shè)計(jì)模式的相似度更高。

6 設(shè)計(jì)模式檢測(cè)算法步驟

1）假設(shè)待檢測(cè)系統(tǒng)有數(shù)量為n的類，需要將系統(tǒng)的每個(gè)特性（如前文提到的a/g圖等等）都表示為一個(gè)獨(dú)立的n * n特征描述矩陣。

2）檢測(cè)繼承結(jié)構(gòu)。這里將每個(gè)繼承結(jié)構(gòu)抽象成一棵樹，特別地，如果某個(gè)類有多個(gè)父節(jié)點(diǎn)，那么該類會(huì)同時(shí)出現(xiàn)在多棵樹中，如下圖所示的C，C1，C2既屬于層次結(jié)構(gòu)1，也屬于層次結(jié)構(gòu)2。

3）構(gòu)建子系統(tǒng)矩陣。依據(jù)目標(biāo)設(shè)計(jì)模式來劃分子系統(tǒng)，如果目標(biāo)設(shè)計(jì)模式有且僅有單。

獨(dú)的繼承樹，那么步驟2中劃分出來的每一棵繼承樹都被視為一個(gè)子系統(tǒng)。如果目標(biāo)設(shè)計(jì)模式有多棵繼承樹組成，那么子系統(tǒng)將是步驟2中劃分出來的繼承樹的組合數(shù)。如：某設(shè)計(jì)模式有2棵繼承樹，待測(cè)項(xiàng)目供有m棵繼承樹，那么子系統(tǒng)的數(shù)量就是m（m-1）/2。

4）相似度算法的計(jì)算。此處計(jì)算每個(gè)子系統(tǒng)矩陣與待測(cè)設(shè)計(jì)模式的相似度，大致計(jì)算過程在第4節(jié)有描述，不再贅述。

5）降序排序相似度計(jì)算結(jié)果。每一個(gè)待測(cè)設(shè)計(jì)模式都會(huì)得到一個(gè)列表，根據(jù)這個(gè)列表里得分最高的類來提取設(shè)計(jì)模式檢測(cè)結(jié)果。

6）閾值選取問題。選取有一個(gè)假設(shè)：給定一個(gè)設(shè)計(jì)模式的實(shí)例，那么這個(gè)實(shí)例里，經(jīng)過修改的特征不會(huì)超過一個(gè)。所以假設(shè)某設(shè)計(jì)模式有x個(gè)特征，閾值就為（x-1）/x。

7 檢測(cè)結(jié)果

8 總結(jié)

基于相似度計(jì)算的UML圖匹配算法比傳統(tǒng)圖匹配算法的設(shè)計(jì)模式檢測(cè)效果更好，效率更高。使用該算法開發(fā)設(shè)計(jì)模式檢測(cè)軟件，可以作為插件集成進(jìn)SonarQube，和其他技術(shù)債務(wù)一起掃描。開發(fā)者根據(jù)掃描結(jié)果識(shí)別到系統(tǒng)哪些地方運(yùn)用了設(shè)計(jì)模式，可以更好地理解系統(tǒng)結(jié)構(gòu)，并對(duì)系統(tǒng)進(jìn)行優(yōu)化和重構(gòu)，提高汽車行業(yè)軟件系統(tǒng)架構(gòu)的質(zhì)量。

參考文獻(xiàn)：

[1] 劉亞珺，李兵，李增揚(yáng)，等.吳閩泉軟件集成開發(fā)環(huán)境的技術(shù)債務(wù)管理研究[J].計(jì)算機(jī)科學(xué)，2017，44（11）：15-21.

[2] 程彩鳳，林德樹.數(shù)據(jù)結(jié)構(gòu)中圖論算法動(dòng)態(tài)智能演示的研究[J].現(xiàn)代電子技術(shù)，2017，40（18）：40-42.

[3] 傅明麗.UML建模技術(shù)在軟件開發(fā)中的應(yīng)用[J].科技展望，2015（18）.

[4] 肖卓宇，黎妍，何锫，等.基于矩陣積分評(píng)估的設(shè)計(jì)模式檢測(cè)研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2016（7）：1428-1433.

【通聯(lián)編輯：朱寶貴】