hgext3rd/topic/stack.py
changeset 2919 5b514ab2ab4e
parent 2918 0437158e0ed6
child 2936 3a9303b7b648
--- 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():