solver.c 38.4 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 291 292 293 294 295 296 297 298 299 300 301 302 303 304
	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 */
		if ((pkgA->ipkg || pkgA->filename || (pkgA->repos & preferred_repos)) &&
		    !(pkgB->ipkg || pkgB->filename || (pkgB->repos & preferred_repos)))
			return 1;
		if ((pkgB->ipkg || pkgA->filename || (pkgB->repos & preferred_repos)) &&
		    !(pkgA->ipkg || pkgB->filename || (pkgA->repos & preferred_repos)))
			return -1;
	}
305

Timo Teräs's avatar
Timo Teräs committed
306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336
	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)
337 338
{
	struct apk_name *name = pkg->name;
339
	struct apk_name_state *ns = name_to_ns(name);
Timo Teräs's avatar
Timo Teräs committed
340 341 342
	unsigned short name_flags = ns->solver_flags_local
		| ns->solver_flags_inherited
		| ss->solver_flags;
343
	unsigned int preferred_repos = ns->preferred_repos;
Timo Teräs's avatar
Timo Teräs committed
344 345
	unsigned short preference = 0;
	int i;
346

347 348 349
	if (preferred_repos == 0)
		preferred_repos = ss->db->repo_tags[0].allowed_repos;

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

Timo Teräs's avatar
Timo Teräs committed
354
		if (pkg0 == pkg || ps0 == NULL)
355 356
			continue;

357 358 359
		if (compare_package_preference(name_flags,
					       preferred_repos,
					       pkg, pkg0) < 0) {
Timo Teräs's avatar
Timo Teräs committed
360 361 362 363 364 365
			if (installable_only) {
				if (ss->topology_position > pkg0->topology_hard &&
				    !(ps0->flags & APK_PKGSTF_DECIDED))
					preference++;
			} else
				preference++;
366 367 368
		}
	}

Timo Teräs's avatar
Timo Teräs committed
369
	return preference;
370 371
}

372 373
static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg)
{
Timo Teräs's avatar
Timo Teräs committed
374
	struct apk_name_state *ns;
375 376 377 378 379
	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
380
		ns = name_to_ns(dep->name);
Timo Teräs's avatar
Timo Teräs committed
381
		if (!ns->locked || !apk_dep_is_satisfied(dep, ns->chosen))
382 383 384 385 386 387
			missing++;
	}

	return missing;
}

Timo Teräs's avatar
Timo Teräs committed
388
static int update_name_state(struct apk_solver_state *ss, struct apk_name *name)
389
{
Timo Teräs's avatar
Timo Teräs committed
390
	struct apk_name_state *ns = name_to_ns(name);
391 392
	struct apk_package *best_pkg = NULL;
	unsigned int best_topology = 0;
393
	unsigned int allowed_repos = ns->allowed_repos | ss->db->repo_tags[0].allowed_repos;
394
	int i, options = 0, skipped_options = 0;
395 396 397

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

400
		if (ps0 == NULL ||
401
		    pkg0->topology_hard >= ss->topology_position ||
402
		    (ps0->flags & APK_PKGSTF_DECIDED))
403 404
			continue;

Timo Teräs's avatar
Timo Teräs committed
405 406 407 408 409 410
		if ((pkg0->repos != 0) && (pkg0->ipkg == NULL) && (pkg0->filename == NULL) &&
		    !(pkg0->repos & allowed_repos)) {
			skipped_options++;
			continue;
		}

411 412 413 414 415 416
		if (ns->requirers == 0 && ns->install_ifs != 0 &&
		    install_if_missing(ss, pkg0)) {
			skipped_options++;
			continue;
		}

417
		options++;
418 419 420
		if (ps0->topology_soft < ss->topology_position &&
		    ps0->topology_soft > best_topology)
			best_pkg = pkg0, best_topology = ps0->topology_soft;
421 422
		else if (pkg0->topology_hard > best_topology)
			best_pkg = pkg0, best_topology = pkg0->topology_hard;
423
	}
424

425
	if (skipped_options == 0 && options == 0) {
Timo Teräs's avatar
Timo Teräs committed
426 427 428 429
		if (!ns->locked) {
			ss->score.unsatisfiable += ns->requirers;
			ss->score.preference += name->pkgs->num;
		}
430 431 432 433 434 435
		ns->locked = 1;
		ns->chosen = NULL;
	} else {
		ns->locked = 0;
	}

Timo Teräs's avatar
Timo Teräs committed
436
	if (ns->requirers == 0 && ns->install_ifs == 0) {
437 438 439 440 441
		if (list_hashed(&ns->unsolved_list)) {
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
			ns->chosen = NULL;
		}
442 443
		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);
444
	} else {
445 446 447
		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);
448 449
		if (!list_hashed(&ns->unsolved_list))
			list_add(&ns->unsolved_list, &ss->unsolved_list_head);
Timo Teräs's avatar
Timo Teräs committed
450 451
		if (!ns->locked)
			ns->chosen = best_pkg;
452 453
	}

454
	return options + skipped_options;
455 456
}

457 458 459 460
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
461
		struct apk_name_state *ns = ns = name_to_ns(pkg->name);
462 463 464

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

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
475
		struct apk_name_state *ns = name_to_ns(pkg->name);
476 477 478

		dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n",
			   PKG_VER_PRINTF(pkg));
479
		ns->topology_last_touched = ss->topology_position;
480
		ns->install_ifs--;
Timo Teräs's avatar
Timo Teräs committed
481
		update_name_state(ss, pkg->name);
482 483 484
	}
}

485 486 487
static void apply_decision(struct apk_solver_state *ss,
			   struct apk_package *pkg,
			   struct apk_package_state *ps)
488
{
Timo Teräs's avatar
Timo Teräs committed
489
	struct apk_name_state *ns = name_to_ns(pkg->name);
490 491 492 493 494 495

	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
496 497
		ss->score.unsatisfiable += ps->conflicts;
		ss->score.preference += get_preference(ss, pkg, FALSE);
498
		ns->chosen = pkg;
Timo Teräs's avatar
Timo Teräs committed
499
		ns->locked = 1;
500 501 502 503 504 505 506

		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);
507
		foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
508
	} else {
Timo Teräs's avatar
Timo Teräs committed
509
		update_name_state(ss, pkg->name);
510 511 512 513 514 515 516
	}
}

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
517
	struct apk_name_state *ns = name_to_ns(pkg->name);
518 519 520 521

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

522 523 524
	if (ps->flags & APK_PKGSTF_INSTALLIF)
		ss->topology_position = ps->topology_soft;
	else
525
		ss->topology_position = pkg->topology_hard;
526

527 528
	if (ps->flags & APK_PKGSTF_INSTALL) {
		ss->assigned_names--;
529 530

		foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
531 532
		foreach_dependency(ss, pkg->depends, undo_constraint);

Timo Teräs's avatar
Timo Teräs committed
533
		ns->locked = 0;
534
		ns->chosen = NULL;
535
	}
536

Timo Teräs's avatar
Timo Teräs committed
537
	ss->score = ps->saved_score;
Timo Teräs's avatar
Timo Teräs committed
538
	update_name_state(ss, pkg->name);
539 540
}

541 542
static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
			  int flags)
543
{
544
	struct apk_package_state *ps = pkg_to_ps(pkg);
545 546

	ps->backtrack = ss->latest_decision;
547
	ps->flags = flags | APK_PKGSTF_DECIDED;
Timo Teräs's avatar
Timo Teräs committed
548
	ps->saved_score = ss->score;
549 550 551 552 553 554 555

	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;
556
		ss->topology_position = pkg->topology_hard;
557
	}
558
	ss->latest_decision = pkg;
559

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

563 564 565 566
	if (ps->flags & APK_PKGSTF_INSTALLIF)
		dbg_printf("triggers due to " PKG_VER_FMT "\n",
			   PKG_VER_PRINTF(pkg));

567
	apply_decision(ss, pkg, ps);
568 569 570 571 572 573 574
}

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

575
	while (ss->latest_decision != NULL) {
576
		pkg = ss->latest_decision;
577
		ps = pkg_to_ps(pkg);
578 579 580 581

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

585
			ss->latest_decision = ps->backtrack;
Timo Teräs's avatar
Timo Teräs committed
586
			ss->refresh_name_states = 1;
587 588 589 590
		} else {
			dbg_printf("next_branch: swapping BRANCH at topology_position %d\n",
				   ss->topology_position);

Timo Teräs's avatar
Timo Teräs committed
591 592
			undo_decision(ss, pkg, ps);

593 594 595
			ps->flags |= APK_PKGSTF_ALT_BRANCH;
			ps->flags ^= APK_PKGSTF_INSTALL;

596 597
			apply_decision(ss, pkg, ps);
			return 0;
598 599
		}
	}
600 601 602

	dbg_printf("next_branch: no more branches\n");
	return 1;
603 604
}

Timo Teräs's avatar
Timo Teräs committed
605 606 607 608 609 610 611 612
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);
613
	tns->allowed_repos |= fns->allowed_repos;
Timo Teräs's avatar
Timo Teräs committed
614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629
}

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;
630 631
	if (ns->allowed_repos)
		return 1;
Timo Teräs's avatar
Timo Teräs committed
632 633 634 635 636 637 638 639
	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;
640
	ns->allowed_repos = 0;
Timo Teräs's avatar
Timo Teräs committed
641 642 643
	foreach_locked_reverse_dependency(name, inherit_name_state_wrapper, name);
}

644
static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
645 646
{
	struct apk_name *name = dep->name;
Timo Teräs's avatar
Timo Teräs committed
647
	struct apk_name_state *ns = name_to_ns(name);
648
	int i;
649

650
	prepare_name(ss, name, ns);
651

Timo Teräs's avatar
Timo Teräs committed
652
	if (ns->locked) {
Timo Teräs's avatar
Timo Teräs committed
653 654 655 656 657 658
		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);
659
		if (!apk_dep_is_satisfied(dep, ns->chosen))
Timo Teräs's avatar
Timo Teräs committed
660
			ss->score.unsatisfiable++;
661 662 663
		return;
	}

664 665 666 667 668 669 670 671 672 673
	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;
	}

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

678
		if (ps0 == NULL ||
679
		    pkg0->topology_hard >= ss->topology_position)
680 681 682 683 684 685 686 687 688 689
			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
690 691 692
	if (ss->latest_decision != NULL)
		inherit_name_state(name, ss->latest_decision->name);

693
	if (!dep->optional)
Timo Teräs's avatar
Timo Teräs committed
694
		ns->requirers++;
695 696
	ns->topology_last_touched = ss->topology_position;

Timo Teräs's avatar
Timo Teräs committed
697
	update_name_state(ss, name);
698 699
}

700
static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
701 702
{
	struct apk_name *name = dep->name;
Timo Teräs's avatar
Timo Teräs committed
703
	struct apk_name_state *ns = name_to_ns(name);
704 705
	int i;

Timo Teräs's avatar
Timo Teräs committed
706
	if (ns->locked) {
707 708 709 710 711 712 713
		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);
		}
714 715
		return;
	}
716 717 718

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

721
		if (pkg0->topology_hard >= ss->topology_position)
722 723 724 725 726 727 728 729 730 731
			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
732 733 734
	if (ss->latest_decision && has_inherited_state(ss->latest_decision->name))
		recalculate_inherted_name_state(name);

735
	if (!dep->optional)
Timo Teräs's avatar
Timo Teräs committed
736
		ns->requirers--;
737 738
	ns->topology_last_touched = ss->topology_position;

Timo Teräs's avatar
Timo Teräs committed
739
	update_name_state(ss, name);
740 741 742 743
}

static int expand_branch(struct apk_solver_state *ss)
{
744 745
	struct apk_name_state *ns;
	struct apk_package *pkg0 = NULL;
746
	unsigned int topology0 = 0;
Timo Teräs's avatar
Timo Teräs committed
747
	int flags;
748 749 750

	/* 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
751 752 753
		if (ss->refresh_name_states)
			update_name_state(ss, ns->name);

754 755 756 757 758 759 760 761 762
		/* 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;
763 764
		else if (ns->chosen->topology_hard > topology0)
			pkg0 = ns->chosen, topology0 = pkg0->topology_hard;
765
	}
Timo Teräs's avatar
Timo Teräs committed
766
	ss->refresh_name_states = 0;
767
	if (pkg0 == NULL) {
768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785
		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;

786
		dbg_printf("expand_branch: list is empty (%d unsatisfied)\n",
Timo Teräs's avatar
Timo Teräs committed
787
			   ss->score.unsatisfiable);
788 789
		return 1;
	}
790

791 792
	/* someone needs to provide this name -- find next eligible
	 * provider candidate */
Timo Teräs's avatar
Timo Teräs committed
793
	ns = name_to_ns(pkg0->name);
794
	dbg_printf("expand_branch: %s\n", pkg0->name->name);
795

Timo Teräs's avatar
Timo Teräs committed
796 797 798 799 800
	if (get_preference(ss, pkg0, TRUE) == 0)
		flags = APK_PKGSTF_INSTALL;
	else
		flags = APK_PKGSTF_NOINSTALL;
	push_decision(ss, pkg0, flags);
801 802 803 804 805 806 807 808 809 810 811 812 813 814 815

	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) {
816
		ps = pkg_to_ps(pkg);
817 818 819
		if (ps->flags & APK_PKGSTF_INSTALL) {
			if (i >= ss->assigned_names)
				abort();
820
			ss->best_solution->item[i++] = pkg;
821
		}
822 823 824 825 826 827 828

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

		pkg = ps->backtrack;
	}
829
	apk_package_array_resize(&ss->best_solution, i);
Timo Teräs's avatar
Timo Teräs committed
830
	ss->best_score = ss->score;
831 832 833 834 835 836 837 838
}

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

Timo Teräs's avatar
Timo Teräs committed
841 842 843 844 845 846 847 848
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 */
849 850
			return  c2->oldpkg->topology_hard -
				c1->oldpkg->topology_hard;
Timo Teräs's avatar
Timo Teräs committed
851 852 853 854 855 856 857 858

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

859 860
	return  c1->newpkg->topology_hard -
		c2->newpkg->topology_hard;
Timo Teräs's avatar
Timo Teräs committed
861 862 863 864
}

static int generate_changeset(struct apk_database *db,
			      struct apk_package_array *solution,
865 866
			      struct apk_changeset *changeset,
			      unsigned short solver_flags)
Timo Teräs's avatar
Timo Teräs committed
867 868 869 870 871 872 873 874 875 876
{
	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
877
		ns = name_to_ns(pkg->name);
Timo Teräs's avatar
Timo Teräs committed
878 879
		ns->chosen = pkg;
		ns->in_changeset = 1;
Timo Teräs's avatar
Timo Teräs committed
880
		if ((pkg->ipkg == NULL) ||
Timo Teräs's avatar
Timo Teräs committed
881 882
		    ((ns->solver_flags_local | ns->solver_flags_inherited |
		      solver_flags) & APK_SOLVERF_REINSTALL))
Timo Teräs's avatar
Timo Teräs committed
883 884 885 886 887
			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
888
		if ((ns->chosen == NULL) || !ns->in_changeset)
Timo Teräs's avatar
Timo Teräs committed
889 890 891 892 893 894 895 896
			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
897
		if ((ns->chosen == NULL) || !ns->in_changeset) {
Timo Teräs's avatar
Timo Teräs committed
898 899 900 901 902 903 904
			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
905
		ns = name_to_ns(name);
Timo Teräs's avatar
Timo Teräs committed
906 907

		if ((pkg->ipkg == NULL) ||
Timo Teräs's avatar
Timo Teräs committed
908 909
		    ((ns->solver_flags_local | ns->solver_flags_inherited |
		      solver_flags) & APK_SOLVERF_REINSTALL)) {
Timo Teräs's avatar
Timo Teräs committed
910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939
			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;
}

940 941 942 943 944 945 946 947 948 949 950
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;
}

951
void apk_solver_set_name_flags(struct apk_name *name,
Timo Teräs's avatar
Timo Teräs committed
952 953
			       unsigned short solver_flags,
			       unsigned short solver_flags_inheritable)
954 955
{
	struct apk_name_state *ns = name_to_ns(name);
Timo Teräs's avatar
Timo Teräs committed
956 957
	ns->solver_flags_local = solver_flags;
	ns->solver_flags_local_mask = solver_flags_inheritable;
958 959
}

960 961 962 963 964 965
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
966 967 968 969 970 971 972 973 974 975 976 977 978
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;
}

979 980 981 982 983 984 985 986 987 988 989 990 991
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
992 993 994 995 996
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)
997 998
{
	struct apk_solver_state *ss;
Timo Teräs's avatar
Timo Teräs committed
999
	struct apk_installed_package *ipkg;
1000
	struct apk_score zero_score;
1001
	int i, r;
1002 1003 1004

	ss = calloc(1, sizeof(struct apk_solver_state));
	ss->db = db;
Timo Teräs's avatar
Timo Teräs committed
1005
	ss->solver_flags = solver_flags;
1006
	ss->topology_position = -1;
Timo Teräs's avatar
Timo Teräs committed
1007
	ss->best_score = (struct apk_score){ .unsatisfiable = -1, .preference = -1 };
1008
	list_init(&ss->unsolved_list_head);
1009 1010 1011

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

1015
	foreach_dependency(ss, world, apply_constraint);
1016 1017
	zero_score = ss->score;

1018
	do {
1019 1020 1021 1022 1023 1024
		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) {
1025 1026
			r = expand_branch(ss);
			if (r) {
Timo Teräs's avatar
Timo Teräs committed
1027 1028 1029 1030 1031 1032 1033
				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);

1034
				if (cmpscore(&zero_score, &ss->score) >= 0) {
1035 1036 1037 1038 1039 1040 1041 1042 1043 1044
					/* 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);
1045
		}
1046
	} while (r == 0);
1047 1048

	/* collect packages */
1049 1050 1051 1052 1053
	if (changeset != NULL) {
		generate_changeset(db, ss->best_solution, changeset,
				   ss->solver_flags);
	}
	if (solution != NULL) {
1054 1055
		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
1056
		*solution = ss->best_solution;
1057
	} else {
Timo Teräs's avatar
Timo Teräs committed
1058
		apk_package_array_free(&ss->best_solution);
1059 1060
	}
	r = ss->best_score.unsatisfiable;
1061
	apk_solver_free(db);
1062 1063 1064 1065 1066
	free(ss);

	return r;
}

Timo Teräs's avatar
Timo Teräs committed
1067 1068 1069
static void print_change(struct apk_database *db,
			 struct apk_change *change,
			 int cur, int total)
1070
{
Timo Teräs's avatar
Timo Teräs committed
1071 1072 1073 1074
	struct apk_name *name;
	struct apk_package *oldpkg = change->oldpkg;
	struct apk_package *newpkg = change->newpkg;
	const char *msg = NULL