利用树遍历快速搜索设计模式(1)
【摘要】
大型软件系统也需要不断修改以保持可用性。当设计被详细地记录下来时，更容易修改。本文提出了一种快速查找已实现到软件系统中设计模式的方法。设计的解决方案，通过将对设计模式的搜索组织当作树进行遍历，大大减少了执行的检查。通过使用设计模式角色自动标记类，令开发人员更容易对大型软件系统进行推理。我们的方法可以提供文档，让开发人员了解每个类所扮演的角色，评估代码的质量，帮助重构和增强软件系统的功能。
关键词：设计模式，源代码分析，软件架构，树遍历。
一、介绍
开发人员发现很难分析大型软件系统的代码。一般来说，有几个问题必须面对：缺乏一个定义良好且文档化的软件架构，或是架构侵蚀、关注点混合。试着去理解系统的软件架构，使用人工检查整个源代码的方法，太过复杂和耗时。此外，这种分析可能会导致开发人员产生一些误解。即使一个软件系统设计得很好，对于大量的代码和不同团队使用的不同设计解决方案来说，分析它仍然是困难的，而且仅通过查看代码很难对其进行评估。
看到软件系统由于新的需求或支持技术而需要更改，理解它们的结构对于保持它们的可用性和维护、改进它们的结构起着基本的作用。通过识别系统中已经实现的设计模式，可以获得关于软件系统的现有设计解决方案和总体架构的相关信息。关于设计模式的任何信息都是对维护人员关于以前开发人员的选择的指示，即设计模式类的角色，揭示了底层的细节。
此外，一旦了解了设计模式，就可以方便地对其类进行修改，从而引入新的功能，关键是如何立即理解包含设计模式类的系统部分。而且，即使知道有些类并不是按照任何设计模式排列的，也是有用的，因为可以对他们进行适当的重构，或者采用先进的技术改进模块化。
与我们的解决方案相比，之前识别设计模式的方法要慢一些。通常是由于它们的假设不准确，或者由于依赖于其他外部工具或人工监督而没有完全自动化。我们的方法包括分析软件系统的Java代码，以发现组成类及其关系，并构建相应的类图。然后，我们通过将图形的某些部分，与设计模式中角色的已知特征相匹配来搜索设计模式；然后将对设计模式有一定作用的候选类组织为树，遍历树以查明是否存在整个设计模式。由于提出的搜索算法，与其他方法相比，设计模式的发现速度更快。在此基础上，根据已知设计模式的模型，提出了一种最精确的匹配方法。
本文的结构如下。第二节概述了我们的方法。第三部分描述了我们的解决方案的细节。第四部分给出了一些实验结果。第五节将我们的解决方案与其他方法进行了比较。最后，第六节给出了我们的结论。
二、方法概述
提出的方法包括两个主要阶段:
（1）Java字节码探索，分析现有的软件系统并提取必要的数据;
（2）通过适当地组织提取的数据以尽可能地减少检查，搜索预先已知的设计模式(如模型)。
探索阶段扫描目标软件系统的Java字节码，以便提取所有类的名称和类之间存在的关系。后者通过仔细处理字节码声明类以及依赖于其他类(如方法调用、变量声明等)中的指令来实现。我们感兴趣的类关系是：继承、使用、调用、实现、方法参数类型、返回类型、覆盖和实例化。这些都是可以与代码单独区分的关系，例如，聚合或组合不能识别。通过提取所有的关系，我们可以构建一个图形，将类表示为节点，将它们的关系表示为边。由于存在不同类型的关系，相应的图边会被相应地标记。在我们的方法中，为了探索系统的字节码，我们使用了计算反射和Javassist库的支持。
至于要找到的设计模式，我们为GoF目录中的每个著名设计模式使用Java实现，类似于软件系统探索，我们为要寻找的每个设计模式构建一个“小”图。然后将这些设计模式图，即模型，存储在一个目录中，以便在搜索过程中使用。此外，新型号的产品在任何时候都可以很容易地储存在我们的产品目录中。
在字节码探索阶段之后，搜索阶段就开始了，目的是将每一个设计模式模型，都在表示整个目标软件系统的图形中找到。
搜索阶段分为几个步骤：
第一步：检查设计模式模型的“小”图的边缘，并将它们与软件系统的“大”图中的节点的边缘进行匹配。这使我们能够找到与设计模式模型的一个角色匹配的、经过检查的、软件系统的类，因为它们与角色规定的其他“周围”类具有所有需要的关系。设计模式模型的每个角色都独立于其他角色进行匹配。
第二步：检查给定角色的类之间的所有关系，是否与所选设计模式模型的关系相对应。如果模型与图关系之间存在完全对应关系，即模型中角色之间的每个关系都存在于图中，那么我们将得出：它是匹配的结论。相反，如果设计模式模型存在一个或多个关系不能有任何对应关系，那么我们就得出：被检查的设计模式不能匹配的结论。在这一步中，为了减少类和设计模式的相应角色之间可能的匹配，我们使用了树。每个树表示一个可能的匹配，每个树级别表示一个类可以具有的角色。在树遍历期间，每个级别的节点作为子节点添加到前一个级别的节点。只有当同一路径中的类之间的所有关系与设计模式角色匹配时，才会出现这种情况。这种算法的细节将在下一节中给出，展示设计选择和优化，目的是在分析大型软件系统时获得快速执行。
【翻译原文】
[1]Stefano Cicciarella,Christian Napoli,Emiliano Tramontana. Searching Design Patterns Fast by Using Tree Traversals[J]. International Journal of Electronics and Telecommunications,2016,61(4).
