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