stablesort: write a flat version of the algorithm
authorPierre-Yves David <pierre-yves.david@octobus.net>
Sun, 26 Nov 2017 10:34:46 -0500
changeset 3267 f9206b009f48
parent 3266 bc173e7f3b6f
child 3268 10badf5951e5
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.
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,