# HG changeset patch
# User Chris Mason <mason@suse.com>
# Date 1144368789 14400
# Node ID 416d8b2a75b85d2f20d7c1f9a16b3f7fef082160
# Parent  1cbb14c048cb78d7621bcd7ab677ee6e0fd096f5
Speedup revlog.ancestors for the linear case

revlog.ancestors can be expensive on big repos.  This cuts down the overall
time for hg update by ~19% by short cutting revlog.ancestors when one of the
revisions is reachable from another.



diff --git a/mercurial/revlog.py b/mercurial/revlog.py
--- a/mercurial/revlog.py
+++ b/mercurial/revlog.py
@@ -940,6 +940,24 @@ class revlog(object):
 
     def ancestor(self, a, b):
         """calculate the least common ancestor of nodes a and b"""
+
+        # start with some short cuts for the linear cases
+        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()):