lib/portage/dep/_dnf.py

# Copyright 2017 Gentoo Foundation
# Distributed under the terms of the GNU General Public License v2

from __future__ import unicode_literals

import itertools


def dnf_convert(dep_struct):
	"""
	Convert dep_struct to disjunctive normal form (DNF), where dep_struct
	is either a conjunction or disjunction of the form produced by
	use_reduce(opconvert=True).
	"""
	# Normalize input to have a top-level conjunction.
	if isinstance(dep_struct, list):
		if dep_struct and dep_struct[0] == '||':
			dep_struct = [dep_struct]
	else:
		dep_struct = [dep_struct]

	conjunction = []
	disjunctions = []

	for x in dep_struct:
		if isinstance (x, list):
			assert x and x[0] == '||', \
				'Normalization error, nested conjunction found in %s' % (dep_struct,)
			if any(isinstance(element, list) for element in x):
				x_dnf = ['||']
				for element in x[1:]:
					if isinstance(element, list):
						# Due to normalization, a disjunction must not be
						# nested directly in another disjunction, so this
						# must be a conjunction.
						assert element, 'Normalization error, empty conjunction found in %s' % (x,)
						assert element[0] != '||', \
							'Normalization error, nested disjunction found in %s' % (x,)
						element = dnf_convert(element)
						if contains_disjunction(element):
							assert (len(element) == 1 and
								element[0] and element[0][0] == '||'), \
								'Normalization error, expected single disjunction in %s' % (element,)
							x_dnf.extend(element[0][1:])
						else:
							x_dnf.append(element)
					else:
						x_dnf.append(element)
				x = x_dnf
			disjunctions.append(x)
		else:
			conjunction.append(x)

	if disjunctions and (conjunction or len(disjunctions) > 1):
		dnf_form = ['||']
		for x in itertools.product(*[x[1:] for x in disjunctions]):
			normalized = conjunction[:]
			for element in x:
				if isinstance(element, list):
					normalized.extend(element)
				else:
					normalized.append(element)
			dnf_form.append(normalized)
		result = [dnf_form]
	else:
		result = conjunction + disjunctions

	return result


def contains_disjunction(dep_struct):
	"""
	Search for a disjunction contained in dep_struct, where dep_struct
	is either a conjunction or disjunction of the form produced by
	use_reduce(opconvert=True). If dep_struct is a disjunction, then
	this only returns True if there is a nested disjunction. Due to
	normalization, recursion is only needed when dep_struct is a
	disjunction containing a conjunction. If dep_struct is a conjunction,
	then it is assumed that normalization has elevated any nested
	disjunctions to the top-level.
	"""
	is_disjunction = dep_struct and dep_struct[0] == '||'
	for x in dep_struct:
		if isinstance(x, list):
			assert x, 'Normalization error, empty conjunction found in %s' % (dep_struct,)
			if x[0] == '||':
				return True
			elif is_disjunction and contains_disjunction(x):
				return True
	return False