代码之家 › 专栏 › 技术社区 › Jakub NarÄbski adamtaub

通过平分(搜索)修订历史和不稳定的提交(修订)来查找错误

version-control debugging algorithm

Jakub NarÄbski adamtaub · 技术社区 · 16 年前

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

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

例如,如果某些修订版代码甚至没有编译,或者它编译后没有启动/运行(或者发现与您正在搜索的错误无关的错误)。这意味着,不再简单地将提交标记为“好”或“坏”,而是现在有了三

好的 -错误不存在
-童车行为
未知的 ( )-不知道是否存在错误

某些版本控制系统(SCM)允许您“跳过”此类提交,通常将其作为下一个测试版本发送到父版本。

问题包括:

是否有一些数学模型(例如用于列表/线性历史的简单平分,甚至用于平分修订的任意DAG)或算法(可能是启发式的),可以优化不稳定提交的跳过。目标再次是在存在不稳定提交(或不相关的bug)的情况下最小化(平均)要测试的版本数。
除了允许通过转到相邻版本来简单地“跳过”不稳定的提交之外,您是否使用版本控制系统,或版本控制系统的某些附加/扩展/插件,或实现此类算法的某些第三方工具?这个VCS或工具是什么?它使用什么算法(如果你知道的话)?

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

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

3 回复 | 直到 16 年前

i_am_jorf 16 年前

显然,已经登记的情况是无法帮助的。我开发的大型代码库需要所有的签入来实际构建。这是通过让开发人员将他们的更改提交到签入服务器来实现的,该服务器将有一个等待进入的更改队列。每个更改都是按照提交顺序为所有目标平台构建的。如果生成失败,则拒绝签入。如果成功,将运行一套自动回归/单元测试。如果任何测试失败,则拒绝签入。如果成功,签入将提交到存储库。

如果您有这样一个系统,它将显著减少无法构建/不稳定修订的数量。糟糕的构建仅限于站点管理员在签入服务器之外做奇怪的事情。

在没有这样一个选项的环境中,我没有硬的统计分析,但我发现轶事般的不可构建的修订发生在口袋里。一次办理登机手续会把一大堆事情搞砸,然后会有一系列的小办理登机手续试图纠正这些混乱。然后,一段时间内情况一般都很好。

Chris Harris 16 年前

您可以将二分法/二进制搜索算法的各个元素重新定义为具有相邻“未知”状态的修订范围,而不是单个修订。

换句话说,如果在二进制搜索过程中发现未知状态,则开始向前和向后执行子搜索,以找到为您生成明确答案的修订范围的边界。这可能是在两个方向上的线性搜索,因此速度会稍慢,您必须假设大多数修订都不稳定。

然后,这将最终输出一系列出现错误的修订,例如修订之间的某个地方(58,63)。然后,您必须手动搜索此范围。

Brian Ewins Brian Ewins 16 年前

只是一个想法:我知道你正在考虑的另一个问题是在有噪音的情况下进行测试。考虑跳过的一种方法是将其视为随机响应的好/坏,并使用对此类错误具有鲁棒性的对分算法,例如: http://www.disp.uniroma2.it/users/grandoni/FGItcs.pdf “存在内存故障时的最佳弹性排序和搜索”。一、菲诺基、F·格兰多尼和G·F·意大利人。

知道哪些点不可靠,所以你可以回溯。