[gentoo-portage-dev] [PATCH 01/10] Add resolver/package_tracker

[Sebastian Luther]

---
 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