|
1 import collections |
|
2 from mercurial import obsolete |
|
3 |
|
4 # Copied from evolve 081605c2e9b6 |
|
5 |
|
6 def _orderrevs(repo, revs): |
|
7 """Compute an ordering to solve instability for the given revs |
|
8 |
|
9 revs is a list of unstable revisions. |
|
10 |
|
11 Returns the same revisions ordered to solve their instability from the |
|
12 bottom to the top of the stack that the stabilization process will produce |
|
13 eventually. |
|
14 |
|
15 This ensures the minimal number of stabilizations, as we can stabilize each |
|
16 revision on its final stabilized destination. |
|
17 """ |
|
18 # Step 1: Build the dependency graph |
|
19 dependencies, rdependencies = builddependencies(repo, revs) |
|
20 # Step 2: Build the ordering |
|
21 # Remove the revisions with no dependency(A) and add them to the ordering. |
|
22 # Removing these revisions leads to new revisions with no dependency (the |
|
23 # one depending on A) that we can remove from the dependency graph and add |
|
24 # to the ordering. We progress in a similar fashion until the ordering is |
|
25 # built |
|
26 solvablerevs = [r for r in sorted(dependencies.keys()) |
|
27 if not dependencies[r]] |
|
28 ordering = [] |
|
29 while solvablerevs: |
|
30 rev = solvablerevs.pop() |
|
31 for dependent in rdependencies[rev]: |
|
32 dependencies[dependent].remove(rev) |
|
33 if not dependencies[dependent]: |
|
34 solvablerevs.append(dependent) |
|
35 del dependencies[rev] |
|
36 ordering.append(rev) |
|
37 |
|
38 ordering.extend(sorted(dependencies)) |
|
39 return ordering |
|
40 |
|
41 def builddependencies(repo, revs): |
|
42 """returns dependency graphs giving an order to solve instability of revs |
|
43 (see _orderrevs for more information on usage)""" |
|
44 |
|
45 # For each troubled revision we keep track of what instability if any should |
|
46 # be resolved in order to resolve it. Example: |
|
47 # dependencies = {3: [6], 6:[]} |
|
48 # Means that: 6 has no dependency, 3 depends on 6 to be solved |
|
49 dependencies = {} |
|
50 # rdependencies is the inverted dict of dependencies |
|
51 rdependencies = collections.defaultdict(set) |
|
52 |
|
53 for r in revs: |
|
54 dependencies[r] = set() |
|
55 for p in repo[r].parents(): |
|
56 try: |
|
57 succ = _singlesuccessor(repo, p) |
|
58 except MultipleSuccessorsError as exc: |
|
59 dependencies[r] = exc.successorssets |
|
60 continue |
|
61 if succ in revs: |
|
62 dependencies[r].add(succ) |
|
63 rdependencies[succ].add(r) |
|
64 return dependencies, rdependencies |
|
65 |
|
66 def _singlesuccessor(repo, p): |
|
67 """returns p (as rev) if not obsolete or its unique latest successors |
|
68 |
|
69 fail if there are no such successor""" |
|
70 |
|
71 if not p.obsolete(): |
|
72 return p.rev() |
|
73 obs = repo[p] |
|
74 ui = repo.ui |
|
75 newer = obsolete.successorssets(repo, obs.node()) |
|
76 # search of a parent which is not killed |
|
77 while not newer: |
|
78 ui.debug("stabilize target %s is plain dead," |
|
79 " trying to stabilize on its parent\n" % |
|
80 obs) |
|
81 obs = obs.parents()[0] |
|
82 newer = obsolete.successorssets(repo, obs.node()) |
|
83 if len(newer) > 1 or len(newer[0]) > 1: |
|
84 raise MultipleSuccessorsError(newer) |
|
85 |
|
86 return repo[newer[0][0]].rev() |
|
87 |
|
88 class MultipleSuccessorsError(RuntimeError): |
|
89 """Exception raised by _singlesuccessor when multiple successor sets exists |
|
90 |
|
91 The object contains the list of successorssets in its 'successorssets' |
|
92 attribute to call to easily recover. |
|
93 """ |
|
94 |
|
95 def __init__(self, successorssets): |
|
96 self.successorssets = successorssets |