二次文本差異化的失配問題及其改進算法

公鑫，楊春花

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

0 引言

現(xiàn)代大型軟件的開發(fā)一般基于版本管理系統(tǒng)由多人協(xié)作完成，開發(fā)者每天將變更的代碼提交到軟件倉庫中，而閱讀和理解代碼變更則成為代碼評審以及日常開發(fā)和維護工作的基礎［1－2］。

當前對代碼變更的審閱一般在文本差異化分析（textual code differencing）工具提供的Hunk 集上進行。例如，圖1 是典型的文本差異化分析工具GNUDiff 返回的一個Hunk 示例。一個Hunk 由一段連續(xù)的被刪除（－）和插入（＋）的行以及前后1～3 個上下文行構成。一個Hunk 集構成了源代碼修改前后的代碼變更，變更審閱者只需要查看這些Hunk，就可以知道代碼哪里發(fā)生了什么改變，不需要人工對比2 個版本的源代碼，提高了代碼變更的理解效率。

對于復雜的變更，以行為單位的Hunk 結果不能展現(xiàn)Hunk 內(nèi)部的具體變化。為此，許多工具如Kdiff3 和Beyond Compare 4、GitHub Diff等對Hunk內(nèi)部的刪除行和添加行之間進行二次差異化分析，從而獲得細化的變更結果。圖2 是Beyond Compare 4 對圖1 的Hunk 進行二次差異化分析的結果，該結果展示在并排（side－by－side）窗口中，其中發(fā)生變化的行和單詞（Token）進行了加亮顯示。后文均默認新版本為右側(cè)文本，老版本為左側(cè)文本。Hunk 內(nèi)的二次差異化分析方便用戶快速理解Hunk 內(nèi)行的具體變化，但是當前的二次差異化分析工具得出的結果存在失配現(xiàn)象，主要體現(xiàn)為行之間的失配和一個完整Token 的拆分現(xiàn)象。根據(jù)圖2 的展示，老版本（左）的132～134 行被分析為與新版本（右）中第161～163行匹配對應；而新版本（右）中“Constraints”等單詞（Token）的部分字符被分析為差異文本。前者是一種行失配，因為事實上老版本（左）的132～134 行應該與新版本（右）中第161～162 行相似性匹配，這種匹配體現(xiàn)了對該變量聲明語句的編程風格的變化。

圖1 Hunk 例子Fig.1 Hunk example

圖2 Beyond Compare 4 分析結果Fig.2 Beyond Compare 4 analysis results

在前期研究工作中，作者發(fā)現(xiàn)這種失配現(xiàn)象在許多工具中都或多或少的存在，由于這種失配現(xiàn)象造成分析的結果不能反映事實上的代碼變更，從而會誤導代碼的理解。為了克服該問題，本文在對該失配現(xiàn)象進行調(diào)查和分析的基礎上，提出了一個對其進行克服的算法，并將該算法進行了實現(xiàn)和驗證。

1 國內(nèi)外研究現(xiàn)狀

代碼差異化分析是理解代碼變更的基礎，通過比較源代碼修改前后2 個版本，獲得變化了的代碼。代碼差異化分析主要分為2 類：文本差異化和樹差異化。

文本差異化分析算法將源代碼看成一個字符串，因此代碼修改前后2 個版本之間的比較就變成了2 個字符串間的比較，一般基于最長公共子序列算法實現(xiàn)［3－4］。最經(jīng)典的文本差異化算法是GNUDiff，目前各種版本管理系統(tǒng)如Git、SVN 和客戶端管理工具source tree、以及eclipse等IDE 的External Compare1 插件中集成的diff 工具或窗口基本都基于該算法。其它典型的文本差異化分析方法包括LDiff、LH Diff、JSync等，這些方法返回基于文本行的變更，以Hunk為單位返回。正如Kdiff3、Beyonce Compared 4等工具提供對Hunk 內(nèi)的二次差異化分析，獲得Hunk 內(nèi)部的差異文本。文本差異化分析算法可以分析各種類型的源代碼文件，而且效率高，因此在實踐中被廣泛采用［5－6］。

樹差異化分析算法，將2 個版本的源代碼分別進行語法分析形成抽象語法樹（AST），通過對比2棵AST 之間的不同，輸出變動的結點［7－8］。最著名的算法是Change Distiller，還存在算法GumTree、CLDIFF、MTDiff、Diff／TS 和IJM 支持對移動代碼的差異檢測，而CSLICER 和RTED 不支持對移動代碼差異檢測，這些樹差異算法可以輸出語法意義上的代碼變更集，但是由于相比文本差異化算法來講效率低，而且一般針對特定的開發(fā)語言，因此在實踐中沒有被廣泛采用。

為此，一些工具對Hunk 內(nèi)部進行二次差異化分析，將Hunk 內(nèi)部刪除行和添加行之間進行相似性比較，獲得細化的差異化結果。例如，針對圖1 的Hunk，Beyonce Compared 4 對其進行二次分析，返回如圖2 的差異結果。但是這些二次差異化分析工具返回的結果存在許多不合理的現(xiàn)象，主要表現(xiàn)為行失配和單詞（Token）失配，前者指語法上相似的語句行之間的不匹配，后者由于單詞沒有作為基本單位進行差異化分析造成的一個或多個單詞的內(nèi)部子串作為差異化結果輸出－即Token 被拆分的現(xiàn)象，如圖2 所示。

這兩種失配現(xiàn)象在大多數(shù)對Hunk 進行二次差異化分析的工具中普遍存在，給變更理解者造成不好的體驗，同時容易誤導給出錯誤的變更結果。

因此，為了克服此現(xiàn)象，本文提出基于Token（單詞）的Hunk 內(nèi)二次差異化分析算法，以Token為基本單位，進行語句行間的相似性匹配以及相似行內(nèi)的Token 差異分析。該算法已實現(xiàn)，并在5 個開源項目進行了驗證。

2 二次差異化分析中的失配問題

2.1 失配問題的占比

為了查清失配問題在二次差異化分析中的分布，從前期工作中一直采用的數(shù)據(jù)集中隨機選取了部分提交版本，分別利用典型的二次差異化分析工具Kdiff3、Beyonce Compared 4 對其分析，人工對其結果中的失配情況進行分析。

數(shù)據(jù)集是由5 個開源項目組成，分別從各個項目的有效文件中各隨機抽取100 條，共500 條數(shù)據(jù)，每條數(shù)據(jù)為一文件的某2 個版本。這些數(shù)據(jù)分別利用工具Kdiff3、Beyonce Compared 4 分析后，人工判斷其差異結果，具體分析結果如圖3 所示。在Kdiff3 和Beyonce Compared 4 工具對該數(shù)據(jù)集分析結果中，均有50%以上的結果存在錯誤，其中由于編程風格等原因造成的語句失配與由于Token 部分差異而造成的Token 失配所占比重尤為突出，可見這些問題在現(xiàn)有工具中是普遍存在的，所以本文的研究是有意義的，同時該數(shù)據(jù)集用來驗證本文算法及工具是有效的。

圖3 Kdiff3、Beyond Compare 4 差異分析情況Fig.3 Kdiff3、Beyond Compare 4 difference analysis

2.2 問題分析

圖2 所示是對圖1 所示的Hunk 應用Beyond Compare 4 得到的差異結果。從該結果可以看出，老版本（左）的第132～134 行被分析為與新版本（右）中第161～163 行對應，新版本160 行分析為添加行，黑色的字符為差異字符。從該結果容易看出，BeyondCompare4 是將每一個刪除行和添加行分別視為一個字符串，然后應用最長公共子序列算法分別得到的差異的字符，沒有體現(xiàn)每個刪除行和添加行之間的匹配關系，也沒有以單詞（Token）為單位，造成了一個Token 的內(nèi)部子串被部分差異化的現(xiàn)象。新版本的第 163 行中的最后一個單詞constraints，被解釋為其中的“c”和“rai”被增加。如果一個Hunk 中存在大量的修改行，且修改無規(guī)律的話，這種分析結果將會干擾變更理解，增加理解者的負擔。

圖4 是對圖1 所示Hunk 應用KDiff3 工具得到的分析結果，可以看出，依據(jù)KDiff3 的結果，新版本（右）中的第160 行、161 行、和163 行被分析為添加行，老版本（左）中的132 和133 行被分析為刪除行，老版本的第134 行被分析為修改成新版本的第162 行（即老版本的第134 行和新版本的第162 行二者相似性匹配）。然而，從理解者的角度，容易看出，老版本的第132～134 行屬于一條賦值語句，其實際被修改成了新版本中第161～162 行所屬的賦值語句，這種修改實際是編碼風格上的改變（即僅僅涉及到回撤、Tab等分隔符的改變）。因此，KDiff3的這個結果一定程度上給理解者造成誤導。

圖4 Kdiff3 分析結果Fig.4 Kdiff3 analysis results

分析圖4 中KDiff3 的結果，不難看出，其首先在刪除的文本行和添加的文本行之間進行了相似性匹配，然后在匹配的文本行內(nèi)部又進行了一次最長公共子序列算法，得到差異的子串。但是編碼風格的修改，可能會使一條語句分散到連續(xù)的多個文本行中，因此這種基于文本行的行與行之間的匹配，不能保證得到的是一條完整語句之間的匹配。因此，要克服KDiff3 的這種局限性，需要首先識別一條完整語句對應的文本行，然后再進行語句間的匹配。

通過以上分析，可以看出造成行失配和Token失配現(xiàn)象是由于在二次差異化分析時沒有實現(xiàn)語法意義上行與行之間的匹配，以及匹配的語句內(nèi)部的差異以字符為單位而不是Token為單位進行的。針對這兩點，提出基于Token 的Hunk 內(nèi)二次差異化分析算法。

3 基于輕語法分析的Hunk 內(nèi)二次差異化分析算法

基于對二次差異化分析方法產(chǎn)生原因的分析，可以發(fā)現(xiàn)失配問題的主要原因是在Hunk 的刪除行和添加行之間未進行語法意義上行之間的相似性匹配。因此，本文提出基于輕語法分析的Hunk 內(nèi)二次差異化分析算法，之所以稱為輕語法分析是指針對流行編程語言如Java、C等的語句構成形式，將Hunk 中的文本行映射為語句行，并從每個語句中抽取其單詞（Token）構成一個Token 序列，然后對語句所對應的Token 序列之間應用相似性匹配和最長公共子序列算法，從而實現(xiàn)二次差異化分析。

3.1 算法架構

算法的總體架構如圖5 所示。算法的輸入是一個Hunk，該Hunk 是通過GNU－Diff 算法產(chǎn)生Hunk集中的一個元素，由刪除行、添加行和上下文行構成，輸出二次差異化分析后的Hunk，包括刪除的語句、添加的語句、以及更新語句內(nèi)部的差異單詞（即添加的Token 和刪除的Token）。

圖5 算法框架圖Fig.5 Algorithm framework

算法主要由語句識別、語句相似性匹配和語句內(nèi)部差異化3 個步驟構成。

首先，對每個刪除的行和添加的行分別進行語句識別。該步驟將根據(jù)源文件所用編程語言的特點，將跨行的語句進行合并處理，必要的話需要添加相應的上下文，該步驟結束將得到一個刪除語句序列和一個添加語句序列。

其次，對所有的刪除語句和添加語句進行相似性匹配，得到最相似的語句對。其中，匹配的語句識別為語句更新（update）；刪除語句中未匹配的語句識別為語句刪除（del）；添加語句中未匹配的語句識別為語句添加（add）。

最后，對每個語句更新，分別產(chǎn)生老版本語句和新版本語句的Token 序列，對這兩個Token 序列進行差異化分析，得到差異的Token。

3.2 算法

算法HunkDiff 實現(xiàn)了提出的算法，其描述如算法1 所示。

算法輸入一個Hunkh，由3 部分構成：刪除行集合L－、添加行集合L＋和上下文行集合Lcontext。其中，Hunkh是GNUDiff 算法分析得到Hunk 集的一個元素。

一般地，一個差異化分析算法的輸出是一個編輯操作（edit operations）集合，常見的編輯操作分為添加ADD，刪除DEL，和更新update。因此，本算法的輸出是差異化分析后的Hunkh＇，其是一個四元組：（SDEL，SADD，Supdate，Delta），其中SDEL為刪除語句操作的集合；SADD為添加語句操作的集合；Supdate為更新語句操作的集合。

對于每一個語句更新操作，設為＜ s－，s＋ ＞，其中s－是老版本的語句，s＋是新版本的語句，則該算法會分析此語句內(nèi)部的Token差異，將識別的結果存到Delta中。具體地說，Delta中的每個元素是一個三元組：（＜s－，s＋＞，TDEL，TADD），其中＜s－，s＋ ＞是一個語句更新操作；TDEL是刪除的Token集合；TADD是新增的Token集合；剩余的Token則是未修改的。

該算法的步驟解釋如下：

算法首先通過輔助函數(shù)identifySentences 分別對刪除行集合L－和添加行集合L＋進行語句識別，根據(jù)源文件編程語言的特點，得到語句集合S－和S＋；

其次，對集合S－和S＋中語句逐一進行相似性匹配，得到集合SDEL、SADD和Supdate。相似性匹配算法matching在算法2 中描述；

省水利廳按照水利部和省領導的指示認真組織學習《條例》，并把貫徹落實《條例》當成在浙江省實施最嚴格水資源管理制度的一個契機。根據(jù)杭嘉湖地區(qū)的實際情況，省水利廳組織專家和水行政主管部門負責人在大量調(diào)查研究的基礎上，形成了貫徹落實《條例》的方案，于2012年2月向浙江省人民政府上報了《關于貫徹落實〈太湖流域管理條例〉意見的函》，經(jīng)省政府批準后實施。

最后，對于集合Supdate中的每個語句更新操作＜s－，s＋＞，執(zhí)行語句內(nèi)的差異化分析，對應于算法的第7～15 行。通過輔助函數(shù)TokenSplit 對s－和s＋中的Token進行識別，得到各自的Token序列l(wèi)－和l＋；對序列l(wèi)－和l＋執(zhí)行最長公共子序列算法，得到一個最長公共子串的下標序列index－和index＋，其中index－代表公共子串在老版本中的下標，index＋代表公共子串在新版本中的下標，具體定義如下：

從l－中抽取不在index－中的下標序列，得到老版本中的Token差異集合TDEL，該功能用輔助函數(shù)genDiffTokens（l－，index－）來實現(xiàn)。同理，依據(jù)index＋，得到新版本中的Token差異集合TADD。因genDiffTokens 函數(shù)實現(xiàn)簡單，在此省略其描述。

算法1HunkDiff

輸入一個Hunkh＝（L－，L＋，Lcontext），其中L－、L＋和Lcontext分別為刪除、添加的文本行和上下文行。

輸出二次差異化后的Hunkh＇＝（SDEL，SADD，Supdate，Delta），其中SDEL為刪除的語句集合；SADD為添加的語句集合；Supdate為更新的語句集合；Delta包含每條語句更新內(nèi)部的差異Token。

若Hunk 中刪除語句行為m，添加語句行數(shù)為n，且存在最大相似語句對max（m，n）；每個相似語句對必存在有限序列的字符串，即相似語句對的差異化分析為常數(shù)級；所以算法1 的時間復雜度為O（m*n*max（m，n））。

3.3 相似性匹配matching 算法的描述

算法matching 實現(xiàn)了語句行之間的相似性匹配，其描述如算法2 所示。

該算法輸入語句行集合S－和S＋，輸出語句刪除操作集合SDEL、語句增加操作集合SADD和語句更新操作集合Supdate。算法設置輔助變量：相似對序列Simlist，匹配標志數(shù)組Matched－和Matched＋。

算法首先將S－中的每條語句與S＋中的每條語句逐一進行相似性比較，將對應的語句及其相似值存入序列Simlist。相似性比較在2 條語句所對應的Token串之間進行，相似性計算采用Jaccard系數(shù)計算［9］。已知Token串l－＝（t1，t2，...，tm）和l＋＝（t1，t2，...，tn），Jaccard值計算如式（1）：

最后，語句集合S－和S＋中剩余的語句分別加到SDEL和SADD中返回。

算法2matching

輸入一個刪除語句行集合S－和一個添加語句行集合S＋。

輸出語句刪除操作集合SDEL，語句增加操作集合SADD，Supdate為語句更新操作集合。

3.4 示例

流行編程語言Java、C 的語句，絕大多數(shù)是以“；”、“｛”或“｝”為語句結束標記，輔助函數(shù)identify Sentences以此為一條語句的結束標記，對于不存在此標記的一行或多行語句，將借助上下文中的標記符。以圖1 所示Hunk為例，輔助函數(shù)identify Sentences在輸入該Hunk 后，首先根據(jù)java 語言的語句特點，將以“；”、“｛”或“｝”結束標記符結尾的語句行劃分記錄為一條語句，使得由于個人編程風格等原因而跨行的語句，在差異分析時能夠完整的參與比較，可能存在無結束標記符的語句行，為此將借助上下文的語句行。得到的刪除集合S－和添加集合S＋，分別記錄一條語句｛＜132，134＞｝和3 條語句｛＜160，160＞，＜161，162＞，＜163，163＞｝。

根據(jù)集合S－和S＋進行語句的相似性匹配，得到相似對序列Simlist＝｛＜132，134＞，＜161，162＞，1｝，由于序列Simlist內(nèi)只包含了一組相似度為1 的元素，所以該Hunk不存在語句更新操作和刪除操作，僅存在語句增加操作集合SADD＝｛＜160，160＞，＜163，163＞｝。

如果存在集合Supdate，會將Supdate中元素的語句s－和s＋進行差異化分析，得到的基于Token 的最長公共子序列，進而得到TDEL和TADD，即得到Delta，具體結果如圖6 所示。

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

4.1 算法實現(xiàn)

該算法采用Java 語言實現(xiàn)，已知源文件的2 個版本，首先通過GNU－Diff 得到Hunk 集，然后對每個Hunk 應用提出的算法，獲得Hunk 的二次差異化分析結果。同時，設計和實現(xiàn)了一個Diff 工具HunkDiff，依托Eclipse 平臺，借助于Eclipse 插件External Diff 對項目提交數(shù)據(jù)進行獲取后，將提交中的源代碼文件的修改采用當前的算法實現(xiàn)抽取結果，基于可視化框架JavaFX 設計了Diff 展示窗口對結果進行展示。

該工具對圖1 的Hunk 應用提出的算法后得到的結果如圖6 所示?？梢钥闯觯瑘D6 的結果克服了行失配和Token 失配，符合變更的真實意圖。相比Beyonce Compared 4 和Kdiff 3 的分析結果，HunkDiff工具通過忽略回撤符進行語句間的差異分析，避免了這種由于編寫風格而產(chǎn)生的差異，減少了對不必要代碼行的分析；同時基于Token 的語句內(nèi)差異分析，使得差異分析結果更加準確，提高了代碼差異分析準確率。

圖6 HunkDiff 分析結果Fig.6 HunkDiff analysis results

此外，本工具為了能夠更加簡單、明了的展示代碼差異，還對結果的展示方面做了進一步的處理，采用了All／Diff 模式，如圖7 所示，該模式可選擇是全文整體展示差異的模式，還是省略相同部分僅展示差異的模式。這使得差異分析結果更加準確、清晰的展示出來，極大的提高了開發(fā)者與代碼評審者閱讀和理解代碼的能力。

圖7 All／Diff 模式Fig.7 All／Diff mode

4.2 算法驗證

本文隨機抽取了5 個開源項目中的部分提交記錄作為數(shù)據(jù)源，將提出的算法與Kdiff3、Beyonce Compared 4 的結果進行了驗證和分析。

4.2.1 數(shù)據(jù)來源

表1 展示了5 個開源項目的概況。該數(shù)據(jù)集抽取自5 個開源項目的某個時間段的提交，采用MiniGit 工具構建，一直用于本課題組的差異化分析方法的研究中［10］。其中eclipseJDTCore 開源項目，這是一個針對Java 的集成開發(fā)環(huán)境。Maven 開源項目，這是一個通過信息描述來管理項目的構建、報告和文檔的一個開源的管理工具。jEdit 開源項目，這是一個跨平臺的文本編輯器。google－guice 是一個輕量級的依賴注入容器。folly 是一個c＋＋組件庫，包含在Facebook 上廣泛使用的各種核心庫組件。本文算法主要是針對java 和c＋＋代碼文件變更的分析，其中代碼文件數(shù)量約為實際文件數(shù)的60%，同時去掉一些只是更改注釋代碼文件，有效文件約為實際文件的50%，有效提交次數(shù)也大大降低，由于一個代碼文件可能提交了多次，所以本文中一個實驗數(shù)據(jù)為一文件的某次提交記錄。

表1 項目概況Tab.1 Project overview

4.2.2 語句相似性判斷閾值的選擇

在Hunk 內(nèi)語句間相似對比時，通過設置語句的相似閾值，避免對不相似語句和完全相同語句的對比分析，只對較為相似的語句組進行后續(xù)的差異分析，進一步提高算法的效率。本文設相似度閾值SIM，表示語句間相似程度，閾值越大，要求的相似度程度就越高。隨機的抽取開源項目中一些有效數(shù)據(jù)為實驗數(shù)據(jù)，分別設置閾值SIM為0.35、0.5、0.65、0.8，得到的差異結果準確率見表2。

表2 不同閾值SIM 結果Tab.2 Different threshold SIM results

根據(jù)表2 結果，當閾值SIM為0.35時，判斷語句為相似語句的標準較低，會導致一些無變更關系的語句也被判定為相似語句，造成差異誤區(qū)；而當閾值SIM為0.8時，判斷語句的標準較高，會使一些變更較大的語句沒被判定相似語句，進而差異結果不盡合理；所以當閾值SIM為0.5時，語句間相似比較結果更加合理，差異結果的正確率為最優(yōu)，因此后續(xù)實驗閾值SIM為0.5。

4.2.3 實驗結果

表3為Kdiff3、Beyonce Compared 4、和HunkDiff工具對5 個開源項目中各100 條有效數(shù)據(jù)的差異分析結果，工具HunkDiff 的差異分析結果的正確率平均在85%左右，相比其它工具，極大提高了差異識別的準確率。本文工具不僅較好的實現(xiàn)其它差異工具基本能夠識別的差異問題，還較好的解決了當前存在的語句、Token 失配問題。

表3 Kdiff3、Beyonce Compared 4、HunkDiff 差異分析結果Tab.3 Kdiff3、Beyonce Compared 4、HunkDiff analysis results

對于上述Kdiff3、Beyonce Compared 4 工具差異分析準確的數(shù)據(jù)，HunkDiff 工具基本也能實現(xiàn)對其差異分析；對差異分析不準確的數(shù)據(jù)，應用提出的算法工具對其進行了分析，分析結果見表4。對當前工具差異不準確數(shù)據(jù)集的差異分析正確率平均為70%以上，有效的克服了現(xiàn)有工具存在的差異不合理問題。

表4 HunkDiff 分析結果Tab.4 HunkDiff analysis results

5 結束語

針對當前Hunk 內(nèi)二次差異化算法存在的失配問題，提出了一種基于Token 的二次差異化算法，通過文本行向語句行的映射和語句間的相似性匹配，解決了語句失配的現(xiàn)象。對于更新的語句，采用基于Token 的最長公共子序列算法，獲取內(nèi)部差異的Token 集，克服了Token 被拆分的問題。該算法當前采用Java 語言實現(xiàn)，并設計了一個HunkDiff 工具對結果進行展示。通過在5 個開源項目的數(shù)據(jù)集上對該工具進行了實驗驗證，表明了該差異分析算法的可行性。該工具能夠幫助軟件開發(fā)者與測試者分析代碼，及時發(fā)現(xiàn)并解決一定的軟件開發(fā)、維護以及重構活動等問題。本文算法還存在得到的Hunk 不準確和多個最長公共子序列的部分問題，后續(xù)工作需進一步解決這方面問題，繼續(xù)提高差異分析準確率，推廣其到其他語言開源項目中的差異分析。