APP下载

基于代码变更块和抽象语法树的两种重构模式识别

2019-07-01张志浩杨春花

智能计算机与应用 2019年3期

张志浩 杨春花

摘 要:内联函数(Inline method)和替换算法(Substitute algorithm)是2种在代码重构中常用的重构手法,本文提出一种基于代码变更块和抽象语法树的重构模式识别算法,首先筛选出变更前后2个文件的代码变更块,找到可能属于这2种重构模式的代码变更块,再建立抽象语法樹对这些变更块中的代码进行准确的语法分析,对其是否属于此2种模式进行判定。该算法在4个开源项目上进行了实验验证,表明了其具有较高的准确率。

关键词: 重构模式; 抽象语法树; 代码变更块; 内联函数; 替换算法

文章编号: 2095-2163(2019)03-0146-05 中图分类号: TP311.5 文献标志码: A

0 引 言

代码重构[1]是在软件开发的过程中一种常用的在结构层次上的代码整理手段,其能在不改变软件可观察行为的前提下,对软件的结构进行调整,提高其可拓展性、可维护性、可读性,从而提升其质量,并降低其维护成本。

目前对重构的研究主要集中在代码自动重构这一方面,相关研究主要有:使用抽象语法树和静态代码分析的克隆代码自重构方法[2]、基于K-近邻的C克隆代码重构方法[3]、单例模式导向的源代码自动重构研究[4]、面向Java锁机制的字节码自动重构框架[5]等等。

重构模式识别指的是对比变更前原代码和变更后代码以寻找符合某种重构模式代码段。在代码更新中,往往包含着对老版本代码的bug的修复、功能的添加以及重构的代码变更,这3种种类各异的代码变更方式的掺杂增加了阅读其代码、理解其内容的难度,若能对其中的重构代码进行自动识别,则可使重构与其他种类的变更相互分离,利于代码的阅读和理解。对代码重构模式的识别的研究也在继续深入之中 Fokaefs等人[6]开发了一种eclipse插件、Weissgerber等人[7]提出了基于签名分析的方法、Prete等人[8]开发了REF-FINDER,这种工具可以对几种重构模式进行识别,刘阳等人[9]提出了一种方法可以识别函数抽取。钟林辉等人[10]提出了一种基于版本的多重软件重构自动检测技术。以上研究中没有涉及到有关内联函数和替换算法这2种重构模式的识别,本文即对此实现了相应的识别算法。

1 内联函数与替换算法重构模式的识别

1.1 变更代码块

目前对代码变更的提取方法有2种。一种是语法分析法,通过对比2个文本的抽象语法树获取差异部分,另一种基于文本差异的对比方法,直接比较目标文本的差异,获取差异部分。

本文考虑到算法效率,采用第二种方式,通过基于文本差异的对比方法获取其基本输出单位变更代码块(hunk),一个hunk可以由删除行和添加行这2个部分组成,也可以只包含删除行部分或添加行部分,研究中列出了同属于项目google_guice(https://github.com/google/guice/)的3个hunk即如图1所示。其中,hunk1中的67~76行是删除行,行首为减号,71~73行为添加行,行首为加号;hunk2只包含添加行;hunk3只包括删除行。

1.2 抽象语法树

抽象语法树是在编程语言源代码的翻译和编译过程中使用的一种中间表示形式,其结构类似于树状结构,树上的每一个节点都表示源代码中的一种结构,但是抽象语法树的节点并不是对应真实语法的每一个细节,比如对于嵌套括号等没有对应的节点,故称为抽象语法树。利用抽象语法树可以对代码进行一定的语法分析。

1.3 内联函数重构模式的识别

1.3.1 内联函数模式

内联函数模式在代码重构中经常出现,当遇见某个函数的内部代码和其函数名同样清晰易读的小粒度函数时,可以使用这个重构模式。一般情况下,其运行过程是将这一个或几个小粒度函数的函数体提取到对此函数的调用语句处,并删除调用语句和此小粒度原函数。

继而,研究中列出了2个hunk如图2所示,且均属于google_guice(https://github.com/google/guice/)项目中版本为315ee3fe10的InjectorImpl.java文件,hunk4中(729~734行)中的injectMembers( )函数整体被移除,函数体被转移到hunk5的(756~758行)call( )函数中,并且call( )函数中的对injectMembers()函数的引用(776行)也被移除,这就是一种典型的内联函数重构模式。

1.3.2 内联函数模式识别

假设原代码中有A,B两个函数,设为A1,B1,变更后代码中也有A函数,设为Ar,若此次变更为内联函数重构模式,则此代码所具有特点可概述为:

(1)B1函数的函数体代码被添加到变更后代码中的Ar函数里,之后B1函数被整体移除。

(2)A1中有对B1的引用,但Ar函数中没有对B1函数的引用语句。

对这2个特点的判断是识别内联函数模式的重点,为了方便起见,称可能符合上述2个特点的函数,如A1,Ar为A型节点,可能符合上述2个特点的函数,如B1为B型节点,下文对这2个特点的识别方法分别进行研究阐述。

1.3.3 基于相似度检测对函数级代码移动进行判断

由于要单独使用到hunk中的删除行或添加行,方便起见,按照添加行和删除行将各个hunk分为2个部分,即添加部分(addpart)和删除部分(delpart),如图3所示,图1中的hunk1拆分为addpart和delpart。

第一个特点本质是检测是否有函数级代码的移动,设B1函数包含在某个hunk(设为h1)的删除行中,而Ar中增加的代码则包含在某个hunk(设为h2)的添加行中,因此对第一个特点的判断就是判断h1中的删除行和h2中的添加行是否有相似关系,即h1.delpart是否和h2.addpart存在相似关系。

1.3.4 基于抽象语法树对函数引用情况进行判断

对第二个特点的判断需要考察A1函数代码中是否有对B1函数的引用语句,以及Ar函数中是否已经移除对B1函数的引用语句,对此研究过程可阐释如下。

(1)在符合第一个特点的情况下,对原代码文件和变更后代码文件分别生成抽象语法树,并且获取2棵语法树的所有函数节点(Method node),函数节点有行范围,h1.delpart和h2.addpart同样有行范围,对比匹配两者的行范围可以找出B1和Ar函数节点,因为函数节点包含函数头的所有信息,故可获取Ar函数节点的函数名,并根据此函数名遍历原代码文件的所有函数节点,找到同名同参数的A1函数节点。

(2)遍历Ar函数节点的所有子节点,确定是否存在一个对B1的方法调用节点,并于A1函数节点中确认此方法调用节点是否已经被删除。

1.3.5 内联函数重构模式识别算法

此算法输入2个版本的源文件filel和filer与第一步输出hunk集合H={},其中h1的删除部分和h2的添加部分有相似关系,输出存在内联函数模式的函数节点(Method node)集合O={},其中n1,n2是filel的A型和B型节点,n3是filer的A型节点,n1, n2, n3之间存在内联函数重构模式关系。算法的伪代码详见如下。

输入:2个版本的源文件filel和filer与第一步输出的hunk集合H

输出:存在内联函数模式的函数节点(Method node)集合O

(Hl,Hr)←getAllHunks(filel, filer)

H←filter(Hl,Hr)

(Hd, Ha)←split(H)

Rd←gethunkrange(Hd)

Ra←gethunkrange(Ha)

tl←generateAST(filel)

tr←generateAST(filer)

M1←getAllMethodNodes(tl)

M2←getAllMethodNodes(tr)

Mdel←, Madd←

for each rd∈Rd, ra∈Ra

for each m1∈M1, m2∈M2

rm1←getMethodRange(m1)

rm2←getMethodRange(m2)

if rm1rd

Mdel←Mdel∪m1

end if

if  rarm2

Madd←Madd∪m2

end if

end for

end for

MA←getLeftAMethod(Madd)

for each (madd, mdel, mA)∈(Madd, Mdel, MA)

if  checkInvoc((madd, mdel, mA))

O←O∪(madd, mdel, mA)

end if

end for

算法第1行使用getAllHunks()函數获取2个版本的源文件filel,filer的所有hunk集合(Hl, Hr);算法第2行使用filter()函数选取Hl中的hunk的删除部分和Hr中的hunk的添加部分相似的hunk集合H={};算法第3行使用split()函数将H中属于filel的hunk.delpart取出来放进Hd,将属于filer的hunk.addpart取出来放进Ha;第4,5行获取行范围Rd,Ra;第11~22行对Rd,Ra和M1,M2的行范围rm1,rm2进行对比匹配,挑选出Hd的行范围包含的函数节点集合Mdel的行范围和行范围包含ra的函数节点集合Madd;第23行通过getLeftAMethod()函数获取属于filel的和Madd同名函数节点集合MA;第24~28行对属于filel的A型节点mA,B型节点mdel,属于filer的A型节点madd通过checkInvoc()函数判断mA中是否有对mdel的调用语句和madd中是否已经移除对mdel的调用语句。

1.4 替换算法重构模式的识别

1.4.1 替换算法模式介绍

在对代码的更新的过程中,随着对问题有了更多的理解,或者相关代码有所改动,往往需要对某个函数进行替换,这种做法在重构模式中即可称为替换算法(Substitute algorithm)。一般情况下,其运行过程是在某个函数的函数头不变的情况下,用新函数体替换此原函数的函数体。

图4的代码来自于maven(https://github.com/apache/maven/)版本为01ae529的RemoteSnapshotMetadata.java文件,可以看到函数getExpandedVersion(Artifact artifact)的原函数体被移除(行94),被替换成了新的函数体(94~95行),这就是一个典型的替换算法重构模式实例。

1.4.2 [ZK(]基于抽象语法树和代码变更块对替换算法模式进行识别

对于替换算法模式而言,可归纳为2个特点,对此可概述为:

(1)原函数和变更后函数的函数头相同,即原函数的函数头没有发生改变。

(2)原函数的函数体和变更后函数的函数体发生了改变。

设有原文件filel变更后文件filer,先使用文本型代码差异化分析工具获取这2个文件的变更代码块集,替换算法发生在一个hunk之中,故对此hunk集的所有hunk进行筛选,筛掉只有添加部分或删除部分的hunk,获取hunk集(设为H),用同样的方法获取H的删除部分和添加部分集(设为Ha,Hd)。

使用语法树分别获取filel和filer在H中包含的函数节点Ml,Mr,若这2个节点的函数头相同,并且2个节点的函数体分别就是删除部分和添加部分,则满足替换算法模式的特点(1)。

在满足第一个特点的前提下,若Ml和Mr节点的函数体不同,则满足替换算法模式的特点(2),可以使用代码相似度检测技术进行检测,判断Ml和Mr节点的函数体是否不同。

1.4.3 算法

此算法输入变更前后2个版本的源文件filel和filer,输出存在替换算法模式的函数节点(MethodNode)元组的集合Ms={},M1,M2是2个函数节点,符合替换算法重构模式。研究给出算法的伪代码详见如下。

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

输出:存在替换算法模式的函数节点集合Ms

Hs ← getAllHunks(filel, filer)

H←

for each hs ∈Hs

if (hs.addpart≠)&&(hs.delpart≠)

H← H∪hs

end if

end for

(Hd, Ha)←split(H)

tl←createAST(filel)

tr←createAST(filer)

M1←getAllMethods(tl)

M2←getAllMethods(tr)

(Ml,Mr)←match(H,M1, M2)

Ms←

for each(ml,mr)∈(Ml,Mr)

if (!checkSimilar((ml, mr))

&&checkMethodHead((ml, mr)))

Ms← Ms∪(ml, mr)

end if

end for

算法第1行是通过文本型差异分析方法获取2个文件的所有hunk集Hs,3~7行将Hs里的所有存在添加部分和删除部分的hunk筛选出放入集合H,第8行是将H按照删除部分、还是添加部分分离为(Hd, Ha),第13行Match(H,M1, M2)函数的功能和上一算法伪代码的第11~22行的功能一致,即实现通过hunk获取相关函数节点;第15~19行实现对函数节点ml, mr函数体是否不同和对其函数头是否相同的判断,即是否是替换算法重构模式,并将符合替换算法重构模式的函数节点元组(ml,mr)放置入Ms中,其中checkSimilar()函数用于检测ml, mr函数节点的函数体是否相似,若不相似说明函数体已经被替换,本文使用编辑距离算法来计算相似度;checkMethodHead((ml, mr))函数用于检测ml, mr这2个节点的函数头是否相同,其方法是比较函数节点中的数个属性(MODIFIERS,RETURN_TYPE,NAME,PARAMETER,THROW_EXCEPTIONS)是否都相同,至此得到最终结果。

2 算法的实现及验证

本文使用Java编程语言来实现这2个算法,采用面向行的文本差异化分析工具Gun Differ(http://www.gnu.org/software/diffutils/)获取Hunk集,采用eclipse jdt parser来获取源文件的抽象语法树,在4个开源项目上进行了实验验证。研究内容具体如下。

2.1 数据来源

获取了4个开源项目的数据集用于对算法的验证,对此拟做出阐析分述如下。

(1)eclipseJDTCore(https://github.com/eclipse/eclipse.jdt.core) 开源项目,这是一个针对Java的集成开发环境,此次实验获取时间段为2001/06/23~2013/10/16的更新数据。

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

(3)jEdit(https://github.com/linzhp/jEdit-Clone),这是一个跨平台的文本编辑器,此次实验获取了时间段为1998/09/27~2012/08/08的更新数据。

(4)google_guice(https://github.com/google/guice/)是一個轻量级的依赖注入容器。数据的获取时间段为:2006/08/23~2013/12/12。

2.2 实验结果和分析

本文对来自于上述4个开源项目的数据集进行了实验,同时列出了内联函数模式检测算法所检测到的内联函数模式的个数见表1,并以人工检测的结果为基准获得了其查全率和查准率。

可以看到,内联函数识别实验结果显示查全率在70%~86%之间波动。查准率在71%~80%之间波动。

接下来,研究列出了替换算法重构模式识别算法所检测到的替换算法模式的个数见表2,同样以人工检测的结果为基准获得了其查全率和查准率。

可以看到,在替换算法模式识别结果中,对这4个开源项目的识别。实验得出,查全率在71%~80%之间波动。查准率在72%~84%之间波动。

分析可知,查全率和查准率没有达到100%的一个原因在于Gun Differ对于大粒度的函数的改动容易划分为多个hunk,使得各个hunk只包含这个大粒度函数的一部分,在算法的运行过程中被自动筛去,以后可以增加hunk合并机制,让某个大粒度函数的多个hunk合并为一个hunk,让一个hunk就能够包含此大粒度函数,从而为这2个算法所识别。

3 结束语

本文提出了基于代码变更块和抽象语法树的对内联函数和替换算法重构模式自动识别的算法,在4个开源项目上进行了实验,表明其有较高的准确率,这种基于代码变更块和抽象语法树的算法也可以对其它有着代码移动情况的代码重构模式,如移动字段(Move field)、抽取类(Extract Class)等进行识别,后续工作仍需开发出针对大粒度函数的多个hunk合并机制以提高算法的准确率,在更多的数据集上验证其有效性,进而将其应用到其它类型的重构模式识别上。

参考文献

[1] FOWLER M. 重构—改善既有代码设计[M]. 北京:中国电力出版社,2003.

[2] 于冬琦,彭鑫,赵文耘. 使用抽象语法树和静态分析的克隆代码自动重构方法[J]. 小型微型计算机系统,2009,30(9):1752-1760.

[3]  冯江辉. 基于K-最近邻的C克隆代码重构方法研究[D]. 哈尔滨:哈尔滨工业大学,2011.

[4]  刘伟,胡志刚,刘宏韬. 单例模式导向的源代码自动重构研究[J]. 小型微型计算机系统,2014,35(12):2664-2669.

[5] 张杨,张冬雯,仇晶. 面向Java锁机制的字节码自动重构框架[J]. 计算机科学,2015,42(11):84-89.

[6] FOKAEFS M,TSANTALIS N, STROULIA E, et al. Identification and application of extract class refactorings in object-oriented systems[J]. Journal of Systems and Software,2012, 85(10): 2241-2260.

[7] WEISSGERBER P, DIEHL S. Identifying refactorings from source-code changes[C]// Proceedings of the 21st IEEE/ACM International Conference on Automated Software Engineering (ASE'06). Tokyo, Japan:IEEE,2006: 231-240.

[8] PRETE K, RACHATASUMRIT N, SUDAN N, et al. Template-based reconstruction of complex refactorings[C]//ICSM '10 Proceedings of the 2010 IEEE International Conference on Software Maintenance.Washington, DC, USA :IEEE, 2010:1-10.

[9] 劉阳,刘秋荣,刘辉 . 函数抽取重构的自动检测方法[J]. 计算机科学,2015,42(12):105-107.

[10]钟林辉,黄小明,薛良波,等.  基于版本的多重软件重构自动检测技术研究[J]. 江西师范大学学报(自然科学版),2018,42(5):464-469,472.