基于代码克隆检测的抽取方法重构模式识别

张志浩 杨春花

(齐鲁工业大学(山东省科学院)计算机科学与技术学院 山东 济南 250000)

0 引 言

代码重构[1]是指使用一系列重构手法，在不改变软件可观察行为的前提下，调整其结构，提高其可理解性、可维护性和可扩展性，降低其修改成本，是一种在结构层次上的代码整理技术。

在现代软件开发的过程中，代码变更包括特征增加、修复bug以及代码重构等。这些不同类型的变更代码混合在一起使得阅读和理解代码变更趋于困难，如果将重构的代码变更与其他变更进行隔离，将有利于阅读和理解。

为了实现代码重构与其他变更的隔离，应该设法对代码重构模式进行自动识别。当前，国内外学者对软件重构识别进行了深入的研究探索。主要相关的研究有：Werβgerber等[2]提出了基于签名分析的方法;Prete等[3]开发了REF-FINDER;Fokaefs等[4]开发了一种eclipse插件，能对一种或者几种重构模式进行识别;钟林辉等[5]提出了一种基于版本的多重软件重构自动检测技术；刘洋[6]提出了一种可以识别函数抽取的方法。但上述算法面对变更的文本时忽视了形式不同而含义相似的情况，比如说一些变更仅仅是变量名称改变，或者仅仅是字母大小写变换，含义并没有变。

克隆代码又称为重复代码，一般指存在于程序代码中的相似或者相同的代码段，对它的检测技术称为代码克隆检测技术。当前对克隆代码检测的技术已经很成熟了，刘复星[7]提出一种基于深度学习的代码克隆检测方法，汪敏[8]提出一种基于依赖图的代码克隆检测方法，王杰[9]提出一种基于序列匹配和字节码的代码克隆检测方法，林蝉[10]提出一种基于索引的分布式代码克隆检测方法。本文提出基于代码克隆检测对重构模式进行识别，并对一种常用的重构模式——抽取方法的识别算法进行了设计与实现。此算法以代码变更块hunk为单位，用代码克隆检测筛选那些具有代码克隆关系的hunk集，然后用语法分析判定两个候选hunk之间是否属于抽取方法模式。该算法在4个开源项目上进行了验证。

1 抽取方法重构模式的识别

1.1 变更代码块(hunk)

对代码变更的抽取方法分为两类：文本型差异化代码分析和树型差异化分析。

Gnu Differ[11]等文本型差异化代码分析比较两个版本的源文件，通过比较它们文本上的差异，得出变更集；Change Distiller[12]等树形差异化分析通过比较两个版本的源文件所对应的抽象语法树之间的差异，得出变更集。

变更代码块(hunk)是文本型差异化代码分析方法输出的基本单位。一个hunk由添加的行和删除的行构成，一般前后还各有三行未变动的上下文行。图1列出了两个hunk，它们属于项目jEdit版本9dd86c7中View.java文件的变更集。以第一个hunk为例，该文件老版本中的第607～620行是删除的行，行首为减号；新版中的第607是增加的行，行首为加号，该hunk之前的604～606行是上下文行，同理后面的三行也是上下文行。第二个hunk只含有增加的行。

图1 hunk示例

1.2 抽取方法模式

抽取方法模式经常出现在代码重构中。当遇见一个过长的函数或者一段比较复杂、需要添加注释才能易于理解的代码时，可以采取这种重构模式，将这一段代码放到一个独立的函数中去。把大型函数分解为几个小粒度的函数，并使用易于理解的名称去命名它，这是抽取方法的一般原因和过程。

在图1所示的代码变更中，hunk1中移走的代码(行607～620)属于方法processKeyEvent，这些代码移动到了hunk2中的新增的方法processKeyEventKeyStrokeHandling中。而且在hunk1中被移走的代码处，有对新增方法的调用语句(行607)。因此，这是一种典型的抽取方法重构。

1.3 抽取方法模式的识别

抽取方法重构模式的代码变更具有如下两个特点：

1) 原代码中的某方法A中的部分代码转移到了变更后代码中的某个新增方法B；

2) 变更后代码中在方法A中移走的代码处有对新增方法B的调用。

因此，对这两个特征进行判断是识别抽取方法模式的关键。下面分别阐述这两个特点的判断方法。

1.3.1基于克隆检测对方法的代码移动进行判断

设A中移走的代码行存在于某个hunk(设为h1)的删除行中，B中新增的代码行存在于某个hunk(设为h2)的添加行中，h1和h2可以相同，也可不同。

因此，第一个特点可以通过检测h1的删除行和h2的添加行之间的克隆关系来判断。

为方便检测，我们将每个hunk分裂为两个子hunk：lefthunk和righthunk，前者存放hunk的删除行，后者存放hunk的添加行。分裂后的两个hunk保存原hunk的id，用于后期使用。例如，图1的hunk1分裂后变为如图2所示的两个hunk：lefthunk和righthunk。

图2 hunk的分裂

因此，h1的删除行和h2的添加行之间的克隆关系检测转为对分裂后的两个hunk(即h1.lefthunk和h2.righthunk)之间的克隆关系的检测。

1.3.2对新增方法调用的判断

设hi.lefthunk和hj.righthunk之间存在克隆关系，则需要在hi中检测是否存在一个新增的方法调用，它调用了hj中的新增代码行所属的方法。

因此，首先要获得hj之中新增代码行所属的方法名(设为B)，然后获得hi之中删除的代码行所属的方法名(设为A)，最后在hi新增的代码行中查找对方法B的调用。

例如图1中，在确定了hunk1和hunk2存在克隆关系之后，需要获得hunk2中新增的方法名processKeyEventKeyStrokeHandling()，然后在hunk1中取被抽取代码行的方法名，并检测hunk1中的新增代码行中是否存在语句或表达式调用了方法processKeyEventKeyStrokeHandling()。

在hunk中查找方法名及方法调用语句或方法调用表达式比较困难，因为hunk是文本，不携带语法信息,因此，我们采用抽象语法树来辅助实现。具体的做法如下：

(1) 对变更前后两个版本的源文件，分别生成其抽象语法树，然后获取每棵树中的所有方法节点。根据方法节点的行范围与hunk的行范围进行匹配来查找hunk中存在的方法名。此过程可以查找方法名A和B。

(2) 在定位到方法A后，取变更后版本的抽象语法树中的该方法节点，对其所有子节点进行查找，确定是否存在一个方法调用节点，该节点存在于hi的新增行范围中，且调用的方法名为B。

1.4 算 法

此算法输入变更前后两个版本的源文件filel和filer，输出存在抽取方法模式的hunk元组的集合R={|h1,h2∈H}，其中h1、h2是两个hunk，且h1的删除行和h2的添加行之间存在方法抽取重构模式。算法的伪代码如下：

输入:变更前后两个版本的源文件filel和filer

输出:存在抽取方法模式的hunk元组的集合R

1H←getHunks(filel,filer)

2 (H1,H2)←split(H)

3Hsim←∅

4 for eachh1∈H1

5 for eachh2∈H2

6 ifcheckSimilar(h1,h2)

7Hsim←Hsim∪(h1,h2)

8 end if

9 end for

10 end for

11tl←createAST(filel)

12tr←createAST(filer)

13M1←getAllMethods(tl)

14M2←getAllMethods(tr)

15 for each(h1,h2)∈Hsim

16 ifcheckMethodInvoc(M1,M2,h1,h2)

（5）微课为主要形式建设教学资源。本课程属于操作类课程，不仅有知识点，还有很多技能点，技能点的讲解较为困难，因此对于知识点主要采用录屏的方式，技能点主要采用拍摄操作微课的方式，着重讲解操作要领和注意事项。同时制作动画来配合微课，使技能点的讲解更加清晰明了。

17R←R∪(h1,h2)

18 end if

19 end for

算法第1行通过文本型差异分析方法获取hunk集H；第2行将H按照删除行和增加行分裂为两个集合H1和H2，H1中的每个hunk只含有删除行，H2中的每个hunk只含有添加行；接下来在第4～10行检测存在克隆关系的hunk元组，其中checkSimilar(h1,h2)函数用来检测h1和h2的克隆关系；第11～14行得到两个版本源文件分别对应的抽象语法树tl和tr，并从中抽取其中的方法集M1和M2；最后第15～19行实现对候选的hunk元组进行判断，确定是否在h1中存在对h2中新增方法的调用，其中函数checkMethodInvoc(M1,M2,h1,h2)实现此判断，其具体流程在上一节已进行描述，在此不再赘述。

2 算法的实现及验证

采用Java语言实现本文算法，它读入两个连续版本的Java源文件，识别其中的抽取方法模式。在当前实现中，采用面向行的文本差异化分析工具Gun Differ来获取hunk集，采用代码克隆检测工具simian实现对候选hunk集的检测。simian可以识别Java、C、C++、Ruby、JSP等多种语言的源代码和纯文本文件中的相似代码。即使两个代码块略有不同，例如变量名称、字符大小写、修饰符、花括号、标识符、数字、字符串略有改变，simian依旧可以识别。最后，采用eclipse jdt parser来获取源文件的抽象语法树。

2.1 数据来源

获取了4个开源项目的数据集用于对算法的验证：

(1) eclipseJDTCore开源项目，它是一个基于Java的IDE，此次实验获取2001/06/23-2013/10/16时间段的更新数据。

(2) maven开源项目，它是一个通过信息描述来管理项目的构建、报告和文档的一个开源的管理工具，此次实验获取了2003/09/02-2014/01/29时间段的更新数据。

(3) jEdit是一个跨平台的文本编辑器，此次实验获取了1998/09/27-2012/08/08时间段的更新数据。

(4) google_guice是一个轻量级的依赖注入容器。数据的获取时间段为:2006/08/23-2013/12/12。

2.2 simian参数与阈值设定

在使用本方法检测抽取方法模式的时候，对simian工具进行了包容度的设置，设置忽略了变量名字的改变、字符串的改变、数字的改变、确认符的改变、子类名的改变，以上这些改变依然会被认为是克隆代码。

同时simian工具可以设置阈值，阈值表示simian工具对待判定代码判断为克隆代码的严格程度，阈值越大，就越严格。使用一个名为dropwizard工具的项目作为测试项目，从1到9调整simian阈值，得到的查全率和查准率如表1所示。

表1 不同simian阈值对应的结果

图3使用折线图的形式更加直观地描绘出了阈值对查准率和查全率的影响，其中查准率和查全率在纵轴表示，simian阈值在横轴表示。可以看出查准率随阈值的增大而增大，而查全率随阈值的增大而减小，在阈值为5时达到均衡，因此以下实验取阈值为5。

图3 在不同阈值下的查准率和查全率

2.3 实验结果和分析

在simian阈值取5的条件下，对4个开源项目中的数据集进行了实验，表2列出了各个项目检测到的方法抽取模式的个数并以人工检测结果作为基准进行准确率判断，计算出其查全率和查准率。可以看到其查全率在75%～88%范围内，查准率则在71%～82%之间波动。

表2 实验结果

3 结 语

本文提出了一种基于克隆代码检测的方法对存在抽取方法重构模式的hunk元组进行自动识别的算法，并在4个开源项目上进行实验，结果表明其具有较高的准确率。基于克隆代码检测的方法可应用到存在代码移动或复制的其他重构模式，如移动方法、抽取类等的识别。本文的后续工作包括继续提升算法的准确率、在更多的开源项目上验证其有效性以及推广应用到其他重构模式的识别。