changeset 2213:fb2937b0dd49

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.

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