杜 欣 趙 康 倪友聰 沈志鵬

一種基于邏輯的Java模塊依賴圖構建工具

杜 欣 趙 康*倪友聰 沈志鵬

(福建師范大學軟件學院 福建 福州 350108)

目前Java模塊依賴圖MDG(Module Dependency Graph)的構建工具還比較稀缺，從一定程度上限制了基于MDG圖的軟件模塊聚類算法的應用。針對這一問題，提出一種基于邏輯的Java模塊依賴圖構建工具TL4JMDG(the tool logic-based for Java MDG)。在開源框架JTransformer和tuProlog的支持下，TL4JMDG工具以邏輯方式實現(xiàn)了Java模塊關系的抽取和MDG圖的生成。闡述TL4JMDG工具的設計與實現(xiàn)，并給出TL4JMDG工具和基于Chava工具構建MDG的耗時比較。TL4JMDG工具具有較好的可配置性、可擴展性和性能，使得目前已有的基于MDG圖的聚類算法能更好地應用于Java軟件模塊聚類。

軟件模塊聚類 模塊關系 模塊依賴圖 JTransformer

0 引 言

軟件模塊化可以提高系統(tǒng)的可理解性、降低系統(tǒng)的維護費用。軟件模塊聚類是軟件模塊化的一種重要手段。目前已涌現(xiàn)出一批基于模塊依賴圖MDG的軟件模塊聚類算法。Mitchell[1, 2]等人使用了爬山算法、遺傳算法等啟發(fā)式算法進行軟件模塊聚類研究。為了進一步增大搜索空間，提高解質(zhì)量，一些多目標軟件模塊聚類算法[3-9]被紛紛提出。Praditwong[7]等人首次將軟件模塊聚類作為一個多目標優(yōu)化問題進行研究，提出了兩種多目標軟件模塊聚類算法ECA和MCA。De Barros[3]提出一種基于多目標遺傳算法的軟件模塊聚類方法。Gupta[5]等人提出一種軟件模塊多目標聚類算法MHypGA。上述這些軟件聚類算法都直接或間接地利用MDG圖來計算各個目標的值。上述這些算法大多集中在對C或C++程序模塊進行聚類。它們常常借助已有的Cia[10]和Acacia[11]等工具構建相應的MDG圖，而針對Java程序模塊的MDG圖構建工具還比較稀缺，這從一定程度上限制了基于MDG圖的軟件模塊聚類算法的應用。雖可基于Doxygen[13]和Chava[12]等Java源代碼分析工具開發(fā)Java程序模塊的MDG圖構建工具，但仍需要解析Doxygen輸出的各種不同格式的結(jié)果文件或處理Chava結(jié)果數(shù)據(jù)庫中各種不同結(jié)構的表。這不僅面臨一定的復雜性，而且影響到Java程序模塊的MDG圖構建工具的可配置性、可擴展性和性能。

針對上述問題, 本文提出一種基于邏輯的Java模塊依賴圖構建工具TL4JMDG。TL4JMDG工具借助開源JTransformer框架將Java程序轉(zhuǎn)換為SWIProlog語言的邏輯事實庫，再將該事實庫轉(zhuǎn)換為tuProlog語言的事實庫，進一步在tuProlog多范型編程框架下以可擴展和可配置的方式實現(xiàn)Java模塊關系的抽取和MDG圖的生成。

1 背景知識

下面簡單介紹本文涉及的MDG圖、JTransformer和tuProlog框架等背景知識。

1.1 MDG圖

MDG圖是一種表示程序中模塊之間依賴關系的無向圖。它由頂點和帶權值的邊構成。其中：頂點表示模塊，邊表示模塊之間的關系，每種模塊關系可以賦予不同權重，邊上的權值是模塊間存在多種關系的權值和。面向?qū)ο缶幊陶Z言多以類和接口作為模塊，模塊之間關系往往定義為類間的繼承、關聯(lián)、方法調(diào)用以及接口與實現(xiàn)等關系。模塊之間關系存在著強弱之分，在軟件模塊聚類研究中常常需要對不同關系賦予不同權重，體現(xiàn)它們對聚類結(jié)果的影響[14]。

本文TL4JMDG工具是一種面向Java程序的MDG構建工具。下面舉一小例子解釋Java程序與MDG圖之間的映射關系。下面的程序代碼和圖1分別是Java程序片斷及其所對應的MDG圖。程序聲明了包demo，并定義了Person、Student和Teacher三個類及其之間的關系。程序中第9行和10行指示了Student類和Teacher類分別與Person類之間存在繼承關系；第11行和第13行定義了Teacher類與Student類之間存在關聯(lián)和方法調(diào)用關系。例中假定繼承、關聯(lián)和方法調(diào)用三種模塊關系的權重被分別設為4、2和1，則程序片斷對應的MDG如圖1所示。圖1表示的MDG圖包括名為demo.Person、demo.Student和demo.Teacher三個結(jié)點和三條邊。

1 package demo;

2 public class Person {

3 String name;

4 public String getName() {

5 return name;

6 }

7 ……

8 }

9 public class Student extends Person { …}

10 public class Teacher extends Person {

11 Student student;

12 public String askStudentName() {

13 String name = student.getName();

14 return name;

15 }

16 }

圖1 程序?qū)腗DG圖

本文TL4JMDG工具借助JTranformer框架來構建Java程序的MDG圖。

1.2 JTransformer框架

JTransformer[14,15]是一種基于邏輯的Java程序分析和重構框架。它的核心功能是將Java程序變換成SWIProlog語言[14]的邏輯事實庫。JTransformer框架中定義了一組用于表示Java語言語法樹結(jié)點及其之間關系的SWIProlog謂詞。通過這些謂詞可將Java程序變換成等價的SWIProlog邏輯事實庫。

在上例的基礎上，給出這種等價變換的簡單說明。圖2示意了程序片斷對應的一棵語法樹。圖2中的橢圓表示樹的結(jié)點，旁邊的數(shù)字表示結(jié)點的ID號；矩形框表示結(jié)點的屬性值；實有向弧邊表示結(jié)點之間的父子關系；無向邊表示結(jié)點與屬性的關系；虛有向弧表示結(jié)點間的引用關系，弧上的標識符定義了引用關系的類型名。下面以圖2中旁邊加實心三角形的結(jié)點為例進行說明。該結(jié)點的ID號、父結(jié)點ID號和名稱分別為28969、28978和Student。該結(jié)點引用ID號為28976的結(jié)點，且引用關系的類型為extendsT。

圖2 Java程序的語法樹

Java語法樹結(jié)點以及結(jié)點之間的引用關系可用JTransformer定義的一階謂詞進行表示。根結(jié)點packageT的謂詞表示中第一個變元表示結(jié)點ID號，第二個變元表示包名。除根結(jié)點外，其余結(jié)點謂詞的第一個變元表示結(jié)點的ID號，第二個變元表示父節(jié)點的ID號，其他項由結(jié)點的類型確定。這些項用于表示結(jié)點的屬性、結(jié)點與其他結(jié)點之間的引用關系等。引用關系謂詞的第一和第二個變元分別表示引用關系的ID號和被引用結(jié)點的ID號。在結(jié)點謂詞和引用關系謂詞定義中的變元名統(tǒng)一用‘_’作為前綴，并約定名為‘_’的變元是匿名變元。式(1)和式(2)分別給出classT類型結(jié)點和extendsT類型引用關系的謂詞定義。對一個具體的Java程序，其語法樹中的每個結(jié)點及其之間的引用關系都可用不含變元的謂詞公式表示，形成一條邏輯事實。例如圖2中旁邊加實心三角形的結(jié)點可表示成式(3)對應的一條邏輯事實，該結(jié)點對應的一個引用關系可用式(4)定義的一條邏輯事實進行表示。因而，一個Java程序可等價表示成一個邏輯事實庫。表1示意了圖2對應的邏輯事實庫。

表1 程序?qū)倪壿嬍聦崕?/p>

classT(_clsid,_pkgid,_name,[_ref1,…,_refn])

(1)

extendT(_id,_clsId)

(2)

classT(28969,28978,′Student′,[28980])

(3)

extendT(28969,28985)

(4)

借助JTransformer雖可將Java程序轉(zhuǎn)換為SWIProlog邏輯事實庫，但已有的SWIProlog編程框架不能很好支持與Java語言的多范型編程。因而，TL4JMDG工具使用tuProlog框架作為編程環(huán)境。將SWIProlog邏輯事實庫變換為tuProlog的邏輯事實庫。下面簡單介紹tuProlog框架。

1.3 tuProlog框架

tuProlog是一種具有多范型編程和并行多線程推理能力的Prolog框架。本文TL4JMDG工具借助tuProlog框架中的Theory、Prolog和SolveInfo三類，可在Java環(huán)境運用多線程訪問Prolog資源和功能。Theory類用于實例化Java程序事實庫，而Prolog類提供解析執(zhí)行邏輯程序和命令的功能，并將返回結(jié)果封裝在SolveInfo類對象中，利用SolveInfo類提供的方法可遍歷解析結(jié)果。

簡要介紹TL4JMDG工具開發(fā)的背景知識后，下面給出它的具體設計與實現(xiàn)。

2 TL4JMDG工具總體設計

圖3示意了TL4JMDG工具的工作流程。其主要包括配置文件生成、tuProlog邏輯事實庫生成和MDG圖生成三個階段。在第一階段中，用戶指定Java程序文件和輸出MDG文件的位置，以及需要提取的模塊關系和權值等信息，并通過UI模塊將這些信息寫入到配置文件中。在第二階段中，借助JTransformer框架先將Java程序轉(zhuǎn)化為SWIProlog邏輯事實庫，再通過SWI2tu轉(zhuǎn)換器將該邏輯事實庫轉(zhuǎn)換為tuProlog邏輯事實庫。SWI2tu轉(zhuǎn)換器主要針對SWIProlog和tuProlog邏輯事實庫在字符編碼和指令格式上的差異，進行相應的字符編碼轉(zhuǎn)換和指令格式轉(zhuǎn)換。在第三階段中，MDG圖生成器MDGCreator先讀入配置文件，決定要抽取的模塊關系，再基于tuProlog邏輯事實庫抽取對應的模塊關系，最后根據(jù)配置文件中各種模塊關系的權重，生成Java程序?qū)腗DG圖。

圖3 MDG圖構建工作流程圖

在TL4JMDG工具中，MDG圖生成器MDGCreator是最為關鍵和核心的模塊。下面詳細闡述它的設計與實現(xiàn)。

3 MDGCreator生成器的設計與實現(xiàn)

MDGCreator生成器主要由MDGController控制器和一組模塊關系提取器MDGExtractor構成。圖4示意了它的工作流程。其主要包含啟動MDGExtractor提取器，生成中間MDG圖和生成最終MDG圖三個階段。在第一階段中，MDGController控制器讀取配置文件獲取用戶需要提取的模塊關系，并行啟動相應的MDGExtractor提取器。在第二階段中，每種MDGExtractor提取器在邏輯事實庫上查詢一種特定的模塊關系，并根據(jù)查詢結(jié)果構建出一個中間MDG圖；在第三階段中，MDGController控制器根據(jù)關系的權重值，通過合并各個中間MDG圖，構建出最終MDG圖。下面給出MDGExtracor提取器和MDGController控制器的設計與實現(xiàn)。

圖4 MDGCreator工作流程示意圖

3.1 MDGExtracor提取器設計與實現(xiàn)

圖5給出了MDGExtracor提取器的設計類圖。其包括extractorPkg、mdgPkg和prologPkg三個包。

圖5 MDGExtracor提取器設計類圖

(1) extractorPkg包包含了IExtractor接口和一組具體的提取器類。IExtractor接口中的方法generateMDG定義了各種提取器類向外部提供的公共行為，即抽取一種特定的模塊關系，生成中間MDG。目前TL4JMDG工具實現(xiàn)了繼承、實現(xiàn)、關聯(lián)和方法調(diào)用四種模塊關系的提取器，分別由ExtractorOfExt、ExtractorOfImp、ExtractorOfAsso和ExtractorOfCal四個類具體實現(xiàn)。用戶可擴展定義自己的提取器類，以抽取其他模塊關系。

(2) mdgPkg包包含MDG、Edge和Node三個類，它們分別用于定義MDG圖及其邊和結(jié)點。Node類中的id和name屬性分別表示結(jié)點id和名稱。Edge類中head、tail和weight三個屬性分別表示邊關聯(lián)的兩個結(jié)點以及權值。為了今后擴展成有向圖，head、tail可定義為弧尾和弧點結(jié)點。MDG類中nodes和edges分別用于表示MDG圖的結(jié)點集和邊集。

(3) prologPkg包包含了tuprolog支持庫中Theory、Prolog和SolveInfo三個類。Theory類的構造函數(shù)以Java程序邏輯事實庫文件作為輸入流，生成tuProlog引擎可加載的理論。Prolog類中setTheory、solve和solveNext三個方法分別表示加載理論、解析執(zhí)行邏輯程序返回解和獲取下一個解。solve和solveNext方法都是返回SolveInfo對象，可請求SolveInfo類方法isSuccess判斷Prolog對象執(zhí)行結(jié)果是否成功，如成功可繼續(xù)獲取下一個解。

限于篇幅下面僅以繼承關系提取器ExtractorOfExt為例說明提取器類的實現(xiàn)方案。圖6的時序圖描述了當MDGController控制器向ExtractorOfExt提取器發(fā)出生成繼承關系MDG圖的請求后，ExtractorOfExt提取器的工作流程。具體而言：ExtractorOfExt提取器根據(jù)Java程序邏輯事實庫的位置實例化Theory對象，然后創(chuàng)建Prolog對象，再請求該Prolog對象加載實例化后的Theory對象；接著ExtractorOfExt提取器發(fā)送查詢模塊繼承關系的邏輯程序文本，并請求Prolog對象解析執(zhí)行，Prolog對象執(zhí)行后返回SolveInfo結(jié)果對象； ExtractorOfExt提取器根據(jù)返回的SolveInfo對象判斷執(zhí)行是否成功，如成功則多次請求Prolog對象獲取每一個解；最后ExtractorOfExt提取器根據(jù)所獲得的解生成繼承關系MDG圖。

圖6 MDGExtractor提取器的工作流程

表2給出了查詢繼承關系的邏輯程序文本。在表2中，第1行到第3行用于查詢一個類的合格名。第4行表示查詢該類引用的父類。第5行到第7行表示獲取父類的ID(由_clsID指示)后，再查詢該父類的合格類名。表2的程序文本由Prolog引擎在Java程序邏輯事實上解析執(zhí)行后，可獲得Java程序中所有類的繼承關系，并能確定每個繼承關系中子類和父類的合格類名。

表2 繼承關系提取器查詢謂詞

3.2 MDGController控制器設計與實現(xiàn)

圖7給出了MDGController控制器的設計類圖。mdgCtlPkg包給出了控制器的設計，其主要包含MDGController、ThreadOfExtor、MDGPara 和MDGCfgInfo四個類。

圖7 MDGController控制器設計類圖

(1) MDGPara類定義了與MDG圖構建相關的參數(shù)。它的relName、weight和implClsName分別表示模塊關系名稱、權重和對應抽取器類的類名。

(2) 從配置文件中獲取用戶需要提取模塊關系、每個關系的權重及對應的提取器類名等，并裝配成MDGPara類對象的列表返回，采用的方法是MDGCfgInfo類中的方法getMDGPara。

(3) ThreadOfExtor類可使每個提取器以獨立的線程進行運行。它實現(xiàn)了Java類庫中Runnable接口的run方法。ExtorOfThread類的構造函數(shù)包含extor、mdgs和idx三個輸入?yún)?shù)。extor參數(shù)表示實現(xiàn)了IExtrator接口的提取類對象。mdgs參數(shù)表示一個MDG圖列表對象，而idx表示extor對象生成的中間MDG存放在mdgs中的下標位置。

(4) MDGController類定義了兩個屬性mdgParas和mdgs，以及mergeMDG和getMDG兩個方法。mdgParas和mdgs屬性分別用于保存MDGPara類對象列表和MDG類對象列表。mergeMDG方法合并mdgs中的各個中間MDG，返回最終的MDG。而getMDG方法則根據(jù)mdgParas中各對象，依次獲取提取器類名，動態(tài)構建對應的提取器對象extor，傳入extor、mdgs和下標以實例化ExtorOfThread對象，并啟動它的run方法。每個ExtorOfThread對象生成完中間MDG圖后，調(diào)用mergeMDG返回最終的MDG。

圖8的時序圖描述了當用戶接口UI向MDGController控制器發(fā)出構建MDG圖請求后，MDGController控制器的工作流程。具體而言：MDGController控制器首先向MDGCfgInfo對象請求獲取構建MDG圖所需的配置參數(shù)，然后再根據(jù)MDGCfgInfo對象返回配置參數(shù)列表中的各個提取器類名，依次生成對應的提取器線程ThreadOfExtor對象，啟動它們并發(fā)出生成中間MDG圖請求；當每個ThreadOfExtor提取器線程對象都生成完中間MDG圖后，MDGController控制器合并這些中間MDG圖，生成最終MDG圖返回給用戶接口UI。

圖8 MDGController控制器的工作流程

4 TL4JMDG工具的性能評估

為了評估TL4JMDG工具的性能，下面以三款不同規(guī)模的開源Java軟件為實驗對象，并與Chava*工具(通過擴展Chava而開發(fā)出的MDG圖構建工具)進行實驗對比。

4.1 實驗環(huán)境

實驗硬件環(huán)境：Intel(R) Core(TM) 2.60 GHz的Lenovo i5-3240MCPU，RAM 4 GB。

實驗軟件環(huán)境：JDK7及JHotDraw6、JfreeChart和jEdit三款規(guī)模從小到大的開源Java軟件。三款開源軟件的基本情況如表3表示。

表3 實驗軟件信息

4.2 性能分析

圖9-圖12分別給出了運用TL4JMDG和Chava*工具在構建三款實驗軟件的繼承、實現(xiàn)、關聯(lián)和方法調(diào)用MDG圖的耗時情況。從圖9-圖12可以看出：在構建繼承、實現(xiàn)、關聯(lián)和方法調(diào)用MDG圖時TL4JMDG較Chava*耗時更短，其主要是由于Chava*訪問數(shù)據(jù)庫較TL4JMDG直接訪問內(nèi)存耗時更多，而且實驗軟件規(guī)模越大對比越明顯。此外，與構建其他三種關系的MDG圖相比，構建方法調(diào)用MDG圖的耗時更長。其原因主要有兩個：一是方法調(diào)用是Java模塊之間最主要的消息通信方式，方法調(diào)用關系普遍存在于Java模塊之間；二是在TL4JMDG和Chava*在分析方法調(diào)用關系時，需要遍歷更多程序元素，耗時也相對較多。

圖9 構建繼承關系MDG圖的耗時情況

圖10 構建實現(xiàn)關系MDG 圖的耗時情況

圖11 構建關聯(lián)關系MDG 圖的耗時情況

圖12 構建方法調(diào)用關系 MDG圖的耗時情況

圖13給出了運用TL4JMDG和Chava*工具在構建三款實驗軟件的包含繼承、實現(xiàn)、關聯(lián)和方法調(diào)用四種關系的MDG圖。從圖13可以看出生成包含這四種關系的MDG圖時TL4JMDG較Chava*耗時更短。此外，從圖13與圖9-圖12對比中可以看出：Chava*生成繼承、實現(xiàn)、關聯(lián)和方法調(diào)用四種MDG圖的總耗時與生成包含這四種關系的MDG圖的耗時相差較小，而TL4JMDG則相差較多。其原因是TL4JMDG工具在生成包含多種關系的MDG圖時，啟動獨立的線程去生成單一關系的MDG，提高了生成MDG圖步驟的并行性，進而降低了構建包含多種關系MDG圖的耗時。

圖13 構建包含繼承、實現(xiàn)、關聯(lián)和方法調(diào)用四種關系的MDG圖耗時情況

5 結(jié) 語

本文基于開源框架JTransformer和tuProlog，提出了一種基于邏輯的Java模塊依賴圖構建工具TL4JMDG，給出了該工具的設計與實現(xiàn)，并評估了其性能。TL4JMDG工具具有良好的可配置性、可擴展性，可較好地用于基于MDG圖的Java模塊聚類分析。未來我們將基于TL4JMDG工具開展Java模塊多目標聚類算法的研究工作。

[1] Mitchell B S, Mancoridis S. On the automatic modularization of software systems using the bunch tool[J].Software Engineering, IEEE Transactions on,2006,32(3):193-208.

[2] Mitchell B S, Mancoridis S. On the evaluation of the Bunch search-based software modularization algorithm[J].Soft Computing,2008,12(1):77-93.

[3] de Barros M O. An analysis of the effects of composite objectives in multiobjective software module clustering[C]//Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference.ACM,2012:1205-1212.

[4] Jeet K, Dhir R. Software re-engineering using imperialist competitive algorithm[J].ACM SIGSOFT Software Engineering Notes,2013,38(6):1-5.

[5] Kumari A C, Srinivas K, Gupta M P. Software module clustering using a hyper-heuristic based multi-objective genetic algorithm[C]//Advance Computing Conference (IACC), 2013 IEEE 3rd International.IEEE,2013:813-818.

[6] Praditwong K. Solving software module clustering problem by evolutionary algorithms[C]//Computer Science and Software Engineering (JCSSE), 2011 Eighth International Joint Conference on.IEEE,2011:154-159.

[7] Praditwong K, Harman M, Yao X. Software module clustering as a multi-objective search problem[J].Software Engineering, IEEE Transactions on,2011,37(2):264-282.

[8] K?hler V, Fampa M, Araújo O. Mixed-Integer Linear Programming Formulations for the Software Clustering Problem[J].Computational Optimization and Applications,2013,55(1):113-135.

[9] Hall M, Walkinshaw N, Mcminn P. Supervised software modularisation[C]//Software Maintenance (ICSM), 2012 28th IEEE International Conference on.IEEE,2012:472-481.

[10] Chen Y. Reverse engineering[C]//Practical reusable UNIX software.John Wiley & Sons, Inc.,1995:177-208.

[11] Chen Y, Gansner E R, Koutsofios E. A C++ data model supporting reachability analysis and dead code detection[J].Software Engineering, IEEE Transactions on,1998,24(9):682-694.

[12] Korn J, Chen Y, Koutsofios E. Chava: Reverse engineering and tracking of java applets[C]//Reverse Engineering, 1999. Proceedings. Sixth Working Conference on.IEEE,1999:314-325.

[13] Laramee R S. Bob’s Concise Introduction to Doxygen[R].Technical Technical report, The Visual and Interactive Computing Group, Computer Science Department, Swansea University, Wales, UK, 2007.(available online), 2011.

[14] Muhammad S, Maqbool O, Abbasi A Q. Evaluating relationship categories for clustering object-oriented software systems[J].IET software,2012,6(3):260-274.

[15] Wielemaker J, Schrijvers T, Triska M, et al. Swi-prolog[J].Theory and Practice of Logic Programming,2012,12(1-2):67-96.

[16] Alves T L, Hage J, Rademaker P. A comparative study of code query technologies[C]//Source Code Analysis and Manipulation (SCAM), 2011 11th IEEE International Working Conference on.IEEE,2011:145-154.

A LOGIC-BASED CONSTRUCTION TOOL FOR JAVA MODULE DEPENDENCY GRAPH

Du Xin Zhao Kang*Ni Youcong Shen Zhipeng

(FacultyofSoftware,FujianNormalUniversity,Fuzhou350108,Fujian,China)

The application of the software module clustering algorithms based on Java module dependency graph (MDG) is limited to certain degree due to the shortage in construction tools for Java MDG at present. Aiming at this issue, we proposed a logic-based Java module dependency graph construction tool named TL4JMDG. Supported by open source frameworks JTransformer and tuProlog, TL4JMDG tool achieves the extraction of Java modules relationship and the generation of MDGs in logical way. In this paper we illustrate the design and implementation of TL4JMDG tool and give the comparison of time consuming in regard to MDG construction by TL4JMDG tool and the Chava-based tool. The TL4JMDG tool has good configurability, extensibility and performance, and this makes the current existing MDG-based clustering algorithms be better applied in Java software module clustering.

Software module clustering Module relationship Module dependency graph JTransformer

2014-08-09。國家自然科學基金項目(61305079);武漢大學軟件工程國家重點實驗室開放基金項目(SKLSE2012-09-28)。杜欣，副教授，主研領域：演化計算，基于搜索的軟件設計。趙康，碩士生。倪友聰，副教授。沈志鵬，本科生。

TP311

A

10.3969/j.issn.1000-386x.2016.04.002