基于子图发现的设计模式识别系统——CodeMiner插件和源码解析模块的设计与实现---毕业论文

本本 科科 毕毕 业业 论论 文文 基于子图发现的设计模式识别基于子图发现的设计模式识别系统系统 CodeMiner 插件和源码解析模块的设计与实现插件和源码解析模块的设计与实现 Design Pattern Detecting System by Subgraph Discovery The Design and Implementation of CodeMiner Plug-in and Code Analysis Module 姓 名： 学 号： 学 院：软件学院 系：软件工程 专 业：软件工程 年 级： 指导教师： 年年 月月 摘摘 要要 现代软件工业已经广泛地应用设计模式来重用成功的设计实践和提高软件系统 的质量，然而受制于软件系统的规模和设计文档的缺失，开发人员无法直观地理解 现有软件系统中应用的设计模式，从源码中发现设计模式实例对于提高软件可理解 性和可维护性、软件设计重用以及软件重构具有重要意义。 为了便于在实际应用中理解、选择和实践设计模式，设计模式的特征通常以非 形式化的方式描述，在进行设计模式识别时需要对其进行形式化的表示，已有的研 究中采用不同的中间表示来描述设计模式和系统源码以及提出不同的算法来进行设 计模式识别。本文在比较目前已有的设计模式发现方法的基础上，进一步提出了一 种新的设计模式识别方法。 本文提出了一种基于子图发现和有限自动机的设计模式识别方法，将抽象语义 图作为系统源码和设计模式签名的中间表示，将在系统源码中发现设计模式实例的 问题转化成在非连通图中发现同构子图的问题。设计模式签名描述了设计模式的结 构和行为特征，并转换成确定性有限自动机，有限自动机的终态代表着特定的设计 模式。子图发现算法采用有限自动机来引导设计模式候选实例的产生，从而缩小搜 索空间，提高了算法效率。 另外，本文实现了 Eclipse 插件 CodeMiner 来支持所提出的设计模式识别方法， 采用 Eclipse JDT(Java Development Toolkit)对目标系统的源码进行解析，从源码中提 取的信息构建抽象语义图，通过在 CodeMiner 上对 3 个开源项目进行实验，并将实 验结果与现有的相关研究的实验结果进行比较，在可识别的设计模式种类和识别的 模式实例准确性上有明显的优势，表明本文提出的基于子图发现的设计模式识别方 法具有较高的应用价值。 关键词：关键词：设计模式；抽象语法树；Eclipse 插件 Abstract Modern software industry has widely adopted design patterns to reuse the best practices and improve the quality of software systems. However, many systems are legacy and the design documents is often missing, this retard the comprehension of systems design and architecture during maintenance actives. Detecting design patterns from existing source code can improve systems internal quality attributes such as reusability and maintainability. Design patterns are normally described informally to understand and used them easily in practice; researchers need to characterize design patterns formally during design pattern detection. Related work uses several intermediate representations of software systems and design patterns, and introduces or proposes some algorithms to detect design pattern instances. This paper analyzed related approaches for mining design patterns from source code in a comparative study and proposed a novel approach for design pattern detection. The paper presented an algorithm based on subgraph discovery and finite automata to recognize instances of design patterns in a software system. In the approach, the system and design patterns are both described with ASG (Abstract Syntax Graph), therefore finding a design pattern is to match ASG sub-structures with pattern signatures. Design pattern signatures describe the structural and behavior characteristics of design patterns and are transformed into DFA (Deterministic Finite Automata), the DFA is used to guide candidate generation, which narrows the search space and improves the computational efficiency. And this paper also developed an Eclipse plug-in CodeMiner to evaluate the algorithm. Experimental evaluation on three open-source projects demonstrates the accuracy and efficiency of the proposed approach. Key words: design pattern; abstract syntax tree; Eclipse Plug-in. 目录目录 第一章第一章绪论绪论1 1.1 研究背景及选题意义研究背景及选题意义1 1.2 . 研究现状及存在问题研究现状及存在问题 2 1.3 . 主要研究内容及特色主要研究内容及特色 4 1.4 本文结构安排本文结构安排 5 第二章第二章CodeMiner 的需求分析和总体架构的需求分析和总体架构6 2.1. 现有设计模式识别方法的比较现有设计模式识别方法的比较 6 2.1.1 设计模式特征的选择 6 2.1.2 中间表示形式的选择 8 2.1.3 匹配方式的选择 .8 2.2. CodeMiner 的需求分析的需求分析 9 2.2.1 功能需求分析.9 2.2.2 非功能性需求分析11 2.3. CodeMiner 的总体架构的总体架构 12 2.4. 系统相关技术概述系统相关技术概述 14 2.4.1 Eclipse 插件体系结构.14 2.4.2 借助 Eclipse JDT 进行源码解析的原理17 2.5. 小结小结 20 第三章第三章CodeMiner 的设计的设计.21 3.1CodeMiner 插件插件 21 3.2源码解析源码解析 26 3.3.设计模式签名设计模式签名 30 3.3.1 结构型设计模式 .31 3.3.2 创建型设计模式 .33 3.3.3 行为型设计模式 .35 3.4.设计模式识别设计模式识别 39 3.4.1 基于子图发现的设计模式识别原理.39 3.4.2 设计模式识别的设计 42 3.5.小结小结 44 第四章第四章CodeMiner 的实现的实现.45 4.1.CodeMiner 插件工程的结构插件工程的结构 45 4.2CodeMiner 插件项目的整体实现插件项目的整体实现 46 4.3CodeMiner 插件相关扩展点的实现插件相关扩展点的实现 48 4.3.1 CodeMiner 插件操作扩展点的实现49 4.3.2 CodeMiner 插件视图扩展点的实现51 4.3.3 CodeMiner 插件透视图扩展点的实现.53 4.4.小结小结 55 第五章第五章实验结果实验结果.56 5.1.实验数据介绍实验数据介绍 56 5.1.1 JUnit 56 5.1.2 JHotDraw.56 5.1.3 JRefactory .56 5.2.实验结果分析实验结果分析 57 5.2.1 识别的设计模式实例分析.57 5.2.2 设计模式变种的分析 61 5.3.小结小结 63 第六章第六章总结和展望总结和展望 .64 参考文献参考文献 66 致谢致谢68 TABLE OF CONTENTS Chapter 1: Introduction1 1.1 Background and Significance .1 1.2 Research Status and Problems 2 1.3. Main Research and Contributions of The Paper 4 1.4 Outline of Thesis 5 Chapter 2: Requirement Analysis and Architecture of CodeMiner6 2.1 . Comparative Study on Design Pattern Mining Techniques 6 2.1.1 Pattern Aspects Checked.6 2.1.2 Intermediate Representations.8 2.1.3 Exact vs. Approximate Matches 8 2.2 Requirement Analysis of CodeMiner 9 2.2.1 Functional Requirements 9 2.2.2 Non-Functional Requirements.11 2.3. The Overall Architecture of CodeMiner 12 2.4 . System Related Technologies Outline 14 2.4.1 Eclipse Plug-in Architecture14 2.4.2 The Theory of Code Analysis Using Eclipse JDT17 2.5 Summary 20 Chapter 3: Design of CodeMiner.21 3.1CodeMiner Plug-in 21 3.2Source Code Analysis 26 3.3.Design Pattern Signature 30 3.3.1 Structural Design Patterns.31 3.3.2 Creational Design Patterns33 3.3.3 Behavioral Design Patterns .35 3.4.Design Pattern Detection 39 3.4.1 The Theory of Design Patttern Detection by Subgraph Discovery.39 3.4.2 Design of Design Pattern Detection .42 3.5.Summary 44 Chapter 4: Implemention of CodeMiner45 4.1The Structure of CodeMiner Plug-in Project 45 4.2.Overall Implemention of CodeMiner Plug-in 46 4.3Implements of Extensions in CodeMiner Plug-in 48 4.3.1 Object Action Extension.49 4.3.2 View Extension51 4.3.3 Perspective Extension.53 4.4.Summary 55 Chapter 5: Experimental Results 56 5.1Introduction of Experimental Datas 56 5.1.1 JUnit.56 5.1.2 JHotDraw56 5.1.3 JRefactory.56 5.2.Evaluation Results 57 5.2.1 Detected Instances of Design Patterns57 5.2.2 Modified Design Patterns61 5.3.Summary 63 Chapter 6: Conclusions and Future Works .64 References66 Acknowledgements.68 第一章第一章 绪论绪论 设计模式是面向对象设计的一个高级抽象，是针对重复发生的软件问题的标准解决 基于子图发现的设计模式识别系统 - 2 - 方案。现代软件工业已经广泛地应用设计模式来重用成功的设计实践和提高软件系统的 质量，然而由于软件系统的规模和设计文档的缺失，导致软件系统的理解和维护也变得 越来越困难，因此从现有的系统源码中抽取设计模式成为许多研究领域的关键课题。这 里将对目前的研究现状以及存在的问题等进行阐述，最后对本文研究内容以及本文结构 安排等进行总体阐述。 1.1研究背景及选题研究背景及选题意义意义 由于现在的软件项目大都包含数目众多的组件，其结构变得相当复杂和混乱，从而 不利于软件系统的维护和改进。在软件系统的整个生命周期中，软件维护是十分重要和 复杂的阶段，可以占据整个投入的 50%-70%，程序理解在软件维护阶段起着重要的作用， 尤其当程序结构较复杂，而且相关的文档与系统不同步。软件工程数据，如代码、代码 的修改历史、执行路径以及错误报告等，蕴含着大量与项目管理、软件平台技术有关的 信息和知识。如果可以从上述大量的数据中挖掘出潜在的具有高度价值的信息和知识， 将更好地进行项目管理，生产出高质量的代码。 设计模式是软件设计中的一些普遍设计问题的解决方案，可以用统一的格式加以描 述，主要有：意图、动机、适用性、结构、参与者、协作、实现细节和代码示例等.上述 模板详细地说明了设计问题以及如何用模式中的类和对象来解决问题的特定情景1，记 录了设计产生的决定过程、选择过程和权衡过程，指导开发人员进行成功的系统设计和 实现。设计模式已被现代软件业广泛采用以复用成功的设计和体系结构以提高软件系统 的质量。 在许多大型软件项目中，设计文档经常缺失，即使设计文档可用，也可能随着系统 的改变和迁移而变得过时，很多时候，开发人员受到上市时间的影响，没有对他们的软 件进行充分的文档化，这些情况导致模式相关信息的丢失使应用设计模式的好处大打折 扣，使后来的开发人员对系统的理解和维护变得很困难2 。 从软件系统中的源码中发现所使用的设计模式已经成为许多研究领域的关键课题， 如在反向工程和代码重构方面。通过发现软件系统中使用的设计模式可以展现系统设计 的结构，帮助新系统开发人员更好地理解系统的设计和实现决策。 第一章 绪 论 - 3 - 1.2研究现状及存在问题研究现状及存在问题 目前，设计模式发现技术在国际上得到普遍关注，现在的大多数研究3-9 没有直接 从源代码去发现设计模式，而是引进了源代码的中间表示，各种具体的设计模式发现方 法主要的差别集中在源码模型、模式模型、查找算法三个方面，在这一节中，将简要介 绍设计模式发现这一研究课题上取得的成果。 Antoniol 等人3提出了基于软件度量和结构特征的多阶段搜索策略从源码或设计中发 现设计模式，多阶段搜索过程包括使用结构度量约束评价和使用方法委托约束评价。在 这种方法中，提出了抽象对象语言（Abstract Object Language，AOL）中间表示，源码 和设计模式都表示成 AOL，其中包含了类、属性、方法以及类之间的关系等信息。在结 构度量评价阶段，从 AOL 中提取类度量（如属性的数目，方法的数目，继承、关联、 聚合关系的数目），这种多阶段搜索策略有效地缩减了查找空间，能够发现 Adapter、Bridge、Composite、Decorator 和 Proxy 这些结构型设计模式。 Niere 等人10提出了一种以设计模式的行为分析作为重点的模式识别方法，在这种方 法中，采用了抽象语法树(Abstract Syntax Tree，AST)作为中间表示，源码被表示成抽象 语义图 (Abstract Syntax Graph，ASG)，每个设计模式形式上定义成一个图的转换规则， 图的转换规则可以看成是时序图的一个子集，分析算法对抽象语义图的某个子图使用图 转换规则以检查图的匹配问题，分析算法使用 FUJABA(From UML to Java And Back Again)环境作为平台，结合使用自底向上和自顶向下策略,最小化了规模问题。已经完成 的实验能够发现 Bridge、Strategy 和 Composite 模式。 Heuzeroth 等人4提供的方法结合了静态和动态分析来发现设计模式。静态分析读取 程序的源码并构建一个属性抽象语法树,接着在抽象语法树的节点上计算模式关系 P,提供 一个符合静态结构的候选集合(抽象语法树节点的元组集合) ,这个集合是源码中实际包含 模式保守的近似值。动态分析在静态分析结束后进行,静态分析提供的候选集合作为它的 输入。动态分析监控每个元组的节点的执行,进一步跟踪已执行节点的影响,检查候选实例 是否符合动态模式规则。 Tsantalis 等人5 应用现有的一种相似度评分算法来识别设计模式。类之间的结构关 系是以多个图和矩阵表示（如关联图和关联矩阵、泛化图和泛化矩阵等），设计模式也 以矩阵表示，设计模式的发现是通过计算表示系统源码的矩阵和表示设计模式的矩阵间 的相似度分值，目前这种方法可以识别 Adapter, Bridge, Composite, Decorator, Factory 基于子图发现的设计模式识别系统 - 4 - Method, Observer, Prototype, Singleton, Strategy, Template Method, 和 Visitor 模式。 Blewitt 等人6 开发了一个证明系统 Hedgehog，能够推理出以 Java 编写的系统中应 用的设计模式，这种方法强调了语义约束的重要性，语义约束说明了类之间是如何相互 关联的以及具体的方法操作是如何实现的。以 java.awt 包进行试验，可以识别 Command, Factory, Proxy 和 Singleton 模式。 Balanyi 等人11引进了设计模式标记语言(Design Pattern Markup Language, DPML),一 种基于 XML 的语言，作为设计模式的表示形式，同时源码被表示成 ASG。在这种方法 中，设计模式的发现过程是 ASG 的子结构和设计模式的 DPML 的匹配过程。这种方法 能够发现 Abstract Factory, Adapter, Bridge, Builder, Chain of Responsibility, Decorator, Factory Method, Prototype, Proxy, Singleton, Strategy, Template Method, and Visitor 模式。 Shi 和 Olsson9 提出了使用数据流图和控制流图来识别设计模式，这种方法在识别 Singleton 和 Flyweight 模式上效果很好，实现该方法的工具 PINOT 能够识别大部分 GoF 设计模式。 Gueheneuc 等人7 提出使用机器学习技术从源码中指纹识别出设计模式，大小，泛 化，内聚性和耦合性作为类的指纹。在这种方法中，首先，手工分析几个程序并查找出 组成设计模式的类，接着解析这些程序得到源码的模型，根据模式计算度量（类的指纹） ；其次，采用规则学习算法获得表征设计模式参与者类的规则集，根据这些规则可以识 别未知类的角色，这个算法可以消除不满足这些度量的类，因此能够减少搜索空间。 虽然在设计模式识别的研究上已经取得了显著的成果，研究人员提出或引进了许多 算法、中间表示以帮助更精确、有效地从系统源码中识别设计模式，并开发了一些工具 来识别设计模式，但是研究依旧存在着问题和难点： 1、在目前的研究中，对每个设计模式的特征还没有标准和严格的定义，在各种研究 方法中，通常研究人员根据自己的理解给设计模式以非正式的描述，这样导致即使是用 同一系统作为实验对象，识别出来的设计模式实例结果也存在很大差别。 2、设计模式识别的研究需要在实验来验证方法的准确性和效果，现在大多数实验都 是在开源系统上进行，由于开源系统无法提供所应用的设计模式的具体数量和确切位置， 加上设计模式存在变种以及一些模式描述的二义性，使得不同研究方法无法很好地进行 比较，目前还没有用于设计模式识别的基准系统可以提供。 第一章 绪 论 - 5 - 1.3主要研究内容及特色主要研究内容及特色 本文的研究内容是基于子图发现和有限自动机的设计模式识别。首先本文采用 ASG 来描述被研究的系统和设计模式，这样设计模式的识别就转换有向非连通图的子图发现 问题；其次，本文提出了一个子图发现算法以用来识别系统中的设计模式实例；最后， 为了分析这个方法，开发了 Eclipse 插件 CodeMiner，并在 CodeMiner 进行一系列的实验 以评估该方法和工具。 本研究采用的设计模式识别方法可以从系统源码信息模型、设计模式表示、模式识 别算法进行阐述： 1、系统源码信息模型：采用 ASG 作为源码的中间表示,根据对设计模式的结构和行 为特征的分析，分类和选择从源码中所要抽取的信息，以具体类、抽象类、方法作为 ASG 的顶点、以类之间的继承、关联、聚合关系，方法与类之间的返回类型、参数类型、 对象创建关系、方法与方法之间的调用依赖、重载关系作为 ASG 的边，构建系统源码的 中间表示。 2、设计模式表示：为了便于在实际应用过程中理解、选择和实践设计模式，设计模 式的特征通常是以非形式化的方式描述。在进行设计模式识别时需要对其进行形式化的 表示，本文采用确定性有限自动机(Deterministic Finite Automaton，DFA)作为设计模式的 中间表示，从设计模式的非形式化描述中提取设计模式签名，完成面向设计模式的 DFA 的定义和实现，并将设计模式签名转换成 DFA。 3、模式识别算法：由于系统源码和设计模式均选择抽象语义图作为中间表示，所以 设计模式识别问题就转化成子图发现问题，发现设计模式实例的过程就是在表示系统源 码的 ASG 中搜索与表示设计模式的子图同构的子结构，因此实现模式识别算法实现了子 图发现算法和图的同构算法以及同构定位功能。 由于本文采用的方法是基于图的模式识别方法，因此还实现基于可扩展存储结构的 图组件，用于保存表示系统源码和设计模式的 ASG，并提供对图的基本操作。 本文研究的着重点是设计与实现 CodeMiner 插件以支持基于子图发现的设计模式识 别方法，采用 Eclipse JDT 对系统源码进行解析以构建 ASG 以及设计模式签名的提取， CodeMiner 插件作为系统的应用层，可以对 Eclipse 中的 Java 项目系统调用源码解析模 块和设计模式识别模块来完成设计模式实例的发现，并将识别结果友好地显示出来而且 支持模式参与者类的定位；源码解析模块采用 Eclipse JDT 对系统源码进行解析，构建系 基于子图发现的设计模式识别系统 - 6 - 统源码对应的 AST 树，分析 AST 树提取信息构建 ASG；提取设计模式签名时，分析 GOF 的 23 种设计模式的结构和行为特征，将设计模式用与表示目标系统的 ASG 相同定 义的图结构表示。相比之前 Tsantalis 等人5 和 Dong 等人2 的研究,CodeMiner 特色如下： 1、CodeMiner 可以找到更多的设计模式实例，Tsantalis 和 Dong 都将系统描述成图 和矩阵，由于图中顶点数量过于庞大，将系统按照层次划分成一系列子系统，这样跨越 多个子系统的模式实例就无法识别到；而 CodeMiner 是基于子图发现算法，无须对系统 进行划分。 2、CodeMiner 只需运行一次就可以发现所有模式的实例，而之前的研究通常是运行 一次只能发现一个模式的实例。 3、CodeMiner 插件的设计模式识别结果的显示更加友好，能够支持设计模式实例参 与者类的定位和显示参与者类的角色，Tsantalis 和 Dong 的系统只是简单地显示设计模 式识别的实例个数或者参与者类。 1.4本文结构安排本文结构安排 本论文重点探讨基于子图发现和确定性有限自动机的设计模式识别方法和设计模式 发现工具的实现，总共分为六章，组织结构如下： 第一章 绪论， 介绍了课题研究背景及实际意义、设计模式发现的国内外研究现状 以及存在的问题等，最后阐述了本文的研究内容以及创新点； 第二章 CodeMiner 的需求分析和总体架构，对比现有研究，详细介绍 CodeMiner 的 功能和非功能需求，对系统的总体架构设计进行了展示和说明； 第三章 CodeMiner 的设计，详细阐述了 Eclipse 插件开发、源码解析、模式识别的原 理，并介绍了 CodeMiner 的总体设计和各个功能模块的具体设计； 第四章 CodeMiner 的实现，介绍基于 Eclipse Plug-in 的设计模式发现工具的整体实 现情况，详细说明 CodeMiner 各个模块的实现细节； 第五章 实验结果分析，分析 CodeMiner 在开源系统上进行实验得出的结果，以评估 本研究所采用方法的效果； 第六章 对本论文的总结和展望，分析了本研究尚待优化之处，并对下一步研究进行 了展望。 基于子图发现的设计模式识别系统 - 7 - 第二章第二章 CodeMiner 的需求分析的需求分析和总体架构和总体架构 从系统源码中发现设计模式的研究已经取得很大进展，研究人员所侧重的设计模式 方面、所采用的中间表示、实现的匹配算法等各不相同，互有优劣，依赖的平台和实现 的工具也各有千秋，通过分析比较现有的设计模式识别方法，可以对设计模式识别的原 理有了清楚的把握，比较全面而客观地收集、分析系统的需求，为研究的顺利进行和系 统的成功开发奠定良好的基础。下面将详细地比较现有研究方法所采用的技术和成果并 从中明确 CodeMiner 的需求，从而根据需求分析的内容定义 CodeMiner 的总体架构以及 所使用的技术框架。 2.1现有设计模式识别方法的比较现有设计模式识别方法的比较 从系统源码中挖掘设计模式实例有助于理解和追踪原始设计决策以及系统的重构， 目前在设计模式识别方向的研究成果的区别主要集中在以下七个方面： 一、每个设计模式通常是通过结构、行为和语义等方面进行描述的，不同的方法选 择其中的一个或者多个来识别； 二、现在的方法基本都是利用现有的反向工程工具来获得系统源码的中间表示，不 同的工具产生的中间表示多有不同，而不同的中间表示形式直接影响了模式识 别算法的选择； 三、在模式匹配上，一些方法要求精确匹配，相反另外一些方法则允许近似匹配； 四、在最终识别结果的显示上，一些方法只是显示识别到的模式实例数目，而有些 方法则展示了识别到的模式实例的位置； 五、大多数方法提供的工具都支持设计模式的自动识别，有一些工具则要求人工交 互； 六、每个研究的工具通常只支持某些模式的识别； 七、不同的方法采用不同的开源系统进行实验。 2.1.1 设计模式特征的选择设计模式特征的选择 每个设计模式都有自己的特征，基本上是通过结构、行为和语义三个方面进行区分， 第二章 CodeMiner 的需求分析和总体架构 - 8 - 其中结构特征是多数设计模式都具备的，以此来识别设计模式相对容易，因此很多方法 都考虑了设计模式的结构特征，如Pat12, DP+13 , JBOORET 34,基于 FUJABA 环境的 工具 8, 14, 15, SPQR16, CroCoPat17, DPRE 18, 19,以及Guhneuc等人开发的工具7 ，这些 方法的大多数考虑了类之间的关系，如泛化、关联、聚合，作为识别的主要属性，还有 一小部分考虑了类的属性和方法，因此基于模式的结构特征考虑的建模元素主要有泛化、 关联、聚合等关系以及类的属性和方法，上述这些建模元素是设计模式必不可少的结构 特征，比如一个设计模式可能需要含有泛化、关联、聚合关系的类集合，也可能要求一 个类中要包含一定数目的属性或方法。在现有的研究中，Guhneuc等人7 考虑了构造 函数、重载函数、类中方法的数目以及函数中包含的方法调用数目；Antoniol等人3考虑 了类中public、private、protected属性和方法的数目，以及关联、聚合、泛化关系的数目； Ferenc等人20收集了类的属性数目，public、private、protected方法和抽象、具体方法的 数目； Dong等人21 将类的属性和方法的数目作为类的权重，并用矩阵记录了类之间的 关系。 尽管从源码中获取行为信息相对较难，但是行为信息在设计模式识别中起着重要的 作用，在设计模式中加入行为分析可以很大程度上减少误判，设计模式的行为信息主要 为方法的调用及对象的创建，对行为信息的分析可以采用静态方式或者在系统运行时动 态分析。Antoniol等人3 静态地分析方法委托；Dong等人21静态地分析类之间的方法委 托和依赖；Park 等人22提出使用引用调用关系来静态地评估模式参与者间的运行时行为； Shi等人9提出使用控制流图分析来检查模式行为，尤其是Singleton和Flyweight模式。 除 了以上静态方式，一些研究人员提出动态地分析模式行为，因为有些模式要求模式参与 者类的对象间的交互和动作必须按照一定的顺序。 Heuzeroth等人4, 23 提出监视类的执 行，他们进一步追踪已经执行的类的效果已检查候选实例是否满足动态模式规则； Huang等人24追踪系统运行时操作的入口和出口，以及对象的分配和回收； Wendehals 等人15 通过人工调试程序来获得行为信息，对设计模式相关的方法设置断点并记录运 行时的方法轨迹，以产生相应的序列图。 对于模式的语义特征的应用，由于对模式语义特征的定义比较模糊，在目前的研究 中并不普遍。Blewitt 等人6 使用语义分析来决定类间的关联是一对一还是一对多，以 及这些关联是否必需，例如Vector和HashTable通常表明关联是一对多的；Dong 等人21 从类的命名规则中发掘模式相关的信息以获取类在相关模式中可能扮演的角色，如一个 基于子图发现的设计模式识别系统 - 9 - 类的名称中包含“strategy”，则该类很可能是Strategy模式的一部分。模式的语义特征应 用可以提高设计模式识别的准确率。 2.1.2 中间表示形式的选择中间表示形式的选择 现有的模式识别方法通常借助已有的反向工程工具将源码转换成中间表示以减少搜 索的复杂性。同样设计模式也以一些形式表示，如断言、语法等。因此实际上现在的研 究多是通过挖掘这些中间表示来识别模式实例。已经提出了的中间表示主要有： AST、ASG、位、向量、矩阵、欧拉模型等以及一些标准的表示形式，如 XML、控制流 图(Control Flow Graph, CFG)、数据流图(Control Flow Graph DFG)。通过对现有研究所采 用的中间表示的统计可知，大部分的方法3, 4, 9, 10, 15, 20 都选择 AST 或者 ASG 作为中间表 示，Antoniol 等人3 将源码和设计表示成 AOL，解析 AOL 得到 AST，最后从 AST 中提 取软件度量; Niere 等人8, 10 将设计模式和源码表示成 ASG，并结合自顶向下和自底向 上两种策略对图进行搜索来提高性能和精确度； Heuzeroth 等人4, 23 采用 AST 来定义 模式的静态方面，同时采用动作的时序逻辑(TLA)来描述模式的动态方面。 有些方法遵从 XML 格式，如 Balanyi 和 Ferenc11 引进了设计模式标记语言(Design Pattern Markup Language, DPML)来描述设计模式，使用 ASG 来表示源码；Dong 等人21 利用 Rational Rose 工具将源码的设计信息转换成 XML 格式；Osprey25 利用 Imagix 解 析源码，并将结果保存成 XML 格式，这样有助于识别结果的验证。 Kaczor 等人26 将设计模式识别问题陈述为有限位向量集上的操作，位-向量算法可 以通过有限的向量操作得到问题的解决方案，提高空间性能。 Costagliola 等人18, 19 提出使用图来表示系统的类图和使用可视语法来指定设计模式 规则，他们使用可视语言解析技术进行匹配；Seemann 等人27 实现的匹配算法也是基 于图的，他们的方法使用集合理论和谓词来定义模式；Zhang 等人28 扩展传统的图概念 来描述面向对象设计和设计模式，并使用子图同构技术来进行模式匹配。 2.1.3 匹配方式的选择匹配方式的选择 由于研究人员都是根据自己的理解来定义设计模式的特征，大多数方法识别模式时 需要系统的子模块同时满足定义的模式结构特征和行为特征，因此对相同的模式的不同 定义会导致不同的识别结果。模式识别如果采用严格的精确匹配会导致一些是模式实例 第二章 CodeMiner 的需求分析和总体架构 - 10 - 的候选者的丢失，因此有些方法采用近似匹配，如相似度评分5 和模板匹配2 ，通过 计算系统和设计模式的相似度进行模式匹配，近似匹配可以保留很多基本满足匹配规则 的候选者。 Niere 等人8 引进了模糊信念，信念的真值取值范围为0,1 ，用来表示每个结构规 则的精度，在识别设计模式时给每个结构规则设定阈值，以排除模糊值低于阈值的匹配， 这样有助于减少计算量和提高可扩展性；为了计算系统和模式之间的匹配度，Tsantalis 等人5 应用了一种相似度评分算法，不过该算法是一个不精确的图匹配算法，无法找出 两个图的精确匹配；Dong等人2 采用模板匹配算法计算系统的子模块和设计模式之间的 匹配度 ；Guhneuc等人7 提出了一种机器学习算法来计算软件度量并且通过规则学习 器使用置信度来推断规则；Ferenc等人20 为每个设计模式引进了预测器，使用机器学习 算法训练模式识别机以获得预测器的值，这些预测器的值可以作为标准与从系统中获得 的预测器值进行比较。 2.2 CodeMiner 的需求分析的需求分析 通过对现有设计模式识别方法的比较，可以发现相对其他方法，基于图表示方式的 模式匹配的设计模式识别方法可以更有效地从系统源码中发现设计模式实例，因此本文 也采用图作为系统源码和设计模式的中间表示，将在系统源码中发现设计模式的问题转 换为有向非连通图中的子图发现问题，并以此为前提，全面而客观地收集、分析和提炼 CodeMiner 的需求，下面将简要说明 CodeMiner 的需求分析。 2.2.1 功能需求分析功能需求分析 本文的主要目标是从系统源码中发现设计模式实例，以帮助开发人员对系统的理解 和维护，由于通常系统源码数量庞大，隐藏在源码中的信息零散而没有条理，需要将系 统源码转换成某些中间表示来降低搜索复杂性，设计模式也表示成某种格式，设计模式 识别方法实际上是从这些中间表示中发现设计模式实例。从目标系统的源码中识别设计 模式的过程主要包含三个部分(图 2-1)： (1) 对设计模式建模，分析设计模式的结构和行为特征，提取设计模式的签名，并将 其转换成某种中间表示。 (2) 以查找设计模式为目的，解析软件系统的源码，提取所需的建模信息（如类、方 基于子图发现的设计模式识别系统 - 11 - 法、类之间的关系等），建立源码信息模型。 (3) 以设计模式和目标系统源码的中间表示作为输入，调用相关的算法识别源码中的 设计模式。 图图 2-1: 设计模式识别流程设计模式识别流程 经过对设计模式识别原理和流程的深入了解和掌握，同时参考现有研究所采用的方 法，得出 CodeMiner 所要实现的五大功能： 1、源码解析：、源码解析：对目标系统的源码进行解析，需要提取出具体类、抽象类、接口和方 法，以及类与类、类与方法、方法与方法之间的关系，如关联关系、聚合关系、泛 化关系、包含关系、方法调用依赖、方法的返回类型依赖、方法的参数类型依赖、 方法重载关系等。 2、设计模式签名提取：、设计模式签名提取：描述不同类型的设计模式所需的信息各不相同，对结构型模 式需要描述类层次结构和类或对象之间的关系（如聚合、关联）；对于创建型模式， 除了描述结构型模式需要的信息之外，还需要描述方法创建对象的信息；对于行为 型模式，除了描述结构型模式需要的信息之外，还需要描述方法之间、方法与类之 第二章 CodeMiner 的需求分析和总体架构 - 12 - 间的关系，如方法调用关系、方法返回类型依赖、方法参数类型依赖。在本研究方 法中，设计模式签名提取需要保证设计模式的信息被准确地提取，并将其转换成中 间表示(ASG)。 3、设计模式识别：、设计模式识别： 依照系统源码和设计模式的中间表示设计设计模式识别算法， 由于在本研究方法中，设计模式的识别是基于子图发现和 DFA，在模式识别部分， 需要实现图同构、同构的对应关系、DFA 的定义和实现，并确保识别的设计模式实 例的准确性。 4、识别结果的显示：、识别结果的显示：设计模式识别结果的可视化对系统的反向工程具有重要意义， 可以帮助开发人员更好地理解系统，CodeMiner 需要完整地呈现识别的模式实例， 并提供对发现的设计模式实例的参与者类的定位，而不仅仅是提供发现的设计模式 实例的数目。 5、识别结果的验证：、识别结果的验证：由于需要验证设计模式识别方法的准确性和效果，以及与现有 的研究方法进行比较，CodeMiner 需要提供对识别结果的验证功能，避免人工校验 造成时间的浪费和误判的发生。 2.2.2 非功能性需求分析非功能性需求分析 在考虑系统的功能需求的同时，还需考虑系统的性能、可靠性、可维护性、可扩展 性和对技术、对业务的适应性等非功能性需求。系统的非功能性定义不仅决定产品的质 量，还在很大程度上影响产品的功能需求定义，在软件系统开发实践中非功能性需求却 常常被忽视，CodeMiner 的非功能性需求主要有： 1、友好性：、友好性：CodeMiner 将被实现为 Eclipse 插件，在操作流程与界面设计方面应参 考用户的操作习惯，总体上应达到以下要求：界面友好、实用，流程清晰合理、识 别结果的显示方式直观易懂。 2、可扩展性：、可扩展性：考虑到研究的应用范围的广泛度，可以进一步延伸到软件工程的其他 方面或者其他领域，系统的设计和实现必须兼顾到可扩展性。 3、时间性能：、时间性能：由于本研究需要在多个开源系统上进行多次试验，以评估方法的准确 性和效果。因此在客观条件下，CodeMiner 必须快速地解析系统源码以及在表示系 统源码的抽象语义图具有大量数据的前提下保证较快的模式识别时间。 4、准确性：、准确性：从系统源码中抽取设计模式对于提高软件可理解性和可维护性、软件设 基于子图发现的设计模式识别系统 - 13 - 计重用以及软件重构具有重要意义，误判和模式丢失的发生会使这种作用大打折扣， 因此，CodeMiner 需要保证源码解析、设计模式签名提取、模式识别等过程的准确 性。 2.3CodeMiner 的总体架构的总体架构 CodeMiner 被设计成 Eclipse 插件，通过在 Eclipse 插件上的操作完成系统源码解析和 设计模式实例识别的过程，通过 Eclipse 插件的视图来显示设计模式识别的结果， CodeMiner 的总体结构如下： 图图 2-2: CodeMiner 的总体结构的总体结构 根据图 2-2 所示的 CodeMiner 的总体结构，基于可扩展存储结构的图组件作为最底 层的模块，为源码解析和设计模式识别提供支持，CodeMiner 插件作为 CodeMiner 系统 的应用层, 调用源码解析模块和设计模式识别模块来完成对系统源码的静态解析和对源 码中间表示的设计模式识别。CodeMiner 的功能模块总共分为以下四个部分： 一、一、CodeMiner 插件插件 CodeMiner 是作为一个 Eclipse 插件进行开发的，CodeMiner 插件作为 CodeMiner 的应用层，负责设计模式识别的整个流程的调度，CodeMiner 插件扩展了 第二章 CodeMiner 的需求分析和总体架构 - 14 - 对象上下文菜单中的操作，已实现对 Java 项目进行源码解析和设计模式识别，同时 添加了自己的视图来展示设计模式识别结果和设计模式实例验证结果，而且创建了 一个定制的透视图来组合 CodeMiner 相关的视图和操作。具体结构如下图： 图图 2-3: CodeMiner 插件的结构插件的结构 二、源码解析模块二、源码解析模块 源码解析部分负责系统源码的解析，借助 Eclipse 的 Java 开发工具包(Java Development Toolkit，JDT)将源码解析为 AST，提取类、接口、方法，并分析类和 类、类与方法、方法与方法之间的关系（关联、聚合、泛化、调用等），调用基于 可扩展存储结构的图组件，以提取的源码信息构建 ASG。 三、设计模式识别模块三、设计模式识别模块 CodeMiner 的模式识别部分主要分为三个步骤，导入系统的 ASG、导入设计模 式的 DFA、将 ASG 和 DFA 作为输入，调用子图发现算法，识别设计模式实例。该 模块