aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat (limited to 'lib/_emerge')
-rw-r--r--lib/_emerge/depgraph.py94
1 files changed, 56 insertions, 38 deletions
diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py
index 0ee50d5de..bf8882774 100644
--- a/lib/_emerge/depgraph.py
+++ b/lib/_emerge/depgraph.py
@@ -7640,21 +7640,6 @@ class depgraph(object):
break
removed_nodes.clear()
self._merge_order_bias(mygraph)
- def cmp_circular_bias(n1, n2):
- """
- RDEPEND is stronger than PDEPEND and this function
- measures such a strength bias within a circular
- dependency relationship.
- """
- n1_n2_medium = n2 in mygraph.child_nodes(n1,
- ignore_priority=priority_range.ignore_medium_soft)
- n2_n1_medium = n1 in mygraph.child_nodes(n2,
- ignore_priority=priority_range.ignore_medium_soft)
- if n1_n2_medium == n2_n1_medium:
- return 0
- elif n1_n2_medium:
- return 1
- return -1
myblocker_uninstalls = self._dynamic_config._blocker_uninstalls.copy()
retlist=[]
# Contains uninstall tasks that have been scheduled to
@@ -7815,7 +7800,8 @@ class depgraph(object):
self._spinner_update()
selected_nodes = None
ignore_priority = None
- if drop_satisfied or (prefer_asap and asap_nodes):
+ cycle_digraph = None
+ if prefer_asap and asap_nodes:
priority_range = DepPrioritySatisfiedRange
else:
priority_range = DepPriorityNormalRange
@@ -7897,11 +7883,12 @@ class depgraph(object):
break
if not selected_nodes:
- nodes = get_nodes(ignore_priority=priority_range.ignore_medium)
- if nodes:
- mergeable_nodes = set(nodes)
+
+ def find_smallest_cycle(mergeable_nodes, priority_ranges):
if prefer_asap and asap_nodes:
nodes = asap_nodes
+ else:
+ nodes = mergeable_nodes
# When gathering the nodes belonging to a runtime cycle,
# we want to minimize the number of nodes gathered, since
# this tends to produce a more optimal merge order.
@@ -7912,21 +7899,44 @@ class depgraph(object):
# that depend on them. Therefore, we search for the
# smallest cycle in order to try and identify and prefer
# these smaller independent cycles.
- ignore_priority = priority_range.ignore_medium_soft
smallest_cycle = None
+ ignore_priority = None
for node in nodes:
if not mygraph.parent_nodes(node):
continue
- selected_nodes = set()
- if gather_deps(ignore_priority,
- mergeable_nodes, selected_nodes, node):
- if smallest_cycle is None or \
- len(selected_nodes) < len(smallest_cycle):
- smallest_cycle = selected_nodes
+ for local_priority_range in priority_ranges:
+ selected_nodes = set()
+ if gather_deps(local_priority_range.ignore_medium_soft,
+ 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
+
+ return smallest_cycle, ignore_priority
- selected_nodes = smallest_cycle
+ priority_ranges = []
+ if priority_range is not DepPriorityNormalRange:
+ priority_ranges.append(DepPriorityNormalRange)
+ priority_ranges.append(priority_range)
+ if drop_satisfied and priority_range is not DepPrioritySatisfiedRange:
+ priority_ranges.append(DepPrioritySatisfiedRange)
- if selected_nodes is not None:
+ 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)
+ if selected_nodes:
+ break
+
+ if not selected_nodes:
+ if prefer_asap and asap_nodes:
+ # We failed to find any asap nodes to merge, so ignore
+ # them for the next iteration.
+ prefer_asap = False
+ continue
+ else:
cycle_digraph = mygraph.copy()
cycle_digraph.difference_update([x for x in
cycle_digraph if x not in selected_nodes])
@@ -7953,12 +7963,6 @@ class depgraph(object):
writemsg("runtime cycle leaf: %s\n\n" %
(selected_nodes[0],), noiselevel=-1)
- if prefer_asap and asap_nodes and not selected_nodes:
- # We failed to find any asap nodes to merge, so ignore
- # them for the next iteration.
- prefer_asap = False
- continue
-
if selected_nodes and ignore_priority is not None:
# Try to merge ignored medium_soft deps as soon as possible
# if they're not satisfied by installed packages.
@@ -7980,10 +7984,24 @@ class depgraph(object):
# Merge PDEPEND asap for bug #180045.
asap_nodes.append(child)
- if selected_nodes and len(selected_nodes) > 1:
- if not isinstance(selected_nodes, list):
- selected_nodes = list(selected_nodes)
- selected_nodes.sort(key=cmp_sort_key(cmp_circular_bias))
+ if selected_nodes and len(selected_nodes) > 1 and cycle_digraph is not None:
+ # Sort nodes to account for direct circular relationships. Relevant
+ # priorities here are: runtime < buildtime < buildtime slot operator
+ ignore_priorities = list(filter(None, chain(
+ DepPriorityNormalRange.ignore_priority,
+ DepPrioritySatisfiedRange.ignore_priority,
+ )))
+ selected_nodes = []
+ while cycle_digraph:
+ for ignore_priority in ignore_priorities:
+ leaves = cycle_digraph.leaf_nodes(ignore_priority=ignore_priority)
+ if leaves:
+ cycle_digraph.difference_update(leaves)
+ selected_nodes.extend(leaves)
+ break
+ else:
+ selected_nodes.extend(cycle_digraph)
+ break
if not selected_nodes and myblocker_uninstalls:
# An Uninstall task needs to be executed in order to