基于图嵌入的软件项目源代码检索方法∗

凌春阳,邹艳珍,3,林泽琦,谢 冰,赵俊峰,3

1(高可信软件技术教育部重点实验室(北京大学),北京 100871)

2(北京大学 信息科学技术学院,北京 100871)

3(北京大学(天津滨海)新一代信息技术研究院,天津 300450)

在软件开发过程中,开发者最常用的复用方式就是通过检索、调用软件项目提供的 API(application programming interface,应用程序接口)来实现所需的功能.然而随着软件项目源代码的规模变得越来越大,源代码之间的依赖关系越来越复杂,API检索也变得越来越困难[1].比如,开源项目Lucene包含了超过5 377个类以及 34 042种方法.而研究人员在研究搜索引擎查询日志时发现,开发者往往花费了大量的时间与精力来查找API[2],通用搜索引擎(如 Google)在检索软件代码方面存在许多问题且效率较低[3].由此也促生了在很多技术性问答网站(如StackOverflow)上,可以发现大量关于如何使用API的提问.

受自然语言处理技术的影响,目前许多软件源代码检索工具,比如 Krugle、Ohloh和 Sourcerer[4]等,都是将源代码视为纯文本进行处理.其基本思路是:利用软件源代码中的自然语言特征,基于查询问题与代码的文本相似度进行匹配,返回相似度较高的检索结果.典型的相似度匹配模型包括布尔模型(Boolean model)[5]、向量空间模型(vector space model)[5]、BM25模型[5]等.然而研究表明,这些工具的准确率不能让人满意.在 Lü等人[6]于2015年进行的一项研究中表明,Ohloh返回的排名前十的结果中,只有25.7%～38.4%是有用的.研究者们指出,导致现有软件源代码检索工具效果不理想的一个主要原因是其缺乏对自然语言查询问题语义的理解.对此,研究者们从深化问题理解的角度提出了许多新的方法,如扩展语义相近的词(semantic similar word)[7]、引入查询重构策略(query reformulation)[8]或利用其他在线文档(如 MSDN)来优化问题理解和检索过程[6]等.虽然这些技术很大程度上提高了API定位的准确度,但其需要积累和利用大量的辅助信息,在上述信息缺乏的情况下,往往不能达到预期效果.本文则希望仅从软件项目的源代码出发,帮助开发者提高API检索的效率,因为源代码是复用过程中能够直接获得的资源,其他信息有时则难以获得.

此外,现有这些检索工具返回的结果往往只有相关的代码片段信息,缺乏对关联API的说明与展示,不便于用户理解目标API调用背后的逻辑关联和整体概念,在一定程度上影响了软件复用的效率.为此,研究者们指出,不应单纯地将软件代码视为纯文本.比如在McMillan等人和Chan等人[9,10]的工作中,将源代码以有向图的形式组织起来,图中的结点表示代码元素,边表示代码元素之间的关联关系.图结构是对源代码知识的一种自然且有效的表示,被广泛应用于软件文档检索、特征定位等问题.借助代码的结构图,对源代码的检索就转化为图上的搜索过程,这样得到的结果既能包含需要被定位的代码元素,又能充分体现代码之间的关联关系.举例来说,假设在使用开源软件项目 ApacheLucene(http://Lucene.apache.org/)的过程中,开发者当前使用 StringField类对一个字符串的字段进行处理.当需求发生变化,还要对含有浮点数的字段进行处理时,这个开发者就需要使用FloatPoint类并考虑如何重构代码.而我们可以从图1所示的源代码图中发现,这两个类都继承自Field类,实现了IndexableField接口,同时具有tokenStream方法.因此对开发者来说,一种更好的策略是使用该抽象的父Field作为变量类型,并在处理不同查询时赋值为不同的子类,从而能够较好地满足其上述需求.

Fig.1 Code graph of Lucene project (Part)图1 Lucene项目的代码图示例(部分)

目前,在基于图结构的 API检索方面,主要采用了最短路径[10]、PageRank[9]等浅层语义分析技术.考虑到在图上进行搜索是一个计算量很大的问题,且要求延迟越短越好,算法的效率至关重要.如果使用在线查询最短路径的方式,则由于搜索过程中经常需要计算图上两个结点之间的距离,将会导致较长的延迟时间.Chan等人的工作[10]也提到了这个问题,并利用了一些近似算法进行优化.

针对这些问题,本文提出一种基于图嵌入的软件项目源代码检索方法.图嵌入是一种表示学习技术,能够将图上的结点映射为低维空间中的实值向量,通过向量之间的关系来表达图上的结构信息.对于本文的问题而言,图嵌入技术一方面能够有效表达软件代码图中的深层结构信息,与最短路径等方法相比,更充分地考虑了结点的上下文和关联关系;另一方面,图嵌入过程可以离线进行,在用户在线查询阶段可以立即参与计算,时间复杂度仅是常数级别,大大提高了算法效率.

对比现有工作,本文主要贡献包括:

(1) 提出了一种将软件源代码进行图嵌入表示的方法,该方法能够能够基于软件项目源代码,自动构建其代码图结构,并通过图嵌入对源代码进行信息表示.

(2) 提出了一种基于图嵌入的软件项目源代码检索方法,该方法能够基于项目源代码的图嵌入技术表示,将自然语言查询问题语义匹配到代码子图,提高了检索的准确性,同时展示了API的关联关系;

(3) 实现了一个基于图嵌入的软件项目API检索工具原型,并通过2个具体软件项目中关于源代码检索的实际问题为例,验证了本文方法的有效性.与Chan等人提出的方法相比,本文方法在召回率、F1值上有了显著提升,并有效减低了检索响应时间.

本文第1节介绍图嵌入技术.第2节详细描述本文提出的基于图嵌入的软件项目源代码检索方法.第3节通过实验验证本文方法的有效性.第4节介绍相关工作.第5节对本文工作进行总结并展望未来研究工作.

1 图嵌入

图嵌入(graph embedding)的主要目的是将一张图上的结点映射到低维空间的向量,通过这些向量来体现原本图上的结构信息.这里的结构信息可以是一阶、二阶甚至更高阶的结构,一阶结构信息即保持原本相邻的结点在嵌入空间中的距离仍然很近,而更高阶的结构信息则可以保持原本具有相似上下文的结点在嵌入空间中的距离仍然很近.目前,图嵌入技术在知识表示领域颇受关注,被广泛应用于可视化、顶点分类、关联预测、推荐等任务.现有的图嵌入技术主要可以分为以下几类[11].

· 基于因子分解的图嵌入方法.该类方法将图上结点之间的关系表示成矩阵,对该矩阵进行因子分解从而得到嵌入的向量.矩阵的类型包括邻接矩阵、拉普拉斯矩阵(Laplacian matrix)、卡兹相似矩阵(Katz similarity matrix)等,根据不同的矩阵类型有不同的分解方法,其中,Belkin等人[12]提出的 Laplacian Eigenmaps就是对拉普拉斯矩阵做特征值分解得到的;Ahmed等人[13]提出的GF算法则是基于对邻接矩阵做因子分解.这种方法的时间复杂度是结点数的平方量级,可扩展性较差,对于规模庞大的代码图而言并不适用.

· 基于随机游走的图嵌入方法.该类方法算法能够近似表示图的许多属性,比如结点的中心度和相似度.Perozzi等人提出的 DeepWalk[14]就是该方法的典型代表,该算法利用了神经语言模型 SkipGram的思想,根据周围的邻居结点来预测当前结点的嵌入向量.该类方法通常从某一结点为中心出发进行多次随机游走,最大化观测到的前k个结点以及后k个结点的概率,能够保持高阶的相似性.当只需要观测图的部分结构或者图太大而无法全部测量时,该类方法是一个不错的选择.但是该类方法通常只能捕捉到一条路径上的局部结构信息,并且难以找到最佳的采样方法,调优困难.

· 基于深度学习的图嵌入方法.该类方法有的利用深度自编码器(deep autoencoder)来实现降维,因为自编码器拥有学习数据中非线性结构的能力.典型地,Wang等人[15]提出的SDNE包括无监督和有监督两部分:前一部分由自编码器学习能够重新构邻居的结点嵌入,后一部分则基于 Laplacian Eigenmaps对那些本来相邻而映射到嵌入空间后却相距很远的结点进行惩罚.还有一些算法利用卷积神经网络来得到嵌入向量,如Kipf等人[16]提出的一种半监督学习的方法,这些算法的计算开销更小,更适用于相对稀疏的图.这一类方法虽然能更好地捕捉非线性的结构,然而复杂度还是较高,需要大量的计算开销.

本文采用的是Tang等人[17]提出的LINE(large-scale information network embedding)方法,该方法的可扩展性很好,能够快速地对大规模网络进行嵌入,并且能够同时保留局部和全局的结构信息.该方法严格意义上不属于上述的 3种类型,而是在模型中显式地定义了一阶和二阶的近似函数以及任意 2个结点之间的联合概率分布,通过最小化嵌入矩阵与邻接矩阵所代表的两个概率分布之间的 KL(Kullback-Leibler)散度得到图嵌入的向量.定义好目标函数之后,LINE并没有采用传统的随机梯度下降算法进行优化,而是提出了一种新的边采样的方法(edge-sampling),根据边的权值成比例的概率进行采样,这样能够防止随机梯度下降中由于边的权值过大导致的梯度爆炸问题.为了进一步形象地阐明一阶近似和二阶近似的意义,我们以图2为例进行说明.一阶近似能够将直接有边相连的结点映射到更近的距离,比如图2中的结点6和结点7,它们之间有一条权重很大的边连接.而二阶近似则能够将具有相同邻居的结点映射到更近的距离,比如图2中的结点 5和结点 6,它们都具有很多相同的邻居结点.因此,一阶近似能够保留更多局部的结构信息,而二阶近似能够保留更多全局的结构信息.同时考虑2种近似的结果,就是将结点5～结点7都映射到嵌入空间中更近的距离.

Fig.2 Graph embedding maps nodes with similar structure to closer distance in the embedding space[17]图2 图嵌入将结构相似的结点映射到嵌入空间中更近的距离[17]

2 本文工作

本文提出了一种基于图嵌入的软件项目源代码检索方法,其基本思想是:利用图嵌入技术有效表达软件代码图中的深层结构信息,在检索过程中充分地考虑了结点的上下文和关联关系.如图3所示.

Fig.3 Framework of searching software project’s source code based on graph embedding图3 基于图嵌入的软件项目源代码检索方法框架

该方法主要包括4个部分.

1)代码图的构建:获取项目的源代码并做相应解析,自动构建其代码图.

2)代码图的嵌入:使用图嵌入技术将代码图中的结点表示为向量,以备后续阶段使用.

3)问题与代码图结点的匹配:对用户输入的自然语言问题进行预处理,然后匹配到代码图中结点作为候选结点,并对候选结点进行度量.

4)代码子图的生成与推荐:从第 2阶段得到的候选结点中挑选合适的结点构成子图,并扩展为连通的子图,将排名最佳的结果返回给用户.

2.1 代码图的构建

在一个软件项目(对于面向对象的函数库而言)的源代码中,主要有两种组成成分:一种是类或接口,另一种是方法.而类与方法之间的关联关系的类型大体上所有面向对象语言都共有,当然,部分关联关系与具体编程语言有关.本文以Java语言作为实验对象,考虑了Java语言中的如下6种关联关系,分别为继承(Inh)、实现(Imp)、成员(Mem)、参数(Par)、返回值(Ret)和调用(Call),用集合Rel={Inh,Imp,Mem,Par,Ret}表示(见表1).在此基础上,我们可以利用现有工具对一个开源软件项目的源码进行解析,构建代码图并存储于图数据库中.

Table 1 Relationship types in code graph表1 代码图中的关系类型

代码图(code graph).代码图G=(VG,EG)是一个有向无权图,顶点集VG是所有的类和方法的结点,边集EG中任一条边e(u,v),∃R∈Rel,使得uRv.其中,uRv表示u,v之间存在R类型的关联关系.

现在主流的Java源码解析工具有很多,例如CheckStyle,JAVAssist,Yasca,JDT等.这些工具都现成可用,可以解析Java项目并提取出代码元素以及它们之间的关系.本文使用的是Eclipse的JDT,作为一个轻量级的代码解析工具,它可以迅速将Java代码构建成一个DOM结构的抽象语法树(AST).代码中的每个元素都对应AST上的一个结点,通过遍历AST就可以得到所有代码元素和它们之间的关系,用来构建软件代码结构图.

本文使用图数据库Neo4j(https://neo4j.com/)来存储代码图.Neo4j是一个用Java实现,完全兼容ACID的图数据库,其本身数据组织的结构和我们需求的代码结构图非常相似,也是通过结点与结点之间的关系构成整张图.除此之外,Neo4j还提供了诸如索引(index)、遍历(traversal)等机制以及一种类SQL的查询语言Cypher,以方便在图上进行更高级的操作.

2.2 代码图的嵌入

本文使用图嵌入的原因是在第 3阶段,即代码子图的生成与推荐时,需要计算图上任意两个顶点之间的距离.图嵌入技术可以使得这一步骤变得十分方便与快速.如果采用在线查询两个顶点的最短路径的方式则将非常耗时,而图嵌入过程却是离线的,在构建完代码图后即可完成.

本文使用了Tang等人[17]提出的名为LINE的方法,该方法的可扩展性很好,时间复杂度较低,能够快速地对大规模网络进行嵌入,并且同时保留局部和全局的结构信息,能够适用于有向图、无向图、带权图等多种类型.LINE的源代码可以在Github上找到,本文用Java语言重新实现了该算法.

结点之间的距离.代码图嵌入以后,代码图中的任一顶点v∈VG,都映射到一个向量rv∈Rd,其中,d表示该向量的维度;任意2个顶点u,v之间的距离定义为相应的向量之间的欧氏距离,即dist(u,v)=||ru-rv||2.

2.3 问题与结点的匹配

从这一阶段开始,便进入在线查询的过程.当用户输入一个自然语言的问题后,我们先对问题进行预处理,然后匹配到代码图中一些候选结点.

2.3.1 问题与结点的预处理

本文采用简单的词袋模型(bag of words),将问题视为一些无序的词组成的集合,忽略其句式和位置等信息.由于自然语言文本还存在单词之外的一些符号,如标点符号等,本文将去除非数字和非字母的其他符号,并以此作为分隔符进行切词.切词以后,进行停用词处理.自然语言包含许多无实际意义的功能词,比如冠词和介词等.这些词存在十分普遍而包含信息的却极少,人们一般称之为停用词(stop words).本文去除的停用词包括常见的英文停用词、Java保留字以及项目领域特有的功能词(比如Lucene),等.

代码图中结点(类或方法)的预处理是将该类或方法的名字通过切词得到一个词袋,用来描述该结点的语义信息.本文使用驼峰切词法进行处理,比如QueryParser这个类名,切词后的结果就是{query,parser}.

问题(query).问题Q是由一些去除停用词之后的单词的集合组成,将该单词集合记为BOWQ={q1,…,qn}.

结点单词集合.代码图G中的任一结点v,都有一个与之关联的单词集合,记为BOWv={s1,…,sm}.

2.3.2 产生候选结点

候选结点集合.问题Q所匹配到的候选结点集合是一个集族,记为CandidateQ={C1,…,Cn},其中,Ci(1≤i≤n)是单词qi匹配到的代码图中结点的集合,其大小记为|Ci|.

对于 Query词袋中的每个词,我们都为之在图上找到一系列的候选结点,这样做是为了充分保留原问题中的语义信息.接下来需要明确对于每个单词q,如何匹配到它所对应的候选结点.本文使用文本匹配的方法,主要考虑了如下5种匹配情形.

(1) 全名匹配.单词q本身就是就是一个类或方法的全名,比如q=QueryParser.

(2) 部分匹配.单词q被结点v所对应的词袋所包含,即q∈BOWv,比如q=query.

(3) 词根化匹配.单词q与结点v所对应的词袋中的词经词根化后相同.词根化(stemming)能够将语义上相同而由于语法等原因导致词形不同的词抽取出同样的词根,本文采用 Snowball(http://snowball.tartarus.org/)作为词根化工具.比如q=parse,由于 parse和 parser词根化后都是 pars,因此q会匹配到QueryParser这个结点.

(4) 缩略规则匹配.单词q经过手工构造的一些规则转换后,被结点v所对应的词袋包含.这是为了解决自然语言的词汇与代码元素中的命名不一致的问题,代码元素的命名为了方便,很可能只采取了自然语言单词的缩写,比如Document在代码中的命名可能是Doc,Number在代码中的命名可能是Num,等.

(5) 同义词匹配.单词q与结点v所对应的词袋中的词,经过相似度计算被判定为同义词.同近义词是自然语言处理领域的一个重要研究问题,在自然语言与代码元素匹配的过程中也存在这个问题,比如问题中的词是delete,但代码中某个方法的名字可能是remove,这种情况也应该被考虑.为了解决这个问题,本文使用了在Wikipedia上预训练的glove(https://nlp.stanford.edu/projects/glove/)词向量.通过计算两个词向量的余弦相似度来表示语义的相近性,当大于特定阈值时,就认为这两个词是同义词.

2.3.3 候选结点的度量

上一步骤为了保证对原问题中词汇的覆盖程度,产生了大量的候选结点.但这些结点不应该都是同等地位的,有的候选结点与问题语义更贴近,有的却徒增了许多噪音,因此需要对结点与问题的文本相似程度进行度量.本文考虑两种评价指标:一是该结点词袋与问题中相关的词越多越好;二是该结点引入的不相关的词越少越好,即当结点与问题相关的词数量相同时,BOWv越小的结点质量越好.可类比于信息检索中的准确率与召回率,具体定义如下.

为了考虑同义词的影响,在计算两个词袋的交集时,需要进行特殊处理.如果结点词袋中的某个单词不在Query词袋中出现过,那么利用词向量计算该单词与Query中所有单词的余弦相似度,取其中的最大值作为该单词对交集的贡献.因此,该交集的值不一定是整数.

结点权重.以scorerelevant和scoreirrelevant的F1值作为该结点与问题的相关度的度量,称为该结点的权重,记为w(v),其计算公式如下所示.

2.4 子图的生成与推荐

得到候选结点集合之后,需要从中挑选合适的结点来构成能够反映问题语义的子图.从大量的候选结点中构成子图的搜索空间非常巨大,如何高效地生成子图并度量其优质程度是问题的重中之重.最后,将生成的子图扩展成为连通的子图返回给用户.因此,本阶段可分为两个部分:子图的生成与度量,子图的扩展与推荐.

2.4.1 子图的生成与度量

本文从两个方面来评价子图的质量:一是子图中的结点与问题之间的文本相似程度尽可能地高,每个结点的文本相似程度即结点的权重w(v);二是子图中结点之间的距离越近越好,这将起到消除歧义的作用.比如子图中的一个结点是Document类,现在有两种同名的方法add,它们的文本相似程度是相同的,那么距离Document类更近的那个方法更可能是相关的,而距离远的结点可能是一个属于其他类的方法,与本问题无关.

首先,我们定义如何从候选结点的集合中选择子图的顶点集.

顶点集.CandidateQ={C1,…,Cn}构成的子图G′的顶点集V′={Ci,j|xi,j=1},其中,xi,j是二元变量,表示Ci中的第j个结点是否被选中,满足约束条件.

这里的第1个约束条件是为了使问题中的每个词所对应的候选结点集合中至少有1个结点被选中,以此保证对原问题语义的覆盖度.另外,同一个结点可能在不同的集合中重复出现,因此只要该结点在某个集合中被选中,则其他集合中也必须选中它,这就由第2个约束条件保证.

接下来,我们定义一个子图G′的度量函数:

其中的距离dist(u,v)即第 2.2节中所述的使用图嵌入向量计算的欧氏距离.子图的生成过程即求解这个优化问题 minscore(G′),这可以看成一个二次优化问题.为了方便求解,本文提出一种基于柱状搜索(beam search)的方法.柱状搜索可以看作对贪心法的一种优化,每次将保留前k个最佳的候选结果.具体如算法1所示.

算法1.柱状搜索子图.

输入:候选结点集合CandidateQ={C1,…,Cn}.

输出:排名最高的一个子图.

对于输入的候选结点集合,按权值排序后取最高的k个结点作为起始结点,其中,参数k就代表着柱状的大小(beam size).第7行～第10行是先根据公式(5)中的度量函数计算加入当前结点后增加的代价,然后生成一个新的子图加入候选集合中,并计算累积的代价.第13行、第14行仍是只保留列表中排序靠前的k个结果.最后,我们返回排名最高的一个子图.

2.4.2 子图的扩展与推荐

利用图嵌入的向量来计算距离,带来了计算的便利和速度的提升,但由于在选择结点的过程中我们并没有考虑实际存在的边,因此到目前为止,我们只得到了子图的顶点集.为了给用户提供更形象地理解,我们应该将这些结点是如何连接起来的一同展示给用户,即从顶点集扩展成一个连通的子图.

本文利用将这个问题定义成给顶点集V′构造一棵最小生成树(minimum spanning tree,简称MST),将V′中任意两个顶点之间的最小跳数定义为它们之间的边的权重,这样做就意味着用尽可能少的边将所有顶点连接起来.具体算法如下表的算法2所示,其中,第5行的FindShortestPath函数即寻找结点集合X和Y之间最短路径,而每两个结点之间的最短路径可以通过Cypher语句在代码图中进行查询;第8行、第9行是将这条路径上所经过的结点和边都加入到扩展后的子图中.直到所有结点都被包含进来,该算法便得到了一个连通的子图.

算法2.扩展为连通子图.

输入:顶点集V′.

输出:扩展后的子图Ge.

3 实验与实例

基于上述方法,本文设计并实现了基于图嵌入的软件 API检索工具原型.下面我们通过一些实验来验证本文所提出方法和工具的有效性.这些实验主要用于回答下列研究问题.

· 研究问题1:本文所提出的方法是否能够有效地定位用户所需要的API?

本文方法将源代码组织成代码结构图的形式而非仅视为纯文本来处理,其中利用了图嵌入技术,定义了子图的度量函数,并使用基于柱状搜索的算法进行代码子图的检索.我们希望本文所提出的方法在回答开发者提出的实际自然语言问题时,能够有效提升软件项目API检索的效果.为了验证这一点,我们选择了两个著名的开源项目以及与它们相关的自然语言问题进行了验证,并与传统基于文本匹配的方法进行了对比.

· 研究问题2:本文中所提出的图嵌入方法与现有其他检索方法相比效果如何?

在本文所提出的方法中,我们使用了图嵌入方法来挖掘代码图的结构信息,在度量结点之间的距离时,使用图嵌入向量之间的距离,并由此定义了子图的度量函数.我们关心图嵌入方法是否能够有效地表达代码结构图中蕴含的语义信息,从而改进代码检索的效果.因此,我们设计了相应的实验,将本文所使用的图嵌入方法与现有的基于最短路径的方法进行了对比,以验证图嵌入方法的有效性.

3.1 实验设计

我们选取了两个著名的开源软件项目——Apache Lucene和Apache POI作为实验对象,自动构造了这两个项目的代码图,并分别对其进行了基于自然语言的代码检索实验.实验设计的细节列举如下.

3.1.1 代码图构造

对于每个软件项目,我们基于它的源代码中构建一个代码结构图.Lucene和POI项目的源代码都可以通过其官网的连接或 Github直接下载.一个软件项目往往会有很多个不同的版本,我们选取了这两个项目其中被广泛使用版本进行代码结构图的提取.与代码结构图相关的统计信息在表2中进行了展示,包括源代码版本、类或接口的结点数量、方法的结点数量、关联关系的数量以及构造时间.我们在一台3.40GHz双核处理器、8GB内存的服务器上,解析生成两个项目的代码结构图的时间开销分别为39min和31min.

Table 2 Information of code graphs for experimental projects表2 实验所用项目的代码图信息

在Chan等人的工作中,他们实验所使用的源代码数据是JSE,它是一个非常通用的底层函数库.本文所关注的问题是在软件项目复用时如何有效进行 API检索,我们实验中使用的 Lucene和 POI是领域特定的函数库/软件项目.基于功能实现的需要,其API之间的关联往往非常紧密,使得这类领域特定的软件项目在实际中的进行代码检索和复用的难度更大.从表2中可以看出,Lucene项目代码图中,结点(类和方法等)数量是39 000左右,但它们之间的关联关系数量达到了255 000.同时,在POI项目的代码图中结点数和关联关系的数量关系也与此类似.

3.1.2 API检索问题

进行 API检索的自然语言提问多种多样,为了保证问题的真实有效性,本文使用了2种客观的方式来获得实验所需的问题.

· 对于 POI项目,我们通过其官方网站上提供的用户指南(https://poi.apache.org/spreadsheet/quick-guide.html),抽取了20个问题作为第1组Query.每一个问题在用户指南中都有对应的示例代码,我们将这些示例代码中涉及的API标注为该问题的groundtruth.

· 对于Lucene项目,由于其官方网站上没有相关教程和示例代码,我们使用StackOverflow上关于Lucene项目的问答帖子作为来源,采取随机抽样的方法,直到挑选出 20个与源代码检索相关的问题作为第 2组Query.具体抽取方法是:首先,从StackOverflow上2008年～2016年的数据中找出带有Lucene标签的问题,并按照问题的投票为正,问题有被接受的答案,答案中含有代码片段的条件进行筛选,得到了923个问题,再从这些候选问题中进行无放回的随机抽取,人工阅读是否属于源代码检索相关的问题,直到挑选出20个相关问题;其次,由于这些问题在StackOverflow上分为标题和内容两部分,且标题基本上都可以作为其内容概括,本文就以问题的标题作为代码检索工具的查询输入,即 Query.针对这 20个Query,我们还需要确定其对应的目标API.为此,我们组织了3名熟悉Lucene项目的研究生,分别阅读了这些Query在StackOverflow上的问题和答案,结合帖子的答案和源代码的相关知识,在代码图上进行标注.具体的标注过程是:开发人员以该问题答案中出现的代码片段为基准,并结合源代码的相关文档,利用代码图数据库的查询结果,最终确定该Query对应的API集合.

本文实验所使用的问题是开发者在实际开发过程中遇到的、真实存在的、用自然语言表述的问题,其中部分问题及其标注见表3,问题之中可能含有代码元素的名称,比如lengthNorm,也可能没有.因此我们认为,对这些问题的解答,可以很好地反映各种方法的实际效果.

Table 3 Examples of query and annotated API表3 问题与标注API示例

3.1.3 比较对象

为了考察本文工作的实际效果,我们首先分析比较了本文方法在检索过程中选择第1个结果和选择前3个结果的情况;其次,我们将这两种情形与其他两种典型的代码检索方法进行了对比.实验方法包括以下几种.

(1) 本文方法(Top 1).这一检索方法只采用了本文基于图嵌入的代码检索方法的第1个结果.

(2) 本文方法(Top 3).这一检索方法采用了本文基于图嵌入的代码检索方法的前3个结果.

(3) 基于文本匹配的方法.这一检索方法只考虑问题与结点的文本相似度进行匹配,而不考虑结点之间的距离因素,即第2.4.1节中子图的度量函数公式(5)中只含权重部分而没有距离部分.

(4) 基于最短路径的方法.这一检索方法来源于 Chan等人的工作,其采用最短路径来计算两个结点之间的距离,而非本文方法中使用的图嵌入向量之间的距离.

3.1.4 评价指标

为了评价检索结果的好坏,本文使用了准确率(precision)、召回率(recall)和F1-值(F1-score)作为评价指标.准确率和召回率的计算与真阳性(true positive)等概念有关,其定义见表4.

Table 4 Metrics for search results表4 检索结果的度量指标

在本文的实验中,准确率和召回率的定义如公式(6)、公式(7)所示.

其中,VH标注结果的结点集合,VG本文工具返回结果的结点集合.这里的True positives即两个集合的交集,F1值即准确率和召回率的调和平均数.

3.2 检索实例

针对表3中的实验问题1“how to set document boost attribute in Lucene?”,本文在Lucene软件项目的代码图上进行了检索实验.首先,这个问题被预处理后的单词集合为{set,document,boost,attribute},对于集合中每一个单词,根据第 2.3.2节中提到的匹配方法,分别得到了{1623,1101,63,122}个对应的候选结点,可以看出,候选结点的规模相当庞大.接着,我们针对每个候选结点计算与问题相关程度作为该结点的权重,比如setBoost结点的权重为0.75,Attribute结点的权重为0.4,在这些候选结点的基础上,按照第2.4节中的算法构造问题检索对应的子图.这里分为两个部分.

1)子图的生成:基于离线完成的图嵌入向量的结果可以计算两个结点之间的距离,比如Document结点和setBoost结点之间距离为13.47,根据本文定义的目标函数,通过柱状搜索算法可以得到子图中应该包含的候选结点为{Document,Attribute,setBoost}.

2)子图的扩展:采用基于最小生成树的方法将子图中的结点扩展为连通的代码子图,得到的结果如图4(a)所示,最终的连通子图共包含了8个结点.

Fig.4 Search result for query “how to set document boost attribute”图4 问题“how to set document boost attribute”的检索结果

根据问题的检索结果,我们可以计算对应的准确率、召回率和F1值.在图4中,用方框标出的5个结点是该问题被人工标注的API,而其余3个结点则不属于被标注的.所以该检索结果的准确率为5/8.而由于方框的5个结点刚好覆盖了全部标注的API,因此该结果的召回率为1,最终得到的F1值为10/13.

本文的检索结果是一个子图,不仅展示了用户需要的目标 API,还展示了其与相关代码元素的关联.在此基础上,用户可以通过点击图中的 API结点显示其对应的代码片段.如图4(b)所示,就是在上述结果中点击结点BoostAttributeImpl后,能够看到对应的代码体.由此,该检索结果能为用户理解和复用API提供有效支持.

3.3 实验结果

针对上述得到的两组各20个问题,本文对比了上述4种方法检索结果的平均准确率、召回率和F1值等评价指标,实验结果见表5.实验环境是在Windows 10系统,2.30GHz的双核处理器,8GB内存,Java版本是1.8.实验中,图嵌入向量的维度设置为200,柱状搜索中的柱大小(beamsize)设置为8.

Table 5 Experimental results analysis表5 实验结果分析

3.3.1 方法效果对比

从表5中可以看出,在Lucene和POI这两个项目中,本文方法的Top3都同时获得了最高的平均准确率、召回率和F1值.而本文方法Top 1与Top 3的结果相差很小,说明对于大部分问题本文方法的Top 1就是最佳的结果.

基于文本匹配的方法在两个项目中都获得了最低的平均准确率、召回率和F1值,表明单纯利用问题与结点的文本相似度而忽视代码结构图中的语义信息,难以取得很好的效果.而本文引入图嵌入技术挖掘代码图结构的方法之后,检索结果得到了显著的提升.

基于最短路径的方法在检索过程中也利用到了代码结构图的信息,只是在计算结点之间的距离时使用的最短路径,而非本文方法中使用的图嵌入向量之间的距离.该方法的效果与纯文本匹配方法相比有了较大提升,但仍然显著低于本文方法的结果.本文方法检索结果的F1值比基于最短路径的方法提高了10%,表明了图嵌入方法的有效性,能够比最短路径方法挖掘到更全面的图结构信息.

此外,我们还对比了不同方法的平均响应时间和最长响应时间.从表5中可以看出,纯文本匹配方法的效率最高,平均响应时间和最长响应时间都非常短,因为其计算十分简单,然而其检索效果也是最不令人满意的.而最短路径方法的平均响应时间则非常长,超过了1min,这对于实际的用户交互而言难以接受.这是因为该方法每次计算距离都需要在线查询两个结点之间的最短路径,使用广度优先搜索的算法最坏情况下也需要O(N)的复杂度,这里的N表示所有结点的数量.图嵌入过程由于离线已经完成在线计算两个向量的距离时只需要常数时间,所以本文方法在改进检索效果的同时也大大提升了运行的效率.

Chan等人提出的方法是基于最短路径方法,他们使用的子图度量函数与本文有所差别,他们在论文中报告的实验结果为准确率0.53、召回率0.56、F1值0.54,与本文实验中最短路径方法的结果十分接近.我们使用的数据集并不相同,他们的实验中所使用的问题是从KodeJava网站上挑选的关于使用JSE编程的20个示例,并且将问题抽取为多个词组的形式作为输入.而本文实验中使用的Lucene和POI则是领域特定的函数库,输入也直接是自然语言的问题.

3.3.2 准确率与召回率分析

从实验结果来看,本文方法检索的召回率比较高,但准确率比较低.也就是说,代码子图中除了与Query相关的结点之外,还包含了较多无关的结点.特别是对于 Lucene项目而言,准确率和召回率的差别比较大,因此我们对Lucene项目的20个问题做了进一步的分析.

首先,我们对每个问题的准确率进行了具体分析,结果如图5所示.其中,斜线底色的柱形表示检索结果中所有的结点(API)数量,纯色柱形表示检索结果中正确的结点数量.可以看到,在我们的检索结果中,通常更多的API被返回和推荐出来,大部分子图的规模(结点数)都在 5～8之间,只有两个问题的子图大小达到了 10.经分析发现,导致这个问题的主要原因是基于最小生成树的子图扩展算法.由于很难断定哪种类型边更加有益,我们将所有边的权值都设为相同,从而产生了大量相同长度的路径,因而在扩展路径上很可能引入没有被标注的结点.虽然我们不能确定这些更多的 API是必要的,但从召回率较高的事实出发,也就是在保证能够返回用户所需API的情况下,我们相信,提供更多的信息对用户理解和使用这些API仍然是有益的.而对子图扩展算法的优化,可以作为本文的进一步工作.

Fig.5 Precision of each question图5 每个问题的准确率

我们对每个问题的检索召回率也进行了具体分析,结果如图6所示.其中,斜线底色的柱形表示人工标注时的API结点数量,纯色柱形表示检索结果中正确的结点数量.从图中可以看出,两种柱形高度十分接近,表明整体的召回率很高.对于其中的10个实验示例而言,召回率都达到了100%,而召回率比较低的只有编号为13和15的两个问题,柱形高度之差为2.我们对这些召回率偏低的问题进行了分析,比如编号为15的问题“How to query document have any term in a set?”,这里影响其实验效果的因素是自然语言的歧义性,问题中的set是指集合的意思,而源代码中则存在大量将 set作为动词使用的方法名.由于本文在解析问题时只采用了简单的词袋模型,目前尚无法很好地解决这类歧义问题.本文工具最终匹配到的是setTerm方法,因为该方法含有两个与问题相同的词,结点的权重就很高.在未来工作中,我们将考虑利用代码结构图和图嵌入技术来尽可能地消除自然语言歧义,进一步提升代码检索的效果.

Fig.6 Recall of each question图6 每个问题的召回率

3.4 有效性讨论

· 实验评估的合理性.

本文工作的目标是提高软件项目 API检索与复用的效率,检索结果是一个代码子图.我们关注该子图中的API及其关联结点是否能够解决开发者的问题.本文参考Chan等人的实验指标,使用准确率、召回率和F值作为主要评价,而非信息检索中的 MRR等排名相关指标.而在进行问题答案的标注过程中,我们从该问题对应的示例代码中提取 API,并通过交叉验证等方式保证标注结果的正确性和客观性.由于实验的问题都对应有被接受的代码片段,因此,如果检索的子图中包含了其中的 API,那么我们认为它的确能够帮助开发者解决问题.在未来工作中,我们也将考虑进行用户研究(UserStudy),以进一步定量探讨给开发者带来的提升效果.

· 影响实验结果的内部因素.

关于检索实例:本文针对Lucene和POI项目,分别通过两组代码检索实例进行了实验,共40个问题.尽管问题数量有限,但我们相信这些问题具有很好的代表性,不会影响实验结论:首先,我们选取的实验问题源于实际,一组问题来源于项目官网的用户指南,另一组问题来源于StackOverflow的帖子,这些问题都是开发过程中真实存在的,并且都有相应的代码片段,能够保证问题的较高质量,而对于帖子的筛选和随机抽取,也能够保证其代表性;其次,问题的数量对实验效果没有明显影响,在第 3.3.2节的实验中可以看到,单个检索实例的评价指标结果与所有实例的结果差异不大.在相关工作中,检索实例的数量基本与本文相似.比如,CodeHow[6]使用了 34个问题,Chan[10]使用了40个问题.

· 影响实验结果的外部因素.

关于实验对比方法:由于本文不仅需要定位目标API,还需要展示其与相关代码元素的关联,为此,检索结果是一个子图.返回代码片段或API列表的相关工作不适合与我们直接进行比较.Chan等人的工作是目前与本文场景最接近的工作,其方法的本质是基于最短路径的.因此,本文实验中以最短路径方法作为比较,能够验证本文方法的有效性.

4 相关工作

本文的相关工作主要包括对源代码API检索和图嵌入技术两部分,图嵌入技术已在第 1节进行了介绍.本节主要介绍源代码检索与API推荐的相关技术,重点关注的场景是针对源代码的基于自然语言问题检索.

早期的源代码检索工作主要是将源代码视为纯文本,考虑查询问题与代码之间的文本相似度进行匹配,利用了TF-IDF,BM25等信息检索技术.Krugle,Ohloh和Sourcerer[4]就是其中的典型代表.Sourcerer将解析后的源代码存储在本地的关系型数据库中,并利用Lucene进行索引.这些方法的查询方式通常是基于关键词,返回结果是包含查询中关键词或正则表达式的代码片段.然而,由于其缺乏对问题语义的理解,这些工具的实际效果往往不够令人满意.

针对上述问题,近来有许多研究工作结合了自然语言处理技术,从深化问题语义理解的角度提出了一系列的查询精炼(query refinement)技术应用于代码检索,包括查询扩展(query expansion)、查询重构(query reformulation)等.典型地,COCAB[18]从 StackOverflow 帖子含有的代码片段中提取结构化信息来增强用户的查询,以此解决自然语言与代码元素的词汇不匹配问题.SNIFF[19]先为代码片段中的 API寻找到相应文档作为其注解,继而在这些被注解过的代码上进行自然语言的查询.CodeHow[6]则是通过搜索在线文档识别出一些与问题相关的潜在API,然后使用扩展布尔模型将这些API的信息结合到代码检索的过程中去,从而提高准确度.还有一些方法通过加入语义上相似的词来扩展用户的自然语言查询,这些相似的词可以来源于对网页[20]或者软件项目[9,21]的挖掘.DERECS[22]就预先构造了一个包含大量代码-描述对的语料库,利用它对缺少注释的代码进行描述增强.然而有研究表明:如果在扩展查询时引入了一些不合适的词,将会导致更为糟糕的结果[23].另一些方法则扩展了用户的查询方式,Gu等人[24]的工作中,用户除了可以使用关键词进行查询,还可以加入代码的语法和语义约束条件,从而实现更精确地检索.Wang等人[25]提出了一种动态的检索方法,能够结合用户的反馈信息来优化查询.Haiduc等人[26]提出了一个名为Refoqus的工具,能够预测用户查询的质量,并自动推荐查询重构的策略.BIKER[27]从StackOverflow上抽取了相似的问题和 API,并利用词嵌入(word embedding)来计算文本描述的相似度.基于机器学习的代码检索和 API推荐工作也是目前的一个研究热点,比如,ROSF[28]先通过信息检索的方法生成候选集,再利用有监督学习为候选结果进行重排序.DEEPAPI[29]使用RNN Encoder-Decoder模型,将自然语言问题翻译到API调用序列.Function Assistant[30]则利用语义解析的技术,从代码-文本对中提取特征学习翻译模型.APIRec[31]从细粒度的代码修改库中训练统计学习的模型,基于上下文上进行 API推荐.RecRank[32]则引入路径相关的特征对APIRec的结果进行重排序,从而提升了Top 1推荐的准确率.虽然这些技术很大程度上提高了API定位的准确度,但其需要积累和利用大量的辅助信息,在上述信息缺乏的情况下,往往不能达到预期效果.在本文工作中,我们尤其关注了在没有辅助文档信息和大量查询历史的前提下,如何借助代码自身蕴含的语义信息来辅助提升代码检索的效果.

由于现有代码检索工具往往返回问题相关的代码片段,缺乏对关联 API的说明与展示,不便于用户理解目标API调用背后的逻辑关联,如调用链、类图等,来理解整体的概念[33,34].为此,一些工作开始关注如何在定位与问题相关API的同时,整合、利用和展示代码元素之间的关联信息.典型地,McMillan和Chan等人的工作就将代码组织成有向图的结构,将代码检索问题转化为图上的搜索问题.McMillan等人提出的工具 Portfolio[9],利用了PageRank和SAN(spreading activation network)算法,返回图上与问题相关的前k个结点作为答案.而Chan等人的工作[10]则更进一步地保证了返回结果是一个连通的子图,从而能够清晰地展现出各个结点之间的连接关系.RACS[35]针对 JavaScript框架,构建方法之间的调用关系图,并将自然语言问题也抽取为图形式,寻找与问题的图结构相似的代码片段.许多其他工作也将同样地思想用于文档检索、特征定位等诸多场景[36,37].受这些工作的启发,本文也将源代码组织为有向图的结构,利用了图嵌入技术来挖掘图结构的深层信息,能够更充分地考虑代码图的上下文信息;同时,由于图嵌入可以离线完成,提高了在线查询算法的效率.

5 总结与展望

为了帮助用户更好地检索和复用软件项目 API,本文提出了一种基于图嵌入的软件项目源代码检索方法.图结构能够很好地反映软件项目源代码中 API之间的关联,帮助用户理解软件项目;图嵌入技术能够更充分地挖掘图结构的深层信息,并且可以离线完成,有效地提高检索过程中生成子图的效率.基于上述方法,我们设计并实现了相应的软件项目API检索工具,并以开源项目ApacheLucene和POI为例,通过相关实验验证了本文方法的有效性.

在未来的的工作中,我们将在图嵌入技术的基础上进一步改进问题与结点的匹配方法,利用词性、句法等自然语言处理技术更好地挖掘问题的语义;同时,在匹配过程中增加对边的类型的分析,在扩展子图时考虑路径上其余结点与问题的相关度,以减少不相关结点的引入,从而提升检索的准确率.此外,我们将进一步探讨在实际过程中用户与搜索结果之间的交互会面临的问题,增强搜索结果的可读性.