solver.c 31.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
#include <strings.h>
15
16
17
18
19
#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
20
21
#include "apk_print.h"

22
23
24
//#define DEBUG_PRINT

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

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

33
34
struct apk_solver_state {
	struct apk_database *db;
35
36
37
38
	struct apk_changeset *changeset;
	struct list_head dirty_head;
	struct list_head unresolved_head;
	unsigned int errors;
39
	unsigned int solver_flags_inherit;
40
41
	unsigned int pinning_inherit;
	unsigned int default_repos;
42
	unsigned ignore_conflict : 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
static int get_tag(struct apk_database *db, unsigned int pinning_mask, unsigned int repos)
{
	int i;

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

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

81
static void mark_error(struct apk_solver_state *ss, struct apk_package *pkg, const char *reason)
82
83
84
{
	if (pkg == NULL || pkg->ss.error)
		return;
85
	dbg_printf("ERROR PKG: %s: %s\n", pkg->name->name, reason);
86
87
88
89
	pkg->ss.error = 1;
	ss->errors++;
}

90
static void queue_dirty(struct apk_solver_state *ss, struct apk_name *name)
91
{
92
93
94
	if (list_hashed(&name->ss.dirty_list) || name->ss.locked ||
	    (name->ss.requirers == 0 && !name->ss.reevaluate_iif))
		return;
95

96
97
	dbg_printf("queue_dirty: %s\n", name->name);
	list_add_tail(&name->ss.dirty_list, &ss->dirty_head);
98
99
}

100
static void queue_unresolved(struct apk_solver_state *ss, struct apk_name *name)
101
{
102
	int want;
103

104
105
	if (name->ss.locked)
		return;
106

107
	want = (name->ss.requirers > 0) || (name->ss.has_iif);
108
	dbg_printf("queue_unresolved: %s, want=%d (requirers=%d, has_iif=%d)\n", name->name, want, name->ss.requirers, name->ss.has_iif);
109
110
111
112
	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);
113
114
}

115
static void reevaluate_reverse_deps(struct apk_solver_state *ss, struct apk_name *name)
116
{
117
118
119
120
121
122
123
124
125
	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);
	}
126
}
127

128
static void reevaluate_reverse_installif(struct apk_solver_state *ss, struct apk_name *name)
129
{
130
131
132
133
134
135
	struct apk_name **pname0, *name0;

	foreach_array_item(pname0, name->rinstall_if) {
		name0 = *pname0;
		if (!name0->ss.seen)
			continue;
136
137
		if (name0->ss.no_iif)
			continue;
138
139
140
		name0->ss.reevaluate_iif = 1;
		queue_dirty(ss, name0);
	}
141
142
}

143
static void disqualify_package(struct apk_solver_state *ss, struct apk_package *pkg, const char *reason)
144
{
145
	struct apk_dependency *p;
146

147
	dbg_printf("disqualify_package: " PKG_VER_FMT " (%s)\n", PKG_VER_PRINTF(pkg), reason);
148
	pkg->ss.pkg_selectable = 0;
149
150
151
152
	reevaluate_reverse_deps(ss, pkg->name);
	foreach_array_item(p, pkg->provides)
		reevaluate_reverse_deps(ss, p->name);
	reevaluate_reverse_installif(ss, pkg->name);
153
154
}

155
static int dependency_satisfiable(struct apk_solver_state *ss, struct apk_dependency *dep)
156
{
157
	struct apk_name *name = dep->name;
158
	struct apk_provider *p;
159

160
161
162
	if (dep->conflict && ss->ignore_conflict)
		return TRUE;

163
164
	if (name->ss.locked)
		return apk_dep_is_provided(dep, &name->ss.chosen);
165

166
167
	if (name->ss.requirers == 0 && apk_dep_is_provided(dep, &provider_none))
		return TRUE;
168

169
	foreach_array_item(p, name->providers)
170
		if (p->pkg->ss.pkg_selectable && apk_dep_is_provided(dep, p))
171
			return TRUE;
172

173
	return FALSE;
174
175
}

176
static void discover_name(struct apk_solver_state *ss, struct apk_name *name)
177
{
178
	struct apk_database *db = ss->db;
179
180
181
	struct apk_name **pname0;
	struct apk_provider *p;
	struct apk_dependency *dep;
182
	unsigned int repos;
183

184
185
	if (name->ss.seen)
		return;
186

187
	name->ss.seen = 1;
188
	name->ss.no_iif = 1;
189
190
	foreach_array_item(p, name->providers) {
		struct apk_package *pkg = p->pkg;
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
		if (!pkg->ss.seen) {
			pkg->ss.seen = 1;
			pkg->ss.pinning_allowed = APK_DEFAULT_PINNING_MASK;
			pkg->ss.pinning_preferred = APK_DEFAULT_PINNING_MASK;
			pkg->ss.pkg_available =
				(pkg->filename != NULL) ||
				(pkg->repos & db->available_repos & ~BIT(APK_REPOSITORY_CACHED));
			/* Package is in 'cached' repository if filename is provided,
			 * or it's a 'virtual' package with install_size zero */
			pkg->ss.pkg_selectable =
				(pkg->repos & db->available_repos) ||
				pkg->cached_non_repository ||
				pkg->ipkg;

			/* Prune install_if packages that are no longer available,
			 * currently works only if SOLVERF_AVAILABLE is set in the
			 * global solver flags. */
			pkg->ss.iif_failed =
				(pkg->install_if->num == 0) ||
				((ss->solver_flags_inherit & APK_SOLVERF_AVAILABLE) &&
				 !pkg->ss.pkg_available);

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

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

229
230
231
232
233
234
			dbg_printf("discover " PKG_VER_FMT ": tag_ok=%d, tag_pref=%d max_dep_chain=%d selectable=%d\n",
				PKG_VER_PRINTF(pkg),
				pkg->ss.tag_ok,
				pkg->ss.tag_preferred,
				pkg->ss.max_dep_chain,
				pkg->ss.pkg_selectable);
235
		}
236
237

		name->ss.no_iif &= pkg->ss.iif_failed;
238
		name->ss.max_dep_chain = max(name->ss.max_dep_chain, pkg->ss.max_dep_chain);
239

240
241
		dbg_printf("discover %s: max_dep_chain=%d no_iif=%d\n",
			name->name, name->ss.max_dep_chain, name->ss.no_iif);
242
	}
243
244
	foreach_array_item(pname0, name->rinstall_if)
		discover_name(ss, *pname0);
245
246
}

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

254
255
static void inherit_pinning_and_flags(
	struct apk_solver_state *ss, struct apk_package *pkg, struct apk_package *ppkg)
256
257
258
{
	unsigned int repos = get_pkg_repos(ss->db, pkg);

259
260
261
262
263
264
265
266
267
268
269
270
	if (ppkg != NULL) {
		/* inherited */
		pkg->ss.solver_flags |= ppkg->ss.solver_flags_inheritable;
		pkg->ss.solver_flags_inheritable |= ppkg->ss.solver_flags_inheritable;
		pkg->ss.pinning_allowed |= ppkg->ss.pinning_allowed;
	} else {
		/* world dependency */
		pkg->ss.solver_flags |= ss->solver_flags_inherit;
		pkg->ss.solver_flags_inheritable |= ss->solver_flags_inherit;
		pkg->ss.pinning_allowed |= ss->pinning_inherit;
		/* also prefer main pinnings */
		pkg->ss.pinning_preferred = ss->pinning_inherit;
271
272
		pkg->ss.tag_preferred = !!(repos & apk_db_get_pinning_mask_repos(ss->db, pkg->ss.pinning_preferred));
	}
273
274
275
276
	pkg->ss.tag_ok |= !!(repos & apk_db_get_pinning_mask_repos(ss->db, pkg->ss.pinning_allowed));

	dbg_printf(PKG_VER_FMT ": tag_ok=%d, tag_pref=%d\n",
		PKG_VER_PRINTF(pkg), pkg->ss.tag_ok, pkg->ss.tag_preferred);
277
278
}

279
static void apply_constraint(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep)
280
{
281
	struct apk_name *name = dep->name;
282
283
	struct apk_provider *p0;
	int is_provided;
284

285
	dbg_printf("    apply_constraint: %s%s%s" BLOB_FMT "\n",
286
287
288
289
290
		dep->conflict ? "!" : "",
		name->name,
		apk_version_op_string(dep->result_mask),
		BLOB_PRINTF(*dep->version));

291
292
293
	if (dep->conflict && ss->ignore_conflict)
		return;

294
	name->ss.requirers += !dep->conflict;
295
296
	if (name->ss.requirers == 1 && !dep->conflict)
		name_requirers_changed(ss, name);
297

298
	foreach_array_item(p0, name->providers) {
299
		struct apk_package *pkg0 = p0->pkg;
300

301
		is_provided = apk_dep_is_provided(dep, p0);
302
		dbg_printf("    apply_constraint: provider: %s-" BLOB_FMT ": %d\n",
303
			pkg0->name->name, BLOB_PRINTF(*p0->version), is_provided);
304

305
		pkg0->ss.conflicts += !is_provided;
306
		if (unlikely(pkg0->ss.pkg_selectable && pkg0->ss.conflicts))
307
			disqualify_package(ss, pkg0, "conflicting dependency");
308

309
310
		if (is_provided)
			inherit_pinning_and_flags(ss, pkg0, ppkg);
311
	}
312
313
}

314
static void exclude_non_providers(struct apk_solver_state *ss, struct apk_name *name, struct apk_name *must_provide, int skip_virtuals)
315
316
317
318
{
	struct apk_provider *p;
	struct apk_dependency *d;

319
	if (name == must_provide || ss->ignore_conflict)
320
321
		return;

322
	dbg_printf("%s must provide %s (skip_virtuals=%d)\n", name->name, must_provide->name, skip_virtuals);
323
324

	foreach_array_item(p, name->providers) {
325
326
		if (p->pkg->name == must_provide || !p->pkg->ss.pkg_selectable ||
		    (skip_virtuals && p->version == &apk_null_blob))
327
328
			goto next;
		foreach_array_item(d, p->pkg->provides)
329
			if (d->name == must_provide || (skip_virtuals && d->version == &apk_null_blob))
330
331
332
333
334
335
				goto next;
		disqualify_package(ss, p->pkg, "provides transitivity");
	next: ;
	}
}

336
static inline int merge_index(unsigned short *index, int num_options)
337
{
338
339
340
	if (*index != num_options) return 0;
	*index = num_options + 1;
	return 1;
341
342
343
344
345
346
347
348
349
350
351
352
}

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

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

	return ret;
}

353
static void reconsider_name(struct apk_solver_state *ss, struct apk_name *name)
354
{
355
	struct apk_name *name0, **pname0;
356
	struct apk_dependency *dep;
357
	struct apk_package *first_candidate = NULL, *pkg;
358
359
	struct apk_provider *p;
	int reevaluate_deps, reevaluate_iif;
360
	int num_options = 0, num_tag_not_ok = 0, has_iif = 0, no_iif = 1;
361

362
	dbg_printf("reconsider_name: %s\n", name->name);
363

364
365
	reevaluate_deps = name->ss.reevaluate_deps;
	reevaluate_iif = name->ss.reevaluate_iif;
366
	name->ss.reevaluate_deps = 0;
367
	name->ss.reevaluate_iif = 0;
368

369
370
	/* propagate down by merging common dependencies and
	 * applying new constraints */
371
	foreach_array_item(p, name->providers) {
372
		/* check if this pkg's dependencies have become unsatisfiable */
373
		pkg = p->pkg;
Timo Teräs's avatar
Timo Teräs committed
374
		pkg->ss.dependencies_merged = 0;
375
		if (reevaluate_deps) {
376
			if (!pkg->ss.pkg_selectable)
377
				continue;
378
			foreach_array_item(dep, pkg->depends) {
379
380
381
382
383
384
				if (!dependency_satisfiable(ss, dep)) {
					disqualify_package(ss, pkg, "dependency no longer satisfiable");
					break;
				}
			}
		}
385
		if (!pkg->ss.pkg_selectable)
386
			continue;
387

388
389
390
		if (reevaluate_iif &&
		    (pkg->ss.iif_triggered == 0 &&
		     pkg->ss.iif_failed == 0)) {
391
			pkg->ss.iif_triggered = 1;
392
			pkg->ss.iif_failed = 0;
393
			foreach_array_item(dep, pkg->install_if) {
394
395
396
397
398
399
				if (!dep->name->ss.locked) {
					pkg->ss.iif_triggered = 0;
					pkg->ss.iif_failed = 0;
					break;
				}
				if (!apk_dep_is_provided(dep, &dep->name->ss.chosen)) {
400
					pkg->ss.iif_triggered = 0;
401
					pkg->ss.iif_failed = 1;
402
					break;
403
				}
404
405
			}
		}
406
407
408
409
		if (reevaluate_iif && pkg->ss.iif_triggered) {
			foreach_array_item(dep, pkg->install_if)
				inherit_pinning_and_flags(ss, pkg, dep->name->ss.chosen.pkg);
		}
410
		has_iif |= pkg->ss.iif_triggered;
411
		no_iif  &= pkg->ss.iif_failed;
412
413
414
		dbg_printf("  "PKG_VER_FMT": iif_triggered=%d iif_failed=%d, no_iif=%d\n",
			PKG_VER_PRINTF(pkg), pkg->ss.iif_triggered, pkg->ss.iif_failed,
			no_iif);
Timo Teräs's avatar
Timo Teräs committed
415

416
		if (name->ss.requirers == 0)
417
			continue;
418

419
		/* merge common dependencies */
Timo Teräs's avatar
Timo Teräs committed
420
		pkg->ss.dependencies_merged = 1;
421
422
		if (first_candidate == NULL)
			first_candidate = pkg;
423
424
425
426
427
428

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

429
430
		if (merge_index(&pkg->name->ss.merge_provides, num_options))
			pkg->name->ss.has_virtual_provides |= (p->version == &apk_null_blob);
431
		foreach_array_item(dep, pkg->provides)
432
433
			if (merge_index(&dep->name->ss.merge_provides, num_options))
				dep->name->ss.has_virtual_provides |= (dep->version == &apk_null_blob);
434
435
436

		num_tag_not_ok += !pkg->ss.tag_ok;
		num_options++;
437
	}
438
	name->ss.has_options = (num_options > 1 || num_tag_not_ok > 0);
439
	name->ss.has_iif = has_iif;
440
	name->ss.no_iif = no_iif;
441
442
	queue_unresolved(ss, name);

443
	if (first_candidate != NULL) {
444
		pkg = first_candidate;
445
446
447
		foreach_array_item(p, name->providers)
			p->pkg->ss.dependencies_used = p->pkg->ss.dependencies_merged;

448
		/* propagate down common dependencies */
449
450
		if (num_options == 1) {
			/* FIXME: keeps increasing counts, use bit fields instead? */
451
452
453
			foreach_array_item(dep, pkg->depends)
				if (merge_index_complete(&dep->name->ss.merge_depends, num_options))
					apply_constraint(ss, pkg, dep);
454
455
		} else {
			/* FIXME: could merge versioning bits too */
456
			foreach_array_item(dep, pkg->depends) {
457
				name0 = dep->name;
458
459
				if (merge_index_complete(&name0->ss.merge_depends, num_options) &&
				    name0->ss.requirers == 0) {
460
					/* common dependency name with all */
461
462
463
464
					dbg_printf("%s common dependency: %s\n",
						   name->name, name0->name);
					name0->ss.requirers++;
					name_requirers_changed(ss, name0);
465
466
					foreach_array_item(p, name0->providers)
						inherit_pinning_and_flags(ss, p->pkg, pkg);
467
468
				}
			}
Timo Teräs's avatar
Timo Teräs committed
469
		}
470
471
472

		/* provides transitivity */
		if (merge_index_complete(&pkg->name->ss.merge_provides, num_options))
473
			exclude_non_providers(ss, pkg->name, name, pkg->name->ss.has_virtual_provides);
474
475
		foreach_array_item(dep, pkg->provides)
			if (merge_index_complete(&dep->name->ss.merge_provides, num_options))
476
477
478
479
480
				exclude_non_providers(ss, dep->name, name, dep->name->ss.has_virtual_provides);

		pkg->name->ss.has_virtual_provides = 0;
		foreach_array_item(dep, pkg->provides)
			dep->name->ss.has_virtual_provides = 0;
Timo Teräs's avatar
Timo Teräs committed
481
	}
482

483
484
485
486
487
488
489
490
491
492
493
	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);
494
495
}

496
497
498
499
500
501
502
503
504
505
506
static int count_requirers(const struct apk_package *pkg)
{
	int cnt = pkg->name->ss.requirers;
	struct apk_dependency *p;

	foreach_array_item(p, pkg->provides)
		cnt += p->name->ss.requirers;

	return cnt;
}

507
508
static int compare_providers(struct apk_solver_state *ss,
			     struct apk_provider *pA, struct apk_provider *pB)
509
{
510
511
	struct apk_database *db = ss->db;
	struct apk_package *pkgA = pA->pkg, *pkgB = pB->pkg;
512
	unsigned int solver_flags;
513
	int r;
514

515
516
517
	/* Prefer existing package */
	if (pkgA == NULL || pkgB == NULL)
		return (pkgA != NULL) - (pkgB != NULL);
518

519
520
521
522
523
524
525
526
527
	/* 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;
528

529
		/* Prefer available */
530
		if (solver_flags & APK_SOLVERF_AVAILABLE) {
531
			r = (int)pkgA->ss.pkg_available - (int)pkgB->ss.pkg_available;
532
533
			if (r)
				return r;
534
535
536
537
		} else if (solver_flags & APK_SOLVERF_REINSTALL) {
			r = (int)pkgA->ss.pkg_selectable - (int)pkgB->ss.pkg_selectable;
			if (r)
				return r;
538
539
540
		}
	} else {
		/* Prefer without errors */
541
		r = (int)pkgA->ss.pkg_selectable - (int)pkgB->ss.pkg_selectable;
542
543
		if (r)
			return r;
Timo Teräs's avatar
Timo Teräs committed
544

545
546
547
548
549
		/* 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
550
551
552
		if (r)
			return r;

553
		/* Prefer installed on self-upgrade */
554
555
		if ((db->performing_self_upgrade && !(solver_flags & APK_SOLVERF_UPGRADE)) ||
		    (solver_flags & APK_SOLVERF_IGNORE_UPGRADE)) {
556
557
558
559
			r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
			if (r)
				return r;
		}
560

561
562
		/* Prefer allowed pinning */
		r = (int)pkgA->ss.tag_ok - (int)pkgB->ss.tag_ok;
563
564
		if (r)
			return r;
565

566
		/* Prefer available */
567
		if (solver_flags & APK_SOLVERF_AVAILABLE) {
568
			r = (int)pkgA->ss.pkg_available - (int)pkgB->ss.pkg_available;
569
570
571
			if (r)
				return r;
		}
572

573
574
		/* Prefer preferred pinning */
		r = (int)pkgA->ss.tag_preferred - (int)pkgB->ss.tag_preferred;
575
576
		if (r)
			return r;
577

578
579
580
581
582
		/* Prefer highest requirer count. */
		r = count_requirers(pkgA) - count_requirers(pkgB);
		if (r)
			return r;

583
		/* Prefer installed */
584
585
		if (!(solver_flags & APK_SOLVERF_UPGRADE) ||
		    (solver_flags & APK_SOLVERF_IGNORE_UPGRADE)) {
586
587
588
589
			r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
			if (r)
				return r;
		}
590
	}
591

592
593
594
595
596
597
598
	/* 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;
	}
599

600
601
602
603
604
605
606
607
608
	/* 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
609

610
611
612
613
	/* Prefer installed (matches here if upgrading) */
	r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
	if (r)
		return r;
614

615
616
617
618
619
	/* Prefer highest declared provider priority. */
	r = pkgA->provider_priority - pkgB->provider_priority;
	if (r)
		return r;

620
621
622
623
624
	/* Prefer without errors (mostly if --latest used, and different provider) */
	r = (int)pkgA->ss.pkg_selectable - (int)pkgB->ss.pkg_selectable;
	if (r)
		return r;

625
	/* Prefer lowest available repository */
626
	return ffs(pkgB->repos) - ffs(pkgA->repos);
627
}
628

629
static void assign_name(struct apk_solver_state *ss, struct apk_name *name, struct apk_provider p)
630
{
631
	struct apk_provider *p0;
632
633
634
635
636
637

	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;
638
639
		if (ss->ignore_conflict)
			return;
640
		/* Conflict: providing same name */
641
642
		mark_error(ss, p.pkg, "conflict: same name provided");
		mark_error(ss, name->ss.chosen.pkg, "conflict: same name provided");
643
		return;
644
	}
645

646
647
	if (p.pkg)
		dbg_printf("assign %s to "PKG_VER_FMT"\n", name->name, PKG_VER_PRINTF(p.pkg));
648

649
650
651
652
653
654
655
656
	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);

	/* disqualify all conflicting packages */
657
658
659
660
661
662
663
664
665
	if (!ss->ignore_conflict) {
		foreach_array_item(p0, name->providers) {
			if (p0->pkg == p.pkg)
				continue;
			if (p.version == &apk_null_blob &&
			    p0->version == &apk_null_blob)
				continue;
			disqualify_package(ss, p0->pkg, "conflicting provides");
		}
666
	}
667
	reevaluate_reverse_deps(ss, name);
668
	reevaluate_reverse_installif(ss, name);
669
670
}

671
static void select_package(struct apk_solver_state *ss, struct apk_name *name)
672
{
673
	struct apk_provider chosen = { NULL, &apk_null_blob }, *p;
674
	struct apk_package *pkg = NULL;
675
	struct apk_dependency *d;
676

677
	dbg_printf("select_package: %s (requirers=%d, iif=%d)\n", name->name, name->ss.requirers, name->ss.has_iif);
678

679
	if (name->ss.requirers || name->ss.has_iif) {
680
		foreach_array_item(p, name->providers) {
681
682
683
684
685
			dbg_printf("  consider "PKG_VER_FMT" iif_triggered=%d, tag_ok=%d, selectable=%d, available=%d, flags=0x%x, provider_priority=%d, installed=%d\n",
				PKG_VER_PRINTF(p->pkg),
				p->pkg->ss.iif_triggered, p->pkg->ss.tag_ok,
				p->pkg->ss.pkg_selectable, p->pkg->ss.pkg_available,
				p->pkg->ss.solver_flags,
686
				p->pkg->provider_priority, p->pkg->ipkg != NULL);
687
			/* Ensure valid pinning and install-if trigger */
688
			if (name->ss.requirers == 0 &&
689
690
			    (!p->pkg->ss.iif_triggered ||
			     !p->pkg->ss.tag_ok))
691
				continue;
692
693
			/* Virtual packages without provider_priority cannot be autoselected,
			 * unless there is only one provider */
694
695
696
			if (p->version == &apk_null_blob &&
			    p->pkg->name->auto_select_virtual == 0 &&
			    p->pkg->name->ss.requirers == 0 &&
697
			    (p->pkg->provider_priority == 0 && name->providers->num > 1))
698
				continue;
699
700
			if (compare_providers(ss, p, &chosen) > 0)
				chosen = *p;
701
		}
702
	}
703

704
705
	pkg = chosen.pkg;
	if (pkg) {
706
		if (!pkg->ss.pkg_selectable || !pkg->ss.tag_ok) {
707
			/* Selecting broken or unallowed package */
708
			mark_error(ss, pkg, "broken package / tag not ok");
709
		}
710
		dbg_printf("selecting: " PKG_VER_FMT ", available: %d\n", PKG_VER_PRINTF(pkg), pkg->ss.pkg_selectable);
711

712
		assign_name(ss, pkg->name, APK_PROVIDER_FROM_PACKAGE(pkg));
713
714
715
716
717
		foreach_array_item(d, pkg->provides)
			assign_name(ss, d->name, APK_PROVIDER_FROM_PROVIDES(pkg, d));

		foreach_array_item(d, pkg->depends)
			apply_constraint(ss, pkg, d);
718
719
720
	} else {
		dbg_printf("selecting: %s [unassigned]\n", name->name);
		assign_name(ss, name, provider_none);
721
722
723
724
		if (name->ss.requirers > 0) {
			dbg_printf("ERROR NO-PROVIDER: %s\n", name->name);
			ss->errors++;
		}
725
	}
726
727
}

728
static void record_change(struct apk_solver_state *ss, struct apk_package *opkg, struct apk_package *npkg)
729
{
730
731
732
	struct apk_changeset *changeset = ss->changeset;
	struct apk_change *change;

733
	change = apk_change_array_add(&changeset->changes);
734
735
736
	*change = (struct apk_change) {
		.old_pkg = opkg,
		.old_repository_tag = opkg ? opkg->ipkg->repository_tag : 0,
737
738
739
		.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,
740
	};
741
	if (npkg == NULL)
742
		changeset->num_remove++;
743
	else if (opkg == NULL)
744
		changeset->num_install++;
745
	else if (npkg != opkg || change->reinstall || change->new_repository_tag != change->old_repository_tag)
746
		changeset->num_adjust++;
747
}
748

749
750
751
752
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);

753
static void cset_track_deps_added(struct apk_package *pkg)
754
755
756
{
	struct apk_dependency *d;

757
758
759
760
761
	foreach_array_item(d, pkg->depends) {
		if (d->conflict || !d->name->ss.installed_name)
			continue;
		d->name->ss.installed_name->ss.requirers++;
	}
762
763
764
765
766
767
768
769
}

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) {
770
		if (d->conflict || !d->name->ss.installed_name)
771
			continue;
772
		if (--d->name->ss.installed_name->ss.requirers > 0)
773
			continue;
774
		pkg0 = d->name->ss.installed_pkg;
775
776
777
778
779
780
781
		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)
{
782
783
784
785
786
787
	/* NOTE: an orphaned package name may have 0 requirers because it is now being satisfied
	 * through an alternate provider.  In these cases, we will handle this later as an adjustment
	 * operation using cset_gen_name_change().  As such, only insert a removal into the transaction
	 * if there is no other resolved provider.
	 */
	if (pkg->name->ss.requirers == 0 && pkg->name->ss.chosen.pkg == NULL)
788
		cset_gen_name_remove(ss, pkg);
789
790
}

791
static void cset_check_install_by_iif(struct apk_solver_state *ss, struct apk_name *name)
792
{
793
	struct apk_package *pkg = name->ss.chosen.pkg;
794
	struct apk_dependency *dep0;
795

796
	if (pkg == NULL || !name->ss.seen || name->ss.in_changeset)
797
798
		return;

799
	foreach_array_item(dep0, pkg->install_if) {
800
801
802
803
804
		struct apk_name *name0 = dep0->name;
		if (!name0->ss.in_changeset)
			return;
		if (!apk_dep_is_provided(dep0, &name0->ss.chosen))
			return;
805
	}
806
807
808
809
810
	cset_gen_name_change(ss, name);
}

static void cset_check_removal_by_iif(struct apk_solver_state *ss, struct apk_name *name)
{
811
	struct apk_package *pkg = name->ss.installed_pkg;
812
	struct apk_dependency *dep0;
813

814
	if (pkg == NULL || name->ss.in_changeset || name->ss.chosen.pkg != NULL)
815
816
817
818
819
820
821
822
823
824
825
		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;
		}
	}
}

826
827
828
829
830
831
832
833
834
835
836
static void cset_gen_name_remove_orphan(struct apk_solver_state *ss, struct apk_name *name)
{
	struct apk_package *pkg = name->ss.chosen.pkg;

	if (name->ss.in_changeset) return;
	name->ss.in_changeset = 1;

	if ((!pkg || pkg->name != name) && name->ss.installed_pkg)
		cset_gen_name_remove(ss, name->ss.installed_pkg);
}

837
838
839
static void cset_gen_name_change(struct apk_solver_state *ss, struct apk_name *name)
{
	struct apk_name **pname;
840
	struct apk_package *pkg, *opkg;
841
842
	struct apk_dependency *d;

843
844
	if (name->ss.in_changeset) return;

845
	cset_gen_name_remove_orphan(ss, name);
846

847
848
	pkg = name->ss.chosen.pkg;
	if (!pkg || pkg->ss.in_changeset) return;
849
	pkg->ss.in_changeset = 1;
850
851

	cset_gen_name_remove_orphan(ss, pkg->name);
852
	foreach_array_item(d, pkg->provides)
853
		cset_gen_name_remove_orphan(ss, d->name);
854

855
	opkg = pkg->name->ss.installed_pkg;
856
857
858
859
860
861
862
863
	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);

864
	dbg_printf("Selecting: "PKG_VER_FMT"%s\n", PKG_VER_PRINTF(pkg), pkg->ss.pkg_selectable ? "" : " [NOT SELECTABLE]");
865
866
867
868
869
	record_change(ss, opkg, pkg);

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

870
	cset_track_deps_added(pkg);
871
872
873
874
	if (opkg)
		cset_track_deps_removed(ss, opkg);
}

875
876
877
878
879
static void cset_gen_name_remove0(struct apk_package *pkg0, struct apk_dependency *dep0, struct apk_package *pkg, void *ctx)
{
	cset_gen_name_remove(ctx, pkg0);
}

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

884
885
886
	if (pkg->ss.in_changeset ||
	    (name->ss.chosen.pkg != NULL &&
	     name->ss.chosen.pkg->name == name))
887
888
889
		return;

	name->ss.in_changeset = 1;
890
	pkg->ss.in_changeset = 1;
891
	apk_pkg_foreach_reverse_dependency(pkg, APK_FOREACH_INSTALLED|APK_DEP_SATISFIES, cset_gen_name_remove0, ss);
892
893
894
895
	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);
896
897
}

898
static void cset_gen_dep(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep)
899
{
900
	struct apk_name *name = dep->name;
901
	struct apk_package *pkg = name->ss.chosen.pkg;
902

903
904
905
	if (dep->conflict && ss->ignore_conflict)
		return;

906
	if (!apk_dep_is_provided(dep, &name->ss.chosen))
907
		mark_error(ss, ppkg, "unfulfilled dependency");
908