Attachment #97306 for bug #147766




	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

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

		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




	def __init__(self):
		"""Create an empty digraph"""
		
		# { node : ( { child : soft_dep } , { parent : soft_dep } ) }
		self.nodes = {}
		self.order = []

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

		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:


	# Backward compatibility
	addnode = add
	delnode = remove
	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 None

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

Return to bug 147766

Lines 356-375 Link Here

(-)portage.firstpatch/bin/emerge (-30 / +13 lines)
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,hard_dep=True,arg=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-707 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, hard_dep=hard_dep)	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):
704	self.digraph.addnode(jbigkey, myparent, hard_dep=hard_dep)	698	self.digraph.addnode(jbigkey, myparent, soft_dep=soft_dep)
705	return 1	699	return 1
706		700
707	self.spinner.update()	701	self.spinner.update()
Lines 724-730 Link Here
724	if self.mydbapi[parent_root].match(mykey) or \	718	if self.mydbapi[parent_root].match(mykey) or \
725	self.trees[parent_root]["vartree"].dbapi.match(mykey):	719	self.trees[parent_root]["vartree"].dbapi.match(mykey):
726	mybigkey.append(myparent.split()[2])	720	mybigkey.append(myparent.split()[2])
727	self.digraph.addnode(" ".join(mybigkey), myparent, hard_dep)	721	self.digraph.addnode(" ".join(mybigkey), myparent, soft_dep=soft_dep)
728	return 1	722	return 1
729	else:	723	else:
730	mydbapi = self.trees[myroot][self.pkg_tree_map[mytype]].dbapi	724	mydbapi = self.trees[myroot][self.pkg_tree_map[mytype]].dbapi
Lines 783-789 Link Here
783	""" 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
784	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
785	add the package to the depgraph; so we do that here. """	779	add the package to the depgraph; so we do that here. """
786	self.digraph.addnode(string.join(mybigkey),myparent,hard_dep=hard_dep)	780	self.digraph.addnode(string.join(mybigkey),myparent,soft_dep=soft_dep)
787		781
788	""" This section determines whether we go deeper into dependencies or not.	782	""" This section determines whether we go deeper into dependencies or not.
789	We want to go deeper on a few occasions:	783	We want to go deeper on a few occasions:
Lines 816-839 Link Here
816	""" We have retrieve the dependency information, now we need to recursively	810	""" We have retrieve the dependency information, now we need to recursively
817	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. """
818		812
819	mydep={}
820	mp=string.join(mybigkey)	813	mp=string.join(mybigkey)
821		814
822	try:	815	try:
823	if myroot=="/":	816	if not self.select_dep("/",edepend["DEPEND"],myparent=mp,myuse=myuse):
824	mydep["/"]=edepend["DEPEND"]+" "+edepend["RDEPEND"]	817	return 0
825	if not self.select_dep("/",edepend["DEPEND"],myparent=mp,myuse=myuse):	818	if not self.select_dep(myroot,edepend["RDEPEND"],myparent=mp,myuse=myuse,soft_deps=True):
826	return 0	819	return 0
827	if not self.select_dep("/",edepend["RDEPEND"],myparent=mp,myuse=myuse,soft_deps=True):
828	return 0
829	else:
830	mydep["/"]=edepend["DEPEND"]
831	mydep[myroot]=edepend["RDEPEND"]
832	if not self.select_dep("/",mydep["/"],myparent=mp,myuse=myuse):
833	return 0
834	if not self.select_dep(myroot,mydep[myroot],myparent=mp,myuse=myuse,soft_deps=True):
835	return 0
836
837	if edepend.has_key("PDEPEND") and edepend["PDEPEND"]:	820	if edepend.has_key("PDEPEND") and edepend["PDEPEND"]:
838	# 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
839	# 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.
Lines 1189-1197 Link Here
1189		1172
1190	if myparent:	1173	if myparent:
1191	#we are a dependency, so we want to be unconditionally added	1174	#we are a dependency, so we want to be unconditionally added
1192	hard_dep = not soft_deps and len(vardb.match(x)) == 0	1175	soft_dep = soft_deps or vardb.match(x)
1193	if not self.create(selected_pkg[0:3], myparent,	1176	if not self.create(selected_pkg[0:3], myparent,
1194	myuse=selected_pkg[-1], hard_dep=hard_dep, arg=arg):	1177	myuse=selected_pkg[-1], soft_dep=soft_dep, arg=arg):
1195	return 0	1178	return 0
1196	else:	1179	else:
1197	#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
Lines 1217-1223 Link Here
1217	while (not mygraph.empty()):	1200	while (not mygraph.empty()):
1218	mycurkey=mygraph.firstzero()	1201	mycurkey=mygraph.firstzero()
1219	if not mycurkey:	1202	if not mycurkey:
1220	installables = mygraph.leaf_nodes(include_soft_deps=False)	1203	installables = mygraph.leaf_nodes(ignore_soft_deps=True)
1221	if not installables:	1204	if not installables:
1222	print "!!! Error: circular dependencies:"	1205	print "!!! Error: circular dependencies:"
1223	print	1206	print

Lines 315-328 Link Here

(-)portage.firstpatch/pym/portage.py (-17 / +35 lines)
315	def __init__(self):	315	def __init__(self):
316	"""Create an empty digraph"""	316	"""Create an empty digraph"""
317		317
318	# { node : ( { child : hard_dep } , { parent : hard_dep } ) }	318	# { node : ( { child : soft_dep } , { parent : soft_dep } ) }
319	self.nodes = {}	319	self.nodes = {}
320	self.order = []	320	self.order = []
321		321
322	def add(self, node, parent, hard_dep=True):	322	def add(self, node, parent, soft_dep=False):
323	"""Adds the specified node with the specified parent. If the dep	323	"""Adds the specified node with the specified parent.
324	is a hard-dep and the node already has a relationship to the parent	324
325	the relationship is ensured to be hard."""	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."""
326		327
327	if node not in self.nodes:	328	if node not in self.nodes:
328	self.nodes[node] = ({}, {})	329	self.nodes[node] = ({}, {})
Lines 336-351 Link Here
336	self.order.append(parent)	337	self.order.append(parent)
337		338
338	if parent in self.nodes[node][1]:	339	if parent in self.nodes[node][1]:
339	if hard_dep:	340	if not soft_dep:
340	self.nodes[node][1][parent] = True	341	self.nodes[node][1][parent] = False
341	else:	342	else:
342	self.nodes[node][1][parent] = hard_dep	343	self.nodes[node][1][parent] = soft_dep
343		344
344	if node in self.nodes[parent][0]:	345	if node in self.nodes[parent][0]:
345	if hard_dep:	346	if not soft_dep:
346	self.nodes[parent][0][node] = True	347	self.nodes[parent][0][node] = False
347	else:	348	else:
348	self.nodes[parent][0][node] = hard_dep	349	self.nodes[parent][0][node] = soft_dep
349		350
350	def remove(self, node):	351	def remove(self, node):
351	"""Removes the specified node from the digraph, also removing	352	"""Removes the specified node from the digraph, also removing
Lines 368-387 Link Here
368	return node in self.nodes	369	return node in self.nodes
369		370
370	def all_nodes(self):	371	def all_nodes(self):
		372	"""Return a list of all nodes in the graph"""
371	return self.order[:]	373	return self.order[:]
372		374
373	def child_nodes(self, node):	375	def child_nodes(self, node):
		376	"""Return all children of the specified node"""
374	return self.nodes[node][0].keys()	377	return self.nodes[node][0].keys()
375		378
376	def parent_nodes(self, node):	379	def parent_nodes(self, node):
		380	"""Return all parents of the specified node"""
377	return self.nodes[node][1].keys()	381	return self.nodes[node][1].keys()
378		382
379	def leaf_nodes(self, include_soft_deps=False):	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
380	leaf_nodes = []	389	leaf_nodes = []
381	for node in self.order:	390	for node in self.order:
382	is_leaf_node = True	391	is_leaf_node = True
383	for child in self.nodes[node][0]:	392	for child in self.nodes[node][0]:
384	if include_soft_deps or self.nodes[node][0][child]:	393	if not (ignore_soft_deps and self.nodes[node][0][child]):
385	is_leaf_node = False	394	is_leaf_node = False
386	break	395	break
387	if is_leaf_node:	396	if is_leaf_node:
Lines 400-414 Link Here
400		409
401	# Backward compatibility	410	# Backward compatibility
402	addnode = add	411	addnode = add
403	delnode = remove
404	allnodes = all_nodes	412	allnodes = all_nodes
405	allzeros = leaf_nodes	413	allzeros = leaf_nodes
406	hasnode = contains	414	hasnode = contains
407	empty = is_empty	415	empty = is_empty
408	copy = clone	416	copy = clone
409		417
		418	def delnode(self, node):
		419	try:
		420	self.remove(node)
		421	except KeyError:
		422	pass
		423
410	def firstzero(self):	424	def firstzero(self):
411	leaf_nodes = self.leaf_nodes(include_soft_deps=True)	425	leaf_nodes = self.leaf_nodes()
412	if leaf_nodes:	426	if leaf_nodes:
413	return leaf_nodes[0]	427	return leaf_nodes[0]
414	return None	428	return None
Lines 441-447 Link Here
441		455
442	def debug_print(self):	456	def debug_print(self):
443	for node in self.nodes:	457	for node in self.nodes:
444	print node,"depends on"	458	print node,
		459	if self.nodes[node][0]:
		460	print "depends on"
		461	else:
		462	print "(no children)"
445	for child in self.nodes[node][0]:	463	for child in self.nodes[node][0]:
446	print " ",child,	464	print " ",child,
447	if self.nodes[node][0][child]:	465	if self.nodes[node][0][child]: