程序源代碼中的切片摘要提取及在搜索中的應(yīng)用*

李潤(rùn)青，曾國(guó)蓀

(1. 同濟(jì)大學(xué) 計(jì)算機(jī)科學(xué)及技術(shù)系，上海 200092；2. 嵌入式系統(tǒng)與服務(wù)計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室，上海 200092)

0　引言

隨著開(kāi)源社區(qū)影響力的增強(qiáng)，軟件工程師的開(kāi)源理念越來(lái)越強(qiáng)，促進(jìn)了高質(zhì)量的開(kāi)源項(xiàng)目數(shù)量不斷增長(zhǎng)。據(jù)統(tǒng)計(jì)僅僅在SourceForge.net開(kāi)源網(wǎng)站中，有448 706個(gè)開(kāi)源項(xiàng)目可供軟件工程師搜索和學(xué)習(xí)[1]。越來(lái)越多的軟件工程師通過(guò)網(wǎng)上搜索源代碼，進(jìn)行代碼重用。對(duì)于開(kāi)源代碼，一方面可以借助通用搜索引擎，如Google、百度等，查找下載獲得，但是搜索返回結(jié)果往往非常多，而且雜亂無(wú)序，需要花費(fèi)大量的時(shí)間進(jìn)一步縮小搜索的范圍，以便得到精確和可信的搜索結(jié)果[2]。另一方面，也可以借助專(zhuān)用的源代碼搜索引擎，以便提高搜索的用戶(hù)滿(mǎn)意度。目前比較流行的有GoogleCS、Koder、Krugle等，它們與通用搜索引擎一樣都是基于關(guān)鍵字查找，但是基于關(guān)鍵字的查找方法往往還是查找結(jié)果不準(zhǔn)確，這是由于計(jì)算機(jī)很難理解自然語(yǔ)言關(guān)鍵詞，且其可能存在二義性[3]。再者基于關(guān)鍵字的代碼查找方法沒(méi)有充分利用源代碼具有的特征信息，比如結(jié)構(gòu)信息、語(yǔ)法信息、語(yǔ)義信息等。針對(duì)上述的問(wèn)題，本文將代碼內(nèi)在關(guān)鍵特征作為摘要，給出相應(yīng)的摘要提取算法，并且應(yīng)用于開(kāi)源代碼搜索引擎中，以便提高代碼搜索的精確度。

1　源程序的結(jié)構(gòu)和特征分析

1.1　源代碼的結(jié)構(gòu)形式

程序設(shè)計(jì)語(yǔ)言發(fā)展至今面向結(jié)構(gòu)的編程方法仍廣泛應(yīng)用，因而本文的研究對(duì)象是面向結(jié)構(gòu)程序設(shè)計(jì)語(yǔ)言編寫(xiě)的源代碼。C語(yǔ)言是非常典型的面向結(jié)構(gòu)的程序設(shè)計(jì)語(yǔ)言，本文后續(xù)部分以C語(yǔ)言作為例子來(lái)闡述。本文不妨將函數(shù)作為研究對(duì)象。下面是一段C語(yǔ)言源程序。

例1：快速排序C語(yǔ)言源代碼

void Qsort(int a[], int low, int high)

s1{if (low >= high)

s2return;

s3int first = low;

s4int last = high;

s5int key = a[first];

s6while (first < last)

s7{while (first < last && a[last] >= key)

s8--last;

s9a[first] = a[last];

s10while (first < last && a[first] <= key)

s11++first;

s12a[last] = a[first];

}

s13a[first] = key;

s14Qsort(a, low, first-1);

s15Qsort(a, first+1, high);

}

1.2　源代碼的關(guān)聯(lián)特征

程序源代碼蘊(yùn)含諸多特征，本文利用程序代碼中的控制依賴(lài)和數(shù)據(jù)依賴(lài)開(kāi)展程序切片摘要研究，其中控制依賴(lài)可以反映源代碼的結(jié)構(gòu)信息，數(shù)據(jù)依賴(lài)可以反映變量的使用關(guān)系。下面給出這兩個(gè)特征的定義。

控制依賴(lài)可以用圖形化的方式表示?？刂埔蕾?lài)圖是一個(gè)有向圖，圖中的節(jié)點(diǎn)表示程序中的語(yǔ)句，邊表示語(yǔ)句間的控制依賴(lài)。如果有節(jié)點(diǎn)s控制依賴(lài)于節(jié)點(diǎn)t，則節(jié)點(diǎn)s和節(jié)點(diǎn)t之間有一條控制依賴(lài)邊。C語(yǔ)言程序中每個(gè)函數(shù)的控制依賴(lài)圖都有Entry節(jié)點(diǎn)，表示函數(shù)執(zhí)行的條件。圖1是根據(jù)例1給出的快速排序源代碼繪制的控制依賴(lài)圖。

圖1　快速排序算法的控制依賴(lài)圖

同樣可以用數(shù)據(jù)依賴(lài)圖表示代碼的數(shù)據(jù)依賴(lài)。如果有節(jié)點(diǎn)s數(shù)據(jù)依賴(lài)于節(jié)點(diǎn)t，則節(jié)點(diǎn)s和節(jié)點(diǎn)t之間有一條數(shù)據(jù)依賴(lài)邊。圖2是根據(jù)例1中快速排序源代碼繪制的數(shù)據(jù)依賴(lài)圖。

圖2　快速排序算法的數(shù)據(jù)依賴(lài)

通常，可以將控制依賴(lài)圖和數(shù)據(jù)依賴(lài)圖合并在一起構(gòu)成程序依賴(lài)圖PDG。在PDG圖中，節(jié)點(diǎn)表示程序的語(yǔ)句，控制依賴(lài)和數(shù)據(jù)依賴(lài)用不同的邊來(lái)表示。程序依賴(lài)圖的構(gòu)建可以通過(guò)文獻(xiàn)[4]的方法實(shí)現(xiàn)。

2　程序中變量切片的定義及其提取方法

2.1　變量切片的定義

程序切片最早是由WEISER M[5-6]提出，他將刪除了無(wú)關(guān)謂詞和語(yǔ)句的程序代碼定義為切片。但是單純利用現(xiàn)有切片的定義不能完全體現(xiàn)某些變量在函數(shù)中的作用，所以本文在靜態(tài)切片基礎(chǔ)上，提出一種新的切片，即變量切片。下面給出變量切片的相關(guān)定義及其提取方法。

定義3變量切片：對(duì)于程序中的變量v，與變量v相關(guān)的數(shù)據(jù)依賴(lài)或控制依賴(lài)組成的一條或多條路徑，稱(chēng)為變量切片。

就函數(shù)代碼而言，其參數(shù)和返回值最能體現(xiàn)它的核心功能，同時(shí)函數(shù)的返回值往往直接或間接地受到函數(shù)參數(shù)的影響，因此本文定義的變量切片都是針對(duì)函數(shù)的參數(shù)變量，以便找出反映函數(shù)和核心功能的語(yǔ)句。將函數(shù)參數(shù)列表中的變量分為兩類(lèi)：一類(lèi)是輸入變量，用于函數(shù)輸出變量的計(jì)算；另一類(lèi)是輸出變量，在函數(shù)中經(jīng)過(guò)計(jì)算后其可被傳出。

2.2　函數(shù)參數(shù)變量切片的獲得

在2.1節(jié)中給出了變量切片SV的定義，可見(jiàn)具體獲得變量切片需要用到第1.2節(jié)中闡述的程序依賴(lài)圖PDG。由于在PDG中并不包括函數(shù)參數(shù)列表中的聲明語(yǔ)句節(jié)點(diǎn)，本文對(duì)參數(shù)列表中的每個(gè)變量聲明添加一個(gè)節(jié)點(diǎn)以及與它相關(guān)的依賴(lài)邊。在算法1中，先將函數(shù)的源代碼文件轉(zhuǎn)化為包含函數(shù)參數(shù)變量v的程序依賴(lài)圖PDG，然后從PDG圖中找到與變量v聲明語(yǔ)句相關(guān)的數(shù)據(jù)依賴(lài)或控制依賴(lài)組成的一條或多條路徑。路徑的獲取可以由圖的深度遍歷獲得，這里用getNextPathFromPDG表示。變量切片獲得算法的偽代碼描述如下。

算法1：程序變量切片的獲得算法getSliceOfVar

輸入：一個(gè)函數(shù)的源代碼的程序依賴(lài)圖PDG，需要切片的一個(gè)變量var，一段函數(shù)的源代碼文件one_src_file

輸出：程序切片SV

getSliceOfVar(PDG, var)

{ varNode ← getVarNodeFromParam(var, PDG);

//通過(guò)遍歷程序依賴(lài)圖獲得變量var對(duì)應(yīng)的節(jié)點(diǎn)

SV ←?;

path ← getNextPathFromPDG(PDG,varNode，SV)

// 獲得PDG中從varNode 發(fā)出的一條路徑，且該

路徑不在SV中

while(path! = NULL)

{ SV ← SV ∪ {path}

path ← getNextPathFromPDG(PDG,varNode,SV)

}

return SV

}

3　源代碼切片摘要及其提取方法

3.1　函數(shù)源代碼切片摘要的定義

對(duì)于源代碼而言，摘要是為了體現(xiàn)源代碼的主要功能，以及服務(wù)于源代碼的檢索。根據(jù)本文2.1節(jié)中對(duì)變量切片的定義以及對(duì)輸入變量和輸出變量的描述，本文將函數(shù)的參數(shù)列表，即輸入輸出變量作為切片對(duì)象，分別提取它們的變量切片，并且將這些變量切片集合作為源代碼的摘要。

定義4函數(shù)源代碼切片摘要：對(duì)于函數(shù)參數(shù)列表中的變量，即輸入和輸出變量，分別求它們對(duì)應(yīng)的切片，這些切片的并集稱(chēng)為函數(shù)源代碼的切片摘要。

3.2　函數(shù)源代碼切片摘要的提取

根據(jù)3.1節(jié)對(duì)函數(shù)源代碼切片摘要的定義，可以得出提取函數(shù)源代碼切片摘要的方法：首先獲得函數(shù)參數(shù)列表中的每一個(gè)變量，然后根據(jù)該變量在函數(shù)中的使用判斷是輸入變量還是輸出變量，如果該變量是輸入變量，則變量切片直接調(diào)用算法1即可獲得；如果該變量是輸出變量，則需要先逆置程序依賴(lài)圖(即把圖的所有邊都反向)，再調(diào)用算法1，從而獲得變量切片。最后對(duì)這些變量切片取并集，這樣就獲得了函數(shù)源代碼的切片摘要，該算法如下。

算法2：程序切片摘要的提取算法getAbstract

輸入：一段函數(shù)的源代碼文件one_src_file

輸出：程序切片摘要Abstract

getAbstract(one_src_file)

line ←readDefineLine(one_src_file);

//讀取函數(shù)定義行

paramDict ← getParamAndTypeDict (line);

//獲取參數(shù)列表變量以及變量的類(lèi)型

PDG ← getPDG(one_src_file);

//通過(guò)函數(shù)源代碼one_src_file獲得PDG圖(使用

文獻(xiàn)[4]的方法)

for param,type in paramDict

{ isVarIn←isVarInOrVarOut(param, type);

//判斷變量是輸出變量還是輸出變量

if (isVarIn)

//輸入變量切片的獲得

{SV ← getSliceOfVar (PDG, param, one_src_file);

//算法2 變量切片的獲得

}

else

//輸出變量切片的獲得

{ reversePDG ← reversePDG(PDG);

SV ← getSliceOfVar (PDG, param);

}

}

return Abstract;

}

4　源代碼摘要在代碼復(fù)用搜索中的應(yīng)用示例

4.1　源代碼切片摘要的應(yīng)用場(chǎng)景

源代碼切片摘要可以應(yīng)用于即時(shí)錄入即時(shí)輸出的代碼編程環(huán)境，即在程序員錄入代碼后自動(dòng)根據(jù)程序員的已有代碼幫助搜索補(bǔ)全程序員所需代碼，從而提高程序員的編碼效率。圖3描述了該應(yīng)用場(chǎng)景。首先將程序員實(shí)時(shí)錄入的編程代碼作為輸入，然后對(duì)該部分代碼進(jìn)行分析，提取切片摘要，接著把提取的切片摘要作為搜索引擎中的關(guān)鍵字進(jìn)行搜索，最后將相關(guān)可復(fù)用源代碼作為參考結(jié)果即時(shí)返回到編程界面，等待程序員選擇、拷貝、修改、使用。

圖3　源代碼切片摘要的應(yīng)用場(chǎng)景

4.2　源代碼摘要在代碼搜索中的使用過(guò)程

本文通過(guò)二次搜索方案，即首先在傳統(tǒng)的搜索方法搜索得到結(jié)果后，再針對(duì)返回結(jié)果使用切片摘要的方案進(jìn)行再次搜索的匹配，以達(dá)到精確查找代碼的目的。該過(guò)程如下：(1)用戶(hù)錄入源代碼，將源代碼整體作為關(guān)鍵字，利用常用的搜索引擎進(jìn)行第一次搜索，并將搜索到的目標(biāo)源代碼結(jié)果緩存起來(lái)；(2)針對(duì)前面得到的目標(biāo)源代碼進(jìn)行代碼切片摘要提?。?3)對(duì)用戶(hù)錄入的代碼進(jìn)行代碼切片摘要提取，并將此摘要與目標(biāo)源代碼中的摘要進(jìn)行匹配；(4)將返回的結(jié)果按照匹配程度進(jìn)行排序并返回。

4.3　實(shí)例分析

圖4　快速排序源代碼的切片摘要

4.4　源代碼搜索應(yīng)用

本次實(shí)驗(yàn)的硬件環(huán)境所使用計(jì)算機(jī)的CPU為2.7 GHz Intel Core i5，內(nèi)存大小為8 GB。在軟件方面，本文設(shè)計(jì)開(kāi)發(fā)了摘要搜索的原型系統(tǒng)，該系統(tǒng)的代碼搜索過(guò)程已在4.1節(jié)中介紹，其中代碼來(lái)源是在SearchCode中用關(guān)鍵字進(jìn)行代碼搜索后返回的結(jié)果。

為了驗(yàn)證切片摘要的有效性，本文設(shè)計(jì)了五組實(shí)驗(yàn)，每組分為三個(gè)對(duì)比試驗(yàn)。第一個(gè)實(shí)驗(yàn)將函數(shù)名作為關(guān)鍵字在SearchCode搜索引擎中獲取結(jié)果，錄入的函數(shù)名見(jiàn)表1；第二個(gè)實(shí)驗(yàn)將實(shí)現(xiàn)表1中函數(shù)功能的源代碼作為關(guān)鍵字在SearchCode搜索引擎中獲取結(jié)果；第三個(gè)實(shí)驗(yàn)進(jìn)一步利用第二個(gè)實(shí)驗(yàn)返回的結(jié)果，傳入到搜索原型系統(tǒng)中進(jìn)行二次搜索，將其與原始搜索結(jié)果進(jìn)行比較，來(lái)判斷代碼摘要是否提高了搜索的精準(zhǔn)度。執(zhí)行上述 5 組實(shí)驗(yàn)后，分別計(jì)算查準(zhǔn)率[7]，數(shù)據(jù)如圖5所示[7]。

表1　五組實(shí)驗(yàn)涉及的函數(shù)

圖5　即錄入即搜索插件

根據(jù)圖5可以得到，以切片摘要作為關(guān)鍵字進(jìn)行匹配相較于以函數(shù)名作為關(guān)鍵字查準(zhǔn)率平均提高了8%，相較于以函數(shù)源代碼作為關(guān)鍵字查準(zhǔn)率提高了6%，從而證明了代碼的切片摘要能夠提高搜索的準(zhǔn)確率。

5　結(jié)論

本文通過(guò)對(duì)比試驗(yàn)證明使用了代碼數(shù)據(jù)依賴(lài)和控制依賴(lài)的切片摘要有助于提高代碼搜索的準(zhǔn)確性。當(dāng)然，源代碼的信息類(lèi)型有很多，本文只是從控制依賴(lài)和數(shù)據(jù)依賴(lài)角度分析代碼以提取摘要，對(duì)其他方面的信息尚未充分發(fā)掘。下一步研究工作將是對(duì)源代碼中相關(guān)更深層次的信息進(jìn)行挖掘和利用。

[1] 黃麗韶.克隆代碼檢測(cè)在代碼搜索中的應(yīng)用研究[J]. 無(wú)線(xiàn)互聯(lián)科技, 2017 (19):45-46.

[2] BAJRACHARYA S K, LOPES C.V. Analyzing and mining a code search engine usage log [M]. Empirical Software Engineering, 2012, 17(4-5):424-466.

[3] 顧逸圣, 曾國(guó)蓀. 基于語(yǔ)法和語(yǔ)義結(jié)合的源代碼精確搜索方法[J]. 計(jì)算機(jī)應(yīng)用, 2017, 37(10):2958-2963.

[4]韓喆, 陳世鴻. 跳轉(zhuǎn)語(yǔ)句跟隨域分析與程序依賴(lài)圖構(gòu)造算法[C]. 2009中國(guó)計(jì)算機(jī)大會(huì)， 2009.

[5] WEISER M. Program slicing[J]. IEEE Transactions on Software Engineering, 1984, SE-10(4):352-357.

[6] FERRANTE J, OTTENSTEIN K.J, WARREN J.D. The program dependence graph and its use in optimization[J]. ACM Transactions on Programming Languages & Systems, 1984, 9(3):319-349.

[7] 王靜疆. 搜索引擎評(píng)價(jià)指標(biāo)體系比較研究[J]. 圖書(shū)情報(bào)工作, 2008, 52(10):136-138.