论文部分内容阅读
在计算机技术日益普及的现代社会中，软件系统中流程比比皆是，形式覆盖程序流程、办公工作流、业务流程以及服务集成等。随着建设流程的组件数量的快速增长和流程逻辑复杂性的提升，手工设计并调整流程变得越来越困难、费时、易错，甚至有时不切实际。这种需求催生了不同研究领域中的相关技术，如应用程序编程接口(API，Application Programming Interface)自动推荐和迁移、自动服务选择和组合以及Mashup混搭自动生成等技术。尽管这些技术产生的背景各异，它们却具有相似的目标:从海量的构件中搜索出满足给定需求的组合流程。 在典型的API自动推荐中，类似的问题是以对象实例化查询作为给定需求，类库中的API方法作为基本组件，组合生成API方法调用序列这样的程序流程。本文从API自动推荐这一领域入手，对上述流程组合问题进行了理论研究和图论问题抽象，并从图论的角度提出了通用算法。当前，针对此类需求的API自动推荐工具存在若干缺陷，主要表现为:(1)满足需求的方法调用序列常呈现为有向无环图(DAG，Directed AcyclicGraph)的形式，而不是一个简单的方法链条。传统方法基于经典图建模问题，而经典图上的可达性定义及其最短路径算法不能反映DAG的特征，因此无法保证推荐结果具有较高的准确率和查全率;(2)当软件类库演化时，已推荐出的方法调用序列常因API方法重构和软件架构调整而无法编译，需要进行改写以适应新的类库环境。目前，相关工作无法同时保证改写后的方法调用序列具有较高的准确率和代码重用率，难以提升开发人员的编程效率;(3)尚缺少对流程问题统一的理论抽象以及在此理论抽象基础上的通用算法，相关工作中的问题抽象及其算法难以推广，应用前景有限。本文针对上述问题展开了一系列研究，主要的工作和贡献如下: 1.提出标记图及其有向无环图(DAG)问题，为API自动推荐的研究工作奠定了坚实的理论基础。 为反映方法调用序列（流程）的本质特征，本文提出一种新的扩展图模型—标记图(Tagged Graph)。标记图包含节点、权值、边及其标记(Tag)，基于该图我们定义了新的可达性使图模型能够刻画API方法的多个输入参数类型构成的前置条件(preconditions)以及DAG的组合逻辑。在分析API自动推荐和迁移形式化问题的基础上，研究提出用来支持更广泛意义的流程推荐问题的新的图论抽象—基于标记图的新问题:最优DAG问题，为后续的研究内容奠定基础。同时，我们研究分析了最优DAG问题和最短问题的异同，提出了最优DAG问题的其它两个变形问题:TopK DAG问题和动态DAG问题，用于API自动推荐和迁移。从应用的角度来看，新图论问题的研究成果对于基于SOA的业务流程管理、供应链管理、应用集成等应用领域中的软件/服务组合流程建模、正确性校验、运行时的性能优化等都具有显著的应用价值。 2.提出了基于标记图的Top K DAG搜索算法，以推荐满足对象实例化查询请求的方法调用序列。 借助标记图模型的结构及可达性质，提出了新的Top K DAG问题来建模方法调用序列的查询问题，并提出了关键路径松弛算法及DAG子图排序方法，指导开发人员选择正确结果。通过一系列对比实验对所提出的方法进行了系统化验证，实验结果表明，采用Top K DAG搜索算法的系统—APISynth获得了更高的查全率和准确率。 3.提出了基于标记图的动态DAG搜索算法，自动迁移因软件类库演化而失效的方法调用序列。 动态DAG搜索算法将动态变化的API，如新增的API、删除的API、接口变化的API以及服务质量(QoS，Quality of Service)变化的API映射为标记图中的变化节点。当软件类库演化时，该算法能高效的识别出标记图中那些受到变化API影响的节点，并且只替换失效DAG形式的方法调用序列中受到影响的节点以保留大多数未受影响的节点。我们在公开可获得的数据集，如Eclipse3.6和Eclipse4.4涉及的相关插件类库上对方法进行了实验评估。结果显示，采用动态DAG搜索算法的MISKeeper可以正确改写和迁移失效的方法调用序列，同时当开发人员使用我们的迁移方案时，能够保证较高的代码重用率，以提升其编程效率。