一种基于逻辑的Java模块依赖图构建工具
2016-05-09倪友聪沈志鹏
杜 欣 赵 康 倪友聪 沈志鹏
一种基于逻辑的Java模块依赖图构建工具
杜 欣 赵 康*倪友聪 沈志鹏
(福建师范大学软件学院 福建 福州 350108)
目前Java模块依赖图MDG(Module Dependency Graph)的构建工具还比较稀缺，从一定程度上限制了基于MDG图的软件模块聚类算法的应用。针对这一问题，提出一种基于逻辑的Java模块依赖图构建工具TL4JMDG(the tool logic-based for Java MDG)。在开源框架JTransformer和tuProlog的支持下，TL4JMDG工具以逻辑方式实现了Java模块关系的抽取和MDG图的生成。阐述TL4JMDG工具的设计与实现，并给出TL4JMDG工具和基于Chava工具构建MDG的耗时比较。TL4JMDG工具具有较好的可配置性、可扩展性和性能，使得目前已有的基于MDG图的聚类算法能更好地应用于Java软件模块聚类。
软件模块聚类 模块关系 模块依赖图 JTransformer
0 引 言
软件模块化可以提高系统的可理解性、降低系统的维护费用。软件模块聚类是软件模块化的一种重要手段。目前已涌现出一批基于模块依赖图MDG的软件模块聚类算法。Mitchell[1, 2]等人使用了爬山算法、遗传算法等启发式算法进行软件模块聚类研究。为了进一步增大搜索空间，提高解质量，一些多目标软件模块聚类算法[3-9]被纷纷提出。Praditwong[7]等人首次将软件模块聚类作为一个多目标优化问题进行研究，提出了两种多目标软件模块聚类算法ECA和MCA。De Barros[3]提出一种基于多目标遗传算法的软件模块聚类方法。Gupta[5]等人提出一种软件模块多目标聚类算法MHypGA。上述这些软件聚类算法都直接或间接地利用MDG图来计算各个目标的值。上述这些算法大多集中在对C或C++程序模块进行聚类。它们常常借助已有的Cia[10]和Acacia[11]等工具构建相应的MDG图，而针对Java程序模块的MDG图构建工具还比较稀缺，这从一定程度上限制了基于MDG图的软件模块聚类算法的应用。虽可基于Doxygen[13]和Chava[12]等Java源代码分析工具开发Java程序模块的MDG图构建工具，但仍需要解析Doxygen输出的各种不同格式的结果文件或处理Chava结果数据库中各种不同结构的表。这不仅面临一定的复杂性，而且影响到Java程序模块的MDG图构建工具的可配置性、可扩展性和性能。
针对上述问题, 本文提出一种基于逻辑的Java模块依赖图构建工具TL4JMDG。TL4JMDG工具借助开源JTransformer框架将Java程序转换为SWIProlog语言的逻辑事实库，再将该事实库转换为tuProlog语言的事实库，进一步在tuProlog多范型编程框架下以可扩展和可配置的方式实现Java模块关系的抽取和MDG图的生成。
1 背景知识
下面简单介绍本文涉及的MDG图、JTransformer和tuProlog框架等背景知识。
1.1 MDG图
MDG图是一种表示程序中模块之间依赖关系的无向图。它由顶点和带权值的边构成。其中：顶点表示模块，边表示模块之间的关系，每种模块关系可以赋予不同权重，边上的权值是模块间存在多种关系的权值和。面向对象编程语言多以类和接口作为模块，模块之间关系往往定义为类间的继承、关联、方法调用以及接口与实现等关系。模块之间关系存在着强弱之分，在软件模块聚类研究中常常需要对不同关系赋予不同权重，体现它们对聚类结果的影响[14]。
本文TL4JMDG工具是一种面向Java程序的MDG构建工具。下面举一小例子解释Java程序与MDG图之间的映射关系。下面的程序代码和图1分别是Java程序片断及其所对应的MDG图。程序声明了包demo，并定义了Person、Student和Teacher三个类及其之间的关系。程序中第9行和10行指示了Student类和Teacher类分别与Person类之间存在继承关系；第11行和第13行定义了Teacher类与Student类之间存在关联和方法调用关系。例中假定继承、关联和方法调用三种模块关系的权重被分别设为4、2和1，则程序片断对应的MDG如图1所示。图1表示的MDG图包括名为demo.Person、demo.Student和demo.Teacher三个结点和三条边。
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 程序对应的MDG图
本文TL4JMDG工具借助JTranformer框架来构建Java程序的MDG图。
1.2 JTransformer框架
JTransformer[14,15]是一种基于逻辑的Java程序分析和重构框架。它的核心功能是将Java程序变换成SWIProlog语言[14]的逻辑事实库。JTransformer框架中定义了一组用于表示Java语言语法树结点及其之间关系的SWIProlog谓词。通过这些谓词可将Java程序变换成等价的SWIProlog逻辑事实库。
在上例的基础上，给出这种等价变换的简单说明。图2示意了程序片断对应的一棵语法树。图2中的椭圆表示树的结点，旁边的数字表示结点的ID号；矩形框表示结点的属性值；实有向弧边表示结点之间的父子关系；无向边表示结点与属性的关系；虚有向弧表示结点间的引用关系，弧上的标识符定义了引用关系的类型名。下面以图2中旁边加实心三角形的结点为例进行说明。该结点的ID号、父结点ID号和名称分别为28969、28978和Student。该结点引用ID号为28976的结点，且引用关系的类型为extendsT。
图2 Java程序的语法树
Java语法树结点以及结点之间的引用关系可用JTransformer定义的一阶谓词进行表示。根结点packageT的谓词表示中第一个变元表示结点ID号，第二个变元表示包名。除根结点外，其余结点谓词的第一个变元表示结点的ID号，第二个变元表示父节点的ID号，其他项由结点的类型确定。这些项用于表示结点的属性、结点与其他结点之间的引用关系等。引用关系谓词的第一和第二个变元分别表示引用关系的ID号和被引用结点的ID号。在结点谓词和引用关系谓词定义中的变元名统一用‘_’作为前缀，并约定名为‘_’的变元是匿名变元。式(1)和式(2)分别给出classT类型结点和extendsT类型引用关系的谓词定义。对一个具体的Java程序，其语法树中的每个结点及其之间的引用关系都可用不含变元的谓词公式表示，形成一条逻辑事实。例如图2中旁边加实心三角形的结点可表示成式(3)对应的一条逻辑事实，该结点对应的一个引用关系可用式(4)定义的一条逻辑事实进行表示。因而，一个Java程序可等价表示成一个逻辑事实库。表1示意了图2对应的逻辑事实库。
表1 程序对应的逻辑事实库
classT(_clsid,_pkgid,_name,[_ref1,…,_refn])
(1)
extendT(_id,_clsId)
(2)
classT(28969,28978,′Student′,[28980])
(3)
extendT(28969,28985)
(4)
借助JTransformer虽可将Java程序转换为SWIProlog逻辑事实库，但已有的SWIProlog编程框架不能很好支持与Java语言的多范型编程。因而，TL4JMDG工具使用tuProlog框架作为编程环境。将SWIProlog逻辑事实库变换为tuProlog的逻辑事实库。下面简单介绍tuProlog框架。
1.3 tuProlog框架
tuProlog是一种具有多范型编程和并行多线程推理能力的Prolog框架。本文TL4JMDG工具借助tuProlog框架中的Theory、Prolog和SolveInfo三类，可在Java环境运用多线程访问Prolog资源和功能。Theory类用于实例化Java程序事实库，而Prolog类提供解析执行逻辑程序和命令的功能，并将返回结果封装在SolveInfo类对象中，利用SolveInfo类提供的方法可遍历解析结果。
简要介绍TL4JMDG工具开发的背景知识后，下面给出它的具体设计与实现。
2 TL4JMDG工具总体设计
图3示意了TL4JMDG工具的工作流程。其主要包括配置文件生成、tuProlog逻辑事实库生成和MDG图生成三个阶段。在第一阶段中，用户指定Java程序文件和输出MDG文件的位置，以及需要提取的模块关系和权值等信息，并通过UI模块将这些信息写入到配置文件中。在第二阶段中，借助JTransformer框架先将Java程序转化为SWIProlog逻辑事实库，再通过SWI2tu转换器将该逻辑事实库转换为tuProlog逻辑事实库。SWI2tu转换器主要针对SWIProlog和tuProlog逻辑事实库在字符编码和指令格式上的差异，进行相应的字符编码转换和指令格式转换。在第三阶段中，MDG图生成器MDGCreator先读入配置文件，决定要抽取的模块关系，再基于tuProlog逻辑事实库抽取对应的模块关系，最后根据配置文件中各种模块关系的权重，生成Java程序对应的MDG图。
图3 MDG图构建工作流程图
在TL4JMDG工具中，MDG图生成器MDGCreator是最为关键和核心的模块。下面详细阐述它的设计与实现。
3 MDGCreator生成器的设计与实现
MDGCreator生成器主要由MDGController控制器和一组模块关系提取器MDGExtractor构成。图4示意了它的工作流程。其主要包含启动MDGExtractor提取器，生成中间MDG图和生成最终MDG图三个阶段。在第一阶段中，MDGController控制器读取配置文件获取用户需要提取的模块关系，并行启动相应的MDGExtractor提取器。在第二阶段中，每种MDGExtractor提取器在逻辑事实库上查询一种特定的模块关系，并根据查询结果构建出一个中间MDG图；在第三阶段中，MDGController控制器根据关系的权重值，通过合并各个中间MDG图，构建出最终MDG图。下面给出MDGExtracor提取器和MDGController控制器的设计与实现。
图4 MDGCreator工作流程示意图
3.1 MDGExtracor提取器设计与实现
图5给出了MDGExtracor提取器的设计类图。其包括extractorPkg、mdgPkg和prologPkg三个包。
图5 MDGExtracor提取器设计类图
(1) extractorPkg包包含了IExtractor接口和一组具体的提取器类。IExtractor接口中的方法generateMDG定义了各种提取器类向外部提供的公共行为，即抽取一种特定的模块关系，生成中间MDG。目前TL4JMDG工具实现了继承、实现、关联和方法调用四种模块关系的提取器，分别由ExtractorOfExt、ExtractorOfImp、ExtractorOfAsso和ExtractorOfCal四个类具体实现。用户可扩展定义自己的提取器类，以抽取其他模块关系。
(2) mdgPkg包包含MDG、Edge和Node三个类，它们分别用于定义MDG图及其边和结点。Node类中的id和name属性分别表示结点id和名称。Edge类中head、tail和weight三个属性分别表示边关联的两个结点以及权值。为了今后扩展成有向图，head、tail可定义为弧尾和弧点结点。MDG类中nodes和edges分别用于表示MDG图的结点集和边集。
(3) prologPkg包包含了tuprolog支持库中Theory、Prolog和SolveInfo三个类。Theory类的构造函数以Java程序逻辑事实库文件作为输入流，生成tuProlog引擎可加载的理论。Prolog类中setTheory、solve和solveNext三个方法分别表示加载理论、解析执行逻辑程序返回解和获取下一个解。solve和solveNext方法都是返回SolveInfo对象，可请求SolveInfo类方法isSuccess判断Prolog对象执行结果是否成功，如成功可继续获取下一个解。
限于篇幅下面仅以继承关系提取器ExtractorOfExt为例说明提取器类的实现方案。图6的时序图描述了当MDGController控制器向ExtractorOfExt提取器发出生成继承关系MDG图的请求后，ExtractorOfExt提取器的工作流程。具体而言：ExtractorOfExt提取器根据Java程序逻辑事实库的位置实例化Theory对象，然后创建Prolog对象，再请求该Prolog对象加载实例化后的Theory对象；接着ExtractorOfExt提取器发送查询模块继承关系的逻辑程序文本，并请求Prolog对象解析执行，Prolog对象执行后返回SolveInfo结果对象； ExtractorOfExt提取器根据返回的SolveInfo对象判断执行是否成功，如成功则多次请求Prolog对象获取每一个解；最后ExtractorOfExt提取器根据所获得的解生成继承关系MDG图。
图6 MDGExtractor提取器的工作流程
表2给出了查询继承关系的逻辑程序文本。在表2中，第1行到第3行用于查询一个类的合格名。第4行表示查询该类引用的父类。第5行到第7行表示获取父类的ID(由_clsID指示)后，再查询该父类的合格类名。表2的程序文本由Prolog引擎在Java程序逻辑事实上解析执行后，可获得Java程序中所有类的继承关系，并能确定每个继承关系中子类和父类的合格类名。
表2 继承关系提取器查询谓词
3.2 MDGController控制器设计与实现
图7给出了MDGController控制器的设计类图。mdgCtlPkg包给出了控制器的设计，其主要包含MDGController、ThreadOfExtor、MDGPara 和MDGCfgInfo四个类。
图7 MDGController控制器设计类图
(1) MDGPara类定义了与MDG图构建相关的参数。它的relName、weight和implClsName分别表示模块关系名称、权重和对应抽取器类的类名。
(2) 从配置文件中获取用户需要提取模块关系、每个关系的权重及对应的提取器类名等，并装配成MDGPara类对象的列表返回，采用的方法是MDGCfgInfo类中的方法getMDGPara。
(3) ThreadOfExtor类可使每个提取器以独立的线程进行运行。它实现了Java类库中Runnable接口的run方法。ExtorOfThread类的构造函数包含extor、mdgs和idx三个输入参数。extor参数表示实现了IExtrator接口的提取类对象。mdgs参数表示一个MDG图列表对象，而idx表示extor对象生成的中间MDG存放在mdgs中的下标位置。
(4) MDGController类定义了两个属性mdgParas和mdgs，以及mergeMDG和getMDG两个方法。mdgParas和mdgs属性分别用于保存MDGPara类对象列表和MDG类对象列表。mergeMDG方法合并mdgs中的各个中间MDG，返回最终的MDG。而getMDG方法则根据mdgParas中各对象，依次获取提取器类名，动态构建对应的提取器对象extor，传入extor、mdgs和下标以实例化ExtorOfThread对象，并启动它的run方法。每个ExtorOfThread对象生成完中间MDG图后，调用mergeMDG返回最终的MDG。
图8的时序图描述了当用户接口UI向MDGController控制器发出构建MDG图请求后，MDGController控制器的工作流程。具体而言：MDGController控制器首先向MDGCfgInfo对象请求获取构建MDG图所需的配置参数，然后再根据MDGCfgInfo对象返回配置参数列表中的各个提取器类名，依次生成对应的提取器线程ThreadOfExtor对象，启动它们并发出生成中间MDG图请求；当每个ThreadOfExtor提取器线程对象都生成完中间MDG图后，MDGController控制器合并这些中间MDG图，生成最终MDG图返回给用户接口UI。
图8 MDGController控制器的工作流程
4 TL4JMDG工具的性能评估
为了评估TL4JMDG工具的性能，下面以三款不同规模的开源Java软件为实验对象，并与Chava*工具(通过扩展Chava而开发出的MDG图构建工具)进行实验对比。
4.1 实验环境
实验硬件环境：Intel(R) Core(TM) 2.60 GHz的Lenovo i5-3240MCPU，RAM 4 GB。
实验软件环境：JDK7及JHotDraw6、JfreeChart和jEdit三款规模从小到大的开源Java软件。三款开源软件的基本情况如表3表示。
表3 实验软件信息
4.2 性能分析
图9-图12分别给出了运用TL4JMDG和Chava*工具在构建三款实验软件的继承、实现、关联和方法调用MDG图的耗时情况。从图9-图12可以看出：在构建继承、实现、关联和方法调用MDG图时TL4JMDG较Chava*耗时更短，其主要是由于Chava*访问数据库较TL4JMDG直接访问内存耗时更多，而且实验软件规模越大对比越明显。此外，与构建其他三种关系的MDG图相比，构建方法调用MDG图的耗时更长。其原因主要有两个：一是方法调用是Java模块之间最主要的消息通信方式，方法调用关系普遍存在于Java模块之间；二是在TL4JMDG和Chava*在分析方法调用关系时，需要遍历更多程序元素，耗时也相对较多。
图9 构建继承关系MDG图的耗时情况
图10 构建实现关系MDG 图的耗时情况
图11 构建关联关系MDG 图的耗时情况
图12 构建方法调用关系 MDG图的耗时情况
图13给出了运用TL4JMDG和Chava*工具在构建三款实验软件的包含继承、实现、关联和方法调用四种关系的MDG图。从图13可以看出生成包含这四种关系的MDG图时TL4JMDG较Chava*耗时更短。此外，从图13与图9-图12对比中可以看出：Chava*生成继承、实现、关联和方法调用四种MDG图的总耗时与生成包含这四种关系的MDG图的耗时相差较小，而TL4JMDG则相差较多。其原因是TL4JMDG工具在生成包含多种关系的MDG图时，启动独立的线程去生成单一关系的MDG，提高了生成MDG图步骤的并行性，进而降低了构建包含多种关系MDG图的耗时。
图13 构建包含继承、实现、关联和方法调用四种关系的MDG图耗时情况
5 结 语
本文基于开源框架JTransformer和tuProlog，提出了一种基于逻辑的Java模块依赖图构建工具TL4JMDG，给出了该工具的设计与实现，并评估了其性能。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
