# HG changeset patch
# User Gregory Szorc <gregory.szorc@gmail.com>
# Date 1534540910 0
# Node ID 0a934ee94f09660c2dcb13238d2cda4a5d6734cc
# Parent  8de52699584449d9a2da4adf481ef40afb55d635
dagop: port revlogdag.linearize() to standalone function

The code should functionally be identical.

We also port the one consumer in changegroup to use the new
standalone function.

After this commit, dagutil is no longer used!

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

diff -r 8de526995844 -r 0a934ee94f09 mercurial/changegroup.py
--- a/mercurial/changegroup.py	Fri Aug 17 19:48:52 2018 +0000
+++ b/mercurial/changegroup.py	Fri Aug 17 21:21:50 2018 +0000
@@ -24,7 +24,7 @@
 )
 
 from . import (
-    dagutil,
+    dagop,
     error,
     match as matchmod,
     mdiff,
@@ -587,8 +587,8 @@
     # for generaldelta revlogs, we linearize the revs; this will both be
     # much quicker and generate a much smaller bundle
     if (store._generaldelta and reorder is None) or reorder:
-        dag = dagutil.revlogdag(store)
-        return dag.linearize(set(store.rev(n) for n in nodes))
+        revs = set(store.rev(n) for n in nodes)
+        return dagop.linearize(revs, store.parentrevs)
     else:
         return sorted([store.rev(n) for n in nodes])
 
diff -r 8de526995844 -r 0a934ee94f09 mercurial/dagop.py
--- a/mercurial/dagop.py	Fri Aug 17 19:48:52 2018 +0000
+++ b/mercurial/dagop.py	Fri Aug 17 21:21:50 2018 +0000
@@ -738,3 +738,40 @@
     headrevs.discard(node.nullrev)
 
     return headrevs
+
+def linearize(revs, parentsfn):
+    """Linearize and topologically sort a list of revisions.
+
+    The linearization process tires to create long runs of revs where a child
+    rev comes immediately after its first parent. This is done by visiting the
+    heads of the revs in inverse topological order, and for each visited rev,
+    visiting its second parent, then its first parent, then adding the rev
+    itself to the output list.
+
+    Returns a list of revision numbers.
+    """
+    visit = list(sorted(headrevs(revs, parentsfn), reverse=True))
+    finished = set()
+    result = []
+
+    while visit:
+        rev = visit.pop()
+        if rev < 0:
+            rev = -rev - 1
+
+            if rev not in finished:
+                result.append(rev)
+                finished.add(rev)
+
+        else:
+            visit.append(-rev - 1)
+
+            for prev in parentsfn(rev):
+                if prev == node.nullrev or prev not in revs or prev in finished:
+                    continue
+
+                visit.append(prev)
+
+    assert len(result) == len(revs)
+
+    return result