from copy import deepcopy

from itertools import product

from pythonforandroid.logger import info

from pythonforandroid.recipe import Recipe

from pythonforandroid.bootstrap import Bootstrap

from pythonforandroid.util import BuildInterruptingException

def fix_deplist(deps):

""" Turn a dependency list into lowercase, and make sure all entries

that are just a string become a tuple of strings

"""

deps = [

((dep.lower(),)

if not isinstance(dep, (list, tuple))

else tuple([dep_entry.lower()

for dep_entry in dep

]))

for dep in deps

]

return deps

class RecipeOrder(dict):

def __init__(self, ctx):

self.ctx = ctx

def conflicts(self):

for name in self.keys():

try:

recipe = Recipe.get_recipe(name, self.ctx)

conflicts = [dep.lower() for dep in recipe.conflicts]

except ValueError:

conflicts = []

if any([c in self for c in conflicts]):

return True

return False

def get_dependency_tuple_list_for_recipe(recipe, blacklist=None):

""" Get the dependencies of a recipe with filtered out blacklist, and

turned into tuples with fix_deplist()

"""

if blacklist is None:

blacklist = set()

assert type(blacklist) is set

if recipe.depends is None:

dependencies = []

else:

# Turn all dependencies into tuples so that product will work

dependencies = fix_deplist(recipe.depends)

# Filter out blacklisted items and turn lowercase:

dependencies = [

tuple(set(deptuple) - blacklist)

for deptuple in dependencies

if tuple(set(deptuple) - blacklist)

]

return dependencies

def recursively_collect_orders(

name, ctx, all_inputs, orders=None, blacklist=None

):

'''For each possible recipe ordering, try to add the new recipe name

to that order. Recursively do the same thing with all the

dependencies of each recipe.

'''

name = name.lower()

if orders is None:

orders = []

if blacklist is None:

blacklist = set()

try:

recipe = Recipe.get_recipe(name, ctx)

dependencies = get_dependency_tuple_list_for_recipe(

recipe, blacklist=blacklist

)

# handle opt_depends: these impose requirements on the build

# order only if already present in the list of recipes to build

dependencies.extend(fix_deplist(

[[d] for d in recipe.get_opt_depends_in_list(all_inputs)

if d.lower() not in blacklist]

))

if recipe.conflicts is None:

conflicts = []

else:

conflicts = [dep.lower() for dep in recipe.conflicts]

except ValueError:

# The recipe does not exist, so we assume it can be installed

# via pip with no extra dependencies

dependencies = []

conflicts = []

new_orders = []

# for each existing recipe order, see if we can add the new recipe name

for order in orders:

if name in order:

new_orders.append(deepcopy(order))

continue

if order.conflicts():

continue

if any([conflict in order for conflict in conflicts]):

continue

for dependency_set in product(*dependencies):

new_order = deepcopy(order)

new_order[name] = set(dependency_set)

dependency_new_orders = [new_order]

for dependency in dependency_set:

dependency_new_orders = recursively_collect_orders(

dependency, ctx, all_inputs, dependency_new_orders,

blacklist=blacklist

)

new_orders.extend(dependency_new_orders)

return new_orders

def find_order(graph):

'''

Do a topological sort on the dependency graph dict.

'''

while graph:

# Find all items without a parent

leftmost = [name for name, dep in graph.items() if not dep]

if not leftmost:

raise ValueError('Dependency cycle detected! %s' % graph)

# If there is more than one, sort them for predictable order

leftmost.sort()

for result in leftmost:

# Yield and remove them from the graph

yield result

graph.pop(result)

for bset in graph.values():

bset.discard(result)

def obvious_conflict_checker(ctx, name_tuples, blacklist=None):

""" This is a pre-flight check function that will completely ignore

recipe order or choosing an actual value in any of the multiple

choice tuples/dependencies, and just do a very basic obvious

conflict check.

"""

deps_were_added_by = dict()

deps = set()

if blacklist is None:

blacklist = set()

# Add dependencies for all recipes:

to_be_added = [(name_tuple, None) for name_tuple in name_tuples]

while len(to_be_added) > 0:

current_to_be_added = list(to_be_added)

to_be_added = []

for (added_tuple, adding_recipe) in current_to_be_added:

assert type(added_tuple) is tuple

if len(added_tuple) > 1:

# No obvious commitment in what to add, don't check it itself

# but throw it into deps for later comparing against

# (Remember this function only catches obvious issues)

deps.add(added_tuple)

continue

name = added_tuple[0]

recipe_conflicts = set()

recipe_dependencies = []

try:

# Get recipe to add and who's ultimately adding it:

recipe = Recipe.get_recipe(name, ctx)

recipe_conflicts = {c.lower() for c in recipe.conflicts}

recipe_dependencies = get_dependency_tuple_list_for_recipe(

recipe, blacklist=blacklist

)

except ValueError:

pass

adder_first_recipe_name = adding_recipe or name

# Collect the conflicts:

triggered_conflicts = []

for dep_tuple_list in deps:

# See if the new deps conflict with things added before:

if set(dep_tuple_list).intersection(

recipe_conflicts) == set(dep_tuple_list):

triggered_conflicts.append(dep_tuple_list)

continue

# See if what was added before conflicts with the new deps:

if len(dep_tuple_list) > 1:

# Not an obvious commitment to a specific recipe/dep

# to be added, so we won't check.

# (remember this function only catches obvious issues)

continue

try:

dep_recipe = Recipe.get_recipe(dep_tuple_list[0], ctx)

except ValueError:

continue

conflicts = [c.lower() for c in dep_recipe.conflicts]

if name in conflicts:

triggered_conflicts.append(dep_tuple_list)

# Throw error on conflict:

if triggered_conflicts:

# Get first conflict and see who added that one:

adder_second_recipe_name = "'||'".join(triggered_conflicts[0])

second_recipe_original_adder = deps_were_added_by.get(

(adder_second_recipe_name,), None

)

if second_recipe_original_adder:

adder_second_recipe_name = second_recipe_original_adder

# Prompt error:

raise BuildInterruptingException(

"Conflict detected: '{}'"

" inducing dependencies {}, and '{}'"

" inducing conflicting dependencies {}".format(

adder_first_recipe_name,

(recipe.name,),

adder_second_recipe_name,

triggered_conflicts[0]

))

# Actually add it to our list:

deps.add(added_tuple)

deps_were_added_by[added_tuple] = adding_recipe

# Schedule dependencies to be added

to_be_added += [

(dep, adder_first_recipe_name or name)

for dep in recipe_dependencies

if dep not in deps

]

# If we came here, then there were no obvious conflicts.

return None

def get_recipe_order_and_bootstrap(ctx, names, bs=None, blacklist=None):

# Get set of recipe/dependency names, clean up and add bootstrap deps:

names = set(names)

if bs is not None and bs.recipe_depends:

names = names.union(set(bs.recipe_depends))

names = fix_deplist([

([name] if not isinstance(name, (list, tuple)) else name)

for name in names

])

if blacklist is None:

blacklist = set()

blacklist = {bitem.lower() for bitem in blacklist}

# Remove all values that are in the blacklist:

names_before_blacklist = list(names)

names = []

for name in names_before_blacklist:

cleaned_up_tuple = tuple([

item for item in name if item not in blacklist

])

if cleaned_up_tuple:

names.append(cleaned_up_tuple)

# Do check for obvious conflicts (that would trigger in any order, and

# without comitting to any specific choice in a multi-choice tuple of

# dependencies):

obvious_conflict_checker(ctx, names, blacklist=blacklist)

# If we get here, no obvious conflicts!

# get all possible order graphs, as names may include tuples/lists

# of alternative dependencies

possible_orders = []

for name_set in product(*names):

new_possible_orders = [RecipeOrder(ctx)]

for name in name_set:

new_possible_orders = recursively_collect_orders(

name, ctx, name_set, orders=new_possible_orders,

blacklist=blacklist

)

possible_orders.extend(new_possible_orders)

# turn each order graph into a linear list if possible

orders = []

for possible_order in possible_orders:

try:

order = find_order(possible_order)

except ValueError: # a circular dependency was found

info('Circular dependency found in graph {}, skipping it.'.format(

possible_order))

continue

orders.append(list(order))

# prefer python3 and SDL2 if available

orders = sorted(orders,

key=lambda order: -('python3' in order) - ('sdl2' in order))

if not orders:

raise BuildInterruptingException(

'Didn\'t find any valid dependency graphs. '

'This means that some of your '

'requirements pull in conflicting dependencies.')

# It would be better to check against possible orders other

# than the first one, but in practice clashes will be rare,

# and can be resolved by specifying more parameters

chosen_order = orders[0]

if len(orders) > 1:

info('Found multiple valid dependency orders:')

for order in orders:

info(' {}'.format(order))

info('Using the first of these: {}'.format(chosen_order))

else:

info('Found a single valid recipe set: {}'.format(chosen_order))

if bs is None:

bs = Bootstrap.get_bootstrap_from_recipes(chosen_order, ctx)

if bs is None:

# Note: don't remove this without thought, causes infinite loop

raise BuildInterruptingException(

"Could not find any compatible bootstrap!"

)

recipes, python_modules, bs = get_recipe_order_and_bootstrap(

ctx, chosen_order, bs=bs, blacklist=blacklist

)

else:

# check if each requirement has a recipe

recipes = []

python_modules = []

for name in chosen_order:

try:

recipe = Recipe.get_recipe(name, ctx)

python_modules += recipe.python_depends

except ValueError:

python_modules.append(name)

else:

recipes.append(name)

python_modules = list(set(python_modules))

return recipes, python_modules, bs