Mercurial > public > mercurial-scm > hg

comparison mercurial/context.py @ 3126:4bf2e895cf86

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
filectx: add rename-aware ancestor algorithm This code works but may trigger recursion depth issues
author Matt Mackall <mpm@selenic.com>
date Tue, 19 Sep 2006 14:58:54 -0500
parents 02b22fefc01f
children abd9a05fca0b
comparison
equal deleted inserted replaced
3125:02b22fefc01f 3126:4bf2e895cf86
4 # 4 #
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
10 demandload(globals(), "heapq")
9 11
10 class changectx(object): 12 class changectx(object):
11 """A changecontext object makes access to data related to a particular 13 """A changecontext object makes access to data related to a particular
12 changeset convenient.""" 14 changeset convenient."""
13 def __init__(self, repo, changeid): 15 def __init__(self, repo, changeid):
143 filelog=self._filelog) for x in c ] 145 filelog=self._filelog) for x in c ]
144 146
145 def annotate(self): 147 def annotate(self):
146 return self._filelog.annotate(self._filenode) 148 return self._filelog.annotate(self._filenode)
147 149
150 def ancestor(self, fc2):
151 """
152 find the common ancestor file context, if any, of self, and fc2
153 """
154
155 a, b = (self._path, self._filenode), (fc2._path, fc2._filenode)
156
157 if a == b:
158 return self
159
160 if a[0] == b[0]:
161 n = self._filelog.ancestor(a[1], b[1])
162 if n != nullid:
163 return filectx(self._repo, self._path,
164 fileid=n, filelog=self._filelog)
165
166 # build a graph of all ancestors, crossing renames
167 ag = {}
168 fv = [a, b]
169 flcache = {self._path:self._filelog, fc2._path:fc2._filelog}
170
171 while fv:
172 f,n = fv.pop()
173 try:
174 fl = flcache[f]
175 except KeyError:
176 flcache[f] = self._repo.file(f)
177 fl = flcache[f]
178 v = [n]
179 while v:
180 n = v.pop()
181 c = (f, n)
182 if c in ag:
183 continue
184
185 pl = [ n for n in fl.parents(n) if n != nullid ]
186 v += pl
187 pl = [ (f, n) for n in pl ]
188 re = fl.renamed(n)
189 if re:
190 pl.append(re)
191 if re not in ag:
192 fv.append(re)
193 ag[c] = pl
194
195 dist = {}
196 def depth(node):
197 try:
198 return dist[node]
199 except KeyError:
200 pl = ag[node]
201 if not pl:
202 dist[node] = 0
203 else:
204 dist[node] = max([depth(p) for p in pl]) + 1
205 return dist[node]
206
207 # traverse ancestors in order of decreasing distance from root
208 def ancestors(vertex):
209 h = [(-depth(vertex), vertex)]
210 seen = {}
211 while h:
212 d, v = heapq.heappop(h)
213 if v not in seen:
214 seen[v] = 1
215 yield (-d, v)
216 for p in ag[v]:
217 heapq.heappush(h, (-depth(p), p))
218
219 def generations(vertex):
220 sg, s = None, {}
221 for g,v in ancestors(vertex):
222 if g != sg:
223 if sg:
224 yield sg, s
225 sg, s = g, {v:1}
226 else:
227 s[v] = 1
228 yield sg, s
229
230 x = generations(a)
231 y = generations(b)
232 gx = x.next()
233 gy = y.next()
234
235 # increment each ancestor list until it is closer to root than
236 # the other, or they match
237 try:
238 while 1:
239 if gx[0] == gy[0]:
240 # find the intersection
241 i = [ n for n in gx[1] if n in gy[1] ]
242 if i:
243 fp,fn = i[0]
244 fl = flcache[fp]
245 return filectx(self._repo, fp, fileid=fn, filelog=fl)
246 else:
247 gy = y.next()
248 gx = x.next()
249 elif gx[0] < gy[0]:
250 gy = y.next()
251 else:
252 gx = x.next()
253 except StopIteration:
254 return None