語句包裹模式的識別和分類

于永勝 楊春花

摘要：軟件演化過程中會產(chǎn)生大量變更代碼，對變更代碼的識別有利于變更理解。其中普遍存在的把一個語句或語句序列移動到一個或多個不同的語法實體中的變更行為，對于這種語句包裹模式的識別和分類，提出了基于代碼變更塊和抽象語法樹的語句包裹模式識別分類算法。首先從變更前后版本2個文件中篩選出代碼變更塊，根據(jù)語句包裹模式的特征找到候選代碼變更塊，再建立抽象語法樹，通過語法分析找到代碼變更塊中存在的語句包裹模式并對其進行分類。該算法在4個開源項目中進行了實驗驗證，實驗結(jié)果表明該算法對語句包裹模式的識別具有較高的準(zhǔn)確率。

關(guān)鍵詞： 語句包裹模式; 軟件演化; 抽象語法樹; 代碼變更塊

【Abstract】 During the software evolution process， a large number of change codes will be generated， and the identification of the change code is conducive to change understanding. Among them is the universal behavior of changing a statement or a sequence of statement into one or more different grammatical entities. For the recognition and classification of such statement encapsulation patterns， the paper proposes a statement encapsulation pattern recognition classification algorithm based on code change blocks and abstract syntax trees. First， the code change block is filtered from the two files before and after the change， and the candidate code change block is found according to the characteristics of the statement encapsulation pattern， then an abstract syntax tree is established. Finally，syntactic analysis is used to find and classify the statement encapsulation patterns existing in the code change block. The algorithm has been experimentally verified in four open source projects， and the experimental results show that the algorithm has a high accuracy rate for statement encapsulation pattern recognition.

【Key words】 ?statement encapsulation pattern; software evolution; abstract syntax tree; code change block

0 引 言

軟件版本控制系統(tǒng)記錄著軟件開發(fā)過程中的每個細節(jié)以及不同時期的不同版本，軟件版本控制系統(tǒng)每天都會產(chǎn)生大量的變更代碼，理解變更代碼可以使軟件日常維護和功能添加變得更加容易。理解軟件變更已經(jīng)成為軟件開發(fā)人員日常開發(fā)和維護的基本要求。

在大量軟件變更代碼中存在對軟件的重構(gòu)、錯誤修復(fù)以及功能添加。重構(gòu)是在不改變軟件外在行為的前提下，改進軟件的內(nèi)部結(jié)構(gòu)，使軟件更易于維護和功能的添加。Fowler[1]在其著作中詳細介紹了重構(gòu)模型，其核心是一個全面的重構(gòu)目錄。變更代碼中也存在對代碼的錯誤修復(fù)。關(guān)于錯誤報告方面的研究有：Zhang等人[2]對Bugzilla上的錯誤報告進行了實證研究，并指出了進行錯誤報告分析時可能存在的問題;童燕翔[3]去除了bug report中的非修正性報告并提出了自動化缺陷定位方法;關(guān)于錯誤修復(fù)的識別方面的研究有：Eshkevari等人[4]提出了沿4個正交維度的標(biāo)識符重命名分類方法，并實現(xiàn)了標(biāo)識符重命名的識別和分類;Kawrykow等人[5]開發(fā)了一種工具支持的技術(shù)，用于檢測軟件系統(tǒng)的修訂歷史記錄中不必要的代碼修改;Kim等人[6]通過分析錯誤修復(fù)的歷史記錄開發(fā)了錯誤修復(fù)存儲器，并提出了一種使用錯誤修復(fù)存儲器的錯誤發(fā)現(xiàn)算法;關(guān)于錯誤預(yù)測方面的研究有： 原子等人[7]提出了語句級的缺陷預(yù)測方法，揭示了變更易于引入缺陷的因素;劉望舒等人[8]針對挖掘軟件歷史倉庫過程中程序模塊類型標(biāo)記和軟件度量時產(chǎn)生的噪聲，提出一種可容忍噪聲的特征選擇框架FECS。

軟件變更代碼中摻雜著大量的對軟件的重構(gòu)、錯誤修復(fù)和功能添加的代碼，對軟件變更代碼中變更模式的提取有利于對軟件變更的理解。在對軟件變更進行研究后，接著又研究了把一個語句或語句序列移動到一個或多個不同的語法實體中的語句包裹模式。Pan等人[9]在其著作中從7個開源項目的配置管理存儲庫中，使用錯誤修復(fù)程序更改所涉及的語法組件和源代碼上下文定義了27個可自動提取的錯誤修復(fù)模式。但是其著作對錯誤修復(fù)模式的研究并沒有完全涵蓋語句包裹模式所包含的變更類型，因此還需要對語句包裹模式做進一步的研究。

1 語句包裹模式的識別和分類

1.1 代碼變更塊

代碼變更塊（hunk）是由代碼變更前后版本之間的變更代碼構(gòu)成的，本文通過基于文本的方法獲取代碼變更塊，圖1中的代碼變更塊取自數(shù)據(jù)倉庫jEdit中KeymapImpl.java文件的一次提交。在圖1所示的代碼變更塊中，左邊頁碼從第106～107行前面帶減號的代碼是代碼變更過程中從原文件中刪除的代碼，右邊頁碼從第106～111行前面帶加號的代碼是代碼變更后新版本文件中增加的代碼。

1.2 抽象語法樹

抽象語法樹抽象地表示了源代碼的語法結(jié)構(gòu)，抽象語法樹通過將源代碼中的每一種結(jié)構(gòu)用節(jié)點表示來表現(xiàn)編程語言的語法結(jié)構(gòu)，而真實語法中的每一個細節(jié)并沒有包含在抽象語法樹中，比如嵌套的括號在抽象語法樹中就沒有以節(jié)點的形式表現(xiàn)出來，對于語句包裹模式的研究需要對代碼變更文件的抽象語法樹進行分析。

1.3 語句包裹模式的識別和分類

1.3.1 語句包裹模式

語句包裹模式所表示的代碼變更行為是把一個語句或語句序列移動到一個或多個不同的語法實體中，這個語法實體是一個結(jié)構(gòu)化的語句，語法實體包括If、Try、For、Switch、Synchronized、While、Labeled和Do。語句包裹模式所表示的代碼變更行為是將一個語句或語句序列移動到一個或多個結(jié)構(gòu)化語句中，這種結(jié)構(gòu)化語句是這個語句或語句序列在被執(zhí)行時需要滿足的條件，是對代碼原文件的錯誤修復(fù)。

在圖2所示的語句包裹模式hunk實例取自數(shù)據(jù)倉庫jEdit中文件Gutter.java的一次提交中，圖2中左邊頁碼第128行是從原文件中刪除的代碼，右側(cè)頁碼從128～129行是代碼變更過程中增加的代碼，第128行刪除的代碼和第129行增加的代碼是非常相似的，圖2中將一行代碼移動到了一個If語法實體中，發(fā)生了語句包裹。對于一個語句或語句序列移動到Try、For、Switch、Synchronized、While、Labeled和Do這七種語法實體中的變更行為也都屬于語句包裹模式。

在圖3所示的語句包裹模式的hunk實例取自數(shù)據(jù)倉庫jEdit中文件EditPane.java的一次提交，第1236行刪除的代碼和第1214行增加的代碼是非常相似的，就是將第1236行代碼從一個If語法實體中移動了出來，發(fā)生了逆向的語句包裹，屬于語句包裹模式。

1.3.2 語句包裹模式的識別和分類

假設(shè)存在ha和hd分別為hunk中增加的代碼和刪除的代碼，la和ld分別為hunk中增加代碼和刪除代碼的相似部分，則pr和pl分別為la和ld的所有父節(jié)點，cr和cl分別為la和ld在hunk內(nèi)的所有父節(jié)點，mr和ml分別是la和ld父節(jié)點中的第一個方法節(jié)點，當(dāng)這次變更屬于語句包裹模式時，則需要滿足以下條件：

（1）語句包裹模式的候選hunk中需要存在語句或語句序列移動到一個或多個語法實體中，這些移動的語句或語句序列是相似的，所以hunk中需要存在相似部分。

（2）hunk中相似部分的父節(jié)點中第一個方法節(jié)點mr和ml的方法名是相同的。對于la和ld在hunk內(nèi)的父節(jié)點cr和cl，需要滿足一個為空集且另一個不為空集的條件，且la和ld的所有父節(jié)點pr和pl不能完全相同。

判斷此次變更屬于語句包裹模式后，當(dāng)cr不為空且cl為空時，可以判斷變更屬于正向的語句包裹模式，并根據(jù)語法實體的種類對語句包裹模式進行分類，這里的語法實體就是cr的第一個節(jié)點。當(dāng)cl不為空且cr為空時，可以判斷為逆向的語句包裹模式，將cl的第一個節(jié)點作為語法實體，并根據(jù)這里的語法實體對語句包裹模式進行分類。

1.3.3 根據(jù)代碼相似度識別hunk中的代碼移動

在圖2語句包裹模式的候選hunk中，從原版本文件中刪除的代碼是左側(cè)頁碼的第128行，代碼變更后增加的代碼是右側(cè)頁碼的第128～129行，原版本文件中第128行代碼在代碼變更后移動到了新版本文件的第129行，這些移動的語句或語句序列具有很高的相似度，因此要識別這樣的代碼移動需要對變更代碼進行相似度識別。

1.3.4 通過抽象語法樹識別語句包裹模式

從語句包裹模式候選hunk中找到移動的語句或語句序列后，需要確定hunk相似部分la和ld的父節(jié)點pr和pl中的第一個方法節(jié)點mr和ml的方法名需要相同，還需要確定hunk和相似部分之間存在一個或多個語法實體，也就是la和ld在hunk內(nèi)的父節(jié)點cr和cl需要一個為空集一個不為空集，la和ld的所有父節(jié)點pr和pl不能完全相同。

首先獲取la和ld的行范圍ra和rd，獲取hunk增加代碼和刪除代碼ha和hd的行范圍ka和kd，遍歷代碼變更前后版本的兩個文件的語法樹，找到行范圍分別包含ra和rd的父節(jié)點pr和pl，找到行范圍位于ra和ka之間的父節(jié)點cr，找到行范圍位于rd和kd之間的父節(jié)點cl，分別從pr和pl中找到la和ld的第一個方法節(jié)點mr和ml，判斷mr和ml是否是同名函數(shù)節(jié)點，判斷cr和cl是否一個為空集、另一個不為空集，判斷pr和pl是否不完全相同，如果都滿足，則該代碼變更是語句包裹模式。

1.3.5 語句包裹模式識別和分類算法

本算法輸入的是變更前后2個版本的文件filel和filer，輸出是語句序列移動到的語法實體En和該語法實體的分支Eb，En=，en是filel和filer文件中的一個語句包裹模式變更中的語句或語句序列移動到的語法實體，Eb=，eb是語句或語句序列移動到語法實體en中后所位于的en的分支。

算法1 語句包裹模式識別算法

輸入：代碼變更前后版本兩個文件filel和filer

輸出：filel和filer文件中每一個語句包裹模式變更中語法實體en的集合En和語句移動到語法實體后所在的分支eb的集合Eb

1（Ha，Hd）←getHunk（filel， filer）

2 （La，Ld）←getSimilarPart（Ha，Hd）

3 Ka←getHunkRange（Ha）

4 Kd←getHunkRange（Hd）

5 tl←generateAST（filel）

6 tr←generateAST（filer）

7 Ra←getSimilarPartRange（La）

8 Rd←getSimilarPartRange（Ld）

9 （Pr，Cr，Br）←ergodicAST（Ka，Ra，tr）

10 （Pl，Cl，Bl）←ergodicAST（Kd，Rd，tl）

11 for each cl∈Cl， cr∈Cr， pl∈Pl， pr∈Pr， bl∈Bl， br∈Br

12 ml←getMethodNode（pl）

13 mr←getMethodNode（pr）

14 if（isSimilarMethod（ml，mr））

15 ?if （（cl=）&&（cr≠）‖（（cl≠）&&（cr=）

16 ? if（pl≠pr）

17 [WB]if（（cl≠）&&（cr=））

18en←identifyEncapsulateNode（cl）

19eb←identifyBranch（bl）

20En←en

21Eb←eb

22 [DW]else if （（cl=）&&（cr≠））

23en←identifyEncapsulateNode（cr）

24eb←identifyBranch（br）

25En←en

26Eb←eb

27end if

28 ? end if

29 ?end if

30 ?end if

31 end for

算法第1行生成代碼變更前后版本文件的hunk集Ha和Hd，從hunk集中識別出相似部分的集合La和Ld，第3～4行得到hunk集Ha和Hd的行范圍集合Ka和Kd，第5～6行得到filel和filer的抽象語法樹的根節(jié)點tl和tr，第7～8行得到hunk的相似部分的集合La和Ld的行范圍集合Ra和Rd，第9～10行通過遍歷filer和filel的語法樹得到相似部分的所有父節(jié)點集合Pr和Pl、在hunk內(nèi)的父節(jié)點的集合Cr和Cl以及相似部分在父節(jié)點Pr和Pl中每一個節(jié)點的分支的集合Br和Bl，第11～13行分別找到pr和pl中相似部分的第一個滿足是方法節(jié)點的父節(jié)點，第14行判斷2個方法父節(jié)點是否滿足方法名不相同的條件，第15行判斷相似部分在hunk內(nèi)的父節(jié)點cl和cr是否滿足一個為空集、另一個不為空集的條件，第16～27行判斷相似部分在文件中的所有父節(jié)點pl和pr是否滿足不完全相同的條件。算法的第17～21行中，當(dāng)cl和cr滿足cl不為空集而cr為空集時，將cl中第一個節(jié)點作為語句包裹模式的語法實體存入en中，en存入En，并將該語法實體的相應(yīng)分支bl存入eb中，eb存入Eb。第22～31行中，當(dāng)cl為空集而cr不為空集時，將cr的第一個父節(jié)點作為語句包裹模式的語法實體存入en，en存入En，并將該語法實體的相應(yīng)分支br存入eb中，eb存入Eb。

上述算法中第9～10行使用了函數(shù)ergodicAST，下面是對函數(shù)ergodicAST的描述：函數(shù)ergodicAST的輸入為文件hunk集H的行范圍的集合K，hunk集中相似部分L的行范圍的集合R，以及文件的語法樹的根節(jié)點t。輸出為文件中相似部分集合的所有父節(jié)點的集合P，相似部分在hunk集內(nèi)的父節(jié)點的集合C，以及相似部分在父節(jié)點集合P中每一個節(jié)點的分支的集合B。

算法2 ergodicAST算法

輸入：文件hunk集H的行范圍K，相似部分集L的行范圍R以及文件的語法樹的根節(jié)點t

輸出：文件hunk集相似部分的父節(jié)點集合P，相似部分在hunk集內(nèi)的父節(jié)點集合C，相似部分在父節(jié)點集合P中每個節(jié)點的分支的集合B

1 for each k∈K，r∈R

2 N←t

3 while（N≠）

4 ?n←takeOutFirstNode（N）

5 ?p←n

6 ?rz←getNodeRange（n）

7 ?if（rrz）&&（rzk）

8 ? [WB]c←n

9 ?end if

10 Bz←getAllBranch（n）

11 ?for each bz∈Bz

12 ?[DW]Nt←getAllNode（bz）

13 ?rb←getRange（Nt）

14 ? if（rrb）

15 ? b←bz

16 ? end if

17 ? for each nc∈Nt

18rc←getNodeRange（nc）

19if（rrc）

20N←nc

21end if

22 ? end for

23 ?end for

24 end while

25 P←p

26 C←c

27 B←b

28 end for

算法第1～5行將文件語法樹中相似部分的第一個父節(jié)點存入p中，第6～9行判斷該節(jié)點是否也在hunk內(nèi)，如果在hunk內(nèi)就將其存入c中，第10～16行獲取n節(jié)點的分支集合Bz，并將包含相似部分的分支存入b中，第17～24行遍歷分支內(nèi)的節(jié)點，將包含相似部分的節(jié)點存入N，若N不為空集，則繼續(xù)遍歷文件的語法樹。第25～28行將p、c和b分別存入P、C和B中。

2 算法的實現(xiàn)和驗證

本文實驗使用了Java編程語言、基于文本的差異化分析工具Gnu Diff[10]以及eclipse jdt parser工具。首先使用了基于文本的差異化分析工具Gnu Differ（http：//www.gnu.org/software/diffutils）獲取代碼變更前后版本文件的代碼變更塊hunk，再使用eclipse jdt parser工具分析代碼變更前后版本文件的抽象語法樹。并從4個開源項目中獲取了數(shù)據(jù)集用于實驗研究。

2.1 數(shù)據(jù)獲取

本實驗使用了從4個開源項目中獲取的數(shù)據(jù)集，下面是對本實驗使用的數(shù)據(jù)集的介紹。

（1）[JP4]開源項目jEdit（http：//sourceforge.net/project/jedit），該開源項目是一個跨平臺的文本編輯器。

（2）開源項目eclipseJDTCore（http：//www.eclipse.org/downloads/eclipse-packages/），該開源項目是一個面向Java的集成開發(fā)環(huán)境。

（3）開源項目maven（http：//maven.apache.org/），該開源項目是通過信息描述來管理項目構(gòu)建、報告和文檔的管理工具。

（4）開源項目google-guice（https：//github.com/apress/google-guice），該開源項目是一個輕量級的依賴注入容器。

表1是描述了從4個開源項目中獲取的數(shù)據(jù)集的項目名稱、獲取時間段、提交總數(shù)、文件總數(shù)以及提交和文件的匹配數(shù)commit_file的信息。

2.2 實驗結(jié)果及分析

本文中分別從4個開源項目的數(shù)據(jù)集中人工抽取了語句包裹模式變更集，并使用本文算法在人工抽取的變更集上進行了實驗驗證，實驗結(jié)果見表2。

從實驗結(jié)果可以看出，本文算法在人工抽取的語句包裹模式的變更集中的識別率在86%～90%之間波動。

將本文算法在4個開源項目的數(shù)據(jù)倉庫中進行實驗驗證后，從實驗結(jié)果所有版本中抽取了10%進行人工檢測，對從實驗結(jié)果中抽取的10%進行人工檢測后的驗證結(jié)果見表3。

本文算法對4個開源項目數(shù)據(jù)倉庫進行了語句包裹模式識別，對從識別結(jié)果所有版本中抽取的10%進行人工檢測后，檢測結(jié)果的準(zhǔn)確率在95%～98%之間波動。

本文算法在4個開源項目數(shù)據(jù)倉庫上進行實驗得到實驗結(jié)果集后，從結(jié)果集中抽取每一種語句包裹模式的變更版本集的10%進行人工檢測，實驗結(jié)果見表4。

對從實驗結(jié)果集中每種語句包裹模式變更版本集中抽取10%并進行人工檢測后，實驗結(jié)果顯示準(zhǔn)確率在95%～97%之間波動。

對人工抽取的變更集的識別率以及對從結(jié)果集中抽取實例進行人工驗證的準(zhǔn)確率未能達到100%的原因，在于語句包裹粒度較大的語句包裹模式變更被Gnu Diff劃分到了多個hunk中，這種情況降低了本文算法識別結(jié)果的準(zhǔn)確度，將來可以為大粒度語句包裹模式變更提供hunk合并功能，以提高對于這種情況的識別準(zhǔn)確率。

3 結(jié)束語

本文通過對代碼變更的研究，介紹了代碼變更中普遍存在的語句包裹模式，提出了基于代碼變更塊和抽象語法樹的語句包裹模式識別分類算法，在4個開源項目數(shù)據(jù)倉庫上進行實驗驗證后，實驗結(jié)果證明本文算法對于語句包裹模式的識別具有較高的準(zhǔn)確率。對于存在代碼移動的提煉函數(shù)（Extract Method）和提煉類（Extract Class）等重構(gòu)模式，本文提出的基于代碼變更塊和抽象語法樹的算法也能對其進行識別。在將來的研究中，需要為大粒度語句包裹模式變更提供hunk合并功能。并將該算法在更多數(shù)據(jù)集上進行實驗驗證的基礎(chǔ)上將其用于其他重構(gòu)模式的識別。

參考文獻

[1] FOWLER M.Refactoring： Improving the design of existing code[M]. USA：Addison-Wesley， 1999.

[2]ZHANG Jie，WANG Xiaoyin，HAO Dan，et al. A survey on bug-report analysis[J]. Science China（Information Sciences），2015，58（2）：92.

[3]童燕翔. 基于Bug Report的降噪和缺陷定位研究[D]. 南京：南京航空航天大學(xué)，2016.

[4]ESHKEVARI L M， ARNAOUDOVA V， PENTA M D， et al. An exploratory study of identifier renamings[C]// International Working Conference on Mining Software Repositories， （MSR）. Honolulu，HI， USA：Dblp， 2011：33.

[5]KAWRYKOW D， ROBILLARD M P. Non-essential changes in version histories[C]// 2011 33rd International Conference on Software Engineering. Honolulu，HI， USA：IEEE， 2011：351.

[6]KIM S ， PAN K ， WHITEHEAD E J . Memories of bug fixes[C]// Proceedings of the 14th ACM SIGSOFT International Symposium on Foundations of Software Engineering， FSE 2006. Portland， Oregon， USA：ACM， 2006：35.

[7]原子，于莉莉，劉超. 面向細粒度源代碼變更的缺陷預(yù)測方法[J]. 軟件學(xué)報，2014，25（11）：2499.

[8]劉望舒，陳翔，顧慶，等. 一種面向軟件缺陷預(yù)測的可容忍噪聲的特征選擇框架[J]. 計算機學(xué)報，2018，41（3）：506.

[9]PAN Kai， KIM S H， WHITEHEAD E J.Toward an understanding of bug fix patterns[J].Empirical Software Engineering，2009，14（3）：286.

[10]HUNT J W， SZYMANSKI T G. A fast algorithm for computing longest common subsequences[J].Communications of the Association for Computing Machinery，1977，20（5）：350.