Attachment #97305 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"):

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

	def create(self,mybigkey,myparent=None,addme=1,myuse=None,hard_dep=True,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, hard_dep=hard_dep)
			return 1
		jbigkey = " ".join(mybigkey) + " nomerge"
		if self.digraph.hasnode(jbigkey):
			self.digraph.addnode(jbigkey, myparent, hard_dep=hard_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, hard_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,hard_dep=hard_dep)
		
		""" This section determines whether we go deeper into dependencies or not.
		    We want to go deeper on a few occasions:

		try:
			if myroot=="/":
				mydep["/"]=edepend["DEPEND"]+" "+edepend["RDEPEND"]
				if not self.select_dep("/",edepend["DEPEND"],myparent=mp,myuse=myuse):
					return 0
				if not self.select_dep("/",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,soft_deps=True):
					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
				hard_dep = not soft_deps and len(vardb.match(x)) == 0
				if not self.create(selected_pkg[0:3], myparent,
					myuse=selected_pkg[-1], hard_dep=hard_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(include_soft_deps=False)
				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 : hard_dep } , { parent : hard_dep } ) }
		self.nodes = {}
		self.order = []

	def add(self, node, parent, hard_dep=True):
		"""Adds the specified node with the specified parent. If the dep
		is a hard-dep and the node already has a relationship to the parent
		the relationship is ensured to be 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 hard_dep:
				self.nodes[node][1][parent] = True
		else:
			self.nodes[node][1][parent] = hard_dep
		
		if node in self.nodes[parent][0]:
			if hard_dep:
				self.nodes[parent][0][node] = True
		else:
			self.nodes[parent][0][node] = hard_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 self.order[:]

	def child_nodes(self, node):
		return self.nodes[node][0].keys()
	
	def parent_nodes(self, node):
		return self.nodes[node][1].keys()

	def leaf_nodes(self, include_soft_deps=False):
		leaf_nodes = []
		for node in self.order:
			is_leaf_node = True
			for child in self.nodes[node][0]:
				if include_soft_deps or 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
	delnode = remove
	allnodes = all_nodes
	allzeros = leaf_nodes
	hasnode = contains
	empty = is_empty
	copy = clone

	def firstzero(self):
		leaf_nodes = self.leaf_nodes(include_soft_deps=True)
		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,"depends on"
			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-358 Link Here

(-)portage.orig/bin/emerge (-25 / +40 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"):
Lines 679-685 Link Here
679	"--getbinpkg" in self.myopts,	679	"--getbinpkg" in self.myopts,
680	"--getbinpkgonly" in self.myopts)	680	"--getbinpkgonly" in self.myopts)
681		681
682	def create(self,mybigkey,myparent=None,addme=1,myuse=None):	682	def create(self,mybigkey,myparent=None,addme=1,myuse=None,hard_dep=True,arg=None):
683	"""	683	"""
684	Fills the digraph with nodes comprised of packages to merge.	684	Fills the digraph with nodes comprised of packages to merge.
685	mybigkey is the package spec of the package to merge.	685	mybigkey is the package spec of the package to merge.
Lines 697-706 Link Here
697	if addme and jbigkey != myparent:	697	if addme and jbigkey != myparent:
698	# Refuse to make a node depend on itself so that the we don't	698	# 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().	699	# don't create a bogus circular dependency in self.altlist().
700	self.digraph.addnode(jbigkey, myparent)	700	self.digraph.addnode(jbigkey, myparent, hard_dep=hard_dep)
701	return 1	701	return 1
702	jbigkey = " ".join(mybigkey) + " nomerge"	702	jbigkey = " ".join(mybigkey) + " nomerge"
703	if self.digraph.hasnode(jbigkey):	703	if self.digraph.hasnode(jbigkey):
		704	self.digraph.addnode(jbigkey, myparent, hard_dep=hard_dep)
704	return 1	705	return 1
705		706
706	self.spinner.update()	707	self.spinner.update()
Lines 723-729 Link Here
723	if self.mydbapi[parent_root].match(mykey) or \	724	if self.mydbapi[parent_root].match(mykey) or \
724	self.trees[parent_root]["vartree"].dbapi.match(mykey):	725	self.trees[parent_root]["vartree"].dbapi.match(mykey):
725	mybigkey.append(myparent.split()[2])	726	mybigkey.append(myparent.split()[2])
726	self.digraph.addnode(" ".join(mybigkey), myparent)	727	self.digraph.addnode(" ".join(mybigkey), myparent, hard_dep)
727	return 1	728	return 1
728	else:	729	else:
729	mydbapi = self.trees[myroot][self.pkg_tree_map[mytype]].dbapi	730	mydbapi = self.trees[myroot][self.pkg_tree_map[mytype]].dbapi
Lines 744-750 Link Here
744	installed we skip merging it."""	745	installed we skip merging it."""
745	if "self" not in self.myparams or \	746	if "self" not in self.myparams or \
746	("selective" in self.myparams and \	747	("selective" in self.myparams and \
747	vardbapi.cpv_exists(mykey)):	748	not arg and vardbapi.cpv_exists(mykey)):
748	merging=0	749	merging=0
749	elif "selective" in self.myparams and vardbapi.cpv_exists(mykey):	750	elif "selective" in self.myparams and vardbapi.cpv_exists(mykey):
750	merging=0	751	merging=0
Lines 782-788 Link Here
782	""" At this point, we have either hit a blocker and returned, found the package in the	783	""" 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	784	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. """	785	add the package to the depgraph; so we do that here. """
785	self.digraph.addnode(string.join(mybigkey),myparent)	786	self.digraph.addnode(string.join(mybigkey),myparent,hard_dep=hard_dep)
786		787
787	""" This section determines whether we go deeper into dependencies or not.	788	""" This section determines whether we go deeper into dependencies or not.
788	We want to go deeper on a few occasions:	789	We want to go deeper on a few occasions:
Lines 821-840 Link Here
821	try:	822	try:
822	if myroot=="/":	823	if myroot=="/":
823	mydep["/"]=edepend["DEPEND"]+" "+edepend["RDEPEND"]	824	mydep["/"]=edepend["DEPEND"]+" "+edepend["RDEPEND"]
824	if not self.select_dep("/",mydep["/"],myparent=mp,myuse=myuse):	825	if not self.select_dep("/",edepend["DEPEND"],myparent=mp,myuse=myuse):
		826	return 0
		827	if not self.select_dep("/",edepend["RDEPEND"],myparent=mp,myuse=myuse,soft_deps=True):
825	return 0	828	return 0
826	else:	829	else:
827	mydep["/"]=edepend["DEPEND"]	830	mydep["/"]=edepend["DEPEND"]
828	mydep[myroot]=edepend["RDEPEND"]	831	mydep[myroot]=edepend["RDEPEND"]
829	if not self.select_dep("/",mydep["/"],myparent=mp,myuse=myuse):	832	if not self.select_dep("/",mydep["/"],myparent=mp,myuse=myuse):
830	return 0	833	return 0
831	if not self.select_dep(myroot,mydep[myroot],myparent=mp,myuse=myuse):	834	if not self.select_dep(myroot,mydep[myroot],myparent=mp,myuse=myuse,soft_deps=True):
832	return 0	835	return 0
833		836
834	if edepend.has_key("PDEPEND") and edepend["PDEPEND"]:	837	if edepend.has_key("PDEPEND") and edepend["PDEPEND"]:
835	# Post Depend -- Add to the list without a parent, as it depends	838	# 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.	839	# on a package being present AND must be built after that package.
837	if not self.select_dep(myroot,edepend["PDEPEND"],myuse=myuse):	840	if not self.select_dep(myroot,edepend["PDEPEND"],myuse=myuse,soft_deps=True):
838	return 0	841	return 0
839	except ValueError, e:	842	except ValueError, e:
840	pkgs = e.args[0]	843	pkgs = e.args[0]
Lines 940-946 Link Here
940	sys.stderr.flush()	943	sys.stderr.flush()
941		944
942	try:	945	try:
943	self.mysd = self.select_dep(myroot, mykey, arg=x)	946	if "--noreplace" in self.myopts:
		947	arg = None
		948	else:
		949	arg = x
		950	self.mysd = self.select_dep(myroot, mykey, arg=arg)
944	except portage_exception.MissingSignature, e:	951	except portage_exception.MissingSignature, e:
945	portage.writemsg("\n\n!!! A missing gpg signature is preventing portage from calculating the\n")	952	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")	953	portage.writemsg("!!! required dependencies. This is a security feature enabled by the admin\n")
Lines 969-975 Link Here
969		976
970	missing=0	977	missing=0
971	if "--usepkgonly" in self.myopts:	978	if "--usepkgonly" in self.myopts:
972	for x in self.digraph.dict.keys():	979	for x in self.digraph.all_nodes():
973	xs=string.split(x," ")	980	xs=string.split(x," ")
974	if (xs[0] != "binary") and (xs[3]=="merge"):	981	if (xs[0] != "binary") and (xs[3]=="merge"):
975	if missing == 0:	982	if missing == 0:
Lines 993-999 Link Here
993	if curslot == myslot:	1000	if curslot == myslot:
994	return match	1001	return match
995		1002
996	def select_dep(self,myroot,depstring,myparent=None,arg=None,myuse=None,raise_on_missing=False):	1003	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.	1004	""" Given a depstring, create the depgraph such that all dependencies are satisfied.
998	myroot = $ROOT from environment, where {R,P}DEPENDs are merged to.	1005	myroot = $ROOT from environment, where {R,P}DEPENDs are merged to.
999	myparent = the node whose depstring is being passed in	1006	myparent = the node whose depstring is being passed in
Lines 1006-1011 Link Here
1006		1013
1007	portdb = self.trees[myroot]["porttree"].dbapi	1014	portdb = self.trees[myroot]["porttree"].dbapi
1008	bindb = self.trees[myroot]["bintree"].dbapi	1015	bindb = self.trees[myroot]["bintree"].dbapi
		1016	vardb = self.trees[myroot]["vartree"].dbapi
1009	pkgsettings = self.pkgsettings[myroot]	1017	pkgsettings = self.pkgsettings[myroot]
1010		1018
1011	if "--debug" in self.myopts:	1019	if "--debug" in self.myopts:
Lines 1020-1026 Link Here
1020	mycheck = portage.dep_check(depstring, self.mydbapi[myroot],	1028	mycheck = portage.dep_check(depstring, self.mydbapi[myroot],
1021	pkgsettings, myuse=myuse,	1029	pkgsettings, myuse=myuse,
1022	use_binaries=("--usepkgonly" in self.myopts),	1030	use_binaries=("--usepkgonly" in self.myopts),
1023	myroot=myroot, trees=self.trees)	1031	myroot=myroot, trees=self.trees, return_all_deps=True)
1024		1032
1025	if not mycheck[0]:	1033	if not mycheck[0]:
1026	mymerge=[]	1034	mymerge=[]
Lines 1056-1064 Link Here
1056	self.pkgsettings[p_root].setinst(p_key,	1064	self.pkgsettings[p_root].setinst(p_key,
1057	self.trees[p_root][self.pkg_tree_map[p_type]].dbapi)	1065	self.trees[p_root][self.pkg_tree_map[p_type]].dbapi)
1058		1066
1059	if not mymerge:
1060	return 1
1061
1062	if "--debug" in self.myopts:	1067	if "--debug" in self.myopts:
1063	print "Candidates:",mymerge	1068	print "Candidates:",mymerge
1064	for x in mymerge:	1069	for x in mymerge:
Lines 1076-1081 Link Here
1076	selected_pkg = ["blocks", myroot, x[1:], None]	1081	selected_pkg = ["blocks", myroot, x[1:], None]
1077	else:	1082	else:
1078	#We are not processing a blocker but a normal dependency	1083	#We are not processing a blocker but a normal dependency
		1084	pkg_key = portage.dep_getkey(x)
		1085	if pkg_key in pkgsettings.pprovideddict and \
		1086	portage.match_from_list(
		1087	x, pkgsettings.pprovideddict[pkg_key]):
		1088	continue
		1089
1079	# List of acceptable packages, ordered by type preference.	1090	# List of acceptable packages, ordered by type preference.
1080	matched_packages = []	1091	matched_packages = []
1081	myeb_matches = portdb.xmatch("match-visible", x)	1092	myeb_matches = portdb.xmatch("match-visible", x)
Lines 1178-1192 Link Here
1178		1189
1179	if myparent:	1190	if myparent:
1180	#we are a dependency, so we want to be unconditionally added	1191	#we are a dependency, so we want to be unconditionally added
		1192	hard_dep = not soft_deps and len(vardb.match(x)) == 0
1181	if not self.create(selected_pkg[0:3], myparent,	1193	if not self.create(selected_pkg[0:3], myparent,
1182	myuse=selected_pkg[-1]):	1194	myuse=selected_pkg[-1], hard_dep=hard_dep, arg=arg):
1183	return 0	1195	return 0
1184	else:	1196	else:
1185	#if mysource is not set, then we are a command-line dependency and should not be added	1197	#if mysource is not set, then we are a command-line dependency and should not be added
1186	#if --onlydeps is specified.	1198	#if --onlydeps is specified.
1187	if not self.create(selected_pkg[0:3], myparent,	1199	if not self.create(selected_pkg[0:3], myparent,
1188	addme=("--onlydeps" not in self.myopts),	1200	addme=("--onlydeps" not in self.myopts),
1189	myuse=selected_pkg[-1]):	1201	myuse=selected_pkg[-1], arg=arg):
1190	return 0	1202	return 0
1191		1203
1192	if "--debug" in self.myopts:	1204	if "--debug" in self.myopts:
Lines 1205-1217 Link Here
1205	while (not mygraph.empty()):	1217	while (not mygraph.empty()):
1206	mycurkey=mygraph.firstzero()	1218	mycurkey=mygraph.firstzero()
1207	if not mycurkey:	1219	if not mycurkey:
1208	print "!!! Error: circular dependencies:"	1220	installables = mygraph.leaf_nodes(include_soft_deps=False)
1209	print	1221	if not installables:
1210	for x in mygraph.dict.keys():	1222	print "!!! Error: circular dependencies:"
1211	for y in mygraph.dict[x][1]:	1223	print
1212	print y,"depends on",x	1224	for x in mygraph.allnodes():
1213	print	1225	for y in mygraph.parent_nodes(x):
1214	sys.exit(1)	1226	print y,"depends on",x
		1227	print
		1228	sys.exit(1)
		1229	mycurkey = installables[0]
1215	splitski=string.split(mycurkey)	1230	splitski=string.split(mycurkey)
1216	#I'm not sure of the significance of the following lines (vestigal?) so I'm commenting 'em out.	1231	#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	1232	#These lines remove already-merged things from our alt-list

Lines 313-396 Link Here

(-)portage.orig/pym/portage.py (-87 / +141 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 : hard_dep } , { parent : hard_dep } ) }
319		319	self.nodes = {}
320	def addnode(self,mykey,myparent):	320	self.order = []
321	if not self.dict.has_key(mykey):	321
322	self.okeys.append(mykey)	322	def add(self, node, parent, hard_dep=True):
323	if myparent is None:	323	"""Adds the specified node with the specified parent. If the dep
324	self.dict[mykey]=[0,[]]	324	is a hard-dep and the node already has a relationship to the parent
325	else:	325	the relationship is ensured to be hard."""
326	self.dict[mykey]=[0,[myparent]]	326
327	self.dict[myparent][0]=self.dict[myparent][0]+1	327	if node not in self.nodes:
		328	self.nodes[node] = ({}, {})
		329	self.order.append(node)
		330
		331	if not parent:
328	return	332	return
329	if myparent and (not myparent in self.dict[mykey][1]):	333
330	self.dict[mykey][1].append(myparent)	334	if parent not in self.nodes:
331	self.dict[myparent][0]=self.dict[myparent][0]+1	335	self.nodes[parent] = ({}, {})
		336	self.order.append(parent)
		337
		338	if parent in self.nodes[node][1]:
		339	if hard_dep:
		340	self.nodes[node][1][parent] = True
		341	else:
		342	self.nodes[node][1][parent] = hard_dep
		343
		344	if node in self.nodes[parent][0]:
		345	if hard_dep:
		346	self.nodes[parent][0][node] = True
		347	else:
		348	self.nodes[parent][0][node] = hard_dep
		349
		350	def remove(self, node):
		351	"""Removes the specified node from the digraph, also removing
		352	and ties to other nodes in the digraph. Raises KeyError if the
		353	node doesn't exist."""
		354
		355	if node not in self.nodes:
		356	raise KeyError(node)
		357
		358	for parent in self.nodes[node][1]:
		359	del self.nodes[parent][0][node]
		360	for child in self.nodes[node][0]:
		361	del self.nodes[child][1][node]
		362
		363	del self.nodes[node]
		364	self.order.remove(node)
332		365
333	def delnode(self,mykey):	366	def contains(self, node):
334	if not self.dict.has_key(mykey):	367	"""Checks if the digraph contains mynode"""
335	return	368	return node in self.nodes
336	for x in self.dict[mykey][1]:	369
337	self.dict[x][0]=self.dict[x][0]-1	370	def all_nodes(self):
338	del self.dict[mykey]	371	return self.order[:]
339	while 1:	372
340	try:	373	def child_nodes(self, node):
341	self.okeys.remove(mykey)	374	return self.nodes[node][0].keys()
342	except ValueError:	375
343	break	376	def parent_nodes(self, node):
		377	return self.nodes[node][1].keys()
344		378
345	def allnodes(self):	379	def leaf_nodes(self, include_soft_deps=False):
346	"returns all nodes in the dictionary"	380	leaf_nodes = []
347	return self.dict.keys()	381	for node in self.order:
		382	is_leaf_node = True
		383	for child in self.nodes[node][0]:
		384	if include_soft_deps or self.nodes[node][0][child]:
		385	is_leaf_node = False
		386	break
		387	if is_leaf_node:
		388	leaf_nodes.append(node)
		389	return leaf_nodes
		390
		391	def is_empty(self):
		392	"""Checks if the digraph is empty"""
		393	return len(self.nodes) == 0
		394
		395	def clone(self):
		396	clone = digraph()
		397	clone.nodes = copy.deepcopy(self.nodes)
		398	clone.order = self.order[:]
		399	return clone
		400
		401	# Backward compatibility
		402	addnode = add
		403	delnode = remove
		404	allnodes = all_nodes
		405	allzeros = leaf_nodes
		406	hasnode = contains
		407	empty = is_empty
		408	copy = clone
348		409
349	def firstzero(self):	410	def firstzero(self):
350	"returns first node with zero references, or NULL if no such node exists"	411	leaf_nodes = self.leaf_nodes(include_soft_deps=True)
351	for x in self.okeys:	412	if leaf_nodes:
352	if self.dict[x][0]==0:	413	return leaf_nodes[0]
353	return x
354	return None	414	return None
355		415
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):	416	def hasallzeros(self):
373	"returns 0/1, Are all nodes zeros? 1 : 0"	417	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		418
380	def empty(self):	419	def depth(self, node):
381	if len(self.dict)==0:	420	"""Find how many nodes are in the parent chain of the passed node
382	return 1	421
383	return 0	422	This method doesn't make sense unless there is no more than one
		423	parent for each node. As this digraph is capable of having multiple
		424	parents on a node, this implementation chooses an arbitrary parent
		425	for calculations, stopping as soon as a loop is detected in order
		426	to mimic the sorts of counts that would have previously been
		427	returned.
		428
		429	This method is only used by emerge's --tree option. That option
		430	needs to be reworked to not use this so that this method can be
		431	removed altogether."""
		432
		433	parents = {}
		434	while self.nodes[node][1]:
		435	parent = self.nodes[node][1].keys()[0]
		436	if parent in parents:
		437	break
		438	parents[parent] = True
		439	node = parent
		440	return len(parents)
		441
		442	def debug_print(self):
		443	for node in self.nodes:
		444	print node,"depends on"
		445	for child in self.nodes[node][0]:
		446	print " ",child,
		447	if self.nodes[node][0][child]:
		448	print "(hard)"
		449	else:
		450	print "(soft)"
384		451
385	def hasnode(self,mynode):
386	return self.dict.has_key(mynode)
387		452
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		453
395	def elog_process(cpv, mysettings):	454	def elog_process(cpv, mysettings):
396	mylogfiles = listdir(mysettings["T"]+"/logging/")	455	mylogfiles = listdir(mysettings["T"]+"/logging/")
Lines 3293-3299 Link Here
3293	return 0	3352	return 0
3294	return 1	3353	return 1
3295		3354
3296	def dep_zapdeps(unreduced, reduced, myroot, use_binaries=0, trees=None):	3355	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.	3356	"""Takes an unreduced and reduced deplist and removes satisfied dependencies.
3298	Returned deplist contains steps that must be taken to satisfy dependencies."""	3357	Returned deplist contains steps that must be taken to satisfy dependencies."""
3299	if trees is None:	3358	if trees is None:
Lines 3308-3315 Link Here
3308	for (dep, satisfied) in zip(unreduced, reduced):	3367	for (dep, satisfied) in zip(unreduced, reduced):
3309	if isinstance(dep, list):	3368	if isinstance(dep, list):
3310	unresolved += dep_zapdeps(dep, satisfied, myroot,	3369	unresolved += dep_zapdeps(dep, satisfied, myroot,
3311	use_binaries=use_binaries, trees=trees)	3370	use_binaries=use_binaries, trees=trees, return_all_deps=return_all_deps)
3312	elif not satisfied:	3371	elif not satisfied or return_all_deps:
3313	unresolved.append(dep)	3372	unresolved.append(dep)
3314	return unresolved	3373	return unresolved
3315		3374
Lines 3413-3419 Link Here
3413	mydep, mydb=mydb, use_cache=use_cache, settings=settings) + postfix	3472	mydep, mydb=mydb, use_cache=use_cache, settings=settings) + postfix
3414		3473
3415	def dep_check(depstring, mydbapi, mysettings, use="yes", mode=None, myuse=None,	3474	def dep_check(depstring, mydbapi, mysettings, use="yes", mode=None, myuse=None,
3416	use_cache=1, use_binaries=0, myroot="/", trees=None):	3475	use_cache=1, use_binaries=0, myroot="/", trees=None, return_all_deps=False):
3417	"""Takes a depend string and parses the condition."""	3476	"""Takes a depend string and parses the condition."""
3418		3477
3419	#check_config_instance(mysettings)	3478	#check_config_instance(mysettings)
Lines 3478-3500 Link Here
3478	writemsg("\n\n\n", 1)	3537	writemsg("\n\n\n", 1)
3479	writemsg("mysplit: %s\n" % (mysplit), 1)	3538	writemsg("mysplit: %s\n" % (mysplit), 1)
3480	writemsg("mysplit2: %s\n" % (mysplit2), 1)	3539	writemsg("mysplit2: %s\n" % (mysplit2), 1)
3481	myeval=dep_eval(mysplit2)
3482	writemsg("myeval: %s\n" % (myeval), 1)
3483		3540
3484	if myeval:	3541	myzaps = dep_zapdeps(mysplit, mysplit2, myroot,
3485	return [1,[]]	3542	use_binaries=use_binaries, trees=trees, return_all_deps=return_all_deps)
3486	else:	3543	mylist = flatten(myzaps)
3487	myzaps = dep_zapdeps(mysplit, mysplit2, myroot,	3544	writemsg("myzaps: %s\n" % (myzaps), 1)
3488	use_binaries=use_binaries, trees=trees)	3545	writemsg("mylist: %s\n" % (mylist), 1)
3489	mylist = flatten(myzaps)	3546	#remove duplicates
3490	writemsg("myzaps: %s\n" % (myzaps), 1)	3547	mydict={}
3491	writemsg("mylist: %s\n" % (mylist), 1)	3548	for x in mylist:
3492	#remove duplicates	3549	mydict[x]=1
3493	mydict={}	3550	writemsg("mydict: %s\n" % (mydict), 1)
3494	for x in mylist:	3551	return [1,mydict.keys()]
3495	mydict[x]=1
3496	writemsg("mydict: %s\n" % (mydict), 1)
3497	return [1,mydict.keys()]
3498		3552
3499	def dep_wordreduce(mydeplist,mysettings,mydbapi,mode,use_cache=1):	3553	def dep_wordreduce(mydeplist,mysettings,mydbapi,mode,use_cache=1):
3500	"Reduces the deplist to ones and zeros"	3554	"Reduces the deplist to ones and zeros"