面向大規(guī)模多版本軟件系統(tǒng)的代碼克隆檢測加速技術(shù)

方維康 吳毅堅 趙文耘

(復(fù)旦大學(xué)軟件學(xué)院 上海 200438) (復(fù)旦大學(xué)上海市數(shù)據(jù)科學(xué)重點實驗室 上海 200438)

0 引 言

在軟件項目的開發(fā)過程中，開發(fā)人員經(jīng)常會通過拷貝粘貼已有代碼片段并伴隨著或多或少的修改來提升開發(fā)效率，這種復(fù)用方式會導(dǎo)致代碼中存在一些完全相同或極其相似的代碼片段，這種完全相同或極其相似的代碼片段通常被稱為代碼克隆。現(xiàn)有的研究報告和經(jīng)驗證據(jù)表明，一個典型軟件系統(tǒng)的9%～17%是由克隆代碼組成的[1]。

代碼克隆通常被認為是一種特殊的代碼味道，對軟件系統(tǒng)的開發(fā)和維護有諸多負面的影響。目前已有許多研究揭示了代碼克隆與程序的缺陷率、軟件穩(wěn)定性、軟件質(zhì)量、軟件維護成本等的關(guān)系[2-9]。所以，為方便克隆研究與維護工作的進行，首要任務(wù)是檢測系統(tǒng)中的代碼克隆。

目前，已經(jīng)有許多研究人員針對克隆檢測方法和技術(shù)進行了研究[10-21]，但這些工具僅針對軟件系統(tǒng)的單個版本進行克隆檢測。而在許多應(yīng)用場景下，例如代碼來源分析、構(gòu)建代碼克隆譜系等[22]，需要獲取軟件系統(tǒng)各個版本的代碼克隆信息。傳統(tǒng)的做法是對軟件系統(tǒng)的各個版本進行克隆檢測。但在軟件系統(tǒng)規(guī)模較大、版本較多時，這種檢測方式往往比較耗時，尤其是對多個系統(tǒng)進行跨項目克隆檢測，這種方式甚至難以進行。經(jīng)研究表明，軟件系統(tǒng)每次經(jīng)歷版本更新時，變更的代碼量只占系統(tǒng)代碼總量的一小部分，當(dāng)系統(tǒng)趨于穩(wěn)定時則尤為明顯。因此實際上，在對系統(tǒng)的各個版本進行克隆檢測時，有許多重復(fù)的代碼被反復(fù)檢測，造成很大的性能浪費。如果能夠在檢測過程中自動識別版本間重復(fù)的代碼而不需要重復(fù)檢測，將會大大節(jié)約檢測的資源和時間。

針對以上問題，本文設(shè)計并實現(xiàn)一種面向多版本軟件系統(tǒng)的代碼克隆檢測加速技術(shù)。該方法首先將不同版本、代碼內(nèi)容相同或高度相似的同一方法構(gòu)建方法版本組，再選取每個方法版本組中最早的版本作為樣本方法，樣本方法的集合稱為歷史映像，然后對所有的歷史映像進行克隆檢測，同時建立起樣本方法和方法版本組間的方法關(guān)系。最終根據(jù)樣本方法的克隆檢測結(jié)果和方法索引恢復(fù)原始的全量克隆關(guān)系。其中，如何快速分析出系統(tǒng)所有版本中的每個方法，基于局部相似性比較在前后版本快速建立演化關(guān)系，基于索引快速恢復(fù)所有克隆關(guān)系，都是該方法需要解決的問題。

1 代碼克隆

1.1 代碼克隆相關(guān)定義

代碼克隆認可度較高的定義是，如果軟件系統(tǒng)代碼庫中的兩個或多個代碼片段彼此相同或近似，則稱之為代碼克隆[23-24]。按照克隆之間的相似程度劃分，克隆被分為四種類型。

Ⅰ型克隆：除去空白符和注釋之外完全一樣的代碼片段。

Ⅱ型克隆：除了空白符、注釋、標識符、類型和字面值有可能不同之外，語法結(jié)構(gòu)上完全一致的代碼片段。

Ⅲ型克隆：除了空白符、注釋、標識符、類型和字面值有可能不同之外，還有可能添加、修改或刪除了一些代碼行的代碼片段。

Ⅳ型克隆：功能上一致但代碼本身相似度較低的代碼片段。該種克隆類型比較特殊，它通常不是由復(fù)制粘貼產(chǎn)生的，而是不同開發(fā)人員對同一種功能的不同實現(xiàn)，例如不同的排序算法。

不難發(fā)現(xiàn)，從Ⅰ型克隆到Ⅲ型克隆，克隆片段之間的語法相似度逐漸降低。而Ⅳ型克隆類型的克隆從代碼文本和語法結(jié)構(gòu)層面已經(jīng)難以直觀地看出克隆實例之間的相似性，通常檢測難度較大，因此本文的克隆檢測加速方法僅面向前三種類型的克隆。

為了后文闡述方便，下面對一些專用名詞或術(shù)語進行簡單的解釋。

克隆對：存在克隆關(guān)系的兩個代碼片段被稱為一組克隆對。

克隆組(類)：一組存在克隆關(guān)系的代碼片段被稱為克隆組。

克隆實例：克隆對或克隆組中的每一個代碼片段都稱為一個克隆實例。

方法級克隆：如果兩個或多個方法是彼此克隆的，則將這種克隆稱為方法級克隆。方法級克隆的克隆實例是完整的方法。

1.2 大規(guī)模多版本克隆檢測的背景與挑戰(zhàn)

在過去幾十年的代碼克隆研究中，已經(jīng)提出了許多用于檢測代碼克隆的技術(shù)，并實現(xiàn)了許多克隆檢測工具。這些技術(shù)和工具根據(jù)所基于的代碼特征大致分為基于文本[10-11]、基于token[12-13]、基于程序依賴圖[14-15]、基于抽象語法樹[16-17]、基于代碼底層表示[18]等。其中，只有SourcererCC[25]和SAGA[26]在大規(guī)模克隆檢測(億行級)上依舊表現(xiàn)良好。

這些工具通常僅面向軟件系統(tǒng)的單個版本進行克隆檢測。在許多場景下，例如為項目構(gòu)建克隆演化譜系時[12]，需要先獲取軟件系統(tǒng)的各個版本的克隆情況。傳統(tǒng)做法是采用已有的克隆檢測工具分別對系統(tǒng)的每個版本進行克隆檢測，而在軟件規(guī)模較大或者軟件版本較多時，這種方式會非常耗時。

針對多版本的克隆檢測，研究人員提出過一些優(yōu)化措施。例如，只對目標項目的初始版本進行克隆檢測，接著根據(jù)版本控制工具記錄的修改信息追蹤克隆，但這種方式實際上會丟失所有初始版本之后出現(xiàn)的克隆[22]。另一種優(yōu)化方式是采用增量克隆檢測[14]，但這種方式不適用于跨項目克隆檢測。

由上可知，在處理大規(guī)模多版本軟件系統(tǒng)進行克隆檢測，尤其是多個多版本系統(tǒng)進行跨項目克隆檢測時，現(xiàn)有的克隆檢測工具通常耗時過長甚至無法正常運行。而實際上，多版本系統(tǒng)中不同版本間的代碼存在大量重復(fù)，反復(fù)檢測這些重復(fù)代碼浪費了大量的工具性能。如果能夠在檢測過程中快速識別這些重復(fù)代碼以避免重復(fù)檢測，將會大大提升大規(guī)模多版本系統(tǒng)克隆檢測的效率，也使得檢測更大規(guī)模的多版本系統(tǒng)成為可能。鑒于此，本文提出一種獨立于克隆檢測工具的針對多版本軟件系統(tǒng)的克隆檢測加速技術(shù)。

2 基于版本間代碼壓縮的多版本克隆檢測加速技術(shù)

本節(jié)將對所提出的多版本軟件系統(tǒng)克隆檢測加速技術(shù)的具體設(shè)計及流程進行詳細介紹。該技術(shù)不僅可以對單個多版本軟件系統(tǒng)進行克隆檢測，還可以對多個多版本軟件系統(tǒng)進行跨項目克隆檢測，下面將以跨項目克隆檢測為例介紹該技術(shù)。考慮到片段級克隆數(shù)量較多、過于細碎且不同的克隆檢測工具對片段的界定方式有所不同，所以本文只討論方法級克隆的檢測。多版本軟件系統(tǒng)克隆檢測方法主要分為以下幾個步驟：(1) 項目信息預(yù)處理;(2) 構(gòu)建目標項目的歷史映像;(3) 對目標項目的歷史映像進行克隆檢測;(4) 恢復(fù)全量克隆關(guān)系。

2.1 項目信息預(yù)處理

本文將所有待檢測的項目稱為目標項目集。在進行后續(xù)步驟之前，需要先對目標項目進行預(yù)處理，主要包括項目版本信息提取和項目方法信息提取。

版本信息提取：對于每個目標項目，需要收集該項目所有發(fā)布版本的相關(guān)信息，包括每個版本的名稱、發(fā)布時間、各個版本的代碼，同時將該項目的各個版本按照發(fā)布時間先后進行組織排序。該步驟相對比較簡單，其主要目的是為后續(xù)的步驟做準備。本文的目標是提出一個通用的多版本軟件系統(tǒng)克隆檢測加速方法，所有對于任何形式的多版本軟件系統(tǒng)，只需要按照規(guī)定的信息格式給出版本相關(guān)信息并準備好各個版本的代碼即可。例如，對于由Git、SVN等源代碼版本管理工具管理的項目，可以非常方便地使用相關(guān)命令導(dǎo)出版本信息。而對于沒有版本管理工具介入的項目，也可以按照規(guī)定格式手動地給出版本信息。

方法信息提取：對目標項目的每個版本，設(shè)計一個方法提取器來提取代碼中所有方法的相關(guān)信息，其中根據(jù)該項目所使用的編程語言采用了相關(guān)的語法解析工具(例如JavaParser、TXL等)。這些信息包括方法簽名、方法完全限定名、方法所在文件的路徑、方法起止行，最后將這些信息以方法為單位保存到一個集合中，將其稱為該版本的方法信息集合。

2.2 構(gòu)建歷史映像

鑒于傳統(tǒng)的全量克隆檢測方法需要對目標項目的所有版本進行克隆檢測，而這些重復(fù)的代碼也會在檢測中被反復(fù)比較而浪費大量時間。因此，提出一種面向多版本代碼的克隆檢測加速技術(shù)。我們不再過多地關(guān)注克隆檢測本身如何加速，而是將工作重心轉(zhuǎn)移到版本間重復(fù)代碼的標記識別以及去除上，通過大幅度地壓縮被檢測的代碼量來縮減克隆檢測時間，壓縮后的代碼稱為歷史映像。

構(gòu)建歷史映像的主要過程包括，為不同版本中方法名及所屬文件路徑一致且代碼內(nèi)容相同或高度相似的同一方法(下文簡稱為相同方法)構(gòu)建方法版本組，再選取每個方法版本組中最早的版本作為樣本方法，樣本方法的集合則稱為歷史映像。構(gòu)建單個項目歷史映像主要包括構(gòu)建方法版本組和選擇樣本方法兩個步驟。

構(gòu)建方法版本組：在項目信息進行預(yù)處理之后，得到了每個目標項目的各個版本的方法信息集合。接下來，需要根據(jù)這些方法信息，尋找并標記版本間相同的方法。為此，我們實現(xiàn)了一個方法映射器用于將含有多個版本的項目基于方法名及文件路徑構(gòu)建將不同版本、代碼內(nèi)容相同或高度相似的相同方法構(gòu)建方法版本組。值得注意的是，本文所指的相同方法并不是完全指代碼文本完全一致的方法，而是指符合本文規(guī)定的判定標準的方法。本文相同方法的具體判定標準是方法完全限定名相同、方法所在的文件的路徑一致且方法源代碼間有非常高的文本相似度，我們使用的是最長公共子序列長度來衡量文本相似程度。這里沒有限定方法文本必須完全相同，是因為在很多情況下，部分方法在演化過程中經(jīng)歷的修改可能會非常細微，就方法整體而言幾乎看不出任何變化，這樣的方法被當(dāng)作新方法并不合適。另一方面，由于不同版本中只有方法完全限定名相同且方法所在的文件的路徑一致的方法才會進行本文相似度的比較，而在具體某個版本中方法完全限定名及其文件路徑實際上可以唯一確定一個方法，所以每個方法至多只需要進行一次相似度比較，整體效率較高。

具體的對于單個目標項目的方法版本組構(gòu)建規(guī)則如下：首先將該項目的各個版本按照發(fā)布時間排好順序，接著按順序處理該項目的每個版本。具體處理規(guī)則是，首先提取當(dāng)前版本中的所有方法，對于每個方法，判斷其是否已經(jīng)屬于某個方法版本組，是則跳過；否則，建立一個新的方法版本組，對于該方法，提取其方法名與所在文件的相對路徑，查找所有后續(xù)版本中與該相對路徑、方法名都相同且文本高度相似的方法，將這些方法添加到該新的方法版本組。

構(gòu)建方法版本組最重要的是建立版本間相同方法的關(guān)聯(lián)，其中相同方法判定依據(jù)是方法完全限定名相同、方法所在的文件的路徑一致且方法源代碼間有非常高的相似度。按照這樣的限定規(guī)則，更名方法以及移動到其他文件方法都將被視作新的方法，在克隆檢測過程中它們?nèi)詫⑴c比較，這似乎有悖于我們的初衷。但實際上，如果僅考慮方法間的相似度，則在為某個方法構(gòu)建方法版本組時，將不得不與后續(xù)版本中的所有方法進行相似度比較，時間復(fù)雜度將會達到O(n2)級別(n為方法數(shù))，并且相似度的比較本身也比較復(fù)雜，所以整個過程會相當(dāng)耗時，導(dǎo)致整個過程可能比進行全版本克隆檢測更加低效。而加上方法完全限定名和文件路徑的限制后，效率會大幅提升，方法的時間復(fù)雜度降為O(n)級別。因為文件路徑和完全限定名可以唯一確定一個方法，所以在為某個方法構(gòu)建方法版本組時，只需與后續(xù)的每個版本中至多一個方法進行相似度比較。雖然，這樣的限制會導(dǎo)致一些更名和移動的方法仍需參與克隆檢測，但考慮到方法的更名或移動所占比例非常小，即使會浪費一部分時間，但與其帶來的整體性能提升相比微不足道，所以這樣的權(quán)衡非常具有價值。

在相同方法的判定過程中，當(dāng)發(fā)現(xiàn)某個方法還未存在于某個方法版本組，則意味著該方法首次出現(xiàn)在該項目中。該方法的相同方法的查找，是將所有后續(xù)版本中與該方法完全限定名及所在文件路徑相同的方法與該方法依次做比較。這表明最終形成的方法版本組中的所有方法實際上都是與同一個方法進行比較，即出現(xiàn)時間最早的那個方法，這樣做的主要目的是避免誤差累積。

選擇樣本方法：在上一步中我們將版本間相同的方法都構(gòu)建為方法版本組，據(jù)此實現(xiàn)了一個歷史映像提取器用于構(gòu)建基準項目的歷史映像。根據(jù)步驟二中的描述，每條方法版本組中包含一系列不同版本中的相同方法，根據(jù)設(shè)定的相似度閾值，相同方法間的相似度閾值高于克隆檢測器判定克隆的相似度閾值，所以為了盡量減少進行克隆檢測的代碼規(guī)模，只需要從每個方法版本組中選取一個方法作為樣本參與克隆檢測即可。為了實現(xiàn)方便，本文統(tǒng)一選取所有方法版本組中最早的版本作為樣本方法，一個項目中所有樣本方法的集合被稱作該項目的歷史映像。最后，建立樣本方法和方法版本組間的索引關(guān)系，該索引稱為方法索引。根據(jù)這些方法索引可以快速根據(jù)樣本方法定位到其所屬的方法版本組。

包含三個發(fā)布版本的項目的歷史映像構(gòu)建過程如圖1所示，圖中實線方框圈出的部分表示其中一個版本的所有方法，每個方塊表示一個方法。首先為不同版本的同一方法構(gòu)建方法版本組，圖中由一系列箭頭串聯(lián)起來的方法則是方法版本組。接著從方法版本組中選擇出現(xiàn)時間最早的方法作為樣本方法，即圖中標記為黑色方塊的方法。最后，這些被提取出的樣本方法的集合就構(gòu)成了該項目的歷史映像。圖中帶有杠的箭頭表示，雖然這兩個方法的方法名及文件路徑相同，但文本相似度較低，因此需要分別構(gòu)建方法版本組。將每個項目的歷史映像分別保存到一個文本文件中，以便后續(xù)的克隆檢測。

圖1 包含三個發(fā)布版本的項目歷史映像構(gòu)建示意圖

2.3 克隆檢測

在得到所有目標項目的歷史映像后，接下來將對所有的歷史映像進行跨項目克隆檢測。因為我們只關(guān)心方法級的克隆，所以將克隆檢測粒度設(shè)為方法級，最終經(jīng)檢測得到跨歷史映像的方法級克隆組的集合。考慮到我們的目標項目集代碼規(guī)模較大，一般的克隆檢測工具可能難以支持，因此特地采用了在大規(guī)模代碼上依然運行良好的克隆檢測工具SAGA[26]。其支持Ⅰ型到Ⅲ型克隆的檢測，利用GPU的計算能力來加速檢測過程。此外，SourcererCC[25]也能支持億行級代碼的克隆檢測，只是速度相對稍慢。該步驟理論上可以采用任何克隆檢測工具，只需要保證檢測結(jié)果能夠轉(zhuǎn)換成規(guī)定的形式即可。該步驟相對簡單，主要是借助已有克隆檢測工具對目標項目的歷史映像集合進行跨項目克隆檢測。

2.4 恢復(fù)全量克隆關(guān)系

在得到所有目標項目歷史映像的跨項目方法級克隆組之后，結(jié)合2.2節(jié)中保存的方法索引即可恢復(fù)完整的全量克隆關(guān)系。圖2給出了單個歷史映像克隆組和全量克隆的大致關(guān)系。其中黑虛線方框圈出的部分為一個歷史映像克隆組，該克隆組中有四個克隆方法實例，每個黑色方塊表示一個樣本方法，其中A、B、C方法分別來自不同的項目，A′和A來自同一個項目。圖中樣本方法后箭頭連接的部分為其所屬方法版本組的其余方法，方法所屬的方法版本組可以通過追蹤之前保存的方法索引得到。圖中四個克隆方法所屬的方法版本組則構(gòu)成了該歷史映像克隆組所對應(yīng)的全量克隆關(guān)系。

圖2 歷史映像克隆組和全量克隆關(guān)系

2.5 優(yōu)化方案

在基于多版本克隆檢測加速技術(shù)實現(xiàn)工具時，為了進一步提高效率，對其中一些步驟進行了優(yōu)化。

在構(gòu)建方法版本組的過程中，需要進行較多的I/O操作并且方法間的相似度比較等也比較復(fù)雜，所以即使算法整體之間的復(fù)雜度為O(n)，但整體仍比較耗時。為了更快地進行大規(guī)模項目方法版本組的構(gòu)建，本文使用多線程技術(shù)對方法版本組構(gòu)建算法進行并行化改造，進一步加快了構(gòu)建速度。在方法版本組構(gòu)建過程中，不同方法的方法版本組構(gòu)建之間互不影響，它們是完全獨立的。這滿足了并行化技術(shù)要求子任務(wù)間相互獨立的前提，因此適合并行化處理。

算法1為并行化構(gòu)建方法版本組算法的偽代碼。首先根據(jù)經(jīng)驗以及多次實驗比較，將并行粒度即線程池的核心線程數(shù)設(shè)置為CPU可用核數(shù)的兩倍(2行-3行)。接著對于項目中每個版本的每個方法，如果該方法已經(jīng)被標記，則表明該方法與更早的版本中的方法相同；否則，表明該方法是當(dāng)前版本新出現(xiàn)的方法，將其稱為目標方法，首先將其標記，接著檢測后續(xù)版本中與該方法相同的方法(4行-11行)。其中，DetectSameFunction函數(shù)執(zhí)行具體的相同方法的檢測。該函數(shù)中，從目標版本的下個版本開始，首先查找是否存在與目標方法完全限定名及所屬文件路徑一致的方法，如果沒有則跳過；否則比較兩個方法間的相似度是否超過給定閾值，超過則表明該方法和目標方法是相同的方法，將其添加到目標方法的方法版本組中并將其標記(16行-27行)。該函數(shù)是并行化的主體部分，每當(dāng)需要對某個方法進行相同方法檢測時，從線程池取出一個空閑線程執(zhí)行該函數(shù)，最終，等待所有線程執(zhí)行完畢，算法結(jié)束。

算法1并行化構(gòu)建方法版本組算法

1.functionFUNCVERGROUPCONSTRUCT(FuncInfoSetList)

2. coreSize←availableProcessors()*2

3. exec←Executors.newFixedThreadPool(coreSzie)

4.forcurrentVer∈AllVersdo

5.forcurrentFunc∈currentVers.getFuncInfoSet()do

6.ifcurrentFunc.isUnmarked()then

7. currentFunc.mark()

8. exec.submit(DetectSameFunc())

9.endif

10.endfor

11.endfor

12. exec.shutdown()

13.returnfuncVerGroupMap

14.endfunction

15.

16.functionDETECTSAMEFUNC()

17.forifromcurrentVertolastVerdo

18. targetVer←FuncInfoSetList.get(i)

19.iftargetVer.getFuncInfoSet()

.contains(currentFunc)then

20. targetFunc←targetVer

.getFuncInfoSet().get(currentFunc)

21.ifgetSimilarity(currentFunc,targetFunc)>

thresholdthen

22. funcVerGroupMap.get(currentFunc)

.add(targetFunc)

23. targetFunction.mark()

24.endif

25.endif

26.endfor

27.endfunction

3 實 驗

本節(jié)我們將通過實驗評估本文提出的多版本軟件系統(tǒng)克隆檢測加速技術(shù)的性能和效果。因為本文提出的是一種與具體克隆檢測工具無關(guān)的克隆檢測加速技術(shù)，所以不單獨考慮工具的準確率等指標。實驗主要采用對比實驗的方式來評估與完整的全版本代碼克隆檢測相比，使用克隆檢測加速技術(shù)，性能提升了多少。

所有實驗均在一臺獨立的服務(wù)器上進行，其主要配置為：英特爾i7- 7820X型CPU(8核心，16線程)，32 GB主存，1 TB固態(tài)存儲硬盤，CentOS7操作系統(tǒng)。

3.1 準備數(shù)據(jù)

首先，在目標項目的選擇上，我們以Java項目為例。為了使實驗更加具有說服力，我們以星數(shù)超過50、有多個發(fā)布版本為標準，從GitHub上挑選了來自不同領(lǐng)域的高質(zhì)量Java開源項目，包括Android、Jedis、Gradle等共計251個知名項目，它們的版本時間跨度從2004年到2019年。對于每個項目，我們借助版本管理工具Git，將其所有的版本源代碼抽取出來并保存，同時將其所有的版本信息保存到數(shù)據(jù)庫。考慮到只關(guān)注Java源代碼，同時為了節(jié)省空間以及方便后期處理，我們只保留了項目中所有的Java代碼文件(.java文件)。經(jīng)統(tǒng)計，這251個項目共有3 234個發(fā)布版本，這些發(fā)布版本共包含4 626 144個Java代碼文件，總代碼行數(shù)達到3億行。

3.2 實驗結(jié)果及分析

基于準備好的實驗數(shù)據(jù)集，首先單獨使用SAGA工具對數(shù)據(jù)集中所有項目的所有版本進行跨項目克隆檢測，耗時約1 h 37 min(為保證結(jié)果可信，經(jīng)過多次執(zhí)行取平均值，下同)。

同樣使用SAGA工具，但結(jié)合本文提出的多版本軟件系統(tǒng)克隆檢測加速技術(shù)，在同樣的數(shù)據(jù)集上進行了跨項目克隆檢測，以下分別統(tǒng)計了四個主要步驟的執(zhí)行時間以便分析。

項目信息預(yù)處理：加載項目版本信息到內(nèi)存，并逐個提取每個項目的方法信息，共耗時10 min 20 s。該步驟耗時較長，因為需要讀取所有的近462萬個Java文件并解析出其中的方法。

構(gòu)建歷史映像：我們的工具為251個項目的3 234個release構(gòu)建歷史映像并保存方法索引，共耗時7 min 30 s。所生成的251個項目的歷史映像共計約四千萬行代碼，788 120個方法。

克隆檢測：使用SAGA工具對第二步生成的歷史映像進行跨項目克隆檢測，共耗時1 min 36 s。

恢復(fù)全量克隆關(guān)系：在得到歷史映像克隆檢測結(jié)果后，需要為每個克隆組恢復(fù)全量的克隆關(guān)系，其間需要借助方法索引查找每個克隆方法所屬的方法版本組，整個恢復(fù)過程共耗時5 min 20 s。

綜上所述，使用SAGA工具并結(jié)合多版本軟件系統(tǒng)克隆加速技術(shù)，整個檢測過程四個步驟共耗時約25 min。與原先的1 h 37 min相比，效率提升了近4倍。

實際上，第二步生成的所有項目歷史映像代碼量共約四千萬行，而原本所有項目的release的代碼約三億行，代碼量縮減了近87%。所以真正的克隆檢測只耗時1 min 36 s，效率明顯提高。而在構(gòu)建歷史映像的過程中，用樣本方法代表整個方法版本組，容忍了部分代碼差異，因此克隆檢測的精確度會有一定的損失。

由以上可知，采用本文的多版本克隆檢測加速技術(shù)，一方面可以大大提升多版本克隆檢測的效率；另一方面，極大縮小了克隆檢測工具實際需要處理的代碼規(guī)模，使得傳統(tǒng)克隆檢測工具能夠檢測更大規(guī)模的多版本軟件系統(tǒng)。

4 結(jié) 語

在軟件項目的開發(fā)過程中，開發(fā)人員出于諸多方面的考慮，往往會傾向于通過拷貝粘貼已有代碼片段并伴隨著或多或少的修改來滿足需要，這導(dǎo)致軟件項目中存在許多代碼克隆。而代碼克隆多數(shù)情況下被認為是一種代碼壞味道，但在特殊情況下卻是唯一選擇。為了管理克隆，通常需要了解項目中各個版本的克隆情況。因此，本文提出一種快速的多版本軟件系統(tǒng)克隆檢測加速技術(shù)，并據(jù)此實現(xiàn)了一個多版本軟件系統(tǒng)克隆檢測加速工具，它可以快速地在億行級代碼中檢測克隆，并且可以很好地適配不同的克隆檢測工具。通過在大規(guī)模項目上進行實驗，證明了該方法的高效性和可用性。

目前，本文的工具還處于雛形階段，仍有許多細節(jié)亟待完善。一方面，在進行版本間相同方法映射時仍然耗費較多的時間；另一方面，該工具目前只提供了方法級的克隆檢測加速。本文下一步將在此基礎(chǔ)上針對片段級的克隆檢測加速制定類似的解決方案，并考慮設(shè)計更加高效的版本間方法映射技術(shù)。