丁雪兒 鈕 俊,2 張開(kāi)樂(lè) 毛昕怡

1(寧波大學(xué)信息科學(xué)與工程學(xué)院 浙江寧波 315211)2(嵌入式系統(tǒng)與服務(wù)計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室(同濟(jì)大學(xué)) 上海 201804)

隨著計(jì)算機(jī)技術(shù)的發(fā)展和應(yīng)用的逐漸深入，出現(xiàn)大量復(fù)雜大規(guī)模軟件系統(tǒng).軟件系統(tǒng)功能的不斷增強(qiáng)與完備等也正導(dǎo)致軟件復(fù)雜度急劇增加，給設(shè)計(jì)、開(kāi)發(fā)和部署、運(yùn)維等帶來(lái)新的挑戰(zhàn).通過(guò)代碼復(fù)用來(lái)構(gòu)造軟件系統(tǒng)可提高軟件開(kāi)發(fā)效率，且對(duì)已被成功使用的各種代碼的復(fù)用還可提高軟件質(zhì)量、降低軟件風(fēng)險(xiǎn)[1].隨著開(kāi)源運(yùn)動(dòng)的興起，互聯(lián)網(wǎng)上已聚集大量開(kāi)放代碼可被學(xué)習(xí)和使用[2]；同時(shí)，企業(yè)組織內(nèi)部也存在大量已被成功實(shí)踐的程序代碼[3]，為基于復(fù)用的高效率、低成本軟件開(kāi)發(fā)提供了基礎(chǔ)和條件.

為了復(fù)用已有代碼，首先需對(duì)已有代碼進(jìn)行有效組織管理，而快速、準(zhǔn)確地搜索到期望代碼則是代碼復(fù)用的關(guān)鍵.當(dāng)前已存在大量針對(duì)代碼復(fù)用的代碼搜索方法，從程序接口、語(yǔ)義、語(yǔ)法等角度去匹配候選代碼[4].其中基于語(yǔ)義的代碼搜索方法主要從用戶期望程序的功能或行為的角度去搜索代碼，能夠更為快速、準(zhǔn)確地定位用戶所需代碼，近年來(lái)獲得學(xué)術(shù)界、工程界重點(diǎn)關(guān)注[5].代碼、語(yǔ)句的功能或行為一般體現(xiàn)為對(duì)輸入數(shù)據(jù)進(jìn)行處理并獲得輸出結(jié)果，故基于輸入/輸出匹配的代碼搜索是一種典型的基于語(yǔ)義的代碼搜索方法.該方法[6-8]需要用戶用多組輸入輸出對(duì)的形式給出自己期望代碼的模糊功能描述，通過(guò)靜態(tài)分析或符號(hào)執(zhí)行等技術(shù)判斷候選代碼能否對(duì)給定輸入獲得期望輸出.2014年，美國(guó)愛(ài)荷華州立大學(xué)的Stolee等人[6]提出一種基于輸入/輸出值匹配的代碼搜索方法，該方法通過(guò)符號(hào)分析技術(shù)將順序結(jié)構(gòu)程序代碼的語(yǔ)義轉(zhuǎn)換為邏輯表達(dá)式，同時(shí)將用戶提供的輸入/輸出值對(duì)轉(zhuǎn)換為語(yǔ)義約束，借助于可滿足性模理論(satisfiability modulo theories, SMT)求解器對(duì)二者的組合進(jìn)行求解，進(jìn)而判斷是否匹配.2016年，文獻(xiàn)[7]對(duì)該方法進(jìn)行擴(kuò)展，使其能夠支持對(duì)分支結(jié)構(gòu)代碼的分析，并通過(guò)執(zhí)行路徑覆蓋度排序等手段解決多路徑代碼的匹配.該方法能在一定程度上提高搜索準(zhǔn)確度和效率，但也存在一些局限性：1)由于計(jì)算過(guò)程的復(fù)雜性，部分程序代碼的輸出值難以直接給出；2)用戶只能提供有限的輸入/輸出值，且難以給出一些特殊的邊界值；3)該方法難以應(yīng)對(duì)如連接數(shù)據(jù)庫(kù)等不具有顯式輸入/輸出值的代碼片段.

為了彌補(bǔ)上述不足，一種有效做法是用戶在以輸入/輸出對(duì)形式進(jìn)行功能描述時(shí)，不必給出具體值，僅給出輸入輸出數(shù)據(jù)的類型即可，從而提出基于輸入/輸出類型匹配的代碼搜索方法[9-12].該類方法一般將代碼功能行為表示為數(shù)據(jù)對(duì)象之間的類型轉(zhuǎn)換圖，基于用戶提供的輸入/輸出類型，通過(guò)對(duì)圖進(jìn)行遍歷以搜索從輸入類型到輸出類型的子圖，每個(gè)子圖所對(duì)應(yīng)代碼序列則構(gòu)成一個(gè)解.這種方法忽略具體數(shù)值，從數(shù)據(jù)類型出發(fā)，在較高語(yǔ)義層次搜索代碼，具有較好實(shí)用性，但已有工作也存在不足.首先，在查詢形式上已有方法僅能處理單個(gè)輸入類型，缺乏對(duì)多個(gè)輸入類型匹配問(wèn)題的研究.其次，在類型分析過(guò)程中，對(duì)具有多個(gè)同類型輸入?yún)?shù)的情形缺乏分析.

針對(duì)上述問(wèn)題，本文提出一種基于Petri網(wǎng)可達(dá)分析的代碼語(yǔ)義搜索方法，整個(gè)搜索過(guò)程如圖1所示.首先，借助程序分析技術(shù)解析候選代碼，構(gòu)建候選代碼數(shù)據(jù)類型轉(zhuǎn)換過(guò)程的Petri網(wǎng)模型.其次，對(duì)于用戶提供輸入/輸出類型對(duì)，利用改進(jìn)后的Petri網(wǎng)可達(dá)分析算法在Petri網(wǎng)上搜索從輸入類型到輸出類型的可達(dá)路徑，并返回該路徑所對(duì)應(yīng)代碼片段.最后采用路徑長(zhǎng)度和代碼復(fù)用率2個(gè)評(píng)價(jià)指標(biāo)對(duì)返回結(jié)果進(jìn)行重排序.注意本文以“函數(shù)”粒度源代碼作為分析對(duì)象.

本文的主要貢獻(xiàn)有2個(gè)方面：

1) 提出一種基于Petri網(wǎng)的代碼行為建模方法，以描述代碼對(duì)數(shù)據(jù)類型的加工變換過(guò)程.與已有工作中所采用的圖模型不同，本文基于Petri網(wǎng)對(duì)代碼行為過(guò)程作進(jìn)一步解析，采用Petri網(wǎng)有向弧表示類型間的轉(zhuǎn)換，有向弧權(quán)重表示轉(zhuǎn)換過(guò)程中參數(shù)類型個(gè)數(shù)，能夠準(zhǔn)確表達(dá)代碼語(yǔ)句及數(shù)據(jù)對(duì)象依賴關(guān)系.

2) 提出一種基于Petri網(wǎng)可達(dá)分析的代碼搜索方法.采用Petri網(wǎng)輸入/輸出標(biāo)識(shí)表示用戶提供查詢中輸入/輸出數(shù)據(jù)對(duì)象的類型及個(gè)數(shù)，利用Petri網(wǎng)可達(dá)算法匹配由輸入標(biāo)識(shí)到輸出標(biāo)識(shí)的目標(biāo)代碼，能夠有效地解決多種形式輸入/輸出類型的搜索問(wèn)題；同時(shí)在基礎(chǔ)Petri網(wǎng)可達(dá)算法上引入誘發(fā)網(wǎng)分析，以提高搜索效率.

1 相關(guān)工作

目前，基于輸入/輸出匹配的代碼搜索方法大致分為2類：基于輸入/輸出測(cè)試值的代碼匹配方法[6-8]和基于輸入/輸出類型的代碼匹配方法[9-12].這2種方法的相同之處在于都是通過(guò)給定的輸入/輸出信息樣例從語(yǔ)義角度描述用戶搜索需求；區(qū)別則在于前者基于符號(hào)執(zhí)行技術(shù)挖掘數(shù)據(jù)對(duì)象值的變化過(guò)程，后者則一般使用圖模型描述數(shù)據(jù)對(duì)象類型的轉(zhuǎn)換過(guò)程.實(shí)踐表明，基于輸入/輸出測(cè)試值的代碼語(yǔ)義搜索方法能夠有效提高代碼搜索的準(zhǔn)確性，而基于輸入/輸出類型的代碼匹配方法則適用更普遍的代碼搜索問(wèn)題.

根據(jù)圖模型的不同，將基于輸入/輸出類型匹配的代碼搜索方法分為基于全局圖模型的方法和基于局部圖模型的方法.其中，前者對(duì)所有源代碼的行為過(guò)程進(jìn)行統(tǒng)一建模，后者則對(duì)單個(gè)函數(shù)進(jìn)行建模.為了更直觀地描述現(xiàn)有方法的各種圖模型，以圖2(a)所示的數(shù)據(jù)庫(kù)連接及表數(shù)據(jù)查詢代碼為例進(jìn)行說(shuō)明，圖2(b)給出代碼對(duì)應(yīng)的類型變化過(guò)程.文獻(xiàn)[9]根據(jù)類庫(kù)和源代碼中的函數(shù)依賴關(guān)系構(gòu)建全局圖模型，如圖3(a)所示，節(jié)點(diǎn)表示數(shù)據(jù)對(duì)象類型，邊表示實(shí)現(xiàn)類型間轉(zhuǎn)換的函數(shù)調(diào)用，采用最短路徑搜索算法求取輸入類型到輸出類型的函數(shù)序列.

文獻(xiàn)[10-12]根據(jù)特定單元源代碼中的函數(shù)依賴關(guān)系構(gòu)建局部圖模型.這些局部圖模型具有各自的特點(diǎn)，文獻(xiàn)[10]的圖模型區(qū)別于文獻(xiàn)[9]的圖模型，增加了專門指向函數(shù)參數(shù)的邊，如圖3(b)所示；文獻(xiàn)[11]的圖模型將節(jié)點(diǎn)分為數(shù)據(jù)節(jié)點(diǎn)和動(dòng)作節(jié)點(diǎn)，其中數(shù)據(jù)節(jié)點(diǎn)表示數(shù)據(jù)對(duì)象類型，動(dòng)作節(jié)點(diǎn)表示函數(shù)調(diào)用，同時(shí)使用數(shù)據(jù)依賴邊和控制依賴邊描述數(shù)據(jù)節(jié)點(diǎn)以及動(dòng)作節(jié)點(diǎn)間的關(guān)系，如圖3(c)所示；在文獻(xiàn)[12]的圖模型中，節(jié)點(diǎn)表示語(yǔ)句，邊表示語(yǔ)句次序，如圖3(d)所示.同時(shí)上述工作的搜索策略也具有差異.文獻(xiàn)[10,12]采用標(biāo)準(zhǔn)的圖搜索算法查找輸入類型到輸出類型的最短函數(shù)序列.文獻(xiàn)[11]則使用Grouminer工具挖掘常用的序列使用模式，然后匹配與查詢相似的使用模式.總的來(lái)看，局部圖模型能夠縮小問(wèn)題空間，相較于全局圖模型有助于提升搜索的準(zhǔn)確性，然而此類圖模型缺乏考慮函數(shù)間的數(shù)據(jù)依賴關(guān)系(參數(shù)類型個(gè)數(shù))，導(dǎo)致其描述的代碼行為不完整，準(zhǔn)確率仍有提升空間.同時(shí)，已有研究無(wú)法滿足多個(gè)輸入類型查詢，適用性較低.

此外，文獻(xiàn)[13-17]基于數(shù)據(jù)對(duì)象的類型來(lái)進(jìn)行代碼搜索，是與本文較為相關(guān)的工作.文獻(xiàn)[13]結(jié)合靜態(tài)分析將源代碼構(gòu)建成有限狀態(tài)自動(dòng)機(jī)，并基于自動(dòng)機(jī)，通過(guò)對(duì)象類型查找語(yǔ)義相關(guān)的代碼片段.但是該方法的查詢形式不支持輸入/輸出類型，因此不能匹配滿足要求的程序代碼或序列.文獻(xiàn)[14]允許用戶使用盡可能準(zhǔn)確的規(guī)格描述，包括關(guān)鍵字、類型、方法簽名、測(cè)試用例等，通過(guò)一組程序轉(zhuǎn)換規(guī)則將用戶要求的內(nèi)容映射到候選方法或類.文獻(xiàn)[15-16]將類型、函數(shù)、接口、成員等代碼結(jié)構(gòu)信息組織為有向圖結(jié)構(gòu)，然后通過(guò)圖搜索算法查找與用戶提供的自然語(yǔ)言查詢相關(guān)的代碼圖.然而由于自然語(yǔ)言與代碼存在較大差異，難以準(zhǔn)確地定位正確解.文獻(xiàn)[17]提出基于神經(jīng)網(wǎng)絡(luò)的深度學(xué)習(xí)方法，首先以向量形式語(yǔ)義關(guān)聯(lián)自然語(yǔ)言查詢與代碼，然后通過(guò)計(jì)算二者的余弦距離返回與查詢語(yǔ)義相近的代碼段.但是其訓(xùn)練過(guò)程過(guò)于復(fù)雜和耗時(shí)，難以被推廣使用.

2 程序代碼的語(yǔ)義描述

2.1 基于類型轉(zhuǎn)換的代碼語(yǔ)義描述

程序代碼為由若干程序語(yǔ)句所構(gòu)成的語(yǔ)句序列，每個(gè)語(yǔ)句代表1個(gè)執(zhí)行數(shù)據(jù)加工的操作，包括操作名以及被加工數(shù)據(jù)對(duì)象2個(gè)部分.這些操作的具體功能通常為讀取或修改對(duì)應(yīng)的數(shù)據(jù)對(duì)象，其具體表現(xiàn)形式為基本運(yùn)算符的運(yùn)用或函數(shù)(或方法)調(diào)用，數(shù)據(jù)對(duì)象可能為常量、變量及數(shù)組、結(jié)構(gòu)體、對(duì)象等擴(kuò)展數(shù)據(jù)類型所對(duì)應(yīng)數(shù)據(jù)實(shí)例.本文暫不考慮與程序結(jié)構(gòu)、流程控制等有關(guān)結(jié)構(gòu)語(yǔ)句、預(yù)編譯指令等不涉及顯式數(shù)據(jù)加工的語(yǔ)句.注意，為了方便描述，本文將融合多個(gè)數(shù)據(jù)加工的復(fù)雜語(yǔ)句劃分為原子操作后進(jìn)行討論，比如，將語(yǔ)句“inta=b+c；”看作“算術(shù)求和”操作及“賦值”操作的復(fù)合.

定義1.數(shù)據(jù)對(duì)象.程序語(yǔ)句的數(shù)據(jù)對(duì)象定義為二元組(type,value)，其中type為數(shù)據(jù)類型，value為該數(shù)據(jù)對(duì)象的值.

定義2.原子操作.程序語(yǔ)句中的原子操作定義為三元組(c,I,o)，其中c為操作符，I為該操作輸入數(shù)據(jù)對(duì)象集合，o為輸出數(shù)據(jù)對(duì)象.

定義1,2中暫未考慮能夠攜帶多個(gè)輸出值的函數(shù)調(diào)用語(yǔ)句，比如C#語(yǔ)言中聲明為out類型的函數(shù)參數(shù).一般地，一段程序代碼的功能或行為由其數(shù)據(jù)加工序列體現(xiàn).具體來(lái)說(shuō)，代碼中所有數(shù)據(jù)對(duì)象的值的變化過(guò)程對(duì)應(yīng)著代碼功能，比如程序分析技術(shù)就主要通過(guò)符號(hào)化手段從值變化過(guò)程來(lái)模擬代碼行為[18].事實(shí)上，忽略數(shù)據(jù)對(duì)象的值的具體變化過(guò)程，單純從被加工數(shù)據(jù)對(duì)象的個(gè)數(shù)、類型的動(dòng)態(tài)變化過(guò)程也能從某種程度上去考察代碼的功能行為[19-20].

本文用程序代碼的操作序列所體現(xiàn)的數(shù)據(jù)對(duì)象的個(gè)數(shù)及其類型的動(dòng)態(tài)變化過(guò)程來(lái)刻畫代碼行為，以應(yīng)對(duì)諸如連接數(shù)據(jù)庫(kù)、模擬HTTP響應(yīng)等不具有顯式數(shù)據(jù)對(duì)象值的程序代碼.Petri網(wǎng)作為一種經(jīng)典的并發(fā)建模語(yǔ)言，能夠很好地刻畫并發(fā)系統(tǒng)的資源加工變化過(guò)程.本文將程序代碼中的數(shù)據(jù)對(duì)象看作資源，用Petri網(wǎng)來(lái)刻畫程序代碼對(duì)數(shù)據(jù)對(duì)象的動(dòng)態(tài)加工過(guò)程，并借助Petri網(wǎng)對(duì)應(yīng)的分析方法來(lái)解決代碼匹配問(wèn)題.

2.2 Petri網(wǎng)基本概念

Petri網(wǎng)為由德國(guó)計(jì)算機(jī)科學(xué)家Carl Adam Petri于20世紀(jì)60年代提出的一種描述離散事件并發(fā)系統(tǒng)的形式化模型，具有嚴(yán)格數(shù)學(xué)定義和圖形表達(dá)能力.Petri網(wǎng)由庫(kù)所、變遷、有向弧3種基本元素組成，庫(kù)所和變遷由有向弧連接.采用Petri網(wǎng)對(duì)系統(tǒng)進(jìn)行分析時(shí)，將庫(kù)所看作系統(tǒng)資源，變遷看作引起資源變化的事件或者操作[21].庫(kù)所能夠容納一定數(shù)量的令牌，表示所代表資源的數(shù)量.為了方便描述，先給出Petri網(wǎng)的形式定義及簡(jiǎn)單實(shí)例.

定義3.Petri網(wǎng).Petri網(wǎng)為五元組PN=(P,T,F,L,W)，其中：

1)P={p1,p2,…,pm}是庫(kù)所的有限集合；

2)T={t1,t2,…,tn}是變遷的有限集合；

3)F?(P×T)∪(T×P)是連接庫(kù)所和變遷的有向弧集合；

4)L:P→是庫(kù)所集合上的標(biāo)記函數(shù)，用于指定庫(kù)所P所對(duì)應(yīng)的令牌數(shù)量；

5)W:F→+是F的權(quán)函數(shù)，表示令牌傳遞中的加權(quán)系數(shù)，W(f)表示W(wǎng)中弧f∈F所對(duì)應(yīng)的分量.

在變遷的觸發(fā)過(guò)程中，各個(gè)庫(kù)所的令牌數(shù)量會(huì)發(fā)生變化.各個(gè)庫(kù)所對(duì)應(yīng)的令牌數(shù)量所構(gòu)成的向量稱為標(biāo)識(shí)M,記初始標(biāo)識(shí)為M0.在標(biāo)識(shí)M中，庫(kù)所p所對(duì)應(yīng)的分量記作M[p].

對(duì)?x∈P∪T，記*x{y∈P∪T|(y,x)∈F}和x*{y∈P∪T|(x,y)∈F}，稱*x和x*分別為x的前集或輸入集和后集或輸出集.如果?p∈*t:M[p]≥W(*t)時(shí)，稱變遷t在標(biāo)識(shí)M下是使能的，記作M[t.如果狀態(tài)標(biāo)識(shí)M下t是使能的，表示資源的數(shù)量滿足觸發(fā)條件，稱t可以觸發(fā).觸發(fā)后得到的后繼標(biāo)識(shí)為M′，記作M[tM′，且有:

定義4.可達(dá)標(biāo)識(shí)集.如果Petri網(wǎng)PN=(P,T,F,L,W)中存在t∈T，使M[tM′，稱M′是從M一步可達(dá)的.如果存在變遷序列t1,t2,…,tk和標(biāo)識(shí)序列M1,M2,…,Mk，使得M0[t1M1[t2…Mk-1[tkMk，稱Mk是從M0多步可達(dá)的.從M0可達(dá)的標(biāo)識(shí)集合稱為可達(dá)標(biāo)識(shí)集，記作R(M0)，且滿足M0∈R(M0).

定義5.Petri網(wǎng)的可達(dá)圖.Petri網(wǎng)PN的可達(dá)圖為二元組GR(PN)=(S,E)，其中S=R(M0)是節(jié)點(diǎn)集，代表Petri網(wǎng)PN中所有的可達(dá)標(biāo)識(shí)或者狀態(tài)；E={(M,t,M′)|M,M′∈R(M0),M[tM′}是有向弧集，代表不同可達(dá)狀態(tài)之間的使能變遷.

例1.Petri網(wǎng)是一種直觀的圖形化建模工具，一般用實(shí)心矩形“”表示變遷，庫(kù)所用圓圈“○”表示，令牌用實(shí)心圓點(diǎn)“?”表示.為便于理解，以圖4為例給出Petri網(wǎng)的數(shù)學(xué)形式化定義的圖形表示.圖4(a)為1個(gè)簡(jiǎn)單Petri網(wǎng)，其初始標(biāo)識(shí)為M0=[p1|→2,p2|→0,p3|→1,p4|→0]，記作向量(2,0,1,0)T，表示庫(kù)所p1的令牌數(shù)量為2，庫(kù)所p3的令牌數(shù)量為1，其余為0；變遷t∈T的前置集為:*t1={p1}，*t2={p2}等；?p∈*t1:M0[p]≥W(*t1)=2，故M0[t1，記作M0[t1M1，其中M1=(0,1,1,0)T為可達(dá)標(biāo)識(shí).圖4(b)為該P(yáng)etri網(wǎng)的狀態(tài)可達(dá)圖.

3 基于Petri網(wǎng)的代碼行為建模

由2.1節(jié)可知，程序語(yǔ)句一般為執(zhí)行數(shù)據(jù)加工的操作組成，而程序代碼的功能行為則表現(xiàn)為數(shù)據(jù)對(duì)象類型及個(gè)數(shù)的轉(zhuǎn)換過(guò)程.本文將操作的數(shù)據(jù)對(duì)象看作資源，程序操作則為導(dǎo)致資源流動(dòng)的事件.根據(jù)定義3的Petri網(wǎng)定義，數(shù)據(jù)對(duì)象的類型和語(yǔ)句可以通過(guò)庫(kù)所和變遷表示，數(shù)據(jù)對(duì)象的個(gè)數(shù)可以通過(guò)有向弧權(quán)重表示.基于Petri網(wǎng)的代碼行為過(guò)程描述為：通過(guò)Petri網(wǎng)中有向弧的指向表示語(yǔ)句中數(shù)據(jù)對(duì)象間的類型轉(zhuǎn)換關(guān)系，通過(guò)有向弧的權(quán)重表示語(yǔ)句中不同類型數(shù)據(jù)對(duì)象的個(gè)數(shù).本節(jié)給出一種基于Petri網(wǎng)的代碼行為過(guò)程建模方法.首先闡明基于Petri網(wǎng)的代碼行為建模機(jī)制，制定Petri網(wǎng)元素與代碼元素之間的對(duì)應(yīng)關(guān)系；其次基于該對(duì)應(yīng)關(guān)系，利用靜態(tài)分析技術(shù)對(duì)程序代碼進(jìn)行分析處理，完成代碼到Petri網(wǎng)的轉(zhuǎn)換.

3.1 基于Petri網(wǎng)的代碼行為模型

單個(gè)程序語(yǔ)句包括有關(guān)操作以及被加工的輸入數(shù)據(jù)對(duì)象集和加工后所生成的輸出數(shù)據(jù)對(duì)象.比如，函數(shù)調(diào)用語(yǔ)句由函數(shù)名、調(diào)用該函數(shù)的主動(dòng)調(diào)用數(shù)據(jù)對(duì)象(caller)、作為參數(shù)的被調(diào)用數(shù)據(jù)對(duì)象(callee)以及返回?cái)?shù)據(jù)對(duì)象組成，其中函數(shù)名為操作符，調(diào)用和被調(diào)用數(shù)據(jù)對(duì)象均為輸入數(shù)據(jù)對(duì)象，返回?cái)?shù)據(jù)對(duì)象為輸出數(shù)據(jù)對(duì)象.

定義6.程序語(yǔ)句為三元組(Sc,Si,O)，其中Sc代表操作符集合，Si代表輸入數(shù)據(jù)對(duì)象集合，O代表輸出數(shù)據(jù)對(duì)象.對(duì)于?c∈Sc，語(yǔ)句輸入數(shù)據(jù)對(duì)象I?Si對(duì)應(yīng)于操作c輸入數(shù)據(jù)對(duì)象，語(yǔ)句輸出數(shù)據(jù)對(duì)象o對(duì)應(yīng)于優(yōu)先級(jí)最低操作c的輸出數(shù)據(jù)對(duì)象.

比如，語(yǔ)句“inta=b+c；”包括算術(shù)、賦值2個(gè)運(yùn)算符，其中算術(shù)運(yùn)算符優(yōu)先級(jí)高于賦值運(yùn)算符，顯然整個(gè)語(yǔ)句功能應(yīng)體現(xiàn)為賦值運(yùn)算的最終結(jié)果，故將變量a作為最終輸出對(duì)象.數(shù)據(jù)對(duì)象個(gè)數(shù)及類型變化過(guò)程可簡(jiǎn)單概括為：通過(guò)語(yǔ)句對(duì)數(shù)據(jù)對(duì)象進(jìn)行加工處理，將一定數(shù)量的特定類型的輸入數(shù)據(jù)對(duì)象轉(zhuǎn)換為特定類型的輸出數(shù)據(jù)對(duì)象.該過(guò)程在Petri網(wǎng)中可描述為：通過(guò)語(yǔ)句變遷的輸入/輸出弧的指向及權(quán)重，表示語(yǔ)句中輸入數(shù)據(jù)對(duì)象到輸出對(duì)象的轉(zhuǎn)換過(guò)程，其中弧由輸入數(shù)據(jù)對(duì)象類型指向輸出數(shù)據(jù)對(duì)象類型，輸入、輸出弧的權(quán)重分別表示轉(zhuǎn)換過(guò)程需要消耗的輸入數(shù)據(jù)對(duì)象、生成的輸出數(shù)據(jù)對(duì)象個(gè)數(shù).

對(duì)于語(yǔ)句s∈S，用ts表示該語(yǔ)句變遷，對(duì)于其輸入數(shù)據(jù)對(duì)象類型i∈Si，用pi表示輸入數(shù)據(jù)對(duì)象類型庫(kù)所，對(duì)于其輸出數(shù)據(jù)對(duì)象類型o，用po表示輸出數(shù)據(jù)對(duì)象類型庫(kù)所.為了方便描述，連接語(yǔ)句變遷與輸入數(shù)據(jù)對(duì)象類型庫(kù)所的輸入弧表示為(pi,ts)，輸入弧權(quán)重表示為W(pi,ts)，即為語(yǔ)句s中類型為i的輸入數(shù)據(jù)對(duì)象個(gè)數(shù).連接語(yǔ)句變遷與輸出數(shù)據(jù)對(duì)象類型的輸出弧表示為(ts,po)，輸出弧權(quán)重表示為W(ts,po)，且W(ts,po)=1.

在Petri網(wǎng)中用輸入數(shù)據(jù)對(duì)象的消耗和輸出數(shù)據(jù)對(duì)象的產(chǎn)生來(lái)建模程序語(yǔ)句，容易出現(xiàn)代碼語(yǔ)義描述的不一致.比如，對(duì)于需要執(zhí)行多次調(diào)用的某個(gè)主動(dòng)對(duì)象x，當(dāng)x執(zhí)行一次方法調(diào)用后，在對(duì)應(yīng)Petri網(wǎng)的語(yǔ)句描述上消耗了該數(shù)據(jù)對(duì)象x，從而導(dǎo)致不能準(zhǔn)確描述將來(lái)其他涉及x調(diào)用的程序語(yǔ)句.因此，對(duì)于被多次重復(fù)使用的數(shù)據(jù)對(duì)象，用Y表示這類數(shù)據(jù)對(duì)象的類型.針對(duì)這類數(shù)據(jù)對(duì)象y∈Y，本文引入一個(gè)特殊的復(fù)制變遷Cy.連接復(fù)制變遷和數(shù)據(jù)對(duì)象類型庫(kù)所的輸入弧和輸出弧分別表示為(py,Cy)和(Cy,py)，其中py表示類型庫(kù)所.輸入弧權(quán)重表示為W(py,Cy)，且W(py,Cy)=1.輸出弧權(quán)重表示為W(Cy,py)，即為該類型的數(shù)據(jù)對(duì)象在程序代碼中被重復(fù)使用的次數(shù).本文給出程序代碼元素與Petri網(wǎng)元素之間的對(duì)應(yīng)關(guān)系，如表1所示:

此外，對(duì)于沒(méi)有明顯輸入或者輸出類型的語(yǔ)句，為了充分保留語(yǔ)句中的語(yǔ)義信息，用void來(lái)表示這類語(yǔ)句的輸入或者輸出數(shù)據(jù)對(duì)象類型，比如new語(yǔ)句的輸入類型、close語(yǔ)句的輸出類型等.

3.2 程序代碼的Petri網(wǎng)構(gòu)建過(guò)程

為了匹配程序代碼，首先需要將所有候選代碼轉(zhuǎn)換成對(duì)應(yīng)Petri網(wǎng)形式.代碼片段到Petri網(wǎng)的轉(zhuǎn)換過(guò)程如圖5所示.本文以Java語(yǔ)言編寫的程序代碼為研究對(duì)象，首先借助已有代碼分析工具解析候選代碼片段，從而提取各個(gè)代碼元素，如語(yǔ)句、操作、參數(shù)個(gè)數(shù)和類型等.其次基于3.1節(jié)所述代碼元素到Petri網(wǎng)元素之間的映射關(guān)系，將候選代碼構(gòu)建成對(duì)應(yīng)Petri網(wǎng)模型，存儲(chǔ)于圖數(shù)據(jù)庫(kù)中，為后期代碼匹配做準(zhǔn)備.

為了便于與Java代碼的無(wú)縫銜接及效率因素考慮，本文選擇輕量級(jí)的Eclipse JDT代碼解析組件ASTParser.該組件可以快速將Java語(yǔ)言程序代碼解析成基于文檔對(duì)象模型(document object model,DOM)結(jié)構(gòu)的抽象語(yǔ)法樹(shù)表示，代碼中的每個(gè)元素對(duì)應(yīng)于抽象語(yǔ)法樹(shù)上某個(gè)節(jié)點(diǎn).采用深度優(yōu)先搜索策略并借助相關(guān)API便可獲取代碼元素如語(yǔ)句、操作、參數(shù)等以及彼此之間的上下文語(yǔ)義關(guān)系，即特定語(yǔ)句、操作、參數(shù)之間的對(duì)應(yīng)，其中重復(fù)對(duì)象集的確定是通過(guò)判斷抽象語(yǔ)法樹(shù)上不同操作節(jié)點(diǎn)是否具有相同的輸入變量.在此基礎(chǔ)上，利用3.1節(jié)描述的代碼元素與Petri網(wǎng)元素之間的映射關(guān)系，完成候選代碼到Petri網(wǎng)模型的轉(zhuǎn)換，詳細(xì)步驟見(jiàn)算法1.

① https://neo4j.com/

算法1.Petri網(wǎng)構(gòu)建算法constructPN.

輸入：代碼片段code_Func;

輸出：Petri網(wǎng)PN.

①PN←{P,T,F,W,L};

②P←?,T←?,F←?,W←?,L←?;

/*初始化Petri網(wǎng)*/

③S←parseStatement(code_Func);

/*將代碼片段中的語(yǔ)句序列放入到語(yǔ)句集S中*/

④ whileS≠? do

⑤ 選擇s∈S;

⑥S←S-{s};

⑦T←T∪{s};/*將語(yǔ)句添加到Petri網(wǎng)的變遷集中*/

⑧T_in←parseInputType(s);

/*將語(yǔ)句的輸入數(shù)據(jù)對(duì)象類型放入集合T_in中*/

⑨ whileT_in≠? do

⑩ 選擇t∈T_in;/*選擇集合T_in中1個(gè)輸入類型*/

/*解析語(yǔ)句中該類型輸入數(shù)據(jù)對(duì)象的個(gè)數(shù)*/

/*解析語(yǔ)句中該類型輸出數(shù)據(jù)對(duì)象的個(gè)數(shù)*/

需要指出，行③函數(shù)parseStatement()用以分析并確定代碼操作，包括程序語(yǔ)句以及本文針對(duì)程序代碼中重復(fù)使用對(duì)象設(shè)置的復(fù)制變遷；行⑧函數(shù)parseInputType()和行函數(shù)parseOutputType()用以分析某個(gè)具體操作的輸入對(duì)象和輸出對(duì)象，包括語(yǔ)句操作的輸入類型和輸出類型，以及復(fù)制變遷對(duì)應(yīng)的重復(fù)使用對(duì)象類型；行函數(shù)parseInputNum()和行函數(shù)parseOutputNum()用以分析某個(gè)具體輸入對(duì)象和輸出對(duì)象在其操作語(yǔ)句中的數(shù)量，包括特定語(yǔ)句操作的某個(gè)輸入類型個(gè)數(shù)和輸出類型個(gè)數(shù)，以及特定復(fù)制變遷對(duì)應(yīng)重復(fù)使用對(duì)象類型輸入個(gè)數(shù)和輸出個(gè)數(shù)(對(duì)象重復(fù)使用次數(shù)).

程序代碼所對(duì)應(yīng)的Petri網(wǎng)描述具有明顯的網(wǎng)式結(jié)構(gòu)化特征.為了提高后期代碼匹配效率，本文采用高效的Neo4j①來(lái)存儲(chǔ)程序代碼所對(duì)應(yīng)的Petri網(wǎng)信息.Neo4j具有與Petri網(wǎng)類似的數(shù)據(jù)組織方式和結(jié)構(gòu)，即通過(guò)節(jié)點(diǎn)和邊來(lái)構(gòu)成圖，并提供類似SQL的語(yǔ)言Cypher以方便用戶執(zhí)行查詢、編輯等操作.

例2.圖6中為數(shù)據(jù)庫(kù)連接的Java代碼，該代碼對(duì)應(yīng)Petri網(wǎng)如圖7所示.為了方便描述，將類型標(biāo)記于對(duì)應(yīng)庫(kù)所，語(yǔ)句標(biāo)記于對(duì)應(yīng)變遷，其中Class，String類型庫(kù)所為該代碼片段的起始庫(kù)所，void類型庫(kù)所為終止庫(kù)所，其余類型庫(kù)所為類型轉(zhuǎn)換過(guò)程中的過(guò)渡或中間庫(kù)所.由庫(kù)所指向變遷的輸入弧代表類型庫(kù)所是語(yǔ)句變遷的輸入數(shù)據(jù)對(duì)象，輸入弧權(quán)重代表該類型的輸入數(shù)據(jù)對(duì)象個(gè)數(shù).由變遷指向庫(kù)所的輸出弧代表類型庫(kù)所是語(yǔ)句變遷的輸出數(shù)據(jù)對(duì)象，輸出弧權(quán)重代表該類型的輸出數(shù)據(jù)對(duì)象個(gè)數(shù).此外，每個(gè)重復(fù)對(duì)象存在其相應(yīng)的克隆變遷，由重復(fù)對(duì)象庫(kù)所指向克隆變遷的輸入弧權(quán)重為1，由克隆變遷指向重復(fù)對(duì)象庫(kù)所的輸出弧權(quán)重為對(duì)象重復(fù)使用的次數(shù).比如，在函數(shù)getConnection調(diào)用語(yǔ)句中，輸入數(shù)據(jù)對(duì)象包括3個(gè)類型為String的參數(shù)以及1個(gè)類型為DriverManager的調(diào)用者，因此輸入弧由String庫(kù)所和DriverManager庫(kù)所指向語(yǔ)句變遷，且輸入弧權(quán)重分別為3和1；輸出數(shù)據(jù)對(duì)象是1個(gè)類型為Connection的返回者，因此輸出弧由語(yǔ)句變遷指向Connection庫(kù)所，且輸出弧權(quán)重為1.Connection對(duì)象在程序片段中被重復(fù)使用2次，因此Connection庫(kù)所處存在Cc克隆變遷，且Cc輸入弧權(quán)重為1，輸出弧權(quán)重為2.出于空間的考慮，在圖6中采用函數(shù)名來(lái)表示函數(shù)調(diào)用語(yǔ)句.需要指出，示例中的異常處理及迭代僅作數(shù)據(jù)流分析.

Table 1 Mapping of Program Code Elements to Petri Net Elements

Table 2 Steps of Reachability Graph Generation Algorithm

Table 3 Experimental Query Test Set

Table 4 Experimental Results

try{Class.forName(dbClass);

Connectionconnection=DriverManager.getConnection(dbUrl,username,password);

Statementstatement=connection.createStatement();

ResultSetresultSet=statement.executeQuery(query);

while(resultSet.next()) StringtableName=resultSet.getString(1);

connection.close();}

catch(ClassNotFoundExceptione){e.printStackTrace();}}

Fig. 1 Overview of code search method based on the reachability analysis of Petri Nets

Fig. 2 Code example and its type representation

Fig. 3 Example of graph models in related work

Fig. 4 Formal definition and graphical representation of Petri Net

Fig. 5 Flow chart of Petri Nets construction process

圖6 “Java數(shù)據(jù)庫(kù)連接”代碼示例

Fig. 7 Petri Net based on the example code of Fig.6

Fig. 8 Flow chart of method for matching code based on the reachability analysis of Petri Nets

Fig. 9 Induced Net of Petri Net in Fig. 7

Fig. 10 P@5 of each question under different methods

Fig. 11 P@10 of each question under different methods

Fig. 12 Trend diagram of Petri Nets construction time and code scale

Fig. 13 Influence of cloned transition on search precision

Fig. 14 Influence of reachability graph pruning on search time

4 基于Petri網(wǎng)可達(dá)分析的代碼匹配方法

本節(jié)引入一種基于Petri網(wǎng)可達(dá)分析的代碼匹配方法.該方法根據(jù)用戶提供的輸入數(shù)據(jù)對(duì)象個(gè)數(shù)、類型信息及期望輸出數(shù)據(jù)對(duì)象類型，從候選代碼所對(duì)應(yīng)Petri網(wǎng)模型中搜索存在功能行為滿足將輸入類型轉(zhuǎn)換為輸出類型的代碼片段.整個(gè)過(guò)程分為3個(gè)階段，如圖8所示.首先，在各個(gè)候選代碼Petri網(wǎng)中，根據(jù)輸入、輸出數(shù)據(jù)對(duì)象信息在候選Petri網(wǎng)中確定初始標(biāo)識(shí)M0和目標(biāo)標(biāo)識(shí)M*；然后基于初始標(biāo)識(shí)M0，對(duì)Petri網(wǎng)進(jìn)行可達(dá)分析，生成反映標(biāo)識(shí)轉(zhuǎn)換的可達(dá)圖；最后通過(guò)分析候選Petri網(wǎng)可達(dá)圖中是否存在目標(biāo)標(biāo)識(shí)M*來(lái)判斷Petri網(wǎng)對(duì)應(yīng)的程序代碼是否為用戶所期待代碼片段.

4.1 確定初始標(biāo)識(shí)與目標(biāo)標(biāo)識(shí)

為了分析Petri網(wǎng)的可達(dá)性，首先需借助用戶提供的輸入、輸出數(shù)據(jù)對(duì)象信息確定Petri網(wǎng)PN=(P,T,F,L,W)的初始標(biāo)識(shí)M0和目標(biāo)標(biāo)識(shí)M*.

定義7.查詢類型對(duì).查詢類型對(duì)為二元組T=(I,o)，其中I代表輸入數(shù)據(jù)對(duì)象的數(shù)據(jù)類型集，o代表輸出數(shù)據(jù)對(duì)象的數(shù)據(jù)類型.

初始標(biāo)識(shí)是指T中輸入類型在Petri網(wǎng)對(duì)應(yīng)庫(kù)所的等量令牌數(shù)，用來(lái)表示需要消耗的數(shù)據(jù)對(duì)象資源.

定義8.初始標(biāo)識(shí).設(shè)在查詢類型對(duì)T中，類型為i∈I的輸入數(shù)據(jù)對(duì)象個(gè)數(shù)為n，如果在Petri網(wǎng)中存在庫(kù)所p∈P的標(biāo)記為i，則M0[p]=n，M0[void]=1，對(duì)于其他類型p′∈P，M0[p′]=0.

考慮到T中通常不包含void輸入類型，為了保證無(wú)明顯輸入類型程序語(yǔ)句的匹配過(guò)程不受影響，因此設(shè)置void類型庫(kù)所的令牌數(shù)為1.目標(biāo)標(biāo)識(shí)是指T中輸出類型在Petri網(wǎng)對(duì)應(yīng)庫(kù)所中的等量令牌數(shù)，用來(lái)表示需要生成的數(shù)據(jù)對(duì)象資源.

定義9.目標(biāo)標(biāo)識(shí).對(duì)于查詢類型對(duì)T中輸出數(shù)據(jù)對(duì)象o，如果在Petri網(wǎng)中存在庫(kù)所p∈P的標(biāo)記為o，則M*[p]=1，M*[void]≥0，對(duì)于其他類型p′∈P，M*[p′]=0.

void庫(kù)所令牌數(shù)可能大于0的原因?yàn)椋翰糠执a包含1個(gè)或多個(gè)無(wú)明顯輸出類型的語(yǔ)句，導(dǎo)致生成1個(gè)或多個(gè)void令牌；部分代碼僅包含明顯輸入類型的語(yǔ)句，導(dǎo)致初始標(biāo)識(shí)void庫(kù)所中的令牌沒(méi)有被消耗.

4.2 Petri網(wǎng)可達(dá)圖生成與剪枝

為了判斷Petri網(wǎng)中是否存在由初始標(biāo)識(shí)可達(dá)的目標(biāo)標(biāo)識(shí)，需對(duì)Petri網(wǎng)進(jìn)行可達(dá)分析，生成所有標(biāo)識(shí)間可達(dá)關(guān)系圖.對(duì)于較為復(fù)雜的Petri網(wǎng)，為了提高分析效率，還需進(jìn)行可達(dá)圖修剪，即去除不影響分析結(jié)論的多余庫(kù)所或變遷.

4.2.1 可達(dá)圖的生成

可達(dá)性分析是研究Petri網(wǎng)動(dòng)態(tài)行為的重要手段[22].對(duì)已確定初始、目標(biāo)標(biāo)識(shí)的Petri網(wǎng)PN，其可達(dá)圖生成過(guò)程如算法2所示.

算法2.Petri網(wǎng)可達(dá)圖生成算法reachGraph.

輸入：Petri網(wǎng)PN、初始標(biāo)識(shí)M0、輸出類型p*;

輸出：PN的可達(dá)圖GR*.

①GR*←(N,E);

②N←{M0};E←?;/*初始化可達(dá)圖*/

③Φ←{M0};

④ whileΦ≠? do/*當(dāng)未處理標(biāo)識(shí)集不為空時(shí)*/

⑤ 選擇M∈Φ;/*選擇未處理標(biāo)識(shí)集中的1個(gè)標(biāo)識(shí)*/

⑥Φ←Φ-{M};

⑦ for所有T∈enabled(M) do/*狀態(tài)標(biāo)識(shí)M下所有使能的變遷T*/

⑧ (M′,p)←fire(M,T);/*計(jì)算M的后繼標(biāo)識(shí)M′以及變遷T的輸出庫(kù)所p*/

⑨ ifpathExists(p,p*,α(PN)) then

/*判斷α(PN)中是否存在p到p*的路徑*/

⑩ Continue；

例3.以圖4為例，假設(shè)輸出類型為p4，表2說(shuō)明Petri網(wǎng)可達(dá)圖生成算法的執(zhí)行過(guò)程.

4.2.2 可達(dá)圖的修剪

隨著代碼規(guī)模的擴(kuò)大，狀態(tài)空間的組合爆炸將使可達(dá)性分析變得非常困難，基于Petri網(wǎng)的可達(dá)分析的復(fù)雜度呈指數(shù)增加[23].為了應(yīng)對(duì)可能的狀態(tài)爆炸問(wèn)題或提高分析效率，本文通過(guò)分析Petri網(wǎng)對(duì)應(yīng)有向網(wǎng)中的路徑對(duì)可達(dá)圖GR(PN)進(jìn)行剪枝，使可達(dá)圖GR(PN)得到化簡(jiǎn)，同時(shí)保證化簡(jiǎn)后的可達(dá)圖GR*也足以反映給定輸入/輸出類型轉(zhuǎn)換過(guò)程.

如果在PN中沒(méi)有從某類型庫(kù)所到輸出類型庫(kù)所的路徑，則不需分析從該類型庫(kù)所到輸出類型庫(kù)所的路徑是否可達(dá)，即沒(méi)有必要對(duì)該類型庫(kù)所分配非零數(shù)量的令牌.本文基于這個(gè)觀察來(lái)修剪GR(PN)冗余節(jié)點(diǎn).為了分析PN類型庫(kù)所間的路徑存在的問(wèn)題，本文定義誘發(fā)網(wǎng)α(PN)的概念，α(PN)忽略變遷及有向弧權(quán)重，僅用無(wú)權(quán)有向弧表示類型庫(kù)所間可達(dá)關(guān)系.

定義10.誘發(fā)網(wǎng).誘發(fā)網(wǎng)α(PN)是由Petri網(wǎng)PN=(P,T,F,L,W)誘發(fā)的表示為(V,E′)的有向網(wǎng)，其中V=P，(P,P′)∈E′，并且存在變遷t∈T使得(P,t)∈E，(t,P′)∈E.

例4.圖7中Petri網(wǎng)的誘發(fā)網(wǎng)α(PN)如圖9所示.出于空間考慮，長(zhǎng)單詞用縮寫表示.

命題1.令α(PN)為Petri網(wǎng)PN的誘發(fā)網(wǎng)，設(shè)α(PN)中沒(méi)有從某庫(kù)所p到目標(biāo)庫(kù)所p*的路徑，設(shè)M為PN中庫(kù)所p內(nèi)令牌數(shù)大于0的標(biāo)識(shí)，M*為庫(kù)所p*內(nèi)令牌數(shù)為1的目標(biāo)標(biāo)識(shí)，則GR(PN)中沒(méi)有從M到M*的路徑.

定理1.約簡(jiǎn)模型中標(biāo)識(shí)可達(dá)性是一致的.

證明.設(shè)PN的化簡(jiǎn)前可達(dá)圖GR(PN)=(SM,SL)，化簡(jiǎn)后可達(dá)圖GR*(PN)=(SM*,SL*)，其中SM和SM*表示可達(dá)標(biāo)識(shí)，SL和SL*表示連接相鄰標(biāo)識(shí)的有向邊.GR*(PN)滿足：

1) ?M∈SM，其中M[P]>0，P={p1,p2,…,pn}，若?p∈P，α(PN)中都存在p到p*的路徑，則M∈SM*.

2) ?M,M′∈SM，M,M′∈SM*，若?l(M,t,M′)∈SL，則l(M,t,M′)∈SL*.

上述描述表明GR*(PN)保留GR(PN)中所有可能到達(dá)目標(biāo)標(biāo)識(shí)M*(M*[p*]=1)的標(biāo)識(shí)M及M→M*的路徑，即約簡(jiǎn)模型中標(biāo)識(shí)可達(dá)性是一致的.

證畢.

4.3 基于可達(dá)圖的代碼匹配算法

Petri網(wǎng)可達(dá)圖反映了Petri網(wǎng)在初始標(biāo)識(shí)M0下可達(dá)的標(biāo)識(shí)空間.因此對(duì)于生成的可達(dá)圖GR*，若GR*存在目標(biāo)標(biāo)識(shí)M*，則Petri網(wǎng)上存在從M0到M*的可達(dá)路徑，表明該P(yáng)etri網(wǎng)匹配.算法3描述了Petri網(wǎng)匹配的整個(gè)過(guò)程：首先初始化匹配Petri網(wǎng)集合、搜索次數(shù)(行①②)；其次，依次獲取Petri網(wǎng)進(jìn)行分析，生成其對(duì)應(yīng)的可達(dá)圖(行③～⑤)；然后，判斷可達(dá)圖是否存在目標(biāo)標(biāo)識(shí)，若存在，則將對(duì)應(yīng)Petri網(wǎng)添加到匹配Petri網(wǎng)集(行⑥～⑧)；最后，當(dāng)所有Petri網(wǎng)分析完畢，則循環(huán)結(jié)束，返回匹配Petri網(wǎng)集合(行⑨⑩).對(duì)于返回的匹配Petri網(wǎng)集，其對(duì)應(yīng)的代碼片段存在將輸入類型轉(zhuǎn)換為輸出類型的語(yǔ)句序列，這些代碼片段匹配，將其納入候選代碼片段集合.

算法3.Petri網(wǎng)匹配算法matchPN.

輸入：待搜索的Petri網(wǎng)庫(kù)PN_database、輸出類型p*、初始標(biāo)識(shí)M0、目標(biāo)標(biāo)識(shí)M*、搜索最大次數(shù)(Petri網(wǎng)個(gè)數(shù))n_max;

輸出：匹配Petri網(wǎng)集合Ok_PNs.

①Ok_PNs←?;

②searchCount←0;

③ while(one_PN←nextFile(PN_database) andsearchCount≤n_max) do /*獲取Petri網(wǎng)*/

④searchCount←searchCount+1;

⑤GR*←reachGraph(one_PN,M0,p*);

/*生成Petri網(wǎng)可達(dá)圖*/

⑦Ok_PNs←Ok_PNs∪{one_PN};

/*若存在，Petri網(wǎng)匹配成功，添加到匹配Petri網(wǎng)集*/

⑧ end if

⑨ end while

⑩ returnOk_PNs.

4.4 候選代碼排序

對(duì)于候選代碼片段集合，本文使用2種代碼質(zhì)量評(píng)價(jià)指標(biāo)對(duì)代碼片段進(jìn)行排序，幫助程序員快速識(shí)別所需的代碼片段.

基于程序員經(jīng)常傾向于使用較短序列而不是較長(zhǎng)序列來(lái)實(shí)現(xiàn)其任務(wù)的現(xiàn)象[9-10,24]，本文采用序列長(zhǎng)度作為評(píng)價(jià)代碼質(zhì)量的指標(biāo)，越短的序列優(yōu)先級(jí)越高.本文將代碼片段中功能序列的長(zhǎng)度作為序列長(zhǎng)度，功能序列指將輸入類型轉(zhuǎn)換為輸出類型的方法序列.

本文還采用代碼復(fù)用率作為評(píng)價(jià)代碼質(zhì)量的指標(biāo).在許多代碼搜索工作如PARSEWeb[10],DERECS[25]中都用到了復(fù)用率對(duì)結(jié)果進(jìn)行排序，其基本考慮是代碼的復(fù)用率(代碼片段在軟件開(kāi)發(fā)過(guò)程中重復(fù)使用的頻率)越高，參考價(jià)值越高，但計(jì)算方式各有差異.本文考慮相似代碼片段在候選代碼庫(kù)中出現(xiàn)的頻率.采用已有代碼克隆檢測(cè)方法CCFinderSW[26]來(lái)識(shí)別候選代碼庫(kù)中的相似代碼，并將相似代碼聚成一類，計(jì)算每一類集合中代碼段個(gè)數(shù)作為此類代碼段的復(fù)用率.CCFinderSW的源代碼可以在GitHub上找到，本文用Java語(yǔ)言重新實(shí)現(xiàn)了此算法.

5 實(shí)驗(yàn)以及分析

為了驗(yàn)證本文所提出方法的有效性，本文進(jìn)行了2個(gè)實(shí)驗(yàn).在第1個(gè)實(shí)驗(yàn)中，我們驗(yàn)證了本方法的有效性，即能否解決多種形式的類型轉(zhuǎn)換問(wèn)題，并與其他檢索方法的準(zhǔn)確率進(jìn)行對(duì)比；第2個(gè)實(shí)驗(yàn)則討論了本方法中涉及的技術(shù)點(diǎn)對(duì)搜索效率的影響.

5.1 實(shí)驗(yàn)建立

5.1.1 實(shí)驗(yàn)準(zhǔn)備

為了確保所收集源代碼的真實(shí)性和可靠性，本文選擇從軟件項(xiàng)目托管平臺(tái)GitHub上收集源代碼.根據(jù)托管項(xiàng)目的Most Stars排序，本文選擇了200個(gè)用戶評(píng)價(jià)較高的Java語(yǔ)言開(kāi)源項(xiàng)目，將項(xiàng)目以函數(shù)為粒度進(jìn)行切分，得到函數(shù)級(jí)代碼片段189 442個(gè).

為了構(gòu)建客觀的用戶真實(shí)查詢測(cè)試集，我們從Stack Overflow中找到帶有Java標(biāo)簽的問(wèn)答對(duì)，并選取票數(shù)為正、答案中含有代碼片段的熱門的20個(gè)問(wèn)題，同時(shí)提取答案代碼示例中的輸入/輸出類型作為代碼搜索工具的查詢輸入如表3所示.需要指出，我們將數(shù)組視為特殊的數(shù)據(jù)對(duì)象，其類型為元素類型.

5.1.2 評(píng)估指標(biāo)

為了評(píng)價(jià)代碼搜索的準(zhǔn)確度或效率，本文采用P@n[27-28]，MAP(mean average precision)[7,29]，MRR(mean reciprocal rank)[7]作為評(píng)價(jià)指標(biāo).P@n表示返回前n個(gè)結(jié)果的準(zhǔn)確率，計(jì)算公式為

(1)

其中，n表示返回的前n個(gè)結(jié)果，relk表示第k個(gè)結(jié)果的相關(guān)性，如果相關(guān)，relk=1，否則relk=0.MAP表示平均準(zhǔn)確率，該指標(biāo)對(duì)出現(xiàn)在列表中較高位置的相關(guān)結(jié)果給予較高的權(quán)重，計(jì)算公式為

(2)

(3)

其中，AveP表示單個(gè)查詢的準(zhǔn)確率，num表示相關(guān)結(jié)果的個(gè)數(shù)，P(k)表示對(duì)于查詢Qi相關(guān)結(jié)果列表中排名為k的權(quán)重，例如結(jié)果列表共有2個(gè)相關(guān)代碼段位于排名1和3，則P(1)=1，P(3)=0.67.MRR表示第1個(gè)相關(guān)結(jié)果排名的倒數(shù)，計(jì)算公式為

(4)

其中，ranki表示對(duì)于查詢Qi第1個(gè)相關(guān)結(jié)果的排名.

5.1.3 比較對(duì)象

為了檢測(cè)搜索方法的有效性，我們與2種典型的代碼檢索方法進(jìn)行對(duì)比.第1種為基于文本匹配的方法.該方法源于大多源代碼搜索引擎，通過(guò)相似度計(jì)算模型[30]計(jì)算查詢與代碼片段的文本相似度.第2種為基于類型匹配的方法.該檢索方法只考慮有向圖中是否存在一條路徑以輸入/輸出類型作為起點(diǎn)和終點(diǎn)節(jié)點(diǎn)，不考慮路徑的可達(dá)問(wèn)題.

5.2 實(shí)驗(yàn)結(jié)果及分析

5.2.1 搜索結(jié)果對(duì)比分析

針對(duì)表3中的20個(gè)查詢問(wèn)題，本文對(duì)比了5.1.3節(jié)中2種方法檢索結(jié)果的P@5，P@10評(píng)價(jià)指標(biāo)，如圖10和圖11所示.

從圖10和圖11中可以看出，相比于基于輸入/輸出值的方法，本方法適用于更普遍的代碼搜索問(wèn)題，例如較好地解決了無(wú)法用具體值描述的查詢4，6，7等編程任務(wù).同時(shí)，本方法還能夠有效地解決多種形式的類型轉(zhuǎn)換問(wèn)題，在已有類型匹配工作已解決的單個(gè)輸入類型轉(zhuǎn)換的基礎(chǔ)上，解決了多個(gè)輸入類型轉(zhuǎn)換.為了能夠更直觀地驗(yàn)證本方法的有效性，針對(duì)單個(gè)輸入/輸出類型的查詢，對(duì)比了2種方法檢索結(jié)果的MAP和MRR這2種評(píng)價(jià)指標(biāo)，實(shí)驗(yàn)結(jié)果如表4所示：

從表4中可以看出，本方法的搜索準(zhǔn)確率要優(yōu)于基于文本匹配和已有類型匹配的方法.基于文本匹配的方法獲得了最低的準(zhǔn)確率，表明僅利用文本相似性解決代碼匹配問(wèn)題，而忽略代碼的語(yǔ)義信息，難以獲得理想的結(jié)果.本文結(jié)合靜態(tài)分析技術(shù)挖掘代碼的行為過(guò)程，并采用Petri網(wǎng)將其整合起來(lái)，添加到搜索中，使檢索的準(zhǔn)確性得到了顯著提升.已有類型匹配的方法在搜索過(guò)程中只是遍歷路徑的存在問(wèn)題，而本文在此基礎(chǔ)上將參數(shù)類型個(gè)數(shù)作為新的約束條件，利用Petri網(wǎng)可達(dá)分析挖掘更全面的代碼行為，從而匹配到更多相關(guān)的代碼片段.

5.2.2 Petri網(wǎng)構(gòu)造過(guò)程分析

設(shè)單個(gè)代碼片段中操作數(shù)為m，每個(gè)操作的輸入數(shù)據(jù)對(duì)象類型數(shù)為n，則構(gòu)建代碼片段Petri網(wǎng)的時(shí)間復(fù)雜度為O(m×n+m).本文設(shè)計(jì)實(shí)驗(yàn)分別從參數(shù)、語(yǔ)句、函數(shù)調(diào)用數(shù)目及重復(fù)使用對(duì)象集4個(gè)方面對(duì)Petri網(wǎng)的構(gòu)造時(shí)長(zhǎng)進(jìn)行考察，如圖12所示.實(shí)驗(yàn)結(jié)果表明，Petri網(wǎng)的構(gòu)造時(shí)間與語(yǔ)句數(shù)量、函數(shù)調(diào)用數(shù)量及重復(fù)使用對(duì)象數(shù)量均成正比關(guān)系，與參數(shù)數(shù)量大約為正比關(guān)系(除參數(shù)為0的情況).原因分析為：由時(shí)間復(fù)雜度可知，構(gòu)造時(shí)長(zhǎng)取決于代碼操作與輸入數(shù)據(jù)對(duì)象類型，且構(gòu)造時(shí)長(zhǎng)隨二者數(shù)量的增加而增加，其中代碼操作涉及代碼語(yǔ)句及本文針對(duì)重復(fù)對(duì)象集設(shè)置的相應(yīng)復(fù)制變遷；從語(yǔ)句內(nèi)部分析，運(yùn)算符操作通常對(duì)同類型數(shù)據(jù)對(duì)象加工，而函數(shù)調(diào)用往往需要處理多個(gè)不同類型的輸入數(shù)據(jù)對(duì)象，因此代碼中函數(shù)調(diào)用數(shù)量越多，涉及輸入數(shù)據(jù)對(duì)象類型越復(fù)雜，導(dǎo)致構(gòu)造時(shí)長(zhǎng)增加；此外，在一般情況下參數(shù)數(shù)量與語(yǔ)句輸入數(shù)據(jù)對(duì)象存在一定關(guān)聯(lián)，參數(shù)數(shù)量越多，語(yǔ)句輸入數(shù)據(jù)對(duì)象越多，但當(dāng)參數(shù)為0時(shí)，輸入數(shù)據(jù)對(duì)象與參數(shù)無(wú)直接關(guān)系，比如圖6代碼示例.

5.2.3 技術(shù)點(diǎn)分析

1) 復(fù)制變遷

為了表明在Petri網(wǎng)構(gòu)建過(guò)程中增加復(fù)制變遷的重要性，本文針對(duì)表3的查詢集進(jìn)行檢索實(shí)驗(yàn)，如圖13所示.從圖13中可知，復(fù)制變遷對(duì)提高搜索準(zhǔn)確率起關(guān)鍵作用.原因分析為：傳統(tǒng)Petri網(wǎng)模型難以蘊(yùn)含程序片段中數(shù)據(jù)對(duì)象的重復(fù)使用過(guò)程，導(dǎo)致Petri網(wǎng)可達(dá)分析過(guò)程中重復(fù)使用對(duì)象的資源數(shù)不夠，對(duì)應(yīng)操作變遷無(wú)法觸發(fā)，可達(dá)圖生成不完整，進(jìn)而影響搜索匹配結(jié)果.

2) 可達(dá)圖修剪

圖14說(shuō)明了分析Petri網(wǎng)可達(dá)時(shí)設(shè)置可達(dá)圖修剪的必要性.總的來(lái)看，在標(biāo)準(zhǔn)可達(dá)圖生成算法的基礎(chǔ)上，增加可達(dá)圖修剪的操作能夠明顯減少搜索時(shí)間.

6 總結(jié)及未來(lái)工作

為了幫助程序員更好地檢索以及復(fù)用已有代碼，本文提出了一種基于Petri網(wǎng)可達(dá)分析的代碼搜索方法.該方法基于已有代碼庫(kù)，結(jié)合靜態(tài)分析技術(shù)分析、提取代碼元素，構(gòu)建代碼的Petri網(wǎng)模型；根據(jù)給定輸入/輸出類型，通過(guò)Petri網(wǎng)可達(dá)分析匹配將輸入類型轉(zhuǎn)換為輸出類型的代碼片段，并采用序列長(zhǎng)度和復(fù)用率代碼質(zhì)量評(píng)價(jià)指標(biāo)對(duì)結(jié)果進(jìn)行排序.使用真實(shí)的查詢測(cè)試集，驗(yàn)證了本文方法的有效性.

在未來(lái)的工作中，我們將針對(duì)搜索結(jié)果的多種情況，完善該方法.例如對(duì)于返回代碼段過(guò)少的問(wèn)題，采取對(duì)查詢進(jìn)行一定程度的放松與收縮(如父類、子類替換)；對(duì)于返回代碼段過(guò)多的問(wèn)題，采用測(cè)試用例(具體的輸入/輸出值)進(jìn)一步篩選代碼段.此外，我們將進(jìn)一步全方面探討代碼Petri網(wǎng)模型的可覆蓋性、安全性、結(jié)構(gòu)有界性等行為性質(zhì)，增強(qiáng)代碼Petri網(wǎng)模型的完備性.

作者貢獻(xiàn)聲明：丁雪兒負(fù)責(zé)論文思路的提出、論文寫作、論文算法和論文實(shí)驗(yàn)；鈕俊負(fù)責(zé)論文思路的把關(guān)、論文寫作和實(shí)驗(yàn)監(jiān)督；張開(kāi)樂(lè)負(fù)責(zé)數(shù)據(jù)收集和論文寫作完善；毛欣怡負(fù)責(zé)結(jié)果驗(yàn)證和論文寫作完善.