GeezerVison is showing github.com — python-for-android/pythonforandroid/graph.py at develop · kivy/python-for-android

Expand file tree

graph.py

Copy path

More file actions

Latest commit

History

341 lines (298 loc) · 12.1 KB

graph.py

Copy path

File metadata and controls

341 lines (298 loc) · 12.1 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

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 committing 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