1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
|
# Copyright 2010-2011 Gentoo Foundation
# Distributed under the terms of the GNU General Public License v2
from __future__ import print_function
from itertools import chain, product
import logging
from portage.dep import use_reduce, extract_affecting_use, check_required_use, get_required_use_flags
from portage.exception import InvalidDependString
from portage.output import colorize
from portage.util import writemsg_level
from _emerge.DepPrioritySatisfiedRange import DepPrioritySatisfiedRange
class circular_dependency_handler(object):
def __init__(self, depgraph, graph):
self.depgraph = depgraph
self.graph = graph
self.all_parent_atoms = depgraph._dynamic_config._parent_atoms
if "--debug" in depgraph._frozen_config.myopts:
# Show this debug output before doing the calculations
# that follow, so at least we have this debug info
# if we happen to hit a bug later.
writemsg_level("\n\ncircular dependency graph:\n\n",
level=logging.DEBUG, noiselevel=-1)
self.debug_print()
self.cycles, self.shortest_cycle = self._find_cycles()
#Guess if it is a large cluster of cycles. This usually requires
#a global USE change.
self.large_cycle_count = len(self.cycles) > 3
self.merge_list = self._prepare_reduced_merge_list()
#The digraph dump
self.circular_dep_message = self._prepare_circular_dep_message()
#Suggestions, in machine and human readable form
self.solutions, self.suggestions = self._find_suggestions()
def _find_cycles(self):
shortest_cycle = None
cycles = self.graph.get_cycles(ignore_priority=DepPrioritySatisfiedRange.ignore_medium_soft)
for cycle in cycles:
if not shortest_cycle or len(cycle) < len(shortest_cycle):
shortest_cycle = cycle
return cycles, shortest_cycle
def _prepare_reduced_merge_list(self):
"""
Create a merge to be displayed by depgraph.display().
This merge list contains only packages involved in
the circular deps.
"""
display_order = []
tempgraph = self.graph.copy()
while tempgraph:
nodes = tempgraph.leaf_nodes()
if not nodes:
node = tempgraph.order[0]
else:
node = nodes[0]
display_order.append(node)
tempgraph.remove(node)
display_order.reverse()
return display_order
def _prepare_circular_dep_message(self):
"""
Like digraph.debug_print(), but prints only the shortest cycle.
"""
if not self.shortest_cycle:
return None
msg = []
indent = ""
for pos, pkg in enumerate(self.shortest_cycle):
parent = self.shortest_cycle[pos-1]
priorities = self.graph.nodes[parent][0][pkg]
if pos > 0:
msg.append(indent + "%s (%s)" % (pkg, priorities[-1],))
else:
msg.append(indent + "%s depends on" % pkg)
indent += " "
pkg = self.shortest_cycle[0]
parent = self.shortest_cycle[-1]
priorities = self.graph.nodes[parent][0][pkg]
msg.append(indent + "%s (%s)" % (pkg, priorities[-1],))
return "\n".join(msg)
def _get_use_mask_and_force(self, pkg):
return pkg.use.mask, pkg.use.force
def _get_autounmask_changes(self, pkg):
needed_use_config_change = self.depgraph._dynamic_config._needed_use_config_changes.get(pkg)
if needed_use_config_change is None:
return frozenset()
use, changes = needed_use_config_change
return frozenset(changes.keys())
def _find_suggestions(self):
if not self.shortest_cycle:
return None, None
suggestions = []
final_solutions = {}
for pos, pkg in enumerate(self.shortest_cycle):
parent = self.shortest_cycle[pos-1]
priorities = self.graph.nodes[parent][0][pkg]
parent_atoms = self.all_parent_atoms.get(pkg)
if priorities[-1].buildtime:
dep = parent.metadata["DEPEND"]
elif priorities[-1].runtime:
dep = parent.metadata["RDEPEND"]
for ppkg, atom in parent_atoms:
if ppkg == parent:
changed_parent = ppkg
parent_atom = atom.unevaluated_atom
break
try:
affecting_use = extract_affecting_use(dep, parent_atom,
eapi=parent.metadata["EAPI"])
except InvalidDependString:
if not parent.installed:
raise
affecting_use = set()
# Make sure we don't want to change a flag that is
# a) in use.mask or use.force
# b) changed by autounmask
usemask, useforce = self._get_use_mask_and_force(parent)
autounmask_changes = self._get_autounmask_changes(parent)
untouchable_flags = frozenset(chain(usemask, useforce, autounmask_changes))
affecting_use.difference_update(untouchable_flags)
#If any of the flags we're going to touch is in REQUIRED_USE, add all
#other flags in REQUIRED_USE to affecting_use, to not lose any solution.
required_use_flags = get_required_use_flags(
parent.metadata.get("REQUIRED_USE", ""))
if affecting_use.intersection(required_use_flags):
# TODO: Find out exactly which REQUIRED_USE flags are
# entangled with affecting_use. We have to limit the
# number of flags since the number of loops is
# exponentially related (see bug #374397).
total_flags = set()
total_flags.update(affecting_use, required_use_flags)
total_flags.difference_update(untouchable_flags)
if len(total_flags) <= 10:
affecting_use = total_flags
affecting_use = tuple(affecting_use)
if not affecting_use:
continue
#We iterate over all possible settings of these use flags and gather
#a set of possible changes
#TODO: Use the information encoded in REQUIRED_USE
solutions = set()
for use_state in product(("disabled", "enabled"),
repeat=len(affecting_use)):
current_use = set(self.depgraph._pkg_use_enabled(parent))
for flag, state in zip(affecting_use, use_state):
if state == "enabled":
current_use.add(flag)
else:
current_use.discard(flag)
try:
reduced_dep = use_reduce(dep,
uselist=current_use, flat=True)
except InvalidDependString:
if not parent.installed:
raise
reduced_dep = None
if reduced_dep is not None and \
parent_atom not in reduced_dep:
#We found an assignment that removes the atom from 'dep'.
#Make sure it doesn't conflict with REQUIRED_USE.
required_use = parent.metadata.get("REQUIRED_USE", "")
if check_required_use(required_use, current_use, parent.iuse.is_valid_flag):
use = self.depgraph._pkg_use_enabled(parent)
solution = set()
for flag, state in zip(affecting_use, use_state):
if state == "enabled" and \
flag not in use:
solution.add((flag, True))
elif state == "disabled" and \
flag in use:
solution.add((flag, False))
solutions.add(frozenset(solution))
for solution in solutions:
ignore_solution = False
for other_solution in solutions:
if solution is other_solution:
continue
if solution.issuperset(other_solution):
ignore_solution = True
if ignore_solution:
continue
#Check if a USE change conflicts with use requirements of the parents.
#If a requiremnet is hard, ignore the suggestion.
#If the requirment is conditional, warn the user that other changes might be needed.
followup_change = False
parent_parent_atoms = self.depgraph._dynamic_config._parent_atoms.get(changed_parent)
for ppkg, atom in parent_parent_atoms:
atom = atom.unevaluated_atom
if not atom.use:
continue
for flag, state in solution:
if flag in atom.use.enabled or flag in atom.use.disabled:
ignore_solution = True
break
elif atom.use.conditional:
for flags in atom.use.conditional.values():
if flag in flags:
followup_change = True
break
if ignore_solution:
break
if ignore_solution:
continue
changes = []
for flag, state in solution:
if state:
changes.append(colorize("red", "+"+flag))
else:
changes.append(colorize("blue", "-"+flag))
msg = "- %s (Change USE: %s)\n" \
% (parent.cpv, " ".join(changes))
if followup_change:
msg += " (This change might require USE changes on parent packages.)"
suggestions.append(msg)
final_solutions.setdefault(pkg, set()).add(solution)
return final_solutions, suggestions
def debug_print(self):
"""
Create a copy of the digraph, prune all root nodes,
and call the debug_print() method.
"""
graph = self.graph.copy()
while True:
root_nodes = graph.root_nodes(
ignore_priority=DepPrioritySatisfiedRange.ignore_medium_soft)
if not root_nodes:
break
graph.difference_update(root_nodes)
graph.debug_print()
|
