--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mercurial/ancestor.py Fri Sep 22 08:48:56 2006 +0200
@@ -0,0 +1,83 @@
+# ancestor.py - generic DAG ancestor algorithm for mercurial
+#
+# Copyright 2006 Matt Mackall <mpm@selenic.com>
+#
+# This software may be used and distributed according to the terms
+# of the GNU General Public License, incorporated herein by reference.
+
+import heapq
+
+def ancestor(a, b, pfunc):
+ """
+ return the least common ancestor of nodes a and b or None if there
+ is no such ancestor.
+
+ pfunc must return a list of parent vertices
+ """
+
+ if a == b:
+ return a
+
+ # find depth from root of all ancestors
+ visit = [a, b]
+ depth = {}
+ while visit:
+ vertex = visit[-1]
+ pl = pfunc(vertex)
+ if not pl:
+ depth[vertex] = 0
+ visit.pop()
+ else:
+ for p in pl:
+ if p == a or p == b: # did we find a or b as a parent?
+ return p # we're done
+ if p not in depth:
+ visit.append(p)
+ if visit[-1] == vertex:
+ depth[vertex] = min([depth[p] for p in pl]) - 1
+ visit.pop()
+
+ # traverse ancestors in order of decreasing distance from root
+ def ancestors(vertex):
+ h = [(depth[vertex], vertex)]
+ seen = {}
+ while h:
+ d, n = heapq.heappop(h)
+ if n not in seen:
+ seen[n] = 1
+ yield (d, n)
+ for p in pfunc(n):
+ heapq.heappush(h, (depth[p], p))
+
+ 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]:
+ for v in gx[1]:
+ if v in gy[1]:
+ return v
+ gy = y.next()
+ gx = x.next()
+ elif gx[0] > gy[0]:
+ gy = y.next()
+ else:
+ gx = x.next()
+ except StopIteration:
+ return None
--- a/mercurial/context.py Tue Sep 19 10:22:30 2006 -0700
+++ b/mercurial/context.py Fri Sep 22 08:48:56 2006 +0200
@@ -5,6 +5,10 @@
# This software may be used and distributed according to the terms
# of the GNU General Public License, incorporated herein by reference.
+from node import *
+from demandload import demandload
+demandload(globals(), "ancestor")
+
class changectx(object):
"""A changecontext object makes access to data related to a particular
changeset convenient."""
@@ -42,7 +46,7 @@
def node(self): return self._node
def user(self): return self.changeset()[1]
def date(self): return self.changeset()[2]
- def changedfiles(self): return self.changeset()[3]
+ def files(self): return self.changeset()[3]
def description(self): return self.changeset()[4]
def parents(self):
@@ -74,10 +78,17 @@
for f in m:
yield self.filectx(f, fileid=mf[f])
+ def ancestor(self, c2):
+ """
+ return the ancestor context of self and c2
+ """
+ n = self._repo.changelog.ancestor(self._node, c2._node)
+ return changectx(self._repo, n)
+
class filectx(object):
"""A filecontext object makes access to data related to a particular
filerevision convenient."""
- def __init__(self, repo, path, changeid=None, fileid=None):
+ def __init__(self, repo, path, changeid=None, fileid=None, filelog=None):
"""changeid can be a changeset revision, node, or tag.
fileid can be a file revision or node."""
self._repo = repo
@@ -85,15 +96,18 @@
assert changeid or fileid
+ if filelog:
+ self._filelog = filelog
+ else:
+ self._filelog = self._repo.file(self._path)
+
if not fileid:
# if given a changeset id, go ahead and look up the file
self._changeid = changeid
self._changectx = self.changectx()
- self._filelog = self._repo.file(self._path)
self._filenode = self._changectx.filenode(self._path)
else:
- # else be lazy
- self._filelog = self._repo.file(self._path)
+ # else delay changectx creation
self._filenode = self._filelog.lookup(fileid)
self._changeid = self._filelog.linkrev(self._filenode)
self._filerev = self._filelog.rev(self._filenode)
@@ -118,18 +132,55 @@
def manifest(self): return self.changectx().manifest()
def data(self): return self._filelog.read(self._filenode)
- def metadata(self): return self._filelog.readmeta(self._filenode)
def renamed(self): return self._filelog.renamed(self._filenode)
+ def path(self): return self._path
def parents(self):
- # need to fix for renames
- p = self._filelog.parents(self._filenode)
- return [ filectx(self._repo, self._path, fileid=x) for x in p ]
+ p = self._path
+ fl = self._filelog
+ pl = [ (p, n, fl) for n in self._filelog.parents(self._filenode) ]
+
+ r = self.renamed()
+ if r:
+ pl[0] = (r[0], r[1], None)
+
+ return [ filectx(self._repo, p, fileid=n, filelog=l)
+ for p,n,l in pl if n != nullid ]
def children(self):
# hard for renames
c = self._filelog.children(self._filenode)
- return [ filectx(self._repo, self._path, fileid=x) for x in c ]
+ return [ filectx(self._repo, self._path, fileid=x,
+ filelog=self._filelog) for x in c ]
def annotate(self):
return self._filelog.annotate(self._filenode)
+
+ def ancestor(self, fc2):
+ """
+ find the common ancestor file context, if any, of self, and fc2
+ """
+
+ acache = {}
+ flcache = {self._path:self._filelog, fc2._path:fc2._filelog}
+ 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]
+ 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
+
+ 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])
+
+ return None
--- a/mercurial/filelog.py Tue Sep 19 10:22:30 2006 -0700
+++ b/mercurial/filelog.py Fri Sep 22 08:48:56 2006 +0200
@@ -37,7 +37,7 @@
s = t.index('\1\n', 2)
return t[s+2:]
- def readmeta(self, node):
+ def _readmeta(self, node):
t = self.revision(node)
if not t.startswith('\1\n'):
return {}
@@ -60,7 +60,7 @@
def renamed(self, node):
if self.parents(node)[0] != nullid:
return False
- m = self.readmeta(node)
+ m = self._readmeta(node)
if m and m.has_key("copy"):
return (m["copy"], bin(m["copyrev"]))
return False
--- a/mercurial/mpatch.c Tue Sep 19 10:22:30 2006 -0700
+++ b/mercurial/mpatch.c Fri Sep 22 08:48:56 2006 +0200
@@ -62,6 +62,9 @@
{
struct flist *a = NULL;
+ if (size < 1)
+ size = 1;
+
a = (struct flist *)malloc(sizeof(struct flist));
if (a) {
a->base = (struct frag *)malloc(sizeof(struct frag) * size);
--- a/mercurial/revlog.py Tue Sep 19 10:22:30 2006 -0700
+++ b/mercurial/revlog.py Fri Sep 22 08:48:56 2006 +0200
@@ -13,7 +13,7 @@
from node import *
from i18n import gettext as _
from demandload import demandload
-demandload(globals(), "binascii changegroup errno heapq mdiff os")
+demandload(globals(), "binascii changegroup errno ancestor mdiff os")
demandload(globals(), "sha struct util zlib")
# revlog version strings
@@ -1016,78 +1016,14 @@
def ancestor(self, a, b):
"""calculate the least common ancestor of nodes a and b"""
- # start with some short cuts for the linear cases
- if a == b:
- return a
- ra = self.rev(a)
- rb = self.rev(b)
- if ra < rb:
- last = b
- first = a
- else:
- last = a
- first = b
-
- # reachable won't include stop in the list, so we have to use a parent
- reachable = self.reachable(last, stop=self.parents(first)[0])
- if first in reachable:
- return first
-
- # calculate the distance of every node from root
- dist = {nullid: 0}
- for i in xrange(self.count()):
- n = self.node(i)
- p1, p2 = self.parents(n)
- dist[n] = max(dist[p1], dist[p2]) + 1
+ def parents(rev):
+ return [p for p in self.parentrevs(rev) if p != -1]
- # traverse ancestors in order of decreasing distance from root
- def ancestors(node):
- # we store negative distances because heap returns smallest member
- h = [(-dist[node], node)]
- seen = {}
- while h:
- d, n = heapq.heappop(h)
- if n not in seen:
- seen[n] = 1
- yield (-d, n)
- for p in self.parents(n):
- heapq.heappush(h, (-dist[p], p))
-
- def generations(node):
- sg, s = None, {}
- for g,n in ancestors(node):
- if g != sg:
- if sg:
- yield sg, s
- sg, s = g, {n:1}
- else:
- s[n] = 1
- yield sg, s
+ c = ancestor.ancestor(self.rev(a), self.rev(b), parents)
+ if c is None:
+ return nullid
- 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
- while 1:
- #print "ancestor gen %s %s" % (gx[0], gy[0])
- if gx[0] == gy[0]:
- # find the intersection
- i = [ n for n in gx[1] if n in gy[1] ]
- if i:
- return i[0]
- else:
- #print "next"
- gy = y.next()
- gx = x.next()
- elif gx[0] < gy[0]:
- #print "next y"
- gy = y.next()
- else:
- #print "next x"
- gx = x.next()
+ return self.node(c)
def group(self, nodelist, lookup, infocollect=None):
"""calculate a delta group