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 |
|