5 import collections

    10     obsolete,

    83 # Copied from evolve 081605c2e9b6

    84 

    85 def _orderrevs(repo, revs):

    86     """Compute an ordering to solve instability for the given revs

    87 

    88     revs is a list of unstable revisions.

    89 

    90     Returns the same revisions ordered to solve their instability from the

    91     bottom to the top of the stack that the stabilization process will produce

    92     eventually.

    93 

    94     This ensures the minimal number of stabilizations, as we can stabilize each

    95     revision on its final stabilized destination.

    96     """

    97     # Step 1: Build the dependency graph

    98     dependencies, rdependencies = builddependencies(repo, revs)

    99     # Step 2: Build the ordering

   100     # Remove the revisions with no dependency(A) and add them to the ordering.

   101     # Removing these revisions leads to new revisions with no dependency (the

   102     # one depending on A) that we can remove from the dependency graph and add

   103     # to the ordering. We progress in a similar fashion until the ordering is

   104     # built

   105     solvablerevs = [r for r in sorted(dependencies.keys())

   106                     if not dependencies[r]]

   107     ordering = []

   108     while solvablerevs:

   109         rev = solvablerevs.pop()

   110         for dependent in rdependencies[rev]:

   111             dependencies[dependent].remove(rev)

   112             if not dependencies[dependent]:

   113                 solvablerevs.append(dependent)

   114         del dependencies[rev]

   115         ordering.append(rev)

   116 

   117     ordering.extend(sorted(dependencies))

   118     return ordering

   119 

   120 def builddependencies(repo, revs):

   121     """returns dependency graphs giving an order to solve instability of revs

   122     (see _orderrevs for more information on usage)"""

   123 

   124     # For each troubled revision we keep track of what instability if any should

   125     # be resolved in order to resolve it. Example:

   126     # dependencies = {3: [6], 6:[]}

   127     # Means that: 6 has no dependency, 3 depends on 6 to be solved

   128     dependencies = {}

   129     # rdependencies is the inverted dict of dependencies

   130     rdependencies = collections.defaultdict(set)

   131 

   132     for r in revs:

   133         dependencies[r] = set()

   134         for p in repo[r].parents():

   135             try:

   136                 succ = _singlesuccessor(repo, p)

   137             except MultipleSuccessorsError as exc:

   138                 dependencies[r] = exc.successorssets

   139                 continue

   140             if succ in revs:

   141                 dependencies[r].add(succ)

   142                 rdependencies[succ].add(r)

   143     return dependencies, rdependencies

   144 

   145 def _singlesuccessor(repo, p):

   146     """returns p (as rev) if not obsolete or its unique latest successors

   147 

   148     fail if there are no such successor"""

   149 

   150     if not p.obsolete():

   151         return p.rev()

   152     obs = repo[p]

   153     ui = repo.ui

   154     newer = obsolete.successorssets(repo, obs.node())

   155     # search of a parent which is not killed

   156     while not newer:

   157         ui.debug("stabilize target %s is plain dead,"

   158                  " trying to stabilize on its parent\n" %

   159                  obs)

   160         obs = obs.parents()[0]

   161         newer = obsolete.successorssets(repo, obs.node())

   162     if len(newer) > 1 or len(newer[0]) > 1:

   163         raise MultipleSuccessorsError(newer)

   164 

   165     return repo[newer[0][0]].rev()

   166 

   167 class MultipleSuccessorsError(RuntimeError):

   168     """Exception raised by _singlesuccessor when multiple successor sets exists

   169 

   170     The object contains the list of successorssets in its 'successorssets'

   171     attribute to call to easily recover.

   172     """

   173 

   174     def __init__(self, successorssets):

   175         self.successorssets = successorssets