diff mercurial/dagop.py @ 40000:0b24fcd88066

dagop: extract descendants() from revlog module 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. Differential Revision: https://phab.mercurial-scm.org/D4794
author Gregory Szorc <gregory.szorc@gmail.com>
date Fri, 28 Sep 2018 10:03:32 -0700
parents 5362c96f2feb
children 8af835af0a85
line wrap: on
line diff
--- a/mercurial/dagop.py	Fri Sep 28 09:33:05 2018 -0700
+++ b/mercurial/dagop.py	Fri Sep 28 10:03:32 2018 -0700
@@ -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>))