--- a/mercurial/context.py Tue Sep 19 15:28:13 2006 -0500
+++ b/mercurial/context.py Wed Sep 20 16:50:50 2006 -0500
@@ -7,7 +7,7 @@
from node import *
from demandload import demandload
-demandload(globals(), "heapq")
+demandload(globals(), "ancestor")
class changectx(object):
"""A changecontext object makes access to data related to a particular
@@ -161,103 +161,26 @@
find the common ancestor file context, if any, of self, and fc2
"""
- a, b = (self._path, self._filenode), (fc2._path, fc2._filenode)
-
- if a == b:
- return self
-
- if a[0] == b[0]:
- n = self._filelog.ancestor(a[1], b[1])
- if n != nullid:
- return filectx(self._repo, self._path,
- fileid=n, filelog=self._filelog)
-
- # build a graph of all ancestors, crossing renames
- ag = {}
- fv = [a, b]
+ acache = {}
flcache = {self._path:self._filelog, fc2._path:fc2._filelog}
-
- while fv:
- f,n = fv.pop()
- try:
- fl = flcache[f]
- except KeyError:
+ def parents(vertex):
+ if vertex in acache:
+ return acache[vertex]
+ f, n = vertex
+ if f not in flcache:
flcache[f] = self._repo.file(f)
- fl = flcache[f]
- v = [n]
- while v:
- n = v.pop()
- c = (f, n)
- if c in ag:
- continue
-
- pl = [ n for n in fl.parents(n) if n != nullid ]
- v += pl
- pl = [ (f, n) for n in pl ]
- re = fl.renamed(n)
- if re:
- pl.append(re)
- if re not in ag:
- fv.append(re)
- ag[c] = pl
+ fl = flcache[f]
+ pl = [ (f,p) for p in fl.parents(n) if p != nullid ]
+ re = fl.renamed(n)
+ if re:
+ pl.append(re)
+ acache[vertex]=pl
+ return pl
- dist = {}
- def depth(node):
- try:
- return dist[node]
- except KeyError:
- pl = ag[node]
- if not pl:
- dist[node] = 0
- else:
- dist[node] = max([depth(p) for p in pl]) + 1
- return dist[node]
-
- # traverse ancestors in order of decreasing distance from root
- def ancestors(vertex):
- h = [(-depth(vertex), vertex)]
- seen = {}
- while h:
- d, v = heapq.heappop(h)
- if v not in seen:
- seen[v] = 1
- yield (-d, v)
- for p in ag[v]:
- heapq.heappush(h, (-depth(p), p))
+ a, b = (self._path, self._filenode), (fc2._path, fc2._filenode)
+ v = ancestor.ancestor(a, b, parents)
+ if v:
+ f,n = v
+ return filectx(self._repo, f, fileid=n, filelog=flcache[f])
- def generations(vertex):
- sg, s = None, {}
- for g,v in ancestors(vertex):
- if g != sg:
- if sg:
- yield sg, s
- sg, s = g, {v:1}
- else:
- s[v] = 1
- yield sg, s
-
- x = generations(a)
- y = generations(b)
- gx = x.next()
- gy = y.next()
-
- # increment each ancestor list until it is closer to root than
- # the other, or they match
- try:
- while 1:
- if gx[0] == gy[0]:
- # find the intersection
- i = [ n for n in gx[1] if n in gy[1] ]
- if i:
- fp,fn = i[0]
- fl = flcache[fp]
- return filectx(self._repo, fp, fileid=fn, filelog=fl)
- else:
- gy = y.next()
- gx = x.next()
- elif gx[0] < gy[0]:
- gy = y.next()
- else:
- gx = x.next()
- except StopIteration:
- return None
+ return None