3649916960

Build Type

push

github

Committed by GitHub

Commit Message

Bump sdl2 version to 2.26.1 (#2712)

Run Details

877 of 2015 branches covered (43.52%)

Branch coverage included in aggregate %.

2 of 2 new or added lines in 1 file covered. (100.0%)

4 existing lines in 1 file now uncovered.

4525 of 6902 relevant lines covered (65.56%)

2.59 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

88.24

/pythonforandroid/graph.py

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) == 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) == 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

1	from copy import deepcopy	4✔
2	from itertools import product	4✔
3
4	from pythonforandroid.logger import info	4✔
5	from pythonforandroid.recipe import Recipe	4✔
6	from pythonforandroid.bootstrap import Bootstrap	4✔
7	from pythonforandroid.util import BuildInterruptingException	4✔
8
9
10	def fix_deplist(deps):	4✔
11	""" Turn a dependency list into lowercase, and make sure all entries
12	that are just a string become a tuple of strings
13	"""
14	deps = [	4✔
15	((dep.lower(),)
16	if not isinstance(dep, (list, tuple))
17	else tuple([dep_entry.lower()
18	for dep_entry in dep
19	]))
20	for dep in deps
21	]
22	return deps	4✔
23
24
25	class RecipeOrder(dict):	4✔
26	def __init__(self, ctx):	4✔
27	self.ctx = ctx	4✔
28
29	def conflicts(self):	4✔
30	for name in self.keys():	4✔
31	try:	4✔
32	recipe = Recipe.get_recipe(name, self.ctx)	4✔
33	conflicts = [dep.lower() for dep in recipe.conflicts]	4✔
34	except ValueError:	×
35	conflicts = []	×
36
37	if any([c in self for c in conflicts]):	4✔
38	return True	4✔
39	return False	4✔
40
41
42	def get_dependency_tuple_list_for_recipe(recipe, blacklist=None):	4✔
43	""" Get the dependencies of a recipe with filtered out blacklist, and
44	turned into tuples with fix_deplist()
45	"""
46	if blacklist is None:	4!
47	blacklist = set()	×
48	assert type(blacklist) == set	4✔
49	if recipe.depends is None:	4!
50	dependencies = []	×
51	else:
52	# Turn all dependencies into tuples so that product will work
53	dependencies = fix_deplist(recipe.depends)	4✔
54
55	# Filter out blacklisted items and turn lowercase:
56	dependencies = [	4✔
57	tuple(set(deptuple) - blacklist)
58	for deptuple in dependencies
59	if tuple(set(deptuple) - blacklist)
60	]
61	return dependencies	4✔
62
63
64	def recursively_collect_orders(	4✔
65	name, ctx, all_inputs, orders=None, blacklist=None
66	):
67	'''For each possible recipe ordering, try to add the new recipe name
68	to that order. Recursively do the same thing with all the
69	dependencies of each recipe.
70
71	'''
72	name = name.lower()	4✔
73	if orders is None:	4!
74	orders = []	×
75	if blacklist is None:	4!
76	blacklist = set()	×
77	try:	4✔
78	recipe = Recipe.get_recipe(name, ctx)	4✔
79	dependencies = get_dependency_tuple_list_for_recipe(	4✔
80	recipe, blacklist=blacklist
81	)
82
83	# handle opt_depends: these impose requirements on the build
84	# order only if already present in the list of recipes to build
85	dependencies.extend(fix_deplist(	4✔
86	[[d] for d in recipe.get_opt_depends_in_list(all_inputs)
87	if d.lower() not in blacklist]
88	))
89
90	if recipe.conflicts is None:	4!
91	conflicts = []	×
92	else:
93	conflicts = [dep.lower() for dep in recipe.conflicts]	4✔
94	except ValueError:	×
95	# The recipe does not exist, so we assume it can be installed
96	# via pip with no extra dependencies
97	dependencies = []	×
98	conflicts = []	×
99
100	new_orders = []	4✔
101	# for each existing recipe order, see if we can add the new recipe name
102	for order in orders:	4✔
103	if name in order:	4✔
104	new_orders.append(deepcopy(order))	4✔
105	continue	4✔
106	if order.conflicts():	4✔
107	continue	4✔
108	if any([conflict in order for conflict in conflicts]):	4✔
109	continue	4✔
110
111	for dependency_set in product(*dependencies):	4✔
112	new_order = deepcopy(order)	4✔
113	new_order[name] = set(dependency_set)	4✔
114
115	dependency_new_orders = [new_order]	4✔
116	for dependency in dependency_set:	4✔
117	dependency_new_orders = recursively_collect_orders(	4✔
118	dependency, ctx, all_inputs, dependency_new_orders,
119	blacklist=blacklist
120	)
121
122	new_orders.extend(dependency_new_orders)	4✔
123
124	return new_orders	4✔
125
126
127	def find_order(graph):	4✔
128	'''
129	Do a topological sort on the dependency graph dict.
130	'''
131	while graph:	4✔
132	# Find all items without a parent
133	leftmost = [name for name, dep in graph.items() if not dep]	4✔
134	if not leftmost:	4!
135	raise ValueError('Dependency cycle detected! %s' % graph)	×
136	# If there is more than one, sort them for predictable order
137	leftmost.sort()	4✔
138	for result in leftmost:	4✔
139	# Yield and remove them from the graph
140	yield result	4✔
141	graph.pop(result)	4✔
142	for bset in graph.values():	4✔
143	bset.discard(result)	4✔
144
145
146	def obvious_conflict_checker(ctx, name_tuples, blacklist=None):	4✔
147	""" This is a pre-flight check function that will completely ignore
148	recipe order or choosing an actual value in any of the multiple
149	choice tuples/dependencies, and just do a very basic obvious
150	conflict check.
151	"""
152	deps_were_added_by = dict()	4✔
153	deps = set()	4✔
154	if blacklist is None:	4✔
155	blacklist = set()	4✔
156
157	# Add dependencies for all recipes:
158	to_be_added = [(name_tuple, None) for name_tuple in name_tuples]	4✔
159	while len(to_be_added) > 0:	4✔
160	current_to_be_added = list(to_be_added)	4✔
161	to_be_added = []	4✔
162	for (added_tuple, adding_recipe) in current_to_be_added:	4✔
163	assert type(added_tuple) == tuple	4✔
164	if len(added_tuple) > 1:	4✔
165	# No obvious commitment in what to add, don't check it itself
166	# but throw it into deps for later comparing against
167	# (Remember this function only catches obvious issues)
168	deps.add(added_tuple)	4✔
169	continue	4✔
170
171	name = added_tuple[0]	4✔
172	recipe_conflicts = set()	4✔
173	recipe_dependencies = []	4✔
174	try:	4✔
175	# Get recipe to add and who's ultimately adding it:
176	recipe = Recipe.get_recipe(name, ctx)	4✔
177	recipe_conflicts = {c.lower() for c in recipe.conflicts}	4✔
178	recipe_dependencies = get_dependency_tuple_list_for_recipe(	4✔
179	recipe, blacklist=blacklist
180	)
181	except ValueError:	4✔
182	pass	4✔
183	adder_first_recipe_name = adding_recipe or name	4✔
184
185	# Collect the conflicts:
186	triggered_conflicts = []	4✔
187	for dep_tuple_list in deps:	4✔
188	# See if the new deps conflict with things added before:
189	if set(dep_tuple_list).intersection(	4✔
190	recipe_conflicts) == set(dep_tuple_list):
191	triggered_conflicts.append(dep_tuple_list)	4✔
192	continue	4✔
193
194	# See if what was added before conflicts with the new deps:
195	if len(dep_tuple_list) > 1:	4✔
196	# Not an obvious commitment to a specific recipe/dep
197	# to be added, so we won't check.
198	# (remember this function only catches obvious issues)
199	continue	4✔
200	try:	4✔
201	dep_recipe = Recipe.get_recipe(dep_tuple_list[0], ctx)	4✔
202	except ValueError:	4✔
203	continue	4✔
204	conflicts = [c.lower() for c in dep_recipe.conflicts]	4✔
205	if name in conflicts:	4✔
206	triggered_conflicts.append(dep_tuple_list)	4✔
207
208	# Throw error on conflict:
209	if triggered_conflicts:	4✔
210	# Get first conflict and see who added that one:
211	adder_second_recipe_name = "'\|\|'".join(triggered_conflicts[0])	4✔
212	second_recipe_original_adder = deps_were_added_by.get(	4✔
213	(adder_second_recipe_name,), None
214	)
215	if second_recipe_original_adder:	4✔
216	adder_second_recipe_name = second_recipe_original_adder	4✔
217
218	# Prompt error:
219	raise BuildInterruptingException(	4✔
220	"Conflict detected: '{}'"
221	" inducing dependencies {}, and '{}'"
222	" inducing conflicting dependencies {}".format(
223	adder_first_recipe_name,
224	(recipe.name,),
225	adder_second_recipe_name,
226	triggered_conflicts[0]
227	))
228
229	# Actually add it to our list:
230	deps.add(added_tuple)	4✔
231	deps_were_added_by[added_tuple] = adding_recipe	4✔
232
233	# Schedule dependencies to be added
234	to_be_added += [	4✔
235	(dep, adder_first_recipe_name or name)
236	for dep in recipe_dependencies
237	if dep not in deps
238	]
239	# If we came here, then there were no obvious conflicts.
240	return None	4✔
241
242
243	def get_recipe_order_and_bootstrap(ctx, names, bs=None, blacklist=None):	4✔
244	# Get set of recipe/dependency names, clean up and add bootstrap deps:
245	names = set(names)	4✔
246	if bs is not None and bs.recipe_depends:	4✔
247	names = names.union(set(bs.recipe_depends))	4✔
248	names = fix_deplist([	4✔
249	([name] if not isinstance(name, (list, tuple)) else name)
250	for name in names
251	])
252	if blacklist is None:	4✔
253	blacklist = set()	4✔
254	blacklist = {bitem.lower() for bitem in blacklist}	4✔
255
256	# Remove all values that are in the blacklist:
257	names_before_blacklist = list(names)	4✔
258	names = []	4✔
259	for name in names_before_blacklist:	4✔
260	cleaned_up_tuple = tuple([	4✔
261	item for item in name if item not in blacklist
262	])
263	if cleaned_up_tuple:	4!
264	names.append(cleaned_up_tuple)	4✔
265
266	# Do check for obvious conflicts (that would trigger in any order, and
267	# without comitting to any specific choice in a multi-choice tuple of
268	# dependencies):
269	obvious_conflict_checker(ctx, names, blacklist=blacklist)	4✔
270	# If we get here, no obvious conflicts!
271
272	# get all possible order graphs, as names may include tuples/lists
273	# of alternative dependencies
274	possible_orders = []	4✔
275	for name_set in product(*names):	4✔
276	new_possible_orders = [RecipeOrder(ctx)]	4✔
277	for name in name_set:	4✔
278	new_possible_orders = recursively_collect_orders(	4✔
279	name, ctx, name_set, orders=new_possible_orders,
280	blacklist=blacklist
281	)
282	possible_orders.extend(new_possible_orders)	4✔
283
284	# turn each order graph into a linear list if possible
285	orders = []	4✔
286	for possible_order in possible_orders:	4✔
287	try:	4✔
288	order = find_order(possible_order)	4✔
289	except ValueError: # a circular dependency was found	×
290	info('Circular dependency found in graph {}, skipping it.'.format(	×
291	possible_order))
292	continue	×
293	orders.append(list(order))	4✔
294
295	# prefer python3 and SDL2 if available
296	orders = sorted(orders,	4✔
297	key=lambda order: -('python3' in order) - ('sdl2' in order))
298
299	if not orders:	4!
300	raise BuildInterruptingException(	×
301	'Didn\'t find any valid dependency graphs. '
302	'This means that some of your '
303	'requirements pull in conflicting dependencies.')
304
305	# It would be better to check against possible orders other
306	# than the first one, but in practice clashes will be rare,
307	# and can be resolved by specifying more parameters
308	chosen_order = orders[0]	4✔
309	if len(orders) > 1:	4!
UNCOV 310	info('Found multiple valid dependency orders:')	×
UNCOV 311	for order in orders:	×
UNCOV 312	info(' {}'.format(order))	×
UNCOV 313	info('Using the first of these: {}'.format(chosen_order))	×
314	else:
315	info('Found a single valid recipe set: {}'.format(chosen_order))	4✔
316
317	if bs is None:	4✔
318	bs = Bootstrap.get_bootstrap_from_recipes(chosen_order, ctx)	4✔
319	if bs is None:	4!
320	# Note: don't remove this without thought, causes infinite loop
321	raise BuildInterruptingException(	×
322	"Could not find any compatible bootstrap!"
323	)
324	recipes, python_modules, bs = get_recipe_order_and_bootstrap(	4✔
325	ctx, chosen_order, bs=bs, blacklist=blacklist
326	)
327	else:
328	# check if each requirement has a recipe
329	recipes = []	4✔
330	python_modules = []	4✔
331	for name in chosen_order:	4✔
332	try:	4✔
333	recipe = Recipe.get_recipe(name, ctx)	4✔
334	python_modules += recipe.python_depends	4✔
335	except ValueError:	×
336	python_modules.append(name)	×
337	else:
338	recipes.append(name)	4✔
339
340	python_modules = list(set(python_modules))	4✔
341	return recipes, python_modules, bs	4✔

kivy / python-for-android / 3649916960

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous