Mercurial > hg > mercurial-crew-with-dirclash

comparison mercurial/ancestor.py @ 3136:b1db258e875c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Abstract ancestor algorithm into generic function Make depth calculation non-recursive Add simple shortcut for linear ancestry Convert context to use ancestor function make memoized parents function Convert revlog to use ancestor function
author Matt Mackall <mpm@selenic.com>
date Wed, 20 Sep 2006 16:50:50 -0500
parents
children eb0b4a2d70a9
comparison
equal deleted inserted replaced
3135:abd9a05fca0b 3136:b1db258e875c
1 # ancestor.py - generic DAG ancestor algorithm for mercurial
2 #
3 # Copyright 2006 Matt Mackall <mpm@selenic.com>
4 #
5 # This software may be used and distributed according to the terms
6 # of the GNU General Public License, incorporated herein by reference.
7
8 import heapq
9
10 def ancestor(a, b, pfunc):
11 """
12 return the least common ancestor of nodes a and b or None if there
13 is no such ancestor.
14
15 pfunc must return a list of parent vertices
16 """
17
18 if a == b:
19 return a
20
21 # find depth from root of all ancestors
22 visit = [a, b]
23 depth = {}
24 while visit:
25 vertex = visit[-1]
26 pl = pfunc(vertex)
27 if not pl:
28 depth[vertex] = 0
29 visit.pop()
30 else:
31 for p in pl:
32 if p == a or p == b: # did we find a or b as a parent?
33 return p # we're done
34 if p not in depth:
35 visit.append(p)
36 if visit[-1] == vertex:
37 depth[vertex] = min([depth[p] for p in pl]) - 1
38 visit.pop()
39
40 # traverse ancestors in order of decreasing distance from root
41 def ancestors(vertex):
42 h = [(depth[vertex], vertex)]
43 seen = {}
44 while h:
45 d, n = heapq.heappop(h)
46 if n not in seen:
47 seen[n] = 1
48 yield (d, n)
49 for p in pfunc(n):
50 heapq.heappush(h, (depth[p], p))
51
52 def generations(vertex):
53 sg, s = None, {}
54 for g,v in ancestors(vertex):
55 if g != sg:
56 if sg:
57 yield sg, s
58 sg, s = g, {v:1}
59 else:
60 s[v] = 1
61 yield sg, s
62
63 x = generations(a)
64 y = generations(b)
65 gx = x.next()
66 gy = y.next()
67
68 # increment each ancestor list until it is closer to root than
69 # the other, or they match
70 try:
71 while 1:
72 if gx[0] == gy[0]:
73 for v in gx[1]:
74 if v in gy[1]:
75 return v
76 gy = y.next()
77 gx = x.next()
78 elif gx[0] > gy[0]:
79 gy = y.next()
80 else:
81 gx = x.next()
82 except StopIteration:
83 return None