译 / 莱斯
作者： Ali Mesbah / Andrew Rice / Emily Johnston, Nick Glorioso, and Edward Aftandilian
发表于： Proceedings of the 27th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE '19)
摘要
开发者往往需要花费大量时间修复代码编译错误。经过观察，我们发现修复错误的过程遵循特定的模式，并且非常机械化。我们提出了一种新颖的方法，该方法可以通过深度神经网络自动学习这些模式，并针对最耗时的编译失败问题提出修复建议。
我们描述了如何收集 Google 所有的构建错误以及导致错误的代码，最终转化为成功的构建。我们由代码更改生成一个抽象语法树（AST）的 diff，将其转换为一种称为 Delta 的 DSL，该 DSL 描述了编译成功所必需的代码修改。然后将编译诊断信息（作为源）以及解决了该诊断报错的 Delta 修改（作为目标）给到神经机器翻译网络，进行训练。
针对最常见且最耗时的两种 Java 编译错误（即符号缺失和方法签名不匹配），我们的 DeepDelta 系统修复了 38,788 个编译错误中的 19,314 个（50%正确率）。正确修复排在修复建议前三位的平均概率达 86%。
关键词
编译错误，程序修复，神经机器翻译
1 背景介绍
使用编译型的编程语言有一个好处是，编程错误在编译阶段就暴露出来，而非运行时。失败的构建通常会给出编辑-编译的周期，开发者要根据提示不断的尝试解决诊断错误，并重新编译，反复循环这一过程。
此前的一项大规模研究报告称，专业开发者每天平均构建 7 至 10 次代码。研究发现构建时编译错误很普遍且成本很高，开发人员需要大量时间和精力来解决。开发者通过构建管理系统如 Bazel，Gradle 或 Maven 编译代码时，构建时编译错误就会出现。
我们的目标是帮助开发者自动修复构建错误。自动化程序修复领域先前的研究集中在通过固定模板和基于搜索的技术在测试失败时查找补丁。在本文中，我们提出了一种新颖的方法，称为 DeepDelta，用于自动修复构建时编译错误。
我们的看法是，开发者在解决编译器错误而修改代码的行为中，存在一些通用模式。通过提取代码的失败快照和已解决快照之间的抽象语法树（AST）更改，并将其作为抽象特征提供给深度神经网络，可以自动学习此类模式。
本文作出了如下贡献：
- 我们对编译错误和相应的修复进行了大量研究，从而找到实践中最普遍且代价最高的错误类型。我们的数据集来自谷歌数千个 Java 项目中开发者的代码更改，包含 3 亿行代码。我们的研究表明，编译器诊断中有 51％ 与编译器无法解析特定符号有关，这也是修复代价最高的编译器错误类别。
- 我们将自动修复过程建模为神经机器翻译（NMT）问题，其中问题源包含故障信息，而目标是一组解决故障的 AST 更改，这些更改以一种称为 Delta 的 DSL 表达。
- 我们介绍了一种名为 DeepDelta 的实例方法，该方法可从开发者历史数据中自动生成源特征和目标特征，并在实践中学习两种最普遍且代价最高的 Java 编译错误的修复模式。
- 通过对 Google 代码中 38,788 个未发现的编译错误进行大量经验评估，我们证明了此项技术的有效性。评估结果表明，DeepDelta 有 47%-50% 的几率生成完全正确的修复方案。正确修复排在修复建议前三名的几率在 85%-87%。
2 收集编译错误
学习修复模式所需的第一步是获取编译错误相关的开发者数据。我们在 Google 的日常开发周期中收集这些数据，同时也使用该数据集来表征各种编译错误在实际中的普遍性和成本。
2.1 数据收集
开发者启动的每次构建都会被 Google 自动记录日志，日志内容为每次构建的详细信息，包括所有编译器诊断信息（即详细的错误信息）以及所构建代码的快照。
在本次研究中，我们收集了两个月的构建日志，从 2018 年 1 月 23 日到 2018 年 3 月 23 日。随后对收集到的日志进行解析和分析，以了解实际中最常发生的构建错误。尽管我们的构建诊断框架与语言无关，但是在本文中，我们仅关注与 Java 项目有关的构建错误。
2.2 诊断类型
我们按诊断类型对编译器错误消息进行分组。诊断类型代表具有相同原因的错误。编译器会在错误消息模板中插入具体名称，例如 javac 对于尝试实例化一个抽象类的情况使用模板““{0} is abstract;cannot be instantiated”，并用 abstract.cant.be.instantiated. 的 key 来引用它。我们构建了一个解析器，将构建日志中的具体错误消息映射回产生它们的消息模板（请参见表2）。
2.3 从诊断到解决
失败的构建可能包含许多诊断信息。这些诊断中有些是新的，有些可能与历史构建中的诊断相同。因此，我们首先着手将包含特定诊断的构建序列转换为_修复会话_。
定义1 修复会话 Resolution Session（RS）。 某个构建诊断 
使用修复会话的目的是捕获开发者用于解决诊断问题的时间段。因此，我们将时间窗 T 定义为一小时。 此窗口代表“任务切换窗口”，即开发者如果没有在 T 时间内执行构建，那么很可能他们已经去忙其他事情了。比如去吃午饭或者离开工位。
我们根据解决特定诊断所需的时间来量化开发人员成本。以诊断
定义2 主动修复成本 Active Resolution Cost（ARC）。 诊断
图 1 描述了我们构建修复会话的过程。如图 1a 所示，D1 和 D2 首次出现在 build 1 中，D3 首次出现在 build 2。我们将某个诊断从构建中消失视为已解决（参考定义1），如 D3 在 build 4 里面不再出现，因此它的修复会话包含 build 2-4，如图 1b 所示。
2.4 数据集与发现
表 1 总结了我们的数据集，我们共处理了 480 万个构建，其中 100 万个是失败的，约占所有构建失败的 20％。
表1 数据集
回想一下，构建失败可能包含多个编译错误，即诊断。这些构建失败共包含 330 万个诊断，我们可以从中得出 190 万个修复会话。剩余的 150 万个诊断我们没有找到修复会话，可能是由开发者放弃更改或两次构建间隔时间超过一小时所致。
表2 按主动修复成本排序的前十大诊断类型
表 2 列出了我们数据集中最常见的十大最耗时的错误。该表显示了诊断类型、主动修复成本（平均，最小和最大）、解决该诊断问题的后续构建数量（平均，最小和最大）、每种诊断类型的比例和数量、相对于总量的主动修复成本，以及诊断类型的文字说明。
总共有 1,853,417 条编译诊断，这些诊断随后在修复会话中修复。表格显示，51%（949,325）的诊断与编译器无法解析某个符号有关，即 cant.resolve 诊断类型，报错信息为“cannot find symbol”。与2014年的调查结果相比，似乎开发者遇到的符号缺失问题在不断加剧。表中的第二项诊断类型是 cant.apply.symbol 错误，占总量的 8%。当编译器无法找到给定类型的方法声明时，就会发生 cant.apply.symbol。
对于每种诊断类型，我们还计算了构建错误的相对成本：构建诊断实例数乘以平均主动修复成本。两个月的数据砺，总成本高达 57,215,441 秒。也就是说两个月内，开发者大约花费了 21 个月来修复构建错误。其中 cant.resolve 仍然是最耗时的诊断类型，占主动修复成本总量的 47%（约 10 个月）。cant.apply.symbol 占主动修复成本总量的 11%（约 2 个月）。单是这两个错误就已经占了总耗时的 58%，在我们的数据集中大约是一年的开发者工时。
3 运行示例
鉴于实践中 cant.resolve 和 cant.apply.symbol 的普遍性和成本很高，我们将生成修复建议的重点放在这两类构建错误上。但是我们的方法具有足够的通用性，稍加修改即可应用于任意诊断类型。本文使用cant.resolve作为运行示例。编译器必须先认识一个标识符，然后才能使用它。标识符定义及其用法之间的不一致（包括找不到该标识符的情况）是此构建错误的根本原因。例如，当缺少依赖项（例如，在另一个库中），缺少导入或符号名称错误时，就会发生这种情况。
以下面的代码片段为例：
import java.util.List;
class Service {
List <String > names () {
return ImmutableList.of( pub , sub );
}
}
复制代码这段代码构建时，编译器会报如下错误：
Service.java :4: error: cannot find symbol symbol: variable ImmutableList
开发者忘记为 ImmutableList 导入包（从Google Guava库），因此编译器无法解析该符号。开发者要为该符号找到正确的包并添加适当的导入语句，来解决这个报错：
import java.util.List;
+++ import com.google.common.collect.ImmutableList;
class Service {
List <String > names () {
return ImmutableList.of( pub , sub );
}
}
复制代码因为 ImmutableList 是在另一个项目中定义的，所以还要声明对构建系统的依赖。如果使用 Bazel 构建系统，修复方法可能是删除现有的对 Guava 基本包的引用，并添加其 collect 包作为替代：
java_library(
name = Service ,
srcs = [
Service.java ,
],
deps = [
--- "//java/com/google/common/base",
+++ "//java/com/google/common/collect",
],
...
)
复制代码4 找出修复更改
收集到诊断信息并构建修复会话之后，我们将修复会话输入到解决方案检测的环节。这一步的目标是系统地检查开发人员如何更改其源代码以解决构建错误。
4.1 检索代码快照
在 Google，开发者的代码更改会作为临时快照被 IDE 自动保存到云端。这意味着使用可检索的快照标识符保留了完整的代码更改记录。这使得我们可以向前追溯，检索特定构建在某个时间点的代码快照。
对每个构建修复会话，我们首先提取第一个和最后一个构建版本的快照 ID。前者对应导致诊断的代码快照，后者对应解决该诊断的代码快照。
然后我们用快照 ID 查询快照云端服务器，获取与该时间点吻合的具体的代码。
4.2 AST 差异对比
此时我们已经得到了每个修复会话的两份代码快照，分别处于出错状态和修复状态。为了了解开发者如何修改代码以解决构建错误，我们对比了出错状态和修复状态的代码差异。
用于检测源代码更改的常规方法是 Unix 行差异（diff），它仅以文本中行级的添加和删除动作为粒度来计算更改。这会导致 diff 依赖于源代码的格式。虽然行差异是一种很流行的人为对比方法，比如在代码 review 中，但是很难从文本行差异自动推断出代码的语法变化。
为分析语法级的代码更改，我们采用树的方法进行差异对比。我们解析每个修复会话的出错快照和修复快照，生成相应的抽象语法树（AST）。我们在本项目中为 Java 和 Bazel 构建语言创建了解析器，当然，对其他语言的支持也可以轻松添加进来。
然后将出错快照和修复快照的 AST 放到树的对比算法中。
定义3 抽象语法树差异 AST Diff。 给定两个 AST：源
AST 差异算法首先尝试对比节点标签，从而将源 AST
- 移动：
- 更新：
- 删除：：
- 插入：
图 2 显示了我们的示例（见第 3 节）中的 AST，图 a 为初始的出错状态，图 b 为开发者添加了 import 语句之后修复的 AST。
图2 Java AST 改动
AST diff 算法检测到的节点改动在图 2 中以灰色表示。运行示例的 AST diff 监测到根节 COMPILATION_UNIT 下插入了一个 IMPORT 节点。ImmutableList 的完整包名称也作为子节点插入到新增的 IMPORT 节点下。对于构建文件，检测到的更改操作是对依赖项（deps）的更新，即，将通用 base 包更新为通用 collect 包。
4.3 修复更改
我们认为开发者在解决构建错误的实践中，存在一些反复出现的模式。我们可以从修复更改中自动推断这些模式，并用于辅助开发。
定义4 修复更改 Resolution Change（RC）。 修复更改（RC）是指修复会话中，报错快照和修复快照之间的 AST Diff。
5 修复构建错误
最近的研究表明，原本用于分析自然语言的模型（例如 n-gram 模型）也可以有效地进行源代码推理。这一点被称作软件语言的_自然性假说_，意思是大型代码集与自然语言文本具有普遍的相似性，因为编码也是一种人与人的交流。遵循这一假说，我们认为处理自然语言的概率机器学习模型也可以用于辅助编程。
具体来讲，我们的想法是将给出修复建议的任务当作神经机器翻译（NMT）问题来处理。在我们的案例中，目标不是将一种自然语言翻译成另一种，而是将给定的源构建诊断特征“翻译”为解决诊断问题的修复更改特征。
5.1 特征提取
我们根据每个修复更改，即构建诊断和修复诊断的编辑，来生成特征值。我们将生成的特征用作神经网络的输入，以学习诊断和修复之间的转换模式。
针对修复会话中的每个修复更改，我们分别生成一个源特征和一个目标特征。一对源-目标特征可反映构建失败的信息和相应修复的 AST 改动。
源特征。源特征与构建诊断类型及其文字描述有关。这些可以包含在任何诊断类型的源特征中，而与诊断信息本身无关。
为了给机器学习算法提供更多上下文，我们可以选择性的为源特征添加诊断相关的信息。举个例子，对于 cant.resolve，我们将报错的代码快照解析为 AST，根据编译器提供的标签和位置等信息，找到 AST 上的缺失符号，然后遍历树来获得其 AST 路径。
图3 ImmutableList 的 AST 路径
定义5 抽象语法树路径 AST Path（AP）。 缺失符号 
图 3 将我们的运行示例中缺失符号的 AST 路径标为高亮。评估结果表明，采用 AST 路径可以使结果的准确率提高 15%-20%。AST 路径为深度神经网络提供缺失符号的上下文信息，比如符号是方法内的局部变量还是类变量。
除了符号的 AST 路径外，我们将其节点类型、标签，及其子节点（例如，方法调用的类型参数）也添加到了源特征中。在运行示例中，源特征包括：
- 诊断类型：compiler.err.cant.resolve
- 诊断文本：cannot find symbol
- AST 路径：COMPILATION_UNIT CLASS METHOD RETURN METHOD_INVOCATION of
- 符号类型：IDENTIFIER
- 符号标签：ImmutableList
对于 cant.apply.symbol 错误，我们使用三种数据来拓展源特征，即预期、发现和原因。预期数据是编译器推断的预期类型，发现数据显示了在代码中找到的类型，原因数据即编译器无法应用该符号的文字描述。
目标特征。目标特征包含修复更改的信息，即为修复编译失败的代码而作出的 AST 改动。
为了获取修复更改的特征，我们定义了一种称为 Delta 的领域特定语言（DSL）。Delta 的语法基于语法解析器的 EBNF 规范定义，如清单 1 所示。
每个 Delta 特征都以发生改动的文件类型（即 JAVAFILE 或 BUILDFILE）开头，随后是一系列更改动作。每个更改操作都包含一个 AST 更改类型（如INSERT，UPDATE）以及更改后的 AST 节点类型和值。对于INSERT，DELETE 和 MOVE 的更改类型，还包含更改后节点的父节点，以提供变动节点的相对接近度等更多上下文信息。对于 UPDATE，将提取节点改动前后的值。
在我们的示例中，Java 文件和构建文件的目标修复更改特征分别如清单 2 和清单 3 所示。
清单3 Delta 构建文件示例
特征生成。提取特征后，我们分别分析源特征和目标特征，以生成两份相应的前 |V| 个高频词例（token）的词汇表。例如，由于词例 COMPILATION_UNIT 是 AST 路径的根节点，它在源特征中会频繁出现。因此这个词例会出现在源词汇表中。同样的，词例 BUILDFILE 出现在很多目标特征中，因此也在目标词汇表里。这些高频词用于在训练和推断中做 embedding，即词汇表中的词例映射到一个实数向量用于训练，而在推断过程中，结果的向量化表达则映射回词汇表。
最后将特征数据集按照比例 70%、15% 与 15% 随机分成三份，分别用于训练、在线评估模型以及针对不可见特征进行模型离线评估。
5.2 学习修复更改模式
深度 NMT 模型最近在自然语言翻译的领域取得了不错的效果。用一个编码器-解码器设置将源特征 x 转换为目标特征 y，也称作 seq2seq，NMT 通过建模并学习这一过程的条件概率 p(y|x) 来获得结果。编码器负责对每个源特征 x 进行表达，不作任何预测。解码器根据源的表达来预测序列中的下一个单词，由此生成翻译 y。
我们的深度神经网络（DNN）基于 TensorFlow 构建，它由 1024 个单元的深度 LSTM 反馈神经网络（RNN）组成，包含 4 个编码器层和 4 个解码器层。编码器我们选择 Google 神经机器翻译（GNMT）编码器，由 1 个双向层和 3 个单向层组成。
我们引入随机梯度下降（SGD）算法作为迭代方法，学习率 1.0。为减少过拟合，我们设置了 0.2 的 dropout 值。也就是随机忽略一部分神经元，dropout 可以防止训练集的协同适应。LSTM 在中短长度的输入序列上表现不错，但是不擅长处理长文本。注意力机制（Attention Mechanism）通过扩展网络的注意力范围，很好的解决了这一局限性。由于修复更改的特征序列可能会很长，我们采用了标准的 Bahdanau 注意力。
5.3 推断修复建议
整个过程都按照顺序依赖形成流水线，包括生成修复会话、修复更改和特征值以及训练模型。因此我们的整个学习过程都是自动化、可重复的。
模型训练完成后上传服务器，用于查询修复预测。模型可以为任意输入生成大量翻译。在我们的 NMT 设置中，翻译使用 beam search 进行搜索，这是一种在翻译时间和精度之间进行折中的新式搜索算法。模型的输入是表征编译失败的源特征 x，输出建议以 n 个序列 {
6 评估
我们对 Delta 在最普遍和最耗时的两个编译错误（即 cant.resolve 和 cant.apply.symbol）上的效果，进行了经验性评估。
6.1 数据生成
第 2.4 节中介绍了我们用于训练和评估的数据集，该数据集包含了 Google 在两个月的时间内收集的构建数据。
我们首先对所有绿色单一的解决会话，计算失败代码和已解决代码之间的 AST 差异。然后将 AST 更改的数量限制在 0 到 6 个之间，因为数量较多的更改常常包含重构，并且早先的研究已经表明修复方案一般少于 6 个改动。我们一共计算了 110,219 个绿色单一解决会话，涵盖 37,867 个 Java 文件和 7,011 个构建文件。
由于要处理的是大型业务代码库，我们将源和目标词汇表的词例上限 |V| 设置为 30,000。特征生成步骤得到源和目标的两个词汇表，每个表最多包含 30,000 个不重复的词例。cant.resolve 和 cant.apply.symbol 分别得出了 265,456 和 25,201 个源/目标特征。如表3所示，这些特征值被随机打乱并划分为三份，即训练集（用于训练），验证集（用于训练期间的在线评估）和测试集（用于模型的离线评估）。每个分集都包含源/目标特征对。
表3 生成的特征值
6.2 训练
我们为 cant.resolve 和 cant.apply.symbol 分别提取特征并训练模型，以对比 DeepDelta 在不同诊断类型上的表现。在第 5.2 节所述的 DNN 设置之上，我们还对网络进行如下配置：源和目标的最大序列长度均设置为 100；batch 大小为 128；训练步数为 100,000；配置推断算法为一次产生 10 条建议（参考第 5.3 节）。
我们将训练集的源/目标特征以及词汇表输入到神经网络来训练模型。模型首先对源/目标词例做一个嵌入（embedding），为此要提供源和目标的词汇表，来确保每个词例不重复。我们同时也将验证集输入到网络，用于训练时的验证。模型在带 GPU 的 Google 内部云节点上进行了训练。
6.3 评估方法
我们用同样包含源/目标特征的测试集进行评估。这些是模型未曾接触过的数据。我们对每个诊断类型分别评估，获取测试集里每条数据的源特征，输入到推断服务器，得出修复建议。测试数据集的目标特征，也就是开发者实际执行的修复方案，作为 DeepDelta 所生成的 10 条修复建议的评估基准。
我们采用了如下指标来评估修复建议的效果。
困惑度（Perplexity）：困惑度反映模型预测样本的优劣，低的困惑度（个位数）表示模型擅长预测给定的序列。
BLEU：BELU 是用于评估机器翻译句子质量的一个常见指标。实践表明它与人为判定有很好的相关性。BELU 使用 n-gram 模型，根据单词及其排序计算输入和输出语句的匹配度。BELU 指标的数值在 1-100 范围内。自然语言翻译达到 25-40 分即可视为高分。
句法验证：为了验证句法正确性，我们通过 ANTLR4 从 Delta 语法生成了词法分析器和解析器。我们将修复建议输入到 Delta 句法分析器/解析器中，这样我们就可以评估模型给出的建议是否符合预期的修复更改语法。输出是个布尔值，即符合与不符合。
修复的正确性：如果推荐的 10 条修复里，至少有一个是有效的并且与开发者的手动修复（即测试集的目标特征基准）完全匹配，那么认为修复是正确的。对比修复建议和基准的时候，我们采用文本字符串相等的比较方式。
正确修复的排名：正确的修复建议在整个修复建议列表中的排名，表明了模型生成正确修复的能力高低。排名越高，就可以越早应用该修复。DeepDelta 生成正确的修复建议时，我们会在 10 个修复建议的列表中标记其位置。
6.4 结果
表 4 给出了我们评估的两种诊断类型的结果。该表显示了每种诊断类型的困惑度和 BLEU 得分，测试集里的失败编译数，生成的建议数量（每个失败编译有 10 条），有效建议的平均占比，正确修复在前三位修复建议里的占比。
表4 结果
困惑度与 BLEU 得分：前面提到，模型追求低的困惑度（个位数）和高的 BLEU 分数（25-40）。表 4 显示我们的模型在 cant.resolve 和 cant.apply.symbol 两种诊断类型上分别取得了 1.8 和 8.5 的低困惑度。BLEU 得分也很高，cant.resolve 得分 42，cant.apply.symbol 得分 43。
验证：图 4 以直方图的形式展示了每个故障里，有效建议在 10 个生成建议上的分布。我们对 Delta 语法进行的验证表明，对于 cant.resolve 报错有 71% 的修复建议是有效的。对于 cant.apply.symbol 报错，由于代码更改在语法上更简单（比如方法参数更改），因此有效建议的百分比更高，达到 98%。可以看出，大多数生成的语句序列都是有效的。我们将在第 7 节中讨论无效建议的主要原因。
图4 单个构建报错的 10 条修复建议中有效建议的分布
正确性：表 4 显示我们的测试集里，cant.resolve 的 36,101 个报错中有 18,051 个（50%）得到正确的修复建议，即该报错的 10 条修复建议中有一条和开发者的手动修复完全匹配。cant.apply.symbol 也得到了相近的正确率，即 2,687 个中有 1,263 正确（47%）。
排名：对于给出了正确修复建议的情况，我们评估正确建议在建议列表中的排序位置。图 5 描述了在 10 条修复建议中，正确建议的位置分布。数据显示大部分正确建议都排在第一位。cant.resolve 的正确修复有 85% 位于前三，cant.apply.symbol 的正确修复有 87% 位于前三。
图5 正确修复的位置分布
7 分析与风险
正确性：DeepDelta 在测试中为大约一半的构建失败提出了正确的修复建议。正确修复不是简单的二进制输出，而是由复杂的代码更改 AST 序列组成。与语法错误的理想修复率 27% 相比，我们的 50% 的正确率在实践中是相当可观的。这一相对较高的准确率可能归因于数据集和方法的以下特点：
- 在开发人员解决构建故障的方式中确实存在一些常规模式，DeepDelta 可以从修复更改中提取出这些模式。
- 我们的目标语言Delta是高度结构化的，模型因此得以用系统的方法学习模式。
无效序列：我们调查了导致无效建议的主要原因，可以归结为：
- 未知词例： 词例在推荐的目标序列中出现。模型预测给出一个向量化的嵌入，然后解码器尝试将其转换为词例。有时嵌入向量会与给定词汇表中的有效词例相距甚远，因此无法与高频词例相匹配。当某个故障的修复模式没有出现在模型学习过的模式之中，或者当词汇表不包含该词例（因为它不属于高频词例）时，就可能会发生这种情况。
- 不完整的序列：生成的语句序列丢失了部分 Delta 语法序列。这个问题在较长的序列（超过 90 个词例）上尤其容易发生，导致序列末尾出现单词丢失。
泛化能力：这些结果和技术有可能会无法推广到其他开发环境，比如在 IDE 广泛使用的情况下，不同的环境可能具有不同的常见诊断类型。虽然我们的数据集都来自同一家公司，但几乎所有项目都在 Google 的大型源码仓库中。因此我们的数据集做到了：
- 涵盖 10,000 以上 Java 项目，3 亿行代码。其中很多是开源项目，虽然只是 Google 主导开发的项目数据。
- 由来自世界各地、背景各异、成千上万的专业开发者，使用大约 5 种编辑器/IDE 进行的代码改动。
- 包含在两个月的时间内收集到的 110,219 个构建编译错误及其修复，超过 37,867 个 Java 文件和 7,011 个构建文件
所以我们有理由相信，我们的程序修复技术可以推广到任何其他相似的开发环境中，只要开发者解决诊断类型的方式具有某种模式。即便我们的模型学习和建议的修复方案无法在其他代码库和构建系统中使用，该技术本身是通用的，可适用于其他源代码库和构建系统。比如，假设我们要将外部项目的依赖添加到 Bazel 构建文件中，这个操作在其他构建系统也是广泛存在的。只要提供解析器来解析其他类型的构建配置文件（例如，用于 Maven 的 POM 文件，用于 Gradle 的 build.gradle），我们的系统就能学习以正确的方式添加依赖。
最常见的修复方式：我们可以使用生成的特征值来研究开发者如何解决编译错误。我们关心的是改动模式，因此我们在目标特征中用常量字符串（即'{X}'）替换标识符名称（如'ImmutableList'），将标识符名称抽象。然后使用带有 n-gram 分词器的 word2vec 模型将这些抽象特征向量化。再将特征向量输入到 k-means 算法中进行聚类，设置 k=20。表 5 给出了 cant.resolve 出现在六个最大聚类中的常见模式，该表包含每个聚类的模式描述、修复更改模式和具体示例。
可复制性：我们的数据集包含专有代码的 AST，但这些是无法发布的。我们的数据集是唯一的，因为它包含进行中的代码快照，而不仅仅是提交的代码。这种细粒度是整个方法可行的关键。我们目前还没有发现任何提供此类错误/修复详细信息的开源数据集。如果可以收集细粒度的开发者操作记录，并使用 Delta 语言规范和开源 TensorFlow NMT库，那么我们的成功是可以重现的。
诊断类型：我们的研究只采用了 Java 项目进行诊断。但是这项技术是通用的，区别只是 AST 的不同而已。唯一和语言相关的部分是用于构建 AST 的解析器。只要实现一下解析器，我们就可以对其他语言进行支持。
本篇论文中我们只关注两种错误类型（cant.resolve 和 cant.apply.symbol），原因有二：首先，这两个错误在 Google 开发者遇到的 Java 编译错误中占绝大多数，数量占比 59%，修复成本占比 58%（表 2）。我们的数据显示，无论其修复难度如何（R1），开发者都要花费大量时间去手动修复。自动化修复的方式可以释放开发者的人力，让他们可以将精力集中到其他问题上。其次，添加新的错误类型需要收集相关的开发者数据并重新训练模型，这非常耗时。
我们的结果表明，DeepDelta 对于两种修复模式不同的错误类型均适用。我们期望在其他构建错误类型上同样适用，并打算扩展对其他类型的支持。目前我们没有发现可以用来对比的其他修复 Java 编译错误的工具，最相似的研究是一篇在 C 语言里面修复语法错误（只包含一种类型）的文章[18]，其成功率要低得多。
可解析的 AST：我们的研究基于 AST 差异对比，因此出错的代码要支持 AST 解析。对于符号缺失的错误，代码始终可解析为唯一的 AST，但对于其他诊断类型则未必。可以对解析器的设计进行优化，不再采用快速失败（failing fast）机制，而是使用从语法错误中恢复的方式。如果要处理不完整的 AST，可能需要改成这种解析器。
8 未来规划
将 Delta 程序转为代码修改：Delta 程序本质上来讲是同一个程序两个版本之间的差异，DeepDelta 根据诊断输入预测该差异。对于预测给出的 Delta 程序，我们还要将其应用到未知程序中，尤其是要知道在哪里进行更改。在此我们大致描述下解决这一问题的想法，以几种常见的 Delta 更改为例。
看一下表 5 显示的 cant.resolve 的常见修复更改模式。对于“添加缺少的导入语句”和“删除导入”，我们不需要任何位置信息，因为导入必须位于 Java 源文件中的特定位置。对于“更改方法调用”和“更改缺少的符号”，我们从诊断文本可知丢失符号的位置，于是可以在该位置修改代码。对于“添加缺少的构建依赖项”和“更改构建依赖项”，我们知道哪个构建规则会产生错误，于是可以对其依赖列表进行更改。
总的来讲，我们根据构造（只有一个语法上有效的改动位置）或者诊断文本中的位置信息，一般都能找到合理的代码更改位置。
将代码修复工具落地：我们打算将 DeepDelta 集成到本公司（即 Google）开发者的开发环境中。为此，我们要在应用到用户代码之前先验证修复建议。我们打算搭一个应用，尝试性地将建议的修复应用到代码快照上并执行构建。然后我们可以丢弃无法编译的修复建议，只向用户提供可通过的修复建议。这里还要做一些有趣的交互，来确保该工具的易用性。
9 相关研究
提取更改模式：前文我们也曾提到从代码中提取更改模式。但是，大多数现有技术都需要预定义的规则或人工干预才能提取模式。Fluri 和 Gall [14]定义了 41 种基本的 Java 更改类型，并用层次聚类算法来研究复杂变更。Pan [37]使用 Unix 差异创建基本更改的数据库，并使用 Datalog 为更复杂的更改类型手动指定规则。
Liveshits 和 Zimmerman [26]提出了一种研究 API 使用模式的方法，通过对两个 Java 项目的代码历史进行关联规则挖掘来实现，他们使用这些模式来进行冲突检测。Kim 等[25]手动检查人工编写的补丁，并提取 Java 中的六个常见修复模式，之后他们将这些模式用于自动程序修复。
Hanam 等[19]提供了一种半自动的错误修复模式的检测方法，他们将解决运行时错误的语言构造 AST 更改提取为特征向量，使用聚类将它们分组为修复模式并排序，然后手动检查聚类以获取错误修复模式。而我们的方法不需要人工干预，还可以学习_未知的_修复更改模式。
通过示例进行合成转换：另一个相关的研究领域是代码转换技术，如 LASE [33]，Genesis [27]，NoFAQ [8]和 REFAZER [41]，可以对示例进行提取与合成语法转换。这些技术也有应用于程序修复的潜在可能。与我们的成果不同，它们以单个示例或少量示例进行操作；从海量示例中提取模式的效果则尚未可知，也不清楚要如何在程序修复的场景中应用它。
程序自动修复：我们的研究属于自动化程序修复领域，即通过自动化技术修复错误。程序修复现已应用于不同的领域，如数据结构[11,12]、用户界面[49]和各种编程语言的源代码，如 C [16,24,29]、Java [10,25]、JavaScript [36]和 PHP [42]（最好的语言）。
补丁搜索技术在实践中有许多缺点。首先，他们通常需要预定义的错误模式模板，无法学习新的模式。其次，补丁生成过程需要搜索巨大的程序空间，这可能需要很大的代价，因为要生成数千个补丁才能解决该故障。最后，研究表明它们会产生许多误报，也就是经常去修复测试失败的情况，而非实际错误。
程序修复的机器学习：Allamanis等[2]对采用机器学习进行源代码分析技术的最新进展的作了全面概述。Wang等[47]提出了一种故障预测技术，他们将代码的抽象语义特征提供给神经网络进行分类。Raychev等[40]使用神经网络来补全代码中缺失的 API 调用。Seidel等[43]通过监督式学习的分类方法实现目标类型错误定位。
Gupta等[18]提出了一种 seq2seq 机器学习方法来修复 C 语言中的语法错误。与我们的工作之间的主要区别在于，他们将出错版本和修复版本的整个源代码输入到网络，并实现了 27％ 的修复率。而我们只专注于学习故障的特征以及解决该故障的相关 AST 更改，这使我们可以实现更高的准确率（50％）。他们针对 C 语言中的语法错误，而我们针对 Java 中的构建时编译错误。另外，他们的测试样本使用小规模的学生作业，而我们的评估则是基于大量真实的开发者数据。
我们的论文是第一篇通过学习 AST 更改模式来解决编译错误的论文。针对构建错误的相关研究[20,31]与我们的不同：它们只专注于构建文件，而我们同时针对 Java 和构建文件；它们使用预定义的修复模板，而我们则学习修复模式；并且我们的规模更大，[31]和[20]分别使用了 37 个和 175 个故障，而我们用了 38,788 个故障来评估DeepDelta 算法。
10 总结
在本文中，我们研究了构建错误，以及开发人员如何更改代码去手动解决错误。我们证明了这样的代码更改中存在某种模式。我们提出了一种通用技术，从出错和修复版本中提取 AST 差异，用来学习代码更改模式。我们将自动程序修复定义为机器翻译问题。
我们的 DeepDelta 技术使用深度神经网络，可以根据构建诊断的输入推荐出修复的 AST 改动。我们对 Google 的大量真实开发者数据的评估表明，DeepDelta 在两种编译诊断类型上生成的修复建议正确率可达 50％，正确修复位于修复建议前三位的情况占 85％-87％。
我们的系统目前支持修复两种最耗时的诊断类型，即 cant.resolve 和 cant.apply.symbol。我们正计划扩展支持其他诊断类型。
广告时间
imgcook 专注以 Sketch、PSD、静态图片等形式的视觉稿作为输入，通过智能化技术一键生成可维护的前端代码，包含视图代码、数据字段绑定、组件代码、部分业务逻辑代码等。 我们期望 imgcook (图像大厨) 能够利用智能化手段，成为一位 P5 级别的前端工程师，在对设计稿轻约束的前提下实现高度还原，释放前端生产力，助力前端与设计师高效协作，让您关注更具挑战性的事情！
欢迎加入我们： [社招/校招] [杭州] [阿里淘系技术部-频道与 D2C 智能] 前端招聘：此时此刻，非我莫属！
参考文献
备注：仅保留相关研究中提及的文章，其余略。
[2] Miltiadis Allamanis, Earl T. Barr, Premkumar Devanbu, and Charles Sutton. 2017. A Survey of
Machine Learning for Big Code and Naturalness. arXiv preprint arXiv:1709.06182 (2017).
[10] Favio DeMarco, Jifeng Xuan, Daniel Le Berre, and Martin Monperrus. 2014. Automatic Repair of Buggy if Conditions and Missing Preconditions with SMT. In Proceedings of the 6th InternationalWorkshop on Constraints in Software Testing, Verification, and Analysis. 30–39.
[11] Brian Demsky and Martin Rinard. 2005. Data Structure Repair Using Goaldirected Reasoning. In Proceedings of the International Conference on Software Engineering (ICSE). 176–185.
[12] Bassem Elkarablieh, Ivan Garcia, Yuk Lai Suen, and Sarfraz Khurshid. 2007. Assertion-based Repair of Complex Data Structures. In Proceedings of the twentysecond IEEE/ACM international conference on Automated software engineering. ACM, 64–73.
[14] Beat Fluri and Harald C Gall. 2006. Classifying Change Types for Qualifying Change Couplings. In Program Comprehension, 2006. ICPC 2006. 14th IEEE International Conference on. IEEE, 35–45.
[16] C. Le Goues, T. Nguyen, S. Forrest, and W. Weimer. 2012. GenProg: A Generic Method for Automatic Software Repair. IEEE Transactions on Software Engineering 38, 1 (Jan 2012), 54–72. doi.org/10.1109/TSE…
[18] Rahul Gupta, Soham Pal, Aditya Kanade, and Shirish Shevade. 2017. DeepFix: Fixing Common C Language Errors by Deep Learning.. In Proceedings of the Conference on Arti.cial Intelligence (AAAI). 1345–1351.
[19] Quinn Hanam, Fernando S de M Brito, and Ali Mesbah. 2016. Discovering Bug Patterns in JavaScript. In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE). ACM, 144–156.
[20] Foyzul Hassan and Xiaoyin Wang. 2018. HireBuild: An Automatic Approach to History-driven Repair of Build Scripts. In 2018 IEEE/ACM 40th International Conference on Software Engineering (ICSE). IEEE, 1078–1089.
[24] Y. Ke, K. T. Stolee, C. L. Goues, and Y. Brun. 2015. Repairing Programs with Semantic Code Search. In Proceedings of the International Conference on Automated Software Engineering (ASE). IEEE Computer Society, 295–306. doi.org/10.1109/ASE…
[25] Dongsun Kim, Jaechang Nam, Jaewoo Song, and Sunghun Kim. 2013. Automatic patch generation learned from human-written patches. In Proceedings of the International Conference on Software Engineering (ICSE). 802–811.
[26] Benjamin Livshits and Thomas Zimmermann. 2005. DynaMine: Finding Common Error Patterns by Mining Software Revision Histories. In ACM SIGSOFT Software Engineering Notes, Vol. 30. ACM, 296–305.
[27] Fan Long, Peter Amidon, and Martin Rinard. 2017. Automatic Inference of Code Transforms for Patch Generation. In Proceedings of the 11th Joint Meeting on Foundations of Software Engineering. ACM, 727–739.
[29] Fan Long and Martin Rinard. 2016. An Analysis of the Search Spaces for Generate and Validate Patch Generation Systems. In Proceedings of the International Conference on Software Engineering (ICSE). ACM, New York, NY, USA, 702–713. doi.org/10.1145/288…
[31] Christian Macho, Shane McIntosh, and Martin Pinzger. 2018. Automatically Repairing Dependency-related Build Breakage. In 2018 IEEE 25th International Conference on Software Analysis, Evolution and Reengineering (SANER). IEEE, 106–117.
[33] Na Meng, Miryung Kim, and Kathryn S McKinley. 2013. LASE: Locating and Applying Systematic Edits by Learning from Examples. IEEE Press.
[36] Frolin Ocariza, Karthik Pattabiraman, and Ali Mesbah. 2014. Vejovis: Suggesting Fixes for JavaScript Faults. In Proceedings of the International Conference on Software Engineering (ICSE). ACM, 837–847.
[37] Kai Pan, Sunghun Kim, and E James Whitehead. 2009. Toward an Understanding of Bug Fix Patterns. Empirical Software Engineering 14, 3 (2009), 286–315.
[40] Veselin Raychev, Martin Vechev, and Eran Yahav. 2014. Code Completion with Statistical Language Models. In Acm Sigplan Notices, Vol. 49. ACM, 419–428.
[41] Reudismam Rolim, Gustavo Soares, Loris D’Antoni, Oleksandr Polozov, Sumit Gulwani, Rohit Gheyi, Ryo Suzuki, and Björn Hartmann. 2017. Learning Syntactic Program Transformations from Examples. In Proceedings of the 39th International Conference on Software Engineering. IEEE Press, 404–415.
[42] Hesam Samimi, Max Schäfer, Shay Artzi, Todd Millstein, Frank Tip, and Laurie Hendren. 2012. Automated Repair of HTML Generation Errors in PHP Applications Using String Constraint Solving. In Proceedings of the International Conference on Software Engineering (ICSE). IEEE, 277–287.
[47] Song Wang, Taiyue Liu, and Lin Tan. 2016. Automatically Learning Semantic Features for Defect Prediction. In Proceedings of the International Conference on Software Engineering (ICSE). ACM, 297–308.
