1、 本 科 毕 业 论 文 基于子图发现的设计模式识别 系统 CodeMiner 插件和源码解析模块 的设计与实现 Design Pattern Detecting System by Subgraph Discovery The Design and Implementation of CodeMiner Plug-in and Code Analysis Module 姓 名： 学 号： 学 院：软件学院 系：软件工程 专 业：软件工程 年 级： 指导教师： 年 月 摘 要 现代软件工业已经广泛地应用设计模式来重用成功的设计实践和提高软件系统的质量，然而受制于软件系统的规模和设计文档的缺失，
2、开发人员无法直观地理解现有软件系统中应用的设计模式，从源码中发现设计模式实例对于提高软件可理解性和可维护性、软件设计重用以及软件重构具 有重要意义 。 为了便于在实际应用中理解、选择和实践设计模式，设计模式的特征通常以非形式化的方式描述，在进行设计模式识别时需要对其进行形式化的表示，已有的研究中采用不同的中间表示来描述设计模式和系统源码以及提出不同的算法来进行设计模式识别。本文在比较目前已有的设计模式发现方法的基础上，进一步提出了一种新的设计模式识别方法。 本文提出了一种基于子图发现和有限自动机的设计模式识别方法，将抽象语义图作为系统源码和设计模式签名的中间表示，将在系统源码中发现设计模式实例
3、的问题转化成在非连通图中发现同构子图的问题。设计模 式签名描述了设计模式的结构和行为特征，并转换成 确定性有限自动机 ，有限自动机的终态代表着特定的设计模式。子图发现算法采用有限自动机来引导设计模式候选实例的产生，从而缩小搜索空间，提高了算法效率。 另外，本文实现了 Eclipse 插件 CodeMiner 来支持所提出的设计模式识别方法，采用 Eclipse JDT(Java Development Toolkit)对目标系统的源码进行解析， 从源码中提取的信息构建抽象语义图， 通过在 CodeMiner 上对 3 个开源项目进行实验，并将实验结果与现有的相关研究的实验结果进行比较 ，在可识
4、别的设计模式种类和识别的模式实例准确性上有明显的优势，表明本文提出的 基于子图发现的设计模式识别方法具有较高的应用价值。 关键词 ： 设计模式 ； 抽象语法树 ； 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 ofte
5、n 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 un
6、derstand 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 in
7、stances. 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
8、 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
9、 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 evaluati
10、on 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.
11、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.1 CodeMiner 插件 .21 3.2 源码解析 .26 3.3 设计模式签名 .30
12、 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.2 CodeMiner 插件项目的整体实现 .46 4.3 CodeMiner 插件相关扩展点的实现 .48 4.3.1 CodeMiner 插件操作扩展点的实现 .49 4.3.2 CodeMiner 插件视图扩展点的实现 .51 4.3.3
13、 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: Introduction .1 1.1 Background and Significance
14、 . 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 CodeMiner .6 2.1 Comparative Study on Design Pattern Mining Techniques . 6 2.1.1 Pattern Aspects Checked. 6 2.1.2 Intermediate
15、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 Architecture .
16、14 2.4.2 The Theory of Code Analysis Using Eclipse JDT .17 2.5 Summary.20 Chapter 3: Design of CodeMiner . 21 3.1 CodeMiner Plug-in .21 3.2 Source Code Analysis .26 3.3 Design Pattern Signature .30 3.3.1 Structural Design Patterns .31 3.3.2 Creational Design Patterns .33 3.3.3 Behavioral Design Patt
17、erns.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 CodeMiner. 45 4.1 The Structure of CodeMiner Plug-in Project .45 4.2 Overall Implemention of CodeMi
18、ner Plug-in.46 4.3 Implements of Extensions in CodeMiner Plug-in.48 4.3.1 Object Action Extension .49 4.3.2 View Extension .51 4.3.3 Perspective Extension .53 4.4 Summary .55 Chapter 5: Experimental Results . 56 5.1 Introduction of Experimental Datas.56 5.1.1 JUnit.56 5.1.2 JHotDraw .56 5.1.3 JRefac
19、tory .56 5.2 Evaluation Results.57 5.2.1 Detected Instances of Design Patterns.57 5.2.2 Modified Design Patterns .61 5.3 Summary .63 Chapter 6: Conclusions and Future Works. 64 References . 66 Acknowledgements . 68 第一章 绪 论 - 1 - 第一章 绪论 设计模式是面向对象设计的一个高级抽象，是针对重复发生的软件问题的标准解决方案。现代软件工业已经广泛地应用设计模式 来重用成功的设
20、计实践和提高软件系统的质量，然而 由于 软件系统的规模和设计文档的缺失， 导致软件系统的理解和维护也变得越来越困难，因此 从现有的系统源码中抽取设计模式成为许多研究领域的关键课题 。这里 将对目前的研究现状以及存在的问题等进行阐述，最后对本文研究内容以及本文结构安排等进行总体阐述。 1.1 研究 背景及选题意义 由于现在的软件项目大都包含数目众多的组件，其结构变得相当复杂和混乱，从而不利于软件系统的 维护和改进。在软件系统的整个生命周期中，软件维护是十分重要和复杂的阶段，可以占据整个投入的 50%-70%，程序理解在软件维护阶段起着重要的作用，尤其当程序结构较复杂，而且相关的文档与系统不同步。
21、软件工程数据，如代码、代码的修改历史、执行路径以及错误报告等，蕴含着大量与项目管理、软件平台技术有关的信息和知识。如果可以从上述大量的数据中挖掘出潜在的具有高度价值的信息和知识，将更好地进行项目管理，生产出高质量的代码。 设计模式是软件设计中的一些普遍设计问题的解决方案，可以用统一的格式加以描述，主要有：意图、动机、 适用性、结构、参与者、协作、实现细节和代码示例等 .上述模板详细地说明了设计问题以及如何用模式中的类和对象来解决问题的特定情景 1，记录了设计产生的决定过程、选择过程和权衡过程，指导开发人员进行成功的系统设计和实现。设计模式已被现代软件业广泛采用以复用成功的设计和体系结构 以 提高软件系统的质量。 在许多大型软件项目中，设计文档经常缺失，即使设计文档可用，也可能随着系统的改变和迁移而变得过时 ，很多时候 ，开发人员受到上市时间的影响，没有对他们的软件进行充分的文档化，这些情况
