[PATCH 2 of 4 resend] revlog: choose a consistent ancestor when there's a tie

[Bryan O'Sullivan]

# HG changeset patch
# User Bryan O'Sullivan <bryano at fb.com>
# Date 1366132099 25200
#      Tue Apr 16 10:08:19 2013 -0700
# Node ID 3605d4e7e6184fc2a9d40521083283044bd1a5df
# Parent  2f7186400a072015db1d962adfecaaac5dd40a24
revlog: choose a consistent ancestor when there's a tie

Previously, we chose a rev based on numeric ordering, which could
cause "the same merge" in topologically identical but numerically
different repos to choose different merge bases.

We now choose the lexically least node; this is stable across
different revlog orderings.

diff --git a/mercurial/ancestor.py b/mercurial/ancestor.py
--- a/mercurial/ancestor.py
+++ b/mercurial/ancestor.py
@@ -5,7 +5,7 @@
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
-import error, heapq, util
+import heapq, util
 from node import nullrev
 
 def ancestors(pfunc, *orignodes):
@@ -213,51 +213,6 @@ def genericancestor(a, b, pfunc):
     except StopIteration:
         return None
 
-def finddepths(nodes, pfunc):
-    visit = list(nodes)
-    rootpl = [nullrev, nullrev]
-    depth = {}
-    while visit:
-        vertex = visit[-1]
-        pl = pfunc(vertex)
-        if not pl or pl == rootpl:
-            depth[vertex] = 0
-            visit.pop()
-        else:
-            for p in pl:
-                if p != nullrev and p not in depth:
-                    visit.append(p)
-            if visit[-1] == vertex:
-                dp = [depth[p] for p in pl if p != nullrev]
-                if dp:
-                    depth[vertex] = max(dp) + 1
-                else:
-                    depth[vertex] = 0
-                visit.pop()
-    return depth
-
-def ancestor(a, b, pfunc):
-    xs = ancestors(pfunc, a, b)
-    y = genericancestor(a, b, pfunc)
-    if y == -1:
-        y = None
-    if not xs:
-        if y is None:
-            return None
-        print xs, y
-        raise error.RepoError('ancestors disagree on whether a gca exists')
-    elif y is None:
-        print xs, y
-        raise error.RepoError('ancestors disagree on whether a gca exists')
-    if y in xs:
-        return y
-    xds = finddepths(xs, pfunc)
-    xds = [ds[x] for x in xs]
-    yd = finddepths([y], pfunc)[y]
-    if len([xd != yd for xd in xds]) > 0:
-        raise error.RepoError('ancestor depths do not match')
-    return xs.pop()
-
 def missingancestors(revs, bases, pfunc):
     """Return all the ancestors of revs that are not ancestors of bases.
 
diff --git a/mercurial/revlog.py b/mercurial/revlog.py
--- a/mercurial/revlog.py
+++ b/mercurial/revlog.py
@@ -705,17 +705,12 @@ class revlog(object):
     def ancestor(self, a, b):
         """calculate the least common ancestor of nodes a and b"""
 
-        # fast path, check if it is a descendant
         a, b = self.rev(a), self.rev(b)
-        start, end = sorted((a, b))
-        if self.descendant(start, end):
-            return self.node(start)
-
-        c = ancestor.ancestor(a, b, self.parentrevs)
-        if c is None:
-            return nullid
-
-        return self.node(c)
+        ancs = ancestor.ancestors(self.parentrevs, a, b)
+        if ancs:
+            # choose a consistent winner when there's a tie
+            return min(map(self.node, ancs))
+        return nullid
 
     def _match(self, id):
         if isinstance(id, int):