克隆代碼檢測在代碼搜索中的應用研究

黃麗韶

摘 要：文章設計和開發的代碼搜索引擎首先通過擴展Heritrix，構建本地代碼庫，利用ANTLR工具對本地代碼庫的Java源文件進行解析；其次，基于程序抽象語法樹（AST）從方法級別和類級別檢測克隆代碼，對源代碼中的方法（method）或者類（class）進行分類；再次，利用ASTParser對本地代碼庫掃描，抽取程序代碼的語法信息，并利用Lucene對含有語法信息的文件建立索引和搜索模塊。實驗比較結果表明，實現的代碼搜索引擎可優化已有的代碼搜索引擎的搜索結果，并且對于搜索時間沒有顯著的影響，從而可更有效地幫助程序員查找與復用已有代碼。

關鍵詞：Java源；代碼搜索；ANTLR；克隆；AST

立足于軟件開發領域，開源軟件變得愈發生命力頑強，這是因為伴隨科技高速發展，程序開發人員開源的理念越發加強，促使開源網站如雨后春筍般層出不窮，高質量的開源項目數量不斷增長，開源網站訪問量激增，其中全球最大最著名的SourceForge.net開源網站已經收錄了448 706個開源項目，并被軟件開發人員不斷搜索、學習和完善[1]。

1 克隆代碼檢測在代碼搜索中的設計與實現

1.1 需求分析

軟件開發人員和編程愛好人員試圖搜索高質量的示例代碼來學習其中的算法，學習應用程序編程接口（Application Programming Interface，API）文檔的使用，加快開發效率。他們不僅想基于全文來搜索源代碼，還想根據不同目的通過包名、類名、方法名等形式來搜索。該系統要求為用戶提供一個友好的搜索界面和多種搜索方式，比如按照文本來搜索，按照包名、類名、方法定義和方法調用搜索。當用戶以方法名或類名來搜索源代碼時，搜索結果對克隆方法和克隆類分類顯示，并根據用戶搜尋目的給出最有代表性的摘要[2]。

1.2 系統設計

本文的源代碼搜索引擎系統設計，分為前端用戶和后臺維護兩部分。查詢用戶主要是選擇查詢方式和輸入搜索關鍵字，后端用戶獲取數據、處理數據、維護系統，維護人員首先通過Heritrix獲取源代碼，然后對源代碼庫中的克隆代碼進行檢測和聚類，把克隆方法和克隆類聚成一類，再對源代碼庫中的源文件進行語法信息的提取和保存，最后對提取出來的語法信息建立索引和搜索模塊，對搜索結果產生摘要和克隆代碼分類顯示。

1.3 克隆方法的聚類分析

通過預處理獲得聚類對象和信息表后進行聚類分析，現有的聚類算法繁多，本文僅給出一種簡單直接的比較算法，效果更好的算法驗證留給后續工作，聚類比較算法1如下所示。

輸入：表名tableName

輸出：void

方法：getMethodDetectInfo （ tableName ）

1 初始化方法個數count，方法類型ID為2；

2 for （ i←0 到 count-1 ） {

3 for （ j←（ i+1 ） 到 count ） {

4 if （ 方法i與方法j的相似度 < 0.6 ） { //相似度小于0.6

5 if（ 方法 j已經分配類 ） continue；

6 else {

7 為方法j分配一個新類型號ID；

8 類型號ID++；

9 }

10 }else{ //相似度大于等于0.6

11 if （ 方法j已經分配類 ） {

12 if （ 方法j的最大相似度 < i和j的相似度 ） {

13 方法j的類型 = 方法i的類型號；

14 方法j的最大相似度 = i和j的相似度；

15 } else {

16 continue；

17 }

18 } else { //方法j和方法i聚為一類

19 方法j的類型 = 方法i的類型號；

20 方法j的最大相似度 = i和j的相似度；

21 }

22 }

23 }

24 }

1.4 類信息表的創建

Java源文件主要由方法和類組成，基于類級別的克隆代碼檢測與基于方法的克隆檢測方法基本一致，本文使用Oracle數據庫表的形式來保存每個類的信息。我們在進行克隆類檢測的時候將會用到文件名、文件存放路徑和類名，在進行克隆類聚類時需要用到類的所有信息，在對搜索結果進行分類顯示時需要知道類ID號、文件名、類名和類型值。

2 系統演示與實驗比較

本文利用Heritrix從SourceForge.net上抓取到70個工程包，共計20 423個Java源文件作為本地代碼庫，再對代碼庫中的方法和類進行克隆檢測和聚類，并把檢測和聚類信息保存在庫表內，最后通過Lucene對含有語法信息的文件建立索引和搜索，首先展示我們實現的代碼搜索引擎友好的搜索界面，然后與已有相關代碼搜索引擎進行實驗搜索結果比較。

2.1 系統實例演示

本文主要在按方法定義和類名搜索模塊上作了優化，所以系統展示代碼搜索引擎在這兩種搜索方式下的搜索結果，這一節只展示代碼搜索引擎的搜索結果，通過展示其他搜索引擎的搜索結果，并與搜索結果進行比較。

通常，用戶搜索源代碼的一個重要潛在目標是想知道某個方法在功能上是怎樣實現的，學習其實現功能和算法，所以通過方法定義來搜索成為用戶搜索的重要方式，用戶在Method Definition界面輸入方法名搜索即可。

結果分析：首先，搜索返回界面（methodImpResult.jsp）上端的搜索框，可以供用戶選擇其他方式或默認以方法定義的方式來繼續搜索。例如，當用戶在搜索到save方法的功能實現后，還想知道其方法調用情況或者某個類中的方法的實現，則可以分別點擊MethodCall和Class搜索方式后輸入關鍵字。

其次，搜索結果返回搜索到的結果文檔的數目、總頁數和搜索時間，本文設定每頁僅顯示5條結果，10條記錄將分成兩頁顯示，不妨列出搜索方法save返回首頁的第5條結果。

再次，摘要顯示搜索結果依次展示出方法所屬文件的路徑、包名和類名信息，摘要顯示10行，由于在方法定義搜索模塊，用戶搜索的目標傾向于查詢某個功能的實現，通過預覽方法實現的功能來判定是否對該方法感興趣。所以本文在顯示摘要的時候優先給出方法的注釋行，再考慮返回方法的實現代碼，同時給出該行在文件中的位置，摘要中匹配關鍵字的字符串高亮紅色標記。

最后，對搜索返回的方法進行分類，若搜索返回的方法中存在幾個方法含有相同類屬性值的話，則把最靠前（得分最高）的方法作為代表顯示，其他方法作為相似代碼的超鏈接界面（simCode.jsp）顯示，有一個相似代碼，點擊超鏈接后得到其相似結果，其相似代碼的摘要中還給出其他相似的超鏈接，用以顯示其所有克隆方法。

2.2 實驗比較與分析

目前，用Krugle來搜索，返回搜索結果中雖然給出了相似代碼分類，但是它是基于文件級別的克隆代碼檢測和分類，分類級別太大，并且基于全文搜索，沒有區分方法定義和方法調用。

3 結語

本文深入研究了克隆代碼檢測技術和源代碼搜索引擎的設計和實現，在按方法定義和類名搜索方式中利用克隆代碼檢測技術加入了相似代碼分類顯示功能，并對部分摘要顯示給出改進。通過與已有的代碼搜索引擎搜索結果進行比較，表明本文實現的優化有比較好的效果。

[參考文獻]

[1]黎宣，王千祥，金芝.基于增強描述的代碼搜索方法[J].軟件學報，2017（6）：1405-1417.

[2]KIM J，LEE S，HWANG SW，et al. Towards an intelligent code search engine[J].Association for the Advancement of Artificial Intelligence，2010（3）：1358-1363.endprint