Как работает пополам Mercurial, когда диапазон включает в себя ветвление?
Если диапазон пополам включает в себя несколько веток, как работает поиск в hg bisect? Эффективно ли это делит пополам каждое подразделение (я думаю, что это будет неэффективно)?
Например, с благодарностью заимствуем диаграмму из ответа на этот связанный вопрос, что, если биссект добрался до набора изменений 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 на правой стороне ветви, или все еще может быть где-нибудь на левой стороне ветви.
Цель моего вопроса состоит в том, чтобы (а) просто лучше понять алгоритм и (б) понять, могу ли я свободно расширять начальный диапазон деления пополам, не задумываясь о том, к какой ветви я иду. Я был в биссектрисе с высокой степенью ветвления, когда после каждого теста меня продолжали просить, чтобы он выходил за рамки следующего слияния, так что вся процедура была по существу O(n). Я задаюсь вопросом, могу ли я просто бросить первый "хороший" маркер назад через некоторое гнездо слияний, не задумываясь об этом, и сэкономит ли это время и даст ли правильные результаты.
1 ответ
Цитировать из Mercurial: полное руководство:
Команда hg bisect знает о "ветвистой" природе истории ревизий проекта Mercurial, поэтому у нее нет проблем при работе с ветвями, слияниями или несколькими заголовками в репозитории. Он может обрезать целые ветви истории с помощью одного зонда, который так эффективно работает.
Код, выполняющий эту работу, находится в 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?