solver.c 30.6 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
			/* Virtual packages without provider_priority cannot be autoselected,
			 * unless there is only one provider */
676
677
678
			if (p->version == &apk_null_blob &&
			    p->pkg->name->auto_select_virtual == 0 &&
			    p->pkg->name->ss.requirers == 0 &&
679
			    (p->pkg->provider_priority == 0 && name->providers->num > 1))
680
				continue;
681
682
			if (compare_providers(ss, p, &chosen) > 0)
				chosen = *p;
683
		}
684
	}
685

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

886
	cset_gen_name_change(ss, name);
887
888

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

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

901
902
903
static void generate_changeset(struct apk_solver_state *ss, struct apk_dependency_array *world)
{
	struct apk_changeset *changeset = ss->changeset;
904
	struct apk_package *pkg;