solver.c 27 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 7 8 9 10 11
 * All rights reserved.
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 as published
 * by the Free Software Foundation. See http://www.gnu.org/ for details.
 */

12
#include <stdint.h>
13
#include <unistd.h>
14
#include <strings.h>
15 16 17 18 19
#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
20 21
#include "apk_print.h"

22 23 24
//#define DEBUG_PRINT

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

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

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

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

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

55 56
	foreach_array_item(p, name->providers) {
		struct apk_package *pkg = p->pkg;
57 58 59
		pkg->ss.solver_flags |= solver_flags;
		pkg->ss.solver_flags_inheritable |= solver_flags_inheritable;
	}
60 61
}

62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
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);
}

80 81 82 83 84 85 86 87
static void mark_error(struct apk_solver_state *ss, struct apk_package *pkg)
{
	if (pkg == NULL || pkg->ss.error)
		return;
	pkg->ss.error = 1;
	ss->errors++;
}

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

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

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

102 103
	if (name->ss.locked)
		return;
104

105
	want = (name->ss.requirers > 0) || (name->ss.has_iif);
106
	dbg_printf("queue_unresolved: %s, want=%d (requirers=%d, has_iif=%d)\n", name->name, want, name->ss.requirers, name->ss.has_iif);
107 108 109 110
	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);
111 112
}

113
static void reevaluate_reverse_deps(struct apk_solver_state *ss, struct apk_name *name)
114
{
115 116 117 118 119 120 121 122 123
	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);
	}
124
}
125

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

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

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

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

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

158 159
	if (name->ss.locked)
		return apk_dep_is_provided(dep, &name->ss.chosen);
160

161 162
	if (name->ss.requirers == 0 && apk_dep_is_provided(dep, &provider_none))
		return TRUE;
163

164
	foreach_array_item(p, name->providers)
165
		if (p->pkg->ss.pkg_selectable && apk_dep_is_provided(dep, p))
166
			return TRUE;
167

168
	return FALSE;
169 170
}

171
static void discover_name(struct apk_solver_state *ss, struct apk_name *name)
172
{
173
	struct apk_database *db = ss->db;
174 175 176
	struct apk_name **pname0;
	struct apk_provider *p;
	struct apk_dependency *dep;
177
	unsigned int repos;
178

179 180
	if (name->ss.seen)
		return;
181

182
	name->ss.seen = 1;
183
	name->ss.no_iif = 1;
184 185
	foreach_array_item(p, name->providers) {
		struct apk_package *pkg = p->pkg;
186
		if (pkg->ss.seen)
187
			continue;
188

189
		pkg->ss.seen = 1;
190 191 192
		pkg->ss.iif_failed = (pkg->install_if->num == 0);
		name->ss.no_iif &= pkg->ss.iif_failed;

193 194
		pkg->ss.pinning_allowed = APK_DEFAULT_PINNING_MASK;
		pkg->ss.pinning_preferred = APK_DEFAULT_PINNING_MASK;
195 196
		pkg->ss.pkg_available =
			(pkg->filename != NULL) ||
197 198 199 200 201 202
			(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->ipkg;
203 204

		repos = get_pkg_repos(db, pkg);
205 206 207 208 209
		pkg->ss.tag_preferred =
			(pkg->filename != NULL) ||
			(pkg->installed_size == 0) ||
			!!(repos & ss->default_repos);
		pkg->ss.tag_ok = pkg->ss.tag_preferred || pkg->ipkg;
210

211 212
		foreach_array_item(dep, pkg->depends) {
			discover_name(ss, dep->name);
213
			pkg->ss.max_dep_chain = max(pkg->ss.max_dep_chain,
214 215
						    dep->name->ss.max_dep_chain+1);
		}
216
		name->ss.max_dep_chain = max(name->ss.max_dep_chain, pkg->ss.max_dep_chain);
217

218
		dbg_printf("discover " PKG_VER_FMT ": tag_ok=%d, tag_pref=%d max_dep_chain=%d selectable=%d\n",
219 220 221
			PKG_VER_PRINTF(pkg),
			pkg->ss.tag_ok,
			pkg->ss.tag_preferred,
222
			pkg->ss.max_dep_chain,
223
			pkg->ss.pkg_selectable);
224
	}
225 226
	foreach_array_item(pname0, name->rinstall_if)
		discover_name(ss, *pname0);
227 228
}

229
static void name_requirers_changed(struct apk_solver_state *ss, struct apk_name *name)
230
{
231
	queue_unresolved(ss, name);
232
	reevaluate_reverse_installif(ss, name);
233
	queue_dirty(ss, name);
234 235
}

236 237
static void inherit_pinning_and_flags(
	struct apk_solver_state *ss, struct apk_package *pkg, struct apk_package *ppkg)
238 239 240
{
	unsigned int repos = get_pkg_repos(ss->db, pkg);

241 242 243 244 245 246 247 248 249 250 251 252
	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;
253 254
		pkg->ss.tag_preferred = !!(repos & apk_db_get_pinning_mask_repos(ss->db, pkg->ss.pinning_preferred));
	}
255 256 257 258
	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);
259 260
}

261
static void apply_constraint(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep)
262
{
263
	struct apk_name *name = dep->name;
264 265
	struct apk_provider *p0;
	int is_provided;
266

267
	dbg_printf("    apply_constraint: %s%s%s" BLOB_FMT "\n",
268 269 270 271 272 273
		dep->conflict ? "!" : "",
		name->name,
		apk_version_op_string(dep->result_mask),
		BLOB_PRINTF(*dep->version));

	name->ss.requirers += !dep->conflict;
274 275
	if (name->ss.requirers == 1 && !dep->conflict)
		name_requirers_changed(ss, name);
276

277
	foreach_array_item(p0, name->providers) {
278
		struct apk_package *pkg0 = p0->pkg;
279

280
		is_provided = apk_dep_is_provided(dep, p0);
281
		dbg_printf("    apply_constraint: provider: %s-" BLOB_FMT ": %d\n",
282
			pkg0->name->name, BLOB_PRINTF(*p0->version), is_provided);
283

284
		pkg0->ss.conflicts += !is_provided;
285
		if (unlikely(pkg0->ss.pkg_selectable && pkg0->ss.conflicts))
286
			disqualify_package(ss, pkg0, "conflicting dependency");
287

288 289
		if (is_provided)
			inherit_pinning_and_flags(ss, pkg0, ppkg);
290
	}
291 292
}

293 294 295 296 297
static void exclude_non_providers(struct apk_solver_state *ss, struct apk_name *name, struct apk_name *must_provide)
{
	struct apk_provider *p;
	struct apk_dependency *d;

298 299 300
	if (name == must_provide)
		return;

301 302 303
	dbg_printf("%s must provide %s\n", name->name, must_provide->name);

	foreach_array_item(p, name->providers) {
304
		if (p->pkg->name == must_provide || !p->pkg->ss.pkg_selectable)
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
			goto next;
		foreach_array_item(d, p->pkg->provides)
			if (d->name == must_provide)
				goto next;
		disqualify_package(ss, p->pkg, "provides transitivity");
	next: ;
	}
}

static inline void merge_index(unsigned short *index, int num_options)
{
	if (*index == num_options)
		*index = num_options + 1;
}

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

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

	return ret;
}

330
static void reconsider_name(struct apk_solver_state *ss, struct apk_name *name)
331
{
332
	struct apk_name *name0, **pname0;
333
	struct apk_dependency *dep;
334
	struct apk_package *first_candidate = NULL, *pkg;
335 336
	struct apk_provider *p;
	int reevaluate_deps, reevaluate_iif;
337
	int num_options = 0, num_tag_not_ok = 0, has_iif = 0, no_iif = 1;
338

339
	dbg_printf("reconsider_name: %s\n", name->name);
340

341 342
	reevaluate_deps = name->ss.reevaluate_deps;
	reevaluate_iif = name->ss.reevaluate_iif;
343
	name->ss.reevaluate_deps = 0;
344
	name->ss.reevaluate_iif = 0;
345

346 347
	/* propagate down by merging common dependencies and
	 * applying new constraints */
348
	foreach_array_item(p, name->providers) {
349
		/* check if this pkg's dependencies have become unsatisfiable */
350
		pkg = p->pkg;
Timo Teräs's avatar
Timo Teräs committed
351
		pkg->ss.dependencies_merged = 0;
352
		if (reevaluate_deps) {
353
			if (!pkg->ss.pkg_selectable)
354
				continue;
355
			foreach_array_item(dep, pkg->depends) {
356 357 358 359 360 361
				if (!dependency_satisfiable(ss, dep)) {
					disqualify_package(ss, pkg, "dependency no longer satisfiable");
					break;
				}
			}
		}
362
		if (!pkg->ss.pkg_selectable)
363
			continue;
364

365 366 367
		if (reevaluate_iif &&
		    (pkg->ss.iif_triggered == 0 &&
		     pkg->ss.iif_failed == 0)) {
368
			pkg->ss.iif_triggered = 1;
369
			pkg->ss.iif_failed = 0;
370
			foreach_array_item(dep, pkg->install_if) {
371 372 373 374 375 376
				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)) {
377
					pkg->ss.iif_triggered = 0;
378
					pkg->ss.iif_failed = 1;
379
					break;
380
				}
381 382
			}
		}
383 384 385 386 387 388
		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);
		}
		dbg_printf("  "PKG_VER_FMT": iif_triggered=%d iif_failed=%d\n",
			PKG_VER_PRINTF(pkg), pkg->ss.iif_triggered, pkg->ss.iif_failed);
389
		has_iif |= pkg->ss.iif_triggered;
390
		no_iif  &= pkg->ss.iif_failed;
Timo Teräs's avatar
Timo Teräs committed
391

392
		if (name->ss.requirers == 0)
393
			continue;
394

395
		/* merge common dependencies */
Timo Teräs's avatar
Timo Teräs committed
396
		pkg->ss.dependencies_merged = 1;
397 398
		if (first_candidate == NULL)
			first_candidate = pkg;
399 400 401 402 403 404 405 406 407 408

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

		merge_index(&pkg->name->ss.merge_provides, num_options);
		foreach_array_item(dep, pkg->provides)
			if (dep->version != &apk_null_blob)
				merge_index(&dep->name->ss.merge_provides, num_options);
409 410 411

		num_tag_not_ok += !pkg->ss.tag_ok;
		num_options++;
412
	}
413
	name->ss.has_options = (num_options > 1 || num_tag_not_ok > 0);
414
	name->ss.has_iif = has_iif;
415
	name->ss.no_iif = no_iif;
416 417
	queue_unresolved(ss, name);

418
	if (first_candidate != NULL) {
419
		pkg = first_candidate;
420 421 422
		foreach_array_item(p, name->providers)
			p->pkg->ss.dependencies_used = p->pkg->ss.dependencies_merged;

423
		/* propagate down common dependencies */
424 425
		if (num_options == 1) {
			/* FIXME: keeps increasing counts, use bit fields instead? */
426 427 428
			foreach_array_item(dep, pkg->depends)
				if (merge_index_complete(&dep->name->ss.merge_depends, num_options))
					apply_constraint(ss, pkg, dep);
429 430
		} else {
			/* FIXME: could merge versioning bits too */
431
			foreach_array_item(dep, pkg->depends) {
432
				name0 = dep->name;
433 434
				if (merge_index_complete(&name0->ss.merge_depends, num_options) &&
				    name0->ss.requirers == 0) {
435
					/* common dependency name with all */
436 437 438 439
					dbg_printf("%s common dependency: %s\n",
						   name->name, name0->name);
					name0->ss.requirers++;
					name_requirers_changed(ss, name0);
440 441
				}
			}
Timo Teräs's avatar
Timo Teräs committed
442
		}
443 444 445 446 447 448 449

		/* provides transitivity */
		if (merge_index_complete(&pkg->name->ss.merge_provides, num_options))
			exclude_non_providers(ss, pkg->name, name);
		foreach_array_item(dep, pkg->provides)
			if (merge_index_complete(&dep->name->ss.merge_provides, num_options))
				exclude_non_providers(ss, dep->name, name);
Timo Teräs's avatar
Timo Teräs committed
450
	}
451

452 453 454 455 456 457 458 459 460 461 462
	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);
463 464
}

465 466
static int compare_providers(struct apk_solver_state *ss,
			     struct apk_provider *pA, struct apk_provider *pB)
467
{
468 469
	struct apk_database *db = ss->db;
	struct apk_package *pkgA = pA->pkg, *pkgB = pB->pkg;
470
	unsigned int solver_flags;
471
	int r;
472

473 474 475
	/* Prefer existing package */
	if (pkgA == NULL || pkgB == NULL)
		return (pkgA != NULL) - (pkgB != NULL);
476

477 478 479 480 481 482 483 484 485
	/* 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;
		if (r)
			return r;
486

487
		/* Prefer available */
488
		if (solver_flags & APK_SOLVERF_AVAILABLE) {
489
			r = (int)pkgA->ss.pkg_available - (int)pkgB->ss.pkg_available;
490 491
			if (r)
				return r;
492 493 494 495
		} else if (solver_flags & APK_SOLVERF_REINSTALL) {
			r = (int)pkgA->ss.pkg_selectable - (int)pkgB->ss.pkg_selectable;
			if (r)
				return r;
496 497 498
		}
	} else {
		/* Prefer without errors */
499
		r = (int)pkgA->ss.pkg_selectable - (int)pkgB->ss.pkg_selectable;
500 501
		if (r)
			return r;
Timo Teräs's avatar
Timo Teräs committed
502

503 504 505 506 507
		/* Prefer those that were in last dependency merging group */
		r = (int)pkgA->ss.dependencies_used - (int)pkgB->ss.dependencies_used;
		if (r)
			return r;
		r = pkgB->ss.conflicts - pkgA->ss.conflicts;
Timo Teräs's avatar
Timo Teräs committed
508 509 510
		if (r)
			return r;

511 512 513 514 515 516
		/* Prefer installed on self-upgrade */
		if (db->performing_self_update && !(solver_flags & APK_SOLVERF_UPGRADE)) {
			r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
			if (r)
				return r;
		}
517

518 519
		/* Prefer allowed pinning */
		r = (int)pkgA->ss.tag_ok - (int)pkgB->ss.tag_ok;
520 521
		if (r)
			return r;
522

523
		/* Prefer available */
524
		if (solver_flags & APK_SOLVERF_AVAILABLE) {
525
			r = (int)pkgA->ss.pkg_available - (int)pkgB->ss.pkg_available;
526 527
			if (r)
				return r;
528 529 530 531
		} else if (solver_flags & APK_SOLVERF_REINSTALL) {
			r = (int)pkgA->ss.pkg_selectable - (int)pkgB->ss.pkg_selectable;
			if (r)
				return r;
532
		}
533

534 535
		/* Prefer preferred pinning */
		r = (int)pkgA->ss.tag_preferred - (int)pkgB->ss.tag_preferred;
536 537
		if (r)
			return r;
538 539 540 541 542 543 544

		/* Prefer installed */
		if (!(solver_flags & APK_SOLVERF_UPGRADE)) {
			r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
			if (r)
				return r;
		}
545
	}
546

547 548 549 550 551 552 553
	/* Select latest by requested name */
	switch (apk_version_compare_blob(*pA->version, *pB->version)) {
	case APK_VERSION_LESS:
		return -1;
	case APK_VERSION_GREATER:
		return 1;
	}
554

555 556 557 558 559 560 561 562 563
	/* Select latest by principal name */
	if (pkgA->name == pkgB->name) {
		switch (apk_version_compare_blob(*pkgA->version, *pkgB->version)) {
		case APK_VERSION_LESS:
			return -1;
		case APK_VERSION_GREATER:
			return 1;
		}
	}
Timo Teräs's avatar
Timo Teräs committed
564

565 566 567 568
	/* Prefer installed (matches here if upgrading) */
	r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
	if (r)
		return r;
569

570
	/* Prefer lowest available repository */
571
	return ffs(pkgB->repos) - ffs(pkgA->repos);
572
}
573

574
static void assign_name(struct apk_solver_state *ss, struct apk_name *name, struct apk_provider p)
575
{
576
	struct apk_provider *p0;
577 578 579 580 581 582

	if (name->ss.locked) {
		/* If both are providing this name without version, it's ok */
		if (p.version == &apk_null_blob &&
		    name->ss.chosen.version == &apk_null_blob)
			return;
583 584 585
		/* Conflict: providing same name */
		mark_error(ss, p.pkg);
		mark_error(ss, name->ss.chosen.pkg);
586
		return;
587
	}
588

589 590
	if (p.pkg)
		dbg_printf("assign %s to "PKG_VER_FMT"\n", name->name, PKG_VER_PRINTF(p.pkg));
591

592 593 594 595 596 597 598 599
	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 */
600 601
	foreach_array_item(p0, name->providers) {
		if (p0->pkg == p.pkg)
602 603
			continue;
		if (p.version == &apk_null_blob &&
604
		    p0->version == &apk_null_blob)
605
			continue;
606
		disqualify_package(ss, p0->pkg, "conflicting provides");
607
	}
608
	reevaluate_reverse_deps(ss, name);
609
	reevaluate_reverse_installif(ss, name);
610 611
}

612
static void select_package(struct apk_solver_state *ss, struct apk_name *name)
613
{
614
	struct apk_provider chosen = { NULL, &apk_null_blob }, *p;
615
	struct apk_package *pkg = NULL;
616
	struct apk_dependency *d;
617

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

620
	if (name->ss.requirers || name->ss.has_iif) {
621
		foreach_array_item(p, name->providers) {
622 623
			dbg_printf("  consider "PKG_VER_FMT" iif_triggered=%d, tag_ok=%d\n",
				PKG_VER_PRINTF(p->pkg), p->pkg->ss.iif_triggered, p->pkg->ss.tag_ok);
624
			/* Ensure valid pinning and install-if trigger */
625
			if (name->ss.requirers == 0 &&
626 627
			    (!p->pkg->ss.iif_triggered ||
			     !p->pkg->ss.tag_ok))
628
				continue;
629 630 631
			/* Virtual packages cannot be autoselected */
			if (p->version == &apk_null_blob && p->pkg->name->ss.requirers == 0)
				continue;
632 633
			if (compare_providers(ss, p, &chosen) > 0)
				chosen = *p;
634
		}
635
	}
636

637 638
	pkg = chosen.pkg;
	if (pkg) {
639
		if (!pkg->ss.pkg_selectable || !pkg->ss.tag_ok) {
640 641 642
			/* Selecting broken or unallowed package */
			mark_error(ss, pkg);
		}
643
		dbg_printf("selecting: " PKG_VER_FMT ", available: %d\n", PKG_VER_PRINTF(pkg), pkg->ss.pkg_selectable);
644

645
		assign_name(ss, pkg->name, APK_PROVIDER_FROM_PACKAGE(pkg));
646 647 648 649 650
		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);
651 652 653
	} else {
		dbg_printf("selecting: %s [unassigned]\n", name->name);
		assign_name(ss, name, provider_none);
654
		ss->errors += (name->ss.requirers > 0);
655
	}
656 657
}

658
static void record_change(struct apk_solver_state *ss, struct apk_package *opkg, struct apk_package *npkg)
659
{
660 661 662
	struct apk_changeset *changeset = ss->changeset;
	struct apk_change *change;

663
	change = apk_change_array_add(&changeset->changes);
664 665 666
	*change = (struct apk_change) {
		.old_pkg = opkg,
		.old_repository_tag = opkg ? opkg->ipkg->repository_tag : 0,
667 668 669
		.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,
670
	};
671
	if (npkg == NULL)
672
		changeset->num_remove++;
673
	else if (opkg == NULL)
674
		changeset->num_install++;
675
	else if (npkg != opkg || change->reinstall || change->new_repository_tag != change->old_repository_tag)
676
		changeset->num_adjust++;
677
}
678

679 680 681 682
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);

683
static void cset_track_deps_added(struct apk_package *pkg)
684 685 686
{
	struct apk_dependency *d;

687 688 689 690 691
	foreach_array_item(d, pkg->depends) {
		if (d->conflict || !d->name->ss.installed_name)
			continue;
		d->name->ss.installed_name->ss.requirers++;
	}
692 693 694 695 696 697 698 699
}

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) {
700
		if (d->conflict || !d->name->ss.installed_name)
701
			continue;
702
		if (--d->name->ss.installed_name->ss.requirers > 0)
703
			continue;
704
		pkg0 = d->name->ss.installed_pkg;
705 706 707 708 709 710 711 712 713
		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)
{
	if (pkg->name->ss.requirers == 0)
		cset_gen_name_remove(ss, pkg);
714 715
}

716
static void cset_check_install_by_iif(struct apk_solver_state *ss, struct apk_name *name)
717
{
718
	struct apk_package *pkg = name->ss.chosen.pkg;
719
	struct apk_dependency *dep0;
720

721
	if (pkg == NULL || !name->ss.seen || name->ss.in_changeset)
722 723
		return;

724
	foreach_array_item(dep0, pkg->install_if) {
725 726 727 728 729
		struct apk_name *name0 = dep0->name;
		if (!name0->ss.in_changeset)
			return;
		if (!apk_dep_is_provided(dep0, &name0->ss.chosen))
			return;
730
	}
731 732 733 734 735
	cset_gen_name_change(ss, name);
}

static void cset_check_removal_by_iif(struct apk_solver_state *ss, struct apk_name *name)
{
736
	struct apk_package *pkg = name->ss.installed_pkg;
737
	struct apk_dependency *dep0;
738

739
	if (pkg == NULL || name->ss.in_changeset || name->ss.chosen.pkg != NULL)
740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761
		return;

	foreach_array_item(dep0, pkg->install_if) {
		if (dep0->name->ss.in_changeset &&
		    dep0->name->ss.chosen.pkg == NULL) {
			cset_check_removal_by_deps(ss, pkg);
			return;
		}
	}
}

static void cset_gen_name_change(struct apk_solver_state *ss, struct apk_name *name)
{
	struct apk_name **pname;
	struct apk_package *pkg = name->ss.chosen.pkg, *opkg;
	struct apk_dependency *d;

	if (pkg == NULL || pkg->ss.in_changeset)
		return;

	pkg->ss.in_changeset = 1;
	pkg->name->ss.in_changeset = 1;
762 763
	foreach_array_item(d, pkg->provides)
		d->name->ss.in_changeset = 1;
764

765
	opkg = pkg->name->ss.installed_pkg;
766 767 768 769 770 771 772 773
	if (opkg) {
		foreach_array_item(pname, opkg->name->rinstall_if)
			cset_check_removal_by_iif(ss, *pname);
	}

	foreach_array_item(d, pkg->depends)
		cset_gen_dep(ss, pkg, d);

774
	dbg_printf("Selecting: "PKG_VER_FMT"%s\n", PKG_VER_PRINTF(pkg), pkg->ss.pkg_selectable ? "" : " [NOT SELECTABLE]");
775 776 777 778 779
	record_change(ss, opkg, pkg);

	foreach_array_item(pname, pkg->name->rinstall_if)
		cset_check_install_by_iif(ss, *pname);

780
	cset_track_deps_added(pkg);
781 782 783 784 785 786 787 788
	if (opkg)
		cset_track_deps_removed(ss, opkg);
}

static void cset_gen_name_remove(struct apk_solver_state *ss, struct apk_package *pkg)
{
	struct apk_name *name = pkg->name, **pname;

789 790 791
	if (pkg->ss.in_changeset ||
	    (name->ss.chosen.pkg != NULL &&
	     name->ss.chosen.pkg->name == name))
792 793 794
		return;

	name->ss.in_changeset = 1;
795
	pkg->ss.in_changeset = 1;
796 797 798 799
	foreach_array_item(pname, pkg->name->rinstall_if)
		cset_check_removal_by_iif(ss, *pname);
	record_change(ss, pkg, NULL);
	cset_track_deps_removed(ss, pkg);
800 801
}

802
static void cset_gen_dep(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep)
803
{
804
	struct apk_name *name = dep->name;
805
	struct apk_package *pkg = name->ss.chosen.pkg;
806

807
	if (!apk_dep_is_provided(dep, &name->ss.chosen))
808
		mark_error(ss, ppkg);
809

810
	cset_gen_name_change(ss, name);
811 812 813

	if (pkg && pkg->ss.error)
		mark_error(ss, ppkg);
814
}
815

816 817 818 819 820 821 822 823 824
static int cset_reset_name(apk_hash_item item, void *ctx)
{
	struct apk_name *name = (struct apk_name *) item;
	name->ss.installed_pkg = NULL;
	name->ss.installed_name = NULL;
	name->ss.requirers = 0;
	return 0;
}

825 826 827
static void generate_changeset(struct apk_solver_state *ss, struct apk_dependency_array *world)
{
	struct apk_changeset *changeset = ss->changeset;
828
	struct apk_package *pkg;
829
	struct apk_installed_package *ipkg;
830
	struct apk_dependency *d;
831

832 833
	apk_change_array_init(&changeset->changes);

834 835 836 837 838 839 840 841 842
	apk_hash_foreach(&ss->db->available.names, cset_reset_name, NULL);
	list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list) {
		pkg = ipkg->pkg;
		pkg->name->ss.installed_pkg = pkg;
		pkg->name->ss.installed_name = pkg->name;
		foreach_array_item(d, pkg->provides)
			if (d->version != &apk_null_blob)
				d->name