Bug #285767 - Add support to to identify and eliminate redundant package
selections when multiple atoms happen to specify a version range.
svn path=/main/trunk/; revision=14432
diff --git a/pym/_emerge/Dependency.py b/pym/_emerge/Dependency.py
index 6f52744..16cb41f 100644
--- a/pym/_emerge/Dependency.py
+++ b/pym/_emerge/Dependency.py
@@ -5,7 +5,7 @@
from _emerge.DepPriority import DepPriority
from _emerge.SlotObject import SlotObject
class Dependency(SlotObject):
- __slots__ = ("atom", "blocker", "depth",
+ __slots__ = ("atom", "blocker", "child", "depth",
"parent", "onlydeps", "priority", "root")
def __init__(self, **kwargs):
SlotObject.__init__(self, **kwargs)
diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index 743dcad..d67eb34 100644
--- a/pym/_emerge/depgraph.py
+++ b/pym/_emerge/depgraph.py
@@ -687,8 +687,19 @@
root=dep.parent.root)
self._dynamic_config._blocker_parents.add(blocker, dep.parent)
return 1
- dep_pkg, existing_node = self._select_package(dep.root, dep.atom,
- onlydeps=dep.onlydeps)
+
+ if dep.child is None:
+ dep_pkg, existing_node = self._select_package(dep.root, dep.atom,
+ onlydeps=dep.onlydeps)
+ else:
+ # The caller has selected a specific package
+ # via self._minimize_packages().
+ dep_pkg = dep.child
+ existing_node = self._dynamic_config._slot_pkg_map[
+ dep.root].get(dep_pkg.slot_atom)
+ if existing_node is not dep_pkg:
+ existing_node = None
+
if not dep_pkg:
if dep.priority.optional:
# This could be an unecessary build-time dep
@@ -1151,16 +1162,18 @@
if debug:
print("Candidates:", selected_atoms)
- vardb = self._frozen_config.roots[dep_root].trees["vartree"].dbapi
+ root_config = self._frozen_config.roots[dep_root]
+ vardb = root_config.trees["vartree"].dbapi
- for atom in selected_atoms[pkg]:
+ for atom, child in self._minimize_children(
+ pkg, dep_priority, root_config, selected_atoms[pkg]):
mypriority = dep_priority.copy()
if not atom.blocker and vardb.match(atom):
mypriority.satisfied = True
if not self._add_dep(Dependency(atom=atom,
- blocker=atom.blocker, depth=depth, parent=pkg,
+ blocker=atom.blocker, child=child, depth=depth, parent=pkg,
priority=mypriority, root=dep_root),
allow_unsatisfied=allow_unsatisfied):
return 0
@@ -1184,14 +1197,15 @@
root=dep_root)):
return 0
- for atom in atoms:
+ for atom, child in self._minimize_children(
+ pkg, self._priority(runtime=True), root_config, atoms):
# This is a GLEP 37 virtual, so its deps are all runtime.
mypriority = self._priority(runtime=True)
if not atom.blocker and vardb.match(atom):
mypriority.satisfied = True
if not self._add_dep(Dependency(atom=atom,
- blocker=atom.blocker, depth=virt_pkg.depth,
+ blocker=atom.blocker, child=child, depth=virt_pkg.depth,
parent=virt_pkg, priority=mypriority, root=dep_root),
allow_unsatisfied=allow_unsatisfied):
return 0
@@ -1201,6 +1215,73 @@
return 1
+ def _minimize_children(self, parent, priority, root_config, atoms):
+ """
+ Selects packages to satisfy the given atoms, and minimizes the
+ number of selected packages. This serves to identify and eliminate
+ redundant package selections when multiple atoms happen to specify
+ a version range.
+ """
+
+ atom_pkg_map = {}
+
+ for atom in atoms:
+ if atom.blocker:
+ yield (atom, None)
+ continue
+ dep_pkg, existing_node = self._select_package(
+ root_config.root, atom)
+ if dep_pkg is None:
+ yield (atom, None)
+ continue
+ atom_pkg_map[atom] = dep_pkg
+
+ if len(atom_pkg_map) < 2:
+ for item in atom_pkg_map.items():
+ yield item
+ return
+
+ cp_pkg_map = {}
+ pkg_atom_map = {}
+ for atom, pkg in atom_pkg_map.items():
+ pkg_atom_map.setdefault(pkg, set()).add(atom)
+ cp_pkg_map.setdefault(pkg.cp, set()).add(pkg)
+
+ for cp, pkgs in cp_pkg_map.items():
+ if len(pkgs) < 2:
+ for pkg in pkgs:
+ for atom in pkg_atom_map[pkg]:
+ yield (atom, pkg)
+ continue
+
+ # Use a digraph to identify and eliminate any
+ # redundant package selections.
+ atom_pkg_graph = digraph()
+ cp_atoms = set()
+ for pkg1 in pkgs:
+ for atom in pkg_atom_map[pkg1]:
+ cp_atoms.add(atom)
+ atom_pkg_graph.add(pkg1, atom)
+ atom_set = InternalPackageSet(initial_atoms=(atom,))
+ for pkg2 in pkgs:
+ if pkg2 is pkg1:
+ continue
+ if atom_set.findAtomForPackage(pkg2):
+ atom_pkg_graph.add(pkg2, atom)
+
+ for pkg in pkgs:
+ eliminate_pkg = True
+ for atom in atom_pkg_graph.parent_nodes(pkg):
+ if len(atom_pkg_graph.child_nodes(atom)) < 2:
+ eliminate_pkg = False
+ break
+ if eliminate_pkg:
+ atom_pkg_graph.remove(pkg)
+
+ for atom in cp_atoms:
+ child_pkgs = atom_pkg_graph.child_nodes(atom)
+ yield (atom, child_pkgs[0])
+
def _queue_disjunctive_deps(self, pkg, dep_root, dep_priority, dep_struct):
"""
Queue disjunctive (virtual and ||) deps in self._dynamic_config._dep_disjunctive_stack.
