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

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

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

0 概述

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

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

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

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

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

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

圖1 差異性克隆實(shí)例

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 代碼的特征向量

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

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

2.3 候選代碼塊的推薦排序

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

3 實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

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

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

3.2 評(píng)估指標(biāo)

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

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

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

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

3.3 結(jié)果分析

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

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

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

圖6 第1組實(shí)驗(yàn)中2種補(bǔ)全方法的結(jié)果對(duì)比

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),這是因?yàn)楸疚氖褂玫牟町愋源a克隆方法非常適用于代碼塊補(bǔ)全的問題,該查找方法可以根據(jù)現(xiàn)有代碼的各種信息(如token的種類、位置、數(shù)量)使用局部匹配的方式在代碼庫(kù)中查找相似代碼,而文獻(xiàn)[5]使用的查找方法只使用了已編寫代碼的token種類和數(shù)量信息,查找準(zhǔn)確率較低,因此,本文方法在Top-10上的效果更好。此外,由于代碼庫(kù)中重復(fù)代碼很多,為了防止重復(fù)推薦,本方法通過使用聚類解決這個(gè)問題,但是文獻(xiàn)[5]補(bǔ)全方法并沒有解決這個(gè)問題,而且本文還使用關(guān)鍵詞和方法名匹配作為輔助手段,使更相關(guān)的代碼塊排名更高,所以,本文方法在Top-1上的效果較好。

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

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

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

4 結(jié)束語

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