Move the clever parts of depgraph._show_circular_deps into its own module.

This also fixes some bugs related to autounmask.

2 files changed, 240 insertions, 155 deletions

diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index 004534dbe..f2950fb66 100644
--- a/pym/_emerge/depgraph.py
+++ b/pym/_emerge/depgraph.py
@@ -56,6 +56,7 @@ from _emerge.show_invalid_depstring_notice import show_invalid_depstring_notice
 from _emerge.UnmergeDepPriority import UnmergeDepPriority
 
 from _emerge.resolver.slot_collision import slot_conflict_handler
+from _emerge.resolver.circular_dependency import circular_dependency_handler
 
 if sys.hexversion >= 0x3000000:
 	basestring = str
@@ -170,6 +171,7 @@ class _dynamic_depgraph_config(object):
 		self._parent_atoms = {}
 		self._slot_conflict_parent_atoms = set()
 		self._slot_conflict_handler = None
+		self._circular_dependency_handler = None
 		self._serialized_tasks_cache = None
 		self._scheduler_graph = None
 		self._displayed_list = None
@@ -4100,170 +4102,27 @@ class depgraph(object):
 		return retlist, scheduler_graph
 
 	def _show_circular_deps(self, mygraph):
-		shortest_cycle = None
-		cycles = mygraph.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
-		# Display the USE flags that are enabled on nodes that are part
-		# of dependency cycles in case that helps the user decide to
-		# disable some of them.
-		display_order = []
-		tempgraph = mygraph.copy()
-		while not tempgraph.empty():
-			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()
+		self._dynamic_config._circular_dependency_handler = \
+			circular_dependency_handler(self, mygraph)
+		handler = self._dynamic_config._circular_dependency_handler
+
 		self._frozen_config.myopts.pop("--quiet", None)
 		self._frozen_config.myopts["--verbose"] = True
 		self._frozen_config.myopts["--tree"] = True
 		portage.writemsg("\n\n", noiselevel=-1)
-		self.display(display_order)
+		self.display(handler.merge_list)
 		prefix = colorize("BAD", " * ")
 		portage.writemsg("\n", noiselevel=-1)
 		portage.writemsg(prefix + "Error: circular dependencies:\n",
 			noiselevel=-1)
 		portage.writemsg("\n", noiselevel=-1)
 
-		suggestions = []
-		if shortest_cycle:
-			indent = ""
-			for id, pkg in enumerate(shortest_cycle):
-				if id > 0:
-					parent = shortest_cycle[id-1]
-				else:
-					parent = shortest_cycle[-1]
-
-				priorities = mygraph.nodes[parent][0][pkg]
-				if id > 0:
-					writemsg(indent + "%s (%s)\n" % (pkg, priorities[-1],), noiselevel=-1)
-				else:
-					writemsg(indent + str(pkg) + " depends on\n", noiselevel=-1)
-
-				if priorities[-1].buildtime:
-					dep = parent.metadata["DEPEND"]
-				elif priorities[-1].runtime:
-					dep = parent.metadata["RDEPEND"]
-				parent_atoms = self._dynamic_config._parent_atoms.get(pkg)
-				for ppkg, atom in parent_atoms:
-					if ppkg == parent:
-						changed_parent = ppkg
-						parent_atom = atom.unevaluated_atom
-						break
-				affecting_use = portage.dep.extract_affecting_use(dep, parent_atom)
-				
-				# Make sure we don't want to change a flag that is in use.mask or use.force.
-				pkgsettings = self._frozen_config.pkgsettings[parent.root]
-				pkgsettings.setcpv(parent)
-				affecting_use.difference_update(pkgsettings.usemask, pkgsettings.useforce)
-				
-				if affecting_use:
-					affecting_use = list(affecting_use)
-					#We iterate over all possible settings of these use flags and gather
-					#a set of possible changes
-					use_state = []
-					for flag in affecting_use:
-						use_state.append("disabled") 
-					
-					def _next_use_state(state, id=None):
-						if id is None:
-							id = len(state)-1
-							
-						if id == 0 and state[0] == "enabled":
-							return False
-
-						if state[id] == "disabled":
-							state[id] = "enabled"
-							for i in range(id+1,len(state)):
-								state[i] = "disabled"
-							return True
-						else:
-							return _next_use_state(state, id-1)
-
-					solutions = set()
-					while(True):
-						current_use = []
-						for flag, state in zip(affecting_use, use_state):
-							if state == "enabled":
-								current_use.append(flag)
-						reduced_dep = portage.dep.use_reduce(dep,
-							uselist=current_use, flat=True)
-
-						if parent_atom not in reduced_dep:
-							#we found a valid solution
-							solution = []
-							for flag, state in zip(affecting_use, use_state):
-								if state == "enabled" and \
-									flag not in parent.use.enabled:
-									solution.append("+" + flag)
-								elif state == "disabled" and \
-									flag in parent.use.enabled:
-									solution.append("-" + flag)
-							solutions.add(frozenset(solution))
-						if not _next_use_state(use_state):
-							break
-					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._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 in solution:
-								flag = flag[1:] #flag has a +/- prefix
-								if flag in atom.use.enabled \
-									or flag in atom.use.disabled:
-									ignore_solution = True
-									break
-								elif atom.use.conditional and flag in atom.use.conditional:
-									followup_change = True
-
-							if ignore_solution:
-								break
-
-						if ignore_solution:
-							continue
-
-						changes = []
-						for flag in solution:
-							if flag.startswith("+"):
-								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)
-
-				indent += " "
-
-			pkg = shortest_cycle[0]
-			parent = shortest_cycle[-1]
-			priorities = mygraph.nodes[parent][0][pkg]
-			writemsg(indent + "%s (%s)\n" % (pkg, priorities[-1],), noiselevel=-1)
-		else:
+		if handler.circular_dep_message is None:
 			mygraph.debug_print()
+		else:
+			portage.writemsg(handler.circular_dep_message, noiselevel=-1)
 
+		suggestions = handler.suggestions
 		if suggestions:
 			writemsg("\n\nIt might be possible to break this cycle\n", noiselevel=-1)
 			if len(suggestions) == 1:
@@ -4274,18 +4133,17 @@ class depgraph(object):
 			writemsg("".join(suggestions), noiselevel=-1)
 			writemsg("\nNote that this change can be reverted, once the package has" + \
 				" been installed.\n", noiselevel=-1)
-			if len(cycles) > 3:
+			if handler.large_cycle_count:
 				writemsg("\nNote that the dependency graph contains a lot of cycles.\n" + \
 					"Several changes might be required to resolve all cycles.\n" + \
 					"Temporarily changing some use flag for all packages might be the better option.\n", noiselevel=-1)
 		else:
-			writemsg("\n", noiselevel=-1)
+			writemsg("\n\n", noiselevel=-1)
 			writemsg(prefix + "Note that circular dependencies " + \
 				"can often be avoided by temporarily\n", noiselevel=-1)
 			writemsg(prefix + "disabling USE flags that trigger " + \
 				"optional dependencies.\n", noiselevel=-1)
 
-
 	def _show_merge_list(self):
 		if self._dynamic_config._serialized_tasks_cache is not None and \
 			not (self._dynamic_config._displayed_list and \
diff --git a/pym/_emerge/resolver/circular_dependency.py b/pym/_emerge/resolver/circular_dependency.py
new file mode 100644
index 000000000..0930049d2
--- /dev/null
+++ b/pym/_emerge/resolver/circular_dependency.py
@@ -0,0 +1,227 @@
+# Copyright 2010 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from __future__ import print_function
+
+from portage.util import writemsg
+from portage.dep import use_reduce, extract_affecting_use
+from portage.output import colorize
+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
+
+		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 not tempgraph.empty():
+			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):
+		pkgsettings = self.depgraph._frozen_config.pkgsettings[pkg.root]
+		pkgsettings.setcpv(pkg)
+		return frozenset(pkgsettings.usemask), frozenset(pkgsettings.useforce)
+
+	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
+
+			affecting_use = extract_affecting_use(dep, parent_atom)
+
+			# 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)
+			affecting_use.difference_update(usemask, useforce, autounmask_changes)
+			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
+			use_state = []
+			for flag in affecting_use:
+				use_state.append("disabled")
+			
+			def _next_use_state(state, id=None):
+				if id is None:
+					id = len(state)-1
+					
+				if id == 0 and state[0] == "enabled":
+					return False
+
+				if state[id] == "disabled":
+					state[id] = "enabled"
+					for i in range(id+1,len(state)):
+						state[i] = "disabled"
+					return True
+				else:
+					return _next_use_state(state, id-1)
+
+			solutions = set()
+			while(True):
+				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)
+				reduced_dep = use_reduce(dep,
+					uselist=current_use, flat=True)
+
+				if parent_atom not in reduced_dep:
+					#we found a valid solution
+					solution = set()
+					use = self.depgraph._pkg_use_enabled(parent)
+					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))
+				if not _next_use_state(use_state):
+					break
+
+			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(frozenset(solution))
+		
+		return final_solutions, suggestions