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