* [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking
@ 2014-01-29 15:33 Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 01/10] Add resolver/package_tracker Sebastian Luther
` (10 more replies)
0 siblings, 11 replies; 13+ messages in thread
From: Sebastian Luther @ 2014-01-29 15:33 UTC (permalink / raw
To: gentoo-portage-dev
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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [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
* Re: [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking
2014-02-02 20:41 ` [gentoo-portage-dev] [PATCH 00/10] First steps to get rid of backtracking Brian Dolbec
@ 2014-02-02 21:04 ` Sebastian Luther
0 siblings, 0 replies; 13+ messages in thread
From: Sebastian Luther @ 2014-02-02 21:04 UTC (permalink / raw
To: gentoo-portage-dev
Am 02.02.2014 21:41, schrieb Brian Dolbec:
>
> 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.
I squashed the additional commits into the corresponding original
commits and pushed the result to the package_tracker2 branch [1].
[1] https://github.com/few/fews-portage-branch/commits/package_tracker2
>
> If Mike/Arfrever gives the thumbs up. They're good to go in my opinion.
>
^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2014-02-02 21:04 UTC | newest]
Thread overview: 13+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
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 ` [gentoo-portage-dev] [PATCH 03/10] Replace mydbapi " Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 04/10] Replace _slot_collision_info " Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 05/10] Replace _slot_collision_nodes " Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 06/10] Package.__str__: show slot/sub-slot Sebastian Luther
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 ` [gentoo-portage-dev] [PATCH 08/10] Some small output fixes for the slot conflict handler Sebastian Luther
2014-01-29 15:33 ` [gentoo-portage-dev] [PATCH 09/10] Add digraph.discard 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
2014-02-02 21:04 ` Sebastian Luther
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox