通过平分（搜索）修订历史记录，查找漏洞和不可测的提交（修订版） [英] Finding bugs by bisecting (searching) revision history, and untestable commits (revisions)
问题描述
大多数现代版本控制工具有一个命令来查找引入一个bug被历史的二进制搜索（平分）的变化。这样的命令可能是内置的，或者它可能被提供为延伸或插件。例子包括的混帐平分在Git中，的汞平分的水银（早期可作为的 hbisect 扩展程序）和 bzr-平分插件集市。
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.
的挑战是要做到这一点在自动或半自动的方式，即使在非线性历史的presence（分支点和合流）。我们的目标是在一般发现在步骤最少数量的坏的修订，或更详细地找到一个承诺要测试的，如果可能的话，分提交到测试图（DAG提交的）中的一半。这个问题就解决了，我想，很好。
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.
但与不可测提交，比如一个问题如果因为某种修改code甚至不进行编译，或者如果它编译没有开始/运行（或发现错误无关，您正在搜索的）。这意味着，而不是简单地标记提交为好或坏一点，你现在的三的可能状态：
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:
- 好 - 的错误是没有present
- 坏 - 错误行为
- 未知（不可测） - 如果错误是不知道present
- good - the bug is not present
- bad - buggy behavior
- unknown (untestable) - not known if the bug is present
一些版本控制系统（SCM），让你跳这样的提交，通常要到母公司的版本作为一个测试下一个。
Some version control systems (SCM) allow you to "skip" such commits, usually going to the parent revision as the one to test next.
问题是：
-
如果你处理了这样的情况，这意味着你用二分法和偶然发现不可测试版本，什么是你的经验等不可测试提交的分布？难道他们单独发生（单未测试的提交），或者他们出现在范围内（修订a..b是不可测的）？你有没有发现自己在一个情况下，你必须提交跳过后提交？
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?
有一些matematical模型（如存在对列表/线性的历史的简单平分，甚至对等分任意修改DAG）或算法（也许是启发式），它可以优化跳过不可测的提交。我们的目标又是最小化（平均）版本的数量，以测试在不可测的提交（或不相关的bug）的presence。
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).
您是否使用版本控制系统，或者一些附加/扩展/插件版本控制系统，或一些第三方的工具，它实现了这样的算法，允许简单的跳过不可测提交转到旁边邻居修订？这是什么VCS或工具？它使用什么样的算法（如果知道的话）？
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...
补充2009年6月6日：的
当使用Git的先进功能，还有就是，即在您使用一情况下，你可以有一个整体的分支的不可测提交（或至少难以测试）的子树的合并，加入两个独立的项目的历史（如完整的Linux内核，一些司机分别开发了使用子树合并）。这是值得考虑的时候想出一个算法来应对不可测提交：用非线性历史可以有不可测提交的整个分支，并且算法考虑到的拓扑结构（有点）
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).
推荐答案
什么被检查的年代，很明显，也没有办法。我已经要求所有的签到工作的大code碱基实际构建。这是根据开发商提交他们的变化签入服务器，就必须修改等着走在队列中。每一个变化是建立在其提交的订单中所有的目标平台上完成的。如果构建失败，办理入住手续将被拒绝。如果成功，这是一套自动回归/单元测试运行。如果任何测试失败，办理入住手续将被拒绝。如果成功，在办理入住手续时提交到库。
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.
在环境中，这样的选择是不是present，我没有很难的统计分析，但我发现，有传言称名不见经传的修改出现在口袋里。一个办理登机手续会搞乱一吨的东西，然后有一系列的小签入试图纠正乱。然后，事情一般都是罚款一段时间。
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屋！
