changeset 3267:f9206b009f48

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.

--- 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,