Fix recursion depth trouble with ancestor algorithm

mercurial/revlog.py

@@ -1,211 +1,229 b''
 # revlog.py - storage back-end for mercurial
 #
 # This provides efficient delta storage with O(1) retrieve and append
 # and O(changes) merge between branches
 #
 # Copyright 2005 Matt Mackall <[e-mail]>
 #
 # This software may be used and distributed according to the terms
 # of the GNU General Public License, incorporated herein by reference.
 
 import zlib, struct, sha, os, tempfile, binascii
 from mercurial import mdiff
 
 def hex(node): return binascii.hexlify(node)
 def bin(node): return binascii.unhexlify(node)
 
 def compress(text):
     return zlib.compress(text)
 
 def decompress(bin):
     return zlib.decompress(bin)
 
 def hash(text, p1, p2):
     l = [p1, p2]
     l.sort()
     return sha.sha(l[0] + l[1] + text).digest()
 
 nullid = "\0" * 20
 indexformat = ">4l20s20s20s"
 
 class revlog:
     def __init__(self, opener, indexfile, datafile):
         self.indexfile = indexfile
         self.datafile = datafile
         self.index = []
         self.opener = opener
         self.cache = None
         self.nodemap = {nullid: -1}
         # read the whole index for now, handle on-demand later
         try:
             n = 0
             i = self.opener(self.indexfile).read()
             s = struct.calcsize(indexformat)
             for f in range(0, len(i), s):
                 # offset, size, base, linkrev, p1, p2, nodeid
                 e = struct.unpack(indexformat, i[f:f + s])
                 self.nodemap[e[6]] = n
                 self.index.append(e)
                 n += 1
         except IOError: pass
 
     def tip(self): return self.node(len(self.index) - 1)
     def count(self): return len(self.index)
     def node(self, rev): return (rev < 0) and nullid or self.index[rev][6]
     def rev(self, node): return self.nodemap[node]
     def linkrev(self, node): return self.index[self.nodemap[node]][3]
     def parents(self, node):
         if node == nullid: return (nullid, nullid)
         return self.index[self.nodemap[node]][4:6]
 
     def start(self, rev): return self.index[rev][0]
     def length(self, rev): return self.index[rev][1]
     def end(self, rev): return self.start(rev) + self.length(rev)
     def base(self, rev): return self.index[rev][2]
 
     def lookup(self, id):
         try:
             rev = int(id)
             return self.node(rev)
         except ValueError:
             c = []
             for n in self.nodemap:
                 if id in hex(n):
                     c.append(n)
             if len(c) > 1: raise KeyError("Ambiguous identifier")
             if len(c) < 1: raise KeyError
             return c[0]
                 
         return None
 
     def revisions(self, list):
         # this can be optimized to do spans, etc
         # be stupid for now
         for node in list:
             yield self.revision(node)
 
     def diff(self, a, b):
         return mdiff.textdiff(a, b)
 
     def patch(self, text, patch):
         return mdiff.patch(text, patch)
 
     def revision(self, node):
         if node == nullid: return ""
         if self.cache and self.cache[0] == node: return self.cache[2]
 
         text = None
         rev = self.rev(node)
         base = self.base(rev)
         start = self.start(base)
         end = self.end(rev)
 
         if self.cache and self.cache[1] >= base and self.cache[1] < rev:
             base = self.cache[1]
             start = self.start(base + 1)
             text = self.cache[2]
             last = 0
 
         f = self.opener(self.datafile)
         f.seek(start)
         data = f.read(end - start)
 
         if not text:
             last = self.length(base)
             text = decompress(data[:last])
 
         for r in range(base + 1, rev + 1):
             s = self.length(r)
             b = decompress(data[last:last + s])
             text = self.patch(text, b)
             last = last + s
 
         (p1, p2) = self.parents(node)
         if node != hash(text, p1, p2):
             raise "integrity check failed on %s:%d" % (self.datafile, rev)
 
         self.cache = (node, rev, text)
         return text  
 
     def addrevision(self, text, transaction, link, p1=None, p2=None):
         if text is None: text = ""
         if p1 is None: p1 = self.tip()
         if p2 is None: p2 = nullid
 
         node = hash(text, p1, p2)
 
         n = self.count()
         t = n - 1
 
         if n:
             start = self.start(self.base(t))
             end = self.end(t)
             prev = self.revision(self.tip())
             data = compress(self.diff(prev, text))
 
         # full versions are inserted when the needed deltas
         # become comparable to the uncompressed text
         if not n or (end + len(data) - start) > len(text) * 2:
             data = compress(text)
             base = n
         else:
             base = self.base(t)
 
         offset = 0
         if t >= 0:
             offset = self.end(t)
 
         e = (offset, len(data), base, link, p1, p2, node)
         
         self.index.append(e)
         self.nodemap[node] = n
         entry = struct.pack(indexformat, *e)
 
         transaction.add(self.datafile, e[0])
         self.opener(self.datafile, "a").write(data)
         transaction.add(self.indexfile, n * len(entry))
         self.opener(self.indexfile, "a").write(entry)
 
         self.cache = (node, n, text)
         return node
 
     def ancestor(self, a, b):
-        def expand(e1, e2, a1, a2):
-            ne = []
-            for n in e1:
-                (p1, p2) = self.parents(n)
-                if p1 in a2: return p1
-                if p2 in a2: return p2
-                if p1 != nullid and p1 not in a1:
-                    a1[p1] = 1
-                    ne.append(p1)
-                if p2 != nullid and p2 not in a1:
-                    a1[p2] = 1
-                    ne.append(p2)
-            return expand(e2, ne, a2, a1)
-        return expand([a], [b], {a:1}, {b:1})
+        def expand(list, map):
+            a = []
+            while list:
+                n = list.pop(0)
+                map[n] = 1
+                yield n
+                for p in self.parents(n):
+                    if p != nullid and p not in map:
+                        list.append(p)
+            yield nullid
+
+        amap = {}
+        bmap = {}
+        ag = expand([a], amap)
+        bg = expand([b], bmap)
+        adone = bdone = 0
+
+        while not adone or not bdone:
+            if not adone:
+                an = ag.next()
+                if an == nullid:
+                    adone = 1
+                elif an in bmap:
+                    return an
+            if not bdone:
+                bn = bg.next()
+                if bn == nullid:
+                    bdone = 1
+                elif bn in amap:
+                    return bn
+
+        return nullid
 
     def mergedag(self, other, transaction, linkseq, accumulate = None):
         """combine the nodes from other's DAG into ours"""
         old = self.tip()
         i = self.count()
         l = []
 
         # merge the other revision log into our DAG
         for r in range(other.count()):
             id = other.node(r)
             if id not in self.nodemap:
                 (xn, yn) = other.parents(id)
                 l.append((id, xn, yn))
                 self.nodemap[id] = i
                 i += 1
 
         # merge node date for new nodes
         r = other.revisions([e[0] for e in l])
         for e in l:
             t = r.next()
             if accumulate: accumulate(t)
             self.addrevision(t, transaction, linkseq.next(), e[1], e[2])
 
         # return the unmerged heads for later resolving
         return (old, self.tip())