from copy import deepcopy
from pythonforandroid.logger import (info, info_notify, warning)
from pythonforandroid.recipe import Recipe
from pythonforandroid.bootstrap import Bootstrap
class Graph(object):
# Taken from the old python-for-android/depsort
# Modified to include alternative dependencies
def __init__(self):
# `graph`: dict that maps each package to a set of its dependencies.
self.graphs = [{}]
# self.graph = {}
def remove_redundant_graphs(self):
'''Removes possible graphs if they are equivalent to others.'''
graphs = self.graphs
# Walk the list backwards so that popping elements doesn't
# mess up indexing.
# n.b. no need to test graph 0 as it will have been tested against
# all others by the time we get to it
for i in range(len(graphs) - 1, 0, -1):
graph = graphs[i]
# test graph i against all graphs 0 to i-1
for j in range(0, i):
comparison_graph = graphs[j]
if set(comparison_graph.keys()) == set(graph.keys()):
# graph[i] == graph[j]
# so remove graph[i] and continue on to testing graph[i-1]
graphs.pop(i)
break
def add(self, dependent, dependency):
"""Add a dependency relationship to the graph"""
if isinstance(dependency, (tuple, list)):
for graph in self.graphs[:]:
for dep in dependency[1:]:
new_graph = deepcopy(graph)
self._add(new_graph, dependent, dep)
self.graphs.append(new_graph)
self._add(graph, dependent, dependency[0])
else:
for graph in self.graphs:
self._add(graph, dependent, dependency)
self.remove_redundant_graphs()
def _add(self, graph, dependent, dependency):
'''Add a dependency relationship to a specific graph, where dependency
must be a single dependency, not a list or tuple.
'''
graph.setdefault(dependent, set())
graph.setdefault(dependency, set())
if dependent != dependency:
graph[dependent].add(dependency)
def conflicts(self, conflict):
graphs = self.graphs
initial_num = len(graphs)
for i in range(len(graphs)):
graph = graphs[initial_num - 1 - i]
if conflict in graph:
graphs.pop(initial_num - 1 - i)
return len(graphs) == 0
def remove_remaining_conflicts(self, ctx):
# It's unpleasant to have to pass ctx as an argument...
'''Checks all possible graphs for conflicts that have arisen during
the additon of alternative repice branches, as these are not checked
for conflicts at the time.'''
new_graphs = []
for i, graph in enumerate(self.graphs):
for name in graph.keys():
recipe = Recipe.get_recipe(name, ctx)
if any([c in graph for c in recipe.conflicts]):
break
else:
new_graphs.append(graph)
self.graphs = new_graphs
def add_optional(self, dependent, dependency):
"""Add an optional (ordering only) dependency relationship to the graph
Only call this after all mandatory requirements are added
"""
for graph in self.graphs:
if dependent in graph and dependency in graph:
self._add(graph, dependent, dependency)
def find_order(self, index=0):
"""Do a topological sort on a dependency graph
:Parameters:
:Returns:
iterator, sorted items form first to last
"""
graph = self.graphs[index]
graph = dict((k, set(v)) for k, v in graph.items())
while graph:
# Find all items without a parent
leftmost = [l for l, s in graph.items() if not s]
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 get_recipe_order_and_bootstrap(ctx, names, bs=None):
'''Takes a list of recipe names and (optionally) a bootstrap. Then
works out the dependency graph (including bootstrap recipes if
necessary). Finally, if no bootstrap was initially selected,
chooses one that supports all the recipes.
'''
graph = Graph()
recipes_to_load = set(names)
if bs is not None and bs.recipe_depends:
info_notify('Bootstrap requires recipes {}'.format(bs.recipe_depends))
recipes_to_load = recipes_to_load.union(set(bs.recipe_depends))
recipes_to_load = list(recipes_to_load)
recipe_loaded = []
python_modules = []
while recipes_to_load:
name = recipes_to_load.pop(0)
if name in recipe_loaded or isinstance(name, (list, tuple)):
continue
try:
recipe = Recipe.get_recipe(name, ctx)
except IOError:
info('No recipe named {}; will attempt to install with pip'
.format(name))
python_modules.append(name)
continue
except (KeyboardInterrupt, SystemExit):
raise
except:
warning('Failed to import recipe named {}; the recipe exists '
'but appears broken.'.format(name))
warning('Exception was:')
raise
graph.add(name, name)
info('Loaded recipe {} (depends on {}{})'.format(
name, recipe.depends,
', conflicts {}'.format(recipe.conflicts) if recipe.conflicts
else ''))
for depend in recipe.depends:
graph.add(name, depend)
recipes_to_load += recipe.depends
for conflict in recipe.conflicts:
if graph.conflicts(conflict):
warning(
('{} conflicts with {}, but both have been '
'included or pulled into the requirements.'
.format(recipe.name, conflict)))
warning(
'Due to this conflict the build cannot continue, exiting.')
exit(1)
python_modules += recipe.python_depends
recipe_loaded.append(name)
graph.remove_remaining_conflicts(ctx)
if len(graph.graphs) > 1:
info('Found multiple valid recipe sets:')
for g in graph.graphs:
info(' {}'.format(g.keys()))
info_notify('Using the first of these: {}'
.format(graph.graphs[0].keys()))
elif len(graph.graphs) == 0:
warning('Didn\'t find any valid dependency graphs, exiting.')
exit(1)
else:
info('Found a single valid recipe set (this is good)')
build_order = list(graph.find_order(0))
if bs is None: # It would be better to check against possible
# orders other than the first one, but in practice
# there will rarely be clashes, and the user can
# specify more parameters if necessary to resolve
# them.
bs = Bootstrap.get_bootstrap_from_recipes(build_order, ctx)
if bs is None:
info('Could not find a bootstrap compatible with the '
'required recipes.')
info('If you think such a combination should exist, try '
'specifying the bootstrap manually with --bootstrap.')
exit(1)
info('{} bootstrap appears compatible with the required recipes.'
.format(bs.name))
info('Checking this...')
recipes_to_load = bs.recipe_depends
# This code repeats the code from earlier! Should move to a function:
while recipes_to_load:
name = recipes_to_load.pop(0)
if name in recipe_loaded or isinstance(name, (list, tuple)):
continue
try:
recipe = Recipe.get_recipe(name, ctx)
except ImportError:
info('No recipe named {}; will attempt to install with pip'
.format(name))
python_modules.append(name)
continue
graph.add(name, name)
info('Loaded recipe {} (depends on {}{})'.format(
name, recipe.depends,
', conflicts {}'.format(recipe.conflicts) if recipe.conflicts
else ''))
for depend in recipe.depends:
graph.add(name, depend)
recipes_to_load += recipe.depends
for conflict in recipe.conflicts:
if graph.conflicts(conflict):
warning(
('{} conflicts with {}, but both have been '
'included or pulled into the requirements.'
.format(recipe.name, conflict)))
warning('Due to this conflict the build cannot continue, '
'exiting.')
exit(1)
recipe_loaded.append(name)
graph.remove_remaining_conflicts(ctx)
build_order = list(graph.find_order(0))
build_order, python_modules, bs = get_recipe_order_and_bootstrap(
ctx, build_order + python_modules, bs)
return build_order, python_modules, bs
# Do a final check that the new bs doesn't pull in any conflicts