Mercurial > hg > mercurial-crew-with-dirclash

comparison mercurial/context.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 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