changeset 2220:0b6745b91d6d

merge-slicing: introduce and use "inheritance point" for merge


The first part of the stable sorted list of revision of a merge will shared with
the one of others. This means we can reuse subranges computed from that point to
compute some of the subranges from the merge.

That point is latest point in the stable sorted list where the depth of the
revisions match its index (that means all revision earlier in the stable sorted
list are its ancestors, no dangling unrelated branches exists). This is a bit
expensive to find since we have to walk all the revision, but being able to
reuse subranges in all case (not just regular changesets) provide a massive
speedup so the cost is worth it.

--- a/hgext3rd/evolve/stablerange.py	Fri Mar 24 08:31:10 2017 +0100
+++ b/hgext3rd/evolve/stablerange.py	Fri Mar 24 08:16:00 2017 +0100
@@ -172,6 +172,11 @@
         self._stablesortprepared = {}
         # caching parent call # as we do so many of them
         self._parentscache = {}
+        # The first part of the stable sorted list of revision of a merge will
+        # shared with the one of others. This means we can reuse subranges
+        # computed from that point to compute some of the subranges from the
+        # merge.
+        self._inheritancecache = {}
 
     def warmup(self, repo, heads):
         """warm the cache up to 'heads'"""
@@ -287,6 +292,37 @@
         revs.extend(reversed(top))
         return revs
 
+    def _inheritancepoint(self, repo, merge):
+        """Find the inheritance point of a Merge
+
+        The first part of the stable sorted list of revision of a merge will shared with
+        the one of others. This means we can reuse subranges computed from that point to
+        compute some of the subranges from the merge.
+
+        That point is latest point in the stable sorted list where the depth of the
+        revisions match its index (that means all revision earlier in the stable sorted
+        list are its ancestors, no dangling unrelated branches exists).
+        """
+        value = self._inheritancecache.get(merge)
+        if value is None:
+            revs = self.revsfromrange(repo, (merge, 0))
+            i = reversed(revs)
+            i.next() # pop the merge
+            expected = len(revs) - 1
+            # Since we do warmup properly, we can expect the cache to be hot
+            # for everythin under the merge we investigate
+            cache = self._depthcache
+            # note: we cannot do a binary search because element under the
+            # inherited point might have mismatching depth because of inner
+            # branching.
+            for rev in i:
+                if cache[rev] == expected:
+                    break
+                expected -= 1
+            value = (expected - 1 , rev)
+            self._inheritancecache[merge] = value
+        return value
+
     @staticmethod
     def _depthmerge(cl, rev, p1, p2, stack, cache):
         # sub method to simplify the main 'depthrev' one
@@ -355,12 +391,16 @@
         rangeid at slicepoint
 
         This function also have the important task to update the revscache of
-        the parent revs if possible and needed"""
-        # is this is a merge, there is not need to prepare the parents.
+        the parent rev s if possible and needed"""
         p1, p2 = self._parents(rangeid[0], repo.changelog.parentrevs)
-        if p2 != nodemod.nullrev:
-            return None
-        reusablerev = p1
+        if p2 == nodemod.nullrev:
+            # regular changesets, we pick the parent
+            reusablerev = p1
+        else:
+            # merge, we try the inheritance point
+            # if it is too low, it will be ditched by the depth check anyway
+            index, reusablerev = self._inheritancepoint(repo, rangeid[0])
+
         # if we reached the slicepoint, no need to go further
         if self.depthrev(repo, reusablerev) <= slicepoint:
             return None
@@ -392,10 +432,12 @@
 
     def _slicesrangeat(self, repo, rangeid, globalindex):
         p1, p2 = self._parents(rangeid[0], repo.changelog.parentrevs)
-        if p2 != nodemod.nullrev:
-            return self._slicesrangeatmerge(repo, rangeid, globalindex)
-
-        reuserev = p1
+        if p2 == nodemod.nullrev:
+            reuserev = p1
+        else:
+            index, reuserev = self._inheritancepoint(repo, rangeid[0])
+            if index < globalindex:
+                return self._slicesrangeatmerge(repo, rangeid, globalindex)
 
         assert reuserev != nodemod.nullrev