solver.c 52.6 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
21
22
23
//#define DEBUG_PRINT
#define DEBUG_CHECKS

#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
42
43
44
45
46
47
48
49
50
51
52
53
	union {
		struct {
#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
			unsigned short preference;
			unsigned short non_preferred_actions;
			unsigned int conflicts;
#elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
			unsigned int conflicts;
			unsigned short non_preferred_actions;
			unsigned short preference;
#else
#error Unknown endianess.
#endif
		};
		uint64_t score;
	};
Timo Teräs's avatar
Timo Teräs committed
54
};
55

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

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

	unsigned no_package : 1;
	unsigned type : 1;
	unsigned branching_point : 1;
	unsigned topology_position : 1;
83
	unsigned found_solution : 1;
84
85
};

86
struct apk_package_state {
87
	unsigned int topology_soft;
88
	unsigned short conflicts;
89
	unsigned char preference;
90
91
	unsigned handle_install_if : 1;
	unsigned locked : 1;
92
93
94
95
};

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

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

103
	/* set on startup */
104
	unsigned short preferred_pinning;
105
106
107
108
	unsigned short maybe_pinning;

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

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

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

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

struct apk_solver_state {
	struct apk_database *db;
133
	struct apk_decision *decisions;
134

135
	struct list_head unsolved_list_head;
136
137
138

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

142
	struct apk_solution_array *best_solution;
143
144
145

	struct apk_score score;
	struct apk_score minimum_penalty;
Timo Teräs's avatar
Timo Teräs committed
146
	struct apk_score best_score;
147
148

	unsigned solver_flags : 4;
149
150
};

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

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

167
#if 0
168
169
static void addscore(struct apk_score *a, struct apk_score *b)
{
170
171
	a->conflicts += b->conflicts;
	a->non_preferred_actions += b->non_preferred_actions;
172
173
174
175
176
	a->preference += b->preference;
}

static void subscore(struct apk_score *a, struct apk_score *b)
{
177
178
	a->conflicts -= b->conflicts;
	a->non_preferred_actions -= b->non_preferred_actions;
179
180
181
	a->preference -= b->preference;
}

182
static inline int cmpscore(struct apk_score *a, struct apk_score *b)
183
{
184
185
186
187
188
189
	if (a->conflicts < b->conflicts)
		return -1;
	if (a->conflicts > b->conflicts)
		return 1;

	if (a->non_preferred_actions < b->non_preferred_actions)
190
		return -1;
191
	if (a->non_preferred_actions > b->non_preferred_actions)
192
		return 1;
193

194
195
196
197
	if (a->preference < b->preference)
		return -1;
	if (a->preference > b->preference)
		return 1;
198

199
200
201
	return 0;
}

202
static inline int cmpscore2(struct apk_score *a1, struct apk_score *a2, struct apk_score *b)
203
{
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
	if (a1->conflicts + a2->conflicts < b->conflicts)
		return -1;
	if (a1->conflicts + a2->conflicts > b->conflicts)
		return 1;

	if (a1->non_preferred_actions + a2->non_preferred_actions < b->non_preferred_actions)
		return -1;
	if (a1->non_preferred_actions + a2->non_preferred_actions > b->non_preferred_actions)
		return 1;

	if (a1->preference + a2->preference < b->preference)
		return -1;
	if (a1->preference + a2->preference > b->preference)
		return 1;

	return 0;
220
}
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
#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;
}

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;
}
#endif
248
249
250
251
252
253
254
255
256
257
258
259
260

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;
261
262
}

Timo Teräs's avatar
Timo Teräs committed
263
static struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
264
265
266
267
{
	return (struct apk_package_state*) pkg->state_ptr;
}

Timo Teräs's avatar
Timo Teräs committed
268
static struct apk_name_state *name_to_ns(struct apk_name *name)
269
270
271
272
273
{
	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
274
{
Timo Teräs's avatar
Timo Teräs committed
275
	struct apk_name_state *ns;
276
	int i;
Timo Teräs's avatar
Timo Teräs committed
277
278
279
280

	if (name->state_ptr == NULL) {
		ns = calloc(1, sizeof(struct apk_name_state));
		ns->name = name;
281
282
283
284
285
286
		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
287
288
289
290
291
		name->state_ptr = ns;
	} else {
		ns = (struct apk_name_state*) name->state_ptr;
	}
	return ns;
Timo Teräs's avatar
Timo Teräs committed
292
293
}

294
static inline int pkg_available(struct apk_database *db, struct apk_package *pkg)
295
{
296
	/* virtual packages - only deps used; no real .apk */
297
298
	if (pkg->installed_size == 0)
		return TRUE;
299
	/* obviously present */
300
	if (pkg->in_cache || pkg->filename != NULL || (pkg->repos & db->local_repos))
301
302
303
		return TRUE;
	/* can download */
	if ((pkg->repos & ~db->bad_repos) && !(apk_flags & APK_NO_NETWORK))
304
305
306
307
		return TRUE;
	return FALSE;
}

308
309
310
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))
311
312
313
{
	int i, j;

314
315
316
	/* And sort the main dependencies */
	for (i = 0; i < depends->num; i++) {
		struct apk_dependency *dep = &depends->item[i];
317
318
319
320
		struct apk_name *name0 = dep->name;

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

322
			/* conflict depends on all to be not installed */
323
			if (!apk_dep_is_satisfied(dep, pkg0))
324
				continue;
325
326

			cb(ss, pkg0);
327
328
		}
	}
329
}
330

331
332
333
334
335
336
337
338
339
340
341
342
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);
343

344
345
346
347
348
349
		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 &&
350
				    apk_dep_is_satisfied(dep, pkg))
351
352
353
354
355
356
357
358
359
360
361
					break;
			}
			if (k >= pkg0->install_if->num)
				continue;

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

362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
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;
}

static void get_topology_score(
		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;

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

393
394
395
396
	if (ss->solver_flags & APK_SOLVERF_AVAILABLE) {
		/* not upgrading: it is not preferred to change package */
		if ((pkg->repos == 0) && ns->has_available_pkgs)
			score.non_preferred_actions++;
397
398
399
400
401
402
	} 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++;
	} else if ((ns->inherited_upgrade == 0) &&
403
404
		   ((ns->solver_flags_local|ss->solver_flags) & APK_SOLVERF_UPGRADE) == 0 &&
		   ((ns->solver_flags_maybe & APK_SOLVERF_UPGRADE) == 0 || (ps->locked))) {
405
406
407
408
409
410
411
412
413
414
415
416
		/* not upgrading: it is not preferred to change package */
		if (pkg->ipkg == NULL && ns->originally_installed)
			score.non_preferred_actions++;
	}

	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))
		score.non_preferred_actions++;

417
	if (ns->locked || (ns->allowed_pinning | ns->maybe_pinning) == ns->allowed_pinning) {
418
		allowed_pinning = ns->allowed_pinning | preferred_pinning | APK_DEFAULT_PINNING_MASK;
419
420
		allowed_repos = get_pinning_mask_repos(ss->db, allowed_pinning);
		if (!(repos & allowed_repos))
421
			score.non_preferred_actions+=2;
422
423
424
425
426
427
428
429
430
431
432
433
434
	}

	*_score = score;
}

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;

435
	get_topology_score(ss, ns, pkg, &score);
436
437
438
439
440
441
442
443
444
445
446
447
	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;

448
		get_topology_score(ss, ns, pkg0, &score0);
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
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
		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++;
	}
}

500
501
502
503
504
505
506
507
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;
	}
}

508
509
510
static void sort_hard_dependencies(struct apk_solver_state *ss, struct apk_package *pkg)
{
	struct apk_package_state *ps;
511
	struct apk_name_state *ns;
512
513
514
515
516

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

	ps = pkg_to_ps(pkg);
517
	if (ps->topology_soft)
518
		return;
519
	pkg->topology_hard = -1;
520
	ps->topology_soft = -1;
521

522
	calculate_pkg_preference(pkg);
523
524
525
526
	/* Consider hard dependencies only */
	foreach_dependency_pkg(ss, pkg->depends, sort_hard_dependencies);
	foreach_dependency_pkg(ss, pkg->install_if, sort_hard_dependencies);

527
	ss->max_decisions++;
528
	ns = name_to_ns_alloc(pkg->name);
529
	count_name(ss, ns);
530

531
	ps->topology_soft = pkg->topology_hard = ++ss->num_topology_positions;
532
	dbg_printf(PKG_VER_FMT ": topology_hard=%d\n",
533
		   PKG_VER_PRINTF(pkg), pkg->topology_hard);
534
535
536
537
538
539
540
541
542
}

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);
543
	if (ps->topology_soft != pkg->topology_hard)
544
		return;
Timo Teräs's avatar
Timo Teräs committed
545
	ps->topology_soft = -1;
546
547
548
549
550
551
552
553
554

	/* 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);
555
556
}

557
558
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
559
{
560
561
	struct apk_name_state *ns = name_to_ns_alloc(name);
	int propagate = FALSE;
Timo Teräs's avatar
Timo Teräs committed
562
563
	int i, j;

564
565
566
567
568
569
570
571
572
	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
573
574
		return;

575
576
	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
577

578
579
580
581
		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
582
		}
583
	}
Timo Teräs's avatar
Timo Teräs committed
584

585
586
587
	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
588
	}
589
590
}

591
592
593
594
595
596
597
598
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]);

599
	count_name(ss, ns);
600
601
602
603
604
	recalculate_maybe(ss, name,
			  ns->solver_flags_local & ns->solver_flags_local_mask,
			  ns->maybe_pinning);
}

605
606
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))
607
{
608
	int i;
609
	for (i = 0; i < deps->num; i++)
610
		func(ss, &deps->item[i]);
611
612
}

613
614
static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg)
{
Timo Teräs's avatar
Timo Teräs committed
615
	struct apk_name_state *ns;
616
617
618
619
620
	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
621
		ns = name_to_ns(dep->name);
622
623
624
625

		/* 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))
626
627
628
629
630
631
			missing++;
	}

	return missing;
}

632
633
634
635
636
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){
637
		.conflicts = ns->requirers,
638
639
640
641
		.preference = name->pkgs->num,
	};
}

Timo Teräs's avatar
Timo Teräs committed
642
static int update_name_state(struct apk_solver_state *ss, struct apk_name *name)
643
{
Timo Teräs's avatar
Timo Teräs committed
644
	struct apk_name_state *ns = name_to_ns(name);
645
	struct apk_package *best_pkg = NULL, *preferred_pkg = NULL;
646
	struct apk_score preferred_score;
647
	unsigned int best_topology = 0;
648
	int i, options = 0;
649

Timo Teräs's avatar
Timo Teräs committed
650
651
652
	if (ns->locked)
		return ns->chosen != NULL;

653
	subscore(&ss->minimum_penalty, &ns->minimum_penalty);
654
	ns->minimum_penalty = (struct apk_score) { .score = 0 };
655

656
657
	ns->name_touched = 1;

658
	get_unassigned_score(name, &preferred_score);
659
660
	for (i = 0; i < name->pkgs->num; i++) {
		struct apk_package *pkg0 = name->pkgs->item[i];
661
		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
662
		struct apk_score pkg0_score;
663

664
		if (ps0 == NULL || ps0->locked ||
Timo Teräs's avatar
Timo Teräs committed
665
		    ss->topology_position < pkg0->topology_hard ||
666
		    (pkg0->ipkg == NULL && !pkg_available(ss->db, pkg0)))
Timo Teräs's avatar
Timo Teräs committed
667
668
			continue;

669
		/* preferred - currently most optimal for end solution */
670
		get_topology_score(ss, ns, pkg0, &pkg0_score);
671
672
673

		if (preferred_pkg == NULL ||
		    cmpscore(&pkg0_score, &preferred_score) < 0) {
674
			preferred_pkg = pkg0;
675
			preferred_score = pkg0_score;
676
677
		}

678
		/* next in topology order - next to get locked in */
679
680
681
		if (ps0->topology_soft < ss->topology_position &&
		    ps0->topology_soft > best_topology)
			best_pkg = pkg0, best_topology = ps0->topology_soft;
682
683
		else if (pkg0->topology_hard > best_topology)
			best_pkg = pkg0, best_topology = pkg0->topology_hard;
684
685

		options++;
686
	}
687

688
	if (ns->requirers == 0 && ns->install_ifs == 0) {
689
		/* No one really needs this name (anymore). */
690
691
692
		if (list_hashed(&ns->unsolved_list)) {
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
693
		}
694
695
696
697
698
699
700
701
702
703
704
705
706
707
		ns->chosen = NULL;
		dbg_printf("%s: not required\n", name->name);
		return options + 1;
	}

	if (!list_hashed(&ns->unsolved_list))
		list_add_tail(&ns->unsolved_list, &ss->unsolved_list_head);

	/* So far decided that something will be installed for this
	 * name. So assign the minimum penalty, and next position. */
	ns->chosen = best_pkg;
	ns->minimum_penalty = preferred_score;
	addscore(&ss->minimum_penalty, &ns->minimum_penalty);

708
	dbg_printf("%s:  min.pen. " SCORE_FMT ", %d requirers, %d install_ifs, %d options (next topology %d)\n",
709
710
		   name->name,
		   SCORE_PRINTF(&ns->minimum_penalty),
711
		   ns->requirers, ns->install_ifs,
712
713
714
715
716
717
		   options, best_topology);

	if (!ns->none_excluded) {
		dbg_printf("%s: none not excluded yet\n", name->name);
		return options + 1;
	}
Timo Teräs's avatar
Timo Teräs committed
718

719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
	return options;
}

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);
		}
743
	}
744
}
745

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

770
771
772
773
static void trigger_install_if(struct apk_solver_state *ss,
			       struct apk_package *pkg)
{
	if (install_if_missing(ss, pkg) == 0) {
774
		struct apk_name *name0 = decision_to_name(&ss->decisions[ss->num_decisions]);
775
		struct apk_name_state *ns = name_to_ns(pkg->name);
776
777
778
779

		dbg_printf("trigger_install_if: " PKG_VER_FMT " triggered\n",
			   PKG_VER_PRINTF(pkg));
		ns->install_ifs++;
780
		inherit_name_state(ss->db, pkg->name, name0);
Timo Teräs's avatar
Timo Teräs committed
781
		update_name_state(ss, pkg->name);
782
783
784
785
786
787
788
	}
}

static void untrigger_install_if(struct apk_solver_state *ss,
			       struct apk_package *pkg)
{
	if (install_if_missing(ss, pkg) != 1) {
789
		struct apk_name *name0 = decision_to_name(&ss->decisions[ss->num_decisions]);
Timo Teräs's avatar
Timo Teräs committed
790
		struct apk_name_state *ns = name_to_ns(pkg->name);
791
792
793
794

		dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n",
			   PKG_VER_PRINTF(pkg));
		ns->install_ifs--;
795
		uninherit_name_state(ss->db, pkg->name, name0);
Timo Teräs's avatar
Timo Teräs committed
796
		update_name_state(ss, pkg->name);
797
798
799
	}
}

Timo Teräs's avatar
Timo Teräs committed
800
static solver_result_t apply_decision(struct apk_solver_state *ss,
801
				      struct apk_decision *d)
802
{
803
	struct apk_name *name = decision_to_name(d);
Timo Teräs's avatar
Timo Teräs committed
804
	struct apk_name_state *ns = name_to_ns(name);
805
806
	struct apk_package *pkg = decision_to_pkg(d);
	struct apk_score score;
807

808
	ns->name_touched = 1;
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
	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
830
831
		}

832
833
		if (d->type == DECISION_ASSIGN) {
			subscore(&ss->minimum_penalty, &ns->minimum_penalty);
834
			ns->minimum_penalty = (struct apk_score) { .score = 0 };
835

836
837
			ns->locked = 1;
			get_topology_score(ss, ns, pkg, &score);
838
839
			addscore(&ss->score, &score);

840
			if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) >= 0) {
841
842
843
844
845
846
847
				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);
848
849
				ns->locked = 0;

850
851
				return SOLVERR_PRUNED;
			}
852

853
854
			ss->assigned_names++;
			ns->chosen = pkg;
855

856
857
858
859
860
861
			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);
		}
862
	} else {
863
864
865
866
867
		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
868
			subscore(&ss->minimum_penalty, &ns->minimum_penalty);
869
			ns->minimum_penalty = (struct apk_score) { .score = 0 };
Timo Teräs's avatar
Timo Teräs committed
870

871
872
			get_unassigned_score(name, &score);
			addscore(&ss->score, &score);
Timo Teräs's avatar
Timo Teräs committed
873

874
			ns->chosen = NULL;
Timo Teräs's avatar
Timo Teräs committed
875
			ns->locked = 1;
876
877
878
879
880
881
882
883
884
885
886
887
888
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
		} else {
			ns->none_excluded = 1;
		}
	}

	if (d->type == DECISION_EXCLUDE) {
		if (update_name_state(ss, name) == 0) {
			dbg_printf("%s: %s would prune name to empty\n",
				name->name,
				(d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
			return SOLVERR_PRUNED;
Timo Teräs's avatar
Timo Teräs committed
889
890
891
892
		}
	}

	if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) >= 0) {
893
894
895
896
897
898
		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
899
		return SOLVERR_PRUNED;
900
	}
Timo Teräs's avatar
Timo Teräs committed
901
902

	return SOLVERR_EXPAND;
903
904
905
}

static void undo_decision(struct apk_solver_state *ss,
906
			  struct apk_decision *d)
907
{
908
	struct apk_name *name = decision_to_name(d);
909
	struct apk_name_state *ns = name_to_ns(name);
910
911
	struct apk_package *pkg = decision_to_pkg(d);
	struct apk_score score;
912

913
	ns->name_touched = 1;
914

915
916
	if (pkg != NULL) {
		struct apk_package_state *ps = pkg_to_ps(pkg);
917

918
919
920
921
922
923
924
925
926
927
		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;
		}
928

Timo Teräs's avatar
Timo Teräs committed
929
		if (ns->locked) {
Timo Teräs's avatar
Timo Teräs committed
930
931
932
			ss->assigned_names--;
			foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
			foreach_dependency(ss, pkg->depends, undo_constraint);
933

934
			get_topology_score(ss, ns, pkg, &score);
935
			subscore(&ss->score, &score);
936
		}
937
		ps->locked = 0;
Timo Teräs's avatar
Timo Teräs committed
938
	} else {
939
940
941
942
943
944
945
946
947
		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;
948
		}
949
	}
950

951
952
	ns->locked = 0;
	ns->chosen = NULL;
953

954
	update_name_state(ss, name);
955
956
}

957
958
959
960
961
962
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)
963
{
964
	struct apk_decision *d;
965

966
967
	ASSERT(ss->num_decisions <= ss->max_decisions,
	       "Decision tree overflow.\n");
968

969
970
971
972
973
	ss->num_decisions++;
	d = &ss->decisions[ss->num_decisions];

#ifdef DEBUG_CHECKS
	d->saved_score = ss->score;
974
	d->saved_requirers = name_to_ns(name)->requirers;
975
976
977
978
#endif
	d->type = primary_decision;
	d->branching_point = branching_point;
	d->topology_position = topology_position;
979
	d->found_solution = 0;
980
981
982
	if (pkg == NULL) {
		d->name = name;
		d->no_package = 1;
983
	} else {
984
985
		d->pkg = pkg;
		d->no_package = 0;
986
	}
987

988
	return apply_decision(ss, d);
989
990
991
992
}

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

995
996
	while (ss->num_decisions > 0) {
		struct apk_decision *d = &ss->decisions[ss->num_decisions];
997
998
		struct apk_name *name = decision_to_name(d);
		struct apk_name_state *ns = name_to_ns(name);
999

1000
		undo_decision(ss, d);