开源对软件工程的作用及关键搜索技术分析*

张 康，曾国荪（.同济大学 计算机科学及技术系，上海 0804；.国家高性能计算机工程技术中心同济分中心，上海 0804）

开源对软件工程的作用及关键搜索技术分析*

张 康1，曾国荪2
（1.同济大学 计算机科学及技术系，上海 201804；2.国家高性能计算机工程技术中心同济分中心，上海 201804）

随着网络技术的迅速发展，开源软件正以前所未有的优势得以迅速发展。现在的开源软件已经成为软件发展的主要流行趋势。开源软件的成功对软件产业起到了巨大的作用。同时，由于目前开源软件数量急剧增加，迅速准确地寻找到用户所需的代码成为一个关键问题。现有的代码搜索引擎大都是基于文本的搜索，并未利用语法、语义信息，在搜索准确性方面受到极大限制。因此，有学者提出利用代码的语法和语义等信息辅助代码搜索。从多个方面对开源的作用做一个较全面的介绍，并对开源代码的关键搜索技术做一个简要综述。

开源；复用；搜索；关键词；语法；语义

0 引言

随着网络时代的来临和开源运动的发展，软件的开发模式、运行环境和提供方式都发生了巨大改变。兴起于20世纪90年代的开源软件取得了巨大成功，其开发活动具有开放分享、频繁发布等特点，能够有效汇聚软件各利益相关方的创意和贡献，其自由松散的表象下隐藏着重要的软件工程新理论，对软件产业的发展和格局产生了深远的影响。目前，开源软件有着良好的发展态势。开源文化是人类几千年的智慧结晶，是一种必然的历史趋势，这种发展趋势是谁也阻挡不了的。

开源软件［1］就是在开发源代码许可证的规范下发布的软件，以保障用户自由使用软件及接触源代码的权利，同时也保障了用户自行修改、复制以及再分发的权利。开源软件的数量目前正在不断大量增长，大量开源软件的出现，对软件工程的实施起到巨大作用，本文以开源对软件工程的作用和关键技术为研究点，主要分析开源对当前软件工程的作用和针对开源代码的关键搜索技术。

1 开源对软件工程的作用

1.1 基于开源库的浏览学习

数量巨大的开源库对于程序员来说是一座巨大的宝藏，源代码融合了作者数十年的方法、经验和教训，对于初学者来说不可多得的学习资源。

对于初学者来说，开源主要有以下两个方面作用：

（1）有助于从理论到实践的平滑过渡。从理论到实践是一个痛苦的过程，正是因为这种痛苦让很多初学者望而却步。

（2）有助于初学者了解技术潮流。开源项目往往没有遗留系统的负担，比较有利于新技术和新想法的实现。初学者通过阅读源码可以紧跟这些新技术和新想法。

1.2开源有助于了解API使用方法

在现代软件行业中，越来越多的程序员依靠API库来完成他们日常的开发任务。HOFFLNANN R［2］等人的研究指出，程序员在软件开发的过程中经常需要调用到其他库里的API。对于一个简单的API来说，通过一个使用例子，可以更加直观地看到使用方法，这会让用户使用API变得更加快捷方便，省下了阅读API文档的过程，提高了开发效率。

通过示例代码学习具体API的使用方法是开发人员进行软件复用的高效手段。例如，Java程序员要使用排序函数sort，通常需要打开文档，找到 sort函数，然后仔细查看文档。这里使用开源代码的搜索引擎 krugle，在开源代码库里输入关键字“sort”，通过对照着搜索结果中调用 API的方法使用该 API，就会省下很多时间，提高开发效率。

1.3 开源有利于代码精确复用

代码复用可以说是任何一个软件企业都不能漠视的课题，因为复用已有的代码意味着开发人员可以节省许多对代码进行测试和提升代码质量的时间。在软件开发中，软件的每个部分几乎都包括可复用的代码块。随着开源的流行，开源代码库的数量的日益庞大，开源代码的数量可以说是不计其数。如此庞大基数的代码几乎包含了各个方面的代码。可以说很多程序员正在写或者将要写的代码都是代码库里已有的代码，这就浪费了大量的人力、物力。因此，开源就是使得任何所需要的代码几乎可以复用。

1.4 开源有助于软件的推广

十年前，开源支持者在试图推广免费软件时陷入了困战，推广实施的障碍包括软件质量、安全保障、后期支持等。然而十年后，开源模式已经被大众接受，相当一部分公司在使用开源软件，开源甚至更加有助于软件的推广［3］。开源已经走过了从忽视到嘲笑到打击到被大家接受的过程［4］，究其原因，可以从以下三点来说明：

（1）注重安全的人更加倾向于开源软件。开源可以让大家更加清楚软件背后到底在做哪些不为人知的事，会让使用开源软件的人更加放心。

（2）节约成本的人更加倾向于开源软件。在使用软件时一个不可避免的因素就是用户是否愿意为其付费。随着开源软件的质量的提高，用户更愿意使用一个安全的、高质量的、便宜的开源软件。

（3）开源社区积攒了大量的人群。在开源代管平台上发布项目会发布得更快，软件发布后很快就会被各种用户使用、转载，形成了一个无形的软件“供需超市”。开源社区内不同背景、不同专长的人汇集成一股集体的力量，对于开源项目的推广起到了重要的作用。正如图1所示，开发者和用户通过社区学习知识、提升能力、提升知名度、扩展人际圈子，企业通过社区可以提高企业知名度、找到合适的人才、推广技术和产品、降低成本等，社区在开源项目的推广中起到了重要的作用。

图1 2社区的作用图

1.5 开源有助于软件的个性化定制

开源软件能够迅速推广得益于个性化定制。个性化定制是用户介入产品的生产过程，将指定的图案和文字印刷到指定的产品上，用户获得自己定制的个人属性强烈的商品。

由于开源的关系，软件也可以个性化定制。开源意味着任何人都可以去下载修改开源软件的源码，制作出属于自己的专属软件版本，而且可以将自己的个性化软件进行传播。

以往，软件给人的思想是“给你什么你就有什么”，大多数专有软件公司根据投资回报比来投资软件，一些个性化的需求往往得不到他们的重视。然而，开源流行开后，个人或者企业可以添加自己想要的功能，这种个性化的定制往往使得开源能够更好地服务于个人或者企业。

1.6 开源有助于软件质量的分析

软件质量是软件产品的灵魂。关于开源和闭源的软件质量的讨论一直没有停止过。闭源，相对来说，表面上是安全的，因为它的代码是不公开的，没有高水平编程能力很难去破解，但它的缺点是本身因开发人员思路的局限性会有很多漏洞，而自己又不知道，这就给了黑客作恶以可乘之机。

开源软件由于源码的开放性，使得用户和第三方评测者能够直接通过代码的分析了解软件的内部质量情况，是一种直观、精确的评测方式。此外，开源软件能集中群体的力量做到及时发现漏洞修补漏洞，可以集思广益发挥群智群力的作用，让开源软件迅速完善起来。

2 源代码搜索的关键技术分析

2.1 基于字符串匹配的搜索技术

2.1.1 基于关键词的搜索

对源代码搜索而言，目前绝大多数的解决方案都可归类为两种：一是借助于开源代码搜索工具或平台如Github或者Sourceforge等；二是借助于通用搜索引擎。两者都是基于关键词的搜索。

在基于关键词的搜索中，主要采用了布尔搜索模型的搜索策略［5］。在布尔搜索中，用户的查询要求用普通的语言叙述，即用户可完全按照自己的思维习惯提问。其中的查询要求（条件）A、B…可以分别用若干个标引词来表示，接着可以用布尔逻辑算符“∨”、“∧”、“﹁”将用户的提问“翻译”成系统可以接受的形式。

一般用tk表示标引词序列，dkn表示与tk有关的文献，则tk*=｛dk1，dk2，…，dkn｝就可以用来表示与标引词tk有关的文献全体组成的集合。令X（q）表示关于查询q的检出文献，则：

（1）q=t，X（q）=t*

（2）q=﹁t，X（q）=t*=Dt*

（3）q=t1∨t2，X（q）=t1*∪t2*

（4）q=t1∧t2，X（q）=t1*∩t2*

很明显，布尔逻辑运算实际上就是集合之间的并、交、补运算，也就是说，布尔逻辑检索系统实际上是通过对若干个代码文件集合（代码文件集D或D的子集）的并、交、补运算回答用户提问的。

然而，这种方法局限性较大，不能充分利用代码在语法结构、语义等方面的特性，也无法保证查询到的代码与用户查询相关。

2.1.2 基于代码段的搜索

尽管基于关键词的搜索也在一定程度上帮助程序员复用源代码，但是它还是会返回给用户数量巨大的搜索结果，其中包括了很多用户并不需要的结果。这是由于基于关键词的搜索并未区分搜索的粒度，比如文件、类或者是函数，而仅仅是将匹配到的所有结果返回给用户。因此，代码搜索技术需要根据用户需要返回不同粒度的结果。基于已复用代码的搜索技术［6］就是返回在过去曾经复用过的代码片段，可以根据用户需求返回粒度较小的函数或者代码段。

在基于已复用代码的搜索技术中，可以认为，过去复用过的代码很有可能会在将来再次被复用，因此返回给用户的结果是在过去被复用过的代码片段。该方法主要包括了代码分析部分和代码搜索部分。代码分析部分探测将要被返回给用户的重复代码片段集合。代码搜索部分返回给用户的是与他们输入相关的重复代码片段。利用基于代码段的搜索方法可以搜索得到更小的粒度，而不仅仅是代码文件，满足用户对于搜索代码段的需求。

2.1.3 源代码及时录入及时搜索参考技术

据调查表明，现代软件开发过程，开发人员大约有19％的工作是在搜索代码。开发人员经常需要参考Web上的代码搜索结果来学习新技术或者辅助开发工作［7］。通常情况下，开发人员需要从IDE或者代码编辑器切换到浏览器，在某个代码搜索网站例如 github上搜索，搜索结果会出现很多结果，每个结果对应着一个链接，开发人员不得不一一打开链接查看结果是否满足需求，十分影响程序员的开发效率。因此，源代码实时录入、实时搜索技术能够帮助用户改善这种状况。

源代码即时录入即时搜索技术旨在即时找到与用户输入代码片段类似或者相同的代码段，并将其实时返回给用户，以帮助用户学习参考或者复用。源代码即时录入即时搜索技术并非是一种新的代码搜索技术，它根据用户在编辑器中实时输入的结果，来搜索和当前用户输入的代码类似的代码片段返回给用户，辅助用户进行开发。

2.2 基于语法的源代码搜索技术

2.2.1 利用程序结构的搜索方法

与网页文件搜索相比，代码文件有着自己的特点，而在传统代码搜索中还只是利用关键字进行搜索，忽略代码本身的特性，因此，有研究人员提出了基于程序结构的源代码搜索。

在结构化程序设计方法中，任何程序都可以用三种基本结构（顺序结构、分支结构、循环结构，如图2所示）来表示，可以利用其程序结构辅助搜索。

图2 三种基本结构

一方面，根据用户的查询输入，生成所需的程序结构的特征向量，这些结构特征包括：顺序结构数、分支结构数、循环结构数等。另一方面，分析出开源库中的源代码文件，得到程序结构的特征向量，并建立数据库。若两个向量的相似度达到一定值，则说明该向量对应的代码与用户所需的程序结构相似，将其返回给用户。

2.2.2 利用控制流图的搜索方法

随后又有研究人员提出利用控制流图辅助搜索。在结构化程序设计方法中，程序是一系列过程的集合，而控制流图是表示一个过程内所有基本快执行的可能流向和每个基本块所对应的语句表，能反映一个过程的实时执行过程。因此，利用控制流图来辅助搜索可以帮助提高精确度。

在该搜索方法中，每个源代码由一个控制流图来表达，每一个节点表示一个基本块。利用从用户输入得到的信息，系统生成一个控制流图，如果两个控制流图是同构的，则可以认为该控制流图对应的代码即为用户要搜索的结果［8］。例如图3（a）中的代码可以生成图 3（b）所示的控制流图。

图3 源代码和对应的控制流图

但是在利用控制流图的搜索方法中，用户需要输入一个控制流图，这无疑加重了用户的使用负担，如何根据用户简单的输入自动生成控制流图值得研究。

2.2.3 利用程序语法树的搜索方法

在2.2.1中，利用程序结构进行代码搜索，然而Sourcerer［9］等搜索引擎比较简单粗糙地利用程序结构信息（比如 if语句的个数、for循环结构的个数等）能使搜索结果精确一些，但是并没有深入全面地利用语法信息来辅助代码搜索，而本文可以利用程序语法树来辅助代码搜索。

语法树是程序代码的树状表示，它是形式化、规范化的程序语义表示，是程序设计者思想的形式化表示。语法树是程序的编译或者解释过程中的一个中间数据结构，处于源代码和中间语言代码之间。源代码太具体，中间语言代码又过于抽象，而语法树介于两者之间，能够形象地抽象出程序的结构信息，为代码的搜索提供更加准确、全面的信息。例如如下代码：

这段代码的语法树如图4所示。

图4 代码的语法树

黄丽韶等人［10］在 Sourcerer的经验上进行了基于程序语法树的源代码搜索的研究，从语法结构角度提出一种源代码的搜索方法，构造基于语法结构的代码过滤器，通过遍历抽象语法树来抽取源代码的信息建立索引。

2.3 基于语义的源代码搜索技术

2.3.1利用功能需求的源代码搜索方法

1998年夏威夷大学的 Woods等人提出了基于需求的代码搜索方法，通过建立代码的抽象数据描述来建立索引，之后通过一种需求描述（Plan）语言来描述软件的功能需求。通过需求描述语言对功能需求的详细描述，可以全面地得到各个功能的具体实现方式，代码搜索引擎将该需求描述和代码库中的抽象数据描述进行匹配，得到匹配后的代码，通过一定的排序和过滤方式，实现了基于需求的搜索方法。该方法搜索的输入比较繁杂，需要用户给出各个过程的实现方法，使用起来会比较复杂。

2.3.2 基于测试的源代码搜索方法

基于测试的源代码搜索（TDCS）［11］是以测试用例作为用户搜索的输入来进行搜索的一种源代码搜索方法。由于测试用例可以用来描述系统中缺失的特征，因此测试用例对于代码搜索来说能够提供更多的语义信息，也会让代码搜索结果更加准确。

TDCS确保测试用例描述了要被搜索的代码的特征。在TDCS中，测试用例被设计用来描述系统中缺失的特征。开发人员通过测试用例来搜索结果，该方法会根据测试用例来构造出用户的查询输入，根据该查询输入在开源库中进行搜索，然后，将搜索得到的结果编织进自己的代码中。

2.3.3 基于输入输出的源代码搜索方法

KATHRYN S［12］提出了一种新的代码搜索方法，基于输入输出来进行源代码搜索。利用该方法，程序设计者只需编写轻量级的需求描述来定义输入和期望的输出。与现有的搜索不同的是，该方法利用 SMT（Satisfiability Modulo Theories）求解，对设计者提供的描述采用符号分析，自动转换为匹配的约束，从而在代码仓库中识别程序或程序片段。

整套方法的核心在于：对代码仓库在独立于用户查询的情况下进行了离线的信息索引，索引使用独特的符号分析，将程序的语义和描述其行为的约束进行映射。

2.4 其他源代码搜索方法

2.4.1 利用程序员行为辅助搜索

程序员始终是软件开发活动的主体，无论哪种源代码搜索方法，都离不开程序员，对程序员习惯进行调查有助于改进搜索方法和搜索体验。通过研究程序员习惯，然后填补程序员搜索活动细节，能够辅助源代码搜索技术，帮助解决程序员搜索代码面临的困难。

例如在沈玲等人［13］对于程序员搜索习惯的研究中发现，程序员一般搜索范围都很广，产生很多不相关的结果。基于他们的观察，如果能在返回结果中包含上下文的信息将是非常有价值的。因此，在代码搜索时，如果能在搜索结果中提供上下文的信息，这将能让程序员更快地做出是否相关的判断。

2.4.2 基于语法结构和输入输出的搜索方法

要提高代码搜索的精度，不仅要从代码的表层字符串含义入手，还要挖掘代码的功能结构和语义信息，这也是当前代码搜索的难点。通过分析语法树和代码的输入输出可以得到非常丰富的信息，进而提高代码搜索的精度。由此产生了结合语法结构和输入输出的搜索方法。

该方法通过分析语法树得到代码的逻辑结构特征，通过分析源代码的输入和输出信息得到程序的语义功能。将语法与语义信息结合起来，可以提高搜索的精度。该方法结合了语法语义信息，为代码搜索方法提供了新的思路。

3 结论

开源软件正在席卷全球，根据Black Duck公司提供的数据，在过去的一年中，他们统计了5000个有开源项目的网址，包括了1000亿源代码行，发现开源项目的数目已经翻了一番。

传统的基于关键字的源代码搜索方法已经不能满足人们的需求，由此产生了各种其他的代码搜索方法，希望更快更好地帮助用户找到高质量代码。然而目前的源代码搜索引擎大都是基于文本的搜索，没有利用代码在语法、语义等上的特性，在搜索准确性方面受到极大的限制。针对这些现有流行的源代码搜索引擎存在的问题已经有越来越多的学者投入了该领域的研究。未来笔者也会继续深入研究开源的相关技术。

［1］徐哲，蔡建平.基于开源软件的软件工程实施系统研究［J］.微计算机信息，2009，25（9）：178-180.

［2］HOFFLNANN R，FOGARTY J，WELD D S.Assieme：finding and leveraging implicit references in a web search interface for programmars In proceedings of the 20th annual AC symposium on User interface software and technology［C］.Newport，Rhode Island，USA，2007：13-22.

［3］熊瑞萍，万江平.开源软件的突围之路——关于开源运动的若干思考［J］.科技管理研究，2009（3）：252-255.

［4］谢世诚.“开源十杰”Michael Tiemann来华开博客［J］.微型机与应用，2007，26（11）：22.

［5］刘红泉，张亮峰.布尔逻辑检索模型的分析探讨［J］.现代情报，2004（9）：4-6.

［6］ISHIHARA T，HOTTA K，HIGO Y，et al.Reusing reused code［J］.WCRE 2013，Koblenz，Germany：ERA-Track，457-461.

［7］陆晨.一种基于 Web资源的代码范例搜索工具［J］.科技资讯，2011（33）：23-25.

［8］BAJRACHARYA S，NGO T，LINSTEAD E，et al.Sourcerer：a search engine for open source code supporting structure-based search［C］.Proceedings of International Conference on Object-Oriented Programming，2006：25-26.

［9］陈新.基于程序控制流图源代码相似程度分析系统［J］.计算机系统应用，2013，22（3）：144-147.

［10］黄丽韶.基于语法结构的源代码搜索的研究［J］.电脑与电信，2013（5）：30-33，39.

［11］LAZZARINI LEMOS O A，CARVALHO de P A，KONISHI G.Using thesaurus-based tag clouds to improve test-driven code search［J］.VII Brazilian Symposium on Software Components，2013，46（1）：99-108.

［12］STOLEE K T，ELBAUM S，DOBOS D.Solving the search for source code［J］.ACM Transactions on Software Engineering and Methodology，2014，23（3）：1-45.

［13］沈玲，黄熹，李艳阳.程序员搜索习惯的研究及对搜索工具开发的启示［J］.中国高新技术企业，2012（27）：27-30.

The role of open source for software engineering and the analysis of the key search technology

Zhang Kang1，Zeng Guosun2
（1.Department of Computer Science and Technology，Tongji University，Shanghai 201804，China；2.Tongji Branch，National Engineering＆amp；Technology Center of High Performance Computer，Shanghai 201804，China）

With the rapid development of network technology，open source software is developing rapidly.Open source software has now become the main trend of software development.The success of open source software has played a huge role in the software industry.Meanwhile，with the current sharp increasing in the number of open source software，finding the code you need has become a key issue.Existing code search engines mostly use text-based search technology.However，these search engines don′t take advantage of syntax，semantics.Therefore，the Search results are inaccurate.So，some scholars have proposed to use of the code syntax，semantics and other information to help code search.This article do a more comprehensive description of the role of open source from the many aspects，and make a review of the key open source search technology.

open source；reuse；search；key words；grammar；semantics

TP311

A

1674-7720（2015）24-0008-05

张康，曾国荪.开源对软件工程的作用及关键搜索技术分析［J］.微型机与应用，2015，34（24）：8-12.

2015-08-24）

张康（1991-），通信作者，男，硕士研究生，主要研究方向：程序设计方法、并行计算。E-mail：zkdnfcf@163.com。

863项目（2009AA012201）；国家自然基金项目（61272107，61202173，61103068）；上海市优秀学科带头人计划项目（10XD1404400）；华为创新研究计划项目（IRP-2013-12-03）；高效能服务器和存储技术国家重点实验室开放基金项目（2014HSSA10）

曾国荪（1964-），男，博士，博士生导师，教授，主要研究方向：并行计算，软件与信息服务。