diff -r 0437158e0ed6 -r 5b514ab2ab4e hgext3rd/topic/stack.py --- 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():