# HG changeset patch
# User Pierre-Yves David <pierre-yves.david@octobus.net>
# Date 1511710486 18000
# Node ID f9206b009f48d2c3eb8c421bbd796472ddb528d5
# Parent  bc173e7f3b6f23ed43fdcad9d158d08e159ed953
stablesort: write a flat version of the algorithm

This new version never needs to iterate over the full repository even when merge
are encountered.

Having the algorithm flat also prepare caching works since the iteration
sequence can we expressed with a couple of flat loop.

diff -r bc173e7f3b6f -r f9206b009f48 hgext3rd/evolve/stablesort.py
--- a/hgext3rd/evolve/stablesort.py	Sat Nov 25 18:53:23 2017 -0500
+++ b/hgext3rd/evolve/stablesort.py	Sun Nov 26 10:34:46 2017 -0500
@@ -314,23 +314,77 @@
         return result
 
     def _revsfrom(self, repo, head):
-        parentsfunc = repo.changelog.parentrevs
+        tiebreaker = _mergepoint_tie_breaker(repo)
+        cl = repo.changelog
+        parentsfunc = cl.parentrevs
 
         def parents(rev):
-            return [p for p in parentsfunc(current) if p is not nodemod.nullrev]
+            return [p for p in parentsfunc(rev) if p is not nodemod.nullrev]
 
         current = head
-        ps = parents(current)
-        while len(ps) == 1:
+        previous_current = None
+
+        while current is not None:
+            assert current is not previous_current
             yield current
-            current = ps[0]
+            previous_current = current
+
+            ps = parents(current)
+            if not ps:
+                current = None # break
+            if len(ps) == 1:
+                current = ps[0]
+            elif len(ps) == 2:
+                lower_parent, higher_parent = sorted(ps, key=tiebreaker)
+
+                for rev in self._process_exclusive_side(lower_parent,
+                                                        higher_parent,
+                                                        cl.findmissingrevs,
+                                                        parents,
+                                                        tiebreaker):
+                    yield rev
+
+                current = lower_parent
+
+    def _process_exclusive_side(self, lower, higher, findmissingrevs, parents, tiebreaker):
+
+        exclusive = findmissingrevs(common=[lower],
+                                    heads=[higher])
+
+        stack = []
+        seen = set()
+        children = collections.defaultdict(set)
+        if not exclusive:
+            current = None
+        else:
+            current = higher
+            bound = set(exclusive)
+            for r in exclusive:
+                for p in parents(r):
+                    children[p].add(r)
+
+        previous_current = None
+        while current is not None:
+            assert current is not previous_current
+            yield current
+            seen.add(current)
+            previous_current = current
+
             ps = parents(current)
 
-        if not ps:
-            yield current
-        elif len(ps) == 2:
-            for rev in stablesort_mergepoint_head(repo, current)[::-1]:
-                yield rev
+            usable_parents = [p for p in ps
+                              if (p in bound and children[p].issubset(seen))]
+            if not usable_parents:
+                if stack:
+                    current = stack.pop()
+                else:
+                    current = None
+            elif len(usable_parents) == 1:
+                    current = usable_parents[0]
+            else:
+                lower_parent, higher_parent = sorted(usable_parents, key=tiebreaker)
+                stack.append(lower_parent)
+                current = higher_parent
 
 _methodmap = {
     'branchpoint': stablesort_branchpoint,