[gentoo-portage-dev] [PATCH] circular_dependency_handler: limit USE combination search (bug 555698)

[gentoo-portage-dev] [PATCH] circular_dependency_handler: limit USE combination search (bug 555698)

[Zac Medico]

Limit the number of USE combinations search to 1024, in order to
avoid consuming unreasonable abouts of time. First, discard
irrelevent flags that are not enabled. Since extract_affecting_use
doesn't distinguish between positive and negative effects (flag? vs.
!flag?), assume a positive relationship. If there are still too many
combinations, then don't bother to explore any of them.

X-Gentoo-Bug: 555698
X-Gentoo-Bug-url: https://bugs.gentoo.org/show_bug.cgi?id=555698
---
 pym/_emerge/resolver/circular_dependency.py | 21 +++++++++++++++++++--
 1 file changed, 19 insertions(+), 2 deletions(-)

diff --git a/pym/_emerge/resolver/circular_dependency.py b/pym/_emerge/resolver/circular_dependency.py
index b710671..5c11956 100644
--- a/pym/_emerge/resolver/circular_dependency.py
+++ b/pym/_emerge/resolver/circular_dependency.py
@@ -14,7 +14,9 @@ from _emerge.DepPrioritySatisfiedRange import DepPrioritySatisfiedRange
 from _emerge.Package import Package
 
 class circular_dependency_handler(object):
-	
+
+	MAX_AFFECTING_USE = 10
+
 	def __init__(self, depgraph, graph):
 		self.depgraph = depgraph
 		self.graph = graph
@@ -156,7 +158,7 @@ class circular_dependency_handler(object):
 				total_flags = set()
 				total_flags.update(affecting_use, required_use_flags)
 				total_flags.difference_update(untouchable_flags)
-				if len(total_flags) <= 10:
+				if len(total_flags) <= self.MAX_AFFECTING_USE:
 					affecting_use = total_flags
 
 			affecting_use = tuple(affecting_use)
@@ -164,6 +166,21 @@ class circular_dependency_handler(object):
 			if not affecting_use:
 				continue
 
+			if len(affecting_use) > self.MAX_AFFECTING_USE:
+				# Limit the number of combinations explored (bug #555698).
+				# First, discard irrelevent flags that are not enabled.
+				# Since extract_affecting_use doesn't distinguish between
+				# positive and negative effects (flag? vs. !flag?), assume
+				# a positive relationship.
+				current_use = self.depgraph._pkg_use_enabled(parent)
+				affecting_use = tuple(flag for flag in affecting_use
+					if flag in current_use)
+
+				if len(affecting_use) > self.MAX_AFFECTING_USE:
+					# There are too many USE combinations to explore in
+					# a reasonable amount of time.
+					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
-- 
2.3.6

Re: [gentoo-portage-dev] [PATCH] circular_dependency_handler: limit USE combination search (bug 555698)

[Brian Dolbec]

On Sun,  2 Aug 2015 23:21:36 -0700
Zac Medico <zmedico@gentoo.org> wrote:

> Limit the number of USE combinations search to 1024, in order to
> avoid consuming unreasonable abouts of time. First, discard

******          typo            ^^ amounts


> irrelevent flags that are not enabled. Since extract_affecting_use
> doesn't distinguish between positive and negative effects (flag? vs.
> !flag?), assume a positive relationship. If there are still too many
> combinations, then don't bother to explore any of them.
> 
> X-Gentoo-Bug: 555698
> X-Gentoo-Bug-url: https://bugs.gentoo.org/show_bug.cgi?id=555698
> ---
>  pym/_emerge/resolver/circular_dependency.py | 21
> +++++++++++++++++++-- 1 file changed, 19 insertions(+), 2 deletions(-)
> 
> diff --git a/pym/_emerge/resolver/circular_dependency.py
> b/pym/_emerge/resolver/circular_dependency.py index b710671..5c11956
> 100644 --- a/pym/_emerge/resolver/circular_dependency.py
> +++ b/pym/_emerge/resolver/circular_dependency.py
> @@ -14,7 +14,9 @@ from _emerge.DepPrioritySatisfiedRange import
> DepPrioritySatisfiedRange from _emerge.Package import Package
>  
>  class circular_dependency_handler(object):
> -	
> +
> +	MAX_AFFECTING_USE = 10
> +


*********  in the commit message you talk about the limit being set to
to 1024
           but here it is set 10?

           Clarify please.



>  	def __init__(self, depgraph, graph):
>  		self.depgraph = depgraph
>  		self.graph = graph
> @@ -156,7 +158,7 @@ class circular_dependency_handler(object):
>  				total_flags = set()
>  				total_flags.update(affecting_use,
> required_use_flags) total_flags.difference_update(untouchable_flags)
> -				if len(total_flags) <= 10:
> +				if len(total_flags) <=
> self.MAX_AFFECTING_USE: affecting_use = total_flags
>  
>  			affecting_use = tuple(affecting_use)
> @@ -164,6 +166,21 @@ class circular_dependency_handler(object):
>  			if not affecting_use:
>  				continue
>  


=================================================


> +			if len(affecting_use) >
> self.MAX_AFFECTING_USE:
> +				# Limit the number of combinations
> explored (bug #555698).
> +				# First, discard irrelevent flags
> that are not enabled.
> +				# Since extract_affecting_use
> doesn't distinguish between
> +				# positive and negative effects
> (flag? vs. !flag?), assume
> +				# a positive relationship.
> +				current_use =
> self.depgraph._pkg_use_enabled(parent)
> +				affecting_use = tuple(flag for flag
> in affecting_use
> +					if flag in current_use)
> +
> +				if len(affecting_use) >
> self.MAX_AFFECTING_USE:
> +					# There are too many USE
> combinations to explore in
> +					# a reasonable amount of
> time.
> +					continue
> +



Damn, that _find_suggestions() is already 150+ LOC, up to 9 indent
levels deep, before you add this :/

Is there a way you can do this in a separate test/function?  At least
it wouldn't be adding directly to something that already could use a
little refactoring.  /me cringes at what repoman is... 

>  			#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



-- 
Brian Dolbec <dolsen>

[gentoo-portage-dev] [PATCH] circular_dependency_handler: limit USE combination search (bug 555698)

[Zac Medico]

Limit the number of USE combinations searched to 1024 = 2 ** 10, where
10 is a constant named MAX_AFFECTING_USE, in order to avoid consuming
unreasonable amounts of time. First, discard irrelevent flags that are
not enabled. Since extract_affecting_use doesn't distinguish between
positive and negative effects (flag? vs.  combinations, then don't
bother to explore any of them.

X-Gentoo-Bug: 555698
X-Gentoo-Bug-url: https://bugs.gentoo.org/show_bug.cgi?id=555698
---
 pym/_emerge/resolver/circular_dependency.py | 21 +++++++++++++++++++--
 1 file changed, 19 insertions(+), 2 deletions(-)

diff --git a/pym/_emerge/resolver/circular_dependency.py b/pym/_emerge/resolver/circular_dependency.py
index b710671..5c11956 100644
--- a/pym/_emerge/resolver/circular_dependency.py
+++ b/pym/_emerge/resolver/circular_dependency.py
@@ -14,7 +14,9 @@ from _emerge.DepPrioritySatisfiedRange import DepPrioritySatisfiedRange
 from _emerge.Package import Package
 
 class circular_dependency_handler(object):
-	
+
+	MAX_AFFECTING_USE = 10
+
 	def __init__(self, depgraph, graph):
 		self.depgraph = depgraph
 		self.graph = graph
@@ -156,7 +158,7 @@ class circular_dependency_handler(object):
 				total_flags = set()
 				total_flags.update(affecting_use, required_use_flags)
 				total_flags.difference_update(untouchable_flags)
-				if len(total_flags) <= 10:
+				if len(total_flags) <= self.MAX_AFFECTING_USE:
 					affecting_use = total_flags
 
 			affecting_use = tuple(affecting_use)
@@ -164,6 +166,21 @@ class circular_dependency_handler(object):
 			if not affecting_use:
 				continue
 
+			if len(affecting_use) > self.MAX_AFFECTING_USE:
+				# Limit the number of combinations explored (bug #555698).
+				# First, discard irrelevent flags that are not enabled.
+				# Since extract_affecting_use doesn't distinguish between
+				# positive and negative effects (flag? vs. !flag?), assume
+				# a positive relationship.
+				current_use = self.depgraph._pkg_use_enabled(parent)
+				affecting_use = tuple(flag for flag in affecting_use
+					if flag in current_use)
+
+				if len(affecting_use) > self.MAX_AFFECTING_USE:
+					# There are too many USE combinations to explore in
+					# a reasonable amount of time.
+					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
-- 
2.3.6

Re: [gentoo-portage-dev] [PATCH] circular_dependency_handler: limit USE combination search (bug 555698)

[Brian Dolbec]

On Mon,  3 Aug 2015 10:45:24 -0700
Zac Medico <zmedico@gentoo.org> wrote:

> Limit the number of USE combinations searched to 1024 = 2 ** 10, where
> 10 is a constant named MAX_AFFECTING_USE, in order to avoid consuming
> unreasonable amounts of time. First, discard irrelevent flags that are
> not enabled. Since extract_affecting_use doesn't distinguish between
> positive and negative effects (flag? vs.  combinations, then don't
> bother to explore any of them.
> 
> X-Gentoo-Bug: 555698
> X-Gentoo-Bug-url: https://bugs.gentoo.org/show_bug.cgi?id=555698
> ---
>

That's better, thanks

looks good

-- 
Brian Dolbec <dolsen>