克隆代码检测在代码搜索中的应用研究

黄丽韶

摘 要：文章设计和开发的代码搜索引擎首先通过扩展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