algorithm - 通过平分(搜索)修订历史和不可测试的提交(修订)来查找错误

Question

大多数现代版本控制工具都有一个命令，可以通过对历史记录进行二进制搜索(二等分)来查找引入错误的更改。这样的命令可能是内置的，也可能作为扩展或插件提供。示例包括 git-bisect在 Git 中，“hg bisect”在 Mercurial 中(早期以 hbisect 扩展名提供)，以及 bzr-bisect Bazaar 插件。

挑战在于即使在存在非线性历史记录(分支点和合并)的情况下，也要以自动或半自动的方式执行此操作。目标通常是在最少的步骤中找到“坏”修订，或者更详细地找到要测试的提交，如果可能的话，将要测试的提交图(提交的 DAG)分成两半。这个问题我觉得很好解决。

但是不可测试的提交有一个问题，例如如果某些修订代码甚至无法编译，或者如果编译它不会启动/运行(或发现与您正在搜索的错误无关的错误)。这意味着您现在有 三种 可能的状态，而不是简单地将提交标记为“好”或“坏”:

• 好 - 错误不存在
• 差 - 错误行为
• 未知(不可测试)- 不知道错误是否存在

一些版本控制系统 (SCM) 允许您“跳过”此类提交，通常转到父修订版作为下一个要测试的版本。

---

问题是:

• 如果您处理过这种情况，这意味着您使用了二分法并偶然发现了不可测试的修订，根据您的经验，这种不可测试的提交的分布情况如何？它们是孤立出现的(单个不可测试的提交)，还是出现在范围内(修订版 a..b 是不可测试的)？您是否发现自己处于必须一次又一次地跳过提交的情况？

• 是否有一些数学模型(例如用于简单平分列表/线性历史，甚至用于平分任意 DAG 修订版)或算法(可能是启发式)，可以优化跳过不可测试的提交。目标再次是在存在不可测试的提交(或不相关的错误)的情况下(平均)最小化要测试的版本数量。

• 除了允许简单地“跳过”不可测试的提交之外，您是否使用版本控制系统，或版本控制系统的一些附加/扩展/插件，或一些实现此类算法的第三方工具邻居修订？这个 VCS 或工具是什么？它使用什么算法(如果你知道的话)？

希望这会导致更容易(半)自动查找错误...

---

添加于 06-06-2009:
在使用 Git 的高级功能时，有一种情况是您可以拥有整个 分支 不可测试的提交(或至少难以测试)，即您使用“子树 "合并以加入两个独立项目的历史记录(例如，完整的 Linux 内核和一些使用“子树”合并单独开发的驱动程序)。在提出处理不可测试提交的算法时，需要考虑这一点:对于非线性历史，可能存在不可测试提交的整个分支，并且算法必须(某种程度上)考虑拓扑。

Answer 1

显然，已 checkin 的内容无能为力。我处理过的大型代码库需要所有 checkin 才能实际构建。这是通过让开发人员将他们的更改提交到 checkin 服务器来完成的，该服务器将有一个更改队列等待进入。每个更改都是按照提交的顺序为所有目标平台构建的。如果构建失败，则拒绝 checkin 。如果成功，将运行一套自动回归/单元测试。如果任何测试失败， checkin 将被拒绝。如果成功，则 checkin 将提交到存储库。

如果您有这样的系统，它会大大减少不可构建/不可测试的修订的数量。糟糕的构建仅限于仓库管理员在 checkin 服务器之外做古怪的事情。

在不存在此类选项的环境中，我没有进行严格的统计分析，但我发现在一些情况下会发生一些无法构建的修订。一次 checkin 会弄乱很多东西，然后会有一系列小的 checkin 试图纠正困惑。然后事情通常会好一段时间。