Mercurial > public > mercurial-scm > hg

annotate mercurial/ancestor.py @ 15063:c20688b7c061 stable

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
setdiscovery: fix hang when #heads>200 (issue2971) When setting up the next sample, we always add all of the heads, regardless of the desired max sample size. But if the number of heads exceeds this size, then we don't add any more nodes from the still undecided set. (This is debatable per se, and I'll investigate it, but it's how we designed it at the moment.) The bug was that we always added the overall heads, not the heads of the remaining undecided set. Thus, if #heads>200 (desired sample size), we did not make progress any longer.
author Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
date Thu, 25 Aug 2011 21:25:14 +0200
parents 1ffeeb91c55d
children 0b03454abae7
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:
14494
1ffeeb91c55d check-code: flag 0/1 used as constant Boolean expression
Martin Geisler <mg@lazybytes.net>
parents: 13554
diff changeset
79 while True:
3135
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