Mercurial > public > mercurial-scm > hg

annotate mercurial/ancestor.py @ 13741:b51bf961b3cb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
wireproto: add getbundle() function getbundle(common, heads) -> bundle Returns the changegroup for all ancestors of heads which are not ancestors of common. For both sets, the heads are included in the set. Intended to eventually supercede changegroupsubset and changegroup. Uses heads of common region to exclude unwanted changesets instead of bases of desired region, which is more useful and easier to implement. Designed to be extensible with new optional arguments (which will have to be guarded by corresponding capabilities).
author Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
date Wed, 23 Mar 2011 16:02:11 +0100
parents 22565ddb28e7
children 1ffeeb91c55d
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 #
8225
46293a0c7e9f updated license to be explicit about GPL version 2
Martin Geisler <mg@lazybytes.net>
parents: 7882
diff changeset
5 # This software may be used and distributed according to the terms of the
10263
25e572394f5c Update license to GPLv2+
Matt Mackall <mpm@selenic.com>
parents: 8465
diff changeset
6 # GNU General Public License version 2 or any later version.
3135
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 """
13554
22565ddb28e7 ancestor: improve description
Matt Mackall <mpm@selenic.com>
parents: 12401
diff changeset
12 Returns the common ancestor of a and b that is furthest from a
22565ddb28e7 ancestor: improve description
Matt Mackall <mpm@selenic.com>
parents: 12401
diff changeset
13 root (as measured by longest path) or None if no ancestor is
22565ddb28e7 ancestor: improve description
Matt Mackall <mpm@selenic.com>
parents: 12401
diff changeset
14 found. If there are multiple common ancestors at the same
22565ddb28e7 ancestor: improve description
Matt Mackall <mpm@selenic.com>
parents: 12401
diff changeset
15 distance, the first one found is returned.
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
16
9915
806e6b6cb8d8 ancestor: improve docstring
Sune Foldager <cryo@cyanite.org>
parents: 8465
diff changeset
17 pfunc must return a list of parent vertices for a given vertex
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
18 """
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
19
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
20 if a == b:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
21 return a
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
22
11418
67bb9d78f05e merge: sort arguments to stabilize the ancestor search
Matt Mackall <mpm@selenic.com>
parents: 10264
diff changeset
23 a, b = sorted([a, b])
67bb9d78f05e merge: sort arguments to stabilize the ancestor search
Matt Mackall <mpm@selenic.com>
parents: 10264
diff changeset
24
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
25 # find depth from root of all ancestors
13554
22565ddb28e7 ancestor: improve description
Matt Mackall <mpm@selenic.com>
parents: 12401
diff changeset
26 # depth is stored as a negative for heapq
7882
8d78fc991b71 ancestor: caching the parent list to improve performance
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 6429
diff changeset
27 parentcache = {}
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
28 visit = [a, b]
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
29 depth = {}
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
30 while visit:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
31 vertex = visit[-1]
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
32 pl = pfunc(vertex)
7882
8d78fc991b71 ancestor: caching the parent list to improve performance
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 6429
diff changeset
33 parentcache[vertex] = pl
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
34 if not pl:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
35 depth[vertex] = 0
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
36 visit.pop()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
37 else:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
38 for p in pl:
12401
4cdaf1adafc8 backout most of 4f8067c94729
Matt Mackall <mpm@selenic.com>
parents: 12387
diff changeset
39 if p == a or p == b: # did we find a or b as a parent?
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
40 return p # we're done
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
41 if p not in depth:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
42 visit.append(p)
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
43 if visit[-1] == vertex:
13554
22565ddb28e7 ancestor: improve description
Matt Mackall <mpm@selenic.com>
parents: 12401
diff changeset
44 # -(maximum distance of parents + 1)
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
45 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
46 visit.pop()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
47
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
48 # traverse ancestors in order of decreasing distance from root
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
49 def ancestors(vertex):
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
50 h = [(depth[vertex], vertex)]
8465
23429ebd3f9d ancestor: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8225
diff changeset
51 seen = set()
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
52 while h:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
53 d, n = heapq.heappop(h)
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
54 if n not in seen:
8465
23429ebd3f9d ancestor: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8225
diff changeset
55 seen.add(n)
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
56 yield (d, n)
7882
8d78fc991b71 ancestor: caching the parent list to improve performance
Nicolas Dumazet <nicdumz.commits@gmail.com>
parents: 6429
diff changeset
57 for p in parentcache[n]:
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
58 heapq.heappush(h, (depth[p], p))
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
59
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
60 def generations(vertex):
8465
23429ebd3f9d ancestor: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8225
diff changeset
61 sg, s = None, set()
3673
eb0b4a2d70a9 white space and line break cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents: 3135
diff changeset
62 for g, v in ancestors(vertex):
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
63 if g != sg:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
64 if sg:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
65 yield sg, s
8465
23429ebd3f9d ancestor: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8225
diff changeset
66 sg, s = g, set((v,))
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
67 else:
8465
23429ebd3f9d ancestor: use set instead of dict
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 8225
diff changeset
68 s.add(v)
3135
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
69 yield sg, s
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
70
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
71 x = generations(a)
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
72 y = generations(b)
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
73 gx = x.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
74 gy = y.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
75
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
76 # 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
77 # the other, or they match
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
78 try:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
79 while 1:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
80 if gx[0] == gy[0]:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
81 for v in gx[1]:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
82 if v in gy[1]:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
83 return v
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
84 gy = y.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
85 gx = x.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
86 elif gx[0] > gy[0]:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
87 gy = y.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
88 else:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
89 gx = x.next()
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
90 except StopIteration:
b1db258e875c Abstract ancestor algorithm into generic function
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
91 return None