一种基于抽象语法树节点变更抽取的Python代码变更提示方法

摘要

本发明提供一种基于抽象语法树节点变更抽取的Python代码变更提示方法，包括下列步骤：1)获取同一软件不同版本程序的源代码；2)生成两个版本的源程序对应的抽象语法树；3)匹配抽象语法树获取变更节点，结合变更节点上下文信息标记节点变更类型；4)将变更元组聚集为事务，构造训练集；5)利用数据挖掘技术，挖掘变更元组中的关联关系；6)根据挖掘出的关联关系，提示开发人员程序中可能出现变更的位置和可能的变更类型。本发明解决了目前存在的缺乏针对Python语言的软件演化分析、无法提示可能的代码变更类型等问题，进而指导软件生命周期的管理，提高软件演化的可控性，从而能更好地控制软件产品的质量。

说明书

技术领域

本发明属于计算机技术领域，尤其是软件演化分析领域。本发明提供了一种面向Python 语言的、基于程序抽象语法树节点变更抽取的代码变更提示方法，用于在Python软件演化过 程中为程序变更提供辅助信息。

背景技术

软件在其生命周期中一直在发生演化，从错误修正到增加功能等，对软件演化进行分析 可以揭示软件发展的基本规律，对软件生命周期的管理提供指导性意见，以达到提高软件质 量、开发可靠性软件的目的。而软件演化分析中的一个关键问题，就是识别程序不同版本间 的变更，挖掘演化信息中的关联代码和关联变更类型，为软件演化过程提供变更辅助信息。

目前，软件演化信息主要源于以文件或者项目为基本单元来记录软件变化历史的软件配 置管理系统、错误报告系统等CASE工具，这些工具大多使用代码行的增加或删除来描述某 一个变化，而与类或函数等特定的源代码实体无关。因此，当前对程序演化分析的研究主要 集中在代码行数、模块数量、发行包大小、宏定义数量等方面。这些数据能够在宏观上揭示 程序的演化过程，通过对它们的研究，已经得到了包括持续演化、复杂度增加、自我规范等 八条基本原则。但由于这些版本信息系统并不存储结构化的变更信息，因而对软件演化的分 析无法深入到函数实体或语句实体级别。例如，无法识别“if语句的else分支中插入了一个 函数调用”这类变化，而这类变更信息对于软件演化分析而言恰恰十分重要。

软件演化信息包含了软件变更历史等信息，一直是学术界的研究热点。Gall等人使用版 本发行信息来识别模块间的耦合关系，并通过分析这种耦合关系发现可能的软件可维护功能 点，但这种方法以模块为单位，分析粒度较粗；为了发现细粒度代码结构间的耦合关系， ThomasZimmermann等人对代码文件进行语法分析，将语法实体与代码行相关联，该方法能 在一定程度上预测程序可能发生变更的位置，但其没有对变更进行分类，无法对可能的变更 类型提出建议；而在程序变更类型分类方面，BeatFluri等人提出了一种源代码变化分类方法， 该方法主要针对Java语言，从类和方法两个角度对变更进行分类。Python虽然也是一种面向 对象的程序设计语言，但其与Java仍有一定区别，如类本身也是对象等，故BeatFluri等人 针对Java提出的源代码变化分类学，不完全适用于Python。Python语言第一个公开发行版本 发行于1991年，诞生时间较短，目前学术界针对Python语言的研究较少，但Python自诞生 以来，已经成为最受欢迎的程序设计语言之一，故对Python程序变更信息进行分析，具有一 定价值。

总的来说，传统的软件变更历史研究方法存在如下缺点：1、仅仅依赖CVS等版本控制 系统提供的变更信息，变更只与代码行的增删相关，而与类或函数等代码实体无关；2、分析 粒度较粗，鲜有方法能分析函数级别的变更，缺乏深入到源代码语句级的分析方法；3、没有 对变更进行分类，仅能提示变更可能发生的位置，无法提示可能的变更类型；4、大多数方法 的研究对象为Java/C++等，针对Python语言的研究成果较少。

发明内容

本发明提供了一种面向Python语言的、基于程序抽象语法树节点变更抽取的代码变更提 示方法，该方法通过匹配源程序的抽象语法树表示，结合基本树编辑操作(插入、删除和更新)， 确定程序中每一处的变更类型，使用成熟的数据挖掘技术从变更信息中挖掘关联规则，根据 关联规则预测程序中可能出现变更的位置和可能的变更类型，从而对程序变更提出建议。本 发明旨在解决目前存在的缺乏针对Python语言的软件演化分析、无法提示可能的代码变更类 型等问题，进而指导软件生命周期的管理，提高软件演化的可控性，从而能更好地控制软件 产品的质量。

为达成上述目的，本发明提出一种基于抽象语法树节点变更抽取的Python代码变更提示 方法。方法包括下列步骤：

1)获取同一软件不同版本程序的源代码；

2)生成两个版本的源程序代码对应的抽象语法树；

3)匹配抽象语法树获取变更节点，结合变更节点上下文信息标记节点变更类型；

4)将变更元组聚集为事务，构造训练集；

5)利用FP-growth算法，挖掘变更元组中的频繁项集，生成关联规则；

6)根据挖掘出的关联代码和关联变更类型，提示开发人员程序中可能出现变更的位置和 可能的变更类型。

进一步，其中上述步骤1)的具体步骤如下：

步骤1)-1：起始状态；

步骤1)-2：根据文件名和版本号，从软件版本控制系统中获取同一软件的两个不同版本 的源程序；

步骤1)-3：软件不同版本源程序采集完毕。

进一步，其中上述步骤2)的具体步骤如下：

步骤2)-1：起始状态；

步骤2)-2：对同一软件的两个不同版本的源程序进行词法分析和语法分析，利用Python 标准库中的ast模块生成两个版本程序对应的抽象语法树；

步骤2)-3：根据Python标准库中定义的抽象语法，为抽象语法树中的每个节点设置label 和value，并设置节点标识符。label表示节点的类型，如函数调用；value用于表示节点的内 容，中间节点的value依赖于其label，如if控制语句的value为其条件表达式，叶子节点的 value即语句的文本表示，如函数调用的具体内容等；节点标识符id用于唯一标识节点；

步骤2)-4：两个不同版本程序对应的抽象语法树生成完毕。

进一步，其中上述步骤3)的具体步骤如下：

步骤3)-1：起始状态；

步骤3)-2：后序遍历抽象语法树，对叶子节点及中间节点采用不同的算法进行匹配；

步骤3)-3：对于发生变更的节点，获取该节点自身及其父节点的label；

步骤3)-4：分析对变更节点执行的基本树编辑操作，标记节点的变更类型；

步骤3)-5：对于每一个发生变更的节点，用元组δ＝(节点标识符，变更类型)记录其变 更情况；

步骤3)-6：变更节点信息收集完毕。

进一步，其中上述步骤4)的具体步骤如下：

步骤4)-1：起始状态；

步骤4)-2：元组δ＝(节点标识符，变更类型)记录了程序中的变更信息，将已获得的记 录两个版本间变更信息的元组序列C＝{δ₁，δ₂，…，δ_n}聚集为一个事务Δ；

步骤4)-3：获取同一Python程序各个版本间的变更，得到事务集合T＝{Δ₁，Δ₂，…，Δ_n}， 保存在数据库中；

步骤4)-4：扫描数据库，一次变更产生的事务作为一条训练数据，构造训练集a；

步骤4)-5：重复上述步骤，获取多个Python程序的训练集{a₁，a₂，…，a_n}，对于a_i中的每 条训练数据，抽取其中包含的变更类型信息，得到序列C′＝{变更类型1，变更类型2，…， 变更类型n}，将序列C′聚集为事务Δ′，利用事务集合T′＝{Δ′₁，Δ′₂，…，Δ′_n}构造新的训练数据集 b：

步骤4)-6：训练集构造完毕。

进一步，其中上述步骤5)的具体步骤如下：

步骤5)-1：起始状态；

步骤5)-2：利用训练集a构造FP树，挖掘生成训练集a的Python程序中，变更元组 δ＝(节点标识符，变更类型)间的关联关系；

步骤5)-3：利用训练数据集b构造FP树，挖掘变更类型间的关联关系，即哪两种变更 类型通常一起发生；

步骤5)-4：变更信息间的关联关系挖掘完毕。

进一步，其中上述步骤6)的具体步骤如下：

步骤6)-1：起始状态；

步骤6)-2：对于变更历史信息包含在训练样本中的待测Python程序，当某个节点发生 变更时，根据挖掘出的变更元组δ＝(节点标识符，变更类型)间的关联关系，提示开发人员与 此变更相关的关联变更节点和关联变更类型；

步骤6)-3：对于变更历史信息未包含在训练样本中的待测Python程序，当某个节点发 生变更时，根据挖掘出的变更模式之间的关联关系，提示开发人员与此变更相关的关联变更 类型；

步骤6)-4：代码变更提示完毕。

本发明基于抽象语法树匹配来抽取同一程序两个版本间的变更，使得变更识别粒度深入 到基本语句级；在识别变更节点后，获取其上下文信息，并结合对变更节点执行的基本树编 辑操作，标记节点的变更类型，实现代码关联变更类型提示；采用FP-growth算法挖掘变更元 组集合中的频繁项集，生成关联规则，以此提示代码变更，提高了软件演化的可控性，有利 于开发出高质量的软件产品。

附图说明

图1为本发明实施例的一种基于抽象语法树节点变更抽取的Python代码变更提示方法的 总体架构图。

图2为本发明实施例的一种基于抽象语法树节点变更抽取的Python代码变更提示方法的 流程图。

图3为一个条件控制结构可能的抽象语法树示意图。

具体实施方式

本发明方法首先通过CVS等软件版本控制系统，收集了同一Python软件两个不同版本 程序的源代码；接着对两个版本源程序进行词法分析和语法分析，生成对应的抽象语法树； 然后匹配两棵抽象语法树，寻找发生变更的节点并获取其上下文信息，结合对变更节点执行 的基本树编辑操作，标记节点的变更类型，并利用元组δ＝(节点标识符，变更类型)记录节点 的变更情况；最后，将一次提交产生的变更元组序列聚集为事务，构造训练集a、b，采用FP- growth算法，挖掘变更元组中的频繁项集，生成相应的关联规则，以此识别程序中的关联代 码块和关联的变更类型，从而在程序演化过程中辅助开发人员实施变更。

为了更好地说明本发明的技术内容，特结合所附图式作如下说明。

本发明的总体架构图如图1所示，流程图如图2所示。本发明提出的一种基于抽象语法 树节点变更抽取的Python代码变更提示方法，包括下列6个步骤：

步骤1：获取同一软件不同版本程序的源代码。CVS等软件版本控制系统中保存了一个 程序所有版本的提交，根据文件名和版本号从软件版本控制系统中获取同一Python软件不同 版本程序的源代码。

步骤2：生成两个版本程序的源代码对应的抽象语法树。对步骤1中获取的两个不同版 本的源程序代码进行词法分析和语法分析，利用Python标准库中的ast模块生成抽象语法树。 在抽象语法树中，每个源代码实体对应一棵子语法树或一个叶子节点。为了更好地对节点变 更进行分类，我们根据Python标准库中定义的抽象语法，为抽象语法树中的每个节点设置 label和value，同时设置节点标识符。对于每个实体节点x，l(x)为节点的label，表示节点的 类型，如函数调用；v(x)为节点的value，表示节点的内容，中间节点的value依赖于其label， 如if控制语句的value为其条件表达式，叶子节点的value即语句的文本表示，如函数调用的 具体内容等；节点标识符id用于唯一标识节点；图3为一个条件控制结构可能的抽象语法树。

步骤3：匹配抽象语法树获取变更节点，结合变更节点上下文信息标记节点变更类型；源 代码在步骤2中被转化为抽象语法树，因此源代码的变更操作对应了对抽象语法树节点执行 的基本树编辑操作，包括插入、删除和更新。后序遍历步骤2中生成的两棵抽象语法树，依 次匹配各个对应节点，寻找其中发生变更的节点，获取变更节点自身及其父节点的label，结 合对变更节点执行的基本树编辑操作，标记节点的变更类型；对于每一个发生变更的节点， 用元组δ＝(节点标识符，变更类型)记录其变更情况；

匹配两棵抽象语法树时，由于叶子节点和中间节点代表不同的代码结构，故采用不同的 匹配算法。对于两个叶子节点，当且仅当label相同且value的相似度大于阈值f时，才认为两 个节点匹配；否则匹配失败，记录对该节点执行的基本树编辑操作类型。叶子节点匹配算法 如下：

其中，x、y为两个叶子节点；l(x)、l(y)为节点的label；v(x)、v(y)为节点的value； sim_2g(v(x)，v(y))为节点value的相似性度量，通过对比LevenshteinDistance等字符串相似性 度量方法，本发明采用2-Grams作为字符串的相似性度量，该方法对字符顺序的改变有较高 的鲁棒性；f为设定的阈值，建议大小为f＝0.6，也可由用户根据经验自行确定。

中间节点可以看作子树的根节点，对中间节点进行匹配时，计算以该中间节点为根的子 树中匹配成功的叶子节点所占的比例及中间节点value的相似度。中间节点匹配算法如下：

其中，|x|表示以节点x为根节点的子树(以下简称子树x)中包含的叶子节点数； common(x，y)＝{(p，q)∈M|p是子树x的叶子节点，q是子树y的叶子节点，M是匹配成功的 叶子节点集合}；t为子树匹配的阈值，其大小随着子树规模动态调整，建议为：n＞4时，t＝ 0.6，n≤4时，t＝0.4，用户也可根据经验自行确定(n为子树包含的叶子节点数)；其余符号 表示含义与match_leaf(x，y)相同。

匹配抽象语法树获取变更节点后，分析对变更节点执行的基本树编辑操作，结合变更节 点的上下文信息，标记节点的变更类型。例如，抽象语法树中一个label为class_name的节点 发生了“更新”操作，说明该变更操作更新了某个类的名称，对应的变更类型为 CLASS_RENAMING；一个label为alternative_part的节点发生了“删除”操作，说明程序中 删除了某个if语句的else分支，对应的变更类型为ALTERNATIVE_PART_DELETE。

对于某些类型为STATEMENT_INSERT或STATEMENT_DELETE等的变更，可以通过 向上获取变更节点父节点的label来标记代码的变更类型。例如，某次变更删除了if控制结构 的else语句块中的某条return语句，变更节点的label为return_statement，父节点label为 alternative_part，所以可识别细粒度的代码变更类型为RETRUN_STATEMENT_DELETE_IN_ ALTERNATIVE_PART。

步骤4：将变更元组聚集为事务，生成训练集。元组δ＝(节点标识符，变更类型)记录了 程序中的变更信息，将记录两个版本间变更情况的元组序列C＝{δ₁，δ₂，…，δ_n}聚集为一个事务 Δ，保存在数据库中。每次版本更新可视为程序的一次变更提交，将一次变更产生的事务作为 一条训练数据。获取同一Python程序多个版本间的变更，得到事务集合T＝{Δ₁，Δ₂，…，Δ_n}， 构造训练集a。重复上述步骤，获取多个Python程序的训练集{a₁，a₂，…，a_n}，抽取其中每条 训练数据包含的变更类型信息，得到记录一次变更提交的变更类型信息的序列C′＝{ 变更类型1，变更类型2，…，变更类型n}，作为一条新的训练数据，即将任意程序一次提交产生 的变更事务作为一条训练数据，构造新的训练数据集b。

步骤5：利用数据挖掘技术，挖掘变更元组中的关联关系。扫描训练集a和b，采用FP- growth算法挖掘变更元组中的频繁项集，根据频繁项集生成关联规则。关联规则是形如 B的蕴含式，其中I＝{I₁，I₂，…，I_m}是项的集合，并且

对于训练集a，构造FP树，挖掘生成训练集a的特定Python程序中，变更元组间的关联 关系，例如(节点标识符a，变更类型1)(节点标识符b，变更类型2)；对于训练集b，构 造FP树，挖掘变更类型间的关联关系，即哪两种变更类型通常一起发生，例如变更类型1变更类型2。

发现频繁项集常用的算法有Apriori算法和FP-growth算法，Apriori算法需要产生大量的 候选项集，并需要重复扫描整个数据库来检查该候选集合，开销太大。FP-growth算法既可以 挖掘全部频繁项集又无须这种代价昂贵的候选产生过程，性能显著优于Apriori算法，故本发 明采用FP-growth算法挖掘元组集合中的频繁项集。找出频繁项集后，直接由它们产生满足 最小支持度和最小置信度的强关联规则。

对于置信度confidence(AB)可以用如下公式计算：

$\mathrm{confidene}(A\Rightarrow B)=P\left(A\right|B)=\frac{\mathrm{support}\_\mathrm{count}(A\cup B)}{\mathrm{support}\_\mathrm{count}\left(A\right)}$

条件概率P(A|B)用项集的支持度计数表示，其中，support_count(A∪B)是包含项集A∪ B的事务数，而support_count(A)是包含项集A的事务数。根据该式，关联规则可以产生如 下：

●对于每个频繁项集l，产生l的所有非空子集；

●对于l的每个非空子集，如果confidence(s(l-s))≥min_conf，则输出规则s

(l-s)。其中，min_conf是最小置信度阈值。

步骤6：根据挖掘出的关联代码和关联变更类型，提示开发人员程序中可能出现变更的 位置和可能的变更类型。对于变更历史信息包含在训练样本中的待测Python程序，根据挖掘 出的变更元组间的关联关系，当程序发生新的变更时，提示与此变更相关联的可能的变更位 置及可能的变更类型；对于变更历史信息未包含在训练样本中的待测Python程序，根据挖掘 出的变更类型之间的关联关系，当程序发生新的变更时，提示与此变更相关联的可能的变更 类型。

例如，a)将一个Python程序的多次提交产生的事务集合作为训练集，通过FP-growth算 法挖掘出如下关联规则：(节点标识符a，变更类型1)(节点标识符b，变更类型2)。则对 于该程序(即变更历史信息包含在训练样本中的待测Python程序)的下一次修改，当程序员对 节点a进行了类型1修改时，提示其对关联节点b进行类型2的修改；b)将任意Python程 序的任意次提交产生的事务集合作为训练集，通过FP-growth算法挖掘出如下关联规则： 变更类型1变更类型2。对于一个全新的未知Python程序(即变更历史信息未包含在训练 样本中的待测Python程序)，当程序员进行了类型1修改后，提示其进行类型2修改。

综上所述，本发明提供了一种面向Python语言的、基于抽象语法树节点变更抽取的代码 变更提示方法，解决了目前存在的缺乏针对Python语言的软件演化分析、无法提示代码变更 类型等问题，提高了软件演化的可控性，从而能更好地控制软件产品的质量。