diff hgext3rd/topic/stack.py @ 2919:5b514ab2ab4e

stack: properly order stack when gaps existing inside it

We transitively search for the next "stack" ancestors, of changeset in the stack
not based on other revision of the stack. This should help having a consistent
display when topic are interleaved.

--- a/hgext3rd/topic/stack.py	Thu Sep 07 19:43:07 2017 +0200
+++ b/hgext3rd/topic/stack.py	Sat Sep 09 22:32:50 2017 +0530
@@ -8,9 +8,10 @@
     context,
     error,
     node,
+    phases,
     util,
 )
-from .evolvebits import builddependencies, _orderrevs, _singlesuccessor
+from .evolvebits import builddependencies, _singlesuccessor
 
 short = node.short
 
@@ -50,11 +51,84 @@
 
     @util.propertycache
     def _dependencies(self):
-        return builddependencies(self._repo, self.revs[1:])
+        deps, rdeps = builddependencies(self._repo, self._revs)
+
+        repo = self._repo
+        srcpfunc = repo.changelog.parentrevs
+
+        ### post process to skip over possible gaps in the stack
+        #
+        # For example in the following situation, we need to detect that "t3"
+        # indirectly depends on t2.
+        #
+        #  o t3
+        #  |
+        #  o other
+        #  |
+        #  o t2
+        #  |
+        #  o t1
+
+        pmap = {}
+
+        def pfuncrev(repo, rev):
+            """a special "parent func" that also consider successors"""
+            parents = pmap.get(rev)
+            if parents is None:
+                parents = [repo[_singlesuccessor(repo, repo[p])].rev()
+                           for p in srcpfunc(rev) if 0 <= p]
+                pmap[rev] = parents
+            return parents
+
+        revs = self._revs
+        stackrevs = set(self._revs)
+        for root in [r for r in revs if not deps[r]]:
+            seen = set()
+            stack = [root]
+            while stack:
+                current = stack.pop()
+                for p in pfuncrev(repo, current):
+                    if p in seen:
+                        continue
+                    seen.add(p)
+                    if p in stackrevs:
+                        rdeps[p].add(root)
+                        deps[root].add(p)
+                    elif phases.public < repo[p].phase():
+                        # traverse only if we did not found a proper candidate
+                        stack.append(p)
+
+        return deps, rdeps
 
     @util.propertycache
     def revs(self):
-        revs = _orderrevs(self._repo, self._revs)
+        # some duplication/change from _orderrevs because we use a post
+        # processed dependency graph.
+
+        # Step 1: compute relation of revision with each other
+        dependencies, rdependencies = self._dependencies
+        dependencies = dependencies.copy()
+        rdependencies = rdependencies.copy()
+        # Step 2: Build the ordering
+        # Remove the revisions with no dependency(A) and add them to the ordering.
+        # Removing these revisions leads to new revisions with no dependency (the
+        # one depending on A) that we can remove from the dependency graph and add
+        # to the ordering. We progress in a similar fashion until the ordering is
+        # built
+        solvablerevs = [r for r in sorted(dependencies.keys())
+                        if not dependencies[r]]
+        revs = []
+        while solvablerevs:
+            rev = solvablerevs.pop()
+            for dependent in rdependencies[rev]:
+                dependencies[dependent].remove(rev)
+                if not dependencies[dependent]:
+                    solvablerevs.append(dependent)
+            del dependencies[rev]
+            revs.append(rev)
+
+        revs.extend(sorted(dependencies))
+        # step 3: add t0
         if revs:
             pt1 = self._repo[revs[0]].p1()
             if pt1.obsolete():