基于代碼克隆檢測的抽取方法重構模式識別

張志浩 楊春花

(齊魯工業大學(山東省科學院)計算機科學與技術學院 山東 濟南 250000)

0 引 言

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

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

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

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

1 抽取方法重構模式的識別

1.1 變更代碼塊(hunk)

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

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

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

圖1 hunk示例

1.2 抽取方法模式

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

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

1.3 抽取方法模式的識別

抽取方法重構模式的代碼變更具有如下兩個特點：

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

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

因此，對這兩個特征進行判斷是識別抽取方法模式的關鍵。下面分別闡述這兩個特點的判斷方法。

1.3.1基于克隆檢測對方法的代碼移動進行判斷

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

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

為方便檢測，我們將每個hunk分裂為兩個子hunk：lefthunk和righthunk，前者存放hunk的刪除行，后者存放hunk的添加行。分裂后的兩個hunk保存原hunk的id，用于后期使用。例如，圖1的hunk1分裂后變為如圖2所示的兩個hunk：lefthunk和righthunk。

圖2 hunk的分裂

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

1.3.2對新增方法調用的判斷

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

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

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

在hunk中查找方法名及方法調用語句或方法調用表達式比較困難，因為hunk是文本，不攜帶語法信息,因此，我們采用抽象語法樹來輔助實現。具體的做法如下：

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

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

1.4 算 法

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

輸入:變更前后兩個版本的源文件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）微課為主要形式建設教學資源。本課程屬于操作類課程，不僅有知識點，還有很多技能點，技能點的講解較為困難，因此對于知識點主要采用錄屏的方式，技能點主要采用拍攝操作微課的方式，著重講解操作要領和注意事項。同時制作動畫來配合微課，使技能點的講解更加清晰明了。

17R←R∪(h1,h2)

18 end if

19 end for

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

2 算法的實現及驗證

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

2.1 數據來源

獲取了4個開源項目的數據集用于對算法的驗證：

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

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

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

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

2.2 simian參數與閾值設定

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

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

表1 不同simian閾值對應的結果

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

圖3 在不同閾值下的查準率和查全率

2.3 實驗結果和分析

在simian閾值取5的條件下，對4個開源項目中的數據集進行了實驗，表2列出了各個項目檢測到的方法抽取模式的個數并以人工檢測結果作為基準進行準確率判斷，計算出其查全率和查準率。可以看到其查全率在75%～88%范圍內，查準率則在71%～82%之間波動。

表2 實驗結果

3 結 語

本文提出了一種基于克隆代碼檢測的方法對存在抽取方法重構模式的hunk元組進行自動識別的算法，并在4個開源項目上進行實驗，結果表明其具有較高的準確率?；诳寺〈a檢測的方法可應用到存在代碼移動或復制的其他重構模式，如移動方法、抽取類等的識別。本文的后續工作包括繼續提升算法的準確率、在更多的開源項目上驗證其有效性以及推廣應用到其他重構模式的識別。