annotate mercurial/ancestor.py @ 6412:9d2983c6a965

merge with -stable
author Benoit Boissinot <benoit.boissinot@ens-lyon.org>
date Sun, 30 Mar 2008 22:23:55 +0200
parents fda369b5779c
children 6b704ef9ed06
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
3135
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: 3135
diff changeset
54 for g, v in ancestors(vertex):
3135
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
6273
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
84
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
85 def symmetricdifference(a, b, pfunc):
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
86 """symmetric difference of the sets of ancestors of a and b
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
87
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
88 I.e. revisions that are ancestors of a or b, but not both.
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
89 """
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
90 # basic idea:
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
91 # - mark a and b with different colors
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
92 # - walk the graph in topological order with the help of a heap;
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
93 # for each revision r:
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
94 # - if r has only one color, we want to return it
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
95 # - add colors[r] to its parents
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
96 #
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
97 # We keep track of the number of revisions in the heap that
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
98 # we may be interested in. We stop walking the graph as soon
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
99 # as this number reaches 0.
6275
fda369b5779c diff: use copy smarts from copies.py
Matt Mackall <mpm@selenic.com>
parents: 6273
diff changeset
100 if a == b:
fda369b5779c diff: use copy smarts from copies.py
Matt Mackall <mpm@selenic.com>
parents: 6273
diff changeset
101 return [a]
fda369b5779c diff: use copy smarts from copies.py
Matt Mackall <mpm@selenic.com>
parents: 6273
diff changeset
102
6273
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
103 WHITE = 1
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
104 BLACK = 2
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
105 ALLCOLORS = WHITE | BLACK
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
106 colors = {a: WHITE, b: BLACK}
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
107
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
108 visit = [-a, -b]
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
109 heapq.heapify(visit)
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
110 n_wanted = len(visit)
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
111 ret = []
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
112
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
113 while n_wanted:
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
114 r = -heapq.heappop(visit)
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
115 wanted = colors[r] != ALLCOLORS
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
116 n_wanted -= wanted
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
117 if wanted:
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
118 ret.append(r)
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
119
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
120 for p in pfunc(r):
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
121 if p not in colors:
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
122 # first time we see p; add it to visit
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
123 n_wanted += wanted
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
124 colors[p] = colors[r]
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
125 heapq.heappush(visit, -p)
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
126 elif colors[p] != ALLCOLORS and colors[p] != colors[r]:
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
127 # at first we thought we wanted p, but now
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
128 # we know we don't really want it
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
129 n_wanted -= 1
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
130 colors[p] |= colors[r]
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
131
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
132 del colors[r]
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
133
20aa460a52b6 merge: move symmetricdifferences to ancestor.py
Matt Mackall <mpm@selenic.com>
parents: 3673
diff changeset
134 return ret