### changeset 3135:b1db258e875c

Abstract ancestor algorithm into generic function Make depth calculation non-recursive Add simple shortcut for linear ancestry Convert context to use ancestor function make memoized parents function Convert revlog to use ancestor function
author Matt Mackall Wed, 20 Sep 2006 16:50:50 -0500 abd9a05fca0b 2c472ab42b08 mercurial/ancestor.py mercurial/context.py mercurial/revlog.py 3 files changed, 107 insertions(+), 169 deletions(-) [+]
line wrap: on
line diff
```--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/mercurial/ancestor.py	Wed Sep 20 16:50:50 2006 -0500
@@ -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 15:28:13 2006 -0500
+++ b/mercurial/context.py	Wed Sep 20 16:50:50 2006 -0500
@@ -7,7 +7,7 @@

from node import *

class changectx(object):
@@ -161,103 +161,26 @@
find the common ancestor file context, if any, of self, and fc2
"""

-        a, b = (self._path, self._filenode), (fc2._path, fc2._filenode)
-
-        if a == b:
-            return self
-
-        if a[0] == b[0]:
-            n = self._filelog.ancestor(a[1], b[1])
-            if n != nullid:
-                return filectx(self._repo, self._path,
-                               fileid=n, filelog=self._filelog)
-
-        # build a graph of all ancestors, crossing renames
-        ag = {}
-        fv = [a, b]
+        acache = {}
flcache = {self._path:self._filelog, fc2._path:fc2._filelog}
-
-        while fv:
-            f,n = fv.pop()
-            try:
-                fl = flcache[f]
-            except KeyError:
+        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]
-            v = [n]
-            while v:
-                n = v.pop()
-                c = (f, n)
-                if c in ag:
-                    continue
-
-                pl = [ n for n in fl.parents(n) if n != nullid ]
-                v += pl
-                pl = [ (f, n) for n in pl ]
-                re = fl.renamed(n)
-                if re:
-                    pl.append(re)
-                    if re not in ag:
-                        fv.append(re)
-                ag[c] = pl
+            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

-        dist = {}
-        def depth(node):
-            try:
-                return dist[node]
-            except KeyError:
-                pl = ag[node]
-                if not pl:
-                    dist[node] = 0
-                else:
-                    dist[node] = max([depth(p) for p in pl]) + 1
-                return dist[node]
-
-        # traverse ancestors in order of decreasing distance from root
-        def ancestors(vertex):
-            h = [(-depth(vertex), vertex)]
-            seen = {}
-            while h:
-                d, v = heapq.heappop(h)
-                if v not in seen:
-                    seen[v] = 1
-                    yield (-d, v)
-                    for p in ag[v]:
-                        heapq.heappush(h, (-depth(p), p))
+        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])

-        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]:
-                    # find the intersection
-                    i = [ n for n in gx[1] if n in gy[1] ]
-                    if i:
-                        fp,fn = i[0]
-                        fl = flcache[fp]
-                        return filectx(self._repo, fp, fileid=fn, filelog=fl)
-                    else:
-                        gy = y.next()
-                        gx = x.next()
-                elif gx[0] < gy[0]:
-                    gy = y.next()
-                else:
-                    gx = x.next()
-        except StopIteration:
-            return None
+        return None```
```--- a/mercurial/revlog.py	Tue Sep 19 15:28:13 2006 -0500
+++ b/mercurial/revlog.py	Wed Sep 20 16:50:50 2006 -0500
@@ -13,7 +13,7 @@
from node import *
from i18n import gettext as _
-demandload(globals(), "binascii changegroup errno heapq mdiff os")
+demandload(globals(), "binascii changegroup errno ancestor mdiff os")

# revlog version strings
@@ -1016,78 +1016,10 @@
def ancestor(self, a, b):
"""calculate the least common ancestor of nodes a and b"""

-        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(node):
+            return [p for p in self.parents(node) if p != nullid]

-        # 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
-
-        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 ancestor.ancestor(a, b, parents) or nullid

def group(self, nodelist, lookup, infocollect=None):
"""calculate a delta group```