How does mercurial's bisect work when the range includes branching?
- by Joshua Goldberg
If the bisect range includes multiple branches, how does hg bisect's search work. Does it effectively bisect each sub-branch (I would think that would be inefficient)?
For instance, borrowing, with gratitude, a diagram from an answer to this related question, what if the bisect got to changeset 7 on the "good" right-side branch first.
@ 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
Will it then look only between 7 and 12, missing the real first-bad that we care about? (thus using "dumb" numerical order) or is it smart enough to use the full topography and to know that the first bad could be below 7 on the right-side branch, or could still be anywhere on the left-side branch.
The purpose of my question is both (a) just to understand the algorithm better, and (b) to understand whether I can liberally extend my initial bisect range without thinking hard about what branch I go to. I've been in high-branching bisect situations where it kept asking me after every test to extend beyond the next merge, so that the whole procedure was essentially O(n). I'm wondering if I can just throw the first "good" marker way back past some nest of merges without thinking about it much, and whether that would save time and give correct results.
