solver.c 21.2 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 31 32

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

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

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

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

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

66 67 68 69
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);
70

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

76 77 78 79 80 81 82 83 84 85 86
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;
}

87 88 89
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))
90 91 92
{
	int i, j;

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

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

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

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

111 112 113 114 115 116 117 118 119 120 121 122
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);
123

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
		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);
181 182 183 184 185 186 187
}

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

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

191 192 193 194 195 196 197 198 199 200
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];
201
		struct apk_package_state *ps = pkg_to_ps(pkg);
202 203 204 205 206 207 208 209 210 211 212 213

		/* 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;
}

214 215
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))
216
{
217
	int i;
218
	for (i = 0; i < deps->num; i++)
219
		func(ss, &deps->item[i]);
220 221
}

222
static int inline can_consider_package(struct apk_solver_state *ss, struct apk_package_state *ps)
223
{
224 225
	if (ps == NULL)
		return FALSE;
226
	if (ps->topology_hard > ss->topology_position)
227 228 229 230 231 232
		return FALSE;
	if (ps->conflicts)
		return FALSE;
	return TRUE;
}

233
static int get_pkg_expansion_flags(struct apk_solver_state *ss, struct apk_package *pkg)
234 235
{
	struct apk_name *name = pkg->name;
236
	int i, options = 0;
237 238 239

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

244
		if (pkg0 == pkg || !can_consider_package(ss, ps0))
245 246
			continue;

247 248 249
		if (apk_flags & APK_PREFER_AVAILABLE) {
			/* pkg available, pkg0 not */
			if (pkg->repos != 0 && pkg0->repos == 0)
250
				continue;
251 252
			/* pkg0 available, pkg not */
			if (pkg0->repos != 0 && pkg->repos == 0)
253
				return APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH;
254 255
		}

256 257
		if (!(apk_flags & APK_UPGRADE)) {
			/* not upgrading, prefer the installed package */
258 259
			if (pkg->ipkg == NULL && pkg0->ipkg != NULL)
				return APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH;
260 261 262 263
		}

		/* upgrading, or neither of the package is installed, so
		 * we just fall back comparing to versions */
264
		options++;
265
		if (apk_pkg_version_compare(pkg0, pkg) == APK_VERSION_GREATER)
266
			return APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH;
267 268
	}

269
	/* no package greater than the selected */
270 271 272 273 274
	if (options)
		return APK_PKGSTF_INSTALL | APK_PKGSTF_BRANCH;

	/* no other choice */
	return APK_PKGSTF_INSTALL;
275 276
}

277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293
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;
}

294
static int update_name_state(struct apk_solver_state *ss,
295 296
			     struct apk_name *name, struct apk_name_state *ns,
			     int requirers_adjustment)
297
{
298 299
	struct apk_package *best_pkg = NULL;
	unsigned int best_topology = 0;
300
	int i, options = 0, skipped_options = 0;
301

302 303
	ns->requirers += requirers_adjustment;

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

308
		if (!can_consider_package(ss, ps0))
309 310
			continue;

311 312 313 314 315 316
		if (ns->requirers == 0 && ns->install_ifs != 0 &&
		    install_if_missing(ss, pkg0)) {
			skipped_options++;
			continue;
		}

317
		options++;
318 319 320 321 322
		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;
323
	}
324

325
	if (options == 0 && skipped_options == 0) {
326 327
		if (!(ns->flags & APK_NAMESTF_NO_OPTIONS)) {
			ss->cur_unsatisfiable += ns->requirers;
328 329
			if (ns->install_ifs)
				ss->cur_unsatisfiable++;
330 331 332 333 334 335 336
			ns->flags |= APK_NAMESTF_NO_OPTIONS;
		} else if (requirers_adjustment > 0) {
			ss->cur_unsatisfiable += requirers_adjustment;
		}
	} else
		ns->flags &= ~APK_NAMESTF_NO_OPTIONS;

337
	if (options == 0 || (ns->requirers == 0 && ns->install_ifs == 0)) {
338 339 340 341 342
		if (list_hashed(&ns->unsolved_list)) {
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
			ns->chosen = NULL;
		}
343 344
		dbg_printf("%s: deleted from unsolved: %d requirers, %d install_ifs, %d options\n",
			   name->name, ns->requirers, ns->install_ifs, options);
345
	} else {
346 347 348
		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);
349 350
		if (!list_hashed(&ns->unsolved_list))
			list_add(&ns->unsolved_list, &ss->unsolved_list_head);
351
		ns->chosen = best_pkg;
352 353
	}

354 355 356
	return options;
}

357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382
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);
	}
}

383 384 385
static void apply_decision(struct apk_solver_state *ss,
			   struct apk_package *pkg,
			   struct apk_package_state *ps)
386 387 388 389 390 391 392 393 394
{
	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++;
		ns->chosen = pkg;
395 396 397 398 399 400 401 402
		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);
403
		foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
404
	} else {
405 406
		ps->conflicts++;
		update_name_state(ss, pkg->name, ns, 0);
407 408 409 410 411 412 413 414 415 416 417 418
	}
}

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");

419
	ss->cur_unsatisfiable = ps->cur_unsatisfiable;
420 421 422 423
	if (ps->flags & APK_PKGSTF_INSTALLIF)
		ss->topology_position = ps->topology_soft;
	else
		ss->topology_position = ps->topology_hard;
424

425 426
	if (ps->flags & APK_PKGSTF_INSTALL) {
		ss->assigned_names--;
427 428

		foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
429 430
		foreach_dependency(ss, pkg->depends, undo_constraint);

431 432 433 434
		ns->flags &= ~APK_NAMESTF_LOCKED;
		ns->chosen = NULL;
	} else {
		ps->conflicts--;
435
	}
436 437

	update_name_state(ss, pkg->name, ns, 0);
438 439
}

440 441
static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
			  int flags)
442
{
443
	struct apk_package_state *ps = pkg_to_ps(pkg);
444 445 446

	ps->backtrack = ss->latest_decision;
	ps->flags = flags;
447
	ps->cur_unsatisfiable = ss->cur_unsatisfiable;
448 449 450 451 452 453 454 455 456

	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;
	}
457
	ss->latest_decision = pkg;
458

459 460 461 462 463 464
	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;

465 466 467 468
	if (ps->flags & APK_PKGSTF_INSTALLIF)
		dbg_printf("triggers due to " PKG_VER_FMT "\n",
			   PKG_VER_PRINTF(pkg));

469
	apply_decision(ss, pkg, ps);
470 471 472 473 474 475 476
}

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

477
	while (ss->latest_decision != NULL) {
478
		pkg = ss->latest_decision;
479
		ps = pkg_to_ps(pkg);
480 481 482 483 484 485 486 487 488 489 490 491 492 493
		undo_decision(ss, pkg, ps);

		if (ps->flags & APK_PKGSTF_ALT_BRANCH) {
			pkg = ps->backtrack;
			ss->latest_decision = pkg;
			dbg_printf("next_branch: undo decision at topology_position %d\n",
				   ss->topology_position);
		} 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;

494 495
			apply_decision(ss, pkg, ps);
			return 0;
496 497
		}
	}
498 499 500

	dbg_printf("next_branch: no more branches\n");
	return 1;
501 502
}

503
static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
504 505 506
{
	struct apk_name *name = dep->name;
	struct apk_name_state *ns = &ss->name_state[name->id];
507
	int i;
508

509
	prepare_name(ss, name, ns);
510 511 512 513 514 515 516 517 518

	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))
			ss->cur_unsatisfiable += 200;
		return;
	}

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

523
		if (ps0 == NULL ||
524
		    ps0->topology_hard >= ss->topology_position)
525 526 527 528 529 530 531 532 533 534
			continue;

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

535 536
	update_name_state(ss, name, ns,
			  (dep->result_mask != APK_DEPMASK_CONFLICT) ? 1 : 0);
537 538
}

539
static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
540 541 542
{
	struct apk_name *name = dep->name;
	struct apk_name_state *ns = &ss->name_state[name->id];
543 544 545 546 547 548 549
	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;
	}
550 551 552

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

555
		if (ps0->topology_hard >= ss->topology_position)
556 557 558 559 560 561 562 563 564 565
			continue;

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

566 567
	update_name_state(ss, name, ns,
		(dep->result_mask != APK_DEPMASK_CONFLICT) ? -1 : 0);
568 569 570 571
}

static int expand_branch(struct apk_solver_state *ss)
{
572 573
	struct apk_name_state *ns;
	struct apk_package *pkg0 = NULL;
574
	unsigned int topology0 = 0;
575 576 577

	/* FIXME: change unsolved_list to a priority queue */
	list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
578 579 580 581 582 583 584 585 586 587 588
		/* 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;
589 590 591 592 593 594
	}
	if (pkg0 == NULL) {
		dbg_printf("expand_branch: list is empty (%d unsatisfied)\n",
			   ss->cur_unsatisfiable);
		return 1;
	}
595

596 597 598
	/* someone needs to provide this name -- find next eligible
	 * provider candidate */
	ns = &ss->name_state[pkg0->name->id];
599
	dbg_printf("expand_branch: %s\n", pkg0->name->name);
600

601
	push_decision(ss, pkg0, get_pkg_expansion_flags(ss, pkg0));
602 603 604 605 606 607 608 609 610 611 612 613 614 615 616

	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) {
617
		ps = pkg_to_ps(pkg);
618 619
		if ((ps->flags & APK_PKGSTF_INSTALL) &&
		    (ps->conflicts == 0))
620 621 622 623 624 625 626 627
			ss->best_solution->item[i++] = pkg;

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

		pkg = ps->backtrack;
	}
628 629 630 631 632 633 634 635 636 637
	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);
638 639 640
}

int apk_solver_solve(struct apk_database *db, struct apk_dependency_array *world,
641
		     struct apk_package_array **solution, int allow_errors)
642 643
{
	struct apk_solver_state *ss;
644
	int i, r;
645 646 647 648

	ss = calloc(1, sizeof(struct apk_solver_state));
	ss->db = db;
	ss->topology_position = -1;
649 650
	ss->best_unsatisfiable = -1;
	ss->allow_errors = allow_errors;
651
	list_init(&ss->unsolved_list_head);
652 653 654 655
	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);
656

657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674
	foreach_dependency(ss, world, apply_constraint);
	do {
		if (ss->allow_errors || ss->cur_unsatisfiable < ss->best_unsatisfiable) {
			r = expand_branch(ss);
			if (r) {
				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);
675
		}
676
	} while (r == 0);
677 678

	/* collect packages */
679
	if (r == 0 && ss->cur_unsatisfiable == 0) {
680 681
		record_solution(ss);
		*solution = ss->best_solution;
682 683 684 685 686 687 688 689
		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;
690 691 692 693 694 695 696 697 698 699 700 701 702 703 704

	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 */
705 706
			return  pkg_to_ps(c2->oldpkg)->topology_hard -
				pkg_to_ps(c1->oldpkg)->topology_hard;
707 708 709 710 711 712 713 714

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

715 716
	return  pkg_to_ps(c1->newpkg)->topology_hard -
		pkg_to_ps(c2->newpkg)->topology_hard;
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 774
}

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;
}