* [gentoo-portage-dev] [PATCH 01/10] Add resolver/package_tracker
2014-01-29 15:33 [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking Sebastian Luther
@ 2014-01-29 15:33 ` Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 02/10] Replace _slot_pkg_map and some tree dbapiS with _package_tracker Sebastian Luther
` (9 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Sebastian Luther @ 2014-01-29 15:33 UTC (permalink / raw
To: gentoo-portage-dev
---
pym/_emerge/resolver/package_tracker.py | 310 ++++++++++++++++++++++++++++++++
1 file changed, 310 insertions(+)
create mode 100644 pym/_emerge/resolver/package_tracker.py
diff --git a/pym/_emerge/resolver/package_tracker.py b/pym/_emerge/resolver/package_tracker.py
new file mode 100644
index 0000000..4aee4ea
--- /dev/null
+++ b/pym/_emerge/resolver/package_tracker.py
@@ -0,0 +1,310 @@
+# Copyright 2014 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from __future__ import print_function
+
+import collections
+
+import portage
+portage.proxy.lazyimport.lazyimport(globals(),
+ 'portage:OrderedDict',
+ 'portage.dep:Atom,match_from_list',
+ 'portage.util:cmp_sort_key',
+ 'portage.versions:vercmp',
+)
+
+_PackageConflict = collections.namedtuple("_PackageConflict", ["root", "pkgs", "atom", "description"])
+
+class PackageConflict(_PackageConflict):
+ """
+ Class to track the reason for a conflict and the conflicting packages.
+ """
+ def __iter__(self):
+ return iter(self.pkgs)
+
+ def __contains__(self, pkg):
+ return pkg in self.pkgs
+
+ def __len__(self):
+ return len(self.pkgs)
+
+
+class PackageTracker(object):
+ """
+ This class tracks packages which are currently
+ installed and packages which have been pulled into
+ the dependency graph.
+
+ It automatically tracks conflicts between packages.
+
+ Possible conflicts:
+ 1) Packages that share the same SLOT.
+ 2) Packages with the same cpv.
+ Not yet implemented:
+ 3) Packages that block each other.
+ """
+
+ def __init__(self):
+ # Mapping from package keys to set of packages.
+ self._cp_pkg_map = collections.defaultdict(list)
+ self._cp_vdb_pkg_map = collections.defaultdict(list)
+ # List of package keys that may contain conflicts.
+ # The insetation order must be preserved.
+ self._multi_pkgs = []
+
+ # Cache for result of conflicts().
+ self._conflicts_cache = None
+
+ # Records for each pulled package which installed package
+ # are replaced.
+ self._replacing = collections.defaultdict(list)
+ # Records which pulled packages replace this package.
+ self._replaced_by = collections.defaultdict(list)
+
+ self._match_cache = collections.defaultdict(dict)
+
+ def add_pkg(self, pkg):
+ """
+ Add a new package to the tracker. Records conflicts as necessary.
+ """
+ cp_key = pkg.root, pkg.cp
+
+ try:
+ if any(other is pkg for other in self._cp_pkg_map[cp_key]):
+ return
+ except KeyError:
+ self._cp_pkg_map[cp_key] = [pkg]
+ else:
+ self._cp_pkg_map[cp_key].append(pkg)
+ if len(self._cp_pkg_map[cp_key]) == 2:
+ self._multi_pkgs.append(cp_key)
+ self._conflicts_cache = None
+
+ self._replacing[pkg] = []
+ for installed in self._cp_vdb_pkg_map[cp_key]:
+ if installed.slot_atom == pkg.slot_atom or \
+ installed.cpv == pkg.cpv:
+ self._replacing[pkg].append(installed)
+ self._replaced_by[installed].append(pkg)
+
+ self._match_cache.pop((pkg.root, pkg.cp))
+
+ def add_installed_pkg(self, installed):
+ """
+ Add an installed package during vdb load. These packages
+ are not returned by matched_pull as long as add_pkg hasn't
+ been called with them. They are only returned by match_final.
+ """
+ cp_key = installed.root, installed.cp
+ try:
+ if any(other is installed for other in self._cp_vdb_pkg_map[cp_key]):
+ return
+ except KeyError:
+ self._cp_vdb_pkg_map[cp_key] = [installed]
+ else:
+ self._cp_vdb_pkg_map[cp_key].append(installed)
+
+ for pkg in self._cp_pkg_map[cp_key]:
+ if installed.slot_atom == pkg.slot_atom or \
+ installed.cpv == pkg.cpv:
+ self._replacing[pkg].append(installed)
+ self._replaced_by[installed].append(pkg)
+
+ def remove_pkg(self, pkg):
+ """
+ Removes the package from the tracker.
+ Raises KeyError if it isn't present.
+ """
+ cp_key = pkg.root, pkg.cp
+ try:
+ self._cp_pkg_map[cp_key].remove(pkg)
+ except ValueError:
+ raise KeyError
+
+ if self._cp_pkg_map[cp_key]:
+ self._conflicts_cache = None
+
+ if not self._cp_pkg_map[cp_key]:
+ del self._cp_pkg_map[cp_key]
+ elif len(self._cp_pkg_map[cp_key]) == 1:
+ self._multi_pkgs = [other_cp_key for other_cp_key in self._multi_pkgs \
+ if other_cp_key != cp_key]
+
+ for installed in self._replacing[pkg]:
+ self._replaced_by[installed].remove(pkg)
+ if not self._replaced_by[installed]:
+ del self._replaced_by[installed]
+ del self._replacing[pkg]
+
+ self._match_cache.pop((pkg.root, pkg.cp))
+
+ def discard_pkg(self, pkg):
+ """
+ Removes the package from the tracker.
+ Does not raises KeyError if it is not present.
+ """
+ try:
+ self.remove_pkg(pkg)
+ except KeyError:
+ pass
+
+ def match(self, root, atom, installed=True):
+ """
+ Iterates over the packages matching 'atom'.
+ If 'installed' is True, installed non-replaced
+ packages may also be returned.
+ """
+ cache_key = (root, atom, installed)
+ try:
+ return iter(self._match_cache[(root, atom.cp)][cache_key])
+ except KeyError:
+ pass
+
+ cp_key = root, atom.cp
+ try:
+ candidates = self._cp_pkg_map[cp_key][:]
+ except KeyError:
+ candidates = []
+
+ if installed:
+ try:
+ for installed in self._cp_vdb_pkg_map[cp_key]:
+ if installed not in self._replaced_by:
+ candidates.append(installed)
+ except KeyError:
+ pass
+
+ ret = match_from_list(atom, candidates)
+ ret.sort(key=cmp_sort_key(lambda x, y: vercmp(x.version, y.version)))
+ self._match_cache[(root, atom.cp)][cache_key] = ret
+
+ return iter(ret)
+
+ def conflicts(self):
+ """
+ Iterates over the curently existing conflicts.
+ """
+ if self._conflicts_cache is None:
+ self._conflicts_cache = []
+
+ for cp_key in self._multi_pkgs:
+
+ # Categorize packages according to cpv and slot.
+ slot_map = collections.defaultdict(set)
+ cpv_map = collections.defaultdict(set)
+ for pkg in self._cp_pkg_map[cp_key]:
+ slot_key = pkg.root, pkg.slot_atom
+ cpv_key = pkg.root, pkg.cpv
+ slot_map[slot_key].add(pkg)
+ cpv_map[cpv_key].add(pkg)
+
+ # Slot conflicts.
+ for slot_key in slot_map:
+ slot_pkgs = slot_map[slot_key]
+ if len(slot_pkgs) > 1:
+ self._conflicts_cache.append(PackageConflict(
+ description = "slot conflict",
+ root = slot_key[0],
+ atom = slot_key[1],
+ pkgs = tuple(slot_pkgs),
+ ))
+
+ # CPV conflicts.
+ for cpv_key in cpv_map:
+ cpv_pkgs = cpv_map[cpv_key]
+ if len(cpv_pkgs) > 1:
+ # Make sure this cpv conflict is not a slot conflict at the same time.
+ # Ignore it if it is.
+ slots = set(pkg.slot for pkg in cpv_pkgs)
+ if len(slots) > 1:
+ self._conflicts_cache.append(PackageConflict(
+ description = "cpv conflict",
+ root = cpv_pkgs[0],
+ atom = cpv_pkgs[1],
+ pkgs = tuple(cpv_pkgs),
+ ))
+
+ return iter(self._conflicts_cache)
+
+ def slot_conflicts(self):
+ """
+ Iterates over present slot conflicts.
+ This is only intended for consumers that haven't been
+ updated to deal with other kinds of conflicts.
+ This funcion should be removed once all consumers are updated.
+ """
+ return (conflict for conflict in self.conflicts() \
+ if conflict.description == "slot conflict")
+
+ def all_pkgs(self, root):
+ """
+ Iterates over all packages for the given root
+ present in the tracker, including the installed
+ packages.
+ """
+ for cp_key in self._cp_pkg_map:
+ if cp_key[0] == root:
+ for pkg in self._cp_pkg_map[cp_key]:
+ yield pkg
+
+ for cp_key in self._cp_vdb_pkg_map:
+ if cp_key[0] == root:
+ for installed in self._cp_vdb_pkg_map[cp_key]:
+ if installed not in self._replaced_by:
+ yield installed
+
+ def contains(self, pkg, installed=True):
+ """
+ Checks if the package is in the tracker.
+ If 'installed' is True, returns True for
+ non-replaced installed packages.
+ """
+ cp_key = pkg.root, pkg.cp
+ for other in self._cp_pkg_map[cp_key]:
+ if other is pkg:
+ return True
+
+ if installed:
+ for installed in self._cp_vdb_pkg_map[cp_key]:
+ if installed is pkg and \
+ installed not in self._replaced_by:
+ return True
+
+ return False
+
+ def __contains__(self, pkg):
+ """
+ Checks if the package is in the tracker.
+ Returns True for non-replaced installed packages.
+ """
+ return self.contains(pkg, installed=True)
+
+
+class PackageTrackerDbapiWrapper(object):
+ """
+ A wrpper class that provides parts of the legacy
+ dbapi interface. Remove it once all consumers have
+ died.
+ """
+ def __init__(self, root, package_tracker):
+ self._root = root
+ self._package_tracker = package_tracker
+
+ def cpv_inject(self, pkg):
+ self._package_tracker.add_pkg(pkg)
+
+ def match_pkgs(self, atom):
+ if not isinstance(atom, Atom):
+ atom = Atom(atom)
+ ret = sorted(self._package_tracker.match(self._root, atom),
+ key=cmp_sort_key(lambda x, y: vercmp(x.version, y.version)))
+ return ret
+
+ def __iter__(self):
+ return self._package_tracker.all_pkgs(self._root)
+
+ def match(self, atom, use_cache=None):
+ return self.match_pkgs(atom)
+
+ def cp_list(self, cp):
+ return self.match_pkgs(cp)
--
1.8.3.2
^ permalink raw reply related [flat|nested] 13+ messages in thread* [gentoo-portage-dev] [PATCH 02/10] Replace _slot_pkg_map and some tree dbapiS with _package_tracker
2014-01-29 15:33 [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 01/10] Add resolver/package_tracker Sebastian Luther
@ 2014-01-29 15:33 ` Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 03/10] Replace mydbapi " Sebastian Luther
` (8 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Sebastian Luther @ 2014-01-29 15:33 UTC (permalink / raw
To: gentoo-portage-dev
---
pym/_emerge/depgraph.py | 48 ++++++++++++++++++++--------------
pym/_emerge/resolver/output_helpers.py | 7 ++---
2 files changed, 32 insertions(+), 23 deletions(-)
diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index 83035c2..fd59dda 100644
--- a/pym/_emerge/depgraph.py
+++ b/pym/_emerge/depgraph.py
@@ -75,6 +75,7 @@ from _emerge.UseFlagDisplay import pkg_use_display
from _emerge.userquery import userquery
from _emerge.resolver.backtracking import Backtracker, BacktrackParameter
+from _emerge.resolver.package_tracker import PackageTracker, PackageTrackerDbapiWrapper
from _emerge.resolver.slot_collision import slot_conflict_handler
from _emerge.resolver.circular_dependency import circular_dependency_handler
from _emerge.resolver.output import Display
@@ -341,8 +342,6 @@ class _dynamic_depgraph_config(object):
self.myparams = myparams.copy()
self._vdb_loaded = False
self._allow_backtracking = allow_backtracking
- # Maps slot atom to package for each Package added to the graph.
- self._slot_pkg_map = {}
# Maps nodes to the reasons they were selected for reinstallation.
self._reinstall_nodes = {}
self.mydbapi = {}
@@ -432,14 +431,14 @@ class _dynamic_depgraph_config(object):
self._traverse_ignored_deps = False
self._complete_mode = False
self._slot_operator_deps = {}
+ self._package_tracker = PackageTracker()
for myroot in depgraph._frozen_config.trees:
self.sets[myroot] = _depgraph_sets()
- self._slot_pkg_map[myroot] = {}
vardb = depgraph._frozen_config.trees[myroot]["vartree"].dbapi
# This dbapi instance will model the state that the vdb will
# have after new packages have been installed.
- fakedb = PackageVirtualDbapi(vardb.settings)
+ fakedb = PackageTrackerDbapiWrapper(myroot, self._package_tracker)
self.mydbapi[myroot] = fakedb
def graph_tree():
@@ -564,12 +563,12 @@ class depgraph(object):
if not dynamic_deps:
for pkg in vardb:
- fakedb.cpv_inject(pkg)
+ self._dynamic_config._package_tracker.add_installed_pkg(pkg)
else:
max_jobs = self._frozen_config.myopts.get("--jobs")
max_load = self._frozen_config.myopts.get("--load-average")
scheduler = TaskScheduler(
- self._dynamic_deps_preload(fake_vartree, fakedb),
+ self._dynamic_deps_preload(fake_vartree),
max_jobs=max_jobs,
max_load=max_load,
event_loop=fake_vartree._portdb._event_loop)
@@ -578,11 +577,11 @@ class depgraph(object):
self._dynamic_config._vdb_loaded = True
- def _dynamic_deps_preload(self, fake_vartree, fakedb):
+ def _dynamic_deps_preload(self, fake_vartree):
portdb = fake_vartree._portdb
for pkg in fake_vartree.dbapi:
self._spinner_update()
- fakedb.cpv_inject(pkg)
+ self._dynamic_config._package_tracker.add_installed_pkg(pkg)
ebuild_path, repo_path = \
portdb.findname2(pkg.cpv, myrepo=pkg.repo)
if ebuild_path is None:
@@ -1050,7 +1049,8 @@ class depgraph(object):
all_parents, conflict_pkgs):
debug = "--debug" in self._frozen_config.myopts
- existing_node = self._dynamic_config._slot_pkg_map[root][slot_atom]
+ existing_node = next(self._dynamic_config._package_tracker.match(
+ root, slot_atom, installed=False))
# In order to avoid a missed update, first mask lower versions
# that conflict with higher versions (the backtracker visits
# these in reverse order).
@@ -1827,8 +1827,8 @@ class depgraph(object):
# 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)
+ existing_node = next(self._dynamic_config._package_tracker.match(
+ dep.root, dep_pkg.slot_atom, installed=False), None)
if not dep_pkg:
if (dep.collapsed_priority.optional or
@@ -1893,7 +1893,9 @@ class depgraph(object):
return 1
def _check_slot_conflict(self, pkg, atom):
- existing_node = self._dynamic_config._slot_pkg_map[pkg.root].get(pkg.slot_atom)
+ existing_node = next(self._dynamic_config._package_tracker.match(
+ pkg.root, pkg.slot_atom, installed=False), None)
+
matches = None
if existing_node:
matches = pkg.cpv == existing_node.cpv
@@ -2046,7 +2048,7 @@ class depgraph(object):
# function despite collisions.
pass
elif not previously_added:
- self._dynamic_config._slot_pkg_map[pkg.root][pkg.slot_atom] = pkg
+ self._dynamic_config._package_tracker.add_pkg(pkg)
self._dynamic_config.mydbapi[pkg.root].cpv_inject(pkg)
self._dynamic_config._filtered_trees[pkg.root]["porttree"].dbapi._clear_cache()
self._dynamic_config._highest_pkg_cache.clear()
@@ -2162,7 +2164,8 @@ class depgraph(object):
slot_nodes = self._dynamic_config._slot_collision_info.get(slot_key)
if slot_nodes is None:
slot_nodes = set()
- slot_nodes.add(self._dynamic_config._slot_pkg_map[pkg.root][pkg.slot_atom])
+ slot_nodes.update(self._dynamic_config._package_tracker.match(
+ pkg.root, pkg.slot_atom, installed=False))
self._dynamic_config._slot_collision_info[slot_key] = slot_nodes
slot_nodes.add(pkg)
@@ -2347,8 +2350,8 @@ class depgraph(object):
mypriority.satisfied.visible and \
dep.child is not None and \
not dep.child.installed and \
- self._dynamic_config._slot_pkg_map[dep.child.root].get(
- dep.child.slot_atom) is None and \
+ not any(self._dynamic_config._package_tracker.match(
+ dep.child.root, dep.child.slot_atom, installed=False)) and \
not slot_operator_rebuild
def _wrapped_add_pkg_dep_string(self, pkg, dep_root, dep_priority,
@@ -5071,7 +5074,9 @@ class depgraph(object):
# will always end with a break statement below
# this point.
if find_existing_node:
- e_pkg = self._dynamic_config._slot_pkg_map[root].get(pkg.slot_atom)
+ e_pkg = next(self._dynamic_config._package_tracker.match(
+ root, pkg.slot_atom, installed=False), None)
+
if not e_pkg:
break
@@ -5319,7 +5324,9 @@ class depgraph(object):
matches = unmasked
pkg = matches[-1] # highest match
- in_graph = self._dynamic_config._slot_pkg_map[root].get(pkg.slot_atom)
+ in_graph = next(self._dynamic_config._package_tracker.match(
+ root, pkg.slot_atom, installed=False), None)
+
return pkg, in_graph
def _complete_graph(self, required_sets=None):
@@ -7988,8 +7995,9 @@ class _dep_check_composite_db(dbapi):
elif not self._depgraph._equiv_ebuild_visible(pkg):
return False
- in_graph = self._depgraph._dynamic_config._slot_pkg_map[
- self._root].get(pkg.slot_atom)
+ in_graph = next(self._depgraph._dynamic_config._package_tracker.match(
+ self._root, pkg.slot_atom, installed=False), None)
+
if in_graph is None:
# Mask choices for packages which are not the highest visible
# version within their slot (since they usually trigger slot
diff --git a/pym/_emerge/resolver/output_helpers.py b/pym/_emerge/resolver/output_helpers.py
index cfa6910..58b2694 100644
--- a/pym/_emerge/resolver/output_helpers.py
+++ b/pym/_emerge/resolver/output_helpers.py
@@ -227,7 +227,7 @@ class _DisplayConfig(object):
self.reinstall_nodes = dynamic_config._reinstall_nodes
self.digraph = dynamic_config.digraph
self.blocker_uninstalls = dynamic_config._blocker_uninstalls
- self.slot_pkg_map = dynamic_config._slot_pkg_map
+ self.package_tracker = dynamic_config._package_tracker
self.set_nodes = dynamic_config._set_nodes
self.pkg_use_enabled = depgraph._pkg_use_enabled
@@ -370,8 +370,9 @@ def _tree_display(conf, mylist):
# If the uninstall task did not need to be executed because
# of an upgrade, display Blocker -> Upgrade edges since the
# corresponding Blocker -> Uninstall edges will not be shown.
- upgrade_node = \
- conf.slot_pkg_map[uninstall.root].get(uninstall.slot_atom)
+ upgrade_node = next(conf.package_tracker.match(
+ uninstall.root, uninstall.slot_atom), None)
+
if upgrade_node is not None and \
uninstall not in executed_uninstalls:
for blocker in uninstall_parents:
--
1.8.3.2
^ permalink raw reply related [flat|nested] 13+ messages in thread* [gentoo-portage-dev] [PATCH 03/10] Replace mydbapi with _package_tracker
2014-01-29 15:33 [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 01/10] Add resolver/package_tracker Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 02/10] Replace _slot_pkg_map and some tree dbapiS with _package_tracker Sebastian Luther
@ 2014-01-29 15:33 ` Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 04/10] Replace _slot_collision_info " Sebastian Luther
` (7 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Sebastian Luther @ 2014-01-29 15:33 UTC (permalink / raw
To: gentoo-portage-dev
---
pym/_emerge/depgraph.py | 211 +++++++++++++++++++++++-------------------------
1 file changed, 101 insertions(+), 110 deletions(-)
diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index fd59dda..9d234c2 100644
--- a/pym/_emerge/depgraph.py
+++ b/pym/_emerge/depgraph.py
@@ -344,7 +344,6 @@ class _dynamic_depgraph_config(object):
self._allow_backtracking = allow_backtracking
# Maps nodes to the reasons they were selected for reinstallation.
self._reinstall_nodes = {}
- self.mydbapi = {}
# Contains a filtered view of preferred packages that are selected
# from available repositories.
self._filtered_trees = {}
@@ -440,7 +439,6 @@ class _dynamic_depgraph_config(object):
# have after new packages have been installed.
fakedb = PackageTrackerDbapiWrapper(myroot, self._package_tracker)
- self.mydbapi[myroot] = fakedb
def graph_tree():
pass
graph_tree.dbapi = fakedb
@@ -558,8 +556,6 @@ class depgraph(object):
if preload_installed_pkgs:
vardb = fake_vartree.dbapi
- fakedb = self._dynamic_config._graph_trees[
- myroot]["vartree"].dbapi
if not dynamic_deps:
for pkg in vardb:
@@ -724,25 +720,23 @@ class depgraph(object):
for pkg in list(self._dynamic_config.ignored_binaries):
- selected_pkg = self._dynamic_config.mydbapi[pkg.root
- ].match_pkgs(pkg.slot_atom)
+ selected_pkg = list()
- if not selected_pkg:
- continue
+ for selected_pkg in self._dynamic_config._package_tracker.match(
+ pkg.root, pkg.slot_atom):
- selected_pkg = selected_pkg[-1]
- if selected_pkg > pkg:
- self._dynamic_config.ignored_binaries.pop(pkg)
- continue
+ if selected_pkg > pkg:
+ self._dynamic_config.ignored_binaries.pop(pkg)
+ break
- if selected_pkg.installed and \
- selected_pkg.cpv == pkg.cpv and \
- selected_pkg.build_time == pkg.build_time:
- # We don't care about ignored binaries when an
- # identical installed instance is selected to
- # fill the slot.
- self._dynamic_config.ignored_binaries.pop(pkg)
- continue
+ if selected_pkg.installed and \
+ selected_pkg.cpv == pkg.cpv and \
+ selected_pkg.build_time == pkg.build_time:
+ # We don't care about ignored binaries when an
+ # identical installed instance is selected to
+ # fill the slot.
+ self._dynamic_config.ignored_binaries.pop(pkg)
+ break
if not self._dynamic_config.ignored_binaries:
return
@@ -788,20 +782,25 @@ class depgraph(object):
# Exclude installed here since we only
# want to show available updates.
continue
- chosen_pkg = self._dynamic_config.mydbapi[pkg.root
- ].match_pkgs(pkg.slot_atom)
- if not chosen_pkg or chosen_pkg[-1] >= pkg:
- continue
- k = (pkg.root, pkg.slot_atom)
- if k in missed_updates:
- other_pkg, mask_type, parent_atoms = missed_updates[k]
- if other_pkg > pkg:
- continue
- for mask_type, parent_atoms in mask_reasons.items():
- if not parent_atoms:
- continue
- missed_updates[k] = (pkg, mask_type, parent_atoms)
- break
+ missed_update = True
+ any_selected = False
+ for chosen_pkg in self._dynamic_config._package_tracker.match(
+ pkg.root, pkg.slot_atom):
+ any_selected = True
+ if chosen_pkg >= pkg:
+ missed_update = False
+ break
+ if any_selected and missed_update:
+ k = (pkg.root, pkg.slot_atom)
+ if k in missed_updates:
+ other_pkg, mask_type, parent_atoms = missed_updates[k]
+ if other_pkg > pkg:
+ continue
+ for mask_type, parent_atoms in mask_reasons.items():
+ if not parent_atoms:
+ continue
+ missed_updates[k] = (pkg, mask_type, parent_atoms)
+ break
return missed_updates
@@ -2040,16 +2039,13 @@ class depgraph(object):
# can show use flags and --tree portage.output. This node is
# only being partially added to the graph. It must not be
# allowed to interfere with the other nodes that have been
- # added. Do not overwrite data for existing nodes in
- # self._dynamic_config.mydbapi since that data will be used for blocker
- # validation.
+ # added.
# Even though the graph is now invalid, continue to process
# dependencies so that things like --fetchonly can still
# function despite collisions.
pass
elif not previously_added:
self._dynamic_config._package_tracker.add_pkg(pkg)
- self._dynamic_config.mydbapi[pkg.root].cpv_inject(pkg)
self._dynamic_config._filtered_trees[pkg.root]["porttree"].dbapi._clear_cache()
self._dynamic_config._highest_pkg_cache.clear()
self._check_masks(pkg)
@@ -3639,35 +3635,37 @@ class depgraph(object):
def _expand_virt_from_graph(self, root, atom):
if not isinstance(atom, Atom):
atom = Atom(atom)
- graphdb = self._dynamic_config.mydbapi[root]
- match = graphdb.match_pkgs(atom)
- if not match:
- yield atom
- return
- pkg = match[-1]
- if not pkg.cpv.startswith("virtual/"):
- yield atom
- return
- try:
- rdepend = self._select_atoms_from_graph(
- pkg.root, pkg._metadata.get("RDEPEND", ""),
- myuse=self._pkg_use_enabled(pkg),
- parent=pkg, strict=False)
- except InvalidDependString as e:
- writemsg_level("!!! Invalid RDEPEND in " + \
- "'%svar/db/pkg/%s/RDEPEND': %s\n" % \
- (pkg.root, pkg.cpv, e),
- noiselevel=-1, level=logging.ERROR)
+
+ if not atom.cp.startswith("virtual/"):
yield atom
return
- for atoms in rdepend.values():
- for atom in atoms:
- if hasattr(atom, "_orig_atom"):
- # Ignore virtual atoms since we're only
- # interested in expanding the real atoms.
- continue
- yield atom
+ any_match = False
+ for pkg in self._dynamic_config._package_tracker.match(root, atom):
+ try:
+ rdepend = self._select_atoms_from_graph(
+ pkg.root, pkg._metadata.get("RDEPEND", ""),
+ myuse=self._pkg_use_enabled(pkg),
+ parent=pkg, strict=False)
+ except InvalidDependString as e:
+ writemsg_level("!!! Invalid RDEPEND in " + \
+ "'%svar/db/pkg/%s/RDEPEND': %s\n" % \
+ (pkg.root, pkg.cpv, e),
+ noiselevel=-1, level=logging.ERROR)
+ continue
+
+ for atoms in rdepend.values():
+ for atom in atoms:
+ if hasattr(atom, "_orig_atom"):
+ # Ignore virtual atoms since we're only
+ # interested in expanding the real atoms.
+ continue
+ yield atom
+
+ any_match = True
+
+ if not any_match:
+ yield atom
def _virt_deps_visible(self, pkg, ignore_use=False):
"""
@@ -5524,10 +5522,14 @@ class depgraph(object):
installed=installed, onlydeps=onlydeps))
if pkg is None and onlydeps and not installed:
# Maybe it already got pulled in as a "merge" node.
- pkg = self._dynamic_config.mydbapi[root_config.root].get(
- Package._gen_hash_key(cpv=cpv, type_name=type_name,
- repo_name=myrepo, root_config=root_config,
- installed=installed, onlydeps=False))
+ for candidate in self._dynamic_config._package_tracker.match(
+ root_config.root, cpv):
+ if candidate.type_name == type_name and \
+ candidate.repo_name == myrepo and \
+ candidate.root_config is root_config and \
+ candidate.installed == installed and \
+ not candidate.onlydeps:
+ pkg = candidate
if pkg is None:
tree_type = self.pkg_tree_map[type_name]
@@ -5587,7 +5589,8 @@ class depgraph(object):
vardb = self._frozen_config.trees[myroot]["vartree"].dbapi
pkgsettings = self._frozen_config.pkgsettings[myroot]
root_config = self._frozen_config.roots[myroot]
- final_db = self._dynamic_config.mydbapi[myroot]
+ final_db = PackageTrackerDbapiWrapper(
+ myroot, self._dynamic_config._package_tracker)
blocker_cache = BlockerCache(myroot, vardb)
stale_cache = set(blocker_cache)
@@ -5604,7 +5607,7 @@ class depgraph(object):
# the merge process or by --depclean. Always warn about
# packages masked by license, since the user likely wants
# to adjust ACCEPT_LICENSE.
- if pkg in final_db:
+ if pkg in self._dynamic_config._package_tracker:
if not self._pkg_visibility_check(pkg,
trust_graph=False) and \
(pkg_in_graph or 'LICENSE' in pkg.masks):
@@ -5686,9 +5689,10 @@ class depgraph(object):
del e
raise
if not success:
- replacement_pkg = final_db.match_pkgs(pkg.slot_atom)
- if replacement_pkg and \
- replacement_pkg[0].operation == "merge":
+ replacement_pkgs = self._dynamic_config._package_tracker.match(
+ myroot, pkg.slot_atom)
+ if any(replacement_pkg[0].operation == "merge" for \
+ replacement_pkg in replacement_pkgs):
# This package is being replaced anyway, so
# ignore invalid dependencies so as not to
# annoy the user too much (otherwise they'd be
@@ -5733,7 +5737,6 @@ class depgraph(object):
virtuals = root_config.settings.getvirtuals()
myroot = blocker.root
initial_db = self._frozen_config.trees[myroot]["vartree"].dbapi
- final_db = self._dynamic_config.mydbapi[myroot]
provider_virtual = False
if blocker.cp in virtuals and \
@@ -5761,7 +5764,7 @@ class depgraph(object):
blocked_final = set()
for atom in atoms:
- for pkg in final_db.match_pkgs(atom):
+ for pkg in self._dynamic_config._package_tracker.match(myroot, atom):
if atom_set.findAtomForPackage(pkg, modified_use=self._pkg_use_enabled(pkg)):
blocked_final.add(pkg)
@@ -5943,19 +5946,15 @@ class depgraph(object):
libc_pkgs = {}
implicit_libc_roots = (self._frozen_config._running_root.root,)
for root in implicit_libc_roots:
- graphdb = self._dynamic_config.mydbapi[root]
vardb = self._frozen_config.trees[root]["vartree"].dbapi
for atom in self._expand_virt_from_graph(root,
portage.const.LIBC_PACKAGE_ATOM):
if atom.blocker:
continue
- match = graphdb.match_pkgs(atom)
- if not match:
- continue
- pkg = match[-1]
- if pkg.operation == "merge" and \
- not vardb.cpv_exists(pkg.cpv):
- libc_pkgs.setdefault(pkg.root, set()).add(pkg)
+ for pkg in self._dynamic_config._package_tracker.match(root, atom):
+ if pkg.operation == "merge" and \
+ not vardb.cpv_exists(pkg.cpv):
+ libc_pkgs.setdefault(pkg.root, set()).add(pkg)
if not libc_pkgs:
return
@@ -6156,8 +6155,8 @@ class depgraph(object):
initial_atoms=[PORTAGE_PACKAGE_ATOM])
running_portage = self._frozen_config.trees[running_root]["vartree"].dbapi.match_pkgs(
PORTAGE_PACKAGE_ATOM)
- replacement_portage = self._dynamic_config.mydbapi[running_root].match_pkgs(
- PORTAGE_PACKAGE_ATOM)
+ replacement_portage = list(self._dynamic_config._package_tracker.match(
+ running_root, Atom(PORTAGE_PACKAGE_ATOM)))
if running_portage:
running_portage = running_portage[0]
@@ -6194,18 +6193,15 @@ class depgraph(object):
for root in implicit_libc_roots:
libc_pkgs = set()
vardb = self._frozen_config.trees[root]["vartree"].dbapi
- graphdb = self._dynamic_config.mydbapi[root]
for atom in self._expand_virt_from_graph(root,
portage.const.LIBC_PACKAGE_ATOM):
if atom.blocker:
continue
- match = graphdb.match_pkgs(atom)
- if not match:
- continue
- pkg = match[-1]
- if pkg.operation == "merge" and \
- not vardb.cpv_exists(pkg.cpv):
- libc_pkgs.add(pkg)
+
+ for pkg in self._dynamic_config._package_tracker.match(root, atom):
+ if pkg.operation == "merge" and \
+ not vardb.cpv_exists(pkg.cpv):
+ libc_pkgs.add(pkg)
if libc_pkgs:
# If there's also an os-headers upgrade, we need to
@@ -6214,13 +6210,11 @@ class depgraph(object):
portage.const.OS_HEADERS_PACKAGE_ATOM):
if atom.blocker:
continue
- match = graphdb.match_pkgs(atom)
- if not match:
- continue
- pkg = match[-1]
- if pkg.operation == "merge" and \
- not vardb.cpv_exists(pkg.cpv):
- asap_nodes.append(pkg)
+
+ for pkg in self._dynamic_config._package_tracker.match(root, atom):
+ if pkg.operation == "merge" and \
+ not vardb.cpv_exists(pkg.cpv):
+ asap_nodes.append(pkg)
asap_nodes.extend(libc_pkgs)
@@ -6562,13 +6556,12 @@ class depgraph(object):
# For packages in the world set, go ahead an uninstall
# when necessary, as long as the atom will be satisfied
# in the final state.
- graph_db = self._dynamic_config.mydbapi[task.root]
skip = False
try:
for atom in root_config.sets[
"selected"].iterAtomsForPackage(task):
satisfied = False
- for pkg in graph_db.match_pkgs(atom):
+ for pkg in self._dynamic_config._package_tracker.match(task.root, atom):
if pkg == inst_pkg:
continue
satisfied = True
@@ -6650,12 +6643,11 @@ class depgraph(object):
# node unnecessary (due to occupying the same SLOT),
# and we want to avoid executing a separate uninstall
# task in that case.
- slot_node = self._dynamic_config.mydbapi[uninst_task.root
- ].match_pkgs(uninst_task.slot_atom)
- if slot_node and \
- slot_node[0].operation == "merge":
- mygraph.add(slot_node[0], uninst_task,
- priority=BlockerDepPriority.instance)
+ for slot_node in self._dynamic_config._package_tracker.match(
+ uninst_task.root, uninst_task.slot_atom):
+ if slot_node.operation == "merge":
+ mygraph.add(slot_node, uninst_task,
+ priority=BlockerDepPriority.instance)
# Reset the state variables for leaf node selection and
# continue trying to select leaf nodes.
@@ -7624,7 +7616,6 @@ class depgraph(object):
else:
args = []
- fakedb = self._dynamic_config.mydbapi
serialized_tasks = []
masked_tasks = []
for x in mergelist:
@@ -7682,7 +7673,7 @@ class depgraph(object):
self._dynamic_config._unsatisfied_deps_for_display.append(
((pkg.root, "="+pkg.cpv), {"myparent":None}))
- fakedb[myroot].cpv_inject(pkg)
+ self._dynamic_config._package_tracker.add_pkg(pkg)
serialized_tasks.append(pkg)
self._spinner_update()
--
1.8.3.2
^ permalink raw reply related [flat|nested] 13+ messages in thread* [gentoo-portage-dev] [PATCH 04/10] Replace _slot_collision_info with _package_tracker
2014-01-29 15:33 [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking Sebastian Luther
` (2 preceding siblings ...)
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 03/10] Replace mydbapi " Sebastian Luther
@ 2014-01-29 15:33 ` Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 05/10] Replace _slot_collision_nodes " Sebastian Luther
` (6 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Sebastian Luther @ 2014-01-29 15:33 UTC (permalink / raw
To: gentoo-portage-dev
---
pym/_emerge/depgraph.py | 59 ++++++++++++----------------------
pym/_emerge/resolver/slot_collision.py | 22 ++++++-------
2 files changed, 31 insertions(+), 50 deletions(-)
diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index 9d234c2..484ac14 100644
--- a/pym/_emerge/depgraph.py
+++ b/pym/_emerge/depgraph.py
@@ -378,11 +378,6 @@ class _dynamic_depgraph_config(object):
# This use used to check if we have accounted for blockers
# relevant to a package.
self._traversed_pkg_deps = set()
- # This should be ordered such that the backtracker will
- # attempt to solve conflicts which occurred earlier first,
- # since an earlier conflict can be the cause of a conflict
- # which occurs later.
- self._slot_collision_info = OrderedDict()
# Slot collision nodes are not allowed to block other packages since
# blocker validation is only able to account for one package per slot.
self._slot_collision_nodes = set()
@@ -915,7 +910,7 @@ class depgraph(object):
cases.
"""
- if not self._dynamic_config._slot_collision_info:
+ if not any(self._dynamic_config._package_tracker.slot_conflicts()):
return
self._show_merge_list()
@@ -971,16 +966,18 @@ class depgraph(object):
is called, so that all relevant reverse dependencies are
available for use in backtracking decisions.
"""
- for (slot_atom, root), slot_nodes in \
- self._dynamic_config._slot_collision_info.items():
- self._process_slot_conflict(root, slot_atom, slot_nodes)
+ for conflict in self._dynamic_config._package_tracker.slot_conflicts():
+ self._process_slot_conflict(conflict)
- def _process_slot_conflict(self, root, slot_atom, slot_nodes):
+ def _process_slot_conflict(self, conflict):
"""
Process slot conflict data to identify specific atoms which
lead to conflict. These atoms only match a subset of the
packages that have been pulled into a given slot.
"""
+ root = conflict.root
+ slot_atom = conflict.atom
+ slot_nodes = conflict.pkgs
debug = "--debug" in self._frozen_config.myopts
@@ -1999,7 +1996,6 @@ class depgraph(object):
existing_node, existing_node_matches = \
self._check_slot_conflict(pkg, dep.atom)
- slot_collision = False
if existing_node:
if existing_node_matches:
# The existing node can be reused.
@@ -2032,19 +2028,7 @@ class depgraph(object):
modified_use=self._pkg_use_enabled(existing_node))),
level=logging.DEBUG, noiselevel=-1)
- slot_collision = True
-
- if slot_collision:
- # Now add this node to the graph so that self.display()
- # can show use flags and --tree portage.output. This node is
- # only being partially added to the graph. It must not be
- # allowed to interfere with the other nodes that have been
- # added.
- # Even though the graph is now invalid, continue to process
- # dependencies so that things like --fetchonly can still
- # function despite collisions.
- pass
- elif not previously_added:
+ if not previously_added:
self._dynamic_config._package_tracker.add_pkg(pkg)
self._dynamic_config._filtered_trees[pkg.root]["porttree"].dbapi._clear_cache()
self._dynamic_config._highest_pkg_cache.clear()
@@ -2156,14 +2140,6 @@ class depgraph(object):
def _add_slot_conflict(self, pkg):
self._dynamic_config._slot_collision_nodes.add(pkg)
- slot_key = (pkg.slot_atom, pkg.root)
- slot_nodes = self._dynamic_config._slot_collision_info.get(slot_key)
- if slot_nodes is None:
- slot_nodes = set()
- slot_nodes.update(self._dynamic_config._package_tracker.match(
- pkg.root, pkg.slot_atom, installed=False))
- self._dynamic_config._slot_collision_info[slot_key] = slot_nodes
- slot_nodes.add(pkg)
def _add_pkg_deps(self, pkg, allow_unsatisfied=False):
@@ -3284,7 +3260,8 @@ class depgraph(object):
except self._unknown_internal_error:
return False, myfavorites
- if (self._dynamic_config._slot_collision_info and
+ have_slot_conflict = any(self._dynamic_config._package_tracker.slot_conflicts())
+ if (have_slot_conflict and
not self._accept_blocker_conflicts()) or \
(self._dynamic_config._allow_backtracking and
"slot conflict" in self._dynamic_config._backtrack_infos):
@@ -6806,7 +6783,8 @@ class depgraph(object):
# conflicts (or by blind luck).
raise self._unknown_internal_error()
- if self._dynamic_config._slot_collision_info and \
+ have_slot_conflict = any(self._dynamic_config._package_tracker.slot_conflicts())
+ if have_slot_conflict and \
not self._accept_blocker_conflicts():
self._dynamic_config._serialized_tasks_cache = retlist
self._dynamic_config._scheduler_graph = scheduler_graph
@@ -6881,13 +6859,17 @@ class depgraph(object):
# the reasons are not apparent from the normal merge list
# display.
- slot_collision_info = self._dynamic_config._slot_collision_info
-
conflict_pkgs = {}
for blocker in blockers:
for pkg in chain(self._dynamic_config._blocked_pkgs.child_nodes(blocker), \
self._dynamic_config._blocker_parents.parent_nodes(blocker)):
- if (pkg.slot_atom, pkg.root) in slot_collision_info:
+
+ is_slot_conflict_pkg = False
+ for conflict in self._dynamic_config._package_tracker.slot_conflicts():
+ if conflict.root == pkg.root and conflict.atom == pkg.slot_atom:
+ is_slot_conflict_pkg = True
+ break
+ if is_slot_conflict_pkg:
# The slot conflict display has better noise reduction
# than the unsatisfied blockers display, so skip
# unsatisfied blockers display for packages involved
@@ -7370,7 +7352,8 @@ class depgraph(object):
self._dynamic_config._circular_deps_for_display)
unresolved_conflicts = False
- if self._dynamic_config._slot_collision_info:
+ have_slot_conflict = any(self._dynamic_config._package_tracker.slot_conflicts())
+ if have_slot_conflict:
unresolved_conflicts = True
self._show_slot_collision_notice()
if self._dynamic_config._unsatisfied_blockers_for_display is not None:
diff --git a/pym/_emerge/resolver/slot_collision.py b/pym/_emerge/resolver/slot_collision.py
index a193baa..ca3fb74 100644
--- a/pym/_emerge/resolver/slot_collision.py
+++ b/pym/_emerge/resolver/slot_collision.py
@@ -89,10 +89,11 @@ class slot_conflict_handler(object):
self.debug = "--debug" in self.myopts
if self.debug:
writemsg("Starting slot conflict handler\n", noiselevel=-1)
- #slot_collision_info is a dict mapping (slot atom, root) to set
- #of packages. The packages in the set all belong to the same
- #slot.
- self.slot_collision_info = depgraph._dynamic_config._slot_collision_info
+
+ # List of tuples, where each tuple represents a slot conflict.
+ self.all_conflicts = []
+ for conflict in depgraph._dynamic_config._package_tracker.slot_conflicts():
+ self.all_conflicts.append((conflict.root, conflict.atom, conflict.pkgs))
#A dict mapping packages to pairs of parent package
#and parent atom
@@ -109,8 +110,7 @@ class slot_conflict_handler(object):
all_conflict_atoms_by_slotatom = []
#fill conflict_pkgs, all_conflict_atoms_by_slotatom
- for (atom, root), pkgs \
- in self.slot_collision_info.items():
+ for root, atom, pkgs in self.all_conflicts:
conflict_pkgs.append(list(pkgs))
all_conflict_atoms_by_slotatom.append(set())
@@ -249,8 +249,7 @@ class slot_conflict_handler(object):
msg.append("!!! into the dependency graph, resulting" + \
" in a slot conflict:\n\n")
- for (slot_atom, root), pkgs \
- in self.slot_collision_info.items():
+ for root, slot_atom, pkgs in self.all_conflicts:
msg.append("%s" % (slot_atom,))
if root != self.depgraph._frozen_config._running_root.root:
msg.append(" for %s" % (root,))
@@ -536,13 +535,13 @@ class slot_conflict_handler(object):
return None
if len(solutions)==1:
- if len(self.slot_collision_info)==1:
+ if len(self.all_conflicts) == 1:
msg += "It might be possible to solve this slot collision\n"
else:
msg += "It might be possible to solve these slot collisions\n"
msg += "by applying all of the following changes:\n"
else:
- if len(self.slot_collision_info)==1:
+ if len(self.all_conflicts) == 1:
msg += "It might be possible to solve this slot collision\n"
else:
msg += "It might be possible to solve these slot collisions\n"
@@ -583,8 +582,7 @@ class slot_conflict_handler(object):
if not pkg.installed:
continue
- for (atom, root), pkgs \
- in self.slot_collision_info.items():
+ for root, atom, pkgs in self.all_conflicts:
if pkg not in pkgs:
continue
for other_pkg in pkgs:
--
1.8.3.2
^ permalink raw reply related [flat|nested] 13+ messages in thread* [gentoo-portage-dev] [PATCH 05/10] Replace _slot_collision_nodes with _package_tracker
2014-01-29 15:33 [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking Sebastian Luther
` (3 preceding siblings ...)
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 04/10] Replace _slot_collision_info " Sebastian Luther
@ 2014-01-29 15:33 ` Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 06/10] Package.__str__: show slot/sub-slot Sebastian Luther
` (5 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Sebastian Luther @ 2014-01-29 15:33 UTC (permalink / raw
To: gentoo-portage-dev
---
pym/_emerge/depgraph.py | 16 +++++++---------
1 file changed, 7 insertions(+), 9 deletions(-)
diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index 484ac14..1bb086b 100644
--- a/pym/_emerge/depgraph.py
+++ b/pym/_emerge/depgraph.py
@@ -378,9 +378,6 @@ class _dynamic_depgraph_config(object):
# This use used to check if we have accounted for blockers
# relevant to a package.
self._traversed_pkg_deps = set()
- # Slot collision nodes are not allowed to block other packages since
- # blocker validation is only able to account for one package per slot.
- self._slot_collision_nodes = set()
self._parent_atoms = {}
self._slot_conflict_handler = None
self._circular_dependency_handler = None
@@ -1799,11 +1796,16 @@ class depgraph(object):
buildpkgonly = "--buildpkgonly" in self._frozen_config.myopts
nodeps = "--nodeps" in self._frozen_config.myopts
if dep.blocker:
+
+ # Slot collision nodes are not allowed to block other packages since
+ # blocker validation is only able to account for one package per slot.
+ is_slot_conflict_parent = any(dep.parent in conflict.pkgs[1:] for conflict in \
+ self._dynamic_config._package_tracker.slot_conflicts())
if not buildpkgonly and \
not nodeps and \
not dep.collapsed_priority.ignored and \
not dep.collapsed_priority.optional and \
- dep.parent not in self._dynamic_config._slot_collision_nodes:
+ not is_slot_conflict_parent:
if dep.parent.onlydeps:
# It's safe to ignore blockers if the
# parent is an --onlydeps node.
@@ -2019,7 +2021,6 @@ class depgraph(object):
level=logging.DEBUG, noiselevel=-1)
else:
- self._add_slot_conflict(pkg)
if debug:
writemsg_level(
"%s%s %s\n" % ("Slot Conflict:".ljust(15),
@@ -2138,9 +2139,6 @@ class depgraph(object):
self._dynamic_config._slot_operator_deps[slot_key] = slot_info
slot_info.append(dep)
- def _add_slot_conflict(self, pkg):
- self._dynamic_config._slot_collision_nodes.add(pkg)
-
def _add_pkg_deps(self, pkg, allow_unsatisfied=False):
myroot = pkg.root
@@ -6019,7 +6017,7 @@ class depgraph(object):
if "complete" not in self._dynamic_config.myparams and \
self._dynamic_config._allow_backtracking and \
- self._dynamic_config._slot_collision_nodes and \
+ any(self._dynamic_config._package_tracker.slot_conflicts()) and \
not self._accept_blocker_conflicts():
self._dynamic_config.myparams["complete"] = True
--
1.8.3.2
^ permalink raw reply related [flat|nested] 13+ messages in thread* [gentoo-portage-dev] [PATCH 06/10] Package.__str__: show slot/sub-slot
2014-01-29 15:33 [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking Sebastian Luther
` (4 preceding siblings ...)
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 05/10] Replace _slot_collision_nodes " Sebastian Luther
@ 2014-01-29 15:33 ` Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 07/10] format_unmatched_atom: Pretty printing for unmatched atoms Sebastian Luther
` (4 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Sebastian Luther @ 2014-01-29 15:33 UTC (permalink / raw
To: gentoo-portage-dev
---
pym/_emerge/Package.py | 5 +++--
1 file changed, 3 insertions(+), 2 deletions(-)
diff --git a/pym/_emerge/Package.py b/pym/_emerge/Package.py
index c795568..a09f73c 100644
--- a/pym/_emerge/Package.py
+++ b/pym/_emerge/Package.py
@@ -1,4 +1,4 @@
-# Copyright 1999-2013 Gentoo Foundation
+# Copyright 1999-2014 Gentoo Foundation
# Distributed under the terms of the GNU General Public License v2
from __future__ import unicode_literals
@@ -468,7 +468,8 @@ class Package(Task):
cpv_color = "PKG_NOMERGE"
s = "(%s, %s" \
- % (portage.output.colorize(cpv_color, self.cpv + _repo_separator + self.repo) , self.type_name)
+ % (portage.output.colorize(cpv_color, self.cpv + _slot_separator + \
+ self.slot + "/" + self.sub_slot + _repo_separator + self.repo) , self.type_name)
if self.type_name == "installed":
if self.root_config.settings['ROOT'] != "/":
--
1.8.3.2
^ permalink raw reply related [flat|nested] 13+ messages in thread* [gentoo-portage-dev] [PATCH 07/10] format_unmatched_atom: Pretty printing for unmatched atoms
2014-01-29 15:33 [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking Sebastian Luther
` (5 preceding siblings ...)
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 06/10] Package.__str__: show slot/sub-slot Sebastian Luther
@ 2014-01-29 15:33 ` Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 08/10] Some small output fixes for the slot conflict handler Sebastian Luther
` (3 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Sebastian Luther @ 2014-01-29 15:33 UTC (permalink / raw
To: gentoo-portage-dev
This is a split out from the slot conflict handler to be
used in other places.
---
pym/_emerge/resolver/output.py | 109 +++++++++++++++++++++++++++++++++++++++--
1 file changed, 106 insertions(+), 3 deletions(-)
diff --git a/pym/_emerge/resolver/output.py b/pym/_emerge/resolver/output.py
index 3e8552f..5f550be 100644
--- a/pym/_emerge/resolver/output.py
+++ b/pym/_emerge/resolver/output.py
@@ -1,4 +1,4 @@
-# Copyright 2010-2013 Gentoo Foundation
+# Copyright 2010-2014 Gentoo Foundation
# Distributed under the terms of the GNU General Public License v2
"""Resolver output display operation.
@@ -7,7 +7,7 @@
from __future__ import unicode_literals
__all__ = (
- "Display",
+ "Display", "format_unmatched_atom",
)
import sys
@@ -23,8 +23,9 @@ from portage.package.ebuild._spawn_nofetch import spawn_nofetch
from portage.output import ( blue, colorize, create_color_func,
darkblue, darkgreen, green, nc_len, teal)
bad = create_color_func("BAD")
+from portage._sets.base import InternalPackageSet
from portage.util import writemsg_stdout
-from portage.versions import best
+from portage.versions import best, cpv_getversion
from _emerge.Blocker import Blocker
from _emerge.create_world_atom import create_world_atom
@@ -916,3 +917,105 @@ class Display(object):
self.print_changelog()
return os.EX_OK
+
+
+def format_unmatched_atom(pkg, atom, pkg_use_enabled):
+ """
+ Returns two strings. The first string contains the
+ 'atom' with parts of the atom colored, which 'pkg'
+ doesn't match. The second string has the same number
+ of characters as the first one, but consists of only
+ white space or ^. The ^ characters have the same position
+ as the colored parts of the first string.
+ """
+ # Things to check:
+ # 1. Version
+ # 2. cp
+ # 3. slot/sub_slot
+ # 4. repository
+ # 5. USE
+
+ highlight = set()
+
+ def perform_coloring():
+ atom_str = ""
+ marker_str = ""
+ for ii, x in enumerate(atom):
+ if ii in highlight:
+ atom_str += colorize("BAD", x)
+ marker_str += "^"
+ else:
+ atom_str += x
+ marker_str += " "
+ return atom_str, marker_str
+
+ if atom.cp != pkg.cp:
+ # Highlight the cp part only.
+ ii = atom.find(atom.cp)
+ highlight.update(range(ii, ii + len(atom.cp)))
+ return perform_coloring()
+
+ version_atom = atom.without_repo.without_slot.without_use
+ version_atom_set = InternalPackageSet(initial_atoms=(version_atom,))
+ highlight_version = not bool(version_atom_set.findAtomForPackage(pkg,
+ modified_use=pkg_use_enabled(pkg)))
+
+ highlight_slot = False
+ if (atom.slot and atom.slot != pkg.slot) or \
+ (atom.sub_slot and atom.sub_slot != pkg.sub_slot):
+ highlight_slot = True
+
+ if highlight_version:
+ op = atom.operator
+ ver = None
+ if atom.cp != atom.cpv:
+ ver = cpv_getversion(atom.cpv)
+
+ if op == "=*":
+ op = "="
+ ver += "*"
+
+ if op is not None:
+ highlight.update(range(len(op)))
+
+ if ver is not None:
+ start = atom.rfind(ver)
+ end = start + len(ver)
+ highlight.update(range(start, end))
+
+ if highlight_slot:
+ slot_str = ":" + atom.slot
+ if atom.sub_slot:
+ slot_str += "/" + atom.sub_slot
+ if atom.slot_operator:
+ slot_str += atom.slot_operator
+ start = atom.find(slot_str)
+ end = start + len(slot_str)
+ highlight.update(range(start, end))
+
+ highlight_use = set()
+ if atom.use:
+ use_atom = "%s[%s]" % (atom.cp, str(atom.use))
+ use_atom_set = InternalPackageSet(initial_atoms=(use_atom,))
+ if not use_atom_set.findAtomForPackage(pkg, \
+ modified_use=pkg_use_enabled(pkg)):
+ missing_iuse = pkg.iuse.get_missing_iuse(
+ atom.unevaluated_atom.use.required)
+ if missing_iuse:
+ highlight_use = set(missing_iuse)
+ else:
+ #Use conditionals not met.
+ violated_atom = atom.violated_conditionals(
+ pkg_use_enabled(pkg), pkg.iuse.is_valid_flag)
+ if violated_atom.use is not None:
+ highlight_use = set(violated_atom.use.enabled.union(
+ violated_atom.use.disabled))
+
+ if highlight_use:
+ ii = atom.find("[") + 1
+ for token in atom.use.tokens:
+ if token.lstrip("-!").rstrip("=?") in highlight_use:
+ highlight.update(range(ii, ii + len(token)))
+ ii += len(token) + 1
+
+ return perform_coloring()
--
1.8.3.2
^ permalink raw reply related [flat|nested] 13+ messages in thread* [gentoo-portage-dev] [PATCH 08/10] Some small output fixes for the slot conflict handler
2014-01-29 15:33 [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking Sebastian Luther
` (6 preceding siblings ...)
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 07/10] format_unmatched_atom: Pretty printing for unmatched atoms Sebastian Luther
@ 2014-01-29 15:33 ` Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 09/10] Add digraph.discard Sebastian Luther
` (2 subsequent siblings)
10 siblings, 0 replies; 13+ messages in thread
From: Sebastian Luther @ 2014-01-29 15:33 UTC (permalink / raw
To: gentoo-portage-dev
* unmatched atom printing now uses ^^ markers
* unmatched atom printing properly supports sub-slots
* Fix spurious "no parents" message caused by AtomArg parents
---
pym/_emerge/resolver/slot_collision.py | 119 ++++++++++++++++++++++++++-------
1 file changed, 96 insertions(+), 23 deletions(-)
diff --git a/pym/_emerge/resolver/slot_collision.py b/pym/_emerge/resolver/slot_collision.py
index ca3fb74..c5936ad 100644
--- a/pym/_emerge/resolver/slot_collision.py
+++ b/pym/_emerge/resolver/slot_collision.py
@@ -1,4 +1,4 @@
-# Copyright 2010-2013 Gentoo Foundation
+# Copyright 2010-2014 Gentoo Foundation
# Distributed under the terms of the GNU General Public License v2
from __future__ import print_function, unicode_literals
@@ -273,12 +273,14 @@ class slot_conflict_handler(object):
for ppkg, atom in parent_atoms:
atom_set = InternalPackageSet(initial_atoms=(atom,))
atom_without_use_set = InternalPackageSet(initial_atoms=(atom.without_use,))
+ atom_without_use_and_slot_set = InternalPackageSet(initial_atoms=(
+ atom.without_use.without_slot,))
for other_pkg in pkgs:
if other_pkg == pkg:
continue
- if not atom_without_use_set.findAtomForPackage(other_pkg, \
+ if not atom_without_use_and_slot_set.findAtomForPackage(other_pkg, \
modified_use=_pkg_use_enabled(other_pkg)):
if atom.operator is not None:
# The version range does not match.
@@ -295,9 +297,11 @@ class slot_conflict_handler(object):
atoms.add((ppkg, atom, other_pkg))
num_all_specific_atoms += 1
collision_reasons[key] = atoms
- else:
- # The sub_slot does not match.
- key = ("sub-slot", atom.sub_slot)
+
+ elif not atom_without_use_set.findAtomForPackage(other_pkg, \
+ modified_use=_pkg_use_enabled(other_pkg)):
+ # The slot and/or sub_slot does not match.
+ key = ("slot", (atom.slot, atom.sub_slot, atom.slot_operator))
atoms = collision_reasons.get(key, set())
atoms.add((ppkg, atom, other_pkg))
num_all_specific_atoms += 1
@@ -342,6 +346,11 @@ class slot_conflict_handler(object):
atoms.add((ppkg, atom, other_pkg))
collision_reasons[("use", flag)] = atoms
num_all_specific_atoms += 1
+ elif isinstance(ppkg, AtomArg) and other_pkg.installed:
+ parent_atoms = collision_reasons.get(("AtomArg", None), set())
+ parent_atoms.add((ppkg, atom))
+ collision_reasons[("AtomArg", None)] = parent_atoms
+ num_all_specific_atoms += 1
msg.append(" pulled in by\n")
@@ -372,9 +381,11 @@ class slot_conflict_handler(object):
if not verboseconflicts:
selected_for_display.update(
best_matches.values())
- elif type == "sub-slot":
+ elif type == "slot":
for ppkg, atom, other_pkg in parents:
selected_for_display.add((ppkg, atom))
+ if not verboseconflicts:
+ break
elif type == "use":
#Prefer atoms with unconditional use deps over, because it's
#not possible to change them on the parent, which means there
@@ -416,21 +427,50 @@ class slot_conflict_handler(object):
# If the list is long, people can simply
# use a pager.
selected_for_display.add((ppkg, atom))
+ elif type == "AtomArg":
+ for ppkg, atom in parents:
+ selected_for_display.add((ppkg, atom))
- def highlight_violations(atom, version, use=[]):
+ def highlight_violations(atom, version, use, slot_violated):
"""Colorize parts of an atom"""
atom_str = "%s" % (atom,)
+ colored_idx = set()
if version:
op = atom.operator
ver = None
if atom.cp != atom.cpv:
ver = cpv_getversion(atom.cpv)
slot = atom.slot
+ sub_slot = atom.sub_slot
+ slot_operator = atom.slot_operator
if op == "=*":
op = "="
ver += "*"
+ slot_str = ""
+ if slot:
+ slot_str = ":" + slot
+ if sub_slot:
+ slot_str += "/" + sub_slot
+ if slot_operator:
+ slot_str += slot_operator
+
+ # Compute color_idx before adding the color codes
+ # as these change the indices of the letters.
+ if op is not None:
+ colored_idx.update(range(len(op)))
+
+ if ver is not None:
+ start = atom_str.rfind(ver)
+ end = start + len(ver)
+ colored_idx.update(range(start, end))
+
+ if slot_str:
+ ii = atom_str.find(slot_str)
+ colored_idx.update(range(ii, ii + len(slot_str)))
+
+
if op is not None:
atom_str = atom_str.replace(op, colorize("BAD", op), 1)
@@ -440,25 +480,48 @@ class slot_conflict_handler(object):
atom_str = atom_str[:start] + \
colorize("BAD", ver) + \
atom_str[end:]
+
+ if slot_str:
+ atom_str = atom_str.replace(slot_str, colorize("BAD", slot_str), 1)
+
+ elif slot_violated:
+ slot = atom.slot
+ sub_slot = atom.sub_slot
+ slot_operator = atom.slot_operator
+
+ slot_str = ""
if slot:
- atom_str = atom_str.replace(":" + slot, colorize("BAD", ":" + slot))
+ slot_str = ":" + slot
+ if sub_slot:
+ slot_str += "/" + sub_slot
+ if slot_operator:
+ slot_str += slot_operator
+
+ if slot_str:
+ ii = atom_str.find(slot_str)
+ colored_idx.update(range(ii, ii + len(slot_str)))
+ atom_str = atom_str.replace(slot_str, colorize("BAD", slot_str), 1)
if use and atom.use.tokens:
use_part_start = atom_str.find("[")
use_part_end = atom_str.find("]")
new_tokens = []
+ # Compute start index in non-colored atom.
+ ii = str(atom).find("[") + 1
for token in atom.use.tokens:
if token.lstrip("-!").rstrip("=?") in use:
new_tokens.append(colorize("BAD", token))
+ colored_idx.update(range(ii, ii + len(token)))
else:
new_tokens.append(token)
+ ii += 1 + len(token)
atom_str = atom_str[:use_part_start] \
+ "[%s]" % (",".join(new_tokens),) + \
atom_str[use_part_end+1:]
- return atom_str
+ return atom_str, colored_idx
# Show unconditional use deps first, since those
# are more problematic than the conditional kind.
@@ -469,37 +532,48 @@ class slot_conflict_handler(object):
ordered_list.append(parent_atom)
for parent_atom in ordered_list:
parent, atom = parent_atom
- msg.append(2*indent)
- if isinstance(parent,
- (PackageArg, AtomArg)):
- # For PackageArg and AtomArg types, it's
+ if isinstance(parent, PackageArg):
+ # For PackageArg it's
# redundant to display the atom attribute.
- msg.append("%s" % (parent,))
+ msg.append("%s\n" % (parent,))
+ elif isinstance(parent, AtomArg):
+ msg.append("%s (Argument)\n" % (atom,))
else:
# Display the specific atom from SetArg or
# Package types.
version_violated = False
- sub_slot_violated = False
+ slot_violated = False
use = []
for (type, sub_type), parents in collision_reasons.items():
for x in parents:
if parent == x[0] and atom == x[1]:
if type == "version":
version_violated = True
- elif type == "sub-slot":
- sub_slot_violated = True
+ elif type == "slot":
+ slot_violated = True
elif type == "use":
use.append(sub_type)
break
- atom_str = highlight_violations(atom.unevaluated_atom, version_violated, use)
+ atom_str, colored_idx = highlight_violations(atom.unevaluated_atom,
+ version_violated, use, slot_violated)
- if version_violated or sub_slot_violated:
+ if version_violated or slot_violated:
self.is_a_version_conflict = True
- msg.append("%s required by %s" % (atom_str, parent))
- msg.append("\n")
-
+ cur_line = "%s required by %s\n" % (atom_str, parent)
+ marker_line = ""
+ for ii in range(len(cur_line)):
+ if ii in colored_idx:
+ marker_line += "^"
+ else:
+ marker_line += " "
+ marker_line += "\n"
+ msg.append(2*indent)
+ msg.append(cur_line)
+ msg.append(2*indent)
+ msg.append(marker_line)
+
if not selected_for_display:
msg.append(2*indent)
msg.append("(no parents that aren't satisfied by other packages in this slot)\n")
@@ -519,7 +593,6 @@ class slot_conflict_handler(object):
def get_explanation(self):
msg = ""
- _pkg_use_enabled = self.depgraph._pkg_use_enabled
if self.is_a_version_conflict:
return None
--
1.8.3.2
^ permalink raw reply related [flat|nested] 13+ messages in thread* [gentoo-portage-dev] [PATCH 09/10] Add digraph.discard
2014-01-29 15:33 [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking Sebastian Luther
` (7 preceding siblings ...)
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 08/10] Some small output fixes for the slot conflict handler Sebastian Luther
@ 2014-01-29 15:33 ` Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 10/10] Solve some slot conflicts without backtracking Sebastian Luther
2014-02-02 20:41 ` [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking Brian Dolbec
10 siblings, 0 replies; 13+ messages in thread
From: Sebastian Luther @ 2014-01-29 15:33 UTC (permalink / raw
To: gentoo-portage-dev
---
pym/portage/util/digraph.py | 12 +++++++++++-
1 file changed, 11 insertions(+), 1 deletion(-)
diff --git a/pym/portage/util/digraph.py b/pym/portage/util/digraph.py
index fc1fb86..4a9cb43 100644
--- a/pym/portage/util/digraph.py
+++ b/pym/portage/util/digraph.py
@@ -1,4 +1,4 @@
-# Copyright 2010-2013 Gentoo Foundation
+# Copyright 2010-2014 Gentoo Foundation
# Distributed under the terms of the GNU General Public License v2
from __future__ import unicode_literals
@@ -47,6 +47,16 @@ class digraph(object):
priorities.append(priority)
priorities.sort()
+ def discard(self, node):
+ """
+ Like remove(), except it doesn't raises KeyError if the
+ node doesn't exist.
+ """
+ try:
+ self.remove(node)
+ except KeyError:
+ pass
+
def remove(self, node):
"""Removes the specified node from the digraph, also removing
and ties to other nodes in the digraph. Raises KeyError if the
--
1.8.3.2
^ permalink raw reply related [flat|nested] 13+ messages in thread* [gentoo-portage-dev] [PATCH 10/10] Solve some slot conflicts without backtracking
2014-01-29 15:33 [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking Sebastian Luther
` (8 preceding siblings ...)
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 09/10] Add digraph.discard Sebastian Luther
@ 2014-01-29 15:33 ` Sebastian Luther
2014-02-02 20:41 ` [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking Brian Dolbec
10 siblings, 0 replies; 13+ messages in thread
From: Sebastian Luther @ 2014-01-29 15:33 UTC (permalink / raw
To: gentoo-portage-dev
---
pym/_emerge/depgraph.py | 345 ++++++++++++++++++++-
pym/portage/tests/resolver/test_backtracking.py | 13 +-
pym/portage/tests/resolver/test_blocker.py | 48 +++
pym/portage/tests/resolver/test_slot_collisions.py | 75 ++++-
4 files changed, 457 insertions(+), 24 deletions(-)
create mode 100644 pym/portage/tests/resolver/test_blocker.py
diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index 1bb086b..b5fecec 100644
--- a/pym/_emerge/depgraph.py
+++ b/pym/_emerge/depgraph.py
@@ -3,6 +3,7 @@
from __future__ import print_function, unicode_literals
+import collections
import errno
import io
import logging
@@ -78,7 +79,7 @@ from _emerge.resolver.backtracking import Backtracker, BacktrackParameter
from _emerge.resolver.package_tracker import PackageTracker, PackageTrackerDbapiWrapper
from _emerge.resolver.slot_collision import slot_conflict_handler
from _emerge.resolver.circular_dependency import circular_dependency_handler
-from _emerge.resolver.output import Display
+from _emerge.resolver.output import Display, format_unmatched_atom
if sys.hexversion >= 0x3000000:
basestring = str
@@ -423,6 +424,8 @@ class _dynamic_depgraph_config(object):
self._complete_mode = False
self._slot_operator_deps = {}
self._package_tracker = PackageTracker()
+ # Track missed updates caused by solved conflicts.
+ self._conflict_missed_update = collections.defaultdict(dict)
for myroot in depgraph._frozen_config.trees:
self.sets[myroot] = _depgraph_sets()
@@ -769,7 +772,8 @@ class depgraph(object):
# missed update from each SLOT.
missed_updates = {}
for pkg, mask_reasons in \
- self._dynamic_config._runtime_pkg_mask.items():
+ chain(self._dynamic_config._runtime_pkg_mask.items(),
+ self._dynamic_config._conflict_missed_update.items()):
if pkg.installed:
# Exclude installed here since we only
# want to show available updates.
@@ -779,7 +783,8 @@ class depgraph(object):
for chosen_pkg in self._dynamic_config._package_tracker.match(
pkg.root, pkg.slot_atom):
any_selected = True
- if chosen_pkg >= pkg:
+ if chosen_pkg > pkg or (not chosen_pkg.installed and \
+ chosen_pkg.version == pkg.version):
missed_update = False
break
if any_selected and missed_update:
@@ -869,7 +874,7 @@ class depgraph(object):
self._show_merge_list()
msg = []
- msg.append("\nWARNING: One or more updates have been " + \
+ msg.append("\nWARNING: One or more updates/rebuilds have been " + \
"skipped due to a dependency conflict:\n\n")
indent = " "
@@ -879,22 +884,29 @@ class depgraph(object):
msg.append(" for %s" % (pkg.root,))
msg.append("\n\n")
- for parent, atom in parent_atoms:
- msg.append(indent)
- msg.append(str(pkg))
+ msg.append(indent)
+ msg.append(str(pkg))
+ msg.append(" conflicts with\n")
- msg.append(" conflicts with\n")
- msg.append(2*indent)
+ for parent, atom in parent_atoms:
if isinstance(parent,
(PackageArg, AtomArg)):
# For PackageArg and AtomArg types, it's
# redundant to display the atom attribute.
+ msg.append(2*indent)
msg.append(str(parent))
+ msg.append("\n")
else:
# Display the specific atom from SetArg or
# Package types.
- msg.append("%s required by %s" % (atom, parent))
- msg.append("\n")
+ atom, marker = format_unmatched_atom(
+ pkg, atom, self._pkg_use_enabled)
+
+ msg.append(2*indent)
+ msg.append("%s required by %s\n" % (atom, parent))
+ msg.append(2*indent)
+ msg.append(marker)
+ msg.append("\n")
msg.append("\n")
writemsg("".join(msg), noiselevel=-1)
@@ -956,6 +968,239 @@ class depgraph(object):
writemsg(line + '\n', noiselevel=-1)
writemsg('\n', noiselevel=-1)
+ def _solve_non_slot_operator_slot_conflicts(self):
+ """
+ This function solves slot conflicts which can
+ be solved by simply choosing one of the conflicting
+ and removing all the other ones.
+ It is able to solve somewhat more complex cases where
+ conflicts can only be solved simultaniously.
+ """
+ debug = "--debug" in self._frozen_config.myopts
+ debug = True
+ # List all conflicts. Ignore those that involve slot operator rebuilds
+ # as the logic there needs special slot conflict behavior which isn't
+ # provided by this function.
+ conflicts = []
+ for conflict in self._dynamic_config._package_tracker.slot_conflicts():
+ slot_key = conflict.root, conflict.atom
+ if slot_key not in self._dynamic_config._slot_operator_replace_installed:
+ conflicts.append(conflict)
+
+ if not conflicts:
+ return
+
+ # Get a set of all conflicting packages.
+ conflict_pkgs = set()
+ for conflict in conflicts:
+ conflict_pkgs.update(conflict)
+
+ # Get the list of other packages which are only
+ # required by conflict packages.
+ indirect_conflict_candidates = set()
+ for pkg in conflict_pkgs:
+ indirect_conflict_candidates.update(self._dynamic_config.digraph.child_nodes(pkg))
+ indirect_conflict_candidates.difference_update(conflict_pkgs)
+
+ indirect_conflict_pkgs = set()
+ while indirect_conflict_candidates:
+ pkg = indirect_conflict_candidates.pop()
+
+ only_conflict_parents = True
+ for parent, atom in self._dynamic_config._parent_atoms.get(pkg, []):
+ if parent not in conflict_pkgs and parent not in indirect_conflict_pkgs:
+ only_conflict_parents = False
+ break
+ if not only_conflict_parents:
+ continue
+
+ indirect_conflict_pkgs.add(pkg)
+ for child in self._dynamic_config.digraph.child_nodes(pkg):
+ if child in conflict_pkgs or child in indirect_conflict_pkgs:
+ continue
+ indirect_conflict_candidates.add(child)
+
+ # Create a graph containing the conflict packages
+ # and a special 'non_conflict_node' that represents
+ # all non-conflict packages.
+ conflict_graph = digraph()
+
+ non_conflict_node = "(non-conflict package)"
+ conflict_graph.add(non_conflict_node, None)
+
+ for pkg in chain(conflict_pkgs, indirect_conflict_pkgs):
+ conflict_graph.add(pkg, None)
+
+ # Add parent->child edges for each conflict package.
+ # Parents, which aren't conflict packages are represented
+ # by 'non_conflict_node'.
+ # If several conflicting packages are matched, but not all,
+ # add a tuple with the matched packages to the graph.
+ class or_tuple(tuple):
+ """
+ Helper class for debug printing.
+ """
+ def __str__(self):
+ return "(%s)" % ",".join(str(pkg) for pkg in self)
+
+ for conflict in conflicts:
+ all_parent_atoms = set()
+ for pkg in conflict:
+ all_parent_atoms.update(
+ self._dynamic_config._parent_atoms.get(pkg, []))
+
+ for parent, atom in all_parent_atoms:
+ is_arg_parent = isinstance(parent, AtomArg)
+
+ if parent not in conflict_pkgs and \
+ parent not in indirect_conflict_pkgs:
+ parent = non_conflict_node
+
+ atom_set = InternalPackageSet(
+ initial_atoms=(atom,), allow_repo=True)
+
+ matched = []
+ for pkg in conflict:
+ if atom_set.findAtomForPackage(pkg, \
+ modified_use=self._pkg_use_enabled(pkg)) and \
+ not (is_arg_parent and pkg.installed):
+ matched.append(pkg)
+ if len(matched) == len(conflict):
+ # All packages match.
+ continue
+ elif len(matched) == 1:
+ conflict_graph.add(matched[0], parent)
+ else:
+ # More than one packages matched, but not all.
+ conflict_graph.add(or_tuple(matched), parent)
+
+ for pkg in indirect_conflict_pkgs:
+ for parent, atom in self._dynamic_config._parent_atoms.get(pkg, []):
+ if parent not in conflict_pkgs and \
+ parent not in indirect_conflict_pkgs:
+ parent = non_conflict_node
+ conflict_graph.add(pkg, parent)
+
+ if debug:
+ writemsg_level(
+ "\n!!! Slot conflict graph:\n",
+ level=logging.DEBUG, noiselevel=-1)
+ conflict_graph.debug_print()
+
+ # Now select required packages. Collect them in the
+ # 'forced' set.
+ forced = set([non_conflict_node])
+ unexplored = set([non_conflict_node])
+ # or_tuples get special handling. We first explore
+ # all packages in the hope of having forced one of
+ # the packages in the tuple. This way we don't have
+ # to choose one.
+ unexplored_tuples = set()
+
+ while unexplored:
+ # Handle all unexplored packages.
+ while unexplored:
+ node = unexplored.pop()
+ for child in conflict_graph.child_nodes(node):
+ if child in forced:
+ continue
+ forced.add(child)
+ if isinstance(child, Package):
+ unexplored.add(child)
+ else:
+ unexplored_tuples.add(child)
+
+ # Now handle unexplored or_tuples. Move on with packages
+ # once we had choose one.
+ while unexplored_tuples:
+ nodes = unexplored_tuples.pop()
+ if any(node in forced for node in nodes):
+ # At least one of the packages in the
+ # tuple is already forced, which means the
+ # dependency represented by this tuple
+ # is satisfied.
+ continue
+
+ # We now have to choose one of packages in the tuple.
+ # In theory one could solve more conflicts if we'd be
+ # able to try different choices here, but that has lots
+ # of other problems. For now choose the package that was
+ # pulled first, as this should be the most desirable choice
+ # (otherwise it wouldn't have been the first one).
+ forced.add(child)
+ unexplored.add(child)
+ break
+
+ # Remove 'non_conflict_node' and or_tuples from 'forced'.
+ forced = set(pkg for pkg in forced if isinstance(pkg, Package))
+ non_forced = set(pkg for pkg in conflict_pkgs if pkg not in forced)
+
+ if debug:
+ writemsg_level(
+ "\n!!! Slot conflict solution:\n",
+ level=logging.DEBUG, noiselevel=-1)
+ for conflict in conflicts:
+ writemsg_level(
+ " Conflict: (%s, %s)\n" % (conflict.root, conflict.atom),
+ level=logging.DEBUG, noiselevel=-1)
+ for pkg in conflict:
+ if pkg in forced:
+ writemsg_level(
+ " keep: %s\n" % pkg,
+ level=logging.DEBUG, noiselevel=-1)
+ else:
+ writemsg_level(
+ " remove: %s\n" % pkg,
+ level=logging.DEBUG, noiselevel=-1)
+
+ broken_packages = set()
+ for pkg in non_forced:
+ for parent, atom in self._dynamic_config._parent_atoms.get(pkg, []):
+ if isinstance(parent, Package) and parent not in non_forced:
+ # Non-forcing set args are expected to be a parent of all
+ # packages in the conflict.
+ broken_packages.add(parent)
+ self._remove_pkg(pkg)
+
+ # Process the dependencies of choosen conflict packages
+ # again to properly account for blockers.
+ broken_packages.update(forced)
+
+ # Filter out broken packages which have been removed during
+ # recursive removal in self._remove_pkg.
+ broken_packages = list(pkg for pkg in broken_packages if pkg in broken_packages \
+ if self._dynamic_config._package_tracker.contains(pkg, installed=False))
+
+ self._dynamic_config._dep_stack.extend(broken_packages)
+
+ if broken_packages:
+ # Process dependencies. This cannot fail because we just ensured that
+ # the remaining packages satisfy all dependencies.
+ self._create_graph()
+
+ # Record missed updates.
+ for conflict in conflicts:
+ if not any(pkg in non_forced for pkg in conflict):
+ continue
+ for pkg in conflict:
+ if pkg not in non_forced:
+ continue
+
+ for other in conflict:
+ if other is pkg:
+ continue
+
+ for parent, atom in self._dynamic_config._parent_atoms.get(other, []):
+ atom_set = InternalPackageSet(
+ initial_atoms=(atom,), allow_repo=True)
+ if not atom_set.findAtomForPackage(pkg,
+ modified_use=self._pkg_use_enabled(pkg)):
+ self._dynamic_config._conflict_missed_update[pkg].setdefault(
+ "slot conflict", set())
+ self._dynamic_config._conflict_missed_update[pkg]["slot conflict"].add(
+ (parent, atom))
+
+
def _process_slot_conflicts(self):
"""
If there are any slot conflicts and backtracking is enabled,
@@ -963,6 +1208,9 @@ class depgraph(object):
is called, so that all relevant reverse dependencies are
available for use in backtracking decisions.
"""
+
+ self._solve_non_slot_operator_slot_conflicts()
+
for conflict in self._dynamic_config._package_tracker.slot_conflicts():
self._process_slot_conflict(conflict)
@@ -1286,9 +1534,29 @@ class depgraph(object):
selective = "selective" in self._dynamic_config.myparams
want_downgrade = None
+ def check_reverse_dependencies(existing_pkg, candidate_pkg):
+ """
+ Check if candidate_pkg satisfies all of existing_pkg's non-
+ slot operator parents.
+ """
+ for parent, atom in self._dynamic_config._parent_atoms.get(existing_pkg, []):
+ if atom.slot_operator == "=" and parent.built:
+ continue
+
+ atom_set = InternalPackageSet(initial_atoms=(atom,),
+ allow_repo=True)
+ if not atom_set.findAtomForPackage(candidate_pkg,
+ modified_use=self._pkg_use_enabled(candidate_pkg)):
+ return False
+ return True
+
+
for replacement_parent in self._iter_similar_available(dep.parent,
dep.parent.slot_atom, autounmask_level=autounmask_level):
+ if not check_reverse_dependencies(dep.parent, replacement_parent):
+ continue
+
selected_atoms = None
atoms = set()
@@ -1389,10 +1657,11 @@ class depgraph(object):
if unevaluated_atom not in selected_atoms:
continue
- if not insignificant:
+ if not insignificant and \
+ check_reverse_dependencies(dep.child, pkg):
+
candidate_pkg_atoms.append((pkg, unevaluated_atom))
candidate_pkgs.append(pkg)
-
replacement_candidates.append(candidate_pkg_atoms)
if all_candidate_pkgs is None:
all_candidate_pkgs = set(candidate_pkgs)
@@ -2113,6 +2382,56 @@ class depgraph(object):
dep_stack.append(pkg)
return 1
+
+ def _remove_pkg(self, pkg):
+ """
+ Remove a package and all its then parentless digraph
+ children from all depgraph datastructures.
+ """
+ try:
+ children = self._dynamic_config.digraph.child_nodes(pkg)
+ self._dynamic_config.digraph.remove(pkg)
+ except KeyError:
+ children = []
+
+ self._dynamic_config._package_tracker.discard_pkg(pkg)
+
+ self._dynamic_config._parent_atoms.pop(pkg, None)
+ self._dynamic_config._set_nodes.discard(pkg)
+
+ for child in children:
+ try:
+ self._dynamic_config._parent_atoms[child] = set((parent, atom) \
+ for (parent, atom) in self._dynamic_config._parent_atoms[child] \
+ if parent is not pkg)
+ except KeyError:
+ pass
+
+ # Remove slot operator dependencies.
+ slot_key = (pkg.root, pkg.slot_atom)
+ if slot_key in self._dynamic_config._slot_operator_deps:
+ self._dynamic_config._slot_operator_deps[slot_key] = \
+ [dep for dep in self._dynamic_config._slot_operator_deps[slot_key] \
+ if dep.child is not pkg]
+ if not self._dynamic_config._slot_operator_deps[slot_key]:
+ del self._dynamic_config._slot_operator_deps[slot_key]
+
+ # Remove blockers.
+ self._dynamic_config._blocker_parents.discard(pkg)
+ self._dynamic_config._irrelevant_blockers.discard(pkg)
+ self._dynamic_config._unsolvable_blockers.discard(pkg)
+ self._dynamic_config._blocked_pkgs.discard(pkg)
+ self._dynamic_config._blocked_world_pkgs.pop(pkg, None)
+
+ for child in children:
+ if not self._dynamic_config.digraph.parent_nodes(child):
+ self._remove_pkg(child)
+
+ # Clear caches.
+ self._dynamic_config._filtered_trees[pkg.root]["porttree"].dbapi._clear_cache()
+ self._dynamic_config._highest_pkg_cache.clear()
+
+
def _check_masks(self, pkg):
slot_key = (pkg.root, pkg.slot_atom)
diff --git a/pym/portage/tests/resolver/test_backtracking.py b/pym/portage/tests/resolver/test_backtracking.py
index 9dc37ac..3b69eda 100644
--- a/pym/portage/tests/resolver/test_backtracking.py
+++ b/pym/portage/tests/resolver/test_backtracking.py
@@ -1,4 +1,4 @@
-# Copyright 2010 Gentoo Foundation
+# Copyright 2010-2014 Gentoo Foundation
# Distributed under the terms of the GNU General Public License v2
from portage.tests import TestCase
@@ -31,7 +31,7 @@ class BacktrackingTestCase(TestCase):
playground.cleanup()
- def testHittingTheBacktrackLimit(self):
+ def testBacktrackNotNeeded(self):
ebuilds = {
"dev-libs/A-1": {},
"dev-libs/A-2": {},
@@ -45,17 +45,10 @@ class BacktrackingTestCase(TestCase):
ResolverPlaygroundTestCase(
["dev-libs/C", "dev-libs/D"],
all_permutations = True,
+ options = { "--backtrack": 1 },
mergelist = ["dev-libs/A-1", "dev-libs/B-1", "dev-libs/C-1", "dev-libs/D-1"],
ignore_mergelist_order = True,
success = True),
- #This one hits the backtrack limit. Be aware that this depends on the argument order.
- ResolverPlaygroundTestCase(
- ["dev-libs/D", "dev-libs/C"],
- options = { "--backtrack": 1 },
- mergelist = ["dev-libs/A-1", "dev-libs/B-1", "dev-libs/A-2", "dev-libs/B-2", "dev-libs/C-1", "dev-libs/D-1"],
- ignore_mergelist_order = True,
- slot_collision_solutions = [],
- success = False),
)
playground = ResolverPlayground(ebuilds=ebuilds)
diff --git a/pym/portage/tests/resolver/test_blocker.py b/pym/portage/tests/resolver/test_blocker.py
new file mode 100644
index 0000000..94a88b8
--- /dev/null
+++ b/pym/portage/tests/resolver/test_blocker.py
@@ -0,0 +1,48 @@
+# Copyright 2014 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+from portage.tests import TestCase
+from portage.tests.resolver.ResolverPlayground import ResolverPlayground, ResolverPlaygroundTestCase
+
+class SlotConflictWithBlockerTestCase(TestCase):
+
+ def testBlocker(self):
+ ebuilds = {
+ "dev-libs/A-1": { "DEPEND": "dev-libs/X" },
+ "dev-libs/B-1": { "DEPEND": "<dev-libs/X-2" },
+ "dev-libs/C-1": { "DEPEND": "<dev-libs/X-3" },
+
+ "dev-libs/X-1": { "EAPI": "2", "RDEPEND": "!=dev-libs/Y-1" },
+ "dev-libs/X-2": { "EAPI": "2", "RDEPEND": "!=dev-libs/Y-2" },
+ "dev-libs/X-3": { "EAPI": "2", "RDEPEND": "!=dev-libs/Y-3" },
+
+ "dev-libs/Y-1": { "SLOT": "1" },
+ "dev-libs/Y-2": { "SLOT": "2" },
+ "dev-libs/Y-3": { "SLOT": "3" },
+ }
+
+ installed = {
+ "dev-libs/Y-1": { "SLOT": "1" },
+ "dev-libs/Y-2": { "SLOT": "2" },
+ "dev-libs/Y-3": { "SLOT": "3" },
+ }
+
+ test_cases = (
+ ResolverPlaygroundTestCase(
+ ["dev-libs/A", "dev-libs/B", "dev-libs/C"],
+ options = { "--backtrack": 0 },
+ all_permutations = True,
+ success = True,
+ ambiguous_merge_order = True,
+ mergelist = ["dev-libs/X-1", "[uninstall]dev-libs/Y-1", "!=dev-libs/Y-1", \
+ ("dev-libs/A-1", "dev-libs/B-1", "dev-libs/C-1")]),
+ )
+
+ playground = ResolverPlayground(ebuilds=ebuilds,
+ installed=installed, debug=False)
+ try:
+ for test_case in test_cases:
+ playground.run_TestCase(test_case)
+ self.assertEqual(test_case.test_success, True, test_case.fail_msg)
+ finally:
+ playground.cleanup()
diff --git a/pym/portage/tests/resolver/test_slot_collisions.py b/pym/portage/tests/resolver/test_slot_collisions.py
index 95d68fe..fdd6dd6 100644
--- a/pym/portage/tests/resolver/test_slot_collisions.py
+++ b/pym/portage/tests/resolver/test_slot_collisions.py
@@ -1,4 +1,4 @@
-# Copyright 2010-2011 Gentoo Foundation
+# Copyright 2010-2011,2014 Gentoo Foundation
# Distributed under the terms of the GNU General Public License v2
from portage.tests import TestCase
@@ -153,3 +153,76 @@ class SlotCollisionTestCase(TestCase):
self.assertEqual(test_case.test_success, True, test_case.fail_msg)
finally:
playground.cleanup()
+
+ def testConnectedCollision(self):
+ """
+ Ensure that we are able to solve connected slot conflicts
+ which cannot be solved each on their own.
+ """
+ ebuilds = {
+ "dev-libs/A-1": { "RDEPEND": "=dev-libs/X-1" },
+ "dev-libs/B-1": { "RDEPEND": "dev-libs/X" },
+
+ "dev-libs/X-1": { "RDEPEND": "=dev-libs/Y-1" },
+ "dev-libs/X-2": { "RDEPEND": "=dev-libs/Y-2" },
+
+ "dev-libs/Y-1": { "PDEPEND": "=dev-libs/X-1" },
+ "dev-libs/Y-2": { "PDEPEND": "=dev-libs/X-2" },
+ }
+
+ test_cases = (
+ ResolverPlaygroundTestCase(
+ ["dev-libs/A", "dev-libs/B"],
+ all_permutations = True,
+ options = { "--backtrack": 0 },
+ success = True,
+ ambiguous_merge_order = True,
+ mergelist = ["dev-libs/Y-1", "dev-libs/X-1", ("dev-libs/A-1", "dev-libs/B-1")]),
+ )
+
+ playground = ResolverPlayground(ebuilds=ebuilds, debug=False)
+ try:
+ for test_case in test_cases:
+ playground.run_TestCase(test_case)
+ self.assertEqual(test_case.test_success, True, test_case.fail_msg)
+ finally:
+ playground.cleanup()
+
+
+ def testDeeplyConnectedCollision(self):
+ """
+ Like testConnectedCollision, except that there is another
+ level of dependencies between the two conflicts.
+ """
+ ebuilds = {
+ "dev-libs/A-1": { "RDEPEND": "=dev-libs/X-1" },
+ "dev-libs/B-1": { "RDEPEND": "dev-libs/X" },
+
+ "dev-libs/X-1": { "RDEPEND": "dev-libs/K" },
+ "dev-libs/X-2": { "RDEPEND": "dev-libs/L" },
+
+ "dev-libs/K-1": { "RDEPEND": "=dev-libs/Y-1" },
+ "dev-libs/L-1": { "RDEPEND": "=dev-libs/Y-2" },
+
+ "dev-libs/Y-1": { "PDEPEND": "=dev-libs/X-1" },
+ "dev-libs/Y-2": { "PDEPEND": "=dev-libs/X-2" },
+ }
+
+ test_cases = (
+ ResolverPlaygroundTestCase(
+ ["dev-libs/A", "dev-libs/B"],
+ all_permutations = True,
+ options = { "--backtrack": 0 },
+ success = True,
+ ignore_mergelist_order = True,
+ mergelist = ["dev-libs/Y-1", "dev-libs/X-1", "dev-libs/K-1", \
+ "dev-libs/A-1", "dev-libs/B-1"]),
+ )
+
+ playground = ResolverPlayground(ebuilds=ebuilds, debug=False)
+ try:
+ for test_case in test_cases:
+ playground.run_TestCase(test_case)
+ self.assertEqual(test_case.test_success, True, test_case.fail_msg)
+ finally:
+ playground.cleanup()
--
1.8.3.2
^ permalink raw reply related [flat|nested] 13+ messages in thread* Re: [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking
2014-01-29 15:33 [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking Sebastian Luther
` (9 preceding siblings ...)
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 10/10] Solve some slot conflicts without backtracking Sebastian Luther
@ 2014-02-02 20:41 ` Brian Dolbec
2014-02-02 21:04 ` Sebastian Luther
10 siblings, 1 reply; 13+ messages in thread
From: Brian Dolbec @ 2014-02-02 20:41 UTC (permalink / raw
To: gentoo-portage-dev
On Wed, 29 Jan 2014 16:33:04 +0100
Sebastian Luther <SebastianLuther@gmx.de> wrote:
> Hi all,
>
> as you may have noticed, emerge can in some cases take ages ( >5-10
> minutes) to resolve dependencies these days. This happens when lots
> of backtracking is required to solve slot conflicts and/or to
> schedule slot operator rebuilds. The problem is that the current
> backtracking implementation has to rebuild the entire dependency
> graph from scratch each time it backtracks.
>
> This series of patches is a first step into fixing this problem.
>
> What these patches do:
> Patch 1
> -------
> Adds a new data structure called package_tracker. This data
> structure is meant to replace several of the depgraph data structures.
> It has some new features not present in the existing data
> structures. 1) It can properly deal with several packages in the same
> slot. 2) It supports removal of previously added packages.
> 3) It tracks package conflicts automatically.
> 4) It has a more general concept of conflicts.
>
> Not all of the features are used for now, but they will make
> future changes easier.
>
> Patch 2-5
> ---------
> These patches replace the old data structures with the
> package tracker
>
> Patch 6-8
> ---------
> These patches fix several issues with emerge output. 6 and 8
> are somewhat independent of the other patches in this series. Patch 7
> introduces a new function used in Patch 10.
>
> Patch 9
> -------
> New function for patch 10.
>
> Patch 10
> --------
> This patch builds on top of all the previous patches. It
> introduces two new functions to the depgraph class. A function to
> remove packages that have previously been pulled in and a function to
> solve simple slot conflicts without backtracking.
>
> This should resolve most "no parents that aren't satisfied by
> other packages in this slot" slot conflicts.
>
> You may find these patches on github here:
> https://github.com/few/fews-portage-branch/tree/package_tracker
>
> Some numbers
> ------------
>
> My system has quite a number of conflicts that give emerge a hard time
> resolving dependencies.
>
> -uDN world
>
> Without the patches:
> * 11 unsolved slot conflicts
> * 2 unsolved blockers
> * takes 5 backtracking steps and then fails
>
> With the patches:
> * no unsolved slot conflicts or blockers
> * takes 7 backtracking steps and then succeeds
>
> In this case it actually became slower, but was finally able to find
> a solution.
>
> -e world
>
> Without the patches:
> * 5 unsolved slot conflicts
> * 1 unsolved blocker
> * takes 23 backtracking steps and then fails
>
> With the patches:
> * 1 unsolved slot conflict (From a quick look it looks like
> there really is no solution.)
> * takes 13 backtracking steps and then fails
>
> In this case it's a lot faster, but still unacceptably slow.
> The result is improved by solving 4 out of 5 conflicts.
>
>
>
I'm replying to all the series. I saw no glaring obvious mistakes.
This code is in areas I know little about, but your changes do seem
logical. Your additional fixes to these patches also look good.
If Mike/Arfrever gives the thumbs up. They're good to go in my opinion.
--
Brian Dolbec <dolsen>
^ permalink raw reply [flat|nested] 13+ messages in thread