Index: pym/_emerge/__init__.py
===================================================================
--- pym/_emerge/__init__.py	(revision 13652)
+++ pym/_emerge/__init__.py	(working copy)
@@ -4754,6 +4754,7 @@
 		self._unsatisfied_blockers_for_display = None
 		self._circular_deps_for_display = None
 		self._dep_stack = []
+		self._dep_disjuctive_stack = []
 		self._unsatisfied_deps = []
 		self._initially_unsatisfied_deps = []
 		self._ignored_deps = []
@@ -5035,16 +5036,20 @@
 
 	def _create_graph(self, allow_unsatisfied=False):
 		dep_stack = self._dep_stack
-		while dep_stack:
+		dep_disjuctive_stack = self._dep_disjuctive_stack
+		while dep_stack or dep_disjuctive_stack:
 			self.spinner.update()
-			dep = dep_stack.pop()
-			if isinstance(dep, Package):
-				if not self._add_pkg_deps(dep,
-					allow_unsatisfied=allow_unsatisfied):
+			while dep_stack:
+				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):
-				return 0
+			if dep_disjuctive_stack:
+				self._pop_disjunctive_dep()
 		return 1
 
 	def _add_dep(self, dep, allow_unsatisfied=False):
@@ -5354,6 +5359,9 @@
 		debug = "--debug" in self.myopts
 		strict = mytype != "installed"
 		try:
+			if not strict:
+				portage.dep._dep_check_strict = False
+
 			for dep_root, dep_string, dep_priority in deps:
 				if not dep_string:
 					continue
@@ -5362,6 +5370,24 @@
 					print "Parent:   ", jbigkey
 					print "Depstring:", dep_string
 					print "Priority:", dep_priority
+
+				try:
+					dep_string = portage.dep.paren_normalize(
+						portage.dep.use_reduce(
+						portage.dep.paren_reduce(dep_string),
+						uselist=pkg.use.enabled))
+				except portage.exception.InvalidDependString, e:
+					if pkg.installed:
+						del e
+						continue
+					show_invalid_depstring_notice(pkg, dep_string, str(e))
+					return 0
+
+				dep_string = self._queue_disjunctive_deps(
+					pkg, dep_root, dep_priority, dep_string)
+
+				dep_string = portage.dep.paren_enclose(dep_string)
+
 				vardb = self.roots[dep_root].trees["vartree"].dbapi
 				try:
 					selected_atoms = self._select_atoms(dep_root,
@@ -5416,8 +5442,24 @@
 			portage.writemsg("!!! Please notify the package maintainer " + \
 				"that atoms must be fully-qualified.\n", noiselevel=-1)
 			return 0
+		finally:
+			portage.dep._dep_check_strict = True
 		return 1
 
+	def _queue_disjunctive_deps(self, pkg, dep_root, dep_priority, dep_string):
+		"""
+		Queue disjunctive (virtual and ||) deps in self._dep_disjuctive_stack.
+		Return only non-disjunctive deps.
+		"""
+		raise NotImplementedError(self)
+
+	def _pop_disjunctive_dep(self):
+		"""
+		Pop one disjuctive dep from self._dep_disjuctive_stack, and use it to
+		populate self._dep_stack.
+		"""
+		raise NotImplementedError(self)
+
 	def _priority(self, **kwargs):
 		if "remove" in self.myparams:
 			priority_constructor = UnmergeDepPriority