Solve more slot-operator conflicts (531656)

Add some heuristics to handle slot conflicts triggered by interaction
of slot-operator dependencies with dependencies like those of labgl:

		ocaml:= || ( labltk <ocaml-4.02 )

The new heuristics involve some behavior modifications in the depgraph
_solve_non_slot_operator_slot_conflicts method and in dep_zapdeps. The
dep_zapdeps changes affect the behavior of _select_atoms_probe calls
in the depgraph _slot_operator_update_probe method.

X-Gentoo-Bug: 531656
X-Gentoo-Bug-URL: https://bugs.gentoo.org/show_bug.cgi?id=531656
Acked-by: Alexander Berntsen <bernalex@gentoo.org>

3 files changed, 124 insertions, 4 deletions

diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index 28abea44f..6266c79c8 100644
--- a/pym/_emerge/depgraph.py
+++ b/pym/_emerge/depgraph.py
@@ -1,4 +1,4 @@
-# Copyright 1999-2014 Gentoo Foundation
+# Copyright 1999-2015 Gentoo Foundation
 # Distributed under the terms of the GNU General Public License v2
 
 from __future__ import division, print_function, unicode_literals
@@ -451,6 +451,7 @@ class _dynamic_depgraph_config(object):
 			self._graph_trees[myroot]["graph_db"]   = graph_tree.dbapi
 			self._graph_trees[myroot]["graph"]      = self.digraph
 			self._graph_trees[myroot]["want_update_pkg"] = depgraph._want_update_pkg
+			self._graph_trees[myroot]["downgrade_probe"] = depgraph._downgrade_probe
 			def filtered_tree():
 				pass
 			filtered_tree.dbapi = _dep_check_composite_db(depgraph, myroot)
@@ -478,6 +479,7 @@ class _dynamic_depgraph_config(object):
 			self._filtered_trees[myroot]["vartree"] = \
 				depgraph._frozen_config.trees[myroot]["vartree"]
 			self._filtered_trees[myroot]["want_update_pkg"] = depgraph._want_update_pkg
+			self._filtered_trees[myroot]["downgrade_probe"] = depgraph._downgrade_probe
 
 			dbs = []
 			#               (db, pkg_type, built, installed, db_keys)
@@ -1144,7 +1146,13 @@ class depgraph(object):
 					writemsg_level("      pkg: %s\n" % pkg, level=logging.DEBUG, noiselevel=-1)
 
 			all_parent_atoms = set()
+			highest_pkg = None
+			inst_pkg = None
 			for pkg in conflict:
+				if pkg.installed:
+					inst_pkg = pkg
+				if highest_pkg is None or highest_pkg < pkg:
+					highest_pkg = pkg
 				all_parent_atoms.update(
 					self._dynamic_config._parent_atoms.get(pkg, []))
 
@@ -1167,6 +1175,15 @@ class depgraph(object):
 
 				matched = []
 				for pkg in conflict:
+					if (pkg is highest_pkg and
+						not highest_pkg.installed and
+						inst_pkg is not None and
+						inst_pkg.sub_slot != highest_pkg.sub_slot and
+						not self._downgrade_probe(highest_pkg)):
+						# If an upgrade is desired, force the highest
+						# version into the graph (bug #531656).
+						non_matching_forced.add(highest_pkg)
+
 					if atom_set.findAtomForPackage(pkg, \
 						modified_use=self._pkg_use_enabled(pkg)) and \
 						not (is_arg_parent and pkg.installed):
@@ -1220,14 +1237,20 @@ class depgraph(object):
 		# the packages in the tuple. This way we don't have
 		# to choose one.
 		unexplored_tuples = set()
+		explored_nodes = set()
 
 		while unexplored:
 			# Handle all unexplored packages.
 			while unexplored:
 				node = unexplored.pop()
 				for child in conflict_graph.child_nodes(node):
-					if child in forced:
+					# Don't explore a node more than once, in order
+					# to avoid infinite recursion. The forced set
+					# cannot be used for this purpose, since it can
+					# contain unexplored nodes from non_matching_forced.
+					if child in explored_nodes:
 						continue
+					explored_nodes.add(child)
 					forced.add(child)
 					if isinstance(child, Package):
 						unexplored.add(child)
@@ -8817,6 +8840,11 @@ def _backtrack_depgraph(settings, trees, myopts, myparams, myaction, myfiles, sp
 			mydepgraph.display_problems()
 
 		backtrack_parameters = backtracker.get()
+		if debug and backtrack_parameters.runtime_pkg_mask:
+			writemsg_level(
+				"\n\nruntime_pkg_mask: %s \n\n" %
+				backtrack_parameters.runtime_pkg_mask,
+				noiselevel=-1, level=logging.DEBUG)
 
 		mydepgraph = depgraph(settings, trees, myopts, myparams, spinner,
 			frozen_config=frozen_config,
diff --git a/pym/portage/dep/dep_check.py b/pym/portage/dep/dep_check.py
index ccdda5993..69b358c95 100644
--- a/pym/portage/dep/dep_check.py
+++ b/pym/portage/dep/dep_check.py
@@ -1,4 +1,4 @@
-# Copyright 2010-2014 Gentoo Foundation
+# Copyright 2010-2015 Gentoo Foundation
 # Distributed under the terms of the GNU General Public License v2
 
 from __future__ import unicode_literals
@@ -319,6 +319,7 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None):
 	graph    = trees[myroot].get("graph")
 	pkg_use_enabled = trees[myroot].get("pkg_use_enabled")
 	want_update_pkg = trees[myroot].get("want_update_pkg")
+	downgrade_probe = trees[myroot].get("downgrade_probe")
 	vardb = None
 	if "vartree" in trees[myroot]:
 		vardb = trees[myroot]["vartree"].dbapi
@@ -351,6 +352,7 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None):
 		all_available = True
 		all_use_satisfied = True
 		all_use_unmasked = True
+		conflict_downgrade = False
 		slot_map = {}
 		cp_map = {}
 		for atom in atoms:
@@ -367,6 +369,16 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None):
 				all_use_satisfied = False
 				break
 
+			if graph_db is not None and downgrade_probe is not None:
+				slot_matches = graph_db.match_pkgs(avail_slot)
+				if (len(slot_matches) > 1 and
+					avail_pkg < slot_matches[-1] and
+					not downgrade_probe(avail_pkg)):
+					# If a downgrade is not desirable, then avoid a
+					# choice that pulls in a lower version involved
+					# in a slot conflict (bug #531656).
+					conflict_downgrade = True
+
 			if atom.use:
 				avail_pkg_use = mydbapi_match_pkgs(atom)
 				if not avail_pkg_use:
@@ -450,6 +462,8 @@ def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None):
 						unsat_use_installed.append(this_choice)
 					else:
 						unsat_use_non_installed.append(this_choice)
+			elif conflict_downgrade:
+				other.append(this_choice)
 			else:
 				all_in_graph = True
 				for atom in atoms:
diff --git a/pym/portage/tests/resolver/test_or_choices.py b/pym/portage/tests/resolver/test_or_choices.py
index 4aae0b2e7..63e62d010 100644
--- a/pym/portage/tests/resolver/test_or_choices.py
+++ b/pym/portage/tests/resolver/test_or_choices.py
@@ -1,4 +1,4 @@
-# Copyright 2013-2014 Gentoo Foundation
+# Copyright 2013-2015 Gentoo Foundation
 # Distributed under the terms of the GNU General Public License v2
 
 from portage.tests import TestCase
@@ -262,3 +262,81 @@ class OrChoicesTestCase(TestCase):
 					test_case.fail_msg)
 		finally:
 			playground.cleanup()
+
+	def testConflictMissedUpdate(self):
+
+		ebuilds = {
+			"dev-lang/ocaml-4.02.1" : {
+				"EAPI": "5",
+				"SLOT": "0/4.02.1",
+			},
+
+			"dev-lang/ocaml-4.01.0" : {
+				"EAPI": "5",
+				"SLOT": "0/4.01.0",
+			},
+
+			"dev-ml/lablgl-1.05" : {
+				"EAPI": "5",
+				"DEPEND": (">=dev-lang/ocaml-3.10.2:= "
+					"|| ( dev-ml/labltk:= <dev-lang/ocaml-4.02 )"),
+				"RDEPEND": (">=dev-lang/ocaml-3.10.2:= "
+					"|| ( dev-ml/labltk:= <dev-lang/ocaml-4.02 )"),
+			},
+
+			"dev-ml/labltk-8.06.0" : {
+				"EAPI": "5",
+				"SLOT": "0/8.06.0",
+				"DEPEND": ">=dev-lang/ocaml-4.02:=",
+				"RDEPEND": ">=dev-lang/ocaml-4.02:=",
+			},
+		}
+
+		installed = {
+			"dev-lang/ocaml-4.01.0" : {
+				"EAPI": "5",
+				"SLOT": "0/4.01.0",
+			},
+
+			"dev-ml/lablgl-1.05" : {
+				"EAPI": "5",
+				"DEPEND": (">=dev-lang/ocaml-3.10.2:0/4.01.0= "
+					"|| ( dev-ml/labltk:= <dev-lang/ocaml-4.02 )"),
+				"RDEPEND": (">=dev-lang/ocaml-3.10.2:0/4.01.0= "
+					"|| ( dev-ml/labltk:= <dev-lang/ocaml-4.02 )"),
+			},
+		}
+
+		world = (
+			"dev-lang/ocaml",
+			"dev-ml/lablgl",
+		)
+
+		test_cases = (
+
+			# bug #531656: If an ocaml update is desirable,
+			# then we need to pull in dev-ml/labltk.
+			ResolverPlaygroundTestCase(
+				["@world"],
+				options = {"--update": True, "--deep": True},
+				success = True,
+				mergelist = [
+					"dev-lang/ocaml-4.02.1",
+					"dev-ml/labltk-8.06.0",
+					"dev-ml/lablgl-1.05",
+				]
+			),
+
+		)
+
+		playground = ResolverPlayground(debug=False,
+			ebuilds=ebuilds, installed=installed, world=world)
+		try:
+			for test_case in test_cases:
+				playground.run_TestCase(test_case)
+				self.assertEqual(test_case.test_success, True,
+					test_case.fail_msg)
+		finally:
+			# Disable debug so that cleanup works.
+			playground.debug = False
+			playground.cleanup()