annotate mercurial/ancestor.py @ 5192:33015dac5df5

convert: fix mercurial_sink.putcommit Changeset 4ebc8693ce72 added some code to putcommit to avoid creating a revision that touches no files, but this can break regular conversions from some repositories: - conceptually, since we're converting a repo, we should try to make the new hg repo as similar as possible to the original repo - we should create a new changeset, even if the original revision didn't touch any files (maybe the commit message had some important bit); - even if a "regular" revision that doesn't touch any file may seem weird (and maybe even broken), it's completely legitimate for a merge revision to not touch any file, and, if we just skip it, the converted repo will end up with wrong history and possibly an extra head. As an example, say the crew and main hg repos are sync'ed. Somebody sends an important patch to the mailing list. Matt quickly applies and pushes it. But at the same time somebody also applies it to crew and pushes it. Suppose the commit message ended up being a bit different (say, there was a typo and somebody didn't fix it) or that the date ended up being different (because of different patch-applying scripts): the changeset hashes will be different, but the manifests will be the same. Since both changesets were pushed to public repos, it's hard to recall them. If both are merged, the manifest from the resulting merge revision will have the exact same contents as its parents - i.e. the merge revision really doesn't touch any file at all. To keep the file filtering stuff "working", the generic code was changed to skip empty revisions if we're filtering the repo, fixing a bug in the process (we want parents[0] instead of tip).
author Alexis S. L. Carvalho <alexis@cecm.usp.br>
date Fri, 17 Aug 2007 20:18:05 -0300
parents eb0b4a2d70a9
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
3136
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
1 # ancestor.py - generic DAG ancestor algorithm for mercurial
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
2 #
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
3 # Copyright 2006 Matt Mackall <mpm@selenic.com>
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
4 #
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
5 # This software may be used and distributed according to the terms
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
6 # of the GNU General Public License, incorporated herein by reference.
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
7
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
8 import heapq
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
9
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
10 def ancestor(a, b, pfunc):
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
11 """
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
12 return the least common ancestor of nodes a and b or None if there
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
13 is no such ancestor.
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
14
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
15 pfunc must return a list of parent vertices
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
16 """
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
17
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
18 if a == b:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
19 return a
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
20
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
21 # find depth from root of all ancestors
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
22 visit = [a, b]
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
23 depth = {}
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
24 while visit:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
25 vertex = visit[-1]
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
26 pl = pfunc(vertex)
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
27 if not pl:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
28 depth[vertex] = 0
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
29 visit.pop()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
30 else:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
31 for p in pl:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
32 if p == a or p == b: # did we find a or b as a parent?
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
33 return p # we're done
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
34 if p not in depth:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
35 visit.append(p)
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
36 if visit[-1] == vertex:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
37 depth[vertex] = min([depth[p] for p in pl]) - 1
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
38 visit.pop()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
39
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
40 # traverse ancestors in order of decreasing distance from root
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
41 def ancestors(vertex):
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
42 h = [(depth[vertex], vertex)]
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
43 seen = {}
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
44 while h:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
45 d, n = heapq.heappop(h)
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
46 if n not in seen:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
47 seen[n] = 1
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
48 yield (d, n)
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
49 for p in pfunc(n):
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
50 heapq.heappush(h, (depth[p], p))
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
51
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
52 def generations(vertex):
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
53 sg, s = None, {}
3673
eb0b4a2d70a9 white space and line break cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents: 3136
diff changeset
54 for g, v in ancestors(vertex):
3136
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
55 if g != sg:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
56 if sg:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
57 yield sg, s
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
58 sg, s = g, {v:1}
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
59 else:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
60 s[v] = 1
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
61 yield sg, s
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
62
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
63 x = generations(a)
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
64 y = generations(b)
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
65 gx = x.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
66 gy = y.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
67
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
68 # increment each ancestor list until it is closer to root than
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
69 # the other, or they match
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
70 try:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
71 while 1:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
72 if gx[0] == gy[0]:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
73 for v in gx[1]:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
74 if v in gy[1]:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
75 return v
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
76 gy = y.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
77 gx = x.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
78 elif gx[0] > gy[0]:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
79 gy = y.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
80 else:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
81 gx = x.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
82 except StopIteration:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
83 return None