portage.dep.use_reduce: Work on depstrings instead of paren_reduce'd dep arrays

This change makes paren_reduce and paren_normalize calls for use_reduce redundant,
resp. wrong. All consumers inside portage are adopted.

10 files changed, 342 insertions, 174 deletions

diff --git a/pym/_emerge/Package.py b/pym/_emerge/Package.py
index e86eab334..58c453ff9 100644
--- a/pym/_emerge/Package.py
+++ b/pym/_emerge/Package.py
@@ -1,4 +1,4 @@
-# Copyright 1999-2009 Gentoo Foundation
+# Copyright 1999-2010 Gentoo Foundation
 # Distributed under the terms of the GNU General Public License v2
 
 import re
@@ -6,8 +6,8 @@ import sys
 from itertools import chain
 import portage
 from portage.cache.mappings import slot_dict_class
-from portage.dep import isvalidatom, paren_reduce, use_reduce, \
-	paren_normalize, paren_enclose, _slot_re
+from portage.dep import isvalidatom, use_reduce, \
+	paren_enclose, _slot_re
 from _emerge.Task import Task
 
 if sys.hexversion >= 0x3000000:
@@ -310,8 +310,7 @@ class _PackageMetadataWrapper(_PackageMetadataWrapperBase):
 		if k in self._use_conditional_keys:
 			if self._pkg.root_config.settings.local_config and '?' in v:
 				try:
-					v = paren_enclose(paren_normalize(use_reduce(
-						paren_reduce(v), uselist=self._pkg.use.enabled)))
+					v = paren_enclose(use_reduce(v, uselist=self._pkg.use.enabled))
 				except portage.exception.InvalidDependString:
 					# This error should already have been registered via
 					# self._pkg._invalid_metadata().
@@ -336,7 +335,7 @@ class _PackageMetadataWrapper(_PackageMetadataWrapperBase):
 			getattr(self, "_set_" + k.lower())(k, v)
 		elif k in self._use_conditional_keys:
 			try:
-				reduced = use_reduce(paren_reduce(v), matchall=1)
+				reduced = use_reduce(v, matchall=1)
 			except portage.exception.InvalidDependString as e:
 				self._pkg._invalid_metadata(k + ".syntax", "%s: %s" % (k, e))
 			else:
diff --git a/pym/_emerge/depgraph.py b/pym/_emerge/depgraph.py
index e9f7c4426..10ad5e491 100644
--- a/pym/_emerge/depgraph.py
+++ b/pym/_emerge/depgraph.py
@@ -1208,10 +1208,8 @@ class depgraph(object):
 
 				try:
 
-					dep_string = portage.dep.paren_normalize(
-						portage.dep.use_reduce(
-						portage.dep.paren_reduce(dep_string),
-						uselist=self._pkg_use_enabled(pkg)))
+					dep_string = portage.dep.use_reduce(dep_string,
+						uselist=self._pkg_use_enabled(pkg))
 
 					dep_string = list(self._queue_disjunctive_deps(
 						pkg, dep_root, dep_priority, dep_string))
@@ -2628,10 +2626,8 @@ class depgraph(object):
 
 			for key in "DEPEND", "RDEPEND", "PDEPEND", "LICENSE":
 				dep = pkg.metadata[key]
-				old_val = set(portage.dep.paren_normalize( \
-					portage.dep.use_reduce(portage.dep.paren_reduce(dep), pkg.use.enabled)))
-				new_val = set(portage.dep.paren_normalize( \
-					portage.dep.use_reduce(portage.dep.paren_reduce(dep), new_use)))
+				old_val = set(portage.dep.use_reduce(dep, pkg.use.enabled))
+				new_val = set(portage.dep.use_reduce(dep, new_use))
 
 				if old_val != new_val:
 					return True
diff --git a/pym/portage/dbapi/bintree.py b/pym/portage/dbapi/bintree.py
index 31bb5f4ab..7dd179ce9 100644
--- a/pym/portage/dbapi/bintree.py
+++ b/pym/portage/dbapi/bintree.py
@@ -18,6 +18,7 @@ portage.proxy.lazyimport.lazyimport(globals(),
 
 from portage.cache.mappings import slot_dict_class
 from portage.dbapi.virtual import fakedbapi
+from portage.dep import use_reduce, paren_enclose
 from portage.exception import InvalidPackageName, \
 	PermissionDenied, PortageException
 from portage.localization import _
@@ -1102,13 +1103,10 @@ class binarytree(object):
 		use = [f for f in use if f in iuse]
 		use.sort()
 		metadata["USE"] = " ".join(use)
-		from portage.dep import paren_reduce, use_reduce, \
-			paren_normalize, paren_enclose
 		for k in self._pkgindex_use_evaluated_keys:
 			try:
-				deps = paren_reduce(metadata[k])
+				deps = metadata[k]
 				deps = use_reduce(deps, uselist=raw_use)
-				deps = paren_normalize(deps)
 				deps = paren_enclose(deps)
 			except portage.exception.InvalidDependString as e:
 				writemsg("%s: %s\n" % (k, str(e)),
diff --git a/pym/portage/dbapi/porttree.py b/pym/portage/dbapi/porttree.py
index 2cf6989b0..f530b6170 100644
--- a/pym/portage/dbapi/porttree.py
+++ b/pym/portage/dbapi/porttree.py
@@ -742,8 +742,7 @@ class portdbapi(dbapi):
 				"getFetchMap(): '%s' has unsupported EAPI: '%s'" % \
 				(mypkg, eapi.lstrip("-")))
 
-		myuris = paren_reduce(myuris)
-		_src_uri_validate(mypkg, eapi, myuris)
+		_src_uri_validate(mypkg, eapi, paren_reduce(myuris))
 		myuris = use_reduce(myuris, uselist=useflags,
 			matchall=(useflags is None))
 		myuris = flatten(myuris)
diff --git a/pym/portage/dbapi/vartree.py b/pym/portage/dbapi/vartree.py
index 28a03ad2c..130f8f537 100644
--- a/pym/portage/dbapi/vartree.py
+++ b/pym/portage/dbapi/vartree.py
@@ -11,7 +11,7 @@ portage.proxy.lazyimport.lazyimport(globals(),
 	'portage.data:portage_gid,portage_uid,secpass',
 	'portage.dbapi.dep_expand:dep_expand',
 	'portage.dep:dep_getkey,isjustname,flatten,match_from_list,' + \
-	 	'use_reduce,paren_reduce,_slot_re',
+	 	'use_reduce,_slot_re',
 	'portage.elog:elog_process',
 	'portage.locks:lockdir,unlockdir',
 	'portage.output:bold,colorize',
@@ -1796,7 +1796,7 @@ class vartree(object):
 			mylines, myuse = self.dbapi.aux_get(mycpv, ["PROVIDE", "USE"])
 			if mylines:
 				myuse = myuse.split()
-				mylines = flatten(use_reduce(paren_reduce(mylines), uselist=myuse))
+				mylines = flatten(use_reduce(mylines, uselist=myuse))
 				for myprovide in mylines:
 					mys = catpkgsplit(myprovide)
 					if not mys:
diff --git a/pym/portage/dep/__init__.py b/pym/portage/dep/__init__.py
index 30b181988..32d3155ab 100644
--- a/pym/portage/dep/__init__.py
+++ b/pym/portage/dep/__init__.py
@@ -1,5 +1,5 @@
 # deps.py -- Portage dependency resolution functions
-# Copyright 2003-2004 Gentoo Foundation
+# Copyright 2003-2010 Gentoo Foundation
 # Distributed under the terms of the GNU General Public License v2
 
 __all__ = [
@@ -214,120 +214,114 @@ def paren_enclose(mylist):
 			mystrparts.append(x)
 	return " ".join(mystrparts)
 
-# This is just for use by emerge so that it can enable a backward compatibility
-# mode in order to gracefully deal with installed packages that have invalid
-# atoms or dep syntax.  For backward compatibility with api consumers, strict
-# behavior will be explicitly enabled as necessary.
-_dep_check_strict = False
-
-def use_reduce(deparray, uselist=[], masklist=[], matchall=0, excludeall=[]):
+def use_reduce(depstr, uselist=[], masklist=[], matchall=False, excludeall=[]):
 	"""
-	Takes a paren_reduce'd array and reduces the use? conditionals out
-	leaving an array with subarrays
+	Takes a dep string and reduces the use? conditionals out, leaving an array
+	with subarrays. All redundant brackets are removed.
 
-	@param deparray: paren_reduce'd list of deps
-	@type deparray: List
-	@param uselist: List of use flags
+	@param deparray: depstring
+	@type deparray: String
+	@param uselist: List of use enabled flags
 	@type uselist: List
-	@param masklist: List of masked flags
+	@param masklist: List of masked flags (always treated as disabled)
 	@type masklist: List
-	@param matchall: Resolve all conditional deps unconditionally.  Used by repoman
-	@type matchall: Integer
+	@param matchall: Treat all conditionals as active. Used by repoman. 
+	@type matchall: Bool
+	@param matchall: List of flags for which negated conditionals are always treated as inactive.
+	@type matchall: List
 	@rtype: List
 	@return: The use reduced depend array
 	"""
-	# Quick validity checks
-	for x, y in enumerate(deparray):
-		if y == '||':
-			if len(deparray) - 1 == x or not isinstance(deparray[x+1], list):
-				raise portage.exception.InvalidDependString(_('%(dep)s missing atom list in "%(deparray)s"') % {"dep": deparray[x], "deparray": paren_enclose(deparray)})
-	if deparray and deparray[-1] and deparray[-1][-1] == "?":
-		raise portage.exception.InvalidDependString(_('Conditional without target in "%s"') % paren_enclose(deparray))
-
-	global _dep_check_strict
-
-	mydeparray = deparray[:]
-	rlist = []
-	while mydeparray:
-		head = mydeparray.pop(0)
-
-		if not isinstance(head, basestring):
-			additions = use_reduce(head, uselist, masklist, matchall, excludeall)
-			if additions:
-				rlist.append(additions)
-			elif rlist and rlist[-1] == "||":
-			#XXX: Currently some DEPEND strings have || lists without default atoms.
-			#	raise portage.exception.InvalidDependString("No default atom(s) in \""+paren_enclose(deparray)+"\"")
-				rlist.append([])
 
+	def is_active(conditional):
+		if conditional.startswith("!"):
+			flag = conditional[1:-1]
+			is_negated = True
 		else:
-			if head[-1:] == "?": # Use reduce next group on fail.
-				# Pull any other use conditions and the following atom or list into a separate array
-				newdeparray = [head]
-				while isinstance(newdeparray[-1], basestring) and \
-					newdeparray[-1][-1:] == "?":
-					if mydeparray:
-						newdeparray.append(mydeparray.pop(0))
-					else:
-						raise ValueError(_("Conditional with no target."))
-
-				# Deprecation checks
-				warned = 0
-				if len(newdeparray[-1]) == 0:
-					sys.stderr.write(_("Note: Empty target in string. (Deprecated)\n"))
-					warned = 1
-				if len(newdeparray) != 2:
-					sys.stderr.write(_("Note: Nested use flags without parenthesis (Deprecated)\n"))
-					warned = 1
-				if warned:
-					sys.stderr.write("  --> "+" ".join(map(str,[head]+newdeparray))+"\n")
-
-				# Check that each flag matches
-				ismatch = True
-				missing_flag = False
-				for head in newdeparray[:-1]:
-					head = head[:-1]
-					if not head:
-						missing_flag = True
-						break
-					if head.startswith("!"):
-						head_key = head[1:]
-						if not head_key:
-							missing_flag = True
-							break
-						if not matchall and head_key in uselist or \
-							head_key in excludeall:
-							ismatch = False
-							break
-					elif head not in masklist:
-						if not matchall and head not in uselist:
-							ismatch = False
-							break
-					else:
-						ismatch = False
-				if missing_flag:
-					raise portage.exception.InvalidDependString(
-						_('Conditional without flag: "') + \
-						paren_enclose([head+"?", newdeparray[-1]])+"\"")
-
-				# If they all match, process the target
-				if ismatch:
-					target = newdeparray[-1]
-					if isinstance(target, list):
-						additions = use_reduce(target, uselist, masklist, matchall, excludeall)
-						if additions:
-							rlist.append(additions)
-					elif not _dep_check_strict:
-						# The old deprecated behavior.
-						rlist.append(target)
-					else:
-						raise portage.exception.InvalidDependString(
-							_("Conditional without parenthesis: '%s?'") % head)
+			flag = conditional[:-1]
+			is_negated = False
+
+		if not flag:
+			raise portage.exception.InvalidDependString(
+				_("malformed syntax: '%s'") % depstr)
+
+		if is_negated and flag in excludeall:
+			return False
+
+		if flag in masklist:
+			return is_negated
+
+		if matchall:
+			return True
+
+		return (flag in uselist and not is_negated) or \
+			(flag not in uselist and is_negated)
+
+	mysplit = depstr.split()
+	level = 0
+	stack = [[]]
+	need_bracket = False
+
+	for token in mysplit:
+		if token == "(":
+			need_bracket = False
+			stack.append([])
+			level += 1
+		elif token == ")":
+			if need_bracket:
+				raise portage.exception.InvalidDependString(
+					_("malformed syntax: '%s'") % depstr)
+			if level > 0:
+				level -= 1
+				l = stack.pop()
+				ignore = False
+
+				if stack[level]:
+					if stack[level][-1] == "||" and not l:
+						stack[level].pop()
+					elif stack[level][-1][-1] == "?":
+						if not is_active(stack[level][-1]):
+							ignore = True
+						stack[level].pop()
 
+				if l and not ignore:
+					if not stack[level] or stack[level][-1] != "||":
+						#Optimize: ( ( ... ) ) -> ( ... )
+						stack[level].extend(l)
+					elif len(l) == 1 and stack[level][-1] == "||":
+						#Optimize: || ( A ) -> A
+						stack[level].pop()
+						stack[level].extend(l)
+					elif len(l) == 2 and l[0] == "||" and stack[level][-1] == "||":
+						#Optimize: 	|| ( || ( ... ) ) -> || ( ... )
+						stack[level].pop()
+						stack[level].extend(l)
+					else:
+						stack[level].append(l)
 			else:
-				rlist += [head]
+				raise portage.exception.InvalidDependString(
+					_("malformed syntax: '%s'") % depstr)
+		elif token == "||":
+			if need_bracket:
+				raise portage.exception.InvalidDependString(
+					_("malformed syntax: '%s'") % depstr)
+			need_bracket = True
+			stack[level].append(token)
+		else:
+			if need_bracket or "(" in token or ")" in token or "|" in token:
+				raise portage.exception.InvalidDependString(
+					_("malformed syntax: '%s'") % depstr)
 
-	return rlist
+			if token[-1] == "?":
+				need_bracket = True
+
+			stack[level].append(token)
+
+	if level != 0 or need_bracket:
+		raise portage.exception.InvalidDependString(
+			_("malformed syntax: '%s'") % depstr)
+
+	return stack[0]
 
 def dep_opconvert(deplist):
 	"""
diff --git a/pym/portage/dep/dep_check.py b/pym/portage/dep/dep_check.py
index 8747bb148..dd6864227 100644
--- a/pym/portage/dep/dep_check.py
+++ b/pym/portage/dep/dep_check.py
@@ -6,7 +6,7 @@ __all__ = ['dep_check', 'dep_eval', 'dep_wordreduce', 'dep_zapdeps']
 import logging
 
 import portage
-from portage.dep import Atom, dep_opconvert, match_from_list, paren_reduce, \
+from portage.dep import Atom, dep_opconvert, match_from_list, \
 	remove_slot, use_reduce
 from portage.exception import InvalidAtom, InvalidDependString, ParseError
 from portage.localization import _
@@ -521,12 +521,6 @@ def dep_check(depstring, mydbapi, mysettings, use="yes", mode=None, myuse=None,
 		# WE ALSO CANNOT USE SETTINGS
 		myusesplit=[]
 
-	#convert parenthesis to sublists
-	try:
-		mysplit = paren_reduce(depstring)
-	except InvalidDependString as e:
-		return [0, str(e)]
-
 	mymasks = set()
 	useforce = set()
 	useforce.add(mysettings["ARCH"])
@@ -544,7 +538,7 @@ def dep_check(depstring, mydbapi, mysettings, use="yes", mode=None, myuse=None,
 		useforce.update(mysettings.useforce)
 		useforce.difference_update(mymasks)
 	try:
-		mysplit = use_reduce(mysplit, uselist=myusesplit,
+		mysplit = use_reduce(depstring, uselist=myusesplit,
 			masklist=mymasks, matchall=(use=="all"), excludeall=useforce)
 	except InvalidDependString as e:
 		return [0, str(e)]
diff --git a/pym/portage/package/ebuild/config.py b/pym/portage/package/ebuild/config.py
index f4f05179b..8fe2d4d30 100644
--- a/pym/portage/package/ebuild/config.py
+++ b/pym/portage/package/ebuild/config.py
@@ -34,7 +34,7 @@ from portage.dbapi.porttree import portdbapi
 from portage.dbapi.vartree import vartree
 from portage.dep import Atom, best_match_to_list, dep_opconvert, \
 	flatten, isvalidatom, match_from_list, match_to_list, \
-	paren_reduce, remove_slot, use_reduce
+	remove_slot, use_reduce
 from portage.env.loaders import KeyValuePairFileLoader
 from portage.exception import DirectoryNotFound, InvalidAtom, \
 	InvalidDependString, ParseError, PortageException
@@ -1278,10 +1278,7 @@ class config(object):
 			E2BIG errors as in bug #262647.
 			"""
 			try:
-				licenses = set(flatten(
-					use_reduce(paren_reduce(
-					settings['LICENSE']),
-					uselist=use)))
+				licenses = set(flatten(use_reduce(settings['LICENSE'],uselist=use)))
 			except InvalidDependString:
 				licenses = set()
 			licenses.discard('||')
@@ -1302,10 +1299,7 @@ class config(object):
 
 		def _restrict(self, use, settings):
 			try:
-				restrict = set(flatten(
-					use_reduce(paren_reduce(
-					settings['RESTRICT']),
-					uselist=use)))
+				restrict = set(flatten(use_reduce(settings['RESTRICT'],uselist=use)))
 			except InvalidDependString:
 				restrict = set()
 			return ' '.join(sorted(restrict))
@@ -1912,8 +1906,7 @@ class config(object):
 				for x in plicence_list:
 					accept_license.extend(x)
 
-		licenses = set(flatten(use_reduce(paren_reduce(
-			metadata["LICENSE"]), matchall=1)))
+		licenses = set(flatten(use_reduce(metadata["LICENSE"], matchall=1)))
 		licenses.discard('||')
 
 		acceptable_licenses = set()
@@ -1933,8 +1926,7 @@ class config(object):
 		else:
 			use = []
 
-		license_struct = use_reduce(
-			paren_reduce(license_str), uselist=use)
+		license_struct = use_reduce(license_str, uselist=use)
 		license_struct = dep_opconvert(license_struct)
 		return self._getMaskedLicenses(license_struct, acceptable_licenses)
 
@@ -2004,8 +1996,7 @@ class config(object):
 				for x in pproperties_list:
 					accept_properties.extend(x)
 
-		properties = set(flatten(use_reduce(paren_reduce(
-			metadata["PROPERTIES"]), matchall=1)))
+		properties = set(flatten(use_reduce(metadata["PROPERTIES"], matchall=1)))
 		properties.discard('||')
 
 		acceptable_properties = set()
@@ -2025,8 +2016,7 @@ class config(object):
 		else:
 			use = []
 
-		properties_struct = use_reduce(
-			paren_reduce(properties_str), uselist=use)
+		properties_struct = use_reduce(properties_str, uselist=use)
 		properties_struct = dep_opconvert(properties_struct)
 		return self._getMaskedProperties(properties_struct, acceptable_properties)
 
@@ -2118,7 +2108,7 @@ class config(object):
 			myuse = mydbapi["USE"]
 		else:
 			myuse = mydbapi.aux_get(mycpv, ["USE"])[0]
-		virts = flatten(use_reduce(paren_reduce(provides), uselist=myuse.split()))
+		virts = flatten(use_reduce(provides, uselist=myuse.split()))
 
 		modified = False
 		cp = Atom(cpv_getkey(mycpv))
diff --git a/pym/portage/package/ebuild/doebuild.py b/pym/portage/package/ebuild/doebuild.py
index 34a7206e2..6ceafb0e1 100644
--- a/pym/portage/package/ebuild/doebuild.py
+++ b/pym/portage/package/ebuild/doebuild.py
@@ -37,8 +37,7 @@ from portage.const import EBUILD_SH_ENV_FILE, EBUILD_SH_ENV_DIR, \
 from portage.data import portage_gid, portage_uid, secpass, \
 	uid, userpriv_groups
 from portage.dbapi.virtual import fakedbapi
-from portage.dep import Atom, paren_enclose, paren_normalize, \
-	paren_reduce, use_reduce
+from portage.dep import Atom, paren_enclose, use_reduce
 from portage.elog import elog_process
 from portage.elog.messages import eerror, eqawarn
 from portage.exception import DigestException, FileNotFound, \
@@ -1073,8 +1072,7 @@ def _validate_deps(mysettings, myroot, mydo, mydbapi):
 
 	for k in misc_keys:
 		try:
-			use_reduce(
-				paren_reduce(metadata[k]), matchall=True)
+			use_reduce(metadata[k], matchall=True)
 		except InvalidDependString as e:
 			msgs.append("  %s: %s\n    %s\n" % (
 				k, metadata[k], str(e)))
@@ -1612,9 +1610,7 @@ def _post_src_install_uid_fix(mysettings, out):
 		v = mysettings.configdict['pkg'].get(k)
 		if v is None:
 			continue
-		v = paren_reduce(v)
 		v = use_reduce(v, uselist=use)
-		v = paren_normalize(v)
 		v = paren_enclose(v)
 		if not v:
 			continue
diff --git a/pym/portage/tests/dep/test_use_reduce.py b/pym/portage/tests/dep/test_use_reduce.py
index ac3a13c0f..a4a23242d 100644
--- a/pym/portage/tests/dep/test_use_reduce.py
+++ b/pym/portage/tests/dep/test_use_reduce.py
@@ -1,28 +1,230 @@
-# Copyright 2009 Gentoo Foundation
+# Copyright 2009-2010 Gentoo Foundation
 # Distributed under the terms of the GNU General Public License v2
 
 from portage.tests import TestCase
 from portage.exception import InvalidDependString
-from portage.dep import paren_reduce, use_reduce
-import portage.dep
-portage.dep._dep_check_strict = True
+from portage.dep import use_reduce
 
+class UseReduceTestCase(object):
+	def __init__(self, deparray, uselist=[], masklist=[], \
+		matchall=0, excludeall=[], expected_result=None):
+		self.deparray = deparray
+		self.uselist = uselist
+		self.masklist = masklist
+		self.matchall = matchall
+		self.excludeall = excludeall
+		self.expected_result = expected_result
+
+	def run(self):
+		return use_reduce(self.deparray, self.uselist, self.masklist, \
+			self.matchall, self.excludeall)
+				
 class UseReduce(TestCase):
 
 	def testUseReduce(self):
 
-		tests = (
-			('|| ( x y )',                                           True  ),
-			('|| x',                                                 False ),
-			('foo? ( x y )',                                         True  ),
-			('foo? ( bar? x y )',                                    False ),
-			('foo? x',                                               False ),
+		test_cases = (
+			UseReduceTestCase(
+				"a? ( A ) b? ( B ) !c? ( C ) !d? ( D )",
+				uselist = ["a", "b", "c", "d"],
+				expected_result = ["A", "B"]
+				),
+			UseReduceTestCase(
+				"a? ( A ) b? ( B ) !c? ( C ) !d? ( D )",
+				uselist = ["a", "b", "c"],
+				expected_result = ["A", "B", "D"]
+				),
+			UseReduceTestCase(
+				"a? ( A ) b? ( B ) !c? ( C ) !d? ( D )",
+				uselist = ["b", "c"],
+				expected_result = ["B", "D"]
+				),
+
+			UseReduceTestCase(
+				"a? ( A ) b? ( B ) !c? ( C ) !d? ( D )",
+				matchall = True,
+				expected_result = ["A", "B", "C", "D"]
+				),
+			UseReduceTestCase(
+				"a? ( A ) b? ( B ) !c? ( C ) !d? ( D )",
+				masklist = ["a", "c"],
+				expected_result = ["C", "D"]
+				),
+			UseReduceTestCase(
+				"a? ( A ) b? ( B ) !c? ( C ) !d? ( D )",
+				matchall = True,
+				masklist = ["a", "c"],
+				expected_result = ["B", "C", "D"]
+				),
+			UseReduceTestCase(
+				"a? ( A ) b? ( B ) !c? ( C ) !d? ( D )",
+				uselist = ["a", "b"],
+				masklist = ["a", "c"],
+				expected_result = ["B", "C", "D"]
+				),
+			UseReduceTestCase(
+				"a? ( A ) b? ( B ) !c? ( C ) !d? ( D )",
+				excludeall = ["a", "c"],
+				expected_result = ["D"]
+				),
+			UseReduceTestCase(
+				"a? ( A ) b? ( B ) !c? ( C ) !d? ( D )",
+				uselist = ["b"],
+				excludeall = ["a", "c"],
+				expected_result = ["B", "D"]
+				),
+			UseReduceTestCase(
+				"a? ( A ) b? ( B ) !c? ( C ) !d? ( D )",
+				matchall = True,
+				excludeall = ["a", "c"],
+				expected_result = ["A", "B", "D"]
+				),
+			UseReduceTestCase(
+				"a? ( A ) b? ( B ) !c? ( C ) !d? ( D )",
+				matchall = True,
+				excludeall = ["a", "c"],
+				masklist = ["b"],
+				expected_result = ["A", "D"]
+				),
+
+			
+			UseReduceTestCase(
+				"a? ( b? ( AB ) )",
+				uselist = ["a", "b"],
+				expected_result = ["AB"]
+				),
+			UseReduceTestCase(
+				"a? ( b? ( AB ) C )",
+				uselist = ["a"],
+				expected_result = ["C"]
+				),
+			UseReduceTestCase(
+				"a? ( b? ( || ( AB CD ) ) )",
+				uselist = ["a", "b"],
+				expected_result = ["||", ["AB", "CD"]]
+				),
+			UseReduceTestCase(
+				"|| ( || ( a? ( A ) b? ( B ) ) )",
+				uselist = ["a", "b"],
+				expected_result = ["||", ["A", "B"]]
+				),
+			UseReduceTestCase(
+				"|| ( || ( a? ( A ) b? ( B ) ) )",
+				uselist = ["a"],
+				expected_result = ["A"]
+				),
+			UseReduceTestCase(
+				"|| ( || ( a? ( A ) b? ( B ) ) )",
+				uselist = [],
+				expected_result = []
+				),
+			UseReduceTestCase(
+				"|| ( || ( a? ( || ( A c? ( C ) ) ) b? ( B ) ) )",
+				uselist = [],
+				expected_result = []
+				),
+			UseReduceTestCase(
+				"|| ( || ( a? ( || ( A c? ( C ) ) ) b? ( B ) ) )",
+				uselist = ["a"],
+				expected_result = ["A"]
+				),
+			UseReduceTestCase(
+				"|| ( || ( a? ( || ( A c? ( C ) ) ) b? ( B ) ) )",
+				uselist = ["b"],
+				expected_result = ["B"]
+				),
+			UseReduceTestCase(
+				"|| ( || ( a? ( || ( A c? ( C ) ) ) b? ( B ) ) )",
+				uselist = ["c"],
+				expected_result = []
+				),
+			UseReduceTestCase(
+				"|| ( || ( a? ( || ( A c? ( C ) ) ) b? ( B ) ) )",
+				uselist = ["a", "c"],
+				expected_result = ["||", [ "A", "C"]]
+				),
+			
+			#paren_reduce tests
+			UseReduceTestCase(
+				"A",
+				expected_result = ["A"]),
+			UseReduceTestCase(
+				"( A )",
+				expected_result = ["A"]),
+			UseReduceTestCase(
+				"|| ( A B )",
+				expected_result = [ "||", ["A", "B"] ]),
+			UseReduceTestCase(
+				"|| ( A || ( B C ) )",
+				expected_result = [ "||", ["A", "||", ["B", "C"]]]),
+			UseReduceTestCase(
+				"|| ( A || ( B C D ) )",
+				expected_result = [ "||", ["A", "||", ["B", "C", "D"]] ]),
+			UseReduceTestCase(
+				"|| ( A || ( B || ( C D ) E ) )",
+				expected_result = [ "||", ["A", "||", ["B", "||", ["C", "D"], "E"]] ]),
+			UseReduceTestCase(
+				"( || ( ( ( A ) B ) ) )",
+				expected_result = [ "||", ["A", "B"] ] ),
+			UseReduceTestCase(
+				"( || ( || ( ( A ) B ) ) )",
+				expected_result = [ "||", ["A", "B"] ]),
+			UseReduceTestCase(
+				"( || ( || ( ( A ) B ) ) )",
+				expected_result = [ "||", ["A", "B"] ]),
+			UseReduceTestCase(
+				"|| ( A )",
+				expected_result = ["A"]),
+			UseReduceTestCase(
+				"( || ( || ( || ( A ) foo? ( B ) ) ) )",
+				expected_result = ["A"]),
+			UseReduceTestCase(
+				"( || ( || ( || ( A ) foo? ( B ) ) ) )",
+				uselist = ["foo"],
+				expected_result = [ "||", ["A", "B"] ]),
+			UseReduceTestCase(
+				"( || ( || ( bar? ( A ) || ( foo? ( B ) ) ) ) )",
+				expected_result = []),
+			UseReduceTestCase(
+				"( || ( || ( bar? ( A ) || ( foo? ( B ) ) ) ) )",
+				uselist = ["foo", "bar"],
+				expected_result = [ "||", [ "A", "B" ] ]),
+			UseReduceTestCase(
+				"A || ( ) foo? ( ) B",
+				expected_result = ["A", "B"]),
+			UseReduceTestCase(
+				"|| ( A ) || ( B )",
+				expected_result = ["A", "B"]),
+			UseReduceTestCase(
+				"foo? ( A ) foo? ( B )",
+				expected_result = []),
+			UseReduceTestCase(
+				"foo? ( A ) foo? ( B )",
+				uselist = ["foo"],
+				expected_result = ["A", "B"]),
 		)
+		
+		test_cases_xfail = (
+			UseReduceTestCase("? ( A )"),
+			UseReduceTestCase("!? ( A )"),
+			UseReduceTestCase("( A"),
+			UseReduceTestCase("A )"),
+			UseReduceTestCase("||( A B )"),
+			UseReduceTestCase("|| (A B )"),
+			UseReduceTestCase("|| ( A B)"),
+			UseReduceTestCase("|| ( A B"),
+			UseReduceTestCase("|| A B )"),
+			UseReduceTestCase("|| A B"),
+			UseReduceTestCase("|| ( A B ) )"),
+			UseReduceTestCase("|| || B C"),
+			UseReduceTestCase("|| ( A B || )"),
+			UseReduceTestCase("a? A"),
+			UseReduceTestCase("( || ( || || ( A ) foo? ( B ) ) )"),
+			UseReduceTestCase("( || ( || bar? ( A ) foo? ( B ) ) )"),
+		)
+
+		for test_case in test_cases:
+			self.assertEqual(test_case.run(), test_case.expected_result)
 
-		for dep_str, valid in tests:
-			try:
-				use_reduce(paren_reduce(dep_str), matchall=True)
-			except InvalidDependString:
-				self.assertEqual(valid, False)
-			else:
-				self.assertEqual(valid, True)
+		for test_case in test_cases_xfail:
+			self.assertRaisesMsg(test_case.deparray, InvalidDependString, test_case.run)