作者：寻壑

DEF 在 FY 22 S1 基于 KAITIAN 纯前端版本实现了 O2 CodeReview，由于 IDE 形式的特点，用户所看到的不论是待审阅版本还是基础版本代码，都是跟一个具体的 commit 版本相对应的，通过 IDE 的能力来进行 Diff，而不是传统 CR 工具的存储、消费 Diff 信息的做法。这一特点给我们的 CR 工具带来了更多的灵活性，但另一方面也决定了我们不能够直接使用底层的 Diff 数据来展示 CR，需要自己去确定待对比版本信息。

图 1.1 IDE diff视图与常规diff信息展示

已审阅代码自动跳过是 CR 工具的一个重要的功能，假设我有一个大的 feature 分支需要开发，那么比较推荐的做法是根据能力的实现拆分多次进行迭代，进行阶段性 CR，每一次 CR 都只会看到基于已审阅的版本的增量信息（版本对应一个代码 push 行为），降低审阅成本，提高审阅质量。基于 Diff 数据来实现的 CR 工具一般会通过 Diff 信息的减法算法来处理这一类情况。假设我们在第一次 CR 时对应的完整 Diff 信息如图 1.2.1，最终的完整 Diff 信息如图 1.2.2，那么我们需要去实现一个 diff2 ㊀ diff1 的算法，使得最终的结果如图 1.2.3 就可以了。在基于 commit 版本做 CR 的场景下，我们也无法延用底层系统的这一套算法，需要自行去处理。

图 1.2 已读版本自动跳过

我该使用哪两个版本对比？

三向合并

在介绍我们的算法之前，先简单介绍一下 Git 分支合并的基础策略：三向合并。

假设我们从主干分支切出了分支 fix1，在 fix1 的 src/index.js 处修改了 24 行处的一行代码，现在我想要把该分支合回主干，Git 怎么知道它该不该把这一行改动合进去呢？如果只看主干分支对应行代码的话（hello word），它无法确定哪一行才是你真正想要的代码，所以这个时候它需要去找出 fix1 和主干分支的公共祖先节点，也就是我们说的 mergeBase（后文简称 base），去对比这一行代码原来是什么，才能够确定该怎么处理。比如说发现 base 上就是 hello word，那么说明主干分支这一行还没有任何改变，直接把 fix1 的改动合进去就好了；如果发现 base 上原来是 hello werd，那就要提示冲突，让合并的人自己来决定哪个才是他想要的代码。

图 2.1 三向合并

我们在 CR 时是判断我们的代码合入主干会带来哪些变化，所以 CR 时所采用的基础版本也是 mergeBase。在和主干分支没有发生冲突的情况下，我们所看到的变化最后就是合入主干的变化。

mergeBase 的获取

传统的 CR 工具在数据层面都是围绕 Diff 信息来做处理的，在 CR 代码有更新时，直接通过 git diff —merge-base 去计算一次实时的 Diff 信息落库，后续做查询就可以了，而不会去做 mergeBase 信息落库。而一般的 IDE CR 工具由于有 Git 环境，直接通过命令 git merge-base 来计算就可以了。一方面，纯前端 IDE 的场景下这些信息的获取都依赖底层服务，若需要单独的 mergeBase 信息需要底层服务排期去支持，有一定的改造成本；另一方面，仅获取 mergeBase 的版本，而不知道整体 commit 树的构造信息，也会制约我们进一步实现版本拆分等相对复杂的能力。

作为一个成熟的代码管理平台，Aone 提供了分支对比能力，我们可以拿到这个分支相比于主干分支多出来的 commit 列表，同时这些 commit 信息都有一个 parent_ids 字段来标识它的父节点是哪些 commit，借助于这一基础能力，我们可以把这个分支的提交信息构造出一个“版本链”，比如：

[
  {
    "author_email": "hui.hongh@alibaba-inc.com",
    "author_name": "灰灰",
    "committer_email": "hui.hongh@alibaba-inc.com",
    "committer_name": "灰灰",
    "created_at": "2020-09-17T18:13:52+08:00",
    "id": "4810d0faf6602dac68e447235f7a0e1da31d721e",
    "message": "权限申请\n",
    "parent_ids": [
      "05cbd07eae346f6d246b5430b268d6963c8e4c25"
    ],
    "short_id": "4810d0fa",
    "title": "权限申请",
  },
  {
    "author_email": "hui.hongh@alibaba-inc.com",
    "author_name": "灰灰",
    "committer_email": "hui.hongh@alibaba-inc.com",
    "committer_name": "灰灰",
    "created_at": "2020-09-21T16:33:32+08:00",
    "id": "c33cbf35cea4516659fd40364a1736cc5b4acd09",
    "message": "增加日志查看\n",
    "parent_ids": [
      "4810d0faf6602dac68e447235f7a0e1da31d721e"
    ],
    "short_id": "c33cbf35",
    "title": "增加日志查看"
  }
]

从这个 commit 数据构造出来的版本链如下图所示（ 05cbd 不属于当前分支，且为第一个提交的 parent_id）：

图 2.2 基础的 commit 形式图

我们可以很直观的看出来，这种场景下两个分支的 mergeBase 就是分支切出来时候的那一个commit 节点。直接取 commit 列表里最早那个 commit 的 parent_id 就是我们想要的 mergeBase。

节点的 parent_id 可能不止一个，在发生了 Git 合并的操作、且两个分支都含有对方没有的代码时（非 fast-forward 场景，具体合并形式可以参考文章《这才是真正的Git——分支合并》），新的提交会是一个合并节点，这个节点会有两个 parent_id，如下图所示：

图 2.3 合并主干的版本链

合并操作使得两个分支之间多了一个新的公共组件节点，也就是合并节点的不属于当前分支的那个 parent_id（图中红色箭头节点），这样我们的分支和主干之间就有了两个 common ancestor。

按照 mergeBase 的定义，当有一个以上的公共祖先节点时，我们要取路径最短的那个作为 mergeBase。反馈到我们的算法上，我们在往前回溯寻找公共祖先节点时，找到的第一个点就是我们想要的 mergeBase。

mergeBase定义：One common ancestor is better than another common ancestor if the latter is an ancestor of the former. A common ancestor that does not have any better common ancestor is a best common ancestor, i.e. a merge base. Note that there can be more than one merge base for a pair of commits.

考虑如下的一种场景，我们在切出目标分支进行开发的时候，中途又尝试切了一个小的特性分支进行开发，开发完成后又合回到了目标分支，此时会产生一个新的合并节点。但是由于这个合并节点的两个 parent_id 都属于当前分支，因而是不能作为 mergeBase 的。

图 2.4 要注意中间可能合入了其他分支

到目前为止我们的算法可以很准确的判断出哪个节点才是真正的合并节点，但是由于信息量的问题，在合并节点的两个 parent_id 都不属于当前分支时（同时意味着由于接口限制，我们还无法获取这两个节点除了 id 以外的更多信息），我们该如何判断该取哪个节点作为 mergeBase 呢？

这种场景会比较少见，但是作为一个底层的 CR 工具，自然是无法限制用户的 commit 行为的。在切出新分支的第一个提交恰好是一个合并节点的场景下（通过 git merge non-fast-forward 选项可以在满足 fast-forward 策略的情况下仍然生成合并节点），这里的 parent_id 就会有两个，以下面的数据为例：

[
  {
    "author_email": "hui.hongh@alibaba-inc.com",
    "author_name": "灰灰",
    "committer_email": "hui.hongh@alibaba-inc.com",
    "committer_name": "灰灰",
    "created_at": "2020-09-17T18:13:52+08:00",
    "id": "4810d0faf6602dac68e447235f7a0e1da31d721e",
    "message": "权限申请\n",
    "parent_ids": [
      "83918b756b3045be62858ec1e622470efa9b3b21",
      "05cbd07eae346f6d246b5430b268d6963c8e4c25"
    ],
    "short_id": "4810d0fa",
    "title": "权限申请",
  },
  {
    "author_email": "hui.hongh@alibaba-inc.com",
    "author_name": "灰灰",
    "committer_email": "hui.hongh@alibaba-inc.com",
    "committer_name": "灰灰",
    "created_at": "2020-09-21T16:33:32+08:00",
    "id": "c33cbf35cea4516659fd40364a1736cc5b4acd09",
    "message": "增加日志查看\n",
    "parent_ids": [
      "4810d0faf6602dac68e447235f7a0e1da31d721e"
    ],
    "short_id": "c33cbf35",
    "title": "增加日志查看"
  }
]

图 2.5 mainline 场景 commit 形式图

通过肉眼可以很轻易的判断 05cbd 为更新的代码，但是在数据层面，我们只有一个 parent_ids 数组 ["83918", "05cbd"] ，唯一的信息是二者的先后顺序，从这个数组的顺序能唯一确定两个节点的先后顺序吗？这个时候要了解一下底层系统的实现。相信大家这时候会想起一个场景，在想要 revert 一个合并节点的时候，git 会弹出一个报错：

error: commit xxx is a merge but no -m option was given

这个 -m 就是所谓的 mainline，由于合并时创建了一个合并节点，由合并节点回溯时有两条路径可以走，Git 不知道你想要使用哪一条 commit 路径作为主线。我们会使用 git revert -m 1 来回归到主干的上次提交，使用 git revert -m 2 来回归到合入分支的上次提交，这个顺序是固定的。回到我们的问题的话，第一个 parent_id 可以确定是属于主干本身的最近一次提交，第二个 panrent_id 就是主干合入的最近一次提交，我们要作为 mergeBase 的，肯定是合入分支的最近一次提交了，也就是 parent_ids[1]。

git revert mainline: Usually you cannot revert a merge because you do not know which side of the merge should be considered the mainline. This option specifies the parent number (starting from 1) of the mainline and allows revert to reverse the change relative to the specified parent.

上述场景在推导的过程中有一个基本的假设，即靠后的节点的 parent_id 也相对靠后，实际上这一假设是不一定成立的。考虑一种相对极端的场景，由于发生了 squash merge，导致虽然按照回溯算法下面那个公共祖先节点更靠前，但是实际上其提交时间远远早于实际的分支切出点，mergeBase 获取错误。

图 2.6 squash merge 导致 mergeBase 获取出错

mergeBase 的分析算法在 O2 CodeReview 的起步阶段帮我们解决了绝大多数场景的 CR 需求，但是由于信息的缺失仍然有部分场景无法支持。近期在底层系统的支持下，我们已经切换到了 git 原生的 mergeBase 获取算法上，能够保证完全可靠的提供正确的 diff 信息。

我该跳过哪部分代码？

两种场景

在传统的 CR 工具中，版本跳过只需要实现一个 Diff 信息的减法算法即可，即从特定版本到最新代码的 Diff 信息 revision ~ head = base ~ head ㊀ base ~ revision（其中 revision 指最近一次审阅过的版本，head 指最新版本），思路比较清晰。但是在 IDE 的场景下，由于我们消费的是特定版本的文件内容而不是 Diff 信息，需要重新思考已审阅变更跳过的实现方式。

还是先思考一个最简单的场景，用户切出一个新的分支，在 commit 1 节点处完成了base ~ revision的审核。之后用户又做了两次 commit，同时推送代码触发 CR 的 reopen，毫无疑问，审阅版本1到最新代码的变更时，直接取 commit 1和最新的代码做对比就可以了。

图 3.1 基础的版本跳过实现

在一般情况下，revision ~ head 的对比确实只需要把 revision 的最新版本用来作为基础版本就可以了，base ~ revision 的代码是用户已经审阅过的，直接把这一部分跳过就能够实现跳过已审阅变更代码的目的。但是如果 mergeBase 在用户推送新代码的过程中发生了变化，比如在版本2中合并了最新的主干分支，那么再取 commit 1 作为基础版本的话，就会反而在变更代码中出现从主干合入带来的新变更，加重了审阅负担（事实上，基于落库的 Diff 信息减法算法，base 变化也会导致作为减数的 base ~ revision diff 信息不正确）。

图 3.2 base 变化的版本跳过情况

算法实现

回归到问题本身，我们的目的是希望在用户审阅过版本 1 的代码之后，在不引入旧的 base ~ 新的 base 带来的变更的前提下，不要再出现用户已经审阅过的内容（后文 base 均指 newBase）。和基于 Diff 的跳过算法有所区别，我们认为用户已经审阅过的内容是对应 revision 的版本内容，而不是 oldBase ~revision 的 diff 信息。所以最终的实现方式用一句话来概括，就是 把 base ~ head 有变化且 base ~ revision 有变化的部分（取 diff 区域的交集，base 删除内容和右侧新增内容分别取交集），使用 base ~ revision 的变更来替代原本 base 的内容，而保证新版代码严格不变。

图 3.3 算法的简单推导

取 base ~ head 和 base ~ revision 的交集，可以剔除来自 base 变化的代码变更（如图 3.2 所示，newBase ~head不会包含 oldBase ~newBase 引入的代码变更，而 newBase ~revison 是包含这部分信息的，取交集就可以消除这一影响）；使用 base ~ revision 来代替 base，可以帮助我们跳过已经审阅过的变更。具体的算法可以参考下图：

图 3.4 base 内容使用交集 revision 内容做 patch 具体案例

CR 阶段化

DEF 的 CR 之前跟 ChangeFree 一样，作为一个发布卡口存在，导致用户在做 CR 时，总是在发布的最后一刻才提交 CR 单，一方面紧急的发布需求会导致审阅人无法及时的看完 CR 信息，另一方面一次性大量的代码变更对审阅质量会有非常致命的影响。在下一阶段，DEF 会进一步去优化 CR 的流程，以我们的 CR 版本跳过算法为基础，把 CR 融入到迭代的日常流程当中，实现 CR 的阶段化：

图 4.1 CR 阶段化

CR 融入研发流程

提升 CR 质量的另一个重要途径是将其融入到开发者的研发流程中，DEF 目前的 CR 能力均是基于 KAITIAN 插件体系搭建的，下一阶段我们会将这一能力迁移适配到研发态 IDE 的插件中，落地到 DEF 的 WebIDE 和本地 IDE 中，一方面充分利用操作系统的能力以实现更好的代码跳转等 CR 体验，另一方面通过补全 DEF 作为发布系统在开发流程中的缺位，进一步感知开发过程中的代码变更信息，实现 CR 质量的提升与研发提效：

图 5.1 CR 融入研发流程

结语

mergeBase 的分析属于特定阶段的过渡工作，在后续底层系统有直接获取 git merge-base 结果的能力时，自然会退出历史舞台。但是 git 版本链的构建、分析过程，仍然会在版本跳过算法等后续的特性中继续发光发热。另外由于个人能力有限，目前的算法可能仍然存在一些场景没有覆盖到，欢迎大家批评指正。

CR 的阶段化与发布系统的结合是 DEF 在研发态能力建设方面的一个重要探索，借助于 IDE 环境、远程库 Hook 等能力，把 CR 的变更信息更完善、更及时的透出给开发者，减少单次评审代码量，减轻评审负担。后续我们也会在 CR 阶段中接入智能化评审能力，通过机器学习辅助决策的方式，进一步提升开发者的 CR 幸福感。