程序設(shè)計(jì)語(yǔ)言中代碼克隆的研究

王國(guó)莉 白昊昱

（1 中國(guó)電子科技集團(tuán)公司第五十四研究所河北石家莊050081）

（2 新加坡國(guó)立大學(xué)新加坡119077）

1 引言

代碼克隆，通常被定義為：在某一軟件項(xiàng)目中，在某一選定的的相似度度量下，較為相似的2段程序設(shè)計(jì)語(yǔ)言語(yǔ)句序列。代碼克隆的存在往往預(yù)示著潛在的不良設(shè)計(jì)，并將增加軟件項(xiàng)目的代碼規(guī)模，維護(hù)成本以及缺陷產(chǎn)生的概率。因此，在軟件重構(gòu)與維護(hù)中，代碼克隆往往被視作一種“代碼臭味”。然而，不同的程序設(shè)計(jì)語(yǔ)言有著不同的設(shè)計(jì)哲學(xué)，因而有著不同的特性。

文章采用C lone Digger做為代碼克隆檢測(cè)工具。Clone Digger是一個(gè)開放源代碼項(xiàng)目，它實(shí)現(xiàn)了基于抽象語(yǔ)法樹(Abstract Syntax Tree,AST)的克隆檢測(cè)算法[1]。人們對(duì)其進(jìn)行了擴(kuò)展，使其支持JavaScript,Haskell與Erlang，并將代碼回饋給了開源社區(qū)。首先，將對(duì)Java,Python,JavaScript,Erlang與Haskell的程序代碼進(jìn)行研究。通過(guò)對(duì)這些語(yǔ)言的學(xué)習(xí)，去總結(jié)它們的一系列對(duì)刪少克隆有潛在幫助的特性。這些特性包括：面向?qū)ο螅嘀乩^承，泛型，宏，鴨子類型，類型推導(dǎo)，第一等函數(shù)，匿名函數(shù)，柯里化，模式匹配，斷言，eval，反射，閉包，生成器。其次，基于選定的一組人們所研究的語(yǔ)言寫成的開源項(xiàng)目的代碼，將構(gòu)建一個(gè)源代碼庫(kù)用于對(duì)特性進(jìn)行比較和分析。最后，將分析克隆檢測(cè)的結(jié)果，并指出一些有趣的現(xiàn)象。

2 克隆檢測(cè)方法

要研究各種程序設(shè)計(jì)語(yǔ)言中的代碼克隆現(xiàn)象，首先需要一個(gè)代碼克隆檢測(cè)工具。檢測(cè)工具需要足夠精確，并能夠容易地進(jìn)行擴(kuò)展使其支持多種語(yǔ)言。并且，需要選擇一組適當(dāng)?shù)恼Z(yǔ)言及其特性。對(duì)每一種語(yǔ)言，必須選擇一組合適的代碼庫(kù)，從而使得分析合理并有價(jià)值[2]。

2.1 克隆檢測(cè)

對(duì)于克隆檢測(cè)工具，評(píng)估了CCFinder以及C lone Digger。二者都功能強(qiáng)大，結(jié)果精確，并具有支持多種語(yǔ)言的設(shè)計(jì)。評(píng)估與比較請(qǐng)見下文的列表。最終，選擇了C lone Digger，因?yàn)樽鰹殚_源軟件，它更方便進(jìn)行擴(kuò)展。

①用戶界面:CCFinder擁有漂亮的代碼克隆分布圖界面，使得代碼克隆的分布可以非常直觀地呈現(xiàn)出來(lái)；CCFinder還擁有對(duì)比視圖，可以直接看到冗余代碼片段，而Clone Digger僅僅生成包含冗余代碼對(duì)比列表的HTML報(bào)告文檔，不過(guò)，這也已經(jīng)能夠滿足需要；

②技術(shù)：CCFinder是基于詞法分析的克隆檢測(cè)工具，而C lone Digger采用的是基于AST的算法，從而將更為精確；但其代價(jià)是，Clone Digger的運(yùn)行速度遠(yuǎn)遠(yuǎn)慢于CCFinder，但對(duì)人們來(lái)說(shuō)，C lone Digger的速度是可以接受的；

③可擴(kuò)展性：Clone Digger的代碼以開源的GPL許可協(xié)議發(fā)布，這使得人們可以非常方便地通過(guò)編寫AST適配器來(lái)擴(kuò)展它；雖然為一個(gè)語(yǔ)言編寫一個(gè)AST分析器要難于為其編寫一個(gè)可用于CCFinder的詞法分析器，但是，幾乎所有的現(xiàn)代編程語(yǔ)言都提供了用于解析其自身源代碼的AST分析器，只要直接使用就可以了，所以擴(kuò)展C loneDigger仍然是非常容易的。

C lone Digger的作者已經(jīng)實(shí)現(xiàn)了對(duì)Python和Java的支持。對(duì)其擴(kuò)展使其支持ECMAScript，Erlang和Haskell。這些代碼已經(jīng)回饋到了C lone Digger的代碼庫(kù)[3]。

2.2 選擇語(yǔ)言和特性

世界上有上百種程序設(shè)計(jì)語(yǔ)言，不可能去研究其中的每一個(gè)。因此，從中選出幾種，以確保人們的研究有意義、有價(jià)值。依照以下的標(biāo)準(zhǔn)來(lái)選擇所研究的語(yǔ)言。

①流行程度：該語(yǔ)言必須足夠流行，從而能夠找到規(guī)模足夠大的開源項(xiàng)目來(lái)構(gòu)；②建代碼庫(kù)：并使得研究能夠讓盡量多的人受益；③成熟度：該語(yǔ)言必須經(jīng)過(guò)了長(zhǎng)期的開發(fā)與進(jìn)化，因此它的設(shè)計(jì)和特性都較為穩(wěn)定；④標(biāo)準(zhǔn)化：該語(yǔ)言應(yīng)當(dāng)有一個(gè)標(biāo)準(zhǔn)，或是事實(shí)上的標(biāo)準(zhǔn)。例如，ECMA標(biāo)準(zhǔn)或是一個(gè)參考實(shí)現(xiàn)；⑤語(yǔ)法易于解析：由于能力有限，并且采用基于AST的克隆檢測(cè)算法，因此該語(yǔ)言的語(yǔ)法必須易于解析，或者是存在語(yǔ)法解析器可供直接使用。

參考上述標(biāo)準(zhǔn)，選擇了Python，ECMAScript，Erlang與Haskell做為研究目標(biāo)。做為業(yè)界最流行的編程語(yǔ)言，Java將被做為評(píng)測(cè)的基準(zhǔn)。每一個(gè)程序設(shè)計(jì)語(yǔ)言都有很多的特性和特點(diǎn)，研究不可能涵蓋它們的每一個(gè)方面。因此，從中選擇對(duì)消除代碼克隆有潛在影響力的特性進(jìn)行研究，如表1所示。

表1 各種程序設(shè)計(jì)語(yǔ)言特性比較

2.3 構(gòu)建源代碼庫(kù)

用于比較測(cè)試的源代碼庫(kù)由精心選擇的一系列開放源代碼項(xiàng)目的代碼構(gòu)建。這個(gè)代碼庫(kù)包括W eb應(yīng)用框架、語(yǔ)法分析程序生成器以及編程語(yǔ)言測(cè)試游戲這3類功能。用文中選擇的每一個(gè)語(yǔ)言實(shí)現(xiàn)了每一類功能的開源項(xiàng)目。所選擇的項(xiàng)目之間，同一個(gè)類別中的項(xiàng)目應(yīng)當(dāng)實(shí)現(xiàn)了相似的功能或用于相似的目的，并在其語(yǔ)言社區(qū)中有較高的流行度。文中比較每一個(gè)類別中的項(xiàng)目的代碼克隆覆蓋率，并將給出由各個(gè)類別的數(shù)據(jù)相加得到的綜合比較數(shù)據(jù)，對(duì)所選擇的開源項(xiàng)目的概覽如表2所示。

表2 源代碼庫(kù)所包含的項(xiàng)目

3 結(jié)果與分析

按語(yǔ)言累計(jì)的代碼克隆覆蓋率如圖2所示。從圖中可以看到，在函數(shù)式編程語(yǔ)言中，有著明顯較少的克隆，尤其是在Haskell中。而Haskell是一個(gè)相對(duì)有著更多特性的語(yǔ)言。不過(guò)，由于W eb應(yīng)用框架往往要比其他類別中的項(xiàng)目大得多，因此，圖2很大程度上由W eb應(yīng)用框架的數(shù)據(jù)所主導(dǎo)。

圖2 按語(yǔ)言累計(jì)的代碼克隆覆蓋率

為了表現(xiàn)其他因素對(duì)克隆覆蓋率的影響，統(tǒng)計(jì)了按類別累計(jì)的數(shù)據(jù)；以及包含所有項(xiàng)目的代碼克隆覆蓋率相對(duì)千代碼行(KLOC)。它與按語(yǔ)言累計(jì)的數(shù)據(jù)的計(jì)算方式相似。根據(jù)統(tǒng)計(jì)結(jié)果，編程語(yǔ)言測(cè)試游戲類別是僅有的一個(gè)有著更小的克隆覆蓋率的類別，這是因?yàn)樗且唤M簡(jiǎn)單的任務(wù)，因而有著較少的LOC。所以，認(rèn)為軟件項(xiàng)目的類型對(duì)于代碼克隆沒有大的影響。

4 結(jié)束語(yǔ)

代碼克隆出現(xiàn)的原因是復(fù)雜多樣的，語(yǔ)言特性對(duì)于代碼克隆的影響也同樣復(fù)雜[4]。通過(guò)擴(kuò)展C lone Digger使其支持更多的編程語(yǔ)言，并構(gòu)建一個(gè)包含了由不同語(yǔ)言寫成的不同種類的開源項(xiàng)目的源代碼庫(kù)，文中觀察到了代碼克隆現(xiàn)象在各個(gè)語(yǔ)言間的差異，并用語(yǔ)言的特性來(lái)解釋這些差異。除了語(yǔ)言特性，文中同樣考慮到了可能影響代碼克隆的其他因素。

實(shí)驗(yàn)結(jié)果指出，一般情況下，由于有著更多特性的語(yǔ)言，例如Python和Haskell寫成的代碼，往往有著較少的代碼克隆。但是，即使是有很高的表達(dá)能力的語(yǔ)言，如Python，所寫成的代碼，仍然會(huì)有著大量的克隆。導(dǎo)致克隆的原因是多種多樣的，可能是因?yàn)閮?yōu)化運(yùn)行效率的目的，可能是對(duì)某一編程風(fēng)格的偏愛，或者僅僅是難于被合并的代碼片段[5,6]。隨著計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的不斷進(jìn)化，越來(lái)越多的語(yǔ)言特性被開發(fā)出來(lái)，并將對(duì)消除代碼克隆有所幫助。但是，人們不能夠僅僅依靠某些語(yǔ)言特性來(lái)消除代碼克隆。仔細(xì)地設(shè)計(jì)和實(shí)現(xiàn)，有效的管理，永遠(yuǎn)是必須和最有效的消除克隆的方法。

[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.