Jak*_*ski 5 algorithm debugging version-control
大多数现代版本控制工具都有一个命令来查找通过二进制搜索(二等分)历史记录引入错误的更改.此类命令可能是内置的,也可能是作为扩展或插件提供的.例子包括Git中的git-bisect,Mercurial中的" hg bisect"(早期可用作hbisect扩展)和Bazar的bzr-bisect插件.
即使存在非线性历史(分支点和合并),挑战在于以自动或半自动方式进行.目标通常是在最少的步骤中找到"坏"修订,或者更详细地找到提交以测试哪个,如果可能的话,将提交的图提交到测试(提交的DAG)的一半.我认为,这个问题很好地解决了.
但是不稳定的提交存在问题,例如,如果某些修订代码甚至没有编译,或者如果它编译它不会启动/运行(或找到与您正在搜索的错误无关的错误).这意味着您现在有三种可能的状态,而不是简单地将提交标记为"好"或"坏".
某些版本控制系统(SCM)允许您"跳过"此类提交,通常转到父修订版作为下一个要测试的版本.
问题是:
如果您处理了这种情况,意味着您使用了二分法并偶然发现了不可测试的修订,那么您的经验是什么,这些不可测试的提交的分发？它们是单独发生的(单个不可测试的提交),还是它们出现在范围内(修订版本a..b是不可测试的)？您是否发现自己处于提交后必须跳过提交的情况？
是否有一些材料模型(比如列表/线性历史的简单二等分,甚至用于二等分修改的任意DAG)或算法(可能是启发式),它允许优化跳过不可测试的提交.目标是再次在存在不可测试提交(或不相关的错误)的情况下最小化(平均)测试版本的数量.
您是否使用版本控制系统,或某些附加/扩展/插件用于修订控制系统,或者某些实现此类算法的第三方工具,除了允许通过转到邻居修订简单地"跳过"不可测试的提交？这个VCS或工具是什么？它使用什么算法(如果你知道的话)？
希望这会导致更容易(半)自动发现错误...
添加06-06-2009:
当使用Git的高级功能时,有一种情况是你可以有一个完整的untestable提交分支(或者至少很难测试),即你使用" subtree "merge来连接两个历史单独的项目(例如,使用"子树"合并单独开发的一些驱动程序的完整Linux内核).在提出处理不稳定提交的算法时需要考虑这一点:对于非线性历史,可以存在整个不可稳定提交的分支,并且算法必须考虑拓扑(在某种程度上).
您可以将二分/二分搜索算法的各个元素重新定义为具有相邻“未知”状态的修订范围，而不是单个修订。
换句话说，如果在二分搜索期间发现未知状态，则开始向前和向后进行子搜索，以找到为您产生明确答案的修订范围的边界。这可能是两个方向的线性搜索，所以它会慢一些，你必须假设大多数修订不是不可测试的。
然后，这最终将输出出现错误的一系列修订版本，例如修订版本 (58,63) 之间的某个位置。然后您必须手动搜索该范围。
| 归档时间： |
|
| 查看次数： |
678 次 |
| 最近记录： |