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

段衛華， 楊春花

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

0 引 言

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

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

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

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

1 語句分裂變更模式

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

1.1 差異分析工具

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

1.1.1 文本差異分析工具

文本差異分析是將更改前后的源文件視為字符串，通過計算公共子序列來判別發生變動的文本，并將這些文本信息以及對應的行號以代碼變更塊（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）是一種源文件語法結構的樹狀表現形式，而樹中的每一個節點都是由源代碼中的語句映射而來的。 通過對抽象語法樹的遍歷，可以準確獲得源代碼中的每一個節點信息。

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

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

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

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

基于上述hunk 的定義并結合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 中部分內容或直接添加到語句s 中而得來的。

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

圖3 替換形式Fig.3 Replacement form

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

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

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

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

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

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

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

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

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

2 語句分裂變更模式識別

本文根據語句分裂變更模式所呈現出的語法特征，設計了該模式的識別算法。 該算法首先在文本層面以hunk 為單位，提取出一次更改前后兩個版本源文件之間所有的變更信息；經初步篩選后，再根據hunk 所包含的語法樹節點信息逐一分析是否包含了語句分裂變更模式的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（） 函數得到整體范圍較小的hunk 的集合H’；第3 行使用parser 工具分別構造兩個目標文件的抽象語法樹（A，A’）；第5 行使用fetchNodes（） 函數獲得hunk 的刪除行和增加行包含的節點信息集合N － 和N ＋； 第6、7 行使用checkSplit（） 函數識別拆分形式，并以三元組＜h，s，s’1～s’n＞的形式存入集合PS 中；第8～16 行判斷替換形式。 對判斷替換形式偽代碼部分的說明：首先利用findVarDefine（） 函數獲取hunk 中變量聲明節點V，并通過getVarName（） 函數獲得新聲明變量的變量名集合M，使用getSameTypeNode（） 函數找出與N －與N ＋中相同類型節點的集合（O －，O ＋）；第12 行使用getChildNodesAsString（）函數獲得集合O ＋中每個節點的子節點信息集合C；第13 行使用contains（）函數判斷字符串C 是否至少包含一個集合M 中的字符序列，以確定分裂后的原句中存在新變量的變量名；第14 行滿足上述條件的hunk 以四元組＜h，o－，m，c＞的形式存入集合PR 中。 此算法的輸出結果中，變量o－、m 和c 分別替代了定義3 中的語句s、語句v 和語句s’。 變量h 表示一個四元組＜L－，L＋，R－，R＋＞；變量o－是集合O－中的元素，代表語句s 的節點信息；變量m 是集合M 中的元素，代表語句v 的新變量變量名；語句s 被m 替換部分內容后變為語句s’；變量c 是集合C 中的元素，代表語句s’的節點信息。

3 算法實現與驗證

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

3.1 數據源

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

（1）eclipseJDTCore4 開源項目，是針對Java 的集成開發環境。

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

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

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

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

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

3.2 實驗結果分析

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

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

表2 識別算法識別人工數據集結果Tab.2 Experimental results of recognition algorithm identifying artificial data set

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

3.2.2 算法對4 個源數據集的識別

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

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

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

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

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

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

3.3 實驗結論

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

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

4 結束語

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