一种基于图数据库的代码结构解析与搜索方法

林泽琦　赵俊峰　谢　冰

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

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

(linzeqi@pku.edu.cn)



一种基于图数据库的代码结构解析与搜索方法

林泽琦赵俊峰谢冰

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

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

(linzeqi@pku.edu.cn)

A Graph Database Based Method for Parsing and Searching Code Structure

Lin Zeqi, Zhao Junfeng, and Xie Bing

(SchoolofElectronicEngineering&ComputerScience,PekingUniversity,Beijing100871)

(KeyLaboratoryofHighConfidenceSoftwareTechnologies(PekingUniversity),MinistryofEducation,Beijing100871)

AbstractSoftware reuse is a solution to reduce duplication of effort in software development. When reusing an existing software project, software developers usually need to understand how code elements in it are worked and their correlation, which is called code structure. Software developers usually navigate among source code files to understand code structure. This task could be time-consuming and difficult, since source code of a software project is usually large and complex. Therefore, it is essential to demonstrate code structure in an automatic way that software developers can understand it clearly. For this purpose, this paper introduces a graph database based method for parsing and searching code structure. Code structure is extracted from source code files, and well-organized as a labeled and directed graph in graph database. Software developers input natural language queries. A search mechanism analyzes each of these queries, searches the whole code structure and determines which part of the code structure should be demonstrated. This method is of high extensibility: code elements at different granularity and various relationship types among them can be easily stored into the graph database, and analyzing algorithms for different search purposes can be easily integrated into the search mechanism. A tool is implemented based on this method. Experiment shows that with the help of this tool, the time software developers spending on understanding code structure reduces by 17%, which validates that our method does help improving the efficiency of software reuse. An industrial case study has been showed on how software developers get help from this method.

Key wordscode structure; graph database; natural language query; search mechanism; software reuse

摘要软件复用是在软件开发中避免重复劳动的解决方案.在复用一个已有的软件项目时，软件开发人员通常需要理解某些代码元素以及其间的关联关系，称之为代码结构.软件开发人员一般通过浏览软件源代码的方式理解代码结构.由于源代码往往规模较大且结构复杂，理解代码结构通常会耗费大量的时间与精力.因此，将软件开发人员想要理解的代码结构自动、清晰地展示出来是很有帮助的.提出一种基于图数据库的代码结构解析与搜索方法以实现这一目的.这一方法可对软件的代码结构进行解析，并在图数据库中对其进行有效的组织和管理.搜索时，软件开发人员输入自然语言查询语句，该方法中的搜索机制会分析查询语句，并从图数据库中截取出与其相对应的代码结构进行展示.该方法具有高度的可扩展性：不同粒度的结点与多样化的关联关系可以容易地存储进图数据库中，且面向不同搜索目的的代码结构搜索算法亦可以容易地集成进搜索机制中.这一方法已在相应的工具中得到了实现，其有效性在一个商业案例研究中得到了验证.

关键词代码结构;图数据库;自然语言查询;搜索机制;软件复用

软件复用是在软件开发中避免重复劳动的解决方案.实践表明，软件复用能够有效提高软件开发的效率和质量，是解决软件危机的现实可行的途径[1].代码复用是软件复用的主要方式之一，理解软件的代码结构是代码复用的重要前提.一个软件系统的代码结构包括大量基本的代码元素(如类、方法等)以及这些代码元素之间的多种关联关系(如继承、调用等).软件的代码结构通常庞大且复杂，因此，在对一个已有的软件系统进行复用时，对其代码结构的理解是一项重要且困难的任务.

软件开发人员在复用一个并不熟悉的软件时，首先需要概览软件的功能点，并根据需要复用的功能点定位到相关的源代码位置作为理解代码结构的起点，已有的研究工作[2]对这一过程提供了高效、自动化的支持.随后，软件开发人员通常采取浏览源代码的方式来理解软件的代码结构，这种做法通常会耗费较多时间与精力.例如，软件开发人员可能想要概览某个类的继承关系树，或是查看2个方法之间是否存在某种调用层次.诸如此类的代码结构通常分布在多个源代码文件内，难以搜索与展示.解决这一问题的一个有效途径就是对软件的代码结构进行解析，并提供有效的搜索支持，从而辅助软件开发人员更好地理解软件代码.目前，相关的研究工作主要分为2类：1)面向代码结构的模式匹配算法[3-6];2)针对代码结构的形式化查询语言[7-9].这些工作在一定程度上辅助了软件开发人员对代码结构的理解，然而仍然存在以下问题：1)每种代码结构模式匹配算法只适用于匹配单一、特定的代码结构模式，目前缺乏能够根据软件开发人员的需求自动选取合适算法的技术；2) 针对代码结构的形式化查询语言通常只适用于对代码结构中的一些简单模式进行查询，在需要查询较复杂的代码结构时易用性过低.

针对上述问题，本文提出了一种基于图数据库的代码结构解析与搜索方法.首先，该方法从软件系统的源代码文件中解析出代码结构，将其组织为带标记的有向图结构，并利用图数据库进行存储管理；对于软件开发人员给出的类自然语言搜索语句，该方法对其语义进行分析，并根据语义分析的结果选取合适的代码结构模式匹配算法在图数据库上运行，得到图数据库中的一个子图作为搜索结果.本文详述了该方法的2个关键技术点：

1) 一种基于图数据库的代码结构解析方法.已有的工作用以描述代码结构的模型多为抽象语法树.本文对抽象语法树做了进一步的解析，从中提炼出了一种带标记的有向图结构作为软件代码结构模型，更加易于辅助软件开发人员对代码结构的理解.

2) 一种基于自然语言的代码结构搜索机制.这一机制提供了能够轻量级地集成多种代码结构模式匹配算法的框架，并通过语义分析实现了对算法的自动选取.同时，这一机制具有较好的可扩展性，各种代码结构模式匹配算法在该机制下的加入或维护都不会耗费太多的开发成本.

基于这一方法，本文以Java软件为例，实现了一个基线版本的代码结构解析与搜索工具.这一工具分别在开源社区的Java软件以及神州数码公司的智慧城市相关系统上得到了应用，有效地辅助了软件开发人员对已有软件系统的复用.本文给出了该工具的使用案例以验证本文方法的有效性.

1相关研究工作

1.1图数据库

图数据库是非关系型数据库(NoSQL)的一种，使用图理论对数据进行存储、管理和查询.图数据库中的数据以图结构的形式存在，即结点(node)集合与边(relationship)集合的组合.每个结点代表1个实体(entity)，每条边则代表实体之间存在的关联关系.结点和边都可以拥有若干属性(property)，每个属性是1个“键-值”对，用以对实体或关联关系进行具体描述.针对大规模图数据的管理与查询，图数据库系统提供了一套高效的解决方案[10].由于代码结构可以天然地采用图数据结构进行描述，因此使用图数据库来管理软件代码是有效可行的，并有较高的检索及运行效率[9].为此，本文基于图数据库提出了一种代码结构建模与搜索方法.

1.2面向代码结构的模式匹配算法

面向代码结构的模式匹配算法[3-6]以软件代码的句法解析结果(多为抽象语法树)为基础进行模式匹配.软件开发人员在理解软件代码结构的过程中遇到的困难类型是多样的，因此细分出了各种不同的代码结构模式匹配算法.它们所匹配的模式各不相同，分别适用于解决不同的代码结构问题.例如，文献[5]适用于发现函数之间的相关性，而文献[3]适用于分析函数间的调用关系图.对于每一种代码结构模式匹配算法，软件开发人员需要了解其适用于何种代码结构模式后才能利用它来辅助理解软件代码结构，随着可选算法的增多，这将带来较高的学习成本.因此，本文的一项重要工作内容是提供一个能够集成各类代码结构模式匹配算法，并能根据软件开发人员的需求自动选取最合适的算法机制.

1.3形式化的代码结构查询语言

辅助软件开发人员理解软件代码结构的另一种方法是：先使用某种模型对软件的代码结构进行抽象，并以某种数据结构存储起来；再使用特定的形式化查询语言构造查询语句，对该数据进行查询.基于这一思路的工作包括SOUL[7],.QL[8],Wiggle[9]等.借助这些工作，软件开发人员可以以较灵活的方式构造形式化的查询语句，对不同模式的代码结构进行查询.然而，查询的灵活性导致了查询语言的复杂性.当软件开发人员想要查询某种模式的代码结构时，他需要详尽构造查询语句，从而花费较多的时间与精力，且具有较高的学习成本.本文工作以此类工作为基础，在其上搭建了一套较高层次的代码结构查询接口，据此开发出的工具在易用性方面有较大程度的改进.

2基于图数据库的代码结构解析方法

本方法从软件的源代码中将软件的代码结构解析为一个有向图结构，并使用图数据库对其进行管理.相比于关系型数据库、面向对象数据库等其他类型的数据库，选取图数据库对代码结构进行建模的原因有2点：

1) 图数据库无需维护元数据(如关系型数据库中的表定义)，这意味着使用图数据库可以灵活地处理各种不同类型的代码结构，从而保证了本方法的可扩展性；

2) 由于图数据库本身就是为了处理具有复杂网状关联的数据而设计的，因此它在对代码结构的存储、管理与查询方面提供了更为有效的支持[10].

采用软件的静态解析技术可以获取软件的抽象语法树.抽象语法树是代码编译的中间产物，既易于获取，又能最详尽地包含整个代码中的语法结构.对于理解代码结构而言，抽象语法树的缺点在于其包含的信息过于庞杂琐碎，且树形结构限制了对关联关系的灵活表达.综上，将软件的代码结构解析为一个有向图结构的工作可以通过对相应的抽象语法树进行提炼、过滤与组织来完成.

2.1抽象语法树的描述方式

为了制定一套规则来指导从抽象语法树到图结构的转换过程，本文需要先确定采用怎样的形式对抽象语法树进行描述.编译技术中对抽象语法树的描述方式的形式化程度较高，不利于简洁地叙述规则.因此，本文参考Eclipse JDT中Eclipse AST对抽象语法树的描述形式给出了一套描述方案：

1) 一个抽象语法树是一个结点集合；

2) 1个结点代表1个代码元素的声明或1个表达式.代码中的其他信息以结点的属性来表示；

3) 属性的值中可以包含对其他结点的引用.其中用于表达原有的树形结构的引用称为主引用.

选取这样的描述方式的优点是这一描述方式符合多数代码静态解析工具用于描述抽象语法树的数据结构，缺点则在于它并不是高度严谨与形式化的.这一缺点是为了满足叙述从抽象语法树到图结构的转换规则时的简洁性而做的让步，并不影响本方法的实用性.

下面给出了抽象语法树上的若干定义：

1) 若结点Ai的属性中存在对结点Ai+1的引用，1≤i≤n，则称序列A1,A2,…,An为从A1到An的一条引用路径.

2) 声明结点的类型.对于Java软件，一个声明结点可能是“类”、“方法”、或“变量”等，将其称为该声明结点的类型.

3) 对于声明结点A，若存在表达式结点B，使得存在B到A的主引用，则称A是一个主结点.以Java软件为例，局部变量和匿名类的声明结点都不是主结点.

在确定了抽象语法树的描述方式之后，本文在2.2节中介绍基于这一描述方式制定的从抽象语法树到图结构的转换规则.

2.2图数据库结点的生成规则

本方法规定：图数据库中的结点与抽象语法树中的主结点一一对应.

这一规则使得图数据库中的结点数量远远小于抽象语法树中的结点数量，保证了图数据库中图结构的复杂度是在软件开发人员所能接受的范围之内.本方法将主结点视为抽象语法树中用于体现代码结构的最核心的结点，对于Java软件，主结点的类型有4种：类(class)、接口(interface)、方法(method)和域(field).

2.3图数据库结点属性和边的生成规则

抽象语法树中的结点属性被用于构造图数据库中的结点属性和边.本文使用大写字母来表示抽象语法树中的结点，若图数据库中存在结点与该结点相对应，则用该字母加撇的方式来表示图数据库中的相应结点.对于抽象语法树中结点A的属性b，本方法通过5条规则将其表达在图数据库中：

1) 若A′存在，b是对结点B的引用，且B′存在，则根据b在A′与B′之间构建相应的边.

2) 若A′存在，b引用了结点B，B′存在，且b中包含了其他信息，则在A′中构造与b相同的属性b′，且根据b在A′与B′之间构造相应的边.

3) 若A′存在，且规则1与规则2的条件皆不成立，则在A′中构造与b相同的属性b′.

4) 若A′不存在，且存在主结点到A的引用路径，则取最短引用路径，记该路径的头结点为C，根据b在C′与A′之间构造相应的边.

5) 若上述规则的条件皆不成立，则不对属性b做任何处理.

以Java软件为例，对这一系列转换规则进行解释：

规则3处理的情况可以分为2种：

① 将代码元素的一些简单描述信息存储为图数据库中相应结点的属性.例如为图数据库中类型为class的结点添加了类名(name)、包路径(package)、访问权限(access)等属性.

② 属性实际上是对代码元素的引用，但引用的代码元素并未在该软件中声明.导致这种情况的原因可能是该代码元素来自编程语言的基础类库或是来自某些外部类库.

规则1将代码元素间一对一的关联关系存储为图数据库中相应的有向边.例如，将抽象语法树中类的声明结点中的属性“父类”转换为了图数据库中类型为继承(EXTEND)的有向边.

规则4构建了图数据库结点之间的引用关系.例如，图数据库的2个方法结点之间可以存在类型为调用(CALL)的有向边，方法结点到域结点之间可以存在类型为操作(OPERATE)的有向边.

规则2保证了属性b中如集合、泛型、顺序关系等难以完全使用有向边来表达的信息不会被丢失.例如，对于方法结点的参数调用，图数据中不仅构造了代表参数调用的有向边，还将完整的参数调用声明以字符串的形式存储为该方法结点的属性.

对于Java软件，使用Eclipse ASTParser解析出软件的抽象语法树，并按照上述转换规则将其转换为图结构存储于图数据库中.表1和表2给出了该图数据库中的内容概况.

Table 1　Content of Java Code Structure Graph-Node

Note: Bold font means that the property always exists.

Table 2　Content of Java Code Structure Graph-Edge

类似地，对于使用其他编程语言编写的软件，也可以采取本节所述方法对其代码结构进行解析，并将解析结果存储于图数据库中.

3基于自然语言的代码结构搜索机制

本节介绍了一种可扩展的代码结构搜索机制，这一机制基于自然语言对代码结构模式匹配算法进行自动选取，对于软件开发人员的不同搜索目的，分别实现了针对性的检索策略.图1给出了基于自然语言的代码结构搜索机制的基本处理流程.这一搜索机制以软件开发人员输入的1个类自然语言搜索语句为起点，给出代码结构解析所生成的图数据库中的1个子图作为搜索结果.搜索流程可以划分为2个阶段：1)使用自然语言处理技术对搜索语句进行语义分析，判断该搜索语句属于哪种搜索目的；2)依据这一分析结果选择合适的代码结构模式匹配算法，从图数据库中生成搜索结果.在这一流程中，搜索目的的判定规则以及各种代码结构模式匹配算法是需要根据开发人员的实际需求在本机制中进行预定义的，本机制的一个突出优势就是保证了这一预定义工作是轻量级且具有高度可扩展性的.

Fig. 1　Process of the nature language based code structure search mechanism.图1　基于自然语言的代码结构搜索机制基本处理流程

3.1判断搜索语句的搜索目的

在代码结构搜索机制中，判断搜索语句的搜索目的是选取合适的代码结构模式匹配算法的前提条件.在本机制中，搜索目的与代码结构模式匹配算法一一对应，1个搜索目的代表了1个代码结构模式匹配算法所适用的单一、特定的代码结构模式.以下列举了5个搜索目的的示例：

1) 查看某个类所属的继承关系树；

2) 查看2个代码元素间存在的调用关系链；

3) 查看如何获取某个类的对象；

4) 查看某个方法在哪些地方被调用了；

5) 查看某个类可以作为哪些方法的参数.

我们将针对一个搜索目的的处理规则称为一个模式，主要包括：1)搜索目的的判定规则；2)相应的代码结构模式匹配算法.图1中所示的模式处理模块即为代码结构搜索机制中预定义一个模式的统一接口，语义识别模块和答案搜索模块分别对应了上述的2点内容.预定义在本机制内的多个模式处理模块以一个序列的形式进行维护，各个模式处理模块在序列中的初始位置可以是随机的.

对于软件开发人员输入的搜索语句，首先对其进行预处理操作，包括：1)使用自然语言句法解析技术对搜索语句的句法结构进行解析；2)识别出搜索语句中的哪些词法单元指的是软件中的代码元素，并将它们与图数据库中相应的结点相关联.

在预处理操作完成之后，本机制将依次访问模式处理模块序列中的各个模式处理模块.在访问模式处理模块时，首先执行其语义识别模块.语义识别模块基于搜索语句的句法结构、搜索语句中出现的代码元素以及搜索语句中出现的关键词来判定该搜索语句是否应该由这一模式处理模块进行处理.其中，前二者已经由预处理操作给出.每个语义识别模块都维护了一个关键词库，搜索语句中出现的关键词可以通过在其中进行匹配来获取.若搜索语句通过了语义识别模块的判定，则还应当使用参数解析模块来获取该搜索语句中的具体参数信息.

下面通过1个例子来说明判定搜索语句的搜索目的的流程.假设K是对应于搜索目的“查看某个类所属的继承关系树”的模式处理模块，软件开发人员输入的搜索语句为“What does RAMDirectory’s inheritance tree look like?”.预处理操作将该搜索语句解析为图2所示的句法树，并识别出了RAMDirectory这一词法单元对应于图数据库中的1个类结点.当本机制访问到模式处理模块K时，inheritance和tree这2个词法单元在关键词库中匹配成功.上述信息符合K的语义识别模块中预定义的模式，因此这个搜索语句通过K的判定，RAMDirectory所对应的结点则是其参数解析模块所解析出的参数.

Fig. 2　Grammar structure and tagging of the sample question.图2　示例问题的句法结构与标注

可以看到，各个模式处理模块之间是相互独立的，它们的语义识别模块之间亦是相互独立的.因此，对于一个搜索语句，语义识别模块判定为真的模式处理模块数量可以是0个、1个或多个.数量为1是理想的结果.

若选中的模式处理模块数量大于1，则选取位于序列最前端的模式处理模块作为默认结果.同时，将得到的模式处理模块返回给软件开发人员以供手动选择.每个模式处理模块都维护了1个计数器，每当一个模式处理模块被最终选中，则对应的计数器技术加1，同时调整该模式处理模块在序列中的位置，使得序列中各个模式处理模块的计数是递减的.这一处理方法借助软件开发人员的历史操作记录，能够动态地将模式处理模块的优先级逐渐调整为更合理的顺序.

为了处理选中的模式处理模块数量为0的情况，本机制定义了一个缺省的模式处理模块.缺省模式处理模块在序列中的位置保持在最末端，且其语义识别模块对任意搜索语句的判别结果皆为真.对缺省模式处理模块更详细的介绍放在3.2节进行.

3.2从图数据库中生成答案

在完成了对搜索语句的搜索目的的判断之后，代码结构搜索机制需要运行相应的代码结构模式匹配算法以从图数据库中生成答案.这一任务由模式处理模块中的答案搜索模块完成.答案搜索模块以图数据库中的1个子图作为1个搜索结果，这种形式的结果易于清晰、图形化地被呈现给软件开发人员.以图3为例，软件开发人员可以直观地从中看到类Document与类IndexSearcher之间的方法调用层次结构(图3中深色的结点为类结点，浅色的结点为方法结点)：类IndexSearcher的方法doc依次调用方法document和DocumentStoredFieldVisitor，最后调用了类Document的一个构造方法.

Fig. 3　A sample of search result.图3　搜索结果示例

通过调用图数据库的编程接口进行查询是实现答案搜索模块的基础.然而，直接使用图数据库的编程接口来实现答案搜索模块是一项繁琐困难的工作.以面向对象开发方法中的“继承”关系为例，图数据库中建立的代码结构模型并未体现出这一关系是具有传递性的；另一个例子是“拥有方法”关系，一个类所拥有的方法不仅仅是它内部声明的方法，还应当包括它泛化的类的部分方法(考虑方法的可见性与重写).为了解决这个问题，代码结构搜索机制需要在答案搜索模块和图数据库编程接口之间加入一个中间层，即图1中所示的针对代码结构的子图提取API.这套API对在软件代码结构中进行的常见子图提取操作进行封装.以Java软件为例，表3中给出了这套API中封装的若干操作作为示例.

Table 3Samples of APIs for Extracting Sub-graphs from Code Structure Graph

表3　针对代码结构的子图提取API中封装的操作示例

Fig. 4　A sample of inheritance tree.图4　继承关系示例

每个子图提取操作都以图数据库中的一个结点作为起点，返回的结果是一个结点，路径对的集合.下面以表3中的extend操作为例进行介绍.在图4显示的代码结构中，结点A,B,C,D均是类结点.结点A到结点B、结点C都存在类型为EXTEND的边，结点C又存在到结点D、结点E的类型为EXTEND的边.若我们需要抽取出类A的所有子类，由于继承关系的传递性，仅抽取结点A的EXTEND出边所对应的结点是不足够的.表3中的extend操作能够沿着从结点A出发的EXTEND路径进行搜索，从而得到如图5所示的正确结果.

{

}

Fig. 5The result of extend(A).
图5extend(A)的返回结果

子图提取操作在实现上可以调用图数据库的编程接口，也可调用其他操作.在针对代码结构的子图提取API的辅助下，模式处理模块中的答案搜索模块能够更快、更好地被实现.

对于3.1节中所提到的缺省模式处理模块，其答案搜索模块采取这样的算法：对于搜索语句中出现的所有代码元素，获取它们两两之间的最短路径(不考虑边的方向)，将这些最短路径取并后生成的图作为搜索结果.

综上所述，由于各个模式处理模块是可插拔的，且相互之间是独立的，因此代码结构搜索机制具有很高的可扩展性.通过添加、修改或删除相应的模式处理模块，可以容易地对软件开发人员输入的搜索语句的处理策略进行改进.

4工具实现与验证

4.1工具的实现

基于本文提出的代码结构建模与搜索方法，我们实现了一个针对Java软件系统的代码结构搜索工具.目前该工具尚是一个基线版本，其代码结构搜索机制中集成了20个模式处理模块，通用推理模块中集成了18条推理指令.图6是对该工具使用界面的一个截图.

Fig. 6　A screenshot of the tool.图6　工具界面截图

4.2实验验证

为了验证本文提出的方法能够辅助软件开发人员理解软件的代码结构，本文进行了实验验证，实验步骤如下：

步骤1. 分别生成Apache Lucene 3.6.0和Apache POI 3.10这2个开源软件的代码结构图数据库.

步骤2. 分别为这2个开源软件制定3项复用任务.对于Lucene，这3项任务分别为“建立索引并插入数据”、“利用组合条件进行检索”和“以文本相似度进行检索”；对于POI，这3项任务分别为“修改xls文件中某个单元格的内容”、“获取xls文件中某个单元格的公式计算出的值”和“抽取docx文件中的列表信息”.为这些任务分别建立JUnit单元测试.

步骤3. 邀请了18位软件开发人员帮助进行实验验证.这些软件开发人员都熟悉Java语法，且之前从未接触过Lucene和POI这2个项目.本文将他们随即等分为实验组和对照组.

步骤4. 18位软件开发人员被要求各自完成步骤2所述的6项复用任务，允许使用互联网进行搜索，但不允许查询问答社区中的内容.实验组中的9位软件开发人员被要求尽量使用本文所实现的工具进行辅助开发，对照组则不被允许使用本文所实现的工具.

步骤5. 记录每位软件开发人员完成每项任务所花费的时间.

按照这样的实验流程，我们首先可以得到各个复用任务完成时间的统计数据，如表4所示.其中，T1是对照组的平均时间，T2是实验组的平均时间.

Table 4　Average Time of Completing Each Reuse Task

表4表明，在本系统的辅助下，软件开发人员对开源软件进行复用时的工作效率约有17%的提升.

4.3案例研究

我们将本文实现的工具在神州数码公司的软件开发过程中进行了实践.该工具被用于辅助智慧城市领域的软件开发人员理解相关的代码结构.在智慧城市领域中，软件系统经常需要在多个城市之间进行灰盒复用，即一个适用于城市A的软件系统可能需要根据城市B的特定的需求进行部分修改后应用于城市B中.为了完成此类工作，软件开发人员需要在短时间内对待复用的软件系统有较为深入的掌握.在本工具的帮助下，软件开发人员能够更有效且更高效地理解相应软件系统的代码结构，进而提升了对该软件系统的复用效率.

我们对神州数码公司中使用过本工具的软件开发人员进行了访谈以了解本文方法是否有效.这里介绍一个较为典型的例子：在对一个停车场管理软件系统进行复用时，软件开发人员需要了解在这个系统中GPS数据是如何进行收集、处理和存储的.首先，该软件开发人员对系统中的代码元素进行浏览，找到了一个名为GpsData的类.随后，将搜索语句“dataflow of @GpsData”输入本工具，得到的搜索结果如图7所示.这一搜索结果清晰地呈现了类GpsData的数据流涉及到了哪些代码元素，以及这些代码元素之间形成了怎样的代码结构.与这个例子类似地，软件开发人员可以使用本工具对软件系统中原本不易查找、理解的代码结构进行搜索.这就使得软件开发人员在对之前已有的软件系统进行复用时无需耗费大量时间与精力在翻阅源代码上.

Fig. 7　An usage sample of the tool: the data flow of class GpsData.图7　工具使用示例：类GpsData的数据流

5总结及未来工作

对已有的软件系统进行复用可以降低软件的开发成本.在软件复用的过程中，如何理解软件的代码结构是软件开发人员需要面对的一个重要问题.本文提出了一种基于图数据库的代码结构解析与搜索方法，使用该方法能够对各种不同类型与粒度的代码结构进行解析与组织，并提供了一个统一的框架用于集成各种不同的代码结构检索算法以便软件开发人员对代码结构进行搜索.据此设计的工具能够辅助软件开发人员理解软件的代码结构，进而提高软件复用的效率.

本文的主要工作包括2个方面：

1) 基于图数据库的代码结构解析方法.以从代码中解析出的抽象语法树为数据源，讨论了应当从抽象语法树中进一步解析出哪些信息，且这些信息应当以何种转换规则抽象为图结构存入图数据库中.这一工作保证了本文方法能够适用于不同编程语言以及不同类型的代码结构.

2) 代码结构搜索机制.给出了对搜索语句进行语义划分以及答案搜索的一个统一的框架，各种不同的代码结构模式匹配算法可以在这个框架中进行轻量级的定义.这一工作的优势在于其高度的可维护性与可扩展性.此外，搜索结果以图数据库中的一个子图的形式进行图形化呈现，更加直观与全面.

根据这一方法，本文实现了相应的工具，并在商业级的软件复用工作中进行了实践与案例研究.实践表明本文工作在实际应用中的确能够起到辅助软件开发人员理解软件代码结构的作用.我们计划在未来将更多代码结构检索算法集成进本文所实现的工具中.

参考文献

[1]Yang Fuqing, Mei Hong, Li Keqing. Software reuse and software component technology[J]. Acta Electronica Sinica, 1999, 27(2): 68-75(杨芙清, 梅宏, 李克勤. 软件复用与软件构件技术[J]. 电子学报, 1999, 27(2): 68-75)

[2]Li Meng, Zhao Junfeng, Xie Bing. Obtaining functional topics from source code based on topic modeling and static analysis[J]. Scientia Sinica: Informationis, 2014, 44(1): 54-69 (in Chinese)(李萌, 赵俊峰, 谢冰. 基于主题建模和静态分析技术的软件代码功能性主题获取方法[J]. 中国科学：信息科学, 2014, 44(1): 54-69)

[3]Feldthaus A, Schafer M, Sridharan M, et al. Efficient construction of approximate call graphs for Javascript IDE services[C]Proc of IEEE ICSE’13. Piscataway, NJ: IEEE, 2013: 752-761

[4]Gligoric M, Gvero T, Lauterburg S, et al. Optimizing generation of object graphs in Java PathFinder[C]Proc of IEEE ICST’09. Piscataway, NJ: IEEE, 2009: 51-60

[5]McMillan C, Grechanik M, Poshyvanyk D, et al. Portfolio: Finding relevant functions and their usage[C]Proc of IEEE ICSE’11. Piscataway, NJ: IEEE, 2011: 111-120

[6]Milanova A, Liu Y. Static analysis for understanding shared objects in open concurrent java programs[C]Proc of IEEE WCRE’10. Piscataway, NJ: IEEE, 2010: 45-54

[7]De Moor O, Verbaere M, Hajiyev E, et al. Keynote address: QL for source code analysis[C]Proc of IEEE SCAM’07. Piscataway, NJ: IEEE, 2007: 3-16

[8]De Roover C, Noguera C, Kellens A, et al. The SOUL tool suite for querying programs in symbiosis with eclipse[C]Proc of ACM PPPJ’11. New York: ACM, 2011: 71-80

[9]Urma R G, Mycroft A. Source-code queries with graph databases—with application to programming language usage and evolution[J]. Science of Computer Programming, 2015, 97(1): 127-134

[10]Yu Jing, Liu Yanbing, Zhang Yu, et al. Survey on large-scale graph pattern matching[J]. Journal of Computer Research and Development, 2015, 52(2): 391-409 (in Chinese)(于静, 刘燕兵, 张宇, 等. 大规模图数据匹配技术综述[J]. 计算机研究与发展, 2015, 52(2): 391-409)

Lin Zeqi, born in 1992. PhD candidate. Received his bachelor’s degree in Peking University in 2014. His main research interests include software engineering, software reuse, knowledge engineering, data mining, etc.

Zhao Junfeng, born in 1974. Received her PhD degree from Peking University in 2005. Associate professor, senior member of China Computer Federation. Her main research interests include software engineering, software reuse, Web services, cloud computing, ubiquitous computing, etc.

Xie Bing, born in 1970. Received his PhD degree from National University of Defense Technology, Changsha, China in 1998. Professor, senior member of China Computer Federation. His main research interests include software engineering, formal method and software reuse (xiebing@sei.pku.edu.cn).

中图法分类号TP311

通信作者：赵俊峰(zhaojf@sei.pku.edu.cn)

基金项目：国家“八六三”高技术研究发展计划基金项目(2013AA01A605)；国家自然科学基金项目(61472007)

收稿日期：2014-12-08；修回日期：2015-03-10

This work was supported by the National High Technology Research and Development Program of China (863 Program) (2013AA01A605) and the National Natural Science Foundation of China (61472007).