changeset 40000:8af835af0a85

dagop: extract DAG local heads functionality from revlog

As part of implementing an alternate storage backend, I found myself
having to reimplement this function.

The DAG traversal logic is generic and can be factored out into a
standalone function.

We could probably combine this with headrevs(). But I'll leave that
for another time.

Differential Revision: https://phab.mercurial-scm.org/D4795

--- a/mercurial/dagop.py	Fri Sep 28 10:03:32 2018 -0700
+++ b/mercurial/dagop.py	Fri Sep 28 10:20:37 2018 -0700
@@ -773,6 +773,42 @@
 
     return headrevs
 
+def headrevssubset(revsfn, parentrevsfn, startrev=None, stoprevs=None):
+    """Returns the set of all revs that have no children with control.
+
+    ``revsfn`` is a callable that with no arguments returns an iterator over
+    all revision numbers in topological order. With a ``start`` argument, it
+    returns revision numbers starting at that number.
+
+    ``parentrevsfn`` is a callable receiving a revision number and returns an
+    iterable of parent revision numbers, where values can include nullrev.
+
+    ``startrev`` is a revision number at which to start the search.
+
+    ``stoprevs`` is an iterable of revision numbers that, when encountered,
+    will stop DAG traversal beyond them. Parents of revisions in this
+    collection will be heads.
+    """
+    if startrev is None:
+        startrev = nullrev
+
+    stoprevs = set(stoprevs or [])
+
+    reachable = {startrev}
+    heads = {startrev}
+
+    for rev in revsfn(start=startrev + 1):
+        for prev in parentrevsfn(rev):
+            if prev in reachable:
+                if rev not in stoprevs:
+                    reachable.add(rev)
+                heads.add(rev)
+
+            if prev in heads and prev not in stoprevs:
+                heads.remove(prev)
+
+    return heads
+
 def linearize(revs, parentsfn):
     """Linearize and topologically sort a list of revisions.
 

--- a/mercurial/revlog.py	Fri Sep 28 10:03:32 2018 -0700
+++ b/mercurial/revlog.py	Fri Sep 28 10:20:37 2018 -0700
@@ -1069,25 +1069,16 @@
             return [self.node(r) for r in self.headrevs()]
 
         if start is None:
-            start = nullid
-        if stop is None:
-            stop = []
-        stoprevs = set([self.rev(n) for n in stop])
-        startrev = self.rev(start)
-        reachable = {startrev}
-        heads = {startrev}
-
-        parentrevs = self.parentrevs
-        for r in self.revs(start=startrev + 1):
-            for p in parentrevs(r):
-                if p in reachable:
-                    if r not in stoprevs:
-                        reachable.add(r)
-                    heads.add(r)
-                if p in heads and p not in stoprevs:
-                    heads.remove(p)
-
-        return [self.node(r) for r in heads]
+            start = nullrev
+        else:
+            start = self.rev(start)
+
+        stoprevs = set(self.rev(n) for n in stop or [])
+
+        revs = dagop.headrevssubset(self.revs, self.parentrevs, startrev=start,
+                                    stoprevs=stoprevs)
+
+        return [self.node(rev) for rev in revs]
 
     def children(self, node):
         """find the children of a given node"""