solver.c 57 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
#define SCORE_ZERO		(struct apk_score) { .unsatisfied = 0 }
Timo Teräs's avatar
Timo Teräs committed
39
#define SCORE_MAX		(struct apk_score) { .unsatisfied = -1 }
40
#define SCORE_FMT		"{%d/%d/%d,%d}"
Timo Teräs's avatar
Timo Teräs committed
41
#define SCORE_PRINTF(s)		(s)->unsatisfied, (s)->non_preferred_actions, (s)->non_preferred_pinnings, (s)->preference
42
43
44
45
46
47
48
49
50
51
52
53

enum {
	DECISION_ASSIGN = 0,
	DECISION_EXCLUDE
};

enum {
	BRANCH_NO,
	BRANCH_YES,
};

struct apk_decision {
54
	struct apk_name *name;
55
56
57
58
	union {
		struct apk_package *pkg;
		unsigned backup_until;
	};
59
60
#ifdef DEBUG_CHECKS
	struct apk_score saved_score;
61
	unsigned short saved_requirers;
62
#endif
63
	unsigned short requirers;
64
	unsigned type : 1;
65
	unsigned has_package : 1;
66
67
	unsigned branching_point : 1;
	unsigned topology_position : 1;
68
	unsigned found_solution : 1;
69
70
};

71
struct apk_package_state {
72
	/* set on startup */
73
	unsigned int topology_soft;
74
75
76
77
78
79
80
81
	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
82
83
	unsigned short conflicts;
	unsigned short unsatisfied;
84

85
	unsigned char preference;
86
	unsigned handle_install_if : 1;
87
	unsigned allowed : 1;
88
	unsigned locked : 1;
89
90

	unsigned solver_flags_maybe : 4;
91
92
};

93
94
#define CHOSEN_NONE	(struct apk_provider) { .pkg = NULL, .version = NULL }

95
96
struct apk_solver_state {
	struct apk_database *db;
97
	struct apk_decision *decisions;
98

99
	struct list_head unsolved_list_head;
100
101
102

	unsigned int num_topology_positions;
	unsigned int num_decisions, max_decisions;
103
104
	unsigned int topology_position;
	unsigned int assigned_names;
Timo Teräs's avatar
Timo Teräs committed
105

106
	struct apk_solution_array *best_solution;
107
108

	struct apk_score score;
Timo Teräs's avatar
Timo Teräs committed
109
	struct apk_score best_score;
110
	struct apk_score minimum_penalty;
111
112

	unsigned solver_flags : 4;
113
	unsigned impossible_state : 1;
114
115
};

Timo Teräs's avatar
Timo Teräs committed
116
117
118
119
120
121
122
typedef enum {
	SOLVERR_SOLUTION = 0,
	SOLVERR_PRUNED,
	SOLVERR_EXPAND,
	SOLVERR_STOP,
} solver_result_t;

123
124
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);
125
126
127
128
129
130
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);
131

132
133
static void addscore(struct apk_score *a, struct apk_score *b)
{
134
	struct apk_score orig = *a;
135
136
137
138
139
140

	a->unsatisfied			+= b->unsatisfied;
	a->non_preferred_actions	+= b->non_preferred_actions;
	a->non_preferred_pinnings	+= b->non_preferred_pinnings;
	a->preference			+= b->preference;

Timo Teräs's avatar
Timo Teräs committed
141
	ASSERT(a->unsatisfied >= orig.unsatisfied, "Unsatisfied overflow");
142
	ASSERT(a->non_preferred_actions >= orig.non_preferred_actions, "Preferred action overflow");
143
	ASSERT(a->non_preferred_pinnings >= orig.non_preferred_pinnings, "Preferred pinning overflow");
144
	ASSERT(a->preference >= orig.preference, "Preference overflow");
145
146
147
148
}

static void subscore(struct apk_score *a, struct apk_score *b)
{
149
	struct apk_score orig = *a;
150
151
152
153
154
155

	a->unsatisfied			-= b->unsatisfied;
	a->non_preferred_actions	-= b->non_preferred_actions;
	a->non_preferred_pinnings	-= b->non_preferred_pinnings;
	a->preference			-= b->preference;

Timo Teräs's avatar
Timo Teräs committed
156
	ASSERT(a->unsatisfied <= orig.unsatisfied, "Unsatisfied underflow");
157
	ASSERT(a->non_preferred_actions <= orig.non_preferred_actions, "Preferred action underflow");
158
	ASSERT(a->non_preferred_pinnings <= orig.non_preferred_pinnings, "Preferred pinning overflow");
159
	ASSERT(a->preference <= orig.preference, "Preference underflow");
160
}
161
162
163

static inline int cmpscore(struct apk_score *a, struct apk_score *b)
{
164
165
166
167
168
169
170
171
	if (a->unsatisfied != b->unsatisfied)
		return a->unsatisfied < b->unsatisfied ? -1 : 1;
	if (a->non_preferred_actions != b->non_preferred_actions)
		return a->non_preferred_actions < b->non_preferred_actions ? -1 : 1;
	if (a->non_preferred_pinnings != b->non_preferred_pinnings)
		return a->non_preferred_pinnings < b->non_preferred_pinnings ? -1 : 1;
	if (a->preference != b->preference)
		return a->preference < b->preference ? -1 : 1;
172
173
174
175
176
	return 0;
}

static inline int cmpscore2(struct apk_score *a1, struct apk_score *a2, struct apk_score *b)
{
177
178
179
	struct apk_score a = *a1;
	addscore(&a, a2);
	return cmpscore(&a, b);
180
}
181

Timo Teräs's avatar
Timo Teräs committed
182
static struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
183
184
185
186
{
	return (struct apk_package_state*) pkg->state_ptr;
}

187
188
189
190
191
192
193
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);
}

194
195
196
197
198
static inline struct apk_package *decision_to_pkg(struct apk_decision *d)
{
	return d->has_package ? d->pkg : NULL;
}

199
static inline int pkg_available(struct apk_database *db, struct apk_package *pkg)
200
{
201
	if (pkg->repos & db->available_repos)
202
203
204
205
		return TRUE;
	return FALSE;
}

206
static void foreach_dependency_pkg(
207
208
	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))
209
210
211
{
	int i, j;

212
213
214
	/* And sort the main dependencies */
	for (i = 0; i < depends->num; i++) {
		struct apk_dependency *dep = &depends->item[i];
215
216
		struct apk_name *name0 = dep->name;

217
218
		for (j = 0; j < name0->providers->num; j++) {
			struct apk_provider *p0 = &name0->providers->item[j];
219

220
			/* conflict depends on all to be not installed */
221
			if (!apk_dep_is_provided(dep, p0))
222
				continue;
223

224
			cb(ss, p0->pkg, parent_package);
225
226
		}
	}
227
}
228

229
230
static void foreach_rinstall_if_pkg(
	struct apk_solver_state *ss, struct apk_package *pkg,
231
	void (*cb)(struct apk_solver_state *ss, struct apk_package *rinstall_if, struct apk_package *parent_pkg))
232
233
234
235
236
237
238
239
240
{
	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);
241

242
243
244
245
246
		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];
247
248

				if (dep->name == name &&
249
				    apk_dep_is_provided(dep, p0))
250
251
					break;
			}
252
			if (k >= p0->pkg->install_if->num)
253
254
255
				continue;

			/* pkg depends (via install_if) on pkg0 */
256
			cb(ss, p0->pkg, pkg);
257
258
259
260
		}
	}
}

261
262
263
264
265
266
267
268
269
270
271
272
273
274
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;
}

275
static int get_topology_score(
276
		struct apk_solver_state *ss,
277
		struct apk_name *name,
278
279
280
281
282
283
284
285
		struct apk_package *pkg,
		struct apk_score *_score)
{
	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;
286
	int score_locked = TRUE, sticky_installed = FALSE;
287
288

	score = (struct apk_score) {
Timo Teräs's avatar
Timo Teräs committed
289
		.unsatisfied = ps->unsatisfied,
290
291
292
		.preference = ps->preference,
	};

293
	if (ss->solver_flags & APK_SOLVERF_AVAILABLE) {
Timo Teräs's avatar
Timo Teräs committed
294
		/* available preferred */
295
		if ((pkg->repos == 0) && name->ss.has_available_pkgs)
296
			score.non_preferred_actions++;
297
	} else if (ps->inherited_reinstall ||
298
		   (((name->ss.solver_flags_local|ss->solver_flags) & APK_SOLVERF_REINSTALL))) {
299
300
301
		/* reinstall requested, but not available */
		if (!pkg_available(ss->db, pkg))
			score.non_preferred_actions++;
302
	} else if (ps->inherited_upgrade ||
303
		   ((name->ss.solver_flags_local|ss->solver_flags) & APK_SOLVERF_UPGRADE)) {
Timo Teräs's avatar
Timo Teräs committed
304
		/* upgrading - score is just locked here */
305
	} else if ((ps->inherited_upgrade == 0) &&
306
		   ((name->ss.solver_flags_local|ss->solver_flags) & APK_SOLVERF_UPGRADE) == 0 &&
307
		   ((ps->solver_flags_maybe & APK_SOLVERF_UPGRADE) == 0 || (ps->locked))) {
308
		/* not upgrading: it is not preferred to change package */
309
		if (pkg->ipkg == NULL && name->ss.originally_installed)
310
			score.non_preferred_actions++;
311
312
		else
			sticky_installed = TRUE;
313
314
	} else {
		score_locked = FALSE;
315
316
317
	}

	repos = pkg->repos | (pkg->ipkg ? ss->db->repo_tags[pkg->ipkg->repository_tag].allowed_repos : 0);
318
	preferred_pinning = name->ss.preferred_pinning ?: APK_DEFAULT_PINNING_MASK;
319
320
321
	preferred_repos = get_pinning_mask_repos(ss->db, preferred_pinning);

	if (!(repos & preferred_repos))
322
		score.non_preferred_pinnings++;
323

324
325
	if (ps->locked || (ps->allowed_pinning | ps->allowed_pinning_maybe) == ps->allowed_pinning) {
		allowed_pinning = ps->allowed_pinning | preferred_pinning | APK_DEFAULT_PINNING_MASK;
326
		allowed_repos = get_pinning_mask_repos(ss->db, allowed_pinning);
327
328
329
		if (!(repos & allowed_repos)) {
			if (sticky_installed)
				score.non_preferred_actions++;
330
			score.non_preferred_pinnings += 16;
331
		}
332
333
	} else {
		score_locked = FALSE;
334
335
336
	}

	*_score = score;
337
	return score_locked;
338
339
340
}

static int compare_absolute_package_preference(
341
342
		struct apk_provider *pA,
		struct apk_provider *pB)
343
{
344
345
346
	struct apk_package *pkgA = pA->pkg;
	struct apk_package *pkgB = pB->pkg;

347
348
349
350
351
352
353
354
	/* 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 */
355
	switch (apk_version_compare_blob(*pA->version, *pB->version)) {
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
	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);
376
	struct apk_provider p = APK_PROVIDER_FROM_PACKAGE(pkg);
377
	int i, j;
378

379
380
381
	for (i = 0; i < name->providers->num; i++) {
		struct apk_provider *p0 = &name->providers->item[i];
		if (pkg == p0->pkg)
382
			continue;
383
		if (compare_absolute_package_preference(&p, p0) < 0)
384
385
			ps->preference++;
	}
386
387
388
389
390
391
	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];
392
			if (name == p0->pkg->name)
393
394
395
396
397
				continue;
			if (compare_absolute_package_preference(&p, p0) < 0)
				ps->preference++;
		}
	}
398
399

	dbg_printf(PKG_VER_FMT ": preference=%d\n", PKG_VER_PRINTF(pkg), ps->preference);
400
401
}

402
static void count_name(struct apk_solver_state *ss, struct apk_name *name)
403
{
404
	if (!name->ss.decision_counted) {
405
		ss->max_decisions++;
406
		name->ss.decision_counted = 1;
407
408
409
	}
}

410
411
412
static void sort_hard_dependencies(struct apk_solver_state *ss,
				   struct apk_package *pkg,
				   struct apk_package *parent_pkg)
413
{
414
	struct apk_name *name = pkg->name;
415
	struct apk_package_state *ps;
416
	int i;
417

418
	ps = pkg_to_ps_alloc(pkg);
419
	if (ps->topology_soft)
420
		return;
421
	pkg->topology_hard = -1;
422
	ps->topology_soft = -1;
423

424
	calculate_pkg_preference(pkg);
425

426
	/* Consider hard dependencies only */
427
428
	foreach_dependency_pkg(ss, pkg, pkg->depends, sort_hard_dependencies);
	foreach_dependency_pkg(ss, pkg, pkg->install_if, sort_hard_dependencies);
429

430
	ss->max_decisions++;
431
432
433
434
	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;
435
		count_name(ss, pkg->provides->item[i].name);
436
	}
437

438
	ps->topology_soft = pkg->topology_hard = ++ss->num_topology_positions;
439
	dbg_printf(PKG_VER_FMT ": topology_hard=%d\n",
440
		   PKG_VER_PRINTF(pkg), pkg->topology_hard);
441
442
}

443
444
445
static void sort_soft_dependencies(struct apk_solver_state *ss,
				   struct apk_package *pkg,
				   struct apk_package *parent_pkg)
446
447
{
	struct apk_package_state *ps;
448
	struct apk_package_state *parent_ps;
449

450
	sort_hard_dependencies(ss, pkg, parent_pkg);
451
452

	ps = pkg_to_ps(pkg);
453
	if (ps->topology_soft != pkg->topology_hard)
454
		return;
Timo Teräs's avatar
Timo Teräs committed
455
	ps->topology_soft = -1;
456

457
458
459
460
461
	/* 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;

462
463
	/* Soft reverse dependencies aka. install_if */
	foreach_rinstall_if_pkg(ss, pkg, sort_hard_dependencies);
464
	foreach_dependency_pkg(ss, pkg, pkg->depends, sort_soft_dependencies);
465
466
467
468
469

	/* 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);
470
471
}

472
473
474
static void update_allowed(struct apk_database *db, struct apk_package *pkg)
{
	struct apk_package_state *ps = pkg_to_ps(pkg);
475
476
477
478
	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))
479
480
481
482
483
		ps->allowed = 1;
	else
		ps->allowed = 0;
}

484
static void sort_name(struct apk_solver_state *ss, struct apk_name *name)
Timo Teräs's avatar
Timo Teräs committed
485
486
487
{
	int i, j;

488
489
	for (i = 0; i < name->providers->num; i++) {
		struct apk_package *pkg = name->providers->item[i].pkg;
490
491
492
		struct apk_package_state *ps = pkg_to_ps_alloc(pkg);
		unsigned short allowed_pinning;

493
494
		ps->allowed_pinning |= name->ss.preferred_pinning;
		ps->allowed_pinning_maybe |= name->ss.preferred_pinning;
Timo Teräs's avatar
Timo Teräs committed
495

496
497
498
499
500
501
		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
502
		}
503
		update_allowed(ss->db, pkg);
504
		sort_soft_dependencies(ss, name->providers->item[i].pkg, pkg);
Timo Teräs's avatar
Timo Teräs committed
505
	}
506
507
}

508
509
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))
510
{
511
	int i;
512
	for (i = 0; i < deps->num; i++)
513
		func(ss, &deps->item[i]);
514
515
}

516
static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg, struct apk_name *exclude)
517
518
519
520
521
{
	int i, missing = 0;

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

524
525
		if (name == exclude ||
		    !name->ss.locked || !apk_dep_is_provided(dep, &name->ss.chosen))
526
527
528
529
530
531
			missing++;
	}

	return missing;
}

532
533
534
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
535
		.unsatisfied = name->ss.requirers,
536
		.preference = name->providers->num,
537
538
539
	};
}

540
static void promote_name(struct apk_solver_state *ss, struct apk_name *name)
541
{
542
	if (name->ss.locked)
543
		return;
Timo Teräs's avatar
Timo Teräs committed
544

545
	/* queue for handling if needed */
546
547
	if (!list_hashed(&name->ss.unsolved_list))
		list_add_tail(&name->ss.unsolved_list, &ss->unsolved_list_head);
548

549
550
	/* update info, but no cached information flush is required, as
	 * minimum_penalty can only go up */
551
	name->ss.name_touched = 1;
552
}
553

554
555
static void demote_name(struct apk_solver_state *ss, struct apk_name *name)
{
556
	if (name->ss.locked)
557
		return;
558

559
	/* remove cached information */
560
	name->ss.chosen = CHOSEN_NONE;
561

562
	/* and remove list, or request refresh */
563
564
565
566
	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);
567
			dbg_printf("%s: not required\n", name->name);
568
		}
569
	} else {
570
571
		/* still needed, put back to list */
		promote_name(ss, name);
572
	}
573
574
}

575
static int inherit_package_state(struct apk_database *db, struct apk_package *to, struct apk_package *from)
576
{
577
	struct apk_name *fname = from->name;
578
579
580
581
	struct apk_package_state *tps = pkg_to_ps(to);
	struct apk_package_state *fps = pkg_to_ps(from);
	int i, changed = 0;

582
	if ((fname->ss.solver_flags_inheritable & APK_SOLVERF_REINSTALL) ||
583
584
585
586
	    fps->inherited_reinstall) {
		tps->inherited_reinstall++;
		changed = 1;
	}
587

588
	if ((fname->ss.solver_flags_inheritable & APK_SOLVERF_UPGRADE) ||
589
590
591
592
	    fps->inherited_upgrade) {
		tps->inherited_upgrade++;
		changed = 1;
	}
593

594
595
596
597
	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)))
598
				continue;
599
600
601
			allowed_pinning &= ~BIT(i);
			if (tps->inherited_pinning[i]++ == 0) {
				tps->allowed_pinning |= BIT(i);
602
				changed = 2;
603
			}
604
		}
605
606
		if (changed == 2)
			update_allowed(db, to);
607
	}
608
609

	return changed;
610
}
611

612
static void uninherit_package_state(struct apk_database *db, struct apk_package *to, struct apk_package *from)
613
{
614
	struct apk_name *fname = from->name;
615
616
	struct apk_package_state *tps = pkg_to_ps(to);
	struct apk_package_state *fps = pkg_to_ps(from);
617
	int i, changed = 0;
618

619
	if ((fname->ss.solver_flags_inheritable & APK_SOLVERF_REINSTALL) ||
620
621
	    fps->inherited_reinstall)
		tps->inherited_reinstall--;
622

623
	if ((fname->ss.solver_flags_inheritable & APK_SOLVERF_UPGRADE) ||
624
625
	    fps->inherited_upgrade)
		tps->inherited_upgrade--;
626

627
628
629
630
	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)))
631
				continue;
632
			allowed_pinning &= ~BIT(i);
633
			if (--tps->inherited_pinning[i] == 0) {
634
				tps->allowed_pinning &= ~BIT(i);
635
636
				changed = 2;
			}
637
		}
638
639
		if (changed == 2)
			update_allowed(db, to);
640
	}
641
642
}

643
static void trigger_install_if(struct apk_solver_state *ss,
644
645
			       struct apk_package *pkg,
			       struct apk_package *parent_pkg)
646
{
647
	struct apk_name *name = pkg->name;
648

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

static void untrigger_install_if(struct apk_solver_state *ss,
660
661
			         struct apk_package *pkg,
			         struct apk_package *parent_pkg)
662
{
663
	struct apk_name *name = pkg->name;
664

665
666
667
668
669
670
671
672
	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);
673
674
}

675
676
677
static inline void assign_name(
	struct apk_solver_state *ss, struct apk_name *name, struct apk_provider p)
{
678
679
	if (name->ss.locked &&
	    (p.version != &apk_null_blob || name->ss.chosen.version != &apk_null_blob)) {
Timo Teräs's avatar
Timo Teräs committed
680
681
		/* Assigning locked name with version is a problem;
		 * generally package providing same name twice */
682
		dbg_printf("%s: re-provided by %s\n", name->name, p.pkg->name->name);
683
684
685
		name->ss.locked++;
		ss->impossible_state = 1;
		return;
686
	}
687
688
689
690
691
	if (!name->ss.locked) {
		struct apk_package *pkg = p.pkg;

		subscore(&ss->minimum_penalty, &name->ss.minimum_penalty);
		name->ss.minimum_penalty = SCORE_ZERO;
692
		name->ss.chosen = p;
693
694
695
696
697
698
699
700
701
702

		if (name->ss.requirers) {
			struct apk_score score;
			if (pkg != NULL)
				get_topology_score(ss, name, pkg, &score);
			else
				get_unassigned_score(name, &score);
			addscore(&ss->score, &score);
		}
	}
703
704
705
706
	name->ss.locked++;
	if (list_hashed(&name->ss.unsolved_list)) {
		list_del(&name->ss.unsolved_list);
		list_init(&name->ss.unsolved_list);
707
708
709
710
711
	}
}

static inline void unassign_name(struct apk_solver_state *ss, struct apk_name *name)
{
Timo Teräs's avatar
Timo Teräs committed
712
	ASSERT(name->ss.locked, "Unassigning unlocked name %s", name->name);
713
714
	name->ss.locked--;
	if (name->ss.locked == 0) {
715
716
		struct apk_package *pkg = name->ss.chosen.pkg;

717
718
		name->ss.chosen = CHOSEN_NONE;
		name->ss.name_touched = 1;
719
		demote_name(ss, name);
720
721
722
723
724
725
726
727
728

		if (name->ss.requirers) {
			struct apk_score score;
			if (pkg != NULL)
				get_topology_score(ss, name, pkg, &score);
			else
				get_unassigned_score(name, &score);
			subscore(&ss->score, &score);
		}
729
	}
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
	struct apk_name *name = d->name;
736
	struct apk_package *pkg = decision_to_pkg(d);
737
	int i;
738

739
	ss->impossible_state = 0;
740
	name->ss.name_touched = 1;
741
742
743
744
745
746
747
	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");

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

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

		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;
		}
761
762

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

769
770
		if (d->type == DECISION_ASSIGN) {
			ss->assigned_names++;
771
772
773
774
775
			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));
			}
776
777

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

		if (d->type == DECISION_ASSIGN) {
787
			assign_name(ss, name, CHOSEN_NONE);
788
		} else {
789
			name->ss.none_excluded = 1;
790
791
792
		}
	}

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

800
801
	if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) >= 0) {
		dbg_printf("%s: %s penalty too big: "SCORE_FMT"+"SCORE_FMT">="SCORE_FMT"\n",
802
803
804
			name->name,
			(d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE",
			SCORE_PRINTF(&ss->score),
805
			SCORE_PRINTF(&ss->minimum_penalty),
806
			SCORE_PRINTF(&ss->best_score));
Timo Teräs's avatar
Timo Teräs committed
807
		return SOLVERR_PRUNED;
808
	}
Timo Teräs's avatar
Timo Teräs committed
809
810

	return SOLVERR_EXPAND;
811
812
813
}

static void undo_decision(struct apk_solver_state *ss,
814
			  struct apk_decision *d)
815
{
816
	struct apk_name *name = d->name;
817
	struct apk_package *pkg = decision_to_pkg(d);
818
	int i;
819

820
	name->ss.name_touched = 1;
821

822
823
	if (pkg != NULL) {
		struct apk_package_state *ps = pkg_to_ps(pkg);
824

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

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

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

844
			unassign_name(ss, pkg->name);
845
846
847
848
849
			for (i = 0; i < pkg->provides->num; i++) {
				struct apk_dependency *p = &pkg->provides->item[i];
				unassign_name(ss, p->name);
			}
			ss->assigned_names--;
850
		}
851
		ps->locked = 0;
Timo Teräs's avatar
Timo Teräs committed
852
	} else {
853
854
855
856
857
		dbg_printf("-->undo_decision: %s %s NOTHING\n",
			   name->name,
			   (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");

		if (d->type == DECISION_ASSIGN) {
858
			unassign_name(ss, name);
859
		} else {
860
			name->ss.none_excluded = 0;
861
		}
862

863
864
865
		/* Put back the name to unsolved list */
		promote_name(ss, name);
	}
866
867
}

868
869
870
871
872
873
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)
874
{
875
	struct apk_decision *d;
876
	int i;
877

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

881
882
883
884
	ss->num_decisions++;
	d = &ss->decisions[ss->num_decisions];

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