solver.c 54.2 KB
Newer Older
1
2
3
/* solver.c - Alpine Package Keeper (APK)
 * A backtracking, forward checking dependency graph solver.
 *
4
 * Copyright (C) 2008-2012 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
14
15
16
17
#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
18
19
#include "apk_print.h"

20
//#define DEBUG_PRINT
21
#define DEBUG_CHECKS
22
23

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

30
31
#if defined(DEBUG_PRINT) || defined(DEBUG_CHECKS)
#define ASSERT(cond, fmt...) \
32
	if (!(cond)) { apk_error(fmt); *(char*)NULL = 0; }
33
34
35
#else
#define ASSERT(cond, fmt...)
#endif
Timo Teräs's avatar
Timo Teräs committed
36
37

struct apk_score {
38
39
40
41
	union {
		struct {
#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
			unsigned short preference;
42
			unsigned short non_preferred_pinnings;
43
			unsigned short non_preferred_actions;
Timo Teräs's avatar
Timo Teräs committed
44
			unsigned short unsatisfied;
45
#elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
Timo Teräs's avatar
Timo Teräs committed
46
			unsigned short unsatisfied;
47
			unsigned short non_preferred_actions;
48
			unsigned short non_preferred_pinnings;
49
50
51
52
53
54
55
			unsigned short preference;
#else
#error Unknown endianess.
#endif
		};
		uint64_t score;
	};
Timo Teräs's avatar
Timo Teräs committed
56
};
57

Timo Teräs's avatar
Timo Teräs committed
58
#define SCORE_MAX		(struct apk_score) { .unsatisfied = -1 }
59
#define SCORE_FMT		"{%d/%d/%d,%d}"
Timo Teräs's avatar
Timo Teräs committed
60
#define SCORE_PRINTF(s)		(s)->unsatisfied, (s)->non_preferred_actions, (s)->non_preferred_pinnings, (s)->preference
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

enum {
	DECISION_ASSIGN = 0,
	DECISION_EXCLUDE
};

enum {
	BRANCH_NO,
	BRANCH_YES,
};

struct apk_decision {
	union {
		struct apk_name *name;
		struct apk_package *pkg;
	};
#ifdef DEBUG_CHECKS
	struct apk_score saved_score;
79
	unsigned short saved_requirers;
80
81
82
83
84
85
#endif

	unsigned no_package : 1;
	unsigned type : 1;
	unsigned branching_point : 1;
	unsigned topology_position : 1;
86
	unsigned found_solution : 1;
87
88
};

89
struct apk_package_state {
90
	/* set on startup */
91
	unsigned int topology_soft;
92
93
94
95
96
97
98
99
	unsigned short allowed_pinning_maybe;

	/* dynamic */
	unsigned short allowed_pinning;
	unsigned short inherited_pinning[APK_MAX_TAGS];
	unsigned short inherited_upgrade;
	unsigned short inherited_reinstall;

Timo Teräs's avatar
Timo Teräs committed
100
101
	unsigned short conflicts;
	unsigned short unsatisfied;
102

103
	unsigned char preference;
104
	unsigned handle_install_if : 1;
105
	unsigned allowed : 1;
106
	unsigned locked : 1;
107
108

	unsigned solver_flags_maybe : 4;
109
110
};

111
112
#define CHOSEN_NONE	(struct apk_provider) { .pkg = NULL, .version = NULL }

113
114
struct apk_solver_state {
	struct apk_database *db;
115
	struct apk_decision *decisions;
116

117
	struct list_head unsolved_list_head;
118
119
120

	unsigned int num_topology_positions;
	unsigned int num_decisions, max_decisions;
121
122
	unsigned int topology_position;
	unsigned int assigned_names;
Timo Teräs's avatar
Timo Teräs committed
123

124
	struct apk_solution_array *best_solution;
125
126

	struct apk_score score;
Timo Teräs's avatar
Timo Teräs committed
127
	struct apk_score best_score;
128
129

	unsigned solver_flags : 4;
130
	unsigned impossible_state : 1;
131
132
};

Timo Teräs's avatar
Timo Teräs committed
133
134
135
136
137
138
139
typedef enum {
	SOLVERR_SOLUTION = 0,
	SOLVERR_PRUNED,
	SOLVERR_EXPAND,
	SOLVERR_STOP,
} solver_result_t;

140
141
static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep);
static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *dep);
142
143
144
145
146
147
static solver_result_t push_decision(struct apk_solver_state *ss,
				     struct apk_name *name,
				     struct apk_package *pkg,
				     int primary_decision,
				     int branching_point,
				     int topology_position);
148

149
#ifdef DEBUG_CHECKS
150
151
static void addscore(struct apk_score *a, struct apk_score *b)
{
152
153
	struct apk_score orig = *a;
	a->score += b->score;
Timo Teräs's avatar
Timo Teräs committed
154
	ASSERT(a->unsatisfied >= orig.unsatisfied, "Unsatisfied overflow");
155
	ASSERT(a->non_preferred_actions >= orig.non_preferred_actions, "Preferred action overflow");
156
	ASSERT(a->non_preferred_pinnings >= orig.non_preferred_pinnings, "Preferred pinning overflow");
157
	ASSERT(a->preference >= orig.preference, "Preference overflow");
158
159
160
161
}

static void subscore(struct apk_score *a, struct apk_score *b)
{
162
163
	struct apk_score orig = *a;
	a->score -= b->score;
Timo Teräs's avatar
Timo Teräs committed
164
	ASSERT(a->unsatisfied <= orig.unsatisfied, "Unsatisfied underflow");
165
	ASSERT(a->non_preferred_actions <= orig.non_preferred_actions, "Preferred action underflow");
166
	ASSERT(a->non_preferred_pinnings <= orig.non_preferred_pinnings, "Preferred pinning overflow");
167
	ASSERT(a->preference <= orig.preference, "Preference underflow");
168
}
169
170
171
172
173
174
175
176
177
178
#else
static void addscore(struct apk_score *a, struct apk_score *b)
{
	a->score += b->score;
}

static void subscore(struct apk_score *a, struct apk_score *b)
{
	a->score -= b->score;
}
179
#endif
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195

static inline int cmpscore(struct apk_score *a, struct apk_score *b)
{
	if (a->score < b->score) return -1;
	if (a->score > b->score) return 1;
	return 0;
}

static inline int cmpscore2(struct apk_score *a1, struct apk_score *a2, struct apk_score *b)
{
	struct apk_score a;
	a.score = a1->score + a2->score;
	if (a.score < b->score) return -1;
	if (a.score > b->score) return 1;
	return 0;
}
196
197
198
199
200
201
202
203
204
205
206
207
208

static struct apk_name *decision_to_name(struct apk_decision *d)
{
	if (d->no_package)
		return d->name;
	return d->pkg->name;
}

static struct apk_package *decision_to_pkg(struct apk_decision *d)
{
	if (d->no_package)
		return NULL;
	return d->pkg;
209
210
}

Timo Teräs's avatar
Timo Teräs committed
211
static struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
212
213
214
215
{
	return (struct apk_package_state*) pkg->state_ptr;
}

216
217
218
219
220
221
222
static struct apk_package_state *pkg_to_ps_alloc(struct apk_package *pkg)
{
	if (pkg->state_ptr == NULL)
		pkg->state_ptr = calloc(1, sizeof(struct apk_package_state));
	return pkg_to_ps(pkg);
}

223
static inline int pkg_available(struct apk_database *db, struct apk_package *pkg)
224
{
225
	/* virtual packages - only deps used; no real .apk */
226
227
	if (pkg->installed_size == 0)
		return TRUE;
228
	/* obviously present */
229
	if (pkg->in_cache || pkg->filename != NULL || (pkg->repos & db->local_repos))
230
231
232
		return TRUE;
	/* can download */
	if ((pkg->repos & ~db->bad_repos) && !(apk_flags & APK_NO_NETWORK))
233
234
235
236
		return TRUE;
	return FALSE;
}

237
static void foreach_dependency_pkg(
238
239
	struct apk_solver_state *ss, struct apk_package *parent_package, struct apk_dependency_array *depends,
	void (*cb)(struct apk_solver_state *ss, struct apk_package *dependency, struct apk_package *parent_package))
240
241
242
{
	int i, j;

243
244
245
	/* And sort the main dependencies */
	for (i = 0; i < depends->num; i++) {
		struct apk_dependency *dep = &depends->item[i];
246
247
		struct apk_name *name0 = dep->name;

248
249
		for (j = 0; j < name0->providers->num; j++) {
			struct apk_provider *p0 = &name0->providers->item[j];
250

251
			/* conflict depends on all to be not installed */
252
			if (!apk_dep_is_provided(dep, p0))
253
				continue;
254

255
			cb(ss, p0->pkg, parent_package);
256
257
		}
	}
258
}
259

260
261
static void foreach_rinstall_if_pkg(
	struct apk_solver_state *ss, struct apk_package *pkg,
262
	void (*cb)(struct apk_solver_state *ss, struct apk_package *rinstall_if, struct apk_package *parent_pkg))
263
264
265
266
267
268
269
270
271
{
	struct apk_name *name = pkg->name;
	int i, j, k;

	for (i = 0; i < pkg->name->rinstall_if->num; i++) {
		struct apk_name *name0 = pkg->name->rinstall_if->item[i];

		dbg_printf(PKG_VER_FMT ": rinstall_if %s\n",
			   PKG_VER_PRINTF(pkg), name0->name);
272

273
274
275
276
277
		for (j = 0; j < name0->providers->num; j++) {
			struct apk_provider *p0 = &name0->providers->item[j];

			for (k = 0; k < p0->pkg->install_if->num; k++) {
				struct apk_dependency *dep = &p0->pkg->install_if->item[k];
278
279

				if (dep->name == name &&
280
				    apk_dep_is_provided(dep, p0))
281
282
					break;
			}
283
			if (k >= p0->pkg->install_if->num)
284
285
286
				continue;

			/* pkg depends (via install_if) on pkg0 */
287
			cb(ss, p0->pkg, pkg);
288
289
290
291
		}
	}
}

292
293
294
295
296
297
298
299
300
301
302
303
304
305
static unsigned int get_pinning_mask_repos(struct apk_database *db, unsigned short pinning_mask)
{
	unsigned int repository_mask = 0;
	int i;

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

306
static int get_topology_score(
307
308
309
310
		struct apk_solver_state *ss,
		struct apk_package *pkg,
		struct apk_score *_score)
{
311
	struct apk_name *name = pkg->name;
312
313
314
315
316
	struct apk_package_state *ps = pkg_to_ps(pkg);
	struct apk_score score;
	unsigned int repos;
	unsigned short preferred_pinning, allowed_pinning;
	unsigned int preferred_repos, allowed_repos;
317
	int score_locked = TRUE, sticky_installed = FALSE;
318
319

	score = (struct apk_score) {
Timo Teräs's avatar
Timo Teräs committed
320
		.unsatisfied = ps->unsatisfied,
321
322
323
		.preference = ps->preference,
	};

324
	if (ss->solver_flags & APK_SOLVERF_AVAILABLE) {
Timo Teräs's avatar
Timo Teräs committed
325
		/* available preferred */
326
		if ((pkg->repos == 0) && name->ss.has_available_pkgs)
327
			score.non_preferred_actions++;
328
	} else if (ps->inherited_reinstall ||
329
		   (((name->ss.solver_flags_local|ss->solver_flags) & APK_SOLVERF_REINSTALL))) {
330
331
332
		/* reinstall requested, but not available */
		if (!pkg_available(ss->db, pkg))
			score.non_preferred_actions++;
333
	} else if (ps->inherited_upgrade ||
334
		   ((name->ss.solver_flags_local|ss->solver_flags) & APK_SOLVERF_UPGRADE)) {
Timo Teräs's avatar
Timo Teräs committed
335
		/* upgrading - score is just locked here */
336
	} else if ((ps->inherited_upgrade == 0) &&
337
		   ((name->ss.solver_flags_local|ss->solver_flags) & APK_SOLVERF_UPGRADE) == 0 &&
338
		   ((ps->solver_flags_maybe & APK_SOLVERF_UPGRADE) == 0 || (ps->locked))) {
339
		/* not upgrading: it is not preferred to change package */
340
		if (pkg->ipkg == NULL && name->ss.originally_installed)
341
			score.non_preferred_actions++;
342
343
		else
			sticky_installed = TRUE;
344
345
	} else {
		score_locked = FALSE;
346
347
348
	}

	repos = pkg->repos | (pkg->ipkg ? ss->db->repo_tags[pkg->ipkg->repository_tag].allowed_repos : 0);
349
	preferred_pinning = name->ss.preferred_pinning ?: APK_DEFAULT_PINNING_MASK;
350
351
352
	preferred_repos = get_pinning_mask_repos(ss->db, preferred_pinning);

	if (!(repos & preferred_repos))
353
		score.non_preferred_pinnings++;
354

355
356
	if (ps->locked || (ps->allowed_pinning | ps->allowed_pinning_maybe) == ps->allowed_pinning) {
		allowed_pinning = ps->allowed_pinning | preferred_pinning | APK_DEFAULT_PINNING_MASK;
357
		allowed_repos = get_pinning_mask_repos(ss->db, allowed_pinning);
358
359
360
		if (!(repos & allowed_repos)) {
			if (sticky_installed)
				score.non_preferred_actions++;
361
			score.non_preferred_pinnings += 16;
362
		}
363
364
	} else {
		score_locked = FALSE;
365
366
367
	}

	*_score = score;
368
	return score_locked;
369
370
371
}

static int compare_absolute_package_preference(
372
373
		struct apk_provider *pA,
		struct apk_provider *pB)
374
{
375
376
377
	struct apk_package *pkgA = pA->pkg;
	struct apk_package *pkgB = pB->pkg;

378
379
380
381
382
383
384
385
	/* specified on command line directly */
	if (pkgA->filename && !pkgB->filename)
		return 1;
	if (pkgB->filename && !pkgA->filename)
		return -1;

	/* upgrading, or neither of the package is installed, so
	 * we just fall back comparing to versions */
386
	switch (apk_version_compare_blob(*pA->version, *pB->version)) {
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
	case APK_VERSION_GREATER:
		return 1;
	case APK_VERSION_LESS:
		return -1;
	}

	/* prefer the installed package */
	if (pkgA->ipkg != NULL && pkgB->ipkg == NULL)
		return 1;
	if (pkgB->ipkg != NULL && pkgA->ipkg == NULL)
		return -1;

	/* prefer the one with lowest available repository */
	return ffsl(pkgB->repos) - ffsl(pkgA->repos);
}

static void calculate_pkg_preference(struct apk_package *pkg)
{
	struct apk_name *name = pkg->name;
	struct apk_package_state *ps = pkg_to_ps(pkg);
407
	struct apk_provider p = APK_PROVIDER_FROM_PACKAGE(pkg);
408
	int i, j;
409

410
411
412
	for (i = 0; i < name->providers->num; i++) {
		struct apk_provider *p0 = &name->providers->item[i];
		if (pkg == p0->pkg)
413
			continue;
414
		if (compare_absolute_package_preference(&p, p0) < 0)
415
416
			ps->preference++;
	}
417
418
419
420
421
422
423
424
425
426
427
428
	for (i = 0; i < pkg->provides->num; i++) {
		struct apk_dependency *d0 = &pkg->provides->item[i];
		if (d0->version == &apk_null_blob)
			continue;
		for (j = 0; j < d0->name->providers->num; j++) {
			struct apk_provider *p0 = &d0->name->providers->item[j];
			if (pkg == p0->pkg)
				continue;
			if (compare_absolute_package_preference(&p, p0) < 0)
				ps->preference++;
		}
	}
429
430
}

431
static void count_name(struct apk_solver_state *ss, struct apk_name *name)
432
{
433
	if (!name->ss.decision_counted) {
434
		ss->max_decisions++;
435
		name->ss.decision_counted = 1;
436
437
438
	}
}

439
440
441
static void sort_hard_dependencies(struct apk_solver_state *ss,
				   struct apk_package *pkg,
				   struct apk_package *parent_pkg)
442
{
443
	struct apk_name *name = pkg->name;
444
	struct apk_package_state *ps;
445
	int i;
446

447
	ps = pkg_to_ps_alloc(pkg);
448
	if (ps->topology_soft)
449
		return;
450
	pkg->topology_hard = -1;
451
	ps->topology_soft = -1;
452

453
	calculate_pkg_preference(pkg);
454

455
	/* Consider hard dependencies only */
456
457
	foreach_dependency_pkg(ss, pkg, pkg->depends, sort_hard_dependencies);
	foreach_dependency_pkg(ss, pkg, pkg->install_if, sort_hard_dependencies);
458

459
	ss->max_decisions++;
460
461
462
463
	name->ss.has_available_pkgs = 1;
	count_name(ss, name);
	for (i = 0; i < pkg->provides->num; i++) {
		pkg->provides->item[i].name->ss.has_available_pkgs = 1;
464
		count_name(ss, pkg->provides->item[i].name);
465
	}
466

467
	ps->topology_soft = pkg->topology_hard = ++ss->num_topology_positions;
468
	dbg_printf(PKG_VER_FMT ": topology_hard=%d\n",
469
		   PKG_VER_PRINTF(pkg), pkg->topology_hard);
470
471
}

472
473
474
static void sort_soft_dependencies(struct apk_solver_state *ss,
				   struct apk_package *pkg,
				   struct apk_package *parent_pkg)
475
476
{
	struct apk_package_state *ps;
477
	struct apk_package_state *parent_ps;
478

479
	sort_hard_dependencies(ss, pkg, parent_pkg);
480
481

	ps = pkg_to_ps(pkg);
482
	if (ps->topology_soft != pkg->topology_hard)
483
		return;
Timo Teräs's avatar
Timo Teräs committed
484
	ps->topology_soft = -1;
485

486
487
488
489
490
	/* Update state */
	parent_ps = pkg_to_ps(parent_pkg);
	ps->allowed_pinning_maybe |= parent_ps->allowed_pinning_maybe;
	ps->solver_flags_maybe |= parent_ps->solver_flags_maybe;

491
492
	/* Soft reverse dependencies aka. install_if */
	foreach_rinstall_if_pkg(ss, pkg, sort_hard_dependencies);
493
	foreach_dependency_pkg(ss, pkg, pkg->depends, sort_soft_dependencies);
494
495
496
497
498

	/* Assign a topology sorting order */
	ps->topology_soft = ++ss->num_topology_positions;
	dbg_printf(PKG_VER_FMT ": topology_soft=%d\n",
		   PKG_VER_PRINTF(pkg), ps->topology_soft);
499
500
}

501
502
503
static void update_allowed(struct apk_database *db, struct apk_package *pkg)
{
	struct apk_package_state *ps = pkg_to_ps(pkg);
504
505
506
507
	unsigned int repos;

	repos = pkg->repos | (pkg->ipkg ? db->repo_tags[pkg->ipkg->repository_tag].allowed_repos : 0);
	if (repos & get_pinning_mask_repos(db, ps->allowed_pinning | APK_DEFAULT_PINNING_MASK))
508
509
510
511
512
		ps->allowed = 1;
	else
		ps->allowed = 0;
}

513
static void sort_name(struct apk_solver_state *ss, struct apk_name *name)
Timo Teräs's avatar
Timo Teräs committed
514
515
516
{
	int i, j;

517
518
	for (i = 0; i < name->providers->num; i++) {
		struct apk_package *pkg = name->providers->item[i].pkg;
519
520
521
		struct apk_package_state *ps = pkg_to_ps_alloc(pkg);
		unsigned short allowed_pinning;

522
523
		ps->allowed_pinning |= name->ss.preferred_pinning;
		ps->allowed_pinning_maybe |= name->ss.preferred_pinning;
Timo Teräs's avatar
Timo Teräs committed
524

525
526
527
528
529
530
		allowed_pinning = ps->allowed_pinning;
		for (j = 0; allowed_pinning; j++) {
			if (!(allowed_pinning & BIT(j)))
				continue;
			allowed_pinning &= ~BIT(j);
			ps->inherited_pinning[j]++;
Timo Teräs's avatar
Timo Teräs committed
531
		}
532
		update_allowed(ss->db, pkg);
533
		sort_soft_dependencies(ss, name->providers->item[i].pkg, pkg);
Timo Teräs's avatar
Timo Teräs committed
534
	}
535
536
}

537
538
static void foreach_dependency(struct apk_solver_state *ss, struct apk_dependency_array *deps,
			       void (*func)(struct apk_solver_state *ss, struct apk_dependency *dep))
539
{
540
	int i;
541
	for (i = 0; i < deps->num; i++)
542
		func(ss, &deps->item[i]);
543
544
}

545
static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg, struct apk_name *exclude)
546
547
548
549
550
{
	int i, missing = 0;

	for (i = 0; i < pkg->install_if->num; i++) {
		struct apk_dependency *dep = &pkg->install_if->item[i];
551
		struct apk_name *name = dep->name;
552

553
554
		if (name == exclude ||
		    !name->ss.locked || !apk_dep_is_provided(dep, &name->ss.chosen))
555
556
557
558
559
560
			missing++;
	}

	return missing;
}

561
562
563
static void get_unassigned_score(struct apk_name *name, struct apk_score *score)
{
	*score = (struct apk_score){
Timo Teräs's avatar
Timo Teräs committed
564
		.unsatisfied = name->ss.requirers,
565
		.preference = name->providers->num,
566
567
568
	};
}

569
static void promote_name(struct apk_solver_state *ss, struct apk_name *name)
570
{
571
	if (name->ss.locked)
572
		return;
Timo Teräs's avatar
Timo Teräs committed
573

574
	/* queue for handling if needed */
575
576
	if (!list_hashed(&name->ss.unsolved_list))
		list_add_tail(&name->ss.unsolved_list, &ss->unsolved_list_head);
577

578
579
	/* update info, but no cached information flush is required, as
	 * minimum_penalty can only go up */
580
	name->ss.name_touched = 1;
581
}
582

583
584
static void demote_name(struct apk_solver_state *ss, struct apk_name *name)
{
585
	if (name->ss.locked)
586
		return;
587

588
	/* remove cached information */
589
	name->ss.chosen = CHOSEN_NONE;
590

591
	/* and remove list, or request refresh */
592
593
594
595
	if (name->ss.requirers == 0 && name->ss.install_ifs == 0) {
		if (list_hashed(&name->ss.unsolved_list)) {
			list_del(&name->ss.unsolved_list);
			list_init(&name->ss.unsolved_list);
596
			dbg_printf("%s: not required\n", name->name);
597
		}
598
	} else {
599
600
		/* still needed, put back to list */
		promote_name(ss, name);
601
	}
602
603
}

604
static int inherit_package_state(struct apk_database *db, struct apk_package *to, struct apk_package *from)
605
{
606
	struct apk_name *fname = from->name;
607
608
609
610
	struct apk_package_state *tps = pkg_to_ps(to);
	struct apk_package_state *fps = pkg_to_ps(from);
	int i, changed = 0;

611
	if ((fname->ss.solver_flags_inheritable & APK_SOLVERF_REINSTALL) ||
612
613
614
615
	    fps->inherited_reinstall) {
		tps->inherited_reinstall++;
		changed = 1;
	}
616

617
	if ((fname->ss.solver_flags_inheritable & APK_SOLVERF_UPGRADE) ||
618
619
620
621
	    fps->inherited_upgrade) {
		tps->inherited_upgrade++;
		changed = 1;
	}
622

623
624
625
626
	if (fps->allowed_pinning) {
		unsigned short allowed_pinning = fps->allowed_pinning;
		for (i = 0; allowed_pinning && i < db->num_repo_tags; i++) {
			if (!(allowed_pinning & BIT(i)))
627
				continue;
628
629
630
			allowed_pinning &= ~BIT(i);
			if (tps->inherited_pinning[i]++ == 0) {
				tps->allowed_pinning |= BIT(i);
631
				changed = 2;
632
			}
633
		}
634
635
		if (changed == 2)
			update_allowed(db, to);
636
	}
637
638

	return changed;
639
}
640

641
static void uninherit_package_state(struct apk_database *db, struct apk_package *to, struct apk_package *from)
642
{
643
	struct apk_name *fname = from->name;
644
645
	struct apk_package_state *tps = pkg_to_ps(to);
	struct apk_package_state *fps = pkg_to_ps(from);
646
	int i, changed = 0;
647

648
	if ((fname->ss.solver_flags_inheritable & APK_SOLVERF_REINSTALL) ||
649
650
	    fps->inherited_reinstall)
		tps->inherited_reinstall--;
651

652
	if ((fname->ss.solver_flags_inheritable & APK_SOLVERF_UPGRADE) ||
653
654
	    fps->inherited_upgrade)
		tps->inherited_upgrade--;
655

656
657
658
659
	if (fps->allowed_pinning) {
		unsigned short allowed_pinning = fps->allowed_pinning;
		for (i = 0; allowed_pinning && i < db->num_repo_tags; i++) {
			if (!(allowed_pinning & BIT(i)))
660
				continue;
661
			allowed_pinning &= ~BIT(i);
662
			if (--tps->inherited_pinning[i] == 0) {
663
				tps->allowed_pinning &= ~BIT(i);
664
665
				changed = 2;
			}
666
		}
667
668
		if (changed == 2)
			update_allowed(db, to);
669
	}
670
671
}

672
static void trigger_install_if(struct apk_solver_state *ss,
673
674
			       struct apk_package *pkg,
			       struct apk_package *parent_pkg)
675
{
676
	struct apk_name *name = pkg->name;
677

678
679
680
681
682
683
684
685
	if (install_if_missing(ss, pkg, NULL) != 0)
		return;

	dbg_printf("trigger_install_if: " PKG_VER_FMT " triggered\n",
		   PKG_VER_PRINTF(pkg));
	name->ss.install_ifs++;
	inherit_package_state(ss->db, pkg, parent_pkg);
	promote_name(ss, name);
686
687
688
}

static void untrigger_install_if(struct apk_solver_state *ss,
689
690
			         struct apk_package *pkg,
			         struct apk_package *parent_pkg)
691
{
692
	struct apk_name *name = pkg->name;
693

694
695
696
697
698
699
700
701
	if (install_if_missing(ss, pkg, parent_pkg->name) != 0)
		return;

	dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n",
		   PKG_VER_PRINTF(pkg));
	name->ss.install_ifs--;
	uninherit_package_state(ss->db, pkg, parent_pkg);
	demote_name(ss, name);
702
703
}

704
705
706
static inline void assign_name(
	struct apk_solver_state *ss, struct apk_name *name, struct apk_provider p)
{
707
	if (p.version == &apk_null_blob) {
708
		ASSERT(!name->ss.locked || name->ss.chosen.version == &apk_null_blob,
709
710
		       "Assigning locked name with version");
	} else {
711
		ASSERT(!name->ss.locked, "Assigning locked name");
712
	}
713
714
715
716
717
	name->ss.chosen = p;
	name->ss.locked++;
	if (list_hashed(&name->ss.unsolved_list)) {
		list_del(&name->ss.unsolved_list);
		list_init(&name->ss.unsolved_list);
718
719
720
721
722
	}
}

static inline void unassign_name(struct apk_solver_state *ss, struct apk_name *name)
{
723
724
725
726
727
	ASSERT(name->ss.locked, "Unassigning unlocked name");
	name->ss.locked--;
	if (name->ss.locked == 0) {
		name->ss.chosen = CHOSEN_NONE;
		name->ss.name_touched = 1;
728
729
		demote_name(ss, name);
	}
730
731
}

Timo Teräs's avatar
Timo Teräs committed
732
static solver_result_t apply_decision(struct apk_solver_state *ss,
733
				      struct apk_decision *d)
734
{
735
736
737
	struct apk_name *name = decision_to_name(d);
	struct apk_package *pkg = decision_to_pkg(d);
	struct apk_score score;
738
	int i;
739

740
	ss->impossible_state = 0;
741
	name->ss.name_touched = 1;
742
743
744
745
746
747
748
	if (pkg != NULL) {
		struct apk_package_state *ps = pkg_to_ps(pkg);

		dbg_printf("-->apply_decision: " PKG_VER_FMT " %s\n",
			   PKG_VER_PRINTF(pkg),
			   (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");

749
		for (i = 0; i < pkg->provides->num; i++)
750
			pkg->provides->item[i].name->ss.name_touched = 1;
751

752
		ps->locked = 1;
753
754
755
756
757
758
759
760
761

		if (d->type == DECISION_ASSIGN &&
		    ps->topology_soft < ss->topology_position) {
			ps->handle_install_if = 1;
			dbg_printf("triggers due to " PKG_VER_FMT "\n",
				   PKG_VER_PRINTF(pkg));
		} else {
			ps->handle_install_if = 0;
		}
762
763

		if (d->topology_position) {
764
			if (ps->topology_soft < ss->topology_position)
765
				ss->topology_position = ps->topology_soft;
766
			else
767
				ss->topology_position = pkg->topology_hard;
Timo Teräs's avatar
Timo Teräs committed
768
769
		}

770
		if (d->type == DECISION_ASSIGN) {
771
			get_topology_score(ss, pkg, &score);
772
773
774
			addscore(&ss->score, &score);

			ss->assigned_names++;
775
776
777
778
779
			assign_name(ss, name, APK_PROVIDER_FROM_PACKAGE(pkg));
			for (i = 0; i < pkg->provides->num; i++) {
				struct apk_dependency *p = &pkg->provides->item[i];
				assign_name(ss, p->name, APK_PROVIDER_FROM_PROVIDES(pkg, p));
			}
780
781

			foreach_dependency(ss, pkg->depends, apply_constraint);
782
783
			if (ps->handle_install_if)
				foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
784
		}
785
	} else {
786
787
788
789
790
791
792
		dbg_printf("-->apply_decision: %s %s NOTHING\n",
			   name->name,
			   (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");

		if (d->type == DECISION_ASSIGN) {
			get_unassigned_score(name, &score);
			addscore(&ss->score, &score);
Timo Teräs's avatar
Timo Teräs committed
793

794
795
796
797
			name->ss.chosen = CHOSEN_NONE;
			name->ss.locked = 1;
			list_del(&name->ss.unsolved_list);
			list_init(&name->ss.unsolved_list);
798
		} else {
799
			name->ss.none_excluded = 1;
800
801
802
		}
	}

803
804
805
806
807
808
809
	if (ss->impossible_state) {
		dbg_printf("%s: %s impossible constraints\n",
			name->name,
			(d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
		return SOLVERR_PRUNED;
	}

810
811
	if (cmpscore(&ss->score, &ss->best_score) >= 0) {
		dbg_printf("%s: %s penalty too big: "SCORE_FMT">="SCORE_FMT"\n",
812
813
814
815
			name->name,
			(d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE",
			SCORE_PRINTF(&ss->score),
			SCORE_PRINTF(&ss->best_score));
Timo Teräs's avatar
Timo Teräs committed
816
		return SOLVERR_PRUNED;
817
	}
Timo Teräs's avatar
Timo Teräs committed
818
819

	return SOLVERR_EXPAND;
820
821
822
}

static void undo_decision(struct apk_solver_state *ss,
823
			  struct apk_decision *d)
824
{
825
826
827
	struct apk_name *name = decision_to_name(d);
	struct apk_package *pkg = decision_to_pkg(d);
	struct apk_score score;
828
	int i;
829

830
	name->ss.name_touched = 1;
831

832
833
	if (pkg != NULL) {
		struct apk_package_state *ps = pkg_to_ps(pkg);
834

835
836
837
838
839
840
841
842
843
844
		dbg_printf("-->undo_decision: " PKG_VER_FMT " %s\n",
			   PKG_VER_PRINTF(pkg),
			   (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");

		if (d->topology_position) {
			if (ps->handle_install_if)
				ss->topology_position = ps->topology_soft;
			else
				ss->topology_position = pkg->topology_hard;
		}
845

846
		for (i = 0; i < pkg->provides->num; i++)
847
			pkg->provides->item[i].name->ss.name_touched = 1;
848

849
		if (name->ss.locked) {
850
851
			if (ps->handle_install_if)
				foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
Timo Teräs's avatar
Timo Teräs committed
852
			foreach_dependency(ss, pkg->depends, undo_constraint);
853

854
			get_topology_score(ss, pkg, &score);
855
			subscore(&ss->score, &score);
856
857
858
859
860
861
862

			unassign_name(ss, name);
			for (i = 0; i < pkg->provides->num; i++) {
				struct apk_dependency *p = &pkg->provides->item[i];
				unassign_name(ss, p->name);
			}
			ss->assigned_names--;
863
		}
864
		ps->locked = 0;
Timo Teräs's avatar
Timo Teräs committed
865
	} else {
866
867
868
869
870
871
872
873
		dbg_printf("-->undo_decision: %s %s NOTHING\n",
			   name->name,
			   (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");

		if (d->type == DECISION_ASSIGN) {
			get_unassigned_score(name, &score);
			subscore(&ss->score, &score);
		} else {
874
			name->ss.none_excluded = 0;
875
		}
876

877
		/* Put back the name to unsolved list */
878
		name->ss.locked = 0;
879
880
		promote_name(ss, name);
	}
881
882
}

883
884
885
886
887
888
static solver_result_t push_decision(struct apk_solver_state *ss,
				     struct apk_name *name,
				     struct apk_package *pkg,
				     int primary_decision,
				     int branching_point,
				     int topology_position)
889
{
890
	struct apk_decision *d;
891

892
	ASSERT(ss->num_decisions <= ss->max_decisions,
893
	       "Decision tree overflow.");
894

895
896
897
898
899
	ss->num_decisions++;
	d = &ss->decisions[ss->num_decisions];

#ifdef DEBUG_CHECKS
	d->saved_score = ss->score;
900
	d->saved_requirers = name->ss.requirers;
901
902
903
904
#endif
	d->type = primary_decision;
	d->branching_point = branching_point;
	d->topology_position = topology_position;
905
	d->found_solution = 0;
906
907
908
	if (pkg == NULL) {
		d->name = name;
		d->no_package = 1;
909
	} else {
910
911
		d->pkg = pkg;
		d->no_package = 0;
912
	}
913

914
	return apply_decision(ss, d);
915
916
917
918
}

static int next_branch(struct apk_solver_state *ss)
{
919
920
	unsigned int backup_until = ss->num_decisions;

921
922
	while (ss->num_decisions > 0) {
		struct apk_decision *d = &ss->decisions[ss->num_decisions];
923
		struct apk_name *name = decision_to_name(d);
924