solver.c 22.2 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 15 16 17 18
#include "apk_defines.h"
#include "apk_database.h"
#include "apk_package.h"
#include "apk_solver.h"

19 20
#include "apk_print.h"

21 22 23
//#define DEBUG_PRINT

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

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

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

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

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

56 57
	foreach_array_item(p, name->providers) {
		struct apk_package *pkg = p->pkg;
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 81 82 83 84
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);
}

static void foreach_rinstall_if_pkg(
	struct apk_solver_state *ss, struct apk_package *pkg,
	void (*cb)(struct apk_solver_state *ss, struct apk_package *rinstall_if, struct apk_package *parent_pkg))
{
85 86 87
	struct apk_name *name = pkg->name, *name0, **pname0;
	struct apk_dependency *dep;
	struct apk_provider *p0;
88

89 90
	foreach_array_item(pname0, pkg->name->rinstall_if) {
		name0 = *pname0;
91
		dbg_printf(PKG_VER_FMT ": rinstall_if %s\n", PKG_VER_PRINTF(pkg), name0->name);
92 93 94 95 96
		foreach_array_item(p0, name0->providers) {
			foreach_array_item(dep, p0->pkg->install_if) {
				if (dep->name == name && apk_dep_is_provided(dep, p0)) {
					/* pkg depends (via install_if) on pkg0 */
					cb(ss, p0->pkg, pkg);
97
					break;
98
				}
99 100 101 102 103
			}
		}
	}
}

104 105 106 107 108 109 110 111
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++;
}

112
static void queue_dirty(struct apk_solver_state *ss, struct apk_name *name)
113
{
114 115 116
	if (list_hashed(&name->ss.dirty_list) || name->ss.locked ||
	    (name->ss.requirers == 0 && !name->ss.reevaluate_iif))
		return;
117

118 119
	dbg_printf("queue_dirty: %s\n", name->name);
	list_add_tail(&name->ss.dirty_list, &ss->dirty_head);
120 121
}

122
static void queue_unresolved(struct apk_solver_state *ss, struct apk_name *name)
123
{
124
	int want;
125

126 127
	if (name->ss.locked)
		return;
128

129 130 131 132 133 134
	want = (name->ss.requirers > 0) || (name->ss.has_iif);
	dbg_printf("queue_unresolved: %s, want=%d\n", name->name, want);
	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);
135 136
}

137
static void reevaluate_reverse_deps(struct apk_solver_state *ss, struct apk_name *name)
138
{
139 140 141 142 143 144 145 146 147
	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);
	}
148
}
149

150
static void reevaluate_reverse_installif(struct apk_solver_state *ss, struct apk_name *name)
151
{
152 153 154 155 156 157 158 159 160
	struct apk_name **pname0, *name0;

	foreach_array_item(pname0, name->rinstall_if) {
		name0 = *pname0;
		if (!name0->ss.seen)
			continue;
		name0->ss.reevaluate_iif = 1;
		queue_dirty(ss, name0);
	}
161 162
}

163
static void disqualify_package(struct apk_solver_state *ss, struct apk_package *pkg, const char *reason)
164
{
165
	struct apk_dependency *p;
166

167 168
	dbg_printf("disqualify_package: " PKG_VER_FMT " (%s)\n", PKG_VER_PRINTF(pkg), reason);
	pkg->ss.available = 0;
169 170 171 172
	reevaluate_reverse_deps(ss, pkg->name);
	foreach_array_item(p, pkg->provides)
		reevaluate_reverse_deps(ss, p->name);
	reevaluate_reverse_installif(ss, pkg->name);
173 174
}

175
static int dependency_satisfiable(struct apk_solver_state *ss, struct apk_dependency *dep)
176
{
177
	struct apk_name *name = dep->name;
178
	struct apk_provider *p;
179

180 181
	if (name->ss.locked)
		return apk_dep_is_provided(dep, &name->ss.chosen);
182

183 184
	if (name->ss.requirers == 0 && apk_dep_is_provided(dep, &provider_none))
		return TRUE;
185

186 187
	foreach_array_item(p, name->providers)
		if (p->pkg->ss.available && apk_dep_is_provided(dep, p))
188
			return TRUE;
189

190
	return FALSE;
191 192
}

193
static void discover_name(struct apk_solver_state *ss, struct apk_name *name)
194
{
195
	struct apk_database *db = ss->db;
196 197 198
	struct apk_name **pname0;
	struct apk_provider *p;
	struct apk_dependency *dep;
199
	unsigned int repos;
200

201 202
	if (name->ss.seen)
		return;
203

204
	name->ss.seen = 1;
205 206
	foreach_array_item(p, name->providers) {
		struct apk_package *pkg = p->pkg;
207
		if (pkg->ss.seen)
208
			continue;
209
		pkg->ss.seen = 1;
210 211 212 213 214 215 216 217
		pkg->ss.available = pkg->ipkg || (pkg->repos & db->available_repos);
		pkg->ss.pinning_allowed = APK_DEFAULT_PINNING_MASK;
		pkg->ss.pinning_preferred = APK_DEFAULT_PINNING_MASK;

		repos = get_pkg_repos(db, pkg);
		pkg->ss.tag_ok = !!(repos & ss->default_repos);
		pkg->ss.tag_preferred = !!(repos & ss->default_repos);

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

		dbg_printf("discover " PKG_VER_FMT ": tag_ok=%d, tag_pref=%d max_dep_chain=%d\n",
			PKG_VER_PRINTF(pkg),
			pkg->ss.tag_ok,
			pkg->ss.tag_preferred,
			pkg->ss.max_dep_chain);
230
	}
231 232
	foreach_array_item(pname0, name->rinstall_if)
		discover_name(ss, *pname0);
233 234
}

235
static void name_requirers_changed(struct apk_solver_state *ss, struct apk_name *name)
236
{
237
	queue_unresolved(ss, name);
238
	reevaluate_reverse_installif(ss, name);
239
	queue_dirty(ss, name);
240 241
}

242 243 244 245 246 247 248 249 250 251 252 253 254
static void inherit_pinning(struct apk_solver_state *ss, struct apk_package *pkg, unsigned int pinning, int prefer)
{
	unsigned int repo_mask = apk_db_get_pinning_mask_repos(ss->db, pinning);
	unsigned int repos = get_pkg_repos(ss->db, pkg);

	pkg->ss.pinning_allowed |= pinning;
	pkg->ss.tag_ok |= !!(repos & repo_mask);
	if (prefer) {
		pkg->ss.pinning_preferred |= pinning;
		pkg->ss.tag_preferred = !!(repos & apk_db_get_pinning_mask_repos(ss->db, pkg->ss.pinning_preferred));
	}
}

255
static void apply_constraint(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep)
256
{
257
	struct apk_name *name = dep->name;
258
	struct apk_provider *p0;
259
	unsigned int solver_flags_inherit = ss->solver_flags_inherit;
260
	int is_provided;
261

262 263 264 265 266 267 268 269
	dbg_printf("apply_constraint: %s%s%s" BLOB_FMT "\n",
		dep->conflict ? "!" : "",
		name->name,
		apk_version_op_string(dep->result_mask),
		BLOB_PRINTF(*dep->version));

	name->ss.requirers += !dep->conflict;
	name_requirers_changed(ss, name);
270

271
	foreach_array_item(p0, name->providers) {
272
		struct apk_package *pkg0 = p0->pkg;
273

274 275 276
		is_provided = apk_dep_is_provided(dep, p0);
		dbg_printf("apply_constraint: provider: %s-" BLOB_FMT ": %d\n",
			pkg0->name->name, BLOB_PRINTF(*p0->version), is_provided);
277

278 279 280
		pkg0->ss.conflicts += !is_provided;
		if (unlikely(pkg0->ss.available && pkg0->ss.conflicts))
			disqualify_package(ss, pkg0, "conflicting dependency");
281

282 283 284
		if (is_provided) {
			pkg0->ss.solver_flags |= solver_flags_inherit;
			pkg0->ss.solver_flags_inheritable |= solver_flags_inherit;
285 286 287 288 289 290
			inherit_pinning(ss, pkg0, ss->pinning_inherit, ss->prefer_pinning);

			dbg_printf(PKG_VER_FMT ": tag_ok=%d, tag_pref=%d\n",
				PKG_VER_PRINTF(pkg0),
				pkg0->ss.tag_ok,
				pkg0->ss.tag_preferred);
291
		}
292
	}
293 294
}

295
static void reconsider_name(struct apk_solver_state *ss, struct apk_name *name)
296
{
297 298
	struct apk_name *name0;
	struct apk_dependency *dep;
299 300 301
	struct apk_package *first_candidate = NULL;
	struct apk_provider *p;
	int reevaluate_deps, reevaluate_iif;
302
	int num_options = 0, num_tag_not_ok = 0, has_iif = 0;
303

304
	dbg_printf("reconsider_name: %s\n", name->name);
305

306 307
	reevaluate_deps = name->ss.reevaluate_deps;
	reevaluate_iif = name->ss.reevaluate_iif;
308
	name->ss.reevaluate_deps = 0;
309
	name->ss.reevaluate_iif = 0;
310

311 312
	/* propagate down by merging common dependencies and
	 * applying new constraints */
313 314
	foreach_array_item(p, name->providers) {
		struct apk_package *pkg = p->pkg;
315

316
		/* check if this pkg's dependencies have become unsatisfiable */
Timo Teräs's avatar
Timo Teräs committed
317
		pkg->ss.dependencies_merged = 0;
318 319 320
		if (reevaluate_deps) {
			if (!pkg->ss.available)
				continue;
321
			foreach_array_item(dep, pkg->depends) {
322 323 324 325 326 327 328 329
				if (!dependency_satisfiable(ss, dep)) {
					disqualify_package(ss, pkg, "dependency no longer satisfiable");
					break;
				}
			}
		}
		if (!pkg->ss.available)
			continue;
330

331
		if (reevaluate_iif) {
332 333 334 335
			pkg->ss.iif_triggered = 1;
			foreach_array_item(dep, pkg->install_if) {
				if (!dependency_satisfiable(ss, dep)) {
					pkg->ss.iif_triggered = 0;
336
					break;
337
				}
338 339 340
			}
			has_iif |= pkg->ss.iif_triggered;
		}
341

342 343
		if (name->ss.requirers == 0 && !pkg->ss.iif_triggered)
			continue;
344

345
		/* merge common dependencies */
Timo Teräs's avatar
Timo Teräs committed
346
		pkg->ss.dependencies_merged = 1;
347 348 349 350 351
		if (first_candidate == NULL)
			first_candidate = pkg;
		foreach_array_item(dep, pkg->depends) {
			/* FIXME: can merge also conflicts */
			if (dep->conflict)
352 353
				continue;
			name0 = dep->name;
354 355
			if (name0->ss.merge_index == num_options)
				name0->ss.merge_index = num_options + 1;
356
		}
357 358 359

		num_tag_not_ok += !pkg->ss.tag_ok;
		num_options++;
360
	}
361
	name->ss.has_options = (num_options > 1 || num_tag_not_ok > 0);
362 363 364
	name->ss.has_iif = has_iif;
	queue_unresolved(ss, name);

365 366 367 368
	if (first_candidate != NULL) {
		foreach_array_item(p, name->providers)
			p->pkg->ss.dependencies_used = p->pkg->ss.dependencies_merged;

369 370
		/* TODO: could merge versioning bits too */
		/* propagate down common dependencies */
371 372
		foreach_array_item(dep, first_candidate->depends) {
			if (dep->conflict)
373
				continue;
374
			name0 = dep->name;
375
			if (name0->ss.merge_index == num_options) {
376 377 378 379 380 381 382 383 384
				/* common dependency name with all */
				if (name0->ss.requirers == 0) {
					dbg_printf("%s common dependency: %s\n",
						   name->name, name0->name);
					name0->ss.requirers++;
					name_requirers_changed(ss, name0);
				}
			}
			name0->ss.merge_index = 0;
385 386
		}
	}
387 388
	dbg_printf("reconsider_name: %s [finished], has_options=%d\n",
		name->name, name->ss.has_options);
389 390
}

391 392
static int compare_providers(struct apk_solver_state *ss,
			     struct apk_provider *pA, struct apk_provider *pB)
393
{
394 395
	struct apk_database *db = ss->db;
	struct apk_package *pkgA = pA->pkg, *pkgB = pB->pkg;
396
	unsigned int solver_flags;
397
	int r;
398

399 400 401
	/* Prefer existing package */
	if (pkgA == NULL || pkgB == NULL)
		return (pkgA != NULL) - (pkgB != NULL);
402

403 404 405 406
	/* Prefer without errors */
	r = (int)pkgA->ss.available - (int)pkgB->ss.available;
	if (r)
		return r;
407

Timo Teräs's avatar
Timo Teräs committed
408 409
	/* Prefer those that were in last dependency merging group */
	r = (int)pkgA->ss.dependencies_used - (int)pkgB->ss.dependencies_used;
410 411 412
	if (r)
		return r;
	r = pkgB->ss.conflicts - pkgA->ss.conflicts;
Timo Teräs's avatar
Timo Teräs committed
413 414 415 416 417 418 419 420 421 422 423
	if (r)
		return r;

	/* Prefer installed on self-upgrade */
	solver_flags = pkgA->ss.solver_flags | pkgB->ss.solver_flags;
	if (db->performing_self_update && !(solver_flags & APK_SOLVERF_UPGRADE)) {
		r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
		if (r)
			return r;
	}

424 425 426 427 428
	/* Prefer allowed pinning */
	r = (int)pkgA->ss.tag_ok - (int)pkgB->ss.tag_ok;
	if (r)
		return r;

429
	/* Prefer available */
430
	if (solver_flags & APK_SOLVERF_AVAILABLE) {
431 432 433 434
		r = !!(pkgA->repos & db->available_repos) -
		    !!(pkgB->repos & db->available_repos);
		if (r)
			return r;
435 436
	}

437 438 439 440 441
	/* Prefer preferred pinning */
	r = (int)pkgA->ss.tag_preferred - (int)pkgB->ss.tag_preferred;
	if (r)
		return r;

442
	/* Prefer installed */
443
	if (!(solver_flags & APK_SOLVERF_UPGRADE)) {
444 445 446 447
		r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
		if (r)
			return r;
	}
448

449 450 451 452 453 454 455
	/* 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;
	}
456

457 458 459 460 461 462 463 464 465
	/* 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
466

467 468 469 470
	/* Prefer installed (matches here if upgrading) */
	r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
	if (r)
		return r;
471

472 473
	/* Prefer lowest available repository */
	return ffsl(pkgB->repos) - ffsl(pkgA->repos);
474
}
475

476 477 478 479 480 481
static void inherit_pinning_from_pkg(struct apk_solver_state *ss, struct apk_package *rinstall_if, struct apk_package *parent_pkg)
{
	inherit_pinning(ss, rinstall_if, parent_pkg->ss.pinning_allowed, 0);
}

static void assign_name(struct apk_solver_state *ss, struct apk_name *name, struct apk_provider p)
482
{
483
	struct apk_provider *p0;
484 485 486 487 488 489

	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;
490 491 492
		/* Conflict: providing same name */
		mark_error(ss, p.pkg);
		mark_error(ss, name->ss.chosen.pkg);
493
		return;
494
	}
495

496 497
	if (p.pkg)
		dbg_printf("assign %s to "PKG_VER_FMT"\n", name->name, PKG_VER_PRINTF(p.pkg));
498

499 500 501 502 503 504 505
	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);

506 507 508 509
	/* propagate pinning to install_if candidates */
	if (p.pkg)
		foreach_rinstall_if_pkg(ss, p.pkg, inherit_pinning_from_pkg);

510
	/* disqualify all conflicting packages */
511 512
	foreach_array_item(p0, name->providers) {
		if (p0->pkg == p.pkg)
513 514
			continue;
		if (p.version == &apk_null_blob &&
515
		    p0->version == &apk_null_blob)
516
			continue;
517
		disqualify_package(ss, p0->pkg, "conflicting provides");
518
	}
519
	reevaluate_reverse_deps(ss, name);
520 521
}

522
static void select_package(struct apk_solver_state *ss, struct apk_name *name)
523
{
524
	struct apk_provider chosen = { NULL, &apk_null_blob }, *p;
525
	struct apk_package *pkg = NULL;
526
	struct apk_dependency *d;
527

528
	dbg_printf("select_package: %s\n", name->name);
529

530
	if (name->ss.requirers || name->ss.has_iif) {
531
		foreach_array_item(p, name->providers) {
532
			if (name->ss.requirers == 0 &&
533 534
			    (!p->pkg->ss.iif_triggered ||
			     !p->pkg->ss.tag_ok))
535
				continue;
536 537
			if (compare_providers(ss, p, &chosen) > 0)
				chosen = *p;
538
		}
539
	}
540

541 542 543 544 545
	pkg = chosen.pkg;
	if (pkg) {
		if (chosen.version == &apk_null_blob) {
			/* Pure virtual package */
			assign_name(ss, name, provider_none);
546
			ss->errors += (name->ss.requirers > 0);
547 548
			return;
		}
549 550 551 552
		if (!pkg->ss.available || !pkg->ss.tag_ok) {
			/* Selecting broken or unallowed package */
			mark_error(ss, pkg);
		}
553
		dbg_printf("selecting: " PKG_VER_FMT ", available: %d\n", PKG_VER_PRINTF(pkg), pkg->ss.available);
554

555
		assign_name(ss, pkg->name, APK_PROVIDER_FROM_PACKAGE(pkg));
556 557 558
		foreach_array_item(d, pkg->provides)
			assign_name(ss, d->name, APK_PROVIDER_FROM_PROVIDES(pkg, d));

559
		ss->solver_flags_inherit = pkg->ss.solver_flags_inheritable;
560
		ss->pinning_inherit = pkg->ss.pinning_allowed;
561 562
		foreach_array_item(d, pkg->depends)
			apply_constraint(ss, pkg, d);
563
		ss->solver_flags_inherit = 0;
564
		ss->pinning_inherit = 0;
565

566 567 568 569
		ss->num_selections++;
	} else {
		dbg_printf("selecting: %s [unassigned]\n", name->name);
		assign_name(ss, name, provider_none);
570
		ss->errors += (name->ss.requirers > 0);
571
	}
572 573
}

574
static void generate_change_dep(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep);
575 576 577
static void generate_change_iif(struct apk_solver_state *ss, struct apk_name *name);

static void generate_change(struct apk_solver_state *ss, struct apk_name *name)
578
{
579
	struct apk_name **pname;
580 581 582
	struct apk_package *pkg = name->ss.chosen.pkg, *opkg;
	struct apk_changeset *changeset = ss->changeset;
	struct apk_change *change;
583
	struct apk_dependency *d;
584 585 586

	if (pkg == NULL)
		return;
587

588
	if (pkg->ss.in_changeset)
589
		return;
590 591 592
	pkg->ss.in_changeset = 1;
	pkg->name->ss.in_changeset = 1;

593 594
	foreach_array_item(d, pkg->depends)
		generate_change_dep(ss, pkg, d);
595 596 597 598 599 600 601 602

	change = &changeset->changes->item[ss->num_solution_entries++];
	dbg_printf("Selecting: "PKG_VER_FMT"%s\n", PKG_VER_PRINTF(pkg), pkg->ss.available ? "" : " [NOT AVAILABLE]");
	opkg = apk_pkg_get_installed(pkg->name);
	*change = (struct apk_change) {
		.old_pkg = opkg,
		.old_repository_tag = opkg ? opkg->ipkg->repository_tag : 0,
		.new_pkg = pkg,
603
		.new_repository_tag = get_tag(ss->db, pkg->ss.pinning_allowed, get_pkg_repos(ss->db, pkg)),
604
		.reinstall = !!(pkg->ss.solver_flags & APK_SOLVERF_REINSTALL),
605 606 607 608 609 610 611 612
	};
	if (change->new_pkg == NULL)
		changeset->num_remove++;
	else if (change->old_pkg == NULL)
		changeset->num_install++;
	else if (change->new_pkg != change->old_pkg || change->reinstall ||
		 change->new_repository_tag != change->old_repository_tag)
		changeset->num_adjust++;
613

614 615
	foreach_array_item(pname, pkg->name->rinstall_if)
		generate_change_iif(ss, *pname);
616 617
}

618
static void generate_change_iif(struct apk_solver_state *ss, struct apk_name *name)
619
{
620
	struct apk_package *pkg = name->ss.chosen.pkg;
621
	struct apk_dependency *dep0;
622

623
	if (pkg == NULL || !name->ss.seen)
624 625
		return;

626
	foreach_array_item(dep0, pkg->install_if) {
627 628 629 630 631
		struct apk_name *name0 = dep0->name;
		if (!name0->ss.in_changeset)
			return;
		if (!apk_dep_is_provided(dep0, &name0->ss.chosen))
			return;
632 633
	}

634
	generate_change(ss, name);
635 636
}

637
static void generate_change_dep(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep)
638
{
639
	struct apk_name *name = dep->name;
640
	struct apk_package *pkg = name->ss.chosen.pkg;
641

642
	if (!apk_dep_is_provided(dep, &name->ss.chosen))
643
		mark_error(ss, ppkg);
644

645
	generate_change(ss, name);
646 647 648

	if (pkg && pkg->ss.error)
		mark_error(ss, ppkg);
649
}
650

651 652 653 654
static void generate_changeset(struct apk_solver_state *ss, struct apk_dependency_array *world)
{
	struct apk_changeset *changeset = ss->changeset;
	struct apk_installed_package *ipkg;
655
	struct apk_dependency *d;
656

657 658 659 660 661
	list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list) {
		struct apk_name *name = ipkg->pkg->name;
		if (name->ss.chosen.pkg == NULL && !name->ss.locked)
			ss->num_selections++;
	}
Timo Teräs's avatar
Timo Teräs committed
662

663
	apk_change_array_resize(&ss->changeset->changes, ss->num_selections);
664 665
	foreach_array_item(d, world)
		generate_change_dep(ss, NULL, d);
666

667 668 669 670 671 672 673 674 675 676
	/* FIXME: could order better the removals of unneeded packages */
	list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list) {
		struct apk_name *name = ipkg->pkg->name;
		if (name->ss.chosen.pkg == NULL && !name->ss.in_changeset) {
			struct apk_change *change = &changeset->changes->item[ss->num_solution_entries++];
			*change = (struct apk_change) {
				.old_pkg = ipkg->pkg,
				.new_pkg = NULL,
			};
			changeset->num_remove++;
677 678 679
		}
	}

680
	changeset->num_total_changes = changeset->num_install + changeset->num_remove + changeset->num_adjust;
681

682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700
#if 1
	/* FIXME: calculate num_solution_entries correctly */
	ASSERT(ss->num_solution_entries <= changeset->changes->num,
		"Got %d changes, but expected %d\n",
		ss->num_solution_entries, changeset->changes->num);
	apk_change_array_resize(&ss->changeset->changes, ss->num_solution_entries);
#else
	ASSERT(ss->num_solution_entries == changeset->changes->num,
		"Got %d changes, but expected %d\n",
		ss->num_solution_entries, changeset->changes->num);
#endif
}

static int free_state(apk_hash_item item, void *ctx)
{
	struct apk_name *name = (struct apk_name *) item;
	memset(&name->ss, 0, sizeof(name->ss));
	return 0;
}
Timo Teräs's avatar
Timo Teräs committed
701

702 703 704 705 706
static int free_package(apk_hash_item item, void *ctx)
{
	struct apk_package *pkg = (struct apk_package *) item;
	memset(&pkg->ss, 0, sizeof(pkg->ss));
	return 0;
707 708
}

709 710 711 712
int apk_solver_solve(struct apk_database *db,
		     unsigned short solver_flags,
		     struct apk_dependency_array *world,
		     struct apk_changeset *changeset)
713
{
714
	struct apk_name *name, *name0;
715
	struct apk_package *pkg;
716
	struct apk_solver_state ss_data, *ss = &ss_data;
717
	struct apk_dependency *d;
718

719
restart:
720 721 722
	memset(ss, 0, sizeof(*ss));
	ss->db = db;
	ss->changeset = changeset;
723
	ss->default_repos = apk_db_get_pinning_mask_repos(db, APK_DEFAULT_PINNING_MASK);
724 725
	list_init(&ss->dirty_head);
	list_init(&ss->unresolved_head);
726

727
	dbg_printf("applying world\n");
728
	ss->prefer_pinning = 1;
729
	ss->solver_flags_inherit = solver_flags;
730 731
	foreach_array_item(d, world) {
		if (d->broken)
732
			continue;
733
		name = d->name;
734
		name->ss.in_world_dependency = 1;
735 736 737
		discover_name(ss, d->name);
		ss->pinning_inherit = BIT(d->repository_tag);
		apply_constraint(ss, NULL, d);
738
	}
739
	ss->solver_flags_inherit = 0;
740 741
	ss->pinning_inherit = 0;
	ss->prefer_pinning = 0;
742
	dbg_printf("applying world [finished]\n");
743

744
	do {
745 746 747
		while (!list_empty(&ss->dirty_head)) {
			name = list_pop(&ss->dirty_head, struct apk_name, ss.dirty_list);
			reconsider_name(ss, name);
748
		}
749

750 751
		name = NULL;
		list_for_each_entry(name0, &ss->unresolved_head, ss.unresolved_list) {
752
			if ((!name0->ss.has_options) && name0->ss.requirers > 0) {
753
				name = name0;
754
				break;
755 756 757
			}
			if (name == NULL)
				goto prefer;
758
			if (name0->ss.requirers == 0 && name->ss.requirers > 0)
Timo Teräs's avatar
Timo Teräs committed
759
				continue;
760
			if (name0->ss.requirers > 0 && name->ss.requirers == 0)
761
				goto prefer;
762 763
			if (name0->ss.max_dep_chain < name->ss.max_dep_chain)
				continue;
764 765
		prefer:
			name = name0;
766
		}
767 768
		if (name == NULL)
			break;
769

770 771
		select_package(ss, name);
	} while (1);
772

773
	generate_changeset(ss, world);
774

775
	if (ss->errors && (apk_flags & APK_FORCE)) {
776 777 778
		foreach_array_item(d, world) {
			name = d->name;
			pkg = name->ss.chosen.pkg;
779
			if (pkg == NULL || pkg->ss.error) {
780
				d->broken = 1;
781 782 783 784 785 786 787 788
				dbg_printf("disabling broken world dep: %s", name->name);
			}
		}
		apk_hash_foreach(&db->available.names, free_state, NULL);
		apk_hash_foreach(&db->available.packages, free_package, NULL);
		goto restart;
	}

789 790 791
	apk_hash_foreach(&db->available.names, free_state, NULL);
	apk_hash_foreach(&db->available.packages, free_package, NULL);
	dbg_printf("solver done, errors=%d\n", ss->errors);
792

793
	return ss->errors;
794
}