程序源代码中的切片摘要提取及在搜索中的应用*

李润青，曾国荪

(1. 同济大学 计算机科学及技术系，上海 200092；2. 嵌入式系统与服务计算教育部重点实验室，上海 200092)

0　引言

随着开源社区影响力的增强，软件工程师的开源理念越来越强，促进了高质量的开源项目数量不断增长。据统计仅仅在SourceForge.net开源网站中，有448 706个开源项目可供软件工程师搜索和学习[1]。越来越多的软件工程师通过网上搜索源代码，进行代码重用。对于开源代码，一方面可以借助通用搜索引擎，如Google、百度等，查找下载获得，但是搜索返回结果往往非常多，而且杂乱无序，需要花费大量的时间进一步缩小搜索的范围，以便得到精确和可信的搜索结果[2]。另一方面，也可以借助专用的源代码搜索引擎，以便提高搜索的用户满意度。目前比较流行的有GoogleCS、Koder、Krugle等，它们与通用搜索引擎一样都是基于关键字查找，但是基于关键字的查找方法往往还是查找结果不准确，这是由于计算机很难理解自然语言关键词，且其可能存在二义性[3]。再者基于关键字的代码查找方法没有充分利用源代码具有的特征信息，比如结构信息、语法信息、语义信息等。针对上述的问题，本文将代码内在关键特征作为摘要，给出相应的摘要提取算法，并且应用于开源代码搜索引擎中，以便提高代码搜索的精确度。

1　源程序的结构和特征分析

1.1　源代码的结构形式

程序设计语言发展至今面向结构的编程方法仍广泛应用，因而本文的研究对象是面向结构程序设计语言编写的源代码。C语言是非常典型的面向结构的程序设计语言，本文后续部分以C语言作为例子来阐述。本文不妨将函数作为研究对象。下面是一段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　源代码的关联特征

程序源代码蕴含诸多特征，本文利用程序代码中的控制依赖和数据依赖开展程序切片摘要研究，其中控制依赖可以反映源代码的结构信息，数据依赖可以反映变量的使用关系。下面给出这两个特征的定义。

控制依赖可以用图形化的方式表示。控制依赖图是一个有向图，图中的节点表示程序中的语句，边表示语句间的控制依赖。如果有节点s控制依赖于节点t，则节点s和节点t之间有一条控制依赖边。C语言程序中每个函数的控制依赖图都有Entry节点，表示函数执行的条件。图1是根据例1给出的快速排序源代码绘制的控制依赖图。

图1　快速排序算法的控制依赖图

同样可以用数据依赖图表示代码的数据依赖。如果有节点s数据依赖于节点t，则节点s和节点t之间有一条数据依赖边。图2是根据例1中快速排序源代码绘制的数据依赖图。

图2　快速排序算法的数据依赖

通常，可以将控制依赖图和数据依赖图合并在一起构成程序依赖图PDG。在PDG图中，节点表示程序的语句，控制依赖和数据依赖用不同的边来表示。程序依赖图的构建可以通过文献[4]的方法实现。

2　程序中变量切片的定义及其提取方法

2.1　变量切片的定义

程序切片最早是由WEISER M[5-6]提出，他将删除了无关谓词和语句的程序代码定义为切片。但是单纯利用现有切片的定义不能完全体现某些变量在函数中的作用，所以本文在静态切片基础上，提出一种新的切片，即变量切片。下面给出变量切片的相关定义及其提取方法。

定义3变量切片：对于程序中的变量v，与变量v相关的数据依赖或控制依赖组成的一条或多条路径，称为变量切片。

就函数代码而言，其参数和返回值最能体现它的核心功能，同时函数的返回值往往直接或间接地受到函数参数的影响，因此本文定义的变量切片都是针对函数的参数变量，以便找出反映函数和核心功能的语句。将函数参数列表中的变量分为两类：一类是输入变量，用于函数输出变量的计算；另一类是输出变量，在函数中经过计算后其可被传出。

2.2　函数参数变量切片的获得

在2.1节中给出了变量切片SV的定义，可见具体获得变量切片需要用到第1.2节中阐述的程序依赖图PDG。由于在PDG中并不包括函数参数列表中的声明语句节点，本文对参数列表中的每个变量声明添加一个节点以及与它相关的依赖边。在算法1中，先将函数的源代码文件转化为包含函数参数变量v的程序依赖图PDG，然后从PDG图中找到与变量v声明语句相关的数据依赖或控制依赖组成的一条或多条路径。路径的获取可以由图的深度遍历获得，这里用getNextPathFromPDG表示。变量切片获得算法的伪代码描述如下。

算法1：程序变量切片的获得算法getSliceOfVar

输入：一个函数的源代码的程序依赖图PDG，需要切片的一个变量var，一段函数的源代码文件one_src_file

输出：程序切片SV

getSliceOfVar(PDG, var)

{ varNode ← getVarNodeFromParam(var, PDG);

//通过遍历程序依赖图获得变量var对应的节点

SV ←Ø;

path ← getNextPathFromPDG(PDG,varNode，SV)

// 获得PDG中从varNode 发出的一条路径，且该

路径不在SV中

while(path! = NULL)

{ SV ← SV ∪ {path}

path ← getNextPathFromPDG(PDG,varNode,SV)

}

return SV

}

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

3.1　函数源代码切片摘要的定义

对于源代码而言，摘要是为了体现源代码的主要功能，以及服务于源代码的检索。根据本文2.1节中对变量切片的定义以及对输入变量和输出变量的描述，本文将函数的参数列表，即输入输出变量作为切片对象，分别提取它们的变量切片，并且将这些变量切片集合作为源代码的摘要。

定义4函数源代码切片摘要：对于函数参数列表中的变量，即输入和输出变量，分别求它们对应的切片，这些切片的并集称为函数源代码的切片摘要。

3.2　函数源代码切片摘要的提取

根据3.1节对函数源代码切片摘要的定义，可以得出提取函数源代码切片摘要的方法：首先获得函数参数列表中的每一个变量，然后根据该变量在函数中的使用判断是输入变量还是输出变量，如果该变量是输入变量，则变量切片直接调用算法1即可获得；如果该变量是输出变量，则需要先逆置程序依赖图(即把图的所有边都反向)，再调用算法1，从而获得变量切片。最后对这些变量切片取并集，这样就获得了函数源代码的切片摘要，该算法如下。

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

输入：一段函数的源代码文件one_src_file

输出：程序切片摘要Abstract

getAbstract(one_src_file)

line ←readDefineLine(one_src_file);

//读取函数定义行

paramDict ← getParamAndTypeDict (line);

//获取参数列表变量以及变量的类型

PDG ← getPDG(one_src_file);

//通过函数源代码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　源代码切片摘要的应用场景

源代码切片摘要可以应用于即时录入即时输出的代码编程环境，即在程序员录入代码后自动根据程序员的已有代码帮助搜索补全程序员所需代码，从而提高程序员的编码效率。图3描述了该应用场景。首先将程序员实时录入的编程代码作为输入，然后对该部分代码进行分析，提取切片摘要，接着把提取的切片摘要作为搜索引擎中的关键字进行搜索，最后将相关可复用源代码作为参考结果即时返回到编程界面，等待程序员选择、拷贝、修改、使用。

图3　源代码切片摘要的应用场景

4.2　源代码摘要在代码搜索中的使用过程

本文通过二次搜索方案，即首先在传统的搜索方法搜索得到结果后，再针对返回结果使用切片摘要的方案进行再次搜索的匹配，以达到精确查找代码的目的。该过程如下：(1)用户录入源代码，将源代码整体作为关键字，利用常用的搜索引擎进行第一次搜索，并将搜索到的目标源代码结果缓存起来；(2)针对前面得到的目标源代码进行代码切片摘要提取；(3)对用户录入的代码进行代码切片摘要提取，并将此摘要与目标源代码中的摘要进行匹配；(4)将返回的结果按照匹配程度进行排序并返回。

4.3　实例分析

图4　快速排序源代码的切片摘要

4.4　源代码搜索应用

本次实验的硬件环境所使用计算机的CPU为2.7 GHz Intel Core i5，内存大小为8 GB。在软件方面，本文设计开发了摘要搜索的原型系统，该系统的代码搜索过程已在4.1节中介绍，其中代码来源是在SearchCode中用关键字进行代码搜索后返回的结果。

为了验证切片摘要的有效性，本文设计了五组实验，每组分为三个对比试验。第一个实验将函数名作为关键字在SearchCode搜索引擎中获取结果，录入的函数名见表1；第二个实验将实现表1中函数功能的源代码作为关键字在SearchCode搜索引擎中获取结果；第三个实验进一步利用第二个实验返回的结果，传入到搜索原型系统中进行二次搜索，将其与原始搜索结果进行比较，来判断代码摘要是否提高了搜索的精准度。执行上述 5 组实验后，分别计算查准率[7]，数据如图5所示[7]。

表1　五组实验涉及的函数

图5　即录入即搜索插件

根据图5可以得到，以切片摘要作为关键字进行匹配相较于以函数名作为关键字查准率平均提高了8%，相较于以函数源代码作为关键字查准率提高了6%，从而证明了代码的切片摘要能够提高搜索的准确率。

5　结论

本文通过对比试验证明使用了代码数据依赖和控制依赖的切片摘要有助于提高代码搜索的准确性。当然，源代码的信息类型有很多，本文只是从控制依赖和数据依赖角度分析代码以提取摘要，对其他方面的信息尚未充分发掘。下一步研究工作将是对源代码中相关更深层次的信息进行挖掘和利用。

[1] 黄丽韶.克隆代码检测在代码搜索中的应用研究[J]. 无线互联科技, 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]韩喆, 陈世鸿. 跳转语句跟随域分析与程序依赖图构造算法[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.