UML活动图模型中错误的定位工具毕业论文

单位代码 10006学号 39061622分 类 号 TP311.52毕 业 设 计 (论 文 )UML 活动图模型中错误的定位工具院 （ 系 ） 名 称 计 算 机 学 院专 业 名 称 计 算 机 科 学 与 技 术学 生 姓 名指 导 教 师2013 年 6 月UML活动图模型中错误的定位工具 北京航空航 天大学本科毕业设 计（论文）任务书、毕业设计（论文） 题目：UML 活动图模型中错 误的定位工具。、毕业设计（论文） 使用的原始资料（数据）及设计技术要求：本文中，主要陈述了 自动化测试中，如何实现界面程序的自动化测试，目 前，界面的自动化测试技术还不成熟，相关的资料也 很少，本文中总结了目前主流的几种实现界面元素提 取和控制的方法，其中包括了操作系统的辅助技术， 应用较广的 python，适用性较好的硬件信号模拟，同 时，也提出了一种自动化测试系统的从脚本到日志的 框架结构。、毕业设计（论文） 工作内容：1）Windows 下用 python 的 pywinauto 模块或者 winGUIAuto 类实现界面元素控制。2）基于 msaa（Microsoft Active Accessibility）的句柄获取技术实现 windows 界面元素控制。3）基于 LDTP（The GNU/Linux Desktop (GUI Application) Testing Project）的句柄获取与控制技术实现 linux 界面元素控制。4）脚本格式与规范。5）日志生成技术。、主要参考资料【1】 （美）丘恩（Chun，W.J.）著，宋吉广译， python核心编程， 人民邮电出版社， 2008-7-1【2】Mark Mc Mahon， pywinauto v0.4.1 documentation，2010【3】liurong，pywinauto 自动化框架调研， 2011-5-5【4】Simon Brunning ， winGUIAuto.py， 2003-7-5【5】李伟明 侯春多 等著， C+从入门到精通， 清华大学出版社， 2010-7【6】Rob Sinclair， Microsoft Active Accessibility：体系结构，MSDN， 2004-12-21【7】Dmitri Klementiev， Software Driving Software: Active Accessibility-Compliant Apps Give Programmers New Tools to Manipulate Software ，MSDN，From the April 2000 issue of MSDN Magazine.【8】崔传凯，MS Active Accessibility 接口技术编程尝试， /document/viewdoc/?id=883计算机学院（系）计算机科学与技术专业类 班学生 毕业设计（论文）时间：2013 年 3 月 01 日至 2013 年 5 月 26日答辩时间：2012 年 6 月 4 日成绩：指导教师： 兼职教师或答疑教师（并指出所负责部分）：系（教研室）主任（签字）： 本人声明我声明，本论文及其研究工作是由本人在导师指导下独立完成的，在完成论文时所利用的一切资料均已在参考文献中列出。作者：签字：时间：UML 活动图模型中错误的定位工具学 生：指导教师摘 要随着计算机软件在各个领域的应用以及软件规模的扩大，软件工程思想在软件开发过程中得到了进一步的体现和应用。研究成果表明，软件开发中 70%的错误是在软件工程生命周期中的早期被引入（即在模型设计中引入）；而错误中的 80%只有到了系统开发后期的测试阶段之后才被发现，而错误的修改成本大大增加。随着各种系统和软件的规模与复杂度增加，模型驱动技术被广泛的应用于系统的构建、静态和动态行为刻画与分析等方面。这其中，以面向对象建模为主导思想的统一建模语言（UML）得到了广泛的应用，它提供了多种图形元素，从静态结构和动态行为等多角度及不同层次刻画系统特征和运行环境。本文主要工作和技术内容如下：1) 分析并总结了 UML 模型错误定位所涉及的相关技术和理论知识，深入介绍了有关模型错误检查和调试的相关发展情况以及各自的特点。2) 将基于 C-Kernal 语言的函数内调式的形式化错误定位算法应用到了 UML模型上，并提出了系统整体设计上的逻辑结构框架，将系统分割成为若干功能模块，清晰明了的完成了系统的实现。3) 提出了一种分析 UML 活动图的方式，即通过解析 UML 标准的导出的 XMI格式文件。在 XMI 格式的文件中，定义了很有规律的标签，它们有规律的记录了该活动图的结构等信息。通过使用高级程序语言对 XMI 文件的解析就可以达到解析 UML 活动图结构的目的。同时，对于 UML 图形化部分，可以通过解析 UML 格式文件来实现。UML 格式文件与 XMI 格式文件类似，也是使用扩展标记语言（XML） ，并且其中记录了 UML 活动图中各个元素的大小、颜色、位置等图形化的相关信息，可以利用来构造一个对应的活动图。4) 本文以一种新的方式来看待 UML 活动图，不仅仅将它看做是一个描述业务和活动的工作流程图，而是将它看做是一个顺序执行的程序。通过在程序中将它抽象成数据结构中的图，将它解析成为代码段，从而实现了错误的定位。关键词： UML 活动图，错误定位，XMI 解析，XMLBug locating tool in the UML activity diagram models STUDENTS: AbstractWith computer software in various fields of application as well as the expansion of software, software engineering thought in the software development process has been further reflected and applications. Research shows that 70% of software development errors in the software engineering life cycle is introduced early (ie, incorporated into the design of the model); while only 80% of errors into the system test phase after development of late been discovered and the error modification costs increased significantly.With a variety of systems and software to increase the size and complexity of the model-driven technology is widely used in the construction of the system, the static and dynamic behavior characterization and analysis and other aspects. Among these, the object-oriented modeling of the dominant ideology of the Unified Modeling Language (UML) has been widely used, it offers a variety of graphic elements, from the static structure and dynamic behavior of different angles and describe system characteristics and operational levels environment. This paper work and technical content are as follows:1) analyze and summarize the UML models involved in positioning errors related technical and theoretical knowledge and insight into the model error checking and debugging on relevant developments and their respective characteristics.2) based on the C-Kernal language formalized within a function tuning error localization algorithm applied to the UML model, and presents the overall design of the system logical structure of the framework, the system is divided into several functional modules, clarity of the completion of the system implementation.3) presents a UML activity diagram analysis methods, namely by parsing the UML standard export XMI format. In XMI format file, define a very regular labels, they regularly record the activity diagram the structure and other information. By using advanced programming language for XMI file parsing can achieve parsing UML activity diagram structure purposes. Meanwhile, the UML graphical part, can be resolved to achieve UML format. UML XMI format file format file with a similar, but also the use of Extensible Markup Language (XML), and which records the various elements of UML activity diagram size, color, position, and other graphical information can be used to construct a corresponding activity diagram .4) In this paper, a new way to look at UML activity diagrams, not only will it be seen as a description of the operations and activities of the work flow, but will it be seen as a sequential process. In the program it will be abstracted into a data structure diagram, it would resolve a code segment, enabling the wrong place.Key words: UML activity diagrams, fault location, XMI parsing, XML一、绪论1 研究背景与意义软件工程是研究和应用如何以系统性的、规范化的、可定量的过程化方法去开发和维护软件，以及如何把经过时间考验而证明正确的管理技术和当前能够得到的最好的技术方法结合起来。众所周知，软件工程主要包括了需求获取、项目策划、建模分析设计、编码、测试以及部署交付等过程。研究成果表明，70%的错误是在软件工程生命周期中的早期被引入（即在模型设计中引入）；而错误中的80%只有到了系统开发后期的测试阶段之后才被发现，而错误的修改成本大大增加。惠普、IBM、以及其他组织的研究人员发现，在构建软件模型阶段清除一个错误，其成本仅仅是在开发过程的最后阶段做同样事情的十分之一到百分之一12。因此针对于设计模型的错误检查研究，有着非常重要的意义，可以大大降低错误检查的成本，有效保障软件质量。随着各种系统和软件的规模与复杂度增加，模型驱动技术被广泛的应用于系统的构建、静态和动态行为刻画与分析等方面，模型作为对系统行为的刻画发挥着越来越重要的作用。统一建模语言（UML）是一种面向对象的建模语言，它是运用统一的、标准化的标记和定义实现对软件系统进行面向对象的描述和建模。它作为一种描述能力强大、涵义直观且被工业界广泛使用的可视化建模语言，提供了多种图形元素，从静态结构和动态行为等多角度及不同层次刻画系统特征和运行环境3 。UML 的目标是以面向对象图的方式来描述任何类型的系统，具有很宽的应用领域。其中最常用的是建立软件系统的模型，但它同样可以用于描述非软件领域的系统，如机械系统、企业机构或业务过程，以及处理复杂数据的信息系统、具有实时要求的工业系统或工业过程等。总之，UML 是一个通用的标准建模语言，可以对任何具有静态结构和动态行为的系统进行建模。此外，UML 适用于系统开发过程中从需求规格描述到系统完成后测试的不同阶段。在需求分析阶段，可以用用例来捕获用户需求。通过用例建模，描述对系统感兴趣的外部角色及其对系统（用例）的功能要求。分析阶段主要关心问题域中的主要概念（如抽象、类和对象等）和机制，需要识别这些类以及它们相互间的关系，并用 UML 类图来描述。为实现用例，类之间需要协作，这可以用 UML 动态模型来描述。在分析阶段，只对问题域的对象（现实世界的概念）建模，而不考虑定义软件系统中技术细节的类（如处理用户接口、数据库、通讯和并行性等问题的类） 。这些技术细节将在设计阶段引入，因此设计阶段为构造阶段提供更详细的规格说明。活动图是UML2.0中动态行为建模中的重要模型之一，可以对系统功能过程实现进行刻画，是一种流程刻画的图形建模语言，它结合了Jim Odell 的事件图、SDL(规约和描述语言)状态建模技术、工作流建模以及Petri网等。活动图的应用领域广泛，且可以对于不同层次的过程模型进行刻画，包括对于工作流建模、执行算法建模以及代码层次模型等4。随着活动图在系统建模中的应用越来越多，活动图模型的正确性检测与错误定位也为复杂系统的错误检查和定位提供了一种方式，即利用活动图作为系统功能的过程模型，结合实际观测或者需求期望来判定该模型是否存在错误，如果存在错误，并进一步自动化进行错误定位。选题具有一定的意义。如果能在建模阶段就自动化的查找包括语法和语义的错误，那么我们就可以大量的减少在后期编程阶段或者测试阶段再次发现错误所需要的工作量并减轻修改这些 bug 所需要的精力财力物力。2 研究现状统一建模语言（UML）作为一种描述能力强大、涵义直观且被工业界广泛使用的可视化建模语言，提供了多种图形元素，从静态结构和动态行为等多角度及不同层次刻画系统特征和运行环境。当前针对于UML 错误检查的相关研究主要集中在UML一致性研究、基于模型检查技术的 UML 模型错误检查以及UML测试调试工具。2.1UML 模型的一致性检查UML模型的一致性检查是最常见的错误检查，它包含了语法检查和语义检查等，对于语法检查是将模型看作一组相互关联的元素，通过把元素之间的关系限定到一定模式，防止模型中产生某些类型的矛盾，这类方法的基本特征是以模型的语法结构为基础，定义元素之间的一致性约束。通常利用模型间语法结构等建立一致性约束，进一步执行模型检查。语义检查则通过形式化语义模型，包括进程代数、Petri网、R-演算等理论，实现语义层面一致性的判定。2.2 模型检查针对于UML的模型检查，通常将模型检查的成果应用到 UML错误检查中，通常的方式是将UML模型转化为常用的模型检查工具输入模型，并建立属性检查期望。模型检查是针对于UML模型错误检查中最常见、也是应用最广泛的，通常将UML模型转化为SMV、SPIN 等主流的模型检查工具所支持的中间语言5 ，然后利用模型检查工具，来判定UML模型是否满足指定的性质。模型检查主要用于检查功能属性，例如无死锁性、活性、安全性等，缺点除了状态空间爆炸问题外，对于检查过程的推理过程缺乏直观的刻画，对于度量模型不统一的检验无法有效处理。2.3UML 测试调试工具UML能够允许开发者在一个较高的抽象层次，利用活动图、状态机和顺序图等来对系统行为进行描述。为了进一步便于模型驱动开发，开发者需要增加对于UML模型的调试和测试。UML测试调试工具则是在UML建模环境中，实现针对于模型的虚拟执行环境，加入测试和调试的功能, 常见的工具如IBM在以色列的Haifa研究室提供的 Model debugger，基于Eclipse的代码调试器，提供了相似的视图：调试、变量和断点67。2.4 小结通过以上的总结，我们可以发现，目前主流的几种UML 错误检查的方法都各自存在优缺点。UML模型的一致性检查多用于进行语法的检测；而模型检查主要用于检查功能属性，对于检查过程的推理过程缺乏直观的刻画，对于度量模型不统一的检验无法有效处理；UML测试调试工具则主要是针对于人工的手动调试8 。选题则是主要针对于语义错误的自动化检测和定位，通过对实际运行状态和期望状态的比较来进行进一步的相对精确的错误定位。3 研究内容与解决方案3.1 研究目标众所周知，现在有很多的错误自动检测系统，但是对于错误的定位方面仍然不是很好。我们的主要研究目标是在软件工程的建模阶段能够自动化的发现并定位出模型中所存在的错误，这样我们就能更多的减少测试阶段发现的错误数量，并进一步减少改正错误时所需要花费的代价。而随着面向对象编程的越来越广泛的应用和推广，UML 建模语言也在众多领域有广泛的使用，而这门语言本身也是一种描述能力强、涵义直观的可视化建模语言。因此我们的选题主要是针对于 UML 活动图，通过对活动图的解析、对其中元素和对象的处理，能够自动的检测并定位其中的语义错误以及产生错误的原因，从而在建模阶段就能发现更多的错误，减少后期测试时发现并改正错误的代价。3.2 研究内容3.2.1UML 活动图的处理UML 活动图中有许多的元素和对象包括了：活动、状态、转移（动作流） 、分支与合并、分叉与汇合以及泳道等等。在这里我们主要讨论的是比较简单的活动图（只含有活动、状态、转移、分支与合并） 。接下来需要研究的是怎样读入一个 UML 文件，并怎么样对这个文件进行操作，读取出其中的元素和对象，供下一步的使用。3.2.2 错误定位的算法如果我们要在一个 UML 活动图中进行错误的定位，那么就必须要有一个高效的错误定位算法。目前我们已经有了一个形式化错误定位算法，但是这个算法的提出是针对于所 C-kernel 语言，它是 C 语言的一个子集，这一语言所有变量和常量都是整型的。而我们的研究的对象是 UML 活动图，这其中有很多不同之处，那么我们就需要对读取出来的 UML 活动图元素对象以及错误定位算法进行进一步的修改和转化，从而能够使我们的研究对象适应这个成型的算法。3.3 解决方案首先，对于 UML 活动图的读取，我们可以使用 starUML 的 export 功能将活动图导出成 XMI 格式或者使用可以直接操作 UML 的库。然而 XMI 的优点是使用扩展标记语言（XML） ，为程序员和其它用户提供元数据信息交换的标准方法。XMI 的目的在于帮助使用 UML 以及不同语言和开发工具的程序员彼此交换数据模型。XMI 也可用于交换数据仓库信息。正如我们都知道的，XML 格式的文件中，定义了很有规律的标签，我们可以用高级程序语言（如C+）对 XML 文件进行操作，从而得到了系统的活动图的结构，从而进行下一步的基于 XML 结构化的形式化的文件的操作9 。接着，我们将对象元素使用高级程序语言转换成错误定位算法所需要的格式从而进行下一步的操作。这其中，从 UML 活动图中读取的结构我们可以对应到编程语言中的某些结构，比如：UML 活动图中的活动就可以看成普通的顺序执行的操作语句；UML 活动图中的分支与合并就可以转换成编程语言中的判定、循环等等。最后，对于语义错误的检测和定位，我们将使用课题组提出的错误形式化定位算法。这个算法的提出是针对于所C-kernel 语言，它是C 语言的一个子集，这一语言所有变量和常量都是整型的。所以我们需要将活动图转换成的XMI中的元素的格式更改并对算法进行适当的调整，使双方能够进行匹配，从而能够使用这个成型的定位算法完成错误的定位。4 课题来源课题来源于实验室在软件的自动化调试方面的科学研究。5 论文组织架构本文的核心在于研究、设计及实现 UML 活动图模型中错误的定位工具。首先，分析国内外研究和相关技术的优缺点。接着，设计系统整体框架并详细讨论系统中每一模块的关键技术和核心功能的设计方案与具体实施。最后，展示系统运行成果并致谢。论文组织结构如下：第一章，介绍课题的研究背景及意义，明确本文的研究目标和主要工作内容，并对目前的研究现状进行介绍。第二章，分析系统中所用到的几项主要技术和相关算法。首先介绍使用高级程序设计语言解析 UML 活动图的技术，随后简要介绍一下 C+和 C#编程的知识，最后介绍错误定位的算法。第三章，根据课题研究目标，提出系统的设计原则，并设计系统的整体框架结构。对于每一个部分，详细说明具体的设计思路、数据结构以及实现细节，并介绍每一部分的关键技术。第四章，在各个部分都完成的基础上，展示系统在相应环境下的运行情况。第五章，总结论文的主要工作。二、相关技术和算法本文的主要研究内容是设计并实现 UML 活动图模型中错误的定位工具。本章中将分别针对系统设计和系统实现过程中的相关技术、算法和概念展开介绍。1. UML 活动图的解析UML 活动图是 UML 建模中行为图中的一种，它主要描述系统的动态模型和组成对象间的交互关系，它对于系统的功能建模特别重要，强调对象间的控制流程。1.1XMI 格式文件的解析软件 starUML 的 export 功能将 UML 活动图导出成 XMI 格式或者使用可以直接操作 UML 的库。然而 XMI 的优点是使用扩展 标记语言（XML） ，为程序员和其它用户提供元数据信息交换的标准方法。XMI 的目的在于帮助使用UML 以及不同语言和开发工具的程序员彼此交换数据模型。在 XMI 格式的文件中，定义了很有规律的标签，我们可以用高级程序语言（如 C+）对 XML文件进行操作。在导出的 XMI 文件中，定义了关于一张 UML 活动图整体结构的信息，包括了所有元素的个数、每个元素的类型（活动、转移、选择、开始节点、结束节点等等） 、每个转移的条件以及各个元素之间的关系，比如：活动 A 和哪个转移相连；转移 B 从哪个活动指向哪个活动等等。这些就是我们分析一张 UML 活动图的重要信息，通过对这些信息的提取，可以将一个抽象的活动图整理成一个顺序执行的程序段，从而进行错误的定位。1.2UML 格式文件的解析UML 格式的文件也是我们进行错误定位要处理的一个文件。与 XMI 文件相似，UML 格式的文件也是使用扩展标记语言（ XML）编写的，这就可以通过高级程序语言进行分析了。与 XMI 文件有所不同的是，UML 格式的文件其中记录的信息不是活动图的整体结构，而是关于一张活动图的图形化的信息。其中记录了关于活动图中每一个元素的位置（基于左上角的横纵坐标像素值） 、每一个转移流的直线或折线的位置信息以及每个元素的大小颜色等等。这些信息都是有助于我们后期在图形界面上进行错误定位的操作。对于 XMI 格式和 UML 格式的文件中元素的解析和读取，我们选择了TinyXML 这个基于 C+的 XML 解析器。TinyXML 是一个开源的解析 XML的解析库，能够用于 C+，能够在 Windows 或 Linux 中编译。它简单易用且小巧 玲珑，非常适合存储简单数据，配置文件，并且支持对 XML 的读取和修改。这个解析库的模型通过解析 XML 文件，然后在内存中生成 DOM 模型，从而让我们很方便的遍历这棵 XML 树。DOM 模型即文档对象模型，是将整个文档分成多个元素（如书、章、节、段等），并利用树型结构表示这些元素之间的顺序关系以及嵌套包含关系。从开源中国社区上下载得到 TinyXML 的项目，配置时只需要通过将tinystr.cpp，tinyxml.cpp， tinyxmlerror.cpp，tinyxmlparser.cpp，tinyxml.h ，tinystr.h 这六个文件导入到我们的项目中，就可以调用其中的 API 来对 XML 文件进行读取解析。2. C+和 C#混合开发相关技术本项目采用 C+和 C#混合开发。主要因为 C+语言十分灵活方便，而且是面向对象语言，而 C#在 GUI 开发方面拥有很强的便利性。使用 C#编写系统的图形界面非常方便，它的封装性非常优秀，既可用代码来编写界面也可以直接通过 C#提供的拖拽控件的功能直接编写界面。我们的整体的思路是使用C+来编写后台的操作和解析部分的程序，而使用 C#来编写程序的界面和前台程序，界面部分调用后台中的函数来完成系统的实现。2.1C+编写后台控制和操作在后台部分，使用 C+语言来编写相关的操作和处理程序。主要包括了：使用 TinyXML 对 XMI 文件和 UML 文件的读取，将一个活动图解析成一个顺序执行的程序段并转换为中间链表结构等等。这些部分主要是使用 C+语言来写的，利用了它的面向对象特性，我们可以写出很多封装的很好的自定义类来帮助完成。2.2C#编写前台界面在 GUI 部分，使用 C#语言来完成界面的绘制。这一部分主要是使用 C#的设计界面，利用它的控件拖拽功能来完成绘制。其中利用到了其中的许多小的设计好的控件，比如：Form，Panel，DataGridView，TreeView，ToolTip 等等。它们都是 C#中已经封装好的十分便于使用的小组件，可以让编程人员方便的实现自己的目的。2.3 多项目混合开发的解决方案在 Visual Studio2012 中，我们把整个系统称为是一个解决方案，而这一个解决方案则可能含有多个小的项目，它们要互相调用内部的函数和数据结构，而且这些小的项目可能并不是一种编程语言写成的（如：我们的解决方案中就是 C+和 C#） 。因为这些项目之间存在着相互调用的关系，这样就需要在属性中设置项目依赖项、启动项目以及包含目录等等，来确认互相之间的调用关系，这样在整个系统启动的时候编译器才能找到互相之间的调用关系一步步来编译，才不至于报错。其次，因为 C#和 C+并不是同一种语言，因此在 C#编写的界面中调用到 C+编写的函数的时候就要使用动态链接库（Dynamic Link Library，简写为 dll） 。将 C#中将要调用到的 C+中的函数，用一系列语句和规定封装成动态链接库，在 C#项目中通过使用 DllImport 语句来引入这些函数，从而实现混合项目之间函数的调用。这其中要主要的就是，这些函数的返回值和参数目前只允许是简单的数据类型和数据结构的（比如：int ，char ，char*，bool）否则就会报错。3. 错误定位算法选题的错误定位选择函数内调试形式化的错误定位算法1011，它在UML 活动图中应用的基本思路是：当活动图测试出现了一个失败的测试用例时，根据用户预期的程序输入和输出，从活动图中找出与用户预期矛盾的极小片段，比如：几个活动和转移流组成的一个片段。若此片段仍然较大，则通过不断的与用户交互，让用户标记其中正确的活动、转移，或者让用户进一步给出片段中变量在某些状态下的预期值，利用这些新的信息缩小片段的范围，直到最终定位到活动图中的一个错误。它的大概过程是：通过活动图的执行轨迹，根据用例的输入进行执行，每执行到一个状态（在某一条语句执行完毕后所有的变量的值） ，则用实际状态与期望状态相比较，从而一步步的定位错误的位置。与用户预期矛盾的极小片段的确定方法具体如下：符号执行，记录轨迹：根据失败的测试用例的输入，对程序进行符号执行，记录每个程序在这一输入下的执行轨迹以及各个程序状态。定位方程组生成：根据程序的执行轨迹，从程序中变量的值与预期值不一致的断点处，反向对程序轨迹中的每一个语句生成定位方程组。求解方程，定位错误：通过二分法反向找到使得定位方程组无解的第一个语句，由断点到此语句之间的与断点变元相关的语句构成了一个极小程序片段。用户交互，缩小范围：通常在上述错误隔离过程结束之后，我们得到的是一个程序片段。如果这个程序片段仍然较大，不容易准确定位错误。在这种情况下，需要与用户交互获得更多关于此程序片段中变量的预期值，以便将错误隔离在一个更小的程序片段之中。这时，需要用户再次输入片段中变量在某个状态下的预期值，在此程序片段中再次定位错误所在的程序片段，不断重复这一交互过程，直到得到的程序片段足够的小，能够精确的定位到错误。在用户将此错误修复之后，还需要在修改后的程序上重新运行测试用例，进行回归测试。如果不存在失败的测试用例，表明程序通过了测试，之前的错误已经修复；否则，则说明程序中还存在其他的错误，需要重复整个错误定位过程，一次一个的找到并修复错误。算法执行的活动图如下：互 互bug互 互 互 互 互 互 互 互 互 互 互 互 互 互 互 互 互互 互 互 互 互互 互 互 互 互 互 互 互 互 互 互 互 互 互 互 互 互互 互 互 互 互 互 互 互 互互 互 互 互 互 互 互 互 互互 互 互 互 互 互 互 互 互 ,互 互 互 互 互 互 互 互 互 互 互 互三、系统的设计与实现1.系统开发和运行环境1.1 系统开发环境硬件配置：（1） 主机 CPU： Intel(R) Core(TM)i5-2430M CPU 2.40GHz（2） 内存：4.00GB 软件配置：（1） 操作系统：Windows 7 旗舰版（2） 编译器：Visual Studio 20121.2 系统运行环境硬件配置：（1） 主机 CPU： Intel(R) Core(TM)i5-2430M CPU 2.40GHz（2） 内存：4.00GB软件配置：（1） 操作系统：Windows 72系统整体设计读取解析 X M L分析活动图并转换成中间链表结构X M I 文件 U M L 文件错误定位界面显示存在错误的部分读取解析 XML：这一个模块主要是负责是解析 UML 格式和 XMI 格式的文件。因为这两种格式的文件内部都是使用使用扩展标记语言（XML ）来编写的，所以在这一模块我们就使用 TinyXML 这个基于 C+的 XML 解析器来对这两个格式的文件进行解析，并将整个活动图抽象成一张图，保存在一个类似于邻接矩阵的复杂二维数组中。分析活动图并转换成中间链表结构：这一个模块的输入是基于上一个模块的输出，即读取解析 XML 模块的操作结果。这一部分的操作类似于编译的过程，有词法分析、语法分析、语义分析，只是最后不需要生成目标机代码，只需要生成错误定位算法输入所需要的数据结构即一个链表结构。错误定位：这一模块就是实现了函数内调式的形式化方法这个错误定位算法。具体思路是：当活动图测试出现了一个失败的测试用例时，根据用户预期的程序输入和输出，从活动图中找出与用户预期矛盾的极小片段，比如：几个活动和转移流组成的一个片段。若此片段仍然较大，则通过不断的与用户交互，让用户标记其中正确的活动、转移，或者让用户进一步给出片段中变量在某些状态下的预期值，利用这些新的信息缩小片段的范围，直到最终定位到活动图中的一个错误。界面显示存在错误的部分：这一个模块就是 GUI 部分，主要是使用 C#的设计模式来进行设计的。3.主要数据结构3.1GraphPointclass GraphPointprivate:string Id;string name;string guid;string guid2;int out;int left;int top;string points;string action;GraphType type;string guard;string transitionId;在我们的系统中，我们把一张 UML 活动图看成是一个抽象的图，主要的操作都集中在这张图的邻接矩阵当中。这个二维数组邻接矩阵（Graph）中的每一个节点都是一个 GraphPoint。这个邻接矩阵与传统的一张图的邻接矩阵并不完全相同，对于传统的邻接矩阵，它只是为了表示一张图的节点与节点之间的连接关系，简单化为一个二维整型数组。而在我们这里，我们的邻接矩阵复杂了不少，每一个节点当中都包含了很多属性。属性 Id 表示当前节点的唯一标记符 ID；属性 name 表示该节点的显示出来的名字；属性 guid 和 guid2 表示节点在 UML 格式文件中的标记符；属性 out 表示节点 i 到节点 j 是否有一条边即是否有转移流；属性 top 和 left 是关于该节点的在图形化界面上对于左上角的像素值，该值保存在 UML 格式文件中；属性 points 是也是关于图形化界面的，它主要是关于转移流的，每一个转移流都是由一系列的点构成的，我们把这些点保存在 string 类型的属性 points 之中，以便后期在界面上绘制转移；属性action 是每一个节点当中的操作，是整个图中的重中之重；属性 type 代表了当前节点的类型，它是我们自定义的类型，包括了：START，ACTIVITY ，CHOOSE，END 这四个类型吗，分别代表开始节点，活动节点，选择节点，结束节点；属性 guard 表示转移流的条件；属性transitionId 表示当前转移的 Id。3.2AstNodeclass AstNode : public Nodepublic:AstType at;这是一个父类，它代表了所有抽象语法树叶节点。它的属性 at 代表了这个叶节点的类型，包括了：ASTINT，ASTVAR，ASTBO，ASTUO。分别代表了：整型常数，变量，双目操作符以及弹幕操作符。因此，我们还设立了对应的子类：AstInteger ，AstVariable，AstBinaryOperator 以及AstUnaryOperator。这些子类都继承于父类 AstNode，各自都拥有各自的不同的属性，在后面的抽象语法树中它们构成了叶子节点。3.3FlowNodeclass FlowNode : public Nodepublic :int lineno;int pointNum;FlowType type;AstNode * astTree;FlowNode * next;FlowNode * last;FlowNode *Line;string Id;同 AstNode 类相似，FlowNode 类也是一个父类，它代表了抽象语法树中上层的一些结构体，如：if-else 语句、while 语句、赋值语句等等。pointNum属性代表了该抽象语法树节点所对应的活动图中的活动或者选择在 Graph 中所在的行号，方便我们查找对应；type 属性代表了它的类型，包括了：F_ASSIGN， F_IF， F_WHILE， F_COMP，F_DECLARE。它们分别代表了赋值语句、if-else 语句、 while 循环语句、block 程序块以及声明语句。对应的子类分别是：FlowAssign ，FlowIF，FlowWhile，FlowCompound 以及FlowDeclare。属性 Id 代表了该抽象语法树节点所对应的活动图中的活动或者选择的唯一标示符。属性 next 和 last，是 FlowNode 类型的指针，它们一个代表了本节点之前的节点，另一个代表了本节点之后的节点，共同构成了一个链表。3.4whileListclass whileListpublic:string list100;int size;对于一个 UML 活动图，不通过人眼的直接判断，我们很难区分一个选择节点后面跟的是一个 ifelse 语句还是一个 while 循环。而如果是在一张图中，我们就很好判断，这就如同是在一张图中来判断是否存在一个环路一样，这只需要一个深度优先搜索来完成。类 whileList 就是深度优先搜索一张图之后保存的数据结构。在程序之中，我们定义了一个 whileList 数组 circle，对于每一个是 while 循环的选择节点，我们都把它和从它开始循环一圈的所有节点保存在 list 数组当中，并设置 size 值，方便我们下一步的操作。3.5AstStackclass AstStackpublic:AstNode *exp;在进行活动图解析和生成中间链表结构的过程中，我们需要生成一个类似的抽象语法树，那么每一个语句中变量、常量、表达式等等都可以需要生成一个对应的抽象语法树节点。而在程序中，我们会生成一个 AstStack 的数组astStack，更加方便进行插入操作和前后的遍历查找操作等。3.6FlowStackclass FlowStackpublic:FlowNode *fn;在进行活动图解析和生成中间链表结构的过程中，我们需要生成一个类似的抽象语法树，与 AstStack 不太相同之处是，每一个语句，包括：定义语句、赋值语句、if 语句、while 语句等等都要生成成这种结构的抽象语法树节点。在程序中，对应的我们会生成一个 FlowStack 类型的 flowStack 数组，更加方便进行插入操作和前后的遍历查找操作等。4.读取解析 XMI 格式和 UML 格式文件4.1 读取解析 XMI 格式文件对于 UML 活动图的读取，我们可以使用 starUML 的 export 功能将活动图导出成 XMI 格式。然而 XMI 的优点是使用扩展标记语言（XML ） ，为程序员和其它用户提供元数据信息交换的标准方法。XMI 的目的在于帮助使用 UML以及不同语言和开发工具的程序员彼此交换数据模型。XMI 也可用于交换数据仓库信息。正如我们都知道的，XML 格式的文件中，定义了很有规律的标签，我们可以用高级程序语言（如 C+）对 XML 文件进行操作。对于活动图中的活动：Activity图 4. 1UML 活动图中活动的表示Name 属性表示该活动的名称Outgoing 和 incoming 属性表示从这个活动出去的“转移”的 id 和进入这个活动的“转移 ”的 id。此外，可以在活动中加入操作，它表明是更加详细的步骤，操作是活动中执行的更小的步骤。分别在以下时刻可以产生操作，为某些变量进行赋值：在进入活动时发生的操作,entry；在活动进行时发生的操作,do；在离开活动时发生的操作,exit；这几个标签嵌套于该 ActionState 标签之中：进入活动时发生的操作：在活动进行时发生的操作：在离开活动时发生的操作： Name 属性表示该操作的行为，由用户定义。对于活动图中的转移：图 4. 2UML 活动图中转移的表示Name 属性表示转移的名字。Source 和 target 属性分别表示源动作和目的动作。这其中还可以嵌套一个子标签，用来表示该转移所需要的条件。对于活动图中的分支与合并，它们的排列组合就类似于高级程序语言的条件选择语句和各种循环语句：Activity1Activity2Activity3Dicision这其中属性的意义同上，kind 属性为“branch”表示是分支合并。这一部分的工作我们主要是使用了网络上开源的基于 C+语言的 XML 文件解析器 tinyXML。调用其中的 API，我完成了 XMI 文件的解析，对于 UML活动图生成的 XMI 文件，然后将读取出来的数据存入我们自定义的数据结构Graph 之中。虽然整个 UML 活动图是一个顺序执行的过程，但是我们把它抽象成一个图，我们利用这个图的邻接矩阵来对它进行解析，判断是否存在环路也就是 while 循环等等，并为下一步对它进行解析生成一棵抽象语法树做准备工作。在程序中，所有的操作封装在函数 SolveXMI(string filePath)之中，通过读入 XMI 文件的路径，从而获取这个文件。它的解析过程大概是：首先通过语句 TiXmlDocument doc(filePath.c_str()函数和 doc.LoadFile()函数得到操作 XML文件的句柄，然后获取第一个 element 节点，循环调用 FirstChildElement()函数来获得子节点并循环调用 NextSiblingElement()函数获得同一级的下一个标签。当找到对应的标签项的时候，我们调用 Attribute()来获取属性的值，接着保存到我们的自定义结构当中。这其中，首先取得标签的名字来判断节点的类型，并保存在节点的 type 属性中；接着取得 xmi.id 的属性值，保存在 Id 中；取得name 的属性值，保存在 name 中。下面来保存转移的属性，与上面稍有不同的是，在取得到了 source 和 target 属性值之后，要在邻接矩阵中遍历，找到对应的节点，然后取得 body 属性值，保存在转移的 guard 中；取得 xmi.id 的属性值，保存在 transitionId 中；最后把对应节点的 out 值赋值为 1，代表从节点 i到节点 j 有一条转移流。在邻接矩阵当中，我们只把关于节点本身的属性值（如 Id，name 等）保存在每行的第一个节点中，而关于转移的属性（如guard，points ，out 等）就保存在对应的第 i 行第 j 列的对应节点中。我们解析XMI 文件的顺序如下：子标签子标签子标签子标签子标签子标签子标签子标签子标签