solver.c 52.4 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
32
33
34
35
#if defined(DEBUG_PRINT) || defined(DEBUG_CHECKS)
#define ASSERT(cond, fmt...) \
	if (!(cond)) { fprintf(stderr, fmt); *(char*)NULL = 0; }
#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
	unsigned int topology_soft;
90
	unsigned short conflicts;
91
	unsigned char preference;
92
93
	unsigned handle_install_if : 1;
	unsigned locked : 1;
94
95
96
97
};

struct apk_name_state {
	struct list_head unsolved_list;
Timo Teräs's avatar
Timo Teräs committed
98
	struct apk_name *name;
99
	struct apk_package *chosen;
100

101
	struct apk_score minimum_penalty;
102
	unsigned short requirers;
103
	unsigned short install_ifs;
Timo Teräs's avatar
Timo Teräs committed
104

105
	/* set on startup */
106
	unsigned short preferred_pinning;
107
108
109
110
	unsigned short maybe_pinning;

	/* dynamic */
	unsigned int last_touched_decision;
111
	unsigned short allowed_pinning;
112
113
114
	unsigned short inherited_pinning[APK_MAX_TAGS];
	unsigned short inherited_upgrade;
	unsigned short inherited_reinstall;
115

116
	/* one time prepare/finish flags */
117
118
	unsigned solver_flags_local : 4;
	unsigned solver_flags_local_mask : 4;
119
	unsigned solver_flags_maybe : 4;
Timo Teräs's avatar
Timo Teräs committed
120

121
122
	unsigned decision_counted : 1;
	unsigned originally_installed : 1;
123
	unsigned has_available_pkgs : 1;
124
	unsigned in_changeset : 1;
125
	unsigned in_world_dependency : 1;
126
127
128
129

	/* dynamic state flags */
	unsigned none_excluded : 1;
	unsigned locked : 1;
130
	unsigned name_touched : 1;
131
132
133
134
};

struct apk_solver_state {
	struct apk_database *db;
135
	struct apk_decision *decisions;
136

137
	struct list_head unsolved_list_head;
138
139
140

	unsigned int num_topology_positions;
	unsigned int num_decisions, max_decisions;
141
142
	unsigned int topology_position;
	unsigned int assigned_names;
Timo Teräs's avatar
Timo Teräs committed
143

144
	struct apk_solution_array *best_solution;
145
146
147

	struct apk_score score;
	struct apk_score minimum_penalty;
Timo Teräs's avatar
Timo Teräs committed
148
	struct apk_score best_score;
149
150

	unsigned solver_flags : 4;
151
152
};

Timo Teräs's avatar
Timo Teräs committed
153
154
155
156
157
158
159
typedef enum {
	SOLVERR_SOLUTION = 0,
	SOLVERR_PRUNED,
	SOLVERR_EXPAND,
	SOLVERR_STOP,
} solver_result_t;

160
161
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);
162
163
164
165
166
167
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);
168

169
#ifdef DEBUG_CHECKS
170
171
static void addscore(struct apk_score *a, struct apk_score *b)
{
172
173
174
175
176
	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");
	ASSERT(a->preference >= orig.preference, "Preference overflow");
177
178
179
180
}

static void subscore(struct apk_score *a, struct apk_score *b)
{
181
182
183
184
185
	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");
	ASSERT(a->preference <= orig.preference, "Preference underflow");
186
}
187
188
189
190
191
192
193
194
195
196
#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;
}
197
#endif
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213

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;
}
214
215
216
217
218
219
220
221
222
223
224
225
226

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;
227
228
}

Timo Teräs's avatar
Timo Teräs committed
229
static struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
230
231
232
233
{
	return (struct apk_package_state*) pkg->state_ptr;
}

Timo Teräs's avatar
Timo Teräs committed
234
static struct apk_name_state *name_to_ns(struct apk_name *name)
235
236
237
238
239
{
	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
240
{
Timo Teräs's avatar
Timo Teräs committed
241
	struct apk_name_state *ns;
242
	int i;
Timo Teräs's avatar
Timo Teräs committed
243
244
245
246

	if (name->state_ptr == NULL) {
		ns = calloc(1, sizeof(struct apk_name_state));
		ns->name = name;
247
248
249
250
251
252
		for (i = 0; i < name->pkgs->num; i++) {
			if (name->pkgs->item[i]->repos != 0) {
				ns->has_available_pkgs = 1;
				break;
			}
		}
Timo Teräs's avatar
Timo Teräs committed
253
254
255
256
257
		name->state_ptr = ns;
	} else {
		ns = (struct apk_name_state*) name->state_ptr;
	}
	return ns;
Timo Teräs's avatar
Timo Teräs committed
258
259
}

260
static inline int pkg_available(struct apk_database *db, struct apk_package *pkg)
261
{
262
	/* virtual packages - only deps used; no real .apk */
263
264
	if (pkg->installed_size == 0)
		return TRUE;
265
	/* obviously present */
266
	if (pkg->in_cache || pkg->filename != NULL || (pkg->repos & db->local_repos))
267
268
269
		return TRUE;
	/* can download */
	if ((pkg->repos & ~db->bad_repos) && !(apk_flags & APK_NO_NETWORK))
270
271
272
273
		return TRUE;
	return FALSE;
}

274
275
276
static void foreach_dependency_pkg(
	struct apk_solver_state *ss, struct apk_dependency_array *depends,
	void (*cb)(struct apk_solver_state *ss, struct apk_package *dependency))
277
278
279
{
	int i, j;

280
281
282
	/* And sort the main dependencies */
	for (i = 0; i < depends->num; i++) {
		struct apk_dependency *dep = &depends->item[i];
283
284
285
286
		struct apk_name *name0 = dep->name;

		for (j = 0; j < name0->pkgs->num; j++) {
			struct apk_package *pkg0 = name0->pkgs->item[j];
287

288
			/* conflict depends on all to be not installed */
289
			if (!apk_dep_is_satisfied(dep, pkg0))
290
				continue;
291
292

			cb(ss, pkg0);
293
294
		}
	}
295
}
296

297
298
299
300
301
302
303
304
305
306
307
308
static void foreach_rinstall_if_pkg(
	struct apk_solver_state *ss, struct apk_package *pkg,
	void (*cb)(struct apk_solver_state *ss, struct apk_package *rinstall_if))
{
	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);
309

310
311
312
313
314
315
		for (j = 0; j < name0->pkgs->num; j++) {
			struct apk_package *pkg0 = name0->pkgs->item[j];

			for (k = 0; k < pkg0->install_if->num; k++) {
				struct apk_dependency *dep = &pkg0->install_if->item[k];
				if (dep->name == name &&
316
				    apk_dep_is_satisfied(dep, pkg))
317
318
319
320
321
322
323
324
325
326
327
					break;
			}
			if (k >= pkg0->install_if->num)
				continue;

			/* pkg depends (via install_if) on pkg0 */
			cb(ss, pkg0);
		}
	}
}

328
329
330
331
332
333
334
335
336
337
338
339
340
341
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;
}

342
static int get_topology_score(
343
344
345
346
347
348
349
350
351
352
		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;
353
	int score_locked = TRUE, sticky_installed = FALSE;
354
355
356
357
358
359

	score = (struct apk_score) {
		.conflicts = ps->conflicts,
		.preference = ps->preference,
	};

360
	if (ss->solver_flags & APK_SOLVERF_AVAILABLE) {
Timo Teräs's avatar
Timo Teräs committed
361
		/* available preferred */
362
363
		if ((pkg->repos == 0) && ns->has_available_pkgs)
			score.non_preferred_actions++;
364
365
366
367
368
	} else if (ns->inherited_reinstall ||
		   (((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++;
Timo Teräs's avatar
Timo Teräs committed
369
370
371
	} else if (ns->inherited_upgrade ||
		   ((ns->solver_flags_local|ss->solver_flags) & APK_SOLVERF_UPGRADE)) {
		/* upgrading - score is just locked here */
372
	} else if ((ns->inherited_upgrade == 0) &&
373
374
		   ((ns->solver_flags_local|ss->solver_flags) & APK_SOLVERF_UPGRADE) == 0 &&
		   ((ns->solver_flags_maybe & APK_SOLVERF_UPGRADE) == 0 || (ps->locked))) {
375
376
377
		/* not upgrading: it is not preferred to change package */
		if (pkg->ipkg == NULL && ns->originally_installed)
			score.non_preferred_actions++;
378
379
		else
			sticky_installed = TRUE;
380
381
	} else {
		score_locked = FALSE;
382
383
384
385
386
387
388
	}

	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))
389
		score.non_preferred_pinnings++;
390

391
	if (ns->locked || (ns->allowed_pinning | ns->maybe_pinning) == ns->allowed_pinning) {
392
		allowed_pinning = ns->allowed_pinning | preferred_pinning | APK_DEFAULT_PINNING_MASK;
393
		allowed_repos = get_pinning_mask_repos(ss->db, allowed_pinning);
394
395
396
		if (!(repos & allowed_repos)) {
			if (sticky_installed)
				score.non_preferred_actions++;
397
			score.non_preferred_pinnings += 16;
398
		}
399
400
	} else {
		score_locked = FALSE;
401
402
403
	}

	*_score = score;
404
	return score_locked;
405
406
407
408
409
410
411
412
413
414
}

static int is_topology_optimum(struct apk_solver_state *ss,
			       struct apk_package *pkg)
{
	struct apk_name *name = pkg->name;
	struct apk_name_state *ns = name_to_ns(name);
	struct apk_score score;
	int i;

415
	get_topology_score(ss, ns, pkg, &score);
416
417
418
419
420
421
422
423
424
425
426
427
	for (i = 0; i < name->pkgs->num; i++) {
		struct apk_package *pkg0 = name->pkgs->item[i];
		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
		struct apk_score score0;

		if (pkg0 == pkg)
			continue;

		if (ps0 == NULL || ps0->locked ||
		    ss->topology_position < pkg->topology_hard)
			continue;

428
		get_topology_score(ss, ns, pkg0, &score0);
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
		if (cmpscore(&score0, &score) < 0)
			return 0;
	}

	return 1;
}

static int compare_absolute_package_preference(
		struct apk_package *pkgA,
		struct apk_package *pkgB)
{
	/* 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 */
	switch (apk_pkg_version_compare(pkgA, pkgB)) {
	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);
	int i;

	for (i = 0; i < name->pkgs->num; i++) {
		struct apk_package *pkg0 = name->pkgs->item[i];
		if (pkg == pkg0)
			continue;
		if (compare_absolute_package_preference(pkg, pkg0) < 0)
			ps->preference++;
	}
}

480
481
482
483
484
485
486
487
static void count_name(struct apk_solver_state *ss, struct apk_name_state *ns)
{
	if (!ns->decision_counted) {
		ss->max_decisions++;
		ns->decision_counted = 1;
	}
}

488
489
490
static void sort_hard_dependencies(struct apk_solver_state *ss, struct apk_package *pkg)
{
	struct apk_package_state *ps;
491
	struct apk_name_state *ns;
492
493
494
495
496

	if (pkg->state_ptr == NULL)
		pkg->state_ptr = calloc(1, sizeof(struct apk_package_state));

	ps = pkg_to_ps(pkg);
497
	if (ps->topology_soft)
498
		return;
499
	pkg->topology_hard = -1;
500
	ps->topology_soft = -1;
501

502
	calculate_pkg_preference(pkg);
503
504
505
506
	/* Consider hard dependencies only */
	foreach_dependency_pkg(ss, pkg->depends, sort_hard_dependencies);
	foreach_dependency_pkg(ss, pkg->install_if, sort_hard_dependencies);

507
	ss->max_decisions++;
508
	ns = name_to_ns_alloc(pkg->name);
509
	count_name(ss, ns);
510

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

static void sort_soft_dependencies(struct apk_solver_state *ss, struct apk_package *pkg)
{
	struct apk_package_state *ps;

	sort_hard_dependencies(ss, pkg);

	ps = pkg_to_ps(pkg);
523
	if (ps->topology_soft != pkg->topology_hard)
524
		return;
Timo Teräs's avatar
Timo Teräs committed
525
	ps->topology_soft = -1;
526
527
528
529
530
531
532
533
534

	/* Soft reverse dependencies aka. install_if */
	foreach_rinstall_if_pkg(ss, pkg, sort_hard_dependencies);
	foreach_dependency_pkg(ss, pkg->depends, sort_soft_dependencies);

	/* 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);
535
536
}

537
538
static void recalculate_maybe(struct apk_solver_state *ss, struct apk_name *name,
			      unsigned short flags, unsigned short pinning)
Timo Teräs's avatar
Timo Teräs committed
539
{
540
541
	struct apk_name_state *ns = name_to_ns_alloc(name);
	int propagate = FALSE;
Timo Teräs's avatar
Timo Teräs committed
542
543
	int i, j;

544
545
546
547
548
549
550
551
552
	if ((ns->maybe_pinning & pinning) != pinning) {
		ns->maybe_pinning |= pinning;
		propagate = TRUE;
	}
	if ((ns->solver_flags_maybe & flags) != flags) {
		ns->solver_flags_maybe |= flags;
		propagate = TRUE;
	}
	if (!propagate)
Timo Teräs's avatar
Timo Teräs committed
553
554
		return;

555
556
	for (i = 0; i < name->pkgs->num; i++) {
		struct apk_package *pkg = name->pkgs->item[i];
Timo Teräs's avatar
Timo Teräs committed
557

558
559
560
561
		for (j = 0; j < pkg->depends->num; j++) {
			struct apk_dependency *dep = &pkg->depends->item[j];
			struct apk_name *name0 = dep->name;
			recalculate_maybe(ss, name0, flags, pinning);
Timo Teräs's avatar
Timo Teräs committed
562
		}
563
	}
Timo Teräs's avatar
Timo Teräs committed
564

565
566
567
	for (i = 0; i < name->rinstall_if->num; i++) {
		struct apk_name *name0 = name->rinstall_if->item[i];
		recalculate_maybe(ss, name0, flags, pinning);
Timo Teräs's avatar
Timo Teräs committed
568
	}
569
570
}

571
572
573
574
575
576
577
578
static void sort_name(struct apk_solver_state *ss, struct apk_name *name)
{
	struct apk_name_state *ns = name_to_ns_alloc(name);
	int i;

	for (i = 0; i < name->pkgs->num; i++)
		sort_soft_dependencies(ss, name->pkgs->item[i]);

579
	count_name(ss, ns);
580
581
582
583
584
	recalculate_maybe(ss, name,
			  ns->solver_flags_local & ns->solver_flags_local_mask,
			  ns->maybe_pinning);
}

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

593
594
static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg)
{
Timo Teräs's avatar
Timo Teräs committed
595
	struct apk_name_state *ns;
596
597
598
599
600
	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
601
		ns = name_to_ns(dep->name);
602
603
604
605

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

	return missing;
}

612
613
614
615
616
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){
617
		.conflicts = ns->requirers,
618
619
620
621
		.preference = name->pkgs->num,
	};
}

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

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

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

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

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

642
643
	if (ns->locked)
		return;
644

645
646
647
648
	/* remove cached information */
	subscore(&ss->minimum_penalty, &ns->minimum_penalty);
	ns->minimum_penalty = (struct apk_score) { .score = 0 };
	ns->chosen = NULL;
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
658
	} else {
		ns->name_touched = 1;
659
	}
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
}

static void inherit_name_state(struct apk_database *db, struct apk_name *to, struct apk_name *from)
{
	struct apk_name_state *tns = name_to_ns(to);
	struct apk_name_state *fns = name_to_ns(from);
	int i;

	if ((fns->solver_flags_local & fns->solver_flags_local_mask & APK_SOLVERF_REINSTALL) ||
	    fns->inherited_reinstall)
		tns->inherited_reinstall++;

	if ((fns->solver_flags_local & fns->solver_flags_local_mask & APK_SOLVERF_UPGRADE) ||
	    fns->inherited_upgrade)
		tns->inherited_upgrade++;

	if (fns->allowed_pinning) {
		for (i = 0; i < db->num_repo_tags; i++) {
			if (!(fns->allowed_pinning & BIT(i)))
				continue;
			if (tns->inherited_pinning[i]++ == 0)
				tns->allowed_pinning |= BIT(i);
		}
683
	}
684
}
685

686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
static void uninherit_name_state(struct apk_database *db, struct apk_name *to, struct apk_name *from)
{
	struct apk_name_state *tns = name_to_ns(to);
	struct apk_name_state *fns = name_to_ns(from);
	int i;

	if ((fns->solver_flags_local & fns->solver_flags_local_mask & APK_SOLVERF_REINSTALL) ||
	    fns->inherited_reinstall)
		tns->inherited_reinstall--;

	if ((fns->solver_flags_local & fns->solver_flags_local_mask & APK_SOLVERF_UPGRADE) ||
	    fns->inherited_upgrade)
		tns->inherited_upgrade--;

	if (fns->allowed_pinning) {
		for (i = 0; i < db->num_repo_tags; i++) {
			if (!(fns->allowed_pinning & BIT(i)))
				continue;
			if (--tns->inherited_pinning[i] == 0)
				tns->allowed_pinning &= ~BIT(i);
		}
	}
708
709
}

710
711
712
713
static void trigger_install_if(struct apk_solver_state *ss,
			       struct apk_package *pkg)
{
	if (install_if_missing(ss, pkg) == 0) {
714
		struct apk_name *name0 = decision_to_name(&ss->decisions[ss->num_decisions]);
715
		struct apk_name_state *ns = name_to_ns(pkg->name);
716
717
718
719

		dbg_printf("trigger_install_if: " PKG_VER_FMT " triggered\n",
			   PKG_VER_PRINTF(pkg));
		ns->install_ifs++;
720
		inherit_name_state(ss->db, pkg->name, name0);
721
		promote_name(ss, pkg->name);
722
723
724
725
726
727
728
	}
}

static void untrigger_install_if(struct apk_solver_state *ss,
			       struct apk_package *pkg)
{
	if (install_if_missing(ss, pkg) != 1) {
729
		struct apk_name *name0 = decision_to_name(&ss->decisions[ss->num_decisions]);
Timo Teräs's avatar
Timo Teräs committed
730
		struct apk_name_state *ns = name_to_ns(pkg->name);
731
732
733
734

		dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n",
			   PKG_VER_PRINTF(pkg));
		ns->install_ifs--;
735
		uninherit_name_state(ss->db, pkg->name, name0);
736
		demote_name(ss, pkg->name);
737
738
739
	}
}

Timo Teräs's avatar
Timo Teräs committed
740
static solver_result_t apply_decision(struct apk_solver_state *ss,
741
				      struct apk_decision *d)
742
{
743
	struct apk_name *name = decision_to_name(d);
Timo Teräs's avatar
Timo Teräs committed
744
	struct apk_name_state *ns = name_to_ns(name);
745
746
	struct apk_package *pkg = decision_to_pkg(d);
	struct apk_score score;
747

748
	ns->name_touched = 1;
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
	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");

		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
770
771
		}

772
773
		if (d->type == DECISION_ASSIGN) {
			subscore(&ss->minimum_penalty, &ns->minimum_penalty);
774
			ns->minimum_penalty = (struct apk_score) { .score = 0 };
775

776
777
			ns->locked = 1;
			get_topology_score(ss, ns, pkg, &score);
778
779
			addscore(&ss->score, &score);

780
			if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) >= 0) {
781
782
783
784
785
786
787
				dbg_printf("install causing "SCORE_FMT", penalty too big: "SCORE_FMT"+"SCORE_FMT">="SCORE_FMT"\n",
					   SCORE_PRINTF(&score),
					   SCORE_PRINTF(&ss->score),
					   SCORE_PRINTF(&ss->minimum_penalty),
					   SCORE_PRINTF(&ss->best_score));

				subscore(&ss->score, &score);
788
789
				ns->locked = 0;

790
791
				return SOLVERR_PRUNED;
			}
792

793
794
			ss->assigned_names++;
			ns->chosen = pkg;
795

796
797
798
799
800
801
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);

			foreach_dependency(ss, pkg->depends, apply_constraint);
			foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
		}
802
	} else {
803
804
805
806
807
		dbg_printf("-->apply_decision: %s %s NOTHING\n",
			   name->name,
			   (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");

		if (d->type == DECISION_ASSIGN) {
Timo Teräs's avatar
Timo Teräs committed
808
			subscore(&ss->minimum_penalty, &ns->minimum_penalty);
809
			ns->minimum_penalty = (struct apk_score) { .score = 0 };
Timo Teräs's avatar
Timo Teräs committed
810

811
812
			get_unassigned_score(name, &score);
			addscore(&ss->score, &score);
Timo Teräs's avatar
Timo Teräs committed
813

814
			ns->chosen = NULL;
Timo Teräs's avatar
Timo Teräs committed
815
			ns->locked = 1;
816
817
818
819
820
821
822
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
		} else {
			ns->none_excluded = 1;
		}
	}

Timo Teräs's avatar
Timo Teräs committed
823
	if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) >= 0) {
824
825
826
827
828
829
		dbg_printf("%s: %s penalty too big: "SCORE_FMT"+"SCORE_FMT">="SCORE_FMT"\n",
			name->name,
			(d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE",
			SCORE_PRINTF(&ss->score),
			SCORE_PRINTF(&ss->minimum_penalty),
			SCORE_PRINTF(&ss->best_score));
Timo Teräs's avatar
Timo Teräs committed
830
		return SOLVERR_PRUNED;
831
	}
Timo Teräs's avatar
Timo Teräs committed
832
833

	return SOLVERR_EXPAND;
834
835
836
}

static void undo_decision(struct apk_solver_state *ss,
837
			  struct apk_decision *d)
838
{
839
	struct apk_name *name = decision_to_name(d);
840
	struct apk_name_state *ns = name_to_ns(name);
841
842
	struct apk_package *pkg = decision_to_pkg(d);
	struct apk_score score;
843

844
	ns->name_touched = 1;
845

846
847
	if (pkg != NULL) {
		struct apk_package_state *ps = pkg_to_ps(pkg);
848

849
850
851
852
853
854
855
856
857
858
		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;
		}
859

Timo Teräs's avatar
Timo Teräs committed
860
		if (ns->locked) {
Timo Teräs's avatar
Timo Teräs committed
861
862
863
			ss->assigned_names--;
			foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
			foreach_dependency(ss, pkg->depends, undo_constraint);
864

865
			get_topology_score(ss, ns, pkg, &score);
866
			subscore(&ss->score, &score);
867
		}
868
		ps->locked = 0;
Timo Teräs's avatar
Timo Teräs committed
869
	} else {
870
871
872
873
874
875
876
877
878
		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;
879
		}
880
	}
881

882
883
	ns->locked = 0;
	ns->chosen = NULL;
884

885
886
	/* Put back the name to unsolved list */
	promote_name(ss, name);
887
888
}

889
890
891
892
893
894
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)
895
{
896
	struct apk_decision *d;
897

898
899
	ASSERT(ss->num_decisions <= ss->max_decisions,
	       "Decision tree overflow.\n");
900

901
902
903
904
905
	ss->num_decisions++;
	d = &ss->decisions[ss->num_decisions];

#ifdef DEBUG_CHECKS
	d->saved_score = ss->score;
906
	d->saved_requirers = name_to_ns(name)->requirers;
907
908
909
910
#endif
	d->type = primary_decision;
	d->branching_point = branching_point;
	d->topology_position = topology_position;
911
	d->found_solution = 0;
912
913
914
	if (pkg == NULL) {
		d->name = name;
		d->no_package = 1;
915
	} else {
916
917
		d->pkg = pkg;
		d->no_package = 0;
918
	}
919

920
	return apply_decision(ss, d);
921
922
923
924
}

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

927
928
	while (ss->num_decisions > 0) {
		struct apk_decision *d = &ss->decisions[ss->num_decisions];
929
930
		struct apk_name *name = decision_to_name(d);
		struct apk_name_state *ns = name_to_ns(name);
931

932
		undo_decision(ss, d);
933

934
935
936
937
938
#ifdef DEBUG_CHECKS
		ASSERT(cmpscore(&d->saved_score, &ss->score) == 0,
			"ERROR! saved_score "SCORE_FMT" != score "SCORE_FMT"\n",
			SCORE_PRINTF(&d->saved_score),
			SCORE_PRINTF(&ss->score));
939
940
		ASSERT(d->saved_requirers == ns->requirers,
			"ERROR! requirers not restored between decisions\n");
941
#endif
942

943
944
		if (backup_until >= ss->num_decisions &&
		    d->branching_point == BRANCH_YES) {
945
946
947
			d->branching_point = BRANCH_NO;
			d->type = (d->type == DECISION_ASSIGN) ? DECISION_EXCLUDE : DECISION_ASSIGN;
			return apply_decision(ss, d);
948
		}
949

950
951
952
953
954
		if (d->no_package && !d->found_solution) {
			if (ns->last_touched_decision < backup_until)
				backup_until = ns->last_touched_decision;
		}

955
		ss->num_decisions--;
956
	}
957

Timo Teräs's avatar
Timo Teräs committed
958
959
	dbg_printf("-->next_branch: no more branches\n");
	return SOLVERR_STOP;
960
961
}

962
static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
963
964
{
	struct apk_name *name = dep->name;
Timo Teräs's avatar
Timo Teräs committed
965
	struct apk_name_state *ns = name_to_ns(name);
966
967
968
969
970
971
972
973
974
	int i, strength;

	if (ss->num_decisions > 0) {
		struct apk_name *name0 = decision_to_name(&ss->decisions[ss->num_decisions]);
		struct apk_name_state *ns0 = name_to_ns(name0);
		strength = ns0->requirers ?: 1;
	} else {
		strength = 1;
	}
975

Timo Teräs's avatar
Timo Teräs committed
976
	if (ns->locked) {
Timo Teräs's avatar
Timo Teräs committed
977
978
		if (ns->chosen)
			dbg_printf("%s: locked to " PKG_VER_FMT " already\n",
979
				   name->name, PKG_VER_PRINTF(ns->chosen));
Timo Teräs's avatar
Timo Teräs committed
980
981
		else
			dbg_printf("%s: locked to empty\n",
982
				   name->name);
983
		if (!apk_dep_is_satisfied(dep, ns->chosen))
984
			ss->score.conflicts += strength;
985
986
		return;
	}
987
988
	if (name->pkgs->num == 0) {
		if (!dep->optional)
989
			ss->score.conflicts += strength;
990
991
		return;
	}
992

993
	if (dep->repository_tag) {
994
		dbg_printf("%s: adding pinnings %d\n",
995
			   dep->name->name, dep->repository_tag);
996
997
		ns->preferred_pinning = BIT(dep->repository_tag);
		ns->allowed_pinning |= BIT(dep->repository_tag);
998
999
		ns->inherited_pinning[dep->repository_tag]++;
		recalculate_maybe(ss, name, 0, ns->allowed_pinning);
1000
	}