一種基于圖數據庫的代碼結構解析與搜索方法

林澤琦　趙俊峰　謝　冰

(北京大學信息科學技術學院　北京　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).