張久杰 翟曄 王春暉 張麗萍 劉東升

摘要：針對(duì)當(dāng)前克隆譜系的構(gòu)建方法較為復(fù)雜、演化模式亟需擴(kuò)充等問題，提出了新的克隆代碼演化模式，并根據(jù)軟件版本間的克隆代碼映射關(guān)系自動(dòng)構(gòu)建了克隆譜系。首先，針對(duì)軟件每一版本進(jìn)行克隆檢測(cè)并利用潛在狄利克雷分配（LDA）抽取克隆代碼的主題信息；然后，根據(jù)克隆代碼主題的相似度確定版本間克隆代碼的映射關(guān)系；進(jìn)而，根據(jù)已有的映射關(guān)系為克隆代碼添加演化模式并分析演化特征；最終，結(jié)合映射信息與演化模式信息完成克隆譜系的構(gòu)建。針對(duì)4款開源軟件進(jìn)行了克隆譜系的構(gòu)建實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明所提克隆譜系構(gòu)建方法可行，證實(shí)了新提出的演化模式在克隆代碼演化過程中確實(shí)存在。實(shí)驗(yàn)發(fā)現(xiàn)約90%的克隆代碼在軟件演化過程中比較穩(wěn)定，約67%的克隆群經(jīng)歷的發(fā)布版本數(shù)不超過發(fā)布版本總數(shù)的一半。實(shí)驗(yàn)結(jié)論及理論分析將為克隆代碼的后續(xù)研究及克隆代碼的維護(hù)與管理提供有力支持。

關(guān)鍵詞：

克隆代碼；主題建模；軟件演化；演化模式；克隆譜系；軟件維護(hù)

中圖分類號(hào)： TP311.5； TP18 文獻(xiàn)標(biāo)志碼：A

0引言

克隆代碼（Code Clone）是指軟件系統(tǒng)中一些具有相同或者相似的語法或語義特征的代碼片段?？寺〈a在軟件系統(tǒng)中普遍存在，并且與軟件工程領(lǐng)域中的各類研究問題密切相關(guān)。軟件單一版本中的基礎(chǔ)性克隆代碼數(shù)據(jù)已經(jīng)難以呈現(xiàn)克隆代碼在軟件演化過程中的變化情況，因此，需要對(duì)軟件中的克隆代碼進(jìn)行演化跟蹤并分析演化情況，從而獲得更全面的信息，為軟件開發(fā)及維護(hù)提供更多幫助。

當(dāng)前的克隆譜系構(gòu)建方法存在一些不足之處，例如克隆演化模式單一、克隆譜系構(gòu)建方法復(fù)雜、能夠分析的克隆類型及編程語言不全面等。本文提出了新的克隆演化模式、克隆演化特征以及克隆譜系的自動(dòng)化構(gòu)建方法。以區(qū)分視角的方式更加全面地分析了克隆代碼的演化模式，利用代碼主題信息確立版本間克隆代碼映射并最終構(gòu)建克隆譜系。本文研究結(jié)果將為軟件開發(fā)、軟件維護(hù)、軟件重構(gòu)及克隆管理等工作提供參考。

1相關(guān)工作

1.1克隆代碼簡(jiǎn)介

在軟件開發(fā)及維護(hù)過程中，由于程序員經(jīng)常使用“拷貝/粘貼/修改”的開發(fā)方式、使用相同或相似的應(yīng)用程序接口（Application Program Interface， API）及算法等因素，導(dǎo)致軟件系統(tǒng)中存在大量相同或相似度非常高的代碼片段，稱為克隆代碼。在該研究領(lǐng)域，經(jīng)過學(xué)者們多年研究，已經(jīng)達(dá)成了克隆代碼至少應(yīng)該被檢測(cè)的基本共識(shí)。

克隆代碼的研究工作最早可追溯到20世紀(jì)90年代，隨后，該研究領(lǐng)域受到越來越多國內(nèi)外相關(guān)研究者的高度關(guān)注，并在克隆檢測(cè)、克隆演化、克隆分析以及克隆重構(gòu)等方面產(chǎn)生了大量研究成果[1]。

在該研究領(lǐng)域，克隆代碼以Type1、Type2、Type3和Type4的方式分類最為流行[2]。Type1指除空白符與注釋變化外完全相同的代碼段；Type2指除空白符、注釋、標(biāo)識(shí)符、類型及常量的替換外句法結(jié)構(gòu)完全相同的代碼段；Type3是指除空白符、注釋、標(biāo)識(shí)符、類型替換外，句法結(jié)構(gòu)基本相同，但含有少量語句增加、刪除或修改的代碼段；Type4克隆代碼則為功能相似或相同但句法結(jié)構(gòu)不同的代碼段。根據(jù)克隆代碼檢測(cè)的反饋粒度，相關(guān)工作通常以克隆對(duì)或克隆群（也稱克隆集合、克隆類）為基本單位進(jìn)行克隆代碼的研究?？寺?duì)是指存在克隆關(guān)系的一對(duì)代碼片段。克隆群代表一些克隆代碼的集合，同一克隆群內(nèi)的任意兩個(gè)代碼片段可以構(gòu)成克隆對(duì)，不同克隆群之間的克隆代碼通常不具有克隆關(guān)系。

圖1呈現(xiàn)了來自同一個(gè)克隆群的三段克隆代碼CF1、CF2和CF3。由克隆代碼類型的定義可知，CF1與CF2為Type2克隆關(guān)系、CF2與CF3為Type2克隆關(guān)系、CF1與CF3也構(gòu)成了Type2克隆關(guān)系。在這三段代碼中，只有函數(shù)名以及一處標(biāo)識(shí)符不同，所以三者之間均可構(gòu)成Type2類型克隆對(duì)。

1.2克隆演化與克隆譜系

隨著軟件需求的不斷增加，軟件需要不斷升級(jí)，軟件中的克隆代碼也可能隨著軟件演化而發(fā)生改變。在分析克隆代碼為軟件帶來的影響時(shí)，不但要研究軟件單一版本中的克隆，還要研究克隆代碼以時(shí)間為序的演化問題[3-4]?；诖?，一些研究者從宏觀上分析了克隆代碼的數(shù)量或密度隨著多版本演化的變化情況[5-6]，從微觀上利用演化模式來研究克隆代碼的演化過程也受到研究者的廣泛關(guān)注[7]。

Kim等[8]在2005年最早提出了克隆譜系的概念，并用克隆譜系抽取工具對(duì)克隆代碼的演化進(jìn)行分析[9]。隨后，借助于克隆譜系研究克隆代碼便在該領(lǐng)域成為了一種基本研究方法。例如，Zibran等[10]借助克隆譜系對(duì)軟件演化過程中克隆代碼的去除活動(dòng)進(jìn)行了研究。Saha等針對(duì)17款C、C++、Java及C#語言的開源軟件進(jìn)行了關(guān)于克隆譜系的實(shí)證研究[11]，并發(fā)現(xiàn)大部分克隆群在演化中要么不發(fā)生句法上的不一致改變，要么會(huì)發(fā)生一致性的改變。雖然克隆譜系已經(jīng)被廣泛用于克隆代碼演化研究，然而針對(duì)克隆譜系構(gòu)建方法本身的研究卻相對(duì)較少。目前構(gòu)建克隆譜系的方法主要可以分為4種，分別為基于版本控制系統(tǒng)（Control Version System， CVS）或SVN（Subversion）、基于增量克隆檢測(cè)、基于克隆區(qū)域描述符（Clone Region Descriptor， CRD）以及基于相似度距離函數(shù)。

基于版本控制系統(tǒng)的方法通常借助SVN或CVS中的修改日志來計(jì)算相鄰版本間克隆代碼的變化情況實(shí)現(xiàn)對(duì)克隆代碼進(jìn)行演化跟蹤，進(jìn)而按照時(shí)序關(guān)系合并修改信息，得到克隆譜系。由于該方法以某一選定版本中的克隆代碼作為起源并進(jìn)行跟蹤，很難處理軟件后續(xù)版本中新增的克隆代碼。

Gde等[12]使用增量克隆檢測(cè)技術(shù)構(gòu)建了克隆譜系，然而該方法只適合處理給定版本的軟件，當(dāng)有新的版本加入后，整個(gè)方法需要重新執(zhí)行，時(shí)空消耗均非常高，所以該方法難以靈活應(yīng)對(duì)具有新增版本的克隆譜系構(gòu)建工作。

基于相似度距離函數(shù)的方法通常要結(jié)合抽象語法樹（Abstract Syntax Tree， AST）、Token等代碼中間表示形式，該類方法的核心算法時(shí)空復(fù)雜度相對(duì)偏高。Bakota[13]提出了一種的基于相似度距離函數(shù)并結(jié)合抽象語法樹的克隆譜系構(gòu)建方法，并針對(duì)軟件的多個(gè)版本進(jìn)行了克隆代碼的演化研究。Ying等[14]提出了基于Token與源碼相結(jié)合的克隆譜系構(gòu)建方法，但該方法只能在Linux系統(tǒng)下處理C語言的Type1和Type2類型的克隆代碼，對(duì)其他程序設(shè)計(jì)語言或其他克隆類型的演化研究存在著很大的局限性。Saha等[15]提出了基于文本并結(jié)合代碼位置信息的方法構(gòu)建了克隆譜系。該方法首次對(duì)Type3克隆代碼進(jìn)行了克隆譜系的構(gòu)建研究，然而由于該方法需要處理文件位置變化、方法重命名等問題導(dǎo)致了構(gòu)建方法較為復(fù)雜。

基于CRD的方法在構(gòu)建克隆譜系時(shí)也存在一定的局限性，如果代碼某些部分（如循環(huán)終止條件、代碼的嵌套結(jié)構(gòu)、條件語句的分支謂詞等）發(fā)生變化，則可能會(huì)導(dǎo)致CRD的失效，這將嚴(yán)重影響克隆譜系構(gòu)建的全面性和準(zhǔn)確性。Meng等[16]基于CRD確立了相鄰版本間克隆群映射關(guān)系，然后基于二元關(guān)系合成方法研究了克隆譜系的構(gòu)建。

1.3克隆演化模式與演化特征

克隆演化模式從微觀上體現(xiàn)了克隆代碼隨著軟件不同版本的演化而發(fā)生的變化情況。雖然不同研究問題針對(duì)克隆演化模式的分類有所不同，但對(duì)相同或相似的克隆演化行為的分類大致相同。根據(jù)匹配粒度及版本長度，可以將克隆演化模式大體上分為3類。

第1類是克隆群在兩個(gè)版本間的演化模式。Kim等[8]最早開展了相關(guān)研究，將演化模式分為無變化、增加、去除、一致變化、不一致變化和位移6種模式。Ying等[14]以Kim等[8]的演化模式概念集為出發(fā)點(diǎn)，識(shí)別了除位移模式以外的其他5種模式。

第2類是克隆片段在兩個(gè)版本間的演化模式。Bakota等[17]介紹了4種不同的克隆片段演化方式，包括消失克隆實(shí)例、發(fā)生克隆實(shí)例、移動(dòng)克隆實(shí)例以及遷移克隆實(shí)例。

第3類是研究克隆群在多個(gè)版本中的長期演化模式，包括延遲傳播（Late Propagation， LP）模式以及獨(dú)立演化模式等[18-19]。

克隆代碼演化特征可以從生命周期以及譜系結(jié)構(gòu)等視角對(duì)克隆代碼的演化過程進(jìn)行分析。各類演化模式出現(xiàn)的時(shí)間及位置信息可以反映克隆代碼的變化方式?？寺〈a的演化特征將為克隆演化分析提供最基本的參考信息。長期性的克隆演化模式與演化特征將為軟件后期開發(fā)及維護(hù)活動(dòng)提供更多具有決策性的意見。

1.4基于主題建模技術(shù)研究軟件演化

近年來，主題建模技術(shù)已不斷地應(yīng)用于軟件工程領(lǐng)域。Kuhn等[20]將主題建模技術(shù)應(yīng)用于代碼分析，并嘗試從中挖掘出代碼的功能性主題；Thomas等[21]驗(yàn)證了利用主題建模技術(shù)進(jìn)行軟件演化分析是具有可行性的，并利用主題建模技術(shù)研究了軟件的演化情況[22]；Asuncion等[23]將主題建模技術(shù)用于軟件的可追蹤性研究；金靖等[24]運(yùn)用潛在狄利克雷分配（Latent Dirichlet Allocation， LDA）模型識(shí)別代碼功能以支持軟件開發(fā)人員對(duì)代碼進(jìn)行良好的理解與復(fù)用；張瑞霞等[25]通過LDA主題模型針對(duì)軟件相鄰版本中的克隆群進(jìn)行了映射研究，但并未構(gòu)建克隆譜系也未深入分析克隆代碼的演化模式和演化特征；Phan等[26]分析比較了LDA、概率隱語義分析（Probability Latent Semantic Analysis，PLSA）、潛在語義分析（Probability Semantic Analysis，LSA）等主題模型，并證明了LDA在挖掘文檔潛在語義時(shí)比其他模型表現(xiàn)更佳。

1.5小結(jié)

通過分析、總結(jié)上述相關(guān)研究現(xiàn)狀可知，現(xiàn)有克隆譜系構(gòu)建方法主要存在以下不足：

1）依賴代碼位置信息且構(gòu)建流程相對(duì)繁瑣。

2）無法處理軟件在演化過程中新增的克隆代碼。

3）代碼語句格式對(duì)克隆譜系的構(gòu)建存在影響。

4）不能處理Type3及Type4克隆代碼。

5）可移植性較差、編程語言不可擴(kuò)展。

6）嚴(yán)重依賴特定的克隆代碼檢測(cè)工具。

本文提出了一種基于主題建模技術(shù)的克隆譜系構(gòu)建方法，通過映射克隆代碼的主題信息進(jìn)行克隆譜系的構(gòu)建。與基于相似度距離函數(shù)的方法相比，本文方法不需要代碼的中間表示形式（如Token、AST），流程相對(duì)簡(jiǎn)單；與基于增量克隆檢測(cè)的方法相比，本文針對(duì)新增版本的克隆譜系構(gòu)建而言具有良好的可擴(kuò)展性。因?yàn)楸疚姆椒ㄖ恍韪鶕?jù)增版本中克隆代碼的主題信息即可擴(kuò)展原有克隆譜系，而基于增量克隆檢測(cè)的方法則需要重新執(zhí)行整個(gè)構(gòu)建過程；與基于CRD的方法相比，本文方法直接利用主題信息構(gòu)建譜系，避免了由于循環(huán)終止及條件語句的變化等情況造成的相鄰版本間克隆代碼映射失敗或錯(cuò)誤的問題。此外，由于本文借助于代碼的主題信息，所以能支持多種程序設(shè)計(jì)語言及多種代碼粒度的克隆譜系構(gòu)建研究，而且能夠有效處理Type3甚至Type4克隆代碼，而不僅局限于Type1和Type2克隆。本文方法不依賴任何特定的克隆代碼檢測(cè)工具，只需運(yùn)用主題模型從克隆檢測(cè)結(jié)果中抽取主題即可。本文將在原型系統(tǒng)的實(shí)現(xiàn)中將克隆代碼檢測(cè)工具視為插件，以支持多種克隆檢測(cè)工具。

自Kim等[8]提出克隆譜系概念以及克隆演化研究中所使用的6種模式后，該領(lǐng)域研究者大多以其作為基準(zhǔn)框架進(jìn)行克隆代碼的演化研究，即便有新的模式提出也只是針對(duì)部分或個(gè)別演化現(xiàn)象而言，例如LP模式[18-19]。

通過分析現(xiàn)有研究中的克隆演化模式可以發(fā)現(xiàn)，前期研究者們不區(qū)分視角地分析各種演化模式，例如Kim等[8]提出的6種模式中，無變化、一致變化和不一致變化是針對(duì)克隆代碼的數(shù)量和文本內(nèi)容而言的，而位移則是針對(duì)代碼位置的變化而言，增加和去除模式則是針對(duì)克隆群內(nèi)代碼片段數(shù)量而言的。這些演化模式屬于不同的視角，但某些視角中顯然缺少一些演化模式來解釋不同的演化現(xiàn)象，例如Kim等[8]的模式中雖然包含了克隆群內(nèi)代碼片段數(shù)量的增加與去除，但并未包含片段數(shù)量不變這一模式，這個(gè)模式與其提出的無變化模式是不沖突的，因?yàn)橐粋€(gè)克隆群內(nèi)的克隆片段數(shù)量不變的情況下，克隆代碼的文本內(nèi)容是完全可以發(fā)生改變的。

本文區(qū)分視角地重新定義了傳統(tǒng)意義上的克隆演化模式，并提出了新的演化模式，將從克隆群生存情況、克隆群內(nèi)片段數(shù)量與克隆代碼片段內(nèi)容這三個(gè)視角來分析克隆代碼的演化模式，這使得不同演化模式之間的區(qū)別更加清晰，模式識(shí)別的方法也將會(huì)變得簡(jiǎn)單。

通過分析1.4節(jié)的相關(guān)研究可知，基于主題建模技術(shù)的軟件演化分析已經(jīng)取得了很大的成功，并且這些研究問題充分證明了主題建模技術(shù)是可以用于軟件工程領(lǐng)域中的眾多問題，包括軟件的理解與演化分析等。LDA已經(jīng)被廣泛并成熟地運(yùn)用在人工智能及自然語言處理等領(lǐng)域，而且文獻(xiàn)[20-26]可以充分說明利用LDA進(jìn)行軟件演化分析是可行的。本文將使用LDA對(duì)克隆代碼進(jìn)行主題建模分析，從而根據(jù)克隆代碼的主題信息進(jìn)行克隆群映射、演化模式識(shí)別及克隆譜系構(gòu)建等工作。

2演化模式識(shí)別及克隆譜系構(gòu)建方法

本文的克隆譜系構(gòu)建方法主要分為5個(gè)核心步驟：

第1步針對(duì)軟件多版本分別進(jìn)行克隆代碼檢測(cè)并獲取克隆檢測(cè)結(jié)果；

第2步以克隆群為基本單位進(jìn)行克隆代碼的主題信息抽??；

第3步進(jìn)行克隆群以及克隆片段的映射；

第4步識(shí)別各類克隆演化模式、分析克隆演化特征；

第5步合并映射結(jié)果與克隆演化模式，完成克隆譜系的構(gòu)建工作。

主要流程如圖2所示。

2.1克隆檢測(cè)及代碼主題抽取

克隆檢測(cè)是克隆代碼研究領(lǐng)域中的基礎(chǔ)性、必要性工作，克隆檢測(cè)的反饋結(jié)果能為克隆代碼分布分析、演化分析、重構(gòu)分析等研究提供最基本的數(shù)據(jù)支持。本文借助現(xiàn)有克隆代碼檢測(cè)工具對(duì)軟件的多個(gè)版本進(jìn)行克隆代碼檢測(cè)。選取了CloneDetective[27]以及本文的前期研究開發(fā)的克隆代碼檢測(cè)工具FClones[28]作為本文實(shí)驗(yàn)時(shí)所使用的克隆代碼檢測(cè)工具。CloneDetective能有效檢測(cè)Java語言的Type1、Type2和Type3克隆代碼，F(xiàn)Clones能有效檢測(cè)C語言的Type1、Type2和Type3克隆代碼。這兩款工具的克隆代碼檢測(cè)結(jié)果將為本文的克隆譜系構(gòu)建研究提供基礎(chǔ)性數(shù)據(jù)。

當(dāng)軟件多個(gè)版本的克隆檢測(cè)完成后，每個(gè)版本中都會(huì)含有一定數(shù)量的克隆群，而相鄰版本間的克隆群映射是構(gòu)建整個(gè)克隆譜系工作中不可缺少的部分。在軟件的每個(gè)版本中，由于同一克隆群內(nèi)的克隆代碼有較高的語法及語義的相似性，而不同克隆群之間克隆代碼的相似程度卻較低。所以，相鄰版本中對(duì)應(yīng)的克隆群之間的主題信息具有較高的相似性，而非對(duì)應(yīng)的克隆群之間的主題信息差異較大?；诖?，本文以克隆群為基本單位進(jìn)行克隆代碼的主題信息抽取，并基于主題的相似性進(jìn)行版本之間的克隆群映射。

本文將使用LDA主題模型對(duì)克隆代碼進(jìn)行主題信息抽取。抽取主題之前需對(duì)代碼進(jìn)行預(yù)處理，方法參考了文獻(xiàn)[24]中使用的靜態(tài)分析以及切詞方法。經(jīng)過切詞后還需針對(duì)部分單詞進(jìn)行過濾處理，因?yàn)槌醪角性~的結(jié)果中會(huì)包含大量的編程語言關(guān)鍵字、Java開發(fā)工具包（Java Developers Kit， JDK）中的類名和接口名及英文中常見的停用詞。過濾之后的結(jié)果作為主題模型的輸入數(shù)據(jù)，然后利用LDA對(duì)克隆群抽取主題。抽取結(jié)果中包含了不同克隆群主題對(duì)應(yīng)的主題詞，本文以克隆群主題詞集合的相似性作為克隆群映射的基本依據(jù)。

2.2克隆群映射

針對(duì)版本間克隆群主題詞集合的相似性計(jì)算問題，本文使用Jaccard相似度計(jì)算模型，之所以采用此計(jì)算模型是考慮了每個(gè)克隆群的主題詞集可視為一個(gè)集合，因此可以利用該模型計(jì)算兩個(gè)克隆群主題詞集之間的相似程度。Jaccard相似度模型計(jì)算兩個(gè)集合A與B的相似度如式（1）所示：

JaccardSim（A，B）=A∩B/A∪B（1）

針對(duì)多版本克隆群映射問題，本文設(shè)計(jì)了映射算法，如算法1所示。算法思想為：按照版本時(shí)序關(guān)系，每個(gè)克隆群在后一版本中先尋找一個(gè)最相似的克隆群作為后繼進(jìn)行映射，此為第一輪映射。之后，對(duì)于任意一個(gè)沒有前驅(qū)的克隆群，在其前一版本中尋找前驅(qū)，如果找到滿足條件的克隆群則進(jìn)行映射；對(duì)于任意一個(gè)沒有后繼的克隆群，在其后一版本中再次尋找后繼，如果找到滿足條件的克隆群則進(jìn)行映射，此為第二輪映射。第二輪映射完成后，對(duì)于任意一個(gè)無后繼的克隆群，從其下下版本開始，找一個(gè)與其最相似的而且無前驅(qū)的克隆群，如果找到滿足條件的克隆群則進(jìn)行映射并結(jié)束尋找，此為第三輪映射。至此所有克隆群映射工作完成。

算法1Clone Group Mapping。

有序號(hào)的程序——————————Shift+Alt+Y

程序前

1）

for each version∈versions do

2）

for each cg∈version do

3）

cg.pre=[]，cg.next=[]

4）

end for

5）

end for

6）

for each version∈versions do

7）

for each cg∈version do

8）

cg.next.append（cg.findNext（version.next））

9）

end for

10）

end for

11）

for each version∈versions do

12）

for each cg∈version do

13）

if cg.pre==[] then

14）

cg.pre.append（cg.findPre（version.pre））

15）

end if

16）

end for

17）

end for

18）

for each version∈versions do

19）

for each cg∈version do

20）

if cg.next==[] then

21）

cg.next.append（cg.findNext（version.next））

22）

end if

23）

end for

24）

end for

25）

for each version∈versions do

26）

for each cg∈version do

27）

nextVersion=（version.next）.next

28）

while cg.next==[] and nextVersion do

29）

if cg.findNext（nextVersion） then

30）

break

31）

nextVersion=nextVersion.next

32）

end if

33）

end while

34）

end for

35）

end for

程序后

在算法1中，Vi和Vi+1分別代表軟件中的兩個(gè)相鄰版本，CGi， j代表版本Vi中編號(hào)為j的克隆群，CGi， j.pre記錄CGi， j映射到了前一版本（或更前版本）中對(duì)應(yīng)的克隆群編號(hào)信息。CGi， j.next記CGi， j映射到了后一版本（或更后版本）中對(duì)應(yīng)的克隆群編號(hào)信息。在映射算法中，首先將當(dāng)前版本Vi中的所有克隆群CGi， j的后繼初始化為空，將后一版本Vi+1中所有克隆群的前驅(qū)初始化為空，然后再進(jìn)行三輪映射。findNext和findPre函數(shù)分別代表在某一版本中為當(dāng)前克隆群尋找后繼克隆群、前驅(qū)克隆群并返回相應(yīng)的克隆群的編號(hào)信息。version.pre和version.next分別代表當(dāng)前版本的前一版本及后一版本。

在算法1中，相鄰版本間克隆群映射的條件相對(duì)嚴(yán)格，對(duì)于當(dāng)前版本Vi中的任一克隆群CGi， j而言，在后一版本Vi+1中映射到的克隆群CGi+1，k是所有Vi+1的克隆群中與CGi， j的主題相似度最高的，而不是僅僅在滿足相似度閾值的情況下即可進(jìn)行映射。這樣的映射規(guī)則保證了每一對(duì)映射包含的兩個(gè)克隆群都有非常高的主題相似度?？寺∪河成溥^程中，主題相似度閾值直接影響映射結(jié)果，參照了前期研究[25]中采用的克隆群映射相似度閾值，本文將主題相似度閾值暫設(shè)為0.8，但該值并非固定，本文將在原型工具的實(shí)現(xiàn)以及后續(xù)研究中對(duì)該閾值的設(shè)定問題進(jìn)行更詳細(xì)的研究。

克隆群映射完成后，除起始本中的克隆群沒有前驅(qū)、最終版本中的克隆群沒有后繼以外，如果某一克隆群未能找到其前驅(qū)，則說明該克隆群是新增克隆群，如果某一克隆群未能找到其后繼，則說明該克隆群在軟件演化的過程中可能被移除?？寺∪旱那膀?qū)與后繼信息將有助于判斷克隆代碼的演化模式類型。

圖3呈現(xiàn)了某款軟件多版本中的部分克隆群映射效果。圖中每一豎排圓點(diǎn)代表一個(gè)版本中的不同克隆群，每條線段代表映射關(guān)系，不同灰度和大小的圓形及線段代表了不同的映射關(guān)系與演化模式。

2.3克隆片段映射

由于單純的克隆群映射還不能夠呈現(xiàn)更多的克隆代碼演化信息，例如不一致變化等。所以，在相鄰版本間的克隆群映射完成后，還需要針對(duì)兩個(gè)對(duì)應(yīng)克隆群內(nèi)的克隆代碼片段進(jìn)行映射，以便識(shí)別出更多的克隆代碼演化模式與演化特征。由于存在映射關(guān)系的兩個(gè)克隆群內(nèi)的克隆代碼片段之間的相似程度相對(duì)較高，導(dǎo)致代碼主題信息區(qū)分度不大，所以片段映射時(shí)不能再次利用代碼的主題信息進(jìn)行匹配。

在Ying等[14]及Saha等[15]的克隆譜系構(gòu)建研究中，克隆片段的映射主要參考了位置信息，例如Saha等[15]在映射克隆代碼片段時(shí)，如果其所在的文件名、函數(shù)名及起止行號(hào)不變，在不匹配克隆代碼內(nèi)容的情況下就直接進(jìn)行映射。該類方法雖然能夠較快地進(jìn)行片段映射，但針對(duì)函數(shù)重命名以及代碼位置變化時(shí)，容易造成映射錯(cuò)誤。如果文件名、函數(shù)名等屬性不一致時(shí)，則還需要根據(jù)代碼文本內(nèi)容或中間形式進(jìn)行克隆片段的映射。如果不考慮文件的位置屬性而僅僅通過代碼相似性來映射克隆片段，則可能由于克隆代碼的位置改變而造成映射的偏差，所以為了綜合考慮克隆代碼片段的位置信息以及克隆代碼本身的相似性，本文針對(duì)克隆代碼片段映射任務(wù)定義了4種距離。

1）目錄距離。兩段克隆代碼所在目錄的相似程度。本文考慮了軟件演化過程中某些路徑名可能出現(xiàn)較小的修改，例如將某一目錄名“temp”改為“tmp”等，所以計(jì)算目錄相似度時(shí)不宜采用嚴(yán)格的字符串匹配。本文采用編輯距離來衡量兩個(gè)目錄的距離，這樣避免了由于個(gè)別目錄名修改而造成映射錯(cuò)位等問題。與Ying等[14]的克隆片段映射方法相比，本文考慮了目錄名可能修改的情況，所以對(duì)位置屬性的處理更為合理。

2）文件名距離。與目錄距離的定義類似，文件名距離是指文件名之間的編輯距離。之所以將目錄距離與文件名距離分開考慮是因?yàn)楹艽笠徊糠挚寺〈a會(huì)來自于同一源代碼文件，所以利用文件名距離輔助判斷克隆代碼片段映射關(guān)系可以大大減少其他距離的計(jì)算量。

3）簽名距離。在本文中，簽名是指能夠代表一段代碼的一個(gè)字符串，例如函數(shù)的簽名可以為函數(shù)名和參數(shù)列表。簽名距離為兩個(gè)代碼段對(duì)應(yīng)的簽名之間的編輯距離，簽名距離可以在路徑距離及文件名距離都相同時(shí)進(jìn)一步來判斷克隆代碼之間的相似度，因此可以用于克隆片段映射。

4）文本距離。文本距離的計(jì)算首先將源代碼視為字符串，進(jìn)而通過計(jì)算字符串的編輯距離得出克隆代碼的文本距離。當(dāng)待映射的克隆片段之間具有相同的目錄距離、文件名距離、簽名距離時(shí)，利用文本距離可以最終判斷克隆片段的映射關(guān)系。本文不僅僅使用文本距離進(jìn)行作為克隆片段的映射依據(jù)是考慮了片段映射的效率問題，前3種距離的計(jì)算量相對(duì)較少，可以大大節(jié)省克隆片段映射的時(shí)間。

為了綜合利用上述4種距離屬性進(jìn)行映射，制訂了以下具有優(yōu)先級(jí)的映射規(guī)則進(jìn)行克隆代碼片段映射，假設(shè)相鄰版本中已經(jīng)映射的兩個(gè)克隆群分別為CG與CG′。它們所包含的克隆片段的映射步驟為：

步驟1對(duì)于克隆群CG中的任一克隆片段CF與CG′中的所有克隆片段計(jì)算目錄距離，CF選擇與其目錄距離最小的克隆片段進(jìn)行映射，已經(jīng)映射的克隆片段不能再次參與映射。

步驟2如果目錄距離相等，CF選擇與其文件名距離最小的克隆片段映射，已經(jīng)映射的克隆片段不能再次參與映射。

步驟3如果文件名距離相等，CF選擇與其簽名距離最小的克隆片段映射，已經(jīng)映射的克隆片段不能再次參與映射。

步驟4如果簽名距離相等時(shí)，CF選擇與任意一個(gè)文本距離最小的克隆片段映射，已經(jīng)映射的克隆片段不能再次參與映射。

克隆片段的映射方法之所以不再使用類似克隆群的映射方法是考慮了克隆片段可能存在新增、去除等情況，所以可能存在克隆片段映射不完全的情況，即部分克隆片段未能與相鄰版本間的其他克隆片段建立映射關(guān)系，但這類信息將有助于克隆群容量演化模式及克隆代碼片段內(nèi)容層面演化模式的分析。

2.4克隆演化模式及其識(shí)別

當(dāng)相鄰版本間克隆群映射完成后，即可識(shí)別克隆群層面的演化模式。針對(duì)克隆群層面演化模式主要涉及到克隆群本身的生存情況以及群內(nèi)包含克隆代碼片段的數(shù)量的變化情況。

與其他研究方法相比，本文將克隆群與克隆片段的演化模式分開研究使得各種模式具有更加清晰的視角。Kim等[8]將演化模式分成6種，與本文所用模式不同的是，Kim等[8]的方法考慮了位移模式，即克隆代碼的位置發(fā)生了改變。本文方法更關(guān)注克隆群及克隆代碼內(nèi)容上的改變，所以不考慮位移模式，取而代之，本文將簡(jiǎn)單模式、復(fù)活模式與合并模式引入到演化模式概念集中。復(fù)活模式的產(chǎn)生意味著克隆代碼存在延遲傳播現(xiàn)象的可能。延遲傳播是指一些克隆代碼在演化過程中出現(xiàn)過內(nèi)容的不一致改變而分離，而在后續(xù)版本中又重新變?yōu)榭寺￡P(guān)系?？寺〈a的延遲傳播研究將有助于分析克隆代碼與Bugs的關(guān)系[18-19]，所以復(fù)活模式值得深入研究。

本文針對(duì)克隆群演化而言主要研究兩種視角下的九種演化模式，分別為克隆群生存視角下的6種模式包括：新生模式、消失模式、分支模式、合并模式、復(fù)活模式、簡(jiǎn)單模式；以及克隆群內(nèi)片段數(shù)量視角下的3種模式，包括：增加模式、去除模式和保持模式。每種模式的基本定義如下：

新生模式當(dāng)前版本中的某一克隆群與前續(xù)版本中的任何克隆群未能建立映射關(guān)系，即該克隆群無前驅(qū)。

消失模式當(dāng)前版本中的某一克隆群與后續(xù)版本中的任何克隆群未能建立映射關(guān)系，即該克隆群無后繼。

分支模式當(dāng)前版本中的某一克隆群在后一版本中與多個(gè)克隆群具有映射關(guān)系，即該克隆群具有多個(gè)后繼。

合并模式當(dāng)前版本中的某一克隆群在前一版本中與多個(gè)克隆群具有映射關(guān)系，即該克隆群具有多個(gè)前驅(qū)。

復(fù)活模式某一克隆群在演化過程中先經(jīng)歷消失模式，而后又經(jīng)歷新生模式，即該克隆群“死而復(fù)活”，為復(fù)活模式。

增加模式當(dāng)前版本中的某一克隆群與前一版本中對(duì)應(yīng)克隆群相比，包含克隆代碼片段的數(shù)量有所增加。

去除模式當(dāng)前版本中的某一克隆群與前一版本中對(duì)應(yīng)的克隆群相比，包含克隆代碼片段的數(shù)量有所減少。

保持模式當(dāng)前版本中的某一克隆群與前一版本中對(duì)應(yīng)的克隆群相比，包含克隆片段的數(shù)量保持不變。

簡(jiǎn)單模式當(dāng)前版本中某一克隆群有唯一的前驅(qū)克隆群和唯一的后繼克隆群，而且前驅(qū)和后繼克隆群都存在于相鄰版本中，演化過程相對(duì)簡(jiǎn)單，沒有發(fā)生過新生、消失、合并、分支以及復(fù)活演化模式。

克隆群映射完成后，克隆群層面的演化模式識(shí)別即可進(jìn)行。由各類模式的定義可知，如果克隆群無前驅(qū)則發(fā)生了新生模式；如果克隆群無后繼則發(fā)生了消失模式；如果克隆群有多個(gè)前驅(qū)則發(fā)生了合并模式；如果克隆群有多個(gè)后繼則發(fā)生了分支模式；如果克隆群先發(fā)生了消失模式而后又出現(xiàn)新生模式則產(chǎn)生了復(fù)活模式；其余模式均為簡(jiǎn)單模式。

圖4呈現(xiàn)了某軟件系統(tǒng)6個(gè)連續(xù)版本中的部分克隆群的演化情況。其中：矩形代表軟件系統(tǒng)的版本，圓形代表克隆群，箭頭代表映射關(guān)系。由映射信息可知，B1和C3克隆群均發(fā)生了分支模式（例如B1分化為C1和C2），B2克隆群發(fā)生了消失模式，C4克隆群發(fā)生了復(fù)活模式，E1克隆群發(fā)生了合并模式，其余均為簡(jiǎn)單模式。

圖5呈現(xiàn)了某克隆群CG在4個(gè)版本中的演化過程；同時(shí)呈現(xiàn)了克隆群內(nèi)克隆片段數(shù)量的變化情況，其中圓形代表克隆群CG，正方形代表克隆代碼片段。顯然，CG在V1到V2的演化過程中增加了克隆片段，即發(fā)生了增加模式；在V2到V3的演化過程中去除了克隆片段，即發(fā)生了去除模式；在V3到V4的演化過程中，群內(nèi)片段數(shù)量保持不變，即屬于保持模式。

此外，本文還研究了3種克隆代碼片段內(nèi)容層面的演化模式，包括：無變化模式、一致變化模式和不一致變化模式。每種模式的基本定義如下：

無變化模式在相鄰版本間對(duì)應(yīng)的克隆群內(nèi)，所有參與了片段映射的克隆代碼片段的內(nèi)容都未發(fā)生改變。

一致變化模式在相鄰版本間對(duì)應(yīng)的克隆群內(nèi)，所有參與了片段映射的克隆片段的內(nèi)容作了一致改變。

不一致變化模式在相鄰版本間對(duì)應(yīng)的克隆群內(nèi)，所有參與了片段映射的部分或全部的克隆代碼片段內(nèi)容做了不一致改變。

克隆片段演化模式與克隆群演化模式不同，克隆片段模式僅僅針對(duì)克隆片段內(nèi)容層面在相鄰版本間的演化而言。本文將克隆片段演化模式分為3種，但這3種模式與Kim等[8]提出的相關(guān)演化模式存在差異。在本文中，這3種模并不涉及克隆群層面的演化，而在Kim等[8]的研究中，這3種模式既涉及到克隆群層面的演化同時(shí)又涉及到克隆代碼內(nèi)容層面的演化，視角混淆。本文將這3種模式重新定義，視角明確，有較好的層次感，更加清晰，易于理解。

圖6呈現(xiàn)了某克隆群CG內(nèi)的克隆代碼片段在4個(gè)相鄰版本間的演化過程，其中圓形代表克隆群，正方形代表克隆代碼片段，不同填充顏色及邊框代表克隆代碼片段內(nèi)容發(fā)生了不同的改變。在V1到V2的演化過程中，群內(nèi)所有克隆代碼片段發(fā)生了內(nèi)容上的一致變化；在V2到V3的演化過程中，克隆代碼片段發(fā)生了內(nèi)容上的不一致變化；在V3到V4的演化過程中，也發(fā)生了內(nèi)容上不一致變化，而且還增加了克隆代碼片段。由此可見，不同視角的克隆演化模式可能會(huì)同時(shí)發(fā)生，所以區(qū)分視角的克隆演化模式分析是十分必要的，這將為克隆演化的后期研究提供更加清晰和明確的思路。

針對(duì)上述3種克隆片段演化模式，本文先識(shí)別無變化模式，即對(duì)應(yīng)克隆群內(nèi)的所有參與映射的克隆代碼片段內(nèi)容不變。這種模式識(shí)別較為簡(jiǎn)單，可以將代碼元素的變化情況作為參考，求出對(duì)應(yīng)克隆片段源代碼的差異，從而確定是否改變。如果在對(duì)應(yīng)克隆群內(nèi)所有參與映射的克隆代碼內(nèi)容不變，則為無變化模式。識(shí)別無變化模式完成后，可識(shí)別一致變化和不一致變化模式。如果參與映射的部分或全部克隆代碼內(nèi)容發(fā)生了改變，先求出所有對(duì)應(yīng)克隆代碼片段的差異，然后計(jì)算這些差異的相似情況。如果所有差異相同，則為一致變化模式，否則為不一致變化模式。本文將借助Diff工具對(duì)克隆代碼片段內(nèi)容層面的演化情況進(jìn)行分析，從而給出克隆代碼片段的演化模式。

2.5克隆演化特征

克隆代碼映射關(guān)系中包含了大量的克隆代碼演化信息?；谝褬?gòu)建的克隆代碼映射關(guān)系，本文從克隆演化模式、克隆生命周期以及克隆代碼數(shù)量增長率等方面選取克隆演化特征進(jìn)行分析?？寺⊙莼Ｊ教峁┝素S富的演化信息，便于研究和理解克隆演化現(xiàn)象?？寺∩芷谀軌蚍从晨寺∪涸谘莼^程中所經(jīng)歷的版本數(shù)量。此外，克隆演化特征還可用于克隆代碼相關(guān)問題的預(yù)測(cè)研究，例如可用代碼的有害性及穩(wěn)定性預(yù)測(cè)等問題。

2.5.1演化模式的數(shù)量特征

通過對(duì)各類克隆演化模式進(jìn)行統(tǒng)計(jì)，可以發(fā)現(xiàn)克隆群在軟件的演化過程中主要進(jìn)行了哪種改變方式。統(tǒng)計(jì)某一克隆群經(jīng)歷各種演化模式的數(shù)量可以宏觀地了解克隆群的演化情況。演化模式的數(shù)量特征可以從側(cè)面反映一款軟件中大部分克隆代碼是否穩(wěn)定，如果簡(jiǎn)單模式與無變化模式數(shù)量較多，則說明大部分克隆代碼的演化相對(duì)穩(wěn)定。而其他模式的數(shù)量較多，則可以反映某些克隆群在演化過程中比較多變，穩(wěn)定性較差。在研究克隆代碼的穩(wěn)定性或有害性時(shí)，克隆代碼所經(jīng)歷的某些演化模式可能作為判斷其性質(zhì)的決定性因素。例如，如果某個(gè)克隆群在演化過程中頻繁發(fā)生一致或者不一致變化模式，則該克隆群必然占據(jù)了過多的維護(hù)成本，可以認(rèn)為其有害性較強(qiáng)，建議優(yōu)先去除或者重構(gòu)，因此，克隆演化模式的數(shù)量特征可以為克隆代碼的其他相關(guān)研究工作提供良好的數(shù)據(jù)支持。

2.5.2克隆代碼的生命周期

對(duì)于一個(gè)克隆群而言，其所經(jīng)歷的版本數(shù)量就是其生命周期?？寺∪旱纳芷诳梢悦鞔_反映克隆群在演化過程中存在時(shí)間的長短。對(duì)于生命周期較長而且演化相對(duì)穩(wěn)定的克隆群，可以建議開發(fā)或維護(hù)人員進(jìn)行簡(jiǎn)單的跟蹤。對(duì)于生命周期比較短暫的克隆，通過分析其引入因素及去除因素，可以總結(jié)一些有意義的開發(fā)及維護(hù)策略作為經(jīng)驗(yàn)，從而為后期的開發(fā)及維護(hù)提供參考，避免再次引入該類克隆代碼，從而降低開發(fā)及維護(hù)的成本。

2.5.3克隆代碼數(shù)量結(jié)構(gòu)特征

在軟件的演化過程中，克隆代碼片段可能被增加或去除，因此，克隆群以及克隆代碼片段數(shù)量的增長比可以直接反映克隆代碼整體數(shù)量結(jié)構(gòu)的變化情況?？寺∪号c克隆代碼片段的數(shù)量比則可以直接反映克隆代碼在演化過程中整體的繁殖量?？寺〈a的數(shù)量結(jié)構(gòu)特征可以在宏觀上反映軟件系統(tǒng)中克隆代碼所占比重的變化情況。在實(shí)際的軟件開發(fā)或維護(hù)環(huán)境中，如果發(fā)現(xiàn)克隆代碼的整體繁殖能力越來越強(qiáng)，則可以考慮重構(gòu)或去除某些克隆代碼，從而為后續(xù)的開發(fā)及維護(hù)工作減輕壓力。

2.6克隆譜系構(gòu)建

克隆譜系是指克隆代碼在軟件多個(gè)版本演化過程中變化情況的記錄信息。將克隆譜系作為克隆代碼分析的基本數(shù)據(jù)，可以進(jìn)行更多克隆代碼相關(guān)問題的研究。當(dāng)相鄰版本間的克隆群映射、對(duì)應(yīng)克隆群之間的克隆代碼片段映射、克隆演化模式識(shí)別及克隆演化特征分析完成后，按照版本的時(shí)序，將所有演化信息合并得到克隆譜系。從宏觀結(jié)構(gòu)層面來看，克隆譜系主要是根據(jù)克隆群映射關(guān)系連接而成的拓?fù)浣Y(jié)構(gòu)。克隆譜系反映了克隆代碼在軟件的演化過程中是如何產(chǎn)生、繁殖和去除的?？寺∽V系中的每個(gè)克隆群都記錄了對(duì)應(yīng)的演化模式信息，其內(nèi)部包含的克隆代碼片段也各自記錄了微觀層面的片段映射關(guān)系以及片段演化模式。

本文克隆譜系結(jié)構(gòu)與前期相關(guān)研究中的克隆譜系結(jié)構(gòu)明顯不同。在前期相關(guān)研究中，其克隆譜系結(jié)構(gòu)主要為克隆群粒度層面的樹形結(jié)構(gòu)，而本文構(gòu)建的克隆譜系不再為樹形結(jié)構(gòu)，而是拓?fù)浣Y(jié)構(gòu)。在前期相關(guān)研究中，克隆演化模式的概念幾乎全部來自于Kim等的研究[8]，僅限于大約6種模式，而且各個(gè)模式之間不分視角，結(jié)構(gòu)不清晰。此外，前期相關(guān)工作也并為分開視角地考慮到克隆群的合并模式與復(fù)活模式，所以其克隆譜系的構(gòu)建工作中還關(guān)注了克隆直系與克隆家系的概念?？寺≈毕得枋隽四骋豢寺∪旱膯沃а莼^程，克隆家系描述了起源于同一個(gè)克隆群的所有克隆直系的演化過程。雖然本文研究方法拓展了傳統(tǒng)意義上的克隆譜系結(jié)構(gòu)，但是克隆直系與克隆家系的子結(jié)構(gòu)仍然可以在本文方法構(gòu)建的克隆譜系中找到，因?yàn)椴⒎撬锌寺∪憾冀?jīng)歷合并或者復(fù)活模式。除了克隆直系與克隆家系以外，本文將引入克隆族系的概念，克隆族系描述了起源于或合并于不同克隆群的所有直系克隆及家系克隆。由于合并及復(fù)活演化模式的存在，某一些克隆群的起源并非前續(xù)版本中的單一克隆群，而可能是經(jīng)由多個(gè)克隆群合并之后演化而來，克隆族系將更加有助于分析克隆群的合并或重構(gòu)問題。

圖7展示了克隆譜系的基本結(jié)構(gòu)，其中圓形代表克隆群，正方形代表克隆代碼片段，箭頭代表映射關(guān)系，不同的灰度及字母分別代表了克隆代碼的模式及編號(hào)。

3實(shí)驗(yàn)與分析

3.1數(shù)據(jù)來源

本文分別針對(duì)4款開源軟件的多個(gè)發(fā)布版本進(jìn)行了克隆譜系的構(gòu)建研究。使用了CloneDetective[27]和FClones[28]克隆代碼檢測(cè)工具以函數(shù)粒度進(jìn)行克隆檢測(cè)。4款開源軟件的基本信息如表1所示。本文所選取的開源軟件常被軟件工程領(lǐng)域研究者作為基礎(chǔ)的實(shí)驗(yàn)數(shù)據(jù)使用，具有一定代表性。例如Lin等[29]在研究克隆代碼模式時(shí)使用了jedit以及jhotdraw等開源軟件作為研究對(duì)象。針對(duì)這些開源軟件的實(shí)驗(yàn)數(shù)據(jù)能為本文的后續(xù)對(duì)比研究作一定的鋪墊。選取這些開源軟件還考慮了不同程序設(shè)計(jì)語言及不同功能的軟件，而且這些開源軟件一直被良好地開發(fā)與維護(hù)，擁有較多的發(fā)布版本，含有豐富的克隆代碼。能為克隆演化研究提供基礎(chǔ)性數(shù)據(jù)。

3.2實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)中，在相鄰版本間克隆群映射時(shí)，主題相似度閾值設(shè)定參照了前期相關(guān)研究[25]，將閾值暫設(shè)為0.8，但是該閾值并非固定不變，本文將在后續(xù)研究中對(duì)此值的選取問題進(jìn)行更為細(xì)致深入的研究。通過對(duì)4款軟件系統(tǒng)構(gòu)建克隆譜系，得出了每款軟件中的克隆群在演化過程中表現(xiàn)在生存層面的演化模式數(shù)量，各類演化模式數(shù)量統(tǒng)計(jì)如表2所示。

由表2可知，本文新提出的克隆演化模式在克隆代碼演化過程中確實(shí)存在，而且占有一定數(shù)量。例如，在jhotdraw的16個(gè)發(fā)布版本的演化過程中，出現(xiàn)了3次合并模式；在ffmpeg的29個(gè)發(fā)布版本中，出現(xiàn)了8次合并模式以及20次復(fù)活模式。復(fù)活模式將為克隆代碼與Bugs的研究提供更多參考信息，因此本文所提出的新的演化模式具有更深層次的研究意義。

此外，實(shí)驗(yàn)還統(tǒng)計(jì)了克隆群在容量層面的演化模式，包括克隆群內(nèi)片段數(shù)量的增加、去除以及保持3種模式，如表3所示。由表3可知，克隆群在容量層面發(fā)生克隆代碼片段增加及去除模式也出現(xiàn)了多次，這說明了克隆代碼在演化過程中是非?？赡茉俅伪粡?fù)制重用或刪除。在jhotdraw及ffmpeg中，克隆群容量發(fā)生多次增加及去除模式，而在jedit及bluefish中該類演化模式數(shù)量則相對(duì)較少。由此可知，各類演化模式在不同功能、不同程序設(shè)計(jì)語言、不同開發(fā)團(tuán)隊(duì)、不同規(guī)模的軟件系統(tǒng)中均有可能發(fā)生。

除了分析粗粒度的克隆演化模式以外，本文還針對(duì)細(xì)粒度的克隆代碼演化情況進(jìn)行了分析。從克隆代碼片段的內(nèi)容層面，分析了同一克隆群內(nèi)的克隆代碼片段在版本之間的變化情況。包括無變化模式、一致變化模式和不一致變化模式。此層面的各類演化模式數(shù)量如表4所示。由表4可知，絕大多數(shù)（平均約90%）克隆克隆代碼在演化過程中基本不變；平均約10%的克隆代碼發(fā)生了改變，而發(fā)生一致改變的克隆代碼較多，平均約為6.5%，發(fā)生不一致改變的克隆群最少，平均約為4.4%。這也說明了絕大多數(shù)克隆代碼在演化過程中不會(huì)被修改，而被修改的克隆代碼超過一半被一致性地修改了，僅有一少部分被不一致地修改。本文將在后續(xù)研究中繼續(xù)關(guān)注引起克隆代碼不一致性修改的原因及其為軟件開發(fā)及軟件維護(hù)帶來的利弊。

本文除了關(guān)注克隆代碼演化模式之外，還統(tǒng)計(jì)了克隆群的生命周期，如表5所示。由表5可知，大部分克隆代碼在軟件演化過程中并未生存較長時(shí)間，而僅有一小部分克隆代碼在演化過程中一直穩(wěn)定地生存下來。生存時(shí)間不超過軟件整體生命周期40%的克隆群數(shù)大約為總數(shù)的67%。生存時(shí)間超過軟件整體生命周期80%的克隆群數(shù)大約為總數(shù)的6%。剩余部分克隆群的生命周期約占軟件整體生命周期的27%。

克隆代碼在演化過程中會(huì)伴隨著克隆群的消失與新生模式，但克隆群及克隆代碼片段的數(shù)量會(huì)隨著軟件演化的推進(jìn)而增多，表6給出了克隆群數(shù)量及克隆代碼數(shù)量在軟件版本演化過程中的數(shù)量增長比率。

由表6可知，這4款開源軟件中的克隆代碼幾乎全部以增加克隆代碼數(shù)量的方式演化?？寺∪簲?shù)量平均增長率約為24.1%，克隆代碼片段數(shù)的平均增長率約為17.4%。也有個(gè)別相鄰版本間存在著克隆群及克隆片段減少的情況，但這種情況比較少見。出現(xiàn)克隆代碼數(shù)目減少的原因可能包括克隆檢測(cè)工具閾值的固定性、克隆代碼修改量較大、克隆代碼被重構(gòu)等。

克隆代碼的數(shù)量結(jié)構(gòu)說明克隆代碼在軟件開發(fā)、維護(hù)、升級(jí)及重構(gòu)等活動(dòng)中都扮演著不可或缺的角色，占據(jù)了軟件整體代碼的一定比例?？寺〈a的跟蹤、維護(hù)及管理將對(duì)軟件開發(fā)活動(dòng)和軟件質(zhì)量產(chǎn)生積極性的影響。

4結(jié)語

本文基于軟件多版本演化，根據(jù)克隆代碼主題信息構(gòu)建版本間克隆代碼的映射關(guān)系，為演化過程中的克隆代碼添加演化模式，分析演化特征并構(gòu)建克隆譜系。

本文傳承了利用克隆代碼主題信息進(jìn)行克隆群映射的工作，并繼續(xù)開展了克隆演化模式識(shí)別、演化特征分析以及克隆譜系構(gòu)建的工作。發(fā)現(xiàn)了大部分克隆代碼（約90%）在演化過程中表現(xiàn)得相對(duì)穩(wěn)定，但仍然有部分克隆代碼在演化過程中比較多變，穩(wěn)定性較差。另外，本文還通過實(shí)驗(yàn)驗(yàn)證了新提出的克隆演化模式在克隆代碼演化過程中確有發(fā)生。還發(fā)現(xiàn)了大部分克隆代碼的生命周期并未超過軟件演化整體周期的50%。本文研究結(jié)論將為克隆代碼演化分析、克隆代碼的維護(hù)管理及重構(gòu)任務(wù)提供更多參考信息。

本文的研究內(nèi)容與實(shí)驗(yàn)依然存在一些不足之處，包括：Type3克隆代碼內(nèi)容層面的演化模式還需要進(jìn)一步深入研究；一致變化模式及不一致變化模式的判斷需要更加詳細(xì)合理的標(biāo)準(zhǔn)；克隆群映射準(zhǔn)確性與全面性的評(píng)價(jià)需要研究；克隆譜系結(jié)果未進(jìn)行良好的可視化等。

本文將在后續(xù)研究中陸續(xù)改進(jìn)、完善不足之處，包括：選取更加適合分析克隆代碼的主題模型；為克隆群和克隆代碼片段映射工作構(gòu)建測(cè)試集和自動(dòng)化的評(píng)價(jià)框架；將克隆譜系的結(jié)果進(jìn)行良好的可視化；研究各種演化模式與Bugs的關(guān)系；為克隆代碼構(gòu)建本體模型以及檢索系統(tǒng)；為克隆代碼的維護(hù)與管理提供更多幫助。此外，將在下一步研究工作中，進(jìn)一步考慮將所提方法與已有的一些經(jīng)典的研究工作進(jìn)行深入的對(duì)比分析；同時(shí)，分析不同方法中某些階段不同算法的選擇或不同參數(shù)的取值對(duì)最終結(jié)果的影響。

參考文獻(xiàn)：

[1]

ROY C K， ZIBRAN M F， KOSCHKE R. The vision of software clone management： past， present， and future （Keynote paper） [C]// Proceedings of the 2014 IEEE Conference on Software Maintenance， Reengineering and Reverse Engineering. Piscataway， NJ： IEEE， 2014： 18-33.

[2]

BELLON S， KOSCHKE R， ANTONIOL G， et al. Comparison and evaluation of clone detection tools [J]. IEEE Transactions on Software Engineering， 2007， 33（9）： 577-591.

[3]

PATE J R， TAIRAS R， KRAFT N A. Clone evolution： a systematic review [J]. Journal of Software： Evolution and Process， 2013， 25（3）： 261-283.

[4]

BARBOUR L， KHOMH F， ZOU Y. An empirical study of faults in late propagation clone genealogies [J]. Journal of Software： Evolution and Process， 2013， 25（11）： 1139-1165.

[5]

LAGUE B， PROULX D， MAYRAND J， et al. Assessing the benefits of incorporating function clone detection in a development process [C]// Proceedings of the 1997 IEEE International Conference on Software Maintenance. Piscataway， NJ： IEEE， 1997： 314-321.

[6]

ANTONIOL G， VILLANO U， MERLO E， et al. Analyzing cloning evolution in the Linux kernel [J]. Information and Software Technology， 2002， 44（13）： 755-765.

[7]

GDE N. Clone Evolution [M]. Berlin： Springer， 2011： 3-4.

[8]

KIM M， SAZAWAL V， NOTKIN D， et al. An empirical study of code clone genealogies [J]. ACM SIGSOFT Software Engineering Notes， 2005， 30（5）： 187-196.

[9]

KIM M， NOTKIN D. Using a clone genealogy extractor for understanding and supporting evolution of code clones [J]. ACM SIGSOFT Software Engineering Notes， 2005， 30（4）： 1-5.

[10]

ZIBRAN M F， SAHA R K， ROY C K， et al. Evaluating the conventional wisdom in clone removal： a genealogybased empirical study [C]// Proceedings of the 28th Annual ACM Symposium on Applied Computing. New York： ACM， 2013： 1123-1130.

[11]

SAHA R K， ASADUZZAMAN M， ZIBRAN M F， et al. Evaluating code clone genealogies at release level： an empirical study [C]// Proceedings of the 10th IEEE Working Conference on Source Code Analysis and Manipulation. Piscataway， NJ： IEEE， 2010： 87-96.

[12]

GDE N， KOSCHKE R. Studying clone evolution using incremental clone detection [J]. Journal of Software： Evolution and Process， 2013， 25（2）： 165-192.

[13]

BAKOTA T. Tracking the Evolution of Code Clones [M]. Berlin： Springer， 2011： 86-98.

[14]

YING T， LI P Z， CHUN H W， et al. Extract function clone genealogies across multiple versions [J]. International Journal of Security and Its Applications， 2015， 9（6）： 167-182.

[15]

SAHA R K， ROY C K， SCHNEIDER K. gCad： a nearmiss clone genealogy extractor to support clone evolution analysis [C]// Proceedings of the 2013 IEEE International Conference on Software Maintenance. Piscataway， NJ： IEEE， 2013： 488-491.

[16]

MENG C， XIAO H， TIAN T， et al. A new clone group mapping algorithm for extracting clone genealogy on multiversion software [C]// Proceedings of the 2013 Third International Conference on Instrumentation， Measurement， Computer， Communication and Control. Piscataway， NJ： IEEE， 2013： 848-853.

[17]

BAKOTA T， FERENC R， GYIMOTHY T. Clone smells in software evolution [C]// Proceedings of the 23rd International Conference on Software Maintenance. Piscataway， NJ： IEEE， 2007： 24-33.

[18]

AVERSANO L， CERULO L， PENTA M D. How clones are maintained： an empirical study [C]// Proceedings of the 11st European Conference on Software Maintenance and Reengineering. Piscataway， NJ： IEEE， 2007： 81-90.

[19]

THUMMALAPENTA S， CERULO L， AVERSANO L， et al. An empirical study on the maintenance of source code clones [J]. Empirical Software Engineering， 2009， 15（1）： 1-34.

[20]

KUHN A， DUCASSE S， GíRBA T. Semantic clustering： identifying topics in source code [J]. Information and Software Technology， 2007， 49（3）： 230-243.

[21]

THOMAS S W， ADAMS B， HASSAN A E， et al. Validating the use of topic models for software evolution [C]// Proceedings of the 2010 IEEE Conference on Source Code Analysis and Manipulation. Piscataway， NJ： IEEE， 2010： 55-64.

[22]

THOMAS S W， ADAMS B， HASSAN A E， et al. Studying software evolution using topic models [J]. Science of Computer Programming， 2014， 80： 457-479.（無期）

[23]

ASUNCION H U， ASUNCION A U， TAYLOR R N. Software traceability with topic modeling [C]// Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering. New York： ACM， 2010： 95-104.

[24]

金靖，李萌，華哲邦，等.一種基于LDA和靜態(tài)分析的代碼功能識(shí)別方法[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（15）：27-31.（JIN J， LI M， HUA Z B， et al. Code function recognition approach based on LDA and static analysis [J]. Computer Engineering and Applications， 2013， 49（15）： 27-31.）

[25]

張瑞霞，張麗萍，王春暉，等.基于主題建模技術(shù)的克隆群映射方法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2015，36（6）：1524-1529.（ZHANG R X， ZHANG L P， WANG C H， et al. Clone group mapping method based on topic modeling [J]. Computer Engineering and Design， 2015， 36（6）： 1524-1529.）

[26]

PHAN X H， NGUYEN L M， HORIGUCHI S. Learning to classify short and sparse text & Web with hidden topics from largescale data collections [C]// Proceedings of the 17th International Conference on World Wide Web. New York： ACM， 2008： 91-100.

[27]

JUERGENS E， DEISSENBOECK F， HUMMEL B. Clonedetectivea workbench for clone detection research [C]// Proceedings of the 31st International Conference on Software Engineering. Piscataway， NJ： IEEE， 2009： 603-606.

[28]

張久杰，王春輝，張麗萍，等.基于Token編輯距離檢測(cè)克隆代碼[J].計(jì)算機(jī)應(yīng)用，2015，35（12）：3536-3543.（ZHANG J J， WANG C H， ZHANG L P， et al. Clone code detection based on Levenshtein distance of token [J]. Journal of Computer Applications， 2015， 35（12）： 3536-3543.）

[29]

LIN Y， XING Z， PENG X， et al. Clonepedia： summarizing code clones by common syntactic context for software maintenance [C]// Proceedings of the 2014 IEEE International Conference on Software Maintenance and Evolution. Piscataway， NJ： IEEE， 2014： 341-350.