solver.c 55.3 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
#include <unistd.h>
14
15
16
17
18
#include "apk_defines.h"
#include "apk_database.h"
#include "apk_package.h"
#include "apk_solver.h"

Timo Teräs's avatar
Timo Teräs committed
19
20
#include "apk_print.h"

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

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

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

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

enum {
	DECISION_ASSIGN = 0,
	DECISION_EXCLUDE
};

enum {
	BRANCH_NO,
	BRANCH_YES,
};

struct apk_decision {
74
75
	struct apk_name *name;
	struct apk_package *pkg;
76
77
#ifdef DEBUG_CHECKS
	struct apk_score saved_score;
78
	unsigned short saved_requirers;
79
80
81
82
83
#endif

	unsigned type : 1;
	unsigned branching_point : 1;
	unsigned topology_position : 1;
84
	unsigned found_solution : 1;
85
86
};

87
struct apk_package_state {
88
	/* set on startup */
89
	unsigned int topology_soft;
90
91
92
93
94
95
96
97
	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
98
99
	unsigned short conflicts;
	unsigned short unsatisfied;
100

101
	unsigned char preference;
102
	unsigned handle_install_if : 1;
103
	unsigned allowed : 1;
104
	unsigned locked : 1;
105
106

	unsigned solver_flags_maybe : 4;
107
108
};

109
110
#define CHOSEN_NONE	(struct apk_provider) { .pkg = NULL, .version = NULL }

111
112
struct apk_solver_state {
	struct apk_database *db;
113
	struct apk_decision *decisions;
114

115
	struct list_head unsolved_list_head;
116
117
118

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

122
	struct apk_solution_array *best_solution;
123
124

	struct apk_score score;
Timo Teräs's avatar
Timo Teräs committed
125
	struct apk_score best_score;
126
127

	unsigned solver_flags : 4;
128
	unsigned impossible_state : 1;
129
130
};

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

138
139
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);
140
141
142
143
144
145
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);
146

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

static void subscore(struct apk_score *a, struct apk_score *b)
{
160
161
	struct apk_score orig = *a;
	a->score -= b->score;
Timo Teräs's avatar
Timo Teräs committed
162
	ASSERT(a->unsatisfied <= orig.unsatisfied, "Unsatisfied underflow");
163
	ASSERT(a->non_preferred_actions <= orig.non_preferred_actions, "Preferred action underflow");
164
	ASSERT(a->non_preferred_pinnings <= orig.non_preferred_pinnings, "Preferred pinning overflow");
165
	ASSERT(a->preference <= orig.preference, "Preference underflow");
166
}
167
168
169
170
171
172
173
174
175
176
#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;
}
177
#endif
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193

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;
}
194

Timo Teräs's avatar
Timo Teräs committed
195
static struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
196
197
198
199
{
	return (struct apk_package_state*) pkg->state_ptr;
}

200
201
202
203
204
205
206
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);
}

207
static inline int pkg_available(struct apk_database *db, struct apk_package *pkg)
208
{
209
	/* virtual packages - only deps used; no real .apk */
210
211
	if (pkg->installed_size == 0)
		return TRUE;
212
	/* obviously present */
213
	if (pkg->in_cache || pkg->filename != NULL || (pkg->repos & db->local_repos))
214
215
216
		return TRUE;
	/* can download */
	if ((pkg->repos & ~db->bad_repos) && !(apk_flags & APK_NO_NETWORK))
217
218
219
220
		return TRUE;
	return FALSE;
}

221
static void foreach_dependency_pkg(
222
223
	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))
224
225
226
{
	int i, j;

227
228
229
	/* And sort the main dependencies */
	for (i = 0; i < depends->num; i++) {
		struct apk_dependency *dep = &depends->item[i];
230
231
		struct apk_name *name0 = dep->name;

232
233
		for (j = 0; j < name0->providers->num; j++) {
			struct apk_provider *p0 = &name0->providers->item[j];
234

235
			/* conflict depends on all to be not installed */
236
			if (!apk_dep_is_provided(dep, p0))
237
				continue;
238

239
			cb(ss, p0->pkg, parent_package);
240
241
		}
	}
242
}
243

244
245
static void foreach_rinstall_if_pkg(
	struct apk_solver_state *ss, struct apk_package *pkg,
246
	void (*cb)(struct apk_solver_state *ss, struct apk_package *rinstall_if, struct apk_package *parent_pkg))
247
248
249
250
251
252
253
254
255
{
	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);
256

257
258
259
260
261
		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];
262
263

				if (dep->name == name &&
264
				    apk_dep_is_provided(dep, p0))
265
266
					break;
			}
267
			if (k >= p0->pkg->install_if->num)
268
269
270
				continue;

			/* pkg depends (via install_if) on pkg0 */
271
			cb(ss, p0->pkg, pkg);
272
273
274
275
		}
	}
}

276
277
278
279
280
281
282
283
284
285
286
287
288
289
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;
}

290
static int get_topology_score(
291
292
293
294
		struct apk_solver_state *ss,
		struct apk_package *pkg,
		struct apk_score *_score)
{
295
	struct apk_name *name = pkg->name;
296
297
298
299
300
	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;
301
	int score_locked = TRUE, sticky_installed = FALSE;
302
303

	score = (struct apk_score) {
Timo Teräs's avatar
Timo Teräs committed
304
		.unsatisfied = ps->unsatisfied,
305
306
307
		.preference = ps->preference,
	};

308
	if (ss->solver_flags & APK_SOLVERF_AVAILABLE) {
Timo Teräs's avatar
Timo Teräs committed
309
		/* available preferred */
310
		if ((pkg->repos == 0) && name->ss.has_available_pkgs)
311
			score.non_preferred_actions++;
312
	} else if (ps->inherited_reinstall ||
313
		   (((name->ss.solver_flags_local|ss->solver_flags) & APK_SOLVERF_REINSTALL))) {
314
315
316
		/* reinstall requested, but not available */
		if (!pkg_available(ss->db, pkg))
			score.non_preferred_actions++;
317
	} else if (ps->inherited_upgrade ||
318
		   ((name->ss.solver_flags_local|ss->solver_flags) & APK_SOLVERF_UPGRADE)) {
Timo Teräs's avatar
Timo Teräs committed
319
		/* upgrading - score is just locked here */
320
	} else if ((ps->inherited_upgrade == 0) &&
321
		   ((name->ss.solver_flags_local|ss->solver_flags) & APK_SOLVERF_UPGRADE) == 0 &&
322
		   ((ps->solver_flags_maybe & APK_SOLVERF_UPGRADE) == 0 || (ps->locked))) {
323
		/* not upgrading: it is not preferred to change package */
324
		if (pkg->ipkg == NULL && name->ss.originally_installed)
325
			score.non_preferred_actions++;
326
327
		else
			sticky_installed = TRUE;
328
329
	} else {
		score_locked = FALSE;
330
331
332
	}

	repos = pkg->repos | (pkg->ipkg ? ss->db->repo_tags[pkg->ipkg->repository_tag].allowed_repos : 0);
333
	preferred_pinning = name->ss.preferred_pinning ?: APK_DEFAULT_PINNING_MASK;
334
335
336
	preferred_repos = get_pinning_mask_repos(ss->db, preferred_pinning);

	if (!(repos & preferred_repos))
337
		score.non_preferred_pinnings++;
338

339
340
	if (ps->locked || (ps->allowed_pinning | ps->allowed_pinning_maybe) == ps->allowed_pinning) {
		allowed_pinning = ps->allowed_pinning | preferred_pinning | APK_DEFAULT_PINNING_MASK;
341
		allowed_repos = get_pinning_mask_repos(ss->db, allowed_pinning);
342
343
344
		if (!(repos & allowed_repos)) {
			if (sticky_installed)
				score.non_preferred_actions++;
345
			score.non_preferred_pinnings += 16;
346
		}
347
348
	} else {
		score_locked = FALSE;
349
350
351
	}

	*_score = score;
352
	return score_locked;
353
354
355
}

static int compare_absolute_package_preference(
356
357
		struct apk_provider *pA,
		struct apk_provider *pB)
358
{
359
360
361
	struct apk_package *pkgA = pA->pkg;
	struct apk_package *pkgB = pB->pkg;

362
363
364
365
366
367
368
369
	/* 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 */
370
	switch (apk_version_compare_blob(*pA->version, *pB->version)) {
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
	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);
391
	struct apk_provider p = APK_PROVIDER_FROM_PACKAGE(pkg);
392
	int i, j;
393

394
395
396
	for (i = 0; i < name->providers->num; i++) {
		struct apk_provider *p0 = &name->providers->item[i];
		if (pkg == p0->pkg)
397
			continue;
398
		if (compare_absolute_package_preference(&p, p0) < 0)
399
400
			ps->preference++;
	}
401
402
403
404
405
406
407
408
409
410
411
412
	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++;
		}
	}
413
414
}

415
static void count_name(struct apk_solver_state *ss, struct apk_name *name)
416
{
417
	if (!name->ss.decision_counted) {
418
		ss->max_decisions++;
419
		name->ss.decision_counted = 1;
420
421
422
	}
}

423
424
425
static void sort_hard_dependencies(struct apk_solver_state *ss,
				   struct apk_package *pkg,
				   struct apk_package *parent_pkg)
426
{
427
	struct apk_name *name = pkg->name;
428
	struct apk_package_state *ps;
429
	int i;
430

431
	ps = pkg_to_ps_alloc(pkg);
432
	if (ps->topology_soft)
433
		return;
434
	pkg->topology_hard = -1;
435
	ps->topology_soft = -1;
436

437
	calculate_pkg_preference(pkg);
438

439
	/* Consider hard dependencies only */
440
441
	foreach_dependency_pkg(ss, pkg, pkg->depends, sort_hard_dependencies);
	foreach_dependency_pkg(ss, pkg, pkg->install_if, sort_hard_dependencies);
442

443
	ss->max_decisions++;
444
445
446
447
	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;
448
		count_name(ss, pkg->provides->item[i].name);
449
	}
450

451
	ps->topology_soft = pkg->topology_hard = ++ss->num_topology_positions;
452
	dbg_printf(PKG_VER_FMT ": topology_hard=%d\n",
453
		   PKG_VER_PRINTF(pkg), pkg->topology_hard);
454
455
}

456
457
458
static void sort_soft_dependencies(struct apk_solver_state *ss,
				   struct apk_package *pkg,
				   struct apk_package *parent_pkg)
459
460
{
	struct apk_package_state *ps;
461
	struct apk_package_state *parent_ps;
462

463
	sort_hard_dependencies(ss, pkg, parent_pkg);
464
465

	ps = pkg_to_ps(pkg);
466
	if (ps->topology_soft != pkg->topology_hard)
467
		return;
Timo Teräs's avatar
Timo Teräs committed
468
	ps->topology_soft = -1;
469

470
471
472
473
474
	/* 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;

475
476
	/* Soft reverse dependencies aka. install_if */
	foreach_rinstall_if_pkg(ss, pkg, sort_hard_dependencies);
477
	foreach_dependency_pkg(ss, pkg, pkg->depends, sort_soft_dependencies);
478
479
480
481
482

	/* 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);
483
484
}

485
486
487
static void update_allowed(struct apk_database *db, struct apk_package *pkg)
{
	struct apk_package_state *ps = pkg_to_ps(pkg);
488
489
490
491
	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))
492
493
494
495
496
		ps->allowed = 1;
	else
		ps->allowed = 0;
}

497
static void sort_name(struct apk_solver_state *ss, struct apk_name *name)
Timo Teräs's avatar
Timo Teräs committed
498
499
500
{
	int i, j;

501
502
	for (i = 0; i < name->providers->num; i++) {
		struct apk_package *pkg = name->providers->item[i].pkg;
503
504
505
		struct apk_package_state *ps = pkg_to_ps_alloc(pkg);
		unsigned short allowed_pinning;

506
507
		ps->allowed_pinning |= name->ss.preferred_pinning;
		ps->allowed_pinning_maybe |= name->ss.preferred_pinning;
Timo Teräs's avatar
Timo Teräs committed
508

509
510
511
512
513
514
		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
515
		}
516
		update_allowed(ss->db, pkg);
517
		sort_soft_dependencies(ss, name->providers->item[i].pkg, pkg);
Timo Teräs's avatar
Timo Teräs committed
518
	}
519
520
}

521
522
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))
523
{
524
	int i;
525
	for (i = 0; i < deps->num; i++)
526
		func(ss, &deps->item[i]);
527
528
}

529
static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg, struct apk_name *exclude)
530
531
532
533
534
{
	int i, missing = 0;

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

537
538
		if (name == exclude ||
		    !name->ss.locked || !apk_dep_is_provided(dep, &name->ss.chosen))
539
540
541
542
543
544
			missing++;
	}

	return missing;
}

545
546
547
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
548
		.unsatisfied = name->ss.requirers,
549
		.preference = name->providers->num,
550
551
552
	};
}

553
static void promote_name(struct apk_solver_state *ss, struct apk_name *name)
554
{
555
	if (name->ss.locked)
556
		return;
Timo Teräs's avatar
Timo Teräs committed
557

558
	/* queue for handling if needed */
559
560
	if (!list_hashed(&name->ss.unsolved_list))
		list_add_tail(&name->ss.unsolved_list, &ss->unsolved_list_head);
561

562
563
	/* update info, but no cached information flush is required, as
	 * minimum_penalty can only go up */
564
	name->ss.name_touched = 1;
565
}
566

567
568
static void demote_name(struct apk_solver_state *ss, struct apk_name *name)
{
569
	if (name->ss.locked)
570
		return;
571

572
	/* remove cached information */
573
	name->ss.chosen = CHOSEN_NONE;
574

575
	/* and remove list, or request refresh */
576
577
578
579
	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);
580
			dbg_printf("%s: not required\n", name->name);
581
		}
582
	} else {
583
584
		/* still needed, put back to list */
		promote_name(ss, name);
585
	}
586
587
}

588
static int inherit_package_state(struct apk_database *db, struct apk_package *to, struct apk_package *from)
589
{
590
	struct apk_name *fname = from->name;
591
592
593
594
	struct apk_package_state *tps = pkg_to_ps(to);
	struct apk_package_state *fps = pkg_to_ps(from);
	int i, changed = 0;

595
	if ((fname->ss.solver_flags_inheritable & APK_SOLVERF_REINSTALL) ||
596
597
598
599
	    fps->inherited_reinstall) {
		tps->inherited_reinstall++;
		changed = 1;
	}
600

601
	if ((fname->ss.solver_flags_inheritable & APK_SOLVERF_UPGRADE) ||
602
603
604
605
	    fps->inherited_upgrade) {
		tps->inherited_upgrade++;
		changed = 1;
	}
606

607
608
609
610
	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)))
611
				continue;
612
613
614
			allowed_pinning &= ~BIT(i);
			if (tps->inherited_pinning[i]++ == 0) {
				tps->allowed_pinning |= BIT(i);
615
				changed = 2;
616
			}
617
		}
618
619
		if (changed == 2)
			update_allowed(db, to);
620
	}
621
622

	return changed;
623
}
624

625
static void uninherit_package_state(struct apk_database *db, struct apk_package *to, struct apk_package *from)
626
{
627
	struct apk_name *fname = from->name;
628
629
	struct apk_package_state *tps = pkg_to_ps(to);
	struct apk_package_state *fps = pkg_to_ps(from);
630
	int i, changed = 0;
631

632
	if ((fname->ss.solver_flags_inheritable & APK_SOLVERF_REINSTALL) ||
633
634
	    fps->inherited_reinstall)
		tps->inherited_reinstall--;
635

636
	if ((fname->ss.solver_flags_inheritable & APK_SOLVERF_UPGRADE) ||
637
638
	    fps->inherited_upgrade)
		tps->inherited_upgrade--;
639

640
641
642
643
	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)))
644
				continue;
645
			allowed_pinning &= ~BIT(i);
646
			if (--tps->inherited_pinning[i] == 0) {
647
				tps->allowed_pinning &= ~BIT(i);
648
649
				changed = 2;
			}
650
		}
651
652
		if (changed == 2)
			update_allowed(db, to);
653
	}
654
655
}

656
static void trigger_install_if(struct apk_solver_state *ss,
657
658
			       struct apk_package *pkg,
			       struct apk_package *parent_pkg)
659
{
660
	struct apk_name *name = pkg->name;
661

662
663
664
665
666
667
668
669
	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);
670
671
672
}

static void untrigger_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, 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);
686
687
}

688
689
690
static inline void assign_name(
	struct apk_solver_state *ss, struct apk_name *name, struct apk_provider p)
{
691
	if (p.version == &apk_null_blob) {
Timo Teräs's avatar
Timo Teräs committed
692
693
694
695
		/* Assigning locked name with version is a problem;
		 * generally package providing same name twice */
		if (name->ss.locked && name->ss.chosen.version != &apk_null_blob)
			ss->impossible_state = 1;
696
	} else {
Timo Teräs's avatar
Timo Teräs committed
697
698
699
		/* Similar to above */
		if (name->ss.locked)
			ss->impossible_state = 1;
700
	}
701
702
703
704
705
	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);
706
707
708
709
710
	}
}

static inline void unassign_name(struct apk_solver_state *ss, struct apk_name *name)
{
Timo Teräs's avatar
Timo Teräs committed
711
	ASSERT(name->ss.locked, "Unassigning unlocked name %s", name->name);
712
713
714
715
	name->ss.locked--;
	if (name->ss.locked == 0) {
		name->ss.chosen = CHOSEN_NONE;
		name->ss.name_touched = 1;
716
717
		demote_name(ss, name);
	}
718
719
}

Timo Teräs's avatar
Timo Teräs committed
720
static solver_result_t apply_decision(struct apk_solver_state *ss,
721
				      struct apk_decision *d)
722
{
723
724
	struct apk_name *name = d->name;
	struct apk_package *pkg = d->pkg;
725
	struct apk_score score;
726
	int i;
727

728
	ss->impossible_state = 0;
729
	name->ss.name_touched = 1;
730
731
732
733
734
735
736
	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");

737
		for (i = 0; i < pkg->provides->num; i++)
738
			pkg->provides->item[i].name->ss.name_touched = 1;
739

740
		ps->locked = 1;
741
742
743
744
745
746
747
748
749

		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;
		}
750
751

		if (d->topology_position) {
752
			if (ps->topology_soft < ss->topology_position)
753
				ss->topology_position = ps->topology_soft;
754
			else
755
				ss->topology_position = pkg->topology_hard;
Timo Teräs's avatar
Timo Teräs committed
756
757
		}

758
		if (d->type == DECISION_ASSIGN) {
759
			get_topology_score(ss, pkg, &score);
760
761
762
			addscore(&ss->score, &score);

			ss->assigned_names++;
763
764
765
766
767
			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));
			}
768
769

			foreach_dependency(ss, pkg->depends, apply_constraint);
770
771
			if (ps->handle_install_if)
				foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
772
		}
773
	} else {
774
775
776
777
778
779
780
		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
781

782
			name->ss.chosen = CHOSEN_NONE;
Timo Teräs's avatar
Timo Teräs committed
783
			name->ss.locked++;
784
785
			list_del(&name->ss.unsolved_list);
			list_init(&name->ss.unsolved_list);
786
		} else {
787
			name->ss.none_excluded = 1;
788
789
790
		}
	}

791
792
793
794
795
796
797
	if (ss->impossible_state) {
		dbg_printf("%s: %s impossible constraints\n",
			name->name,
			(d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
		return SOLVERR_PRUNED;
	}

798
799
	if (cmpscore(&ss->score, &ss->best_score) >= 0) {
		dbg_printf("%s: %s penalty too big: "SCORE_FMT">="SCORE_FMT"\n",
800
801
802
803
			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
804
		return SOLVERR_PRUNED;
805
	}
Timo Teräs's avatar
Timo Teräs committed
806
807

	return SOLVERR_EXPAND;
808
809
810
}

static void undo_decision(struct apk_solver_state *ss,
811
			  struct apk_decision *d)
812
{
813
814
	struct apk_name *name = d->name;
	struct apk_package *pkg = d->pkg;
815
	struct apk_score score;
816
	int i;
817

818
	name->ss.name_touched = 1;
819

820
821
	if (pkg != NULL) {
		struct apk_package_state *ps = pkg_to_ps(pkg);
822

823
824
825
826
827
828
829
830
831
832
		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;
		}
833

834
		for (i = 0; i < pkg->provides->num; i++)
835
			pkg->provides->item[i].name->ss.name_touched = 1;
836

Timo Teräs's avatar
Timo Teräs committed
837
		if (d->type == DECISION_ASSIGN) {
838
839
			if (ps->handle_install_if)
				foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
Timo Teräs's avatar
Timo Teräs committed
840
			foreach_dependency(ss, pkg->depends, undo_constraint);
841

842
			get_topology_score(ss, pkg, &score);
843
			subscore(&ss->score, &score);
844

845
			unassign_name(ss, pkg->name);
846
847
848
849
850
			for (i = 0; i < pkg->provides->num; i++) {
				struct apk_dependency *p = &pkg->provides->item[i];
				unassign_name(ss, p->name);
			}
			ss->assigned_names--;
851
		}
852
		ps->locked = 0;
Timo Teräs's avatar
Timo Teräs committed
853
	} else {
854
855
856
857
858
859
860
		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);
Timo Teräs's avatar
Timo Teräs committed
861
			name->ss.locked--;
862
		} else {
863
			name->ss.none_excluded = 0;
864
		}
865

866
867
868
		/* Put back the name to unsolved list */
		promote_name(ss, name);
	}
869
870
}

871
872
873
874
875
876
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)
877
{
878
	struct apk_decision *d;
879

880
	ASSERT(ss->num_decisions <= ss->max_decisions,
881
	       "Decision tree overflow.");
882

883
884
885
886
	ss->num_decisions++;
	d = &ss->decisions[ss->num_decisions];

#ifdef DEBUG_CHECKS
Timo Teräs's avatar
Timo Teräs committed
887
888
	dbg_printf("Saving score ("SCORE_FMT") and requirers (%d) for %s\n",
		SCORE_PRINTF(&ss->score), name->ss.requirers, name->name);
889
	d->saved_score = ss->score;
890
	d->saved_requirers = name->ss.requirers;
891
892
893
894
#endif
	d->type = primary_decision;
	d->branching_point = branching_point;
	d->topology_position = topology_position;
895
	d->found_solution = 0;
896
897
	d->name = name;
	d->pkg = pkg;
898

899
	return apply_decision(ss, d);
900
901
902
903
}

static int next_branch(struct apk_solver_state *ss)
{
904