# HG changeset patch
# User Pierre-Yves David <pierre-yves.david@ens-lyon.org>
# Date 1490333492 -3600
# Node ID fb2937b0dd499bd4957750cb1bd582cfc0d1736f
# Parent  afb35ad42040fc1cc936d8ea5116544ff6836856
revsfromrange: reuse information from the stablesort

We collaborate with the stablesort to store the order that led to a merge. That
way, when we needs to retrieve revision from that merge we can reuse that order.
We might need to filter to only retains ancestors of the merge we care about but
skipping the stablesort safe a large amount of time.

diff -r afb35ad42040 -r fb2937b0dd49 hgext3rd/evolve/stablerange.py
--- a/hgext3rd/evolve/stablerange.py	Fri Mar 24 03:22:56 2017 +0100
+++ b/hgext3rd/evolve/stablerange.py	Fri Mar 24 06:31:32 2017 +0100
@@ -167,6 +167,9 @@
         # the same for all ranges headed at the same merge. So we cache these
         # value to reuse them accross the same invocation.
         self._stablesortcache = {}
+        # something useful to compute the above
+        # mergerev -> stablesort, length
+        self._stablesortprepared = {}
         # if we already know all the revision that belong to a range, it is
         # quite trivial to have the subrange "inherit" that knowledge. This
         # cache is dedicated to hold the full list of revs inside a subrange
@@ -246,7 +249,10 @@
                 # call for the general case.
                 allrevs = self._stablesortcache.get(headrev)
                 if allrevs is None:
-                    allrevs = stablesort(repo, [headrev])
+                    allrevs = self._getrevsfrommerge(repo, headrev)
+                    if allrevs is None:
+                        allrevs = stablesort(repo, [headrev],
+                                             mergecallback=self._filestablesortcache)
                     self._stablesortcache[headrev] = allrevs
                 # takes from index
                 revs = allrevs[index:]
@@ -262,6 +268,37 @@
             self._parentscache[rev] = parents
         return parents
 
+    def _filestablesortcache(self, sortedrevs, merge):
+        if merge not in self._stablesortprepared:
+            self._stablesortprepared[merge] = (sortedrevs, len(sortedrevs))
+
+    def _getrevsfrommerge(self, repo, merge):
+        prepared = self._stablesortprepared.get(merge)
+        if prepared is None:
+            return None
+
+        mergedepth = self.depthrev(repo, merge)
+        allrevs = prepared[0][:prepared[1]]
+        nbextrarevs = prepared[1] - mergedepth
+        if not nbextrarevs:
+            return allrevs
+
+        anc = repo.changelog.ancestors([merge], inclusive=True)
+        top = []
+        counter = nbextrarevs
+        for rev in reversed(allrevs):
+            if rev in anc:
+                top.append(rev)
+            else:
+                counter -= 1
+                if counter <= 0:
+                    break
+
+        bottomidx = prepared[1] - (nbextrarevs + len(top))
+        revs = allrevs[:bottomidx]
+        revs.extend(reversed(top))
+        return revs
+
     @staticmethod
     def _depthmerge(cl, rev, p1, p2, stack, cache):
         # sub method to simplify the main 'depthrev' one