系列文章

引言

前面几篇文章，主要站在应用层面上对 bisect 进行讨论，本文章开始对底层进行解析。

进入正题前，不敢不先呈现一个文章 :

• 英语原文 : Fighting regressions with git bisect from Christian Couder
  • 你也可看 git 官网中不同排版的同内容文章 : git-bisect-lk2009
• 中文译文 ( 质量为 "机翻"…… 但如果英语不太好，还是可以比对着看看的 )

这篇文章，是本系列文章，最重度依赖的一个引用。无论在读本系列文章之前，或是之后，非常推荐一定要再找机会过一下。

所以，如何二分定位一个 commit ?

关于这个问题，原文章已经解释的很清楚，但是其叙述角度，更像是 "探索验证完毕，反过来提供正确答案并论证"。

因而，我们尝试从另一个角度来展开说明，假设我们不知道当前的最优解，给定 git bisect 的基础设定，我们如何在给定提交信息 (Good commits & Bad commit) 时，选取出一个 commit 以供下一次的检验呢?

Let's start

注意，关于一些 bisect 的基础设定，如果不清楚，推荐还是回顾一下之前的第一篇文章了解一下 :

线性提交的场景

要找到二分定位最佳 commit 的算法，我们先构造一个最简单的场景 : 完全线性的提交历史记录。

这种场景下要二分定位一个 commit 的话，应该非常容易，不假思索，毫无疑问，脱口而出地联想到 :

// 找中点

COMMIT_INDEX = floor( (FIRST_UNKNOWN_INDEX + LAST_UNKNOWN_INDEX) / 2 )

注意 :

• 如上的数字为 : commit 的虚构出来的 index
• floor 是为了处理 index 为整数的处理 ( 当计算出 x.5 时，x 或 x+1 是等价的最优 commit )

有合并提交的场景

线性场景挺简单，但是骨感的现实是，我们会有各式各样的分支，导致真正到手的总不太理想，更可能是一个符合 git 尿性的有向图，而不是一根骨感的线。

这种场景下，原来的中位 index 计算就不好实施了。我们需要其他更合理的处理模型，用于理解和计算。

先回到线性场景中，我们来考虑一下 "当选中一个 commit"，意味着什么?

1. 选取出一个 commit 之后，接下来就是要对其进行 "检验"，看看这个 commit 属于好提交，还是坏提交。
2. 确认完其状态之后，我们会利用 bisect 的设定，对当前剩余 commit 范围进行裁剪，剩下无法确认好坏的部分，则当做下一轮二分查找的范围
3. 循环以上过程，直至我们确定第一个坏提交，或者出现问题终止

假设选取一个 commit，那么它有可能是好的，也可能是坏的。假设如果是好提交，根据规则，下一轮剩余 X 个提交。坏提交的话，剩余 Y 个提交 (如下图)

那么我们为了避免进入最坏情况，我们会希望经过这轮检验之后，X 要尽可能接近 Y，也就是要尽可能地 "平衡" (全范围被二分)。那么我们可能得出如下的结论 :

如果每个 commit 被赋予一个数值 A，代表 : MAX( X, Y ) - MIN( X, Y )
那么, 被选取出来的 commit 的 A 要尽可能的小

以上的结论，也等同于如下两个版本 :

// 版本 a。

如果每个 commit 被赋予一个数值 A, 代表 : MAX( X, Y )
那么, 被选取出来的 commit 的 A 要尽可能的小

// 版本 b。

如果每个 commit 被赋予一个数值 A, 代表 : MIN( X, Y )
那么, 被选取出来的 commit 的 A 要尽可能的大

如下图所示 :

这几个不同的逻辑版本，可以用更直观的含义进行理解 :

类别	含义
MAX - MIN 取最小	选取最平衡的 => 避免最坏情况
MAX 取最小	最坏情况下，选取 "剩余数量" 最少的
MIN 取最大	最坏情况下，选取 "裁剪掉的数量" 最多的

小 tips : 同样，可以按照另一个角度来理解，比如说 "剩余数量" 最少，或 "裁剪掉的数量" 最多，等同于，检验选取出来的 commit 之后，能获得最大的信息量

为了让讨论更加聚焦，我们采用上述提到的文章中的角度，使用 "裁剪掉的数量" 来进行讨论。( 也就是 MIN( X, Y ) 这个权重值，方便起见，记为 M )。

于是问题可以进一步转换为 :

• 为待定的所有 commit 确定这个权重值
• 选取最大的权重值作为结果

另外，为了避免混淆，我们和上述文章以及本系列的前面章节保持一致，选择如下设定 :

• 每一次进行二分法查找时，待选提交的范围包含 : "未知好坏的提交" (一个或多个) & "坏提交" (一个)
  • 当未知提交为零个时，说明已经产生最后结果了，故不在讨论范围
• ancestors (祖先)，翻译为前置提交
• descendants (后代)，翻译为后续提交

如何确定 M ? ( 初步猜测 )

好的，有了一定的处理思路，那么 M 如何被确定呢?

还是回到线性场景中讨论 :

可以看到，无论选中的 commit 是好是坏，提交范围会被分为两组 :

• 第一组 : 选中提交本身 & 所有前置提交
• 第二组 : 原范围内的所有后续提交 ( 含原坏提交 )

因而，先做一个猜测 :

M = MIN( 前置提交数量 + 1, 后续提交 )

但这个猜测对么? 别着急，继续扩展一下场景，验证一下。

考虑合并场景，对 M 进行验证

以下用一个提交结构为例，这个例子简单，但可代表很多的类似场景。

这里可通过两个区域 (区域 A, B) 进行分析，也就是选取的 commit 可能位于这两个区域的其中一个。另一个分支和区域 B 属于对称情况，故不用单独讨论。

首先，看看选取的 commit 被判定为好提交的情况 (下图)。从图中可确认，在这种情况中，无论 commit 落在哪一个位置，被裁剪掉的数量，等于所选取 commit 的前置提交数量 + 1，符合上述的猜测。

其次，再看看选取的 commit 被判定为坏提交的情况 (下图)。如果选取 commit 来自区域 A，那么符合后续提交数的猜想，但如果来自区域 B，裁剪掉的提交不仅仅是所选取 commit 的后续提交，而是连并行分支中的提交都可以排除掉。这个情况，与上述猜想不一致。

事实上，上图中的 C1 ~ C4，并不能被确定是好提交还是坏提交，只是根据 bisect 的基础设定，当我们知道区域 B 某个提交为坏提交时，我们并不需要关注他们的状态。如下图，我们想要找的引入错误的提交，必然是存在于区域 B 或者区域 B 再往前的提交。因此，它们亦可被裁剪。

利用上面的分析，推导出一个更合理的计算方式 :

M = MIN( 前置提交数量 + 1, 待选提交总数 - (前置提交数量 + 1) )

同时，这个公式在线性场景中，也是符合所有之前的要求。或者说，之前的猜测，等价于这个计算公式一种在线性场景中的 "特例"。

算法总结

综上分析，git bisect 的二分查找算法，可简化为如下的表述 :

参考文章

• 英语原文 : Fighting regressions with git bisect from Christian Couder
• 你也可看 git 官网中不同排版的同内容文章 : git-bisect-lk2009
• 中文译文 ( 质量为 "机翻"…… 但如果英语不太好，还是可以比对着看看的 )

系列文章

作者信息