張志浩 楊春花

摘 要：內(nèi)聯(lián)函數(shù)（Inline method）和替換算法（Substitute algorithm）是2種在代碼重構(gòu)中常用的重構(gòu)手法，本文提出一種基于代碼變更塊和抽象語法樹的重構(gòu)模式識別算法，首先篩選出變更前后2個文件的代碼變更塊，找到可能屬于這2種重構(gòu)模式的代碼變更塊，再建立抽象語法樹對這些變更塊中的代碼進(jìn)行準(zhǔn)確的語法分析，對其是否屬于此2種模式進(jìn)行判定。該算法在4個開源項(xiàng)目上進(jìn)行了實(shí)驗(yàn)驗(yàn)證，表明了其具有較高的準(zhǔn)確率。

關(guān)鍵詞： 重構(gòu)模式; 抽象語法樹; 代碼變更塊; 內(nèi)聯(lián)函數(shù); 替換算法

文章編號： 2095-2163（2019）03-0146-05 中圖分類號： TP311.5 文獻(xiàn)標(biāo)志碼： A

0 引 言

代碼重構(gòu)[1]是在軟件開發(fā)的過程中一種常用的在結(jié)構(gòu)層次上的代碼整理手段，其能在不改變軟件可觀察行為的前提下，對軟件的結(jié)構(gòu)進(jìn)行調(diào)整，提高其可拓展性、可維護(hù)性、可讀性，從而提升其質(zhì)量，并降低其維護(hù)成本。

目前對重構(gòu)的研究主要集中在代碼自動重構(gòu)這一方面，相關(guān)研究主要有：使用抽象語法樹和靜態(tài)代碼分析的克隆代碼自重構(gòu)方法[2]、基于K-近鄰的C克隆代碼重構(gòu)方法[3]、單例模式導(dǎo)向的源代碼自動重構(gòu)研究[4]、面向Java鎖機(jī)制的字節(jié)碼自動重構(gòu)框架[5]等等。

重構(gòu)模式識別指的是對比變更前原代碼和變更后代碼以尋找符合某種重構(gòu)模式代碼段。在代碼更新中，往往包含著對老版本代碼的bug的修復(fù)、功能的添加以及重構(gòu)的代碼變更，這3種種類各異的代碼變更方式的摻雜增加了閱讀其代碼、理解其內(nèi)容的難度，若能對其中的重構(gòu)代碼進(jìn)行自動識別，則可使重構(gòu)與其他種類的變更相互分離，利于代碼的閱讀和理解。對代碼重構(gòu)模式的識別的研究也在繼續(xù)深入之中 Fokaefs等人[6]開發(fā)了一種eclipse插件、Weissgerber等人[7]提出了基于簽名分析的方法、Prete等人[8]開發(fā)了REF-FINDER，這種工具可以對幾種重構(gòu)模式進(jìn)行識別，劉陽等人[9]提出了一種方法可以識別函數(shù)抽取。鐘林輝等人[10]提出了一種基于版本的多重軟件重構(gòu)自動檢測技術(shù)。以上研究中沒有涉及到有關(guān)內(nèi)聯(lián)函數(shù)和替換算法這2種重構(gòu)模式的識別，本文即對此實(shí)現(xiàn)了相應(yīng)的識別算法。

1 內(nèi)聯(lián)函數(shù)與替換算法重構(gòu)模式的識別

1.1 變更代碼塊

目前對代碼變更的提取方法有2種。一種是語法分析法，通過對比2個文本的抽象語法樹獲取差異部分，另一種基于文本差異的對比方法，直接比較目標(biāo)文本的差異，獲取差異部分。

本文考慮到算法效率，采用第二種方式，通過基于文本差異的對比方法獲取其基本輸出單位變更代碼塊（hunk），一個hunk可以由刪除行和添加行這2個部分組成，也可以只包含刪除行部分或添加行部分，研究中列出了同屬于項(xiàng)目google_guice（https：//github.com/google/guice/）的3個hunk即如圖1所示。其中，hunk1中的67～76行是刪除行，行首為減號，71～73行為添加行，行首為加號;hunk2只包含添加行;hunk3只包括刪除行。

1.2 抽象語法樹

抽象語法樹是在編程語言源代碼的翻譯和編譯過程中使用的一種中間表示形式，其結(jié)構(gòu)類似于樹狀結(jié)構(gòu)，樹上的每一個節(jié)點(diǎn)都表示源代碼中的一種結(jié)構(gòu)，但是抽象語法樹的節(jié)點(diǎn)并不是對應(yīng)真實(shí)語法的每一個細(xì)節(jié)，比如對于嵌套括號等沒有對應(yīng)的節(jié)點(diǎn)，故稱為抽象語法樹。利用抽象語法樹可以對代碼進(jìn)行一定的語法分析。

1.3 內(nèi)聯(lián)函數(shù)重構(gòu)模式的識別

1.3.1 內(nèi)聯(lián)函數(shù)模式

內(nèi)聯(lián)函數(shù)模式在代碼重構(gòu)中經(jīng)常出現(xiàn)，當(dāng)遇見某個函數(shù)的內(nèi)部代碼和其函數(shù)名同樣清晰易讀的小粒度函數(shù)時，可以使用這個重構(gòu)模式。一般情況下，其運(yùn)行過程是將這一個或幾個小粒度函數(shù)的函數(shù)體提取到對此函數(shù)的調(diào)用語句處，并刪除調(diào)用語句和此小粒度原函數(shù)。

繼而，研究中列出了2個hunk如圖2所示，且均屬于google_guice（https：//github.com/google/guice/）項(xiàng)目中版本為315ee3fe10的InjectorImpl.java文件，hunk4中（729～734行）中的injectMembers（ ）函數(shù)整體被移除，函數(shù)體被轉(zhuǎn)移到hunk5的（756～758行）call（ ）函數(shù)中，并且call（ ）函數(shù)中的對injectMembers（）函數(shù)的引用（776行）也被移除，這就是一種典型的內(nèi)聯(lián)函數(shù)重構(gòu)模式。

1.3.2 內(nèi)聯(lián)函數(shù)模式識別

假設(shè)原代碼中有A，B兩個函數(shù)，設(shè)為A1，B1，變更后代碼中也有A函數(shù)，設(shè)為Ar，若此次變更為內(nèi)聯(lián)函數(shù)重構(gòu)模式，則此代碼所具有特點(diǎn)可概述為：

（1）B1函數(shù)的函數(shù)體代碼被添加到變更后代碼中的Ar函數(shù)里，之后B1函數(shù)被整體移除。

（2）A1中有對B1的引用，但Ar函數(shù)中沒有對B1函數(shù)的引用語句。

對這2個特點(diǎn)的判斷是識別內(nèi)聯(lián)函數(shù)模式的重點(diǎn)，為了方便起見，稱可能符合上述2個特點(diǎn)的函數(shù)，如A1，Ar為A型節(jié)點(diǎn)，可能符合上述2個特點(diǎn)的函數(shù)，如B1為B型節(jié)點(diǎn)，下文對這2個特點(diǎn)的識別方法分別進(jìn)行研究闡述。

1.3.3 基于相似度檢測對函數(shù)級代碼移動進(jìn)行判斷

由于要單獨(dú)使用到hunk中的刪除行或添加行，方便起見，按照添加行和刪除行將各個hunk分為2個部分，即添加部分（addpart）和刪除部分（delpart），如圖3所示，圖1中的hunk1拆分為addpart和delpart。

第一個特點(diǎn)本質(zhì)是檢測是否有函數(shù)級代碼的移動，設(shè)B1函數(shù)包含在某個hunk（設(shè)為h1）的刪除行中，而Ar中增加的代碼則包含在某個hunk（設(shè)為h2）的添加行中，因此對第一個特點(diǎn)的判斷就是判斷h1中的刪除行和h2中的添加行是否有相似關(guān)系，即h1.delpart是否和h2.addpart存在相似關(guān)系。

1.3.4 基于抽象語法樹對函數(shù)引用情況進(jìn)行判斷

對第二個特點(diǎn)的判斷需要考察A1函數(shù)代碼中是否有對B1函數(shù)的引用語句，以及Ar函數(shù)中是否已經(jīng)移除對B1函數(shù)的引用語句，對此研究過程可闡釋如下。

（1）在符合第一個特點(diǎn)的情況下，對原代碼文件和變更后代碼文件分別生成抽象語法樹，并且獲取2棵語法樹的所有函數(shù)節(jié)點(diǎn)（Method node），函數(shù)節(jié)點(diǎn)有行范圍，h1.delpart和h2.addpart同樣有行范圍，對比匹配兩者的行范圍可以找出B1和Ar函數(shù)節(jié)點(diǎn)，因?yàn)楹瘮?shù)節(jié)點(diǎn)包含函數(shù)頭的所有信息，故可獲取Ar函數(shù)節(jié)點(diǎn)的函數(shù)名，并根據(jù)此函數(shù)名遍歷原代碼文件的所有函數(shù)節(jié)點(diǎn)，找到同名同參數(shù)的A1函數(shù)節(jié)點(diǎn)。

（2）遍歷Ar函數(shù)節(jié)點(diǎn)的所有子節(jié)點(diǎn)，確定是否存在一個對B1的方法調(diào)用節(jié)點(diǎn)，并于A1函數(shù)節(jié)點(diǎn)中確認(rèn)此方法調(diào)用節(jié)點(diǎn)是否已經(jīng)被刪除。

1.3.5 內(nèi)聯(lián)函數(shù)重構(gòu)模式識別算法

此算法輸入2個版本的源文件filel和filer與第一步輸出hunk集合H={}，其中h1的刪除部分和h2的添加部分有相似關(guān)系，輸出存在內(nèi)聯(lián)函數(shù)模式的函數(shù)節(jié)點(diǎn)（Method node）集合O={}，其中n1，n2是filel的A型和B型節(jié)點(diǎn)，n3是filer的A型節(jié)點(diǎn)，n1， n2， n3之間存在內(nèi)聯(lián)函數(shù)重構(gòu)模式關(guān)系。算法的偽代碼詳見如下。

輸入：2個版本的源文件filel和filer與第一步輸出的hunk集合H

輸出：存在內(nèi)聯(lián)函數(shù)模式的函數(shù)節(jié)點(diǎn)（Method node）集合O

（Hl，Hr）←getAllHunks（filel， filer）

H←filter（Hl，Hr）

（Hd， Ha）←split（H）

Rd←gethunkrange（Hd）

Ra←gethunkrange（Ha）

tl←generateAST（filel）

tr←generateAST（filer）

M1←getAllMethodNodes（tl）

M2←getAllMethodNodes（tr）

Mdel←， Madd←

for each rd∈Rd， ra∈Ra

for each m1∈M1， m2∈M2

rm1←getMethodRange（m1）

rm2←getMethodRange（m2）

if rm1rd

Mdel←Mdel∪m1

end if

if? rarm2

Madd←Madd∪m2

end if

end for

end for

MA←getLeftAMethod（Madd）

for each （madd， mdel， mA）∈（Madd， Mdel， MA）

if? checkInvoc（（madd， mdel， mA））

O←O∪（madd， mdel， mA）

end if

end for

算法第1行使用getAllHunks（）函數(shù)獲取2個版本的源文件filel，filer的所有hunk集合（Hl， Hr）;算法第2行使用filter（）函數(shù)選取Hl中的hunk的刪除部分和Hr中的hunk的添加部分相似的hunk集合H={};算法第3行使用split（）函數(shù)將H中屬于filel的hunk.delpart取出來放進(jìn)Hd，將屬于filer的hunk.addpart取出來放進(jìn)Ha;第4，5行獲取行范圍Rd，Ra;第11～22行對Rd，Ra和M1，M2的行范圍rm1，rm2進(jìn)行對比匹配，挑選出Hd的行范圍包含的函數(shù)節(jié)點(diǎn)集合Mdel的行范圍和行范圍包含ra的函數(shù)節(jié)點(diǎn)集合Madd;第23行通過getLeftAMethod（）函數(shù)獲取屬于filel的和Madd同名函數(shù)節(jié)點(diǎn)集合MA;第24～28行對屬于filel的A型節(jié)點(diǎn)mA，B型節(jié)點(diǎn)mdel，屬于filer的A型節(jié)點(diǎn)madd通過checkInvoc（）函數(shù)判斷mA中是否有對mdel的調(diào)用語句和madd中是否已經(jīng)移除對mdel的調(diào)用語句。

1.4 替換算法重構(gòu)模式的識別

1.4.1 替換算法模式介紹

在對代碼的更新的過程中，隨著對問題有了更多的理解，或者相關(guān)代碼有所改動，往往需要對某個函數(shù)進(jìn)行替換，這種做法在重構(gòu)模式中即可稱為替換算法（Substitute algorithm）。一般情況下，其運(yùn)行過程是在某個函數(shù)的函數(shù)頭不變的情況下，用新函數(shù)體替換此原函數(shù)的函數(shù)體。

圖4的代碼來自于maven（https：//github.com/apache/maven/）版本為01ae529的RemoteSnapshotMetadata.java文件，可以看到函數(shù)getExpandedVersion（Artifact artifact）的原函數(shù)體被移除（行94），被替換成了新的函數(shù)體（94～95行），這就是一個典型的替換算法重構(gòu)模式實(shí)例。

1.4.2 [ZK（]基于抽象語法樹和代碼變更塊對替換算法模式進(jìn)行識別

對于替換算法模式而言，可歸納為2個特點(diǎn)，對此可概述為：

（1）原函數(shù)和變更后函數(shù)的函數(shù)頭相同，即原函數(shù)的函數(shù)頭沒有發(fā)生改變。

（2）原函數(shù)的函數(shù)體和變更后函數(shù)的函數(shù)體發(fā)生了改變。

設(shè)有原文件filel變更后文件filer，先使用文本型代碼差異化分析工具獲取這2個文件的變更代碼塊集，替換算法發(fā)生在一個hunk之中，故對此hunk集的所有hunk進(jìn)行篩選，篩掉只有添加部分或刪除部分的hunk，獲取hunk集（設(shè)為H），用同樣的方法獲取H的刪除部分和添加部分集（設(shè)為Ha，Hd）。

使用語法樹分別獲取filel和filer在H中包含的函數(shù)節(jié)點(diǎn)Ml，Mr，若這2個節(jié)點(diǎn)的函數(shù)頭相同，并且2個節(jié)點(diǎn)的函數(shù)體分別就是刪除部分和添加部分，則滿足替換算法模式的特點(diǎn)（1）。

在滿足第一個特點(diǎn)的前提下，若Ml和Mr節(jié)點(diǎn)的函數(shù)體不同，則滿足替換算法模式的特點(diǎn)（2），可以使用代碼相似度檢測技術(shù)進(jìn)行檢測，判斷Ml和Mr節(jié)點(diǎn)的函數(shù)體是否不同。

1.4.3 算法

此算法輸入變更前后2個版本的源文件filel和filer，輸出存在替換算法模式的函數(shù)節(jié)點(diǎn)（MethodNode）元組的集合Ms={}，M1，M2是2個函數(shù)節(jié)點(diǎn)，符合替換算法重構(gòu)模式。研究給出算法的偽代碼詳見如下。

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

輸出：存在替換算法模式的函數(shù)節(jié)點(diǎn)集合Ms

Hs ← getAllHunks（filel， filer）

H←

for each hs ∈Hs

if （hs.addpart≠）&&（hs.delpart≠）

H← H∪hs

end if

end for

（Hd， Ha）←split（H）

tl←createAST（filel）

tr←createAST（filer）

M1←getAllMethods（tl）

M2←getAllMethods（tr）

（Ml，Mr）←match（H，M1， M2）

Ms←

for each（ml，mr）∈（Ml，Mr）

if （！checkSimilar（（ml， mr））

&&checkMethodHead（（ml， mr）））

Ms← Ms∪（ml， mr）

end if

end for

算法第1行是通過文本型差異分析方法獲取2個文件的所有hunk集Hs，3～7行將Hs里的所有存在添加部分和刪除部分的hunk篩選出放入集合H，第8行是將H按照刪除部分、還是添加部分分離為（Hd， Ha），第13行Match（H，M1， M2）函數(shù)的功能和上一算法偽代碼的第11～22行的功能一致，即實(shí)現(xiàn)通過hunk獲取相關(guān)函數(shù)節(jié)點(diǎn);第15～19行實(shí)現(xiàn)對函數(shù)節(jié)點(diǎn)ml， mr函數(shù)體是否不同和對其函數(shù)頭是否相同的判斷，即是否是替換算法重構(gòu)模式，并將符合替換算法重構(gòu)模式的函數(shù)節(jié)點(diǎn)元組（ml，mr）放置入Ms中，其中checkSimilar（）函數(shù)用于檢測ml， mr函數(shù)節(jié)點(diǎn)的函數(shù)體是否相似，若不相似說明函數(shù)體已經(jīng)被替換，本文使用編輯距離算法來計(jì)算相似度;checkMethodHead（（ml， mr））函數(shù)用于檢測ml， mr這2個節(jié)點(diǎn)的函數(shù)頭是否相同，其方法是比較函數(shù)節(jié)點(diǎn)中的數(shù)個屬性（MODIFIERS，RETURN_TYPE，NAME，PARAMETER，THROW_EXCEPTIONS）是否都相同，至此得到最終結(jié)果。

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

本文使用Java編程語言來實(shí)現(xiàn)這2個算法，采用面向行的文本差異化分析工具Gun Differ（http：//www.gnu.org/software/diffutils/）獲取Hunk集，采用eclipse jdt parser來獲取源文件的抽象語法樹，在4個開源項(xiàng)目上進(jìn)行了實(shí)驗(yàn)驗(yàn)證。研究內(nèi)容具體如下。

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

獲取了4個開源項(xiàng)目的數(shù)據(jù)集用于對算法的驗(yàn)證，對此擬做出闡析分述如下。

（1）eclipseJDTCore（https：//github.com/eclipse/eclipse.jdt.core） 開源項(xiàng)目，這是一個針對Java的集成開發(fā)環(huán)境，此次實(shí)驗(yàn)獲取時間段為2001/06/23～2013/10/16的更新數(shù)據(jù)。

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

（3）jEdit（https：//github.com/linzhp/jEdit-Clone），這是一個跨平臺的文本編輯器，此次實(shí)驗(yàn)獲取了時間段為1998/09/27～2012/08/08的更新數(shù)據(jù)。

（4）google_guice（https：//github.com/google/guice/）是一個輕量級的依賴注入容器。數(shù)據(jù)的獲取時間段為：2006/08/23～2013/12/12。

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

本文對來自于上述4個開源項(xiàng)目的數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)，同時列出了內(nèi)聯(lián)函數(shù)模式檢測算法所檢測到的內(nèi)聯(lián)函數(shù)模式的個數(shù)見表1，并以人工檢測的結(jié)果為基準(zhǔn)獲得了其查全率和查準(zhǔn)率。

可以看到，內(nèi)聯(lián)函數(shù)識別實(shí)驗(yàn)結(jié)果顯示查全率在70%～86%之間波動。查準(zhǔn)率在71%～80%之間波動。

接下來，研究列出了替換算法重構(gòu)模式識別算法所檢測到的替換算法模式的個數(shù)見表2，同樣以人工檢測的結(jié)果為基準(zhǔn)獲得了其查全率和查準(zhǔn)率。

可以看到，在替換算法模式識別結(jié)果中，對這4個開源項(xiàng)目的識別。實(shí)驗(yàn)得出，查全率在71%～80%之間波動。查準(zhǔn)率在72%～84%之間波動。

分析可知，查全率和查準(zhǔn)率沒有達(dá)到100%的一個原因在于Gun Differ對于大粒度的函數(shù)的改動容易劃分為多個hunk，使得各個hunk只包含這個大粒度函數(shù)的一部分，在算法的運(yùn)行過程中被自動篩去，以后可以增加hunk合并機(jī)制，讓某個大粒度函數(shù)的多個hunk合并為一個hunk，讓一個hunk就能夠包含此大粒度函數(shù)，從而為這2個算法所識別。

3 結(jié)束語

本文提出了基于代碼變更塊和抽象語法樹的對內(nèi)聯(lián)函數(shù)和替換算法重構(gòu)模式自動識別的算法，在4個開源項(xiàng)目上進(jìn)行了實(shí)驗(yàn)，表明其有較高的準(zhǔn)確率，這種基于代碼變更塊和抽象語法樹的算法也可以對其它有著代碼移動情況的代碼重構(gòu)模式，如移動字段（Move field）、抽取類（Extract Class）等進(jìn)行識別，后續(xù)工作仍需開發(fā)出針對大粒度函數(shù)的多個hunk合并機(jī)制以提高算法的準(zhǔn)確率，在更多的數(shù)據(jù)集上驗(yàn)證其有效性，進(jìn)而將其應(yīng)用到其它類型的重構(gòu)模式識別上。

參考文獻(xiàn)

[1] FOWLER M. 重構(gòu)—改善既有代碼設(shè)計(jì)[M]. 北京：中國電力出版社，2003.

[2] 于冬琦，彭鑫，趙文耘. 使用抽象語法樹和靜態(tài)分析的克隆代碼自動重構(gòu)方法[J]. 小型微型計(jì)算機(jī)系統(tǒng)，2009，30（9）：1752-1760.

[3]? 馮江輝. 基于K-最近鄰的C克隆代碼重構(gòu)方法研究[D]. 哈爾濱：哈爾濱工業(yè)大學(xué)，2011.

[4]? 劉偉，胡志剛，劉宏韜. 單例模式導(dǎo)向的源代碼自動重構(gòu)研究[J]. 小型微型計(jì)算機(jī)系統(tǒng)，2014，35（12）：2664-2669.

[5] 張楊，張冬雯，仇晶. 面向Java鎖機(jī)制的字節(jié)碼自動重構(gòu)框架[J]. 計(jì)算機(jī)科學(xué)，2015，42（11）：84-89.

[6] FOKAEFS M，TSANTALIS N， STROULIA E， et al. Identification and application of extract class refactorings in object-oriented systems[J]. Journal of Systems and Software，2012， 85（10）： 2241-2260.

[7] WEISSGERBER P， DIEHL S. Identifying refactorings from source-code changes[C]// Proceedings of the 21st IEEE/ACM International Conference on Automated Software Engineering （ASE'06）. Tokyo， Japan：IEEE，2006： 231-240.

[8] PRETE K， RACHATASUMRIT N， SUDAN N， et al. Template-based reconstruction of complex refactorings[C]//ICSM '10 Proceedings of the 2010 IEEE International Conference on Software Maintenance.Washington， DC， USA ：IEEE， 2010：1-10.

[9] 劉陽，劉秋榮，劉輝 . 函數(shù)抽取重構(gòu)的自動檢測方法[J]. 計(jì)算機(jī)科學(xué)，2015，42（12）：105-107.

[10]鐘林輝，黃小明，薛良波，等.? 基于版本的多重軟件重構(gòu)自動檢測技術(shù)研究[J]. 江西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，42（5）：464-469，472.