（计算机软件与理论专业论文）针对代码克隆的面向对象程序的重构研究.pdf

论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果论文中 除了特别加以标注和致谢的地方外不包含其他人或其它机构已经发表或撰写 ： 过的研究成果其他同志对本研究的启发和所做的贡献均已在论文中作了明确 的声明并表示了谢意 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定即：学校有权保 留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容可以采用影印、缩印或其它复衬手段保存论文保密的论文在解密后 遵守此规定 作者签名：导师签名： 针对代码克隆的面向对象程序的重构研究 【摘要】 软件重构是软件工程的一个重要研究领域，是当前软件工程界的一个重要研 究课题。通过软件重构，人们可以去除软件中的不良设计，改进软件质量。代码 克隆是软件源程序中普遍存在的一个问题，一个软件中往往存在着很多相同或基 本相似的代码片段。代码克隆不利于软件的维护及更新，因为假如有一处需要修 改，其他克隆之处都要作相应修改。 由于代码克隆存在这种负面影响，我们有必要针对代码克隆进行软件重构。 针对代码克隆的软件重构研究主要包括克隆的度量、检测及消除。其目的就是尽 可能全面地找出源程序中的代码克隆，并根据不同的克隆情况采取最合理的消除 措施，以得到最优的重构效果 本文从代码克隆出发，以j a v a 语言为例，讨论面向对象程序中针对代码克隆 的重构方法本文首先用基于编辑距离的相似度来度量代码克隆，即通过计算两 个代码片段对应的标符序列的编辑距离，并求出其相似度来判断是否克隆。本文 接着讨论源程序中的克隆检测，详细阐述克隆检测的各个步骤，包括确定代码片 段、生成标符序列、计算编辑距离及相似度。本文同时考虑了满足语义逻辑等价 性的代码克隆，即将形式上不相似但逻辑上等价的代码片段也视为克隆，本文使 用程序逻辑图来判断逻辑等价性。本文最后针对不同的克隆情况实行不同的消除 克隆方法以实现最有效的重构。 【关键字】 软件重构，代码克隆，克隆度量，克隆检测，克隆消除 【中图分类号】t p 3 1 1 5 针对代码克隆的面向对象程序的重构研究 a b s t r a c t r e f a c t o r i n gi sa l li m p o r t a n tr e s e a r c hf i e l do fs o f t , r a r ee n g i n e e r i n g ，a n di ti sn o w w i d e l ys t u d i e db yr e s e a r c h e r s t h r o u g hr e f a c t o r i n g ，p e o p l ec a nr e m o v et h ef a u l t so r d e f e c t sa n di m p r o v et h eq u a l i t yo fs o f t w a r e c o d ec l o n ei saw i d e s p r e a dp r o b l e m e x i s t i n gi ns o u r c o d e s ，as o i t w a r eu s u a l l yc o n t a i n sm a n yi d e n t i c a lo rs i m i l a rc o d e f i a g m e n t s o b v i o u s l yc o d ec l o n e sa r eh a r m f u lt ot h em a i n t e n a n c ea n de n h a n c e m e n to f s o f t w a r e ，b e c a u s em o d i f i c a t i o n so ft h eo r i g i n a lc o d em u s ta l s ob ea p p l i e dt ot h e d u p l i c a t e dc o d e s b e c a u s eo ft h eh a r m f u li m p a c tp r o d u c e db yt h ec o d ec l o n e s ，“i sn e c e s s a r yt o r e f a c t o rt h es o r w a r ea i m i n ga tc o d ec l o n e s r e f a e t o r i n gr e s e a r c h e sa i m i n ga tc o d e c l o n e sm a i n l yi n c l u d ec l o n em e a s u r e m e n t , d e t e c t i o na n de l i m i n a t i o n 1 1 l eg o a lo ft h e r e f a c t o r i n gi st of i n dt h ec o d ec l o n e se x i s t i n gi ns o u r c ec o d e sa sc o m p r e h e n s i v e l ya s p o s s i b l e ，t h e na d o p ta no p t i m a le l i m i n a t i o na p p r o a c ha c c o r d i n gt od i f f e r e n tc l o n e s i t u a t i o n si no r d e rt oa c h i e v eab e s tr e f a c t o r i n gr e s u l t m sa r t i c l e ，蛐j a v aa se x a m p l e ，d i s c u s s e st h er e f a c t o r m ga p p r o a c h e sa i m i n g a tc o d ec l o n e si n0 0c o d e s t h i sa r t i c l ef i r s t l ya d o p t st h ee d i td i s t a n c eb a s e d s i m i l a r i t yt om e a s u r et h ec o d ec l o n e , w h i c hm e a n st h ec l o n ec a nb ed e t e r m i n e db y c o m p u t i n gt h ee d i td i s t a n c eo ft w ot o k e ns e q u e n c e sc o r r e s p o n d i n gt ot w oc o d e f r a g m e n t st h e nc a l c u l a t i n gt h e i rs i m i l a r i t y t h e nt h i sa r t i c l ed i s c u s s e s t h ec l o n e d e t e c t i n gi nt h es o n r c ec o d e 。i l l u s t r a t e s a ud e t e c t i n gs t e p si nd e t a i l ，i n c l u d i n g i d e n t i l y i n gc o d ef r a g m e n t s ，g e n e r a t i n gt o k e ns e q u e n c e s ，c a l c u l a t i n ge d i td i s t a n c ea n d s i m i l a r i t y t h i sa r t i c l ea l s ot a k e s t h ec o d ec l o n ee q u i v a l e n ti ns e m a n t i cl o g i ci n t o a c c o u n t , i td e e m st h ec o d ef r a g m e n t sw h i c ha l en o ts i m i l a ri ns h a p eb u te q u i v a l e n ti n l o g i ca sc l o n et o o ，a n du s e st h ep r o g r a ml o g i cg r a p ht oj a d g et h el o g i ce q u i v a l e n c e a t l a s tt h i sa r t i c l eg i v e ss o i n ed i f f e r e n tm e t h o d sw h i c hc a nb ea p p l i e dt or f f m o v ec o d e c l o n e sa c c o r d i n gt od i f f e r e n tc l o n es i t u a t i o n st og e tt h eb e s tr e s u l to f r e f a e t o r i n g k e yw o r d s s o f t w a r er e f a c t o r i n g ，c o d ec l o n e ，c l o n em e a s u r e m e n t , c l o n ed e t e c t i o n , c l o n e e l i m i n a t i o n c h i n e s e l i b r a r y c l a s s i f i c a t i o n t p 3 1 1 5 2 针对代码克隆的面向对象程序的重构研究 第一章引言 1 1 软件重构 在软件生命周期中，维护所占的比重越来越大，据统计，软件维护约占软件 总成本的6 6 2 9 1 。随着软件规模的不断扩大，维护现有软件变得越来越难。很 多软件存在着大量不合理的设计，代码冗余，结构混乱，注释不详，这严重影响 了程序的可阅读性，给软件维护带来了巨大的不便。 所以我们很有必要改善软件中的不良设计，以提高软件的可维护性，这就是 软件重构。m a r t i n f o w l e r 在( r e f a c t o r i n g ：i m p r o v i n g t h e d e s i g n o t e x 硒u g c o d e 一书中提出：“软件重构是指在不改变软件的功能和外部可见性的情况下，为了 改善软件的结构，提高清晰性、可扩展性和可重用性而对软件进行的改造。”【l 】 m a r t i nf o w l e r 同时也提出了很多重构的方法例如将一串较长的代码重构成一系 列函数的调用以缩短长度，s w i t c h 语句用多态来代替，根据不同情况在父类和子 类之间交换f i e l d 或m e t h o d ，等等。此外在面向对象系统中应该尽量使用设计模 式去改进源程序，因为设计模式代表了良好的设计架构，使程序编制真正工程化。 软件重构的主要目的有： 简化测试 使设计更加简单 更加容易理解 提高软件设计的质量 容易发现原有代码中的b u g 使编码的效率提高 提高软件的可维护性 提高软件的扩展性 软件重构已成为软件工程领域的一个重要研究课题。j i al i u 在2 0 0 6 国际软 件工程会议上提出了一种面向特征的重构技术，他以特征为单位将程序进行分 片，并结合代数学理论来实现重构【2 】d a v ea s t e l s 利用u m l 来实现重构他先 从源程序中得到u m l 图，然后对u m l 图进行改造以满足合理的设计模式【4 】。 t o m t o u r w e 和t o m m e n 使用逻辑元编程的方法来检测程序中的不良设计【5 】。 1 2 本文的研究目的 代码克隆是当今软件中普遍存在的一种不良设计，在软件源程序中往往出现 针对代码克隆的面向对象程序的重构研究 相同或相似的代码片段，很多程序员为了复用源程序而执行复制粘贴操作从而 产生了代码克隆。代码克隆对于软件的修改和维护是不利的，因为假如有一处需 要修改，其他各处都要作相应修改。 正因为代码克隆的存在严重影响了软件的修改和维护，所以我们有必要研究 针对代码克隆的软件重构。本文研究了面向对象程序中的代码克隆，讨论了代码 克隆的度量、检测及消除的一系列措施，其目的在于找出并消除源程序中的代码 克隆，从而改善软件中的不良设计，以提高软件的可维护性。 1 3 相关研究 当前有不少针对代码克隆的研究，主要围绕代码克隆的度量、检测及消除。 在代码克隆的度量方面，当前最普遍的方法就是求出两段代码的公共部分。 并且根据公共部分在代码中所占的比重来衡量相似程度。这种方法简单直观，因 为人们对于克隆的传统习惯就是看相同部分有多少。 9 1 1 2 0 i 使用这种度量方法对 代码进行逐行比较，即比较两行代码中公共字符序列有多少。 在代码克隆的检测方面，因为检测是按照度量标准进行的，所以当前检测代 码克隆用得最普遍的方法就是基于字符的比较，即找出公共字符有多少。在比较 的时候需要先确定代码片段，然后对两个代码片段作比较，显然代码片段的长度 会影响相似度。【9 1 1 2 0 i 使用单个代码行当作代码片段，对源文件进行逐行比较， 同时用s c a t t e rs l o t 这种点状矩阵图来直观地显示克隆情况，如果片段1 的第f 行 跟片段2 的第，行在字符上相似，则在矩阵图的第f 行，第_ ，列的方格中画一个 点，这种可视化的方法可以直观地反映克隆情况。在 1 4 5 即l i j 选取函数体作为代 码片段，通过计算两个函数体的公共部分来判断是否克隆。 除了字符比较之外，【1 2 】提出了抽象语法树，【1 9 提出了抽象语法后缀树来检 测代码克隆。这两种方法通过分析源代码的语法树来检测代码克隆，语句a b j 跟x = y ；具有类似的语法树，这种方法适合于检测语句内容不同但形式上相似的 克隆。 在消除克隆方面，当前的研究普遍将克隆部分抽取成一个函数，并调用该函 数来消除克隆，这也是最直接易行的措旅。【7 1 1 8 1 都提出了抽取函数这种措施， 而在很多研究中，研究人员只检测出代码克隆，不给出消除代码克隆的措施，因 为消除最终应由程序开发员人为决定。 当前关于代码克隆的研究存在一些不足之处。在检测代码克隆的时候必须先 确定用来比较的代码片段，代码片段的长度会影响相似度。在【1 4 】中选取函数体 作为代码片段而不同的函数体往往长短变化很大。如果代码片段选得太长，则 会降低相似度；如果选得太短，则没有消除克隆的意义，例如在 9 】中选取单一 4 针对代码克隆的面向对象程序的重构研究 代码行作为代码片段进行比较，显然这样傲只能检测出程序里克隆的代码行，而 没有消除克隆的意义。当前的检测代码克隆的方法集中于研究字符的匹配程度， 而不考虑程序语句之间的逻辑关联。在实际中，我们常常看到有的语句可以等价 调换。我们应该把这种满足逻辑等价性的代码片段也看作克隆。如果两段不连续 的克隆块能够通过等价调换语句变成连续块，这可以合并成一个大的克隆块，这 样显然有利于克隆的消除此外，当前关于消除代码克隆的研究大多是仅仅将克 隆的代码抽取成一个新函数，而对新函数应搁放的位置缺少必要的研究，这种做 法虽然在一定程度上减少了克隆，但不一定能够最有效地消除克隆在面向对象 系统中，代码克隆可能存在于同一个类中或不同的类中，有时克隆的方法之间存 在调用关系而形成克隆链，对这些情况应采取不同的重构方法。 1 4 本文主要工作 本文研究了面向对象程序中针对代码克隆的软件重构，针对当前研究的上述 不足之处，提出了一系列改进措施。 在克隆度量方面，本文不用两段代码含有多少公共字符来度量，而采用编辑 距离来度量。编辑距离即一段代码转换成另一段代码需要进行插入、删除或者修 改的最少次数，如果编辑距离越短，则相似程度越高。求编辑距离的算法具有较 好的时间复杂度，而且编辑距离能够反映出两段代码之间做了多少次修改。 在克隆检测方面，本文对代码片段的选取考虑了合适的长度，在j a v a 程序中， 选取方法中包含的语句块作为代码片段，而不是整个方法体。对于复合语句块， 则对嵌套的语句块进行分层处理，这样做能够检测出更多的克隆，因为两个复合 语句块不存在克隆，但是里面可能包含克隆的小语句块。同时，本文中检测代码 克隆的措施考虑了语句之间的逻辑等价性，即满足语义逻辑等价性的代码克隆。 本文采用程序逻辑图来判断语句之问的逻辑等价性，语句之间的逻辑关联用图的 边来表示。两个程序逻辑图同构则可以反映两段代码在逻辑上的等价性 在克隆消除方面，本文考虑了面向对象程序中克隆的各种存在形式，并且根 据不同的存在形式提出不同的消除措施。如果仅使用抽取函数，并不能得到最佳 的重构效果。在面向对象程序中，克隆可能存在于同一个方法中，同一个类的不 同方法中，以及不同类的方法中，对于这些复杂的情形，本文详细探讨合理的消 除措施，以求最佳重构效果。 1 5 本文组织 本文各章节的内容如下： 针对代码克隆的面向对象程序的重构研究 第二章介绍代码克隆的概念及度量，给出判断是否克隆的标准。要研究针对 代码克隆的软件重构，首先必须明确什么样的情形才是代码克隆。这一章用基于 标符的相似度来衡量代码克隆。 第三章讨论如何在源程序中检测代码克隆。在这一章提出了用基于编辑距离 的算法来计算相似度，并以此检测代码克隆。然后提出程序逻辑图来判断语句之 间的逻辑等价性，并以此来讨论满足语义逻辑等价性的代码克隆。 第四章针对不同的克隆情况提出不同的消除克隆方法以实现最有效的重构。 检测出来的代码克隆其存在方式可能多种多样，这一章详细讨论代码克隆的处理 方法。 第五章对所提出的算法和步骤用实验进行验证 第六章总结和展望。对本文所做的工作进行总结，并提出以后的研究方向。 6 针对代码克隆的面向对象程序的重构研究 第二章代码克隆的概念及度量 2 1 代码克隆的概念 2 1 i 什么是代码克隆 我们在阅读程序时，经常会发现有两处或多处代码片段完全相同或基本相似 的情况，我们将这种完全相同或基本相似的代码片段称为代码克隆，或者我们可 以将基本相似的代码片段称为准代码克隆，但是本文统一称作代码克隆。 例如，在开源项目5 h o t d r a w 2 2 的饿忙h i f a 、d r 抓幅訇】耐r e c t a l l 9 1 e f i g u 陀j a v a 和s r c c h k i f a d r a w k f i g u r e s l r o u n d r e e m n g l e f i g u r e j a v a 这两个文件中都存在图2 1 所示的代码片段： s u p e r w r i t e ( d w ) ； d w w r i t e i n t ( f d i s p l a y b o x x ) ； d w w r i t e i n t ( f d i s p l a y b o x y ) ； d w w r i t e i n t ( f d i s p l a y b o x w i d t h ) ； d w w r i t e i n t ( f d i s p l a y b o x h e i g h t ) ； 如果两个代码片段一和占是代码克隆，则称a 和曰满足克隆关系，记作： c a = b 显然克隆关系是一个符合自反、传递和对称的关系。一和曰称为克隆对。 如果一个代码片段集合，其内部任意两个代码片段都有克隆关系，则称这个集合 为克隆集，也就是： c 对于集合墨v qc ，e 墨c ，= c ，o d ，则勋克隆集。 2 1 2 代码克隆的产生 据统计，在大型程序代码中，大约存在5 - 1 0 的克隆。代码克隆的产生有很 多原因，最常见的情况是，当一个程序员在编写程序时。经常会编写相似功能的 程序，这时他往往会采取一种简单快速的方法，即复制已有程序，并执行粘贴操 7 针对代码克隆的面向对象程序的重构研究 作，这样就产生了代码克隆。 例如，假设有人在编写一个作图程序，用来画直线、多边形、圆等图形，当 他编写完画直线的代码时，他会发现画多边形跟直线有很多代码是相同的( 如设 置画笔粗细、颜色等，不同之处仅在于调用画直线和多边形的库函数) ，这时他 就采取复制粘贴操作，于是就有了代码克隆同样他在编写画其它图形的程序 时也会复用这部分代码。 此外，一个软件系统是由很多人共同编写的，如果这些成员之间没有沟通好， 也会编写出很多冗余的相似代码。有的软件公司以代码量来衡量员工的工作，这 使得很多员工会插入大量的克隆代码以增加代码量。 在面向对象程序中，代码克隆的产生大多集中在关系密切的类中( 如有公共 父类) ，关系越密切，则其包含的代码所实现的功能越相似，于是它们的很多方 法中包含相似的代码。例如在作图程序中的直线类和箭头类，它们有很多相似的 地方，如果编写它们的d r a w ( ) 方法，则画箭头实质上就是先画直线再画末端，这 就会跟直线类有代码克隆。 2 1 3 代码克隆对软件的影响 代码克隆是一种不良的设计，它的存在使程序难以作一致的修改，从而影响 软件的更新和维护。程序编写完成以后，我们要对它进行多次测试以找出其中的 错误，同时为了适应客户不断变化的需求也要对程序作修改。假如有克隆关系的 那部分代码中，发现有一处需要改动，则其余克隆之处都要被改动。 以上面的作图程序为例，程序员复用了画直线的代码，使得多个地方存在着 克隆，假如以后需求发生了变化，画笔颜色需要修改，则很多地方需要修改画笔 颜色，显然很费力。 此外，代码克隆的存在也会影响程序的阅读性。程序员在阅读程序的时候， 肯定不愿意多次看到克隆的代码。如果第一次看到一段代码他会认真地研究程序 的功能，当第二次遇到的时候，他肯定是希望对这部分代码进行封装，因为他已 经掌握了这部分代码的功能，以后如果再用到的话，希望只调用一下接口即可， 而不必再去仔细地阅读。 正因为代码克隆的存在严重影响了软件的修改和维护，所以我们有必要研究 针对代码克隆的软件重构，检测并设法消除源程序中的大量重复代码。这正是本 文的研究目的，通过检测并消除源程序中的代码克隆，来改善软件中的不良设计， 以提高软件的可维护性。 针对代码克隆的面向对象程序的重构研究 2 1 4 代码克隆的语义完整性 在研究代码克隆的时候，不能忽视程序设计语言的语义。程序设计语言都是 按照特定的文法规则编写的，所以我们讨论的克隆代码片段也必须符合这个文法 规则，这就是我们要考虑的语义完整性。 看以下两个j a v a 代码片段： 图2 2 两个代码片段 这两段代码含有完全相同的片段： 图2 3完全相同部分 这个片段虽然也属于代码克隆，但它不是一个语义完整的片段，因为i f 语句 是不完整的。对于这种语义不完整的代码克隆，我们不予分析。在第四章讨论消 除代码克隆的时候，我们会讲到将克隆的代码片段用其他语句来代替，而语义不 完整的片段显然没法代替。 本文我们只讨论语义完整的代码克隆，在j a v a 语言中，语义的完整性可以用 和) 的匹配来判断。 2 2 代码克隆的度量 为了找出程序中的代码克隆，首先必须给出一个代码克隆的度量方法，即满 足什么条件的代码片段才是代码克隆。下面我们详细讨论度量方法。 9 针对代码克隆的面向对象程序的重构研究 2 2 i 源代码中的标符 根据代码克隆的定义，代码克隆是指完全相同或基本相似的代码片段，这种 相同或相似可以通过比较两段程序的字符来判断，找出它们之间最大的公共字符 序列，然后从公共字符序列的长度来分析其相似程度。 这一方法确实能够比较代码之间的相似性，但是对于程序语言来说，单单考 虑字符是没有意义的，因为字符不能完全反映程序的语义。例如在j a v a 程序中， 操作符一和= 虽然有公共的字符，但它们的语义却是完全不一样的，前者为逻辑 操作符，而后者为赋值操作符。为此我们在分析程序的相似度之前，先引入标符 这一概念 源代码中的标符是指能够保持语义的不可分割的字符序列例如程序中的 = = ，我们不能把它分割成= ，= ，因为分割后语义就变了。我们知道，程序中的关 键词，变量，常量，操作符等都是不可分割的，它们都有完整的语义，不能分割 成字符序列，所以它们都是标符。对于j a v a 语言，标符的种类见下表： 表2 1标符类型 类型举例 i fw h i l ef o r 关键词 n e wc l a s sp u b l i c +一 操作符 + =一i 搴= 1 变量程序员命名的标识符 常量 10 s 举个例子，在语句i f l a = - b ) 中，有i f ，l ，a ，一，b ，) 这6 个标符。 有了标符这个概念后，我们就可以将代码片段视作标符的序列。标符序列v 的长度记为上o ，) ，代码片段c 对应的标符序列长度记为( c ) 。 既然代码片段是标符的序列，那么我们可以通过比较标符来分析代码的相似 程度。不过在实际比较中，对于长度过小的代码是没有意义的，例如在源代码中 存在着很多i f ，如果把这些i f 看作代码克隆，那是没有任何意义的。所以我们 只去分析具有一定长度的代码片段，为此引入最小标符长度这一概念。 最小标符长度是一段代码要进行相似程度比较所应具有的最小标符数量，记 为厶。，其数值可根据实际情况指定。指定了最小标符长度后，我们不再去分析 那些很短的代码，使得找到的代码克隆更有意义。 当两个代码片段都转变成标符序列后( 并且标符序列长度都超过上胁) ，就 可以通过度量方法来比较相似程度，我们采用基于编辑距离的相似度来度量，后 1 0 针对代码克隆的面向对象程序的重构研究 面几节将详细介绍这些度量方法。 2 2 2 编辑距离 对于两个标符序列，如果要度量其相似程度，最常见的方法就是求出它们的 公共子序列，然后根据公共子序列的长度来衡量相似程度这种方法虽然直观易 懂，但是求出公共子序列的算法的时间复杂度较差本文通过编辑距离来反映相 似程度，下面介绍编辑距离的定义 如果两个标符序列v 1 和1 ，2 ，v l 要转变成v 2 需要经过插入、删除或者修改标 符的最少次数，称为两个标符序列的编辑距离，记为e d i s t a n c e 。显然编辑距离 越小，则表明两个序列越相似 例如两个标符序列a b c d 和a c e ，前者最少经过两次操作删除b ，并将d 改成e 后可以转变为后者，所以它们的编辑距离为2 。 编辑距离不仅可以体现两个标符序列的相似程度，还可以指明它们之间作了 多少次修改，这有利于我们对克隆代码的分析，可以让我们立即知道程序员在复 制粘贴一段代码后作了几次修改。 求编辑距离的算法将在第三章作介绍。 2 2 3 相似度 设有两段代码c l 和c 2 ，其标符序列分别为v l 和v 2 ，定义这两段代码之间的 相似度为： s 幽毗兄) = l 一忑e 瓦d i s t j a 而n e e 可以看出，如果编辑距离越小，则相似度越大。如果编辑距离为0 ，则有 s i m i l a r i t y ( c i ，c 2 产l ，即表明两段代码完全相同。 我们可以指定一个相似度阈值t h r e s h o l d ，两段代码c i ，c 2 ，如果有 s i m i l a r i t y ( e , ，c 2 ) 一 t h r e s h o l d 则表示它们之间有克隆关系，即c - - - - c 2 。 有了相似度阈值，我们可以设定检测出来的代码克隆的最小相似度。如果我 们只检测完全相同的代码，则将阚值设为l ；如果需要找出基本相似的代码，则 可以适当降低阅值。 看一下图2 4 所示的两段代码： 针对代码克隆的面向对象程序的重构研究 这两段代码的标符序列为： 图2 4代码片段举例 图2 5代码片段对应的标符序列 第一个标符序列最少可以经过以下7 次操作转变为第二个标符序列： 插入，插入j插入， 插入j插入一+ = 改为+ +删除2 两个标符序列的e d i s t a n c e = 7 ，m a x ( l ( v , ) , l ( 屹) ) - - 2 6 ，所以 s i i i l i t y = 1 一里望皇竺：1 7 0 7 3 2 2 4 满足语义逻辑等价性的克隆度量 前面分析的度量是基于标符的，即分析标符序列的相似度。然而程序设计语 言是有一定的语义的，不是简单的字符串。程序设计语言的语义使我们必须考虑 这样一个问题：如果两段程序虽然从表面上看不相似，但是如果在不改变语义逻 辑的情况下对语句进行调换，从而将相似度提升到阈值之上，那么这是不是代码 克隆呢? 本文将这种情况也视作代码克隆，因为这种情况下程序之间存在逻辑等价 性，代码克隆不能只看表面上的相似性，也要看本质上的相似性。我们来看一个 最简单的例子：有这样两个代码片段，a + + ；b 一，和b - - 7a + + ；这两段代码如 果仅从标符序列上看则会认为是不相似的，但是我们知道a + + ；b - - ，可以进行 语句调换变成b 一；a + + j 逻辑上是等价的，通过调换后可以发现两段代码是完 针对代码克隆的面向对象程序的重构研究 全相同的。 这种满足语义逻辑等价性的克隆度量，首先需要判断逻辑上的等价性，在逻 辑等价的前提下对代码进行调换，然后再利用基于标符的相似性度量方法。判断 逻辑等价性的算法将在第三章讨论。 2 3 本章小结 本章的主要工作为针对代码克隆的软件重构提供了前提和基础，只有确定克 隆度量标准，才能在源代码中检测克隆并设法将它消除。本章提出的度量标准是 基于编辑距离的相似度比较，同时考虑了代码的语义完整性，以及满足语义逻辑 等价性的代码克隆。有了克隆度量，我们就可以检测源程序中的代码克隆了，下 一章我们将详细讨论代码克隆的检测。 针对代码克隆的面向对象程序的重构研究 第三章代码克隆的检测 在前一章我们定义了代码克隆的度量方法，即通过计算标符序列的相似度来 判断克隆。由相似度计算公式 s i i n i t y 如, e 2 ) = l 一忑e 面d i s t 面a n c e 丽 可知，我们只要得到两段代码的编辑距离就可以求出相似度。所以为了检测代码 克隆，我们需要有一个求编辑距离的算法。 有了这个算法以后，我们可以将代码片段视作标符的序列，运用这一算法求 出编辑距离，然后计算相似度的值，如果相似度超过阙值，则表明这两段代码存 在克隆关系。 本章同时讨论满足语义逻辑等价性的代码克隆的检测，详细分析两段形式上 不相似但逻辑上等价的代码，提出程序逻辑图来判断代码语句之间的逻辑等价 性。 3 1 检测代码克隆的基本过程 检测代码克隆，要对代码片段进行比较，根据克隆度量，其实是对标符序列 的比较。所以首先我们要将代码片段生成标符序列，再设计算法求出两个标符序 列的最长公共标符序列，从而计算相似度，最后将相似度跟阈值进行比较以决定 是否克隆。基本流程图如下： 图3 1检测代码克隆的流程图 1 4 针对代码克隆的面向对象程序的重构研究 在上述流程图中，我们看到检测代码克隆的核心在于代码片段的相似度比 较。首先我们确定用于比较相似度的代码片段，然后将代码片段转变为对应的标 符序列，再对标符序列求出编辑距离并计算相似度值，如果相似度大于阈值则表 明找到了一个克隆，此后继续对其他代码片段进行比较。下面逐个讨论上图所示 的检测过程。 3 2 代码片段的选取 在检测的时候我们要选取合适的代码片段，然后运用编辑距离算法进行相似 度比较。最直接的办法是将单个源文件当作代码片段，但是这样的话可能由于源 文件太长而检测不到克隆。实际中可以采取将类( c l a s s ) 、方法( m e t h o d ) ( 或方法中 的语句块) 当作代码片段。本文中，我采取方法中的语句块当作代码片段，而不 用类。所谓语句块就是连续的语句集合。先确定方法中的语句块，然后转变成标 符序列，再求出其相似度。选取方法中的语句块有以下好处： 方法中的语句块长度比较适中。如果比较两个类的相似度，则很可能得不 到较大的相似度值，要找到代码克隆就必须降低阈值，这样一来会使检测到的克 隆缺乏意义。 我们检测到的代码克隆，最终要设法去除。如果我们检测到两个克隆的方 法中的语句块，则比较容易消除克隆( 例如将两个方法中的相同部分提取成一个 新的方法，并调用该方法即可) ，而方法外的代码克隆不易消除。 j a v a 程序中，不在方法中的代码( 例如i m p o r t 语句，类中的成员声明语句 等) ，即使存在克隆也不是不良设计，因为很多类可能存在相同的成员变量，很 多源文件都要用到一系列相同的类从而都要写对应的i m p o r t 语句，所以我们只 需考虑方法中的代码克隆 3 2 1 代码片段的语义完整性 在第二章中，我们提出了代码克隆的语义完整性这一概念，即代码片段必须 是语义完整的，我们在选取代码片段的时候必须确保语义完整性。 在j a v a 语言中，我们可以通过 和 的匹配来判断是否语义完整。一段代码中 每遇到一个( ，如果后面没有对应的 ，则它的语义肯定不完整，这可以通过栈的 操作来判断 看图3 2 中的例子，这是一段i fe l s e 语句块。 针对代码克隆的面向对象程序的重构研究 图3 2 代码片段举例 在这段代码中，我们不能选取下图所示的代码片段： 图3 3 语义不完整的代码片段 这个代码片段显然是语义不完整的。为了确保语义完整性，我们应该选取完 整的i f , f o r ，w h i l e 等语句块，一旦遇到这类关键词，我们向后搜索一对匹配的 i 和】。为了便于处理，我们对mf o r ，w h i l e 等后面只包含单一语句的情形加一 对( 和。 3 2 2 确定代码片段 对于j a v a 程序，代码一般都包含在类中( 除i m p o r t 语句以外) ，包含在类中 的代码有成员变量和方法两种，我们在研究代码克隆的时候只考虑方法。为了得 到尽可能高的相似度值，我们不宜选取太长的代码片段，而应该选取长度适宜的 代码片段。最后可以将连续的小克隆块合并成大克隆块。根据前面的语义完整性 分析，我们将方法中的完整语句块当作代码片段来比较相似度，为了确定代码片 段，我们考虑三种基本语句块： 针对代码克隆的面向对象程序的重构研究 顺序语句块，即由连续的声明变量、赋值等语句组成的语句块。 选择语句块，即i fe l 辩，s 晰t c h 这样的语句块。 循环语句块，即矗扔w h i l e 这样的语句块。 而对于选择，循环这样的复合语句块( 即存在嵌套的语句结构) ，我们可以对它 进行分层处理，当遇到一个复合语句块时，向里面分析被嵌套的语句块，最终可 以把它分为若干基本语句块。在克隆检测时，我们通过先分析这些基本语句块的 克隆情况，再得出复合语句块的克隆结果。当划分好基本语句块后。如果一个代 码片段的标符长度小于工椭，则跟它前面或后面的代码片段进行合并( 合并前面 还是后面的代码片段，采取优先合并长度较小的代码片段这一策略) ，使得代码 片段的长度超过上。 3 3 生成标符序列 要检测代码克隆，就必须首先将代码生成相应的标符序列，在克隆度量那一 章我们知道了标符的一些基本类型，包括关键词、操作符、变量和常量。所以可 以根据这四种类型将代码转变成标符序列，下面介绍生成标符序列的过程。 3 3 1 去除代码中的注释 注释对程序的语义没有作用，我们在检测代码克隆的时候，无须考虑这些东 西可以对程序代码片段作一遍扫描，如果遇到，则将以及在这一行中 后面的所有字符都去除；如果遇n * ，则向后扫描直到。并将和以及夹 在它们之间的所有字符都去除。 3 3 2 将程序的字符组合成标符 去除注释以后，我们把代码片段中的字符逐个组合成标符，基本算法为： i n p u t ：代码片段c o d e ，类型为字符串s t r i n g o u t p u t ：标符序列v ，类型为向量v e c t o r c l a s st o k e nl s t r i n gt o k e n ； i n tt y p e ；标符类型，0 关键词，1 操作符，2 变量标识符，3 常量 t o k e n s t r i n gt o k e n ，i n tt y p e ) l t h i s t o k e n = t o k e n ， t h i s t y p e = t y p e ； 1 7 针对代码克隆的面向对象程序的重构研究 j j i n ti = 0 ，j ； v e c t o rv ； w h i l e ( i c o d e 1 e n g t h ( i f ( c o d e 【i 】是字母或下划线) ii 这表明遇到了关键词或标识符 j 篁i + 1 7 w h i l e ( c o d e 【j 】是字母或下划线或数字) i 往后扫描以确定一个完整的标符 j + + ， i f ( c o d e s u b s t r i n g ( i ，j ) 属于关键词集合) v a d d ( n e wt o k e n ( c o d e s u b s t r i n g ( i ，j ) ，0 ) ) ， e l s e v a d d ( n e wt o k e n ( c o d e s u b s t r i n g ( i ，) ) ，2 ) ) ； i = j ， ) e l s ei f ( c o d e 【i 】是数字) 这表明遇到了常量，可能为整型或浮点型 j = i + l ； w h i l e ( c o d e j 】是数字或小数点) i ，+ + ； v 。a d d ( n e wt o k e n ( c o d e 。s u b s t r i n g ( i ，j ，3 ”； 1 = 】； e l s ei f ( c o d e 【i 】是操作符) i j = “1 7 w h i l e ( c o d e 【j 】是操作符) i j + + ； ， v a d d ( n e wt o k e n ( c o d e s u b s t r i n g ( i ，j ) ，1 ) ) ； i = j ； e l s e 空格或换行符 i + + ； 1 8 针对代码克隆的面向对象程序的重构研究 下图是以上算法的程序实现，运行于j d k i 5 。 3 4 求编辑距离的算法 图3 4生成标符序列 设有两个标符序列”l = f l t 2 k ，屹= 苫l 兜翰，现要计算n 转变成屹所需最少 的插入、删除或修改标符的次数。 设一个矩阵a 0 埘】【0 。棚，用它来记录插入删除或者修改的次数，例如a 【3 】 2 】 表示h t 2 t s 转变成s i s 2 所需的最少次数。很显然a 【司【o 】= f ，a 0 y - - y 。 对于a 0 阴我们考虑三种情况： a i - q ：3 表示“f 2 f j 1 转变成s i s 2 研所需的最少次数，那么 f 2 t t 只要在 原来基础上删除一个厶即可，所以a 【习 t = a i - l l i d l + l 。 同理，a 【司 - 1 】表示t i t 2 6 转变成s i s 2 s j i 所需的最少次数，那么h t 2 ，1 只要在原来基础上插入一个自即可，所以a 0 阴- a 【f 】 - l 】+ 1 。 a 【“】【- 1 】表示，l ，2 轧l 转变成s i s 2 s j 1 所需的最少次数，这时如果，雨， 1 9 针对代码克隆的面向对象程序的重构研究 则无需改动，否则在原来基础上作一次修改，即将 改成毋，所以 a 【f m 书a - 1 】i - 1 j - 】+ 1 1 , ，6 麓 综上所述，a 【刁们应该取以上三种情况的最小值。最终a 【坍】陋】的值就是我们 要得到的编辑距离。 该算法的代码描述如下： t o k e nv l 【m + 1 】，v 2 【n + l 】，v l 【1 】v l 【m 】，v 2 1 】v 2 【n 1 存放标符序列 i n ta 【m + 1 】【n + 1 】， i n tc o s t ，i ，j ， f o r ( i = 0 ，i = 嘲；i + + ) a 【i 】【0 】= i ； f o r ( i f f i o j i f f i n ；i + 十j f o r i i = 1 ，i = 潮，i + + ) f o r ( j 。l ，j = n ，9 + + ) i f ( v l 【i 一1 】f f i = v 2 【j 一1 】j c o s t = 0 ； e l s e c o s t = 1 ； a 【i 】【j 】- - m i n ( a 【i - 1 】【j 】+ 1 ，a 【i j 【j 。1 】+ 1 ，a i - 1 】【j 一1 】+ c o s t ) ； l 其中m i n 函数如下 i n tm i n ( i n ta ，i n tb ，i n tc ) f i n tr e s u l t ? r e s u l t = a c ) r e s u l t f f i c ； r e t u r nr e s u l t ； 可以看一个例子，有两个标符序列a b c d e ，a a b b d e ，运用以上算法可得到以 下矩阵： 针对代码克隆的面向对象程序的重构研究 表3 1 编辑距离矩阵 口abbde ol2 345 6 lo12 3 4 5 21l l 2 34 3 2 222 34 43 3 3 3 2 3 544443 2 最右下角的数字为2 ，这就是