solver.c 55.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
//#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
	unsigned short conflicts;
100
	unsigned char preference;
101
102
	unsigned handle_install_if : 1;
	unsigned locked : 1;
103
104

	unsigned solver_flags_maybe : 4;
105
106
};

107
108
#define CHOSEN_NONE	(struct apk_provider) { .pkg = NULL, .version = NULL }

109
struct apk_name_state {
110
	/* dynamic */
111
	struct list_head unsolved_list;
Timo Teräs's avatar
Timo Teräs committed
112
	struct apk_name *name;
113
	struct apk_provider chosen;
114

115
	unsigned int last_touched_decision;
116
	unsigned short requirers;
117
	unsigned short install_ifs;
118
	unsigned short preferred_pinning;
119
	unsigned short locked;
120

121
	/* one time prepare/finish flags */
122
	unsigned solver_flags_local : 4;
123
	unsigned solver_flags_inheritable : 4;
Timo Teräs's avatar
Timo Teräs committed
124

125
126
	unsigned decision_counted : 1;
	unsigned originally_installed : 1;
127
	unsigned has_available_pkgs : 1;
128
	unsigned in_changeset : 1;
129
	unsigned in_world_dependency : 1;
130
131
132

	/* dynamic state flags */
	unsigned none_excluded : 1;
133
	unsigned name_touched : 1;
134
135
136
137
};

struct apk_solver_state {
	struct apk_database *db;
138
	struct apk_decision *decisions;
139

140
	struct list_head unsolved_list_head;
141
142
143

	unsigned int num_topology_positions;
	unsigned int num_decisions, max_decisions;
144
145
	unsigned int topology_position;
	unsigned int assigned_names;
Timo Teräs's avatar
Timo Teräs committed
146

147
	struct apk_solution_array *best_solution;
148
149

	struct apk_score score;
Timo Teräs's avatar
Timo Teräs committed
150
	struct apk_score best_score;
151
152

	unsigned solver_flags : 4;
153
154
};

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

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

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

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

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;
}
218
219
220
221
222
223
224
225
226
227
228
229
230

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;
231
232
}

Timo Teräs's avatar
Timo Teräs committed
233
static struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
234
235
236
237
{
	return (struct apk_package_state*) pkg->state_ptr;
}

238
239
240
241
242
243
244
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
245
static struct apk_name_state *name_to_ns(struct apk_name *name)
246
247
248
249
250
{
	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
251
{
Timo Teräs's avatar
Timo Teräs committed
252
	struct apk_name_state *ns;
253
	int i;
Timo Teräs's avatar
Timo Teräs committed
254
255
256
257

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

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

285
static void foreach_dependency_pkg(
286
287
	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))
288
289
290
{
	int i, j;

291
292
293
	/* And sort the main dependencies */
	for (i = 0; i < depends->num; i++) {
		struct apk_dependency *dep = &depends->item[i];
294
295
		struct apk_name *name0 = dep->name;

296
297
		for (j = 0; j < name0->providers->num; j++) {
			struct apk_provider *p0 = &name0->providers->item[j];
298

299
			/* conflict depends on all to be not installed */
300
			if (!apk_dep_is_provided(dep, p0))
301
				continue;
302

303
			cb(ss, p0->pkg, parent_package);
304
305
		}
	}
306
}
307

308
309
static void foreach_rinstall_if_pkg(
	struct apk_solver_state *ss, struct apk_package *pkg,
310
	void (*cb)(struct apk_solver_state *ss, struct apk_package *rinstall_if, struct apk_package *parent_pkg))
311
312
313
314
315
316
317
318
319
{
	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);
320

321
322
323
324
325
		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];
326
327

				if (dep->name == name &&
328
				    apk_dep_is_provided(dep, p0))
329
330
					break;
			}
331
			if (k >= p0->pkg->install_if->num)
332
333
334
				continue;

			/* pkg depends (via install_if) on pkg0 */
335
			cb(ss, p0->pkg, pkg);
336
337
338
339
		}
	}
}

340
341
342
343
344
345
346
347
348
349
350
351
352
353
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;
}

354
static int get_topology_score(
355
356
357
358
359
360
361
362
363
364
		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;
365
	int score_locked = TRUE, sticky_installed = FALSE;
366
367
368
369
370
371

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

372
	if (ss->solver_flags & APK_SOLVERF_AVAILABLE) {
Timo Teräs's avatar
Timo Teräs committed
373
		/* available preferred */
374
375
		if ((pkg->repos == 0) && ns->has_available_pkgs)
			score.non_preferred_actions++;
376
	} else if (ps->inherited_reinstall ||
377
378
379
380
		   (((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++;
381
	} else if (ps->inherited_upgrade ||
Timo Teräs's avatar
Timo Teräs committed
382
383
		   ((ns->solver_flags_local|ss->solver_flags) & APK_SOLVERF_UPGRADE)) {
		/* upgrading - score is just locked here */
384
	} else if ((ps->inherited_upgrade == 0) &&
385
		   ((ns->solver_flags_local|ss->solver_flags) & APK_SOLVERF_UPGRADE) == 0 &&
386
		   ((ps->solver_flags_maybe & APK_SOLVERF_UPGRADE) == 0 || (ps->locked))) {
387
388
389
		/* not upgrading: it is not preferred to change package */
		if (pkg->ipkg == NULL && ns->originally_installed)
			score.non_preferred_actions++;
390
391
		else
			sticky_installed = TRUE;
392
393
	} else {
		score_locked = FALSE;
394
395
396
397
398
399
400
	}

	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))
401
		score.non_preferred_pinnings++;
402

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

	*_score = score;
416
	return score_locked;
417
418
419
420
421
422
423
424
425
426
}

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;

427
	get_topology_score(ss, ns, pkg, &score);
428
429
	for (i = 0; i < name->providers->num; i++) {
		struct apk_package *pkg0 = name->providers->item[i].pkg;
430
431
432
433
434
435
436
437
438
439
		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;

440
		get_topology_score(ss, ns, pkg0, &score0);
441
442
443
444
445
446
447
448
		if (cmpscore(&score0, &score) < 0)
			return 0;
	}

	return 1;
}

static int compare_absolute_package_preference(
449
450
		struct apk_provider *pA,
		struct apk_provider *pB)
451
{
452
453
454
	struct apk_package *pkgA = pA->pkg;
	struct apk_package *pkgB = pB->pkg;

455
456
457
458
459
460
461
462
	/* 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 */
463
	switch (apk_version_compare_blob(*pA->version, *pB->version)) {
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
	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);
484
	struct apk_provider p = APK_PROVIDER_FROM_PACKAGE(pkg);
485
	int i, j;
486

487
488
489
	for (i = 0; i < name->providers->num; i++) {
		struct apk_provider *p0 = &name->providers->item[i];
		if (pkg == p0->pkg)
490
			continue;
491
		if (compare_absolute_package_preference(&p, p0) < 0)
492
493
			ps->preference++;
	}
494
495
496
497
498
499
500
501
502
503
504
505
	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++;
		}
	}
506
507
}

508
static void count_name(struct apk_solver_state *ss, struct apk_name *name)
509
{
510
511
	struct apk_name_state *ns = name_to_ns_alloc(name);

512
513
514
515
516
517
	if (!ns->decision_counted) {
		ss->max_decisions++;
		ns->decision_counted = 1;
	}
}

518
519
520
static void sort_hard_dependencies(struct apk_solver_state *ss,
				   struct apk_package *pkg,
				   struct apk_package *parent_pkg)
521
522
{
	struct apk_package_state *ps;
523
	int i;
524

525
	ps = pkg_to_ps_alloc(pkg);
526
	if (ps->topology_soft)
527
		return;
528
	pkg->topology_hard = -1;
529
	ps->topology_soft = -1;
530

531
	calculate_pkg_preference(pkg);
532

533
	/* Consider hard dependencies only */
534
535
	foreach_dependency_pkg(ss, pkg, pkg->depends, sort_hard_dependencies);
	foreach_dependency_pkg(ss, pkg, pkg->install_if, sort_hard_dependencies);
536

537
	ss->max_decisions++;
538
539
540
	count_name(ss, pkg->name);
	for (i = 0; i < pkg->provides->num; i++)
		count_name(ss, pkg->provides->item[i].name);
541

542
	ps->topology_soft = pkg->topology_hard = ++ss->num_topology_positions;
543
	dbg_printf(PKG_VER_FMT ": topology_hard=%d\n",
544
		   PKG_VER_PRINTF(pkg), pkg->topology_hard);
545
546
}

547
548
549
static void sort_soft_dependencies(struct apk_solver_state *ss,
				   struct apk_package *pkg,
				   struct apk_package *parent_pkg)
550
551
{
	struct apk_package_state *ps;
552
	struct apk_package_state *parent_ps;
553

554
	sort_hard_dependencies(ss, pkg, parent_pkg);
555
556

	ps = pkg_to_ps(pkg);
557
	if (ps->topology_soft != pkg->topology_hard)
558
		return;
Timo Teräs's avatar
Timo Teräs committed
559
	ps->topology_soft = -1;
560

561
562
563
564
565
	/* 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;

566
567
	/* Soft reverse dependencies aka. install_if */
	foreach_rinstall_if_pkg(ss, pkg, sort_hard_dependencies);
568
	foreach_dependency_pkg(ss, pkg, pkg->depends, sort_soft_dependencies);
569
570
571
572
573

	/* 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);
574
575
}

576
static void sort_name(struct apk_solver_state *ss, struct apk_name *name)
Timo Teräs's avatar
Timo Teräs committed
577
{
578
	struct apk_name_state *ns = name_to_ns_alloc(name);
Timo Teräs's avatar
Timo Teräs committed
579
580
	int i, j;

581
582
	for (i = 0; i < name->providers->num; i++) {
		struct apk_package *pkg = name->providers->item[i].pkg;
583
584
585
586
587
		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
588

589
590
591
592
593
594
		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
595
596
		}

597
		sort_soft_dependencies(ss, name->providers->item[i].pkg, pkg);
Timo Teräs's avatar
Timo Teräs committed
598
	}
599
600
}

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

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

		/* ns can be NULL, if the install_if has a name with
		 * no packages */
621
622
		if (ns == NULL || !ns->locked ||
		    !apk_dep_is_provided(dep, &ns->chosen))
623
624
625
626
627
628
			missing++;
	}

	return missing;
}

629
630
631
632
633
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){
634
		.conflicts = ns->requirers,
635
		.preference = name->providers->num,
636
637
638
	};
}

639
static void promote_name(struct apk_solver_state *ss, struct apk_name *name)
640
{
Timo Teräs's avatar
Timo Teräs committed
641
	struct apk_name_state *ns = name_to_ns(name);
642

Timo Teräs's avatar
Timo Teräs committed
643
	if (ns->locked)
644
		return;
Timo Teräs's avatar
Timo Teräs committed
645

646
647
648
	/* queue for handling if needed */
	if (!list_hashed(&ns->unsolved_list))
		list_add_tail(&ns->unsolved_list, &ss->unsolved_list_head);
649

650
651
	/* update info, but no cached information flush is required, as
	 * minimum_penalty can only go up */
652
	ns->name_touched = 1;
653
}
654

655
656
657
static void demote_name(struct apk_solver_state *ss, struct apk_name *name)
{
	struct apk_name_state *ns = name_to_ns(name);
658

659
660
	if (ns->locked)
		return;
661

662
	/* remove cached information */
663
	ns->chosen = CHOSEN_NONE;
664

665
	/* and remove list, or request refresh */
666
	if (ns->requirers == 0 && ns->install_ifs == 0) {
667
668
669
		if (list_hashed(&ns->unsolved_list)) {
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
670
			dbg_printf("%s: not required\n", name->name);
671
		}
672
	} else {
673
674
		/* still needed, put back to list */
		promote_name(ss, name);
675
	}
676
677
}

678
static int inherit_package_state(struct apk_database *db, struct apk_package *to, struct apk_package *from)
679
{
680
681
682
683
684
685
686
687
688
689
	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;
	}
690

691
692
693
694
695
	if ((fns->solver_flags_inheritable & APK_SOLVERF_UPGRADE) ||
	    fps->inherited_upgrade) {
		tps->inherited_upgrade++;
		changed = 1;
	}
696

697
698
699
700
	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)))
701
				continue;
702
703
704
705
706
			allowed_pinning &= ~BIT(i);
			if (tps->inherited_pinning[i]++ == 0) {
				tps->allowed_pinning |= BIT(i);
				changed = 1;
			}
707
		}
708
	}
709
710

	return changed;
711
}
712

713
static void uninherit_package_state(struct apk_database *db, struct apk_package *to, struct apk_package *from)
714
{
715
716
717
	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);
718
719
	int i;

720
721
722
	if ((fns->solver_flags_inheritable & APK_SOLVERF_REINSTALL) ||
	    fps->inherited_reinstall)
		tps->inherited_reinstall--;
723

724
725
726
	if ((fns->solver_flags_inheritable & APK_SOLVERF_UPGRADE) ||
	    fps->inherited_upgrade)
		tps->inherited_upgrade--;
727

728
729
730
731
	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)))
732
				continue;
733
734
735
			allowed_pinning &= ~BIT(i);
			if (--tps->inherited_pinning[i] == 0)
				tps->allowed_pinning &= ~BIT(i);
736
737
		}
	}
738
739
}

740
static void trigger_install_if(struct apk_solver_state *ss,
741
742
			       struct apk_package *pkg,
			       struct apk_package *parent_pkg)
743
744
{
	if (install_if_missing(ss, pkg) == 0) {
745
		struct apk_name_state *ns = name_to_ns(pkg->name);
746
747
748
749

		dbg_printf("trigger_install_if: " PKG_VER_FMT " triggered\n",
			   PKG_VER_PRINTF(pkg));
		ns->install_ifs++;
750
		inherit_package_state(ss->db, pkg, parent_pkg);
751
		promote_name(ss, pkg->name);
752
753
754
755
	}
}

static void untrigger_install_if(struct apk_solver_state *ss,
756
757
			         struct apk_package *pkg,
			         struct apk_package *parent_pkg)
758
759
{
	if (install_if_missing(ss, pkg) != 1) {
Timo Teräs's avatar
Timo Teräs committed
760
		struct apk_name_state *ns = name_to_ns(pkg->name);
761
762
763
764

		dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n",
			   PKG_VER_PRINTF(pkg));
		ns->install_ifs--;
765
		uninherit_package_state(ss->db, pkg, parent_pkg);
766
		demote_name(ss, pkg->name);
767
768
769
	}
}

770
771
772
773
774
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);

775
776
777
778
779
780
	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");
	}
781
	ns->chosen = p;
782
	ns->locked++;
783
784
785
786
787
788
789
790
791
792
793
	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");
794
795
796
797
798
799
	ns->locked--;
	if (ns->locked == 0) {
		ns->chosen = CHOSEN_NONE;
		ns->name_touched = 1;
		demote_name(ss, name);
	}
800
801
}

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

811
	ns->name_touched = 1;
812
813
814
815
816
817
818
	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");

819
820
821
		for (i = 0; i < pkg->provides->num; i++)
			name_to_ns(pkg->provides->item[i].name)->name_touched = 1;

822
823
824
825
826
827
828
829
830
831
832
833
834
835
		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
836
837
		}

838
		if (d->type == DECISION_ASSIGN) {
839
			get_topology_score(ss, ns, pkg, &score);
840
841
842
			addscore(&ss->score, &score);

			ss->assigned_names++;
843
844
845
846
847
			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));
			}
848
849
850
851

			foreach_dependency(ss, pkg->depends, apply_constraint);
			foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
		}
852
	} else {
853
854
855
856
857
858
859
		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
860

861
			ns->chosen = CHOSEN_NONE;
Timo Teräs's avatar
Timo Teräs committed
862
			ns->locked = 1;
863
864
865
866
867
868
869
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
		} else {
			ns->none_excluded = 1;
		}
	}

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

	return SOLVERR_EXPAND;
880
881
882
}

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

891
	ns->name_touched = 1;
892

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

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

907
908
909
		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
910
		if (ns->locked) {
Timo Teräs's avatar
Timo Teräs committed
911
912
			foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
			foreach_dependency(ss, pkg->depends, undo_constraint);
913

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

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

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

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

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

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

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

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

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

981
982
	while (ss->num_decisions > 0) {
		struct apk_decision *d = &ss->decisions[ss->num_decisions];
983
984
		struct apk_name *name = decision_to_name(d);
		struct apk_name_state *ns = name_to_ns(name);
985

986
		undo_decision(ss, d);
987

988
989
#ifdef DEBUG_CHECKS
		ASSERT(cmpscore(&d->saved_score, &ss->score) == 0,
990
			"ERROR! saved_score "SCORE_FMT" != score "SCORE_FMT,
991
992
			SCORE_PRINTF(&d->saved_score),
			SCORE_PRINTF(&ss->score));
993
		ASSERT(d->saved_requirers == ns->requirers,
994
			"ERROR! requirers not restored between decisions");
995
#endif
996

997
998