revlog: calculate base revisions iteratively

revlog: calculate base revisions iteratively

This is in preparation for generaldelta, where the revlog entry base field is
reinterpreted as the deltaparent. For that reason we also rename the base
function to chainbase.

Without generaldelta, performance is unaffected, but generaldelta will suffer
from this in _addrevision, since delta chains will be walked repeatedly.
A cache has been added to eliminate this problem completely.

--- a/mercurial/commands.py	Sat May 07 22:37:40 2011 +0200
+++ b/mercurial/commands.py	Sat May 07 22:40:14 2011 +0200
@@ -1564,13 +1564,13 @@
             except:
                 pp = [nullid, nullid]
             ui.write("% 6d % 9d % 7d % 6d % 7d %s %s %s\n" % (
-                    i, r.start(i), r.length(i), r.base(i), r.linkrev(i),
+                    i, r.start(i), r.length(i), r.chainbase(i), r.linkrev(i),
                     short(node), short(pp[0]), short(pp[1])))
         elif format == 1:
             pr = r.parentrevs(i)
             ui.write("% 6d %04x % 8d % 8d % 8d % 6d % 6d % 6d % 6d %s\n" % (
                     i, r.flags(i), r.start(i), r.length(i), r.rawsize(i),
-                    r.base(i), r.linkrev(i), pr[0], pr[1], short(node)))
+                    r.chainbase(i), r.linkrev(i), pr[0], pr[1], short(node)))
 
 def debugindexdot(ui, repo, file_):
     """dump an index DAG as a graphviz dot file"""

--- a/mercurial/revlog.py	Sat May 07 22:37:40 2011 +0200
+++ b/mercurial/revlog.py	Sat May 07 22:40:14 2011 +0200
@@ -217,6 +217,7 @@
         self.datafile = indexfile[:-2] + ".d"
         self.opener = opener
         self._cache = None
+        self._basecache = None
         self._chunkcache = (0, '')
         self.index = []
         self._pcache = {}
@@ -313,8 +314,13 @@
         return self.start(rev) + self.length(rev)
     def length(self, rev):
         return self.index[rev][1]
-    def base(self, rev):
-        return self.index[rev][3]
+    def chainbase(self, rev):
+        index = self.index
+        base = index[rev][3]
+        while base != rev:
+            rev = base
+            base = index[rev][3]
+        return base
     def flags(self, rev):
         return self.index[rev][0] & 0xFFFF
     def rawsize(self, rev):
@@ -850,7 +856,6 @@
         # look up what we need to read
         text = None
         rev = self.rev(node)
-        base = self.base(rev)
 
         # check rev flags
         if self.flags(rev) & ~REVIDX_KNOWN_FLAGS:
@@ -859,10 +864,13 @@
 
         # build delta chain
         chain = []
+        index = self.index # for performance
         iterrev = rev
-        while iterrev != base and iterrev != cachedrev:
+        e = index[iterrev]
+        while iterrev != e[3] and iterrev != cachedrev:
             chain.append(iterrev)
             iterrev -= 1
+            e = index[iterrev]
         chain.reverse()
         base = iterrev
 
@@ -984,7 +992,11 @@
                 delta = mdiff.textdiff(ptext, t)
             data = compress(delta)
             l = len(data[1]) + len(data[0])
-            base = self.base(rev)
+            basecache = self._basecache
+            if basecache and basecache[0] == rev:
+                base = basecache[1]
+            else:
+                base = self.chainbase(rev)
             dist = l + offset - self.start(base)
             return dist, l, data, base
 
@@ -1038,6 +1050,7 @@
 
         if type(text) == str: # only accept immutable objects
             self._cache = (node, curr, text)
+        self._basecache = (curr, base)
         return node
 
     def group(self, nodelist, bundler):