语句包裹模式的识别和分类

于永胜 杨春花

摘要：软件演化过程中会产生大量变更代码，对变更代码的识别有利于变更理解。其中普遍存在的把一个语句或语句序列移动到一个或多个不同的语法实体中的变更行为，对于这种语句包裹模式的识别和分类，提出了基于代码变更块和抽象语法树的语句包裹模式识别分类算法。首先从变更前后版本2个文件中筛选出代码变更块，根据语句包裹模式的特征找到候选代码变更块，再建立抽象语法树，通过语法分析找到代码变更块中存在的语句包裹模式并对其进行分类。该算法在4个开源项目中进行了实验验证，实验结果表明该算法对语句包裹模式的识别具有较高的准确率。

关键词： 语句包裹模式; 软件演化; 抽象语法树; 代码变更块

【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 引 言

软件版本控制系统记录着软件开发过程中的每个细节以及不同时期的不同版本，软件版本控制系统每天都会产生大量的变更代码，理解变更代码可以使软件日常维护和功能添加变得更加容易。理解软件变更已经成为软件开发人员日常开发和维护的基本要求。

在大量软件变更代码中存在对软件的重构、错误修复以及功能添加。重构是在不改变软件外在行为的前提下，改进软件的内部结构，使软件更易于维护和功能的添加。Fowler[1]在其著作中详细介绍了重构模型，其核心是一个全面的重构目录。变更代码中也存在对代码的错误修复。关于错误报告方面的研究有：Zhang等人[2]对Bugzilla上的错误报告进行了实证研究，并指出了进行错误报告分析时可能存在的问题;童燕翔[3]去除了bug report中的非修正性报告并提出了自动化缺陷定位方法;关于错误修复的识别方面的研究有：Eshkevari等人[4]提出了沿4个正交维度的标识符重命名分类方法，并实现了标识符重命名的识别和分类;Kawrykow等人[5]开发了一种工具支持的技术，用于检测软件系统的修订历史记录中不必要的代码修改;Kim等人[6]通过分析错误修复的历史记录开发了错误修复存储器，并提出了一种使用错误修复存储器的错误发现算法;关于错误预测方面的研究有： 原子等人[7]提出了语句级的缺陷预测方法，揭示了变更易于引入缺陷的因素;刘望舒等人[8]針对挖掘软件历史仓库过程中程序模块类型标记和软件度量时产生的噪声，提出一种可容忍噪声的特征选择框架FECS。

软件变更代码中掺杂着大量的对软件的重构、错误修复和功能添加的代码，对软件变更代码中变更模式的提取有利于对软件变更的理解。在对软件变更进行研究后，接着又研究了把一个语句或语句序列移动到一个或多个不同的语法实体中的语句包裹模式。Pan等人[9]在其著作中从7个开源项目的配置管理存储库中，使用错误修复程序更改所涉及的语法组件和源代码上下文定义了27个可自动提取的错误修复模式。但是其著作对错误修复模式的研究并没有完全涵盖语句包裹模式所包含的变更类型，因此还需要对语句包裹模式做进一步的研究。

1 语句包裹模式的识别和分类

1.1 代码变更块

代码变更块（hunk）是由代码变更前后版本之间的变更代码构成的，本文通过基于文本的方法获取代码变更块，图1中的代码变更块取自数据仓库jEdit中KeymapImpl.java文件的一次提交。在图1所示的代码变更块中，左边页码从第106～107行前面带减号的代码是代码变更过程中从原文件中删除的代码，右边页码从第106～111行前面带加号的代码是代码变更后新版本文件中增加的代码。

1.2 抽象语法树

抽象语法树抽象地表示了源代码的语法结构，抽象语法树通过将源代码中的每一种结构用节点表示来表现编程语言的语法结构，而真实语法中的每一个细节并没有包含在抽象语法树中，比如嵌套的括号在抽象语法树中就没有以节点的形式表现出来，对于语句包裹模式的研究需要对代码变更文件的抽象语法树进行分析。

1.3 语句包裹模式的识别和分类

1.3.1 语句包裹模式

语句包裹模式所表示的代码变更行为是把一个语句或语句序列移动到一个或多个不同的语法实体中，这个语法实体是一个结构化的语句，语法实体包括If、Try、For、Switch、Synchronized、While、Labeled和Do。语句包裹模式所表示的代码变更行为是将一个语句或语句序列移动到一个或多个结构化语句中，这种结构化语句是这个语句或语句序列在被执行时需要满足的条件，是对代码原文件的错误修复。

在图2所示的语句包裹模式hunk实例取自数据仓库jEdit中文件Gutter.java的一次提交中，图2中左边页码第128行是从原文件中删除的代码，右侧页码从128～129行是代码变更过程中增加的代码，第128行删除的代码和第129行增加的代码是非常相似的，图2中将一行代码移动到了一个If语法实体中，发生了语句包裹。对于一个语句或语句序列移动到Try、For、Switch、Synchronized、While、Labeled和Do这七种语法实体中的变更行为也都属于语句包裹模式。

在图3所示的语句包裹模式的hunk实例取自数据仓库jEdit中文件EditPane.java的一次提交，第1236行删除的代码和第1214行增加的代码是非常相似的，就是将第1236行代码从一个If语法实体中移动了出来，发生了逆向的语句包裹，属于语句包裹模式。

1.3.2 语句包裹模式的识别和分类

假设存在ha和hd分别为hunk中增加的代码和删除的代码，la和ld分别为hunk中增加代码和删除代码的相似部分，则pr和pl分别为la和ld的所有父节点，cr和cl分别为la和ld在hunk内的所有父节点，mr和ml分别是la和ld父节点中的第一个方法节点，当这次变更属于语句包裹模式时，则需要满足以下条件：

（1）语句包裹模式的候选hunk中需要存在语句或语句序列移动到一个或多个语法实体中，这些移动的语句或语句序列是相似的，所以hunk中需要存在相似部分。

（2）hunk中相似部分的父节点中第一个方法节点mr和ml的方法名是相同的。对于la和ld在hunk内的父节点cr和cl，需要满足一个为空集且另一个不为空集的条件，且la和ld的所有父节点pr和pl不能完全相同。

判断此次变更属于语句包裹模式后，当cr不为空且cl为空时，可以判断变更属于正向的语句包裹模式，并根据语法实体的种类对语句包裹模式进行分类，这里的语法实体就是cr的第一个节点。当cl不为空且cr为空时，可以判断为逆向的语句包裹模式，将cl的第一个节点作为语法实体，并根据这里的语法实体对语句包裹模式进行分类。

1.3.3 根据代码相似度识别hunk中的代码移动

在图2语句包裹模式的候选hunk中，从原版本文件中删除的代码是左侧页码的第128行，代码变更后增加的代码是右侧页码的第128～129行，原版本文件中第128行代碼在代码变更后移动到了新版本文件的第129行，这些移动的语句或语句序列具有很高的相似度，因此要识别这样的代码移动需要对变更代码进行相似度识别。

1.3.4 通过抽象语法树识别语句包裹模式

从语句包裹模式候选hunk中找到移动的语句或语句序列后，需要确定hunk相似部分la和ld的父节点pr和pl中的第一个方法节点mr和ml的方法名需要相同，还需要确定hunk和相似部分之间存在一个或多个语法实体，也就是la和ld在hunk内的父节点cr和cl需要一个为空集一个不为空集，la和ld的所有父节点pr和pl不能完全相同。

首先获取la和ld的行范围ra和rd，获取hunk增加代码和删除代码ha和hd的行范围ka和kd，遍历代码变更前后版本的两个文件的语法树，找到行范围分别包含ra和rd的父节点pr和pl，找到行范围位于ra和ka之间的父节点cr，找到行范围位于rd和kd之间的父节点cl，分别从pr和pl中找到la和ld的第一个方法节点mr和ml，判断mr和ml是否是同名函数节点，判断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的抽象语法树的根节点tl和tr，第7～8行得到hunk的相似部分的集合La和Ld的行范围集合Ra和Rd，第9～10行通过遍历filer和filel的语法树得到相似部分的所有父节点集合Pr和Pl、在hunk内的父节点的集合Cr和Cl以及相似部分在父节点Pr和Pl中每一个节点的分支的集合Br和Bl，第11～13行分别找到pr和pl中相似部分的第一个满足是方法节点的父节点，第14行判断2个方法父节点是否满足方法名不相同的条件，第15行判断相似部分在hunk内的父节点cl和cr是否满足一个为空集、另一个不为空集的条件，第16～27行判断相似部分在文件中的所有父节点pl和pr是否满足不完全相同的条件。算法的第17～21行中，当cl和cr满足cl不为空集而cr为空集时，将cl中第一个节点作为语句包裹模式的语法实体存入en中，en存入En，并将该语法实体的相应分支bl存入eb中，eb存入Eb。第22～31行中，当cl为空集而cr不为空集时，将cr的第一个父节点作为语句包裹模式的语法实体存入en，en存入En，并将该语法实体的相应分支br存入eb中，eb存入Eb。

上述算法中第9～10行使用了函数ergodicAST，下面是对函数ergodicAST的描述：函数ergodicAST的输入为文件hunk集H的行范围的集合K，hunk集中相似部分L的行范围的集合R，以及文件的语法树的根节点t。输出为文件中相似部分集合的所有父节点的集合P，相似部分在hunk集内的父节点的集合C，以及相似部分在父节点集合P中每一个节点的分支的集合B。

算法2 ergodicAST算法

输入：文件hunk集H的行范围K，相似部分集L的行范围R以及文件的语法树的根节点t

输出：文件hunk集相似部分的父节点集合P，相似部分在hunk集内的父节点集合C，相似部分在父节点集合P中每个节点的分支的集合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行將文件语法树中相似部分的第一个父节点存入p中，第6～9行判断该节点是否也在hunk内，如果在hunk内就将其存入c中，第10～16行获取n节点的分支集合Bz，并将包含相似部分的分支存入b中，第17～24行遍历分支内的节点，将包含相似部分的节点存入N，若N不为空集，则继续遍历文件的语法树。第25～28行将p、c和b分别存入P、C和B中。

2 算法的实现和验证

本文实验使用了Java编程语言、基于文本的差异化分析工具Gnu Diff[10]以及eclipse jdt parser工具。首先使用了基于文本的差异化分析工具Gnu Differ（http：//www.gnu.org/software/diffutils）获取代码变更前后版本文件的代码变更块hunk，再使用eclipse jdt parser工具分析代码变更前后版本文件的抽象语法树。并从4个开源项目中获取了数据集用于实验研究。

2.1 数据获取

本实验使用了从4个开源项目中获取的数据集，下面是对本实验使用的数据集的介绍。

（1）[JP4]开源项目jEdit（http：//sourceforge.net/project/jedit），该开源项目是一个跨平台的文本编辑器。

（2）开源项目eclipseJDTCore（http：//www.eclipse.org/downloads/eclipse-packages/），该开源项目是一个面向Java的集成开发环境。

（3）开源项目maven（http：//maven.apache.org/），该开源项目是通过信息描述来管理项目构建、报告和文档的管理工具。

（4）开源项目google-guice（https：//github.com/apress/google-guice），该开源项目是一个轻量级的依赖注入容器。

表1是描述了从4个开源项目中获取的数据集的项目名称、获取时间段、提交总数、文件总数以及提交和文件的匹配数commit_file的信息。

2.2 实验结果及分析

本文中分别从4个开源项目的数据集中人工抽取了语句包裹模式变更集，并使用本文算法在人工抽取的变更集上进行了实验验证，实验结果见表2。

从实验结果可以看出，本文算法在人工抽取的语句包裹模式的变更集中的识别率在86%～90%之间波动。

将本文算法在4个开源项目的数据仓库中进行实验验证后，从实验结果所有版本中抽取了10%进行人工检测，对从实验结果中抽取的10%进行人工检测后的验证结果见表3。

本文算法对4个开源项目数据仓库进行了语句包裹模式识别，对从识别结果所有版本中抽取的10%进行人工检测后，检测结果的准确率在95%～98%之间波动。

本文算法在4个开源项目数据仓库上进行实验得到实验结果集后，从结果集中抽取每一种语句包裹模式的变更版本集的10%进行人工检测，实验结果见表4。

对从实验结果集中每种语句包裹模式变更版本集中抽取10%并进行人工检测后，实验结果显示准确率在95%～97%之间波动。

对人工抽取的变更集的识别率以及对从结果集中抽取实例进行人工验证的准确率未能达到100%的原因，在于语句包裹粒度较大的语句包裹模式变更被Gnu Diff划分到了多个hunk中，这种情况降低了本文算法识别结果的准确度，将来可以为大粒度语句包裹模式变更提供hunk合并功能，以提高对于这种情况的识别准确率。

3 结束语

本文通过对代码变更的研究，介绍了代码变更中普遍存在的语句包裹模式，提出了基于代码变更块和抽象语法树的语句包裹模式识别分类算法，在4个开源项目数据仓库上进行实验验证后，实验结果证明本文算法对于语句包裹模式的识别具有较高的准确率。对于存在代码移动的提炼函数（Extract Method）和提炼类（Extract Class）等重构模式，本文提出的基于代码变更块和抽象语法树的算法也能对其进行识别。在将来的研究中，需要为大粒度语句包裹模式变更提供hunk合并功能。并将该算法在更多数据集上进行实验验证的基础上将其用于其他重构模式的识别。

参考文献

[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]. 南京：南京航空航天大学，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]原子，于莉莉，劉超. 面向细粒度源代码变更的缺陷预测方法[J]. 软件学报，2014，25（11）：2499.

[8]刘望舒，陈翔，顾庆，等. 一种面向软件缺陷预测的可容忍噪声的特征选择框架[J]. 计算机学报，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.