solver.c 24.5 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
	struct apk_provider *p;
55

56
57
	foreach_array_item(p, name->providers) {
		struct apk_package *pkg = p->pkg;
58
59
60
		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
81
82
83
84
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);
}

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))
{
85
86
87
	struct apk_name *name = pkg->name, *name0, **pname0;
	struct apk_dependency *dep;
	struct apk_provider *p0;
88

89
90
	foreach_array_item(pname0, pkg->name->rinstall_if) {
		name0 = *pname0;
91
		dbg_printf(PKG_VER_FMT ": rinstall_if %s\n", PKG_VER_PRINTF(pkg), name0->name);
92
93
94
95
96
		foreach_array_item(p0, name0->providers) {
			foreach_array_item(dep, p0->pkg->install_if) {
				if (dep->name == name && apk_dep_is_provided(dep, p0)) {
					/* pkg depends (via install_if) on pkg0 */
					cb(ss, p0->pkg, pkg);
97
					break;
98
				}
99
100
101
102
103
			}
		}
	}
}

104
105
106
107
108
109
110
111
static void mark_error(struct apk_solver_state *ss, struct apk_package *pkg)
{
	if (pkg == NULL || pkg->ss.error)
		return;
	pkg->ss.error = 1;
	ss->errors++;
}

112
static void queue_dirty(struct apk_solver_state *ss, struct apk_name *name)
113
{
114
115
116
	if (list_hashed(&name->ss.dirty_list) || name->ss.locked ||
	    (name->ss.requirers == 0 && !name->ss.reevaluate_iif))
		return;
117

118
119
	dbg_printf("queue_dirty: %s\n", name->name);
	list_add_tail(&name->ss.dirty_list, &ss->dirty_head);
120
121
}

122
static void queue_unresolved(struct apk_solver_state *ss, struct apk_name *name)
123
{
124
	int want;
125

126
127
	if (name->ss.locked)
		return;
128

129
130
131
132
133
134
	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);
135
136
}

137
static void reevaluate_reverse_deps(struct apk_solver_state *ss, struct apk_name *name)
138
{
139
140
141
142
143
144
145
146
147
	struct apk_name **pname0, *name0;

	foreach_array_item(pname0, name->rdepends) {
		name0 = *pname0;
		if (!name0->ss.seen)
			continue;
		name0->ss.reevaluate_deps = 1;
		queue_dirty(ss, name0);
	}
148
}
149

150
static void reevaluate_reverse_installif(struct apk_solver_state *ss, struct apk_name *name)
151
{
152
153
154
155
156
157
158
159
160
	struct apk_name **pname0, *name0;

	foreach_array_item(pname0, name->rinstall_if) {
		name0 = *pname0;
		if (!name0->ss.seen)
			continue;
		name0->ss.reevaluate_iif = 1;
		queue_dirty(ss, name0);
	}
161
162
}

163
static void disqualify_package(struct apk_solver_state *ss, struct apk_package *pkg, const char *reason)
164
{
165
	struct apk_dependency *p;
166

167
168
	dbg_printf("disqualify_package: " PKG_VER_FMT " (%s)\n", PKG_VER_PRINTF(pkg), reason);
	pkg->ss.available = 0;
169
170
171
172
	reevaluate_reverse_deps(ss, pkg->name);
	foreach_array_item(p, pkg->provides)
		reevaluate_reverse_deps(ss, p->name);
	reevaluate_reverse_installif(ss, pkg->name);
173
174
}

175
static int dependency_satisfiable(struct apk_solver_state *ss, struct apk_dependency *dep)
176
{
177
	struct apk_name *name = dep->name;
178
	struct apk_provider *p;
179

180
181
	if (name->ss.locked)
		return apk_dep_is_provided(dep, &name->ss.chosen);
182

183
184
	if (name->ss.requirers == 0 && apk_dep_is_provided(dep, &provider_none))
		return TRUE;
185

186
187
	foreach_array_item(p, name->providers)
		if (p->pkg->ss.available && apk_dep_is_provided(dep, p))
188
			return TRUE;
189

190
	return FALSE;
191
192
}

193
static void discover_name(struct apk_solver_state *ss, struct apk_name *name)
194
{
195
	struct apk_database *db = ss->db;
196
197
198
	struct apk_name **pname0;
	struct apk_provider *p;
	struct apk_dependency *dep;
199
	unsigned int repos;
200

201
202
	if (name->ss.seen)
		return;
203

204
	name->ss.seen = 1;
205
206
	foreach_array_item(p, name->providers) {
		struct apk_package *pkg = p->pkg;
207
		if (pkg->ss.seen)
208
			continue;
209
		pkg->ss.seen = 1;
210
211
212
213
214
215
216
217
		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);

218
219
		foreach_array_item(dep, pkg->depends) {
			discover_name(ss, dep->name);
220
			pkg->ss.max_dep_chain = max(pkg->ss.max_dep_chain,
221
222
						    dep->name->ss.max_dep_chain+1);
		}
223
		name->ss.max_dep_chain = max(name->ss.max_dep_chain, pkg->ss.max_dep_chain);
224

225
		dbg_printf("discover " PKG_VER_FMT ": tag_ok=%d, tag_pref=%d max_dep_chain=%d available=%d\n",
226
227
228
			PKG_VER_PRINTF(pkg),
			pkg->ss.tag_ok,
			pkg->ss.tag_preferred,
229
230
			pkg->ss.max_dep_chain,
			pkg->ss.available);
231
	}
232
233
	foreach_array_item(pname0, name->rinstall_if)
		discover_name(ss, *pname0);
234
235
}

236
static void name_requirers_changed(struct apk_solver_state *ss, struct apk_name *name)
237
{
238
	queue_unresolved(ss, name);
239
	reevaluate_reverse_installif(ss, name);
240
	queue_dirty(ss, name);
241
242
}

243
244
245
246
247
248
249
250
251
252
253
254
255
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));
	}
}

256
static void apply_constraint(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep)
257
{
258
	struct apk_name *name = dep->name;
259
	struct apk_provider *p0;
260
	unsigned int solver_flags_inherit = ss->solver_flags_inherit;
261
	int is_provided;
262

263
264
265
266
267
268
269
	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;
270
271
	if (name->ss.requirers == 1 && !dep->conflict)
		name_requirers_changed(ss, name);
272

273
	foreach_array_item(p0, name->providers) {
274
		struct apk_package *pkg0 = p0->pkg;
275

276
277
278
		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);
279

280
281
282
		pkg0->ss.conflicts += !is_provided;
		if (unlikely(pkg0->ss.available && pkg0->ss.conflicts))
			disqualify_package(ss, pkg0, "conflicting dependency");
283

284
285
286
		if (is_provided) {
			pkg0->ss.solver_flags |= solver_flags_inherit;
			pkg0->ss.solver_flags_inheritable |= solver_flags_inherit;
287
288
289
290
291
292
			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);
293
		}
294
	}
295
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
327
328
329
330
static void exclude_non_providers(struct apk_solver_state *ss, struct apk_name *name, struct apk_name *must_provide)
{
	struct apk_provider *p;
	struct apk_dependency *d;

	dbg_printf("%s must provide %s\n", name->name, must_provide->name);

	foreach_array_item(p, name->providers) {
		if (p->pkg->name == must_provide)
			goto next;
		foreach_array_item(d, p->pkg->provides)
			if (d->name == must_provide)
				goto next;
		disqualify_package(ss, p->pkg, "provides transitivity");
	next: ;
	}
}

static inline void merge_index(unsigned short *index, int num_options)
{
	if (*index == num_options)
		*index = num_options + 1;
}

static inline int merge_index_complete(unsigned short *index, int num_options)
{
	int ret;

	ret = (*index == num_options);
	*index = 0;

	return ret;
}

331
static void reconsider_name(struct apk_solver_state *ss, struct apk_name *name)
332
{
333
	struct apk_name *name0, **pname0;
334
	struct apk_dependency *dep;
335
	struct apk_package *first_candidate = NULL, *pkg;
336
337
	struct apk_provider *p;
	int reevaluate_deps, reevaluate_iif;
338
	int num_options = 0, num_tag_not_ok = 0, has_iif = 0;
339

340
	dbg_printf("reconsider_name: %s\n", name->name);
341

342
343
	reevaluate_deps = name->ss.reevaluate_deps;
	reevaluate_iif = name->ss.reevaluate_iif;
344
	name->ss.reevaluate_deps = 0;
345
	name->ss.reevaluate_iif = 0;
346

347
348
	/* propagate down by merging common dependencies and
	 * applying new constraints */
349
	foreach_array_item(p, name->providers) {
350
		/* check if this pkg's dependencies have become unsatisfiable */
351
		pkg = p->pkg;
Timo Teräs's avatar
Timo Teräs committed
352
		pkg->ss.dependencies_merged = 0;
353
354
355
		if (reevaluate_deps) {
			if (!pkg->ss.available)
				continue;
356
			foreach_array_item(dep, pkg->depends) {
357
358
359
360
361
362
363
364
				if (!dependency_satisfiable(ss, dep)) {
					disqualify_package(ss, pkg, "dependency no longer satisfiable");
					break;
				}
			}
		}
		if (!pkg->ss.available)
			continue;
365

366
		if (reevaluate_iif) {
367
368
369
370
			pkg->ss.iif_triggered = 1;
			foreach_array_item(dep, pkg->install_if) {
				if (!dependency_satisfiable(ss, dep)) {
					pkg->ss.iif_triggered = 0;
371
					break;
372
				}
373
374
375
			}
			has_iif |= pkg->ss.iif_triggered;
		}
Timo Teräs's avatar
Timo Teräs committed
376

377
378
		if (name->ss.requirers == 0 && !pkg->ss.iif_triggered)
			continue;
379

380
		/* merge common dependencies */
Timo Teräs's avatar
Timo Teräs committed
381
		pkg->ss.dependencies_merged = 1;
382
383
		if (first_candidate == NULL)
			first_candidate = pkg;
384
385
386
387
388
389
390
391
392
393

		/* FIXME: can merge also conflicts */
		foreach_array_item(dep, pkg->depends)
			if (!dep->conflict)
				merge_index(&dep->name->ss.merge_depends, num_options);

		merge_index(&pkg->name->ss.merge_provides, num_options);
		foreach_array_item(dep, pkg->provides)
			if (dep->version != &apk_null_blob)
				merge_index(&dep->name->ss.merge_provides, num_options);
394
395
396

		num_tag_not_ok += !pkg->ss.tag_ok;
		num_options++;
397
	}
398
	name->ss.has_options = (num_options > 1 || num_tag_not_ok > 0);
399
400
401
	name->ss.has_iif = has_iif;
	queue_unresolved(ss, name);

402
	if (first_candidate != NULL) {
403
		pkg = first_candidate;
404
405
406
		foreach_array_item(p, name->providers)
			p->pkg->ss.dependencies_used = p->pkg->ss.dependencies_merged;

407
		/* propagate down common dependencies */
408
409
		if (num_options == 1) {
			/* FIXME: keeps increasing counts, use bit fields instead? */
410
411
412
			foreach_array_item(dep, pkg->depends)
				if (merge_index_complete(&dep->name->ss.merge_depends, num_options))
					apply_constraint(ss, pkg, dep);
413
414
		} else {
			/* FIXME: could merge versioning bits too */
415
			foreach_array_item(dep, pkg->depends) {
416
				name0 = dep->name;
417
418
				if (merge_index_complete(&name0->ss.merge_depends, num_options) &&
				    name0->ss.requirers == 0) {
419
					/* common dependency name with all */
420
421
422
423
					dbg_printf("%s common dependency: %s\n",
						   name->name, name0->name);
					name0->ss.requirers++;
					name_requirers_changed(ss, name0);
424
425
				}
			}
Timo Teräs's avatar
Timo Teräs committed
426
		}
427
428
429
430
431
432
433

		/* provides transitivity */
		if (merge_index_complete(&pkg->name->ss.merge_provides, num_options))
			exclude_non_providers(ss, pkg->name, name);
		foreach_array_item(dep, pkg->provides)
			if (merge_index_complete(&dep->name->ss.merge_provides, num_options))
				exclude_non_providers(ss, dep->name, name);
Timo Teräs's avatar
Timo Teräs committed
434
	}
435

436
437
438
439
440
441
442
443
444
445
446
	name->ss.reverse_deps_done = 1;
	foreach_array_item(pname0, name->rdepends) {
		name0 = *pname0;
		if (name0->ss.seen && !name0->ss.locked) {
			name->ss.reverse_deps_done = 0;
			break;
		}
	}

	dbg_printf("reconsider_name: %s [finished], has_options=%d, reverse_deps_done=%d\n",
		name->name, name->ss.has_options, name->ss.reverse_deps_done);
447
448
}

449
450
static int compare_providers(struct apk_solver_state *ss,
			     struct apk_provider *pA, struct apk_provider *pB)
451
{
452
453
	struct apk_database *db = ss->db;
	struct apk_package *pkgA = pA->pkg, *pkgB = pB->pkg;
454
	unsigned int solver_flags;
455
	int r;
456

457
458
459
	/* Prefer existing package */
	if (pkgA == NULL || pkgB == NULL)
		return (pkgA != NULL) - (pkgB != NULL);
460

461
462
463
464
465
466
467
468
469
	/* Latest version required? */
	solver_flags = pkgA->ss.solver_flags | pkgB->ss.solver_flags;
	if ((solver_flags & APK_SOLVERF_LATEST) &&
	    (pkgA->ss.pinning_allowed == APK_DEFAULT_PINNING_MASK) &&
	    (pkgB->ss.pinning_allowed == APK_DEFAULT_PINNING_MASK)) {
		/* Prefer allowed pinning */
		r = (int)pkgA->ss.tag_ok - (int)pkgB->ss.tag_ok;
		if (r)
			return r;
470

471
472
473
474
475
476
477
478
479
480
481
		/* Prefer available */
		if (solver_flags & (APK_SOLVERF_AVAILABLE | APK_SOLVERF_REINSTALL)) {
			r = !!(pkgA->repos & db->available_repos) - !!(pkgB->repos & db->available_repos);
			if (r)
				return r;
		}
	} else {
		/* Prefer without errors */
		r = (int)pkgA->ss.available - (int)pkgB->ss.available;
		if (r)
			return r;
Timo Teräs's avatar
Timo Teräs committed
482

483
484
485
486
487
		/* Prefer those that were in last dependency merging group */
		r = (int)pkgA->ss.dependencies_used - (int)pkgB->ss.dependencies_used;
		if (r)
			return r;
		r = pkgB->ss.conflicts - pkgA->ss.conflicts;
Timo Teräs's avatar
Timo Teräs committed
488
489
490
		if (r)
			return r;

491
492
493
494
495
496
		/* Prefer installed on self-upgrade */
		if (db->performing_self_update && !(solver_flags & APK_SOLVERF_UPGRADE)) {
			r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
			if (r)
				return r;
		}
497

498
499
		/* Prefer allowed pinning */
		r = (int)pkgA->ss.tag_ok - (int)pkgB->ss.tag_ok;
500
501
		if (r)
			return r;
502

503
504
505
506
507
508
		/* Prefer available */
		if (solver_flags & (APK_SOLVERF_AVAILABLE | APK_SOLVERF_REINSTALL)) {
			r = !!(pkgA->repos & db->available_repos) - !!(pkgB->repos & db->available_repos);
			if (r)
				return r;
		}
509

510
511
		/* Prefer preferred pinning */
		r = (int)pkgA->ss.tag_preferred - (int)pkgB->ss.tag_preferred;
512
513
		if (r)
			return r;
514
515
516
517
518
519
520

		/* Prefer installed */
		if (!(solver_flags & APK_SOLVERF_UPGRADE)) {
			r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
			if (r)
				return r;
		}
521
	}
522

523
524
525
526
527
528
529
	/* 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;
	}
530

531
532
533
534
535
536
537
538
539
	/* 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
540

541
542
543
544
	/* Prefer installed (matches here if upgrading) */
	r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
	if (r)
		return r;
545

546
547
	/* Prefer lowest available repository */
	return ffsl(pkgB->repos) - ffsl(pkgA->repos);
548
}
549

550
551
552
553
554
555
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)
556
{
557
	struct apk_provider *p0;
558
559
560
561
562
563

	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;
564
565
566
		/* Conflict: providing same name */
		mark_error(ss, p.pkg);
		mark_error(ss, name->ss.chosen.pkg);
567
		return;
568
	}
569

570
571
	if (p.pkg)
		dbg_printf("assign %s to "PKG_VER_FMT"\n", name->name, PKG_VER_PRINTF(p.pkg));
572

573
574
575
576
577
578
579
	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);

580
581
582
583
	/* propagate pinning to install_if candidates */
	if (p.pkg)
		foreach_rinstall_if_pkg(ss, p.pkg, inherit_pinning_from_pkg);

584
	/* disqualify all conflicting packages */
585
586
	foreach_array_item(p0, name->providers) {
		if (p0->pkg == p.pkg)
587
588
			continue;
		if (p.version == &apk_null_blob &&
589
		    p0->version == &apk_null_blob)
590
			continue;
591
		disqualify_package(ss, p0->pkg, "conflicting provides");
592
	}
593
	reevaluate_reverse_deps(ss, name);
594
595
}

596
static void select_package(struct apk_solver_state *ss, struct apk_name *name)
597
{
598
	struct apk_provider chosen = { NULL, &apk_null_blob }, *p;
599
	struct apk_package *pkg = NULL;
600
	struct apk_dependency *d;
601

602
	dbg_printf("select_package: %s\n", name->name);
603

604
	if (name->ss.requirers || name->ss.has_iif) {
605
		foreach_array_item(p, name->providers) {
606
			/* Ensure valid pinning and install-if trigger */
607
			if (name->ss.requirers == 0 &&
608
609
			    (!p->pkg->ss.iif_triggered ||
			     !p->pkg->ss.tag_ok))
610
				continue;
611
612
613
			/* Virtual packages cannot be autoselected */
			if (p->version == &apk_null_blob && p->pkg->name->ss.requirers == 0)
				continue;
614
615
			if (compare_providers(ss, p, &chosen) > 0)
				chosen = *p;
616
		}
617
	}
618

619
620
	pkg = chosen.pkg;
	if (pkg) {
621
622
623
624
		if (!pkg->ss.available || !pkg->ss.tag_ok) {
			/* Selecting broken or unallowed package */
			mark_error(ss, pkg);
		}
625
		dbg_printf("selecting: " PKG_VER_FMT ", available: %d\n", PKG_VER_PRINTF(pkg), pkg->ss.available);
626

627
		assign_name(ss, pkg->name, APK_PROVIDER_FROM_PACKAGE(pkg));
628
629
630
		foreach_array_item(d, pkg->provides)
			assign_name(ss, d->name, APK_PROVIDER_FROM_PROVIDES(pkg, d));

631
		ss->solver_flags_inherit = pkg->ss.solver_flags_inheritable;
632
		ss->pinning_inherit = pkg->ss.pinning_allowed;
633
634
		foreach_array_item(d, pkg->depends)
			apply_constraint(ss, pkg, d);
635
		ss->solver_flags_inherit = 0;
636
		ss->pinning_inherit = 0;
637

638
639
640
641
		ss->num_selections++;
	} else {
		dbg_printf("selecting: %s [unassigned]\n", name->name);
		assign_name(ss, name, provider_none);
642
		ss->errors += (name->ss.requirers > 0);
643
	}
644
645
}

646
static void generate_change_dep(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep);
647
648
649
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)
650
{
651
	struct apk_name **pname;
652
653
654
	struct apk_package *pkg = name->ss.chosen.pkg, *opkg;
	struct apk_changeset *changeset = ss->changeset;
	struct apk_change *change;
655
	struct apk_dependency *d;
656
657
658

	if (pkg == NULL)
		return;
659

660
	if (pkg->ss.in_changeset)
661
		return;
662
663
664
	pkg->ss.in_changeset = 1;
	pkg->name->ss.in_changeset = 1;

665
666
	foreach_array_item(d, pkg->depends)
		generate_change_dep(ss, pkg, d);
667
668
669
670
671
672
673
674

	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,
675
		.new_repository_tag = get_tag(ss->db, pkg->ss.pinning_allowed, get_pkg_repos(ss->db, pkg)),
676
		.reinstall = !!(pkg->ss.solver_flags & APK_SOLVERF_REINSTALL),
677
678
679
680
681
682
683
684
	};
	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++;
685

686
687
	foreach_array_item(pname, pkg->name->rinstall_if)
		generate_change_iif(ss, *pname);
688
689
}

690
static void generate_change_iif(struct apk_solver_state *ss, struct apk_name *name)
691
{
692
	struct apk_package *pkg = name->ss.chosen.pkg;
693
	struct apk_dependency *dep0;
694

695
	if (pkg == NULL || !name->ss.seen)
696
697
		return;

698
	foreach_array_item(dep0, pkg->install_if) {
699
700
701
702
703
		struct apk_name *name0 = dep0->name;
		if (!name0->ss.in_changeset)
			return;
		if (!apk_dep_is_provided(dep0, &name0->ss.chosen))
			return;
704
705
	}

706
	generate_change(ss, name);
707
708
}

709
static void generate_change_dep(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep)
710
{
711
	struct apk_name *name = dep->name;
712
	struct apk_package *pkg = name->ss.chosen.pkg;
713

714
	if (!apk_dep_is_provided(dep, &name->ss.chosen))
715
		mark_error(ss, ppkg);
716

717
	generate_change(ss, name);
718
719
720

	if (pkg && pkg->ss.error)
		mark_error(ss, ppkg);
721
}
722

723
724
725
726
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;
727
	struct apk_dependency *d;
728

729
730
731
732
733
	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
734

735
	apk_change_array_resize(&ss->changeset->changes, ss->num_selections);
736
737
	foreach_array_item(d, world)
		generate_change_dep(ss, NULL, d);
738

739
740
741
742
743
744
745
746
747
748
	/* 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++;
749
750
751
		}
	}

752
	changeset->num_total_changes = changeset->num_install + changeset->num_remove + changeset->num_adjust;
753

754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
#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
773

774
775
776
777
778
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;
779
780
}

781
782
783
784
int apk_solver_solve(struct apk_database *db,
		     unsigned short solver_flags,
		     struct apk_dependency_array *world,
		     struct apk_changeset *changeset)
785
{
786
	struct apk_name *name, *name0;
787
	struct apk_package *pkg;
788
	struct apk_solver_state ss_data, *ss = &ss_data;
789
	struct apk_dependency *d;
790

791
restart:
792
793
794
	memset(ss, 0, sizeof(*ss));
	ss->db = db;
	ss->changeset = changeset;
795
	ss->default_repos = apk_db_get_pinning_mask_repos(db, APK_DEFAULT_PINNING_MASK);
796
797
	list_init(&ss->dirty_head);
	list_init(&ss->unresolved_head);
798

799
	dbg_printf("applying world\n");
800
	ss->prefer_pinning = 1;
801
	ss->solver_flags_inherit = solver_flags;
802
803
	foreach_array_item(d, world) {
		if (d->broken)
804
			continue;
805
		name = d->name;
806
		name->ss.in_world_dependency = 1;
807
808
809
		discover_name(ss, d->name);
		ss->pinning_inherit = BIT(d->repository_tag);
		apply_constraint(ss, NULL, d);
810
	}
811
	ss->solver_flags_inherit = 0;
812
813
	ss->pinning_inherit = 0;
	ss->prefer_pinning = 0;
814
	dbg_printf("applying world [finished]\n");
815

816
	do {
817
818
819
		while (!list_empty(&ss->dirty_head)) {
			name = list_pop(&ss->dirty_head, struct apk_name, ss.dirty_list);
			reconsider_name(ss, name);
820
		}
Timo Teräs's avatar
Timo Teräs committed
821

822
823
		name = NULL;
		list_for_each_entry(name0, &ss->unresolved_head, ss.unresolved_list) {
824
			if (name0->ss.reverse_deps_done && name0->ss.requirers && !name0->ss.has_options) {
825
				name = name0;
Timo Teräs's avatar
Timo Teräs committed
826
				break;
827
828
829
			}
			if (name == NULL)
				goto prefer;
830
			if ((!!name0->ss.requirers) - (!!name->ss.requirers) < 0)
Timo Teräs's avatar
Timo Teräs committed
831
				continue;
832
			if (name0->ss.max_dep_chain - name->ss.max_dep_chain < 0)
833
				continue;
834
835
		prefer:
			name = name0;
836
		}
837
838
		if (name == NULL)
			break;
839

840
841
		select_package(ss, name);
	} while (1);
842

843
	generate_changeset(ss, world);
844

845
	if (ss->errors && (apk_flags & APK_FORCE)) {
846
847
848
		foreach_array_item(d, world) {
			name = d->name;
			pkg = name->ss.chosen.pkg;
849
			if (pkg == NULL || pkg->ss.error) {
850
				d->broken = 1;
851
852
853
854
855
856
857
858
				dbg_printf("disabling broken world dep: %s", name->name);
			}
		}
		apk_hash_foreach(&db->available.names, free_state, NULL);
		apk_hash_foreach(&db->available.packages, free_package, NULL);
		goto restart;
	}

859
860
861
	apk_hash_foreach(&db->available.names, free_state, NULL);
	apk_hash_foreach(&db->available.packages, free_package, NULL);
	dbg_printf("solver done, errors=%d\n", ss->errors);
Timo Teräs's avatar
Timo Teräs committed
862

863
	return ss->errors;
864
}