[PATCH] ancestors: add stopfunc to revlog.ancestors

[Durham Goode]

# HG changeset patch
# User Durham Goode <durham at fb.com>
# Date 1446945262 28800
#      Sat Nov 07 17:14:22 2015 -0800
# Node ID ed19800302c1e16491ec40cedea37b304774f1d2
# Parent  60db725e6c3d79385908a948ce5620419c22ac51
ancestors: add stopfunc to revlog.ancestors

This adds a stopfunc argument to revlog.ancestors. This allows the caller to
specify a function that can be used to stop the ancestor traversal.

This is useful in situations where we need to walk the graph up to a certain
point. Ex: efficiently walking draft ancestors; efficiently walking ancestors
that match a certain date criteria

This is necessary for improving the performance of the inhibit extension
detecting new obsolete nodes to inhibit (by preventing it from walking public
commits).

diff --git a/mercurial/ancestor.py b/mercurial/ancestor.py
--- a/mercurial/ancestor.py
+++ b/mercurial/ancestor.py
@@ -258,7 +258,7 @@ class incrementalmissingancestors(object
         return missing
 
 class lazyancestors(object):
-    def __init__(self, pfunc, revs, stoprev=0, inclusive=False):
+    def __init__(self, pfunc, revs, stoprev=0, inclusive=False, stopfunc=None):
         """Create a new object generating ancestors for the given revs. Does
         not generate revs lower than stoprev.
 
@@ -269,12 +269,22 @@ class lazyancestors(object):
         a boolean that indicates whether revs should be included. Revs lower
         than stoprev will not be generated.
 
+        If `stopfunc` is specified, stopfunc will be called for each ancestor,
+        and if it returns True, the traversal will stop at that ancestor.
+
         Result does not include the null revision."""
         self._parentrevs = pfunc
         self._initrevs = revs
         self._stoprev = stoprev
         self._inclusive = inclusive
 
+        if stopfunc:
+            def stopparentrevs(rev):
+                for parentrev in pfunc(rev):
+                    if not stopfunc(parentrev):
+                        yield parentrev
+            self._parentrevs = stopparentrevs
+
         # Initialize data structures for __contains__.
         # For __contains__, we use a heap rather than a deque because
         # (a) it minimizes the number of parentrevs calls made
diff --git a/mercurial/revlog.py b/mercurial/revlog.py
--- a/mercurial/revlog.py
+++ b/mercurial/revlog.py
@@ -411,14 +411,14 @@ class revlog(object):
         return len(t)
     size = rawsize
 
-    def ancestors(self, revs, stoprev=0, inclusive=False):
+    def ancestors(self, revs, stoprev=0, inclusive=False, stopfunc=None):
         """Generate the ancestors of 'revs' in reverse topological order.
         Does not generate revs lower than stoprev.
 
         See the documentation for ancestor.lazyancestors for more details."""
 
         return ancestor.lazyancestors(self.parentrevs, revs, stoprev=stoprev,
-                                      inclusive=inclusive)
+                                      inclusive=inclusive, stopfunc=stopfunc)
 
     def descendants(self, revs):
         """Generate the descendants of 'revs' in revision order.