公鑫，楊春花

（齊魯工業(yè)大學(xué)（山東省科學(xué)院）計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，濟(jì)南 250300）

0 引言

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

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

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

圖1 Hunk 例子Fig.1 Hunk example

圖2 Beyond Compare 4 分析結(jié)果Fig.2 Beyond Compare 4 analysis results

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

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

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

文本差異化分析算法將源代碼看成一個(gè)字符串，因此代碼修改前后2 個(gè)版本之間的比較就變成了2 個(gè)字符串間的比較，一般基于最長(zhǎng)公共子序列算法實(shí)現(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等工具提供對(duì)Hunk 內(nèi)的二次差異化分析，獲得Hunk 內(nèi)部的差異文本。文本差異化分析算法可以分析各種類型的源代碼文件，而且效率高，因此在實(shí)踐中被廣泛采用［5－6］。

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

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

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

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

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

2.1 失配問題的占比

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

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

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

2.2 問題分析

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

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

圖4 Kdiff3 分析結(jié)果Fig.4 Kdiff3 analysis results

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

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

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

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

3.1 算法架構(gòu)

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

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

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

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

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

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

3.2 算法

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

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

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

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

該算法的步驟解釋如下：

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

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

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

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

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

算法1HunkDiff

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

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

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

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

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

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

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

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

算法2matching

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

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

3.4 示例

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

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

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

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

4.1 算法實(shí)現(xiàn)

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

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

圖6 HunkDiff 分析結(jié)果Fig.6 HunkDiff analysis results

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

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

4.2 算法驗(yàn)證

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

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

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

表1 項(xiàng)目概況Tab.1 Project overview

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

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

表2 不同閾值SIM 結(jié)果Tab.2 Different threshold SIM results

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

4.2.3 實(shí)驗(yàn)結(jié)果

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

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

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

表4 HunkDiff 分析結(jié)果Tab.4 HunkDiff analysis results

5 結(jié)束語

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