solver.c 32.8 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 498 499 500 501 502 503 504 505 506
static int count_requirers(const struct apk_package *pkg)
{
	int cnt = pkg->name->ss.requirers;
	struct apk_dependency *p;

	foreach_array_item(p, pkg->provides)
		cnt += p->name->ss.requirers;

	return cnt;
}

507 508
static int compare_providers(struct apk_solver_state *ss,
			     struct apk_provider *pA, struct apk_provider *pB)
509
{
510 511
	struct apk_database *db = ss->db;
	struct apk_package *pkgA = pA->pkg, *pkgB = pB->pkg;
512
	unsigned int solver_flags;
513
	int r;
514

515
	/* Prefer existing package */
Oliver Smith's avatar
Oliver Smith committed
516 517
	if (pkgA == NULL || pkgB == NULL) {
		dbg_printf("   prefer existing package\n");
518
		return (pkgA != NULL) - (pkgB != NULL);
Oliver Smith's avatar
Oliver Smith committed
519
	}
520

521 522 523 524 525 526 527
	/* 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
528 529
		if (r) {
			dbg_printf("    prefer allowed pinning\n");
530
			return r;
Oliver Smith's avatar
Oliver Smith committed
531
		}
532

533
		/* Prefer available */
534
		if (solver_flags & APK_SOLVERF_AVAILABLE) {
535
			r = (int)pkgA->ss.pkg_available - (int)pkgB->ss.pkg_available;
Oliver Smith's avatar
Oliver Smith committed
536 537
			if (r) {
				dbg_printf("    prefer available\n");
538
				return r;
Oliver Smith's avatar
Oliver Smith committed
539
			}
540 541
		} 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
542 543
			if (r) {
				dbg_printf("    prefer available (reinstall)\n");
544
				return r;
Oliver Smith's avatar
Oliver Smith committed
545
			}
546 547 548
		}
	} else {
		/* Prefer without errors */
549
		r = (int)pkgA->ss.pkg_selectable - (int)pkgB->ss.pkg_selectable;
Oliver Smith's avatar
Oliver Smith committed
550 551
		if (r) {
			dbg_printf("    prefer without errors\n");
552
			return r;
Oliver Smith's avatar
Oliver Smith committed
553
		}
Timo Teräs's avatar
Timo Teräs committed
554

555 556
		/* 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
557 558
		if (r) {
			dbg_printf("    prefer those that were in last dependency merging group\n");
559
			return r;
Oliver Smith's avatar
Oliver Smith committed
560
		}
561
		r = pkgB->ss.conflicts - pkgA->ss.conflicts;
Oliver Smith's avatar
Oliver Smith committed
562 563
		if (r) {
			dbg_printf("    prefer those that were in last dependency merging group (#2)\n");
Timo Teräs's avatar
Timo Teräs committed
564
			return r;
Oliver Smith's avatar
Oliver Smith committed
565
		}
Timo Teräs's avatar
Timo Teräs committed
566

567
		/* Prefer installed on self-upgrade */
568
		if ((db->performing_self_upgrade && !(solver_flags & APK_SOLVERF_UPGRADE)) ||
569
		    (solver_flags & APK_SOLVERF_INSTALLED)) {
570
			r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
Oliver Smith's avatar
Oliver Smith committed
571
			if (r) {
572
				dbg_printf("    prefer installed\n");
573
				return r;
Oliver Smith's avatar
Oliver Smith committed
574
			}
575
		}
576

577 578
		/* Prefer allowed pinning */
		r = (int)pkgA->ss.tag_ok - (int)pkgB->ss.tag_ok;
Oliver Smith's avatar
Oliver Smith committed
579 580
		if (r) {
			dbg_printf("    prefer allowed pinning\n");
581
			return r;
Oliver Smith's avatar
Oliver Smith committed
582
		}
583

584
		/* Prefer available */
585
		if (solver_flags & APK_SOLVERF_AVAILABLE) {
586
			r = (int)pkgA->ss.pkg_available - (int)pkgB->ss.pkg_available;
Oliver Smith's avatar
Oliver Smith committed
587 588
			if (r) {
				dbg_printf("    prefer available\n");
589
				return r;
Oliver Smith's avatar
Oliver Smith committed
590
			}
591
		}
592

593 594
		/* Prefer preferred pinning */
		r = (int)pkgA->ss.tag_preferred - (int)pkgB->ss.tag_preferred;
Oliver Smith's avatar
Oliver Smith committed
595 596
		if (r) {
			dbg_printf("    prefer preferred pinning\n");
597
			return r;
Oliver Smith's avatar
Oliver Smith committed
598
		}
599

600 601
		/* Prefer highest requirer count. */
		r = count_requirers(pkgA) - count_requirers(pkgB);
Oliver Smith's avatar
Oliver Smith committed
602 603
		if (r) {
			dbg_printf("    prefer highest requirer count\n");
604
			return r;
Oliver Smith's avatar
Oliver Smith committed
605
		}
606

607
		/* Prefer installed */
608
		if (!(solver_flags & APK_SOLVERF_UPGRADE)) {
609
			r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
Oliver Smith's avatar
Oliver Smith committed
610 611
			if (r) {
				dbg_printf("    prefer installed\n");
612
				return r;
Oliver Smith's avatar
Oliver Smith committed
613
			}
614
		}
615
	}
616

617 618 619
	/* 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
620
		dbg_printf("    select latest by requested name (less)\n");
621 622
		return -1;
	case APK_VERSION_GREATER:
Oliver Smith's avatar
Oliver Smith committed
623
		dbg_printf("    select latest by requested name (greater)\n");
624 625
		return 1;
	}
626

627 628 629 630
	/* 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
631
			dbg_printf("    select latest by principal name (less)\n");
632 633
			return -1;
		case APK_VERSION_GREATER:
Oliver Smith's avatar
Oliver Smith committed
634
			dbg_printf("    select latest by principal name (greater)\n");
635 636 637
			return 1;
		}
	}
Timo Teräs's avatar
Timo Teräs committed
638

639 640
	/* Prefer installed (matches here if upgrading) */
	r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
Oliver Smith's avatar
Oliver Smith committed
641 642
	if (r) {
		dbg_printf("    prefer installed (upgrading)\n");
643
		return r;
Oliver Smith's avatar
Oliver Smith committed
644
	}
645

646 647
	/* Prefer highest declared provider priority. */
	r = pkgA->provider_priority - pkgB->provider_priority;
Oliver Smith's avatar
Oliver Smith committed
648 649
	if (r) {
		dbg_printf("    prefer highest declared provider priority\n");
650
		return r;
Oliver Smith's avatar
Oliver Smith committed
651
	}
652

653 654
	/* 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
655 656
	if (r) {
		dbg_printf("    prefer without errors (#2)\n");
657
		return r;
Oliver Smith's avatar
Oliver Smith committed
658
	}
659

660
	/* Prefer lowest available repository */
Oliver Smith's avatar
Oliver Smith committed
661
	dbg_printf("    prefer lowest available repository\n");
662
	return ffs(pkgB->repos) - ffs(pkgA->repos);
663
}
664

665
static void assign_name(struct apk_solver_state *ss, struct apk_name *name, struct apk_provider p)
666
{
667
	struct apk_provider *p0;
668 669 670

	if (name->ss.locked) {
		/* If both are providing this name without version, it's ok */
671 672
		if (p.version == &apk_atom_null &&
		    name->ss.chosen.version == &apk_atom_null)
673
			return;
674 675
		if (ss->ignore_conflict)
			return;
676
		/* Conflict: providing same name */
677 678
		mark_error(ss, p.pkg, "conflict: same name provided");
		mark_error(ss, name->ss.chosen.pkg, "conflict: same name provided");
679
		return;
680
	}
681

682 683
	if (p.pkg)
		dbg_printf("assign %s to "PKG_VER_FMT"\n", name->name, PKG_VER_PRINTF(p.pkg));
684

685 686 687 688 689 690 691 692
	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 */
693 694 695 696
	if (!ss->ignore_conflict) {
		foreach_array_item(p0, name->providers) {
			if (p0->pkg == p.pkg)
				continue;
697 698
			if (p.version == &apk_atom_null &&
			    p0->version == &apk_atom_null)
699 700 701
				continue;
			disqualify_package(ss, p0->pkg, "conflicting provides");
		}
702
	}
703
	reevaluate_reverse_deps(ss, name);
704
	reevaluate_reverse_installif(ss, name);
705 706
}

707
static void select_package(struct apk_solver_state *ss, struct apk_name *name)
708
{
709
	struct apk_provider chosen = { NULL, &apk_atom_null }, *p;
710
	struct apk_package *pkg = NULL;
711
	struct apk_dependency *d;
712

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

715
	if (name->ss.requirers || name->ss.has_iif) {
716
		foreach_array_item(p, name->providers) {
717 718 719 720 721
			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,
722
				p->pkg->provider_priority, p->pkg->ipkg != NULL);
723
			/* Ensure valid pinning and install-if trigger */
724
			if (name->ss.requirers == 0 &&
725
			    (!p->pkg->ss.iif_triggered ||
Oliver Smith's avatar
Oliver Smith committed
726 727
			     !p->pkg->ss.tag_ok)) {
				dbg_printf("    ignore: invalid install-if trigger or invalid pinning\n");
728
				continue;
Oliver Smith's avatar
Oliver Smith committed
729
			}
730 731
			/* Virtual packages without provider_priority cannot be autoselected,
			 * unless there is only one provider */
732
			if (p->version == &apk_atom_null &&
733 734
			    p->pkg->name->auto_select_virtual == 0 &&
			    p->pkg->name->ss.requirers == 0 &&
Oliver Smith's avatar
Oliver Smith committed
735 736
			    (p->pkg->provider_priority == 0 && name->providers->num > 1)) {
				dbg_printf("    ignore: virtual package without provider_priority with >1 provider\n");
737
				continue;
Oliver Smith's avatar
Oliver Smith committed
738 739 740
			}
			if (compare_providers(ss, p, &chosen) > 0) {
				dbg_printf("    choose as new provider\n");
741
				chosen = *p;
Oliver Smith's avatar
Oliver Smith committed
742
			}
743
		}
744
	}