基于差異性代碼克隆的代碼塊補(bǔ)全提示方法

殷康麒,吳 鳴,王鵬程,徐 云

(中國科學(xué)技術(shù)大學(xué) a.計算機(jī)科學(xué)與技術(shù)學(xué)院; b.安徽省高性能計算重點(diǎn)實驗室,合肥 230027)

0 概述

軟件編程作為軟件開發(fā)中的重要步驟,其效率將直接影響軟件開發(fā)的整體進(jìn)程。由于集成開發(fā)環(huán)境(Integrated Development Environment,IDE)中的代碼補(bǔ)全功能可以減少軟件編程中的拼寫錯誤和編碼所需記憶,有效提高編程效率,因此被程序員廣泛使用。

目前多數(shù)IDE通過增加一些簡單的提示用于幫助代碼補(bǔ)全,如已經(jīng)拼寫出一個對象名,然后通過查詢這個對象所屬的類列出此對象所有的變量名和函數(shù)名。但是目前IDE只能對特定的關(guān)鍵詞(如對象和函數(shù))進(jìn)行補(bǔ)全。為能補(bǔ)全代碼中所有的關(guān)鍵詞,文獻(xiàn)[1-2]對源代碼進(jìn)行詞法分析,將其轉(zhuǎn)變?yōu)榛趖oken的源碼,使用統(tǒng)計語言模型(如n-gram和RNN)學(xué)習(xí)token序列的規(guī)律,并利用學(xué)習(xí)后的統(tǒng)計語言模型對下一個token進(jìn)行提示。

此外,研究者還提出了對代碼行和代碼塊進(jìn)行補(bǔ)全提示的方法。文獻(xiàn)[3]提取出代碼中對象所使用的API,通過API的使用序列預(yù)測下次使用的API,從而對下一行語句進(jìn)行補(bǔ)全。文獻(xiàn)[4]根據(jù)API的使用頻率并通過關(guān)聯(lián)規(guī)則挖掘等對可能會使用的API進(jìn)行補(bǔ)全。文獻(xiàn)[5]通過使用代碼克隆方法在代碼庫中查找出相似的代碼對代碼塊進(jìn)行補(bǔ)全。

隨著軟件應(yīng)用領(lǐng)域的不斷擴(kuò)大,基于關(guān)鍵詞和單行函數(shù)調(diào)用的補(bǔ)全已不能滿足編程人員的需求,是否能夠?qū)崿F(xiàn)若干連續(xù)行的代碼塊補(bǔ)全,對于提高軟件開發(fā)效率至關(guān)重要。隨著GitHub、SourceForge等大型代碼庫的出現(xiàn),可供參考的代碼數(shù)量變得更多,并且種類也更豐富。在此環(huán)境下,本文提出一種新的代碼塊補(bǔ)全提示方法,利用差異性代碼克隆檢測技術(shù)在代碼庫中查找與待補(bǔ)全代碼塊相似的候選代碼塊,并對其進(jìn)行特征提取、聚類和相關(guān)性排名,從而得到候選代碼塊的提示順序。

1 相關(guān)概念及問題定義

代碼塊是指一個函數(shù)或者是一個大括號({})里的一段語句序列[6]。代碼克隆是指2個代碼塊有相同或相似的代碼片段[7]。差異性代碼克隆[6]是指2個在代碼規(guī)模上有較大差異的代碼塊有相同或相似的代碼片段,如圖1所示。

圖1 差異性克隆實例

IDE中的代碼補(bǔ)全提示功能是指通過提示一些相關(guān)的信息將未完成的代碼補(bǔ)全完整,如圖2所示[1,5]。代碼補(bǔ)全提示根據(jù)補(bǔ)全的粒度可以劃分為關(guān)鍵詞粒度的補(bǔ)全、語句粒度的補(bǔ)全和代碼塊粒度的補(bǔ)全,本文主要研究代碼塊粒度的補(bǔ)全提示。下文中待補(bǔ)全代碼塊是指正在編寫但沒有全部完成的代碼塊。

圖2 代碼補(bǔ)全提示實例

對一個正在編寫但沒有完成的代碼塊,在代碼塊待補(bǔ)全的部分添加“???”和與這部分要實現(xiàn)的功能相關(guān)的方法名或關(guān)鍵詞以構(gòu)造待補(bǔ)全代碼塊,如圖3所示?？墒褂么a塊補(bǔ)全方法在代碼庫中查找出與待補(bǔ)全代碼塊相似的代碼塊提示給程序員以輔助編程,如圖4所示。

圖3 待補(bǔ)全代碼塊實例

圖4 代碼塊補(bǔ)全提示實例

2 補(bǔ)全提示方法設(shè)計

本文將差異性代碼克隆方法應(yīng)用于代碼塊補(bǔ)全問題,然后對克隆技術(shù)的查找結(jié)果進(jìn)行特征提取、聚類、相關(guān)性打分,最后為程序員提示有用的代碼塊以提高編程效率,其總體流程如圖5所示。

圖5 代碼塊補(bǔ)全提示流程

2.1 代碼克隆方法的選取與改進(jìn)

為在代碼庫中找到與待補(bǔ)全代碼相似的代碼塊,需要選取一個合適的代碼克隆方法對代碼庫中的代碼塊進(jìn)行粗粒度的過濾,將與待補(bǔ)全代碼相似的代碼塊留下。為比較代碼塊之間的相似性,首先要對代碼進(jìn)行預(yù)處理,常用的技術(shù)有文本化[8-9]、token化[10-11]、AST化[12-13]和PDG化[14-15],因為是在大型代碼庫中進(jìn)行查找比較,所以需要速度較快的預(yù)處理方法。AST化和PDG化技術(shù)由于算法復(fù)雜度高時間性能很差,不適合在大規(guī)模的代碼庫中進(jìn)行查找,而文本化后的特征過于簡單,查找效果很差。token化的預(yù)處理技術(shù)不僅時間性能較優(yōu),而且還保留了代碼的一些的詞法特征,查找效果較好。

此外,由于是對待補(bǔ)全代碼和完整的代碼塊進(jìn)行比較,兩部分代碼的規(guī)模有較大的差異,因此需要選取一個在代碼規(guī)模有較大差異情況下能有效檢測出代碼相似性的方法。文獻(xiàn)[6]提出的基于滑動窗口技術(shù)和帶誤配索引技術(shù)的匹配算法,可以有效解決這一問題,與其他的基于token化的相似代碼查找方法不同,本文使用滑動的代碼窗口(即連續(xù)的代碼片段),而不是單個token作為比對的基本單元。對每個長為q的代碼窗口,如果每個窗口允許e個誤配,提取其所有的長為q-e的子串,如果至少存在一個子串匹配,則認(rèn)為2個窗口是一次成功的匹配。如果2個代碼塊中匹配上的窗口數(shù)目符合設(shè)定的相似度閾值,則認(rèn)為這2塊代碼段是相似代碼。本文基于此算法進(jìn)行改進(jìn),使其適用于代碼塊補(bǔ)全問題,具體步驟如下:

1)由于進(jìn)行粗粒度過濾,因此本文在查找時設(shè)定的相似度閾值比一般查找相似代碼的相似度閾值低,以找到更多的候選代碼塊。

2)由于只對待補(bǔ)全代碼塊進(jìn)行相似代碼查找,因此本文將查找模式由代碼克隆的多對多模式改為一對多模式。

3)由于補(bǔ)全的目標(biāo)是擴(kuò)展代碼塊,因此在預(yù)處理過程直接過濾所有小于待補(bǔ)全代碼塊的代碼塊。

4)由于只需要尋找和待補(bǔ)全代碼塊相似的代碼塊,因此本文并沒有存儲所有滑動窗口的鍵值對,而只存待補(bǔ)全代碼塊窗口的鍵值對,有效減少了存儲空間。

2.2 代碼特征向量設(shè)計與聚類算法應(yīng)用

用改進(jìn)后的差異性代碼克隆方法會在代碼庫找出很多符合相似性要求的代碼塊,本文稱之為候選代碼塊。

因為這些代碼塊是在代碼庫中查找出來,而代碼庫的代碼量很大且不同程序中有很多相同實現(xiàn)的代碼塊,所以找出的候選代碼塊數(shù)量也會很大,因此下一步需要對找出的候選代碼塊進(jìn)行細(xì)粒度劃分。

首先對代碼進(jìn)行特征向量設(shè)計,代碼的特征有很多種,例如:衡量源代碼復(fù)雜性的特征如McCabe度量元、代碼塊的長度[16];衡量源代碼模塊化的特征如調(diào)用其他方法的數(shù)量;代碼中關(guān)鍵詞和變量的種類和數(shù)量[17];建立抽象語法樹從中提取表示代碼結(jié)構(gòu)關(guān)系的特征[18]。本文綜合各類型的特征建立特征向量,具體如表1所示。

表1 代碼的特征向量

對于劃分而言,另一個重點(diǎn)是準(zhǔn)確度量特征向量之間的相似度。由于每個特征度量的量綱不統(tǒng)一,如代碼塊行數(shù)的絕對數(shù)值相對其他特征絕對數(shù)值過大,如果使用歐式距離度量就會導(dǎo)致一些特征在度量時權(quán)重變得很大,其他一些特征的權(quán)重就會變得很小,余弦相似度更多是從方向上區(qū)分差異,而對絕對數(shù)值不敏感從而修正了量綱標(biāo)準(zhǔn)不統(tǒng)一問題,因此，本文選擇余弦相似度用于度量特征向量的相似度。

在選取合適的相似度度量方法之后,下一步需要選取聚類算法對候選代碼塊進(jìn)行細(xì)粒度劃分?？紤]到預(yù)先未知代碼的特征向量在數(shù)據(jù)空間的分布,也未知需要劃分為多少類,因此,本文選取DBSCAN作為聚類方法,這是一種基于密度的聚類算法,有一定抗噪聲的能力,不需要設(shè)定生成的類別數(shù),只需要設(shè)定一個相似度閾值,如果兩個代碼塊的特征向量之間的相似度小于設(shè)定的閾值,便認(rèn)為這兩個代碼塊是屬于一類的。

2.3 候選代碼塊的推薦排序

使用聚類算法對候選代碼集完成進(jìn)一步的劃分后,本文選取每個類中與待補(bǔ)全代碼塊關(guān)鍵詞匹配最多的代碼塊作為這個類別的代表性代碼塊。在選出代表性代碼塊之后,本文通過計算每個代表性代碼塊所屬類別的代碼塊數(shù)(代表此類代碼在代碼庫出現(xiàn)的頻率)、與待補(bǔ)全代碼塊匹配的代碼占總代碼的比例和與待補(bǔ)全代碼塊的方法名或關(guān)鍵詞的匹配數(shù)。根據(jù)以上3個指標(biāo)的數(shù)值對每個候選代碼塊進(jìn)行相關(guān)性打分,最后按照候選代碼塊的分?jǐn)?shù)順序提示給程序員。

3 實驗與結(jié)果分析

3.1 數(shù)據(jù)集

3.1.1 數(shù)據(jù)集來源

首先建立供查找的代碼庫,為了更好地測試本文方法的效果,建立的代碼庫與待補(bǔ)全代碼塊之間需要較高的相似度,可以通過從大型的開源網(wǎng)站搜尋同類型軟件的源碼以建立同類型軟件代碼庫。

本文從GitHub上搜尋了44個同屬于Android Social Network類型軟件的源碼,然后使用TXL[19]從這44個軟件的源碼中提取出所有的代碼塊,在此基礎(chǔ)上,對提取出的代碼塊進(jìn)行詞法分析以得到token化的代碼塊,將代碼塊轉(zhuǎn)化為token化的形式是為了加快在代碼庫中的查找速度,最后將詞法分析后的代碼塊與處理前的源碼建立一一對應(yīng)關(guān)系,通過上述操作建立Android Social Network同類型的軟件代碼庫。

3.1.2 測試數(shù)據(jù)集構(gòu)建

本文從代碼庫中隨機(jī)挑選出代碼塊,從中刪除部分關(guān)鍵代碼,并在刪除的部分添加與這部分要實現(xiàn)功能相關(guān)的關(guān)鍵詞,對保留部分代碼有2種處理,分別是不進(jìn)行改變和引入一些代碼突變[20](如進(jìn)行變量名的替換和少數(shù)語句的添加刪減),將處理完后的代碼塊作為待補(bǔ)全代碼塊。

3.2 評估指標(biāo)

本文主要通過以下3個指標(biāo)來衡量補(bǔ)全提示方法的效果:

1)Top-1,表示代碼塊補(bǔ)全提示方法的精確率。此指標(biāo)排名第一的代碼塊實現(xiàn)了預(yù)定功能。

2)Top-3,選取此指標(biāo)是考慮到程序員一般編程時重點(diǎn)關(guān)注前三個提示。此指標(biāo)排名前三的代碼塊中有實現(xiàn)預(yù)定功能的代碼塊。

3)Top-10,表示代碼塊補(bǔ)全提示方法的召回率。此指標(biāo)排名前十的代碼塊中有實現(xiàn)預(yù)定功能的代碼塊。

3.3 結(jié)果分析

本文使用交叉驗證的方式對結(jié)果進(jìn)行檢驗,把19 764個代碼塊隨機(jī)分為4份,然后將每一份代碼輪流作為測試集,而剩下的另外3份代碼作為代碼庫。本文方法從作為測試集的每份代碼中隨機(jī)抽取20個代碼塊按照上節(jié)描述的做法構(gòu)造待補(bǔ)全代碼塊。

由于文獻(xiàn)[5]方法只能應(yīng)用于代碼塊最后一部分缺少的情況,不能應(yīng)用于代碼塊中間部分缺少的情況,因此本文根據(jù)代碼塊中缺失代碼的位置進(jìn)行2組實驗。

第1組實驗的80個待補(bǔ)全代碼塊缺失部分全部位于代碼塊的最后部分,2種補(bǔ)全方法對第1組的待補(bǔ)全代碼塊的補(bǔ)全結(jié)果如圖6所示。

圖6 第1組實驗中2種補(bǔ)全方法的結(jié)果對比

Fig.6 Results comparison between two completion methods in experiment 1

從圖6可以看出,本文方法在補(bǔ)全推薦的Top-1、Top-3和Top-10指標(biāo)上較文獻(xiàn)[5]方法均更優(yōu),這是因為本文使用的差異性代碼克隆方法非常適用于代碼塊補(bǔ)全的問題,該查找方法可以根據(jù)現(xiàn)有代碼的各種信息(如token的種類、位置、數(shù)量)使用局部匹配的方式在代碼庫中查找相似代碼,而文獻(xiàn)[5]使用的查找方法只使用了已編寫代碼的token種類和數(shù)量信息,查找準(zhǔn)確率較低,因此,本文方法在Top-10上的效果更好。此外,由于代碼庫中重復(fù)代碼很多,為了防止重復(fù)推薦,本方法通過使用聚類解決這個問題,但是文獻(xiàn)[5]補(bǔ)全方法并沒有解決這個問題,而且本文還使用關(guān)鍵詞和方法名匹配作為輔助手段,使更相關(guān)的代碼塊排名更高,所以,本文方法在Top-1上的效果較好。

第2組實驗的80個待補(bǔ)全代碼塊缺失部分隨機(jī)分布于代碼塊的各個部分,本文方法對其補(bǔ)全的結(jié)果如圖7所示。結(jié)合圖6可以發(fā)現(xiàn),相對于第1組實驗的結(jié)果,本文方法在第2組實驗中的結(jié)果略差,原因是由于待補(bǔ)全代碼塊缺失代碼可能位于代碼塊的中間,從而在查找時缺失代碼對前后的窗口都造成影響,加大了查找的難度。

圖7 第2組實驗中本文方法的補(bǔ)全結(jié)果

Fig.7 Completion results of the proposed method in experiment 2

4 結(jié)束語

IDE代碼補(bǔ)全難以查找規(guī)模差異較大的相似代碼。針對該問題，本文提出一種基于差異性代碼克隆的代碼塊補(bǔ)全提示方法。使用差異性代碼克隆方法查找與待補(bǔ)全代碼相似的候選代碼集,并通過特征提取、聚類劃分和相關(guān)性打分從候選代碼集中挑選相關(guān)性最強(qiáng)的代碼推薦給程序員。實驗結(jié)果表明,該方法相對于文獻(xiàn)[5]方法在Top-10指標(biāo)上有大幅提高,而使用已有代碼的結(jié)構(gòu)信息和提示來進(jìn)行精確推薦,使其在Top-1指標(biāo)上也具有較好的提升效果。后續(xù)將利用代碼注釋等文本信息進(jìn)一步提高本文方法補(bǔ)全提示的準(zhǔn)確性。