solver.c 55.8 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;
44
			unsigned short conflicts;
45
#elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
46
			unsigned short conflicts;
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

58
59
#define SCORE_FMT		"{%d/%d/%d,%d}"
#define SCORE_PRINTF(s)		(s)->conflicts, (s)->non_preferred_actions, (s)->non_preferred_pinnings, (s)->preference
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

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;
78
	unsigned short saved_requirers;
79
80
81
82
83
84
#endif

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

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

99
100
101
	unsigned short must_not;
	unsigned short incompat_dep;

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

	unsigned solver_flags_maybe : 4;
108
109
};

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

112
struct apk_name_state {
113
	/* dynamic */
114
	struct list_head unsolved_list;
Timo Teräs's avatar
Timo Teräs committed
115
	struct apk_name *name;
116
	struct apk_provider chosen;
117

118
	unsigned int last_touched_decision;
119
	unsigned short requirers;
120
	unsigned short install_ifs;
121
	unsigned short preferred_pinning;
122
	unsigned short locked;
123

124
	/* one time prepare/finish flags */
125
	unsigned solver_flags_local : 4;
126
	unsigned solver_flags_inheritable : 4;
Timo Teräs's avatar
Timo Teräs committed
127

128
129
	unsigned decision_counted : 1;
	unsigned originally_installed : 1;
130
	unsigned has_available_pkgs : 1;
131
	unsigned in_changeset : 1;
132
	unsigned in_world_dependency : 1;
133
134
135

	/* dynamic state flags */
	unsigned none_excluded : 1;
136
	unsigned name_touched : 1;
137
	unsigned preferred_chosen : 1;
138
139
140
141
};

struct apk_solver_state {
	struct apk_database *db;
142
	struct apk_decision *decisions;
143

144
	struct list_head unsolved_list_head;
145
146
147

	unsigned int num_topology_positions;
	unsigned int num_decisions, max_decisions;
148
149
	unsigned int topology_position;
	unsigned int assigned_names;
Timo Teräs's avatar
Timo Teräs committed
150

151
	struct apk_solution_array *best_solution;
152
153

	struct apk_score score;
Timo Teräs's avatar
Timo Teräs committed
154
	struct apk_score best_score;
155
156

	unsigned solver_flags : 4;
157
	unsigned impossible_state : 1;
158
159
};

Timo Teräs's avatar
Timo Teräs committed
160
161
162
163
164
165
166
typedef enum {
	SOLVERR_SOLUTION = 0,
	SOLVERR_PRUNED,
	SOLVERR_EXPAND,
	SOLVERR_STOP,
} solver_result_t;

167
168
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);
169
170
171
172
173
174
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);
175

176
#ifdef DEBUG_CHECKS
177
178
static void addscore(struct apk_score *a, struct apk_score *b)
{
179
180
181
182
	struct apk_score orig = *a;
	a->score += b->score;
	ASSERT(a->conflicts >= orig.conflicts, "Conflict overflow");
	ASSERT(a->non_preferred_actions >= orig.non_preferred_actions, "Preferred action overflow");
183
	ASSERT(a->non_preferred_pinnings >= orig.non_preferred_pinnings, "Preferred pinning overflow");
184
	ASSERT(a->preference >= orig.preference, "Preference overflow");
185
186
187
188
}

static void subscore(struct apk_score *a, struct apk_score *b)
{
189
190
191
192
	struct apk_score orig = *a;
	a->score -= b->score;
	ASSERT(a->conflicts <= orig.conflicts, "Conflict underflow");
	ASSERT(a->non_preferred_actions <= orig.non_preferred_actions, "Preferred action underflow");
193
	ASSERT(a->non_preferred_pinnings <= orig.non_preferred_pinnings, "Preferred pinning overflow");
194
	ASSERT(a->preference <= orig.preference, "Preference underflow");
195
}
196
197
198
199
200
201
202
203
204
205
#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;
}
206
#endif
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222

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;
}
223
224
225
226
227
228
229
230
231
232
233
234
235

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;
236
237
}

Timo Teräs's avatar
Timo Teräs committed
238
static struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
239
240
241
242
{
	return (struct apk_package_state*) pkg->state_ptr;
}

243
244
245
246
247
248
249
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);
}

Timo Teräs's avatar
Timo Teräs committed
250
static struct apk_name_state *name_to_ns(struct apk_name *name)
251
252
253
254
255
{
	return (struct apk_name_state*) name->state_ptr;
}

static struct apk_name_state *name_to_ns_alloc(struct apk_name *name)
Timo Teräs's avatar
Timo Teräs committed
256
{
Timo Teräs's avatar
Timo Teräs committed
257
	struct apk_name_state *ns;
258
	int i;
Timo Teräs's avatar
Timo Teräs committed
259
260
261
262

	if (name->state_ptr == NULL) {
		ns = calloc(1, sizeof(struct apk_name_state));
		ns->name = name;
263
264
		for (i = 0; i < name->providers->num; i++) {
			if (name->providers->item[i].pkg->repos != 0) {
265
266
267
268
				ns->has_available_pkgs = 1;
				break;
			}
		}
Timo Teräs's avatar
Timo Teräs committed
269
270
271
272
273
		name->state_ptr = ns;
	} else {
		ns = (struct apk_name_state*) name->state_ptr;
	}
	return ns;
Timo Teräs's avatar
Timo Teräs committed
274
275
}

276
static inline int pkg_available(struct apk_database *db, struct apk_package *pkg)
277
{
278
	/* virtual packages - only deps used; no real .apk */
279
280
	if (pkg->installed_size == 0)
		return TRUE;
281
	/* obviously present */
282
	if (pkg->in_cache || pkg->filename != NULL || (pkg->repos & db->local_repos))
283
284
285
		return TRUE;
	/* can download */
	if ((pkg->repos & ~db->bad_repos) && !(apk_flags & APK_NO_NETWORK))
286
287
288
289
		return TRUE;
	return FALSE;
}

290
static void foreach_dependency_pkg(
291
292
	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))
293
294
295
{
	int i, j;

296
297
298
	/* And sort the main dependencies */
	for (i = 0; i < depends->num; i++) {
		struct apk_dependency *dep = &depends->item[i];
299
300
		struct apk_name *name0 = dep->name;

301
302
		for (j = 0; j < name0->providers->num; j++) {
			struct apk_provider *p0 = &name0->providers->item[j];
303

304
			/* conflict depends on all to be not installed */
305
			if (!apk_dep_is_provided(dep, p0))
306
				continue;
307

308
			cb(ss, p0->pkg, parent_package);
309
310
		}
	}
311
}
312

313
314
static void foreach_rinstall_if_pkg(
	struct apk_solver_state *ss, struct apk_package *pkg,
315
	void (*cb)(struct apk_solver_state *ss, struct apk_package *rinstall_if, struct apk_package *parent_pkg))
316
317
318
319
320
321
322
323
324
{
	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);
325

326
327
328
329
330
		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];
331
332

				if (dep->name == name &&
333
				    apk_dep_is_provided(dep, p0))
334
335
					break;
			}
336
			if (k >= p0->pkg->install_if->num)
337
338
339
				continue;

			/* pkg depends (via install_if) on pkg0 */
340
			cb(ss, p0->pkg, pkg);
341
342
343
344
		}
	}
}

345
346
347
348
349
350
351
352
353
354
355
356
357
358
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;
}

359
static int get_topology_score(
360
361
362
363
364
365
366
367
368
369
		struct apk_solver_state *ss,
		struct apk_name_state *ns,
		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;
370
	int score_locked = TRUE, sticky_installed = FALSE;
371
372

	score = (struct apk_score) {
373
		.conflicts = ps->incompat_dep,
374
375
376
		.preference = ps->preference,
	};

377
	if (ss->solver_flags & APK_SOLVERF_AVAILABLE) {
Timo Teräs's avatar
Timo Teräs committed
378
		/* available preferred */
379
380
		if ((pkg->repos == 0) && ns->has_available_pkgs)
			score.non_preferred_actions++;
381
	} else if (ps->inherited_reinstall ||
382
383
384
385
		   (((ns->solver_flags_local|ss->solver_flags) & APK_SOLVERF_REINSTALL))) {
		/* reinstall requested, but not available */
		if (!pkg_available(ss->db, pkg))
			score.non_preferred_actions++;
386
	} else if (ps->inherited_upgrade ||
Timo Teräs's avatar
Timo Teräs committed
387
388
		   ((ns->solver_flags_local|ss->solver_flags) & APK_SOLVERF_UPGRADE)) {
		/* upgrading - score is just locked here */
389
	} else if ((ps->inherited_upgrade == 0) &&
390
		   ((ns->solver_flags_local|ss->solver_flags) & APK_SOLVERF_UPGRADE) == 0 &&
391
		   ((ps->solver_flags_maybe & APK_SOLVERF_UPGRADE) == 0 || (ps->locked))) {
392
393
394
		/* not upgrading: it is not preferred to change package */
		if (pkg->ipkg == NULL && ns->originally_installed)
			score.non_preferred_actions++;
395
396
		else
			sticky_installed = TRUE;
397
398
	} else {
		score_locked = FALSE;
399
400
401
402
403
404
405
	}

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

	if (!(repos & preferred_repos))
406
		score.non_preferred_pinnings++;
407

408
409
	if (ps->locked || (ps->allowed_pinning | ps->allowed_pinning_maybe) == ps->allowed_pinning) {
		allowed_pinning = ps->allowed_pinning | preferred_pinning | APK_DEFAULT_PINNING_MASK;
410
		allowed_repos = get_pinning_mask_repos(ss->db, allowed_pinning);
411
412
413
		if (!(repos & allowed_repos)) {
			if (sticky_installed)
				score.non_preferred_actions++;
414
			score.non_preferred_pinnings += 16;
415
		}
416
417
	} else {
		score_locked = FALSE;
418
419
420
	}

	*_score = score;
421
	return score_locked;
422
423
424
}

static int compare_absolute_package_preference(
425
426
		struct apk_provider *pA,
		struct apk_provider *pB)
427
{
428
429
430
	struct apk_package *pkgA = pA->pkg;
	struct apk_package *pkgB = pB->pkg;

431
432
433
434
435
436
437
438
	/* 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 */
439
	switch (apk_version_compare_blob(*pA->version, *pB->version)) {
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
	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);
460
	struct apk_provider p = APK_PROVIDER_FROM_PACKAGE(pkg);
461
	int i, j;
462

463
464
465
	for (i = 0; i < name->providers->num; i++) {
		struct apk_provider *p0 = &name->providers->item[i];
		if (pkg == p0->pkg)
466
			continue;
467
		if (compare_absolute_package_preference(&p, p0) < 0)
468
469
			ps->preference++;
	}
470
471
472
473
474
475
476
477
478
479
480
481
	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++;
		}
	}
482
483
}

484
static void count_name(struct apk_solver_state *ss, struct apk_name *name)
485
{
486
487
	struct apk_name_state *ns = name_to_ns_alloc(name);

488
489
490
491
492
493
	if (!ns->decision_counted) {
		ss->max_decisions++;
		ns->decision_counted = 1;
	}
}

494
495
496
static void sort_hard_dependencies(struct apk_solver_state *ss,
				   struct apk_package *pkg,
				   struct apk_package *parent_pkg)
497
498
{
	struct apk_package_state *ps;
499
	int i;
500

501
	ps = pkg_to_ps_alloc(pkg);
502
	if (ps->topology_soft)
503
		return;
504
	pkg->topology_hard = -1;
505
	ps->topology_soft = -1;
506

507
	calculate_pkg_preference(pkg);
508

509
	/* Consider hard dependencies only */
510
511
	foreach_dependency_pkg(ss, pkg, pkg->depends, sort_hard_dependencies);
	foreach_dependency_pkg(ss, pkg, pkg->install_if, sort_hard_dependencies);
512

513
	ss->max_decisions++;
514
515
516
	count_name(ss, pkg->name);
	for (i = 0; i < pkg->provides->num; i++)
		count_name(ss, pkg->provides->item[i].name);
517

518
	ps->topology_soft = pkg->topology_hard = ++ss->num_topology_positions;
519
	dbg_printf(PKG_VER_FMT ": topology_hard=%d\n",
520
		   PKG_VER_PRINTF(pkg), pkg->topology_hard);
521
522
}

523
524
525
static void sort_soft_dependencies(struct apk_solver_state *ss,
				   struct apk_package *pkg,
				   struct apk_package *parent_pkg)
526
527
{
	struct apk_package_state *ps;
528
	struct apk_package_state *parent_ps;
529

530
	sort_hard_dependencies(ss, pkg, parent_pkg);
531
532

	ps = pkg_to_ps(pkg);
533
	if (ps->topology_soft != pkg->topology_hard)
534
		return;
Timo Teräs's avatar
Timo Teräs committed
535
	ps->topology_soft = -1;
536

537
538
539
540
541
	/* 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;

542
543
	/* Soft reverse dependencies aka. install_if */
	foreach_rinstall_if_pkg(ss, pkg, sort_hard_dependencies);
544
	foreach_dependency_pkg(ss, pkg, pkg->depends, sort_soft_dependencies);
545
546
547
548
549

	/* 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);
550
551
}

552
553
554
555
556
557
558
559
560
static void update_allowed(struct apk_database *db, struct apk_package *pkg)
{
	struct apk_package_state *ps = pkg_to_ps(pkg);
	if (pkg->repos & get_pinning_mask_repos(db, ps->allowed_pinning | APK_DEFAULT_PINNING_MASK))
		ps->allowed = 1;
	else
		ps->allowed = 0;
}

561
static void sort_name(struct apk_solver_state *ss, struct apk_name *name)
Timo Teräs's avatar
Timo Teräs committed
562
{
563
	struct apk_name_state *ns = name_to_ns_alloc(name);
Timo Teräs's avatar
Timo Teräs committed
564
565
	int i, j;

566
567
	for (i = 0; i < name->providers->num; i++) {
		struct apk_package *pkg = name->providers->item[i].pkg;
568
569
570
571
572
		struct apk_package_state *ps = pkg_to_ps_alloc(pkg);
		unsigned short allowed_pinning;

		ps->allowed_pinning |= ns->preferred_pinning;
		ps->allowed_pinning_maybe |= ns->preferred_pinning;
Timo Teräs's avatar
Timo Teräs committed
573

574
575
576
577
578
579
		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
580
		}
581
		update_allowed(ss->db, pkg);
582
		sort_soft_dependencies(ss, name->providers->item[i].pkg, pkg);
Timo Teräs's avatar
Timo Teräs committed
583
	}
584
585
}

586
587
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))
588
{
589
	int i;
590
	for (i = 0; i < deps->num; i++)
591
		func(ss, &deps->item[i]);
592
593
}

594
595
static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg)
{
Timo Teräs's avatar
Timo Teräs committed
596
	struct apk_name_state *ns;
597
598
599
600
601
	int i, missing = 0;

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

Timo Teräs's avatar
Timo Teräs committed
602
		ns = name_to_ns(dep->name);
603
604
605

		/* ns can be NULL, if the install_if has a name with
		 * no packages */
606
607
		if (ns == NULL || !ns->locked ||
		    !apk_dep_is_provided(dep, &ns->chosen))
608
609
610
611
612
613
			missing++;
	}

	return missing;
}

614
615
616
617
618
static void get_unassigned_score(struct apk_name *name, struct apk_score *score)
{
	struct apk_name_state *ns = name_to_ns(name);

	*score = (struct apk_score){
619
		.conflicts = ns->requirers,
620
		.preference = name->providers->num,
621
622
623
	};
}

624
static void promote_name(struct apk_solver_state *ss, struct apk_name *name)
625
{
Timo Teräs's avatar
Timo Teräs committed
626
	struct apk_name_state *ns = name_to_ns(name);
627

Timo Teräs's avatar
Timo Teräs committed
628
	if (ns->locked)
629
		return;
Timo Teräs's avatar
Timo Teräs committed
630

631
632
633
	/* queue for handling if needed */
	if (!list_hashed(&ns->unsolved_list))
		list_add_tail(&ns->unsolved_list, &ss->unsolved_list_head);
634

635
636
	/* update info, but no cached information flush is required, as
	 * minimum_penalty can only go up */
637
	ns->name_touched = 1;
638
}
639

640
641
642
static void demote_name(struct apk_solver_state *ss, struct apk_name *name)
{
	struct apk_name_state *ns = name_to_ns(name);
643

644
645
	if (ns->locked)
		return;
646

647
	/* remove cached information */
648
	ns->chosen = CHOSEN_NONE;
649

650
	/* and remove list, or request refresh */
651
	if (ns->requirers == 0 && ns->install_ifs == 0) {
652
653
654
		if (list_hashed(&ns->unsolved_list)) {
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
655
			dbg_printf("%s: not required\n", name->name);
656
		}
657
	} else {
658
659
		/* still needed, put back to list */
		promote_name(ss, name);
660
	}
661
662
}

663
static int inherit_package_state(struct apk_database *db, struct apk_package *to, struct apk_package *from)
664
{
665
666
667
668
669
670
671
672
673
674
	struct apk_package_state *tps = pkg_to_ps(to);
	struct apk_name_state *fns = name_to_ns(from->name);
	struct apk_package_state *fps = pkg_to_ps(from);
	int i, changed = 0;

	if ((fns->solver_flags_inheritable & APK_SOLVERF_REINSTALL) ||
	    fps->inherited_reinstall) {
		tps->inherited_reinstall++;
		changed = 1;
	}
675

676
677
678
679
680
	if ((fns->solver_flags_inheritable & APK_SOLVERF_UPGRADE) ||
	    fps->inherited_upgrade) {
		tps->inherited_upgrade++;
		changed = 1;
	}
681

682
683
684
685
	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)))
686
				continue;
687
688
689
			allowed_pinning &= ~BIT(i);
			if (tps->inherited_pinning[i]++ == 0) {
				tps->allowed_pinning |= BIT(i);
690
				changed = 2;
691
			}
692
		}
693
694
		if (changed == 2)
			update_allowed(db, to);
695
	}
696
697

	return changed;
698
}
699

700
static void uninherit_package_state(struct apk_database *db, struct apk_package *to, struct apk_package *from)
701
{
702
703
704
	struct apk_package_state *tps = pkg_to_ps(to);
	struct apk_name_state *fns = name_to_ns(from->name);
	struct apk_package_state *fps = pkg_to_ps(from);
705
	int i, changed = 0;
706

707
708
709
	if ((fns->solver_flags_inheritable & APK_SOLVERF_REINSTALL) ||
	    fps->inherited_reinstall)
		tps->inherited_reinstall--;
710

711
712
713
	if ((fns->solver_flags_inheritable & APK_SOLVERF_UPGRADE) ||
	    fps->inherited_upgrade)
		tps->inherited_upgrade--;
714

715
716
717
718
	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)))
719
				continue;
720
			allowed_pinning &= ~BIT(i);
721
			if (--tps->inherited_pinning[i] == 0) {
722
				tps->allowed_pinning &= ~BIT(i);
723
724
				changed = 2;
			}
725
		}
726
727
		if (changed == 2)
			update_allowed(db, to);
728
	}
729
730
}

731
static void trigger_install_if(struct apk_solver_state *ss,
732
733
			       struct apk_package *pkg,
			       struct apk_package *parent_pkg)
734
735
{
	if (install_if_missing(ss, pkg) == 0) {
736
		struct apk_name_state *ns = name_to_ns(pkg->name);
737
738
739
740

		dbg_printf("trigger_install_if: " PKG_VER_FMT " triggered\n",
			   PKG_VER_PRINTF(pkg));
		ns->install_ifs++;
741
		inherit_package_state(ss->db, pkg, parent_pkg);
742
		promote_name(ss, pkg->name);
743
744
745
746
	}
}

static void untrigger_install_if(struct apk_solver_state *ss,
747
748
			         struct apk_package *pkg,
			         struct apk_package *parent_pkg)
749
750
{
	if (install_if_missing(ss, pkg) != 1) {
Timo Teräs's avatar
Timo Teräs committed
751
		struct apk_name_state *ns = name_to_ns(pkg->name);
752
753
754
755

		dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n",
			   PKG_VER_PRINTF(pkg));
		ns->install_ifs--;
756
		uninherit_package_state(ss->db, pkg, parent_pkg);
757
		demote_name(ss, pkg->name);
758
759
760
	}
}

761
762
763
764
765
static inline void assign_name(
	struct apk_solver_state *ss, struct apk_name *name, struct apk_provider p)
{
	struct apk_name_state *ns = name_to_ns(name);

766
767
768
769
770
771
	if (p.version == &apk_null_blob) {
		ASSERT(!ns->locked || ns->chosen.version == &apk_null_blob,
		       "Assigning locked name with version");
	} else {
		ASSERT(!ns->locked, "Assigning locked name");
	}
772
	ns->chosen = p;
773
	ns->locked++;
774
775
776
777
778
779
780
781
782
783
784
	if (list_hashed(&ns->unsolved_list)) {
		list_del(&ns->unsolved_list);
		list_init(&ns->unsolved_list);
	}
}

static inline void unassign_name(struct apk_solver_state *ss, struct apk_name *name)
{
	struct apk_name_state *ns = name_to_ns(name);

	ASSERT(ns->locked, "Unassigning unlocked name");
785
786
787
788
789
790
	ns->locked--;
	if (ns->locked == 0) {
		ns->chosen = CHOSEN_NONE;
		ns->name_touched = 1;
		demote_name(ss, name);
	}
791
792
}

Timo Teräs's avatar
Timo Teräs committed
793
static solver_result_t apply_decision(struct apk_solver_state *ss,
794
				      struct apk_decision *d)
795
{
796
	struct apk_name *name = decision_to_name(d);
Timo Teräs's avatar
Timo Teräs committed
797
	struct apk_name_state *ns = name_to_ns(name);
798
799
	struct apk_package *pkg = decision_to_pkg(d);
	struct apk_score score;
800
	int i;
801

802
	ss->impossible_state = 0;
803
	ns->name_touched = 1;
804
805
806
807
808
809
810
	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");

811
812
813
		for (i = 0; i < pkg->provides->num; i++)
			name_to_ns(pkg->provides->item[i].name)->name_touched = 1;

814
815
816
817
818
819
820
821
822
823
824
825
826
827
		ps->locked = 1;
		ps->handle_install_if = 0;

		if (d->topology_position) {
			if (ps->topology_soft < ss->topology_position) {
				if (d->type == DECISION_ASSIGN) {
					ps->handle_install_if = 1;
					dbg_printf("triggers due to " PKG_VER_FMT "\n",
						   PKG_VER_PRINTF(pkg));
				}
				ss->topology_position = ps->topology_soft;
			} else {
				ss->topology_position = pkg->topology_hard;
			}
Timo Teräs's avatar
Timo Teräs committed
828
829
		}

830
		if (d->type == DECISION_ASSIGN) {
831
			get_topology_score(ss, ns, pkg, &score);
832
833
834
			addscore(&ss->score, &score);

			ss->assigned_names++;
835
836
837
838
839
			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));
			}
840
841
842
843

			foreach_dependency(ss, pkg->depends, apply_constraint);
			foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
		}
844
	} else {
845
846
847
848
849
850
851
		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
852

853
			ns->chosen = CHOSEN_NONE;
Timo Teräs's avatar
Timo Teräs committed
854
			ns->locked = 1;
855
856
857
858
859
860
861
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
		} else {
			ns->none_excluded = 1;
		}
	}

862
863
864
865
866
867
868
	if (ss->impossible_state) {
		dbg_printf("%s: %s impossible constraints\n",
			name->name,
			(d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
		return SOLVERR_PRUNED;
	}

869
870
	if (cmpscore(&ss->score, &ss->best_score) >= 0) {
		dbg_printf("%s: %s penalty too big: "SCORE_FMT">="SCORE_FMT"\n",
871
872
873
874
			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
875
		return SOLVERR_PRUNED;
876
	}
Timo Teräs's avatar
Timo Teräs committed
877
878

	return SOLVERR_EXPAND;
879
880
881
}

static void undo_decision(struct apk_solver_state *ss,
882
			  struct apk_decision *d)
883
{
884
	struct apk_name *name = decision_to_name(d);
885
	struct apk_name_state *ns = name_to_ns(name);
886
887
	struct apk_package *pkg = decision_to_pkg(d);
	struct apk_score score;
888
	int i;
889

890
	ns->name_touched = 1;
891

892
893
	if (pkg != NULL) {
		struct apk_package_state *ps = pkg_to_ps(pkg);
894

895
896
897
898
899
900
901
902
903
904
		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;
		}
905

906
907
908
		for (i = 0; i < pkg->provides->num; i++)
			name_to_ns(pkg->provides->item[i].name)->name_touched = 1;

Timo Teräs's avatar
Timo Teräs committed
909
		if (ns->locked) {
Timo Teräs's avatar
Timo Teräs committed
910
911
			foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
			foreach_dependency(ss, pkg->depends, undo_constraint);
912

913
			get_topology_score(ss, ns, pkg, &score);
914
			subscore(&ss->score, &score);
915
916
917
918
919
920
921

			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--;
922
		}
923
		ps->locked = 0;
Timo Teräs's avatar
Timo Teräs committed
924
	} else {
925
926
927
928
929
930
931
932
933
		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 {
			ns->none_excluded = 0;
934
		}
935

936
937
938
939
		/* Put back the name to unsolved list */
		ns->locked = 0;
		promote_name(ss, name);
	}
940
941
}

942
943
944
945
946
947
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)
948
{
949
	struct apk_decision *d;
950

951
	ASSERT(ss->num_decisions <= ss->max_decisions,
952
	       "Decision tree overflow.");
953

954
955
956
957
958
	ss->num_decisions++;
	d = &ss->decisions[ss->num_decisions];

#ifdef DEBUG_CHECKS
	d->saved_score = ss->score;
959
	d->saved_requirers = name_to_ns(name)->requirers;
960
961
962
963
#endif
	d->type = primary_decision;
	d->branching_point = branching_point;
	d->topology_position = topology_position;
964
	d->found_solution = 0;
965
966
967
	if (pkg == NULL) {
		d->name = name;
		d->no_package = 1;
968
	} else {
969
970
		d->pkg = pkg;
		d->no_package = 0;
971
	}
972

973
	return apply_decision(ss, d);
974
975
976
977
}

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

980
981
	while (ss->num_decisions > 0) {
		struct apk_decision *d = &ss->decisions[ss->num_decisions];