李潤青，曾國蓀

(1. 同濟大學 計算機科學及技術系，上海 200092；2. 嵌入式系統(tǒng)與服務計算教育部重點實驗室，上海 200092)

0　引言

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

1　源程序的結構和特征分析

1.1　源代碼的結構形式

程序設計語言發(fā)展至今面向結構的編程方法仍廣泛應用，因而本文的研究對象是面向結構程序設計語言編寫的源代碼。C語言是非常典型的面向結構的程序設計語言，本文后續(xù)部分以C語言作為例子來闡述。本文不妨將函數(shù)作為研究對象。下面是一段C語言源程序。

例1：快速排序C語言源代碼

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　源代碼的關聯(lián)特征

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

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

圖1　快速排序算法的控制依賴圖

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

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

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

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

2.1　變量切片的定義

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

定義3變量切片：對于程序中的變量v，與變量v相關的數(shù)據(jù)依賴或控制依賴組成的一條或多條路徑，稱為變量切片。

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

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

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

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

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

輸出：程序切片SV

getSliceOfVar(PDG, var)

{ varNode ← getVarNodeFromParam(var, PDG);

//通過遍歷程序依賴圖獲得變量var對應的節(jié)點

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ù)源代碼切片摘要的定義

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

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

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

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

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

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

輸出：程序切片摘要Abstract

getAbstract(one_src_file)

line ←readDefineLine(one_src_file);

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

paramDict ← getParamAndTypeDict (line);

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

PDG ← getPDG(one_src_file);

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

文獻[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　源代碼摘要在代碼復用搜索中的應用示例

4.1　源代碼切片摘要的應用場景

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

圖3　源代碼切片摘要的應用場景

4.2　源代碼摘要在代碼搜索中的使用過程

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

4.3　實例分析

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

4.4　源代碼搜索應用

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

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

表1　五組實驗涉及的函數(shù)

圖5　即錄入即搜索插件

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

5　結論

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

[1] 黃麗韶.克隆代碼檢測在代碼搜索中的應用研究[J]. 無線互聯(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] 顧逸圣, 曾國蓀. 基于語法和語義結合的源代碼精確搜索方法[J]. 計算機應用, 2017, 37(10):2958-2963.

[4]韓喆, 陳世鴻. 跳轉(zhuǎn)語句跟隨域分析與程序依賴圖構造算法[C]. 2009中國計算機大會， 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] 王靜疆. 搜索引擎評價指標體系比較研究[J]. 圖書情報工作, 2008, 52(10):136-138.