Domain Knowledge Matters: Improving Prompts with Fix Templates for Repairing Python Type Errors

Yun Peng1 , Shuzheng Gao1, Cuiyun Gao2,* , Yintong Huo1, Micheal R. Lyu1

1The Chinese University of Hong Kong,Hong Kong, China,

2Harbin Institute of Technology Shenzhen, China

引用

Yun Peng, Shuzheng Gao, Cuiyun Gao, Yintong Huo, and Michael R. Lyu. Domain Knowledge Matters: Improving Prompts with Fix Templates for Repairing Python Type Errors. [Preprint]. 2023.

论文：https://arxiv.org/abs/2306.01394

摘要

如何利用领域知识自动改进提示以修复类型错误是一个具有挑战性但尚未充分探索的问题。我们提出了TypeFix，一种新颖的基于提示的方法，结合修复模板来修复Python类型错误。TypeFix首先通过一种新颖的层次聚类算法挖掘出通用的修复模板。这些识别出的修复模板指示了现有类型错误修复的常见编辑模式和上下文。然后，TypeFix通过将通用修复模板作为领域知识，为预训练的代码模型生成代码提示。

1 引言

近年来，Python在大多数人工智能和数据科学应用中得到了广泛应用，因此变得极为流行。Python采用动态类型系统，其中变量的类型仅在运行时确定。然而，问题在于，更多的类型错误会在运行时发生，威胁到Python应用程序的可靠性。近年来，基于学习的自动程序修复（APR）方法变得相当流行且强大，因为它们不依赖于特定特征，并且能够自动学习从现有错误修复中生成补丁，而无需明确定义合成规则。在基于学习的方法中，过去通常使用基于神经机器翻译（NMT）的方法，将错误代码行翻译成正确的代码行。最近，有人提出了首个基于提示的APR方法，名为AlphaRepair，并取得了最佳性能。然而，由于类型错误的级别不同和类型错误修复模式的多样性，自动将提示与领域知识相结合是一项挑战。

为了应对上述挑战，我们提出了TypeFix，一个基于提示的领域感知方法来修复类型错误。我们的贡献如下：

首个领域感知的基于提示的Python类型错误修复方法。创新的修复模板设计与层次聚类方法。广泛的实验验证与高覆盖率的修复模板。

2 方法

TypeFix包含两个主要阶段：模板挖掘阶段和补丁生成阶段，其概述如图1所示。

图 1：TypeFix的概览

2.1 模板挖掘阶段

模板挖掘阶段主要包含两个阶段：修复解析和修复模板挖掘。修复解析阶段旨在将类型错误的修复转化为特定的修复模板，而修复模板挖掘阶段则通过提出的层次聚类算法，将解析出的特定修复模板抽象并合并为通用的修复模板。

2.1.1 修复模板的定义

我们将修复模板定义为三个部分的组合：修复模式、内部上下文和外部上下文。这三个部分都基于下面定义的模板树来表示。

定义 2.1.1.1（模板树）

模板树是一个树形结构（N,E,rt），其中 N是节点集合，E是边集合，rt ∈ N 是根节点。

我们基于 Python 的抽象语法树（AST）来定义模板树。在保持原始 AST 节点类型 t的同时，我们通过将所有原始 AST 节点类型和属性类型重新分类为八个基类型来添加一个基类型 bt。

定义 2.1.1.2（修复模式）

修复模式是一个映射B_Tree → A_Tree，其中B_Tree 是错误代码的模板树，而 A_tree 是修复后代码的模板树。

定义 2.1.1.3（内部上下文）

内部上下文是一个对 (IC_Tree, rn)，其中 IC_Tree 是包含修复模式的最深语句的模板树，而rn 是一个映射 n → (br , ar)，其中 br 和 ar 是边关系，n ∈ IC_Tree.N。这个映射指示了从 B_Tree（错误代码的模板树）中移除的节点，以及在 A_Tree（修复后代码的模板树）中添加的节点。

定义 2.1.1.4（外部上下文）

外部上下文是一个对 (BC_Tree, AC_Tree)，其中BC_Tree是内部上下文之前的语句的模板树，而 AC_Tree 是内部上下文之后的语句的模板树。

定义 2.1.1.5（修复模板）

修复模板是一个三元组 (修复模式, 内部上下文, 外部上下文)。

我们根据修复模式P将修复模板分为四类：

Add: B_Tree = ∅⋀A_Tree ≠ ∅

Remove: B_Tree ≠ ∅⋀A_Tree = ∅

Insert: B_Tree ≠ ∅⋀A_Tree ≠ ∅⋀B_Tree ⊂ A_Tree

Replace: B_Tree ≠ ∅⋀A_Tree ≠ ∅⋀B_Tree ⊈ A_Tree

2.1.2 修复解析

在修复解析过程中，TypeFix 将所有类型错误修复解析为特定的修复模板，图 2 给出了一个示例说明。

图 2：一个针对 fix commit（ansible:075c6e）的修复解析过程的示例。

解析修复模式和内部上下文：给定一个修复提交，TypeFix 首先提取所有添加和删除语句的行信息，然后遍历错误代码和修复后代码的抽象语法树（ASTs）来构建模板树。为了处理不同级别的编辑，TypeFix 定位包含修改行的最深语句级别的 AST 节点，并分别从错误代码和修复后代码中提取相应的子树作为Bug_Tree 和 Fix_Tree。然后，TypeFix 修剪 Bug_Tree 和 Fix_Tree 中共有的相同子树，仅留下变化的部分。

由于修剪后的 Bug_Tree 和 Fix_Tree仅包含编辑部分，TypeFix 可以检查编辑是在表达式级别还是语句级别。如果 Bug_Tree 和 Fix_Tree共享相同的根节点，TypeFix 就确定编辑没有重写整个语句，因此它是表达式级别的。否则，TypeFix 可以确定编辑是语句级别的。

对于语句级别的编辑，内部上下文是空的。对于表达式级别的编辑，TypeFix 通过提取 Bug_Tree 和 Fix_Tree 共有的相同节点来创建内部上下文，形成一个新的模板树IC_Tree，并从 Bug_Tree 和 Fix_Tree 中减去 IC_Tree来构建修复模式中的B_Tree和 A_Tree。内部上下文中连接 IC_Tree 与修复模式中B_Tree和 A_Tree的边的关系也被记录在内部上下文中。

解析外部上下文：TypeFix 识别位于内部上下文作用域之外但与修复模式有直接数据依赖关系的语句作为外部上下文。具体而言，它提取在内部上下文之前和之后与修复模式共享相同变量的语句，以分别构建BC_Tree和AC_Tree。为了简化修复模板的抽象过程，TypeFix 还修剪 BC_Tree和AC_Tree 中不包含共享变量的子树。

2.1.3 修复模板挖掘。

在修复模板挖掘过程中，TypeFix 通过层次聚类将具体的修复模板抽象并合并为一般的修复模板。TypeFix 每次都会抽象或合并两个最相似的修复模板，并将从具体到一般的修复模板组织成聚类树。我们定义了两种相似度度量：值距离和结构距离。

定义 2.1.3.1 (修复模板距离)。

修复模板中两个模板树之间的值距离dp和结构距离sdp定义为：

在这里，Num(t)表示模板树t中的节点数量，而ValueMatch(VMp)和TypeMatch(TMp)被定义为：

定义 2.1.3.2 (上下文距离)。

上下文中两个模板树之间的值距离dc和结构距离sdc定义为：

在这里，MAX（a,b,c）将集合a和b中的元素进行配对，并找出这些配对所能达到的最高相似度c，然后返回配对的数量。Num(t)表示模板树t中的节点数量，而LeafNode(t)返回一个模板树t的叶节点集合。ValueMatch(VMc)和TypeMatch(TMc)被定义为：

模板抽象。TypeFix 并不一次性抽象整个修复模板，而是每次抽象一个组件，即修复模式、内部上下文或外部上下文。TypeFix 通过一个名为“Abstract”的过程来抽象两个相似的组件。图 3 和图 4 分别正式展示了在修复模式和上下文中执行“Abstract”过程的方法。

图 3：修复模版的抽象过程

修复模式和上下文的抽象分别遵循上述的自顶向下和自底向上的方法。一般来说，在从两个相似的模板树中抽象模板节点a和b时，可能有以下四种情况：

• 相同节点：a和b完全相同，它们可以被保留在泛化的修复模板中。

• 值抽象：a和b具有相同的类型但值不同。TypeFix 创建一个具有相同类型的节点，并将值设置为一个特殊的 ABS 标记来指示一个占位符（hole）。

• 类型抽象：a和b具有相同的基类型但具有不同的类型或值。TypeFix 创建一个具有相同基类型的节点，并将类型和值都设置为一个特殊的 ABS 标记来指示一个占位符。

• 节点移除：a和b没有共同的属性。TypeFix 直接移除这两个节点。

TypeFix 还会在类型抽象和节点移除时修剪所有子节点，因为AST节点类型的改变会使其原始子节点的功能失效。

通过层次聚类挖掘修复模板。利用上述提到的相似度度量和抽象过程，TypeFix 选择相似的修复模板，并通过层次聚类将它们合并以构建聚类树。我们对聚类树的定义如下。

图 4：内部和外部上下文的抽象过程

定义 2.1.3.3（聚类树）

聚类树是一个树（T,E,rt），其中T是修复模板集合，E是边，rtT是根修复模板。边是一个对（t,），其中修复模板的父节点，表示t是直接从抽象出来的。

为了确保领域知识损失最少，TypeFix 在挖掘过程中遵循两种策略。首先，TypeFix 在选择组件对进行抽象时遵循“外部上下文 > 内部上下文 > 修复模式”的优先级顺序。其次，TypeFix 优先进行值抽象而不是类型抽象。

我们展示了TypeFix的层次聚类算法（算法1）。

2.2 补丁生成阶段

TypeFix 的补丁生成阶段主要包含两个过程：修复模板匹配和基于提示的补丁生成。

2.2.1 修复模板匹配

在修复模板匹配过程中，TypeFix 通过广度优先搜索（BFS）在聚类树上选择匹配的修复模板，然后根据频率和抽象比例对修复模板进行排名。

选择修复模板。给定一个包含错误的程序，TypeFix 会将错误行解析为一个模板树Bug_Tree，并将错误行之前和之后的上下文分别解析为模板树BBug_Tree和ABug_Tree。TypeFix 会将这三元组 (Bug_Tree,BBug_Tree,ABug_Tree) 与聚类树中的修复模板进行比较，以找到适当的修复模板。

定义 2.2.1.1（模板节点匹配）：

对于两个模板节点a和b，如果a.value匹配b.value，并且(a.t,a.bt)匹配（b.t,b.bt），则a匹配b。

a.value匹配b.value如果b.value=ABS a.value=b.value。

(a.t,a.bt)匹配（b.t,b.bt）如果a.bt=b.bt(a.bt=b.ta.t=b.t)。

定义2.2.1.2（模板树匹配）：

对于两个模板树A和B，如果A中存在一个节点aA.N，使得a与B的根节点B.rt匹配，并且存在节点映射,其中aci与bci匹配，{ac1,...,acn}是a的子节点集合，且满足aci+1.id > aci.id (即子节点的ID是递增的)，同时{bc1,...,bcn}等于B.rt的子节点集合，那么A与B匹配。如果B为空树（即没有节点），则A总是与B匹配。

定义 2.2.1.3（修复模板匹配）：

对于一个包含错误的程序（由Bug_Tree、BBug_Tree和ABug_Tree组成）和一个修复模板（由P、IC和EC组成），如果错误程序与修复模板匹配，则需要满足以下条件：BBug_Tree(错误前的上下文模板树)与EC.BC_Tree(修复模板的错误前上下文模板树)匹配，ABug_Tree(错误后的上下文模板树)与EC.A_Tree（修复模板的错误后上下文模板树）匹配，并且Bug_Tree（错误行模板树）与 Concat(IC.IC_Tree,P.B_Tree,IC.rn)匹配。其中，Concat(a,b,rn)表示将模板树b连接到模板树a上，通过边(n,b.rt,rn[n].br)，这里的n是新添加的边的标识，b.rt是b的根节点，rn[n].br是n对应的边界条件。

根据上述规则，TypeFix 从每个聚类树的根修复模板（最通用的修复模板）开始，通过广度优先搜索（BFS）遍历聚类树，直到找到与错误程序匹配的最深修复模板（最具体的修复模板）。这些修复模板将被收集起来，以便在下一步中进行排名。

修复模板排序。TypeFix 在将修复模板应用于错误程序之前会对它们进行排序。为了在补丁生成过程中为预训练模型提供最多的领域知识，TypeFix 利用了两步策略来优先排序修复模板。

TypeFix 将具有相同连接模板树IC_Tree和B_Tree的修复模板进行分组。这些修复模板为相同的错误模式提供了不同的修复方案。TypeFix 根据修复模板所代表的训练实例数量对同一组内的修复模板进行排序，因为数量越多表明该修复模板在给定的错误程序上被使用得更频繁。然后，TypeFix 根据每个组中第一个修复模板的A_Tree的抽象比率对组进行排序。模板树的抽象比率定义为节点值或类型为ABS标记的节点的比率。A_Tree的抽象比率越高，表明与之相关的领域知识越少，因此预训练的代码模型在生成完整的候选补丁之前需要预测更多的信息。

2.2.2 基于提示的补丁生成。

在这个过程中，TypeFix 将排序后的修复模板应用于错误程序并生成代码提示。然后调用 CodeT5 模型来填充代码提示中的掩码并生成候选补丁。

应用修复模板。对于每个选定的修复模板，TypeFix 通过添加虚拟 AST 节点（即，值为ABS标记的 AST 节点）作为占位符来完成其修复模式中的A_Tree，因为在修复模板挖掘过程中移除了一些子 AST 节点。然后，TypeFix 将错误程序中匹配B_Tree的子树 AST 替换为完成的A_Tree，并将修改后的错误程序 AST 转换为代码提示。代码提示是包含 ABS 标记作为掩码的源代码，这些掩码将由预训练的代码模型进行预测。

生成补丁。大多数预训练的代码模型都被训练用于预测源代码中的掩码，因此它们自然可以用于预测代码提示中ABS标记的值。在本文中，我们选择 CodeT5 作为补丁生成过程中的预训练代码模型。在生成补丁时，TypeFix 将代码提示中的 ABS 标记替换为 CodeT5 中使用的有序掩码标记，然后调用 CodeT5 来预测每个掩码的标记。将掩码的预测值填充到代码提示中以生成候选补丁。

验证补丁。TypeFix 采用经典的生成-验证方法在补丁生成中。对于生成的补丁，TypeFix 首先过滤掉那些包含语法错误的补丁，然后对每个补丁运行测试套件以找到合理的补丁。进一步的，合理的补丁会被作者检查以识别正确的补丁。

3 实验设计

3.1 数据集

训练集。我们从GitHub上收集了8,722个包含“fix type error”术语的合并拉取请求，在剔除过长提交后从中提取到了10,981个修复代码来形成训练集。

基准测试集。我们使用了两个基准测试集BugsInPy和TypeBugs。我们还在两个基准测试集中移除了重复的类型错误，即具有相同提交签名的类型错误。最终，我们从BugsInPy中得到了54个类型错误，从TypeBugs中得到了109个类型错误。

3.2 基线模型

我们将TypeFix与以下四个基线模型进行比较：

PyTER。PyTER是一个基于规则的自动程序修复（APR）方法，专为修复Python类型错误而设计。它拥有九个预定义的模板和几个用于合成模板以生成候选补丁的规则。AlphaRepair。AlphaRepair是通用的基于提示的APR方法的当前最先进方法。它基于一些通用的提示模板在错误代码中屏蔽标记，并调用预训练的代码模型来生成补丁。CoCoNuT。CoCoNuT是一种基于神经机器翻译（NMT）的通用APR方法。它将错误代码翻译成候选补丁。Codex。Codex是一个大型GPT模型，在GitHub上公开可用的代码上进行了微调。

3.3 评估指标

我们采用了先前工作中常用的正确（Correct）和合理（Plausible）指标来评估TypeFix在修复类型错误方面的性能。此外，我们还添加了一个新的指标，名为模板覆盖率（Template Coverage），模板覆盖率定义为：bug的开发者补丁与某个方法的修复模板相匹配的bug的比例。

表 1：与三个基线方法相比，TypeFix 的评估结果以“Correct/Plausible”格式呈现。修复率（Fix rate）是正确补丁的比例。

3.4 实现

TypeFix的整个框架是使用Python实现的，包含超过10,000行代码。对于PyTER、AlphaRepair和CoCoNuT，我们直接使用了作者发布的复现代码包。我们使用原始训练集和我们收集的训练集来训练CoCoNuT，以适应修复Python类型错误。由于Codex不对公众开放，我们使用OpenAI提供的engine code-davinci-002的公共API来通过提示查询它。

4 评估

在本节中，我们将评估TypeFix在以下三个研究问题上的性能：

RQ1: TypeFix在修复类型错误方面的有效性如何？RQ2: TypeFix从现有的bug修复中挖掘修复模板的能力如何？RQ3: 在什么情况下TypeFix无法修复类型错误？

4.1 RQ1:TypeFix的有效性

为了评估TypeFix在修复类型错误方面的有效性，我们将TypeFix与基于规则的APR方法和基于学习的APR方法进行了比较。表1展示了TypeFix以及基准方法在TypeBugs和BugsInPy两个基准测试集上的性能。

与基于学习的方法的比较。从表1中我们可以看到，TypeFix、Codex和AlphaRepair的表现普遍比CoCoNuT好得多。当将TypeFix与采用一般领域无关提示模板的AlphaRepair进行比较时，我们发现TypeFix的修复率比AlphaRepair高1到4倍。

此外，图5以维恩图的形式展示了TypeFix和三种基于学习的方法在TypeBugs和BugsInPy中能够正确修复的唯一类型错误。

图 5：基于学习的自动程序修复方法提供的正确补丁的韦恩图

针对RQ1的回答：

TypeFix在两个基准测试中均比目前最先进的方法修复了更多的bug。同时，TypeFix在两个基准测试中获得了最多的独特类型错误修复。这证明了TypeFix在修复类型错误方面的有效性。

表 2：TypeFix 和 PyTER 之间唯一类型错误修复数量和模板覆盖率的比较。

表 3：TypeFix 中修复模板挖掘的统计信息。

表 4：消融实验结果。

4.2 RQ2：TypeFix的模板挖掘能力

为了全面调查TypeFix挖掘修复模板的能力，我们关注TypeFix在模板挖掘过程中的性能以及TypeFix挖掘的修复模板的有用性。

表3展示了TypeFix在修复模板挖掘过程中的性能。表2展示了TypeFix和PyTER所实现的模板覆盖率。

为了进一步研究TypeFix挖掘的修复模板如何帮助补丁生成过程，我们在每个类别下的修复模板上进行了消融研究。表4展示了结果。

针对RQ2的回答：

TypeFix在两个基准测试中均实现了约75%的模板覆盖率。此外，消融研究结果也证明了TypeFix挖掘的修复模板在每个类别下的有用性。

4.3 RQ3:TypeFix的局限性

第一个局限性是TypeFix有时无法为当前的错误程序找到匹配的修复模板。这个局限性可以通过让TypeFix适应新的代码模式来缓解。

第二个原因是TypeFix使用的CodeT5模型有时即使给出了正确的修复模板，也无法生成正确的补丁。局限性可以通过使用更先进的预训练代码模型来缓解。

针对RQ3的回答：

TypeFix有时无法修复类型错误，以及大约25%的情况下挖掘的修复模板无法覆盖。

5 相关工作

5.1 自动程序修复

大多数APR方法可以归类为基于规则的方法和基于学习的方法。

基于规则的方法：基于规则的APR方法利用预定义的模板和规则，通过静态和动态分析生成针对错误的补丁。然而，传统的基于规则的方法通常是特定于领域的，并且只能修复有限数量的真实世界中的错误。TypeFix实现了一种新的修复模板设计，专门用于处理不同级别的类型错误。

基于学习的方法： 最近，基于学习的APR方法变得相当流行，并显示出卓越的性能。AlphaRepair是第一个基于提示的APR方法，它将APR问题转化为填空问题。然而，AlphaRepair使用的通用且不了解特定领域的提示很难处理复杂的类型错误。TypeFix通过结合领域知识和提出的修复模板，并通过现有的类型错误修复来挖掘它们，从而解决了这个问题。

5.2 预训练语言模型

CodeBERT：是一个BERT风格的模型，在编程语言和自然语言上都进行了预训练，可以跨语言地理解和生成代码。

GraphCodeBERT：在预训练阶段利用了数据流图。它不仅能够理解代码的文本信息，还能理解代码中的控制流和数据流信息。

CodeGPT：是一个GPT风格的模型，它能够生成与给定上下文相关的代码片段，对于代码补全和代码生成等任务非常有用。

Codex：是通过微调GPT3模型来生成Python函数的GPT风格模型，在代码生成和代码理解等任务上取得了显著的效果。

CodeT5：是一个编码器-解码器模型，能够处理各种与代码相关的任务，如代码搜索、代码摘要生成等。

6 结论

我们提出了一种基于领域感知提示的方法TypeFix，用于修复Python类型错误。TypeFix通过融入领域感知的修复模板来改进基于提示的方法。TypeFix实现了一种新颖的修复模板设计，以处理不同级别的类型错误，并通过一种新颖的层次聚类算法挖掘修复模板。TypeFix通过将修复模板应用于有错误的代码来将领域知识融入代码提示中，并调用预训练的代码模型根据代码提示生成候选补丁。实验证明了TypeFix的有效性以及TypeFix挖掘的修复模板的有用性。

转述：朱轶凡