solver.c 25.7 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
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
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);

static void cset_track_deps_added(struct apk_dependency_array *deps)
{
	struct apk_dependency *d;

	foreach_array_item(d, deps)
		if (!d->conflict)
			d->name->ss.requirers++;
}

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) {
		if (d->conflict)
			continue;
		d->name->ss.requirers--;
		if (d->name->ss.requirers > 0)
			continue;
		pkg0 = apk_pkg_get_installed(d->name);
		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);
698
699
}

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

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

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

static void cset_check_removal_by_iif(struct apk_solver_state *ss, struct apk_name *name)
{
	struct apk_package *pkg;
	struct apk_dependency *dep0;
722

723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
	if (name->ss.in_changeset || name->ss.chosen.pkg != NULL)
		return;

	pkg = apk_pkg_get_installed(name);
	if (pkg == NULL)
		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;

	opkg = apk_pkg_get_installed(pkg->name);
	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);

	cset_track_deps_added(pkg->depends);
	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);
783
784
}

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

790
	if (!apk_dep_is_provided(dep, &name->ss.chosen))
791
		mark_error(ss, ppkg);
792

793
	cset_gen_name_change(ss, name);
794
795
796

	if (pkg && pkg->ss.error)
		mark_error(ss, ppkg);
797
}
798

799
800
801
802
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;
803
	struct apk_dependency *d;
804

805
806
807
808
809
810
811
812
	apk_change_array_init(&changeset->changes);

	list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list)
		ipkg->pkg->name->ss.requirers = 0;
	list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list)
		cset_track_deps_added(ipkg->pkg->depends);
	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
813

814
	foreach_array_item(d, world)
815
		cset_gen_dep(ss, NULL, d);
816

817
818
	list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list)
		cset_gen_name_remove(ss, ipkg->pkg);
819

820
821
822
823
	changeset->num_total_changes =
		changeset->num_install +
		changeset->num_remove +
		changeset->num_adjust;
824
825
826
827
828
829
830
831
}

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
832

833
834
835
836
837
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;
838
839
}

840
841
842
843
int apk_solver_solve(struct apk_database *db,
		     unsigned short solver_flags,
		     struct apk_dependency_array *world,
		     struct apk_changeset *changeset)
844
{
845
	struct apk_name *name, *name0;
846
	struct apk_package *pkg;
847
	struct apk_solver_state ss_data, *ss = &ss_data;
848
	struct apk_dependency *d;
849

850
restart:
851
852
853
	memset(ss, 0, sizeof(*ss));
	ss->db = db;
	ss->changeset = changeset;
854
	ss->default_repos = apk_db_get_pinning_mask_repos(db, APK_DEFAULT_PINNING_MASK);
855
856
	list_init(&ss->dirty_head);
	list_init(&ss->unresolved_head);
857

858
	dbg_printf("applying world\n");
859
	ss->prefer_pinning = 1;
860
	ss->solver_flags_inherit = solver_flags;
861
862
	foreach_array_item(d, world) {
		if (d->broken)
863
			continue;
864
865
866
867
		name = d->name;
		discover_name(ss, d->name);
		ss->pinning_inherit = BIT(d->repository_tag);
		apply_constraint(ss, NULL, d);
868
	}
869
	ss->solver_flags_inherit = 0;
870
871
	ss->pinning_inherit = 0;
	ss->prefer_pinning = 0;
872
	dbg_printf("applying world [finished]\n");
873

874
	do {
875
876
877
		while (!list_empty(&ss->dirty_head)) {
			name = list_pop(&ss->dirty_head, struct apk_name, ss.dirty_list);
			reconsider_name(ss, name);
878
		}
Timo Teräs's avatar
Timo Teräs committed
879

880
881
		name = NULL;
		list_for_each_entry(name0, &ss->unresolved_head, ss.unresolved_list) {
882
			if (name0->ss.reverse_deps_done && name0->ss.requirers && !name0->ss.has_options) {
883
				name = name0;
Timo Teräs's avatar
Timo Teräs committed
884
				break;
885
886
887
			}
			if (name == NULL)
				goto prefer;
888
			if ((!!name0->ss.requirers) - (!!name->ss.requirers) < 0)
Timo Teräs's avatar
Timo Teräs committed
889
				continue;
890
			if (name0->ss.max_dep_chain - name->ss.max_dep_chain < 0)
891
				continue;
892
893
		prefer:
			name = name0;
894
		}
895
896
		if (name == NULL)
			break;
897

898
899
		select_package(ss, name);
	} while (1);
900

901
	generate_changeset(ss, world);
902

903
	if (ss->errors && (apk_flags & APK_FORCE)) {
904
905
906
		foreach_array_item(d, world) {
			name = d->name;
			pkg = name->ss.chosen.pkg;
907
			if (pkg == NULL || pkg->ss.error) {
908
				d->broken = 1;
909
910
911
912
913
914
915
916
				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;
	}

917
918
919
	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
920

921
	return ss->errors;
922
}