Mercurial > hg
annotate mercurial/hbisect.py @ 6900:def492d1b592
store: change handling of decoding errors
author | Matt Mackall <mpm@selenic.com> |
---|---|
date | Wed, 13 Aug 2008 20:18:43 -0500 |
parents | 0b6f2fa5e03f |
children | e1afb50ec2aa |
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 |
6750
fb42030d79d6
add __len__ and __iter__ methods to repo and revlog
Matt Mackall <mpm@selenic.com>
parents:
6694
diff
changeset
|
33 ancestors = [[]] * (len(changelog) + 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 |
6750
fb42030d79d6
add __len__ and __iter__ methods to repo and revlog
Matt Mackall <mpm@selenic.com>
parents:
6694
diff
changeset
|
38 for rev in xrange(len(changelog), -1, -1): |
5776
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) |