pym/portage_syntax.py pym/portage_dep.py: Filled out most of TargetGraph.

Still need to complete support for OR deps. Added a bit some more support
functions to Atom and DependSpec.

bin/test_target_graph.py: Just a script to help test and show the usage of
TargetGraph.

2 files changed, 231 insertions, 72 deletions

diff --git a/pym/portage_dep.py b/pym/portage_dep.py
index 8772568..cb84025 100644
--- a/pym/portage_dep.py
+++ b/pym/portage_dep.py
@@ -1,8 +1,8 @@
 # deps.py -- Portage dependency resolution functions
 # Copyright 2003-2004 Gentoo Foundation
 # Distributed under the terms of the GNU General Public License v2
-# $Header: /local/data/ulm/cvs/history/var/cvsroot/gentoo-src/portage/pym/portage_dep.py,v 1.31 2005/05/04 03:17:33 jstubbs Exp $
-cvs_id_string="$Id: portage_dep.py,v 1.31 2005/05/04 03:17:33 jstubbs Exp $"[5:-2]
+# $Header: /local/data/ulm/cvs/history/var/cvsroot/gentoo-src/portage/pym/portage_dep.py,v 1.32 2005/05/04 13:27:57 jstubbs Exp $
+cvs_id_string="$Id: portage_dep.py,v 1.32 2005/05/04 13:27:57 jstubbs Exp $"[5:-2]
 
 # DEPEND SYNTAX:
 #
@@ -276,6 +276,11 @@ class DependencyGraph(object):
 			self.graph[child][0].append(parent)
 			self.graph[parent][1].append(child)
 
+	def remove_relationship(self, parent, child):
+		"""Remove an existing relationship between two nodes."""
+		self.graph[child][0].remove(parent)
+		self.graph[parent][1].remove(child)
+
 	def get_relationships(self, node):
 		"""Retrieve parent and children lists of a node.
 
@@ -659,57 +664,57 @@ def match_from_list(mydep,candidate_list):
 	return mylist
 
 
-class GluePkg(portage_syntax.CPV):
-
-	def __init__(self, cpv, db, use, bdeps, rdeps):
-		portage_syntax.CPV.__init__(self, cpv)
-		self.db = db
-		self.use = use
-		self.bdeps = bdeps
-		self.rdeps = rdeps
+def prepare_prefdict(preferences):
+	myprefdict = {}
+	idx = 0
+	for atom in preferences:
+		if atom.cpv.key not in myprefdict:
+			myprefdict[atom.cpv.key] = []
+		myprefdict[atom.cpv.key].append((idx, atom))
+		idx += 1
+	myprefdict["____"] = idx
+	return myprefdict
 
 
-def transform_dependspec(dependspec, preferences):
-	def dotransform(dependspec, preferences):
+def transform_dependspec(dependspec, prefdict):
+	def dotransform(dependspec, prefdict):
 		dependspec = copy.copy(dependspec)
 		elements = dependspec.elements
 		dependspec.elements = []
 		neworder = []
-		prio = len(preferences)+1
-		idx = -1
+		prio = prefdict["____"]
 		for element in elements[:]:
 			if isinstance(element, portage_syntax.DependSpec):
-				neworder.append(dotransform(element, preferences))
+				neworder.append(dotransform(element, prefdict))
 				elements.remove(element)
-		for pref in preferences:
-			idx += 1
-			for element in elements[:]:
-				if pref.intersects(element):
-					if idx < prio:
-						prio = idx
-					if pref.encapsulates(element):
-						neworder.append((idx, element))
-						elements.remove(element)
-					else:
-						subdependspec = portage_syntax.DependSpec(element_class=portage_syntax.Atom)
-						if element.encapsulates(pref):
-							subsubdependspec = portage_syntax.DependSpec(element_class=portage_syntax.Atom)
-							subsubdependspec.add_element(pref)
-							subsubdependspec.add_element(element)
-							subdependspec.add_element(subsubdependspec)
+			elif element.cpv.key in prefdict:
+				for (idx, pref) in prefdict[element.cpv.key]:
+					if pref.intersects(element):
+						if idx < prio:
+							prio = idx
+						if pref.encapsulates(element):
+							neworder.append((idx, element))
+							elements.remove(element)
 						else:
-							subdependspec.add_element(pref)
-						subdependspec.add_element(element)
-						subdependspec.preferential = True
-						neworder.append((idx, subdependspec))
-						elements.remove(element)
+							subdependspec = portage_syntax.DependSpec(element_class=portage_syntax.Atom)
+							if element.encapsulates(pref):
+								subsubdependspec = portage_syntax.DependSpec(element_class=portage_syntax.Atom)
+								subsubdependspec.add_element(pref)
+								subsubdependspec.add_element(element)
+								subdependspec.add_element(subsubdependspec)
+							else:
+								subdependspec.add_element(pref)
+							subdependspec.add_element(element)
+							subdependspec.preferential = True
+							neworder.append((idx, subdependspec))
+							elements.remove(element)
 		neworder.sort()
 		for element in neworder:
 			dependspec.add_element(element[1])
 		for element in elements:
 			dependspec.add_element(element)
 		return (prio, dependspec)
-	return dotransform(dependspec, preferences)[1]
+	return dotransform(dependspec, prefdict)[1]
 
 
 class TargetGraph(object):
@@ -718,19 +723,125 @@ class TargetGraph(object):
 		# keys
 		self.graph = DependencyGraph()
 
-		# key : ([GLuePkg], [GluePkg], [Atom])
+		# key : ([GluePkg], [GluePkg], [Atom])
 		self.pkgrec = {}
-		self.unresolved = []
+
+		self.unmatched_atoms = {}
 
 	def add_package(self, pkg):
-		self.graph.add_node(pkg.key)
-		if not self.pkgrec.has_key(pkg.key):
-			self.pkgrec[pkg.key] = ([], [], [])
-		if self.pkgrec[pkg.key][0] or self.pkgrec[pkg.key][2]:
-			self.pkgrec[pkg.key][1].append(pkg)
-			self._validate(pkg.key)
+		key = pkg.key
+		if key not in self.pkgrec:
+			self.pkgrec[key] = ([], [pkg], [])
 		else:
-			self.pkgrec[pkg.key][0].append(pkg)
-
-	def _validate(self, key):
-		pkgs = self[pkg.key]
+			self.pkgrec[key][1].append(pkg)
+		self._recheck(key)
+
+	def _recheck(self, key):
+		(used, unused, unmatched) = self._select_pkgs(key)
+		for pkg in used:
+			if pkg not in self.pkgrec[key][0]:
+				self._promote_pkg(pkg)
+		for pkg in unused:
+			if pkg not in self.pkgrec[key][1]:
+				self._demote_pkg(pkg)
+		if unmatched:
+			self.unmatched_atoms[key] = unmatched
+		elif key in self.unmatched_atoms:
+			del self.unmatched_atoms[key]
+
+	def _select_pkgs(self, key):
+		allpkgs = self.pkgrec[key][0] + self.pkgrec[key][1]
+		unused = []
+		regular_atoms = []
+		unmatched = []
+		for atom in self.pkgrec[key][2]:
+			if atom.blocks:
+				for pkg in allpkgs[:]:
+					if atom.match(pkg):
+						allpkgs.remove(pkg)
+						unused.append(pkg)
+			elif atom not in regular_atoms:
+				regular_atoms.append(atom)
+
+		if regular_atoms:
+			slots = {}
+			for pkg in allpkgs:
+				if pkg.slot not in slots:
+					slots[pkg.slot] = []
+				slots[pkg.slot].append(pkg)
+
+			used_slots = []
+			multislot_atoms = []
+			for atom in regular_atoms:
+				matched_slots = []
+				for slot in slots:
+					for pkg in slots[slot]:
+						if atom.match(pkg):
+							matched_slots.append(slot)
+							break
+					if len(matched_slots) > 1:
+						multislot_atoms.append(atom)
+						break
+				if atom in multislot_atoms:
+					continue
+				if not matched_slots:
+					unmatched.append(atom)
+					continue
+				slot = matched_slots[0]
+				if slot not in used_slots:
+					used_slots.append(slot)
+				for idx in range(len(slots[slot])-1, -1, -1):
+					if not atom.match(slots[slot][idx]):
+						unused.append(slots[slot][idx])
+						del slots[slot][idx]
+			used = []
+			uncertain = []
+			for slot in slots:
+				if slot in used_slots:
+					used.extend(slots[slot])
+				else:
+					uncertain.extend(slots[slot])
+			for atom in multislot_atoms:
+				matched = False
+				for pkg in used[:]:
+					if atom.match(pkg):
+						matched = True
+						break
+				if matched:
+					continue
+				for pkg in uncertain:
+					if atom.match(pkg):
+						uncertain.remove(pkg)
+						used.append(pkg)
+						matched = True
+						break
+				if not matched:
+					unmatched.append(atom)
+			unused.extend(uncertain)
+		else:
+			used = allpkgs
+		return (used, unused, unmatched)
+
+	def _promote_pkg(self, pkg):
+		key = pkg.key
+		self.pkgrec[key][1].remove(pkg)
+		self.pkgrec[key][0].append(pkg)
+		if not pkg.rdeps.preferential:
+			for atom in pkg.rdeps.elements:
+				if atom.cpv.key not in self.pkgrec:
+					self.pkgrec[atom.cpv.key] = ([], [], [atom])
+				else:
+					self.pkgrec[atom.cpv.key][2].append(atom)
+				self._recheck(atom.cpv.key)
+
+	def _demote_pkg(self, pkg):
+		key = pkg.key
+		self.pkgrec[key][0].remove(pkg)
+		self.pkgrec[key][1].append(pkg)
+		if not pkg.rdeps.preferential:
+			for atom in pkg.rdeps.elements:
+				self.pkgrec[atom.cpv.key][2].remove(atom)
+				if not self.pkgrec[atom.cpv.key][0] and not self.pkgrec[atom.cpv.key][1] and not self.pkgrec[atom.cpv.key][2]:
+					del self.pkgrec[atom.cpv.key]
+				else:
+					self._recheck(atom.cpv.key)
diff --git a/pym/portage_syntax.py b/pym/portage_syntax.py
index ee31f40..7dee730 100644
--- a/pym/portage_syntax.py
+++ b/pym/portage_syntax.py
@@ -233,9 +233,17 @@ class Atom(object):
 	def __setattr__(self, name, value):
 		raise Exception()
 
+	def __eq__(self, other):
+		if isinstance(other, Atom):
+			return hash(self) == other.hash
+		return False
+
+	def __copy__(self):
+		return self
+
 	def __getattr__(self, name):
 
-		if not self.__dict__.has_key("category"):
+		if "operator" not in self.__dict__:
 
 			myatom = self.atomstr
 
@@ -300,6 +308,7 @@ class Atom(object):
 				return False
 			if self.cpv.revision != cpv.revision:
 				return False
+			return True
 
 		if self.operator == "~" and self.cpv.version == cpv.version:
 			return True
@@ -553,6 +562,33 @@ class DependSpec:
 		self.dependstr == dependstr
 		return dependstr
 
+	def flatten(self):
+		for element in self.elements:
+			if isinstance(element, DependSpec):
+				element.flatten()
+
+		self.compact()
+
+		if not self.preferential:
+			for idx in range(len(self.elements)):
+				if isinstance(self.elements[idx], DependSpec) and self.elements[idx].preferential:
+					otherelements = []
+					for idx2 in range(len(self.elements)):
+						if idx2 != idx:
+							otherelements.append(self.elements[idx2])
+					newelements = []
+					for element in self.elements[idx].elements:
+						dependspec = DependSpec(element_class=self.element_class)
+						dependspec.elements.extend(otherelements)
+						dependspec.elements.append(DependSpec(element_class=self.element_class))
+						dependspec.elements[-1].condition = self.elements[idx].condition
+						dependspec.elements[-1].elements.append(element)
+						newelements.append(dependspec)
+					self.elements = newelements
+					self.preferential = True
+					self.flatten()
+					return
+
 	def compact(self):
 		for element in self.elements:
 			if isinstance(element, DependSpec):
@@ -564,14 +600,12 @@ class DependSpec:
 			for x in range(len(self.elements)-1, -1, -1):
 				if isinstance(self.elements[x], DependSpec) and not len(self.elements[x].elements):
 					del self.elements[x]
-					changed = True
-			if not self.condition and not self.preferential:
-				for x in range(len(self.elements)-1, -1, -1):
-					if isinstance(self.elements[x], DependSpec):
-						if not self.elements[x].condition and not self.elements[x].preferential:
-							self.elements.extend(self.elements[x].elements)
-							del self.elements[x]
-							changed = True
+			for x in range(len(self.elements)-1, -1, -1):
+				if isinstance(self.elements[x], DependSpec):
+					if self.elements[x].condition == self.condition and self.elements[x].preferential == self.preferential:
+						self.elements.extend(self.elements[x].elements)
+						del self.elements[x]
+						changed = True
 
 		elements = self.elements[:]
 		del self.elements[:]
@@ -579,6 +613,9 @@ class DependSpec:
 			if element not in self.elements:
 				self.elements.append(element)
 
+		if self.preferential and len(self.elements) == 1:
+			self.preferential = False
+
 		if not self.condition and not self.preferential and len(self.elements) == 1 and isinstance(self.elements[0], DependSpec):
 			element = self.elements[0]
 			self.condition = element.condition
@@ -596,24 +633,22 @@ class DependSpec:
 		return dependspec
 
 	def resolve_conditions(self, truths):
-		if self.condition and self.condition not in truths:
-			del self.elements[:]
-			return
-
-		dependspec.preferential = self.preferential
-		for element in self.elements:
-			if isinstance(element, DependSpec):
-				element.resolve_conditions(truths)
+		mycondition = self.condition
+		self.condition = None
 
-		self.compact()
+		if mycondition:
+			if mycondition[0] == "!":
+				mycondition = mycondition[1:]
+				keep = (mycondition not in truths)
+			else:
+				keep = (mycondition in truths)
+			if not keep:
+				del self.elements[:]
+				return
 
-	def remove_preferentials(self):
-		if self.preferential and self.elements:
-			self.elements = [self.elements[0]]
 		for element in self.elements:
 			if isinstance(element, DependSpec):
-				element.remove_preferentials()
-		self.compact()
+				element.resolve_conditions(truths)
 
 	def add_element(self, element):
 		if isinstance(element, self.element_class) or (isinstance(element, DependSpec) and element.element_class is self.element_class):
@@ -625,3 +660,16 @@ class DependSpec:
 	def remove_element(self, element):
 		self.elements.remove(element)
 		self.dependstr = None
+
+
+class GluePkg(CPV):
+
+	def __init__(self, cpv, db, slot, use, bdeps, rdeps):
+		CPV.__init__(self, cpv)
+		self.__dict__["db"] = db
+		self.__dict__["slot"] = slot
+		self.__dict__["use"] = use
+		bdeps.flatten()
+		self.__dict__["bdeps"] = bdeps
+		rdeps.flatten()
+		self.__dict__["rdeps"] = rdeps