--- emerge.orig	2004-08-17 11:23:33.482194936 +0100
+++ emerge	2004-08-17 11:52:31.465981240 +0100
@@ -11,7 +11,7 @@
 from stat import *
 from output import *
 
-import portage
+import portage, portage_dep
 import portage_util
 import portage_locks
 import portage_exception
@@ -35,7 +35,7 @@
 	colours: a List of Functions taking and returning a String, used to 
 	process the responses for display. Typically these will be functions 
 	like red() but could be e.g. lambda x: "DisplayString".
-	If responses is omitted, defaults to ["Yes, "No"], [green, red].
+	If responses is omitted, defaults to ["Yes", "No"], [green, red].
 	If only colours is omitted, defaults to [bold, ...].
 
 	Returns a member of the List responses. (If called without optional
@@ -1820,6 +1820,220 @@
 			else:
 				sys.exit(0)
 
+# 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()
+		
+
 def unmerge(unmerge_action, unmerge_files):
 	candidate_catpkgs=[]
 	global_unmerge=0
@@ -1906,6 +2120,14 @@
 	
 	pkgmap={}
 	numselected=0
+	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()
+	
 	for x in candidate_catpkgs:
 		#cycle through all our candidate deps and determine what will and will not get unmerged
 		try:
@@ -1930,6 +2152,8 @@
 		if not pkgmap.has_key(mykey):
 			pkgmap[mykey]={"protected":[], "selected":[], "omitted":[] }
 		if unmerge_action=="unmerge":
+			if "--nodeps" in myopts:
+				# We're not interested in revdeps, so just add this package to the pkgmap.
 				for y in mymatch:
 					if y not in pkgmap[mykey]["selected"]:
 						pkgmap[mykey]["selected"].append(y)
@@ -1940,7 +2164,11 @@
 					print yellow("\a!!! This could be damaging to your system.\n")
 					if "--pretend" not in myopts:
 						countdown(10,red("Press Ctrl-C to Stop"))
-
+			else:
+				# Add this package to the revdepgraph.
+				for y in mymatch:
+					myrdepgraph.create(y)
+				
 		else:
 			#unmerge_action in ["prune", clean"]
 			slotmap={}
@@ -1966,6 +2194,20 @@
 					pkgmap[mykey]["selected"].append(slotmap[myslot][ckey])
 					numselected=numselected+1
 				#ok, now the last-merged package is protected, and the rest are selected
+
+	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")
+		
 	if global_unmerge and not numselected:
 		print "\n>>> No outdated packages were found on your system.\n"
 		return 0