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.
--- a/mercurial/ancestor.py Tue Apr 16 10:08:18 2013 -0700
+++ b/mercurial/ancestor.py Tue Apr 16 10:08:19 2013 -0700
@@ -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 @@
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.
--- a/mercurial/revlog.py Tue Apr 16 10:08:18 2013 -0700
+++ b/mercurial/revlog.py Tue Apr 16 10:08:19 2013 -0700
@@ -705,17 +705,12 @@
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):