solver.c 37.2 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
	unsigned int topology_last_touched;
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
	struct list_head unsolved_list_head;
	struct apk_package *latest_decision;
	unsigned int topology_position;
70
	unsigned int penalty_topology;
71
	unsigned int assigned_names;
Timo Teräs's avatar
Timo Teräs committed
72
	struct apk_score score;
73
	struct apk_score penalty_score;
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

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

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

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

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

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

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

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

			cb(ss, pkg0);
136 137
		}
	}
138
}
139

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

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

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

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

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

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

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

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

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

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

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

Timo Teräs's avatar
Timo Teräs committed
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 273 274
	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);
	}
275 276
}

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

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

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

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

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

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

Timo Teräs's avatar
Timo Teräs committed
358
	return preference;
359 360
}

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

	return missing;
}

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

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

389
		if (ps0 == NULL ||
390
		    pkg0->topology_hard >= ss->topology_position ||
391
		    (ps0->flags & APK_PKGSTF_DECIDED))
392 393
			continue;

Timo Teräs's avatar
Timo Teräs committed
394 395 396 397 398 399
		if ((pkg0->repos != 0) && (pkg0->ipkg == NULL) && (pkg0->filename == NULL) &&
		    !(pkg0->repos & allowed_repos)) {
			skipped_options++;
			continue;
		}

400 401 402 403 404 405
		if (ns->requirers == 0 && ns->install_ifs != 0 &&
		    install_if_missing(ss, pkg0)) {
			skipped_options++;
			continue;
		}

406
		options++;
407 408 409
		if (ps0->topology_soft < ss->topology_position &&
		    ps0->topology_soft > best_topology)
			best_pkg = pkg0, best_topology = ps0->topology_soft;
410 411
		else if (pkg0->topology_hard > best_topology)
			best_pkg = pkg0, best_topology = pkg0->topology_hard;
412
	}
413

414
	if (skipped_options == 0 && options == 0) {
Timo Teräs's avatar
Timo Teräs committed
415 416 417 418
		if (!ns->locked) {
			ss->score.unsatisfiable += ns->requirers;
			ss->score.preference += name->pkgs->num;
		}
419 420 421 422 423 424
		ns->locked = 1;
		ns->chosen = NULL;
	} else {
		ns->locked = 0;
	}

Timo Teräs's avatar
Timo Teräs committed
425
	if (ns->requirers == 0 && ns->install_ifs == 0) {
426 427 428 429 430
		if (list_hashed(&ns->unsolved_list)) {
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
			ns->chosen = NULL;
		}
431 432
		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);
433
	} else {
434 435 436
		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);
437 438
		if (!list_hashed(&ns->unsolved_list))
			list_add(&ns->unsolved_list, &ss->unsolved_list_head);
Timo Teräs's avatar
Timo Teräs committed
439 440
		if (!ns->locked)
			ns->chosen = best_pkg;
441 442
	}

443
	return options + skipped_options;
444 445
}

446 447 448 449
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
450
		struct apk_name_state *ns = ns = name_to_ns(pkg->name);
451 452 453

		dbg_printf("trigger_install_if: " PKG_VER_FMT " triggered\n",
			   PKG_VER_PRINTF(pkg));
454
		ns->topology_last_touched = ss->topology_position;
455
		ns->install_ifs++;
Timo Teräs's avatar
Timo Teräs committed
456
		update_name_state(ss, pkg->name);
457 458 459 460 461 462 463
	}
}

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
464
		struct apk_name_state *ns = name_to_ns(pkg->name);
465 466 467

		dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n",
			   PKG_VER_PRINTF(pkg));
468
		ns->topology_last_touched = ss->topology_position;
469
		ns->install_ifs--;
Timo Teräs's avatar
Timo Teräs committed
470
		update_name_state(ss, pkg->name);
471 472 473
	}
}

474 475 476
static void apply_decision(struct apk_solver_state *ss,
			   struct apk_package *pkg,
			   struct apk_package_state *ps)
477
{
Timo Teräs's avatar
Timo Teräs committed
478
	struct apk_name_state *ns = name_to_ns(pkg->name);
479 480 481 482 483 484

	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
485 486
		ss->score.unsatisfiable += ps->conflicts;
		ss->score.preference += get_preference(ss, pkg, FALSE);
487
		ns->chosen = pkg;
Timo Teräs's avatar
Timo Teräs committed
488
		ns->locked = 1;
489 490 491 492 493 494 495

		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);
496
		foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
497
	} else {
Timo Teräs's avatar
Timo Teräs committed
498
		update_name_state(ss, pkg->name);
499 500 501 502 503 504 505
	}
}

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
506
	struct apk_name_state *ns = name_to_ns(pkg->name);
507 508 509 510

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

511 512 513
	if (ps->flags & APK_PKGSTF_INSTALLIF)
		ss->topology_position = ps->topology_soft;
	else
514
		ss->topology_position = pkg->topology_hard;
515

516 517
	if (ps->flags & APK_PKGSTF_INSTALL) {
		ss->assigned_names--;
518 519

		foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
520 521
		foreach_dependency(ss, pkg->depends, undo_constraint);

Timo Teräs's avatar
Timo Teräs committed
522
		ns->locked = 0;
523
		ns->chosen = NULL;
524
	}
525

Timo Teräs's avatar
Timo Teräs committed
526
	ss->score = ps->saved_score;
Timo Teräs's avatar
Timo Teräs committed
527
	update_name_state(ss, pkg->name);
528 529
}

530 531
static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
			  int flags)
532
{
533
	struct apk_package_state *ps = pkg_to_ps(pkg);
534 535

	ps->backtrack = ss->latest_decision;
536
	ps->flags = flags | APK_PKGSTF_DECIDED;
Timo Teräs's avatar
Timo Teräs committed
537
	ps->saved_score = ss->score;
538 539 540 541 542 543 544

	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;
545
		ss->topology_position = pkg->topology_hard;
546
	}
547
	ss->latest_decision = pkg;
548

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

552 553 554 555
	if (ps->flags & APK_PKGSTF_INSTALLIF)
		dbg_printf("triggers due to " PKG_VER_FMT "\n",
			   PKG_VER_PRINTF(pkg));

556
	apply_decision(ss, pkg, ps);
557 558 559 560 561 562 563
}

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

564
	while (ss->latest_decision != NULL) {
565
		pkg = ss->latest_decision;
566
		ps = pkg_to_ps(pkg);
567 568 569 570

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

574
			ss->latest_decision = ps->backtrack;
Timo Teräs's avatar
Timo Teräs committed
575
			ss->refresh_name_states = 1;
576 577 578 579
		} else {
			dbg_printf("next_branch: swapping BRANCH at topology_position %d\n",
				   ss->topology_position);

Timo Teräs's avatar
Timo Teräs committed
580 581
			undo_decision(ss, pkg, ps);

582 583 584
			ps->flags |= APK_PKGSTF_ALT_BRANCH;
			ps->flags ^= APK_PKGSTF_INSTALL;

585 586
			apply_decision(ss, pkg, ps);
			return 0;
587 588
		}
	}
589 590 591

	dbg_printf("next_branch: no more branches\n");
	return 1;
592 593
}

Timo Teräs's avatar
Timo Teräs committed
594 595 596 597 598 599 600 601
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);
602
	tns->allowed_repos |= fns->allowed_repos;
Timo Teräs's avatar
Timo Teräs committed
603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618
}

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;
619 620
	if (ns->allowed_repos)
		return 1;
Timo Teräs's avatar
Timo Teräs committed
621 622 623 624 625 626 627 628
	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;
629
	ns->allowed_repos = 0;
Timo Teräs's avatar
Timo Teräs committed
630 631 632
	foreach_locked_reverse_dependency(name, inherit_name_state_wrapper, name);
}

633
static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
634 635
{
	struct apk_name *name = dep->name;
Timo Teräs's avatar
Timo Teräs committed
636
	struct apk_name_state *ns = name_to_ns(name);
637
	int i;
638

639
	prepare_name(ss, name, ns);
640

Timo Teräs's avatar
Timo Teräs committed
641
	if (ns->locked) {
Timo Teräs's avatar
Timo Teräs committed
642 643 644 645 646 647
		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);
648
		if (!apk_dep_is_satisfied(dep, ns->chosen))
Timo Teräs's avatar
Timo Teräs committed
649
			ss->score.unsatisfiable++;
650 651 652
		return;
	}

653 654 655 656 657 658 659 660 661 662
	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;
	}

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

667
		if (ps0 == NULL ||
668
		    pkg0->topology_hard >= ss->topology_position)
669 670 671 672 673 674 675 676 677 678
			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
679 680 681
	if (ss->latest_decision != NULL)
		inherit_name_state(name, ss->latest_decision->name);

682
	if (!dep->optional)
Timo Teräs's avatar
Timo Teräs committed
683
		ns->requirers++;
684 685
	ns->topology_last_touched = ss->topology_position;

Timo Teräs's avatar
Timo Teräs committed
686
	update_name_state(ss, name);
687 688
}

689
static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
690 691
{
	struct apk_name *name = dep->name;
Timo Teräs's avatar
Timo Teräs committed
692
	struct apk_name_state *ns = name_to_ns(name);
693 694
	int i;

Timo Teräs's avatar
Timo Teräs committed
695
	if (ns->locked) {
696 697 698 699 700 701 702
		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);
		}
703 704
		return;
	}
705 706 707

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

710
		if (pkg0->topology_hard >= ss->topology_position)
711 712 713 714 715 716 717 718 719 720
			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
721 722 723
	if (ss->latest_decision && has_inherited_state(ss->latest_decision->name))
		recalculate_inherted_name_state(name);

724
	if (!dep->optional)
Timo Teräs's avatar
Timo Teräs committed
725
		ns->requirers--;
726 727
	ns->topology_last_touched = ss->topology_position;

Timo Teräs's avatar
Timo Teräs committed
728
	update_name_state(ss, name);
729 730 731 732
}

static int expand_branch(struct apk_solver_state *ss)
{
733 734
	struct apk_name_state *ns;
	struct apk_package *pkg0 = NULL;
735
	unsigned int topology0 = 0;
Timo Teräs's avatar
Timo Teräs committed
736
	int flags;
737 738 739

	/* 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
740 741 742
		if (ss->refresh_name_states)
			update_name_state(ss, ns->name);

743 744 745 746 747 748 749 750 751
		/* 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;
752 753
		else if (ns->chosen->topology_hard > topology0)
			pkg0 = ns->chosen, topology0 = pkg0->topology_hard;
754
	}
Timo Teräs's avatar
Timo Teräs committed
755
	ss->refresh_name_states = 0;
756
	if (pkg0 == NULL) {
757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774
		struct apk_score penalty_score = {0,0};
		int penalty_topology = 0;

		list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
			if (!ns->locked) {
				penalty_score.unsatisfiable += ns->requirers;
				penalty_score.preference += ns->name->pkgs->num;
				if (penalty_topology < ns->topology_last_touched)
					penalty_topology = ns->topology_last_touched;
			}
		}
		if (ss->penalty_topology < penalty_topology) {
			ss->penalty_topology = penalty_topology;
			ss->penalty_score = penalty_score;
		}
		ss->score.unsatisfiable += penalty_score.unsatisfiable;
		ss->score.preference    += penalty_score.preference;

775
		dbg_printf("expand_branch: list is empty (%d unsatisfied)\n",
Timo Teräs's avatar
Timo Teräs committed
776
			   ss->score.unsatisfiable);
777 778
		return 1;
	}
779

780 781
	/* someone needs to provide this name -- find next eligible
	 * provider candidate */
Timo Teräs's avatar
Timo Teräs committed
782
	ns = name_to_ns(pkg0->name);
783
	dbg_printf("expand_branch: %s\n", pkg0->name->name);
784

Timo Teräs's avatar
Timo Teräs committed
785 786 787 788 789
	if (get_preference(ss, pkg0, TRUE) == 0)
		flags = APK_PKGSTF_INSTALL;
	else
		flags = APK_PKGSTF_NOINSTALL;
	push_decision(ss, pkg0, flags);
790 791 792 793 794 795 796 797 798 799 800 801 802 803 804

	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) {
805
		ps = pkg_to_ps(pkg);
806 807 808
		if (ps->flags & APK_PKGSTF_INSTALL) {
			if (i >= ss->assigned_names)
				abort();
809
			ss->best_solution->item[i++] = pkg;
810
		}
811 812 813 814 815 816 817

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

		pkg = ps->backtrack;
	}
818
	apk_package_array_resize(&ss->best_solution, i);
Timo Teräs's avatar
Timo Teräs committed
819
	ss->best_score = ss->score;
820 821 822 823 824 825 826 827
}

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

Timo Teräs's avatar
Timo Teräs committed
830 831 832 833 834 835 836 837
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 */
838 839
			return  c2->oldpkg->topology_hard -
				c1->oldpkg->topology_hard;
Timo Teräs's avatar
Timo Teräs committed
840 841 842 843 844 845 846 847

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

848 849
	return  c1->newpkg->topology_hard -
		c2->newpkg->topology_hard;
Timo Teräs's avatar
Timo Teräs committed
850 851 852 853
}

static int generate_changeset(struct apk_database *db,
			      struct apk_package_array *solution,
854 855
			      struct apk_changeset *changeset,
			      unsigned short solver_flags)
Timo Teräs's avatar
Timo Teräs committed
856 857 858 859 860 861 862 863 864 865
{
	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
866
		ns = name_to_ns(pkg->name);
Timo Teräs's avatar
Timo Teräs committed
867 868
		ns->chosen = pkg;
		ns->in_changeset = 1;
Timo Teräs's avatar
Timo Teräs committed
869
		if ((pkg->ipkg == NULL) ||
Timo Teräs's avatar
Timo Teräs committed
870 871
		    ((ns->solver_flags_local | ns->solver_flags_inherited |
		      solver_flags) & APK_SOLVERF_REINSTALL))
Timo Teräs's avatar
Timo Teräs committed
872 873 874 875 876
			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
877
		if ((ns->chosen == NULL) || !ns->in_changeset)
Timo Teräs's avatar
Timo Teräs committed
878 879 880 881 882 883 884 885
			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
886
		if ((ns->chosen == NULL) || !ns->in_changeset) {
Timo Teräs's avatar
Timo Teräs committed
887 888 889 890 891 892 893
			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
894
		ns = name_to_ns(name);
Timo Teräs's avatar
Timo Teräs committed
895 896

		if ((pkg->ipkg == NULL) ||
Timo Teräs's avatar
Timo Teräs committed
897 898
		    ((ns->solver_flags_local | ns->solver_flags_inherited |
		      solver_flags) & APK_SOLVERF_REINSTALL)) {
Timo Teräs's avatar
Timo Teräs committed
899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928
			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;
}

929 930 931 932 933 934 935 936 937 938 939
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;
}

940
void apk_solver_set_name_flags(struct apk_name *name,
Timo Teräs's avatar
Timo Teräs committed
941 942
			       unsigned short solver_flags,
			       unsigned short solver_flags_inheritable)
943 944
{
	struct apk_name_state *ns = name_to_ns(name);
Timo Teräs's avatar
Timo Teräs committed
945 946
	ns->solver_flags_local = solver_flags;
	ns->solver_flags_local_mask = solver_flags_inheritable;
947 948
}

949 950 951 952 953 954
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
955 956 957 958 959 960 961 962 963 964 965 966 967
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;
}

968 969 970 971 972 973 974 975 976 977 978 979 980
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
981 982 983 984 985
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)
986 987
{
	struct apk_solver_state *ss;
Timo Teräs's avatar
Timo Teräs committed
988
	struct apk_installed_package *ipkg;
989
	struct apk_score zero_score;
990
	int i, r;
991 992 993

	ss = calloc(1, sizeof(struct apk_solver_state));
	ss->db = db;
Timo Teräs's avatar
Timo Teräs committed
994
	ss->solver_flags = solver_flags;
995
	ss->topology_position = -1;
Timo Teräs's avatar
Timo Teräs committed
996
	ss->best_score = (struct apk_score){ .unsatisfiable = -1, .preference = -1 };
997
	list_init(&ss->unsolved_list_head);
998 999 1000

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

1004
	foreach_dependency(ss, world, apply_constraint);
1005 1006
	zero_score = ss->score;

1007
	do {
1008 1009 1010 1011 1012 1013
		if (ss->topology_position <= ss->penalty_topology) {
			ss->penalty_score = zero_score;
			ss->penalty_topology = 0;
		}

		if (cmpscore2(&ss->score, &ss->penalty_score, &ss->best_score) < 0) {
1014 1015
			r = expand_branch(ss);
			if (r) {
Timo Teräs's avatar
Timo Teräs committed
1016 1017 1018 1019 1020 1021 1022
				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);

1023
				if (cmpscore(&zero_score, &ss->score) >= 0) {
1024 1025 1026 1027 1028 1029 1030 1031 1032 1033
					/* 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);
1034
		}
1035
	} while (r == 0);
1036 1037

	/* collect packages */
1038 1039 1040 1041 1042
	if (changeset != NULL) {
		generate_changeset(db, ss->best_solution, changeset,
				   ss->solver_flags);
	}
	if (solution != NULL) {
1043 1044
		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
1045
		*solution = ss->best_solution;
1046
	} else {
Timo Teräs's avatar
Timo Teräs committed
1047
		apk_package_array_free(&ss->best_solution);
1048 1049
	}
	r = ss->best_score.unsatisfiable;
1050
	apk_solver_free(db);
1051 1052 1053 1054 1055
	free(ss);

	return r;
}

Timo Teräs's avatar
Timo Teräs committed
1056 1057 1058
static void print_change(struct apk_database *db,
			 struct apk_change *change,
			 int cur, int total)
1059
{
Timo Teräs's avatar
Timo Teräs committed
1060 1061 1062 1063 1064 1065
	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;
1066

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

Timo Teräs's avatar
Timo Teräs committed
1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102
	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));
1103
	}
Timo Teräs's avatar
Timo Teräs committed
1104
}
1105

Timo Teräs's avatar
Timo Teräs committed
1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133
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);
1134 1135
}

Timo Teräs's avatar
Timo Teräs committed
1136 1137 1138 1139 1140 1141 1142 1143
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)
1144
{
Timo Teräs's avatar
Timo Teräs committed
1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163
	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;
1164
	struct apk_name *name;
1165
	struct apk_indent indent = { .indent = 2 };
Timo Teräs's avatar
Timo Teräs committed
1166
	int match = 0, i;
1167

Timo Teräs's avatar
Timo Teräs committed
1168 1169 1170 1171 1172
	for (i = 0; i < changeset->changes->num; i++) {
		change = &changeset->changes->item[i];
		if (!cmp(change))
			continue;
		if (match == 0)
1173
			printf("%s:\n", msg);
Timo Teräs's avatar
Timo Teräs committed
1174 1175 1176 1177 1178 1179 1180
		if (change->newpkg != NULL)
			name = change->newpkg->name;
		else
			name = change->oldpkg->name;

		apk_print_indented(&indent, APK_BLOB_STR(name->name));
		match++;
1181
	}
Timo Teräs's avatar
Timo Teräs committed
1182 1183 1184 1185
	if (match)
		printf("\n");
	return match;
}
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 1215 1216 1217 1218 1219 1220 1221 1222 1223
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
1224
static int compare_package_topology(const void *p1, const void *p2)
1225 1226 1227 1228
{
	struct apk_package *pkg1 = *(struct apk_package **) p1;
	struct apk_package *pkg2 = *(struct apk_package **) p2;

1229
	return pkg1->topology_hard - pkg2->topology_hard;
1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241
}

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
1242
	      compare_package_topology);
1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255

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

1256 1257 1258
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
1259 1260 1261 1262 1263
{
	struct progress prog;
	struct apk_change *change;
	int i, r = 0, size_diff = 0;

1264 1265 1266
	if (changeset->changes == NULL)
		goto all_done;

Timo Teräs's avatar
Timo Teräs committed
1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291