💻 computer science

Combining Example-Based and Rule-Based Program Transformations to Resolve Build Conflicts

本文介绍了 BuCoR（构建冲突解决器），这是一种通过结合基于规则的预定义策略与基于示例的分支版本挖掘技术，来有效检测并自动解决软件合并过程中构建和测试冲突的新工具。

原作者： Sheikh Shadab Towqir, Fei He, Todd Mytkowicz, Na Meng

发布于 2026-02-13

📖 1 分钟阅读☕ 轻松阅读

原作者： Sheikh Shadab Towqir, Fei He, Todd Mytkowicz, Na Meng

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文介绍了一个名为 BuCoR 的新工具，它的任务是帮助程序员解决在合并代码时遇到的“灾难性”错误。

为了让你更容易理解，我们可以把软件开发想象成两个厨师（左厨师和右厨师）在各自独立的厨房里，根据同一份原始食谱（基础版本）做不同的改良菜，最后要把这两份改良版合并成一道新菜的过程。

1. 什么是“构建冲突”？（The Problem）

想象一下：

左厨师把食谱里的“糖”改成了“蜂蜜”。
右厨师把食谱里的“糖”改成了“代糖”，并且把原本用来放糖的碗也拆了。

当你们试图把这两份食谱强行拼在一起时，新食谱里会出现混乱：有的地方写着“加蜂蜜”，有的地方写着“加代糖”，甚至有的地方还在找那个已经被拆掉的“糖碗”。

在编程世界里，这就是构建冲突（Build Conflict）。它不仅仅是文字上的打架（比如两个人在同一行写了不同的字），而是逻辑上的死胡同：代码拼在一起后，编译器会报错，程序根本跑不起来。

以前的工具只能像“文字校对员”一样，告诉你们“这里打架了”，但很少能告诉你们“怎么打平”。

2. BuCoR 是什么？（The Solution）

BuCoR 就像是一个拥有双重超能力的“超级主厨”。它不只会看文字，还能理解逻辑。它通过两种策略来解决问题：

策略 A：模仿大师（基于示例的转换 - BuCoR-E）

比喻：看“错题集”找灵感。

原理：BuCoR 会去翻看左厨师或右厨师在之前的厨房里，有没有遇到过类似的问题，以及他们当时是怎么巧妙解决的。
怎么做：
- 比如，左厨师之前把“糖”改成“蜂蜜”时，不仅改了名字，还顺手把装糖的勺子换成了木勺，把量杯的刻度也改了。
- 现在合并时，BuCoR 发现右厨师把“糖”改成了“代糖”。于是它想：“既然左厨师改糖的时候连勺子和量杯都一起改了，那我也应该把右厨师的‘代糖’相关的勺子和量杯一起改过来，而不仅仅是改个名字。”
优点：它能解决那些非标准、很复杂的问题，因为它是在“模仿”人类开发者的真实智慧。

策略 B：死记硬背规则（基于规则的转换 - BuCoR-R）

比喻：查阅“标准操作手册”。

原理：有些冲突是非常常见的，就像“把 A 改成 B，所有叫 A 的地方都要改成 B"。BuCoR 预先背下了 16 种常见的“标准解法”。
怎么做：
- 如果冲突只是简单的“改名”，BuCoR 会直接套用规则：“哦，这是 C1 类冲突，直接全局替换名字就行。”
优点：速度快，处理那些老生常谈的问题非常高效。

3. BuCoR 是怎么工作的？（The Process）

BuCoR 的工作流程就像是一个侦探 + 建筑师的组合：

侦探阶段（检测冲突）：它先不看代码能不能跑，而是像侦探一样，拿着放大镜对比三份食谱（原版、左版、右版），找出哪里逻辑不通。
绘图阶段（构建图谱）：它把代码里的类、方法、变量画成一张巨大的关系网（图谱）。这就像把厨房里的所有食材、工具、步骤画成一张复杂的地图，这样它就能看清“糖”和“勺子”之间到底有什么关系。
双管齐下（解决问题）：
- 它先试试模仿大师（BuCoR-E）：在地图里找有没有类似的“改错案例”，如果有，就照着画。
- 如果没找到案例，它就试试标准手册（BuCoR-R）：看看是不是那种常见的 16 种情况之一，直接套用公式。
最终输出：它会把修改好的新食谱（代码）交给程序员检查。

4. 效果怎么样？（The Results）

研究人员拿 BuCoR 去测试了 88 个真实的、棘手的代码冲突案例（涵盖了 21 种不同的“灾难”类型）。

覆盖率：BuCoR 成功给出了至少一种解决方案的有 65 个（占 74%）。也就是说，大部分冲突它都能想办法。
准确率：在它给出的所有方案中，有 52% 是完全正确且符合人类开发者意图的。
- 其中，“模仿大师”策略（BuCoR-E）虽然尝试得少，但准确率高达 75%（因为它更懂上下文）。
- “标准手册”策略（BuCoR-R）尝试得多，但准确率只有 39%（因为有些情况不能死板套用）。

结论：这两个策略是互补的。就像你既需要“灵活变通的创意”，也需要“稳扎稳打的规则”，BuCoR 把它们结合在了一起。

总结

这篇论文的核心思想是：解决代码合并冲突，不能只靠死板的规则，也不能只靠死记硬背。

BuCoR 就像是一个聪明的助手，它既懂得举一反三（从过去的错误中学习如何修复），又懂得按章办事（利用已知的标准解法）。它不仅能告诉程序员“这里错了”，还能像一位经验丰富的老厨师一样，告诉你“把糖换成蜂蜜，顺便把勺子也换了，这样菜才好吃”。

这大大减轻了程序员在合并代码时的痛苦，让软件更新变得更顺畅、更安全。

这是一篇关于解决软件合并过程中构建冲突（Build Conflicts）的学术论文《Combining Example-Based and Rule-Based Program Transformations to Resolve Build Conflicts》的详细技术总结。

1. 研究背景与问题 (Problem)

在协同软件开发中，开发者经常需要将不同分支的更改合并到主分支。合并过程中会产生两类冲突：

文本冲突 (Textual Conflicts)：同一代码片段被不同分支修改，导致无法自动合并。
构建与测试冲突 (Build and Test Conflicts)：即使文本能自动合并，合并后的代码也可能因为语义不兼容（如符号重命名、类层次结构变化、方法删除等）导致编译错误或测试失败。

现有工具的局限性：

现有的工具（如 Gmerge, MrgBldBrkFixer）主要依赖编译器错误信息或简单的符号重命名规则。
它们通常只能处理符号重命名导致的冲突。
它们无法处理更复杂的冲突，如类层次结构变化、方法/参数的增删、以及需要系统性修改上下文代码的复杂场景。
缺乏自动化的解决方案，开发者往往需要花费大量时间手动修复。

2. 方法论 (Methodology)

作者提出了 BuCoR (BUild COnflict Resolver)，一种结合基于示例的转换 (Example-Based) 和 基于规则的转换 (Rule-Based) 的新型混合冲突解决工具。

核心流程

BuCoR 接收三个版本作为输入：基线版本 ( $b$ )、左分支 ( $l$ ) 和右分支 ( $r$ )。

冲突检测 (Conflict Detection)：利用静态分析工具 Bucond 构建程序实体图 (PEG)，对比 $l, r, b$ 之间的差异，识别导致构建错误的冲突对（例如： $l$ 重命名了类， $r$ 却引用了旧类名）。
图构建 (Graph Construction)：生成自动合并版本 $A_m$ ，并构建四向互联图 ( $G_b, G_l, G_r, G_{Am}$ )，用于定位冲突上下文和锚点。
混合解决策略：
- BuCoR-E (基于示例的转换)：
  - 原理：利用“分支上的构建错误修复”与“合并冲突解决”之间的共性。如果开发者在分支中通过特定编辑修复了定义（def）与使用（use）的不匹配，BuCoR 会挖掘这些示例编辑 (Exemplar Edits)。
  - 步骤：
    1. 挖掘示例：在贡献了定义变更的分支中，寻找调整了相关用法的编辑示例。
    2. 模式推断：利用 GumTree 提取 AST 编辑脚本，并通过控制流和数据流依赖分析，提炼出最小化的转换模式 (Transformation Pattern)，去除无关上下文。
    3. 模式应用：在自动合并版本 $A_m$ 中，以“使用点”为中心进行自底向上的上下文匹配。如果匹配成功，则应用推断出的模式（包括变量名、字面量、方法调用等的同步修改）。
- BuCoR-R (基于规则的转换)：
  - 原理：针对频繁出现的冲突类型，预定义 16 种常规解决规则。
  - 覆盖范围：不仅包含符号重命名，还涵盖类层次结构变化（如父类方法参数变更导致子类需更新）、接口实现变更、重复定义移除等。
  - 机制：当 BuCoR-E 无法找到示例或冲突类型符合预定义规则时，BuCoR-R 会尝试应用相应的规则进行修复。

3. 关键贡献 (Key Contributions)

BuCoR 工具：首个将基于示例的学习与基于规则的推理相结合，专门用于解决构建冲突的静态分析工具。
先进的基于示例方法 (BuCoR-E)：
- 不同于现有工具仅做简单的符号替换，BuCoR-E 利用程序依赖分析从分支历史中提取复杂的修复模式。
- 实现了上下文匹配和模式定制，能够处理非标准化的、项目特定的复杂编辑（如同时修改变量名、字面量和方法调用）。
基于规则的方法 (BuCoR-R)：
- 定义了 16 种解决常见构建冲突的常规规则，填补了现有工具在处理非重命名类冲突（如类层次、参数列表变更）方面的空白。
系统性评估：
- 在 30 个开源 Java 项目中构建了包含 88 个真实构建冲突的数据集，涵盖 21 种冲突类型。
- 开源了工具代码和数据集。

4. 实验结果 (Results)

实验在 88 个真实构建冲突上进行评估，主要指标为覆盖率 (Coverage) 和 准确率 (Accuracy)。

覆盖率：
- BuCoR 整体为 65/88 (74%) 的冲突生成了至少一个解决方案。
- BuCoR-E 覆盖了 28 个 (32%)，BuCoR-R 覆盖了 51 个 (58%)。两者互补，BuCoR-E 擅长处理非标准/项目特定冲突，BuCoR-R 擅长处理常规冲突。
准确率：
- BuCoR 整体正确解决了 34/88 个冲突，生成的 79 个解决方案中有 41 个 是正确的，准确率为 52%。
- BuCoR-E：准确率高达 75% (21/28)。它生成的解决方案更符合开发者的意图，因为它模仿了项目内的具体修复模式。
- BuCoR-R：准确率为 39% (20/51)。虽然覆盖率高，但在处理复杂语义变更时容易出错（例如，规则建议重命名，但开发者实际选择了删除或重构）。
对比分析：
- 在两者都生成解决方案的 14 个案例中，BuCoR-E 通常提供更优的解决方案。
- BuCoR 成功解决了 19 种冲突类型，仅在 C19 和 C22 两种类型上失败（缺乏示例且无通用规则）。

5. 意义与价值 (Significance)

超越现有工具：BuCoR 突破了现有工具仅能处理“符号重命名”的局限，能够处理类层次结构、参数变更、定义删除等更复杂的构建冲突。
混合智能策略：证明了将“数据驱动的示例挖掘”与“知识驱动的规则推理”相结合，能有效平衡冲突解决的覆盖率和准确性。
自动化潜力：BuCoR 展示了自动化工具在解决复杂语义冲突方面的潜力，减少了开发者手动处理构建错误的时间，提升了软件合并的效率和软件质量。
未来方向：研究指出了未来改进方向，包括扩展规则集、改进在无本地示例情况下的挖掘能力，以及探索更鲁棒的 AST 节点匹配算法。

总结：BuCoR 通过结合从历史分支中学习的“具体修复经验”和预定义的“通用解决规则”，显著提高了自动解决软件构建冲突的能力，为更智能的自动化合并工具提供了新的研究范式。