solver.c 21.5 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* solver.c - Alpine Package Keeper (APK)
 * A backtracking, forward checking dependency graph solver.
 *
 * Copyright (C) 2011 Timo Teräs <timo.teras@iki.fi>
 * 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"

#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
#define APK_PKGSTF_BRANCH		2
#define APK_PKGSTF_ALT_BRANCH		4
29
#define APK_PKGSTF_INSTALLIF		8
30
#define APK_PKGSTF_DECIDED		16
31
32
33

struct apk_package_state {
	struct apk_package *backtrack;
34
	unsigned int topology_hard, topology_soft;
35
36
	unsigned short flags;
	unsigned short conflicts;
37
	unsigned short cur_unsatisfiable;
38
39
};

40
#define APK_NAMESTF_AVAILABILITY_CHECKED	1
41
42
#define APK_NAMESTF_LOCKED			2
#define APK_NAMESTF_NO_OPTIONS			4
43
44
45
struct apk_name_state {
	struct list_head unsolved_list;
	struct apk_package *chosen;
46
	unsigned short flags;
47
	unsigned short requirers;
48
	unsigned short install_ifs;
49
50
51
52
53
};

struct apk_solver_state {
	struct apk_database *db;
	struct apk_name_state *name_state;
54
55
	unsigned num_topology_positions;

56
57
58
59
	struct list_head unsolved_list_head;
	struct apk_package *latest_decision;
	unsigned int topology_position;
	unsigned int assigned_names;
60
61
	unsigned short cur_unsatisfiable;
	unsigned short allow_errors;
62
63

	struct apk_package_array *best_solution;
64
	unsigned short best_unsatisfiable;
65
66
};

67
68
69
70
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);
71

72
73
74
75
76
static inline struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
{
	return (struct apk_package_state*) pkg->state_ptr;
}

77
78
79
80
81
82
83
84
85
86
87
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;
}

88
89
90
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))
91
92
93
{
	int i, j;

94
95
96
	/* And sort the main dependencies */
	for (i = 0; i < depends->num; i++) {
		struct apk_dependency *dep = &depends->item[i];
97
98
99
100
		struct apk_name *name0 = dep->name;

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

102
103
104
105
			/* conflict depends on all to be not installed */
			if (dep->result_mask != APK_DEPMASK_CONFLICT &&
			    !apk_dep_is_satisfied(dep, pkg0))
				continue;
106
107

			cb(ss, pkg0);
108
109
		}
	}
110
}
111

112
113
114
115
116
117
118
119
120
121
122
123
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);
124

125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
		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 &&
				    (dep->result_mask == APK_DEPMASK_CONFLICT ||
				     apk_dep_is_satisfied(dep, pkg)))
					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);
	if (ps->topology_hard)
		return;

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

	ps->topology_soft = ps->topology_hard = ++ss->num_topology_positions;
	dbg_printf(PKG_VER_FMT ": topology_hard=%d\n",
		   PKG_VER_PRINTF(pkg), ps->topology_hard);
}

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);
	if (ps->topology_soft != ps->topology_hard)
		return;

	/* 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);
182
183
184
185
186
187
188
}

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

	for (i = 0; i < name->pkgs->num; i++)
189
		sort_soft_dependencies(ss, name->pkgs->item[i]);
190
191
}

192
193
194
195
196
197
198
199
200
201
static void prepare_name(struct apk_solver_state *ss, struct apk_name *name,
			 struct apk_name_state *ns)
{
	int i;

	if (ns->flags & APK_NAMESTF_AVAILABILITY_CHECKED)
		return;

	for (i = 0; i < name->pkgs->num; i++) {
		struct apk_package *pkg = name->pkgs->item[i];
202
		struct apk_package_state *ps = pkg_to_ps(pkg);
203
204
205
206
207
208
209
210
211
212
213
214

		/* if package is needed for (re-)install */
		if ((name->flags & APK_NAME_REINSTALL) || (pkg->ipkg == NULL)) {
			/* and it's not available, we can't use it */
			if (!pkg_available(ss->db, pkg))
				ps->conflicts++;
		}
	}

	ns->flags |= APK_NAMESTF_AVAILABILITY_CHECKED;
}

215
216
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))
217
{
218
	int i;
219
	for (i = 0; i < deps->num; i++)
220
		func(ss, &deps->item[i]);
221
222
}

223
static int get_pkg_expansion_flags(struct apk_solver_state *ss, struct apk_package *pkg)
224
225
{
	struct apk_name *name = pkg->name;
226
	int i, options = 0;
227
228
229

	/* check if the suggested package is the most preferred one of
	 * available packages for the name */
230
	for (i = 0; i < name->pkgs->num; i++) {
231
		struct apk_package *pkg0 = name->pkgs->item[i];
232
		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
233

234
235
236
237
		if (pkg0 == pkg || ps0 == NULL ||
		    ps0->topology_hard > ss->topology_position ||
		    (ps0->flags & APK_PKGSTF_DECIDED) ||
		    ps0->conflicts != 0)
238
239
			continue;

240
241
242
		if (apk_flags & APK_PREFER_AVAILABLE) {
			/* pkg available, pkg0 not */
			if (pkg->repos != 0 && pkg0->repos == 0)
243
				continue;
244
245
			/* pkg0 available, pkg not */
			if (pkg0->repos != 0 && pkg->repos == 0)
246
				return APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH;
247
248
		}

249
250
		if (!(apk_flags & APK_UPGRADE)) {
			/* not upgrading, prefer the installed package */
251
252
			if (pkg->ipkg == NULL && pkg0->ipkg != NULL)
				return APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH;
253
254
255
256
		}

		/* upgrading, or neither of the package is installed, so
		 * we just fall back comparing to versions */
257
		options++;
258
		if (apk_pkg_version_compare(pkg0, pkg) == APK_VERSION_GREATER)
259
			return APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH;
260
261
	}

262
	/* no package greater than the selected */
263
264
265
266
267
	if (options)
		return APK_PKGSTF_INSTALL | APK_PKGSTF_BRANCH;

	/* no other choice */
	return APK_PKGSTF_INSTALL;
268
269
}

270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg)
{
	struct apk_name_state *ns = &ss->name_state[pkg->name->id];
	int i, missing = 0;

	for (i = 0; i < pkg->install_if->num; i++) {
		struct apk_dependency *dep = &pkg->install_if->item[i];

		ns = &ss->name_state[dep->name->id];
		if (!(ns->flags & APK_NAMESTF_LOCKED) ||
		    !apk_dep_is_satisfied(dep, ns->chosen))
			missing++;
	}

	return missing;
}

287
static int update_name_state(struct apk_solver_state *ss,
288
289
			     struct apk_name *name, struct apk_name_state *ns,
			     int requirers_adjustment)
290
{
291
292
	struct apk_package *best_pkg = NULL;
	unsigned int best_topology = 0;
293
	int i, options = 0, skipped_options = 0;
294

295
296
	ns->requirers += requirers_adjustment;

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

301
302
303
		if (ps0 == NULL ||
		    ps0->topology_hard >= ss->topology_position ||
		    (ps0->flags & APK_PKGSTF_DECIDED))
304
305
			continue;

306
307
308
309
310
311
		if (ns->requirers == 0 && ns->install_ifs != 0 &&
		    install_if_missing(ss, pkg0)) {
			skipped_options++;
			continue;
		}

312
		options++;
313
314
315
316
317
		if (ps0->topology_soft < ss->topology_position &&
		    ps0->topology_soft > best_topology)
			best_pkg = pkg0, best_topology = ps0->topology_soft;
		else if (ps0->topology_hard > best_topology)
			best_pkg = pkg0, best_topology = ps0->topology_hard;
318
	}
319

320
	if (options == 0 && skipped_options == 0) {
321
322
		if (!(ns->flags & APK_NAMESTF_NO_OPTIONS)) {
			ss->cur_unsatisfiable += ns->requirers;
323
324
			if (ns->install_ifs)
				ss->cur_unsatisfiable++;
325
326
327
328
329
330
331
			ns->flags |= APK_NAMESTF_NO_OPTIONS;
		} else if (requirers_adjustment > 0) {
			ss->cur_unsatisfiable += requirers_adjustment;
		}
	} else
		ns->flags &= ~APK_NAMESTF_NO_OPTIONS;

332
333
	if ((options == 0 && skipped_options == 0) ||
	    (ns->requirers == 0 && ns->install_ifs == 0)) {
334
335
336
337
338
		if (list_hashed(&ns->unsolved_list)) {
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
			ns->chosen = NULL;
		}
339
340
		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);
341
	} else {
342
343
344
		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);
345
346
		if (!list_hashed(&ns->unsolved_list))
			list_add(&ns->unsolved_list, &ss->unsolved_list_head);
347
		ns->chosen = best_pkg;
348
349
	}

350
	return options + skipped_options;
351
352
}

353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
static void trigger_install_if(struct apk_solver_state *ss,
			       struct apk_package *pkg)
{
	if (install_if_missing(ss, pkg) == 0) {
		struct apk_name_state *ns = ns = &ss->name_state[pkg->name->id];

		dbg_printf("trigger_install_if: " PKG_VER_FMT " triggered\n",
			   PKG_VER_PRINTF(pkg));
		ns->install_ifs++;
		update_name_state(ss, pkg->name, ns, 0);
	}
}

static void untrigger_install_if(struct apk_solver_state *ss,
			       struct apk_package *pkg)
{
	if (install_if_missing(ss, pkg) != 1) {
		struct apk_name_state *ns = ns = &ss->name_state[pkg->name->id];

		dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n",
			   PKG_VER_PRINTF(pkg));
		ns->install_ifs--;
		update_name_state(ss, pkg->name, ns, 0);
	}
}

379
380
381
static void apply_decision(struct apk_solver_state *ss,
			   struct apk_package *pkg,
			   struct apk_package_state *ps)
382
383
384
385
386
387
388
389
{
	struct apk_name_state *ns = &ss->name_state[pkg->name->id];

	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++;
390
		ss->cur_unsatisfiable += ps->conflicts;
391
		ns->chosen = pkg;
392
393
394
395
396
397
398
399
		ns->flags |= APK_NAMESTF_LOCKED;

		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);
400
		foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
401
	} else {
402
		update_name_state(ss, pkg->name, ns, 0);
403
404
405
406
407
408
409
410
411
412
413
414
	}
}

static void undo_decision(struct apk_solver_state *ss,
			  struct apk_package *pkg,
			  struct apk_package_state *ps)
{
	struct apk_name_state *ns = &ss->name_state[pkg->name->id];

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

415
416
417
418
	if (ps->flags & APK_PKGSTF_INSTALLIF)
		ss->topology_position = ps->topology_soft;
	else
		ss->topology_position = ps->topology_hard;
419

420
421
	if (ps->flags & APK_PKGSTF_INSTALL) {
		ss->assigned_names--;
422
423

		foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
424
425
		foreach_dependency(ss, pkg->depends, undo_constraint);

426
427
		ns->flags &= ~APK_NAMESTF_LOCKED;
		ns->chosen = NULL;
428
	}
429

430
	ss->cur_unsatisfiable = ps->cur_unsatisfiable;
431
	update_name_state(ss, pkg->name, ns, 0);
432
433
}

434
435
static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
			  int flags)
436
{
437
	struct apk_package_state *ps = pkg_to_ps(pkg);
438
439

	ps->backtrack = ss->latest_decision;
440
	ps->flags = flags | APK_PKGSTF_DECIDED;
441
	ps->cur_unsatisfiable = ss->cur_unsatisfiable;
442
443
444
445
446
447
448
449
450

	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;
		ss->topology_position = ps->topology_hard;
	}
451
	ss->latest_decision = pkg;
452

453
454
455
456
457
458
	if (flags & APK_PKGSTF_BRANCH) {
		dbg_printf("push_decision: adding new BRANCH at topology_position %d\n",
			   ss->topology_position);
	} else
		ps->flags |= APK_PKGSTF_ALT_BRANCH;

459
460
461
462
	if (ps->flags & APK_PKGSTF_INSTALLIF)
		dbg_printf("triggers due to " PKG_VER_FMT "\n",
			   PKG_VER_PRINTF(pkg));

463
	apply_decision(ss, pkg, ps);
464
465
466
467
468
469
470
}

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

471
	while (ss->latest_decision != NULL) {
472
		pkg = ss->latest_decision;
473
		ps = pkg_to_ps(pkg);
474
475
476
477
478
		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);
479
480
			ps->flags &= ~(APK_PKGSTF_ALT_BRANCH | APK_PKGSTF_DECIDED);
			ss->latest_decision = ps->backtrack;
481
482
483
484
485
486
487
		} 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;

488
489
			apply_decision(ss, pkg, ps);
			return 0;
490
491
		}
	}
492
493
494

	dbg_printf("next_branch: no more branches\n");
	return 1;
495
496
}

497
static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
498
499
500
{
	struct apk_name *name = dep->name;
	struct apk_name_state *ns = &ss->name_state[name->id];
501
	int i;
502

503
	prepare_name(ss, name, ns);
504
505
506
507
508

	if (ns->flags & APK_NAMESTF_LOCKED) {
		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))
509
			ss->cur_unsatisfiable++;
510
511
512
		return;
	}

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

517
		if (ps0 == NULL ||
518
		    ps0->topology_hard >= ss->topology_position)
519
520
521
522
523
524
525
526
527
528
			continue;

		if (!apk_dep_is_satisfied(dep, pkg0)) {
			ps0->conflicts++;
			dbg_printf(PKG_VER_FMT ": conflicts++ -> %d\n",
				   PKG_VER_PRINTF(pkg0),
				   ps0->conflicts);
		}
	}

529
530
	update_name_state(ss, name, ns,
			  (dep->result_mask != APK_DEPMASK_CONFLICT) ? 1 : 0);
531
532
}

533
static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
534
535
536
{
	struct apk_name *name = dep->name;
	struct apk_name_state *ns = &ss->name_state[name->id];
537
538
539
540
541
542
543
	int i;

	if (ns->flags & APK_NAMESTF_LOCKED) {
		dbg_printf(PKG_VER_FMT " selected already for %s\n",
			   PKG_VER_PRINTF(ns->chosen), dep->name->name);
		return;
	}
544
545
546

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

549
		if (ps0->topology_hard >= ss->topology_position)
550
551
552
553
554
555
556
557
558
559
			continue;

		if (!apk_dep_is_satisfied(dep, pkg0)) {
			ps0->conflicts--;
			dbg_printf(PKG_VER_FMT ": conflicts-- -> %d\n",
				   PKG_VER_PRINTF(pkg0),
				   ps0->conflicts);
		}
	}

560
561
	update_name_state(ss, name, ns,
		(dep->result_mask != APK_DEPMASK_CONFLICT) ? -1 : 0);
562
563
564
565
}

static int expand_branch(struct apk_solver_state *ss)
{
566
567
	struct apk_name_state *ns;
	struct apk_package *pkg0 = NULL;
568
	unsigned int topology0 = 0;
569
570
571

	/* FIXME: change unsolved_list to a priority queue */
	list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
572
573
574
575
576
577
578
579
580
581
582
		/* 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;
		else if (pkg_to_ps(ns->chosen)->topology_hard > topology0)
			pkg0 = ns->chosen, topology0 = pkg_to_ps(pkg0)->topology_hard;
583
584
585
586
587
588
	}
	if (pkg0 == NULL) {
		dbg_printf("expand_branch: list is empty (%d unsatisfied)\n",
			   ss->cur_unsatisfiable);
		return 1;
	}
589

590
591
592
	/* someone needs to provide this name -- find next eligible
	 * provider candidate */
	ns = &ss->name_state[pkg0->name->id];
593
	dbg_printf("expand_branch: %s\n", pkg0->name->name);
594

595
	push_decision(ss, pkg0, get_pkg_expansion_flags(ss, pkg0));
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610

	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) {
611
		ps = pkg_to_ps(pkg);
612
613
614
		if (ps->flags & APK_PKGSTF_INSTALL) {
			if (i >= ss->assigned_names)
				abort();
615
			ss->best_solution->item[i++] = pkg;
616
		}
617
618
619
620
621
622
623

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

		pkg = ps->backtrack;
	}
624
625
626
627
628
629
630
631
632
633
	apk_package_array_resize(&ss->best_solution, i);
	ss->best_unsatisfiable = ss->cur_unsatisfiable;
}

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);
634
635
636
}

int apk_solver_solve(struct apk_database *db, struct apk_dependency_array *world,
637
		     struct apk_package_array **solution, int allow_errors)
638
639
{
	struct apk_solver_state *ss;
640
	int i, r;
641
642
643
644

	ss = calloc(1, sizeof(struct apk_solver_state));
	ss->db = db;
	ss->topology_position = -1;
645
646
	ss->best_unsatisfiable = -1;
	ss->allow_errors = allow_errors;
647
	list_init(&ss->unsolved_list_head);
648
649
650
651
	ss->name_state = calloc(db->available.names.num_items + 1, sizeof(struct apk_name_state));

	for (i = 0; i < world->num; i++)
		sort_name(ss, world->item[i].name);
652

653
654
	foreach_dependency(ss, world, apply_constraint);
	do {
655
656
		if (ss->allow_errors ||
		    ss->cur_unsatisfiable < ss->best_unsatisfiable) {
657
658
			r = expand_branch(ss);
			if (r) {
659
660
				dbg_printf("solution with %d unsatisfiable\n",
					   ss->cur_unsatisfiable);
661
662
663
664
665
666
667
668
669
670
671
672
673
				if (ss->cur_unsatisfiable == 0) {
					/* found solution - it is optimal because we permutate
					 * each preferred local option first, and permutations
					 * happen in topologally sorted order. */
					r = 0;
					break;
				}
				if (ss->cur_unsatisfiable < ss->best_unsatisfiable)
					record_solution(ss);
				r = next_branch(ss);
			}
		} else {
			r = next_branch(ss);
674
		}
675
	} while (r == 0);
676
677

	/* collect packages */
678
	if (r == 0 && ss->cur_unsatisfiable == 0) {
679
680
		record_solution(ss);
		*solution = ss->best_solution;
681
682
683
684
685
686
687
688
		r = 0;
	} else if (ss->allow_errors) {
		*solution = ss->best_solution;
		qsort(ss->best_solution->item, ss->best_solution->num,
		      sizeof(struct apk_package *), compare_package_name);
		r = ss->best_unsatisfiable;
	} else
		r = -1;
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703

	free(ss->name_state);
	free(ss);

	return r;
}

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 */
704
705
			return  pkg_to_ps(c2->oldpkg)->topology_hard -
				pkg_to_ps(c1->oldpkg)->topology_hard;
706
707
708
709
710
711
712
713

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

714
715
	return  pkg_to_ps(c1->newpkg)->topology_hard -
		pkg_to_ps(c2->newpkg)->topology_hard;
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
}

int apk_solver_generate_changeset(struct apk_database *db,
				  struct apk_package_array *solution,
				  struct apk_changeset *changeset)
{
	struct apk_name *name;
	struct apk_package *pkg, *pkg0;
	struct apk_installed_package *ipkg;
	int num_installs = 0, num_removed = 0, ci = 0;
	int i, j;

	/* calculate change set size */
	for (i = 0; i < solution->num; i++) {
		pkg = solution->item[i];
		name = pkg->name;
		if (pkg->ipkg == NULL || (name->flags & APK_NAME_REINSTALL))
			num_installs++;
		name->flags |= APK_NAME_VISITED;
	}

	list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
		if (!(ipkg->pkg->name->flags & APK_NAME_VISITED))
			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) {
		if (ipkg->pkg->name->flags & APK_NAME_VISITED)
			continue;
		changeset->changes->item[ci].oldpkg = ipkg->pkg;
		ci++;
	}
	for (i = 0; i < solution->num; i++) {
		pkg = solution->item[i];
		name = pkg->name;

		if (pkg->ipkg == NULL || (name->flags & APK_NAME_REINSTALL)) {
			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++;
		}
		name->flags &= ~APK_NAME_VISITED;
	}

	/* sort changeset to topology order */
	qsort(changeset->changes->item, changeset->changes->num,
	      sizeof(struct apk_change), compare_change);

	return 0;
}