張志浩 楊春花

(齊魯工業(yè)大學(xué)(山東省科學(xué)院)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 山東 濟(jì)南 250000)

0 引 言

代碼重構(gòu)[1]是指使用一系列重構(gòu)手法，在不改變軟件可觀察行為的前提下，調(diào)整其結(jié)構(gòu)，提高其可理解性、可維護(hù)性和可擴(kuò)展性，降低其修改成本，是一種在結(jié)構(gòu)層次上的代碼整理技術(shù)。

在現(xiàn)代軟件開發(fā)的過程中，代碼變更包括特征增加、修復(fù)bug以及代碼重構(gòu)等。這些不同類型的變更代碼混合在一起使得閱讀和理解代碼變更趨于困難，如果將重構(gòu)的代碼變更與其他變更進(jìn)行隔離，將有利于閱讀和理解。

為了實(shí)現(xiàn)代碼重構(gòu)與其他變更的隔離，應(yīng)該設(shè)法對代碼重構(gòu)模式進(jìn)行自動識別。當(dāng)前，國內(nèi)外學(xué)者對軟件重構(gòu)識別進(jìn)行了深入的研究探索。主要相關(guān)的研究有：Werβgerber等[2]提出了基于簽名分析的方法;Prete等[3]開發(fā)了REF-FINDER;Fokaefs等[4]開發(fā)了一種eclipse插件，能對一種或者幾種重構(gòu)模式進(jìn)行識別;鐘林輝等[5]提出了一種基于版本的多重軟件重構(gòu)自動檢測技術(shù)；劉洋[6]提出了一種可以識別函數(shù)抽取的方法。但上述算法面對變更的文本時忽視了形式不同而含義相似的情況，比如說一些變更僅僅是變量名稱改變，或者僅僅是字母大小寫變換，含義并沒有變。

克隆代碼又稱為重復(fù)代碼，一般指存在于程序代碼中的相似或者相同的代碼段，對它的檢測技術(shù)稱為代碼克隆檢測技術(shù)。當(dāng)前對克隆代碼檢測的技術(shù)已經(jīng)很成熟了，劉復(fù)星[7]提出一種基于深度學(xué)習(xí)的代碼克隆檢測方法，汪敏[8]提出一種基于依賴圖的代碼克隆檢測方法，王杰[9]提出一種基于序列匹配和字節(jié)碼的代碼克隆檢測方法，林蟬[10]提出一種基于索引的分布式代碼克隆檢測方法。本文提出基于代碼克隆檢測對重構(gòu)模式進(jìn)行識別，并對一種常用的重構(gòu)模式——抽取方法的識別算法進(jìn)行了設(shè)計(jì)與實(shí)現(xiàn)。此算法以代碼變更塊hunk為單位，用代碼克隆檢測篩選那些具有代碼克隆關(guān)系的hunk集，然后用語法分析判定兩個候選hunk之間是否屬于抽取方法模式。該算法在4個開源項(xiàng)目上進(jìn)行了驗(yàn)證。

1 抽取方法重構(gòu)模式的識別

1.1 變更代碼塊(hunk)

對代碼變更的抽取方法分為兩類：文本型差異化代碼分析和樹型差異化分析。

Gnu Differ[11]等文本型差異化代碼分析比較兩個版本的源文件，通過比較它們文本上的差異，得出變更集；Change Distiller[12]等樹形差異化分析通過比較兩個版本的源文件所對應(yīng)的抽象語法樹之間的差異，得出變更集。

變更代碼塊(hunk)是文本型差異化代碼分析方法輸出的基本單位。一個hunk由添加的行和刪除的行構(gòu)成，一般前后還各有三行未變動的上下文行。圖1列出了兩個hunk，它們屬于項(xiàng)目jEdit版本9dd86c7中View.java文件的變更集。以第一個hunk為例，該文件老版本中的第607～620行是刪除的行，行首為減號；新版中的第607是增加的行，行首為加號，該hunk之前的604～606行是上下文行，同理后面的三行也是上下文行。第二個hunk只含有增加的行。

圖1 hunk示例

1.2 抽取方法模式

抽取方法模式經(jīng)常出現(xiàn)在代碼重構(gòu)中。當(dāng)遇見一個過長的函數(shù)或者一段比較復(fù)雜、需要添加注釋才能易于理解的代碼時，可以采取這種重構(gòu)模式，將這一段代碼放到一個獨(dú)立的函數(shù)中去。把大型函數(shù)分解為幾個小粒度的函數(shù)，并使用易于理解的名稱去命名它，這是抽取方法的一般原因和過程。

在圖1所示的代碼變更中，hunk1中移走的代碼(行607～620)屬于方法processKeyEvent，這些代碼移動到了hunk2中的新增的方法processKeyEventKeyStrokeHandling中。而且在hunk1中被移走的代碼處，有對新增方法的調(diào)用語句(行607)。因此，這是一種典型的抽取方法重構(gòu)。

1.3 抽取方法模式的識別

抽取方法重構(gòu)模式的代碼變更具有如下兩個特點(diǎn)：

1) 原代碼中的某方法A中的部分代碼轉(zhuǎn)移到了變更后代碼中的某個新增方法B；

2) 變更后代碼中在方法A中移走的代碼處有對新增方法B的調(diào)用。

因此，對這兩個特征進(jìn)行判斷是識別抽取方法模式的關(guān)鍵。下面分別闡述這兩個特點(diǎn)的判斷方法。

1.3.1基于克隆檢測對方法的代碼移動進(jìn)行判斷

設(shè)A中移走的代碼行存在于某個hunk(設(shè)為h1)的刪除行中，B中新增的代碼行存在于某個hunk(設(shè)為h2)的添加行中，h1和h2可以相同，也可不同。

因此，第一個特點(diǎn)可以通過檢測h1的刪除行和h2的添加行之間的克隆關(guān)系來判斷。

為方便檢測，我們將每個hunk分裂為兩個子hunk：lefthunk和righthunk，前者存放hunk的刪除行，后者存放hunk的添加行。分裂后的兩個hunk保存原h(huán)unk的id，用于后期使用。例如，圖1的hunk1分裂后變?yōu)槿鐖D2所示的兩個hunk：lefthunk和righthunk。

圖2 hunk的分裂

因此，h1的刪除行和h2的添加行之間的克隆關(guān)系檢測轉(zhuǎn)為對分裂后的兩個hunk(即h1.lefthunk和h2.righthunk)之間的克隆關(guān)系的檢測。

1.3.2對新增方法調(diào)用的判斷

設(shè)hi.lefthunk和hj.righthunk之間存在克隆關(guān)系，則需要在hi中檢測是否存在一個新增的方法調(diào)用，它調(diào)用了hj中的新增代碼行所屬的方法。

因此，首先要獲得hj之中新增代碼行所屬的方法名(設(shè)為B)，然后獲得hi之中刪除的代碼行所屬的方法名(設(shè)為A)，最后在hi新增的代碼行中查找對方法B的調(diào)用。

例如圖1中，在確定了hunk1和hunk2存在克隆關(guān)系之后，需要獲得hunk2中新增的方法名processKeyEventKeyStrokeHandling()，然后在hunk1中取被抽取代碼行的方法名，并檢測hunk1中的新增代碼行中是否存在語句或表達(dá)式調(diào)用了方法processKeyEventKeyStrokeHandling()。

在hunk中查找方法名及方法調(diào)用語句或方法調(diào)用表達(dá)式比較困難，因?yàn)閔unk是文本，不攜帶語法信息,因此，我們采用抽象語法樹來輔助實(shí)現(xiàn)。具體的做法如下：

(1) 對變更前后兩個版本的源文件，分別生成其抽象語法樹，然后獲取每棵樹中的所有方法節(jié)點(diǎn)。根據(jù)方法節(jié)點(diǎn)的行范圍與hunk的行范圍進(jìn)行匹配來查找hunk中存在的方法名。此過程可以查找方法名A和B。

(2) 在定位到方法A后，取變更后版本的抽象語法樹中的該方法節(jié)點(diǎn)，對其所有子節(jié)點(diǎn)進(jìn)行查找，確定是否存在一個方法調(diào)用節(jié)點(diǎn)，該節(jié)點(diǎn)存在于hi的新增行范圍中，且調(diào)用的方法名為B。

1.4 算 法

此算法輸入變更前后兩個版本的源文件filel和filer，輸出存在抽取方法模式的hunk元組的集合R={|h1,h2∈H}，其中h1、h2是兩個hunk，且h1的刪除行和h2的添加行之間存在方法抽取重構(gòu)模式。算法的偽代碼如下：

輸入:變更前后兩個版本的源文件filel和filer

輸出:存在抽取方法模式的hunk元組的集合R

1H←getHunks(filel,filer)

2 (H1,H2)←split(H)

3Hsim←?

4 for eachh1∈H1

5 for eachh2∈H2

6 ifcheckSimilar(h1,h2)

7Hsim←Hsim∪(h1,h2)

8 end if

9 end for

10 end for

11tl←createAST(filel)

12tr←createAST(filer)

13M1←getAllMethods(tl)

14M2←getAllMethods(tr)

15 for each(h1,h2)∈Hsim

16 ifcheckMethodInvoc(M1,M2,h1,h2)

（5）微課為主要形式建設(shè)教學(xué)資源。本課程屬于操作類課程，不僅有知識點(diǎn)，還有很多技能點(diǎn)，技能點(diǎn)的講解較為困難，因此對于知識點(diǎn)主要采用錄屏的方式，技能點(diǎn)主要采用拍攝操作微課的方式，著重講解操作要領(lǐng)和注意事項(xiàng)。同時制作動畫來配合微課，使技能點(diǎn)的講解更加清晰明了。

17R←R∪(h1,h2)

18 end if

19 end for

算法第1行通過文本型差異分析方法獲取hunk集H；第2行將H按照刪除行和增加行分裂為兩個集合H1和H2，H1中的每個hunk只含有刪除行，H2中的每個hunk只含有添加行；接下來在第4～10行檢測存在克隆關(guān)系的hunk元組，其中checkSimilar(h1,h2)函數(shù)用來檢測h1和h2的克隆關(guān)系；第11～14行得到兩個版本源文件分別對應(yīng)的抽象語法樹tl和tr，并從中抽取其中的方法集M1和M2；最后第15～19行實(shí)現(xiàn)對候選的hunk元組進(jìn)行判斷，確定是否在h1中存在對h2中新增方法的調(diào)用，其中函數(shù)checkMethodInvoc(M1,M2,h1,h2)實(shí)現(xiàn)此判斷，其具體流程在上一節(jié)已進(jìn)行描述，在此不再贅述。

2 算法的實(shí)現(xiàn)及驗(yàn)證

采用Java語言實(shí)現(xiàn)本文算法，它讀入兩個連續(xù)版本的Java源文件，識別其中的抽取方法模式。在當(dāng)前實(shí)現(xiàn)中，采用面向行的文本差異化分析工具Gun Differ來獲取hunk集，采用代碼克隆檢測工具simian實(shí)現(xiàn)對候選hunk集的檢測。simian可以識別Java、C、C++、Ruby、JSP等多種語言的源代碼和純文本文件中的相似代碼。即使兩個代碼塊略有不同，例如變量名稱、字符大小寫、修飾符、花括號、標(biāo)識符、數(shù)字、字符串略有改變，simian依舊可以識別。最后，采用eclipse jdt parser來獲取源文件的抽象語法樹。

2.1 數(shù)據(jù)來源

獲取了4個開源項(xiàng)目的數(shù)據(jù)集用于對算法的驗(yàn)證：

(1) eclipseJDTCore開源項(xiàng)目，它是一個基于Java的IDE，此次實(shí)驗(yàn)獲取2001/06/23-2013/10/16時間段的更新數(shù)據(jù)。

(2) maven開源項(xiàng)目，它是一個通過信息描述來管理項(xiàng)目的構(gòu)建、報(bào)告和文檔的一個開源的管理工具，此次實(shí)驗(yàn)獲取了2003/09/02-2014/01/29時間段的更新數(shù)據(jù)。

(3) jEdit是一個跨平臺的文本編輯器，此次實(shí)驗(yàn)獲取了1998/09/27-2012/08/08時間段的更新數(shù)據(jù)。

(4) google_guice是一個輕量級的依賴注入容器。數(shù)據(jù)的獲取時間段為:2006/08/23-2013/12/12。

2.2 simian參數(shù)與閾值設(shè)定

在使用本方法檢測抽取方法模式的時候，對simian工具進(jìn)行了包容度的設(shè)置，設(shè)置忽略了變量名字的改變、字符串的改變、數(shù)字的改變、確認(rèn)符的改變、子類名的改變，以上這些改變依然會被認(rèn)為是克隆代碼。

同時simian工具可以設(shè)置閾值，閾值表示simian工具對待判定代碼判斷為克隆代碼的嚴(yán)格程度，閾值越大，就越嚴(yán)格。使用一個名為dropwizard工具的項(xiàng)目作為測試項(xiàng)目，從1到9調(diào)整simian閾值，得到的查全率和查準(zhǔn)率如表1所示。

表1 不同simian閾值對應(yīng)的結(jié)果

圖3使用折線圖的形式更加直觀地描繪出了閾值對查準(zhǔn)率和查全率的影響，其中查準(zhǔn)率和查全率在縱軸表示，simian閾值在橫軸表示?？梢钥闯霾闇?zhǔn)率隨閾值的增大而增大，而查全率隨閾值的增大而減小，在閾值為5時達(dá)到均衡，因此以下實(shí)驗(yàn)取閾值為5。

圖3 在不同閾值下的查準(zhǔn)率和查全率

2.3 實(shí)驗(yàn)結(jié)果和分析

在simian閾值取5的條件下，對4個開源項(xiàng)目中的數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)，表2列出了各個項(xiàng)目檢測到的方法抽取模式的個數(shù)并以人工檢測結(jié)果作為基準(zhǔn)進(jìn)行準(zhǔn)確率判斷，計(jì)算出其查全率和查準(zhǔn)率?？梢钥吹狡洳槿试?5%～88%范圍內(nèi)，查準(zhǔn)率則在71%～82%之間波動。

表2 實(shí)驗(yàn)結(jié)果

3 結(jié) 語

本文提出了一種基于克隆代碼檢測的方法對存在抽取方法重構(gòu)模式的hunk元組進(jìn)行自動識別的算法，并在4個開源項(xiàng)目上進(jìn)行實(shí)驗(yàn)，結(jié)果表明其具有較高的準(zhǔn)確率。基于克隆代碼檢測的方法可應(yīng)用到存在代碼移動或復(fù)制的其他重構(gòu)模式，如移動方法、抽取類等的識別。本文的后續(xù)工作包括繼續(xù)提升算法的準(zhǔn)確率、在更多的開源項(xiàng)目上驗(yàn)證其有效性以及推廣應(yīng)用到其他重構(gòu)模式的識別。