語句分裂變更模式的定義及識別

段衛(wèi)華， 楊春花

（齊魯工業(yè)大學 計算機科學與技術學院， 濟南250353）

0 引 言

現(xiàn)代軟件的開發(fā)一般基于版本管理系統(tǒng)設計實現(xiàn)，軟件工程師為了實現(xiàn)開發(fā)和維護的任務，每天都會提交大量的代碼變更，而這些變更往往會遵循一定的修改模式，如重構(gòu)（Refactoring）、缺陷修復（bug－fixing）和一些裝飾型（cosmetic）的修改模式等等。由于變更的日志描述往往反映不了變更的真正行為［1］，因此對代碼變更的理解還需要人工審查變更代碼來確定。 日常代碼修改往往存在多種變更模式的重疊，如果將代碼變更模式進行識別，則可將各種模式的變更代碼區(qū)別開來，減少這些代碼之間的耦合，從而方便分析和理解軟件的演化過程。

對于典型的重構(gòu)模式，M.Fowler［2］對其進行了系統(tǒng)的研究。 重構(gòu)的目的是優(yōu)化代碼中存在的一些不合理結(jié)構(gòu)（即代碼異味），而對代碼異味的檢測主要有人工檢測［3－4］和自動化檢測［5］2 種方式。 對于缺陷修復（bug－fixing）較為重要的研究方向就是對缺陷的檢測。 缺陷的檢測方法有：基于信息檢索技術的缺陷定位方法［6］和利用項目的歷史信息改進的缺陷檢測方法［7］等。 裝飾型修改的目的一般是規(guī)范代碼的編寫，所以不會影響整個軟件的作用，對其研究包括標識符重命名［8］和編程風格［9］的研究等。

替換算法是將函數(shù)體中復雜的功能塊進行封裝，從而使函數(shù)體結(jié)構(gòu)更為簡潔清晰的重構(gòu)手法。 但在開發(fā)實踐中，常見將一條語句分裂成多條語句的代碼變更模式，即語句分裂變更模式。 該模式在代碼語句層面利用封裝思想優(yōu)化代碼語句結(jié)構(gòu)。 然而有些語句分裂變更類似于重構(gòu)，不會改變語句行為，而有時又會像缺陷修復模式一樣改變語句行為。 因此，不能將該模式簡單歸類為重構(gòu)模式或是缺陷修復模式。

本文對語句分裂變更模式進行了定義及識別研究，通過對大量的語句分裂變更模式實例進行人工觀察，分析總結(jié)出了2 種該模式常見的變更形式，并將其定義命名為拆分形式和替換形式，同時還設計并實現(xiàn)了2 種形式的識別算法。

1 語句分裂變更模式

代碼變更是指一個源代碼文件修改前后的兩個版本的差異。 目前，對變更的提取基本是借助于差異化分析工具來實現(xiàn)的，對語句分裂變更模式的定義是基于差異分析工具的輸出結(jié)果而制定的。

1.1 差異分析工具

目前使用的差異分析工具主要有：文本差異分析（Textual － Differencing） 和 樹 差 異 分 析（Tree －Differencing）。

1.1.1 文本差異分析工具

文本差異分析是將更改前后的源文件視為字符串，通過計算公共子序列來判別發(fā)生變動的文本，并將這些文本信息以及對應的行號以代碼變更塊（hunk）為單位輸出。 所以，hunk 實際上就是不同行的集合，其包括舊版本源文件的刪除行和新版本源文件的增加行，也可以只包含刪除行部分或增加行部分。

常見的文本差異分析工具是diff。 其中， GNUDiff［10］推出了“合并格式”的Diff，2 個文件的上下文合并在一起顯示，并由“－”表示變動前的文件，“＋”表示變動后的文件。 hunk 實例如圖1 所示，hunk 中左邊行號88 行為舊版本的刪除行，右邊行號88－89則為新版本的增加行。

圖1 hunk 示例Fig.1 hunk example

1.1.2 樹差異分析工具

抽象語法樹（abstract syntax tree， AST）是一種源文件語法結(jié)構(gòu)的樹狀表現(xiàn)形式，而樹中的每一個節(jié)點都是由源代碼中的語句映射而來的。 通過對抽象語法樹的遍歷，可以準確獲得源代碼中的每一個節(jié)點信息。

樹差異分析是通過對比修改前后源文件所對應的抽象語法樹，來獲取結(jié)構(gòu)化的變更信息，這些信息更有利于變更的分析。 最著名的基于抽象語法樹差異分析工具是Change－Distiller［11］，其可以獲得一個文件變更前后所有的代碼變更類型。 這是Fluri 等人編寫的一個Tree differ 算法，對變更前后抽象語法樹進行對比，獲取分類的變更。 同時，也可以區(qū)別多種方法類型的變化或類等級上的變化。

1.2 語句分裂變更模式的定義

語句分裂變更模式包含拆分和替換兩種形式，而對于這2 種形式的研究是以文本差異分析工具輸出的代碼變更塊（hunk）為單位的，所以要對hunk進行定義。

定義1代碼變更塊hunk 可以用四元組h ＝＜L－，L＋，R－，R＋＞的形式來表示。 其中， L－和L＋分別代表刪除行和增加行的文本內(nèi)容， R－和R＋分別代表刪除行和增加行的行號范圍。

基于上述hunk 的定義并結(jié)合2 種形式的文本特征，來定義拆分形式和替換形式的語句分裂變更模式。

定義2拆分形式的語句分裂變更模式可以用三元組＜h，s，s’1 ～s’n＞的形式表示。 在h 中，?語句s∈L－∧語句s’1～s’n∈L＋。 在此需滿足：

（1）s 是一條存在傳遞賦值的賦值語句。

（2）s’1 ～s’n 是由s 拆分而來的多條賦值語句。 拆分形式實例如圖2 所示。 其中，刪除行872行為傳遞賦值語句，增加行872－873 行為拆分后得到的兩個賦值語句。

圖2 拆分形式Fig.2 Split form

定義3替換形式的語句分裂變更模式是一個四元組＜h，s，v，s’＞。 在一個h 中，?語句s∈L－∧語句v∈L＋∧語句s’∈L＋。 此時需滿足：

（1）v 是一條變量賦值語句。

（2）s’是由語句v 中的變量替換語句s 中部分內(nèi)容或直接添加到語句s 中而得來的。

替換形式實例如圖3 所示。 其中：刪除行398 為語句s；增加行402 為變量賦值語句v，404 行為語句v中 的 變 量 extensionComponents， 替 換 語 句s 中getPlugExtensionComponents（plugin）而得到的語句s’。

圖3 替換形式Fig.3 Replacement form

1.3 語句分裂變更模式的抽象語法樹節(jié)點變化特征

語句分裂變更模式的識別，要借助于抽象語法樹節(jié)點變化特征的分析。 抽象語法樹的每一層結(jié)構(gòu)被稱做節(jié)點（Node），一個AST 可以由單一節(jié)點或多個節(jié)點構(gòu)成，每個節(jié)點包含了type（類型）和location（位置信息）。 抽象語法樹的節(jié)點類型分為：語句（Statement） 類、 表 達 式（Expression） 類、 聲 明（Declaration）類等。 節(jié)點的位置信息包括起始位置（被解析的源區(qū)域的第一個字符的位置）和結(jié)束位置（被解析的源區(qū)域之后的第一個字符的位置）。

假設在一個hunk：＜L－，L＋，R－，R＋＞中，刪除行L－和增加行L＋所包含的全部節(jié)點集合分別為N－與N＋。

根據(jù)定義2 的拆分形式存在以下語法特征：

（1）N－中一定存在至少一個賦值語句類型的節(jié)點，且其包含賦值語句類型的子節(jié)點（對應上述定義2 中的語句s）。

（2）N＋中一定存在至少2 個賦值語句類型的節(jié)點（對應上述定義2 中的語句s’1 ～s’n），并且這些節(jié)點的子節(jié)點要包含（1）中賦值語句節(jié)點的所有子節(jié)點，以確保N＋中的多個賦值語句是由N－中的賦值語句拆分得來的。

根據(jù)定義3 的替換形式存在以下語法特征：

（1）N＋比N－多一個變量賦值節(jié)點（對應上述定義3 中的語句v）；

（2）N－與N＋存在相同類型的語句節(jié)點（對應上述定義3 中的語句s 與s’），并且N＋中的語句節(jié)點的子節(jié)點信息中要包含（1）中變量賦值節(jié)點的變量名信息。

2 語句分裂變更模式識別

本文根據(jù)語句分裂變更模式所呈現(xiàn)出的語法特征，設計了該模式的識別算法。 該算法首先在文本層面以hunk 為單位，提取出一次更改前后兩個版本源文件之間所有的變更信息；經(jīng)初步篩選后，再根據(jù)hunk 所包含的語法樹節(jié)點信息逐一分析是否包含了語句分裂變更模式的2 種常見形式；最后將包含語句分裂變更模式拆分形式的hunk 以三元組＜h，s，s’1～s’n＞的形式存入集合PS，將包含替換形式的hunk 以四元組＜h，o－，m，c＞的形式存入集合PR。算法部分偽代碼如下所示：

輸入：同一文件的一次更改前后2 個版本的源文件Fileold 和Filenew。

輸出：拆分形式語句分裂變更模式的hunk 集PS與替換形式的語句分裂變更模式的hunk 集PR。

算法第1 行使用diff 工具獲得兩個源文件的hunk 集合H；第2 行使用filter（） 函數(shù)得到整體范圍較小的hunk 的集合H’；第3 行使用parser 工具分別構(gòu)造兩個目標文件的抽象語法樹（A，A’）；第5 行使用fetchNodes（） 函數(shù)獲得hunk 的刪除行和增加行包含的節(jié)點信息集合N － 和N ＋； 第6、7 行使用checkSplit（） 函數(shù)識別拆分形式，并以三元組＜h，s，s’1～s’n＞的形式存入集合PS 中；第8～16 行判斷替換形式。 對判斷替換形式偽代碼部分的說明：首先利用findVarDefine（） 函數(shù)獲取hunk 中變量聲明節(jié)點V，并通過getVarName（） 函數(shù)獲得新聲明變量的變量名集合M，使用getSameTypeNode（） 函數(shù)找出與N －與N ＋中相同類型節(jié)點的集合（O －，O ＋）；第12 行使用getChildNodesAsString（）函數(shù)獲得集合O ＋中每個節(jié)點的子節(jié)點信息集合C；第13 行使用contains（）函數(shù)判斷字符串C 是否至少包含一個集合M 中的字符序列，以確定分裂后的原句中存在新變量的變量名；第14 行滿足上述條件的hunk 以四元組＜h，o－，m，c＞的形式存入集合PR 中。 此算法的輸出結(jié)果中，變量o－、m 和c 分別替代了定義3 中的語句s、語句v 和語句s’。 變量h 表示一個四元組＜L－，L＋，R－，R＋＞；變量o－是集合O－中的元素，代表語句s 的節(jié)點信息；變量m 是集合M 中的元素，代表語句v 的新變量變量名；語句s 被m 替換部分內(nèi)容后變?yōu)檎Z句s’；變量c 是集合C 中的元素，代表語句s’的節(jié)點信息。

3 算法實現(xiàn)與驗證

該算法基于Java 編程語言實現(xiàn)，算法使用文本差異分析工具Gnu Differ 來提取變更，并使用Java Parser 工具構(gòu)造2 個源文件的抽象語法樹，最后在4個開源項目上進行了驗證。 具體研究內(nèi)容如下。

3.1 數(shù)據(jù)源

利用Minigit3 工具從Git Hub 項目托管平臺中抓取一定時間內(nèi)4 個開源項目的版本變更歷史數(shù)據(jù)作為源數(shù)據(jù)集。

（1）eclipseJDTCore4 開源項目，是針對Java 的集成開發(fā)環(huán)境。

（2） mavens 開源項目，是通過信息描述來管理項目的構(gòu)建、報告和文檔的開源管理工具。

（3）jEdit6 開源項目，是跨平臺的文本編輯器。

（4）google－guice7 是輕量級的依賴注入容器。

表1 列出了上述4 個源數(shù)據(jù)集各自所包含更改提交的次數(shù)和4 個項目的文件數(shù)，每次更改的提交會涉及到對多個文件的更改。

表1 4 個源數(shù)據(jù)集的提交更改的次數(shù)和文件數(shù)Tab.1 Number of commit changes and files for four source datasets

3.2 實驗結(jié)果分析

3.2.1 算法對人工篩選hunk 集的識別

經(jīng)人工篩選4 個源數(shù)據(jù)集，并且得到包含語句分裂變更模式的hunk 集后，用識別算法去識別人工篩選出的hunk 集，目的是驗證識別算法的準確率，實驗結(jié)果見表2。

表2 識別算法識別人工數(shù)據(jù)集結(jié)果Tab.2 Experimental results of recognition algorithm identifying artificial data set

由表2 可見，該識別算法在識別人工篩選數(shù)據(jù)集時的準確率在81%～89%之間波動。 由于在人工篩選過程中，包含語句分裂變更模式的hunk 行數(shù)一般較少，所以識別算法中篩掉了一些行數(shù)較多的hunk，這樣做可提升算法的效率，但導致識別算法的準確率沒有達到最高水平。

3.2.2 算法對4 個源數(shù)據(jù)集的識別

在上述實驗結(jié)果的基礎上，利用識別算法對4個源數(shù)據(jù)集進行識別，并將輸出的hunk 集進行人工篩查，去除其中可能存在的非語句分裂變更模式的hunk。 表3 列出了識別算法所檢測到的hunk 的個數(shù)，以及人工篩查后留下的真正包含語句分裂變更模式的hunk 的個數(shù)及準確率。

表3 識別算法識別4 個源數(shù)據(jù)集的實驗結(jié)果Tab.3 Experimental results of identification algorithm identifying four source data sets

由表3 可見，識別算法識別4 個源數(shù)據(jù)集的準確率在71%～80%之間波動。

對結(jié)果分析可知，識別算法的輸出結(jié)果中存在非語句分裂變更模式的hunk 的原因主要是：在識別替換模式時，要查找hunk 的刪除行和增加行中相類型的語句，并且增加行中的語句要包含新聲明的變量，但類型相同并不一定能保證增加行的語句是由刪除行的語句變化得來的。 即使增加行的語句包含了新變量，也不能說明其與刪除行語句本質(zhì)上是同一條語句，所以并不能保證一定是替換形式，這種情況多發(fā)生于return 語句的變更中。

圖4 是一個算法輸出的hunk。 其中刪除行和增加行包含了同種類型的return 語句，且1 841 行的return 語句包含了1 839 行新聲明的變量clone。 但從clone 的賦值內(nèi)容來看，顯然與1 832 行return 語句的內(nèi)容不同。 因而算法識別出的這兩個相同類型的return 語句，從本質(zhì)上并不是同一條語句。 所以，此hunk 不能作為語句分裂變更模式的實例。

圖4 特例展示Fig.4 Special case display

3.3 實驗結(jié)論

（1）由語句分裂變更模式的2 個形式進行比較可知，該模式大多情況都是以替換形式出現(xiàn)的，拆分形式只為極少數(shù)。

（2）由各項目所包含的語句分裂變更模式的hunk 個數(shù)對比可知，變更提交次數(shù)和文件數(shù)越多的項目，包含該模式的hunk 就越多。 說明語句分裂變更模式的出現(xiàn)次數(shù)，與項目屬性和更改提交者的個人習慣等因素關系較小。 項目規(guī)模越是龐大，該模式出現(xiàn)的次數(shù)就越多。

4 結(jié)束語

本文通過人工篩選的數(shù)據(jù)歸納，總結(jié)了語句分裂變更模式的特征，制定了該模式的定義，并且設計了基于該模式語法特征和以hunk 為識別單位的語句分裂變更模式的識別算法。 分別在人工篩選的數(shù)據(jù)集和4 個開源項目的源數(shù)據(jù)集上進行了算法的驗證，并由實驗結(jié)果得到了一些結(jié)論。 后續(xù)工作還需要對識別出來的語句分裂變更模式進行更為細致的分類，即對語句分裂變更過程中各個部分伴隨的一些變化進行分析，以便更加深入的了解語句分裂變更模式；另外還需要考慮到行數(shù)較多的hunk 或多個hunk 之間存在語句分裂變更模式的情況，并盡可能的對此類復雜情況進行研究分析。