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;