solver.c 30.5 KB
Newer Older
1
/* solver.c - Alpine Package Keeper (APK)
2
 * Up- and down-propagating, forwarding checking, deductive dependency solver.
3
 *
4
 * Copyright (C) 2008-2013 Timo Teräs <timo.teras@iki.fi>
5
6
7
8
9
10
11
 * All rights reserved.
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 as published
 * by the Free Software Foundation. See http://www.gnu.org/ for details.
 */

12
#include <stdint.h>
13
#include <unistd.h>
14
#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
};
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
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);
}

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

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

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

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

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

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

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

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

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

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

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

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

159
160
	if (name->ss.locked)
		return apk_dep_is_provided(dep, &name->ss.chosen);
161

162
163
	if (name->ss.requirers == 0 && apk_dep_is_provided(dep, &provider_none))
		return TRUE;
164

165
	foreach_array_item(p, name->providers)
166
		if (p->pkg->ss.pkg_selectable && apk_dep_is_provided(dep, p))
167
			return TRUE;
168

169
	return FALSE;
170
171
}

172
static void discover_name(struct apk_solver_state *ss, struct apk_name *name)
173
{
174
	struct apk_database *db = ss->db;
175
176
177
	struct apk_name **pname0;
	struct apk_provider *p;
	struct apk_dependency *dep;
178
	unsigned int repos;
179

180
181
	if (name->ss.seen)
		return;
182

183
	name->ss.seen = 1;
184
	name->ss.no_iif = 1;
185
186
	foreach_array_item(p, name->providers) {
		struct apk_package *pkg = p->pkg;
187
188
189
190
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
		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;
218

219
220
221
222
223
			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);
			}
224

225
226
227
228
229
230
			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);
231
		}
232
233

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

236
237
		dbg_printf("discover %s: max_dep_chain=%d no_iif=%d\n",
			name->name, name->ss.max_dep_chain, name->ss.no_iif);
238
	}
239
240
	foreach_array_item(pname0, name->rinstall_if)
		discover_name(ss, *pname0);
241
242
}

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

250
251
static void inherit_pinning_and_flags(
	struct apk_solver_state *ss, struct apk_package *pkg, struct apk_package *ppkg)
252
253
254
{
	unsigned int repos = get_pkg_repos(ss->db, pkg);

255
256
257
258
259
260
261
262
263
264
265
266
	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;
267
268
		pkg->ss.tag_preferred = !!(repos & apk_db_get_pinning_mask_repos(ss->db, pkg->ss.pinning_preferred));
	}
269
270
271
272
	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);
273
274
}

275
static void apply_constraint(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep)
276
{
277
	struct apk_name *name = dep->name;
278
279
	struct apk_provider *p0;
	int is_provided;
280

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

	name->ss.requirers += !dep->conflict;
288
289
	if (name->ss.requirers == 1 && !dep->conflict)
		name_requirers_changed(ss, name);
290

291
	foreach_array_item(p0, name->providers) {
292
		struct apk_package *pkg0 = p0->pkg;
293

294
		is_provided = apk_dep_is_provided(dep, p0);
295
		dbg_printf("    apply_constraint: provider: %s-" BLOB_FMT ": %d\n",
296
			pkg0->name->name, BLOB_PRINTF(*p0->version), is_provided);
297

298
		pkg0->ss.conflicts += !is_provided;
299
		if (unlikely(pkg0->ss.pkg_selectable && pkg0->ss.conflicts))
300
			disqualify_package(ss, pkg0, "conflicting dependency");
301

302
303
		if (is_provided)
			inherit_pinning_and_flags(ss, pkg0, ppkg);
304
	}
305
306
}

307
static void exclude_non_providers(struct apk_solver_state *ss, struct apk_name *name, struct apk_name *must_provide, int skip_virtuals)
308
309
310
311
{
	struct apk_provider *p;
	struct apk_dependency *d;

312
313
314
	if (name == must_provide)
		return;

315
	dbg_printf("%s must provide %s (skip_virtuals=%d)\n", name->name, must_provide->name, skip_virtuals);
316
317

	foreach_array_item(p, name->providers) {
318
319
		if (p->pkg->name == must_provide || !p->pkg->ss.pkg_selectable ||
		    (skip_virtuals && p->version == &apk_null_blob))
320
321
			goto next;
		foreach_array_item(d, p->pkg->provides)
322
			if (d->name == must_provide || (skip_virtuals && d->version == &apk_null_blob))
323
324
325
326
327
328
				goto next;
		disqualify_package(ss, p->pkg, "provides transitivity");
	next: ;
	}
}

329
static inline int merge_index(unsigned short *index, int num_options)
330
{
331
332
333
	if (*index != num_options) return 0;
	*index = num_options + 1;
	return 1;
334
335
336
337
338
339
340
341
342
343
344
345
}

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

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

	return ret;
}

346
static void reconsider_name(struct apk_solver_state *ss, struct apk_name *name)
347
{
348
	struct apk_name *name0, **pname0;
349
	struct apk_dependency *dep;
350
	struct apk_package *first_candidate = NULL, *pkg;
351
352
	struct apk_provider *p;
	int reevaluate_deps, reevaluate_iif;
353
	int num_options = 0, num_tag_not_ok = 0, has_iif = 0, no_iif = 1;
354

355
	dbg_printf("reconsider_name: %s\n", name->name);
356

357
358
	reevaluate_deps = name->ss.reevaluate_deps;
	reevaluate_iif = name->ss.reevaluate_iif;
359
	name->ss.reevaluate_deps = 0;
360
	name->ss.reevaluate_iif = 0;
361

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

381
382
383
		if (reevaluate_iif &&
		    (pkg->ss.iif_triggered == 0 &&
		     pkg->ss.iif_failed == 0)) {
384
			pkg->ss.iif_triggered = 1;
385
			pkg->ss.iif_failed = 0;
386
			foreach_array_item(dep, pkg->install_if) {
387
388
389
390
391
392
				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)) {
393
					pkg->ss.iif_triggered = 0;
394
					pkg->ss.iif_failed = 1;
395
					break;
396
				}
397
398
			}
		}
399
400
401
402
		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);
		}
403
		has_iif |= pkg->ss.iif_triggered;
404
		no_iif  &= pkg->ss.iif_failed;
405
406
407
		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
408

409
		if (name->ss.requirers == 0)
410
			continue;
411

412
		/* merge common dependencies */
Timo Teräs's avatar
Timo Teräs committed
413
		pkg->ss.dependencies_merged = 1;
414
415
		if (first_candidate == NULL)
			first_candidate = pkg;
416
417
418
419
420
421

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

422
423
		if (merge_index(&pkg->name->ss.merge_provides, num_options))
			pkg->name->ss.has_virtual_provides |= (p->version == &apk_null_blob);
424
		foreach_array_item(dep, pkg->provides)
425
426
			if (merge_index(&dep->name->ss.merge_provides, num_options))
				dep->name->ss.has_virtual_provides |= (dep->version == &apk_null_blob);
427
428
429

		num_tag_not_ok += !pkg->ss.tag_ok;
		num_options++;
430
	}
431
	name->ss.has_options = (num_options > 1 || num_tag_not_ok > 0);
432
	name->ss.has_iif = has_iif;
433
	name->ss.no_iif = no_iif;
434
435
	queue_unresolved(ss, name);

436
	if (first_candidate != NULL) {
437
		pkg = first_candidate;
438
439
440
		foreach_array_item(p, name->providers)
			p->pkg->ss.dependencies_used = p->pkg->ss.dependencies_merged;

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

		/* provides transitivity */
		if (merge_index_complete(&pkg->name->ss.merge_provides, num_options))
464
			exclude_non_providers(ss, pkg->name, name, pkg->name->ss.has_virtual_provides);
465
466
		foreach_array_item(dep, pkg->provides)
			if (merge_index_complete(&dep->name->ss.merge_provides, num_options))
467
468
469
470
471
				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
472
	}
473

474
475
476
477
478
479
480
481
482
483
484
	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);
485
486
}

487
488
489
490
491
492
493
494
495
496
497
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;
}

498
499
static int compare_providers(struct apk_solver_state *ss,
			     struct apk_provider *pA, struct apk_provider *pB)
500
{
501
502
	struct apk_database *db = ss->db;
	struct apk_package *pkgA = pA->pkg, *pkgB = pB->pkg;
503
	unsigned int solver_flags;
504
	int r;
505

506

507
508
509
	/* Prefer existing package */
	if (pkgA == NULL || pkgB == NULL)
		return (pkgA != NULL) - (pkgB != NULL);
510

511
512
513
514
515
516
517
518
519
	/* 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;
520

521
		/* Prefer available */
522
		if (solver_flags & APK_SOLVERF_AVAILABLE) {
523
			r = (int)pkgA->ss.pkg_available - (int)pkgB->ss.pkg_available;
524
525
			if (r)
				return r;
526
527
528
529
		} else if (solver_flags & APK_SOLVERF_REINSTALL) {
			r = (int)pkgA->ss.pkg_selectable - (int)pkgB->ss.pkg_selectable;
			if (r)
				return r;
530
531
532
		}
	} else {
		/* Prefer without errors */
533
		r = (int)pkgA->ss.pkg_selectable - (int)pkgB->ss.pkg_selectable;
534
535
		if (r)
			return r;
Timo Teräs's avatar
Timo Teräs committed
536

537
538
539
540
541
		/* 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
542
543
544
		if (r)
			return r;

545
		/* Prefer installed on self-upgrade */
546
		if (db->performing_self_upgrade && !(solver_flags & APK_SOLVERF_UPGRADE)) {
547
548
549
550
			r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
			if (r)
				return r;
		}
551

552
553
		/* Prefer allowed pinning */
		r = (int)pkgA->ss.tag_ok - (int)pkgB->ss.tag_ok;
554
555
		if (r)
			return r;
556

557
		/* Prefer available */
558
		if (solver_flags & APK_SOLVERF_AVAILABLE) {
559
			r = (int)pkgA->ss.pkg_available - (int)pkgB->ss.pkg_available;
560
561
			if (r)
				return r;
562
563
564
565
		} else if (solver_flags & APK_SOLVERF_REINSTALL) {
			r = (int)pkgA->ss.pkg_selectable - (int)pkgB->ss.pkg_selectable;
			if (r)
				return r;
566
		}
567

568
569
		/* Prefer preferred pinning */
		r = (int)pkgA->ss.tag_preferred - (int)pkgB->ss.tag_preferred;
570
571
		if (r)
			return r;
572

573
574
575
576
577
		/* Prefer highest requirer count. */
		r = count_requirers(pkgA) - count_requirers(pkgB);
		if (r)
			return r;

578
579
580
581
582
583
		/* Prefer installed */
		if (!(solver_flags & APK_SOLVERF_UPGRADE)) {
			r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
			if (r)
				return r;
		}
584
	}
585

586
587
588
589
590
591
592
	/* 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;
	}
593

594
595
596
597
598
599
600
601
602
	/* 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
603

604
605
606
607
	/* Prefer installed (matches here if upgrading) */
	r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
	if (r)
		return r;
608

609
610
611
612
613
	/* Prefer highest declared provider priority. */
	r = pkgA->provider_priority - pkgB->provider_priority;
	if (r)
		return r;

614
	/* Prefer lowest available repository */
615
	return ffs(pkgB->repos) - ffs(pkgA->repos);
616
}
617

618
static void assign_name(struct apk_solver_state *ss, struct apk_name *name, struct apk_provider p)
619
{
620
	struct apk_provider *p0;
621
622
623
624
625
626

	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;
627
		/* Conflict: providing same name */
628
629
		mark_error(ss, p.pkg, "conflict: same name provided");
		mark_error(ss, name->ss.chosen.pkg, "conflict: same name provided");
630
		return;
631
	}
632

633
634
	if (p.pkg)
		dbg_printf("assign %s to "PKG_VER_FMT"\n", name->name, PKG_VER_PRINTF(p.pkg));
635

636
637
638
639
640
641
642
643
	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 */
644
645
	foreach_array_item(p0, name->providers) {
		if (p0->pkg == p.pkg)
646
647
			continue;
		if (p.version == &apk_null_blob &&
648
		    p0->version == &apk_null_blob)
649
			continue;
650
		disqualify_package(ss, p0->pkg, "conflicting provides");
651
	}
652
	reevaluate_reverse_deps(ss, name);
653
	reevaluate_reverse_installif(ss, name);
654
655
}

656
static void select_package(struct apk_solver_state *ss, struct apk_name *name)
657
{
658
	struct apk_provider chosen = { NULL, &apk_null_blob }, *p;
659
	struct apk_package *pkg = NULL;
660
	struct apk_dependency *d;
661

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

664
	if (name->ss.requirers || name->ss.has_iif) {
665
		foreach_array_item(p, name->providers) {
666
			dbg_printf("  consider "PKG_VER_FMT" iif_triggered=%d, tag_ok=%d, selectable=%d, provider_priority=%d, installed=%d\n",
667
				PKG_VER_PRINTF(p->pkg), p->pkg->ss.iif_triggered, p->pkg->ss.tag_ok, p->pkg->ss.pkg_selectable,
668
				p->pkg->provider_priority, p->pkg->ipkg != NULL);
669
			/* Ensure valid pinning and install-if trigger */
670
			if (name->ss.requirers == 0 &&
671
672
			    (!p->pkg->ss.iif_triggered ||
			     !p->pkg->ss.tag_ok))
673
				continue;
674
675
676
677
678
679
			/* Virtual packages without provider_priority cannot be autoselected */
			if (p->version == &apk_null_blob &&
			    p->pkg->name->auto_select_virtual == 0 &&
			    p->pkg->name->ss.requirers == 0 &&
			    p->pkg->provider_priority == 0)
				continue;
680
681
			if (compare_providers(ss, p, &chosen) > 0)
				chosen = *p;
682
		}
683
	}
684

685
686
	pkg = chosen.pkg;
	if (pkg) {
687
		if (!pkg->ss.pkg_selectable || !pkg->ss.tag_ok) {
688
			/* Selecting broken or unallowed package */
689
			mark_error(ss, pkg, "broken package / tag not ok");
690
		}
691
		dbg_printf("selecting: " PKG_VER_FMT ", available: %d\n", PKG_VER_PRINTF(pkg), pkg->ss.pkg_selectable);
692

693
		assign_name(ss, pkg->name, APK_PROVIDER_FROM_PACKAGE(pkg));
694
695
696
697
698
		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);
699
700
701
	} else {
		dbg_printf("selecting: %s [unassigned]\n", name->name);
		assign_name(ss, name, provider_none);
702
703
704
705
		if (name->ss.requirers > 0) {
			dbg_printf("ERROR NO-PROVIDER: %s\n", name->name);
			ss->errors++;
		}
706
	}
707
708
}

709
static void record_change(struct apk_solver_state *ss, struct apk_package *opkg, struct apk_package *npkg)
710
{
711
712
713
	struct apk_changeset *changeset = ss->changeset;
	struct apk_change *change;

714
	change = apk_change_array_add(&changeset->changes);
715
716
717
	*change = (struct apk_change) {
		.old_pkg = opkg,
		.old_repository_tag = opkg ? opkg->ipkg->repository_tag : 0,
718
719
720
		.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,
721
	};
722
	if (npkg == NULL)
723
		changeset->num_remove++;
724
	else if (opkg == NULL)
725
		changeset->num_install++;
726
	else if (npkg != opkg || change->reinstall || change->new_repository_tag != change->old_repository_tag)
727
		changeset->num_adjust++;
728
}
729

730
731
732
733
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);

734
static void cset_track_deps_added(struct apk_package *pkg)
735
736
737
{
	struct apk_dependency *d;

738
739
740
741
742
	foreach_array_item(d, pkg->depends) {
		if (d->conflict || !d->name->ss.installed_name)
			continue;
		d->name->ss.installed_name->ss.requirers++;
	}
743
744
745
746
747
748
749
750
}

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) {
751
		if (d->conflict || !d->name->ss.installed_name)
752
			continue;
753
		if (--d->name->ss.installed_name->ss.requirers > 0)
754
			continue;
755
		pkg0 = d->name->ss.installed_pkg;
756
757
758
759
760
761
762
		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)
{
763
764
765
766
767
768
	/* 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)
769
		cset_gen_name_remove(ss, pkg);
770
771
}

772
static void cset_check_install_by_iif(struct apk_solver_state *ss, struct apk_name *name)
773
{
774
	struct apk_package *pkg = name->ss.chosen.pkg;
775
	struct apk_dependency *dep0;
776

777
	if (pkg == NULL || !name->ss.seen || name->ss.in_changeset)
778
779
		return;

780
	foreach_array_item(dep0, pkg->install_if) {
781
782
783
784
785
		struct apk_name *name0 = dep0->name;
		if (!name0->ss.in_changeset)
			return;
		if (!apk_dep_is_provided(dep0, &name0->ss.chosen))
			return;
786
	}
787
788
789
790
791
	cset_gen_name_change(ss, name);
}

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

795
	if (pkg == NULL || name->ss.in_changeset || name->ss.chosen.pkg != NULL)
796
797
798
799
800
801
802
803
804
805
806
807
808
809
		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;
810
	struct apk_package *pkg, *opkg;
811
812
	struct apk_dependency *d;

813
814
815
	if (name->ss.in_changeset) return;

	pkg = name->ss.chosen.pkg;
816
817
818
	if (pkg == NULL || pkg->name != name) {
		/* Original package dependency name was orphaned, emit a removal.
		 * See cset_gen_name_remove() for more details. */
819
820
821
		opkg = name->ss.installed_pkg;
		if (opkg) cset_gen_name_remove(ss, opkg);
		name->ss.in_changeset = 1;
822
823
824
825

		/* If a replacement is not provided, then we're done here. */
		if (pkg == NULL)
			return;
826
827
	}
	if (pkg->ss.in_changeset) return;
828
829
830

	pkg->ss.in_changeset = 1;
	pkg->name->ss.in_changeset = 1;
831
832
	foreach_array_item(d, pkg->provides)
		d->name->ss.in_changeset = 1;
833

834
	opkg = pkg->name->ss.installed_pkg;
835
836
837
838
839
840
841
842
	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);

843
	dbg_printf("Selecting: "PKG_VER_FMT"%s\n", PKG_VER_PRINTF(pkg), pkg->ss.pkg_selectable ? "" : " [NOT SELECTABLE]");
844
845
846
847
848
	record_change(ss, opkg, pkg);

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

849
	cset_track_deps_added(pkg);
850
851
852
853
	if (opkg)
		cset_track_deps_removed(ss, opkg);
}

854
855
856
857
858
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);
}

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

863
864
865
	if (pkg->ss.in_changeset ||
	    (name->ss.chosen.pkg != NULL &&
	     name->ss.chosen.pkg->name == name))
866
867
868
		return;

	name->ss.in_changeset = 1;
869
	pkg->ss.in_changeset = 1;
870
	apk_pkg_foreach_reverse_dependency(pkg, APK_FOREACH_INSTALLED|APK_DEP_SATISFIES, cset_gen_name_remove0, ss);
871
872
873
874
	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);
875
876
}

877
static void cset_gen_dep(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep)
878
{
879
	struct apk_name *name = dep->name;
880
	struct apk_package *pkg = name->ss.chosen.pkg;
881

882
	if (!apk_dep_is_provided(dep, &name->ss.chosen))
883
		mark_error(ss, ppkg, "unfulfilled dependency");
884

885
	cset_gen_name_change(ss, name);
886
887

	if (pkg && pkg->ss.error)
888
		mark_error(ss, ppkg, "propagation up");
889
}
890

891
892
893
894
895
896
897
898
899
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;
}

900
901
902
static void generate_changeset(struct apk_solver_state *ss, struct apk_dependency_array *world)
{
	struct apk_changeset *changeset = ss->changeset;
903
	struct apk_package *pkg;
904
	struct apk_installed_package *ipkg;
905
	struct apk_dependency *d;
906
</