revsfromrange: reuse information from the stablesort
authorPierre-Yves David <pierre-yves.david@ens-lyon.org>
Fri, 24 Mar 2017 06:31:32 +0100
changeset 2213 fb2937b0dd49
parent 2212 afb35ad42040
child 2214 14e876c5e1c3
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.
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