emerge: terminate backtracking early for autounmask changes (bug 615680)

Since autounmask changes are a strong indicator that backtracking
will ultimately fail to produce a solution, terminate early for
autounmask changes, and add a --autounmask-backtrack=<y|n> option
to modify this behavior. The --autounmask-continue option implies
--autounmask-backtrack=y behavior, for backward compatibility.

When backtracking terminates early, the following warning message
is displayed after the autounmask change(s):

 * In order to avoid wasting time, backtracking has terminated early
 * due to the above autounmask change(s). The --autounmask-backtrack=y
 * option can be used to force further backtracking, but there is no
 * guarantee that it will produce a solution.

With this change, five of the existing cases fail unless
--autounmask-backtrack=y is added to the options. For each of
these cases, comments below the test case document how it behaves
with and without --autounmask-backtrack=y enabled.

X-Gentoo-bug: 615680
X-Gentoo-bug-url: https://bugs.gentoo.org/show_bug.cgi?id=615680
Acked-by: Brian Dolbec <dolsen@gentoo.org>

6 files changed, 237 insertions, 17 deletions

diff --git a/man/emerge.1 b/man/emerge.1
index f1a9d4f3f..94edc9095 100644
--- a/man/emerge.1
+++ b/man/emerge.1
@@ -363,12 +363,20 @@ the specified configuration file(s), or enable the
 \fBEMERGE_DEFAULT_OPTS\fR variable may be used to
 disable this option by default in \fBmake.conf\fR(5).
 .TP
+.BR "\-\-autounmask\-backtrack < y | n >"
+Allow backtracking after autounmask has detected that
+configuration changes are necessary. This option is not
+recommended, since it can cause a large amount of time to
+be wasted by backtracking calculations, even though there
+is no guarantee that it will produce a solution. This
+option is disabled by default.
+.TP
 .BR "\-\-autounmask\-continue [ y | n ]"
 Automatically apply autounmask changes to configuration
 files, and continue to execute the specified command. If
 the dependency calculation is not entirely successful, then
 emerge will simply abort without modifying any configuration
-files.
+files. This option implies \fB\-\-autounmask\-backtrack=y\fR.
 \fBWARNING:\fR
 This option is intended to be used only with great caution,
 since it is possible for it to make nonsensical configuration
diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index e1119af3c..53910dd25 100644
--- a/pym/_emerge/depgraph.py
+++ b/pym/_emerge/depgraph.py
@@ -444,6 +444,7 @@ class _dynamic_depgraph_config(object):
 		self._autounmask = depgraph._frozen_config.myopts.get('--autounmask') != 'n'
 		self._displayed_autounmask = False
 		self._success_without_autounmask = False
+		self._autounmask_backtrack_disabled = False
 		self._required_use_unsatisfied = False
 		self._traverse_ignored_deps = False
 		self._complete_mode = False
@@ -1129,7 +1130,8 @@ class depgraph(object):
 
 		self._show_merge_list()
 
-		self._dynamic_config._slot_conflict_handler = slot_conflict_handler(self)
+		if self._dynamic_config._slot_conflict_handler is None:
+			self._dynamic_config._slot_conflict_handler = slot_conflict_handler(self)
 		handler = self._dynamic_config._slot_conflict_handler
 
 		conflict = handler.get_conflict()
@@ -4243,17 +4245,7 @@ class depgraph(object):
 		# set below is reserved for cases where there are *zero* other
 		# problems. For reference, see backtrack_depgraph, where it skips the
 		# get_best_run() call when success_without_autounmask is True.
-
-		digraph_nodes = self._dynamic_config.digraph.nodes
-
-		if any(x in digraph_nodes for x in
-			self._dynamic_config._needed_unstable_keywords) or \
-			any(x in digraph_nodes for x in
-			self._dynamic_config._needed_p_mask_changes) or \
-			any(x in digraph_nodes for x in
-			self._dynamic_config._needed_use_config_changes) or \
-			any(x in digraph_nodes for x in
-			self._dynamic_config._needed_license_changes) :
+		if self._have_autounmask_changes():
 			#We failed if the user needs to change the configuration
 			self._dynamic_config._success_without_autounmask = True
 			if (self._frozen_config.myopts.get("--autounmask-continue") is True and
@@ -8564,6 +8556,17 @@ class depgraph(object):
 				"experimental or unstable packages.\n",
 				noiselevel=-1)
 
+		if self._dynamic_config._autounmask_backtrack_disabled:
+			msg = [
+				"In order to avoid wasting time, backtracking has terminated early",
+				"due to the above autounmask change(s). The --autounmask-backtrack=y",
+				"option can be used to force further backtracking, but there is no",
+				"guarantee that it will produce a solution.",
+			]
+			writemsg("\n", noiselevel=-1)
+			for line in msg:
+				writemsg(" %s %s\n" % (colorize("WARN", "*"), line),
+					noiselevel=-1)
 
 	def display_problems(self):
 		"""
@@ -9072,8 +9075,57 @@ class depgraph(object):
 			not self._dynamic_config._skip_restart
 
 	def need_config_change(self):
-		return self._dynamic_config._success_without_autounmask or \
-			self._dynamic_config._required_use_unsatisfied
+		"""
+		Returns true if backtracking should terminate due to a needed
+		configuration change.
+		"""
+		if (self._dynamic_config._success_without_autounmask or
+			self._dynamic_config._required_use_unsatisfied):
+			return True
+
+		if (self._dynamic_config._slot_conflict_handler is None and
+			not self._accept_blocker_conflicts() and
+			any(self._dynamic_config._package_tracker.slot_conflicts())):
+			self._dynamic_config._slot_conflict_handler = slot_conflict_handler(self)
+			if self._dynamic_config._slot_conflict_handler.changes:
+				# Terminate backtracking early if the slot conflict
+				# handler finds some changes to suggest. The case involving
+				# sci-libs/L and sci-libs/M in SlotCollisionTestCase will
+				# otherwise fail with --autounmask-backtrack=n, since
+				# backtracking will eventually lead to some autounmask
+				# changes. Changes suggested by the slot conflict handler
+				# are more likely to be useful.
+				return True
+
+		if (self._dynamic_config._allow_backtracking and
+			self._frozen_config.myopts.get("--autounmask-backtrack") != 'y' and
+			self._have_autounmask_changes()):
+
+			if (self._frozen_config.myopts.get("--autounmask-continue") is True and
+				self._frozen_config.myopts.get("--autounmask-backtrack") != 'n'):
+				# --autounmask-continue implies --autounmask-backtrack=y behavior,
+				# for backward compatibility.
+				return False
+
+			# This disables backtracking when there are autounmask
+			# config changes. The display_problems method will notify
+			# the user that --autounmask-backtrack=y can be used to
+			# force backtracking in this case.
+			self._dynamic_config._autounmask_backtrack_disabled = True
+			return True
+
+		return False
+
+	def _have_autounmask_changes(self):
+		digraph_nodes = self._dynamic_config.digraph.nodes
+		return (any(x in digraph_nodes for x in
+			self._dynamic_config._needed_unstable_keywords) or
+			any(x in digraph_nodes for x in
+			self._dynamic_config._needed_p_mask_changes) or
+			any(x in digraph_nodes for x in
+			self._dynamic_config._needed_use_config_changes) or
+			any(x in digraph_nodes for x in
+			self._dynamic_config._needed_license_changes))
 
 	def need_config_reload(self):
 		return self._dynamic_config._need_config_reload
diff --git a/pym/_emerge/main.py b/pym/_emerge/main.py
index 76e963ac9..808496722 100644
--- a/pym/_emerge/main.py
+++ b/pym/_emerge/main.py
@@ -326,6 +326,12 @@ def parse_opts(tmpcmdline, silent=False):
 			"choices" : true_y_or_n
 		},
 
+		"--autounmask-backtrack": {
+			"help": ("continue backtracking when there are autounmask "
+				"configuration changes"),
+			"choices":("y", "n")
+		},
+
 		"--autounmask-continue": {
 			"help"    : "write autounmask changes and continue",
 			"choices" : true_y_or_n
diff --git a/pym/portage/tests/resolver/test_autounmask.py b/pym/portage/tests/resolver/test_autounmask.py
index 75fb36843..e2a7de028 100644
--- a/pym/portage/tests/resolver/test_autounmask.py
+++ b/pym/portage/tests/resolver/test_autounmask.py
@@ -81,20 +81,73 @@ class AutounmaskTestCase(TestCase):
 				#Make sure we restart if needed.
 				ResolverPlaygroundTestCase(
 					["dev-libs/A:1", "dev-libs/B"],
-					options={"--autounmask": True},
+					options={"--autounmask": True, "--autounmask-backtrack": "y"},
 					all_permutations=True,
 					success=False,
 					mergelist=["dev-libs/C-1", "dev-libs/B-1", "dev-libs/A-1"],
 					use_changes={ "dev-libs/B-1": {"foo": True} }),
+
+				# With --autounmask-backtrack=y:
+				#[ebuild  N     ] dev-libs/C-1
+				#[ebuild  N     ] dev-libs/B-1  USE="foo -bar"
+				#[ebuild  N     ] dev-libs/A-1
+				#
+				#The following USE changes are necessary to proceed:
+				# (see "package.use" in the portage(5) man page for more details)
+				## required by dev-libs/A-1::test_repo
+				## required by dev-libs/A:1 (argument)
+				#>=dev-libs/B-1 foo
+
+				# Without --autounmask-backtrack=y:
+				#[ebuild  N     ] dev-libs/B-1  USE="foo -bar"
+				#[ebuild  N     ] dev-libs/A-1
+				#
+				#The following USE changes are necessary to proceed:
+				# (see "package.use" in the portage(5) man page for more details)
+				## required by dev-libs/A-1::test_repo
+				## required by dev-libs/A:1 (argument)
+				#>=dev-libs/B-1 foo
+
 				ResolverPlaygroundTestCase(
 					["dev-libs/A:1", "dev-libs/A:2", "dev-libs/B"],
-					options={"--autounmask": True},
+					options={"--autounmask": True, "--autounmask-backtrack": "y"},
 					all_permutations=True,
 					success=False,
 					mergelist=["dev-libs/D-1", "dev-libs/C-1", "dev-libs/B-1", "dev-libs/A-1", "dev-libs/A-2"],
 					ignore_mergelist_order=True,
 					use_changes={ "dev-libs/B-1": {"foo": True, "bar": True} }),
 
+				# With --autounmask-backtrack=y:
+				#[ebuild  N     ] dev-libs/C-1
+				#[ebuild  N     ] dev-libs/D-1
+				#[ebuild  N     ] dev-libs/B-1  USE="bar foo"
+				#[ebuild  N     ] dev-libs/A-2
+				#[ebuild  N     ] dev-libs/A-1
+				#
+				#The following USE changes are necessary to proceed:
+				# (see "package.use" in the portage(5) man page for more details)
+				## required by dev-libs/A-2::test_repo
+				## required by dev-libs/A:2 (argument)
+				#>=dev-libs/B-1 bar foo
+
+				# Without --autounmask-backtrack=y:
+				#[ebuild  N     ] dev-libs/B-1  USE="bar foo"
+				#[ebuild  N     ] dev-libs/A-1
+				#[ebuild  N     ] dev-libs/A-2
+				#
+				#The following USE changes are necessary to proceed:
+				# (see "package.use" in the portage(5) man page for more details)
+				## required by dev-libs/A-1::test_repo
+				## required by dev-libs/A:1 (argument)
+				#>=dev-libs/B-1 foo bar
+
+				# NOTE: The --autounmask-backtrack=n behavior is acceptable, but
+				# it would be nicer if it added the dev-libs/C-1 and dev-libs/D-1
+				# deps to the depgraph without backtracking. It could add two
+				# instances of dev-libs/B-1 to the graph with different USE flags,
+				# and then use _solve_non_slot_operator_slot_conflicts to eliminate
+				# the redundant instance.
+
 				#Test keywording.
 				#The simple case.
 
diff --git a/pym/portage/tests/resolver/test_autounmask_use_breakage.py b/pym/portage/tests/resolver/test_autounmask_use_breakage.py
index 3654aa6a3..173941629 100644
--- a/pym/portage/tests/resolver/test_autounmask_use_breakage.py
+++ b/pym/portage/tests/resolver/test_autounmask_use_breakage.py
@@ -46,12 +46,52 @@ class AutounmaskUseBreakageTestCase(TestCase):
 			# due to autounmask USE breakage.
 			ResolverPlaygroundTestCase(
 				["app-misc/C", "app-misc/B", "app-misc/A"],
+				options={"--autounmask-backtrack": "y"},
 				all_permutations = True,
 				success = False,
 				ambiguous_slot_collision_solutions = True,
 				slot_collision_solutions = [None, []]
 			),
 
+			# With --autounmask-backtrack=y:
+			#emerge: there are no ebuilds built with USE flags to satisfy "app-misc/D[foo]".
+			#!!! One of the following packages is required to complete your request:
+			#- app-misc/D-0::test_repo (Change USE: +foo)
+			#(dependency required by "app-misc/B-0::test_repo" [ebuild])
+			#(dependency required by "app-misc/B" [argument])
+
+			# Without --autounmask-backtrack=y:
+			#[ebuild  N     ] app-misc/D-0  USE="foo"
+			#[ebuild  N     ] app-misc/D-1  USE="-bar"
+			#[ebuild  N     ] app-misc/C-0
+			#[ebuild  N     ] app-misc/B-0
+			#[ebuild  N     ] app-misc/A-0
+			#
+			#!!! Multiple package instances within a single package slot have been pulled
+			#!!! into the dependency graph, resulting in a slot conflict:
+			#
+			#app-misc/D:0
+			#
+			#  (app-misc/D-0:0/0::test_repo, ebuild scheduled for merge) pulled in by
+			#    app-misc/D[-foo] required by (app-misc/A-0:0/0::test_repo, ebuild scheduled for merge)
+			#               ^^^^
+			#    app-misc/D[foo] required by (app-misc/B-0:0/0::test_repo, ebuild scheduled for merge)
+			#               ^^^
+			#
+			#  (app-misc/D-1:0/0::test_repo, ebuild scheduled for merge) pulled in by
+			#    >=app-misc/D-1 required by (app-misc/C-0:0/0::test_repo, ebuild scheduled for merge)
+			#    ^^           ^
+			#
+			#The following USE changes are necessary to proceed:
+			# (see "package.use" in the portage(5) man page for more details)
+			## required by app-misc/B-0::test_repo
+			## required by app-misc/B (argument)
+			#=app-misc/D-0 foo
+
+			# NOTE: The --autounmask-backtrack=n output is preferable here,
+			# because it highlights the unsolvable dependency conflict.
+			# It would be better if it eliminated the autounmask suggestion,
+			# since that suggestion won't solve the conflict.
 		)
 
 		playground = ResolverPlayground(ebuilds=ebuilds, debug=False)
diff --git a/pym/portage/tests/resolver/test_slot_conflict_unsatisfied_deep_deps.py b/pym/portage/tests/resolver/test_slot_conflict_unsatisfied_deep_deps.py
index 13f7e67e3..846ba0e59 100644
--- a/pym/portage/tests/resolver/test_slot_conflict_unsatisfied_deep_deps.py
+++ b/pym/portage/tests/resolver/test_slot_conflict_unsatisfied_deep_deps.py
@@ -79,6 +79,7 @@ class SlotConflictUnsatisfiedDeepDepsTestCase(TestCase):
 				["@world"],
 				options={
 					"--autounmask": "y",
+					"--autounmask-backtrack": "y",
 					"--complete-graph": True,
 					"--selective": True,
 					"--deep": 1
@@ -89,11 +90,63 @@ class SlotConflictUnsatisfiedDeepDepsTestCase(TestCase):
 				unsatisfied_deps=["dev-libs/initially-unsatisfied"],
 				success=False),
 
+			# With --autounmask-backtrack=y:
+			#[ebuild  N    ~] dev-libs/A-2 
+			#[ebuild  N     ] dev-libs/C-1 
+			#[ebuild  N     ] dev-libs/D-1 
+			#[ebuild  N     ] dev-libs/B-1 
+			#
+			#The following keyword changes are necessary to proceed:
+			# (see "package.accept_keywords" in the portage(5) man page for more details)
+			## required by dev-libs/C-1::test_repo
+			## required by @selected
+			## required by @world (argument)
+			#=dev-libs/A-2 ~x86
+			#
+			#!!! Problems have been detected with your world file
+			#!!! Please run emaint --check world
+			#
+			#
+			#!!! Ebuilds for the following packages are either all
+			#!!! masked or don't exist:
+			#dev-libs/broken
+			#
+			#emerge: there are no ebuilds to satisfy "dev-libs/initially-unsatisfied".
+			#(dependency required by "dev-libs/broken-1::test_repo" [installed])
+			#(dependency required by "@selected" [set])
+			#(dependency required by "@world" [argument])
+
+			# Without --autounmask-backtrack=y:
+			#!!! Multiple package instances within a single package slot have been pulled
+			#!!! into the dependency graph, resulting in a slot conflict:
+			#
+			#dev-libs/A:0
+			#
+			#  (dev-libs/A-1:0/0::test_repo, ebuild scheduled for merge) pulled in by
+			#    (no parents that aren't satisfied by other packages in this slot)
+			#
+			#  (dev-libs/A-2:0/0::test_repo, ebuild scheduled for merge) pulled in by
+			#    >=dev-libs/A-2 required by (dev-libs/C-1:0/0::test_repo, ebuild scheduled for merge)
+			#    ^^           ^
+			#
+			#The following keyword changes are necessary to proceed:
+			# (see "package.accept_keywords" in the portage(5) man page for more details)
+			## required by dev-libs/C-1::test_repo
+			## required by @selected
+			## required by @world (argument)
+			#=dev-libs/A-2 ~x86
+			#
+			#emerge: there are no ebuilds to satisfy "dev-libs/initially-unsatisfied".
+			#(dependency required by "dev-libs/broken-1::test_repo" [installed])
+			#(dependency required by "@selected" [set])
+			#(dependency required by "@world" [argument])
+
 			# Test --deep = True
 			ResolverPlaygroundTestCase(
 				["@world"],
 				options={
 					"--autounmask": "y",
+					"--autounmask-backtrack": "y",
 					"--complete-graph": True,
 					"--selective": True,
 					"--deep": True
@@ -103,6 +156,14 @@ class SlotConflictUnsatisfiedDeepDepsTestCase(TestCase):
 				unstable_keywords=["dev-libs/A-2"],
 				unsatisfied_deps=["dev-libs/initially-unsatisfied"],
 				success=False),
+
+			# The effects of --autounmask-backtrack are the same as the previous test case.
+			# Both test cases can randomly succeed with --autounmask-backtrack=n, when
+			# "backtracking due to unsatisfied dep" randomly occurs before the autounmask
+			# unstable keyword change. It would be possible to eliminate backtracking here
+			# by recognizing that there are no alternatives to satisfy the dev-libs/broken
+			# atom in the world file. Then the test cases will consistently succeed with
+			# --autounmask-backtrack=n.
 		)
 
 		playground = ResolverPlayground(ebuilds=ebuilds, installed=installed,