高東靜 林 云 彭 鑫 趙文耘

(復(fù)旦大學(xué)軟件學(xué)院 上海 201203)

(上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室 上海 201203)

面向設(shè)計(jì)層次優(yōu)化的軟件自動(dòng)化重構(gòu)

高東靜 林 云 彭 鑫 趙文耘

(復(fù)旦大學(xué)軟件學(xué)院 上海 201203)

(上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室 上海 201203)

目前許多研究人員對(duì)自動(dòng)化軟件重構(gòu)進(jìn)行了探索并開發(fā)了一系列重構(gòu)工具，旨在幫助程序員更高效地完成軟件重構(gòu)任務(wù)、提升代碼質(zhì)量。然而，現(xiàn)有的軟件重構(gòu)工具多側(cè)重于局部的設(shè)計(jì)或編碼問(wèn)題，而非設(shè)計(jì)層面的問(wèn)題。另一方面，基于搜索的重構(gòu)方法往往將改進(jìn)某一項(xiàng)代碼度量指標(biāo)作為重構(gòu)目標(biāo)，而非面向軟件的層次化設(shè)計(jì)。針對(duì)這種情況，提出一種新的基于搜索的軟件自動(dòng)化重構(gòu)方法，該方法使用了基于設(shè)計(jì)結(jié)構(gòu)矩陣(DSM)的軟件模塊層次化度量方法，能夠自動(dòng)生成可以得到最優(yōu)軟件模塊化設(shè)計(jì)的重構(gòu)建議。在此基礎(chǔ)上，實(shí)現(xiàn)了自動(dòng)化重構(gòu)工具DSMRefactoring，并將DSMRefactoring應(yīng)用于開源系統(tǒng)進(jìn)行案例研究，初步驗(yàn)證了方法和工具的有效性。

自動(dòng)化重構(gòu) 軟件設(shè)計(jì) 模塊化 設(shè)計(jì)層次

0 引 言

軟件重構(gòu)是對(duì)軟件內(nèi)部結(jié)構(gòu)的一種調(diào)整，目的是在不改變軟件行為的前提下提高可理解性并降低修改成本[1]。在現(xiàn)在的企業(yè)實(shí)踐中，軟件的需求和設(shè)計(jì)的頻繁修改常常會(huì)帶來(lái)系統(tǒng)依賴過(guò)多、結(jié)構(gòu)混亂等“技術(shù)債”問(wèn)題。這些技術(shù)債產(chǎn)生的原因可能是缺乏經(jīng)驗(yàn)的程序員編程時(shí)沒(méi)有遵行合理的編程規(guī)范，也可能是某些程序員為了在有限時(shí)間內(nèi)完成任務(wù)不得不破壞原有的代碼結(jié)構(gòu)。這些技術(shù)債犧牲了代碼質(zhì)量，降低了軟件后續(xù)開發(fā)和維護(hù)的效率，并將導(dǎo)致軟件系統(tǒng)的退化。因此，為了保證軟件系統(tǒng)的可理解性和可維護(hù)性，對(duì)現(xiàn)有代碼進(jìn)行合理的重構(gòu)變得非常必要。

目前研究人員對(duì)軟件自動(dòng)化重構(gòu)的場(chǎng)景、用戶的自動(dòng)化重構(gòu)需求以及應(yīng)當(dāng)何時(shí)采用自動(dòng)化重構(gòu)進(jìn)行了大量研究并開發(fā)了相應(yīng)的工具[2-3]。這些自動(dòng)化重構(gòu)工具大都集成在集成開發(fā)環(huán)境(IDE)中，可以幫助程序員更高效快速地完成局部代碼的重構(gòu)操作。此外，研究人員也進(jìn)行了大量研究嘗試從更高的層面上對(duì)軟件進(jìn)行自動(dòng)化重構(gòu)。例如，Cinnéide等研究人員[4]實(shí)現(xiàn)了一個(gè)基于搜索的、度量驅(qū)動(dòng)的軟件自動(dòng)化重構(gòu)工具Code-Imp，并利用它分析了各種軟件度量之間的關(guān)系。該工具可以對(duì)代碼在總體上進(jìn)行重構(gòu)，使得整個(gè)系統(tǒng)的某一軟件度量值變得最優(yōu)。

高質(zhì)量的軟件設(shè)計(jì)往往需要具有良好的模塊化和層次化的設(shè)計(jì)，由此能夠讓軟件代碼內(nèi)部依賴關(guān)系能夠變得清晰且易于維護(hù)。然而，現(xiàn)有的兩方面重構(gòu)工作(即，集成于IDE中的局部代碼重構(gòu)和基于搜索的全局代碼重構(gòu))仍然有所不足。集成于IDE中的局部代碼重構(gòu)無(wú)法提供一個(gè)設(shè)計(jì)層面的重構(gòu)方案；而基于搜索的全局代碼重構(gòu)雖然能夠在總體層面上調(diào)整軟件的組織結(jié)構(gòu)，但是它們僅能使代碼在現(xiàn)有的某個(gè)度量值上達(dá)到最優(yōu)，無(wú)法得到一個(gè)用戶可見(jiàn)的模塊化與層次化設(shè)計(jì)。

本文提出了一種新的軟件自動(dòng)化重構(gòu)方法，該方法基于設(shè)計(jì)結(jié)構(gòu)矩陣(DSM)[9]將軟件的模塊層次化情況刻畫為可度量的模塊層次化度量指標(biāo)，并利用優(yōu)化搜索的方法找到一個(gè)最優(yōu)的軟件模塊層次化方案推薦給軟件設(shè)計(jì)人員，由此來(lái)提高軟件的可維護(hù)性。本方法的主要思想是將某些代碼元素(如方法，屬性等)分配到更為合理的類或接口中以產(chǎn)生一個(gè)更具模塊層次的設(shè)計(jì)。此外，我們基于該方法實(shí)現(xiàn)了一個(gè)重構(gòu)工具DSMRefactoring，并使用了開源項(xiàng)目進(jìn)行案例研究，初步驗(yàn)證了方法和工具的有效性。

1 相關(guān)工作

1.1 軟件自動(dòng)化重構(gòu)

目前，許多研究人員都對(duì)軟件自動(dòng)化重構(gòu)進(jìn)行了研究。Ge等[2]認(rèn)為：雖然目前已經(jīng)有了很多自動(dòng)化重構(gòu)工具，但由于開發(fā)人員常常不能意識(shí)到自己將要或正在進(jìn)行重構(gòu)，這些工具并沒(méi)有在開發(fā)過(guò)程中得到充分的利用。針對(duì)這個(gè)問(wèn)題，他們對(duì)開發(fā)者的手動(dòng)重構(gòu)過(guò)程進(jìn)行了研究，并基于這些研究的發(fā)現(xiàn)，實(shí)現(xiàn)了一個(gè)重構(gòu)工具BeneFactor來(lái)探測(cè)用戶正在進(jìn)行的重構(gòu)操作并提醒和輔助用戶完成重構(gòu)。Vakilian等研究人員在文獻(xiàn)[3]中，通過(guò)收集和分析程序員的編程數(shù)據(jù)，研究了軟件自動(dòng)化重構(gòu)工具的使用情況。他們的調(diào)查數(shù)據(jù)顯示，程序員更愿意接受輕量級(jí)的自動(dòng)化重構(gòu)工具調(diào)用方式，而不愿意在使用工具之前先進(jìn)行配置。調(diào)查還發(fā)現(xiàn)，有時(shí)程序員會(huì)忽略重構(gòu)工具，或者用設(shè)計(jì)者意料之外的方式來(lái)使用工具。Foster等在文獻(xiàn)[5]中實(shí)現(xiàn)了一個(gè)集成在IDE中的重構(gòu)工具WitchDoctor，該工具可以實(shí)時(shí)檢測(cè)一個(gè)程序員是否在進(jìn)行手動(dòng)的重構(gòu)工作，如果檢測(cè)到程序員在手動(dòng)重構(gòu)，那么它會(huì)在程序員手動(dòng)完成之前把結(jié)果展示出來(lái)，并自動(dòng)完成后續(xù)重構(gòu)工作。與這些針對(duì)局部代碼設(shè)計(jì)的重構(gòu)工作相比，我們的工作側(cè)重于全局的代碼重構(gòu)和調(diào)整。

1.2 基于搜索的軟件自動(dòng)化重構(gòu)

基于搜索的軟件自動(dòng)化重構(gòu)是目前關(guān)于軟件自動(dòng)化重構(gòu)的研究中的一種常用思想[6-8]，這種思想把軟件重構(gòu)問(wèn)題抽象成屬性與方法、屬性與類、方法與類之間的組合優(yōu)化問(wèn)題，并利用常見(jiàn)的搜索算法來(lái)求解。Cinnéide等[4]利用基于搜索的軟件自動(dòng)化重構(gòu)方法實(shí)現(xiàn)了一個(gè)重構(gòu)工具Code-Imp。該工具可以對(duì)軟件進(jìn)行設(shè)計(jì)層面上的重構(gòu)，實(shí)現(xiàn)了類、屬性和方法層面上的若干種重構(gòu)方式，如添加繼承關(guān)系、取消繼承關(guān)系、用組合關(guān)系代替繼承關(guān)系等。該工具使用了爬山算法、模擬退火算法和遺傳算法等進(jìn)行優(yōu)化搜索。Cinnéide等的工作除了對(duì)基于搜索的軟件自動(dòng)化重構(gòu)進(jìn)行了一次有效的實(shí)踐外，還分析比較了各種軟件度量值之間的相互關(guān)系。他們挑選了一些度量值用于研究，通過(guò)比較整個(gè)重構(gòu)過(guò)程中這些度量值的變化情況，考察了度量值之間的關(guān)系與差異。然而，Cinnéide 等的研究工作所考慮的軟件度量值都是軟件內(nèi)部的內(nèi)聚耦合之類的度量值，并沒(méi)有將軟件模塊層次化方面的度量納入研究范圍。與這些工作相比，我們的工作側(cè)重于調(diào)整出具有良好模塊層次化結(jié)構(gòu)的代碼。

1.3 軟件模塊化和層次化研究

在軟件設(shè)計(jì)的相關(guān)研究中，研究者們提出了一些重要的思想。其中設(shè)計(jì)結(jié)構(gòu)矩陣(DSM)模型[9]就是一個(gè)十分重要的刻畫軟件模塊化信息的模型，它具有簡(jiǎn)潔明了的特點(diǎn)。DSM利用矩陣來(lái)刻畫軟件設(shè)計(jì)空間中的依賴情況，它的每行每列分別代表設(shè)計(jì)空間中的一個(gè)變量，某行某列上的一個(gè)標(biāo)記則代表某行所代表的設(shè)計(jì)變量依賴于另一列所代表的設(shè)計(jì)變量。圖1中的DSM刻畫了一個(gè)包含三個(gè)設(shè)計(jì)變量A、B和C的軟件設(shè)計(jì)，其中B和C相互依賴，B同時(shí)還依賴于A。從圖1我們可以看出，DSM可以用來(lái)刻畫設(shè)計(jì)變量的聚類信息：由于B和C相互依賴，B、C可以被劃分成一個(gè)模塊，而A則需要單獨(dú)劃分成另一個(gè)模塊，圖1中的黑線劃出了根據(jù)設(shè)計(jì)變量的依賴關(guān)系劃分出的兩個(gè)模塊。

ABCABXXCX

圖1 DSM示例

在此基礎(chǔ)上， Wong等提出了設(shè)計(jì)規(guī)則層次(DRH)理論[10]。在DRH中，一個(gè)軟件中的各個(gè)設(shè)計(jì)變量和它們之間的依賴關(guān)系通過(guò)DSM來(lái)刻畫，此外，該DSM中的行和列被重新排序以構(gòu)成一定的層次結(jié)構(gòu)。圖2展示了一個(gè)被劃分成四層DRH的DSM，圖中的細(xì)邊矩形代表模塊，粗邊矩形代表層次。DSM模型和DRH理論是軟件模塊化和層次化方面十分重要的理論，它們對(duì)軟件特征的刻畫十分清晰。此外，利用矩陣來(lái)刻畫軟件結(jié)構(gòu)使得設(shè)計(jì)一個(gè)度量值來(lái)度量軟件的模塊化和層次化變得可行。本文設(shè)計(jì)實(shí)現(xiàn)的面向設(shè)計(jì)層次優(yōu)化的軟件自動(dòng)化重構(gòu)工具所使用的度量值就是基于這套理論所設(shè)計(jì)的。這些工作的主要貢獻(xiàn)在于呈現(xiàn)出代碼的模塊化信息，而我們的工作側(cè)重于解決如何將代碼變得更模塊層次化的問(wèn)題。

圖2 被劃分成四層DRH的DSM

2 面向設(shè)計(jì)層次優(yōu)化的軟件自動(dòng)化重構(gòu)方法

DSMRefactoring通過(guò)改變代碼類之間的依賴關(guān)系來(lái)改善軟件的層次化結(jié)構(gòu)。我們方法的輸入是某一個(gè)項(xiàng)目的源代碼，輸出是針對(duì)該項(xiàng)目代碼的重構(gòu)建議。首先，我們對(duì)項(xiàng)目的源代碼進(jìn)行內(nèi)部依賴關(guān)系的分析以得到程序元素之間(類、方法和屬性之間)的依賴關(guān)系。然后，我們通過(guò)調(diào)整類成員(方法或?qū)傩?與類之間的映射關(guān)系(即，哪個(gè)類成員應(yīng)屬于哪個(gè)類)來(lái)提高項(xiàng)目源碼的模塊化程度。在這個(gè)過(guò)程中，我們利用遺傳算法和基于DSM矩陣的模塊層次化度量方法來(lái)計(jì)算出類成員對(duì)各類的最優(yōu)映射關(guān)系。最后，我們對(duì)比現(xiàn)有的類成員與類的映射關(guān)系和遺傳算法計(jì)算出的最優(yōu)類成員與類的映射關(guān)系，由此生成重構(gòu)建議并展示給軟件開發(fā)人員。

2.1 基本思想

本文將Java類之間的依賴關(guān)系作為軟件模塊化和層次結(jié)構(gòu)的一個(gè)重要依據(jù)，而Java類之間的依賴關(guān)系實(shí)際上是通過(guò)類中的屬性和方法之間的相互依賴產(chǎn)生的，因此，我們可以通過(guò)改變類成員與類之間的映射關(guān)系來(lái)改變Java類之間的依賴關(guān)系，從而改變整個(gè)Java項(xiàng)目的層次結(jié)構(gòu)。如圖3所示，A、B、C三個(gè)類本具有相對(duì)復(fù)雜的依賴關(guān)系(圖3(a))，通過(guò)從類B中移動(dòng)方法m3()到類C中能夠解耦A(yù)、B之間的互相依賴(圖3(b))，而再通過(guò)從類B中移動(dòng)屬性b1到類C中，則可以得到一個(gè)比較好的層次依賴結(jié)構(gòu)。因此，我們旨在通過(guò)調(diào)整類成員與類之間的映射關(guān)系來(lái)改善原項(xiàng)目代碼的模塊化層次結(jié)構(gòu)。

(a) 初始類圖

(b) 移動(dòng)m3之后的類圖 (c) 移動(dòng)b1之后的類圖圖3 通過(guò)改變成員與類的映射關(guān)系改變?cè)O(shè)計(jì)的層次結(jié)構(gòu)

2.2 算法過(guò)程

基于上述思想，我們利用遺傳算法通過(guò)不斷改變各個(gè)類成員與各類之間的映射關(guān)系，計(jì)算和比較軟件結(jié)構(gòu)對(duì)應(yīng)的模塊層次化度量值(由此來(lái)判斷某一結(jié)構(gòu)的優(yōu)劣)，來(lái)對(duì)軟件結(jié)構(gòu)進(jìn)行優(yōu)化。該重構(gòu)遺傳算法的搜索空間是各個(gè)類成員和類之間所有可能的映射方式(即，哪個(gè)類成員應(yīng)處于哪個(gè)類之中)，軟件的模塊層次化信息通過(guò)DSM來(lái)刻畫，并通過(guò)度量值L(Layering)來(lái)度量，具體的度量方法在下一節(jié)中詳述。算法中使用的個(gè)體代表了類成員和類的映射關(guān)系，個(gè)體中的每一個(gè)基因位代表一個(gè)類成員，而基因位的值代表對(duì)應(yīng)類成員所在的類。

2.2.1 目標(biāo)函數(shù)

1) 目標(biāo)函數(shù)度量介紹

本方法所采用的目標(biāo)函數(shù)基于DSM模型和DRH理論。給定一個(gè)個(gè)體，即類成員與類的映射關(guān)系，我們可以通過(guò)類成員之間的依賴關(guān)系來(lái)得到它們所在類之間的依賴關(guān)系。本節(jié)所使用的DSM中，行和列代表的設(shè)計(jì)變量都是Java類(如圖4)，設(shè)計(jì)變量之間的依賴關(guān)系也就是Java類之間的依賴關(guān)系，Java類之間的依賴關(guān)系則通過(guò)類中的屬性和方法之間的調(diào)用關(guān)系來(lái)決定。

(a) 5個(gè)Java類組成的DSM (b) DSM中的層次結(jié)構(gòu)圖4 DSM示例

圖4(a)展示了一個(gè)由5個(gè)Java類組成的DSM樣例，圖中第i行第j列的1表示類i依賴于類j，0則表示沒(méi)有依賴。每個(gè)Java類與它本身的依賴關(guān)系不需要考慮。根據(jù)DRH理論，DSM的行和列可以被重新排序來(lái)展示層次結(jié)構(gòu)，圖4(b)就展示了(a)中的DSM所代表的層次結(jié)構(gòu)，其中每個(gè)加粗的矩形代表一個(gè)層次，下層依賴于上層。

在此基礎(chǔ)上，軟件層次結(jié)構(gòu)的好壞用度量值Layering(L)來(lái)度量，一個(gè)DSM(M)的L值被這樣定義如下：

L=4×l2-4×n-m

(1)

其中l(wèi)是DSM的行數(shù)，也就是Java類的個(gè)數(shù)，n是DSM中右上角的1的個(gè)數(shù)，m是DSM中左下角不符合層次化約束(在下文中將介紹層次化約束的具體定義)的1的個(gè)數(shù)。在Java類的個(gè)數(shù)l一定的情況下，L的值越大表示軟件的層次化結(jié)構(gòu)越好。度量值L的定義可以分成三部分：4×l2，-4×n和-m。其中4×l2是一個(gè)由l個(gè)類組成的軟件的L度量值的最大值；-4×n和-m則分別是對(duì)軟件中可能存在的兩種違背層次化要求的結(jié)構(gòu)(反向依賴情況與跨層依賴情況)采取的懲罰措施。

? 反向依賴情況

4×n針對(duì)的是DRH的第一個(gè)特征：DSM沿對(duì)角線形成的右上角為空。DSM矩陣中呈現(xiàn)的模塊依賴應(yīng)該是偏序的(即右下角的模塊應(yīng)依賴于左上角的模塊，反之不然)，因此，如果DSM的右上角上出現(xiàn)了依賴關(guān)系，則說(shuō)明軟件中出現(xiàn)了反向依賴的模塊，違背了軟件層次化的要求，會(huì)使L值降低。我們認(rèn)為由于DRH的這一偏序要求十分必要，違背了這個(gè)要求的軟件，其層次化結(jié)構(gòu)往往容易腐化，所以本節(jié)的算法賦予了這種依賴關(guān)系更高的權(quán)重，它們會(huì)更直接地影響L的值。

? 跨層依賴情況

m針對(duì)的則是另一種層次化約束，這一約束是相對(duì)于DRH的另一個(gè)特征：設(shè)計(jì)中的第n層只依賴于第1到第n-1層提出的。在本文中，模塊將進(jìn)一步被劃分層次，依賴關(guān)系只應(yīng)該存在于相鄰的層次之間，而不應(yīng)該存在于跨級(jí)層次之間。即，本文認(rèn)為，當(dāng)一個(gè)具有好的層次結(jié)構(gòu)的軟件設(shè)計(jì)被劃分成若干層之后，設(shè)計(jì)中的第n層并不能依賴于第1到第n-1的所有n-1層，而是只能依賴于第n-1層，也就是說(shuō)好的層次結(jié)構(gòu)應(yīng)當(dāng)如圖5所示。圖5中的細(xì)邊矩形代表模塊，粗邊矩形代表層次。

圖5 符合層次化約束的DSM

2) DSM矩陣L值計(jì)算

我們使用了迭代的方式來(lái)計(jì)算一個(gè)代碼結(jié)構(gòu)DSM的L值，過(guò)程如下：(1) 對(duì)DSM中的設(shè)計(jì)變量進(jìn)行聚類(即重新排列DSM矩陣的行及其相應(yīng)的列)，將某些相互依賴的設(shè)計(jì)變量劃分成一個(gè)模塊，圖6(a)就表示了圖5中的DSM對(duì)應(yīng)的模塊劃分。(2) 對(duì)上一步產(chǎn)生的模塊進(jìn)行層次劃分，將相鄰的所有相互獨(dú)立的模塊劃分到一個(gè)層次中，并計(jì)算對(duì)應(yīng)的L值，圖5、圖6(b)就分別表示了該DSM中的一種模塊聚類情況，以及對(duì)應(yīng)的層次劃分結(jié)果，圖6(b)中的陰影標(biāo)明了這種排列中對(duì)應(yīng)的違背要求的項(xiàng)，其中，圖5中的DSM變形對(duì)應(yīng)的L5=4×l2-4×n-m=4×92-4×0-0=324，而圖6(b)對(duì)應(yīng)的L6b=4×l2-4×n-m=4×92-4×5-4=300。在這一步計(jì)算中，本文采用的做法是對(duì)所有可能的模塊排列順序都進(jìn)行一次層次劃分并計(jì)算對(duì)應(yīng)的L值，以確保L值計(jì)算的準(zhǔn)確性。(3) 迭代(1)、(2)中所有排列取最大值作為該DSM最終的L值，并記下對(duì)應(yīng)的設(shè)計(jì)變量的排列順序，例如上述舉例中的DSM最終的LD=L5=324，對(duì)應(yīng)的設(shè)計(jì)變量的排列順序如圖5所示。值得注意的是，這個(gè)例子中的L5達(dá)到了9個(gè)類組成的軟件的最大L值，當(dāng)發(fā)現(xiàn)當(dāng)前的L值已經(jīng)達(dá)到最大值時(shí)，則重構(gòu)算法直接結(jié)束。

(a) 圖5的模塊分割 (b) 另一種可能的變體圖6 計(jì)算一個(gè)DSM的L值

完成聚類之后，需要根據(jù)聚類產(chǎn)生的模塊排列順序來(lái)對(duì)模塊進(jìn)行分層，連續(xù)的所有兩兩相互獨(dú)立的模塊都屬于同一個(gè)層次。在計(jì)算L值時(shí)，實(shí)際算法使用的DSM的每一行(列)代表的都是劃分之后的一個(gè)層次，圖7展示了圖5在實(shí)際計(jì)算時(shí)對(duì)應(yīng)的DSM。每個(gè)層次用大括號(hào)表示，大括號(hào)中的數(shù)字表示這個(gè)層次中包含的Java文件，矩陣中的數(shù)字表示一個(gè)層次中依賴于另一個(gè)層次的Java文件的個(gè)數(shù)。

圖7 計(jì)算時(shí)使用的DSM

2.2.2 選擇算子

在遺傳算法中，選擇算子的作用是從同一代的個(gè)體中選擇出合適的個(gè)體來(lái)產(chǎn)生下一代，其目標(biāo)是把優(yōu)勝的個(gè)體(或問(wèn)題的解)直接遺傳到下一代，或者讓這些優(yōu)勝的個(gè)體或解通過(guò)產(chǎn)生后代的方式遺傳到下一代。在本節(jié)中，選擇算子的目標(biāo)就是從同一代的各種軟件結(jié)構(gòu)中，選擇出對(duì)應(yīng)DSM的L值最大的來(lái)產(chǎn)生下一代。

DSMRefactoring中使用的選擇算子是最基本的比例選擇算子(輪盤賭選擇)：同一代中的每個(gè)個(gè)體被選中的概率與它對(duì)應(yīng)的DSM的L值的大小成比例，L值越大被選中的概率也越大。假設(shè)每代有n個(gè)個(gè)體，其中第i個(gè)個(gè)體對(duì)應(yīng)的DSM的L值為L(zhǎng)i，則它被選中的概率Pi為：

(2)

2.2.3 交叉算子

在遺傳算法中，交叉算子起到了提高算法搜索能力的核心作用。交叉算子通過(guò)將選擇算子選擇出的兩個(gè)父代個(gè)體的部分結(jié)構(gòu)進(jìn)行重組來(lái)產(chǎn)生下一代中的新個(gè)體。在本節(jié)中，交叉算子的作用是將通過(guò)選擇算子選擇出的父代中的軟件結(jié)構(gòu)進(jìn)行交叉重組，生成新一代的軟件結(jié)構(gòu)，在搜索空間中搜索最優(yōu)解。

DSMRefactoring采用了均勻交叉的方法。具體實(shí)現(xiàn)中使用的交叉概率是0.5，這樣從概率上來(lái)說(shuō)，兩個(gè)父代個(gè)體產(chǎn)生的下一代個(gè)體的軟件結(jié)構(gòu)中，來(lái)自兩個(gè)父代個(gè)體中的軟件結(jié)構(gòu)各占一半。交叉算子的實(shí)現(xiàn)如下：兩個(gè)父代個(gè)體代表了兩種軟件結(jié)構(gòu)，各自分別用對(duì)應(yīng)的類成員列表來(lái)表示，列表中的每個(gè)成員都記錄了當(dāng)前所在的Java類，在執(zhí)行交叉之前，分別對(duì)兩個(gè)父代個(gè)體進(jìn)行克隆，然后分別對(duì)克隆個(gè)體的列表中的每個(gè)成員進(jìn)行如下操作：(1) 比較兩個(gè)克隆個(gè)體中該成員所在的類是否相同，若相同，結(jié)束對(duì)該成員的操作。(2) 如果在這兩個(gè)克隆個(gè)體中，該成員所在的類不同，則隨機(jī)產(chǎn)生一個(gè)布爾值，如果該值為真，那么就將兩個(gè)克隆個(gè)體中該成員所在的Java類互換，否則，結(jié)束對(duì)該成員的操作。

經(jīng)過(guò)上述操作，原本的兩個(gè)克隆個(gè)體就變成了兩個(gè)新個(gè)體，經(jīng)過(guò)下一節(jié)的變異算子的操作后，就會(huì)成為下一代中的兩個(gè)個(gè)體。

2.2.4 變異算子

變異算子通過(guò)對(duì)個(gè)體中的某些結(jié)構(gòu)進(jìn)行改動(dòng)，提高了遺傳算法種群的多樣性，由此避免了遺傳算法往局部最優(yōu)解收斂的情況。在本節(jié)中，交叉算子的作用就是對(duì)需要變異的軟件結(jié)構(gòu)中的某些結(jié)構(gòu)進(jìn)行改變，產(chǎn)生新一代的軟件結(jié)構(gòu)。DSMRefactoring中使用的變異算子是這樣設(shè)計(jì)的：(1) 根據(jù)變異概率來(lái)判斷每個(gè)個(gè)體是否需要變異。(2) 從需要變異的個(gè)體的類成員列表中，隨機(jī)選擇一個(gè)屬性或方法將它根據(jù)一定的概率移動(dòng)到另一個(gè)類中。

3 案例分析

本文使用DSMRefactoring對(duì)若干個(gè)Java項(xiàng)目進(jìn)行了自動(dòng)化重構(gòu)實(shí)驗(yàn)，并通過(guò)實(shí)驗(yàn)數(shù)據(jù)對(duì)DSMRefactoring進(jìn)行了評(píng)估。我們使用的實(shí)驗(yàn)項(xiàng)目包括了開源計(jì)算器軟件Calculator (http://plugins.jedit.org/plugins/?Calculator)。在實(shí)驗(yàn)過(guò)程中，我們主要根據(jù)兩方面的實(shí)驗(yàn)結(jié)果來(lái)對(duì)DSMRefactoring進(jìn)行評(píng)估，驗(yàn)證該工具的有效性：(1) 遺傳算法是否能有效地得到最優(yōu)(次優(yōu))解；(2) 最終的重構(gòu)建議是否合理有效。

3.1 遺傳算法的有效性

DSMRefactoring在對(duì)Calculator開源項(xiàng)目進(jìn)行重構(gòu)的過(guò)程中，共產(chǎn)生了256代個(gè)體，每代包括1 280個(gè)個(gè)體。為了分析重構(gòu)過(guò)程中的收斂情況，DSMRefactoring在重構(gòu)過(guò)程中對(duì)每一代個(gè)體都計(jì)算了最優(yōu)目標(biāo)函數(shù)值、平均目標(biāo)函數(shù)值和目標(biāo)函數(shù)值的標(biāo)準(zhǔn)差，表1展示了其中的部分?jǐn)?shù)據(jù)結(jié)果。

表1 Calculator重構(gòu)過(guò)程中的迭代數(shù)據(jù)

從表1的數(shù)據(jù)中我們可以看出：總體來(lái)說(shuō)，每一代中的最優(yōu)目標(biāo)函數(shù)值一直在變大，但也存在一些例外，有些時(shí)候會(huì)出現(xiàn)最優(yōu)L值先變大再變小的情況，而且最優(yōu)L值的變化幅度在重構(gòu)剛開始和快結(jié)束時(shí)比較小，在中期比較大；每代的平均目標(biāo)函數(shù)值一直處于穩(wěn)步的上升中；目標(biāo)函數(shù)值的標(biāo)準(zhǔn)差則是先變大再變小。

由此可以看出：在整個(gè)重構(gòu)過(guò)程當(dāng)中，Calculator每一代的軟件結(jié)構(gòu)整體上來(lái)說(shuō)都在變好，最好的軟件結(jié)構(gòu)也基本上在越變?cè)胶?，但有一些特例，不同的軟件結(jié)構(gòu)之間的差距則是先變大后變小。通過(guò)上述分析，我們可以看出：DSMRefactoring在對(duì)項(xiàng)目進(jìn)行重構(gòu)的過(guò)程中，項(xiàng)目的結(jié)構(gòu)是在不斷向更好的方向收斂的，本節(jié)實(shí)現(xiàn)的重構(gòu)方法是合理有效的。

3.2 重構(gòu)結(jié)果的合理性

我們通過(guò)觀察重構(gòu)建議的結(jié)果與經(jīng)典的設(shè)計(jì)結(jié)構(gòu)進(jìn)行比較，來(lái)驗(yàn)證重構(gòu)建議的合理性。為了避免因?yàn)槿说闹饔^因素而影響評(píng)估結(jié)果，我們只針對(duì)經(jīng)典的設(shè)計(jì)結(jié)構(gòu)進(jìn)行觀察，例如MVC架構(gòu)、觀察者模式、訪問(wèn)者模式等。根據(jù)我們對(duì)Calculator項(xiàng)目最初的軟件結(jié)構(gòu)的觀察，它的結(jié)構(gòu)主要包括四個(gè)部分：界面、監(jiān)聽器、計(jì)算功能和輔助功能。用戶通過(guò)在界面上點(diǎn)擊不同的按鈕觸發(fā)不同的監(jiān)聽器，繼而調(diào)用不同的功能，這是一個(gè)典型的MVC架構(gòu)，Calculator中的界面部分對(duì)應(yīng)MVC中的View模塊，監(jiān)聽器部分對(duì)應(yīng)MVC中的Controller模塊，計(jì)算功能和輔助功能部分則對(duì)應(yīng)MVC中的Model模塊，他們之間理想的依賴關(guān)系應(yīng)當(dāng)如圖8所示。

圖8 理想的MVC架構(gòu)

但是，在Calculator原本的實(shí)現(xiàn)中，一些對(duì)計(jì)算功能的調(diào)用被直接放在了CalculatorPanel類中的方法中，這導(dǎo)致CalculatorPanel類對(duì)實(shí)現(xiàn)了計(jì)算功能的類(如Op、Num等)產(chǎn)生了直接的依賴，也就是圖8中的View模塊對(duì)Model模塊直接產(chǎn)生了依賴關(guān)系，這破壞了原本的MVC架構(gòu)。而在DSMRefactoring的重構(gòu)結(jié)果中，這些依賴關(guān)系都被去除了，下文將詳細(xì)地描述這一結(jié)果。為了更清楚簡(jiǎn)潔地描述這一過(guò)程，下文將只分析界面、監(jiān)聽器和計(jì)算功能三個(gè)模塊之間的結(jié)構(gòu)，其中界面模塊只表示CalculatorPanel一個(gè)類，監(jiān)聽器模塊表示ZeroOpListener、BinaryOpListener和UnaryOpListener三個(gè)類，計(jì)算功能模塊表示Op和Num兩個(gè)類。

Calculator原本的設(shè)計(jì)結(jié)構(gòu)可以用圖9中的類圖表示，從這個(gè)類圖中我們可以看出，由于CalculatorPanel類對(duì)Op和Num類產(chǎn)生了直接的依賴，整個(gè)軟件的結(jié)構(gòu)比較混亂，類與類之間的依賴關(guān)系很復(fù)雜，無(wú)法看出任何層次關(guān)系或設(shè)計(jì)架構(gòu)。圖10表示了對(duì)應(yīng)的DSM圖，其中模塊和層次的表示方法如前文，陰影部分標(biāo)出了圖中違背結(jié)構(gòu)要求的依賴關(guān)系。

圖9 重構(gòu)之前的類圖

圖10 重構(gòu)之前的DSM

圖11則表示了重構(gòu)之后Calculator的軟件結(jié)構(gòu)，從圖11我們可以看出，經(jīng)過(guò)重構(gòu)，Calculator顯示出了良好的層次結(jié)構(gòu)，類與類之間的依賴關(guān)系十分清晰，整個(gè)軟件層次分明，結(jié)構(gòu)良好。

圖11 重構(gòu)之后的類圖

圖12表示了對(duì)應(yīng)的DSM圖，表示方法同圖10，從圖中我們可以看出，DSM中各Java類之間的依賴關(guān)系都符合層次化約束，但仍然存在違反偏序要求的依賴關(guān)系(即最優(yōu)的重構(gòu)方案依然可能違反DSM偏序關(guān)系)。在Calculator項(xiàng)目中，View模塊會(huì)調(diào)用Controller模塊，Controller模塊也需要把Model模塊的處理結(jié)果顯示在View中，這兩者之間無(wú)法解耦。這也說(shuō)明，并不是在每次重構(gòu)中，最終的重構(gòu)結(jié)果對(duì)應(yīng)的L值都能達(dá)到最大值。通過(guò)該案例研究，我們可以初步得出本文所提出的面向設(shè)計(jì)層次優(yōu)化的軟件自動(dòng)化重構(gòu)方法有一定實(shí)用價(jià)值。

圖12 重構(gòu)之后的DSM

4 結(jié) 語(yǔ)

關(guān)于軟件自動(dòng)化重構(gòu)的研究有很多，但現(xiàn)有重構(gòu)工具多側(cè)重于局部代碼的重構(gòu)或針對(duì)某些度量值的重構(gòu)，很少考慮提高代碼模塊化質(zhì)量的全局性重構(gòu)。本文實(shí)現(xiàn)了一個(gè)面向設(shè)計(jì)層次優(yōu)化的軟件自動(dòng)化重構(gòu)方法，該方法基于遺傳算法和DSM矩陣度量公式來(lái)調(diào)整類成員與類之間的映射關(guān)系，并向軟件開發(fā)人員提出重構(gòu)建議。同時(shí)，我們實(shí)現(xiàn)了相應(yīng)工具DSMRefactoring，并通過(guò)案例研究初步證明了方法的有效性。

[1] Fowler M. Refactoring: improving the design of existing code[M]. Boston: Addison-Wesley Professional, 1999.

[2] Ge X, Dubose Q L, Murphyhill E. Reconciling manual and automatic refactoring[C]// International Conference on Software Engineering. IEEE, 2012:211-221.

[3] Vakilian M, Chen N, Negara S, et al. Use, disuse, and misuse of automated refactorings[C]// 34th International Conference on Software Engineering (ICSE), Zurich, 2012. Piscataway: IEEE Press, 2012: 233-243.

[4] Cinnéide M ó , Tratt L, Harman M, et al. Experimental assessment of software metrics using automated refactoring[C]// Acm-Ieee International Symposium on Empirical Software Engineering and Measurement. IEEE, 2013:49-58.

[5] Foster S R, Griswold W G, Lerner S. WitchDoctor: IDE support for real-time auto-completion of refactorings [C]//Proceedings of the 2012 International Conference on Software Engineering, Zurich, 2012. Piscataway: IEEE Press, 2012: 222-232.

[6] Harman M, Tratt L. Pareto optimal search based refactoring at the design level[C]// Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, London, 2007. New York: ACM, 2007: 1106-1113.

[7] O’Keeffe M, Cinnéide M. Search-based refactoring: an empirical study[J]. Journal of Software Maintenance & Evolution Research & Practice, 2008, 20(5):345-364.

[8] O’Keeffe M, Cinnéide M. Search-based refactoring for software maintenance[J]. Journal of Systems & Software, 2008, 81(4):502-516.

[9] Cai Y, Sullivan K. A formal model for automated software modularity and evolvability analysis[J]. ACM Transactions on Software Engineering and Methodology (TOSEM), 2012, 21(4): 21.

[10] Wong S, Cai Y, Kim M, et al. Detecting software modularity violations[C]// Proceedings of the 33rd International Conference on Software Engineering, Hawaii, 2011. New York: ACM, 2011: 411-420.

AUTOMATICSOFTWAREREFACTORINGTOWARDSTHEOPTIMIZATIONOFDESIGNHIERARCHY

Gao Dongjing Lin Yun Peng Xin Zhao Wenyun

(SchoolofSoftware,FudanUniversity,Shanghai201203,China)(ShanghaiKeyLaboratoryofDataScience,FudanUniversity,Shanghai201203,China)

At present, many researchers have explored automated software refactoring and developed a series of refactoring tools designed to help developers conduct refactoring tasks with more efficiency and improve the code quality accordingly. However, existing software refactoring tools mainly focus on improving the code quality from a local perspective instead of an overall design perspective. On the other hand, search-based refactoring approaches usually aim at improving some specific code metrics instead of modularized and layered software design. This paper proposes a novel search-based automatic software refactoring approach, which leverages DSM-based code metric to modularize code. This approach is able to generate refactoring suggestions to achieve an optimal modularized and layered software design. This paper also introduces a proof-of-concept tool, DSMRefactoring, and applies the tool on an open-source system. The results validate the effectiveness of both the approach and its proof-of-concept tool.

Automatic refactoring Software design Modularity Design hierarchy

TP311

A

10.3969/j.issn.1000-386x.2017.10.002

2016-12-22。國(guó)家自然科學(xué)基金項(xiàng)目(61370079)；國(guó)家高技術(shù)研究發(fā)展計(jì)劃(2012AA011202)。高東靜，碩士，主研領(lǐng)域：軟件自動(dòng)化重構(gòu)，缺陷預(yù)測(cè)，程序分析。林云，博士。彭鑫，教授。趙文耘，教授。