Attachment #97307 for bug #147766




	# recurse:   go into the dependencies
	# deep:      go into the dependencies of already merged packages
	# empty:     pretend nothing is merged
	myparams=["self","recurse","selective"]
	add=[]
	sub=[]
	if "--update" in myopts or myaction in ("system", "world"):
		add.extend(["empty"])
	if "--emptytree" in myopts:
		add.extend(["empty"])
		sub.extend(["selective"])
	if "--nodeps" in myopts:
		sub.extend(["recurse"])
	if "--noreplace" in myopts:
		add.extend(["selective"])
	if "--deep" in myopts:
		add.extend(["deep"])
	if "--selective" in myopts:
		add.extend(["selective"])
	if myaction in ["world","system"]:
		add.extend(["selective"])
	elif myaction in ["depclean"]:
		add.extend(["empty"])
		sub.extend(["selective"])

					"--getbinpkg" in self.myopts,
					"--getbinpkgonly" in self.myopts)

	def create(self,mybigkey,myparent=None,addme=1,myuse=None,soft_dep=False,arg=None):
		"""
		Fills the digraph with nodes comprised of packages to merge.
		mybigkey is the package spec of the package to merge.

			if addme and jbigkey != myparent:
				# Refuse to make a node depend on itself so that the we don't
				# don't create a bogus circular dependency in self.altlist().
				self.digraph.addnode(jbigkey, myparent, soft_dep=soft_dep)
			return 1
		jbigkey = " ".join(mybigkey) + " nomerge"
		if self.digraph.hasnode(jbigkey):
			self.digraph.addnode(jbigkey, myparent, soft_dep=soft_dep)
			return 1
		
		self.spinner.update()

				if self.mydbapi[parent_root].match(mykey) or \
					self.trees[parent_root]["vartree"].dbapi.match(mykey):
					mybigkey.append(myparent.split()[2])
					self.digraph.addnode(" ".join(mybigkey), myparent, soft_dep=soft_dep)
			return 1
		else:
			mydbapi = self.trees[myroot][self.pkg_tree_map[mytype]].dbapi

				    installed we skip merging it."""
				if "self" not in self.myparams or \
					("selective" in self.myparams and \
					not arg and vardbapi.cpv_exists(mykey)):
					merging=0
			elif "selective" in self.myparams and vardbapi.cpv_exists(mykey):
				merging=0

		""" At this point, we have either hit a blocker and returned, found the package in the
		    depgraph already and returned, or we are here.  Whether we are merging or not; we must
		    add the package to the depgraph; so we do that here. """
		self.digraph.addnode(string.join(mybigkey),myparent,soft_dep=soft_dep)
		
		""" This section determines whether we go deeper into dependencies or not.
		    We want to go deeper on a few occasions:

		""" We have retrieve the dependency information, now we need to recursively
		    process them.  DEPEND gets processed for root = "/", {R,P}DEPEND in myroot. """
		
		mydep={}
		mp=string.join(mybigkey)

		try:
			if not self.select_dep("/",edepend["DEPEND"],myparent=mp,myuse=myuse):
				return 0
			if not self.select_dep(myroot,edepend["RDEPEND"],myparent=mp,myuse=myuse,soft_deps=True):
				return 0
			else:
				mydep["/"]=edepend["DEPEND"]
				mydep[myroot]=edepend["RDEPEND"]
				if not self.select_dep("/",mydep["/"],myparent=mp,myuse=myuse):
					return 0
				if not self.select_dep(myroot,mydep[myroot],myparent=mp,myuse=myuse):
					return 0
	
			if edepend.has_key("PDEPEND") and edepend["PDEPEND"]:
				# Post Depend -- Add to the list without a parent, as it depends
				# on a package being present AND must be built after that package.
				if not self.select_dep(myroot,edepend["PDEPEND"],myuse=myuse,soft_deps=True):
					return 0
		except ValueError, e:
			pkgs = e.args[0]

				sys.stderr.flush()

				try:
					if "--noreplace" in self.myopts:
						arg = None
					else:
						arg = x
					self.mysd = self.select_dep(myroot, mykey, arg=arg)
				except portage_exception.MissingSignature, e:
					portage.writemsg("\n\n!!! A missing gpg signature is preventing portage from calculating the\n")
					portage.writemsg("!!! required dependencies. This is a security feature enabled by the admin\n")


		missing=0
		if "--usepkgonly" in self.myopts:
			for x in self.digraph.all_nodes():
				xs=string.split(x," ")
				if (xs[0] != "binary") and (xs[3]=="merge"):
					if missing == 0:

					if curslot == myslot:
						return match

	def select_dep(self,myroot,depstring,myparent=None,arg=None,myuse=None,raise_on_missing=False,soft_deps=False):
		""" Given a depstring, create the depgraph such that all dependencies are satisfied.
		    myroot = $ROOT from environment, where {R,P}DEPENDs are merged to.
		    myparent = the node whose depstring is being passed in


		portdb = self.trees[myroot]["porttree"].dbapi
		bindb  = self.trees[myroot]["bintree"].dbapi
		vardb  = self.trees[myroot]["vartree"].dbapi
		pkgsettings = self.pkgsettings[myroot]

		if "--debug" in self.myopts:

			mycheck = portage.dep_check(depstring, self.mydbapi[myroot],
				pkgsettings, myuse=myuse,
				use_binaries=("--usepkgonly" in self.myopts),
				myroot=myroot, trees=self.trees, return_all_deps=True)

			if not mycheck[0]:
				mymerge=[]

				self.pkgsettings[p_root].setinst(p_key,
					self.trees[p_root][self.pkg_tree_map[p_type]].dbapi)

		if not mymerge:
			return 1

		if "--debug" in self.myopts:
			print "Candidates:",mymerge
		for x in mymerge:

				selected_pkg = ["blocks", myroot, x[1:], None]
			else:
				#We are not processing a blocker but a normal dependency
				pkg_key = portage.dep_getkey(x)
				if pkg_key in pkgsettings.pprovideddict and \
					portage.match_from_list(
						x, pkgsettings.pprovideddict[pkg_key]):
						continue

				# List of acceptable packages, ordered by type preference.
				matched_packages = []
				myeb_matches = portdb.xmatch("match-visible", x)


			if myparent:
				#we are a dependency, so we want to be unconditionally added
				soft_dep = soft_deps or vardb.match(x)
				if not self.create(selected_pkg[0:3], myparent,
					myuse=selected_pkg[-1], soft_dep=soft_dep, arg=arg):
					return 0
			else:
				#if mysource is not set, then we are a command-line dependency and should not be added
				#if --onlydeps is specified.
				if not self.create(selected_pkg[0:3], myparent,
					addme=("--onlydeps" not in self.myopts),
					myuse=selected_pkg[-1], arg=arg):
					return 0

		if "--debug" in self.myopts:

		while (not mygraph.empty()):
			mycurkey=mygraph.firstzero()
			if not mycurkey:
				installables = mygraph.leaf_nodes(ignore_soft_deps=True)
				if not installables:
					print "!!! Error: circular dependencies:"
					print
					for x in mygraph.allnodes():
						for y in mygraph.parent_nodes(x):
							print y,"depends on",x
						print
					sys.exit(1)
				mycurkey = installables[0]
			splitski=string.split(mycurkey)
			#I'm not sure of the significance of the following lines (vestigal?) so I'm commenting 'em out.
			#These lines remove already-merged things from our alt-list





class digraph:
	def __init__(self):
		"""Create an empty digraph"""
		
		# { node : ( { child : soft_dep } , { parent : soft_dep } ) }
		self.nodes = {}
		self.order = []
		if not self.dict.has_key(mykey):
			self.okeys.append(mykey)
			if myparent is None:
				self.dict[mykey]=[0,[]]
			else:
				self.dict[mykey]=[0,[myparent]]
				self.dict[myparent][0]=self.dict[myparent][0]+1
			return
		if myparent and (not myparent in self.dict[mykey][1]):
			self.dict[mykey][1].append(myparent)
			self.dict[myparent][0]=self.dict[myparent][0]+1

	def add(self, node, parent, soft_dep=False):
		"""Adds the specified node with the specified parent.
		
		If the dep is a soft-dep and the node already has a hard
		relationship to the parent, the relationship is left as hard."""
		
		if node not in self.nodes:
			self.nodes[node] = ({}, {})
			self.order.append(node)
		
		if not parent:
			return
		
		if parent not in self.nodes:
			self.nodes[parent] = ({}, {})
			self.order.append(parent)
		
		if parent in self.nodes[node][1]:
			if not soft_dep:
				self.nodes[node][1][parent] = False
		else:
			self.nodes[node][1][parent] = soft_dep
		
		if node in self.nodes[parent][0]:
			if not soft_dep:
				self.nodes[parent][0][node] = False
		else:
			self.nodes[parent][0][node] = soft_dep

	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
		node doesn't exist."""
		
		if node not in self.nodes:
			raise KeyError(node)
		
		for parent in self.nodes[node][1]:
			del self.nodes[parent][0][node]
		for child in self.nodes[node][0]:
			del self.nodes[child][1][node]
		
		del self.nodes[node]
		self.order.remove(node)

	def contains(self, node):
		"""Checks if the digraph contains mynode"""
		return node in self.nodes

	def all_nodes(self):
		"""Return a list of all nodes in the graph"""
		return self.order[:]

	def child_nodes(self, node):
		"""Return all children of the specified node"""
		return self.nodes[node][0].keys()

	def parent_nodes(self, node):
		"""Return all parents of the specified node"""
		return self.nodes[node][1].keys()

	def leaf_nodes(self, ignore_soft_deps=False):
		"""Return all nodes that have no children
		
		If ignore_soft_deps is True, soft deps are not counted as
		children in calculations."""
		
		leaf_nodes = []
		for node in self.order:
			is_leaf_node = True
			for child in self.nodes[node][0]:
				if not (ignore_soft_deps and self.nodes[node][0][child]):
					is_leaf_node = False
					break
			if is_leaf_node:
				leaf_nodes.append(node)
		return leaf_nodes

	def is_empty(self):
		"""Checks if the digraph is empty"""
		return len(self.nodes) == 0

	def clone(self):
		clone = digraph()
		clone.nodes = copy.deepcopy(self.nodes)
		clone.order = self.order[:]
		return clone

	# Backward compatibility
	addnode = add
	allnodes = all_nodes
	allzeros = leaf_nodes
	hasnode = contains
	empty = is_empty
	copy = clone

	def delnode(self, node):
		try:
			self.remove(node)
		except KeyError:
			pass

	def firstzero(self):
		leaf_nodes = self.leaf_nodes()
		if leaf_nodes:
			return leaf_nodes[0]
				return x
		return None

	def depth(self, mykey):
		depth=0
		while (self.dict[mykey][1]):
			depth=depth+1
			mykey=self.dict[mykey][1][0]
		return depth

	def allzeros(self):
		"returns all nodes with zero references, or NULL if no such node exists"
		zerolist = []
		for x in self.dict.keys():
			mys = string.split(x)
			if mys[0] != "blocks" and self.dict[x][0]==0:
				zerolist.append(x)
		return zerolist

	def hasallzeros(self):
		return len(self.leaf_nodes() == 0)
		zerolist = []
		for x in self.dict.keys():
			if self.dict[x][0]!=0:
				return 0
		return 1

	def depth(self, node):
		"""Find how many nodes are in the parent chain of the passed node
		
		This method doesn't make sense unless there is no more than one
		parent for each node. As this digraph is capable of having multiple
		parents on a node, this implementation chooses an arbitrary parent
		for calculations, stopping as soon as a loop is detected in order
		to mimic the sorts of counts that would have previously been
		returned.
		
		This method is only used by emerge's --tree option. That option
		needs to be reworked to not use this so that this method can be
		removed altogether."""
		
		parents = {}
		while self.nodes[node][1]:
			parent = self.nodes[node][1].keys()[0]
			if parent in parents:
				break
			parents[parent] = True
			node = parent
		return len(parents)
	
	def debug_print(self):
		for node in self.nodes:
			print node,
			if self.nodes[node][0]:
				print "depends on"
			else:
				print "(no children)"
			for child in self.nodes[node][0]:
				print "  ",child,
				if self.nodes[node][0][child]:
					print "(hard)"
				else:
					print "(soft)"

	def hasnode(self,mynode):
		return self.dict.has_key(mynode)

	def copy(self):
		mygraph=digraph()
		for x in self.dict.keys():
			mygraph.dict[x]=self.dict[x][:]
			mygraph.okeys=self.okeys[:]
		return mygraph

def elog_process(cpv, mysettings):
	mylogfiles = listdir(mysettings["T"]+"/logging/")

				return 0
		return 1

def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None, return_all_deps=False):
	"""Takes an unreduced and reduced deplist and removes satisfied dependencies.
	Returned deplist contains steps that must be taken to satisfy dependencies."""
	if trees is None:

		for (dep, satisfied) in zip(unreduced, reduced):
			if isinstance(dep, list):
				unresolved += dep_zapdeps(dep, satisfied, myroot,
					use_binaries=use_binaries, trees=trees, return_all_deps=return_all_deps)
			elif not satisfied or return_all_deps:
				unresolved.append(dep)
		return unresolved


		mydep, mydb=mydb, use_cache=use_cache, settings=settings) + postfix

def dep_check(depstring, mydbapi, mysettings, use="yes", mode=None, myuse=None,
	use_cache=1, use_binaries=0, myroot="/", trees=None, return_all_deps=False):
	"""Takes a depend string and parses the condition."""

	#check_config_instance(mysettings)

	writemsg("\n\n\n", 1)
	writemsg("mysplit:  %s\n" % (mysplit), 1)
	writemsg("mysplit2: %s\n" % (mysplit2), 1)
	myeval=dep_eval(mysplit2)
	writemsg("myeval:   %s\n" % (myeval), 1)

	myzaps = dep_zapdeps(mysplit, mysplit2, myroot,
		use_binaries=use_binaries, trees=trees, return_all_deps=return_all_deps)
	mylist = flatten(myzaps)
	writemsg("myzaps:   %s\n" % (myzaps), 1)
	writemsg("mylist:   %s\n" % (mylist), 1)
	#remove duplicates
	mydict={}
	for x in mylist:
		mydict[x]=1
	writemsg("mydict:   %s\n" % (mydict), 1)
	return [1,mydict.keys()]
			mydict[x]=1
		writemsg("mydict:   %s\n" % (mydict), 1)
		return [1,mydict.keys()]

def dep_wordreduce(mydeplist,mysettings,mydbapi,mode,use_cache=1):
	"Reduces the deplist to ones and zeros"

Return to bug 147766

Lines 352-375 Link Here

(-)portage.orig/bin/emerge (-43 / +41 lines)
352	# recurse: go into the dependencies	352	# recurse: go into the dependencies
353	# deep: go into the dependencies of already merged packages	353	# deep: go into the dependencies of already merged packages
354	# empty: pretend nothing is merged	354	# empty: pretend nothing is merged
355	myparams=["self","recurse"]	355	myparams=["self","recurse","selective"]
356	add=[]	356	add=[]
357	sub=[]	357	sub=[]
358	if "--update" in myopts or myaction in ("system", "world"):	358	if "--update" in myopts or myaction in ("system", "world"):
359	add.extend(["selective","empty"])	359	add.extend(["empty"])
360	if "--emptytree" in myopts:	360	if "--emptytree" in myopts:
361	add.extend(["empty"])	361	add.extend(["empty"])
362	sub.extend(["selective"])	362	sub.extend(["selective"])
363	if "--nodeps" in myopts:	363	if "--nodeps" in myopts:
364	sub.extend(["recurse"])	364	sub.extend(["recurse"])
365	if "--noreplace" in myopts:
366	add.extend(["selective"])
367	if "--deep" in myopts:	365	if "--deep" in myopts:
368	add.extend(["deep"])	366	add.extend(["deep"])
369	if "--selective" in myopts:
370	add.extend(["selective"])
371	if myaction in ["world","system"]:
372	add.extend(["selective"])
373	elif myaction in ["depclean"]:	367	elif myaction in ["depclean"]:
374	add.extend(["empty"])	368	add.extend(["empty"])
375	sub.extend(["selective"])	369	sub.extend(["selective"])
Lines 679-685 Link Here
679	"--getbinpkg" in self.myopts,	673	"--getbinpkg" in self.myopts,
680	"--getbinpkgonly" in self.myopts)	674	"--getbinpkgonly" in self.myopts)
681		675
682	def create(self,mybigkey,myparent=None,addme=1,myuse=None):	676	def create(self,mybigkey,myparent=None,addme=1,myuse=None,soft_dep=False,arg=None):
683	"""	677	"""
684	Fills the digraph with nodes comprised of packages to merge.	678	Fills the digraph with nodes comprised of packages to merge.
685	mybigkey is the package spec of the package to merge.	679	mybigkey is the package spec of the package to merge.
Lines 697-706 Link Here
697	if addme and jbigkey != myparent:	691	if addme and jbigkey != myparent:
698	# Refuse to make a node depend on itself so that the we don't	692	# Refuse to make a node depend on itself so that the we don't
699	# don't create a bogus circular dependency in self.altlist().	693	# don't create a bogus circular dependency in self.altlist().
700	self.digraph.addnode(jbigkey, myparent)	694	self.digraph.addnode(jbigkey, myparent, soft_dep=soft_dep)
701	return 1	695	return 1
702	jbigkey = " ".join(mybigkey) + " nomerge"	696	jbigkey = " ".join(mybigkey) + " nomerge"
703	if self.digraph.hasnode(jbigkey):	697	if self.digraph.hasnode(jbigkey):
		698	self.digraph.addnode(jbigkey, myparent, soft_dep=soft_dep)
704	return 1	699	return 1
705		700
706	self.spinner.update()	701	self.spinner.update()
Lines 723-729 Link Here
723	if self.mydbapi[parent_root].match(mykey) or \	718	if self.mydbapi[parent_root].match(mykey) or \
724	self.trees[parent_root]["vartree"].dbapi.match(mykey):	719	self.trees[parent_root]["vartree"].dbapi.match(mykey):
725	mybigkey.append(myparent.split()[2])	720	mybigkey.append(myparent.split()[2])
726	self.digraph.addnode(" ".join(mybigkey), myparent)	721	self.digraph.addnode(" ".join(mybigkey), myparent, soft_dep=soft_dep)
727	return 1	722	return 1
728	else:	723	else:
729	mydbapi = self.trees[myroot][self.pkg_tree_map[mytype]].dbapi	724	mydbapi = self.trees[myroot][self.pkg_tree_map[mytype]].dbapi
Lines 744-750 Link Here
744	installed we skip merging it."""	739	installed we skip merging it."""
745	if "self" not in self.myparams or \	740	if "self" not in self.myparams or \
746	("selective" in self.myparams and \	741	("selective" in self.myparams and \
747	vardbapi.cpv_exists(mykey)):	742	not arg and vardbapi.cpv_exists(mykey)):
748	merging=0	743	merging=0
749	elif "selective" in self.myparams and vardbapi.cpv_exists(mykey):	744	elif "selective" in self.myparams and vardbapi.cpv_exists(mykey):
750	merging=0	745	merging=0
Lines 782-788 Link Here
782	""" At this point, we have either hit a blocker and returned, found the package in the	777	""" At this point, we have either hit a blocker and returned, found the package in the
783	depgraph already and returned, or we are here. Whether we are merging or not; we must	778	depgraph already and returned, or we are here. Whether we are merging or not; we must
784	add the package to the depgraph; so we do that here. """	779	add the package to the depgraph; so we do that here. """
785	self.digraph.addnode(string.join(mybigkey),myparent)	780	self.digraph.addnode(string.join(mybigkey),myparent,soft_dep=soft_dep)
786		781
787	""" This section determines whether we go deeper into dependencies or not.	782	""" This section determines whether we go deeper into dependencies or not.
788	We want to go deeper on a few occasions:	783	We want to go deeper on a few occasions:
Lines 815-840 Link Here
815	""" We have retrieve the dependency information, now we need to recursively	810	""" We have retrieve the dependency information, now we need to recursively
816	process them. DEPEND gets processed for root = "/", {R,P}DEPEND in myroot. """	811	process them. DEPEND gets processed for root = "/", {R,P}DEPEND in myroot. """
817		812
818	mydep={}
819	mp=string.join(mybigkey)	813	mp=string.join(mybigkey)
820		814
821	try:	815	try:
822	if myroot=="/":	816	if not self.select_dep("/",edepend["DEPEND"],myparent=mp,myuse=myuse):
823	mydep["/"]=edepend["DEPEND"]+" "+edepend["RDEPEND"]	817	return 0
824	if not self.select_dep("/",mydep["/"],myparent=mp,myuse=myuse):	818	if not self.select_dep(myroot,edepend["RDEPEND"],myparent=mp,myuse=myuse,soft_deps=True):
825	return 0	819	return 0
826	else:
827	mydep["/"]=edepend["DEPEND"]
828	mydep[myroot]=edepend["RDEPEND"]
829	if not self.select_dep("/",mydep["/"],myparent=mp,myuse=myuse):
830	return 0
831	if not self.select_dep(myroot,mydep[myroot],myparent=mp,myuse=myuse):
832	return 0
833
834	if edepend.has_key("PDEPEND") and edepend["PDEPEND"]:	820	if edepend.has_key("PDEPEND") and edepend["PDEPEND"]:
835	# Post Depend -- Add to the list without a parent, as it depends	821	# Post Depend -- Add to the list without a parent, as it depends
836	# on a package being present AND must be built after that package.	822	# on a package being present AND must be built after that package.
837	if not self.select_dep(myroot,edepend["PDEPEND"],myuse=myuse):	823	if not self.select_dep(myroot,edepend["PDEPEND"],myuse=myuse,soft_deps=True):
838	return 0	824	return 0
839	except ValueError, e:	825	except ValueError, e:
840	pkgs = e.args[0]	826	pkgs = e.args[0]
Lines 940-946 Link Here
940	sys.stderr.flush()	926	sys.stderr.flush()
941		927
942	try:	928	try:
943	self.mysd = self.select_dep(myroot, mykey, arg=x)	929	if "--noreplace" in self.myopts:
		930	arg = None
		931	else:
		932	arg = x
		933	self.mysd = self.select_dep(myroot, mykey, arg=arg)
944	except portage_exception.MissingSignature, e:	934	except portage_exception.MissingSignature, e:
945	portage.writemsg("\n\n!!! A missing gpg signature is preventing portage from calculating the\n")	935	portage.writemsg("\n\n!!! A missing gpg signature is preventing portage from calculating the\n")
946	portage.writemsg("!!! required dependencies. This is a security feature enabled by the admin\n")	936	portage.writemsg("!!! required dependencies. This is a security feature enabled by the admin\n")
Lines 969-975 Link Here
969		959
970	missing=0	960	missing=0
971	if "--usepkgonly" in self.myopts:	961	if "--usepkgonly" in self.myopts:
972	for x in self.digraph.dict.keys():	962	for x in self.digraph.all_nodes():
973	xs=string.split(x," ")	963	xs=string.split(x," ")
974	if (xs[0] != "binary") and (xs[3]=="merge"):	964	if (xs[0] != "binary") and (xs[3]=="merge"):
975	if missing == 0:	965	if missing == 0:
Lines 993-999 Link Here
993	if curslot == myslot:	983	if curslot == myslot:
994	return match	984	return match
995		985
996	def select_dep(self,myroot,depstring,myparent=None,arg=None,myuse=None,raise_on_missing=False):	986	def select_dep(self,myroot,depstring,myparent=None,arg=None,myuse=None,raise_on_missing=False,soft_deps=False):
997	""" Given a depstring, create the depgraph such that all dependencies are satisfied.	987	""" Given a depstring, create the depgraph such that all dependencies are satisfied.
998	myroot = $ROOT from environment, where {R,P}DEPENDs are merged to.	988	myroot = $ROOT from environment, where {R,P}DEPENDs are merged to.
999	myparent = the node whose depstring is being passed in	989	myparent = the node whose depstring is being passed in
Lines 1006-1011 Link Here
1006		996
1007	portdb = self.trees[myroot]["porttree"].dbapi	997	portdb = self.trees[myroot]["porttree"].dbapi
1008	bindb = self.trees[myroot]["bintree"].dbapi	998	bindb = self.trees[myroot]["bintree"].dbapi
		999	vardb = self.trees[myroot]["vartree"].dbapi
1009	pkgsettings = self.pkgsettings[myroot]	1000	pkgsettings = self.pkgsettings[myroot]
1010		1001
1011	if "--debug" in self.myopts:	1002	if "--debug" in self.myopts:
Lines 1020-1026 Link Here
1020	mycheck = portage.dep_check(depstring, self.mydbapi[myroot],	1011	mycheck = portage.dep_check(depstring, self.mydbapi[myroot],
1021	pkgsettings, myuse=myuse,	1012	pkgsettings, myuse=myuse,
1022	use_binaries=("--usepkgonly" in self.myopts),	1013	use_binaries=("--usepkgonly" in self.myopts),
1023	myroot=myroot, trees=self.trees)	1014	myroot=myroot, trees=self.trees, return_all_deps=True)
1024		1015
1025	if not mycheck[0]:	1016	if not mycheck[0]:
1026	mymerge=[]	1017	mymerge=[]
Lines 1056-1064 Link Here
1056	self.pkgsettings[p_root].setinst(p_key,	1047	self.pkgsettings[p_root].setinst(p_key,
1057	self.trees[p_root][self.pkg_tree_map[p_type]].dbapi)	1048	self.trees[p_root][self.pkg_tree_map[p_type]].dbapi)
1058		1049
1059	if not mymerge:
1060	return 1
1061
1062	if "--debug" in self.myopts:	1050	if "--debug" in self.myopts:
1063	print "Candidates:",mymerge	1051	print "Candidates:",mymerge
1064	for x in mymerge:	1052	for x in mymerge:
Lines 1076-1081 Link Here
1076	selected_pkg = ["blocks", myroot, x[1:], None]	1064	selected_pkg = ["blocks", myroot, x[1:], None]
1077	else:	1065	else:
1078	#We are not processing a blocker but a normal dependency	1066	#We are not processing a blocker but a normal dependency
		1067	pkg_key = portage.dep_getkey(x)
		1068	if pkg_key in pkgsettings.pprovideddict and \
		1069	portage.match_from_list(
		1070	x, pkgsettings.pprovideddict[pkg_key]):
		1071	continue
		1072
1079	# List of acceptable packages, ordered by type preference.	1073	# List of acceptable packages, ordered by type preference.
1080	matched_packages = []	1074	matched_packages = []
1081	myeb_matches = portdb.xmatch("match-visible", x)	1075	myeb_matches = portdb.xmatch("match-visible", x)
Lines 1178-1192 Link Here
1178		1172
1179	if myparent:	1173	if myparent:
1180	#we are a dependency, so we want to be unconditionally added	1174	#we are a dependency, so we want to be unconditionally added
		1175	soft_dep = soft_deps or vardb.match(x)
1181	if not self.create(selected_pkg[0:3], myparent,	1176	if not self.create(selected_pkg[0:3], myparent,
1182	myuse=selected_pkg[-1]):	1177	myuse=selected_pkg[-1], soft_dep=soft_dep, arg=arg):
1183	return 0	1178	return 0
1184	else:	1179	else:
1185	#if mysource is not set, then we are a command-line dependency and should not be added	1180	#if mysource is not set, then we are a command-line dependency and should not be added
1186	#if --onlydeps is specified.	1181	#if --onlydeps is specified.
1187	if not self.create(selected_pkg[0:3], myparent,	1182	if not self.create(selected_pkg[0:3], myparent,
1188	addme=("--onlydeps" not in self.myopts),	1183	addme=("--onlydeps" not in self.myopts),
1189	myuse=selected_pkg[-1]):	1184	myuse=selected_pkg[-1], arg=arg):
1190	return 0	1185	return 0
1191		1186
1192	if "--debug" in self.myopts:	1187	if "--debug" in self.myopts:
Lines 1205-1217 Link Here
1205	while (not mygraph.empty()):	1200	while (not mygraph.empty()):
1206	mycurkey=mygraph.firstzero()	1201	mycurkey=mygraph.firstzero()
1207	if not mycurkey:	1202	if not mycurkey:
1208	print "!!! Error: circular dependencies:"	1203	installables = mygraph.leaf_nodes(ignore_soft_deps=True)
1209	print	1204	if not installables:
1210	for x in mygraph.dict.keys():	1205	print "!!! Error: circular dependencies:"
1211	for y in mygraph.dict[x][1]:	1206	print
1212	print y,"depends on",x	1207	for x in mygraph.allnodes():
1213	print	1208	for y in mygraph.parent_nodes(x):
1214	sys.exit(1)	1209	print y,"depends on",x
		1210	print
		1211	sys.exit(1)
		1212	mycurkey = installables[0]
1215	splitski=string.split(mycurkey)	1213	splitski=string.split(mycurkey)
1216	#I'm not sure of the significance of the following lines (vestigal?) so I'm commenting 'em out.	1214	#I'm not sure of the significance of the following lines (vestigal?) so I'm commenting 'em out.
1217	#These lines remove already-merged things from our alt-list	1215	#These lines remove already-merged things from our alt-list

Lines 313-396 Link Here

(-)portage.orig/pym/portage.py (-87 / +159 lines)
313		313
314	class digraph:	314	class digraph:
315	def __init__(self):	315	def __init__(self):
316	self.dict={}	316	"""Create an empty digraph"""
317	#okeys = keys, in order they were added (to optimize firstzero() ordering)	317
318	self.okeys=[]	318	# { node : ( { child : soft_dep } , { parent : soft_dep } ) }
319		319	self.nodes = {}
320	def addnode(self,mykey,myparent):	320	self.order = []
321	if not self.dict.has_key(mykey):
322	self.okeys.append(mykey)
323	if myparent is None:
324	self.dict[mykey]=[0,[]]
325	else:
326	self.dict[mykey]=[0,[myparent]]
327	self.dict[myparent][0]=self.dict[myparent][0]+1
328	return
329	if myparent and (not myparent in self.dict[mykey][1]):
330	self.dict[mykey][1].append(myparent)
331	self.dict[myparent][0]=self.dict[myparent][0]+1
332		321
333	def delnode(self,mykey):	322	def add(self, node, parent, soft_dep=False):
334	if not self.dict.has_key(mykey):	323	"""Adds the specified node with the specified parent.
		324
		325	If the dep is a soft-dep and the node already has a hard
		326	relationship to the parent, the relationship is left as hard."""
		327
		328	if node not in self.nodes:
		329	self.nodes[node] = ({}, {})
		330	self.order.append(node)
		331
		332	if not parent:
335	return	333	return
336	for x in self.dict[mykey][1]:	334
337	self.dict[x][0]=self.dict[x][0]-1	335	if parent not in self.nodes:
338	del self.dict[mykey]	336	self.nodes[parent] = ({}, {})
339	while 1:	337	self.order.append(parent)
340	try:	338
341	self.okeys.remove(mykey)	339	if parent in self.nodes[node][1]:
342	except ValueError:	340	if not soft_dep:
343	break	341	self.nodes[node][1][parent] = False
		342	else:
		343	self.nodes[node][1][parent] = soft_dep
		344
		345	if node in self.nodes[parent][0]:
		346	if not soft_dep:
		347	self.nodes[parent][0][node] = False
		348	else:
		349	self.nodes[parent][0][node] = soft_dep
		350
		351	def remove(self, node):
		352	"""Removes the specified node from the digraph, also removing
		353	and ties to other nodes in the digraph. Raises KeyError if the
		354	node doesn't exist."""
		355
		356	if node not in self.nodes:
		357	raise KeyError(node)
		358
		359	for parent in self.nodes[node][1]:
		360	del self.nodes[parent][0][node]
		361	for child in self.nodes[node][0]:
		362	del self.nodes[child][1][node]
		363
		364	del self.nodes[node]
		365	self.order.remove(node)
		366
		367	def contains(self, node):
		368	"""Checks if the digraph contains mynode"""
		369	return node in self.nodes
		370
		371	def all_nodes(self):
		372	"""Return a list of all nodes in the graph"""
		373	return self.order[:]
		374
		375	def child_nodes(self, node):
		376	"""Return all children of the specified node"""
		377	return self.nodes[node][0].keys()
		378
		379	def parent_nodes(self, node):
		380	"""Return all parents of the specified node"""
		381	return self.nodes[node][1].keys()
		382
		383	def leaf_nodes(self, ignore_soft_deps=False):
		384	"""Return all nodes that have no children
		385
		386	If ignore_soft_deps is True, soft deps are not counted as
		387	children in calculations."""
		388
		389	leaf_nodes = []
		390	for node in self.order:
		391	is_leaf_node = True
		392	for child in self.nodes[node][0]:
		393	if not (ignore_soft_deps and self.nodes[node][0][child]):
		394	is_leaf_node = False
		395	break
		396	if is_leaf_node:
		397	leaf_nodes.append(node)
		398	return leaf_nodes
		399
		400	def is_empty(self):
		401	"""Checks if the digraph is empty"""
		402	return len(self.nodes) == 0
		403
		404	def clone(self):
		405	clone = digraph()
406	clone.nodes = copy.deepcopy(self.nodes)
407	clone.order = self.order[:]
408	return clone
409
410	# Backward compatibility
411	addnode = add
412	allnodes = all_nodes
413	allzeros = leaf_nodes
414	hasnode = contains
415	empty = is_empty
416	copy = clone
344		417
345	def allnodes(self):	418	def delnode(self, node):
346	"returns all nodes in the dictionary"	419	try:
347	return self.dict.keys()	420	self.remove(node)
		421	except KeyError:
		422	pass
348		423
349	def firstzero(self):	424	def firstzero(self):
350	"returns first node with zero references, or NULL if no such node exists"	425	leaf_nodes = self.leaf_nodes()
351	for x in self.okeys:	426	if leaf_nodes:
352	if self.dict[x][0]==0:	427	return leaf_nodes[0]
353	return x
354	return None	428	return None
355		429
356	def depth(self, mykey):
357	depth=0
358	while (self.dict[mykey][1]):
359	depth=depth+1
360	mykey=self.dict[mykey][1][0]
361	return depth
362
363	def allzeros(self):
364	"returns all nodes with zero references, or NULL if no such node exists"
365	zerolist = []
366	for x in self.dict.keys():
367	mys = string.split(x)
368	if mys[0] != "blocks" and self.dict[x][0]==0:
369	zerolist.append(x)
370	return zerolist
371
372	def hasallzeros(self):	430	def hasallzeros(self):
373	"returns 0/1, Are all nodes zeros? 1 : 0"	431	return len(self.leaf_nodes() == 0)
374	zerolist = []
375	for x in self.dict.keys():
376	if self.dict[x][0]!=0:
377	return 0
378	return 1
379		432
380	def empty(self):	433	def depth(self, node):
381	if len(self.dict)==0:	434	"""Find how many nodes are in the parent chain of the passed node
382	return 1	435
383	return 0	436	This method doesn't make sense unless there is no more than one
		437	parent for each node. As this digraph is capable of having multiple
		438	parents on a node, this implementation chooses an arbitrary parent
		439	for calculations, stopping as soon as a loop is detected in order
		440	to mimic the sorts of counts that would have previously been
		441	returned.
		442
		443	This method is only used by emerge's --tree option. That option
		444	needs to be reworked to not use this so that this method can be
		445	removed altogether."""
		446
		447	parents = {}
		448	while self.nodes[node][1]:
		449	parent = self.nodes[node][1].keys()[0]
		450	if parent in parents:
		451	break
		452	parents[parent] = True
		453	node = parent
		454	return len(parents)
		455
		456	def debug_print(self):
		457	for node in self.nodes:
		458	print node,
		459	if self.nodes[node][0]:
		460	print "depends on"
		461	else:
		462	print "(no children)"
		463	for child in self.nodes[node][0]:
		464	print " ",child,
		465	if self.nodes[node][0][child]:
		466	print "(hard)"
		467	else:
		468	print "(soft)"
384		469
385	def hasnode(self,mynode):
386	return self.dict.has_key(mynode)
387		470
388	def copy(self):
389	mygraph=digraph()
390	for x in self.dict.keys():
391	mygraph.dict[x]=self.dict[x][:]
392	mygraph.okeys=self.okeys[:]
393	return mygraph
394		471
395	def elog_process(cpv, mysettings):	472	def elog_process(cpv, mysettings):
396	mylogfiles = listdir(mysettings["T"]+"/logging/")	473	mylogfiles = listdir(mysettings["T"]+"/logging/")
Lines 3293-3299 Link Here
3293	return 0	3370	return 0
3294	return 1	3371	return 1
3295		3372
3296	def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None):	3373	def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None, return_all_deps=False):
3297	"""Takes an unreduced and reduced deplist and removes satisfied dependencies.	3374	"""Takes an unreduced and reduced deplist and removes satisfied dependencies.
3298	Returned deplist contains steps that must be taken to satisfy dependencies."""	3375	Returned deplist contains steps that must be taken to satisfy dependencies."""
3299	if trees is None:	3376	if trees is None:
Lines 3308-3315 Link Here
3308	for (dep, satisfied) in zip(unreduced, reduced):	3385	for (dep, satisfied) in zip(unreduced, reduced):
3309	if isinstance(dep, list):	3386	if isinstance(dep, list):
3310	unresolved += dep_zapdeps(dep, satisfied, myroot,	3387	unresolved += dep_zapdeps(dep, satisfied, myroot,
3311	use_binaries=use_binaries, trees=trees)	3388	use_binaries=use_binaries, trees=trees, return_all_deps=return_all_deps)
3312	elif not satisfied:	3389	elif not satisfied or return_all_deps:
3313	unresolved.append(dep)	3390	unresolved.append(dep)
3314	return unresolved	3391	return unresolved
3315		3392
Lines 3413-3419 Link Here
3413	mydep, mydb=mydb, use_cache=use_cache, settings=settings) + postfix	3490	mydep, mydb=mydb, use_cache=use_cache, settings=settings) + postfix
3414		3491
3415	def dep_check(depstring, mydbapi, mysettings, use="yes", mode=None, myuse=None,	3492	def dep_check(depstring, mydbapi, mysettings, use="yes", mode=None, myuse=None,
3416	use_cache=1, use_binaries=0, myroot="/", trees=None):	3493	use_cache=1, use_binaries=0, myroot="/", trees=None, return_all_deps=False):
3417	"""Takes a depend string and parses the condition."""	3494	"""Takes a depend string and parses the condition."""
3418		3495
3419	#check_config_instance(mysettings)	3496	#check_config_instance(mysettings)
Lines 3478-3500 Link Here
3478	writemsg("\n\n\n", 1)	3555	writemsg("\n\n\n", 1)
3479	writemsg("mysplit: %s\n" % (mysplit), 1)	3556	writemsg("mysplit: %s\n" % (mysplit), 1)
3480	writemsg("mysplit2: %s\n" % (mysplit2), 1)	3557	writemsg("mysplit2: %s\n" % (mysplit2), 1)
3481	myeval=dep_eval(mysplit2)
3482	writemsg("myeval: %s\n" % (myeval), 1)
3483		3558
3484	if myeval:	3559	myzaps = dep_zapdeps(mysplit, mysplit2, myroot,
3485	return [1,[]]	3560	use_binaries=use_binaries, trees=trees, return_all_deps=return_all_deps)
3486	else:	3561	mylist = flatten(myzaps)
3487	myzaps = dep_zapdeps(mysplit, mysplit2, myroot,	3562	writemsg("myzaps: %s\n" % (myzaps), 1)
3488	use_binaries=use_binaries, trees=trees)	3563	writemsg("mylist: %s\n" % (mylist), 1)
3489	mylist = flatten(myzaps)	3564	#remove duplicates
3490	writemsg("myzaps: %s\n" % (myzaps), 1)	3565	mydict={}
3491	writemsg("mylist: %s\n" % (mylist), 1)	3566	for x in mylist:
3492	#remove duplicates	3567	mydict[x]=1
3493	mydict={}	3568	writemsg("mydict: %s\n" % (mydict), 1)
3494	for x in mylist:	3569	return [1,mydict.keys()]
3495	mydict[x]=1
3496	writemsg("mydict: %s\n" % (mydict), 1)
3497	return [1,mydict.keys()]
3498		3570
3499	def dep_wordreduce(mydeplist,mysettings,mydbapi,mode,use_cache=1):	3571	def dep_wordreduce(mydeplist,mysettings,mydbapi,mode,use_cache=1):
3500	"Reduces the deplist to ones and zeros"	3572	"Reduces the deplist to ones and zeros"