[gentoo-commits] proj/portage:master commit in: pym/_emerge/resolver/, pym/portage/tests/resolver/

[Sebastian Luther]

commit:     ea85cb655918ebdec65a49a2c0b1b4a8d4090208
Author:     Sebastian Luther <SebastianLuther <AT> gmx <DOT> de>
AuthorDate: Tue Jan 28 21:29:54 2014 +0000
Commit:     Sebastian Luther <SebastianLuther <AT> gmx <DOT> de >
CommitDate: Wed Feb  5 19:39:20 2014 +0000
URL:        http://git.overlays.gentoo.org/gitweb/?p=proj/portage.git;a=commit;h=ea85cb65

Add resolver/package_tracker

---
 pym/_emerge/resolver/package_tracker.py            | 301 +++++++++++++++++++++
 pym/portage/tests/resolver/test_package_tracker.py | 261 ++++++++++++++++++
 2 files changed, 562 insertions(+)

diff --git a/pym/_emerge/resolver/package_tracker.py b/pym/_emerge/resolver/package_tracker.py
new file mode 100644
index 0000000..5982750
--- /dev/null
+++ b/pym/_emerge/resolver/package_tracker.py
@@ -0,0 +1,301 @@
+# 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.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
+
+		if any(other is pkg for other in self._cp_pkg_map[cp_key]):
+			return
+
+		self._cp_pkg_map[cp_key].append(pkg)
+
+		if len(self._cp_pkg_map[cp_key]) > 1:
+			self._conflicts_cache = None
+			if len(self._cp_pkg_map[cp_key]) == 2:
+				self._multi_pkgs.append(cp_key)
+
+		self._replacing[pkg] = []
+		for installed in self._cp_vdb_pkg_map.get(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(cp_key, None)
+
+	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
+		if any(other is installed for other in self._cp_vdb_pkg_map[cp_key]):
+			return
+
+		self._cp_vdb_pkg_map[cp_key].append(installed)
+
+		for pkg in self._cp_pkg_map.get(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(cp_key, None)
+
+	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.get(cp_key, []).remove(pkg)
+		except ValueError:
+			raise KeyError(pkg)
+
+		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(cp_key, None)
+
+	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.
+		"""
+		cp_key = root, atom.cp
+		cache_key = root, atom, installed
+		try:
+			return iter(self._match_cache.get(cp_key, {})[cache_key])
+		except KeyError:
+			pass
+
+		candidates = self._cp_pkg_map.get(cp_key, [])[:]
+
+		if installed:
+			for installed in self._cp_vdb_pkg_map.get(cp_key, []):
+				if installed not in self._replaced_by:
+					candidates.append(installed)
+
+		ret = match_from_list(atom, candidates)
+		ret.sort(key=cmp_sort_key(lambda x, y: vercmp(x.version, y.version)))
+		self._match_cache[cp_key][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(list)
+				cpv_map = collections.defaultdict(list)
+				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].append(pkg)
+					cpv_map[cpv_key].append(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_key[0],
+								atom = cpv_key[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.get(cp_key, []):
+			if other is pkg:
+				return True
+
+		if installed:
+			for installed in self._cp_vdb_pkg_map.get(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)

diff --git a/pym/portage/tests/resolver/test_package_tracker.py b/pym/portage/tests/resolver/test_package_tracker.py
new file mode 100644
index 0000000..8fa3513
--- /dev/null
+++ b/pym/portage/tests/resolver/test_package_tracker.py
@@ -0,0 +1,261 @@
+# Copyright 2014 Gentoo Foundation
+# Distributed under the terms of the GNU General Public License v2
+
+import collections
+
+from portage.dep import Atom
+from portage.tests import TestCase
+from _emerge.resolver.package_tracker import PackageTracker, PackageTrackerDbapiWrapper
+
+class PackageTrackerTestCase(TestCase):
+
+	FakePackage = collections.namedtuple("FakePackage",
+		["root", "cp", "cpv", "slot", "slot_atom", "version", "repo"])
+
+	FakeConflict = collections.namedtuple("FakeConflict",
+		["description", "root", "pkgs"])
+
+	def make_pkg(self, root, atom, repo="test_repo"):
+		atom = Atom(atom)
+		slot_atom = Atom("%s:%s" % (atom.cp, atom.slot))
+		slot = atom.slot
+
+		return self.FakePackage(root=root, cp=atom.cp, cpv=atom.cpv,
+			slot=slot, slot_atom=slot_atom, version=atom.version, repo=repo)
+
+	def make_conflict(self, description, root, pkgs):
+		return self.FakeConflict(description=description, root=root, pkgs=pkgs)
+
+	def test_add_remove_discard(self):
+		p = PackageTracker()
+
+		x1 = self.make_pkg("/", "=dev-libs/X-1:0")
+		x2 = self.make_pkg("/", "=dev-libs/X-2:0")
+
+		p.add_pkg(x1)
+		self.assertTrue(x1 in p)
+		self.assertTrue(p.contains(x1, installed=True))
+		self.assertTrue(p.contains(x1, installed=False))
+		p.remove_pkg(x1)
+		self.assertTrue(x1 not in p)
+
+		p.add_pkg(x1)
+		self.assertTrue(x1 in p)
+		p.add_pkg(x1)
+		self.assertTrue(x1 in p)
+
+		self.assertRaises(KeyError, p.remove_pkg, x2)
+
+		p.add_pkg(x2)
+		self.assertTrue(x2 in p)
+		p.remove_pkg(x2)
+		self.assertTrue(x2 not in p)
+		p.discard_pkg(x2)
+		self.assertTrue(x2 not in p)
+		p.add_pkg(x2)
+		self.assertTrue(x2 in p)
+
+		all_pkgs = list(p.all_pkgs("/"))
+		self.assertEqual(len(all_pkgs), 2)
+		self.assertTrue(all_pkgs[0] is x1 and all_pkgs[1] is x2)
+
+		self.assertEqual(len(list(p.all_pkgs("/"))), 2)
+		self.assertEqual(len(list(p.all_pkgs("/xxx"))), 0)
+
+	def test_match(self):
+		p = PackageTracker()
+		x1 = self.make_pkg("/", "=dev-libs/X-1:0")
+		x2 = self.make_pkg("/", "=dev-libs/X-2:0")
+		x3 = self.make_pkg("/", "=dev-libs/X-3:1")
+
+		p.add_pkg(x2)
+		p.add_pkg(x1)
+
+		matches = list(p.match("/", Atom("=dev-libs/X-1")))
+		self.assertTrue(x1 in matches)
+		self.assertEqual(len(matches), 1)
+
+		matches = list(p.match("/", Atom("dev-libs/X")))
+		self.assertTrue(x1 is matches[0] and x2 is matches[1])
+		self.assertEqual(len(matches), 2)
+
+		matches = list(p.match("/xxx", Atom("dev-libs/X")))
+		self.assertEqual(len(matches), 0)
+
+		matches = list(p.match("/", Atom("dev-libs/Y")))
+		self.assertEqual(len(matches), 0)
+
+		p.add_pkg(x3)
+		matches = list(p.match("/", Atom("dev-libs/X")))
+		self.assertTrue(x1 is matches[0] and x2 is matches[1] and x3 is matches[2])
+		self.assertEqual(len(matches), 3)
+
+		p.remove_pkg(x3)
+		matches = list(p.match("/", Atom("dev-libs/X")))
+		self.assertTrue(x1 is matches[0] and x2 is matches[1])
+		self.assertEqual(len(matches), 2)
+
+	def test_dbapi_interface(self):
+		p = PackageTracker()
+		dbapi = PackageTrackerDbapiWrapper("/", p)
+		installed = self.make_pkg("/", "=dev-libs/X-0:0")
+		x1 = self.make_pkg("/", "=dev-libs/X-1:0")
+		x2 = self.make_pkg("/", "=dev-libs/X-2:0")
+		x3 = self.make_pkg("/", "=dev-libs/X-3:0")
+		x4 = self.make_pkg("/", "=dev-libs/X-4:6")
+		x5 = self.make_pkg("/xxx", "=dev-libs/X-5:6")
+
+		def check_dbapi(pkgs):
+			all_pkgs = set(dbapi)
+			self.assertEqual(len(all_pkgs), len(pkgs))
+
+			x_atom = "dev-libs/X"
+			y_atom = "dev-libs/Y"
+			matches = dbapi.cp_list(x_atom)
+			for pkg in pkgs:
+				if pkg.root == "/" and pkg.cp == x_atom:
+					self.assertTrue(pkg in matches)
+			self.assertTrue(not dbapi.cp_list(y_atom))
+			matches = dbapi.match(x_atom)
+			for pkg in pkgs:
+				if pkg.root == "/" and pkg.cp == x_atom:
+					self.assertTrue(pkg in matches)
+			self.assertTrue(not dbapi.match(y_atom))
+
+		check_dbapi([])
+
+		p.add_installed_pkg(installed)
+		check_dbapi([installed])
+
+		p.add_pkg(x1)
+		check_dbapi([x1])
+
+		p.remove_pkg(x1)
+		check_dbapi([installed])
+
+		dbapi.cpv_inject(x1)
+		check_dbapi([x1])
+
+		dbapi.cpv_inject(x2)
+		check_dbapi([x1, x2])
+
+		p.remove_pkg(x1)
+		check_dbapi([x2])
+
+		p.add_pkg(x5)
+		check_dbapi([x2])
+
+
+	def test_installed(self):
+		p = PackageTracker()
+		x1 = self.make_pkg("/", "=dev-libs/X-1:0")
+		x1b = self.make_pkg("/", "=dev-libs/X-1.1:0")
+		x2 = self.make_pkg("/", "=dev-libs/X-2:0")
+		x3 = self.make_pkg("/", "=dev-libs/X-3:1")
+
+		def check_installed(x, should_contain, num_pkgs):
+			self.assertEqual(x in p, should_contain)
+			self.assertEqual(p.contains(x), should_contain)
+			self.assertEqual(p.contains(x1, installed=True), should_contain)
+			self.assertEqual(p.contains(x1, installed=False), False)
+			self.assertEqual(len(list(p.all_pkgs("/"))), num_pkgs)
+
+		def check_matches(atom, expected):
+			matches = list(p.match("/", Atom(atom)))
+			self.assertEqual(len(matches), len(expected))
+			for x, y in zip(matches, expected):
+				self.assertTrue(x is y)
+
+		p.add_installed_pkg(x1)
+		check_installed(x1, True, 1)
+		check_matches("dev-libs/X", [x1])
+
+		p.add_installed_pkg(x1)
+		check_installed(x1, True, 1)
+		check_matches("dev-libs/X", [x1])
+
+		p.add_pkg(x2)
+		check_installed(x1, False, 1)
+		check_matches("dev-libs/X", [x2])
+
+		p.add_installed_pkg(x1)
+		check_installed(x1, False, 1)
+		check_matches("dev-libs/X", [x2])
+
+		p.add_installed_pkg(x1b)
+		check_installed(x1, False, 1)
+		check_installed(x1b, False, 1)
+		check_matches("dev-libs/X", [x2])
+
+		p.remove_pkg(x2)
+		check_installed(x1, True, 2)
+		check_installed(x1b, True, 2)
+		check_matches("dev-libs/X", [x1, x1b])
+
+	def test_conflicts(self):
+		p = PackageTracker()
+		installed1 = self.make_pkg("/", "=dev-libs/X-0:0")
+		installed2 = self.make_pkg("/", "=dev-libs/X-0.1:0")
+		x1 = self.make_pkg("/", "=dev-libs/X-1:0")
+		x2 = self.make_pkg("/", "=dev-libs/X-2:0")
+		x3 = self.make_pkg("/", "=dev-libs/X-3:0")
+		x4 = self.make_pkg("/", "=dev-libs/X-4:4")
+		x4b = self.make_pkg("/", "=dev-libs/X-4:4b::x-repo")
+
+		def check_conflicts(expected, slot_conflicts_only=False):
+			if slot_conflicts_only:
+				conflicts = list(p.slot_conflicts())
+			else:
+				conflicts = list(p.conflicts())
+			self.assertEqual(len(conflicts), len(expected))
+			for got, exp in zip(conflicts, expected):
+				self.assertEqual(got.description, exp.description)
+				self.assertEqual(got.root, exp.root)
+				self.assertEqual(len(got.pkgs), len(exp.pkgs))
+				self.assertEqual(len(got), len(exp.pkgs))
+				for x, y in zip(got.pkgs, exp.pkgs):
+					self.assertTrue(x is y)
+				for x, y in zip(got, exp.pkgs):
+					self.assertTrue(x is y)
+				for x in exp.pkgs:
+					self.assertTrue(x in got)
+
+		check_conflicts([])
+		check_conflicts([])
+
+		p.add_installed_pkg(installed1)
+		p.add_installed_pkg(installed2)
+		check_conflicts([])
+
+		p.add_pkg(x1)
+		check_conflicts([])
+		p.add_pkg(x2)
+		check_conflicts([self.make_conflict("slot conflict", "/", [x1, x2])])
+		p.add_pkg(x3)
+		check_conflicts([self.make_conflict("slot conflict", "/", [x1, x2, x3])])
+		p.remove_pkg(x3)
+		check_conflicts([self.make_conflict("slot conflict", "/", [x1, x2])])
+		p.remove_pkg(x2)
+		check_conflicts([])
+		p.add_pkg(x3)
+		check_conflicts([self.make_conflict("slot conflict", "/", [x1, x3])])
+		p.add_pkg(x2)
+		check_conflicts([self.make_conflict("slot conflict", "/", [x1, x3, x2])])
+
+		p.add_pkg(x4)
+		check_conflicts([self.make_conflict("slot conflict", "/", [x1, x3, x2])])
+
+		p.add_pkg(x4b)
+		check_conflicts(
+			[
+			self.make_conflict("slot conflict", "/", [x1, x3, x2]),
+			self.make_conflict("cpv conflict", "/", [x4, x4b]),
+			]
+			)
+
+		check_conflicts(
+			[
+			self.make_conflict("slot conflict", "/", [x1, x3, x2]),
+			],
+			slot_conflicts_only=True
+			)