# Helper function; I can't seem to find another function to do this...

def cpv_satisfies_dep(cpv, atom):

	# hack. Move along now.

	#print "cpv_satisfies_dep:", cpv, atom

	return ( len(portage.match_from_list(atom, [cpv])) > 0 )

class revdepgraph:

	"A reverse dependency graph. What depends upon this package?"

	def __init__(self):

		self.pkgsettings = portage.config(clone=portage.settings)

		if not self.pkgsettings["ARCH"]:

			portage.writemsg(red("\a!!! ARCH is not set... Are you missing the /etc/make.profile symlink?\n"))

			portage.writemsg(red("\a!!! Is the symlink correct? Is your portage tree complete?\n\n"))

			sys.exit(9)

		self.applied_useflags = {}

		self.digraph=portage.digraph()

	def potential_revdeps(self, cpv):

		" Returns a list of tuples (cpv, depstring) that /might/ depend upon cpv. "

		" Only considers run-time dependencies (RDEPEND). "

		vardbapi=portage.db[self.myroot]["vartree"].dbapi

		mycp=portage.pkgsplit(cpv)[0]

		myprovide=vardbapi.aux_get(cpv, ["PROVIDE"])[0].split()

		myret=[]

		for x in vardbapi.cpv_all():

			#myrawdep=string.join(vardbapi.aux_get(x,["DEPEND","RDEPEND","PDEPEND"]), " ")

			myrawdep=string.join(vardbapi.aux_get(x,self.depvars), " ")

			if string.find(myrawdep, mycp) != -1:

				myret.append( (x,myrawdep) )

			for p in myprovide:

				if string.find(myrawdep, p) != -1:

					myret.append( (x,myrawdep) )

			#print "potential revdeps for "+cpv+":",map(lambda x:x[0],myret)

		return myret

	def parse_dep(self, atom, cpv, others):

		""" Returns 1 if cpv and no package in others will satisfy atom, 0 otherwise.

		atom is either a DEPEND atom, or a list beginning with '||'. """

		if type(atom) is list:

			# We have a '||' construct.

			mylist = atom[:]

			head = mylist.pop(0)

			if head == "||":

				# Does cpv satisfy any of the alternatives? If not, return 0.

				if True not in map(lambda x:cpv_satisfies_dep(cpv,x), mylist):

					return 0

				# cpv satisfies the || dep. Now check the others.

				for p in others:

					if True in map(lambda x:cpv_satisfies_dep(cpv,x), mylist):

						# Another packages satisfies it.

						return 0

				return 1

			else:

				portage.writemsg("revdepgraph: parse_dep: don't understand " + str(atom) + ".\n")

				raise ValueError, str(atom)

		else:

			#print "atom: " + atom

			if portage.pkgsplit(portage.dep_getcpv(atom)):

				mycp = portage.pkgsplit( portage.dep_getcpv(atom) )[0]

			else:

				mycp = atom

			if mycp in portage.settings.virtuals.keys():

				#print "testing virtual",mycp

				myop = portage.get_operator(atom)

				if not myop:

					# A virtual. Yay.

					vardbapi = portage.db[self.myroot]["vartree"].dbapi

					myprovide = vardbapi.aux_get(cpv, ["PROVIDE"])[0].split()

					#print "myprovide:",myprovide

					if mycp not in myprovide:

						#print "mycp not in myprovide"

						return 0

					for p in others:

						myprovide = vardbapi.aux_get(p, ["PROVIDE"])[0].split()

						if mycp in myprovide:

							#print p,"satisfies virtual",mycp

							return 0

					return 1

				else:

					# A virtual with an operator. Even better.

					vardbapi = portage.db[self.myroot]["vartree"].dbapi

					myprovide = vardbapi.aux_get(cpv, ["PROVIDE"])[0].split()

					if mycp not in myprovide:

						return 0

					# It provides the right virtual; does it have the right version number?

					mycpver,mycprev = portage.pkgsplit(cpv)[1:3]

					# This is probably cleaner than switching through all the operators here...

					if not cpv_satisfies_dep(mycp+"-"+mycpver+"-"+mycprev, atom):

						return 0

					for p in others:

						myprovide = vardbapi.aux_get(cpv, ["PROVIDE"])[0].split()

						if mycp not in myprovide:

							continue

						myver,myrev = portage.pkgsplit(p)[1:3]

						if cpv_satisfies_dep(mycp+"-"+myver+"-"+myrev, atom):

							return 0

					return 1

			else:

				# A simple depend atom.

				#print "Simple atom", atom

				if not cpv_satisfies_dep(cpv, atom):

					return 0

				for p in others:

					if cpv_satisfies_dep(p, atom):

						return 0

				return 1

		# Stick this here just in case...

		return 0

	def dep_flatten(self, dep):

		" Flattens out every sublist not beginning with '||'. "

		#print "attempting to flatten:", dep

		returnme = []

		for x in dep:

			#print "x:", x

			if type(x) is list and len(x)>0 and x[0] != '||':

				returnme = returnme + self.dep_flatten(x)

			elif type(x) is not list:

				returnme.append(x)

		return returnme

	def workaround_broken_use_dep(self, myrawdep):

		#return string.join(map((lambda x: (x[0]=='!' and x[-1]!='?') and x+'?' or x), string.split(myrawdep)))

		#print "workaround: myrawdep=",myrawdep

		mysplit=myrawdep.split()

		for x in range(0, len(mysplit)-1):

			if mysplit[x][0]=='!' and mysplit[x][-1]!='?' and mysplit[x+1]=='(':

				mysplit[x] = mysplit[x]+'?'

		#print mysplit

		return string.join(mysplit)

	def direct_revdeps(self, cpv):

		" Returns a list of first-level reverse dependencies on a given package. "

		#print "calculating revdeps for " + cpv

		vardbapi=portage.db[self.myroot]["vartree"].dbapi

		myinstcpvs = vardbapi.cpv_all()

		while cpv in myinstcpvs:

			myinstcpvs.remove(cpv)

		myrevdeps = []

		for myp,myrawdep in self.potential_revdeps(cpv):

			# Check the rdepend string. Does it really require this package?

			#print "checking " + myp

			myuse = vardbapi.aux_get(myp, ["USE"])[0].split()

			#print "mydep=", myrawdep

			# use_reduce doesn't handle '!flag ( package )'; workaround

			mydep = self.workaround_broken_use_dep(myrawdep)

			#print "mydep=", mydep

			mydep = portage_dep.paren_reduce(mydep)

			mydep = portage_dep.dep_opconvert(mydep)

			mydep = portage_dep.use_reduce(mydep,myuse)

			#print "mydep=", mydep

			# At this point we need to flatten out any sublist not beginning with '||'.

			mydep = self.dep_flatten(mydep)

			#print "mydep=", mydep

			for myatom in mydep:

				#print "Checking atom", myatom

				if self.parse_dep(myatom, cpv, myinstcpvs):

					# This package requires cpv. Add it to the list.

					#print "Found revdep " + myp + " for " + cpv

					myrevdeps.append(myp)

					break

		return myrevdeps

	def create(self, cpv, myparent=None, addme=1, buildtimedeps=0):

		""" Creates the digraph. This function is a good deal simpler than the normal depgraph creation,

		since there are so many fewer possible scenarios to worry about. """

		#jbigkey = string.join(mybigkey)

		#if self.digraph.hasnode(jbigkey+" unmerge"):

		#	return 1

		if self.digraph.hasnode(cpv):

			return 1

		if buildtimedeps:

			self.depvars=["DEPEND","RDEPEND","PDEPEND"]

		else:

			self.depvars=["RDEPEND"]

		update_spinner()

		#print "mybigkey: ", mybigkey

		#mytype,myroot,mykey = mybigkey

		#self.myroot = myroot

		self.myroot = portage.root

		#if mytype not in ["unmerge"]:

			#portage.writemsg("Using revdeps for something other than unmerge?\n")

		# Check that mykey is valid...

		if not portage.pkgsplit(cpv):

			portage.writemsg("Invalid package key: " + cpv + "\n")

			sys.exit(1)

		vardbapi = portage.db[self.myroot]["vartree"].dbapi

		if addme:

			#print "adding '"+cpv+"'; parent=",myparent

			#print self.digraph.allnodes()

			self.digraph.addnode(cpv, myparent)

		for mydep in self.direct_revdeps(cpv):

			self.create( mydep, cpv, 1 )

	def getpackages(self):

		#return map(lambda x: string.split(x)[2], self.digraph.allnodes())

		return self.digraph.allnodes()

	if unmerge_action=="unmerge" and "--nodeps" not in myopts:

		# Print the calculating deps message here, instead of once per package.

		print

		portage.writemsg("Calculating reverse dependencies  ")

		# Also create the revdepgraph here once, so that we can reuse it. Should be significantly

		# more efficient when unmerging multiple packages.

		myrdepgraph=revdepgraph()

			if "--nodeps" in myopts:

				# We're not interested in revdeps, so just add this package to the pkgmap.

	if unmerge_action=="unmerge" and "--nodeps" not in myopts:

		# Above, we didn't actually add packages to pkgmap, so we need to do that here.

		print myrdepgraph.getpackages()

		for x in myrdepgraph.getpackages():

			print x

			mycp = portage.pkgsplit(x)[0]

			if not pkgmap.has_key(mycp):

				pkgmap[mycp]={"selected":[],"protected":[],"omitted":[]}

			pkgmap[mycp]["selected"].append(x)

			numselected = numselected+1

		sys.stdout.write("\b\b  ...done!\n\n")