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.

mercurial/commands.py

@@ -1564,13 +1564,13 b' def debugindex(ui, repo, file_, **opts):'
             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"""

mercurial/revlog.py

@@ -217,6 +217,7 b' class revlog(object):'
         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 b' class revlog(object):'
         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 b' class revlog(object):'
         # 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 b' class revlog(object):'
 
         # 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 b' class revlog(object):'
                 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 b' class revlog(object):'
 
         if type(text) == str: # only accept immutable objects
             self._cache = (node, curr, text)
+        self._basecache = (curr, base)
         return node
 
     def group(self, nodelist, bundler):