重復(fù)代碼檢測(cè)技術(shù)的現(xiàn)究現(xiàn)狀

易長安

摘要:重復(fù)代碼是程序中最常見的“壞味道”,也是導(dǎo)致軟件維護(hù)費(fèi)用高昂的原因之一。關(guān)于重復(fù)代碼的重構(gòu)技術(shù)已經(jīng)研究了很多年了,該文主要對(duì)重復(fù)代碼檢測(cè)技術(shù)的國內(nèi)外研究現(xiàn)狀進(jìn)行分析和比較、指出了它們的優(yōu)缺點(diǎn),并在此基礎(chǔ)上展望了其以后的發(fā)展趨勢(shì)。

關(guān)鍵詞:重構(gòu);重復(fù)代碼;抽象語法樹;程序依賴圖;過程藍(lán)圖

中圖分類號(hào):TP311文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2009)20-0000-00

0 引言

軟件的本質(zhì)屬性是演化[1]。對(duì)于一家軟件公司來說,代碼是其重要的“遺產(chǎn)系統(tǒng)”,而重構(gòu)是實(shí)現(xiàn)軟件演化的主要方法,它可以大大提高“遺產(chǎn)系統(tǒng)”的價(jià)值?，F(xiàn)代主流的的軟件開發(fā)方法,如RUP和XP等都運(yùn)用重構(gòu)來支持迭代開發(fā),重構(gòu)是XP的基石。關(guān)于重構(gòu)的研究已經(jīng)有很多年了,但是,直到現(xiàn)在,沒有一種好的度量方法能夠勝過人的直覺,“何時(shí)在何地使用何種重構(gòu)”仍然是重構(gòu)技術(shù)所需要解決的主要問題之一,自動(dòng)化的重構(gòu)工具也依然是研究人員和程序員所最希望擁有的。

重構(gòu),就是對(duì)軟件系統(tǒng)作一些改變,它只改變軟件的內(nèi)部結(jié)構(gòu),而不改變代碼的外部行為[2]。重構(gòu)是一種改進(jìn)軟件的可維護(hù)性的技術(shù)。那些需要進(jìn)行重構(gòu)的地方被稱為壞味道[2]。重復(fù)代碼、長方法、長參數(shù)列表等都是常見的壞味道。

所謂重復(fù)代碼,是指那些彼此相似或者完全相同的代碼片段。有研究表明,在大型軟件中,重復(fù)代碼的比例高達(dá)5-10%[1]。重復(fù)代碼在所有的軟件中都是很常見的,它也是使得軟件的維護(hù)成本高昂的原因之一。大量的重復(fù)代碼會(huì)導(dǎo)致運(yùn)行時(shí)間的急劇增加[3]。

既然重復(fù)代碼的危害性這么大,那么,為什么它還如此普遍呢?一般認(rèn)為,重復(fù)代碼的產(chǎn)生有如下的原因[1]:

1) 復(fù)制已經(jīng)存在的代碼。當(dāng)要實(shí)現(xiàn)一個(gè)新的功能特別是當(dāng)有時(shí)間壓力時(shí),程序員往往首先去尋找已有的、實(shí)現(xiàn)了相似功能的代碼,然后拷貝過來,并稍微作一些修改。

2) 編碼風(fēng)格。特別是在驅(qū)動(dòng)程序的編寫方面,這種情況特別普遍。因?yàn)閷?duì)于各個(gè)驅(qū)動(dòng)程序來說,大部分代碼都有樣板可尋,僅僅只是核心部分需要作修改。

3) 對(duì)所定義的操作的實(shí)例化。程序員在這種情況下往往會(huì)使用宏。

4) 沒有充分利用抽象數(shù)據(jù)類型。有時(shí)候重用庫函數(shù)比“粘貼”更好。

5) 為了提高系統(tǒng)性能而有意讓代碼冗余,如實(shí)時(shí)系統(tǒng)。

6) 偶然的情況。有時(shí)候代碼段之間僅僅是偶然的一致,而并不是重復(fù)。

雖然復(fù)制-粘貼-剪切(以及一定的修改)被認(rèn)為是一種不好的做法,但實(shí)際上幾乎所有的程序員都使用這種方法。雖然復(fù)制代碼非常容易,但是,它使得軟件維護(hù)更加困難,主要表現(xiàn)在兩個(gè)方面[3]:

1) 當(dāng)代碼被復(fù)制時(shí),代碼中的錯(cuò)誤也在被復(fù)制;

2) 對(duì)初始代碼進(jìn)行修改時(shí)也必須同時(shí)對(duì)復(fù)制后的代碼進(jìn)行修改。

1 重復(fù)代碼的分類

重復(fù)代碼的危害性引起了軟件人員的高度重視,關(guān)于這方面的研究已經(jīng)進(jìn)行了很久,并且取得了一定的成果。現(xiàn)在,從以下幾個(gè)方面來討論重復(fù)代碼的研究狀況。

1.1 大型軟件系統(tǒng)中重復(fù)代碼的分類

Kapser等人對(duì)重復(fù)代碼進(jìn)行了初步的分類,并將這個(gè)分類與對(duì)Linux操作系統(tǒng)內(nèi)核的分析結(jié)合起來[4]。該項(xiàng)研究使用CCFinder來作為重復(fù)代碼檢測(cè)工具,結(jié)果表明重復(fù)不僅在文件系統(tǒng)內(nèi)部發(fā)生,而且在文件系統(tǒng)之間也存在大量的重復(fù)代碼。

Kapser將所檢測(cè)到的重復(fù)代碼分成了如下幾類:

1) 同一個(gè)函數(shù)里的重復(fù)代碼;

2) 同一個(gè)文件里的相似函數(shù);

3) 同一目錄下不同文件之間的重復(fù)函數(shù);

4) 不同目錄之間的重復(fù)函數(shù);

5) 文件重復(fù)(可能作了一些改變);

6) 不同文件之間的重復(fù)塊。

Kapser率先對(duì)大型軟件系統(tǒng)的重復(fù)狀況進(jìn)行研究,其另外的一個(gè)獨(dú)特之處是使用三維圖形來可視化重復(fù)信息。

1.2 類以及類之間的重復(fù)代碼

從軟件維護(hù)的角度看,重復(fù)代碼應(yīng)該被清除。但是,有時(shí)候這些重復(fù)代碼之間存在依賴關(guān)系,此時(shí)就需要一次性地將它們?nèi)壳宄?Norihiro Yoshida等人為此定義了“方法鏈”[4]。所謂“方法鏈”,是指一系列有依賴關(guān)系的方法。如果一系列“方法鏈”彼此互為重復(fù)關(guān)系的話,那么就稱其為“重復(fù)鏈”,與“重復(fù)鏈”相對(duì)應(yīng)的類就稱為“重復(fù)鏈集合”。 Norihiro Yoshida等人對(duì)“重復(fù)鏈集合”進(jìn)行了分類,并為它們分別提出了相應(yīng)的重構(gòu)模式,而且,還在一些實(shí)際案例中對(duì)所提出的方法的正確性進(jìn)行了驗(yàn)證。這篇文章還提出了度量方法來衡量重復(fù)方法之間的距離(根據(jù)這些方法所在的類的關(guān)系來求值)。該項(xiàng)研究還通過所實(shí)現(xiàn)的原型工具Aries來對(duì)三個(gè)軟件ANTER、Tomcat和JBoss的重復(fù)情況進(jìn)行分析,進(jìn)而評(píng)價(jià)方法的正確性,結(jié)果發(fā)現(xiàn)不同風(fēng)格的軟件其重復(fù)代碼的特點(diǎn)也是不同的。

2 重復(fù)代碼的檢測(cè)方法

研究重復(fù)代碼的最終目的是為了把理論成果轉(zhuǎn)換為產(chǎn)品,提高重復(fù)代碼的檢測(cè)和改進(jìn)效率。

2.1 基于抽象語法樹的重復(fù)代碼檢測(cè)方法

以前的重復(fù)檢測(cè)方法只能檢測(cè)出那些極為相似的代碼片段或者完整函數(shù)之間的代碼片段。Baxter[1]等人提出的基于抽象語法樹的方法是一種簡單而且實(shí)用的重復(fù)檢測(cè)方法,它能夠檢測(cè)出源代碼中任意片段之間的重復(fù)情況。該方法是在程序的結(jié)構(gòu)上進(jìn)行操作,所以可以通過一些常用的方法來清除重復(fù)代碼。重復(fù)檢測(cè)中最基本的問題就是找出那些有相同功能的代碼片段,以往的方法很難對(duì)某個(gè)功能的起止位置進(jìn)行定位,而基于抽象語法樹的方法可以做到這一點(diǎn)。使用抽象語法樹來檢測(cè)重復(fù)代碼的第一步就是將源代碼解析成抽象語法樹,然后陸續(xù)應(yīng)用三種算法來尋找重復(fù)代碼。其中,第一個(gè)算法用來檢測(cè)子樹重復(fù),第二個(gè)算法用來檢測(cè)連續(xù)重復(fù),第三個(gè)算法用來檢測(cè)更加復(fù)雜的重復(fù)。

2.2 使用程序依賴圖來識(shí)別相似代碼

雖然存在很多種檢測(cè)重復(fù)代碼的方法,但是大部分都只能檢測(cè)出完全一致的重復(fù)代碼,而通常情況下程序員都對(duì)復(fù)制過來的代碼進(jìn)行了一定的修改。Jens Krinke提出的方法是基于在屬性有向圖里尋找相似子圖進(jìn)而來識(shí)別相似代碼[3]。該方法使用程序依賴圖,既要考慮程序的句法結(jié)構(gòu)也要考慮數(shù)據(jù)流結(jié)構(gòu),因此也就不需要在精確和回溯之間進(jìn)行折衷(所謂精確,是指所發(fā)現(xiàn)的重復(fù)代碼中那些沒有價(jià)值的重復(fù)代碼的數(shù)量;所謂回溯,是指尚未發(fā)現(xiàn)的重復(fù)代碼的數(shù)量)。該方法還可以檢測(cè)到那些被修改了的重復(fù)代碼,它不僅僅是基于文本或者語法,而且還考慮語義。Jens Krinke提出的方法是基于精煉了的程序依賴圖,程序依賴圖描述程序的結(jié)構(gòu)和數(shù)據(jù)流。在這些圖里,我們主要是識(shí)別由重復(fù)代碼所產(chǎn)生的相似子圖,所識(shí)別出來的相似子圖可以被直接映射到程序源代碼并呈現(xiàn)給用戶。

2.3 基于過程藍(lán)圖的重復(fù)代碼檢測(cè)方法

Roberts[5]在其博士論文中指出,表達(dá)式變換最自然的方式是使用樹到樹的變換規(guī)則。過程藍(lán)圖[6]是一種圖形化程序過程規(guī)格說明方法,是對(duì)過程的源代碼進(jìn)行描述的模型,其本質(zhì)上是抽象語法樹,具有豐富的語義,因而具有對(duì)程序重構(gòu)、重復(fù)代碼檢測(cè)的支持能力。

2.4 一種關(guān)于重復(fù)代碼檢測(cè)的新思想

軟件維護(hù)的確很重要,關(guān)于這方面的工作大部分是提出新的方法來創(chuàng)建或者修改軟件。但是,由于當(dāng)對(duì)一個(gè)問題理解的程度加深時(shí),就能夠產(chǎn)生更好的方法,所以,Rysselberghe等人通過研究軟件演化的方式而提出了一種新的方法[7]。其實(shí),Rysselberghe是把已有的技術(shù)按一種全新的方式來應(yīng)用,即不是尋找那些代表重復(fù)關(guān)系的匹配,而是尋找那些反映程序發(fā)生了變化的非匹配。Dotplogs是一種可視化技術(shù),它最初是被用來檢測(cè)DNA序列的相似性,但是后來被用來分析重復(fù)代碼。該項(xiàng)研究使用重復(fù)檢測(cè)工具Duploc來對(duì)Tomcat的五個(gè)不同版本進(jìn)行比較?！癕oving methods”被認(rèn)為是重構(gòu)的重要組成部分[8],在該項(xiàng)研究中也得到了證實(shí)。另外,Rysselberghe還得出了一個(gè)重要結(jié)論:“Moving methods”更重要的目的不是消除代碼冗余而是將功能聚合(即讓一組實(shí)體完成某一個(gè)特定的功能)。

3 各種重復(fù)代碼檢測(cè)技術(shù)的比較

在過去的十多年里,開展了大量的關(guān)于重復(fù)代碼方面的研究,有些研究還是在大型軟件上進(jìn)行,所有這些技術(shù)都有各自的優(yōu)缺點(diǎn)。Rysselberghe等人比較了三種有代表性的檢測(cè)技術(shù),即簡單行匹配、參數(shù)化匹配和度量方法[9],結(jié)果發(fā)現(xiàn)這三種技術(shù)均有各自的適應(yīng)性:簡單行匹配適用于對(duì)重復(fù)代碼的初步探測(cè);參數(shù)化匹配最好與能夠在語句層次上執(zhí)行重構(gòu)的工具結(jié)合使用;度量技術(shù)最好與能夠消除重復(fù)子程序的重構(gòu)工具結(jié)合使用。

重復(fù)代碼的檢測(cè)由轉(zhuǎn)換和比較兩個(gè)階段組成。在第一個(gè)階段,源代碼被轉(zhuǎn)換成一種內(nèi)部表示形式,在第二個(gè)階段才執(zhí)行真正的匹配過程。根據(jù)源代碼轉(zhuǎn)換后的內(nèi)部格式,可以把重復(fù)檢測(cè)技術(shù)分成三類:基于字符串、基于符號(hào)流和基于分析樹?；谧址募夹g(shù)都獨(dú)立于編程語言,它們僅僅是字符串比較算法的不同?；诜?hào)流的技術(shù)所使用的轉(zhuǎn)換算法更加復(fù)雜,還需要用到詞法分析器。基于分析樹的技術(shù)使用一種重量級(jí)的轉(zhuǎn)換算法,即創(chuàng)建分析樹。分析樹的信息豐富,可以在分析樹上進(jìn)行各種算法的比較。通過對(duì)這些技術(shù)的比較,可以為更加系統(tǒng)化地檢測(cè)和消除重復(fù)代碼奠定一個(gè)良好的基礎(chǔ)。

隨著對(duì)大型軟件的需求不斷增加,重復(fù)代碼的探測(cè)與消除問題也變得越來越重要。以上列舉了四種有代表性的重復(fù)代碼檢測(cè)方法,在以后的研究中,新的方法將會(huì)不斷涌現(xiàn)。

4 總結(jié)

關(guān)于重復(fù)代碼方面的研究工作正在進(jìn)行,新的檢測(cè)方法和檢測(cè)工具會(huì)不斷地出現(xiàn)。以前的研究中,雖然提出了檢測(cè)方法并進(jìn)行了試驗(yàn)性的驗(yàn)證,但是,都不是大規(guī)模的,不具有很強(qiáng)的說服力。所以,今后的一個(gè)研究方向就是將所提出的方法應(yīng)用到商業(yè)軟件中,以便從更深層次和更廣范圍來檢驗(yàn)其正確性。

另外,雖然在軟件設(shè)計(jì)度量和軟件代碼度量方面開展了深入的研究,但是,這些度量還沒有被廣泛地運(yùn)用,使用度量與不使用度量的積極意義與不良影響都很值得研究[9]。

重復(fù)代碼都是在源代碼中產(chǎn)生,既然它的危害如此之大,那么,從另一個(gè)角度說,源代碼的設(shè)計(jì)也就變得更加重要了[10]。

參考文獻(xiàn):

[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] 劉建賓.過程藍(lán)圖設(shè)計(jì)方法學(xué)[M].北京:科學(xué)出版社,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).