# HG changeset patch
# User Pierre-Yves David <pierre-yves.david@octobus.net>
# Date 1513544734 -3600
# Node ID 5c45df0c8e36e3e78dbfa57461d739eeb526a1f7
# Parent  2d49773a378bdf532f18e9a7c573fe7fe44e8771
stablerange: use sort cache to build 'mergepoint' information

Using the walk cache gives use a better complexity we need to scale. There are
further improvement we could make, but this is a good first step.

diff -r 2d49773a378b -r 5c45df0c8e36 hgext3rd/evolve/stablerange.py
--- a/hgext3rd/evolve/stablerange.py	Sun Dec 10 03:31:28 2017 +0100
+++ b/hgext3rd/evolve/stablerange.py	Sun Dec 17 22:05:34 2017 +0100
@@ -326,6 +326,111 @@
         limit = self.rangelength(repo, rangeid)
         return self._sortcache.get(repo, rangeid[0], limit=limit)
 
+    def _stableparent(self, repo, headrev):
+        """The parent of the changeset with reusable subrange
+
+        For non-merge it is simple, there is a single parent. For Mercurial we
+        have to find the right one. Since the stable sort use merge-point, we
+        know that one of REV parents stable sort is a subset of REV stable
+        sort. In other word:
+
+            sort(::REV) = sort(::min(parents(REV))
+                          + sort(only(max(parents(REV)), min(parents(REV)))
+                          + [REV]
+
+        We are looking for that `min(parents(REV))`. Since the subrange are
+        based on the sort, we can reuse its subrange as well.
+        """
+        p1, p2 = repo.changelog.parentrevs(headrev)
+        relevant_parent = None
+        if p2 == nodemod.nullrev:
+            relevant_parent = p1
+        else:
+            tiebreaker = stablesort._mergepoint_tie_breaker(repo)
+            relevant_parent = min(p1, p2, key=tiebreaker)
+        return relevant_parent
+
+    def subranges(self, repo, rangeid):
+        headrev, initial_index = rangeid
+        # size 1 range can't be sliced
+        if self.rangelength(repo, rangeid) == 1:
+            return []
+        # find were we need to slice
+        slicepoint = self._slicepoint(repo, rangeid)
+
+        stable_parent = self._stableparent(repo, headrev)
+        stable_parent_depth = self.depthrev(repo, stable_parent)
+        stable_parent_range = (stable_parent, initial_index)
+
+        # top range is always the same, so we can build it early for all
+        top_range = (headrev, slicepoint)
+
+        # now find out about the lower range, if we are lucky there is only
+        # one, otherwise we need to issue multiple one to cover every revision
+        # on the lower set. (and cover them only once).
+        if slicepoint == stable_parent_depth:
+            # luckly shot, the parent is actually the head of the lower range
+            subranges = [
+                stable_parent_range,
+                top_range,
+            ]
+        elif slicepoint < stable_parent_depth:
+            # The parent is above the slice point,
+            # it's lower subrange will be the same so we just get them,
+            # (and the top range is always the same)
+            subranges = self.subranges(repo, stable_parent_range)[:-1]
+            subranges.append(top_range)
+        elif initial_index < stable_parent_depth < slicepoint:
+            # the parent is below the range we are considering, we need to
+            # compute these uniques subranges
+            subranges = [stable_parent_range]
+            subranges.extend(self._unique_subranges(repo, headrev,
+                                                    stable_parent_depth,
+                                                    slicepoint))
+            subranges.append(top_range)
+        else:
+            # we cannot reuse the parent range at all
+            subranges = list(self._unique_subranges(repo, headrev,
+                                                    initial_index,
+                                                    slicepoint))
+            subranges.append(top_range)
+
+        return subranges
+
+    def _unique_subranges(self, repo, headrev, initial_index, slicepoint):
+        """Compute subrange unique to the exclusive part of merge"""
+        result = []
+        depth = repo.depthcache.get
+        skips = depth(headrev) - slicepoint
+
+        def nextrevs():
+            revs = self._sortcache.walkfrom(repo, headrev)
+            towalk = depth(headrev) - initial_index
+            while 0 < towalk:
+                yield next(revs)
+                towalk -= 1
+            yield None
+        revs = nextrevs()
+        for i in xrange(skips):
+            next(revs)
+        rangehead = current = next(revs)
+        rangepath = self._sortcache.walkfrom(repo, current)
+        nextonpath = next(rangepath, None)
+        steps = 0
+        while current is not None:
+            while current == nextonpath and current is not None:
+                steps += 1
+                current = next(revs)
+                nextonpath = next(rangepath, None)
+            result.append((rangehead, depth(rangehead) - steps))
+            if current is not None:
+                rangehead = current
+                rangepath = self._sortcache.walkfrom(repo, current)
+                nextonpath = next(rangepath, None)
+                steps = 0
+        result.reverse()
+        return result
+
 class stablerange(stablerangecached):
 
     def __init__(self, lrusize=2000):