結合可達性分析的代碼片段推薦

賈 翕,于海波,方 璐

(上海交通大學軟件學院,上海200240)

結合可達性分析的代碼片段推薦

賈 翕,于海波,方 璐

(上海交通大學軟件學院,上海200240)

為滿足日益復雜的軟件需求,開發人員需要通過代碼提示工具來輔助完成開發任務,但現有代碼提示工具在推薦包含靜態方法的代碼片段時存在空間爆炸問題。為此,提出一種基于程序環境信息的代碼片段推薦方法。結合可達性分析進行推薦能夠有效削減靜態方法入口點,在避免空間爆炸的同時,還可以準確、有效地描述程序環境信息。基于該方法實現在Eclipse中的代碼推薦插件,并對Tomcat源碼進行實驗驗證。實驗結果表明,該方法可實現靜態方法的代碼片段推薦,與Eclipse Code Recommenders插件中的推薦方法相比,能獲得更準確的推薦結果。

靜態方法;代碼片段;語義網規則語言;可達性分析;代碼推薦;排序

1 概述

由于軟件系統越來越復雜,因此研究者大多采用成熟的框架來進行開發,以此來提高軟件開發的效率和質量。目前框架的種類越來越多,而且框架本身也越來越復雜,例如,在.NET Framework 4.0中有近700個命名空間、30 000個類型、280 000個方法,在這種情況下,開發人員想要在短時間內掌握龐大的信息就變得十分具有挑戰性。因此,開發環境中集成了很多代碼提示工具來幫助開發人員進行開發工作,如參數補全、函數提示等。

目前,代碼片段推薦主要采用的方法有基于歷史代碼的推薦方法和基于程序環境信息的推薦方法。但對于包含靜態方法的代碼片段,這2種方法均不能給出滿意的推薦結果,其原因在于,僅根據程序上下文,無法得知所有可能的靜態成員,而即使得知所有的靜態成員,由于其數量眾多,如果將其全部加至入口點進行搜索,會造成空間爆炸。

針對上述問題,本文提出一種基于程序環境信息的代碼片段推薦方法,該方法通過本體描述Java程序代碼,結合SWRL規則語言［1］進行類型的可達性分析,同時,根據代碼片段的特征對推薦結果進行排序,使推薦結果更加合理。

2 相關工作

目前,代碼片段推薦研究中主要采用的方法有2種:基于歷史代碼的推薦方法,基于程序環境信息的推薦方法。

基于歷史代碼的推薦方法工作較多,其中,文獻［2］提出了基于歷史代碼的推薦方法,其主要思想為根據當前開發環境的上下文,在歷史代碼中尋找與之相似的節點,查看歷史代碼中的代碼片段并推薦給開發人員。在后續的工作中,擴大了歷史代碼的范圍,采用了網絡上的開源代碼［3］;通過挖掘用例模型來提高推薦的準確性［4-5］;以及采用貝葉斯網絡進行概率分析［6］。但是在該類方法中,歷史代碼的質量直接影響到推薦結果,因此,該方法主要存在以下2個方面的問題:(1)無法確保歷史代碼的覆蓋范圍,當沒有相應的歷史代碼時將無法做出推薦; (2)面對日益更新的框架,無法確保歷史代碼是否過時,甚至是否正確。

文獻［7-8］提出了基于程序環境信息的合成方法,其主要流程包括以下4個部分:

(1)根據程序上下文選取合適的入口點,如局部變量,當前可直接訪問的方法等。

(2)對于每一個入口點,根據其類型中可訪問的類型轉換(通過訪問域成員或者方法成員得到另外一個類型的實例),逐層展開,構成一棵類型轉換樹。

(3)在類型轉換樹上進行搜索,找出根節點到目標類型的可達路徑。

(4)對這些可達路徑進行排序,將結果返回給開發人員。

在上述方法中,通常樹的展開和搜索是同時進行的,而且,為了限制搜索空間,通常會限制搜索的深度或者可能路徑的最大數目,當搜索范圍超過限制的深度或者搜索結果已經找到足夠多的路徑時,就停止搜索。

圖1展示了在Eclipse環境下進行開發過程的一個場景,開發人員在開發Eclipse插件時,希望修改當前狀態欄的信息。開發人員通過查閱API文檔后,找到了IStatusLineManager接口下的setMessage方法。但當前的開發環境并未告知開發人員如何獲取一個IStatus LineManager的實例。本文針對上述場景,研究如何有效地進行推薦出形如圖1所示的 getViewSite().getActionBars().getStatus LineManager()代碼片段,并使推薦結果和上下文緊密相關。

圖1 代碼推薦應用場景實例

對于圖1中所示的靜態方法的代碼片段,現有方法并不能給出滿意的推薦結果,其原因在于:僅根據程序上下文,無法得知所有可能的靜態成員,而即使得知所有的靜態成員,由于其數量眾多,如果將其全部加至入口點進行搜索,會造成空間爆炸。

文獻［9-11］使用了本體對代碼進行描述,但是其不能很好地適用于類型轉換問題。

為解決含靜態方法的代碼片段推薦中的空間爆炸問題,對含靜態方法的代碼片段給出較好的推薦結果,本文提出一種基于程序環境信息的代碼片段推薦方法,該方法通過本體描述Java程序代碼,結合SWRL規則語言［1］進行類型的可達性分析,同時,根據代碼片段的特征對推薦結果進行排序,使推薦結果更加合理。

3 工作流程

為了解決本文第2節中所述靜態方法推薦過程中的空間爆炸問題,需要削減靜態入口點的數目。本文研究通過計算類型的可達性來選取可能的入口點,使其在推薦過程中,僅對目標類型可達的靜態方法和成員進行搜索。

類型可達性是指:在一個特定的程序環境下,一種類型能否通過一系列的類型轉換得到目標類型,它是由一系列類型轉換的傳遞決定的。類型可達性分析的難點在于:

(1)類型轉換并不是在所有環境下都可以一概而論,在實際應用中,很多類型轉換具有可見性(如Java語言中的protected和private關鍵字),從而導致在不同的程序環境下,類型轉換可能具有不同的可達性。

(2)在類型轉換具有不同的可見性時,可達性不具備明顯的傳遞性。

因此,為了準確地分析可達性,需要提出一種準確計算可達性的方法。而可達性又和當前程序環境相關聯,所以本文采用一種形式化的方法,首先構建了一個簡單的本體來描述程序的基本信息,并基于SWRL規則語言定義了類型轉換及可達性判斷規則,然后通過pellet推理機［12］對基本信息進行推理,計算出與環境無關的可達性信息;而與環境相關的可達性信息,本文通過有限次數的對與環境無關的可達性信息的查詢計算出結果。

本文所提出的結合可達性分析的代碼片段推薦方法工作流程如圖2所示。該工作流程分為預計算和實時計算2個部分。預計算對當前工程所引入代碼進行信息提取,通過SWRL規則推理得到可達性。在推薦過程中,可達性信息將被用來判斷目標類型是否可達。在實時計算部分,當開發人員在開發環境中發起推薦請求時,根據程序上下文以及可達性信息,本文方法將得出搜索的入口點,通過搜索得出的多個代碼片段再結合代碼片段特征及程序上下文排序后,將作為最終的推薦結果返回給開發人員。

圖2 含靜態方法代碼片段的推薦過程

4 可達性分析及推薦方法

4.1 Java類型轉換本體模型定義與基本信息生成

在Java類型的本體模型中主要有4個部分組成,分別是類、對象屬性、數據屬性和規則。類定義了Java類型、方法等具體概念以及它們本身的特性;對象屬性定義了這些概念之間存在的關系,也就是類型和方法具備什么樣的關聯;數據屬性則描述了本體類具備的一些常量信息,例如類和方法的名稱等;規則定義了如何根據一系列關系和概念推理出新的關系和概念,通過規則可以推導出類型轉換及類型可達關系。

圖3描述了Java類型轉換的本體模型的主要部分,其中本體和對象屬性描述如下:

本體類package用來描述Java語言中的包;本體類Type用來描述 Java語言中的類型,本體類Type下包含的2個子類:Clazz和Interface,分別用來描述Java語言中類和接口;本體類Member用來描述Java語言中的成員,本體類Member下包含的2個子類:Method和Field,分別用來描述Java語言中的成員方法和成員變量;本體類 Visibility用來描述Java語言中成員的可見性,其4個實例對應Java語言中的4個關鍵字,分別為Public,Protected,Default和Private。

對象屬性HasReturnType用來描述Java語言中成員的類型,其中成員變量的類型為聲明類型,而成員方法的類型為該方法的返回類型;對象屬性IsA表示了Java語言中類型的繼承關系,其不僅表示了類型的繼承關系,還表示了接口的實現,對象屬性IsA關系具有傳遞性;對象屬性Transfer來表達類型轉換關系,根據2種不同的可見性,有2種不同的類型轉換關系,其含義如下:

PublicTransfer(T1,T2):在任何環境中,T1都可以通過類型轉換到達類型T2;

ProtectTransfer(T1,T2):必須在T1的子孫類中,T1可以通過類型轉換到達類型T2;

DefaultTransfer(T1,T2):必須在T1的同包類中,T1可以通過類型轉換到達類型T2;

PrivateTransfer(T1,T2):必須在T1類中,T1可以通過類型轉換到達類型T2。

對象屬性Reach表達的是類型可達關系,根據4種不同的可見性,與對象屬性Transfer一致,也有4種可達關系:PublicReach,ProtectReach,DefaultReach和Private-Reach。

依據上述本體描述和程序源碼,可以得到類型、成員、可見性等基本信息。

圖3 Java類型轉換的本體模型

4.2 SWRL規則定義與可達性信息生成

SWRL規則分為2類:第1類規則定義了如何基于類型自身屬性直接推導得到相應的類型轉換,即圖4中的4條規則;第2類規則定義了如何基于類型轉換信息推導出相應的類型可達性,將在下文中詳細闡述。通過圖3類型轉換的SWRL規則和4.1節中得到的程序基本信息,就可以推理得到代碼中所包含的類型轉換信息。通過圖5類型可達的SWRL規則中的規則5～規則8,可以得到最簡單的可達性信息。規則9～規則11表述的是類型可達性與環境無關的傳遞性,所以,這些信息可以通過預計算來得出。

通過上述規則,即可得到與環境無關的類型可達性信息。

圖4 類型轉換的SWRL規則

圖5 類型可達的SWRL規則

4.3 入口點選取

根據4.2節中的可達性信息生成方法,可以直接得到與環境信息無關的靜態成員入口點,這些靜態成員的返回類型可達目標類型,剩余的一部分可用的靜態成員入口點,則需要結合當前程序環境的信息進行查詢。

發起請求時,當前環境類型為E,其祖先類型的集合為A(T),與其在同一包下的類型集合為S(T),目標類型為D,那么一個類型T在環境類型E中可達類型D必須滿足以下條件中的一個:

(1)T在當前環境類型E的限制下可達A(T)中的任一類型A,且A和D具有ProtectReach關系。

(2)T在當前環境類型E的限制下可達S(T)中的任一類型S,且S和D具有DefaultReach關系。

(3)T和E為同一類型,且E和D具有PrivateReach關系。

通過以上方法就可以選取出可用的靜態成員入口點,并結合當前程序環境中可以訪問的域成員、方法以及局部變量,由這4個部分構成搜索的入口點。

搜索過程的具體步驟如下:

(1)預定義一個COST常量,其為當前代碼片段最大代價值。

(2)在口點中進行搜索不超過目標COST的代碼片段,若返回值為需要類型的代碼片段,這些將計入結果;若其代價超過了目標COST,這些代碼片段將作為下一次搜索的入口點;若既不是筆者需要的類型,也沒有超過目標COST,這些代碼片段將被拋棄。

(3)如果沒有找到足夠多的代碼片段,則提高目標COST,用第(2)步產生的入口點,進行下一次搜索;若第(2)步沒有產生更多的入口點或已找到足夠多的代碼片段,搜索結束。

4.5 排序

代碼片段的代價為每一步類型轉換的代價總和,對于每一步類型轉換的代價,本文通過以下因素計算得出:

(1)代碼片段長度。代碼片段的長度即一個代碼片段完成所需要的類型轉換的數目,筆者希望以更少的類型轉換來達到目標類型,所以,在代價計算中,若代碼片段長度為length,最后代碼片段的整體代價增加Clength。

(2)類型轉換類型。在實際應用中,筆者更希望使用對象方法調用,而不是其他類型下的域成員或者是靜態方法作為其中的一環,因為靜態方法是全局可見的,對象方法比靜態方法與上下文關系更加緊密,而直接訪問其他類型的域成員是一個壞的編程方式。若代碼片段中訪問其他類型的域成員次數為Numfield,使用靜態方法次數為Numstatic,代碼片段的整體代價增加Numfield×Cfield+Numstatic×Cstatic。

一是計算機資源分散、重復建設、設備閑置等現象突出。一般每個分院、系(部)都有自己的小機房，實驗室不具備一定規模，不利于學校整體排課和大型考試等共享應用。同時，分院(系、部)由于缺乏專業計算機教師對設備進行維護與管理，設備完好率偏低，實驗室運行存在一定安全隱患。

(3)方法調用中的參數類型。程序上下文能提供一部分信息,這些信息可以被用作填充代碼片段中所需要的參數。如果一個代碼片段的參數類型在當前環境能夠提供,說明該代碼片段與當前環境關系緊密。在計算中,若代碼片段使用能由當前環境提供的參數次數為Numprovided,而使用了當前環境不能提供的類型的次數為Numunprovided,代碼片段的整體代價增加Numprovided×Cprovided+Numunprovided×Cunprovided。

通過在已有的歷史代碼中進行機器學習,每個因素權重取值如表1所示時,可取得較高的命中率。

表1 因素權重取值

5 代碼片段推薦實驗

5.1 實驗環境與方法

為驗證可達性在尋找靜態方法入口的有效性,以及推薦排序方法的準確性,本文進行實驗數據分析。本次實驗的開發環境為Eclipse 4.2,實驗設備為一臺內存為8 GB,CPU為酷睿雙核2.5 GHz,操作系統為 Windows 7的PC機。通過擴展Eclipse Code Recommenders提供的擴展點,實現了在Eclipse中的代碼推薦插件,并在Eclipse4.2中,下載并編譯了Tomcat 7.0.47的源碼,在源碼中找出了1 338處獲取類型實例的代碼片段,其中145處包含了靜態方法入口點,對這些代碼片段的調用點分別使用基于本文方法的插件和Eclipse Code Recommenders中的推薦功能［12］,與源碼進行對比統計,以該統計結果分析方法的準確性和有效性。

5.2 實驗結果與分析

在Tomcat 7.0.47的源碼中,共找出7處靜態成員作為起始的獲取類型實例的代碼片段,在Tomcat及所依賴的類庫(包括JRE)中共有7 451處靜態成員入口點,在可達性分析后入口點數的統計如表2所示,可以看出在可達性分析后,靜態入口明顯減少,其中在6個入口點以下的達到81.3%,可以有效地削減搜索空間。

表2 靜態方法入口點削減結果

在這145處靜態方法推薦中,命中率如表3所示,可以看出,在削減了搜索空間后,依然能保證78%的推薦命中率,說明可達性分析是準確的。

表3 靜態方法代碼片段命中頻次

在Tomcat 7.0.47的源碼中,共有1 338處獲取類型實例的代碼片段,實驗結果如表4所示,可以看出,大部分情況下都可以在推薦列表中的前三位命中,命中率達到72.2%,其中前十位達到了90.3%,準確率較高,相較目前 Eclipse中的 Eclipse Code Recommenders,在前三命中率(60.7%)和整體命中率(78.4%)上均有所提高,原因在于145處包含靜態方法的代碼片段中,本文方法能有效推薦其中112處,提高整體命中率8.4%;此外,更合理的排序也使得命中率有所提高。

表4 代碼片段命中頻次比較

進一步分析結果,在未命中130處中,有92處屬于向下類型轉換,無法給出合理的推薦,對于向下類型轉換,由于目前的推薦算法是基于靜態代碼,無法很好地預知程序執行過程中的實際類型,因此較難做出合理的推薦。

6 結束語

本文提出一種結合可達性分析實現代碼片段推薦的方法,在排序時結合了程序內部信息,增強了語義性。實驗結果表明,可達性分析在處理靜態方法推薦時可有效削減搜索空間,在擴大可推薦代碼片段范圍的同時,也可提高推薦結果的準確率。與傳統推薦方法相比,本文方法推薦的可用范圍更廣,該方法不僅可用于對象方法的序列,而且對靜態方法也能進行準確推薦;同時在獲取多個結果時,能對結果進行有效排序,提供給開發人員更直觀、有效的結果。但由于本文方法是基于靜態的程序上下文信息,無法很好地應對程序的動態特性,因此對其進行改進是下一步的研究方向。

［1］ Horrocks I,Patel-Schneider P F,Boley H,et al.SWRL: A Semantic Web Rule Language Combining OWL and RuleML［J］.W3C Member Submission,2004,21:79.

［2］ Holmes R,Murphy G C.Using Structural Context to Recommend Source Code Examples［C］//Proceedings of the 27th International Conference on Software Engineering.［S.l.］:ACM Press,2005:117-125.

［3］ Thummalapenta S,Xie Tao.Parseweb:A Programmer Assistant for Reusing Open Source Code on the Web［C］//Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering.［S.l.］: ACM Press,2007:204-213.

［4］ Xie Tao,Pei Jian.MAPO:Mining API Usages from Open Source Repositories［C］//Proceedings of 2006 InternationalWorkshop on Mining SoftwareRepositories.［S.l.］:ACM Press,2006:54-57.

［5］ Mcmillan C,Poshyvanyk D,Grechanik M,et al.Portfolio: Searching for Relevant Functions and Their Usages in Millions of Lines of Code［J］.ACM Tran-sactions on Software Engineering and Methodology,2013,22(4):37.

［6］ 章 程.基于機器學習和程序分析相結合的程序調試技術研究［D］.上海:上海交通大學,2013.

［7］ Perelman D,Gulwani S,Ball T,et al.Type-directed Completion of Partial Expressions［J］.ACM SIGPLAN Notices,2012,47(6):275-286.

［8］ Gvero T,Kuncak V,Kuraj I,et al.Complete Completion Using Types and Weights［C］//Proceedings of PLDI'13.［S.l.］:ACM Press,2013:27-38.

［9］ Würsch M,Ghezzi G,Hert M,et al.SEON:A Pyramid of Ontologies for Software Evolution and Its Applications［J］.Computing,2012,94(11):857-885.

［10］ Keivanloo I,Rilling J,Charland P.Internet-scale Real-time Code Clone Search via Multi-levelIndexing［C］// Proceedings of WCRE'11.［S.l.］:IEEE Press,2011: 23-27.

［11］ Frey T.Hypermodelling:Next Level Software Engineering with Data Warehouses［EB/OL］.(2013-06-26).http:// wwwiti.cs.uni-magdeburg.de/iti_db/publikationen/ps/ auto/phdFrey13.pdf.

［12］ Sirin E,Parsia B,Grau B C,et al.Pellet:A Practical OWL-DL Reasoner［J］.Journal of Web Semantics, 5(2):51-53.

編輯 金胡考

Code Snippet Recommendation Combining with Reachability Analysis

JIA Xi,YU Haibo,FANG Lu
(School of Software,Shanghai Jiaotong University,Shanghai 200240,China)

As the software requirement becoming more and more complicated,developers have an increasing dependency on the code recommendation tools to assist their development tasks,while current code recommendation tools can not provide efficient recommendation for static methods.In order to recommend code snippet including static methods in a faster and more accurate mean,this paper proposes code snippet recommendation method based on program context combing with the reachability analysis,which solvesthespaceexplosion problem during thestaticmethod recommendation well,and it can also describe the program context accurately and effectively.Based on the proposed method,a code recommendation Eclipse plugin is implemented,and a corresponding experiment on Tomcat source code is conducted.Experimental results show that,the proposed method not only owns the capability of recommending code snippet with static method,but also has a higher accuracy compared with the recommendation method of Eclipse Code Recommenders.

static method;code snippet;Semantic Web Rule Language(SWRL);reachability analysis;code recommendation;ranking

1000-3428(2014)11-0071-06

A

TP31

10.3969/j.issn.1000-3428.2014.11.014

賈 翕(1991-),男,碩士研究生,主研方向:語義網;于海波,講師;方 璐,碩士研究生。

2013-12-11

2014-01-02E-mail:g.jessejia@gmail.com

中文引用格式:賈 翕,于海波,方 璐.結合可達性分析的代碼片段推薦［J］.計算機工程,2014,40(11):71-76.

英文引用格式:Jia Xi,Yu Haibo,Fang Lu.Code Snippet Recommendation Combining with Reachability Analysis［J］.Computer Engineering,2014,40(11):71-76.