D4794: dagop: extract descendants() from revlog module

indygreg (Gregory Szorc) phabricator at mercurial-scm.org
Sat Sep 29 00:19:18 UTC 2018


indygreg created this revision.
Herald added a subscriber: mercurial-devel.
Herald added a reviewer: hg-reviewers.

REVISION SUMMARY
  This method needs to be implemented in other storage backends and is
  generic if we parameterize the functions for retrieving revision
  numbers and parent revision numbers.
  
  Let's extract it to dagop so backends don't need to reinvent the
  wheel.
  
  I'm not too worried about performance overhead of the extra function
  call because I don't expect anyone to be calling descendants() in a
  tight loop.

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D4794

AFFECTED FILES
  mercurial/dagop.py
  mercurial/revlog.py

CHANGE DETAILS

diff --git a/mercurial/revlog.py b/mercurial/revlog.py
--- a/mercurial/revlog.py
+++ b/mercurial/revlog.py
@@ -748,25 +748,7 @@
                                       inclusive=inclusive)
 
     def descendants(self, revs):
-        """Generate the descendants of 'revs' in revision order.
-
-        Yield a sequence of revision numbers starting with a child of
-        some rev in revs, i.e., each revision is *not* considered a
-        descendant of itself.  Results are ordered by revision number (a
-        topological sort)."""
-        first = min(revs)
-        if first == nullrev:
-            for i in self:
-                yield i
-            return
-
-        seen = set(revs)
-        for i in self.revs(start=first + 1):
-            for x in self.parentrevs(i):
-                if x != nullrev and x in seen:
-                    seen.add(i)
-                    yield i
-                    break
+        return dagop.descendantrevs(revs, self.revs, self.parentrevs)
 
     def findcommonmissing(self, common=None, heads=None):
         """Return a tuple of the ancestors of common and the ancestors of heads
diff --git a/mercurial/dagop.py b/mercurial/dagop.py
--- a/mercurial/dagop.py
+++ b/mercurial/dagop.py
@@ -9,6 +9,9 @@
 
 import heapq
 
+from .node import (
+    nullrev,
+)
 from .thirdparty import (
     attr,
 )
@@ -225,6 +228,37 @@
                                         startdepth, stopdepth)
     return generatorset(gen, iterasc=True)
 
+def descendantrevs(revs, revsfn, parentrevsfn):
+    """Generate revision number descendants in revision order.
+
+    Yields revision numbers starting with a child of some rev in
+    ``revs``. Results are ordered by revision number and are
+    therefore topological. Each revision is not considered a descendant
+    of itself.
+
+    ``revsfn`` is a callable that with no argument iterates over all
+    revision numbers and with a ``start`` argument iterates over revision
+    numbers beginning with that value.
+
+    ``parentrevsfn`` is a callable that receives a revision number and
+    returns an iterable of parent revision numbers, whose values may include
+    nullrev.
+    """
+    first = min(revs)
+
+    if first == nullrev:
+        for rev in revsfn():
+            yield rev
+        return
+
+    seen = set(revs)
+    for rev in revsfn(start=first + 1):
+        for prev in parentrevsfn(rev):
+            if prev != nullrev and prev in seen:
+                seen.add(rev)
+                yield rev
+                break
+
 def _reachablerootspure(repo, minroot, roots, heads, includepath):
     """return (heads(::<roots> and ::<heads>))
 



To: indygreg, #hg-reviewers
Cc: mercurial-devel


More information about the Mercurial-devel mailing list