aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorZac Medico <zmedico@gentoo.org>2020-11-15 21:55:54 -0800
committerZac Medico <zmedico@gentoo.org>2020-11-21 19:19:29 -0800
commit5095c2023595a75e2848f1ad3dbe25b5fb451a44 (patch)
treebc2e7d105582ea0274a1d57f4e3dba9013e883b9 /lib/_emerge
parentemerge: Disable profile deprecation warning inheritance (bug 753497) (diff)
downloadportage-5095c2023595a75e2848f1ad3dbe25b5fb451a44.tar.gz
portage-5095c2023595a75e2848f1ad3dbe25b5fb451a44.tar.bz2
portage-5095c2023595a75e2848f1ad3dbe25b5fb451a44.zip
find_smallest_cycle: enhance search prioritization
Enhance the find_smallest_cycle function to prioritize its search so that it will minimize the use of installed packages to break cycles. When installed packages must be used to break cycles, it will now prefer to do this for runtime dependencies over buildtime dependencies, since it's preferable to build against latest versions of buildtime dependencies whenever possible. This should solve some cases of bug 199856 which have been triggered by unsafe reliance on installed packages to break cycles. The included unit test case demonstrates correct merge order for a dependency calculation involving 6 independent cycles. This test case fails with the master branch, due to a buildtime dependency cycle of 3 packages being merged earlier than cycles of 2 packages. We can generalize this to say that the master branch may use an installed package to break an arbitrarily sized cycle in a somewhat random location, even though that cycle may be composed of smaller independent cycles which would be safer to break individually. Bug: https://bugs.gentoo.org/754903 Signed-off-by: Zac Medico <zmedico@gentoo.org>
Diffstat (limited to 'lib/_emerge')
-rw-r--r--lib/_emerge/DepPriorityNormalRange.py2
-rw-r--r--lib/_emerge/DepPrioritySatisfiedRange.py53
-rw-r--r--lib/_emerge/depgraph.py43
3 files changed, 60 insertions, 38 deletions
diff --git a/lib/_emerge/DepPriorityNormalRange.py b/lib/_emerge/DepPriorityNormalRange.py
index 5f3f3da70..10f205a3b 100644
--- a/lib/_emerge/DepPriorityNormalRange.py
+++ b/lib/_emerge/DepPriorityNormalRange.py
@@ -14,6 +14,7 @@ class DepPriorityNormalRange:
"""
MEDIUM = 3
MEDIUM_SOFT = 2
+ MEDIUM_POST = 2
SOFT = 1
NONE = 0
@@ -37,6 +38,7 @@ class DepPriorityNormalRange:
ignore_medium = _ignore_runtime
ignore_medium_soft = _ignore_runtime_post
+ ignore_medium_post = _ignore_runtime_post
ignore_soft = _ignore_optional
DepPriorityNormalRange.ignore_priority = (
diff --git a/lib/_emerge/DepPrioritySatisfiedRange.py b/lib/_emerge/DepPrioritySatisfiedRange.py
index e056e676f..fb0d7db4e 100644
--- a/lib/_emerge/DepPrioritySatisfiedRange.py
+++ b/lib/_emerge/DepPrioritySatisfiedRange.py
@@ -8,17 +8,18 @@ class DepPrioritySatisfiedRange:
not satisfied and buildtime HARD
not satisfied and runtime 7 MEDIUM
- not satisfied and runtime_post 6 MEDIUM_SOFT
- satisfied and buildtime_slot_op 5 SOFT
- satisfied and buildtime 4 SOFT
- satisfied and runtime 3 SOFT
- satisfied and runtime_post 2 SOFT
+ satisfied and buildtime_slot_op 6 MEDIUM_SOFT
+ satisfied and buildtime 5 MEDIUM_SOFT
+ satisfied and runtime 4 MEDIUM_SOFT
+ runtime_post 3 MEDIUM_POST
+ satisfied and runtime_post 2 MEDIUM_POST
optional 1 SOFT
(none of the above) 0 NONE
"""
MEDIUM = 7
MEDIUM_SOFT = 6
- SOFT = 5
+ MEDIUM_POST = 3
+ SOFT = 1
NONE = 0
@classmethod
@@ -35,42 +36,51 @@ class DepPrioritySatisfiedRange:
return True
if not priority.satisfied:
return False
+ if priority.buildtime or priority.runtime:
+ return False
return bool(priority.runtime_post)
@classmethod
- def _ignore_satisfied_runtime(cls, priority):
+ def _ignore_runtime_post(cls, priority):
if priority.__class__ is not DepPriority:
return False
if priority.optional:
return True
- if not priority.satisfied:
+ if priority.buildtime or priority.runtime:
return False
- return not priority.buildtime
+ return bool(priority.runtime_post)
@classmethod
- def _ignore_satisfied_buildtime(cls, priority):
+ def _ignore_satisfied_runtime(cls, priority):
if priority.__class__ is not DepPriority:
return False
if priority.optional:
return True
- if priority.buildtime_slot_op:
+ if priority.buildtime:
return False
+ if not priority.runtime:
+ return True
return bool(priority.satisfied)
@classmethod
- def _ignore_satisfied_buildtime_slot_op(cls, priority):
+ def _ignore_satisfied_buildtime(cls, priority):
if priority.__class__ is not DepPriority:
return False
- return bool(priority.optional or \
- priority.satisfied)
+ if priority.optional:
+ return True
+ if priority.buildtime_slot_op:
+ return False
+ return bool(priority.satisfied)
@classmethod
- def _ignore_runtime_post(cls, priority):
+ def _ignore_satisfied_buildtime_slot_op(cls, priority):
if priority.__class__ is not DepPriority:
return False
- return bool(priority.optional or \
- priority.satisfied or \
- priority.runtime_post)
+ if priority.optional:
+ return True
+ if priority.satisfied:
+ return True
+ return not priority.buildtime and not priority.runtime
@classmethod
def _ignore_runtime(cls, priority):
@@ -81,17 +91,18 @@ class DepPrioritySatisfiedRange:
not priority.buildtime)
ignore_medium = _ignore_runtime
- ignore_medium_soft = _ignore_runtime_post
- ignore_soft = _ignore_satisfied_buildtime
+ ignore_medium_soft = _ignore_satisfied_buildtime_slot_op
+ ignore_medium_post = _ignore_runtime_post
+ ignore_soft = _ignore_optional
DepPrioritySatisfiedRange.ignore_priority = (
None,
DepPrioritySatisfiedRange._ignore_optional,
DepPrioritySatisfiedRange._ignore_satisfied_runtime_post,
+ DepPrioritySatisfiedRange._ignore_runtime_post,
DepPrioritySatisfiedRange._ignore_satisfied_runtime,
DepPrioritySatisfiedRange._ignore_satisfied_buildtime,
DepPrioritySatisfiedRange._ignore_satisfied_buildtime_slot_op,
- DepPrioritySatisfiedRange._ignore_runtime_post,
DepPrioritySatisfiedRange._ignore_runtime
)
diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py
index a994caea7..d10474ab3 100644
--- a/lib/_emerge/depgraph.py
+++ b/lib/_emerge/depgraph.py
@@ -7905,7 +7905,7 @@ class depgraph:
if check_asap_parent:
for node in nodes:
parents = mygraph.parent_nodes(node,
- ignore_priority=DepPrioritySatisfiedRange.ignore_soft)
+ ignore_priority=DepPrioritySatisfiedRange.ignore_medium_soft)
if any(x in asap_nodes for x in parents):
selected_nodes = [node]
break
@@ -7921,7 +7921,7 @@ class depgraph:
if not selected_nodes:
- def find_smallest_cycle(mergeable_nodes, priority_ranges):
+ def find_smallest_cycle(mergeable_nodes, local_priority_range):
if prefer_asap and asap_nodes:
nodes = asap_nodes
else:
@@ -7938,18 +7938,27 @@ class depgraph:
# these smaller independent cycles.
smallest_cycle = None
ignore_priority = None
- for node in nodes:
- if not mygraph.parent_nodes(node):
- continue
- for local_priority_range in priority_ranges:
+
+ # Sort nodes for deterministic results.
+ nodes = sorted(nodes)
+ for priority in (local_priority_range.ignore_priority[i] for i in range(
+ local_priority_range.MEDIUM_POST,
+ local_priority_range.MEDIUM_SOFT + 1)):
+ for node in nodes:
+ if not mygraph.parent_nodes(node):
+ continue
selected_nodes = set()
- if gather_deps(local_priority_range.ignore_medium_soft,
+ if gather_deps(priority,
mergeable_nodes, selected_nodes, node):
if smallest_cycle is None or \
len(selected_nodes) < len(smallest_cycle):
smallest_cycle = selected_nodes
- ignore_priority = local_priority_range.ignore_medium_soft
- break
+ ignore_priority = priority
+
+ # Exit this loop with the lowest possible priority, which
+ # minimizes the use of installed packages to break cycles.
+ if smallest_cycle is not None:
+ break
return smallest_cycle, ignore_priority
@@ -7963,7 +7972,7 @@ class depgraph:
for local_priority_range in priority_ranges:
mergeable_nodes = set(get_nodes(ignore_priority=local_priority_range.ignore_medium))
if mergeable_nodes:
- selected_nodes, ignore_priority = find_smallest_cycle(mergeable_nodes, priority_ranges)
+ selected_nodes, ignore_priority = find_smallest_cycle(mergeable_nodes, local_priority_range)
if selected_nodes:
break
@@ -8001,19 +8010,19 @@ class depgraph:
(selected_nodes[0],), noiselevel=-1)
if selected_nodes and ignore_priority is not None:
- # Try to merge ignored medium_soft deps as soon as possible
+ # Try to merge ignored medium_post deps as soon as possible
# if they're not satisfied by installed packages.
for node in selected_nodes:
children = set(mygraph.child_nodes(node))
soft = children.difference(
mygraph.child_nodes(node,
- ignore_priority=DepPrioritySatisfiedRange.ignore_soft))
- medium_soft = children.difference(
- mygraph.child_nodes(node,
ignore_priority = \
- DepPrioritySatisfiedRange.ignore_medium_soft))
- medium_soft -= soft
- for child in medium_soft:
+ DepPrioritySatisfiedRange.ignore_soft))
+ medium_post = children.difference(
+ mygraph.child_nodes(node,
+ ignore_priority=DepPrioritySatisfiedRange.ignore_medium_post))
+ medium_post -= soft
+ for child in medium_post:
if child in selected_nodes:
continue
if child in asap_nodes: