solver.c 26.4 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
	struct apk_changeset *changeset;
	struct list_head dirty_head;
	struct list_head unresolved_head;
	unsigned int errors;
38
	unsigned int solver_flags_inherit;
39
40
41
	unsigned int pinning_inherit;
	unsigned int default_repos;
	unsigned prefer_pinning : 1;
42
};
43

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

49
50
51
void apk_solver_set_name_flags(struct apk_name *name,
			       unsigned short solver_flags,
			       unsigned short solver_flags_inheritable)
52
{
53
	struct apk_provider *p;
54

55
56
	foreach_array_item(p, name->providers) {
		struct apk_package *pkg = p->pkg;
57
58
59
		pkg->ss.solver_flags |= solver_flags;
		pkg->ss.solver_flags_inheritable |= solver_flags_inheritable;
	}
60
61
}

62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
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))
{
84
85
86
	struct apk_name *name = pkg->name, *name0, **pname0;
	struct apk_dependency *dep;
	struct apk_provider *p0;
87

88
89
	foreach_array_item(pname0, pkg->name->rinstall_if) {
		name0 = *pname0;
90
		dbg_printf(PKG_VER_FMT ": rinstall_if %s\n", PKG_VER_PRINTF(pkg), name0->name);
91
92
93
94
95
		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);
96
					break;
97
				}
98
99
100
101
102
			}
		}
	}
}

103
104
105
106
107
108
109
110
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++;
}

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

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

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

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

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

136
static void reevaluate_reverse_deps(struct apk_solver_state *ss, struct apk_name *name)
137
{
138
139
140
141
142
143
144
145
146
	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);
	}
147
}
148

149
static void reevaluate_reverse_installif(struct apk_solver_state *ss, struct apk_name *name)
150
{
151
152
153
154
155
156
157
158
159
	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);
	}
160
161
}

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

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

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

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

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

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

189
	return FALSE;
190
191
}

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

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

203
	name->ss.seen = 1;
204
205
	foreach_array_item(p, name->providers) {
		struct apk_package *pkg = p->pkg;
206
		if (pkg->ss.seen)
207
			continue;
208

209
		pkg->ss.seen = 1;
210
211
		pkg->ss.pinning_allowed = APK_DEFAULT_PINNING_MASK;
		pkg->ss.pinning_preferred = APK_DEFAULT_PINNING_MASK;
212
213
214
215
216
		pkg->ss.pkg_available =
			(pkg->filename != NULL) ||
			(pkg->installed_size == 0) ||
			(pkg->repos & db->available_repos);
		pkg->ss.pkg_selectable = pkg->ss.pkg_available || pkg->ipkg;
217
218

		repos = get_pkg_repos(db, pkg);
219
220
221
222
223
		pkg->ss.tag_preferred =
			(pkg->filename != NULL) ||
			(pkg->installed_size == 0) ||
			!!(repos & ss->default_repos);
		pkg->ss.tag_ok = pkg->ss.tag_preferred || pkg->ipkg;
224

225
226
		foreach_array_item(dep, pkg->depends) {
			discover_name(ss, dep->name);
227
			pkg->ss.max_dep_chain = max(pkg->ss.max_dep_chain,
228
229
						    dep->name->ss.max_dep_chain+1);
		}
230
		name->ss.max_dep_chain = max(name->ss.max_dep_chain, pkg->ss.max_dep_chain);
231

232
		dbg_printf("discover " PKG_VER_FMT ": tag_ok=%d, tag_pref=%d max_dep_chain=%d selectable=%d\n",
233
234
235
			PKG_VER_PRINTF(pkg),
			pkg->ss.tag_ok,
			pkg->ss.tag_preferred,
236
			pkg->ss.max_dep_chain,
237
			pkg->ss.pkg_selectable);
238
	}
239
240
	foreach_array_item(pname0, name->rinstall_if)
		discover_name(ss, *pname0);
241
242
}

243
static void name_requirers_changed(struct apk_solver_state *ss, struct apk_name *name)
244
{
245
	queue_unresolved(ss, name);
246
	reevaluate_reverse_installif(ss, name);
247
	queue_dirty(ss, name);
248
249
}

250
251
252
253
254
255
256
257
258
259
260
261
262
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));
	}
}

263
static void apply_constraint(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep)
264
{
265
	struct apk_name *name = dep->name;
266
	struct apk_provider *p0;
267
	unsigned int solver_flags_inherit = ss->solver_flags_inherit;
268
	int is_provided;
269

270
271
272
273
274
275
276
	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;
277
278
	if (name->ss.requirers == 1 && !dep->conflict)
		name_requirers_changed(ss, name);
279

280
	foreach_array_item(p0, name->providers) {
281
		struct apk_package *pkg0 = p0->pkg;
282

283
284
285
		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);
286

287
		pkg0->ss.conflicts += !is_provided;
288
		if (unlikely(pkg0->ss.pkg_selectable && pkg0->ss.conflicts))
289
			disqualify_package(ss, pkg0, "conflicting dependency");
290

291
292
293
		if (is_provided) {
			pkg0->ss.solver_flags |= solver_flags_inherit;
			pkg0->ss.solver_flags_inheritable |= solver_flags_inherit;
294
295
296
297
298
299
			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);
300
		}
301
	}
302
303
}

304
305
306
307
308
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;

309
310
311
	if (name == must_provide)
		return;

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
337
338
339
340
	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;
}

341
static void reconsider_name(struct apk_solver_state *ss, struct apk_name *name)
342
{
343
	struct apk_name *name0, **pname0;
344
	struct apk_dependency *dep;
345
	struct apk_package *first_candidate = NULL, *pkg;
346
347
	struct apk_provider *p;
	int reevaluate_deps, reevaluate_iif;
348
	int num_options = 0, num_tag_not_ok = 0, has_iif = 0;
349

350
	dbg_printf("reconsider_name: %s\n", name->name);
351

352
353
	reevaluate_deps = name->ss.reevaluate_deps;
	reevaluate_iif = name->ss.reevaluate_iif;
354
	name->ss.reevaluate_deps = 0;
355
	name->ss.reevaluate_iif = 0;
356

357
358
	/* propagate down by merging common dependencies and
	 * applying new constraints */
359
	foreach_array_item(p, name->providers) {
360
		/* check if this pkg's dependencies have become unsatisfiable */
361
		pkg = p->pkg;
Timo Teräs's avatar
Timo Teräs committed
362
		pkg->ss.dependencies_merged = 0;
363
		if (reevaluate_deps) {
364
			if (!pkg->ss.pkg_selectable)
365
				continue;
366
			foreach_array_item(dep, pkg->depends) {
367
368
369
370
371
372
				if (!dependency_satisfiable(ss, dep)) {
					disqualify_package(ss, pkg, "dependency no longer satisfiable");
					break;
				}
			}
		}
373
		if (!pkg->ss.pkg_selectable)
374
			continue;
375

376
		if (reevaluate_iif) {
377
378
379
380
			pkg->ss.iif_triggered = 1;
			foreach_array_item(dep, pkg->install_if) {
				if (!dependency_satisfiable(ss, dep)) {
					pkg->ss.iif_triggered = 0;
381
					break;
382
				}
383
384
385
			}
			has_iif |= pkg->ss.iif_triggered;
		}
Timo Teräs's avatar
Timo Teräs committed
386

387
388
		if (name->ss.requirers == 0 && !pkg->ss.iif_triggered)
			continue;
389

390
		/* merge common dependencies */
Timo Teräs's avatar
Timo Teräs committed
391
		pkg->ss.dependencies_merged = 1;
392
393
		if (first_candidate == NULL)
			first_candidate = pkg;
394
395
396
397
398
399
400
401
402
403

		/* 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);
404
405
406

		num_tag_not_ok += !pkg->ss.tag_ok;
		num_options++;
407
	}
408
	name->ss.has_options = (num_options > 1 || num_tag_not_ok > 0);
409
410
411
	name->ss.has_iif = has_iif;
	queue_unresolved(ss, name);

412
	if (first_candidate != NULL) {
413
		pkg = first_candidate;
414
415
416
		foreach_array_item(p, name->providers)
			p->pkg->ss.dependencies_used = p->pkg->ss.dependencies_merged;

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

		/* 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
444
	}
445

446
447
448
449
450
451
452
453
454
455
456
	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);
457
458
}

459
460
static int compare_providers(struct apk_solver_state *ss,
			     struct apk_provider *pA, struct apk_provider *pB)
461
{
462
463
	struct apk_database *db = ss->db;
	struct apk_package *pkgA = pA->pkg, *pkgB = pB->pkg;
464
	unsigned int solver_flags;
465
	int r;
466

467
468
469
	/* Prefer existing package */
	if (pkgA == NULL || pkgB == NULL)
		return (pkgA != NULL) - (pkgB != NULL);
470

471
472
473
474
475
476
477
478
479
	/* 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;
480

481
482
		/* Prefer available */
		if (solver_flags & (APK_SOLVERF_AVAILABLE | APK_SOLVERF_REINSTALL)) {
483
			r = (int)pkgA->ss.pkg_available - (int)pkgB->ss.pkg_available;
484
485
486
487
488
			if (r)
				return r;
		}
	} else {
		/* Prefer without errors */
489
		r = (int)pkgA->ss.pkg_selectable - (int)pkgB->ss.pkg_selectable;
490
491
		if (r)
			return r;
Timo Teräs's avatar
Timo Teräs committed
492

493
494
495
496
497
		/* 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
498
499
500
		if (r)
			return r;

501
502
503
504
505
506
		/* 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;
		}
507

508
509
		/* Prefer allowed pinning */
		r = (int)pkgA->ss.tag_ok - (int)pkgB->ss.tag_ok;
510
511
		if (r)
			return r;
512

513
514
		/* Prefer available */
		if (solver_flags & (APK_SOLVERF_AVAILABLE | APK_SOLVERF_REINSTALL)) {
515
			r = (int)pkgA->ss.pkg_available - (int)pkgB->ss.pkg_available;
516
517
518
			if (r)
				return r;
		}
519

520
521
		/* Prefer preferred pinning */
		r = (int)pkgA->ss.tag_preferred - (int)pkgB->ss.tag_preferred;
522
523
		if (r)
			return r;
524
525
526
527
528
529
530

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

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

541
542
543
544
545
546
547
548
549
	/* 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
550

551
552
553
554
	/* Prefer installed (matches here if upgrading) */
	r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
	if (r)
		return r;
555

556
557
	/* Prefer lowest available repository */
	return ffsl(pkgB->repos) - ffsl(pkgA->repos);
558
}
559

560
561
562
563
564
565
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)
566
{
567
	struct apk_provider *p0;
568
569
570
571
572
573

	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;
574
575
576
		/* Conflict: providing same name */
		mark_error(ss, p.pkg);
		mark_error(ss, name->ss.chosen.pkg);
577
		return;
578
	}
579

580
581
	if (p.pkg)
		dbg_printf("assign %s to "PKG_VER_FMT"\n", name->name, PKG_VER_PRINTF(p.pkg));
582

583
584
585
586
587
588
589
	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);

590
591
592
593
	/* propagate pinning to install_if candidates */
	if (p.pkg)
		foreach_rinstall_if_pkg(ss, p.pkg, inherit_pinning_from_pkg);

594
	/* disqualify all conflicting packages */
595
596
	foreach_array_item(p0, name->providers) {
		if (p0->pkg == p.pkg)
597
598
			continue;
		if (p.version == &apk_null_blob &&
599
		    p0->version == &apk_null_blob)
600
			continue;
601
		disqualify_package(ss, p0->pkg, "conflicting provides");
602
	}
603
	reevaluate_reverse_deps(ss, name);
604
605
}

606
static void select_package(struct apk_solver_state *ss, struct apk_name *name)
607
{
608
	struct apk_provider chosen = { NULL, &apk_null_blob }, *p;
609
	struct apk_package *pkg = NULL;
610
	struct apk_dependency *d;
611

612
	dbg_printf("select_package: %s\n", name->name);
613

614
	if (name->ss.requirers || name->ss.has_iif) {
615
		foreach_array_item(p, name->providers) {
616
			/* Ensure valid pinning and install-if trigger */
617
			if (name->ss.requirers == 0 &&
618
619
			    (!p->pkg->ss.iif_triggered ||
			     !p->pkg->ss.tag_ok))
620
				continue;
621
622
623
			/* Virtual packages cannot be autoselected */
			if (p->version == &apk_null_blob && p->pkg->name->ss.requirers == 0)
				continue;
624
625
			if (compare_providers(ss, p, &chosen) > 0)
				chosen = *p;
626
		}
627
	}
628

629
630
	pkg = chosen.pkg;
	if (pkg) {
631
		if (!pkg->ss.pkg_selectable || !pkg->ss.tag_ok) {
632
633
634
			/* Selecting broken or unallowed package */
			mark_error(ss, pkg);
		}
635
		dbg_printf("selecting: " PKG_VER_FMT ", available: %d\n", PKG_VER_PRINTF(pkg), pkg->ss.pkg_selectable);
636

637
		assign_name(ss, pkg->name, APK_PROVIDER_FROM_PACKAGE(pkg));
638
639
640
		foreach_array_item(d, pkg->provides)
			assign_name(ss, d->name, APK_PROVIDER_FROM_PROVIDES(pkg, d));

641
		ss->solver_flags_inherit = pkg->ss.solver_flags_inheritable;
642
		ss->pinning_inherit = pkg->ss.pinning_allowed;
643
644
		foreach_array_item(d, pkg->depends)
			apply_constraint(ss, pkg, d);
645
		ss->solver_flags_inherit = 0;
646
		ss->pinning_inherit = 0;
647
648
649
	} else {
		dbg_printf("selecting: %s [unassigned]\n", name->name);
		assign_name(ss, name, provider_none);
650
		ss->errors += (name->ss.requirers > 0);
651
	}
652
653
}

654
static void record_change(struct apk_solver_state *ss, struct apk_package *opkg, struct apk_package *npkg)
655
{
656
657
658
	struct apk_changeset *changeset = ss->changeset;
	struct apk_change *change;

659
	change = apk_change_array_add(&changeset->changes);
660
661
662
	*change = (struct apk_change) {
		.old_pkg = opkg,
		.old_repository_tag = opkg ? opkg->ipkg->repository_tag : 0,
663
664
665
		.new_pkg = npkg,
		.new_repository_tag = npkg ? get_tag(ss->db, npkg->ss.pinning_allowed, get_pkg_repos(ss->db, npkg)) : 0,
		.reinstall = npkg ? !!(npkg->ss.solver_flags & APK_SOLVERF_REINSTALL) : 0,
666
	};
667
	if (npkg == NULL)
668
		changeset->num_remove++;
669
	else if (opkg == NULL)
670
		changeset->num_install++;
671
	else if (npkg != opkg || change->reinstall || change->new_repository_tag != change->old_repository_tag)
672
		changeset->num_adjust++;
673
}
674

675
676
677
678
static void cset_gen_name_change(struct apk_solver_state *ss, struct apk_name *name);
static void cset_gen_name_remove(struct apk_solver_state *ss, struct apk_package *pkg);
static void cset_gen_dep(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep);

679
static void cset_track_deps_added(struct apk_package *pkg)
680
681
682
{
	struct apk_dependency *d;

683
684
685
686
687
	foreach_array_item(d, pkg->depends) {
		if (d->conflict || !d->name->ss.installed_name)
			continue;
		d->name->ss.installed_name->ss.requirers++;
	}
688
689
690
691
692
693
694
695
}

static void cset_track_deps_removed(struct apk_solver_state *ss, struct apk_package *pkg)
{
	struct apk_dependency *d;
	struct apk_package *pkg0;

	foreach_array_item(d, pkg->depends) {
696
		if (d->conflict || !d->name->ss.installed_name)
697
			continue;
698
		if (--d->name->ss.installed_name->ss.requirers > 0)
699
			continue;
700
		pkg0 = d->name->ss.installed_pkg;
701
702
703
704
705
706
707
708
709
		if (pkg0 != NULL)
			cset_gen_name_remove(ss, pkg0);
	}
}

static void cset_check_removal_by_deps(struct apk_solver_state *ss, struct apk_package *pkg)
{
	if (pkg->name->ss.requirers == 0)
		cset_gen_name_remove(ss, pkg);
710
711
}

712
static void cset_check_install_by_iif(struct apk_solver_state *ss, struct apk_name *name)
713
{
714
	struct apk_package *pkg = name->ss.chosen.pkg;
715
	struct apk_dependency *dep0;
716

717
	if (pkg == NULL || !name->ss.seen || name->ss.in_changeset)
718
719
		return;

720
	foreach_array_item(dep0, pkg->install_if) {
721
722
723
724
725
		struct apk_name *name0 = dep0->name;
		if (!name0->ss.in_changeset)
			return;
		if (!apk_dep_is_provided(dep0, &name0->ss.chosen))
			return;
726
	}
727
728
729
730
731
	cset_gen_name_change(ss, name);
}

static void cset_check_removal_by_iif(struct apk_solver_state *ss, struct apk_name *name)
{
732
	struct apk_package *pkg = name->ss.installed_pkg;
733
	struct apk_dependency *dep0;
734

735
	if (pkg == NULL || name->ss.in_changeset || name->ss.chosen.pkg != NULL)
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
		return;

	foreach_array_item(dep0, pkg->install_if) {
		if (dep0->name->ss.in_changeset &&
		    dep0->name->ss.chosen.pkg == NULL) {
			cset_check_removal_by_deps(ss, pkg);
			return;
		}
	}
}

static void cset_gen_name_change(struct apk_solver_state *ss, struct apk_name *name)
{
	struct apk_name **pname;
	struct apk_package *pkg = name->ss.chosen.pkg, *opkg;
	struct apk_dependency *d;

	if (pkg == NULL || pkg->ss.in_changeset)
		return;

	pkg->ss.in_changeset = 1;
	pkg->name->ss.in_changeset = 1;

759
	opkg = pkg->name->ss.installed_pkg;
760
761
762
763
764
765
766
767
	if (opkg) {
		foreach_array_item(pname, opkg->name->rinstall_if)
			cset_check_removal_by_iif(ss, *pname);
	}

	foreach_array_item(d, pkg->depends)
		cset_gen_dep(ss, pkg, d);

768
	dbg_printf("Selecting: "PKG_VER_FMT"%s\n", PKG_VER_PRINTF(pkg), pkg->ss.pkg_selectable ? "" : " [NOT SELECTABLE]");
769
770
771
772
773
	record_change(ss, opkg, pkg);

	foreach_array_item(pname, pkg->name->rinstall_if)
		cset_check_install_by_iif(ss, *pname);

774
	cset_track_deps_added(pkg);
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
	if (opkg)
		cset_track_deps_removed(ss, opkg);
}

static void cset_gen_name_remove(struct apk_solver_state *ss, struct apk_package *pkg)
{
	struct apk_name *name = pkg->name, **pname;

	if (name->ss.chosen.pkg != NULL || name->ss.in_changeset)
		return;

	name->ss.in_changeset = 1;
	foreach_array_item(pname, pkg->name->rinstall_if)
		cset_check_removal_by_iif(ss, *pname);
	record_change(ss, pkg, NULL);
	cset_track_deps_removed(ss, pkg);
791
792
}

793
static void cset_gen_dep(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep)
794
{
795
	struct apk_name *name = dep->name;
796
	struct apk_package *pkg = name->ss.chosen.pkg;
797

798
	if (!apk_dep_is_provided(dep, &name->ss.chosen))
799
		mark_error(ss, ppkg);
800

801
	cset_gen_name_change(ss, name);
802
803
804

	if (pkg && pkg->ss.error)
		mark_error(ss, ppkg);
805
}
806

807
808
809
810
811
812
813
814
815
static int cset_reset_name(apk_hash_item item, void *ctx)
{
	struct apk_name *name = (struct apk_name *) item;
	name->ss.installed_pkg = NULL;
	name->ss.installed_name = NULL;
	name->ss.requirers = 0;
	return 0;
}

816
817
818
static void generate_changeset(struct apk_solver_state *ss, struct apk_dependency_array *world)
{
	struct apk_changeset *changeset = ss->changeset;
819
	struct apk_package *pkg;
820
	struct apk_installed_package *ipkg;
821
	struct apk_dependency *d;
822

823
824
	apk_change_array_init(&changeset->changes);

825
826
827
828
829
830
831
832
833
	apk_hash_foreach(&ss->db->available.names, cset_reset_name, NULL);
	list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list) {
		pkg = ipkg->pkg;
		pkg->name->ss.installed_pkg = pkg;
		pkg->name->ss.installed_name = pkg->name;
		foreach_array_item(d, pkg->provides)
			if (d->version != &apk_null_blob)
				d->name->ss.installed_name = pkg->name;
	}
834
	list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list)
835
		cset_track_deps_added(ipkg->pkg);
836
837
	list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list)
		cset_check_removal_by_deps(ss, ipkg->pkg);
Timo Teräs's avatar
Timo Teräs committed
838

839
	foreach_array_item(d, world)
840
		cset_gen_dep(ss, NULL, d);
841

842
843
	list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list)
		cset_gen_name_remove(ss, ipkg->pkg);
844

845
846
847
848
	changeset->num_total_changes =
		changeset->num_install +
		changeset->num_remove +
		changeset->num_adjust;
849
850
}

851
static int free_name(apk_hash_item item, void *ctx)
852
853
854
855
856
{
	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
857

858
859
860
861
862
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;
863
864
}

865
866
867
868
int apk_solver_solve(struct apk_database *db,
		     unsigned short solver_flags,
		     struct apk_dependency_array *world,
		     struct apk_changeset *changeset)
869
{
870
	struct apk_name *name, *name0;
871
	struct apk_package *pkg;
872
	struct apk_solver_state ss_data, *ss = &ss_data;
873
	struct apk_dependency *d;
874

875
restart:
876
877
878
	memset(ss, 0, sizeof(*ss));
	ss->db = db;
	ss->changeset = changeset;
879
	ss->default_repos = apk_db_get_pinning_mask_repos(db, APK_DEFAULT_PINNING_MASK);
880
881
	list_init(&ss->dirty_head);
	list_init(&ss->unresolved_head);
882

883
	dbg_printf("applying world\n");
884
	ss->prefer_pinning = 1;
885
	ss->solver_flags_inherit = solver_flags;
886
887
	foreach_array_item(d, world) {
		if (d->broken)
888
			continue;
889
890
891
892
		name = d->name;
		discover_name(ss, d->name);
		ss->pinning_inherit = BIT(d->repository_tag);
		apply_constraint(ss, NULL, d);
893
	}
894
	ss->solver_flags_inherit = 0;
895
896
	ss->pinning_inherit = 0;
	ss->prefer_pinning = 0;
897
	dbg_printf("applying world [finished]\n");
898

899
	do {
900
901
902
		while (!list_empty(&ss->dirty_head)) {
			name = list_pop(&ss->dirty_head, struct apk_name, ss.dirty_list);
			reconsider_name(ss, name);
903
		}
Timo Teräs's avatar
Timo Teräs committed
904

905
906
		name = NULL;
		list_for_each_entry(name0, &ss->unresolved_head, ss.unresolved_list) {
907
			if (name0->ss.reverse_deps_done && name0->ss.requirers && !name0->ss.has_options) {
908
				name = name0;
Timo Teräs's avatar
Timo Teräs committed
909
				break;
910
911
912
			}
			if (name == NULL)
				goto prefer;
913
			if ((!!name0->ss.requirers) - (!!name->ss.requirers) < 0)
Timo Teräs's avatar
Timo Teräs committed
914
				continue;
915
			if (name0->ss.max_dep_chain - name->ss.max_dep_chain < 0)
916
				continue;
917
918
		prefer:
			name = name0;
919
		}