solver.c 35.5 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
#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
29 30 31 32 33 34 35 36
#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;
};
37 38 39

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

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

	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
60
	unsigned int in_changeset : 1;
61 62 63 64
};

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

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

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

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

80 81 82 83
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);
84

Timo Teräs's avatar
Timo Teräs committed
85
static struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
86 87 88 89
{
	return (struct apk_package_state*) pkg->state_ptr;
}

Timo Teräs's avatar
Timo Teräs committed
90 91
static struct apk_name_state *name_to_ns(struct apk_name *name)
{
Timo Teräs's avatar
Timo Teräs committed
92 93 94 95 96 97 98 99 100 101
	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
102 103
}

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

115 116 117
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))
118 119 120
{
	int i, j;

121 122 123
	/* And sort the main dependencies */
	for (i = 0; i < depends->num; i++) {
		struct apk_dependency *dep = &depends->item[i];
124 125 126 127
		struct apk_name *name0 = dep->name;

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

129
			/* conflict depends on all to be not installed */
130
			if (!apk_dep_is_satisfied(dep, pkg0))
131
				continue;
132 133

			cb(ss, pkg0);
134 135
		}
	}
136
}
137

138 139 140 141 142 143 144 145 146 147 148 149
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);
150

151 152 153 154 155 156
		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 &&
157
				    apk_dep_is_satisfied(dep, pkg))
158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176
					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);
177
	if (ps->topology_soft)
178
		return;
179
	pkg->topology_hard = -1;
180
	ps->topology_soft = -1;
181 182 183 184 185

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

186
	ps->topology_soft = pkg->topology_hard = ++ss->num_topology_positions;
187
	dbg_printf(PKG_VER_FMT ": topology_hard=%d\n",
188
		   PKG_VER_PRINTF(pkg), pkg->topology_hard);
189 190 191 192 193 194 195 196 197
}

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);
198
	if (ps->topology_soft != pkg->topology_hard)
199
		return;
Timo Teräs's avatar
Timo Teräs committed
200
	ps->topology_soft = -1;
201 202 203 204 205 206 207 208 209

	/* 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);
210 211 212 213 214 215 216
}

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

	for (i = 0; i < name->pkgs->num; i++)
217
		sort_soft_dependencies(ss, name->pkgs->item[i]);
218 219
}

220 221 222 223 224
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
225
	if (ns->availability_checked)
226 227 228 229
		return;

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

		/* if package is needed for (re-)install */
Timo Teräs's avatar
Timo Teräs committed
234
		if ((pkg->ipkg == NULL) ||
Timo Teräs's avatar
Timo Teräs committed
235 236
		    ((ns->solver_flags_local | ns->solver_flags_inherited |
		      ss->solver_flags) & APK_SOLVERF_REINSTALL)) {
237 238
			/* and it's not available, we can't use it */
			if (!pkg_available(ss->db, pkg))
239
				ps->conflicts = 1024;
240 241 242
		}
	}

Timo Teräs's avatar
Timo Teräs committed
243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272
	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);
	}
273 274
}

275 276
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))
277
{
278
	int i;
279
	for (i = 0; i < deps->num; i++)
280
		func(ss, &deps->item[i]);
281 282
}

Timo Teräs's avatar
Timo Teräs committed
283
static int compare_package_preference(unsigned short solver_flags,
284
				      unsigned int preferred_repos,
Timo Teräs's avatar
Timo Teräs committed
285 286 287
				      struct apk_package *pkgA,
				      struct apk_package *pkgB)
{
288 289 290 291 292 293 294 295
	/* preferred repository pinning */
	if ((pkgA->ipkg || (pkgA->repos & preferred_repos)) &&
	    !(pkgB->ipkg || (pkgB->repos & preferred_repos)))
		return 1;
	if ((pkgB->ipkg || (pkgB->repos & preferred_repos)) &&
	    !(pkgA->ipkg || (pkgA->repos & preferred_repos)))
		return -1;

Timo Teräs's avatar
Timo Teräs committed
296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326
	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;
	}

	/* 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)
327 328
{
	struct apk_name *name = pkg->name;
329
	struct apk_name_state *ns = name_to_ns(name);
Timo Teräs's avatar
Timo Teräs committed
330 331 332
	unsigned short name_flags = ns->solver_flags_local
		| ns->solver_flags_inherited
		| ss->solver_flags;
333
	unsigned int preferred_repos = ns->preferred_repos | ss->db->repo_tags[0].allowed_repos;
Timo Teräs's avatar
Timo Teräs committed
334 335
	unsigned short preference = 0;
	int i;
336

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

Timo Teräs's avatar
Timo Teräs committed
341
		if (pkg0 == pkg || ps0 == NULL)
342 343
			continue;

344 345 346
		if (compare_package_preference(name_flags,
					       preferred_repos,
					       pkg, pkg0) < 0) {
Timo Teräs's avatar
Timo Teräs committed
347 348 349 350 351 352
			if (installable_only) {
				if (ss->topology_position > pkg0->topology_hard &&
				    !(ps0->flags & APK_PKGSTF_DECIDED))
					preference++;
			} else
				preference++;
353 354 355
		}
	}

Timo Teräs's avatar
Timo Teräs committed
356
	return preference;
357 358
}

359 360
static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg)
{
Timo Teräs's avatar
Timo Teräs committed
361
	struct apk_name_state *ns;
362 363 364 365 366
	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
367
		ns = name_to_ns(dep->name);
Timo Teräs's avatar
Timo Teräs committed
368
		if (!ns->locked || !apk_dep_is_satisfied(dep, ns->chosen))
369 370 371 372 373 374
			missing++;
	}

	return missing;
}

Timo Teräs's avatar
Timo Teräs committed
375
static int update_name_state(struct apk_solver_state *ss, struct apk_name *name)
376
{
Timo Teräs's avatar
Timo Teräs committed
377
	struct apk_name_state *ns = name_to_ns(name);
378 379
	struct apk_package *best_pkg = NULL;
	unsigned int best_topology = 0;
380
	unsigned int allowed_repos = ns->allowed_repos | ss->db->repo_tags[0].allowed_repos;
381
	int i, options = 0, skipped_options = 0;
382 383 384

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

387
		if (ps0 == NULL ||
388
		    pkg0->topology_hard >= ss->topology_position ||
389
		    ((pkg0->repos != 0) && (pkg0->ipkg == NULL) && !(pkg0->repos & allowed_repos)) ||
390
		    (ps0->flags & APK_PKGSTF_DECIDED))
391 392
			continue;

393 394 395 396 397 398
		if (ns->requirers == 0 && ns->install_ifs != 0 &&
		    install_if_missing(ss, pkg0)) {
			skipped_options++;
			continue;
		}

399
		options++;
400 401 402
		if (ps0->topology_soft < ss->topology_position &&
		    ps0->topology_soft > best_topology)
			best_pkg = pkg0, best_topology = ps0->topology_soft;
403 404
		else if (pkg0->topology_hard > best_topology)
			best_pkg = pkg0, best_topology = pkg0->topology_hard;
405
	}
406

407
	if (skipped_options == 0 && options == 0) {
Timo Teräs's avatar
Timo Teräs committed
408 409 410 411
		if (!ns->locked) {
			ss->score.unsatisfiable += ns->requirers;
			ss->score.preference += name->pkgs->num;
		}
412 413 414 415 416 417
		ns->locked = 1;
		ns->chosen = NULL;
	} else {
		ns->locked = 0;
	}

Timo Teräs's avatar
Timo Teräs committed
418
	if (ns->requirers == 0 && ns->install_ifs == 0) {
419 420 421 422 423
		if (list_hashed(&ns->unsolved_list)) {
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
			ns->chosen = NULL;
		}
424 425
		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);
426
	} else {
427 428 429
		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);
430 431
		if (!list_hashed(&ns->unsolved_list))
			list_add(&ns->unsolved_list, &ss->unsolved_list_head);
432
		ns->chosen = best_pkg;
433 434
	}

435
	return options + skipped_options;
436 437
}

438 439 440 441
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
442
		struct apk_name_state *ns = ns = name_to_ns(pkg->name);
443 444 445 446

		dbg_printf("trigger_install_if: " PKG_VER_FMT " triggered\n",
			   PKG_VER_PRINTF(pkg));
		ns->install_ifs++;
Timo Teräs's avatar
Timo Teräs committed
447
		update_name_state(ss, pkg->name);
448 449 450 451 452 453 454
	}
}

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
455
		struct apk_name_state *ns = name_to_ns(pkg->name);
456 457 458 459

		dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n",
			   PKG_VER_PRINTF(pkg));
		ns->install_ifs--;
Timo Teräs's avatar
Timo Teräs committed
460
		update_name_state(ss, pkg->name);
461 462 463
	}
}

464 465 466
static void apply_decision(struct apk_solver_state *ss,
			   struct apk_package *pkg,
			   struct apk_package_state *ps)
467
{
Timo Teräs's avatar
Timo Teräs committed
468
	struct apk_name_state *ns = name_to_ns(pkg->name);
469 470 471 472 473 474

	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++;
Timo Teräs's avatar
Timo Teräs committed
475 476
		ss->score.unsatisfiable += ps->conflicts;
		ss->score.preference += get_preference(ss, pkg, FALSE);
477
		ns->chosen = pkg;
Timo Teräs's avatar
Timo Teräs committed
478
		ns->locked = 1;
479 480 481 482 483 484 485

		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);
486
		foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
487
	} else {
Timo Teräs's avatar
Timo Teräs committed
488
		update_name_state(ss, pkg->name);
489 490 491 492 493 494 495
	}
}

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
496
	struct apk_name_state *ns = name_to_ns(pkg->name);
497 498 499 500

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

501 502 503
	if (ps->flags & APK_PKGSTF_INSTALLIF)
		ss->topology_position = ps->topology_soft;
	else
504
		ss->topology_position = pkg->topology_hard;
505

506 507
	if (ps->flags & APK_PKGSTF_INSTALL) {
		ss->assigned_names--;
508 509

		foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
510 511
		foreach_dependency(ss, pkg->depends, undo_constraint);

Timo Teräs's avatar
Timo Teräs committed
512
		ns->locked = 0;
513
		ns->chosen = NULL;
514
	}
515

Timo Teräs's avatar
Timo Teräs committed
516
	ss->score = ps->saved_score;
Timo Teräs's avatar
Timo Teräs committed
517
	update_name_state(ss, pkg->name);
518 519
}

520 521
static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
			  int flags)
522
{
523
	struct apk_package_state *ps = pkg_to_ps(pkg);
524 525

	ps->backtrack = ss->latest_decision;
526
	ps->flags = flags | APK_PKGSTF_DECIDED;
Timo Teräs's avatar
Timo Teräs committed
527
	ps->saved_score = ss->score;
528 529 530 531 532 533 534

	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;
535
		ss->topology_position = pkg->topology_hard;
536
	}
537
	ss->latest_decision = pkg;
538

Timo Teräs's avatar
Timo Teräs committed
539 540
	dbg_printf("push_decision: adding new BRANCH at topology_position %d\n",
		   ss->topology_position);
541

542 543 544 545
	if (ps->flags & APK_PKGSTF_INSTALLIF)
		dbg_printf("triggers due to " PKG_VER_FMT "\n",
			   PKG_VER_PRINTF(pkg));

546
	apply_decision(ss, pkg, ps);
547 548 549 550 551 552 553
}

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

554
	while (ss->latest_decision != NULL) {
555
		pkg = ss->latest_decision;
556
		ps = pkg_to_ps(pkg);
557 558 559 560 561
		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);
562 563
			ps->flags &= ~(APK_PKGSTF_ALT_BRANCH | APK_PKGSTF_DECIDED);
			ss->latest_decision = ps->backtrack;
Timo Teräs's avatar
Timo Teräs committed
564
			ss->refresh_name_states = 1;
565 566 567 568 569 570 571
		} 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;

572 573
			apply_decision(ss, pkg, ps);
			return 0;
574 575
		}
	}
576 577 578

	dbg_printf("next_branch: no more branches\n");
	return 1;
579 580
}

Timo Teräs's avatar
Timo Teräs committed
581 582 583 584 585 586 587 588
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);
589
	tns->allowed_repos |= fns->allowed_repos;
Timo Teräs's avatar
Timo Teräs committed
590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605
}

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;
606 607
	if (ns->allowed_repos)
		return 1;
Timo Teräs's avatar
Timo Teräs committed
608 609 610 611 612 613 614 615
	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;
616
	ns->allowed_repos = 0;
Timo Teräs's avatar
Timo Teräs committed
617 618 619
	foreach_locked_reverse_dependency(name, inherit_name_state_wrapper, name);
}

620
static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
621 622
{
	struct apk_name *name = dep->name;
Timo Teräs's avatar
Timo Teräs committed
623
	struct apk_name_state *ns = name_to_ns(name);
624
	int i;
625

626
	prepare_name(ss, name, ns);
627

Timo Teräs's avatar
Timo Teräs committed
628
	if (ns->locked) {
629 630 631
		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))
Timo Teräs's avatar
Timo Teräs committed
632
			ss->score.unsatisfiable++;
633 634 635
		return;
	}

636 637 638 639 640 641 642 643 644 645
	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;
	}

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

650
		if (ps0 == NULL ||
651
		    pkg0->topology_hard >= ss->topology_position)
652 653 654 655 656 657 658 659 660 661
			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
662 663 664
	if (ss->latest_decision != NULL)
		inherit_name_state(name, ss->latest_decision->name);

665
	if (!dep->optional)
Timo Teräs's avatar
Timo Teräs committed
666 667
		ns->requirers++;
	update_name_state(ss, name);
668 669
}

670
static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
671 672
{
	struct apk_name *name = dep->name;
Timo Teräs's avatar
Timo Teräs committed
673
	struct apk_name_state *ns = name_to_ns(name);
674 675
	int i;

Timo Teräs's avatar
Timo Teräs committed
676
	if (ns->locked) {
677 678 679 680 681 682 683
		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);
		}
684 685
		return;
	}
686 687 688

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

691
		if (pkg0->topology_hard >= ss->topology_position)
692 693 694 695 696 697 698 699 700 701
			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
702 703 704
	if (ss->latest_decision && has_inherited_state(ss->latest_decision->name))
		recalculate_inherted_name_state(name);

705
	if (!dep->optional)
Timo Teräs's avatar
Timo Teräs committed
706 707
		ns->requirers--;
	update_name_state(ss, name);
708 709 710 711
}

static int expand_branch(struct apk_solver_state *ss)
{
712 713
	struct apk_name_state *ns;
	struct apk_package *pkg0 = NULL;
714
	unsigned int topology0 = 0;
Timo Teräs's avatar
Timo Teräs committed
715
	int flags;
716 717 718

	/* 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
719 720 721
		if (ss->refresh_name_states)
			update_name_state(ss, ns->name);

722 723 724 725 726 727 728 729 730
		/* 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;
731 732
		else if (ns->chosen->topology_hard > topology0)
			pkg0 = ns->chosen, topology0 = pkg0->topology_hard;
733
	}
Timo Teräs's avatar
Timo Teräs committed
734
	ss->refresh_name_states = 0;
735 736
	if (pkg0 == NULL) {
		dbg_printf("expand_branch: list is empty (%d unsatisfied)\n",
Timo Teräs's avatar
Timo Teräs committed
737
			   ss->score.unsatisfiable);
738 739
		return 1;
	}
740

741 742
	/* someone needs to provide this name -- find next eligible
	 * provider candidate */
Timo Teräs's avatar
Timo Teräs committed
743
	ns = name_to_ns(pkg0->name);
744
	dbg_printf("expand_branch: %s\n", pkg0->name->name);
745

Timo Teräs's avatar
Timo Teräs committed
746 747 748 749 750
	if (get_preference(ss, pkg0, TRUE) == 0)
		flags = APK_PKGSTF_INSTALL;
	else
		flags = APK_PKGSTF_NOINSTALL;
	push_decision(ss, pkg0, flags);
751 752 753 754 755 756 757 758 759 760 761 762 763 764 765

	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) {
766
		ps = pkg_to_ps(pkg);
767 768 769
		if (ps->flags & APK_PKGSTF_INSTALL) {
			if (i >= ss->assigned_names)
				abort();
770
			ss->best_solution->item[i++] = pkg;
771
		}
772 773 774 775 776 777 778

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

		pkg = ps->backtrack;
	}
779
	apk_package_array_resize(&ss->best_solution, i);
Timo Teräs's avatar
Timo Teräs committed
780
	ss->best_score = ss->score;
781 782 783 784 785 786 787 788
}

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

Timo Teräs's avatar
Timo Teräs committed
791 792 793 794 795 796 797 798
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 */
799 800
			return  c2->oldpkg->topology_hard -
				c1->oldpkg->topology_hard;
Timo Teräs's avatar
Timo Teräs committed
801 802 803 804 805 806 807 808

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

809 810
	return  c1->newpkg->topology_hard -
		c2->newpkg->topology_hard;
Timo Teräs's avatar
Timo Teräs committed
811 812 813 814
}

static int generate_changeset(struct apk_database *db,
			      struct apk_package_array *solution,
815 816
			      struct apk_changeset *changeset,
			      unsigned short solver_flags)
Timo Teräs's avatar
Timo Teräs committed
817 818 819 820 821 822 823 824 825 826
{
	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
827
		ns = name_to_ns(pkg->name);
Timo Teräs's avatar
Timo Teräs committed
828 829
		ns->chosen = pkg;
		ns->in_changeset = 1;
Timo Teräs's avatar
Timo Teräs committed
830
		if ((pkg->ipkg == NULL) ||
Timo Teräs's avatar
Timo Teräs committed
831 832
		    ((ns->solver_flags_local | ns->solver_flags_inherited |
		      solver_flags) & APK_SOLVERF_REINSTALL))
Timo Teräs's avatar
Timo Teräs committed
833 834 835 836 837
			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
838
		if ((ns->chosen == NULL) || !ns->in_changeset)
Timo Teräs's avatar
Timo Teräs committed
839 840 841 842 843 844 845 846
			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
847
		if ((ns->chosen == NULL) || !ns->in_changeset) {
Timo Teräs's avatar
Timo Teräs committed
848 849 850 851 852 853 854
			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
855
		ns = name_to_ns(name);
Timo Teräs's avatar
Timo Teräs committed
856 857

		if ((pkg->ipkg == NULL) ||
Timo Teräs's avatar
Timo Teräs committed
858 859
		    ((ns->solver_flags_local | ns->solver_flags_inherited |
		      solver_flags) & APK_SOLVERF_REINSTALL)) {
Timo Teräs's avatar
Timo Teräs committed
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 889
			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;
}

890 891 892 893 894 895 896 897 898 899 900
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;
}

901
void apk_solver_set_name_flags(struct apk_name *name,
Timo Teräs's avatar
Timo Teräs committed
902 903
			       unsigned short solver_flags,
			       unsigned short solver_flags_inheritable)
904 905
{
	struct apk_name_state *ns = name_to_ns(name);
Timo Teräs's avatar
Timo Teräs committed
906 907
	ns->solver_flags_local = solver_flags;
	ns->solver_flags_local_mask = solver_flags_inheritable;
908 909
}

910 911 912 913 914 915
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
916 917 918 919 920 921 922 923 924 925 926 927 928
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;
}

Timo Teräs's avatar
Timo Teräs committed
929 930 931 932 933
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)
934 935
{
	struct apk_solver_state *ss;
Timo Teräs's avatar
Timo Teräs committed
936
	struct apk_installed_package *ipkg;
937
	int i, r;
938 939 940

	ss = calloc(1, sizeof(struct apk_solver_state));
	ss->db = db;
Timo Teräs's avatar
Timo Teräs committed
941
	ss->solver_flags = solver_flags;
942
	ss->topology_position = -1;
Timo Teräs's avatar
Timo Teräs committed
943
	ss->best_score = (struct apk_score){ .unsatisfiable = -1, .preference = -1 };
944
	list_init(&ss->unsolved_list_head);
945 946 947

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

951 952
	foreach_dependency(ss, world, apply_constraint);
	do {
Timo Teräs's avatar
Timo Teräs committed
953
		if (cmpscore(&ss->score, &ss->best_score) < 0) {
954 955
			r = expand_branch(ss);
			if (r) {
Timo Teräs's avatar
Timo Teräs committed
956 957 958 959 960 961 962 963 964
				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);

				if (ss->score.unsatisfiable == 0 &&
				    ss->score.preference == 0) {
965 966 967 968 969 970 971 972 973 974
					/* 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);
975
		}
976
	} while (r == 0);
977 978

	/* collect packages */
Timo Teräs's avatar
Timo Teräs committed
979
	if (ss->best_score.unsatisfiable == 0) {
Timo Teräs's avatar
Timo Teräs committed
980
		if (changeset != NULL)
981 982
			generate_changeset(db, ss->best_solution, changeset,
					   ss->solver_flags);
983
		r = 0;
Timo Teräs's avatar
Timo Teräs committed
984
	} else {
985 986
		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
987
		r = ss->best_score.unsatisfiable;
Timo Teräs's avatar
Timo Teräs committed
988 989 990 991 992 993
	}

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

995
	apk_solver_free(db);
996 997 998 999 1000
	free(ss);

	return r;
}

Timo Teräs's avatar
Timo Teräs committed
1001 1002 1003
static void print_change(struct apk_database *db,
			 struct apk_change *change,
			 int cur, int total)
1004
{
Timo Teräs's avatar
Timo Teräs committed
1005 1006 1007 1008 1009 1010
	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;
1011

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

Timo Teräs's avatar
Timo Teräs committed
1015 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 1042 1043 1044 1045 1046 1047
	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));
1048
	}
Timo Teräs's avatar
Timo Teräs committed
1049
}
1050

Timo Teräs's avatar
Timo Teräs committed
1051 1052 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
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);
1079 1080
}

Timo Teräs's avatar
Timo Teräs committed
1081 1082 1083 1084 1085 1086 1087 1088
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)
1089
{
Timo Teräs's avatar
Timo Teräs committed
1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108
	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;
1109
	struct apk_name *name;
1110
	struct apk_indent indent = { .indent = 2 };
Timo Teräs's avatar
Timo Teräs committed
1111
	int match = 0, i;
1112

Timo Teräs's avatar
Timo Teräs committed
1113 1114 1115 1116 1117
	for (i = 0; i < changeset->changes->num; i++) {
		change = &changeset->changes->item[i];
		if (!cmp(change))
			continue;
		if (match == 0)
1118
			printf("%s:\n", msg);
Timo Teräs's avatar
Timo Teräs committed
1119 1120 1121 1122 1123 1124 1125
		if (change->newpkg != NULL)
			name = change->newpkg->name;
		else
			name = change->oldpkg->name;

		apk_print_indented(&indent, APK_BLOB_STR(name->name));
		match++;
1126
	}
Timo Teräs's avatar
Timo Teräs committed
1127 1128 1129 1130
	if (match)
		printf("\n");
	return match;
}
1131

Timo Teräs's avatar
Timo Teräs committed
1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168
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;
}

Timo Teräs's avatar
Timo Teräs committed
1169
static int compare_package_topology(const void *p1, const void *p2)
1170 1171 1172 1173
{
	struct apk_package *pkg1 = *(struct apk_package **) p1;
	struct apk_package *pkg2 = *(struct apk_package **) p2;

1174
	return pkg1->topology_hard - pkg2->topology_hard;
1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186
}

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 *),
Timo Teräs's avatar
Timo Teräs committed
1187
	      compare_package_topology);
1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200

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

1201 1202 1203
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
1204 1205 1206 1207 1208
{
	struct progress prog;
	struct apk_change *change;
	int i, r = 0, size_diff = 0;

1209 1210 1211
	if (changeset->changes == NULL)
		goto all_done;

Timo Teräs's avatar
Timo Teräs committed
1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245
	/* 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;
		}
1246 1247
	}

Timo Teräs's avatar
Timo Teräs committed
1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271
	/* 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);

1272
	run_triggers(db);
Timo Teräs's avatar
Timo Teräs committed
1273

1274
all_done:
Timo Teräs's avatar
Timo Teräs committed
1275 1276 1277
	apk_dependency_array_copy(&db->world, world);
	apk_db_write_config(db);

1278
	if (r == 0 && !db->performing_self_update) {
Timo Teräs's avatar
Timo Teräs committed
1279 1280 1281 1282 1283 1284 1285 1286 1287
		apk_message("OK: %d packages, %d dirs, %d files",
			    db->installed.stats.packages,
			    db->installed.stats.dirs,
			    db->installed.stats.files);
	}

	return r;
}

1288
static void print_dep_errors(struct apk_database *db, char *label, struct apk_dependency_array *deps)
Timo Teräs's avatar
Timo Teräs committed
1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299
{
	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))
1300
			continue;
Timo Teräs's avatar
Timo Teräs committed
1301 1302 1303 1304 1305 1306 1307

		if (print_label) {
			print_label = 0;
			indent.x = printf("  %s:", label);
			indent.indent = indent.x + 1;
		}
		p = APK_BLOB_BUF(buf);
1308
		apk_blob_push_dep(&p, db, dep);
Timo Teräs's avatar
Timo Teräs committed
1309 1310
		p = apk_blob_pushed(APK_BLOB_BUF(buf), p);
		apk_print_indented(&indent, p);
1311
	}
Timo Teräs's avatar
Timo Teräs committed
1312 1313 1314 1315
	if (!print_label)
		printf("\n");
}