solver.c 32.4 KB
Newer Older
1
/* solver.c - Alpine Package Keeper (APK)
2
 * Up- and down-propagating, forwarding checking, deductive dependency solver.
3
 *
4
 * Copyright (C) 2008-2013 Timo Teräs <timo.teras@iki.fi>
5
6
 * All rights reserved.
 *
7
 * SPDX-License-Identifier: GPL-2.0-only
8
9
 */

10
#include <stdint.h>
11
#include <unistd.h>
12
#include <strings.h>
13
14
15
16
17
#include "apk_defines.h"
#include "apk_database.h"
#include "apk_package.h"
#include "apk_solver.h"

Timo Teräs's avatar
Timo Teräs committed
18
19
#include "apk_print.h"

20
21
22
//#define DEBUG_PRINT

#ifdef DEBUG_PRINT
23
24
25
26
27
28
#include <stdio.h>
#define dbg_printf(args...) fprintf(stderr, args)
#else
#define dbg_printf(args...)
#endif

29
#define ASSERT(cond, fmt...)	if (!(cond)) { apk_error(fmt); *(char*)NULL = 0; }
30

31
32
struct apk_solver_state {
	struct apk_database *db;
33
34
35
36
	struct apk_changeset *changeset;
	struct list_head dirty_head;
	struct list_head unresolved_head;
	unsigned int errors;
37
	unsigned int solver_flags_inherit;
38
39
	unsigned int pinning_inherit;
	unsigned int default_repos;
40
	unsigned ignore_conflict : 1;
41
};
42

43
44
static struct apk_provider provider_none = {
	.pkg = NULL,
45
	.version = &apk_atom_null
46
47
};

48
49
50
void apk_solver_set_name_flags(struct apk_name *name,
			       unsigned short solver_flags,
			       unsigned short solver_flags_inheritable)
51
{
52
	struct apk_provider *p;
53

54
55
	foreach_array_item(p, name->providers) {
		struct apk_package *pkg = p->pkg;
56
57
		dbg_printf("marking '" PKG_VER_FMT "' = 0x%04x / 0x%04x\n",
			PKG_VER_PRINTF(pkg), solver_flags, solver_flags_inheritable);
58
59
60
		pkg->ss.solver_flags |= solver_flags;
		pkg->ss.solver_flags_inheritable |= solver_flags_inheritable;
	}
61
62
}

63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
static int get_tag(struct apk_database *db, unsigned int pinning_mask, unsigned int repos)
{
	int i;

	for (i = 0; i < db->num_repo_tags; i++) {
		if (!(BIT(i) & pinning_mask))
			continue;
		if (db->repo_tags[i].allowed_repos & repos)
			return i;
	}
	return APK_DEFAULT_REPOSITORY_TAG;
}

static unsigned int get_pkg_repos(struct apk_database *db, struct apk_package *pkg)
{
	return pkg->repos | (pkg->ipkg ? db->repo_tags[pkg->ipkg->repository_tag].allowed_repos : 0);
}

81
static void mark_error(struct apk_solver_state *ss, struct apk_package *pkg, const char *reason)
82
83
84
{
	if (pkg == NULL || pkg->ss.error)
		return;
85
	dbg_printf("ERROR PKG: %s: %s\n", pkg->name->name, reason);
86
87
88
89
	pkg->ss.error = 1;
	ss->errors++;
}

90
static void queue_dirty(struct apk_solver_state *ss, struct apk_name *name)
91
{
92
93
94
	if (list_hashed(&name->ss.dirty_list) || name->ss.locked ||
	    (name->ss.requirers == 0 && !name->ss.reevaluate_iif))
		return;
95

96
97
	dbg_printf("queue_dirty: %s\n", name->name);
	list_add_tail(&name->ss.dirty_list, &ss->dirty_head);
98
99
}

100
static void queue_unresolved(struct apk_solver_state *ss, struct apk_name *name)
101
{
102
	int want;
103

104
105
	if (name->ss.locked)
		return;
106

107
	want = (name->ss.requirers > 0) || (name->ss.has_iif);
108
	dbg_printf("queue_unresolved: %s, want=%d (requirers=%d, has_iif=%d)\n", name->name, want, name->ss.requirers, name->ss.has_iif);
109
110
111
112
	if (want && !list_hashed(&name->ss.unresolved_list))
		list_add(&name->ss.unresolved_list, &ss->unresolved_head);
	else if (!want && list_hashed(&name->ss.unresolved_list))
		list_del_init(&name->ss.unresolved_list);
113
114
}

115
static void reevaluate_reverse_deps(struct apk_solver_state *ss, struct apk_name *name)
116
{
117
118
119
120
121
122
123
124
125
	struct apk_name **pname0, *name0;

	foreach_array_item(pname0, name->rdepends) {
		name0 = *pname0;
		if (!name0->ss.seen)
			continue;
		name0->ss.reevaluate_deps = 1;
		queue_dirty(ss, name0);
	}
126
}
127

128
static void reevaluate_reverse_installif(struct apk_solver_state *ss, struct apk_name *name)
129
{
130
131
132
133
134
135
	struct apk_name **pname0, *name0;

	foreach_array_item(pname0, name->rinstall_if) {
		name0 = *pname0;
		if (!name0->ss.seen)
			continue;
136
137
		if (name0->ss.no_iif)
			continue;
138
139
140
		name0->ss.reevaluate_iif = 1;
		queue_dirty(ss, name0);
	}
141
142
}

143
static void disqualify_package(struct apk_solver_state *ss, struct apk_package *pkg, const char *reason)
144
{
145
	struct apk_dependency *p;
146

147
	dbg_printf("disqualify_package: " PKG_VER_FMT " (%s)\n", PKG_VER_PRINTF(pkg), reason);
148
	pkg->ss.pkg_selectable = 0;
149
150
151
152
	reevaluate_reverse_deps(ss, pkg->name);
	foreach_array_item(p, pkg->provides)
		reevaluate_reverse_deps(ss, p->name);
	reevaluate_reverse_installif(ss, pkg->name);
153
154
}

155
static int dependency_satisfiable(struct apk_solver_state *ss, struct apk_dependency *dep)
156
{
157
	struct apk_name *name = dep->name;
158
	struct apk_provider *p;
159

160
161
162
	if (dep->conflict && ss->ignore_conflict)
		return TRUE;

163
164
	if (name->ss.locked)
		return apk_dep_is_provided(dep, &name->ss.chosen);
165

166
167
	if (name->ss.requirers == 0 && apk_dep_is_provided(dep, &provider_none))
		return TRUE;
168

169
	foreach_array_item(p, name->providers)
170
		if (p->pkg->ss.pkg_selectable && apk_dep_is_provided(dep, p))
171
			return TRUE;
172

173
	return FALSE;
174
175
}

176
static void discover_name(struct apk_solver_state *ss, struct apk_name *name)
177
{
178
	struct apk_database *db = ss->db;
179
180
181
	struct apk_name **pname0;
	struct apk_provider *p;
	struct apk_dependency *dep;
182
	unsigned int repos;
183

184
185
	if (name->ss.seen)
		return;
186

187
	name->ss.seen = 1;
188
	name->ss.no_iif = 1;
189
190
	foreach_array_item(p, name->providers) {
		struct apk_package *pkg = p->pkg;
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
		if (!pkg->ss.seen) {
			pkg->ss.seen = 1;
			pkg->ss.pinning_allowed = APK_DEFAULT_PINNING_MASK;
			pkg->ss.pinning_preferred = APK_DEFAULT_PINNING_MASK;
			pkg->ss.pkg_available =
				(pkg->filename != NULL) ||
				(pkg->repos & db->available_repos & ~BIT(APK_REPOSITORY_CACHED));
			/* Package is in 'cached' repository if filename is provided,
			 * or it's a 'virtual' package with install_size zero */
			pkg->ss.pkg_selectable =
				(pkg->repos & db->available_repos) ||
				pkg->cached_non_repository ||
				pkg->ipkg;

			/* Prune install_if packages that are no longer available,
			 * currently works only if SOLVERF_AVAILABLE is set in the
			 * global solver flags. */
			pkg->ss.iif_failed =
				(pkg->install_if->num == 0) ||
				((ss->solver_flags_inherit & APK_SOLVERF_AVAILABLE) &&
				 !pkg->ss.pkg_available);

			repos = get_pkg_repos(db, pkg);
			pkg->ss.tag_preferred =
				(pkg->filename != NULL) ||
				(pkg->installed_size == 0) ||
				(repos & ss->default_repos);
			pkg->ss.tag_ok =
				pkg->ss.tag_preferred ||
				pkg->cached_non_repository ||
				pkg->ipkg;
222

223
224
225
226
227
			foreach_array_item(dep, pkg->depends) {
				discover_name(ss, dep->name);
				pkg->ss.max_dep_chain = max(pkg->ss.max_dep_chain,
							    dep->name->ss.max_dep_chain+1);
			}
228

229
230
231
232
233
234
			dbg_printf("discover " PKG_VER_FMT ": tag_ok=%d, tag_pref=%d max_dep_chain=%d selectable=%d\n",
				PKG_VER_PRINTF(pkg),
				pkg->ss.tag_ok,
				pkg->ss.tag_preferred,
				pkg->ss.max_dep_chain,
				pkg->ss.pkg_selectable);
235
		}
236
237

		name->ss.no_iif &= pkg->ss.iif_failed;
238
		name->ss.max_dep_chain = max(name->ss.max_dep_chain, pkg->ss.max_dep_chain);
239

240
241
		dbg_printf("discover %s: max_dep_chain=%d no_iif=%d\n",
			name->name, name->ss.max_dep_chain, name->ss.no_iif);
242
	}
243
244
	foreach_array_item(pname0, name->rinstall_if)
		discover_name(ss, *pname0);
245
246
}

247
static void name_requirers_changed(struct apk_solver_state *ss, struct apk_name *name)
248
{
249
	queue_unresolved(ss, name);
250
	reevaluate_reverse_installif(ss, name);
251
	queue_dirty(ss, name);
252
253
}

254
255
static void inherit_pinning_and_flags(
	struct apk_solver_state *ss, struct apk_package *pkg, struct apk_package *ppkg)
256
257
258
{
	unsigned int repos = get_pkg_repos(ss->db, pkg);

259
260
261
262
263
264
265
266
267
268
269
270
	if (ppkg != NULL) {
		/* inherited */
		pkg->ss.solver_flags |= ppkg->ss.solver_flags_inheritable;
		pkg->ss.solver_flags_inheritable |= ppkg->ss.solver_flags_inheritable;
		pkg->ss.pinning_allowed |= ppkg->ss.pinning_allowed;
	} else {
		/* world dependency */
		pkg->ss.solver_flags |= ss->solver_flags_inherit;
		pkg->ss.solver_flags_inheritable |= ss->solver_flags_inherit;
		pkg->ss.pinning_allowed |= ss->pinning_inherit;
		/* also prefer main pinnings */
		pkg->ss.pinning_preferred = ss->pinning_inherit;
271
272
		pkg->ss.tag_preferred = !!(repos & apk_db_get_pinning_mask_repos(ss->db, pkg->ss.pinning_preferred));
	}
273
274
275
276
	pkg->ss.tag_ok |= !!(repos & apk_db_get_pinning_mask_repos(ss->db, pkg->ss.pinning_allowed));

	dbg_printf(PKG_VER_FMT ": tag_ok=%d, tag_pref=%d\n",
		PKG_VER_PRINTF(pkg), pkg->ss.tag_ok, pkg->ss.tag_preferred);
277
278
}

279
static void apply_constraint(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep)
280
{
281
	struct apk_name *name = dep->name;
282
283
	struct apk_provider *p0;
	int is_provided;
284

285
	dbg_printf("    apply_constraint: %s%s%s" BLOB_FMT "\n",
286
287
288
289
290
		dep->conflict ? "!" : "",
		name->name,
		apk_version_op_string(dep->result_mask),
		BLOB_PRINTF(*dep->version));

291
292
293
	if (dep->conflict && ss->ignore_conflict)
		return;

294
	name->ss.requirers += !dep->conflict;
295
296
	if (name->ss.requirers == 1 && !dep->conflict)
		name_requirers_changed(ss, name);
297

298
	foreach_array_item(p0, name->providers) {
299
		struct apk_package *pkg0 = p0->pkg;
300

301
		is_provided = apk_dep_is_provided(dep, p0);
302
		dbg_printf("    apply_constraint: provider: %s-" BLOB_FMT ": %d\n",
303
			pkg0->name->name, BLOB_PRINTF(*p0->version), is_provided);
304

305
		pkg0->ss.conflicts += !is_provided;
306
		if (unlikely(pkg0->ss.pkg_selectable && pkg0->ss.conflicts))
307
			disqualify_package(ss, pkg0, "conflicting dependency");
308

309
310
		if (is_provided)
			inherit_pinning_and_flags(ss, pkg0, ppkg);
311
	}
312
313
}

314
static void exclude_non_providers(struct apk_solver_state *ss, struct apk_name *name, struct apk_name *must_provide, int skip_virtuals)
315
316
317
318
{
	struct apk_provider *p;
	struct apk_dependency *d;

319
	if (name == must_provide || ss->ignore_conflict)
320
321
		return;

322
	dbg_printf("%s must provide %s (skip_virtuals=%d)\n", name->name, must_provide->name, skip_virtuals);
323
324

	foreach_array_item(p, name->providers) {
325
		if (p->pkg->name == must_provide || !p->pkg->ss.pkg_selectable ||
326
		    (skip_virtuals && p->version == &apk_atom_null))
327
328
			goto next;
		foreach_array_item(d, p->pkg->provides)
329
			if (d->name == must_provide || (skip_virtuals && d->version == &apk_atom_null))
330
331
332
333
334
335
				goto next;
		disqualify_package(ss, p->pkg, "provides transitivity");
	next: ;
	}
}

336
static inline int merge_index(unsigned short *index, int num_options)
337
{
338
339
340
	if (*index != num_options) return 0;
	*index = num_options + 1;
	return 1;
341
342
343
344
345
346
347
348
349
350
351
352
}

static inline int merge_index_complete(unsigned short *index, int num_options)
{
	int ret;

	ret = (*index == num_options);
	*index = 0;

	return ret;
}

353
static void reconsider_name(struct apk_solver_state *ss, struct apk_name *name)
354
{
355
	struct apk_name *name0, **pname0;
356
	struct apk_dependency *dep;
357
	struct apk_package *first_candidate = NULL, *pkg;
358
359
	struct apk_provider *p;
	int reevaluate_deps, reevaluate_iif;
360
	int num_options = 0, num_tag_not_ok = 0, has_iif = 0, no_iif = 1;
361

362
	dbg_printf("reconsider_name: %s\n", name->name);
363

364
365
	reevaluate_deps = name->ss.reevaluate_deps;
	reevaluate_iif = name->ss.reevaluate_iif;
366
	name->ss.reevaluate_deps = 0;
367
	name->ss.reevaluate_iif = 0;
368

369
370
	/* propagate down by merging common dependencies and
	 * applying new constraints */
371
	foreach_array_item(p, name->providers) {
372
		/* check if this pkg's dependencies have become unsatisfiable */
373
		pkg = p->pkg;
Timo Teräs's avatar
Timo Teräs committed
374
		pkg->ss.dependencies_merged = 0;
375
		if (reevaluate_deps) {
376
			if (!pkg->ss.pkg_selectable)
377
				continue;
378
			foreach_array_item(dep, pkg->depends) {
379
380
381
382
383
384
				if (!dependency_satisfiable(ss, dep)) {
					disqualify_package(ss, pkg, "dependency no longer satisfiable");
					break;
				}
			}
		}
385
		if (!pkg->ss.pkg_selectable)
386
			continue;
387

388
389
390
		if (reevaluate_iif &&
		    (pkg->ss.iif_triggered == 0 &&
		     pkg->ss.iif_failed == 0)) {
391
			pkg->ss.iif_triggered = 1;
392
			pkg->ss.iif_failed = 0;
393
			foreach_array_item(dep, pkg->install_if) {
394
395
396
397
398
399
				if (!dep->name->ss.locked) {
					pkg->ss.iif_triggered = 0;
					pkg->ss.iif_failed = 0;
					break;
				}
				if (!apk_dep_is_provided(dep, &dep->name->ss.chosen)) {
400
					pkg->ss.iif_triggered = 0;
401
					pkg->ss.iif_failed = 1;
402
					break;
403
				}
404
405
			}
		}
406
407
408
409
		if (reevaluate_iif && pkg->ss.iif_triggered) {
			foreach_array_item(dep, pkg->install_if)
				inherit_pinning_and_flags(ss, pkg, dep->name->ss.chosen.pkg);
		}
410
		has_iif |= pkg->ss.iif_triggered;
411
		no_iif  &= pkg->ss.iif_failed;
412
413
414
		dbg_printf("  "PKG_VER_FMT": iif_triggered=%d iif_failed=%d, no_iif=%d\n",
			PKG_VER_PRINTF(pkg), pkg->ss.iif_triggered, pkg->ss.iif_failed,
			no_iif);
Timo Teräs's avatar
Timo Teräs committed
415

416
		if (name->ss.requirers == 0)
417
			continue;
418

419
		/* merge common dependencies */
Timo Teräs's avatar
Timo Teräs committed
420
		pkg->ss.dependencies_merged = 1;
421
422
		if (first_candidate == NULL)
			first_candidate = pkg;
423
424
425
426
427
428

		/* FIXME: can merge also conflicts */
		foreach_array_item(dep, pkg->depends)
			if (!dep->conflict)
				merge_index(&dep->name->ss.merge_depends, num_options);

429
		if (merge_index(&pkg->name->ss.merge_provides, num_options))
430
			pkg->name->ss.has_virtual_provides |= (p->version == &apk_atom_null);
431
		foreach_array_item(dep, pkg->provides)
432
			if (merge_index(&dep->name->ss.merge_provides, num_options))
433
				dep->name->ss.has_virtual_provides |= (dep->version == &apk_atom_null);
434
435
436

		num_tag_not_ok += !pkg->ss.tag_ok;
		num_options++;
437
	}
438
	name->ss.has_options = (num_options > 1 || num_tag_not_ok > 0);
439
	name->ss.has_iif = has_iif;
440
	name->ss.no_iif = no_iif;
441
442
	queue_unresolved(ss, name);

443
	if (first_candidate != NULL) {
444
		pkg = first_candidate;
445
446
447
		foreach_array_item(p, name->providers)
			p->pkg->ss.dependencies_used = p->pkg->ss.dependencies_merged;

448
		/* propagate down common dependencies */
449
450
		if (num_options == 1) {
			/* FIXME: keeps increasing counts, use bit fields instead? */
451
452
453
			foreach_array_item(dep, pkg->depends)
				if (merge_index_complete(&dep->name->ss.merge_depends, num_options))
					apply_constraint(ss, pkg, dep);
454
455
		} else {
			/* FIXME: could merge versioning bits too */
456
			foreach_array_item(dep, pkg->depends) {
457
				name0 = dep->name;
458
459
				if (merge_index_complete(&name0->ss.merge_depends, num_options) &&
				    name0->ss.requirers == 0) {
460
					/* common dependency name with all */
461
462
463
464
					dbg_printf("%s common dependency: %s\n",
						   name->name, name0->name);
					name0->ss.requirers++;
					name_requirers_changed(ss, name0);
465
466
					foreach_array_item(p, name0->providers)
						inherit_pinning_and_flags(ss, p->pkg, pkg);
467
468
				}
			}
Timo Teräs's avatar
Timo Teräs committed
469
		}
470
471
472

		/* provides transitivity */
		if (merge_index_complete(&pkg->name->ss.merge_provides, num_options))
473
			exclude_non_providers(ss, pkg->name, name, pkg->name->ss.has_virtual_provides);
474
475
		foreach_array_item(dep, pkg->provides)
			if (merge_index_complete(&dep->name->ss.merge_provides, num_options))
476
477
478
479
480
				exclude_non_providers(ss, dep->name, name, dep->name->ss.has_virtual_provides);

		pkg->name->ss.has_virtual_provides = 0;
		foreach_array_item(dep, pkg->provides)
			dep->name->ss.has_virtual_provides = 0;
Timo Teräs's avatar
Timo Teräs committed
481
	}
482

483
484
485
486
487
488
489
490
491
492
493
	name->ss.reverse_deps_done = 1;
	foreach_array_item(pname0, name->rdepends) {
		name0 = *pname0;
		if (name0->ss.seen && !name0->ss.locked) {
			name->ss.reverse_deps_done = 0;
			break;
		}
	}

	dbg_printf("reconsider_name: %s [finished], has_options=%d, reverse_deps_done=%d\n",
		name->name, name->ss.has_options, name->ss.reverse_deps_done);
494
495
}

496
497
static int compare_providers(struct apk_solver_state *ss,
			     struct apk_provider *pA, struct apk_provider *pB)
498
{
499
500
	struct apk_database *db = ss->db;
	struct apk_package *pkgA = pA->pkg, *pkgB = pB->pkg;
501
	unsigned int solver_flags;
502
	int r;
503

504
	/* Prefer existing package */
Oliver Smith's avatar
Oliver Smith committed
505
506
	if (pkgA == NULL || pkgB == NULL) {
		dbg_printf("   prefer existing package\n");
507
		return (pkgA != NULL) - (pkgB != NULL);
Oliver Smith's avatar
Oliver Smith committed
508
	}
509

510
511
512
513
514
515
516
	/* Latest version required? */
	solver_flags = pkgA->ss.solver_flags | pkgB->ss.solver_flags;
	if ((solver_flags & APK_SOLVERF_LATEST) &&
	    (pkgA->ss.pinning_allowed == APK_DEFAULT_PINNING_MASK) &&
	    (pkgB->ss.pinning_allowed == APK_DEFAULT_PINNING_MASK)) {
		/* Prefer allowed pinning */
		r = (int)pkgA->ss.tag_ok - (int)pkgB->ss.tag_ok;
Oliver Smith's avatar
Oliver Smith committed
517
518
		if (r) {
			dbg_printf("    prefer allowed pinning\n");
519
			return r;
Oliver Smith's avatar
Oliver Smith committed
520
		}
521

522
		/* Prefer available */
523
		if (solver_flags & APK_SOLVERF_AVAILABLE) {
524
			r = (int)pkgA->ss.pkg_available - (int)pkgB->ss.pkg_available;
Oliver Smith's avatar
Oliver Smith committed
525
526
			if (r) {
				dbg_printf("    prefer available\n");
527
				return r;
Oliver Smith's avatar
Oliver Smith committed
528
			}
529
530
		} else if (solver_flags & APK_SOLVERF_REINSTALL) {
			r = (int)pkgA->ss.pkg_selectable - (int)pkgB->ss.pkg_selectable;
Oliver Smith's avatar
Oliver Smith committed
531
532
			if (r) {
				dbg_printf("    prefer available (reinstall)\n");
533
				return r;
Oliver Smith's avatar
Oliver Smith committed
534
			}
535
536
537
		}
	} else {
		/* Prefer without errors */
538
		r = (int)pkgA->ss.pkg_selectable - (int)pkgB->ss.pkg_selectable;
Oliver Smith's avatar
Oliver Smith committed
539
540
		if (r) {
			dbg_printf("    prefer without errors\n");
541
			return r;
Oliver Smith's avatar
Oliver Smith committed
542
		}
Timo Teräs's avatar
Timo Teräs committed
543

544
545
		/* Prefer those that were in last dependency merging group */
		r = (int)pkgA->ss.dependencies_used - (int)pkgB->ss.dependencies_used;
Oliver Smith's avatar
Oliver Smith committed
546
547
		if (r) {
			dbg_printf("    prefer those that were in last dependency merging group\n");
548
			return r;
Oliver Smith's avatar
Oliver Smith committed
549
		}
550
		r = pkgB->ss.conflicts - pkgA->ss.conflicts;
Oliver Smith's avatar
Oliver Smith committed
551
552
		if (r) {
			dbg_printf("    prefer those that were in last dependency merging group (#2)\n");
Timo Teräs's avatar
Timo Teräs committed
553
			return r;
Oliver Smith's avatar
Oliver Smith committed
554
		}
Timo Teräs's avatar
Timo Teräs committed
555

556
		/* Prefer installed on self-upgrade */
557
		if ((db->performing_self_upgrade && !(solver_flags & APK_SOLVERF_UPGRADE)) ||
558
		    (solver_flags & APK_SOLVERF_INSTALLED)) {
559
			r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
Oliver Smith's avatar
Oliver Smith committed
560
			if (r) {
561
				dbg_printf("    prefer installed\n");
562
				return r;
Oliver Smith's avatar
Oliver Smith committed
563
			}
564
		}
565

566
567
		/* Prefer allowed pinning */
		r = (int)pkgA->ss.tag_ok - (int)pkgB->ss.tag_ok;
Oliver Smith's avatar
Oliver Smith committed
568
569
		if (r) {
			dbg_printf("    prefer allowed pinning\n");
570
			return r;
Oliver Smith's avatar
Oliver Smith committed
571
		}
572

573
		/* Prefer available */
574
		if (solver_flags & APK_SOLVERF_AVAILABLE) {
575
			r = (int)pkgA->ss.pkg_available - (int)pkgB->ss.pkg_available;
Oliver Smith's avatar
Oliver Smith committed
576
577
			if (r) {
				dbg_printf("    prefer available\n");
578
				return r;
Oliver Smith's avatar
Oliver Smith committed
579
			}
580
		}
581

582
583
		/* Prefer preferred pinning */
		r = (int)pkgA->ss.tag_preferred - (int)pkgB->ss.tag_preferred;
Oliver Smith's avatar
Oliver Smith committed
584
585
		if (r) {
			dbg_printf("    prefer preferred pinning\n");
586
			return r;
Oliver Smith's avatar
Oliver Smith committed
587
		}
588
589

		/* Prefer installed */
590
		if (!(solver_flags & APK_SOLVERF_UPGRADE)) {
591
			r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
Oliver Smith's avatar
Oliver Smith committed
592
593
			if (r) {
				dbg_printf("    prefer installed\n");
594
				return r;
Oliver Smith's avatar
Oliver Smith committed
595
			}
596
		}
597
	}
598

599
600
601
	/* Select latest by requested name */
	switch (apk_version_compare_blob(*pA->version, *pB->version)) {
	case APK_VERSION_LESS:
Oliver Smith's avatar
Oliver Smith committed
602
		dbg_printf("    select latest by requested name (less)\n");
603
604
		return -1;
	case APK_VERSION_GREATER:
Oliver Smith's avatar
Oliver Smith committed
605
		dbg_printf("    select latest by requested name (greater)\n");
606
607
		return 1;
	}
608

609
610
611
612
	/* Select latest by principal name */
	if (pkgA->name == pkgB->name) {
		switch (apk_version_compare_blob(*pkgA->version, *pkgB->version)) {
		case APK_VERSION_LESS:
Oliver Smith's avatar
Oliver Smith committed
613
			dbg_printf("    select latest by principal name (less)\n");
614
615
			return -1;
		case APK_VERSION_GREATER:
Oliver Smith's avatar
Oliver Smith committed
616
			dbg_printf("    select latest by principal name (greater)\n");
617
618
619
			return 1;
		}
	}
Timo Teräs's avatar
Timo Teräs committed
620

621
622
	/* Prefer installed (matches here if upgrading) */
	r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
Oliver Smith's avatar
Oliver Smith committed
623
624
	if (r) {
		dbg_printf("    prefer installed (upgrading)\n");
625
		return r;
Oliver Smith's avatar
Oliver Smith committed
626
	}
627

628
629
	/* Prefer highest declared provider priority. */
	r = pkgA->provider_priority - pkgB->provider_priority;
Oliver Smith's avatar
Oliver Smith committed
630
631
	if (r) {
		dbg_printf("    prefer highest declared provider priority\n");
632
		return r;
Oliver Smith's avatar
Oliver Smith committed
633
	}
634

635
636
	/* Prefer without errors (mostly if --latest used, and different provider) */
	r = (int)pkgA->ss.pkg_selectable - (int)pkgB->ss.pkg_selectable;
Oliver Smith's avatar
Oliver Smith committed
637
638
	if (r) {
		dbg_printf("    prefer without errors (#2)\n");
639
		return r;
Oliver Smith's avatar
Oliver Smith committed
640
	}
641

642
	/* Prefer lowest available repository */
Oliver Smith's avatar
Oliver Smith committed
643
	dbg_printf("    prefer lowest available repository\n");
644
	return ffs(pkgB->repos) - ffs(pkgA->repos);
645
}
646

647
static void assign_name(struct apk_solver_state *ss, struct apk_name *name, struct apk_provider p)
648
{
649
	struct apk_provider *p0;
650
651
652

	if (name->ss.locked) {
		/* If both are providing this name without version, it's ok */
653
654
		if (p.version == &apk_atom_null &&
		    name->ss.chosen.version == &apk_atom_null)
655
			return;
656
657
		if (ss->ignore_conflict)
			return;
658
		/* Conflict: providing same name */
659
660
		mark_error(ss, p.pkg, "conflict: same name provided");
		mark_error(ss, name->ss.chosen.pkg, "conflict: same name provided");
661
		return;
662
	}
663

664
665
	if (p.pkg)
		dbg_printf("assign %s to "PKG_VER_FMT"\n", name->name, PKG_VER_PRINTF(p.pkg));
666

667
668
669
670
671
672
673
674
	name->ss.locked = 1;
	name->ss.chosen = p;
	if (list_hashed(&name->ss.unresolved_list))
		list_del(&name->ss.unresolved_list);
	if (list_hashed(&name->ss.dirty_list))
		list_del(&name->ss.dirty_list);

	/* disqualify all conflicting packages */
675
676
677
678
	if (!ss->ignore_conflict) {
		foreach_array_item(p0, name->providers) {
			if (p0->pkg == p.pkg)
				continue;
679
680
			if (p.version == &apk_atom_null &&
			    p0->version == &apk_atom_null)
681
682
683
				continue;
			disqualify_package(ss, p0->pkg, "conflicting provides");
		}
684
	}
685
	reevaluate_reverse_deps(ss, name);
686
	reevaluate_reverse_installif(ss, name);
687
688
}

689
static void select_package(struct apk_solver_state *ss, struct apk_name *name)
690
{
691
	struct apk_provider chosen = { NULL, &apk_atom_null }, *p;
692
	struct apk_package *pkg = NULL;
693
	struct apk_dependency *d;
694

695
	dbg_printf("select_package: %s (requirers=%d, iif=%d)\n", name->name, name->ss.requirers, name->ss.has_iif);
696

697
	if (name->ss.requirers || name->ss.has_iif) {
698
		foreach_array_item(p, name->providers) {
699
700
701
702
703
			dbg_printf("  consider "PKG_VER_FMT" iif_triggered=%d, tag_ok=%d, selectable=%d, available=%d, flags=0x%x, provider_priority=%d, installed=%d\n",
				PKG_VER_PRINTF(p->pkg),
				p->pkg->ss.iif_triggered, p->pkg->ss.tag_ok,
				p->pkg->ss.pkg_selectable, p->pkg->ss.pkg_available,
				p->pkg->ss.solver_flags,
704
				p->pkg->provider_priority, p->pkg->ipkg != NULL);
705
			/* Ensure valid pinning and install-if trigger */
706
			if (name->ss.requirers == 0 &&
707
			    (!p->pkg->ss.iif_triggered ||
Oliver Smith's avatar
Oliver Smith committed
708
709
			     !p->pkg->ss.tag_ok)) {
				dbg_printf("    ignore: invalid install-if trigger or invalid pinning\n");
710
				continue;
Oliver Smith's avatar
Oliver Smith committed
711
			}
712
713
			/* Virtual packages without provider_priority cannot be autoselected,
			 * unless there is only one provider */
714
			if (p->version == &apk_atom_null &&
715
716
			    p->pkg->name->auto_select_virtual == 0 &&
			    p->pkg->name->ss.requirers == 0 &&
Oliver Smith's avatar
Oliver Smith committed
717
718
			    (p->pkg->provider_priority == 0 && name->providers->num > 1)) {
				dbg_printf("    ignore: virtual package without provider_priority with >1 provider\n");
719
				continue;
Oliver Smith's avatar
Oliver Smith committed
720
721
722
			}
			if (compare_providers(ss, p, &chosen) > 0) {
				dbg_printf("    choose as new provider\n");
723
				chosen = *p;
Oliver Smith's avatar
Oliver Smith committed
724
			}
725
		}
726
	}
727

728
729
	pkg = chosen.pkg;
	if (pkg) {
730
		if (!pkg->ss.pkg_selectable || !pkg->ss.tag_ok) {
731
			/* Selecting broken or unallowed package */
732
			mark_error(ss, pkg, "broken package / tag not ok");
733
		}
734
		dbg_printf("selecting: " PKG_VER_FMT ", available: %d\n", PKG_VER_PRINTF(pkg), pkg->ss.pkg_selectable);
735

736
		assign_name(ss, pkg->name, APK_PROVIDER_FROM_PACKAGE(pkg));
737
738
739
740
741
		foreach_array_item(d, pkg->provides)
			assign_name(ss, d->name, APK_PROVIDER_FROM_PROVIDES(pkg, d));

		foreach_array_item(d, pkg->depends)
			apply_constraint(ss, pkg, d);
742
743
744
	} else {
		dbg_printf("selecting: %s [unassigned]\n", name->name);
		assign_name(ss, name, provider_none);
745
746
747
748
		if (name->ss.requirers > 0) {
			dbg_printf("ERROR NO-PROVIDER: %s\n", name->name);
			ss->errors++;
		}
749
	}
750
751
}

752
static void record_change(struct apk_solver_state *ss, struct apk_package *opkg, struct apk_package *npkg)
753
{
754
755
756
	struct apk_changeset *changeset = ss->changeset;
	struct apk_change *change;

757
	change = apk_change_array_add(&changeset->changes);
758
759
760
	*change = (struct apk_change) {
		.old_pkg = opkg,
		.old_repository_tag = opkg ? opkg->ipkg->repository_tag : 0,
761
762
763
		.new_pkg = npkg,
		.new_repository_tag = npkg ? get_tag(ss->db, npkg->ss.pinning_allowed, get_pkg_repos(ss->db, npkg)) : 0,
		.reinstall = npkg ? !!(npkg->ss.solver_flags & APK_SOLVERF_REINSTALL) : 0,
764
	};
765
	if (npkg == NULL)
766
		changeset->num_remove++;
767
	else if (opkg == NULL)
768
		changeset->num_install++;
769
	else if (npkg != opkg || change->reinstall || change->new_repository_tag != change->old_repository_tag)
770
		changeset->num_adjust++;
771
}
772

773
774
775
776
static void cset_gen_name_change(struct apk_solver_state *ss, struct apk_name *name);
static void cset_gen_name_remove(struct apk_solver_state *ss, struct apk_package *pkg);
static void cset_gen_dep(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep);

777
static void cset_track_deps_added(struct apk_package *pkg)
778
779
780
{
	struct apk_dependency *d;

781
782
783
784
785
	foreach_array_item(d, pkg->depends) {
		if (d->conflict || !d->name->ss.installed_name)
			continue;
		d->name->ss.installed_name->ss.requirers++;
	}
786
787
788
789
790
791
792
793
}

static void cset_track_deps_removed(struct apk_solver_state *ss, struct apk_package *pkg)
{
	struct apk_dependency *d;
	struct apk_package *pkg0;

	foreach_array_item(d, pkg->depends) {
794
		if (d->conflict || !d->name->ss.installed_name)
795
			continue;
796
		if (--d->name->ss.installed_name->ss.requirers > 0)
797
			continue;
798
		pkg0 = d->name->ss.installed_pkg;
799
800
801
802
803
804
805
		if (pkg0 != NULL)
			cset_gen_name_remove(ss, pkg0);
	}
}

static void cset_check_removal_by_deps(struct apk_solver_state *ss, struct apk_package *pkg)
{
806
807
808
809
810
811
	/* NOTE: an orphaned package name may have 0 requirers because it is now being satisfied
	 * through an alternate provider.  In these cases, we will handle this later as an adjustment
	 * operation using cset_gen_name_change().  As such, only insert a removal into the transaction
	 * if there is no other resolved provider.
	 */
	if (pkg->name->ss.requirers == 0 && pkg->name->ss.chosen.pkg == NULL)
812
		cset_gen_name_remove(ss, pkg);
813
814
}

815
static void cset_check_install_by_iif(struct apk_solver_state *ss, struct apk_name *name)
816
{
817
	struct apk_package *pkg = name->ss.chosen.pkg;
818
	struct apk_dependency *dep0;
819

820
	if (pkg == NULL || !name->ss.seen || name->ss.in_changeset)
821
822
		return;