Mercurial > public > mercurial-scm > hg-stable
annotate mercurial/hbisect.py @ 6858:8f256bf98219
Add support for multiple possible bisect results (issue1228, issue1182)
The real reason for both issue is that bisect can not handle cases where there
are multiple possibilities for the result.
Example (from issue1228):
rev 0 -> good
rev 1 -> skipped
rev 2 -> skipped
rev 3 -> skipped
rev 4 -> bad
Note that this patch does not only fix the reported Assertion Error but also
the problem of a non converging bisect:
hg init
for i in `seq 3`; do echo $i > $i; hg add $i; hg ci -m$i; done
hg bisect -b 2
hg bisect -g 0
hg bisect -s
From this state on, you can:
a) mark as bad forever (non converging!)
b) mark as good to get an inconsistent state
c) skip for the Assertion Error
Minor description and code edits by pmezard.
author | Bernhard Leiner <bleiner@gmail.com> |
---|---|
date | Sat, 02 Aug 2008 22:10:10 +0200 |
parents | fe8dbbe9520d |
children | 0b6f2fa5e03f |
rev | line source |
---|---|
5775
2dd202a6e15b
bisect: make bisect a built-in command
Matt Mackall <mpm@selenic.com>
parents:
5774
diff
changeset
|
1 # changelog bisection for mercurial |
1367
a7678cbd7c28
bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff
changeset
|
2 # |
5775
2dd202a6e15b
bisect: make bisect a built-in command
Matt Mackall <mpm@selenic.com>
parents:
5774
diff
changeset
|
3 # Copyright 2007 Matt Mackall |
1861
65949d1c9bf7
Added copyright information to hbisect.py
Thomas Arendsen Hein <thomas@intevation.de>
parents:
1856
diff
changeset
|
4 # Copyright 2005, 2006 Benoit Boissinot <benoit.boissinot@ens-lyon.org> |
65949d1c9bf7
Added copyright information to hbisect.py
Thomas Arendsen Hein <thomas@intevation.de>
parents:
1856
diff
changeset
|
5 # Inspired by git bisect, extension skeleton taken from mq.py. |
65949d1c9bf7
Added copyright information to hbisect.py
Thomas Arendsen Hein <thomas@intevation.de>
parents:
1856
diff
changeset
|
6 # |
1367
a7678cbd7c28
bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff
changeset
|
7 # This software may be used and distributed according to the terms |
a7678cbd7c28
bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff
changeset
|
8 # of the GNU General Public License, incorporated herein by reference. |
a7678cbd7c28
bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff
changeset
|
9 |
5775
2dd202a6e15b
bisect: make bisect a built-in command
Matt Mackall <mpm@selenic.com>
parents:
5774
diff
changeset
|
10 from i18n import _ |
6217
fe8dbbe9520d
Avoid importing mercurial.node/mercurial.repo stuff from mercurial.hg
Joel Rosdahl <joel@rosdahl.net>
parents:
5777
diff
changeset
|
11 from node import short |
fe8dbbe9520d
Avoid importing mercurial.node/mercurial.repo stuff from mercurial.hg
Joel Rosdahl <joel@rosdahl.net>
parents:
5777
diff
changeset
|
12 import util |
1367
a7678cbd7c28
bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff
changeset
|
13 |
5775
2dd202a6e15b
bisect: make bisect a built-in command
Matt Mackall <mpm@selenic.com>
parents:
5774
diff
changeset
|
14 def bisect(changelog, state): |
6858
8f256bf98219
Add support for multiple possible bisect results (issue1228, issue1182)
Bernhard Leiner <bleiner@gmail.com>
parents:
6217
diff
changeset
|
15 """find the next node (if any) for testing during a bisect search. |
8f256bf98219
Add support for multiple possible bisect results (issue1228, issue1182)
Bernhard Leiner <bleiner@gmail.com>
parents:
6217
diff
changeset
|
16 returns a (nodes, number, good) tuple. |
8f256bf98219
Add support for multiple possible bisect results (issue1228, issue1182)
Bernhard Leiner <bleiner@gmail.com>
parents:
6217
diff
changeset
|
17 |
8f256bf98219
Add support for multiple possible bisect results (issue1228, issue1182)
Bernhard Leiner <bleiner@gmail.com>
parents:
6217
diff
changeset
|
18 'nodes' is the final result of the bisect if 'number' is 0. |
8f256bf98219
Add support for multiple possible bisect results (issue1228, issue1182)
Bernhard Leiner <bleiner@gmail.com>
parents:
6217
diff
changeset
|
19 Otherwise 'number' indicates the remaining possible candidates for |
8f256bf98219
Add support for multiple possible bisect results (issue1228, issue1182)
Bernhard Leiner <bleiner@gmail.com>
parents:
6217
diff
changeset
|
20 the search and 'nodes' contains the next bisect target. |
8f256bf98219
Add support for multiple possible bisect results (issue1228, issue1182)
Bernhard Leiner <bleiner@gmail.com>
parents:
6217
diff
changeset
|
21 'good' is True if bisect is searching for a first good changeset, False |
8f256bf98219
Add support for multiple possible bisect results (issue1228, issue1182)
Bernhard Leiner <bleiner@gmail.com>
parents:
6217
diff
changeset
|
22 if searching for a first bad one. |
8f256bf98219
Add support for multiple possible bisect results (issue1228, issue1182)
Bernhard Leiner <bleiner@gmail.com>
parents:
6217
diff
changeset
|
23 """ |
8f256bf98219
Add support for multiple possible bisect results (issue1228, issue1182)
Bernhard Leiner <bleiner@gmail.com>
parents:
6217
diff
changeset
|
24 |
5737 | 25 clparents = changelog.parentrevs |
5770
f5b858fc8067
bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents:
5769
diff
changeset
|
26 skip = dict.fromkeys([changelog.rev(n) for n in state['skip']]) |
1367
a7678cbd7c28
bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff
changeset
|
27 |
5776
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
28 def buildancestors(bad, good): |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
29 # only the earliest bad revision matters |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
30 badrev = min([changelog.rev(n) for n in bad]) |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
31 goodrevs = [changelog.rev(n) for n in good] |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
32 # build ancestors array |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
33 ancestors = [[]] * (changelog.count() + 1) # an extra for [-1] |
1367
a7678cbd7c28
bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff
changeset
|
34 |
5776
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
35 # clear good revs from array |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
36 for node in goodrevs: |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
37 ancestors[node] = None |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
38 for rev in xrange(changelog.count(), -1, -1): |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
39 if ancestors[rev] is None: |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
40 for prev in clparents(rev): |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
41 ancestors[prev] = None |
1367
a7678cbd7c28
bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff
changeset
|
42 |
5776
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
43 if ancestors[badrev] is None: |
5777 | 44 return badrev, None |
5776
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
45 return badrev, ancestors |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
46 |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
47 good = 0 |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
48 badrev, ancestors = buildancestors(state['bad'], state['good']) |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
49 if not ancestors: # looking for bad to good transition? |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
50 good = 1 |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
51 badrev, ancestors = buildancestors(state['good'], state['bad']) |
5777 | 52 bad = changelog.node(badrev) |
5776
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
53 if not ancestors: # now we're confused |
5737 | 54 raise util.Abort(_("Inconsistent state, %s:%s is good and bad") |
6217
fe8dbbe9520d
Avoid importing mercurial.node/mercurial.repo stuff from mercurial.hg
Joel Rosdahl <joel@rosdahl.net>
parents:
5777
diff
changeset
|
55 % (badrev, short(bad))) |
5723
e3b09819496b
bisect: switch to rev-based calculation
Matt Mackall <mpm@selenic.com>
parents:
5722
diff
changeset
|
56 |
5768
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
57 # build children dict |
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
58 children = {} |
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
59 visit = [badrev] |
5769
49809f4a38d8
bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents:
5768
diff
changeset
|
60 candidates = [] |
5768
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
61 while visit: |
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
62 rev = visit.pop(0) |
5767
dd5f8ed31057
bisect: propagate ancestor lists directly to children
Matt Mackall <mpm@selenic.com>
parents:
5766
diff
changeset
|
63 if ancestors[rev] == []: |
5769
49809f4a38d8
bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents:
5768
diff
changeset
|
64 candidates.append(rev) |
5767
dd5f8ed31057
bisect: propagate ancestor lists directly to children
Matt Mackall <mpm@selenic.com>
parents:
5766
diff
changeset
|
65 for prev in clparents(rev): |
5768
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
66 if prev != -1: |
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
67 if prev in children: |
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
68 children[prev].append(rev) |
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
69 else: |
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
70 children[prev] = [rev] |
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
71 visit.append(prev) |
5767
dd5f8ed31057
bisect: propagate ancestor lists directly to children
Matt Mackall <mpm@selenic.com>
parents:
5766
diff
changeset
|
72 |
5769
49809f4a38d8
bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents:
5768
diff
changeset
|
73 candidates.sort() |
5770
f5b858fc8067
bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents:
5769
diff
changeset
|
74 # have we narrowed it down to one entry? |
6858
8f256bf98219
Add support for multiple possible bisect results (issue1228, issue1182)
Bernhard Leiner <bleiner@gmail.com>
parents:
6217
diff
changeset
|
75 # or have all other possible candidates besides 'bad' have been skipped? |
5770
f5b858fc8067
bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents:
5769
diff
changeset
|
76 tot = len(candidates) |
6858
8f256bf98219
Add support for multiple possible bisect results (issue1228, issue1182)
Bernhard Leiner <bleiner@gmail.com>
parents:
6217
diff
changeset
|
77 unskipped = [c for c in candidates if (c not in skip) and (c != badrev)] |
8f256bf98219
Add support for multiple possible bisect results (issue1228, issue1182)
Bernhard Leiner <bleiner@gmail.com>
parents:
6217
diff
changeset
|
78 if tot == 1 or not unskipped: |
8f256bf98219
Add support for multiple possible bisect results (issue1228, issue1182)
Bernhard Leiner <bleiner@gmail.com>
parents:
6217
diff
changeset
|
79 return ([changelog.node(rev) for rev in candidates], 0, good) |
5771
9d3f49f52a4a
bisect: stop early if we find a perfect candidate
Matt Mackall <mpm@selenic.com>
parents:
5770
diff
changeset
|
80 perfect = tot / 2 |
5769
49809f4a38d8
bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents:
5768
diff
changeset
|
81 |
5770
f5b858fc8067
bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents:
5769
diff
changeset
|
82 # find the best node to test |
f5b858fc8067
bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents:
5769
diff
changeset
|
83 best_rev = None |
f5b858fc8067
bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents:
5769
diff
changeset
|
84 best_len = -1 |
5772
4c46636eafe5
bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents:
5771
diff
changeset
|
85 poison = {} |
5769
49809f4a38d8
bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents:
5768
diff
changeset
|
86 for rev in candidates: |
5772
4c46636eafe5
bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents:
5771
diff
changeset
|
87 if rev in poison: |
4c46636eafe5
bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents:
5771
diff
changeset
|
88 for c in children.get(rev, []): |
4c46636eafe5
bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents:
5771
diff
changeset
|
89 poison[c] = True # poison children |
4c46636eafe5
bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents:
5771
diff
changeset
|
90 continue |
5773
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
91 |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
92 a = ancestors[rev] or [rev] |
5770
f5b858fc8067
bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents:
5769
diff
changeset
|
93 ancestors[rev] = None |
5773
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
94 |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
95 x = len(a) # number of ancestors |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
96 y = tot - x # number of non-ancestors |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
97 value = min(x, y) # how good is this test? |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
98 if value > best_len and rev not in skip: |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
99 best_len = value |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
100 best_rev = rev |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
101 if value == perfect: # found a perfect candidate? quit early |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
102 break |
5772
4c46636eafe5
bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents:
5771
diff
changeset
|
103 |
5773
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
104 if y < perfect: # all downhill from here? |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
105 for c in children.get(rev, []): |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
106 poison[c] = True # poison children |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
107 continue |
5772
4c46636eafe5
bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents:
5771
diff
changeset
|
108 |
5773
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
109 for c in children.get(rev, []): |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
110 if ancestors[c]: |
5774 | 111 ancestors[c] = dict.fromkeys(ancestors[c] + a).keys() |
5773
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
112 else: |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
113 ancestors[c] = a + [c] |
5734
944b231fa0e7
bisect: move reporting out of core bisect function
Matt Mackall <mpm@selenic.com>
parents:
5733
diff
changeset
|
114 |
5737 | 115 assert best_rev is not None |
116 best_node = changelog.node(best_rev) | |
1367
a7678cbd7c28
bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff
changeset
|
117 |
6858
8f256bf98219
Add support for multiple possible bisect results (issue1228, issue1182)
Bernhard Leiner <bleiner@gmail.com>
parents:
6217
diff
changeset
|
118 return ([best_node], tot, good) |