Bug #275217 - Part 5 - When a slot conflict occurs, mask the first package

that got pulled in and restart the calculation. Thanks to Sebastian Mingramm
(few) <s.mingramm@gmx.de> for the initial patch which I added some additional
features to:

 * display message about missed updates
 * cache frozen_config instance, to optimize performance
 * disable backtracking if it fails, fall back to a normal
   dep calculation + error message.

svn path=/main/trunk/; revision=13769

2 files changed, 143 insertions, 23 deletions

diff --git a/pym/_emerge/actions.py b/pym/_emerge/actions.py
index 9213211a0..85a8170ff 100644
--- a/pym/_emerge/actions.py
+++ b/pym/_emerge/actions.py
@@ -40,7 +40,7 @@ from _emerge.clear_caches import clear_caches
 from _emerge.countdown import countdown
 from _emerge.create_depgraph_params import create_depgraph_params
 from _emerge.Dependency import Dependency
-from _emerge.depgraph import depgraph, resume_depgraph
+from _emerge.depgraph import depgraph, resume_depgraph, _frozen_depgraph_config
 from _emerge.DepPrioritySatisfiedRange import DepPrioritySatisfiedRange
 from _emerge.emergelog import emergelog
 from _emerge.is_valid_package_atom import is_valid_package_atom
@@ -297,25 +297,49 @@ def action_build(settings, trees, mtimedb,
 			print darkgreen("emerge: It seems we have nothing to resume...")
 			return os.EX_OK
 
-		myparams = create_depgraph_params(myopts, myaction)
 		if "--quiet" not in myopts and "--nodeps" not in myopts:
 			print "Calculating dependencies  ",
 			sys.stdout.flush()
-		mydepgraph = depgraph(settings, trees, myopts, myparams, spinner)
-		try:
-			retval, favorites = mydepgraph.select_files(myfiles)
-		except portage.exception.PackageNotFound, e:
-			portage.writemsg("\n!!! %s\n" % str(e), noiselevel=-1)
-			return 1
-		except portage.exception.PackageSetNotFound, e:
-			root_config = trees[settings["ROOT"]]["root_config"]
-			display_missing_pkg_set(root_config, e.value)
-			return 1
+
+		runtime_pkg_mask = None
+		allow_backtracking = True
+		backtracked = False
+		frozen_config = _frozen_depgraph_config(settings, trees,
+			myopts, spinner)
+		myparams = create_depgraph_params(myopts, myaction)
+		while True:
+			mydepgraph = depgraph(settings, trees, myopts, myparams, spinner,
+				frozen_config=frozen_config,
+				allow_backtracking=allow_backtracking,
+				runtime_pkg_mask=runtime_pkg_mask)
+			try:
+				retval, favorites = mydepgraph.select_files(myfiles)
+			except portage.exception.PackageNotFound, e:
+				portage.writemsg("\n!!! %s\n" % str(e), noiselevel=-1)
+				return 1
+			except portage.exception.PackageSetNotFound, e:
+				root_config = trees[settings["ROOT"]]["root_config"]
+				display_missing_pkg_set(root_config, e.value)
+				return 1
+			if not retval:
+				if mydepgraph.need_restart():
+					runtime_pkg_mask = mydepgraph.get_runtime_pkg_mask()
+					backtracked = True
+				elif backtracked and allow_backtracking:
+					# Backtracking failed, so disable it and do
+					# a plain dep calculation + error message.
+					allow_backtracking = False
+					runtime_pkg_mask = None
+				else:
+					mydepgraph.display_problems()
+					return 1
+			else:
+				break
+
+		del frozen_config
+
 		if show_spinner:
 			print "\b\b... done!"
-		if not retval:
-			mydepgraph.display_problems()
-			return 1
 
 	if "--pretend" not in myopts and \
 		("--ask" in myopts or "--tree" in myopts or \
diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index 144f57bc9..509f298e3 100644
--- a/pym/_emerge/depgraph.py
+++ b/pym/_emerge/depgraph.py
@@ -91,8 +91,10 @@ class _frozen_depgraph_config(object):
 
 class _dynamic_depgraph_config(object):
 
-	def __init__(self, depgraph, myparams):
-		self.myparams = myparams
+	def __init__(self, depgraph, myparams, allow_backtracking,
+		runtime_pkg_mask):
+		self.myparams = myparams.copy()
+		self._allow_backtracking = allow_backtracking
 		# Maps slot atom to package for each Package added to the graph.
 		self._slot_pkg_map = {}
 		# Maps nodes to the reasons they were selected for reinstallation.
@@ -155,6 +157,13 @@ class _dynamic_depgraph_config(object):
 		self._initially_unsatisfied_deps = []
 		self._ignored_deps = []
 		self._highest_pkg_cache = {}
+		if runtime_pkg_mask is None:
+			runtime_pkg_mask = {}
+		else:
+			runtime_pkg_mask = dict((k, v.copy()) for (k, v) in \
+				runtime_pkg_mask.iteritems())
+		self._runtime_pkg_mask = runtime_pkg_mask
+		self._need_restart = False
 
 		for myroot in depgraph._frozen_config.trees:
 			self._slot_pkg_map[myroot] = {}
@@ -245,16 +254,63 @@ class depgraph(object):
 	_dep_keys = ["DEPEND", "RDEPEND", "PDEPEND"]
 	
 	def __init__(self, settings, trees, myopts, myparams, spinner,
-		frozen_config=None):	
+		frozen_config=None, runtime_pkg_mask=None, allow_backtracking=False):
 		if frozen_config is None:
 			frozen_config = _frozen_depgraph_config(settings, trees,
 			myopts, spinner)
 		self._frozen_config = frozen_config
-		self._dynamic_config = _dynamic_depgraph_config(self, myparams)
+		self._dynamic_config = _dynamic_depgraph_config(self, myparams,
+			allow_backtracking, runtime_pkg_mask)
 
 		self._select_atoms = self._select_atoms_highest_available
 		self._select_package = self._select_pkg_highest_available
 
+	def _show_missed_update(self):
+
+		missed_updates = {}
+		for pkg, mask_reasons in \
+			self._dynamic_config._runtime_pkg_mask.iteritems():
+			if mask_reasons.get("slot conflict"):
+				if pkg.slot_atom in missed_updates:
+					other_pkg, parent_atoms = missed_updates[pkg.slot_atom]
+					if other_pkg > pkg:
+						continue
+				missed_updates[pkg.slot_atom] = \
+					(pkg, mask_reasons["slot conflict"])
+
+		if not missed_updates:
+			return
+
+		msg = []
+		msg.append("\n!!! One or more updates have been skipped due to " + \
+			"a dependency conflict:\n\n")
+
+		indent = "  "
+		for pkg, parent_atoms in missed_updates.itervalues():
+			msg.append(str(pkg.slot_atom))
+			msg.append("\n\n")
+
+			for parent, atom in parent_atoms:
+				msg.append(indent)
+				msg.append(str(pkg))
+
+				msg.append(" conflicts with\n")
+				for parent, atom in parent_atoms:
+					msg.append(2*indent)
+					if isinstance(parent,
+						(PackageArg, AtomArg)):
+						# For PackageArg and AtomArg types, it's
+						# redundant to display the atom attribute.
+						msg.append(str(parent))
+					else:
+						# Display the specific atom from SetArg or
+						# Package types.
+						msg.append("%s required by %s" % (atom, parent))
+					msg.append("\n")
+				msg.append("\n")
+		sys.stderr.write("".join(msg))
+		sys.stderr.flush()
+
 	def _show_slot_collision_notice(self):
 		"""Show an informational message advising the user to mask one of the
 		the packages. In some cases it may be possible to resolve this
@@ -696,6 +752,31 @@ class depgraph(object):
 								(dep.parent, dep.atom))
 					return 1
 				else:
+					# A slot conflict has occurred. 
+					if self._dynamic_config._allow_backtracking and \
+						not self._accept_blocker_conflicts():
+						self._add_slot_conflict(pkg)
+						if dep.atom is not None and dep.parent is not None:
+							self._add_parent_atom(pkg, (dep.parent, dep.atom))
+						if arg_atoms:
+							for parent_atom in arg_atoms:
+								parent, atom = parent_atom
+								self._add_parent_atom(pkg, parent_atom)
+						self._process_slot_conflicts()
+
+						parent_atoms = \
+							self._dynamic_config._parent_atoms.get(pkg, set())
+						if parent_atoms:
+							parent_atoms = self._dynamic_config._slot_conflict_parent_atoms.intersection(parent_atoms)
+						if pkg >= existing_node:
+							# We only care about the parent atoms
+							# when they trigger a downgrade.
+							parent_atoms = set()
+
+						self._dynamic_config._runtime_pkg_mask.setdefault(
+							existing_node, {})["slot conflict"] = parent_atoms
+						self._dynamic_config._need_restart = True
+						return 0
 
 					# A slot collision has occurred.  Sometimes this coincides
 					# with unresolvable blockers, so the slot collision will be
@@ -1380,8 +1461,10 @@ class depgraph(object):
 					if isinstance(arg, PackageArg):
 						if not self._add_pkg(arg.package, dep) or \
 							not self._create_graph():
-							sys.stderr.write(("\n\n!!! Problem resolving " + \
-								"dependencies for %s\n") % arg.arg)
+							if not self._dynamic_config._need_restart:
+								sys.stderr.write(("\n\n!!! Problem " + \
+									"resolving dependencies for %s\n") % \
+									arg.arg)
 							return 0, myfavorites
 						continue
 					if debug:
@@ -1441,7 +1524,9 @@ class depgraph(object):
 					# so that later dep_check() calls can use it as feedback
 					# for making more consistent atom selections.
 					if not self._add_pkg(pkg, dep):
-						if isinstance(arg, SetArg):
+						if self._dynamic_config._need_restart:
+							pass
+						elif isinstance(arg, SetArg):
 							sys.stderr.write(("\n\n!!! Problem resolving " + \
 								"dependencies for %s from %s\n") % \
 								(atom, arg.arg))
@@ -1945,6 +2030,9 @@ class depgraph(object):
 
 				for pkg in self._iter_match_pkgs(root_config, pkg_type, atom, 
 					onlydeps=onlydeps):
+					if pkg in self._dynamic_config._runtime_pkg_mask:
+						# The package has been masked by the backtracking logic
+						continue
 					cpv = pkg.cpv
 					# Make --noreplace take precedence over --newuse.
 					if not pkg.installed and noreplace and \
@@ -4212,8 +4300,10 @@ class depgraph(object):
 		if self._dynamic_config._unsatisfied_blockers_for_display is not None:
 			self._show_unsatisfied_blockers(
 				self._dynamic_config._unsatisfied_blockers_for_display)
-		else:
+		elif self._dynamic_config._slot_collision_info:
 			self._show_slot_collision_notice()
+		else:
+			self._show_missed_update()
 
 		# TODO: Add generic support for "set problem" handlers so that
 		# the below warnings aren't special cases for world only.
@@ -4572,6 +4662,12 @@ class depgraph(object):
 		graph in order to avoid making a potentially unsafe decision.
 		"""
 
+	def need_restart(self):
+		return self._dynamic_config._need_restart
+
+	def get_runtime_pkg_mask(self):
+		return self._dynamic_config._runtime_pkg_mask.copy()
+
 class _dep_check_composite_db(portage.dbapi):
 	"""
 	A dbapi-like interface that is optimized for use in dep_check() calls.