#!/usr/bin/env python
# Copyright 1999-2007 Gentoo Foundation
# Distributed under the terms of the GNU General Public License v2
#
# Zac Medico <zmedico@gentoo.org>
#

import sys, os

try:
	from portage.versions import pkgcmp, pkgsplit
	from portage.dep import dep_getkey, dep_opconvert, paren_reduce, use_reduce
except ImportError:
	# backward compat for <=portage-2.1.2
	from portage_versions import pkgcmp, pkgsplit
	from portage_dep import dep_getkey, dep_opconvert, paren_reduce, use_reduce

if not hasattr(__builtins__, "set"):
	from sets import Set as set # python-2.3 compat

combination_test_data = [
	("|| ( a b c d || ( e f ) )", 6),
	("|| ( a b c d || ( e f g || ( h i ) ) )", 9),
	("|| ( a b c )", 3),
	("|| ( ( a b ) ( c d || ( e f ) ) )", 3),
	("a b c d || ( e f ) || ( i j k ) || ( l m n o )", 24)
]

def test_combinations():
	failures = 0
	for depstring, expected_count in combination_test_data:
		deps = paren_reduce(depstring)
		deps = use_reduce(deps, uselist=[])
		deps = dep_opconvert(deps)
		combinations = expand_combinations(deps)
		if len(combinations) != expected_count:
			failures += 1
			print "depstring: %s" % depstring
			print "combinations: %s" % str(combinations)
			print "expected %s combinations, got %s" % \
				(expected_count, len(results))
	if failures != 0:
		return 1
	print "success"
	return os.EX_OK

def expand_combinations(deps):
	if not deps:
		return []
	if deps[0] == "||":
		ret = []
		for element in deps[1:]:
			if isinstance(element, list):
				if element:
					variables = expand_combinations(element)
					if variables:
						if len(variables) > 1:
							ret.extend(variables)
						else:
							ret.append(variables[0])
			else:
				ret.append([element])
		if len(deps) == 1:
			return []
		return ret

	constant_deps = []
	variable_deps = []
	for element in deps:
		if isinstance(element, list):
			if element:
				variables = expand_combinations(element)
				if variables:
					if len(variables) > 1:
						variable_deps.append(variables)
					else:
						constant_deps.append(variables[0])
		else:
			constant_deps.append(element)
	if not variable_deps:
		return [constant_deps]

	# Cover all possible combinations of indexes for variable deps, analogous
	# to a set of combinations such as { 000, 001, 010, 011, 100, 101, ... }
	# where the number of possibilities may differ from one variable dep to
	# the next.
	ret = []
	choice_indexes = []
	var_total = len(variable_deps)
	for x in xrange(var_total):
		choice_indexes.append(0)
	var_index = 0
	while True:
		if choice_indexes[var_index] >= len(variable_deps[var_index]):
			# Bring it back into bounds.
			choice_indexes[var_index] -= 1
			var_index += 1
			if var_index >= var_total:
				break
			for i in xrange(var_index):
				choice_indexes[i] = 0
			choice_indexes[var_index] += 1
			# Check to see if incrementing it has put it out of bounds.
			continue 
		else:
			# Choice_indexes are in bounds.  Always try to increment the least
			# significant index (0) first, and let the boundary checks correct
			# when necessary.
			var_index = 0
		comb = constant_deps[:]
		for i in xrange(var_total):
			comb.extend(variable_deps[i][choice_indexes[i]])
		ret.append(comb)
		choice_indexes[var_index] += 1
	return ret

def cmp_pkgs(cpv1, cpv2):
	return pkgcmp(pkgsplit(cpv2), pkgsplit(cpv1))

def expand_new_virtuals(mydb, deps):
	ret = []
	for x in deps:
		if isinstance(x, list):
			ret.append(expand_new_virtuals(mydb, x))
			continue
		elif x == "||" or x.startswith("!"):
			ret.append(x)
			continue
		cp = dep_getkey(x)
		if not cp.startswith("virtual/"):
			ret.append(x)
			continue
		pkgs = []
		for cpv in mydb.match(x):
			# only use new-style matches
			if cpv.startswith("virtual/"):
				pkgs.append(cpv)
		if not pkgs:
			ret.append(x)
			continue
		pkgs.sort(cmp_pkgs)
		choices = ["||"]
		for cpv in pkgs:
			depstring = " ".join(mydb.aux_get(cpv,
				["DEPEND", "RDEPEND", "PDEPEND"]))
			uselist = mydb.aux_get(cpv, ["USE"])[0].split()
			depstring = paren_reduce(depstring)
			depstring = use_reduce(depstring, uselist=uselist)
			depstring = dep_opconvert(depstring)
			virtual_deps = expand_new_virtuals(mydb, depstring)
			if virtual_deps and virtual_deps[0] != "||":
				choices.append(["="+cpv] + virtual_deps)
			else:
				choices.append(["="+cpv, virtual_deps])
		ret.append(choices)
	return ret

def get_available_pkg_combinations(mydb, deps):
	deps = expand_new_virtuals(mydb, deps)
	atom_combs = expand_combinations(deps)
	pkg_combs = ["||"]
	for atom_comb in atom_combs:
		unsatisfied = False
		pkg_comb = []
		for atom in atom_comb:
			if atom.startswith("!"):
				continue
			avail_pkgs = mydb.match(atom)
			if not avail_pkgs:
				unsatisfied = True
				break
			if len(avail_pkgs) == 1:
				pkg_comb.append("="+avail_pkgs[0])
			else:
				avail_pkgs.sort(cmp_pkgs)
				pkg_comb.append(["||"] + ["="+cpv for cpv in avail_pkgs])
		if unsatisfied:
			continue
		pkg_combs.append(pkg_comb)
	pkg_combs = expand_combinations(pkg_combs)
	return pkg_combs

def get_installed_combinations(depstring):
	import portage
	myroot = portage.settings["ROOT"]
	uselist = portage.settings["USE"].split()
	vardb = portage.db[myroot]["vartree"].dbapi
	deps = paren_reduce(depstring)
	deps = use_reduce(deps, uselist=uselist)
	deps = dep_opconvert(deps)
	return get_available_pkg_combinations(vardb, deps)

def show_installed_combinations(depstring, filter_virtuals):
	combinations = get_installed_combinations(depstring)
	shown_combinations = set()
	for x in combinations:
		atoms = list(set(x))
		atoms.sort()
		if filter_virtuals:
			atoms = [atom for atom in atoms \
				if not atom.startswith("=virtual/")]
		atoms = tuple(atoms)
		if atoms in shown_combinations:
			continue
		shown_combinations.add(atoms)
		print " ".join([atom.lstrip("=") for atom in atoms])

if __name__ == "__main__":
	description = "Show all possible combinations of installed " + \
		"packages that satisfy a given dependency string."
	usage = "usage: %s [options] <depstring>" % os.path.basename(sys.argv[0])
	from optparse import OptionParser
	parser = OptionParser(description=description, usage=usage)
	parser.add_option("--show-virtuals", action="store_false",
		dest="filter_virtuals", default=True,
		help="show new-style virtuals")
	parser.add_option("--test", action="store_true",
		dest="test", default=False,
		help="test the combinations logic")
	options, args = parser.parse_args()
	if options.test:
		retval = test_combinations()
	elif len(args) != 1:
		parser.print_usage()
		retval = 1
	else:
		retval = show_installed_combinations(args[0], options.filter_virtuals)
	sys.exit(retval)