commit: 680276cc4d4faa653203366cbe3c896ac3883cf2 Author: Zac Medico <zmedico <AT> gentoo <DOT> org> AuthorDate: Wed Dec 25 08:37:18 2019 +0000 Commit: Zac Medico <zmedico <AT> gentoo <DOT> org> CommitDate: Thu Dec 26 22:56:39 2019 +0000 URL: https://gitweb.gentoo.org/proj/portage.git/commit/?id=680276cc
_serialize_tasks: limit scope of dropped circular dependencies Ensure that all members of a buildtime dependency cycle are merged as a group, such that packages which depend on one or more members of the group will only be merged *after* the entire group has been merged. This extends runtime cycle handling to also handle buildtime cycles in cases where the buildtime dependencies happen to be satisfied by installed packages. In situations when this is necessary, it is desirable to rely on the old installed instances of these packages as little as possible, since they might have been broken by the upgrade of a package that is a member of the dependency cycle. Upgrading members of the cycle as a group effectively minimizes reliance on the old installed package instances, avoiding some cases of bug 199856. For example, it should avoid bug 703676, where libspectre reportedly failed to build against an old installed instance of ghostscript-gpl. Bug: https://bugs.gentoo.org/199856 Bug: https://bugs.gentoo.org/689644 Bug: https://bugs.gentoo.org/690436 Bug: https://bugs.gentoo.org/703676 Signed-off-by: Zac Medico <zmedico <AT> gentoo.org> lib/_emerge/depgraph.py | 94 +++++++++++++++----------- lib/portage/tests/resolver/test_merge_order.py | 25 ++++++- 2 files changed, 78 insertions(+), 41 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 diff --git a/lib/portage/tests/resolver/test_merge_order.py b/lib/portage/tests/resolver/test_merge_order.py index 74e826661..11752d71e 100644 --- a/lib/portage/tests/resolver/test_merge_order.py +++ b/lib/portage/tests/resolver/test_merge_order.py @@ -81,6 +81,13 @@ class MergeOrderTestCase(TestCase): "DEPEND": "app-misc/circ-satisfied-a", "RDEPEND": "app-misc/circ-satisfied-a", }, + "app-misc/circ-direct-a-1": { + "RDEPEND": "app-misc/circ-direct-b", + }, + "app-misc/circ-direct-b-1": { + "RDEPEND": "app-misc/circ-direct-a", + "DEPEND": "app-misc/circ-direct-a", + }, "app-misc/circ-smallest-a-1": { "RDEPEND": "app-misc/circ-smallest-b", }, @@ -220,6 +227,13 @@ class MergeOrderTestCase(TestCase): } installed = { + "app-misc/circ-direct-a-1": { + "RDEPEND": "app-misc/circ-direct-b", + }, + "app-misc/circ-direct-b-1": { + "RDEPEND": "app-misc/circ-direct-a", + "DEPEND": "app-misc/circ-direct-a", + }, "app-misc/circ-buildtime-a-0": {}, "app-misc/circ-satisfied-a-0": { "RDEPEND": "app-misc/circ-satisfied-b", @@ -295,6 +309,12 @@ class MergeOrderTestCase(TestCase): } test_cases = ( + ResolverPlaygroundTestCase( + ["app-misc/circ-direct-a", "app-misc/circ-direct-b"], + success = True, + all_permutations = True, + mergelist = ["app-misc/circ-direct-a-1", "app-misc/circ-direct-b-1"], + ), ResolverPlaygroundTestCase( ["app-misc/some-app-a"], success = True, @@ -321,9 +341,8 @@ class MergeOrderTestCase(TestCase): ambiguous_merge_order = True, # The following merge order assertion reflects optimal order for # a circular relationship which is DEPEND in one direction and - # RDEPEND in the other. The assertion currently fails, and the - # patch for bug 690436 will fix it. - #merge_order_assertions = (("app-misc/circ-buildtime-a-1", "app-misc/circ-buildtime-c-1"),), + # RDEPEND in the other. + merge_order_assertions = (("app-misc/circ-buildtime-a-1", "app-misc/circ-buildtime-c-1"),), mergelist = [("app-misc/circ-buildtime-b-1", "app-misc/circ-buildtime-c-1", "app-misc/circ-buildtime-a-1"), "app-misc/some-app-c-1"]), # Test optimal merge order for a circular dep that is # RDEPEND in one direction and PDEPEND in the other.
