solver.c 39.9 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
 * 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 "apk_defines.h"
#include "apk_database.h"
#include "apk_package.h"
#include "apk_solver.h"

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

19 20 21 22 23 24 25 26 27
#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
Timo Teräs's avatar
Timo Teräs committed
28 29 30 31 32 33 34 35
#define APK_PKGSTF_ALT_BRANCH		2
#define APK_PKGSTF_INSTALLIF		4
#define APK_PKGSTF_DECIDED		8

struct apk_score {
	unsigned short unsatisfiable;
	unsigned short preference;
};
36 37 38

struct apk_package_state {
	struct apk_package *backtrack;
39
	unsigned int topology_soft;
Timo Teräs's avatar
Timo Teräs committed
40
	struct apk_score saved_score;
41 42 43 44 45 46
	unsigned short flags;
	unsigned short conflicts;
};

struct apk_name_state {
	struct list_head unsolved_list;
Timo Teräs's avatar
Timo Teräs committed
47
	struct apk_name *name;
48
	struct apk_package *chosen;
49
	struct apk_score minimum_penalty;
50
	unsigned int topology_last_touched;
51
	unsigned int allowed_repos, preferred_repos;
52
	unsigned short requirers;
53
	unsigned short install_ifs;
Timo Teräs's avatar
Timo Teräs committed
54 55 56 57 58 59 60

	unsigned int solver_flags_local : 4;
	unsigned int solver_flags_local_mask : 4;
	unsigned int solver_flags_inherited : 4;

	unsigned int availability_checked : 1;
	unsigned int locked : 1;
Timo Teräs's avatar
Timo Teräs committed
61
	unsigned int in_changeset : 1;
62 63 64 65
};

struct apk_solver_state {
	struct apk_database *db;
66 67
	unsigned num_topology_positions;

68 69 70 71
	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
72
	struct apk_score score;
73
	struct apk_score minimum_penalty;
74

Timo Teräs's avatar
Timo Teräs committed
75 76
	unsigned int solver_flags : 4;
	unsigned int refresh_name_states : 1;
Timo Teräs's avatar
Timo Teräs committed
77

78
	struct apk_package_array *best_solution;
Timo Teräs's avatar
Timo Teräs committed
79
	struct apk_score best_score;
80 81
};

82 83 84 85
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);
86

87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124
static void addscore(struct apk_score *a, struct apk_score *b)
{
	a->unsatisfiable += b->unsatisfiable;
	a->preference += b->preference;
}

static void subscore(struct apk_score *a, struct apk_score *b)
{
	a->unsatisfiable -= b->unsatisfiable;
	a->preference -= b->preference;
}

static int cmpscore(struct apk_score *a, struct apk_score *b)
{
	if (a->unsatisfiable < b->unsatisfiable)
		return -1;
	if (a->unsatisfiable > b->unsatisfiable)
		return 1;
	if (a->preference < b->preference)
		return -1;
	if (a->preference > b->preference)
		return 1;
	return 0;
}

static int cmpscore2(struct apk_score *a1, struct apk_score *a2, struct apk_score *b)
{
	if (a1->unsatisfiable+a2->unsatisfiable < b->unsatisfiable)
		return -1;
	if (a1->unsatisfiable+a2->unsatisfiable > b->unsatisfiable)
		return 1;
	if (a1->preference+a2->preference < b->preference)
		return -1;
	if (a1->preference+a2->preference > b->preference)
		return 1;
	return 0;
}

Timo Teräs's avatar
Timo Teräs committed
125
static struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
126 127 128 129
{
	return (struct apk_package_state*) pkg->state_ptr;
}

Timo Teräs's avatar
Timo Teräs committed
130 131
static struct apk_name_state *name_to_ns(struct apk_name *name)
{
Timo Teräs's avatar
Timo Teräs committed
132 133 134 135 136 137 138 139 140 141
	struct apk_name_state *ns;

	if (name->state_ptr == NULL) {
		ns = calloc(1, sizeof(struct apk_name_state));
		ns->name = name;
		name->state_ptr = ns;
	} else {
		ns = (struct apk_name_state*) name->state_ptr;
	}
	return ns;
Timo Teräs's avatar
Timo Teräs committed
142 143
}

144 145 146 147 148 149 150 151 152 153 154
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;
}

155 156 157
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))
158 159 160
{
	int i, j;

161 162 163
	/* And sort the main dependencies */
	for (i = 0; i < depends->num; i++) {
		struct apk_dependency *dep = &depends->item[i];
164 165 166 167
		struct apk_name *name0 = dep->name;

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

169
			/* conflict depends on all to be not installed */
170
			if (!apk_dep_is_satisfied(dep, pkg0))
171
				continue;
172 173

			cb(ss, pkg0);
174 175
		}
	}
176
}
177

178 179 180 181 182 183 184 185 186 187 188 189
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);
190

191 192 193 194 195 196
		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 &&
197
				    apk_dep_is_satisfied(dep, pkg))
198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216
					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);
217
	if (ps->topology_soft)
218
		return;
219
	pkg->topology_hard = -1;
220
	ps->topology_soft = -1;
221 222 223 224 225

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

226
	ps->topology_soft = pkg->topology_hard = ++ss->num_topology_positions;
227
	dbg_printf(PKG_VER_FMT ": topology_hard=%d\n",
228
		   PKG_VER_PRINTF(pkg), pkg->topology_hard);
229 230 231 232 233 234 235 236 237
}

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);
238
	if (ps->topology_soft != pkg->topology_hard)
239
		return;
Timo Teräs's avatar
Timo Teräs committed
240
	ps->topology_soft = -1;
241 242 243 244 245 246 247 248 249

	/* 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);
250 251 252 253 254 255 256
}

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

	for (i = 0; i < name->pkgs->num; i++)
257
		sort_soft_dependencies(ss, name->pkgs->item[i]);
258 259
}

260 261 262 263 264
static void prepare_name(struct apk_solver_state *ss, struct apk_name *name,
			 struct apk_name_state *ns)
{
	int i;

Timo Teräs's avatar
Timo Teräs committed
265
	if (ns->availability_checked)
266 267 268 269
		return;

	for (i = 0; i < name->pkgs->num; i++) {
		struct apk_package *pkg = name->pkgs->item[i];
270
		struct apk_package_state *ps = pkg_to_ps(pkg);
Timo Teräs's avatar
Timo Teräs committed
271
		struct apk_name_state *ns = name_to_ns(pkg->name);
272 273

		/* if package is needed for (re-)install */
Timo Teräs's avatar
Timo Teräs committed
274
		if ((pkg->ipkg == NULL) ||
Timo Teräs's avatar
Timo Teräs committed
275 276
		    ((ns->solver_flags_local | ns->solver_flags_inherited |
		      ss->solver_flags) & APK_SOLVERF_REINSTALL)) {
277 278
			/* and it's not available, we can't use it */
			if (!pkg_available(ss->db, pkg))
279
				ps->conflicts = 1024;
280 281 282
		}
	}

Timo Teräs's avatar
Timo Teräs committed
283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312
	ns->availability_checked = 1;
}

static void foreach_locked_reverse_dependency(
	struct apk_name *name,
	void (*cb)(struct apk_package *rdepend, void *ctx), void *ctx)
{
	int i, j;

	if (name == NULL)
		return;

	for (i = 0; i < name->rdepends->num; i++) {
		struct apk_name *name0 = name->rdepends->item[i];
		struct apk_name_state *ns0 = name_to_ns(name0);
		struct apk_package *pkg0 = ns0->chosen;

		if (!ns0->locked || ns0->chosen == NULL)
			continue;

		for (j = 0; j < pkg0->depends->num; j++) {
			struct apk_dependency *dep = &pkg0->depends->item[j];
			if (dep->name == name)
				break;
		}
		if (j >= pkg0->depends->num)
			continue;

		cb(pkg0, ctx);
	}
313 314
}

315 316
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))
317
{
318
	int i;
319
	for (i = 0; i < deps->num; i++)
320
		func(ss, &deps->item[i]);
321 322
}

Timo Teräs's avatar
Timo Teräs committed
323
static int compare_package_preference(unsigned short solver_flags,
324
				      unsigned int preferred_repos,
Timo Teräs's avatar
Timo Teräs committed
325 326 327
				      struct apk_package *pkgA,
				      struct apk_package *pkgB)
{
328 329 330 331 332 333
	/* specified on command line directly */
	if (pkgA->filename && !pkgB->filename)
		return 1;
	if (pkgB->filename && !pkgA->filename)
		return -1;

334 335 336 337 338 339 340 341
	if (solver_flags & APK_SOLVERF_PREFER_TAG) {
		/* preferred repository pinning */
		if ((pkgA->repos & preferred_repos) && !(pkgB->repos & preferred_repos))
			return 1;
		if ((pkgB->repos & preferred_repos) && !(pkgA->repos & preferred_repos))
			return -1;
	} else {
		/* preferred repository pinning */
342 343
		if ((pkgA->ipkg || (pkgA->repos & preferred_repos)) &&
		    !(pkgB->ipkg || (pkgB->repos & preferred_repos)))
344
			return 1;
345 346
		if ((pkgB->ipkg || (pkgB->repos & preferred_repos)) &&
		    !(pkgA->ipkg || (pkgA->repos & preferred_repos)))
347 348
			return -1;
	}
349

Timo Teräs's avatar
Timo Teräs committed
350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373
	if (solver_flags & APK_SOLVERF_AVAILABLE) {
		if (pkgA->repos != 0 && pkgB->repos == 0)
			return 1;
		if (pkgB->repos != 0 && pkgA->repos == 0)
			return -1;
	}

	if (!(solver_flags & APK_SOLVERF_UPGRADE)) {
		/* not upgrading, prefer the installed package */
		if (pkgA->ipkg != NULL && pkgB->ipkg == NULL)
			return 1;
		if (pkgB->ipkg != NULL && pkgA->ipkg == NULL)
			return -1;
	}

	/* upgrading, or neither of the package is installed, so
	 * we just fall back comparing to versions */
	switch (apk_pkg_version_compare(pkgA, pkgB)) {
	case APK_VERSION_GREATER:
		return 1;
	case APK_VERSION_LESS:
		return -1;
	}

374 375 376 377 378 379
	/* upgrading, prefer the installed package */
	if (pkgA->ipkg != NULL && pkgB->ipkg == NULL)
		return 1;
	if (pkgB->ipkg != NULL && pkgA->ipkg == NULL)
		return -1;

Timo Teräs's avatar
Timo Teräs committed
380 381 382 383 384 385 386
	/* prefer the one with lowest available repository */
	return ffsl(pkgB->repos) - ffsl(pkgA->repos);
}

static int get_preference(struct apk_solver_state *ss,
			  struct apk_package *pkg,
			  int installable_only)
387 388
{
	struct apk_name *name = pkg->name;
389
	struct apk_name_state *ns = name_to_ns(name);
Timo Teräs's avatar
Timo Teräs committed
390 391 392
	unsigned short name_flags = ns->solver_flags_local
		| ns->solver_flags_inherited
		| ss->solver_flags;
393
	unsigned int preferred_repos = ns->preferred_repos;
Timo Teräs's avatar
Timo Teräs committed
394 395
	unsigned short preference = 0;
	int i;
396

397 398 399
	if (preferred_repos == 0)
		preferred_repos = ss->db->repo_tags[0].allowed_repos;

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

Timo Teräs's avatar
Timo Teräs committed
404
		if (pkg0 == pkg || ps0 == NULL)
405 406
			continue;

407 408 409
		if (compare_package_preference(name_flags,
					       preferred_repos,
					       pkg, pkg0) < 0) {
Timo Teräs's avatar
Timo Teräs committed
410 411 412 413 414 415
			if (installable_only) {
				if (ss->topology_position > pkg0->topology_hard &&
				    !(ps0->flags & APK_PKGSTF_DECIDED))
					preference++;
			} else
				preference++;
416 417 418
		}
	}

Timo Teräs's avatar
Timo Teräs committed
419
	return preference;
420 421
}

422 423
static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg)
{
Timo Teräs's avatar
Timo Teräs committed
424
	struct apk_name_state *ns;
425 426 427 428 429
	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
430
		ns = name_to_ns(dep->name);
Timo Teräs's avatar
Timo Teräs committed
431
		if (!ns->locked || !apk_dep_is_satisfied(dep, ns->chosen))
432 433 434 435 436 437
			missing++;
	}

	return missing;
}

Timo Teräs's avatar
Timo Teräs committed
438
static int update_name_state(struct apk_solver_state *ss, struct apk_name *name)
439
{
Timo Teräs's avatar
Timo Teräs committed
440
	struct apk_name_state *ns = name_to_ns(name);
441 442
	struct apk_package *best_pkg = NULL, *preferred_pkg = NULL;
	struct apk_package_state *preferred_ps = NULL;
443
	unsigned int best_topology = 0;
444
	unsigned int allowed_repos = ns->allowed_repos | ss->db->repo_tags[0].allowed_repos;
445 446 447 448
	unsigned int preferred_repos = ns->preferred_repos;
	unsigned short name_flags = ns->solver_flags_local
		| ns->solver_flags_inherited
		| ss->solver_flags;
449
	int i, options = 0, skipped_options = 0;
450

451 452 453
	subscore(&ss->minimum_penalty, &ns->minimum_penalty);
	ns->minimum_penalty = (struct apk_score) { 0, 0 };

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

458
		if (ps0 == NULL ||
459
		    pkg0->topology_hard >= ss->topology_position ||
460
		    (ps0->flags & APK_PKGSTF_DECIDED))
461 462
			continue;

Timo Teräs's avatar
Timo Teräs committed
463 464 465 466 467 468
		if ((pkg0->repos != 0) && (pkg0->ipkg == NULL) && (pkg0->filename == NULL) &&
		    !(pkg0->repos & allowed_repos)) {
			skipped_options++;
			continue;
		}

469 470 471 472 473 474 475 476 477 478
		if ((preferred_pkg == NULL) ||
		    (ps0->conflicts < preferred_ps->conflicts) ||
		    (ps0->conflicts == preferred_ps->conflicts &&
		     compare_package_preference(name_flags,
					        preferred_repos,
					        pkg0, preferred_pkg) > 0)) {
			preferred_pkg = pkg0;
			preferred_ps = ps0;
		}

479 480 481 482 483 484
		if (ns->requirers == 0 && ns->install_ifs != 0 &&
		    install_if_missing(ss, pkg0)) {
			skipped_options++;
			continue;
		}

485
		options++;
486 487 488
		if (ps0->topology_soft < ss->topology_position &&
		    ps0->topology_soft > best_topology)
			best_pkg = pkg0, best_topology = ps0->topology_soft;
489 490
		else if (pkg0->topology_hard > best_topology)
			best_pkg = pkg0, best_topology = pkg0->topology_hard;
491
	}
492

493
	if (skipped_options == 0 && options == 0) {
Timo Teräs's avatar
Timo Teräs committed
494 495 496 497
		if (!ns->locked) {
			ss->score.unsatisfiable += ns->requirers;
			ss->score.preference += name->pkgs->num;
		}
498 499 500 501 502 503
		ns->locked = 1;
		ns->chosen = NULL;
	} else {
		ns->locked = 0;
	}

Timo Teräs's avatar
Timo Teräs committed
504
	if (ns->requirers == 0 && ns->install_ifs == 0) {
505 506 507 508 509
		if (list_hashed(&ns->unsolved_list)) {
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
			ns->chosen = NULL;
		}
510 511
		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);
512 513 514
	} else {
		if (!list_hashed(&ns->unsolved_list))
			list_add(&ns->unsolved_list, &ss->unsolved_list_head);
515
		if (!ns->locked) {
Timo Teräs's avatar
Timo Teräs committed
516
			ns->chosen = best_pkg;
517 518 519 520 521 522
			if (preferred_pkg != NULL &&
			    preferred_ps->conflicts < ns->requirers) {
				ns->minimum_penalty = (struct apk_score) {
					.unsatisfiable = preferred_ps->conflicts,
					.preference = get_preference(ss, preferred_pkg, FALSE),
				};
523 524 525 526 527
				dbg_printf("%s: min.penalty for name {%d, %d} from pkg " PKG_VER_FMT "\n",
					   name->name,
					   ns->minimum_penalty.unsatisfiable,
					   ns->minimum_penalty.preference,
					   PKG_VER_PRINTF(preferred_pkg));
528 529 530 531 532 533 534 535
			} else {
				ns->minimum_penalty = (struct apk_score) {
					.unsatisfiable = ns->requirers,
					.preference = name->pkgs->num,
				};
			}
			addscore(&ss->minimum_penalty, &ns->minimum_penalty);
		}
536 537 538
		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);
539 540
	}

541
	return options + skipped_options;
542 543
}

544 545 546 547
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
548
		struct apk_name_state *ns = ns = name_to_ns(pkg->name);
549 550 551

		dbg_printf("trigger_install_if: " PKG_VER_FMT " triggered\n",
			   PKG_VER_PRINTF(pkg));
552
		ns->topology_last_touched = ss->topology_position;
553
		ns->install_ifs++;
Timo Teräs's avatar
Timo Teräs committed
554
		update_name_state(ss, pkg->name);
555 556 557 558 559 560 561
	}
}

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
562
		struct apk_name_state *ns = name_to_ns(pkg->name);
563 564 565

		dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n",
			   PKG_VER_PRINTF(pkg));
566
		ns->topology_last_touched = ss->topology_position;
567
		ns->install_ifs--;
Timo Teräs's avatar
Timo Teräs committed
568
		update_name_state(ss, pkg->name);
569 570 571
	}
}

572 573 574
static void apply_decision(struct apk_solver_state *ss,
			   struct apk_package *pkg,
			   struct apk_package_state *ps)
575
{
Timo Teräs's avatar
Timo Teräs committed
576
	struct apk_name_state *ns = name_to_ns(pkg->name);
577 578 579 580 581

	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) {
582 583 584
		subscore(&ss->minimum_penalty, &ns->minimum_penalty);
		ns->minimum_penalty = (struct apk_score) { 0, 0 };

585
		ss->assigned_names++;
Timo Teräs's avatar
Timo Teräs committed
586 587
		ss->score.unsatisfiable += ps->conflicts;
		ss->score.preference += get_preference(ss, pkg, FALSE);
588
		ns->chosen = pkg;
Timo Teräs's avatar
Timo Teräs committed
589
		ns->locked = 1;
590 591 592 593 594 595 596

		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);
597
		foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
598
	} else {
Timo Teräs's avatar
Timo Teräs committed
599
		update_name_state(ss, pkg->name);
600 601 602 603 604 605 606
	}
}

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
607
	struct apk_name_state *ns = name_to_ns(pkg->name);
608 609 610 611

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

612 613 614
	if (ps->flags & APK_PKGSTF_INSTALLIF)
		ss->topology_position = ps->topology_soft;
	else
615
		ss->topology_position = pkg->topology_hard;
616

617 618
	if (ps->flags & APK_PKGSTF_INSTALL) {
		ss->assigned_names--;
619 620

		foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
621 622
		foreach_dependency(ss, pkg->depends, undo_constraint);

Timo Teräs's avatar
Timo Teräs committed
623
		ns->locked = 0;
624
		ns->chosen = NULL;
625
	}
626

Timo Teräs's avatar
Timo Teräs committed
627
	ss->score = ps->saved_score;
Timo Teräs's avatar
Timo Teräs committed
628
	update_name_state(ss, pkg->name);
629 630
}

631 632
static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
			  int flags)
633
{
634
	struct apk_package_state *ps = pkg_to_ps(pkg);
635 636

	ps->backtrack = ss->latest_decision;
637
	ps->flags = flags | APK_PKGSTF_DECIDED;
Timo Teräs's avatar
Timo Teräs committed
638
	ps->saved_score = ss->score;
639 640 641 642 643 644 645

	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;
646
		ss->topology_position = pkg->topology_hard;
647
	}
648
	ss->latest_decision = pkg;
649

650 651 652 653
	dbg_printf("push_decision: adding new BRANCH at topology_position %d (score: unsatisfied %d, preference %d)\n",
		   ss->topology_position,
		   ss->score.unsatisfiable,
		   ss->score.preference);
654

655 656 657 658
	if (ps->flags & APK_PKGSTF_INSTALLIF)
		dbg_printf("triggers due to " PKG_VER_FMT "\n",
			   PKG_VER_PRINTF(pkg));

659
	apply_decision(ss, pkg, ps);
660 661 662 663 664 665 666
}

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

667
	while (ss->latest_decision != NULL) {
668
		pkg = ss->latest_decision;
669
		ps = pkg_to_ps(pkg);
670 671 672 673

		if (ps->flags & APK_PKGSTF_ALT_BRANCH) {
			dbg_printf("next_branch: undo decision at topology_position %d\n",
				   ss->topology_position);
674
			ps->flags &= ~(APK_PKGSTF_ALT_BRANCH | APK_PKGSTF_DECIDED);
Timo Teräs's avatar
Timo Teräs committed
675 676
			undo_decision(ss, pkg, ps);

677
			ss->latest_decision = ps->backtrack;
Timo Teräs's avatar
Timo Teräs committed
678
			ss->refresh_name_states = 1;
679
		} else {
680 681
			undo_decision(ss, pkg, ps);

682 683 684 685 686 687
			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;

688 689
			apply_decision(ss, pkg, ps);
			return 0;
690 691
		}
	}
692 693 694

	dbg_printf("next_branch: no more branches\n");
	return 1;
695 696
}

Timo Teräs's avatar
Timo Teräs committed
697 698 699 700 701 702 703 704
static void inherit_name_state(struct apk_name *to, struct apk_name *from)
{
	struct apk_name_state *tns = name_to_ns(to);
	struct apk_name_state *fns = name_to_ns(from);

	tns->solver_flags_inherited |=
		fns->solver_flags_inherited |
		(fns->solver_flags_local & fns->solver_flags_local_mask);
705
	tns->allowed_repos |= fns->allowed_repos;
Timo Teräs's avatar
Timo Teräs committed
706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721
}

static void inherit_name_state_wrapper(struct apk_package *rdepend, void *ctx)
{
	struct apk_name *name = (struct apk_name *) ctx;
	inherit_name_state(name, rdepend->name);
}

static int has_inherited_state(struct apk_name *name)
{
	struct apk_name_state *ns = name_to_ns(name);

	if (name == NULL)
		return 0;
	if (ns->solver_flags_inherited || (ns->solver_flags_local & ns->solver_flags_local_mask))
		return 1;
722 723
	if (ns->allowed_repos)
		return 1;
Timo Teräs's avatar
Timo Teräs committed
724 725 726 727 728 729 730 731
	return 0;
}

static void recalculate_inherted_name_state(struct apk_name *name)
{
	struct apk_name_state *ns = name_to_ns(name);

	ns->solver_flags_inherited = 0;
732
	ns->allowed_repos = 0;
Timo Teräs's avatar
Timo Teräs committed
733 734 735
	foreach_locked_reverse_dependency(name, inherit_name_state_wrapper, name);
}

736
static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
737 738
{
	struct apk_name *name = dep->name;
Timo Teräs's avatar
Timo Teräs committed
739
	struct apk_name_state *ns = name_to_ns(name);
740
	int i;
741

742
	prepare_name(ss, name, ns);
743

Timo Teräs's avatar
Timo Teräs committed
744
	if (ns->locked) {
Timo Teräs's avatar
Timo Teräs committed
745 746 747 748 749 750
		if (ns->chosen)
			dbg_printf("%s: locked to " PKG_VER_FMT " already\n",
				   dep->name->name, PKG_VER_PRINTF(ns->chosen));
		else
			dbg_printf("%s: locked to empty\n",
				   dep->name->name);
751
		if (!apk_dep_is_satisfied(dep, ns->chosen))
Timo Teräs's avatar
Timo Teräs committed
752
			ss->score.unsatisfiable++;
753 754 755
		return;
	}

756 757 758 759 760 761 762 763 764 765
	if (dep->repository_tag) {
		unsigned int allowed_repos;

		dbg_printf("%s: enabling repository tag %d\n",
			   dep->name->name, dep->repository_tag);
		allowed_repos = ss->db->repo_tags[dep->repository_tag].allowed_repos;
		ns->allowed_repos |= allowed_repos;
		ns->preferred_repos |= allowed_repos;
	}

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

770
		if (ps0 == NULL ||
771
		    pkg0->topology_hard >= ss->topology_position)
772 773 774 775 776 777 778 779 780 781
			continue;

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

Timo Teräs's avatar
Timo Teräs committed
782 783 784
	if (ss->latest_decision != NULL)
		inherit_name_state(name, ss->latest_decision->name);

785
	if (!dep->optional)
Timo Teräs's avatar
Timo Teräs committed
786
		ns->requirers++;
787 788
	ns->topology_last_touched = ss->topology_position;

Timo Teräs's avatar
Timo Teräs committed
789
	update_name_state(ss, name);
790 791
}

792
static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
793 794
{
	struct apk_name *name = dep->name;
Timo Teräs's avatar
Timo Teräs committed
795
	struct apk_name_state *ns = name_to_ns(name);
796 797
	int i;

Timo Teräs's avatar
Timo Teräs committed
798
	if (ns->locked) {
799 800 801 802 803 804 805
		if (ns->chosen != NULL) {
			dbg_printf(PKG_VER_FMT " selected already for %s\n",
				   PKG_VER_PRINTF(ns->chosen), dep->name->name);
		} else {
			dbg_printf("%s selected to not be satisfied\n",
				   dep->name->name);
		}
806 807
		return;
	}
808 809 810

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

813
		if (pkg0->topology_hard >= ss->topology_position)
814 815 816 817 818 819 820 821 822 823
			continue;

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

Timo Teräs's avatar
Timo Teräs committed
824 825 826
	if (ss->latest_decision && has_inherited_state(ss->latest_decision->name))
		recalculate_inherted_name_state(name);

827
	if (!dep->optional)
Timo Teräs's avatar
Timo Teräs committed
828
		ns->requirers--;
829 830
	ns->topology_last_touched = ss->topology_position;

Timo Teräs's avatar
Timo Teräs committed
831
	update_name_state(ss, name);
832 833 834 835
}

static int expand_branch(struct apk_solver_state *ss)
{
836 837
	struct apk_name_state *ns;
	struct apk_package *pkg0 = NULL;
838
	unsigned int topology0 = 0;
Timo Teräs's avatar
Timo Teräs committed
839
	int flags;
840 841 842

	/* FIXME: change unsolved_list to a priority queue */
	list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
Timo Teräs's avatar
Timo Teräs committed
843 844 845
		if (ss->refresh_name_states)
			update_name_state(ss, ns->name);

846 847 848 849 850 851 852 853 854
		/* 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;
855 856
		else if (ns->chosen->topology_hard > topology0)
			pkg0 = ns->chosen, topology0 = pkg0->topology_hard;
857
	}
Timo Teräs's avatar
Timo Teräs committed
858
	ss->refresh_name_states = 0;
859
	if (pkg0 == NULL) {
860
		list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
861 862 863 864 865
			if (ns->locked)
				continue;

			ss->score.unsatisfiable += ns->requirers;
			ss->score.preference += ns->name->pkgs->num;
866 867
		}

868
		dbg_printf("expand_branch: list is empty (%d unsatisfied)\n",
Timo Teräs's avatar
Timo Teräs committed
869
			   ss->score.unsatisfiable);
870

871 872
		return 1;
	}
873

874 875
	/* someone needs to provide this name -- find next eligible
	 * provider candidate */
Timo Teräs's avatar
Timo Teräs committed
876
	ns = name_to_ns(pkg0->name);
877
	dbg_printf("expand_branch: %s\n", pkg0->name->name);
878

Timo Teräs's avatar
Timo Teräs committed
879 880 881 882 883
	if (get_preference(ss, pkg0, TRUE) == 0)
		flags = APK_PKGSTF_INSTALL;
	else
		flags = APK_PKGSTF_NOINSTALL;
	push_decision(ss, pkg0, flags);
884 885 886 887 888 889 890 891 892 893 894 895 896 897 898

	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) {
899
		ps = pkg_to_ps(pkg);
900 901 902
		if (ps->flags & APK_PKGSTF_INSTALL) {
			if (i >= ss->assigned_names)
				abort();
903
			ss->best_solution->item[i++] = pkg;
904
		}
905 906 907 908 909 910 911

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

		pkg = ps->backtrack;
	}
912
	apk_package_array_resize(&ss->best_solution, i);
Timo Teräs's avatar
Timo Teräs committed
913
	ss->best_score = ss->score;
914 915 916 917 918 919 920 921
}

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

Timo Teräs's avatar
Timo Teräs committed
924 925 926 927 928 929
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) {
930
		if (c2->newpkg == NULL) {
Timo Teräs's avatar
Timo Teräs committed
931
			/* both deleted - reverse topology order */
932
			return	c2->oldpkg->topology_hard -
933
				c1->oldpkg->topology_hard;
934
		}
Timo Teräs's avatar
Timo Teräs committed
935 936

		/* c1 deleted, c2 installed -> c2 first*/
937
		return 1;
Timo Teräs's avatar
Timo Teräs committed
938 939 940
	}
	if (c2->newpkg == NULL)
		/* c1 installed, c2 deleted -> c1 first*/
941
		return -1;
Timo Teräs's avatar
Timo Teräs committed
942

943
	return	c1->newpkg->topology_hard -
944
		c2->newpkg->topology_hard;
Timo Teräs's avatar
Timo Teräs committed
945 946 947 948
}

static int generate_changeset(struct apk_database *db,
			      struct apk_package_array *solution,
949 950
			      struct apk_changeset *changeset,
			      unsigned short solver_flags)
Timo Teräs's avatar
Timo Teräs committed
951 952 953 954 955 956 957 958 959 960
{
	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];
Timo Teräs's avatar
Timo Teräs committed
961
		ns = name_to_ns(pkg->name);
Timo Teräs's avatar
Timo Teräs committed
962 963
		ns->chosen = pkg;
		ns->in_changeset = 1;
Timo Teräs's avatar
Timo Teräs committed
964
		if ((pkg->ipkg == NULL) ||
Timo Teräs's avatar
Timo Teräs committed
965 966
		    ((ns->solver_flags_local | ns->solver_flags_inherited |
		      solver_flags) & APK_SOLVERF_REINSTALL))
Timo Teräs's avatar
Timo Teräs committed
967 968 969 970 971
			num_installs++;
	}
	list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
		name = ipkg->pkg->name;
		ns = name_to_ns(name);
Timo Teräs's avatar
Timo Teräs committed
972
		if ((ns->chosen == NULL) || !ns->in_changeset)
Timo Teräs's avatar
Timo Teräs committed
973 974 975 976 977 978 979 980
			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);
Timo Teräs's avatar
Timo Teräs committed
981
		if ((ns->chosen == NULL) || !ns->in_changeset) {
Timo Teräs's avatar
Timo Teräs committed
982 983 984 985 986 987 988
			changeset->changes->item[ci].oldpkg = ipkg->pkg;
			ci++;
		}
	}
	for (i = 0; i < solution->num; i++) {
		pkg = solution->item[i];
		name = pkg->name;
Timo Teräs's avatar
Timo Teräs committed
989
		ns = name_to_ns(name);
Timo Teräs's avatar
Timo Teräs committed
990 991

		if ((pkg->ipkg == NULL) ||
Timo Teräs's avatar
Timo Teräs committed
992 993
		    ((ns->solver_flags_local | ns->solver_flags_inherited |
		      solver_flags) & APK_SOLVERF_REINSTALL)) {
Timo Teräs's avatar
Timo Teräs committed
994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023
			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;
}

1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034
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;
}

1035
void apk_solver_set_name_flags(struct apk_name *name,
Timo Teräs's avatar
Timo Teräs committed
1036 1037
			       unsigned short solver_flags,
			       unsigned short solver_flags_inheritable)
1038 1039
{
	struct apk_name_state *ns = name_to_ns(name);
Timo Teräs's avatar
Timo Teräs committed
1040 1041
	ns->solver_flags_local = solver_flags;
	ns->solver_flags_local_mask = solver_flags_inheritable;
1042 1043
}

1044 1045 1046 1047 1048 1049
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
1050 1051 1052 1053 1054
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)
1055 1056
{
	struct apk_solver_state *ss;
Timo Teräs's avatar
Timo Teräs committed
1057
	struct apk_installed_package *ipkg;
1058
	struct apk_score zero_score;
1059
	int i, r;
1060 1061 1062

	ss = calloc(1, sizeof(struct apk_solver_state));
	ss->db = db;
Timo Teräs's avatar
Timo Teräs committed
1063
	ss->solver_flags = solver_flags;
1064
	ss->topology_position = -1;
Timo Teräs's avatar
Timo Teräs committed
1065
	ss->best_score = (struct apk_score){ .unsatisfiable = -1, .preference = -1 };
1066
	list_init(&ss->unsolved_list_head);
1067 1068 1069

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

1073
	foreach_dependency(ss, world, apply_constraint);
1074 1075
	zero_score = ss->score;

1076 1077 1078
	dbg_printf("solver_solve: zero score: %d unsatisfiable, %d preference\n",
		   zero_score.unsatisfiable,
		   zero_score.preference);
1079

1080 1081
	do {
		if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) < 0) {
1082 1083
			r = expand_branch(ss);
			if (r) {
Timo Teräs's avatar
Timo Teräs committed
1084 1085 1086 1087 1088 1089 1090
				dbg_printf("solution with: %d unsatisfiable, %d preference\n",
					   ss->score.unsatisfiable,
					   ss->score.preference);

				if (cmpscore(&ss->score, &ss->best_score) < 0)
					record_solution(ss);

1091
				if (cmpscore(&zero_score, &ss->score) >= 0) {
1092 1093 1094 1095 1096 1097 1098 1099 1100 1101
					/* found solution - it is optimal because we permutate
					 * each preferred local option first, and permutations
					 * happen in topologally sorted order. */
					r = 0;
					break;
				}
				r = next_branch(ss);
			}
		} else {
			r = next_branch(ss);
1102
		}
1103
	} while (r == 0);
1104 1105

	/* collect packages */
1106 1107 1108 1109 1110
	if (changeset != NULL) {
		generate_changeset(db, ss->best_solution, changeset,
				   ss->solver_flags);
	}
	if (solution != NULL) {
1111 1112
		qsort(ss->best_solution->item, ss->best_solution->num,
		      sizeof(struct apk_package *), compare_package_name);
Timo Teräs's avatar
Timo Teräs committed
1113
		*solution = ss->best_solution;
1114
	} else {
Timo Teräs's avatar
Timo Teräs committed
1115
		apk_package_array_free(&ss->best_solution);
1116 1117
	}
	r = ss->best_score.unsatisfiable;
1118
	apk_solver_free(db);
1119 1120 1121 1122 1123
	free(ss);

	return r;
}

Timo Teräs's avatar
Timo Teräs committed
1124 1125 1126
static void print_change(struct apk_database *db,
			 struct apk_change *change,
			 int cur, int total)
1127
{
Timo Teräs's avatar
Timo Teräs committed
1128 1129 1130 1131
	struct apk_name *name;
	struct apk_package *oldpkg = change->oldpkg;
	struct apk_package *newpkg = change->newpkg;
	const char *msg = NULL;
1132 1133
	char status[32], n[512], *nameptr;
	int r, tag;
1134

Timo Teräs's avatar
Timo Teräs committed
1135
	snprintf(status, sizeof(status), "(%i/%i)", cur+1, total);
1136
	status[sizeof(status) - 1] = 0;
1137

1138
	if (newpkg != NULL) {
Timo Teräs's avatar
Timo Teräs committed
1139
		name = newpkg->name;
1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154
		tag = apk_db_get_tag_id_by_repos(db, newpkg->repos);
	} else {
		name = oldpkg->name;
		tag = apk_db_get_tag_id_by_repos(db, oldpkg->repos);
	}

	if (tag > 0) {
		snprintf(n, sizeof(n), "%s@" BLOB_FMT,
			 name->name,
			 BLOB_PRINTF(*db->repo_tags[tag].name));
		n[sizeof(n) - 1] = 0;
		nameptr = n;
	} else {
		nameptr = name->name;
	}
Timo Teräs's avatar
Timo Teräs committed
1155 1156 1157

	if (oldpkg == NULL) {
		apk_message("%s Installing %s (" BLOB_FMT ")",
1158
			    status, nameptr,
Timo Teräs's avatar
Timo Teräs committed
1159 1160 1161
			    BLOB_PRINTF(*newpkg->version));
	} else if (newpkg == NULL) {
		apk_message("%s Purging %s (" BLOB_FMT ")",
1162
			    status, nameptr,
Timo Teräs's avatar
Timo Teräs committed
1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180
			    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 ")",
1181
			    status, msg, nameptr,
Timo Teräs's avatar
Timo Teräs committed
1182 1183
			    BLOB_PRINTF(*oldpkg->version),
			    BLOB_PRINTF(*newpkg->version));
1184
	}
Timo Teräs's avatar
Timo Teräs committed
1185
}
1186

Timo Teräs's avatar
Timo Teräs committed
1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214
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);
1215