Show More
@@ -0,0 +1,83 b'' | |||
|
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 |
@@ -5,6 +5,10 b'' | |||
|
5 | 5 | # This software may be used and distributed according to the terms |
|
6 | 6 | # of the GNU General Public License, incorporated herein by reference. |
|
7 | 7 | |
|
8 | from node import * | |
|
9 | from demandload import demandload | |
|
10 | demandload(globals(), "ancestor") | |
|
11 | ||
|
8 | 12 | class changectx(object): |
|
9 | 13 | """A changecontext object makes access to data related to a particular |
|
10 | 14 | changeset convenient.""" |
@@ -42,7 +46,7 b' class changectx(object):' | |||
|
42 | 46 | def node(self): return self._node |
|
43 | 47 | def user(self): return self.changeset()[1] |
|
44 | 48 | def date(self): return self.changeset()[2] |
|
45 |
def |
|
|
49 | def files(self): return self.changeset()[3] | |
|
46 | 50 | def description(self): return self.changeset()[4] |
|
47 | 51 | |
|
48 | 52 | def parents(self): |
@@ -74,10 +78,17 b' class changectx(object):' | |||
|
74 | 78 | for f in m: |
|
75 | 79 | yield self.filectx(f, fileid=mf[f]) |
|
76 | 80 | |
|
81 | def ancestor(self, c2): | |
|
82 | """ | |
|
83 | return the ancestor context of self and c2 | |
|
84 | """ | |
|
85 | n = self._repo.changelog.ancestor(self._node, c2._node) | |
|
86 | return changectx(self._repo, n) | |
|
87 | ||
|
77 | 88 | class filectx(object): |
|
78 | 89 | """A filecontext object makes access to data related to a particular |
|
79 | 90 | filerevision convenient.""" |
|
80 | def __init__(self, repo, path, changeid=None, fileid=None): | |
|
91 | def __init__(self, repo, path, changeid=None, fileid=None, filelog=None): | |
|
81 | 92 | """changeid can be a changeset revision, node, or tag. |
|
82 | 93 | fileid can be a file revision or node.""" |
|
83 | 94 | self._repo = repo |
@@ -85,15 +96,18 b' class filectx(object):' | |||
|
85 | 96 | |
|
86 | 97 | assert changeid or fileid |
|
87 | 98 | |
|
99 | if filelog: | |
|
100 | self._filelog = filelog | |
|
101 | else: | |
|
102 | self._filelog = self._repo.file(self._path) | |
|
103 | ||
|
88 | 104 | if not fileid: |
|
89 | 105 | # if given a changeset id, go ahead and look up the file |
|
90 | 106 | self._changeid = changeid |
|
91 | 107 | self._changectx = self.changectx() |
|
92 | self._filelog = self._repo.file(self._path) | |
|
93 | 108 | self._filenode = self._changectx.filenode(self._path) |
|
94 | 109 | else: |
|
95 |
# else |
|
|
96 | self._filelog = self._repo.file(self._path) | |
|
110 | # else delay changectx creation | |
|
97 | 111 | self._filenode = self._filelog.lookup(fileid) |
|
98 | 112 | self._changeid = self._filelog.linkrev(self._filenode) |
|
99 | 113 | self._filerev = self._filelog.rev(self._filenode) |
@@ -118,18 +132,55 b' class filectx(object):' | |||
|
118 | 132 | def manifest(self): return self.changectx().manifest() |
|
119 | 133 | |
|
120 | 134 | def data(self): return self._filelog.read(self._filenode) |
|
121 | def metadata(self): return self._filelog.readmeta(self._filenode) | |
|
122 | 135 | def renamed(self): return self._filelog.renamed(self._filenode) |
|
136 | def path(self): return self._path | |
|
123 | 137 | |
|
124 | 138 | def parents(self): |
|
125 | # need to fix for renames | |
|
126 |
|
|
|
127 | return [ filectx(self._repo, self._path, fileid=x) for x in p ] | |
|
139 | p = self._path | |
|
140 | fl = self._filelog | |
|
141 | pl = [ (p, n, fl) for n in self._filelog.parents(self._filenode) ] | |
|
142 | ||
|
143 | r = self.renamed() | |
|
144 | if r: | |
|
145 | pl[0] = (r[0], r[1], None) | |
|
146 | ||
|
147 | return [ filectx(self._repo, p, fileid=n, filelog=l) | |
|
148 | for p,n,l in pl if n != nullid ] | |
|
128 | 149 | |
|
129 | 150 | def children(self): |
|
130 | 151 | # hard for renames |
|
131 | 152 | c = self._filelog.children(self._filenode) |
|
132 |
return [ filectx(self._repo, self._path, fileid=x |
|
|
153 | return [ filectx(self._repo, self._path, fileid=x, | |
|
154 | filelog=self._filelog) for x in c ] | |
|
133 | 155 | |
|
134 | 156 | def annotate(self): |
|
135 | 157 | return self._filelog.annotate(self._filenode) |
|
158 | ||
|
159 | def ancestor(self, fc2): | |
|
160 | """ | |
|
161 | find the common ancestor file context, if any, of self, and fc2 | |
|
162 | """ | |
|
163 | ||
|
164 | acache = {} | |
|
165 | flcache = {self._path:self._filelog, fc2._path:fc2._filelog} | |
|
166 | def parents(vertex): | |
|
167 | if vertex in acache: | |
|
168 | return acache[vertex] | |
|
169 | f, n = vertex | |
|
170 | if f not in flcache: | |
|
171 | flcache[f] = self._repo.file(f) | |
|
172 | fl = flcache[f] | |
|
173 | pl = [ (f,p) for p in fl.parents(n) if p != nullid ] | |
|
174 | re = fl.renamed(n) | |
|
175 | if re: | |
|
176 | pl.append(re) | |
|
177 | acache[vertex]=pl | |
|
178 | return pl | |
|
179 | ||
|
180 | a, b = (self._path, self._filenode), (fc2._path, fc2._filenode) | |
|
181 | v = ancestor.ancestor(a, b, parents) | |
|
182 | if v: | |
|
183 | f,n = v | |
|
184 | return filectx(self._repo, f, fileid=n, filelog=flcache[f]) | |
|
185 | ||
|
186 | return None |
@@ -37,7 +37,7 b' class filelog(revlog):' | |||
|
37 | 37 | s = t.index('\1\n', 2) |
|
38 | 38 | return t[s+2:] |
|
39 | 39 | |
|
40 | def readmeta(self, node): | |
|
40 | def _readmeta(self, node): | |
|
41 | 41 | t = self.revision(node) |
|
42 | 42 | if not t.startswith('\1\n'): |
|
43 | 43 | return {} |
@@ -60,7 +60,7 b' class filelog(revlog):' | |||
|
60 | 60 | def renamed(self, node): |
|
61 | 61 | if self.parents(node)[0] != nullid: |
|
62 | 62 | return False |
|
63 | m = self.readmeta(node) | |
|
63 | m = self._readmeta(node) | |
|
64 | 64 | if m and m.has_key("copy"): |
|
65 | 65 | return (m["copy"], bin(m["copyrev"])) |
|
66 | 66 | return False |
@@ -62,6 +62,9 b' static struct flist *lalloc(int size)' | |||
|
62 | 62 | { |
|
63 | 63 | struct flist *a = NULL; |
|
64 | 64 | |
|
65 | if (size < 1) | |
|
66 | size = 1; | |
|
67 | ||
|
65 | 68 | a = (struct flist *)malloc(sizeof(struct flist)); |
|
66 | 69 | if (a) { |
|
67 | 70 | a->base = (struct frag *)malloc(sizeof(struct frag) * size); |
@@ -13,7 +13,7 b' of the GNU General Public License, incor' | |||
|
13 | 13 | from node import * |
|
14 | 14 | from i18n import gettext as _ |
|
15 | 15 | from demandload import demandload |
|
16 |
demandload(globals(), "binascii changegroup errno |
|
|
16 | demandload(globals(), "binascii changegroup errno ancestor mdiff os") | |
|
17 | 17 | demandload(globals(), "sha struct util zlib") |
|
18 | 18 | |
|
19 | 19 | # revlog version strings |
@@ -1016,78 +1016,14 b' class revlog(object):' | |||
|
1016 | 1016 | def ancestor(self, a, b): |
|
1017 | 1017 | """calculate the least common ancestor of nodes a and b""" |
|
1018 | 1018 | |
|
1019 | # start with some short cuts for the linear cases | |
|
1020 | if a == b: | |
|
1021 | return a | |
|
1022 | ra = self.rev(a) | |
|
1023 | rb = self.rev(b) | |
|
1024 | if ra < rb: | |
|
1025 | last = b | |
|
1026 | first = a | |
|
1027 | else: | |
|
1028 | last = a | |
|
1029 | first = b | |
|
1030 | ||
|
1031 | # reachable won't include stop in the list, so we have to use a parent | |
|
1032 | reachable = self.reachable(last, stop=self.parents(first)[0]) | |
|
1033 | if first in reachable: | |
|
1034 | return first | |
|
1035 | ||
|
1036 | # calculate the distance of every node from root | |
|
1037 | dist = {nullid: 0} | |
|
1038 | for i in xrange(self.count()): | |
|
1039 | n = self.node(i) | |
|
1040 | p1, p2 = self.parents(n) | |
|
1041 | dist[n] = max(dist[p1], dist[p2]) + 1 | |
|
1019 | def parents(rev): | |
|
1020 | return [p for p in self.parentrevs(rev) if p != -1] | |
|
1042 | 1021 | |
|
1043 | # traverse ancestors in order of decreasing distance from root | |
|
1044 | def ancestors(node): | |
|
1045 | # we store negative distances because heap returns smallest member | |
|
1046 | h = [(-dist[node], node)] | |
|
1047 | seen = {} | |
|
1048 | while h: | |
|
1049 | d, n = heapq.heappop(h) | |
|
1050 | if n not in seen: | |
|
1051 | seen[n] = 1 | |
|
1052 | yield (-d, n) | |
|
1053 | for p in self.parents(n): | |
|
1054 | heapq.heappush(h, (-dist[p], p)) | |
|
1055 | ||
|
1056 | def generations(node): | |
|
1057 | sg, s = None, {} | |
|
1058 | for g,n in ancestors(node): | |
|
1059 | if g != sg: | |
|
1060 | if sg: | |
|
1061 | yield sg, s | |
|
1062 | sg, s = g, {n:1} | |
|
1063 | else: | |
|
1064 | s[n] = 1 | |
|
1065 | yield sg, s | |
|
1022 | c = ancestor.ancestor(self.rev(a), self.rev(b), parents) | |
|
1023 | if c is None: | |
|
1024 | return nullid | |
|
1066 | 1025 | |
|
1067 | x = generations(a) | |
|
1068 | y = generations(b) | |
|
1069 | gx = x.next() | |
|
1070 | gy = y.next() | |
|
1071 | ||
|
1072 | # increment each ancestor list until it is closer to root than | |
|
1073 | # the other, or they match | |
|
1074 | while 1: | |
|
1075 | #print "ancestor gen %s %s" % (gx[0], gy[0]) | |
|
1076 | if gx[0] == gy[0]: | |
|
1077 | # find the intersection | |
|
1078 | i = [ n for n in gx[1] if n in gy[1] ] | |
|
1079 | if i: | |
|
1080 | return i[0] | |
|
1081 | else: | |
|
1082 | #print "next" | |
|
1083 | gy = y.next() | |
|
1084 | gx = x.next() | |
|
1085 | elif gx[0] < gy[0]: | |
|
1086 | #print "next y" | |
|
1087 | gy = y.next() | |
|
1088 | else: | |
|
1089 | #print "next x" | |
|
1090 | gx = x.next() | |
|
1026 | return self.node(c) | |
|
1091 | 1027 | |
|
1092 | 1028 | def group(self, nodelist, lookup, infocollect=None): |
|
1093 | 1029 | """calculate a delta group |
General Comments 0
You need to be logged in to leave comments.
Login now