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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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
6c8df073c3ee bisect: remove class
Matt Mackall <mpm@selenic.com>
parents: 5736
diff changeset
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
51776e50bc8c bisect: improve tests
Matt Mackall <mpm@selenic.com>
parents: 5776
diff changeset
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
51776e50bc8c bisect: improve tests
Matt Mackall <mpm@selenic.com>
parents: 5776
diff changeset
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
6c8df073c3ee bisect: remove class
Matt Mackall <mpm@selenic.com>
parents: 5736
diff changeset
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
c850a8640981 bisect: faster merging
Matt Mackall <mpm@selenic.com>
parents: 5773
diff changeset
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
6c8df073c3ee bisect: remove class
Matt Mackall <mpm@selenic.com>
parents: 5736
diff changeset
115 assert best_rev is not None
6c8df073c3ee bisect: remove class
Matt Mackall <mpm@selenic.com>
parents: 5736
diff changeset
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)