Re: [gentoo-portage-dev] [PATCH 1/2] emerge: terminate backtracking early for autounmask changes (bug 615680)

[Brian Dolbec]

On Tue,  9 May 2017 20:52:34 -0700
Zac Medico <zmedico@g.o> wrote:

> 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
> ---
>  man/emerge.1                                       | 10 ++-
>  pym/_emerge/depgraph.py                            | 80
> ++++++++++++++++++----
> pym/_emerge/main.py                                |  6 ++
> pym/portage/tests/resolver/test_autounmask.py      | 57
> ++++++++++++++- .../tests/resolver/test_autounmask_use_breakage.py |
> 40 +++++++++++ .../test_slot_conflict_unsatisfied_deep_deps.py    |
> 61 +++++++++++++++++ 6 files changed, 237 insertions(+), 17
> deletions(-)
>
> diff --git a/man/emerge.1 b/man/emerge.1
> index f1a9d4f..94edc90 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 e1119af..53910dd 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 76e963a..8084967 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
> 75fb368..e2a7de0 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
> 3654aa6..1739416 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 13f7e67..846ba0e 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,


Looks good, thank you :)

-- 
Brian Dolbec <dolsen>