通过平分（搜索）修订历史和不可测试的提交（修订）来查找错误 [英] Finding bugs by bisecting (searching) revision history, and untestable commits (revisions)
问题描述
挑战是以自动或半自动的方式进行，即使存在非线性历史（分支点和合并）。目标是通常以最少的步骤找到坏修订，或者在更详细的地方找到一个提交来测试如果可能的话，将提交的提交图（DAG）分成两半。这个问题解决了，我觉得很好。
但是，不可推荐的提交有一个问题，例如如果某些修订代码甚至不编译，或者编译时，它不会启动/运行（或查找与您正在搜索的bug无关）。这意味着您现在可以使用三个可能的状态：
- 好 - 该错误不存在
- 不好 - 越野车行为
- unknown （ untestable ） - 不知道是否存在错误
版本控制系统（SCM）允许您跳过这样的提交，通常作为下一个测试的父版本。
$ b $问题是：
-
如果你处理了这样的情况，意思是你使用二分法，偶然发现不可测试的修订在你的经验中，这种不可测试的提交的分布是什么？它们是孤立发生的（单个不可测试的提交），还是出现在范围内（修订版本a..b是不可测试的）？你是否发现自己在提交后不得不跳过提交的情况？
-
是否有一些伴侣模型（就像有简单的等分列表/线性历史，甚至平分任意DAG的修订）或算法（可能启发式），这允许优化跳过不可尝试的提交。目标是在存在不可逾越的提交（或无关的错误）的情况下，最大限度地减少（平均）测试版本。
-
您是否使用版本控制系统或一些用于修订版控制系统的附加/扩展/插件，或者实现这种算法的一些第三方工具，除了允许简单地通过去邻居修改跳过不可尝试的提交之外？这是什么VCS或工具？它使用什么算法（如果你知道的话）？
希望这将导致更简单（半）自动化发现错误...
添加06-06-2009：
当使用Git的高级功能时，有一种情况可以让您的整个分支不可尝试的提交（或至少难以测试），即您使用的位置子树合并到两个独立项目的历史中（例如，使用子树合并单独开发的一些驱动程序的完整Linux内核）。这是需要考虑的，当提出一个算法来处理不可逾越的提交：非线性历史可以有一个完整的分支的不可逾越的提交，并且算法必须考虑拓扑（有点）。
显然，检查的内容无法帮助。我所工作的大型代码库需要所有的入门级才能实际构建。这是通过让开发人员将其更改提交给登记服务器来完成的，该服务器将具有等待进入的更改队列。每个更改按照提交的顺序为所有目标平台构建。如果构建失败，则拒绝签入。如果成功，则会运行一套自动回归/单元测试。如果任何测试失败，登记入住将被拒绝。如果成功，登记将被提交到存储库。
如果您有这样的系统，它大大减少了不可修改/不可测试的修订版本数量。糟糕的构建局限于仓库管理员在登入服务器之外进行古怪的事情。
在不存在此选项的环境中，我没有硬统计分析，但是我发现口袋里出现了无法修改的修改。一次登机会弄乱一大堆东西，然后有一系列的小型入境登记，试图纠正这个混乱。那么事情一般都很好。
Most modern version control tools have a command to find a change that introduced a bug by binary search (bisecting) of a history. Such command might be built-in, or it might be provided as extension or plugin. Examples include git-bisect in Git, "hg bisect" in Mercurial (earlier available as hbisect extension), and bzr-bisect plugin for Bazaar.
The challenge is to do it in an automatic or semi-automatic way even in the presence of nonlinear history (branching points and merges). The goal is in general to find "bad" revision in minimal number of steps, or in more detail to find a commit to test which, if possible, divides graph of commits to test (DAG of commits) in half. This problem is solved, I think, very well.
But there is a problem with untestable commits, e.g. if for some revision code doesn't even compile, or if it compiles it doesn't start/run (or finding bug unrelated to the one you are searching). This means that instead of simply marking commit as "good" or "bad", you now have three possible states:
- good - the bug is not present
- bad - buggy behavior
- unknown (untestable) - not known if the bug is present
Some version control systems (SCM) allow you to "skip" such commits, usually going to the parent revision as the one to test next.
Questions are:
If you dealt with such situation, meaning you used bisection and stumbled upon non-testable revisions, what is in your experience the distribution of such non-testable commits? Do they occur in isolation (single un-testable commit), or do they appear in ranges (revisions a..b are untestable)? Did you find yourself in a situation where you had to skip commit after commit?
Is there some matematical model (like there is for simple bisecting of list / linear history, and even for bisecting arbitrary DAG of revisions) or algorithm (perhaps heuristic), which allow to optimize skipping of untestable commits. The goal is again to minimize (in average) number of versions to tests in the presence of untestable commits (or unrelated bug).
Do you use version control system, or some add-on / extension / plugin for revision control system, or some third-party tool which implements such algorithm, beside allowing to simply "skip" untestable commits by going to neighbour revision? What is this VCS or tool? What algorithm does it use (if you know it)?
Hopefully this would lead to even easier (semi)automated finding bugs...
Added 06-06-2009:
When using advanced features of Git, there is one situation where you can have a whole branch of untestable commits (or at least hard to test), namely where you use "subtree" merge to join histories of two separate projects (e.g. full Linux kernel with some driver developed separately using "subtree" merge). This is something to consider when coming up with an algorithm to deal with untestable commits: with nonlinear history there can be a whole branch of untestable commits, and algorithm has to take into account the topology (somewhat).
What's been checked in, obviously, cannot be helped. The large code bases I've worked on required all check-ins to actually build. This was done by having developers submit their change to check-in server which would have a queue of changes waiting to go in. Each change is built for all target platforms in the order it is submitted. If the build fails, the check-in is rejected. If it succeeds, a suite of automated regression / unit tests are run. If any test fails, the check-in is rejected. If it succeeds, the check-in is committed to the repository.
If you have such a system in place, it dramatically reduces the number of unbuildable / untestable revisions. Bad builds are limited to depot administrators doing wacky things outside the check-in server.
In environments where such an option isn't present, I have no hard statistical analysis, but I've found that anecdotally unbuildable revisions occur in pockets. One check-in will mess up a ton of stuff and then there is a series of small check-ins attempting to correct the mess. Then things are generally fine for awhile.
这篇关于通过平分（搜索）修订历史和不可测试的提交（修订）来查找错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
