Mercurial > hg > mercurial-crew-with-dirclash
comparison mercurial/context.py @ 3136:b1db258e875c
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 | abd9a05fca0b |
children | db25f7b80fdb |
comparison
equal
deleted
inserted
replaced
3135:abd9a05fca0b | 3136:b1db258e875c |
---|---|
5 # This software may be used and distributed according to the terms | 5 # This software may be used and distributed according to the terms |
6 # of the GNU General Public License, incorporated herein by reference. | 6 # of the GNU General Public License, incorporated herein by reference. |
7 | 7 |
8 from node import * | 8 from node import * |
9 from demandload import demandload | 9 from demandload import demandload |
10 demandload(globals(), "heapq") | 10 demandload(globals(), "ancestor") |
11 | 11 |
12 class changectx(object): | 12 class changectx(object): |
13 """A changecontext object makes access to data related to a particular | 13 """A changecontext object makes access to data related to a particular |
14 changeset convenient.""" | 14 changeset convenient.""" |
15 def __init__(self, repo, changeid=None): | 15 def __init__(self, repo, changeid=None): |
159 def ancestor(self, fc2): | 159 def ancestor(self, fc2): |
160 """ | 160 """ |
161 find the common ancestor file context, if any, of self, and fc2 | 161 find the common ancestor file context, if any, of self, and fc2 |
162 """ | 162 """ |
163 | 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 | |
164 a, b = (self._path, self._filenode), (fc2._path, fc2._filenode) | 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]) | |
165 | 185 |
166 if a == b: | 186 return None |
167 return self | |
168 | |
169 if a[0] == b[0]: | |
170 n = self._filelog.ancestor(a[1], b[1]) | |
171 if n != nullid: | |
172 return filectx(self._repo, self._path, | |
173 fileid=n, filelog=self._filelog) | |
174 | |
175 # build a graph of all ancestors, crossing renames | |
176 ag = {} | |
177 fv = [a, b] | |
178 flcache = {self._path:self._filelog, fc2._path:fc2._filelog} | |
179 | |
180 while fv: | |
181 f,n = fv.pop() | |
182 try: | |
183 fl = flcache[f] | |
184 except KeyError: | |
185 flcache[f] = self._repo.file(f) | |
186 fl = flcache[f] | |
187 v = [n] | |
188 while v: | |
189 n = v.pop() | |
190 c = (f, n) | |
191 if c in ag: | |
192 continue | |
193 | |
194 pl = [ n for n in fl.parents(n) if n != nullid ] | |
195 v += pl | |
196 pl = [ (f, n) for n in pl ] | |
197 re = fl.renamed(n) | |
198 if re: | |
199 pl.append(re) | |
200 if re not in ag: | |
201 fv.append(re) | |
202 ag[c] = pl | |
203 | |
204 dist = {} | |
205 def depth(node): | |
206 try: | |
207 return dist[node] | |
208 except KeyError: | |
209 pl = ag[node] | |
210 if not pl: | |
211 dist[node] = 0 | |
212 else: | |
213 dist[node] = max([depth(p) for p in pl]) + 1 | |
214 return dist[node] | |
215 | |
216 # traverse ancestors in order of decreasing distance from root | |
217 def ancestors(vertex): | |
218 h = [(-depth(vertex), vertex)] | |
219 seen = {} | |
220 while h: | |
221 d, v = heapq.heappop(h) | |
222 if v not in seen: | |
223 seen[v] = 1 | |
224 yield (-d, v) | |
225 for p in ag[v]: | |
226 heapq.heappush(h, (-depth(p), p)) | |
227 | |
228 def generations(vertex): | |
229 sg, s = None, {} | |
230 for g,v in ancestors(vertex): | |
231 if g != sg: | |
232 if sg: | |
233 yield sg, s | |
234 sg, s = g, {v:1} | |
235 else: | |
236 s[v] = 1 | |
237 yield sg, s | |
238 | |
239 x = generations(a) | |
240 y = generations(b) | |
241 gx = x.next() | |
242 gy = y.next() | |
243 | |
244 # increment each ancestor list until it is closer to root than | |
245 # the other, or they match | |
246 try: | |
247 while 1: | |
248 if gx[0] == gy[0]: | |
249 # find the intersection | |
250 i = [ n for n in gx[1] if n in gy[1] ] | |
251 if i: | |
252 fp,fn = i[0] | |
253 fl = flcache[fp] | |
254 return filectx(self._repo, fp, fileid=fn, filelog=fl) | |
255 else: | |
256 gy = y.next() | |
257 gx = x.next() | |
258 elif gx[0] < gy[0]: | |
259 gy = y.next() | |
260 else: | |
261 gx = x.next() | |
262 except StopIteration: | |
263 return None |