solver.c 32 KB
Newer Older
1 2 3
/* solver.c - Alpine Package Keeper (APK)
 * A backtracking, forward checking dependency graph solver.
 *
4
 * Copyright (C) 2008-2011 Timo Teräs <timo.teras@iki.fi>
5 6 7 8 9 10 11 12 13 14 15 16 17
 * 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"

Timo Teräs's avatar
Timo Teräs committed
18 19
#include "apk_print.h"

20 21 22 23 24 25 26 27 28 29 30
#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
31
#define APK_PKGSTF_INSTALLIF		8
32
#define APK_PKGSTF_DECIDED		16
33 34 35

struct apk_package_state {
	struct apk_package *backtrack;
36
	unsigned int topology_soft;
37 38
	unsigned short flags;
	unsigned short conflicts;
39
	unsigned short cur_unsatisfiable;
40 41
};

42
#define APK_NAMESTF_AVAILABILITY_CHECKED	1
43 44
#define APK_NAMESTF_LOCKED			2
#define APK_NAMESTF_NO_OPTIONS			4
45 46 47
struct apk_name_state {
	struct list_head unsolved_list;
	struct apk_package *chosen;
Timo Teräs's avatar
Timo Teräs committed
48
	unsigned short solver_flags;
49
	unsigned short flags;
50
	unsigned short requirers;
51
	unsigned short install_ifs;
52 53 54 55
};

struct apk_solver_state {
	struct apk_database *db;
56 57
	unsigned num_topology_positions;

58 59 60 61
	struct list_head unsolved_list_head;
	struct apk_package *latest_decision;
	unsigned int topology_position;
	unsigned int assigned_names;
Timo Teräs's avatar
Timo Teräs committed
62
	unsigned short solver_flags;
63
	unsigned short cur_unsatisfiable;
64 65

	struct apk_package_array *best_solution;
66
	unsigned short best_unsatisfiable;
67 68
};

69 70 71 72
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);
73

Timo Teräs's avatar
Timo Teräs committed
74
static struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
75 76 77 78
{
	return (struct apk_package_state*) pkg->state_ptr;
}

Timo Teräs's avatar
Timo Teräs committed
79 80 81 82 83 84 85
static struct apk_name_state *name_to_ns(struct apk_name *name)
{
	if (name->state_ptr == NULL)
		name->state_ptr = calloc(1, sizeof(struct apk_name_state));
	return (struct apk_name_state*) name->state_ptr;
}

86 87 88 89 90 91 92 93 94 95 96
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;
}

97 98 99
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))
100 101 102
{
	int i, j;

103 104 105
	/* And sort the main dependencies */
	for (i = 0; i < depends->num; i++) {
		struct apk_dependency *dep = &depends->item[i];
106 107 108 109
		struct apk_name *name0 = dep->name;

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

111 112 113 114
			/* conflict depends on all to be not installed */
			if (dep->result_mask != APK_DEPMASK_CONFLICT &&
			    !apk_dep_is_satisfied(dep, pkg0))
				continue;
115 116

			cb(ss, pkg0);
117 118
		}
	}
119
}
120

121 122 123 124 125 126 127 128 129 130 131 132
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);
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
		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);
161
	if (ps->topology_soft)
162
		return;
163
	pkg->topology_hard = -1;
164
	ps->topology_soft = -1;
165 166 167 168 169

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

170
	ps->topology_soft = pkg->topology_hard = ++ss->num_topology_positions;
171
	dbg_printf(PKG_VER_FMT ": topology_hard=%d\n",
172
		   PKG_VER_PRINTF(pkg), pkg->topology_hard);
173 174 175 176 177 178 179 180 181
}

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);
182
	if (ps->topology_soft != pkg->topology_hard)
183
		return;
Timo Teräs's avatar
Timo Teräs committed
184
	ps->topology_soft = -1;
185 186 187 188 189 190 191 192 193

	/* 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);
194 195 196 197 198 199 200
}

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

	for (i = 0; i < name->pkgs->num; i++)
201
		sort_soft_dependencies(ss, name->pkgs->item[i]);
202 203
}

204 205 206 207 208 209 210 211 212 213
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];
214
		struct apk_package_state *ps = pkg_to_ps(pkg);
Timo Teräs's avatar
Timo Teräs committed
215
		struct apk_name_state *ns = name_to_ns(pkg->name);
216 217

		/* if package is needed for (re-)install */
Timo Teräs's avatar
Timo Teräs committed
218
		if ((pkg->ipkg == NULL) ||
219
		    ((ns->solver_flags | ss->solver_flags) & APK_SOLVERF_REINSTALL)) {
220 221
			/* and it's not available, we can't use it */
			if (!pkg_available(ss->db, pkg))
222
				ps->conflicts = 1024;
223 224 225 226 227 228
		}
	}

	ns->flags |= APK_NAMESTF_AVAILABILITY_CHECKED;
}

229 230
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))
231
{
232
	int i;
233
	for (i = 0; i < deps->num; i++)
234
		func(ss, &deps->item[i]);
235 236
}

237
static int get_pkg_expansion_flags(struct apk_solver_state *ss, struct apk_package *pkg)
238 239
{
	struct apk_name *name = pkg->name;
240
	struct apk_name_state *ns = name_to_ns(name);
241
	int i, options = 0;
242 243 244

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

249
		if (pkg0 == pkg || ps0 == NULL ||
250
		    pkg0->topology_hard > ss->topology_position ||
251 252
		    (ps0->flags & APK_PKGSTF_DECIDED) ||
		    ps0->conflicts != 0)
253 254
			continue;

255 256 257
		options++;

		if ((ns->solver_flags | ss->solver_flags) & APK_SOLVERF_AVAILABLE) {
258 259
			/* pkg available, pkg0 not */
			if (pkg->repos != 0 && pkg0->repos == 0)
260
				continue;
261 262
			/* pkg0 available, pkg not */
			if (pkg0->repos != 0 && pkg->repos == 0)
263
				return APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH;
264 265
		}

266 267 268 269 270
		if ((ns->solver_flags | ss->solver_flags) & APK_SOLVERF_UPGRADE) {
			/* upgrading, or neither of the package is installed, so
			 * we just fall back comparing to versions */
			switch (apk_pkg_version_compare(pkg0, pkg)) {
			case APK_VERSION_GREATER:
271
				return APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH;
272 273 274
			case APK_VERSION_LESS:
				continue;
			}
275 276
		}

277 278
		/* not upgrading, prefer the installed package */
		if (pkg->ipkg == NULL && pkg0->ipkg != NULL)
279
			return APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH;
280 281
	}

282
	/* no package greater than the selected */
283 284 285 286 287
	if (options)
		return APK_PKGSTF_INSTALL | APK_PKGSTF_BRANCH;

	/* no other choice */
	return APK_PKGSTF_INSTALL;
288 289
}

290 291
static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg)
{
Timo Teräs's avatar
Timo Teräs committed
292
	struct apk_name_state *ns;
293 294 295 296 297
	int i, missing = 0;

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

Timo Teräs's avatar
Timo Teräs committed
298
		ns = name_to_ns(dep->name);
299 300 301 302 303 304 305 306
		if (!(ns->flags & APK_NAMESTF_LOCKED) ||
		    !apk_dep_is_satisfied(dep, ns->chosen))
			missing++;
	}

	return missing;
}

307
static int update_name_state(struct apk_solver_state *ss,
308 309
			     struct apk_name *name, struct apk_name_state *ns,
			     int requirers_adjustment)
310
{
311 312
	struct apk_package *best_pkg = NULL;
	unsigned int best_topology = 0;
313
	int i, options = 0, skipped_options = 0;
314

315 316
	ns->requirers += requirers_adjustment;

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

321
		if (ps0 == NULL ||
322
		    pkg0->topology_hard >= ss->topology_position ||
323
		    (ps0->flags & APK_PKGSTF_DECIDED))
324 325
			continue;

326 327 328 329 330 331
		if (ns->requirers == 0 && ns->install_ifs != 0 &&
		    install_if_missing(ss, pkg0)) {
			skipped_options++;
			continue;
		}

332
		options++;
333 334 335
		if (ps0->topology_soft < ss->topology_position &&
		    ps0->topology_soft > best_topology)
			best_pkg = pkg0, best_topology = ps0->topology_soft;
336 337
		else if (pkg0->topology_hard > best_topology)
			best_pkg = pkg0, best_topology = pkg0->topology_hard;
338
	}
339

340
	if (options == 0 && skipped_options == 0) {
341 342
		if (!(ns->flags & APK_NAMESTF_NO_OPTIONS)) {
			ss->cur_unsatisfiable += ns->requirers;
343 344
			if (ns->install_ifs)
				ss->cur_unsatisfiable++;
345 346 347 348 349 350 351
			ns->flags |= APK_NAMESTF_NO_OPTIONS;
		} else if (requirers_adjustment > 0) {
			ss->cur_unsatisfiable += requirers_adjustment;
		}
	} else
		ns->flags &= ~APK_NAMESTF_NO_OPTIONS;

352 353
	if ((options == 0 && skipped_options == 0) ||
	    (ns->requirers == 0 && ns->install_ifs == 0)) {
354 355 356 357 358
		if (list_hashed(&ns->unsolved_list)) {
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
			ns->chosen = NULL;
		}
359 360
		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);
361
	} else {
362 363 364
		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);
365 366
		if (!list_hashed(&ns->unsolved_list))
			list_add(&ns->unsolved_list, &ss->unsolved_list_head);
367
		ns->chosen = best_pkg;
368 369
	}

370
	return options + skipped_options;
371 372
}

373 374 375 376
static void trigger_install_if(struct apk_solver_state *ss,
			       struct apk_package *pkg)
{
	if (install_if_missing(ss, pkg) == 0) {
Timo Teräs's avatar
Timo Teräs committed
377
		struct apk_name_state *ns = ns = name_to_ns(pkg->name);
378 379 380 381 382 383 384 385 386 387 388 389

		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) {
Timo Teräs's avatar
Timo Teräs committed
390
		struct apk_name_state *ns = name_to_ns(pkg->name);
391 392 393 394 395 396 397 398

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

399 400 401
static void apply_decision(struct apk_solver_state *ss,
			   struct apk_package *pkg,
			   struct apk_package_state *ps)
402
{
Timo Teräs's avatar
Timo Teräs committed
403
	struct apk_name_state *ns = name_to_ns(pkg->name);
404 405 406 407 408 409

	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++;
410
		ss->cur_unsatisfiable += ps->conflicts;
411
		ns->chosen = pkg;
412 413 414 415 416 417 418 419
		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);
420
		foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
421
	} else {
422
		update_name_state(ss, pkg->name, ns, 0);
423 424 425 426 427 428 429
	}
}

static void undo_decision(struct apk_solver_state *ss,
			  struct apk_package *pkg,
			  struct apk_package_state *ps)
{
Timo Teräs's avatar
Timo Teräs committed
430
	struct apk_name_state *ns = name_to_ns(pkg->name);
431 432 433 434

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

435 436 437
	if (ps->flags & APK_PKGSTF_INSTALLIF)
		ss->topology_position = ps->topology_soft;
	else
438
		ss->topology_position = pkg->topology_hard;
439

440 441
	if (ps->flags & APK_PKGSTF_INSTALL) {
		ss->assigned_names--;
442 443

		foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
444 445
		foreach_dependency(ss, pkg->depends, undo_constraint);

446 447
		ns->flags &= ~APK_NAMESTF_LOCKED;
		ns->chosen = NULL;
448
	}
449

450
	ss->cur_unsatisfiable = ps->cur_unsatisfiable;
451
	update_name_state(ss, pkg->name, ns, 0);
452 453
}

454 455
static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
			  int flags)
456
{
457
	struct apk_package_state *ps = pkg_to_ps(pkg);
458 459

	ps->backtrack = ss->latest_decision;
460
	ps->flags = flags | APK_PKGSTF_DECIDED;
461
	ps->cur_unsatisfiable = ss->cur_unsatisfiable;
462 463 464 465 466 467 468

	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;
469
		ss->topology_position = pkg->topology_hard;
470
	}
471
	ss->latest_decision = pkg;
472

473 474 475 476 477 478
	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;

479 480 481 482
	if (ps->flags & APK_PKGSTF_INSTALLIF)
		dbg_printf("triggers due to " PKG_VER_FMT "\n",
			   PKG_VER_PRINTF(pkg));

483
	apply_decision(ss, pkg, ps);
484 485 486 487 488 489 490
}

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

491
	while (ss->latest_decision != NULL) {
492
		pkg = ss->latest_decision;
493
		ps = pkg_to_ps(pkg);
494 495 496 497 498
		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);
499 500
			ps->flags &= ~(APK_PKGSTF_ALT_BRANCH | APK_PKGSTF_DECIDED);
			ss->latest_decision = ps->backtrack;
501 502 503 504 505 506 507
		} 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;

508 509
			apply_decision(ss, pkg, ps);
			return 0;
510 511
		}
	}
512 513 514

	dbg_printf("next_branch: no more branches\n");
	return 1;
515 516
}

517
static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
518 519
{
	struct apk_name *name = dep->name;
Timo Teräs's avatar
Timo Teräs committed
520
	struct apk_name_state *ns = name_to_ns(name);
521
	int i;
522

523
	prepare_name(ss, name, ns);
524 525 526 527 528

	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))
529
			ss->cur_unsatisfiable++;
530 531 532
		return;
	}

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

537
		if (ps0 == NULL ||
538
		    pkg0->topology_hard >= ss->topology_position)
539 540 541 542 543 544 545 546 547 548
			continue;

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

549 550
	update_name_state(ss, name, ns,
			  (dep->result_mask != APK_DEPMASK_CONFLICT) ? 1 : 0);
551 552
}

553
static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
554 555
{
	struct apk_name *name = dep->name;
Timo Teräs's avatar
Timo Teräs committed
556
	struct apk_name_state *ns = name_to_ns(name);
557 558 559 560 561 562 563
	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;
	}
564 565 566

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

569
		if (pkg0->topology_hard >= ss->topology_position)
570 571 572 573 574 575 576 577 578 579
			continue;

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

580 581
	update_name_state(ss, name, ns,
		(dep->result_mask != APK_DEPMASK_CONFLICT) ? -1 : 0);
582 583 584 585
}

static int expand_branch(struct apk_solver_state *ss)
{
586 587
	struct apk_name_state *ns;
	struct apk_package *pkg0 = NULL;
588
	unsigned int topology0 = 0;
589 590 591

	/* FIXME: change unsolved_list to a priority queue */
	list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
592 593 594 595 596 597 598 599 600
		/* 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;
601 602
		else if (ns->chosen->topology_hard > topology0)
			pkg0 = ns->chosen, topology0 = pkg0->topology_hard;
603 604 605 606 607 608
	}
	if (pkg0 == NULL) {
		dbg_printf("expand_branch: list is empty (%d unsatisfied)\n",
			   ss->cur_unsatisfiable);
		return 1;
	}
609

610 611
	/* someone needs to provide this name -- find next eligible
	 * provider candidate */
Timo Teräs's avatar
Timo Teräs committed
612
	ns = name_to_ns(pkg0->name);
613
	dbg_printf("expand_branch: %s\n", pkg0->name->name);
614

615
	push_decision(ss, pkg0, get_pkg_expansion_flags(ss, pkg0));
616 617 618 619 620 621 622 623 624 625 626 627 628 629 630

	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) {
631
		ps = pkg_to_ps(pkg);
632 633 634
		if (ps->flags & APK_PKGSTF_INSTALL) {
			if (i >= ss->assigned_names)
				abort();
635
			ss->best_solution->item[i++] = pkg;
636
		}
637 638 639 640 641 642 643

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

		pkg = ps->backtrack;
	}
644 645 646 647 648 649 650 651 652 653
	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);
654 655
}

Timo Teräs's avatar
Timo Teräs committed
656 657 658 659 660 661 662 663
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 */
664 665
			return  c2->oldpkg->topology_hard -
				c1->oldpkg->topology_hard;
Timo Teräs's avatar
Timo Teräs committed
666 667 668 669 670 671 672 673

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

674 675
	return  c1->newpkg->topology_hard -
		c2->newpkg->topology_hard;
Timo Teräs's avatar
Timo Teräs committed
676 677 678 679
}

static int generate_changeset(struct apk_database *db,
			      struct apk_package_array *solution,
680 681
			      struct apk_changeset *changeset,
			      unsigned short solver_flags)
Timo Teräs's avatar
Timo Teräs committed
682 683 684 685 686 687 688 689 690 691 692
{
	struct apk_name *name;
	struct apk_name_state *ns;
	struct apk_package *pkg, *pkg0;
	struct apk_installed_package *ipkg;
	int i, j, num_installs = 0, num_removed = 0, ci = 0;

	/* calculate change set size */
	for (i = 0; i < solution->num; i++) {
		pkg = solution->item[i];
		if ((pkg->ipkg == NULL) ||
693
		    ((solver_flags | name_to_ns(pkg->name)->solver_flags) & APK_SOLVERF_REINSTALL))
Timo Teräs's avatar
Timo Teräs committed
694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717
			num_installs++;
	}
	list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
		name = ipkg->pkg->name;
		ns = name_to_ns(name);
		if ((ns->chosen == NULL) || !(ns->flags & APK_NAMESTF_LOCKED))
			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) {
		name = ipkg->pkg->name;
		ns = name_to_ns(name);
		if ((ns->chosen == NULL) || !(ns->flags & APK_NAMESTF_LOCKED)) {
			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) ||
718
		    ((solver_flags | name_to_ns(name)->solver_flags) & APK_SOLVERF_REINSTALL)) {
Timo Teräs's avatar
Timo Teräs committed
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
			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++;
		}
	}

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

	return 0;
}

static int free_state(apk_hash_item item, void *ctx)
{
	struct apk_name *name = (struct apk_name *) item;

	if (name->state_ptr != NULL) {
		free(name->state_ptr);
		name->state_ptr = NULL;
	}
	return 0;
}

749 750 751 752 753 754 755 756 757 758 759
static int free_package(apk_hash_item item, void *ctx)
{
	struct apk_package *pkg = (struct apk_package *) item;

	if (pkg->state_ptr != NULL) {
		free(pkg->state_ptr);
		pkg->state_ptr = NULL;
	}
	return 0;
}

760 761 762 763 764 765 766
void apk_solver_set_name_flags(struct apk_name *name,
			       unsigned short solver_flags)
{
	struct apk_name_state *ns = name_to_ns(name);
	ns->solver_flags = solver_flags;
}

767 768 769 770 771 772
static void apk_solver_free(struct apk_database *db)
{
	apk_hash_foreach(&db->available.names, free_state, NULL);
	apk_hash_foreach(&db->available.packages, free_package, NULL);
}

Timo Teräs's avatar
Timo Teräs committed
773 774 775 776 777
int apk_solver_solve(struct apk_database *db,
		     unsigned short solver_flags,
		     struct apk_dependency_array *world,
		     struct apk_package_array **solution,
		     struct apk_changeset *changeset)
778 779
{
	struct apk_solver_state *ss;
Timo Teräs's avatar
Timo Teräs committed
780
	struct apk_installed_package *ipkg;
781
	int i, r;
782 783 784

	ss = calloc(1, sizeof(struct apk_solver_state));
	ss->db = db;
Timo Teräs's avatar
Timo Teräs committed
785
	ss->solver_flags = solver_flags;
786
	ss->topology_position = -1;
787
	ss->best_unsatisfiable = -1;
788
	list_init(&ss->unsolved_list_head);
789 790 791

	for (i = 0; i < world->num; i++)
		sort_name(ss, world->item[i].name);
Timo Teräs's avatar
Timo Teräs committed
792 793
	list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list)
		sort_name(ss, ipkg->pkg->name);
794

795 796
	foreach_dependency(ss, world, apply_constraint);
	do {
Timo Teräs's avatar
Timo Teräs committed
797
		if (ss->cur_unsatisfiable < ss->best_unsatisfiable) {
798 799
			r = expand_branch(ss);
			if (r) {
800 801
				dbg_printf("solution with %d unsatisfiable\n",
					   ss->cur_unsatisfiable);
802 803 804 805 806 807 808 809 810 811 812 813 814
				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);
815
		}
816
	} while (r == 0);
817 818

	/* collect packages */
819
	if (r == 0 && ss->cur_unsatisfiable == 0) {
820
		record_solution(ss);
Timo Teräs's avatar
Timo Teräs committed
821
		if (changeset != NULL)
822 823
			generate_changeset(db, ss->best_solution, changeset,
					   ss->solver_flags);
824
		r = 0;
Timo Teräs's avatar
Timo Teräs committed
825
	} else {
826 827 828
		qsort(ss->best_solution->item, ss->best_solution->num,
		      sizeof(struct apk_package *), compare_package_name);
		r = ss->best_unsatisfiable;
Timo Teräs's avatar
Timo Teräs committed
829 830 831 832 833 834
	}

	if (solution != NULL)
		*solution = ss->best_solution;
	else
		apk_package_array_free(&ss->best_solution);
835

836
	apk_solver_free(db);
837 838 839 840 841
	free(ss);

	return r;
}

Timo Teräs's avatar
Timo Teräs committed
842 843 844
static void print_change(struct apk_database *db,
			 struct apk_change *change,
			 int cur, int total)
845
{
Timo Teräs's avatar
Timo Teräs committed
846 847 848 849 850 851
	struct apk_name *name;
	struct apk_package *oldpkg = change->oldpkg;
	struct apk_package *newpkg = change->newpkg;
	const char *msg = NULL;
	char status[64];
	int r;
852

Timo Teräs's avatar
Timo Teräs committed
853 854
	snprintf(status, sizeof(status), "(%i/%i)", cur+1, total);
	status[sizeof(status) - 1] = '\0';
855

Timo Teräs's avatar
Timo Teräs committed
856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888
	if (oldpkg != NULL)
		name = oldpkg->name;
	else
		name = newpkg->name;

	if (oldpkg == NULL) {
		apk_message("%s Installing %s (" BLOB_FMT ")",
			    status, name->name,
			    BLOB_PRINTF(*newpkg->version));
	} else if (newpkg == NULL) {
		apk_message("%s Purging %s (" BLOB_FMT ")",
			    status, name->name,
			    BLOB_PRINTF(*oldpkg->version));
	} else {
		r = apk_pkg_version_compare(newpkg, oldpkg);
		switch (r) {
		case APK_VERSION_LESS:
			msg = "Downgrading";
			break;
		case APK_VERSION_EQUAL:
			if (newpkg == oldpkg)
				msg = "Re-installing";
			else
				msg = "Replacing";
			break;
		case APK_VERSION_GREATER:
			msg = "Upgrading";
			break;
		}
		apk_message("%s %s %s (" BLOB_FMT " -> " BLOB_FMT ")",
			    status, msg, name->name,
			    BLOB_PRINTF(*oldpkg->version),
			    BLOB_PRINTF(*newpkg->version));
889
	}
Timo Teräs's avatar
Timo Teräs committed
890
}
891

Timo Teräs's avatar
Timo Teräs committed
892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919
struct apk_stats {
	unsigned int bytes;
	unsigned int packages;
};

static void count_change(struct apk_change *change, struct apk_stats *stats)
{
	if (change->newpkg != NULL) {
		stats->bytes += change->newpkg->installed_size;
		stats->packages ++;
	}
	if (change->oldpkg != NULL)
		stats->packages ++;
}

static void draw_progress(int percent)
{
	const int bar_width = apk_get_screen_width() - 7;
	int i;

	fprintf(stderr, "\e7%3i%% [", percent);
	for (i = 0; i < bar_width * percent / 100; i++)
		fputc('#', stderr);
	for (; i < bar_width; i++)
		fputc(' ', stderr);
	fputc(']', stderr);
	fflush(stderr);
	fputs("\e8\e[0K", stderr);
920 921
}

Timo Teräs's avatar
Timo Teräs committed
922 923 924 925 926 927 928 929
struct progress {
	struct apk_stats done;
	struct apk_stats total;
	struct apk_package *pkg;
	size_t count;
};

static void progress_cb(void *ctx, size_t progress)
930
{
Timo Teräs's avatar
Timo Teräs committed
931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949
	struct progress *prog = (struct progress *) ctx;
	size_t partial = 0, count;

	if (prog->pkg != NULL)
		partial = muldiv(progress, prog->pkg->installed_size, APK_PROGRESS_SCALE);

        count = muldiv(100, prog->done.bytes + prog->done.packages + partial,
		       prog->total.bytes + prog->total.packages);

	if (prog->count != count)
		draw_progress(count);
	prog->count = count;
}

static int dump_packages(struct apk_changeset *changeset,
			 int (*cmp)(struct apk_change *change),
			 const char *msg)
{
	struct apk_change *change;
950
	struct apk_name *name;
951
	struct apk_indent indent = { .indent = 2 };
Timo Teräs's avatar
Timo Teräs committed
952
	int match = 0, i;
953

Timo Teräs's avatar
Timo Teräs committed
954 955 956 957 958 959 960 961 962 963 964 965 966
	for (i = 0; i < changeset->changes->num; i++) {
		change = &changeset->changes->item[i];
		if (!cmp(change))
			continue;
		if (match == 0)
			printf("%s:\n ", msg);
		if (change->newpkg != NULL)
			name = change->newpkg->name;
		else
			name = change->oldpkg->name;

		apk_print_indented(&indent, APK_BLOB_STR(name->name));
		match++;
967
	}
Timo Teräs's avatar
Timo Teräs committed
968 969 970 971
	if (match)
		printf("\n");
	return match;
}
972

Timo Teräs's avatar
Timo Teräs committed
973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009
static int cmp_remove(struct apk_change *change)
{
	return change->newpkg == NULL;
}

static int cmp_new(struct apk_change *change)
{
	return change->oldpkg == NULL;
}

static int cmp_downgrade(struct apk_change *change)
{
	if (change->newpkg == NULL || change->oldpkg == NULL)
		return 0;
	if (apk_pkg_version_compare(change->newpkg, change->oldpkg)
	    & APK_VERSION_LESS)
		return 1;
	return 0;
}

static int cmp_upgrade(struct apk_change *change)
{
	if (change->newpkg == NULL || change->oldpkg == NULL)
		return 0;

	/* Count swapping package as upgrade too - this can happen if
	 * same package version is used after it was rebuilt against
	 * newer libraries. Basically, different (and probably newer)
	 * package, but equal version number. */
	if ((apk_pkg_version_compare(change->newpkg, change->oldpkg) &
	     (APK_VERSION_GREATER | APK_VERSION_EQUAL)) &&
	    (change->newpkg != change->oldpkg))
		return 1;

	return 0;
}

1010 1011 1012 1013 1014
static int compare_package(const void *p1, const void *p2)
{
	struct apk_package *pkg1 = *(struct apk_package **) p1;
	struct apk_package *pkg2 = *(struct apk_package **) p2;

1015
	return pkg1->topology_hard - pkg2->topology_hard;
1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041
}

static void run_triggers(struct apk_database *db)
{
	struct apk_package_array *pkgs;
	int i;

	pkgs = apk_db_get_pending_triggers(db);
	if (pkgs == NULL || pkgs->num == 0)
		return;

	qsort(pkgs->item, pkgs->num, sizeof(struct apk_package *),
	      compare_package);

	for (i = 0; i < pkgs->num; i++) {
		struct apk_package *pkg = pkgs->item[i];
		struct apk_installed_package *ipkg = pkg->ipkg;

		*apk_string_array_add(&ipkg->pending_triggers) = NULL;
		apk_ipkg_run_script(ipkg, db, APK_SCRIPT_TRIGGER,
				    ipkg->pending_triggers->item);
		apk_string_array_free(&ipkg->pending_triggers);
	}
	apk_package_array_free(&pkgs);
}

1042 1043 1044
int apk_solver_commit_changeset(struct apk_database *db,
				struct apk_changeset *changeset,
				struct apk_dependency_array *world)
Timo Teräs's avatar
Timo Teräs committed
1045 1046 1047 1048 1049
{
	struct progress prog;
	struct apk_change *change;
	int i, r = 0, size_diff = 0;

1050 1051 1052
	if (changeset->changes == NULL)
		goto all_done;

Timo Teräs's avatar
Timo Teräs committed
1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086
	/* Count what needs to be done */
	memset(&prog, 0, sizeof(prog));
	for (i = 0; i < changeset->changes->num; i++) {
		change = &changeset->changes->item[i];
		count_change(change, &prog.total);
		if (change->newpkg)
			size_diff += change->newpkg->installed_size;
		if (change->oldpkg)
			size_diff -= change->oldpkg->installed_size;
	}
	size_diff /= 1024;

	if (apk_verbosity > 1 || (apk_flags & APK_INTERACTIVE)) {
		r = dump_packages(changeset, cmp_remove,
				  "The following packages will be REMOVED");
		r += dump_packages(changeset, cmp_downgrade,
				   "The following packages will be DOWNGRADED");
		if (r || (apk_flags & APK_INTERACTIVE) || apk_verbosity > 2) {
			dump_packages(changeset, cmp_new,
				      "The following NEW packages will be installed");
			dump_packages(changeset, cmp_upgrade,
				      "The following packages will be upgraded");
			printf("After this operation, %d kB of %s\n", abs(size_diff),
			       (size_diff < 0) ?
			       "disk space will be freed." :
			       "additional disk space will be used.");
		}
		if (apk_flags & APK_INTERACTIVE) {
			printf("Do you want to continue [Y/n]? ");
			fflush(stdout);
			r = fgetc(stdin);
			if (r != 'y' && r != 'Y' && r != '\n')
				return -1;
		}
1087 1088
	}

Timo Teräs's avatar
Timo Teräs committed
1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112
	/* Go through changes */
	r = 0;
	for (i = 0; i < changeset->changes->num; i++) {
		change = &changeset->changes->item[i];

		print_change(db, change, i, changeset->changes->num);
		if (apk_flags & APK_PROGRESS)
			draw_progress(prog.count);
		prog.pkg = change->newpkg;

		if (!(apk_flags & APK_SIMULATE)) {
			r = apk_db_install_pkg(db,
					       change->oldpkg, change->newpkg,
					       (apk_flags & APK_PROGRESS) ? progress_cb : NULL,
					       &prog);
			if (r != 0)
				break;
		}

		count_change(change, &prog.done);
	}
	if (apk_flags & APK_PROGRESS)
		draw_progress(100);

1113
	run_triggers(db);
Timo Teräs's avatar
Timo Teräs committed
1114

1115
all_done:
Timo Teräs's avatar
Timo Teräs committed
1116 1117 1118
	apk_dependency_array_copy(&db->world, world);
	apk_db_write_config(db);

1119
	if (r == 0 && !db->performing_self_update) {
Timo Teräs's avatar
Timo Teräs committed
1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140
		apk_message("OK: %d packages, %d dirs, %d files",
			    db->installed.stats.packages,
			    db->installed.stats.dirs,
			    db->installed.stats.files);
	}

	return r;
}

static void print_dep_errors(char *label, struct apk_dependency_array *deps)
{
	int i, print_label = 1;
	char buf[256];
	apk_blob_t p;
	struct apk_indent indent;

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

		if (pkg != NULL && apk_dep_is_satisfied(dep, pkg))
1141
			continue;
Timo Teräs's avatar
Timo Teräs committed
1142 1143 1144 1145 1146 1147 1148 1149 1150 1151

		if (print_label) {
			print_label = 0;
			indent.x = printf("  %s:", label);
			indent.indent = indent.x + 1;
		}
		p = APK_BLOB_BUF(buf);
		apk_blob_push_dep(&p, dep);
		p = apk_blob_pushed(APK_BLOB_BUF(buf), p);
		apk_print_indented(&indent, p);
1152
	}
Timo Teräs's avatar
Timo Teräs committed
1153 1154 1155 1156
	if (!print_label)
		printf("\n");
}

1157 1158 1159 1160
void apk_solver_print_errors(struct apk_database *db,
			     struct apk_package_array *solution,
			     struct apk_dependency_array *world,
			     int unsatisfiable)
Timo Teräs's avatar
Timo Teräs committed
1161 1162 1163 1164 1165
{
	int i;

	apk_error("%d unsatisfiable dependencies:", unsatisfiable);

1166
	for (i = 0; i < solution->num; i++) {
Timo Teräs's avatar
Timo Teräs committed
1167 1168 1169
		struct apk_package *pkg = solution->item[i];
		pkg->name->state_ptr = pkg;
	}
1170

Timo Teräs's avatar
Timo Teräs committed
1171 1172 1173 1174 1175 1176
	print_dep_errors("world", world);
	for (i = 0; i < solution->num; i++) {
		struct apk_package *pkg = solution->item[i];
		char pkgtext[256];
		snprintf(pkgtext, sizeof(pkgtext), PKG_VER_FMT, PKG_VER_PRINTF(solution->item[i]));
		print_dep_errors(pkgtext, pkg->depends);
1177
	}
Timo Teräs's avatar
Timo Teräs committed
1178
}
1179

Timo Teräs's avatar
Timo Teräs committed
1180 1181 1182 1183 1184 1185 1186
int apk_solver_commit(struct apk_database *db,
		      unsigned short solver_flags,
		      struct apk_dependency_array *world)
{
	struct apk_changeset changeset = {};
	struct apk_package_array *solution = NULL;
	int r;
1187

1188
	r = apk_solver_solve(db, solver_flags,
1189
			     world, &solution, &changeset);
Timo Teräs's avatar
Timo Teräs committed
1190 1191 1192 1193 1194
	if (r < 0)
		return r;

	if (r == 0 || (apk_flags & APK_FORCE)) {
		/* Success -- or forced installation of bad graph */
1195
		apk_solver_commit_changeset(db, &changeset, world);
Timo Teräs's avatar
Timo Teräs committed
1196 1197 1198
		r = 0;
	} else {
		/* Failure -- print errors */
1199
		apk_solver_print_errors(db, solution, world, r);
Timo Teräs's avatar
Timo Teräs committed
1200 1201 1202 1203
	}
	apk_package_array_free(&solution);

	return r;
1204
}