changeset 3315:c153441cdc0e

stablesort: record, cache and reuse jump

Iterating below a merge means two things:

1) iterate over the part exclusive to the higher parents,
2) iterate from the lower parents.

While iterating on the exclusive part, there will be case were we just go the
next natural parent, and case were we'll have to "jump" to another revision. If
we record all point this "jump" happens and their target, we can easily
reproduce the iteration in the future. With that information we can iterate over
the exclusive part of the merge without having to compute it entirely.

In addition we store the reason of the jump. This will help the stable range
processing later.

--- a/hgext3rd/evolve/stablesort.py	Mon Dec 18 18:49:34 2017 +0100
+++ b/hgext3rd/evolve/stablesort.py	Mon Dec 18 09:04:16 2017 +0100
@@ -302,10 +302,23 @@
                           % len(heads))
     head = heads.first()
     cache = stablesortcache()
-    return cache.get(repo, head, limit=limit)
+    first = list(cache.get(repo, head, limit=limit))
+    second = list(cache.get(repo, head, limit=limit))
+    if first != second:
+        repo.ui.warn('stablesort-cache: initial run different from re-run:\n'
+                     '    %s\n'
+                     '    %s\n' % (first, second))
+    return second
+
+JUMPSOFT = 1  # jump when a branch have been explored
+JUMPHARD = 2  # jump because we reach the outside of the exclusive area
+JUMPFINAL = 3 # jump because we are done sorting the exclusive area
 
 class stablesortcache(object):
 
+    def __init__(self):
+        self._jumps = collections.defaultdict(lambda: None)
+
     def get(self, repo, rev, limit=None):
         result = []
         for r in self.walkfrom(repo, rev):
@@ -323,13 +336,47 @@
         def parents(rev):
             return filterparents(parentsfunc(rev))
 
+        def oneparent(rev):
+            ps = parents(rev)
+            if not ps:
+                return None
+            if len(ps) == 1:
+                return ps[0]
+            return max(ps, key=tiebreaker)
+
+        def walkfrom(start, stop, oneparent):
+            current = oneparent(start)
+            while current is not None:
+                yield current
+                current = oneparent(start)
+
         current = head
-        previous_current = None
+        previous_current_1 = object()
+        previous_current_2 = object()
 
         while current is not None:
-            assert current is not previous_current
+            previous_current_2 = previous_current_1
+            previous_current_1 = current
+            assert previous_current_1 is not previous_current_2
+
+            jumps = self._jumps[current]
+            if jumps is not None:
+                # we have enough cached information to directly iterate over
+                # the exclusive size.
+                for j in jumps:
+                    jump_point = j[0]
+                    jump_dest = j[1]
+                    if current == jump_point:
+                        yield current
+                    else:
+                        while current != jump_point:
+                            yield current
+                            current = oneparent(current)
+                        yield current
+                    current = jump_dest
+                    continue
+
             yield current
-            previous_current = current
 
             ps = parents(current)
             if not ps:
@@ -339,16 +386,24 @@
             elif len(ps) == 2:
                 lower_parent, higher_parent = sorted(ps, key=tiebreaker)
 
+                rev = current
+                jumps = []
                 for rev in self._process_exclusive_side(lower_parent,
                                                         higher_parent,
                                                         cl.findmissingrevs,
                                                         parents,
-                                                        tiebreaker):
+                                                        tiebreaker,
+                                                        jumps):
                     yield rev
 
+                jumps.append((rev, lower_parent, JUMPFINAL))
+
+                self._jumps[current] = jumps
+
                 current = lower_parent
 
-    def _process_exclusive_side(self, lower, higher, findmissingrevs, parents, tiebreaker):
+    def _process_exclusive_side(self, lower, higher, findmissingrevs,
+                                parents, tiebreaker, jumps):
 
         exclusive = findmissingrevs(common=[lower],
                                     heads=[higher])
@@ -372,21 +427,46 @@
             seen.add(current)
             previous_current = current
 
-            ps = parents(current)
+            all_parents = parents(current)
+
+            max_parents = None
+            if 1 == len(all_parents):
+                max_parents = all_parents[0]
+            if 2 <= len(all_parents):
+                max_parents = max(all_parents, key=tiebreaker)
+
+            jump_type = None
+
+            ready_parents = [p for p in all_parents
+                             if children[p].issubset(seen)]
+
+            okay_parents = [p for p in ready_parents if p in bound]
 
-            usable_parents = [p for p in ps
-                              if (p in bound and children[p].issubset(seen))]
-            if not usable_parents:
+            if (len(all_parents) != len(ready_parents)
+                    and max_parents not in ready_parents):
+                jump_type = JUMPSOFT
+            elif (len(ready_parents) != len(okay_parents)
+                    and max_parents not in okay_parents):
+                jump_type = JUMPHARD
+            elif not all_parents:
+                jump_type = JUMPSOFT
+
+            if not okay_parents:
+                if jump_type is None:
+                    jump_type = JUMPSOFT
                 if stack:
-                    current = stack.pop()
+                    next = stack.pop()
                 else:
-                    current = None
-            elif len(usable_parents) == 1:
-                    current = usable_parents[0]
+                    next = None
+            elif len(okay_parents) == 1:
+                    next = okay_parents[0]
             else:
-                lower_parent, higher_parent = sorted(usable_parents, key=tiebreaker)
+                lower_parent, higher_parent = sorted(ready_parents, key=tiebreaker)
                 stack.append(lower_parent)
-                current = higher_parent
+                next = higher_parent
+            if jump_type is not None and next is not None:
+                    jumps.append((current, next, jump_type))
+            current = next
 
 _methodmap = {
     'branchpoint': stablesort_branchpoint,