Mercurial > public > mercurial-scm > hg

annotate mercurial/hbisect.py @ 5909:f45f7390c1c5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
strip: calculate list of extra nodes to save and pass it to changegroupsubset When we remove revision N from the repository, all revisions >= N are affected: either it's a descendant from N and will also be removed, or it's not a descendant of N and will be renumbered. As a consequence, we have to (at least temporarily) remove all filelog and manifest revisions that have a linkrev >= N, readding some of them later. Unfortunately, it's possible to have a revlog with two revisions r1 and r2 such that r1 < r2, but linkrev(r1) > linkrev(r2). If we try to strip revision linkrev(r1) from the repository, we'll also lose revision r2 when we truncate this revlog. We already use changegroupsubset to create a temporary changegroup containing the revisions that have to be restored, but that function is unable to detect that we also wanted to save the r2 in the case above. So we manually calculate these extra nodes and pass it to changegroupsubset. This should fix issue764.
author Alexis S. L. Carvalho <alexis@cecm.usp.br>
date Sat, 19 Jan 2008 18:01:16 -0200
parents 51776e50bc8c
children fe8dbbe9520d
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 _
2dd202a6e15b bisect: make bisect a built-in command
Matt Mackall <mpm@selenic.com>
parents: 5774
diff changeset
11 import hg, util
1367
a7678cbd7c28 bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff changeset
12
5775
2dd202a6e15b bisect: make bisect a built-in command
Matt Mackall <mpm@selenic.com>
parents: 5774
diff changeset
13 def bisect(changelog, state):
5737
6c8df073c3ee bisect: remove class
Matt Mackall <mpm@selenic.com>
parents: 5736
diff changeset
14 clparents = changelog.parentrevs
5770
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
15 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
16
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
17 def buildancestors(bad, good):
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
18 # only the earliest bad revision matters
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
19 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
20 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
21 # build ancestors array
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
22 ancestors = [[]] * (changelog.count() + 1) # an extra for [-1]
1367
a7678cbd7c28 bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff changeset
23
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
24 # clear good revs from array
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
25 for node in goodrevs:
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
26 ancestors[node] = None
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
27 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
28 if ancestors[rev] is None:
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
29 for prev in clparents(rev):
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
30 ancestors[prev] = None
1367
a7678cbd7c28 bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff changeset
31
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
32 if ancestors[badrev] is None:
5777
51776e50bc8c bisect: improve tests
Matt Mackall <mpm@selenic.com>
parents: 5776
diff changeset
33 return badrev, None
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
34 return badrev, ancestors
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
35
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
36 good = 0
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
37 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
38 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
39 good = 1
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
40 badrev, ancestors = buildancestors(state['good'], state['bad'])
5777
51776e50bc8c bisect: improve tests
Matt Mackall <mpm@selenic.com>
parents: 5776
diff changeset
41 bad = changelog.node(badrev)
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
42 if not ancestors: # now we're confused
5737
6c8df073c3ee bisect: remove class
Matt Mackall <mpm@selenic.com>
parents: 5736
diff changeset
43 raise util.Abort(_("Inconsistent state, %s:%s is good and bad")
6c8df073c3ee bisect: remove class
Matt Mackall <mpm@selenic.com>
parents: 5736
diff changeset
44 % (badrev, hg.short(bad)))
5723
e3b09819496b bisect: switch to rev-based calculation
Matt Mackall <mpm@selenic.com>
parents: 5722
diff changeset
45
5768
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
46 # build children dict
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
47 children = {}
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
48 visit = [badrev]
5769
49809f4a38d8 bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents: 5768
diff changeset
49 candidates = []
5768
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
50 while visit:
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
51 rev = visit.pop(0)
5767
dd5f8ed31057 bisect: propagate ancestor lists directly to children
Matt Mackall <mpm@selenic.com>
parents: 5766
diff changeset
52 if ancestors[rev] == []:
5769
49809f4a38d8 bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents: 5768
diff changeset
53 candidates.append(rev)
5767
dd5f8ed31057 bisect: propagate ancestor lists directly to children
Matt Mackall <mpm@selenic.com>
parents: 5766
diff changeset
54 for prev in clparents(rev):
5768
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
55 if prev != -1:
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
56 if prev in children:
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
57 children[prev].append(rev)
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
58 else:
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
59 children[prev] = [rev]
78d14403bdc7 bisect: use a dict for children
Matt Mackall <mpm@selenic.com>
parents: 5767
diff changeset
60 visit.append(prev)
5767
dd5f8ed31057 bisect: propagate ancestor lists directly to children
Matt Mackall <mpm@selenic.com>
parents: 5766
diff changeset
61
5769
49809f4a38d8 bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents: 5768
diff changeset
62 candidates.sort()
5770
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
63 # 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
64 tot = len(candidates)
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
65 if tot == 1:
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
66 return (bad, 0, good)
5771
9d3f49f52a4a bisect: stop early if we find a perfect candidate
Matt Mackall <mpm@selenic.com>
parents: 5770
diff changeset
67 perfect = tot / 2
5769
49809f4a38d8 bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents: 5768
diff changeset
68
5770
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
69 # find the best node to test
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
70 best_rev = None
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
71 best_len = -1
5772
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
72 poison = {}
5769
49809f4a38d8 bisect: calculate candidate set while finding children
Matt Mackall <mpm@selenic.com>
parents: 5768
diff changeset
73 for rev in candidates:
5772
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
74 if rev in poison:
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
75 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
76 poison[c] = True # poison children
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
77 continue
5773
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
78
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
79 a = ancestors[rev] or [rev]
5770
f5b858fc8067 bisect: find best node in ancestor collection pass
Matt Mackall <mpm@selenic.com>
parents: 5769
diff changeset
80 ancestors[rev] = None
5773
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
81
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
82 x = len(a) # number of ancestors
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
83 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
84 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
85 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
86 best_len = value
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
87 best_rev = rev
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
88 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
89 break
5772
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
90
5773
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
91 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
92 for c in children.get(rev, []):
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
93 poison[c] = True # poison children
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
94 continue
5772
4c46636eafe5 bisect: skip calculations on candidates with too many ancestors
Matt Mackall <mpm@selenic.com>
parents: 5771
diff changeset
95
5773
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
96 for c in children.get(rev, []):
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
97 if ancestors[c]:
5774
c850a8640981 bisect: faster merging
Matt Mackall <mpm@selenic.com>
parents: 5773
diff changeset
98 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
99 else:
2f6105ab4c54 bisect: merge ancestor lists when pushing to children
Matt Mackall <mpm@selenic.com>
parents: 5772
diff changeset
100 ancestors[c] = a + [c]
5734
944b231fa0e7 bisect: move reporting out of core bisect function
Matt Mackall <mpm@selenic.com>
parents: 5733
diff changeset
101
5737
6c8df073c3ee bisect: remove class
Matt Mackall <mpm@selenic.com>
parents: 5736
diff changeset
102 assert best_rev is not None
6c8df073c3ee bisect: remove class
Matt Mackall <mpm@selenic.com>
parents: 5736
diff changeset
103 best_node = changelog.node(best_rev)
1367
a7678cbd7c28 bisect extension for mercurial
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents:
diff changeset
104
5776
35ec669cdd43 bisect: handle search for bad to good transitions
Matt Mackall <mpm@selenic.com>
parents: 5775
diff changeset
105 return (best_node, tot, good)