案例研究
PDF程序合并：深度学习与它有什么关系？
与 Shuvendu Lahiri、Alexey Svyatkovskiy、Christian Bird、Erik Meijer 和 Terry Coatta 的讨论
如果您经常使用开源代码或为大型组织制作软件，您已经熟悉大规模协作编程带来的许多挑战。其中一些最棘手的问题往往会因为对代码进行的许多独立更改而浮出水面，不出所料，这可能会导致更新无法同步。
当然，困难的合并并非新鲜事，但问题的规模已经变得更加严重。这促使 MSR（微软研究院）的一组研究人员将复杂的合并作为一项宏大的程序修复挑战来承担——他们认为机器学习可能至少在一定程度上解决这个问题。
为了理解导致这项工作的想法，然后跟踪它的发展方向，我们请 Erik Meijer 和 Terry Coatta 与 MSR 研究工作的三位主要人物进行了对话，该工作名为 DeepMerge （“DeepMerge：学习合并程序”，微软研究院）。Meijer 长期以来一直是 MSR 的成员，但在本次讨论时是 Meta 的工程总监。Coatta 是 Marine Learning Systems 的首席技术官。Shuvendu Lahiri 和 Christian Bird 是推动这项工作的两位研究人员，他们代表 MSR，Alexey Svyatkovskiy 也是如此，他当时在微软 DevDiv（开发部门）。
TERRY COATTA 最初是什么启发您关注合并冲突？是什么让您认为可以通过应用 AI 技术来获得一些优势？
CHRISTIAN BIRD 回到 2020 年冬天，我们中的一些人开始讨论如何利用机器学习来改善软件工程的状况。我们当然认为现在是投入到这方面的努力的合适时机，希望能够获得足够的能力来启动相关的研究计划。
我们试图找出其他研究人员尚未解决的问题，这意味着像代码完成这样的问题——人们已经研究了相当长一段时间——很快就被排除了。相反，我们转向了开发人员还没有太多帮助的问题。
Shuvendu [Lahiri] 在符号角度研究程序合并方面有着悠久的历史，而我自己的重点更多地与理解程序合并过程中发生的更改有关。当我们讨论这个问题时，我们突然意识到似乎没有人从事程序合并工作。然而，对于开发人员来说，这是一个仍然几乎无所依靠的问题。在大多数情况下，我们只是查看不同代码版本之间的差异，看看是否能弄清楚到底发生了什么。但是，除了这些之外，目前几乎没有工具可以提供帮助，这在需要解决合并冲突时可能会成为问题。
因此，我们认为，“好吧，让我们看看如何将一些深度学习模型应用于这个问题。在进行过程中，我们可能还会发现一些其他可以做的事情来以此为基础进行构建。”
SHUVENDU LAHIRI 是的，正如 Chris 所建议的那样，我思考这些问题已经有一段时间了。此外，我们发现程序合并很有吸引力，因为它是一个协作问题。也就是说，即使两位熟练的开发人员进行了正确的更改，合并本身也可能引入错误。
我们也敏锐地意识到程序合并问题可能造成的痛苦，这在我们对微软内部的研究中已经了解到了（“开发人员希望和需要程序分析什么：一项实证研究”，微软研究院）。我认为也许我们可以做些什么来减轻痛苦。而且，事实证明，当时人工智能刚刚兴起，Alexey [Svyatkovskiy] 已经开发了几个功能强大的模型，这些模型在代码完成方面看起来非常有前景。更重要的是，关于合并冲突的信息才刚刚开始更容易从 Git 提交历史记录中获得，因此这看起来也可能成为一个良好的前期清洁数据来源。
ERIK MEIJER 我喜欢你们专注于合并冲突这一事实，因为当涉及到这个问题时，我认为源代码控制并没有解决任何实际问题。也许我在这里有点极端，但即使源代码控制让您知道哪里有合并冲突，它也不会在您实际解决冲突时提供任何帮助。事实上，我不明白为什么这个问题很久以前没有以智能方式解决。人们只是不听取实际用户的抱怨吗？
SL 基本上，我认为这归结为学者们一直以来都求助于符号方法来解决这个问题。而现实世界中的人们则将此视为编程的另一个方面，从业者更倾向于将其视为一个社会过程——也就是说，最好通过鼓励同事共同找出解决方案来解决这个问题。就我个人而言，我一直认为合并冲突更像是一个工具挑战。
ALEXEY SVYATKOVSKIY 对我来说，这看起来只是一个令人兴奋的软件工程问题，可以通过机器学习来解决。我已经花了多年时间研究代码完成，但这项工作看起来像是将代码完成提升到了更高的复杂程度，因为它必然会涉及以某种方式对齐多个序列，然后再补充对应该插入、删除或交换的位置的理解。而且，当然，还有一些特殊情况，开发人员可以在合并期间添加新标记。
这带领我们踏上了一段旅程，最终我们在行和标记级别解决了程序合并问题。我发现这很吸引人，因为很多人根本不了解合并的实际工作原理，因此，推而广之，也不清楚是什么导致了合并冲突。解决这个问题似乎也很重要，因为虽然合并冲突远不如软件错误常见，但它们需要花费更多的时间来解决，并且最终可能会造成更多的痛苦。
TC 您最初是如何着手解决这个问题的？
SL 我们意识到存储库（GitHub 上的开源存储库和微软内部的存储库）包含关于跨多种不同编程语言的合并冲突及其解决方案的数据。更重要的是，Alexey 最近创建了一个神经模型，该模型已经在这些存储库中代码的很大一部分子集上进行了预训练。我们最初的想法是用关于合并冲突及其解决方案的信息来微调该模型。我们认为这应该足够简单，可以作为实习生项目来处理。所以，这就是我们最初的范围。我们认为：只需获取数据，训练模型并部署。我们没有理解的是，虽然有大量的程序合并数据可以挖掘，但理解所有这些合并背后的意图至少与数据本身同等重要。事实上，它被证明绝对至关重要。
需要大量的时间和精力来理解和解释数据。这包括一些重大的技术挑战。例如，如何最好地对齐这些程序？以及如何向神经模型传达这些不是独立的程序，而是表示对底层程序的若干更改？如何从程序文本转变为程序编辑的概念变得至关重要，实际上，这需要大量的研究。最终，我们得出结论，如果您能够正确地组合现有的合并工具，添加适当的粒度——对于我们来说，这被证明是标记——然后采用神经建模，您通常可以成功地降低复杂性。但这花费了我们相当长的时间才弄清楚。
当然，我们也低估了用户体验的重要性。用户究竟将如何使用这样的工具——一个基于 AI 的工具？以及何时才是展示该工具的正确时机？
TC 我发现正确地确定这个项目的范围如此困难，这真是令人着迷。您能否更深入地探讨一下？
AS 至少对我而言，当我们分析不同类型的合并时，很快就清楚地意识到合并的复杂程度各不相同。有时我们会发现自己正在研究两种简单的合并解决方案策略，这实际上归结为“采用我们的或采用他们的”。当然，这种情况很容易分析，并且开发人员在解决这些冲突时不需要太多 AI 帮助。
但还有另一类合并，其中引入了新的交错行，这不仅仅涉及连接。也可能存在标记级交错，其中代码行已被断开，并在中间引入了新标记。这导致了臭名昭著的复杂情况，在这种情况下，切换到标记级粒度被证明至关重要。除此之外，还有另一类合并，您会发现有人引入了一些新标记。
EM 您如何定义您认为的正确合并？这是否需要在某种程度上做出您自己的价值判断？
SL 嗯，我只想说我们有一种非常语义化的看待合并的方式。本质上：“忘记语法；相反，合并的意义是什么才是正确的？”实际上，这相当于：如果一个程序中的某些内容被更改了，那么这应该反映在合并中。而且，如果这也改变了行为，那么也应该包含在合并中。但不应引入其他更改或更改的行为。
然而，我们随后发现，每当我们遇到这些“采用我的更改或采用您的更改”的合并之一时，我们都会陷入困境。我们还发现，一组更改通常会被直接删除——就像分支被弃用一样，正如 Alexey 曾经指出的那样。这就是我们发现我们最初的正确性概念并不总是成立的原因。这也是我们意识到我们不应该坚持过于语义化的概念的原因。
因此，我们决定尽最大努力来管理训练数据，尽可能删除任何“采用您的更改或采用我的更改”的迹象。然后，我们查看了那些在某种程度上结合了两种更改的地方，并说：“好的，这现在是我们的真实情况——我们对什么是正确的概念。”但请注意，这是经验正确性，而不是语义正确性——也就是说，我们不得不从我们最初对语义正确性的崇高抱负中退缩。
AS 我们现在将从 GitHub 提交历史记录中检索的用户解决方案视为我们的真实情况。但是，是的，当然，有各种各样的方法来定义“正确”的合并。例如，可以重新排序结构化合并中的语句，但仍然最终得到功能上等效的解决方案。然而，这将被视为“不正确”，因此，显然有重新调整我们对正确性定义的空间。但是，在这种情况下，我们选择采用数据驱动的方法，将来自 GitHub 提交历史记录的用户解决方案视为我们的真实情况。
CB 对。还让我说一下，从这个项目开始，我们就决定将其作为可能产生产品的项目来对待。考虑到这一点，我们意识到它需要具有语言不可知性，或者至少是可以轻松适应多种语言的东西——并且绝对不是需要为每种语言定制分析框架的东西。这基本上指导了我们选择不采用更丰富或更复杂的代码表示形式。
EM 我也遇到过类似的情况，在这种情况下，使用 AST [抽象语法树] 或类似的东西看起来非常诱人，因为这将提供所需的所有结构。但是，随着您深入研究这类项目，您会发现自己想知道将语义丰富的程序输入模型并开始认为最好只发送字符串是否真的是一个好主意。
TC 为了更深入地探讨这个问题，您有使用基于标记的方法的实际动机。但是，当您这样做时，您的直觉告诉您模型会如何表现？如果您向模型输入丰富、结构化的信息集，那么该模型是否真的更有可能做出更好的决策？或者这可能是一个错误的假设？
AS 我认为模型应该能够做出更好的决策。
EM 好的，但我可以稍微挑战一下吗？模型可以处理语法和语义分析，这表明这项工作可能不需要提前完成，因为机器看待代码的方式与人类不同。我不知道为什么模型不能构建自己的内部表示，然后在过程结束时让类型检查器介入。
CB 我认为推测模型可能能够做什么或可能不能做什么是有风险的。我的意思是，这是一个非常细致入微的问题，因为它取决于模型的训练方式以及架构——以及许多其他因素。我总是惊讶地了解到模型现在能够做什么。而且，在这种情况下，我们谈论的是 2020 年的世界状况——即使我现在发现很难记住 GPT 模型普及之前六个月的世界状况。
SL 首先，我们使用预训练模型来处理分类和生成，这给我们留下了大量的工作要做，即在调整性能之前，在 AST 级别表示生成的编辑。这当然被证明是一个复杂的问题——并且伴随着一些额外的计算成本。另外，我记得，我们当时使用的模型已被训练为代码的文本表示——这意味着我们需要在更多的 AST 级别表示上训练它们才能获得更好的性能。我相信，如果回到 2020 年重新审视我们当时做出的一些决定，那将非常有趣。
EM 您现在使用什么模型？
AS 对于这个迭代，我们采用标记级合并以及基于 Transformer 的分类器。我们还一直在研究使用基于 GPT-4 的提示驱动方法。
EM 我喜欢现在您可以利用已证明的偏好来解决合并冲突，而不是仅仅依靠您自己的观点。
SL 在我们的用户研究中提出的另一种看待这个问题的方式是，即使在生成合并之后，有人可能想知道为什么以这种特定方式完成合并，甚至可能想看到一些关于推理的证据。嗯，这是一个棘手的问题。
但是，关于这些大型基础模型的一个优点是，它们能够生成对它们所做工作的文本描述。尽管如此，我们还没有深入探索这种能力，因为我们现在实际上没有可用的手段来评估这些描述的真实性。这必须等到一些用户研究为我们提供更多数据后才能进行。尽管如此，我认为这里有一些令人着迷的可能性，最终应该能够减少在使用这些 AI 动力工具完成某些关键任务时似乎出现的某些摩擦。
如果您经常使用开源代码，您肯定已经熟悉在尝试解决合并冲突的过程中可能出现的一些挑战。自从人们开始协作编写程序以来，就遇到了许多此类问题，并且随着软件规模和复杂性成倍增加，这些问题也已扩散。此外，由于有时现在有成千上万的开发人员协作处理项目，冲突的可能性只会继续飙升。
当然，其中许多冲突可能导致程序失败。但在某些方面更糟糕的是更微妙的语义合并冲突，这些冲突可能导致编译器失败、破坏测试或引入回归。尽管存在这些痛苦的明显问题，但程序合并问题在很大程度上被搁置了几十年，仅仅是因为解决它的挑战似乎如此艰巨。
TC 您提到您可以访问大量训练数据，但您也暗示其中一些数据包含惊喜——也就是说，事实证明它既是祝福也是诅咒。您能否更深入地探讨一下？
SL 是的，我们惊讶地发现，很大一部分合并——可能占 70%——具有只选择编辑的一方然后删除另一方的属性。在某些情况下，似乎一个编辑正在取代另一个编辑，但当语法稍有变化时，很难确定。在许多情况下，有真正的编辑被丢弃了。目前尚不清楚这是否是由于工具问题或社会问题——也就是说，在某些情况下，也许是高级开发人员的更改取代了初级开发人员的更改。另一种假设是，有些人可能选择合并多个提交而不是单个合并。
这种事情非常普遍，以至于它占据了数据的重要组成部分，起初让我们不确定是否应该丢弃这些实例、忽略它们，还是以某种方式努力解释它们。这当然被证明是我们遇到的更大的惊喜之一。
另一个惊喜是，我们发现了一些与合并无关的新标记被引入的实例。起初尚不清楚这些是由于合并中真正的冲突造成的，还是仅仅因为有人在进行重构时决定添加一个漂亮的打印语句。这被证明是我们的另一个棘手问题。
TC 您是如何解决这个问题的？听起来您有一些不太清楚如何解释的数据集。那么，您是如何决定哪些应该被归类为正确的合并，哪些应该被视为不正确的合并？
SL 我们管理了一个不包括“琐碎”合并解决方案的数据集，目标是首先帮助用户处理更复杂的情况。正如 Alexey 提到的，用户可能不需要工具支持那些只需要删除两个编辑中的一个的解决方案。
AS 然后，从用户研究中，我们了解到一些用户仍然希望能够使用已被驳回的方法。我们通过提供用户可以使用下拉菜单访问的“B 选项”来解决了这个问题。
SL 也就是说，我们通过用户体验而不是通过更改模型来解决这个问题。
我们遇到的另一个数据问题与偶尔出现的新标记有关。经过仔细检查，我们发现这些标记通常与现有更改有关。通过下降到标记级合并，我们能够消除其中许多方面。最终，我们构建了一个模型，该模型排除了数据集中引入新标记的部分。
EM 就您的工作方式而言，我了解到您特别依赖的工具之一是 Tree-sitter [一种用于构建语法树的解析器生成器工具]。您能否告诉我们它在您的整体开发过程中所起的作用？
CB 我们立即被 Tree-sitter 吸引，因为它允许您直接解析几乎任何您可以想象到的东西。而且它提供了统一的 API，这与大多数其他解析器不同，后者每个都带有自己的 API，并且仅适用于一种或另一种语言。
尽管如此，我还是惊讶地得知 Tree-sitter 不提供标记化 API。例如，对于为什么这对我们来说是一个问题，我们想尝试 Python，它基本上让每个人都处理自己的标记化。但是，当然，Tree-sitter 在这方面没有帮助。我们求助于 Python 标记化库。
除了这个相对较小的抱怨之外，Tree-sitter 在让您将算法应用于一种语言，然后快速将其扩展到许多其他语言方面非常出色。事实上，凭借这种能力和 Python 标记化库（使我们能够处理多种语言），我们能够尝试其他语言的东西，而无需投入大量的前期努力。当然，仍然存在获取训练模型所需的所有数据的问题，这始终是一个挑战。至少我们不需要编写自己的解析器，并且统一的接口已被证明非常有益。
EM 一旦您最终成功部署了所有这些，您最大的惊喜是什么？
CB 惊喜太多了。我特别记得的一个惊喜是在我们试图弄清楚人们甚至希望如何查看合并冲突和差异时出现的。起初，我们中的一些人认为他们只想关注冲突本身——也就是说，以一种让他们看到自己一方和另一方的视图。事实证明，您还需要能够看到基础分支，以了解基础分支和您的分支之间的不同含义。
因此，我们进行了一项 Twitter 调查，以了解人们认为我们应该展示多少内容。他们甚至想看到多少内容？例如，我记得，大多数人甚至无法理解三向差异的概念，或者至少没有期望看到任何类似的东西。这真的让我大吃一惊，因为我不知道如果他们不确切地知道自己面临什么，任何人怎么可能期望确定性地解决冲突。
还出现了一些其他问题，UI 人员可能会预料到，但我仍然感到非常惊讶。这被证明是一个巨大的挑战，因为我们在这个整个过程中一直认为，只要我们有空，我们就会着手处理 UI。是的，正如这表明的那样，我们最初的趋势只是专注于确保底层算法有效。但是，后来我们惊讶地发现，找到与之关联的正确 UI 可能有多么困难。
TC 从您所说的来看，似乎您对需要良好的用户体验并不感到惊讶，但您确实惊讶地得知什么是被认为是良好的体验。您现在对什么构成良好的合并用户体验有什么看法？
CB 即使到现在，我也不完全清楚这一点，但我很乐意分享我们早期学到的一些关于这方面的事情。正如我们已经讨论过的那样，人们绝对希望看到合并的双方。除此之外，我们发现他们希望能够研究合并中每个部分的来源，因为他们想知道每个标记来自哪里。
因此，我们编写了一些代码来跟踪每个标记，一直追溯到它来自的任何一方。
也有来自双方的标记。为了清楚地表明标记的来源，我们一直在纠结是否应该添加颜色作为指示。这也可以用来指示标记是来自双方还是仅仅是新的？
此外，我们知道界面不应该只是要求您单击“是”或“否”来响应建议的更改，因为很少有任何合并是 100% 正确的。也就是说，开发人员将希望能够修改代码，并且任何拒绝他们这种机会的界面最终都会让他们感到沮丧。
真正的挑战在于，任何给定的合并中都有许多移动的部分。因此，有很多可能的视图，但您仍然希望保持足够简单，以避免让用户感到不知所措。这是一个真正的挑战。例如，我们知道，如果我们为合并提供三个建议而不是一个，则选择最佳建议的机会要高得多。但这也会增加复杂性，因此我们最终决定建议最有可能的选项，即使这有时可能会导致不太理想的结果。
还有一些其他值得注意的用户体验考虑因素。例如，如果您正在处理某些特定的 Visual Studio 功能，您将希望生成一些对于一直使用该工具的人来说感觉直观的东西。可以说，在这方面有很多值得思考的地方。基本上，一旦您最终让您的模型工作，您可能甚至还没有完成一半的路程，因为用户体验方面的工作就是如此关键——而且耗时。
是的，用户体验实际上很重要——即使用户恰好是开发人员。因此，在这种情况下，启动了一项重要的用户研究，该研究的受试者是 MSR 自己的技术人员。
另一个有趣的方面是，研究参与者被呈现了从他们自己的工作中提取的代码示例。当然，这方面的意义在于，它不仅涉及真实世界的示例，还涉及所有与每个重要决策点相关的权衡和含义肯定会被研究对象充分理解的示例。
也就是说，这项练习被证明对所有参与方来说都是一次有趣的學習经历。
TC 我们都知道，为内部目的创建工具是一回事，而将其转化为产品则是另一回事。看来你们在这里经历了这段旅程，那么你们在此过程中遇到的更大的惊喜是什么？
SL 实际上，我们还没有实现 DeepMerge 算法的产品，也无法谈论如何在未来的产品中使用它。尽管如此，正如我们刚刚讨论的那样，我可以说我们遇到的大多数不寻常的挑战都与用户体验的各个方面有关。因此，我们在这里比通常情况下更深入地研究了这个问题。
最大的挑战之一是如何确定需要展示多少信息才能让用户相信刚刚完成的事情甚至有可能——更不用说合适了。突然，您就在这里引入了一些新标记，以及那里的新可解析树。我认为这真的会让一些用户感到困惑。
CB 从 DevDiv 的角度来看，这一切看起来如何，Alexey？您一直与客户打交道。在那里，最大的挑战是什么？
AS 一些最关键的设计决策归结为选择客户端或服务器端实现。我们主要关注的是我们之前讨论过的新合并算法。从用户研究和早期采用者那里获得的客户反馈被证明对于找到平滑过渡的方法至关重要。当然，这有助于确定需要改进的领域，例如在将 A 合并到 B 与将 B 合并到 A 时实现更好的对称性。
SL 我想补充几点。一是有些开发人员宁愿自己处理这些合并。当工具用于处理他们自己可以做的事情时，他们只是看不到工具的价值。但这只是导致了一些惯性，如果没有大量的使用，这种惯性总是很难克服。尽管如此，从我们的实证研究中，我们了解到，即使合并与真实情况不完全相同，如果它们被证明在语义上是等效的，用户也会接受它们。最终，这被证明是一个令人愉快的惊喜，因为它揭示了我们之前在成功指标方面低估了我们的胜利。
TC 沿途还有其他有趣的事情出现吗？
CB 有一次，我们的一位实习生做了一项用户研究，从微软的历史存储库中提取了合并冲突及其解决方案，以便将它们与我们的工具将应用的解决方案进行比较。正如您可能想象的那样，出现了相当多的差异。为了了解我们的工具可能在哪里出错，我们回去咨询了那些参与原始合并的人员，并向他们展示了他们所做的事情与该工具如何解决相同合并冲突之间的比较。
我们特别关注了过去三个月内已解决的冲突，前提是人们可能还记得这些决策背后的原因。通过这次特别的实践，我们学到了很多。其中一个教训是，我们可能低估了我们做对事情的频率，因为一些开发人员会说这样的话：“嗯，这可能与我做的合并不完全一致，但我无论如何都会接受它。”
该研究的另一个主要好处是，它深入了解了我们工具的用户体验应该是什么样的。这一切对我来说都是一个重大的启示，因为这是我第一次参与以这种方式进行的用户研究——开发者被邀请进来，并展示他们实际处理过的代码。
这只是想说明，这完全不像那些让人们解决玩具问题的实验室研究。在这种情况下，我们引入了真实世界的合并冲突，然后与那些致力于解决这些冲突的开发人员进行了交谈。通过采取这种方法，我们学到了很多，我建议其他研究人员也考虑以大致相同的方式进行自己的研究。
AS 这些用户研究的另一个成果是可解释性的重要性。例如，对于大型语言模型，我们可以深入研究特定的三向差异及其提出的解决方案，然后要求对某些决策进行总结，这在建立对某些 AI 建议的信心方面可能很有帮助。
此外，正如 Chris 指出的那样，即使当用户选择不采用 DeepMerge 提供的解决方案时，该建议背后的理由似乎仍然影响了他们自己的思考，并经常促成更佳的合并解决。
TC 接下来是什么？
SL 在确定模型的输入内容方面，提示工程还有更多空间。我们还需要解决相关冲突。到目前为止，我们将每个冲突都视为独立的，但是在一个文件中可能会有多个冲突都与某个依赖项相关。一些用户告诉我们，一旦解决了其中一个冲突，他们希望看到类似的方法应用于其他表现出类似模式的冲突，这当然似乎非常合理。
此外，虽然到目前为止我们处理的冲突类型在本质上是高度句法的，但实际上，合并冲突有一个完整的范围。还有很多问题需要解决，包括包含语义冲突的静默合并，这比我们迄今为止处理的任何问题都更难处理。不过，我想说，感觉我们已经有了一个相当好的开端。
版权 © 2024 由所有者/作者持有。出版权已许可给 。
最初发表于 Queue vol. 22, no. 4—
在 数字图书馆 中评论本文
© 保留所有权利。