solver.c 22 KB
Newer Older
1
/* solver.c - Alpine Package Keeper (APK)
2
 * Up- and down-propagating, forwarding checking, deductive dependency solver.
3
 *
4
 * Copyright (C) 2008-2013 Timo Teräs <timo.teras@iki.fi>
5
6
7
8
9
10
11
 * 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.
 */

12
#include <stdint.h>
13
#include <unistd.h>
14
15
16
17
18
#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
19
20
#include "apk_print.h"

21
22
23
//#define DEBUG_PRINT

#ifdef DEBUG_PRINT
24
25
26
27
28
29
#include <stdio.h>
#define dbg_printf(args...) fprintf(stderr, args)
#else
#define dbg_printf(args...)
#endif

30
#define ASSERT(cond, fmt...)	if (!(cond)) { apk_error(fmt); *(char*)NULL = 0; }
31

32
33
struct apk_solver_state {
	struct apk_database *db;
34
35
36
37
38
	struct apk_changeset *changeset;
	struct list_head dirty_head;
	struct list_head unresolved_head;
	unsigned int errors;
	unsigned int num_selections, num_solution_entries;
39
	unsigned int solver_flags_inherit;
40
41
42
	unsigned int pinning_inherit;
	unsigned int default_repos;
	unsigned prefer_pinning : 1;
43
};
44

45
46
47
static struct apk_provider provider_none = {
	.pkg = NULL,
	.version = &apk_null_blob
48
49
};

50
51
52
void apk_solver_set_name_flags(struct apk_name *name,
			       unsigned short solver_flags,
			       unsigned short solver_flags_inheritable)
53
{
54
55
56
57
58
59
60
	int i;

	for (i = 0; i < name->providers->num; i++) {
		struct apk_package *pkg = name->providers->item[i].pkg;
		pkg->ss.solver_flags |= solver_flags;
		pkg->ss.solver_flags_inheritable |= solver_flags_inheritable;
	}
61
62
}

63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
static int get_tag(struct apk_database *db, unsigned int pinning_mask, unsigned int repos)
{
	int i;

	for (i = 0; i < db->num_repo_tags; i++) {
		if (!(BIT(i) & pinning_mask))
			continue;
		if (db->repo_tags[i].allowed_repos & repos)
			return i;
	}
	return APK_DEFAULT_REPOSITORY_TAG;
}

static unsigned int get_pkg_repos(struct apk_database *db, struct apk_package *pkg)
{
	return pkg->repos | (pkg->ipkg ? db->repo_tags[pkg->ipkg->repository_tag].allowed_repos : 0);
}

81
82
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))
83
{
84
85
86
	int i;
	for (i = 0; i < deps->num; i++)
		func(ss, &deps->item[i]);
87
}
88

89
90
static void foreach_name(struct apk_solver_state *ss, struct apk_name_array *names,
			 void (*func)(struct apk_solver_state *ss, struct apk_name *name))
91
{
92
93
94
95
	int i;
	for (i = 0; i < names->num; i++)
		if (names->item[i]->ss.seen)
			func(ss, names->item[i]);
96
97
}

98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
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_package *parent_pkg))
{
	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);

		for (j = 0; j < name0->providers->num; j++) {
			struct apk_provider *p0 = &name0->providers->item[j];

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

				if (dep->name == name &&
				    apk_dep_is_provided(dep, p0))
					break;
			}
			if (k >= p0->pkg->install_if->num)
				continue;

			/* pkg depends (via install_if) on pkg0 */
			cb(ss, p0->pkg, pkg);
		}
	}
}

129
static void queue_dirty(struct apk_solver_state *ss, struct apk_name *name)
130
{
131
132
133
	if (list_hashed(&name->ss.dirty_list) || name->ss.locked ||
	    (name->ss.requirers == 0 && !name->ss.reevaluate_iif))
		return;
134

135
136
	dbg_printf("queue_dirty: %s\n", name->name);
	list_add_tail(&name->ss.dirty_list, &ss->dirty_head);
137
138
}

139
static void queue_unresolved(struct apk_solver_state *ss, struct apk_name *name)
140
{
141
	int want;
142

143
144
	if (name->ss.locked)
		return;
145

146
147
148
149
150
151
	want = (name->ss.requirers > 0) || (name->ss.has_iif);
	dbg_printf("queue_unresolved: %s, want=%d\n", name->name, want);
	if (want && !list_hashed(&name->ss.unresolved_list))
		list_add(&name->ss.unresolved_list, &ss->unresolved_head);
	else if (!want && list_hashed(&name->ss.unresolved_list))
		list_del_init(&name->ss.unresolved_list);
152
153
}

154
static void reevaluate_deps(struct apk_solver_state *ss, struct apk_name *name)
155
{
156
157
	name->ss.reevaluate_deps = 1;
	queue_dirty(ss, name);
158
}
159

160
static void reevaluate_installif(struct apk_solver_state *ss, struct apk_name *name)
161
{
162
163
	name->ss.reevaluate_iif = 1;
	queue_dirty(ss, name);
164
165
}

166
static void disqualify_package(struct apk_solver_state *ss, struct apk_package *pkg, const char *reason)
167
168
169
{
	int i;

170
171
172
173
174
175
176
	dbg_printf("disqualify_package: " PKG_VER_FMT " (%s)\n", PKG_VER_PRINTF(pkg), reason);
	pkg->ss.available = 0;

	foreach_name(ss, pkg->name->rdepends, reevaluate_deps);
	for (i = 0; i < pkg->provides->num; i++)
		foreach_name(ss, pkg->provides->item[i].name->rdepends, reevaluate_deps);
	foreach_name(ss, pkg->name->rinstall_if, reevaluate_installif);
177
178
}

179
static int dependency_satisfiable(struct apk_solver_state *ss, struct apk_dependency *dep)
180
{
181
182
	struct apk_name *name = dep->name;
	int i;
183

184
185
	if (name->ss.locked)
		return apk_dep_is_provided(dep, &name->ss.chosen);
186

187
188
	if (name->ss.requirers == 0 && apk_dep_is_provided(dep, &provider_none))
		return TRUE;
189

190
191
192
193
194
195
	for (i = 0; i < name->providers->num; i++) {
		struct apk_package *pkg = name->providers->item[i].pkg;
		if (!pkg->ss.available)
			continue;
		if (apk_dep_is_provided(dep, &name->providers->item[i]))
			return TRUE;
196
197
	}

198
	return FALSE;
199
200
}

201
202
static void discover_name(struct apk_solver_state *ss, struct apk_name *name);
static void discover_names(struct apk_solver_state *ss, struct apk_dependency *dep)
203
{
204
	discover_name(ss, dep->name);
205
206
}

207
static void discover_name(struct apk_solver_state *ss, struct apk_name *name)
208
{
209
	struct apk_database *db = ss->db;
210
	unsigned int repos;
211
	int i, j;
212

213
214
	if (name->ss.seen)
		return;
215

216
	name->ss.seen = 1;
217
	for (i = 0; i < name->providers->num; i++) {
218
219
		struct apk_package *pkg = name->providers->item[i].pkg;
		if (pkg->ss.seen)
220
			continue;
221
		pkg->ss.seen = 1;
222
223
224
225
226
227
228
229
		pkg->ss.available = pkg->ipkg || (pkg->repos & db->available_repos);
		pkg->ss.pinning_allowed = APK_DEFAULT_PINNING_MASK;
		pkg->ss.pinning_preferred = APK_DEFAULT_PINNING_MASK;

		repos = get_pkg_repos(db, pkg);
		pkg->ss.tag_ok = !!(repos & ss->default_repos);
		pkg->ss.tag_preferred = !!(repos & ss->default_repos);

230
231
		foreach_dependency(ss, pkg->depends, discover_names);
		for (j = 0; j < pkg->depends->num; j++)
232
233
			pkg->ss.max_dep_chain = max(pkg->ss.max_dep_chain,
						    pkg->depends->item[j].name->ss.max_dep_chain+1);
234
		name->ss.max_dep_chain = max(name->ss.max_dep_chain, pkg->ss.max_dep_chain);
235
236
237
238
239
240

		dbg_printf("discover " PKG_VER_FMT ": tag_ok=%d, tag_pref=%d max_dep_chain=%d\n",
			PKG_VER_PRINTF(pkg),
			pkg->ss.tag_ok,
			pkg->ss.tag_preferred,
			pkg->ss.max_dep_chain);
241
	}
242
243
244
	/* Can't use foreach_name, as it checks the seen flag */
	for (i = 0; i < name->rinstall_if->num; i++)
		discover_name(ss, name->rinstall_if->item[i]);
245
246
}

247
static void name_requirers_changed(struct apk_solver_state *ss, struct apk_name *name)
248
{
249
250
251
	queue_unresolved(ss, name);
	foreach_name(ss, name->rinstall_if, reevaluate_installif);
	queue_dirty(ss, name);
252
253
}

254
255
256
257
258
259
260
261
262
263
264
265
266
static void inherit_pinning(struct apk_solver_state *ss, struct apk_package *pkg, unsigned int pinning, int prefer)
{
	unsigned int repo_mask = apk_db_get_pinning_mask_repos(ss->db, pinning);
	unsigned int repos = get_pkg_repos(ss->db, pkg);

	pkg->ss.pinning_allowed |= pinning;
	pkg->ss.tag_ok |= !!(repos & repo_mask);
	if (prefer) {
		pkg->ss.pinning_preferred |= pinning;
		pkg->ss.tag_preferred = !!(repos & apk_db_get_pinning_mask_repos(ss->db, pkg->ss.pinning_preferred));
	}
}

267
static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
268
{
269
	struct apk_name *name = dep->name;
270
	unsigned int solver_flags_inherit = ss->solver_flags_inherit;
271
	int i;
272

273
274
275
276
277
278
279
280
	dbg_printf("apply_constraint: %s%s%s" BLOB_FMT "\n",
		dep->conflict ? "!" : "",
		name->name,
		apk_version_op_string(dep->result_mask),
		BLOB_PRINTF(*dep->version));

	name->ss.requirers += !dep->conflict;
	name_requirers_changed(ss, name);
281

282
283
284
285
	for (i = 0; i < name->providers->num; i++) {
		struct apk_provider *p0 = &name->providers->item[i];
		struct apk_package *pkg0 = p0->pkg;
		int is_provided;
286

287
288
289
		is_provided = apk_dep_is_provided(dep, p0);
		dbg_printf("apply_constraint: provider: %s-" BLOB_FMT ": %d\n",
			pkg0->name->name, BLOB_PRINTF(*p0->version), is_provided);
290

291
292
293
		pkg0->ss.conflicts += !is_provided;
		if (unlikely(pkg0->ss.available && pkg0->ss.conflicts))
			disqualify_package(ss, pkg0, "conflicting dependency");
294

295
296
297
		if (is_provided) {
			pkg0->ss.solver_flags |= solver_flags_inherit;
			pkg0->ss.solver_flags_inheritable |= solver_flags_inherit;
298
299
300
301
302
303
			inherit_pinning(ss, pkg0, ss->pinning_inherit, ss->prefer_pinning);

			dbg_printf(PKG_VER_FMT ": tag_ok=%d, tag_pref=%d\n",
				PKG_VER_PRINTF(pkg0),
				pkg0->ss.tag_ok,
				pkg0->ss.tag_preferred);
304
		}
305
	}
306
307
}

308
static void reconsider_name(struct apk_solver_state *ss, struct apk_name *name)
309
{
310
311
312
313
314
	struct apk_name *name0;
	struct apk_dependency *dep;
	struct apk_package *pkg;
	int i, j, reevaluate_deps, reevaluate_iif;
	int first_candidate = -1, last_candidate = 0;
315
	int num_options = 0, num_tag_not_ok = 0, has_iif = 0;
316

317
	dbg_printf("reconsider_name: %s\n", name->name);
318

319
320
	reevaluate_deps = name->ss.reevaluate_deps;
	name->ss.reevaluate_deps = 0;
321

322
323
	reevaluate_iif = name->ss.reevaluate_iif;
	name->ss.reevaluate_iif = 0;
324

325
326
327
328
329
	/* propagate down by merging common dependencies and
	 * applying new constraints */
	for (i = 0; i < name->providers->num; i++) {
		struct apk_provider *p0 = &name->providers->item[i];
		struct apk_package *pkg = p0->pkg;
330

331
332
333
334
335
336
337
338
339
340
341
342
343
344
		/* check if this pkg's dependencies have become unsatisfiable */
		if (reevaluate_deps) {
			if (!pkg->ss.available)
				continue;
			for (j = 0; j < pkg->depends->num; j++) {
				dep = &pkg->depends->item[j];
				if (!dependency_satisfiable(ss, dep)) {
					disqualify_package(ss, pkg, "dependency no longer satisfiable");
					break;
				}
			}
		}
		if (!pkg->ss.available)
			continue;
345

346
347
348
349
350
351
352
353
354
		if (reevaluate_iif) {
			for (j = 0; j < pkg->install_if->num; j++) {
				dep = &pkg->install_if->item[j];
				if (!dependency_satisfiable(ss, dep))
					break;
			}
			pkg->ss.iif_triggered = (j >= pkg->install_if->num);
			has_iif |= pkg->ss.iif_triggered;
		}
Timo Teräs's avatar
Timo Teräs committed
355

356
357
		if (name->ss.requirers == 0 && !pkg->ss.iif_triggered)
			continue;
358

359
		num_options++;
360
		num_tag_not_ok += !pkg->ss.tag_ok;
Timo Teräs's avatar
Timo Teräs committed
361

362
363
364
365
366
367
368
369
370
371
372
373
374
		/* merge common dependencies */
		if (first_candidate == -1)
			first_candidate = i;
		for (j = 0; j < pkg->depends->num; j++) {
			dep = &pkg->depends->item[j];
			if (dep->conflict /*&& dep->result_mask != APK_DEPMASK_ANY*/)
				continue;
			name0 = dep->name;
			if (name0->ss.merge_index == last_candidate)
				name0->ss.merge_index = i + 1;
		}
		last_candidate = i + 1;
	}
375
	name->ss.has_options = (num_options > 1 || num_tag_not_ok > 0);
376
377
378
379
380
381
382
383
384
385
	name->ss.has_iif = has_iif;
	queue_unresolved(ss, name);

	if (first_candidate != -1) {
		/* TODO: could merge versioning bits too */
		/* propagate down common dependencies */
		pkg = name->providers->item[first_candidate].pkg;
		for (j = 0; j < pkg->depends->num; j++) {
			dep = &pkg->depends->item[j];
			if (dep->conflict && dep->result_mask != APK_DEPMASK_ANY)
386
				continue;
387
388
389
390
391
392
393
394
395
396
397
			name0 = dep->name;
			if (name0->ss.merge_index == last_candidate) {
				/* common dependency name with all */
				if (name0->ss.requirers == 0) {
					dbg_printf("%s common dependency: %s\n",
						   name->name, name0->name);
					name0->ss.requirers++;
					name_requirers_changed(ss, name0);
				}
			}
			name0->ss.merge_index = 0;
Timo Teräs's avatar
Timo Teräs committed
398
399
		}
	}
400
401
	dbg_printf("reconsider_name: %s [finished], has_options=%d\n",
		name->name, name->ss.has_options);
402
403
}

404
405
static int compare_providers(struct apk_solver_state *ss,
			     struct apk_provider *pA, struct apk_provider *pB)
406
{
407
408
	struct apk_database *db = ss->db;
	struct apk_package *pkgA = pA->pkg, *pkgB = pB->pkg;
409
	unsigned int solver_flags;
410
	int r;
411

412
413
414
	/* Prefer existing package */
	if (pkgA == NULL || pkgB == NULL)
		return (pkgA != NULL) - (pkgB != NULL);
415

416
417
418
419
	/* Prefer without errors */
	r = (int)pkgA->ss.available - (int)pkgB->ss.available;
	if (r)
		return r;
420

421
422
423
424
425
	/* Prefer allowed pinning */
	r = (int)pkgA->ss.tag_ok - (int)pkgB->ss.tag_ok;
	if (r)
		return r;

426
	/* Prefer available */
427
428
	solver_flags = pkgA->ss.solver_flags | pkgB->ss.solver_flags;
	if (solver_flags & APK_SOLVERF_AVAILABLE) {
429
430
431
432
		r = !!(pkgA->repos & db->available_repos) -
		    !!(pkgB->repos & db->available_repos);
		if (r)
			return r;
433
434
	}

435
436
437
438
439
	/* Prefer preferred pinning */
	r = (int)pkgA->ss.tag_preferred - (int)pkgB->ss.tag_preferred;
	if (r)
		return r;

440
	/* Prefer installed */
441
	if (!(solver_flags & APK_SOLVERF_UPGRADE)) {
442
443
444
445
		r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
		if (r)
			return r;
	}
446

447
448
449
450
451
452
453
	/* Select latest by requested name */
	switch (apk_version_compare_blob(*pA->version, *pB->version)) {
	case APK_VERSION_LESS:
		return -1;
	case APK_VERSION_GREATER:
		return 1;
	}
454

455
456
457
458
459
460
461
462
463
	/* Select latest by principal name */
	if (pkgA->name == pkgB->name) {
		switch (apk_version_compare_blob(*pkgA->version, *pkgB->version)) {
		case APK_VERSION_LESS:
			return -1;
		case APK_VERSION_GREATER:
			return 1;
		}
	}
Timo Teräs's avatar
Timo Teräs committed
464

465
466
467
468
	/* Prefer installed (matches here if upgrading) */
	r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
	if (r)
		return r;
469

470
471
	/* Prefer lowest available repository */
	return ffsl(pkgB->repos) - ffsl(pkgA->repos);
472
}
473

474
475
476
477
478
479
static void inherit_pinning_from_pkg(struct apk_solver_state *ss, struct apk_package *rinstall_if, struct apk_package *parent_pkg)
{
	inherit_pinning(ss, rinstall_if, parent_pkg->ss.pinning_allowed, 0);
}

static void assign_name(struct apk_solver_state *ss, struct apk_name *name, struct apk_provider p)
480
{
481
482
483
484
485
486
487
488
489
	int i;

	if (name->ss.locked) {
		/* If both are providing this name without version, it's ok */
		if (p.version == &apk_null_blob &&
		    name->ss.chosen.version == &apk_null_blob)
			return;
		/* Othewise providing locked item is an error */
		ss->errors++;
490
		return;
491
	}
492

493
494
	if (p.pkg)
		dbg_printf("assign %s to "PKG_VER_FMT"\n", name->name, PKG_VER_PRINTF(p.pkg));
495

496
497
498
499
500
501
502
	name->ss.locked = 1;
	name->ss.chosen = p;
	if (list_hashed(&name->ss.unresolved_list))
		list_del(&name->ss.unresolved_list);
	if (list_hashed(&name->ss.dirty_list))
		list_del(&name->ss.dirty_list);

503
504
505
506
	/* propagate pinning to install_if candidates */
	if (p.pkg)
		foreach_rinstall_if_pkg(ss, p.pkg, inherit_pinning_from_pkg);

507
508
509
510
511
512
513
514
515
	/* disqualify all conflicting packages */
	for (i = 0; i < name->providers->num; i++) {
		if (name->providers->item[i].pkg == p.pkg)
			continue;
		if (p.version == &apk_null_blob &&
		    name->providers->item[i].version == &apk_null_blob)
			continue;
		disqualify_package(ss, name->providers->item[i].pkg,
				   "conflicting provides");
516
	}
517
518

	foreach_name(ss, name->rdepends, reevaluate_deps);
519
520
}

521
static void select_package(struct apk_solver_state *ss, struct apk_name *name)
522
{
523
524
525
	struct apk_provider chosen = { NULL, &apk_null_blob };
	struct apk_package *pkg = NULL;
	int i;
526

527
	dbg_printf("select_package: %s\n", name->name);
528

529
530
	if (name->ss.requirers || name->ss.has_iif) {
		for (i = 0; i < name->providers->num; i++) {
531
532
533
			if (name->ss.requirers == 0 &&
			    (!name->providers->item[i].pkg->ss.iif_triggered ||
			     !name->providers->item[i].pkg->ss.tag_ok))
534
				continue;
535
536
			if (compare_providers(ss, &name->providers->item[i], &chosen) > 0)
				chosen = name->providers->item[i];
537
		}
538
	}
539

540
541
542
543
544
545
546
547
	pkg = chosen.pkg;
	if (pkg) {
		if (chosen.version == &apk_null_blob) {
			/* Pure virtual package */
			assign_name(ss, name, provider_none);
			ss->errors++;
			return;
		}
548
		if (!pkg->ss.available || !pkg->ss.tag_ok)
549
550
551
552
553
554
			ss->errors++;
		dbg_printf("selecting: " PKG_VER_FMT ", available: %d\n", PKG_VER_PRINTF(pkg), pkg->ss.available);
		assign_name(ss, pkg->name, APK_PROVIDER_FROM_PACKAGE(pkg));
		for (i = 0; i < pkg->provides->num; i++) {
			struct apk_dependency *p = &pkg->provides->item[i];
			assign_name(ss, p->name, APK_PROVIDER_FROM_PROVIDES(pkg, p));
555
		}
556
		ss->solver_flags_inherit = pkg->ss.solver_flags_inheritable;
557
		ss->pinning_inherit = pkg->ss.pinning_allowed;
558
		foreach_dependency(ss, pkg->depends, apply_constraint);
559
		ss->solver_flags_inherit = 0;
560
		ss->pinning_inherit = 0;
561
562
563
564
565
566
		ss->num_selections++;
	} else {
		dbg_printf("selecting: %s [unassigned]\n", name->name);
		assign_name(ss, name, provider_none);
		if (name->ss.requirers)
			ss->errors++;
567
	}
568
569
}

570
571
572
573
static void generate_change_dep(struct apk_solver_state *ss, struct apk_dependency *dep);
static void generate_change_iif(struct apk_solver_state *ss, struct apk_name *name);

static void generate_change(struct apk_solver_state *ss, struct apk_name *name)
574
{
575
576
577
578
579
580
	struct apk_package *pkg = name->ss.chosen.pkg, *opkg;
	struct apk_changeset *changeset = ss->changeset;
	struct apk_change *change;

	if (pkg == NULL)
		return;
581

582
	if (pkg->ss.in_changeset)
583
		return;
584
585
586
587
588
589
590
591
592
593
594
595
	pkg->ss.in_changeset = 1;
	pkg->name->ss.in_changeset = 1;

	foreach_dependency(ss, pkg->depends, generate_change_dep);

	change = &changeset->changes->item[ss->num_solution_entries++];
	dbg_printf("Selecting: "PKG_VER_FMT"%s\n", PKG_VER_PRINTF(pkg), pkg->ss.available ? "" : " [NOT AVAILABLE]");
	opkg = apk_pkg_get_installed(pkg->name);
	*change = (struct apk_change) {
		.old_pkg = opkg,
		.old_repository_tag = opkg ? opkg->ipkg->repository_tag : 0,
		.new_pkg = pkg,
596
		.new_repository_tag = get_tag(ss->db, pkg->ss.pinning_allowed, get_pkg_repos(ss->db, pkg)),
597
		.reinstall = !!(pkg->ss.solver_flags & APK_SOLVERF_REINSTALL),
598
599
600
601
602
603
604
605
	};
	if (change->new_pkg == NULL)
		changeset->num_remove++;
	else if (change->old_pkg == NULL)
		changeset->num_install++;
	else if (change->new_pkg != change->old_pkg || change->reinstall ||
		 change->new_repository_tag != change->old_repository_tag)
		changeset->num_adjust++;
606

607
	foreach_name(ss, pkg->name->rinstall_if, generate_change_iif);
608
609
}

610
static void generate_change_iif(struct apk_solver_state *ss, struct apk_name *name)
611
{
612
613
	struct apk_package *pkg = name->ss.chosen.pkg;
	int i;
614

615
	if (pkg == NULL)
616
617
		return;

618
619
620
	for (i = 0; i < pkg->install_if->num; i++) {
		struct apk_dependency *dep0 = &pkg->install_if->item[i];
		struct apk_name *name0 = dep0->name;
621

622
623
624
625
		if (!name0->ss.in_changeset)
			return;
		if (!apk_dep_is_provided(dep0, &name0->ss.chosen))
			return;
626
627
	}

628
	generate_change(ss, name);
629
630
}

631
static void generate_change_dep(struct apk_solver_state *ss, struct apk_dependency *dep)
632
{
633
	struct apk_name *name = dep->name;
634

635
636
	if (!apk_dep_is_provided(dep, &name->ss.chosen))
		ss->errors++;
637

638
639
	generate_change(ss, name);
}
640

641
642
643
644
static void generate_changeset(struct apk_solver_state *ss, struct apk_dependency_array *world)
{
	struct apk_changeset *changeset = ss->changeset;
	struct apk_installed_package *ipkg;
645

646
647
648
649
650
	list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list) {
		struct apk_name *name = ipkg->pkg->name;
		if (name->ss.chosen.pkg == NULL && !name->ss.locked)
			ss->num_selections++;
	}
Timo Teräs's avatar
Timo Teräs committed
651

652
653
	apk_change_array_resize(&ss->changeset->changes, ss->num_selections);
	foreach_dependency(ss, world, generate_change_dep);
654

655
656
657
658
659
660
661
662
663
664
	/* FIXME: could order better the removals of unneeded packages */
	list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list) {
		struct apk_name *name = ipkg->pkg->name;
		if (name->ss.chosen.pkg == NULL && !name->ss.in_changeset) {
			struct apk_change *change = &changeset->changes->item[ss->num_solution_entries++];
			*change = (struct apk_change) {
				.old_pkg = ipkg->pkg,
				.new_pkg = NULL,
			};
			changeset->num_remove++;
665
666
667
		}
	}

668
	changeset->num_total_changes = changeset->num_install + changeset->num_remove + changeset->num_adjust;
669

670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
#if 1
	/* FIXME: calculate num_solution_entries correctly */
	ASSERT(ss->num_solution_entries <= changeset->changes->num,
		"Got %d changes, but expected %d\n",
		ss->num_solution_entries, changeset->changes->num);
	apk_change_array_resize(&ss->changeset->changes, ss->num_solution_entries);
#else
	ASSERT(ss->num_solution_entries == changeset->changes->num,
		"Got %d changes, but expected %d\n",
		ss->num_solution_entries, changeset->changes->num);
#endif
}

static int free_state(apk_hash_item item, void *ctx)
{
	struct apk_name *name = (struct apk_name *) item;
	memset(&name->ss, 0, sizeof(name->ss));
	return 0;
}
Timo Teräs's avatar
Timo Teräs committed
689

690
691
692
693
694
static int free_package(apk_hash_item item, void *ctx)
{
	struct apk_package *pkg = (struct apk_package *) item;
	memset(&pkg->ss, 0, sizeof(pkg->ss));
	return 0;
695
696
}

697
698
699
700
int apk_solver_solve(struct apk_database *db,
		     unsigned short solver_flags,
		     struct apk_dependency_array *world,
		     struct apk_changeset *changeset)
701
{
702
703
	struct apk_name *name, *name0;
	struct apk_solver_state ss_data, *ss = &ss_data;
704
	int i;
705

706
707
708
	memset(ss, 0, sizeof(*ss));
	ss->db = db;
	ss->changeset = changeset;
709
	ss->default_repos = apk_db_get_pinning_mask_repos(db, APK_DEFAULT_PINNING_MASK);
710
711
	list_init(&ss->dirty_head);
	list_init(&ss->unresolved_head);
712

713
	foreach_dependency(ss, world, discover_names);
714

715
	/* FIXME: If filename specified, force to use it */
716

717
	dbg_printf("applying world\n");
718
	ss->prefer_pinning = 1;
719
	ss->solver_flags_inherit = solver_flags;
720
	for (i = 0; i < world->num; i++) {
721
		struct apk_dependency *dep = &world->item[i];
722
		name = dep->name;
723
		name->ss.in_world_dependency = 1;
724
		ss->pinning_inherit = BIT(dep->repository_tag);
725
		apply_constraint(ss, dep);
726
	}
727
	ss->solver_flags_inherit = 0;
728
729
	ss->pinning_inherit = 0;
	ss->prefer_pinning = 0;
730
	dbg_printf("applying world [finished]\n");
731

732
	do {
733
734
735
		while (!list_empty(&ss->dirty_head)) {
			name = list_pop(&ss->dirty_head, struct apk_name, ss.dirty_list);
			reconsider_name(ss, name);
736
		}
Timo Teräs's avatar
Timo Teräs committed
737

738
739
		name = NULL;
		list_for_each_entry(name0, &ss->unresolved_head, ss.unresolved_list) {
740
			if ((!name0->ss.has_options) && name0->ss.requirers > 0) {
741
				name = name0;
Timo Teräs's avatar
Timo Teräs committed
742
				break;
743
744
745
			}
			if (name == NULL)
				goto prefer;
746
			if (name0->ss.requirers == 0 && name->ss.requirers > 0)
Timo Teräs's avatar
Timo Teräs committed
747
				continue;
748
			if (name0->ss.requirers > 0 && name->ss.requirers == 0)
749
				goto prefer;
750
751
			if (name0->ss.max_dep_chain < name->ss.max_dep_chain)
				continue;
752
753
		prefer:
			name = name0;
754
		}
755
756
		if (name == NULL)
			break;
757

758
759
		select_package(ss, name);
	} while (1);
760

761
	generate_changeset(ss, world);
762

763
764
	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
765

766
	dbg_printf("solver done, errors=%d\n", ss->errors);
Timo Teräs's avatar
Timo Teräs committed
767

768
	return ss->errors;
769
}