changeset 3321:14024940f369

stablesort: rework jump gathering

The old code was buggy in some case, the new code give the same result as the
'headstart' version.

--- a/hgext3rd/evolve/stablesort.py	Wed Dec 20 12:36:45 2017 +0100
+++ b/hgext3rd/evolve/stablesort.py	Wed Dec 20 13:41:33 2017 +0100
@@ -368,6 +368,7 @@
                         while current != jump_point:
                             yield current
                             current = oneparent(current)
+                            assert current is not None
                         yield current
                     current = jump_dest
                     continue
@@ -404,65 +405,68 @@
 
         exclusive = cl.findmissingrevs(common=[lower], heads=[higher])
 
-        stack = []
+        def popready(stack):
+            """pop the top most ready item in the list"""
+            for idx in xrange(len(stack) - 1, -1, -1):
+                if children[stack[idx]].issubset(seen):
+                    return stack.pop(idx)
+            return None
+
+        hardstack = []
+        previous = None
         seen = set()
+        current = higher
         children = collections.defaultdict(set)
-        if not exclusive:
-            current = None
-        else:
-            current = higher
-            bound = set(exclusive)
+        bound = set(exclusive)
+        if exclusive:
             for r in exclusive:
                 for p in parents(r):
                     children[p].add(r)
 
-        previous_current = None
-        while current is not None:
-            assert current is not previous_current
-            yield current
-            seen.add(current)
-            previous_current = current
-
-            all_parents = parents(current)
+            hardstack.append(higher)
+        nextjump = False
+        while hardstack:
+            current = popready(hardstack)
+            if current in seen:
+                continue
+            softstack = []
+            while current in bound and current not in seen:
+                if nextjump:
+                    recordjump(previous, current)
+                    nextjump = False
+                yield current
+                previous = current
+                seen.add(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 = False
-
-            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]
+                all_parents = parents(current)
 
-            if (len(all_parents) != len(ready_parents)
-                    and max_parents not in ready_parents):
-                jump = True
-            elif (len(ready_parents) != len(okay_parents)
-                    and max_parents not in okay_parents):
-                jump = True
-            elif not all_parents:
-                jump = True
+                # search or next parent to walk through
+                fallback, next = None, None
+                if 1 == len(all_parents):
+                    next = all_parents[0]
+                elif 2 <= len(all_parents):
+                    fallback, next = sorted(all_parents, key=tiebreaker)
+
+                # filter parent not ready (children not emitted)
+                while next is not None and not children[next].issubset(seen):
+                    nextjump = True
+                    next = fallback
+                    fallback = None
 
-            if not okay_parents:
-                if jump is None:
-                    jump = True
-                if stack:
-                    next = stack.pop()
-                else:
-                    next = None
-            elif len(okay_parents) == 1:
-                next = okay_parents[0]
-            else:
-                lower_parent, higher_parent = sorted(ready_parents, key=tiebreaker)
-                stack.append(lower_parent)
-                next = higher_parent
-            if jump is not None and next is not None:
-                recordjump(current, next)
-            current = next
+                # stack management
+                if next is None:
+                    next = popready(softstack)
+                    if next is not None:
+                        nextjump = True
+                elif fallback is not None:
+                    softstack.append(fallback)
+
+                # get ready for next iteration
+                current = next
+
+            # any in processed head has to go in the hard stack
+            nextjump = True
+            hardstack.extend(softstack)
 
 _methodmap = {
     'branchpoint': stablesort_branchpoint,