Index: pym/portage/dep.py
===================================================================
--- pym/portage/dep.py	(revision 13651)
+++ pym/portage/dep.py	(working copy)
@@ -339,7 +339,38 @@
 			retlist.append(deplist[x])
 		x += 1
 	return retlist
+	
+def dep_restructure(deplist):
+	"""
+	Iterate recursively through a list of deps, if the
+	dep is a '||' or 'useflag?' operator, combine it with the
+	list of deps that follows.
 
+	Example usage:
+		>>> test = ["blah", "||", ["foo", "bar"], "useflag?", ["baz"] ]
+		>>> dep_opconvert(test)
+		['blah', ['||', ['foo', 'bar', 'baz'] ], [ "useflag?", ["baz"] ] ]
+
+	@param deplist: A list of deps to format
+	@type mydep: List
+	@rtype: List
+	@return:
+		The new list with the new ordering
+	"""
+
+	retlist = []
+	x = 0
+	while x != len(deplist):
+		if isinstance(deplist[x], list):
+			retlist.append(dep_restructure(deplist[x]))
+		elif deplist[x] == "||" or deplist[x][-1] == "?":
+			retlist.append([deplist[x]] + [ dep_restructure(deplist[x+1]) ] )
+			x += 1
+		else:
+			retlist.append(deplist[x])
+		x += 1
+	return retlist
+
 class _use_dep(object):
 
 	__slots__ = ("__weakref__", "conditional",
Index: pym/_emerge/__init__.py
===================================================================
--- pym/_emerge/__init__.py	(revision 13651)
+++ pym/_emerge/__init__.py	(working copy)
@@ -4752,6 +4752,7 @@
 		self._unsatisfied_blockers_for_display = None
 		self._circular_deps_for_display = None
 		self._dep_stack = []
+		self._deps = []
 		self._unsatisfied_deps = []
 		self._initially_unsatisfied_deps = []
 		self._ignored_deps = []
@@ -5033,15 +5034,19 @@
 
 	def _create_graph(self, allow_unsatisfied=False):
 		dep_stack = self._dep_stack
-		while dep_stack:
-			self.spinner.update()
-			dep = dep_stack.pop()
-			if isinstance(dep, Package):
-				if not self._add_pkg_deps(dep,
-					allow_unsatisfied=allow_unsatisfied):
+		deps = self._deps
+		while dep_stack or deps:
+			while dep_stack:
+				self.spinner.update()
+				dep = dep_stack.pop()
+				if isinstance(dep, Package):
+					if not self._add_pkg_deps(dep,
+						allow_unsatisfied=allow_unsatisfied):
+						return 0
+					continue
+				if not self._add_dep(dep, allow_unsatisfied=allow_unsatisfied):
 					return 0
-				continue
-			if not self._add_dep(dep, allow_unsatisfied=allow_unsatisfied):
+			if not self._process_deps(allow_unsatisfied):
 				return 0
 		return 1
 
@@ -5341,20 +5346,53 @@
 			elif root_deps == "rdeps":
 				edepend["DEPEND"] = ""
 
-		deps = (
-			(bdeps_root, edepend["DEPEND"],
-				self._priority(buildtime=(not bdeps_optional),
-				optional=bdeps_optional)),
-			(myroot, edepend["RDEPEND"], self._priority(runtime=True)),
-			(myroot, edepend["PDEPEND"], self._priority(runtime_post=True))
-		)
+		for dep_type in ["DEPEND", "RDEPEND", "PDEPEND"]:
+			dep_string = edepend[dep_type]
+			if not dep_string:
+				continue
+			
+			try:
+				dep_string = portage.dep.paren_reduce(dep_string)
+			except portage.exception.InvalidDependString, e:				
+				return 0
 
+			dep_string = portage.dep.dep_restructure(dep_string)
+			
+			for dep in dep_string:
+				self._deps.append((pkg, bdeps_root, dep,
+					self._priority(buildtime=(not bdeps_optional),
+					optional=bdeps_optional)))
+
+		return 1
+		
+	def _is_or_dep(self, dep):
+		if isinstance(dep,list):
+			for d in dep:
+				if self._is_or_dep(d):
+					return 1
+		else:
+			return dep.find("||") != -1
+		
+		return 0
+
+	def _process_deps(self, allow_unsatisfied=False):
 		debug = "--debug" in self.myopts
-		strict = mytype != "installed"
+		deps = self._deps
 		try:
-			for dep_root, dep_string, dep_priority in deps:
+			while deps:
+				is_or_dep = self._is_or_dep(deps[-1][2])
+
+				if is_or_dep and self._dep_stack:
+					#don't process or-deps if we don't have to
+					return 1
+				pkg, dep_root, dep_string, dep_priority = deps.pop()
 				if not dep_string:
 					continue
+				mytype = pkg.type_name
+				myuse = pkg.use.enabled
+				jbigkey = pkg
+				depth = pkg.depth + 1
+				strict = mytype != "installed"
 				if debug:
 					print
 					print "Parent:   ", jbigkey
@@ -5362,8 +5400,12 @@
 					print "Priority:", dep_priority
 				vardb = self.roots[dep_root].trees["vartree"].dbapi
 				try:
+					if isinstance(dep_string,list):
+						new_dep_string = portage.dep.paren_enclose(dep_string)
+					else:
+						new_dep_string = dep_string
 					selected_atoms = self._select_atoms(dep_root,
-						dep_string, myuse=myuse, parent=pkg, strict=strict,
+						new_dep_string, myuse=myuse, parent=pkg, strict=strict,
 						priority=dep_priority)
 				except portage.exception.InvalidDependString, e:
 					show_invalid_depstring_notice(jbigkey, dep_string, str(e))