pym/_emerge/resolver/circular_dependency.py

# Copyright 2010-2012 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
from _emerge.Package import Package

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 = " ".join(parent.metadata[k]
					for k in Package._buildtime_keys)
			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", ""),
				eapi=parent.metadata["EAPI"])

			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,
						eapi=parent.metadata["EAPI"]):
						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()