stablerange: introduce an 'basicstablerange'
authorPierre-Yves David <pierre-yves.david@octobus.net>
Sat, 09 Dec 2017 22:37:10 +0100
changeset 3251 0e4a05907c5e
parent 3250 8eaf30e1019f
child 3252 d57400a0f4c3
stablerange: introduce an 'basicstablerange' This class hold all the basic of stable range but the part specific to the sorting. This allow to clearly express what is expected from each method and to generate tests output to be validated against the more complex implementation. While writing this, we spotted a bug in the current stable range implementation. Fix coming.
hgext3rd/evolve/stablerange.py
--- a/hgext3rd/evolve/stablerange.py	Wed Nov 29 11:18:53 2017 -0500
+++ b/hgext3rd/evolve/stablerange.py	Sat Dec 09 22:37:10 2017 +0100
@@ -75,6 +75,7 @@
 
 _stablerangemethodmap = {
     'branchpoint': lambda repo: repo.stablerange,
+    'basic-branchpoint': lambda repo: stablerangebasic(),
 }
 
 @eh.command(
@@ -203,6 +204,82 @@
             slicepoint = standard_start
         return slicepoint
 
+class stablerangebasic(abstractstablerange):
+    """a very dummy implementation of stablerange
+
+    the implementation is here to lay down the basic algorithm in the stable
+    range in a inefficient but easy to read manners. It should be used by test
+    to validate output."""
+
+    __metaclass__ = abc.ABCMeta
+
+    def _sortfunction(self, repo, headrev):
+        return stablesort.stablesort_branchpoint(repo, [headrev])
+
+    def warmup(self, repo, upto=None):
+        # no cache to warm for basic implementation
+        pass
+
+    def depthrev(self, repo, rev):
+        """depth a revision"""
+        return len(repo.revs('::%d', rev))
+
+    def revsfromrange(self, repo, rangeid):
+        """return revision contained in a range
+
+        The range `(<head>, <skip>)` contains all revisions stable-sorted from
+        <head>, skipping the <index>th lower revisions.
+        """
+        headrev, index = rangeid[0], rangeid[1]
+        revs = self._sortfunction(repo, headrev)
+        return revs[index:]
+
+    def rangelength(self, repo, rangeid):
+        """number of revision in <range>"""
+        return len(self.revsfromrange(repo, rangeid))
+
+    def subranges(self, repo, rangeid):
+        """return the stable sub-ranges of a rangeid"""
+        headrev, index = rangeid[0], rangeid[1]
+        if self.rangelength(repo, rangeid) == 1:
+            return []
+        slicepoint = self._slicepoint(repo, rangeid)
+
+        # search for range defining the lower set of revision
+        #
+        # we walk the lower set 
+        result = []
+        lowerrevs = self.revsfromrange(repo, rangeid)[:(slicepoint - index)]
+        head = None
+        headrange = None
+        skip = None
+        for rev in lowerrevs[::-1]:
+            if head is None:
+                head = rev
+                headrange = self.revsfromrange(repo, (head, 0))
+                skip = self.depthrev(repo, rev) - 1
+            elif rev != headrange[skip - 1]:
+                result.append((head, skip))
+                head = rev
+                headrange = self.revsfromrange(repo, (head, 0))
+                skip = self.depthrev(repo, rev) - 1
+            else:
+                skip -= 1
+        result.append((head, skip))
+
+        result.reverse()
+
+        # top part is trivial
+        top = (headrev, slicepoint)
+        result.append(top)
+
+        # double check the result
+        initialrevs = self.revsfromrange(repo, rangeid)
+        subrangerevs = sum((self.revsfromrange(repo, sub) for sub in result),
+                           [])
+        assert initialrevs == subrangerevs
+        return result
+
 class stablerange(abstractstablerange):
 
     def __init__(self, lrusize=2000):