賈 翕,于海波,方 璐

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

結(jié)合可達性分析的代碼片段推薦

賈 翕,于海波,方 璐

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

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

靜態(tài)方法;代碼片段;語義網(wǎng)規(guī)則語言;可達性分析;代碼推薦;排序

1 概述

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

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

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

2 相關工作

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

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

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

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

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

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

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

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

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

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

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

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

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

3 工作流程

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

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

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

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

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

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

圖2 含靜態(tài)方法代碼片段的推薦過程

4 可達性分析及推薦方法

4.1 Java類型轉(zhuǎn)換本體模型定義與基本信息生成

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

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

本體類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語言中類型的繼承關系,其不僅表示了類型的繼承關系,還表示了接口的實現(xiàn),對象屬性IsA關系具有傳遞性;對象屬性Transfer來表達類型轉(zhuǎn)換關系,根據(jù)2種不同的可見性,有2種不同的類型轉(zhuǎn)換關系,其含義如下:

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

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

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

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

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

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

圖3 Java類型轉(zhuǎn)換的本體模型

4.2 SWRL規(guī)則定義與可達性信息生成

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

通過上述規(guī)則,即可得到與環(huán)境無關的類型可達性信息。

圖4 類型轉(zhuǎn)換的SWRL規(guī)則

圖5 類型可達的SWRL規(guī)則

4.3 入口點選取

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

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

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

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

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

通過以上方法就可以選取出可用的靜態(tài)成員入口點,并結(jié)合當前程序環(huán)境中可以訪問的域成員、方法以及局部變量,由這4個部分構(gòu)成搜索的入口點。

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

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

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

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

4.5 排序

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

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

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

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

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

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

表1 因素權重取值

5 代碼片段推薦實驗

5.1 實驗環(huán)境與方法

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

5.2 實驗結(jié)果與分析

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

表2 靜態(tài)方法入口點削減結(jié)果

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

表3 靜態(tài)方法代碼片段命中頻次

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

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

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

6 結(jié)束語

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

［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］ 章 程.基于機器學習和程序分析相結(jié)合的程序調(diào)試技術研究［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-),男,碩士研究生,主研方向:語義網(wǎng);于海波,講師;方 璐,碩士研究生。

2013-12-11

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

中文引用格式:賈 翕,于海波,方 璐.結(jié)合可達性分析的代碼片段推薦［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.