solver.c 21.5 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
/* solver.c - Alpine Package Keeper (APK)
 * A backtracking, forward checking dependency graph solver.
 *
 * Copyright (C) 2011 Timo Teräs <timo.teras@iki.fi>
 * 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.
 */

#include <stdlib.h>
#include "apk_defines.h"
#include "apk_database.h"
#include "apk_package.h"
#include "apk_solver.h"

#if 0
#include <stdio.h>
#define dbg_printf(args...) fprintf(stderr, args)
#else
#define dbg_printf(args...)
#endif

#define APK_PKGSTF_NOINSTALL		0
#define APK_PKGSTF_INSTALL		1
#define APK_PKGSTF_BRANCH		2
#define APK_PKGSTF_ALT_BRANCH		4
29
#define APK_PKGSTF_INSTALLIF		8
30
#define APK_PKGSTF_DECIDED		16
31 32 33

struct apk_package_state {
	struct apk_package *backtrack;
34
	unsigned int topology_hard, topology_soft;
35 36
	unsigned short flags;
	unsigned short conflicts;
37
	unsigned short cur_unsatisfiable;
38 39
};

40
#define APK_NAMESTF_AVAILABILITY_CHECKED	1
41 42
#define APK_NAMESTF_LOCKED			2
#define APK_NAMESTF_NO_OPTIONS			4
43 44 45
struct apk_name_state {
	struct list_head unsolved_list;
	struct apk_package *chosen;
46
	unsigned short flags;
47
	unsigned short requirers;
48
	unsigned short install_ifs;
49 50 51 52 53
};

struct apk_solver_state {
	struct apk_database *db;
	struct apk_name_state *name_state;
54 55
	unsigned num_topology_positions;

56 57 58 59
	struct list_head unsolved_list_head;
	struct apk_package *latest_decision;
	unsigned int topology_position;
	unsigned int assigned_names;
60 61
	unsigned short cur_unsatisfiable;
	unsigned short allow_errors;
62 63

	struct apk_package_array *best_solution;
64
	unsigned short best_unsatisfiable;
65 66
};

67 68 69 70
static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep);
static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *dep);
static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
			  int flags);
71

72 73 74 75 76
static inline struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
{
	return (struct apk_package_state*) pkg->state_ptr;
}

77 78 79 80 81 82 83 84 85 86 87
static inline int pkg_available(struct apk_database *db, struct apk_package *pkg)
{
	if (pkg->installed_size == 0)
		return TRUE;
	if (pkg->filename != NULL)
		return TRUE;
	if (apk_db_select_repo(db, pkg) != NULL)
		return TRUE;
	return FALSE;
}

88 89 90
static void foreach_dependency_pkg(
	struct apk_solver_state *ss, struct apk_dependency_array *depends,
	void (*cb)(struct apk_solver_state *ss, struct apk_package *dependency))
91 92 93
{
	int i, j;

94 95 96
	/* And sort the main dependencies */
	for (i = 0; i < depends->num; i++) {
		struct apk_dependency *dep = &depends->item[i];
97 98 99 100
		struct apk_name *name0 = dep->name;

		for (j = 0; j < name0->pkgs->num; j++) {
			struct apk_package *pkg0 = name0->pkgs->item[j];
101

102 103 104 105
			/* conflict depends on all to be not installed */
			if (dep->result_mask != APK_DEPMASK_CONFLICT &&
			    !apk_dep_is_satisfied(dep, pkg0))
				continue;
106 107

			cb(ss, pkg0);
108 109
		}
	}
110
}
111

112 113 114 115 116 117 118 119 120 121 122 123
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_name *name = pkg->name;
	int i, j, k;

	for (i = 0; i < pkg->name->rinstall_if->num; i++) {
		struct apk_name *name0 = pkg->name->rinstall_if->item[i];

		dbg_printf(PKG_VER_FMT ": rinstall_if %s\n",
			   PKG_VER_PRINTF(pkg), name0->name);
124

125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181
		for (j = 0; j < name0->pkgs->num; j++) {
			struct apk_package *pkg0 = name0->pkgs->item[j];

			for (k = 0; k < pkg0->install_if->num; k++) {
				struct apk_dependency *dep = &pkg0->install_if->item[k];
				if (dep->name == name &&
				    (dep->result_mask == APK_DEPMASK_CONFLICT ||
				     apk_dep_is_satisfied(dep, pkg)))
					break;
			}
			if (k >= pkg0->install_if->num)
				continue;

			/* pkg depends (via install_if) on pkg0 */
			cb(ss, pkg0);
		}
	}
}

static void sort_hard_dependencies(struct apk_solver_state *ss, struct apk_package *pkg)
{
	struct apk_package_state *ps;

	if (pkg->state_ptr == NULL)
		pkg->state_ptr = calloc(1, sizeof(struct apk_package_state));

	ps = pkg_to_ps(pkg);
	if (ps->topology_hard)
		return;

	/* Consider hard dependencies only */
	foreach_dependency_pkg(ss, pkg->depends, sort_hard_dependencies);
	foreach_dependency_pkg(ss, pkg->install_if, sort_hard_dependencies);

	ps->topology_soft = ps->topology_hard = ++ss->num_topology_positions;
	dbg_printf(PKG_VER_FMT ": topology_hard=%d\n",
		   PKG_VER_PRINTF(pkg), ps->topology_hard);
}

static void sort_soft_dependencies(struct apk_solver_state *ss, struct apk_package *pkg)
{
	struct apk_package_state *ps;

	sort_hard_dependencies(ss, pkg);

	ps = pkg_to_ps(pkg);
	if (ps->topology_soft != ps->topology_hard)
		return;

	/* Soft reverse dependencies aka. install_if */
	foreach_rinstall_if_pkg(ss, pkg, sort_hard_dependencies);
	foreach_dependency_pkg(ss, pkg->depends, sort_soft_dependencies);

	/* Assign a topology sorting order */
	ps->topology_soft = ++ss->num_topology_positions;
	dbg_printf(PKG_VER_FMT ": topology_soft=%d\n",
		   PKG_VER_PRINTF(pkg), ps->topology_soft);
182 183 184 185 186 187 188
}

static void sort_name(struct apk_solver_state *ss, struct apk_name *name)
{
	int i;

	for (i = 0; i < name->pkgs->num; i++)
189
		sort_soft_dependencies(ss, name->pkgs->item[i]);
190 191
}

192 193 194 195 196 197 198 199 200 201
static void prepare_name(struct apk_solver_state *ss, struct apk_name *name,
			 struct apk_name_state *ns)
{
	int i;

	if (ns->flags & APK_NAMESTF_AVAILABILITY_CHECKED)
		return;

	for (i = 0; i < name->pkgs->num; i++) {
		struct apk_package *pkg = name->pkgs->item[i];
202
		struct apk_package_state *ps = pkg_to_ps(pkg);
203 204 205 206 207 208 209 210 211 212 213 214

		/* if package is needed for (re-)install */
		if ((name->flags & APK_NAME_REINSTALL) || (pkg->ipkg == NULL)) {
			/* and it's not available, we can't use it */
			if (!pkg_available(ss->db, pkg))
				ps->conflicts++;
		}
	}

	ns->flags |= APK_NAMESTF_AVAILABILITY_CHECKED;
}

215 216
static void foreach_dependency(struct apk_solver_state *ss, struct apk_dependency_array *deps,
			       void (*func)(struct apk_solver_state *ss, struct apk_dependency *dep))
217
{
218
	int i;
219
	for (i = 0; i < deps->num; i++)
220
		func(ss, &deps->item[i]);
221 222
}

223
static int get_pkg_expansion_flags(struct apk_solver_state *ss, struct apk_package *pkg)
224 225
{
	struct apk_name *name = pkg->name;
226
	int i, options = 0;
227 228 229

	/* check if the suggested package is the most preferred one of
	 * available packages for the name */
230
	for (i = 0; i < name->pkgs->num; i++) {
231
		struct apk_package *pkg0 = name->pkgs->item[i];
232
		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
233

234 235 236 237
		if (pkg0 == pkg || ps0 == NULL ||
		    ps0->topology_hard > ss->topology_position ||
		    (ps0->flags & APK_PKGSTF_DECIDED) ||
		    ps0->conflicts != 0)
238 239
			continue;

240 241 242
		if (apk_flags & APK_PREFER_AVAILABLE) {
			/* pkg available, pkg0 not */
			if (pkg->repos != 0 && pkg0->repos == 0)
243
				continue;
244 245
			/* pkg0 available, pkg not */
			if (pkg0->repos != 0 && pkg->repos == 0)
246
				return APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH;
247 248
		}

249 250
		if (!(apk_flags & APK_UPGRADE)) {
			/* not upgrading, prefer the installed package */
251 252
			if (pkg->ipkg == NULL && pkg0->ipkg != NULL)
				return APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH;
253 254 255 256
		}

		/* upgrading, or neither of the package is installed, so
		 * we just fall back comparing to versions */
257
		options++;
258
		if (apk_pkg_version_compare(pkg0, pkg) == APK_VERSION_GREATER)
259
			return APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH;
260 261
	}

262
	/* no package greater than the selected */
263 264 265 266 267
	if (options)
		return APK_PKGSTF_INSTALL | APK_PKGSTF_BRANCH;

	/* no other choice */
	return APK_PKGSTF_INSTALL;
268 269
}

270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286
static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg)
{
	struct apk_name_state *ns = &ss->name_state[pkg->name->id];
	int i, missing = 0;

	for (i = 0; i < pkg->install_if->num; i++) {
		struct apk_dependency *dep = &pkg->install_if->item[i];

		ns = &ss->name_state[dep->name->id];
		if (!(ns->flags & APK_NAMESTF_LOCKED) ||
		    !apk_dep_is_satisfied(dep, ns->chosen))
			missing++;
	}

	return missing;
}

287
static int update_name_state(struct apk_solver_state *ss,
288 289
			     struct apk_name *name, struct apk_name_state *ns,
			     int requirers_adjustment)
290
{
291 292
	struct apk_package *best_pkg = NULL;
	unsigned int best_topology = 0;
293
	int i, options = 0, skipped_options = 0;
294

295 296
	ns->requirers += requirers_adjustment;

297 298
	for (i = 0; i < name->pkgs->num; i++) {
		struct apk_package *pkg0 = name->pkgs->item[i];
299
		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
300

301 302 303
		if (ps0 == NULL ||
		    ps0->topology_hard >= ss->topology_position ||
		    (ps0->flags & APK_PKGSTF_DECIDED))
304 305
			continue;

306 307 308 309 310 311
		if (ns->requirers == 0 && ns->install_ifs != 0 &&
		    install_if_missing(ss, pkg0)) {
			skipped_options++;
			continue;
		}

312
		options++;
313 314 315 316 317
		if (ps0->topology_soft < ss->topology_position &&
		    ps0->topology_soft > best_topology)
			best_pkg = pkg0, best_topology = ps0->topology_soft;
		else if (ps0->topology_hard > best_topology)
			best_pkg = pkg0, best_topology = ps0->topology_hard;
318
	}
319

320
	if (options == 0 && skipped_options == 0) {
321 322
		if (!(ns->flags & APK_NAMESTF_NO_OPTIONS)) {
			ss->cur_unsatisfiable += ns->requirers;
323 324
			if (ns->install_ifs)
				ss->cur_unsatisfiable++;
325 326 327 328 329 330 331
			ns->flags |= APK_NAMESTF_NO_OPTIONS;
		} else if (requirers_adjustment > 0) {
			ss->cur_unsatisfiable += requirers_adjustment;
		}
	} else
		ns->flags &= ~APK_NAMESTF_NO_OPTIONS;

332 333
	if ((options == 0 && skipped_options == 0) ||
	    (ns->requirers == 0 && ns->install_ifs == 0)) {
334 335 336 337 338
		if (list_hashed(&ns->unsolved_list)) {
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
			ns->chosen = NULL;
		}
339 340
		dbg_printf("%s: deleted from unsolved: %d requirers, %d install_ifs, %d options, %d skipped\n",
			   name->name, ns->requirers, ns->install_ifs, options, skipped_options);
341
	} else {
342 343 344
		dbg_printf("%s: added to unsolved: %d requirers, %d install_ifs, %d options (next topology %d)\n",
			   name->name, ns->requirers, ns->install_ifs, options,
			   best_topology);
345 346
		if (!list_hashed(&ns->unsolved_list))
			list_add(&ns->unsolved_list, &ss->unsolved_list_head);
347
		ns->chosen = best_pkg;
348 349
	}

350
	return options + skipped_options;
351 352
}

353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378
static void trigger_install_if(struct apk_solver_state *ss,
			       struct apk_package *pkg)
{
	if (install_if_missing(ss, pkg) == 0) {
		struct apk_name_state *ns = ns = &ss->name_state[pkg->name->id];

		dbg_printf("trigger_install_if: " PKG_VER_FMT " triggered\n",
			   PKG_VER_PRINTF(pkg));
		ns->install_ifs++;
		update_name_state(ss, pkg->name, ns, 0);
	}
}

static void untrigger_install_if(struct apk_solver_state *ss,
			       struct apk_package *pkg)
{
	if (install_if_missing(ss, pkg) != 1) {
		struct apk_name_state *ns = ns = &ss->name_state[pkg->name->id];

		dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n",
			   PKG_VER_PRINTF(pkg));
		ns->install_ifs--;
		update_name_state(ss, pkg->name, ns, 0);
	}
}

379 380 381
static void apply_decision(struct apk_solver_state *ss,
			   struct apk_package *pkg,
			   struct apk_package_state *ps)
382 383 384 385 386 387 388 389
{
	struct apk_name_state *ns = &ss->name_state[pkg->name->id];

	dbg_printf("apply_decision: " PKG_VER_FMT " %s\n", PKG_VER_PRINTF(pkg),
		   (ps->flags & APK_PKGSTF_INSTALL) ? "INSTALL" : "NO_INSTALL");

	if (ps->flags & APK_PKGSTF_INSTALL) {
		ss->assigned_names++;
390
		ss->cur_unsatisfiable += ps->conflicts;
391
		ns->chosen = pkg;
392 393 394 395 396 397 398 399
		ns->flags |= APK_NAMESTF_LOCKED;

		list_del(&ns->unsolved_list);
		list_init(&ns->unsolved_list);
		dbg_printf("%s: deleting from unsolved list\n",
			   pkg->name->name);

		foreach_dependency(ss, pkg->depends, apply_constraint);
400
		foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
401
	} else {
402
		update_name_state(ss, pkg->name, ns, 0);
403 404 405 406 407 408 409 410 411 412 413 414
	}
}

static void undo_decision(struct apk_solver_state *ss,
			  struct apk_package *pkg,
			  struct apk_package_state *ps)
{
	struct apk_name_state *ns = &ss->name_state[pkg->name->id];

	dbg_printf("undo_decision: " PKG_VER_FMT " %s\n", PKG_VER_PRINTF(pkg),
		   (ps->flags & APK_PKGSTF_INSTALL) ? "INSTALL" : "NO_INSTALL");

415 416 417 418
	if (ps->flags & APK_PKGSTF_INSTALLIF)
		ss->topology_position = ps->topology_soft;
	else
		ss->topology_position = ps->topology_hard;
419

420 421
	if (ps->flags & APK_PKGSTF_INSTALL) {
		ss->assigned_names--;
422 423

		foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
424 425
		foreach_dependency(ss, pkg->depends, undo_constraint);

426 427
		ns->flags &= ~APK_NAMESTF_LOCKED;
		ns->chosen = NULL;
428
	}
429

430
	ss->cur_unsatisfiable = ps->cur_unsatisfiable;
431
	update_name_state(ss, pkg->name, ns, 0);
432 433
}

434 435
static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
			  int flags)
436
{
437
	struct apk_package_state *ps = pkg_to_ps(pkg);
438 439

	ps->backtrack = ss->latest_decision;
440
	ps->flags = flags | APK_PKGSTF_DECIDED;
441
	ps->cur_unsatisfiable = ss->cur_unsatisfiable;
442 443 444 445 446 447 448 449 450

	if (ps->topology_soft < ss->topology_position) {
		if (flags & APK_PKGSTF_INSTALL)
			ps->flags |= APK_PKGSTF_INSTALLIF;
		ss->topology_position = ps->topology_soft;
	} else {
		ps->flags &= ~APK_PKGSTF_INSTALLIF;
		ss->topology_position = ps->topology_hard;
	}
451
	ss->latest_decision = pkg;
452

453 454 455 456 457 458
	if (flags & APK_PKGSTF_BRANCH) {
		dbg_printf("push_decision: adding new BRANCH at topology_position %d\n",
			   ss->topology_position);
	} else
		ps->flags |= APK_PKGSTF_ALT_BRANCH;

459 460 461 462
	if (ps->flags & APK_PKGSTF_INSTALLIF)
		dbg_printf("triggers due to " PKG_VER_FMT "\n",
			   PKG_VER_PRINTF(pkg));

463
	apply_decision(ss, pkg, ps);
464 465 466 467 468 469 470
}

static int next_branch(struct apk_solver_state *ss)
{
	struct apk_package *pkg;
	struct apk_package_state *ps;

471
	while (ss->latest_decision != NULL) {
472
		pkg = ss->latest_decision;
473
		ps = pkg_to_ps(pkg);
474 475 476 477 478
		undo_decision(ss, pkg, ps);

		if (ps->flags & APK_PKGSTF_ALT_BRANCH) {
			dbg_printf("next_branch: undo decision at topology_position %d\n",
				   ss->topology_position);
479 480
			ps->flags &= ~(APK_PKGSTF_ALT_BRANCH | APK_PKGSTF_DECIDED);
			ss->latest_decision = ps->backtrack;
481 482 483 484 485 486 487
		} else {
			dbg_printf("next_branch: swapping BRANCH at topology_position %d\n",
				   ss->topology_position);

			ps->flags |= APK_PKGSTF_ALT_BRANCH;
			ps->flags ^= APK_PKGSTF_INSTALL;

488 489
			apply_decision(ss, pkg, ps);
			return 0;
490 491
		}
	}
492 493 494

	dbg_printf("next_branch: no more branches\n");
	return 1;
495 496
}

497
static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
498 499 500
{
	struct apk_name *name = dep->name;
	struct apk_name_state *ns = &ss->name_state[name->id];
501
	int i;
502

503
	prepare_name(ss, name, ns);
504 505 506 507 508

	if (ns->flags & APK_NAMESTF_LOCKED) {
		dbg_printf(PKG_VER_FMT " selected already for %s\n",
			   PKG_VER_PRINTF(ns->chosen), dep->name->name);
		if (!apk_dep_is_satisfied(dep, ns->chosen))
509
			ss->cur_unsatisfiable++;
510 511 512
		return;
	}

513 514
	for (i = 0; i < name->pkgs->num; i++) {
		struct apk_package *pkg0 = name->pkgs->item[i];
515
		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
516

517
		if (ps0 == NULL ||
518
		    ps0->topology_hard >= ss->topology_position)
519 520 521 522 523 524 525 526 527 528
			continue;

		if (!apk_dep_is_satisfied(dep, pkg0)) {
			ps0->conflicts++;
			dbg_printf(PKG_VER_FMT ": conflicts++ -> %d\n",
				   PKG_VER_PRINTF(pkg0),
				   ps0->conflicts);
		}
	}

529 530
	update_name_state(ss, name, ns,
			  (dep->result_mask != APK_DEPMASK_CONFLICT) ? 1 : 0);
531 532
}

533
static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
534 535 536
{
	struct apk_name *name = dep->name;
	struct apk_name_state *ns = &ss->name_state[name->id];
537 538 539 540 541 542 543
	int i;

	if (ns->flags & APK_NAMESTF_LOCKED) {
		dbg_printf(PKG_VER_FMT " selected already for %s\n",
			   PKG_VER_PRINTF(ns->chosen), dep->name->name);
		return;
	}
544 545 546

	for (i = 0; i < name->pkgs->num; i++) {
		struct apk_package *pkg0 = name->pkgs->item[i];
547
		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
548

549
		if (ps0->topology_hard >= ss->topology_position)
550 551 552 553 554 555 556 557 558 559
			continue;

		if (!apk_dep_is_satisfied(dep, pkg0)) {
			ps0->conflicts--;
			dbg_printf(PKG_VER_FMT ": conflicts-- -> %d\n",
				   PKG_VER_PRINTF(pkg0),
				   ps0->conflicts);
		}
	}

560 561
	update_name_state(ss, name, ns,
		(dep->result_mask != APK_DEPMASK_CONFLICT) ? -1 : 0);
562 563 564 565
}

static int expand_branch(struct apk_solver_state *ss)
{
566 567
	struct apk_name_state *ns;
	struct apk_package *pkg0 = NULL;
568
	unsigned int topology0 = 0;
569 570 571

	/* FIXME: change unsolved_list to a priority queue */
	list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
572 573 574 575 576 577 578 579 580 581 582
		/* ns->chosen can be NULL if the name has only install_if
		 * requirers that got later conflicted, but it still has
		 * other options that can get activated later due to more
		 * complicated install_if rules in some other package. */
		if (ns->chosen == NULL)
			continue;
		if (pkg_to_ps(ns->chosen)->topology_soft < ss->topology_position &&
		    pkg_to_ps(ns->chosen)->topology_soft > topology0)
			pkg0 = ns->chosen, topology0 = pkg_to_ps(pkg0)->topology_soft;
		else if (pkg_to_ps(ns->chosen)->topology_hard > topology0)
			pkg0 = ns->chosen, topology0 = pkg_to_ps(pkg0)->topology_hard;
583 584 585 586 587 588
	}
	if (pkg0 == NULL) {
		dbg_printf("expand_branch: list is empty (%d unsatisfied)\n",
			   ss->cur_unsatisfiable);
		return 1;
	}
589

590 591 592
	/* someone needs to provide this name -- find next eligible
	 * provider candidate */
	ns = &ss->name_state[pkg0->name->id];
593
	dbg_printf("expand_branch: %s\n", pkg0->name->name);
594

595
	push_decision(ss, pkg0, get_pkg_expansion_flags(ss, pkg0));
596 597 598 599 600 601 602 603 604 605 606 607 608 609 610

	return 0;
}

static void record_solution(struct apk_solver_state *ss)
{
	struct apk_package *pkg;
	struct apk_package_state *ps;
	int i;

	apk_package_array_resize(&ss->best_solution, ss->assigned_names);

	i = 0;
	pkg = ss->latest_decision;
	while (pkg != NULL) {
611
		ps = pkg_to_ps(pkg);
612 613 614
		if (ps->flags & APK_PKGSTF_INSTALL) {
			if (i >= ss->assigned_names)
				abort();
615
			ss->best_solution->item[i++] = pkg;
616
		}
617 618 619 620 621 622 623

		dbg_printf("record_solution: " PKG_VER_FMT ": %sINSTALL\n",
			   PKG_VER_PRINTF(pkg),
			   (ps->flags & APK_PKGSTF_INSTALL) ? "" : "NO_");

		pkg = ps->backtrack;
	}
624 625 626 627 628 629 630 631 632 633
	apk_package_array_resize(&ss->best_solution, i);
	ss->best_unsatisfiable = ss->cur_unsatisfiable;
}

static int compare_package_name(const void *p1, const void *p2)
{
	const struct apk_package **c1 = (const struct apk_package **) p1;
	const struct apk_package **c2 = (const struct apk_package **) p2;

	return strcmp((*c1)->name->name, (*c2)->name->name);
634 635 636
}

int apk_solver_solve(struct apk_database *db, struct apk_dependency_array *world,
637
		     struct apk_package_array **solution, int allow_errors)
638 639
{
	struct apk_solver_state *ss;
640
	int i, r;
641 642 643 644

	ss = calloc(1, sizeof(struct apk_solver_state));
	ss->db = db;
	ss->topology_position = -1;
645 646
	ss->best_unsatisfiable = -1;
	ss->allow_errors = allow_errors;
647
	list_init(&ss->unsolved_list_head);
648 649 650 651
	ss->name_state = calloc(db->available.names.num_items + 1, sizeof(struct apk_name_state));

	for (i = 0; i < world->num; i++)
		sort_name(ss, world->item[i].name);
652

653 654
	foreach_dependency(ss, world, apply_constraint);
	do {
655 656
		if (ss->allow_errors ||
		    ss->cur_unsatisfiable < ss->best_unsatisfiable) {
657 658
			r = expand_branch(ss);
			if (r) {
659 660
				dbg_printf("solution with %d unsatisfiable\n",
					   ss->cur_unsatisfiable);
661 662 663 664 665 666 667 668 669 670 671 672 673
				if (ss->cur_unsatisfiable == 0) {
					/* found solution - it is optimal because we permutate
					 * each preferred local option first, and permutations
					 * happen in topologally sorted order. */
					r = 0;
					break;
				}
				if (ss->cur_unsatisfiable < ss->best_unsatisfiable)
					record_solution(ss);
				r = next_branch(ss);
			}
		} else {
			r = next_branch(ss);
674
		}
675
	} while (r == 0);
676 677

	/* collect packages */
678
	if (r == 0 && ss->cur_unsatisfiable == 0) {
679 680
		record_solution(ss);
		*solution = ss->best_solution;
681 682 683 684 685 686 687 688
		r = 0;
	} else if (ss->allow_errors) {
		*solution = ss->best_solution;
		qsort(ss->best_solution->item, ss->best_solution->num,
		      sizeof(struct apk_package *), compare_package_name);
		r = ss->best_unsatisfiable;
	} else
		r = -1;
689 690 691 692 693 694 695 696 697 698 699 700 701 702 703

	free(ss->name_state);
	free(ss);

	return r;
}

static int compare_change(const void *p1, const void *p2)
{
	const struct apk_change *c1 = (const struct apk_change *) p1;
	const struct apk_change *c2 = (const struct apk_change *) p2;

	if (c1->newpkg == NULL) {
		if (c2->newpkg == NULL)
			/* both deleted - reverse topology order */
704 705
			return  pkg_to_ps(c2->oldpkg)->topology_hard -
				pkg_to_ps(c1->oldpkg)->topology_hard;
706 707 708 709 710 711 712 713

		/* c1 deleted, c2 installed -> c2 first*/
		return -1;
	}
	if (c2->newpkg == NULL)
		/* c1 installed, c2 deleted -> c1 first*/
		return 1;

714 715
	return  pkg_to_ps(c1->newpkg)->topology_hard -
		pkg_to_ps(c2->newpkg)->topology_hard;
716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773
}

int apk_solver_generate_changeset(struct apk_database *db,
				  struct apk_package_array *solution,
				  struct apk_changeset *changeset)
{
	struct apk_name *name;
	struct apk_package *pkg, *pkg0;
	struct apk_installed_package *ipkg;
	int num_installs = 0, num_removed = 0, ci = 0;
	int i, j;

	/* calculate change set size */
	for (i = 0; i < solution->num; i++) {
		pkg = solution->item[i];
		name = pkg->name;
		if (pkg->ipkg == NULL || (name->flags & APK_NAME_REINSTALL))
			num_installs++;
		name->flags |= APK_NAME_VISITED;
	}

	list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
		if (!(ipkg->pkg->name->flags & APK_NAME_VISITED))
			num_removed++;
	}

	/* construct changeset */
	apk_change_array_resize(&changeset->changes, num_installs + num_removed);
	list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
		if (ipkg->pkg->name->flags & APK_NAME_VISITED)
			continue;
		changeset->changes->item[ci].oldpkg = ipkg->pkg;
		ci++;
	}
	for (i = 0; i < solution->num; i++) {
		pkg = solution->item[i];
		name = pkg->name;

		if (pkg->ipkg == NULL || (name->flags & APK_NAME_REINSTALL)) {
			for (j = 0; j < name->pkgs->num; j++) {
				pkg0 = name->pkgs->item[j];
				if (pkg0->ipkg == NULL)
					continue;
				changeset->changes->item[ci].oldpkg = pkg0;
				break;
			}
			changeset->changes->item[ci].newpkg = pkg;
			ci++;
		}
		name->flags &= ~APK_NAME_VISITED;
	}

	/* sort changeset to topology order */
	qsort(changeset->changes->item, changeset->changes->num,
	      sizeof(struct apk_change), compare_change);

	return 0;
}