Mercurial > hg
annotate mercurial/ancestor.py @ 6409:47f4a47161b4
merge with crew
author | Benoit Boissinot <benoit.boissinot@ens-lyon.org> |
---|---|
date | Sun, 30 Mar 2008 20:31:35 +0200 |
parents | fda369b5779c |
children | 6b704ef9ed06 |
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 |