重复代码检测技术的现究现状

易长安

摘要:重复代码是程序中最常见的“坏味道”,也是导致软件维护费用高昂的原因之一。关于重复代码的重构技术已经研究了很多年了,该文主要对重复代码检测技术的国内外研究现状进行分析和比较、指出了它们的优缺点,并在此基础上展望了其以后的发展趋势。

关键词:重构;重复代码;抽象语法树;程序依赖图;过程蓝图

中图分类号:TP311文献标识码:A文章编号:1009-3044(2009)20-0000-00

0 引言

软件的本质属性是演化[1]。对于一家软件公司来说,代码是其重要的“遗产系统”,而重构是实现软件演化的主要方法,它可以大大提高“遗产系统”的价值。现代主流的的软件开发方法,如RUP和XP等都运用重构来支持迭代开发,重构是XP的基石。关于重构的研究已经有很多年了,但是,直到现在,没有一种好的度量方法能够胜过人的直觉,“何时在何地使用何种重构”仍然是重构技术所需要解决的主要问题之一,自动化的重构工具也依然是研究人员和程序员所最希望拥有的。

重构,就是对软件系统作一些改变,它只改变软件的内部结构,而不改变代码的外部行为[2]。重构是一种改进软件的可维护性的技术。那些需要进行重构的地方被称为坏味道[2]。重复代码、长方法、长参数列表等都是常见的坏味道。

所谓重复代码,是指那些彼此相似或者完全相同的代码片段。有研究表明,在大型软件中,重复代码的比例高达5-10%[1]。重复代码在所有的软件中都是很常见的,它也是使得软件的维护成本高昂的原因之一。大量的重复代码会导致运行时间的急剧增加[3]。

既然重复代码的危害性这么大,那么,为什么它还如此普遍呢?一般认为,重复代码的产生有如下的原因[1]:

1) 复制已经存在的代码。当要实现一个新的功能特别是当有时间压力时,程序员往往首先去寻找已有的、实现了相似功能的代码,然后拷贝过来,并稍微作一些修改。

2) 编码风格。特别是在驱动程序的编写方面,这种情况特别普遍。因为对于各个驱动程序来说,大部分代码都有样板可寻,仅仅只是核心部分需要作修改。

3) 对所定义的操作的实例化。程序员在这种情况下往往会使用宏。

4) 没有充分利用抽象数据类型。有时候重用库函数比“粘贴”更好。

5) 为了提高系统性能而有意让代码冗余,如实时系统。

6) 偶然的情况。有时候代码段之间仅仅是偶然的一致,而并不是重复。

虽然复制-粘贴-剪切(以及一定的修改)被认为是一种不好的做法,但实际上几乎所有的程序员都使用这种方法。虽然复制代码非常容易,但是,它使得软件维护更加困难,主要表现在两个方面[3]:

1) 当代码被复制时,代码中的错误也在被复制;

2) 对初始代码进行修改时也必须同时对复制后的代码进行修改。

1 重复代码的分类

重复代码的危害性引起了软件人员的高度重视,关于这方面的研究已经进行了很久,并且取得了一定的成果。现在,从以下几个方面来讨论重复代码的研究状况。

1.1 大型软件系统中重复代码的分类

Kapser等人对重复代码进行了初步的分类,并将这个分类与对Linux操作系统内核的分析结合起来[4]。该项研究使用CCFinder来作为重复代码检测工具,结果表明重复不仅在文件系统内部发生,而且在文件系统之间也存在大量的重复代码。

Kapser将所检测到的重复代码分成了如下几类:

1) 同一个函数里的重复代码;

2) 同一个文件里的相似函数;

3) 同一目录下不同文件之间的重复函数;

4) 不同目录之间的重复函数;

5) 文件重复(可能作了一些改变);

6) 不同文件之间的重复块。

Kapser率先对大型软件系统的重复状况进行研究,其另外的一个独特之处是使用三维图形来可视化重复信息。

1.2 类以及类之间的重复代码

从软件维护的角度看,重复代码应该被清除。但是,有时候这些重复代码之间存在依赖关系,此时就需要一次性地将它们全部清除,Norihiro Yoshida等人为此定义了“方法链”[4]。所谓“方法链”,是指一系列有依赖关系的方法。如果一系列“方法链”彼此互为重复关系的话,那么就称其为“重复链”,与“重复链”相对应的类就称为“重复链集合”。 Norihiro Yoshida等人对“重复链集合”进行了分类,并为它们分别提出了相应的重构模式,而且,还在一些实际案例中对所提出的方法的正确性进行了验证。这篇文章还提出了度量方法来衡量重复方法之间的距离(根据这些方法所在的类的关系来求值)。该项研究还通过所实现的原型工具Aries来对三个软件ANTER、Tomcat和JBoss的重复情况进行分析,进而评价方法的正确性,结果发现不同风格的软件其重复代码的特点也是不同的。

2 重复代码的检测方法

研究重复代码的最终目的是为了把理论成果转换为产品,提高重复代码的检测和改进效率。

2.1 基于抽象语法树的重复代码检测方法

以前的重复检测方法只能检测出那些极为相似的代码片段或者完整函数之间的代码片段。Baxter[1]等人提出的基于抽象语法树的方法是一种简单而且实用的重复检测方法,它能够检测出源代码中任意片段之间的重复情况。该方法是在程序的结构上进行操作,所以可以通过一些常用的方法来清除重复代码。重复检测中最基本的问题就是找出那些有相同功能的代码片段,以往的方法很难对某个功能的起止位置进行定位,而基于抽象语法树的方法可以做到这一点。使用抽象语法树来检测重复代码的第一步就是将源代码解析成抽象语法树,然后陆续应用三种算法来寻找重复代码。其中,第一个算法用来检测子树重复,第二个算法用来检测连续重复,第三个算法用来检测更加复杂的重复。

2.2 使用程序依赖图来识别相似代码

虽然存在很多种检测重复代码的方法,但是大部分都只能检测出完全一致的重复代码,而通常情况下程序员都对复制过来的代码进行了一定的修改。Jens Krinke提出的方法是基于在属性有向图里寻找相似子图进而来识别相似代码[3]。该方法使用程序依赖图,既要考虑程序的句法结构也要考虑数据流结构,因此也就不需要在精确和回溯之间进行折衷(所谓精确,是指所发现的重复代码中那些没有价值的重复代码的数量;所谓回溯,是指尚未发现的重复代码的数量)。该方法还可以检测到那些被修改了的重复代码,它不仅仅是基于文本或者语法,而且还考虑语义。Jens Krinke提出的方法是基于精炼了的程序依赖图,程序依赖图描述程序的结构和数据流。在这些图里,我们主要是识别由重复代码所产生的相似子图,所识别出来的相似子图可以被直接映射到程序源代码并呈现给用户。

2.3 基于过程蓝图的重复代码检测方法

Roberts[5]在其博士论文中指出,表达式变换最自然的方式是使用树到树的变换规则。过程蓝图[6]是一种图形化程序过程规格说明方法,是对过程的源代码进行描述的模型,其本质上是抽象语法树,具有丰富的语义,因而具有对程序重构、重复代码检测的支持能力。

2.4 一种关于重复代码检测的新思想

软件维护的确很重要,关于这方面的工作大部分是提出新的方法来创建或者修改软件。但是,由于当对一个问题理解的程度加深时,就能够产生更好的方法,所以,Rysselberghe等人通过研究软件演化的方式而提出了一种新的方法[7]。其实,Rysselberghe是把已有的技术按一种全新的方式来应用,即不是寻找那些代表重复关系的匹配,而是寻找那些反映程序发生了变化的非匹配。Dotplogs是一种可视化技术,它最初是被用来检测DNA序列的相似性,但是后来被用来分析重复代码。该项研究使用重复检测工具Duploc来对Tomcat的五个不同版本进行比较。“Moving methods”被认为是重构的重要组成部分[8],在该项研究中也得到了证实。另外,Rysselberghe还得出了一个重要结论:“Moving methods”更重要的目的不是消除代码冗余而是将功能聚合(即让一组实体完成某一个特定的功能)。

3 各种重复代码检测技术的比较

在过去的十多年里,开展了大量的关于重复代码方面的研究,有些研究还是在大型软件上进行,所有这些技术都有各自的优缺点。Rysselberghe等人比较了三种有代表性的检测技术,即简单行匹配、参数化匹配和度量方法[9],结果发现这三种技术均有各自的适应性:简单行匹配适用于对重复代码的初步探测;参数化匹配最好与能够在语句层次上执行重构的工具结合使用;度量技术最好与能够消除重复子程序的重构工具结合使用。

重复代码的检测由转换和比较两个阶段组成。在第一个阶段,源代码被转换成一种内部表示形式,在第二个阶段才执行真正的匹配过程。根据源代码转换后的内部格式,可以把重复检测技术分成三类:基于字符串、基于符号流和基于分析树。基于字符串的技术都独立于编程语言,它们仅仅是字符串比较算法的不同。基于符号流的技术所使用的转换算法更加复杂,还需要用到词法分析器。基于分析树的技术使用一种重量级的转换算法,即创建分析树。分析树的信息丰富,可以在分析树上进行各种算法的比较。通过对这些技术的比较,可以为更加系统化地检测和消除重复代码奠定一个良好的基础。

随着对大型软件的需求不断增加,重复代码的探测与消除问题也变得越来越重要。以上列举了四种有代表性的重复代码检测方法,在以后的研究中,新的方法将会不断涌现。

4 总结

关于重复代码方面的研究工作正在进行,新的检测方法和检测工具会不断地出现。以前的研究中,虽然提出了检测方法并进行了试验性的验证,但是,都不是大规模的,不具有很强的说服力。所以,今后的一个研究方向就是将所提出的方法应用到商业软件中,以便从更深层次和更广范围来检验其正确性。

另外,虽然在软件设计度量和软件代码度量方面开展了深入的研究,但是,这些度量还没有被广泛地运用,使用度量与不使用度量的积极意义与不良影响都很值得研究[9]。

重复代码都是在源代码中产生,既然它的危害如此之大,那么,从另一个角度说,源代码的设计也就变得更加重要了[10]。

参考文献:

[1] Baxter L D,Yahin A,Moura L,et al.Clone detection using abstract syntax trees[C].International Conference on Software Maintenance,1998.

[2] Fowler M.Refactoring:Improving the design of existing code[M].Addison Wesley,1999.

[3] Krinke J.Identifying similar code with program dependence graphs[C].Proc. Eigth Working Conference on Reverse Engineering,2001.

[4] Kapser C,Godfrey M W.Toward a taxonomy of clones in source code:A case study[Z].

[5] Roberts D.Practical Analysis for Refactoring[D].PhD thesis, Univ.of Illinois at Urbana-Champaign,1999.

[6] 刘建宾.过程蓝图设计方法学[M].北京:科学出版社,2005.

[7] Van Rysselberghe F,Demeyer S.Reconstruction of successful software evolution using clone detection[C].Proceedings of the Sixth International Workshop on Principles of Software Evolution(IWPSE03).

[8] Yoshida N.On refactoring support based on code clone dependency relation[C].11th IEEE International Software Metrics Symposium(METRICS 2005).

[9] Van Rysselberghe F,Demeyer S.Evaluating clone detection techniques[Z].

[10] Munro M J.Product metrics for automatic identification of “bad smell” design problems in java source-code[C].11th IEEE International Software metrics Symposium (METRICS 2005).