程序设计语言中代码克隆的研究

王国莉 白昊昱

（1 中国电子科技集团公司第五十四研究所河北石家庄050081）

（2 新加坡国立大学新加坡119077）

1 引言

代码克隆，通常被定义为：在某一软件项目中，在某一选定的的相似度度量下，较为相似的2段程序设计语言语句序列。代码克隆的存在往往预示着潜在的不良设计，并将增加软件项目的代码规模，维护成本以及缺陷产生的概率。因此，在软件重构与维护中，代码克隆往往被视作一种“代码臭味”。然而，不同的程序设计语言有着不同的设计哲学，因而有着不同的特性。

文章采用C lone Digger做为代码克隆检测工具。Clone Digger是一个开放源代码项目，它实现了基于抽象语法树(Abstract Syntax Tree,AST)的克隆检测算法[1]。人们对其进行了扩展，使其支持JavaScript,Haskell与Erlang，并将代码回馈给了开源社区。首先，将对Java,Python,JavaScript,Erlang与Haskell的程序代码进行研究。通过对这些语言的学习，去总结它们的一系列对删少克隆有潜在帮助的特性。这些特性包括：面向对象，多重继承，泛型，宏，鸭子类型，类型推导，第一等函数，匿名函数，柯里化，模式匹配，断言，eval，反射，闭包，生成器。其次，基于选定的一组人们所研究的语言写成的开源项目的代码，将构建一个源代码库用于对特性进行比较和分析。最后，将分析克隆检测的结果，并指出一些有趣的现象。

2 克隆检测方法

要研究各种程序设计语言中的代码克隆现象，首先需要一个代码克隆检测工具。检测工具需要足够精确，并能够容易地进行扩展使其支持多种语言。并且，需要选择一组适当的语言及其特性。对每一种语言，必须选择一组合适的代码库，从而使得分析合理并有价值[2]。

2.1 克隆检测

对于克隆检测工具，评估了CCFinder以及C lone Digger。二者都功能强大，结果精确，并具有支持多种语言的设计。评估与比较请见下文的列表。最终，选择了C lone Digger，因为做为开源软件，它更方便进行扩展。

①用户界面:CCFinder拥有漂亮的代码克隆分布图界面，使得代码克隆的分布可以非常直观地呈现出来；CCFinder还拥有对比视图，可以直接看到冗余代码片段，而Clone Digger仅仅生成包含冗余代码对比列表的HTML报告文档，不过，这也已经能够满足需要；

②技术：CCFinder是基于词法分析的克隆检测工具，而C lone Digger采用的是基于AST的算法，从而将更为精确；但其代价是，Clone Digger的运行速度远远慢于CCFinder，但对人们来说，C lone Digger的速度是可以接受的；

③可扩展性：Clone Digger的代码以开源的GPL许可协议发布，这使得人们可以非常方便地通过编写AST适配器来扩展它；虽然为一个语言编写一个AST分析器要难于为其编写一个可用于CCFinder的词法分析器，但是，几乎所有的现代编程语言都提供了用于解析其自身源代码的AST分析器，只要直接使用就可以了，所以扩展C loneDigger仍然是非常容易的。

C lone Digger的作者已经实现了对Python和Java的支持。对其扩展使其支持ECMAScript，Erlang和Haskell。这些代码已经回馈到了C lone Digger的代码库[3]。

2.2 选择语言和特性

世界上有上百种程序设计语言，不可能去研究其中的每一个。因此，从中选出几种，以确保人们的研究有意义、有价值。依照以下的标准来选择所研究的语言。

①流行程度：该语言必须足够流行，从而能够找到规模足够大的开源项目来构；②建代码库：并使得研究能够让尽量多的人受益；③成熟度：该语言必须经过了长期的开发与进化，因此它的设计和特性都较为稳定；④标准化：该语言应当有一个标准，或是事实上的标准。例如，ECMA标准或是一个参考实现；⑤语法易于解析：由于能力有限，并且采用基于AST的克隆检测算法，因此该语言的语法必须易于解析，或者是存在语法解析器可供直接使用。

参考上述标准，选择了Python，ECMAScript，Erlang与Haskell做为研究目标。做为业界最流行的编程语言，Java将被做为评测的基准。每一个程序设计语言都有很多的特性和特点，研究不可能涵盖它们的每一个方面。因此，从中选择对消除代码克隆有潜在影响力的特性进行研究，如表1所示。

表1 各种程序设计语言特性比较

2.3 构建源代码库

用于比较测试的源代码库由精心选择的一系列开放源代码项目的代码构建。这个代码库包括W eb应用框架、语法分析程序生成器以及编程语言测试游戏这3类功能。用文中选择的每一个语言实现了每一类功能的开源项目。所选择的项目之间，同一个类别中的项目应当实现了相似的功能或用于相似的目的，并在其语言社区中有较高的流行度。文中比较每一个类别中的项目的代码克隆覆盖率，并将给出由各个类别的数据相加得到的综合比较数据，对所选择的开源项目的概览如表2所示。

表2 源代码库所包含的项目

3 结果与分析

按语言累计的代码克隆覆盖率如图2所示。从图中可以看到，在函数式编程语言中，有着明显较少的克隆，尤其是在Haskell中。而Haskell是一个相对有着更多特性的语言。不过，由于W eb应用框架往往要比其他类别中的项目大得多，因此，图2很大程度上由W eb应用框架的数据所主导。

图2 按语言累计的代码克隆覆盖率

为了表现其他因素对克隆覆盖率的影响，统计了按类别累计的数据；以及包含所有项目的代码克隆覆盖率相对千代码行(KLOC)。它与按语言累计的数据的计算方式相似。根据统计结果，编程语言测试游戏类别是仅有的一个有着更小的克隆覆盖率的类别，这是因为它是一组简单的任务，因而有着较少的LOC。所以，认为软件项目的类型对于代码克隆没有大的影响。

4 结束语

代码克隆出现的原因是复杂多样的，语言特性对于代码克隆的影响也同样复杂[4]。通过扩展C lone Digger使其支持更多的编程语言，并构建一个包含了由不同语言写成的不同种类的开源项目的源代码库，文中观察到了代码克隆现象在各个语言间的差异，并用语言的特性来解释这些差异。除了语言特性，文中同样考虑到了可能影响代码克隆的其他因素。

实验结果指出，一般情况下，由于有着更多特性的语言，例如Python和Haskell写成的代码，往往有着较少的代码克隆。但是，即使是有很高的表达能力的语言，如Python，所写成的代码，仍然会有着大量的克隆。导致克隆的原因是多种多样的，可能是因为优化运行效率的目的，可能是对某一编程风格的偏爱，或者仅仅是难于被合并的代码片段[5,6]。随着计算机程序设计语言的不断进化，越来越多的语言特性被开发出来，并将对消除代码克隆有所帮助。但是，人们不能够仅仅依靠某些语言特性来消除代码克隆。仔细地设计和实现，有效的管理，永远是必须和最有效的消除克隆的方法。

[1]Bulychev Peter,M inea Marius.Duplicate code detection using antiunification:In Proceedings of Spring Young Researchers Colloquium on Software Engineering[C].2008:4- 12.

[2]M Kim,L Bergman,T.Lau,et al.An ethnographic study of copy and paste programm ing practices in OOPL.In Empirical Software Engineering,2004:ISESE’04.Proceedings.International Symposium on[C].2004:83- 92.

[3]G V Rossum,F L Drake.Python language reference[M].Network Theory Ltd,2003.

[4]C Kapser,M W Godfrey.“cloning considered harm ful”consideredharm ful:In Reverse Engineering,2006.WCRE’06.13th W orking Conference[C].2006:19- 28.

[5]D C Rajapakse,S Jarzabek.Using server pages to unify clones in webapplications:A trade- off analysis:In Proceedings of the 29th internationalconference on Software Engineering[C].2007:116- 126.

[6]M Kim,V Sazawal,D.Notkin,et al.An empirical study of code clone genealogies:In Proceedings of the 10th European Software Engineering Conference[C].2005:187- 196.