Mercurial > hg
annotate mercurial/hbisect.py @ 6409:47f4a47161b4
merge with crew
author | Benoit Boissinot <benoit.boissinot@ens-lyon.org> |
---|---|
date | Sun, 30 Mar 2008 20:31:35 +0200 |
parents | fe8dbbe9520d |
children | 683428d1e639 8f256bf98219 |
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): |
5737 | 15 clparents = changelog.parentrevs |
5770
f5b858fc8067
bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents:
5769
diff
changeset
|
16 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
|
17 |
5776
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
18 def buildancestors(bad, good): |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
19 # only the earliest bad revision matters |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
20 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
|
21 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
|
22 # build ancestors array |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
23 ancestors = [[]] * (changelog.count() + 1) # an extra for [-1] |
1367
a7678cbd7c28
bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff
changeset
|
24 |
5776
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
25 # clear good revs from array |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
26 for node in goodrevs: |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
27 ancestors[node] = None |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
28 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
|
29 if ancestors[rev] is None: |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
30 for prev in clparents(rev): |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
31 ancestors[prev] = None |
1367
a7678cbd7c28
bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff
changeset
|
32 |
5776
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
33 if ancestors[badrev] is None: |
5777 | 34 return badrev, None |
5776
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
35 return badrev, ancestors |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
36 |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
37 good = 0 |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
38 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
|
39 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
|
40 good = 1 |
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
41 badrev, ancestors = buildancestors(state['good'], state['bad']) |
5777 | 42 bad = changelog.node(badrev) |
5776
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
43 if not ancestors: # now we're confused |
5737 | 44 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
|
45 % (badrev, short(bad))) |
5723
e3b09819496b
bisect: switch to rev-based calculation
Matt Mackall <mpm@selenic.com>
parents:
5722
diff
changeset
|
46 |
5768
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
47 # build children dict |
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
48 children = {} |
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
49 visit = [badrev] |
5769
49809f4a38d8
bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents:
5768
diff
changeset
|
50 candidates = [] |
5768
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
51 while visit: |
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
52 rev = visit.pop(0) |
5767
dd5f8ed31057
bisect: propagate ancestor lists directly to children
Matt Mackall <mpm@selenic.com>
parents:
5766
diff
changeset
|
53 if ancestors[rev] == []: |
5769
49809f4a38d8
bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents:
5768
diff
changeset
|
54 candidates.append(rev) |
5767
dd5f8ed31057
bisect: propagate ancestor lists directly to children
Matt Mackall <mpm@selenic.com>
parents:
5766
diff
changeset
|
55 for prev in clparents(rev): |
5768
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
56 if prev != -1: |
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
57 if prev in children: |
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
58 children[prev].append(rev) |
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
59 else: |
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
60 children[prev] = [rev] |
78d14403bdc7
bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents:
5767
diff
changeset
|
61 visit.append(prev) |
5767
dd5f8ed31057
bisect: propagate ancestor lists directly to children
Matt Mackall <mpm@selenic.com>
parents:
5766
diff
changeset
|
62 |
5769
49809f4a38d8
bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents:
5768
diff
changeset
|
63 candidates.sort() |
5770
f5b858fc8067
bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents:
5769
diff
changeset
|
64 # have we narrowed it down to one entry? |
f5b858fc8067
bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents:
5769
diff
changeset
|
65 tot = len(candidates) |
f5b858fc8067
bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents:
5769
diff
changeset
|
66 if tot == 1: |
5776
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
67 return (bad, 0, good) |
5771
9d3f49f52a4a
bisect: stop early if we find a perfect candidate
Matt Mackall <mpm@selenic.com>
parents:
5770
diff
changeset
|
68 perfect = tot / 2 |
5769
49809f4a38d8
bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents:
5768
diff
changeset
|
69 |
5770
f5b858fc8067
bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents:
5769
diff
changeset
|
70 # find the best node to test |
f5b858fc8067
bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents:
5769
diff
changeset
|
71 best_rev = None |
f5b858fc8067
bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents:
5769
diff
changeset
|
72 best_len = -1 |
5772
4c46636eafe5
bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents:
5771
diff
changeset
|
73 poison = {} |
5769
49809f4a38d8
bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents:
5768
diff
changeset
|
74 for rev in candidates: |
5772
4c46636eafe5
bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents:
5771
diff
changeset
|
75 if rev in poison: |
4c46636eafe5
bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents:
5771
diff
changeset
|
76 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
|
77 poison[c] = True # poison children |
4c46636eafe5
bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents:
5771
diff
changeset
|
78 continue |
5773
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
79 |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
80 a = ancestors[rev] or [rev] |
5770
f5b858fc8067
bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents:
5769
diff
changeset
|
81 ancestors[rev] = None |
5773
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
82 |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
83 x = len(a) # number of ancestors |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
84 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
|
85 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
|
86 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
|
87 best_len = value |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
88 best_rev = rev |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
89 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
|
90 break |
5772
4c46636eafe5
bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents:
5771
diff
changeset
|
91 |
5773
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
92 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
|
93 for c in children.get(rev, []): |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
94 poison[c] = True # poison children |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
95 continue |
5772
4c46636eafe5
bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents:
5771
diff
changeset
|
96 |
5773
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
97 for c in children.get(rev, []): |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
98 if ancestors[c]: |
5774 | 99 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
|
100 else: |
2f6105ab4c54
bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents:
5772
diff
changeset
|
101 ancestors[c] = a + [c] |
5734
944b231fa0e7
bisect: move reporting out of core bisect function
Matt Mackall <mpm@selenic.com>
parents:
5733
diff
changeset
|
102 |
5737 | 103 assert best_rev is not None |
104 best_node = changelog.node(best_rev) | |
1367
a7678cbd7c28
bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff
changeset
|
105 |
5776
35ec669cdd43
bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents:
5775
diff
changeset
|
106 return (best_node, tot, good) |