version-control - 当范围包括分支时，mercurial 的二等分如何工作？

Question

如果 bisect 范围包括多个分支，hg bisect 的搜索是如何工作的。它是否有效地将每个子分支一分为二(我认为这会效率低下)？

例如，感激地从 this related question 的答案中借用一张图，如果二等分首先在“好”右侧分支上得到变更集 7 会怎样。

@  12:8ae1fff407c8:bad6
|
o  11:27edd4ba0a78:bad5
|
o    10:312ba3d6eb29:bad4
|\
| o  9:68ae20ea0c02:good33
| |
| o  8:916e977fa594:good32
| |
| o  7:b9d00094223f:good31
| |
o |  6:a7cab1800465:bad3
| |
o |  5:a84e45045a29:bad2
| |
o |  4:d0a381a67072:bad1
| |
o |  3:54349a6276cc:good4
|/
o  2:4588e394e325:good3
|
o  1:de79725cb39a:good2
|
o  0:2641cc78ce7a:good1

那么它会不会看起来只在 7 到 12 之间，而忽略了我们关心的真正的第一坏事？ (因此使用“哑”数字顺序)或者它是否足够聪明以使用完整的地形并知道第一个坏点可能在右侧分支上低于 7，或者仍然可能在左侧分支上的任何位置。

我的问题的目的是 (a) 只是为了更好地理解算法，以及 (b) 了解我是否可以自由地扩展我的初始二等分范围而无需仔细考虑我要去哪个分支。我一直在 high-branching bisect situations 中，每次测试后它一直问我要扩展到下一次合并之外，因此整个过程基本上是 O(n)。我想知道我是否可以将第一个“好”标记扔回一些合并嵌套而不用太多考虑，以及这是否会节省时间并给出正确的结果。

Answer 1

引自 Mercurial: The Definitive Guide :

The hg bisect command is aware of the “branchy” nature of a Mercurial project's revision history, so it has no problems dealing with branches, merges, or multiple heads in a repository. It can prune entire branches of history with a single probe, which is how it operates so efficiently.

完成工作的代码在 hbisect.py 中并实际查看来自每个节点的后代树和祖先树，其中状态已确定。

在我看来，选择要测试的变更集是通过对尚未测试的图表中的“中心程度”进行加权来选择的(即按祖先与非祖先平分，而不是按时间顺序):

108     x = len(a) # number of ancestors
109     y = tot - x # number of non-ancestors
110     value = min(x, y) # how good is this test?