開源對軟件工程的作用及關鍵搜索技術分析*

張 康，曾國蓀（.同濟大學 計算機科學及技術系，上海 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-），男，博士，博士生導師，教授，主要研究方向：并行計算，軟件與信息服務。