方維康 吳毅堅(jiān) 趙文耘

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

0 引 言

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

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

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

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

1 代碼克隆

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

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

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

Ⅱ型克?。撼丝瞻追⒆⑨?、標(biāo)識(shí)符、類型和字面值有可能不同之外，語(yǔ)法結(jié)構(gòu)上完全一致的代碼片段。

Ⅲ型克?。撼丝瞻追?、注釋、標(biāo)識(shí)符、類型和字面值有可能不同之外，還有可能添加、修改或刪除了一些代碼行的代碼片段。

Ⅳ型克?。汗δ苌弦恢碌a本身相似度較低的代碼片段。該種克隆類型比較特殊，它通常不是由復(fù)制粘貼產(chǎn)生的，而是不同開(kāi)發(fā)人員對(duì)同一種功能的不同實(shí)現(xiàn)，例如不同的排序算法。

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

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

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

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

克隆實(shí)例：克隆對(duì)或克隆組中的每一個(gè)代碼片段都稱為一個(gè)克隆實(shí)例。

方法級(jí)克?。喝绻麅蓚€(gè)或多個(gè)方法是彼此克隆的，則將這種克隆稱為方法級(jí)克隆。方法級(jí)克隆的克隆實(shí)例是完整的方法。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 克隆檢測(cè)

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

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

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

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

2.5 優(yōu)化方案

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

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

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

本節(jié)我們將通過(guò)實(shí)驗(yàn)評(píng)估本文提出的多版本軟件系統(tǒng)克隆檢測(cè)加速技術(shù)的性能和效果。因?yàn)楸疚奶岢龅氖且环N與具體克隆檢測(cè)工具無(wú)關(guān)的克隆檢測(cè)加速技術(shù)，所以不單獨(dú)考慮工具的準(zhǔn)確率等指標(biāo)。實(shí)驗(yàn)主要采用對(duì)比實(shí)驗(yàn)的方式來(lái)評(píng)估與完整的全版本代碼克隆檢測(cè)相比，使用克隆檢測(cè)加速技術(shù)，性能提升了多少。

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

3.1 準(zhǔn)備數(shù)據(jù)

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

3.2 實(shí)驗(yàn)結(jié)果及分析

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

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

項(xiàng)目信息預(yù)處理：加載項(xiàng)目版本信息到內(nèi)存，并逐個(gè)提取每個(gè)項(xiàng)目的方法信息，共耗時(shí)10 min 20 s。該步驟耗時(shí)較長(zhǎng)，因?yàn)樾枰x取所有的近462萬(wàn)個(gè)Java文件并解析出其中的方法。

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

克隆檢測(cè)：使用SAGA工具對(duì)第二步生成的歷史映像進(jìn)行跨項(xiàng)目克隆檢測(cè)，共耗時(shí)1 min 36 s。

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

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

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

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

4 結(jié) 語(yǔ)

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

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