solver.c 26.2 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
167
	dbg_printf("disqualify_package: " PKG_VER_FMT " (%s)\n", PKG_VER_PRINTF(pkg), reason);
	pkg->ss.available = 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
186
	foreach_array_item(p, name->providers)
		if (p->pkg->ss.available && 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
		pkg->ss.seen = 1;
209
210
211
212
213
214
215
216
		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);

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

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

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

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

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

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

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

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

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

283
284
285
		if (is_provided) {
			pkg0->ss.solver_flags |= solver_flags_inherit;
			pkg0->ss.solver_flags_inheritable |= solver_flags_inherit;
286
287
288
289
290
291
			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);
292
		}
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
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;
}

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

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

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

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

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

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

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

		/* 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);
393
394
395

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

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

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

		/* 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
433
	}
434

435
436
437
438
439
440
441
442
443
444
445
	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);
446
447
}

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

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

460
461
462
463
464
465
466
467
468
	/* 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;
469

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

482
483
484
485
486
		/* 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
487
488
489
		if (r)
			return r;

490
491
492
493
494
495
		/* 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;
		}
496

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

630
		ss->solver_flags_inherit = pkg->ss.solver_flags_inheritable;
631
		ss->pinning_inherit = pkg->ss.pinning_allowed;
632
633
		foreach_array_item(d, pkg->depends)
			apply_constraint(ss, pkg, d);
634
		ss->solver_flags_inherit = 0;
635
		ss->pinning_inherit = 0;
636
637
638
	} else {
		dbg_printf("selecting: %s [unassigned]\n", name->name);
		assign_name(ss, name, provider_none);
639
		ss->errors += (name->ss.requirers > 0);
640
	}
641
642
}

643
static void record_change(struct apk_solver_state *ss, struct apk_package *opkg, struct apk_package *npkg)
644
{
645
646
647
	struct apk_changeset *changeset = ss->changeset;
	struct apk_change *change;

648
	change = apk_change_array_add(&changeset->changes);
649
650
651
	*change = (struct apk_change) {
		.old_pkg = opkg,
		.old_repository_tag = opkg ? opkg->ipkg->repository_tag : 0,
652
653
654
		.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,
655
	};
656
	if (npkg == NULL)
657
		changeset->num_remove++;
658
	else if (opkg == NULL)
659
		changeset->num_install++;
660
	else if (npkg != opkg || change->reinstall || change->new_repository_tag != change->old_repository_tag)
661
		changeset->num_adjust++;
662
}
663

664
665
666
667
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);

668
static void cset_track_deps_added(struct apk_package *pkg)
669
670
671
{
	struct apk_dependency *d;

672
673
674
675
676
	foreach_array_item(d, pkg->depends) {
		if (d->conflict || !d->name->ss.installed_name)
			continue;
		d->name->ss.installed_name->ss.requirers++;
	}
677
678
679
680
681
682
683
684
}

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) {
685
		if (d->conflict || !d->name->ss.installed_name)
686
			continue;
687
		if (--d->name->ss.installed_name->ss.requirers > 0)
688
			continue;
689
		pkg0 = d->name->ss.installed_pkg;
690
691
692
693
694
695
696
697
698
		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);
699
700
}

701
static void cset_check_install_by_iif(struct apk_solver_state *ss, struct apk_name *name)
702
{
703
	struct apk_package *pkg = name->ss.chosen.pkg;
704
	struct apk_dependency *dep0;
705

706
	if (pkg == NULL || !name->ss.seen || name->ss.in_changeset)
707
708
		return;

709
	foreach_array_item(dep0, pkg->install_if) {
710
711
712
713
714
		struct apk_name *name0 = dep0->name;
		if (!name0->ss.in_changeset)
			return;
		if (!apk_dep_is_provided(dep0, &name0->ss.chosen))
			return;
715
	}
716
717
718
719
720
	cset_gen_name_change(ss, name);
}

static void cset_check_removal_by_iif(struct apk_solver_state *ss, struct apk_name *name)
{
721
	struct apk_package *pkg = name->ss.installed_pkg;
722
	struct apk_dependency *dep0;
723

724
	if (pkg == NULL || name->ss.in_changeset || name->ss.chosen.pkg != NULL)
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
		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;

748
	opkg = pkg->name->ss.installed_pkg;
749
750
751
752
753
754
755
756
757
758
759
760
761
762
	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);

	dbg_printf("Selecting: "PKG_VER_FMT"%s\n", PKG_VER_PRINTF(pkg), pkg->ss.available ? "" : " [NOT AVAILABLE]");
	record_change(ss, opkg, pkg);

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

763
	cset_track_deps_added(pkg);
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
	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);
780
781
}

782
static void cset_gen_dep(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep)
783
{
784
	struct apk_name *name = dep->name;
785
	struct apk_package *pkg = name->ss.chosen.pkg;
786

787
	if (!apk_dep_is_provided(dep, &name->ss.chosen))
788
		mark_error(ss, ppkg);
789

790
	cset_gen_name_change(ss, name);
791
792
793

	if (pkg && pkg->ss.error)
		mark_error(ss, ppkg);
794
}
795

796
797
798
799
800
801
802
803
804
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;
}

805
806
807
static void generate_changeset(struct apk_solver_state *ss, struct apk_dependency_array *world)
{
	struct apk_changeset *changeset = ss->changeset;
808
	struct apk_package *pkg;
809
	struct apk_installed_package *ipkg;
810
	struct apk_dependency *d;
811

812
813
	apk_change_array_init(&changeset->changes);

814
815
816
817
818
819
820
821
822
	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;
	}
823
	list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list)
824
		cset_track_deps_added(ipkg->pkg);
825
826
	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
827

828
	foreach_array_item(d, world)
829
		cset_gen_dep(ss, NULL, d);
830

831
832
	list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list)
		cset_gen_name_remove(ss, ipkg->pkg);
833

834
835
836
837
	changeset->num_total_changes =
		changeset->num_install +
		changeset->num_remove +
		changeset->num_adjust;
838
839
}

840
static int free_name(apk_hash_item item, void *ctx)
841
842
843
844
845
{
	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
846

847
848
849
850
851
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;
852
853
}

854
855
856
857
int apk_solver_solve(struct apk_database *db,
		     unsigned short solver_flags,
		     struct apk_dependency_array *world,
		     struct apk_changeset *changeset)
858
{
859
	struct apk_name *name, *name0;
860
	struct apk_package *pkg;
861
	struct apk_solver_state ss_data, *ss = &ss_data;
862
	struct apk_dependency *d;
863

864
restart:
865
866
867
	memset(ss, 0, sizeof(*ss));
	ss->db = db;
	ss->changeset = changeset;
868
	ss->default_repos = apk_db_get_pinning_mask_repos(db, APK_DEFAULT_PINNING_MASK);
869
870
	list_init(&ss->dirty_head);
	list_init(&ss->unresolved_head);
871

872
	dbg_printf("applying world\n");
873
	ss->prefer_pinning = 1;
874
	ss->solver_flags_inherit = solver_flags;
875
876
	foreach_array_item(d, world) {
		if (d->broken)
877
			continue;
878
879
880
881
		name = d->name;
		discover_name(ss, d->name);
		ss->pinning_inherit = BIT(d->repository_tag);
		apply_constraint(ss, NULL, d);
882
	}
883
	ss->solver_flags_inherit = 0;
884
885
	ss->pinning_inherit = 0;
	ss->prefer_pinning = 0;
886
	dbg_printf("applying world [finished]\n");
887

888
	do {
889
890
891
		while (!list_empty(&ss->dirty_head)) {
			name = list_pop(&ss->dirty_head, struct apk_name, ss.dirty_list);
			reconsider_name(ss, name);
892
		}
Timo Teräs's avatar
Timo Teräs committed
893

894
895
		name = NULL;
		list_for_each_entry(name0, &ss->unresolved_head, ss.unresolved_list) {
896
			if (name0->ss.reverse_deps_done && name0->ss.requirers && !name0->ss.has_options) {
897
				name = name0;
Timo Teräs's avatar
Timo Teräs committed
898
				break;
899
900
901
			}
			if (name == NULL)
				goto prefer;
902
			if ((!!name0->ss.requirers) - (!!name->ss.requirers) < 0)
Timo Teräs's avatar
Timo Teräs committed
903
				continue;
904
			if (name0->ss.max_dep_chain - name->ss.max_dep_chain < 0)
905
				continue;
906
907
		prefer:
			name = name0;
908
		}
909
910
		if (name == NULL)
			break;
911

912
913
		select_package(ss, name);
	} while (1);
914

915
	generate_changeset(ss, world);
916

917
	if (ss->errors && (apk_flags & APK_FORCE)) {
918
919
920
		foreach_array_item(d, world) {
			name = d->name;
			pkg = name->ss.chosen.pkg;
921
			if (pkg == NULL || pkg->ss.error) {
922
				d->broken = 1;
923
924
925
				dbg_printf("disabling broken world dep: %s", name->name);
			}
		}
926
		apk_hash_foreach(&db->available.names, free_name, NULL);
927
928
929
930
		apk_hash_foreach(&db->available.packages, free_package, NULL);
		goto restart;
	}

931
	apk_hash_foreach(&db->available.names, free_name, NULL);
932
933
	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
934

935
	return ss->errors;
936
}