solver.c 50.1 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
12
13
14
15
16
 * 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.
 */

#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
17
18
#include "apk_print.h"

19
20
21
22
//#define DEBUG_PRINT
#define DEBUG_CHECKS

#ifdef DEBUG_PRINT
23
24
25
26
27
28
#include <stdio.h>
#define dbg_printf(args...) fprintf(stderr, args)
#else
#define dbg_printf(args...)
#endif

29
30
31
32
33
34
#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
35
36

struct apk_score {
37
38
	unsigned short conflicts;
	unsigned short non_preferred_actions;
Timo Teräs's avatar
Timo Teräs committed
39
40
	unsigned short preference;
};
41

42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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;
#endif

	unsigned no_package : 1;
	unsigned type : 1;
	unsigned branching_point : 1;
	unsigned topology_position : 1;
};

70
struct apk_package_state {
71
	unsigned int topology_soft;
72
	unsigned short conflicts;
73
	unsigned char preference;
Timo Teräs's avatar
Timo Teräs committed
74
75
76
	unsigned availability_checked : 1;
	unsigned unavailable : 1;
	unsigned install_applied : 1;
77
78
	unsigned handle_install_if : 1;
	unsigned locked : 1;
79
80
81
82
};

struct apk_name_state {
	struct list_head unsolved_list;
Timo Teräs's avatar
Timo Teräs committed
83
	struct apk_name *name;
84
	struct apk_package *chosen;
85

86
	struct apk_score minimum_penalty;
87
88
	unsigned short merge_index;
	unsigned short prerequires;
89
	unsigned short requirers;
90
	unsigned short install_ifs;
Timo Teräs's avatar
Timo Teräs committed
91

92
93
94
	unsigned short preferred_pinning;
	unsigned short allowed_pinning;

95
96
97
	unsigned solver_flags_local : 4;
	unsigned solver_flags_local_mask : 4;
	unsigned solver_flags_inherited : 4;
Timo Teräs's avatar
Timo Teräs committed
98

99
100
101
102
103
104
105
106
107
	/* one time prepare/finish flags */
	unsigned decision_counted : 1;
	unsigned originally_installed : 1;
	unsigned prepared : 1;
	unsigned in_changeset : 1;

	/* dynamic state flags */
	unsigned none_excluded : 1;
	unsigned locked : 1;
108
109
110
111
};

struct apk_solver_state {
	struct apk_database *db;
112
	struct apk_decision *decisions;
113

114
	struct list_head unsolved_list_head;
115
116
117

	unsigned int num_topology_positions;
	unsigned int num_decisions, max_decisions;
118
119
	unsigned int topology_position;
	unsigned int assigned_names;
Timo Teräs's avatar
Timo Teräs committed
120

121
	struct apk_solution_array *best_solution;
122
123
124

	struct apk_score score;
	struct apk_score minimum_penalty;
Timo Teräs's avatar
Timo Teräs committed
125
	struct apk_score best_score;
126
127
128

	unsigned solver_flags : 4;
	unsigned impossible_constraints : 1;
129
130
};

Timo Teräs's avatar
Timo Teräs committed
131
132
133
134
135
136
137
typedef enum {
	SOLVERR_SOLUTION = 0,
	SOLVERR_PRUNED,
	SOLVERR_EXPAND,
	SOLVERR_STOP,
} solver_result_t;

138
139
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);
140
141
142
143
144
145
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);
146

147
148
static void addscore(struct apk_score *a, struct apk_score *b)
{
149
150
	a->conflicts += b->conflicts;
	a->non_preferred_actions += b->non_preferred_actions;
151
152
153
154
155
	a->preference += b->preference;
}

static void subscore(struct apk_score *a, struct apk_score *b)
{
156
157
	a->conflicts -= b->conflicts;
	a->non_preferred_actions -= b->non_preferred_actions;
158
159
160
161
162
	a->preference -= b->preference;
}

static int cmpscore(struct apk_score *a, struct apk_score *b)
{
163
164
165
166
167
168
	if (a->conflicts < b->conflicts)
		return -1;
	if (a->conflicts > b->conflicts)
		return 1;

	if (a->non_preferred_actions < b->non_preferred_actions)
169
		return -1;
170
	if (a->non_preferred_actions > b->non_preferred_actions)
171
		return 1;
172

173
174
175
176
	if (a->preference < b->preference)
		return -1;
	if (a->preference > b->preference)
		return 1;
177

178
179
180
181
182
	return 0;
}

static int cmpscore2(struct apk_score *a1, struct apk_score *a2, struct apk_score *b)
{
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
	struct apk_score tmp = *a1;
	addscore(&tmp, a2);
	return cmpscore(&tmp, b);
}

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;
200
201
}

Timo Teräs's avatar
Timo Teräs committed
202
static struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
203
204
205
206
{
	return (struct apk_package_state*) pkg->state_ptr;
}

Timo Teräs's avatar
Timo Teräs committed
207
208
static struct apk_name_state *name_to_ns(struct apk_name *name)
{
Timo Teräs's avatar
Timo Teräs committed
209
210
211
212
213
214
215
216
217
218
	struct apk_name_state *ns;

	if (name->state_ptr == NULL) {
		ns = calloc(1, sizeof(struct apk_name_state));
		ns->name = name;
		name->state_ptr = ns;
	} else {
		ns = (struct apk_name_state*) name->state_ptr;
	}
	return ns;
Timo Teräs's avatar
Timo Teräs committed
219
220
}

221
222
223
224
225
226
227
228
229
230
231
static inline int pkg_available(struct apk_database *db, struct apk_package *pkg)
{
	if (pkg->installed_size == 0)
		return TRUE;
	if (pkg->filename != NULL)
		return TRUE;
	if (apk_db_select_repo(db, pkg) != NULL)
		return TRUE;
	return FALSE;
}

232
233
234
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))
235
236
237
{
	int i, j;

238
239
240
	/* And sort the main dependencies */
	for (i = 0; i < depends->num; i++) {
		struct apk_dependency *dep = &depends->item[i];
241
242
243
244
		struct apk_name *name0 = dep->name;

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

246
			/* conflict depends on all to be not installed */
247
			if (!apk_dep_is_satisfied(dep, pkg0))
248
				continue;
249
250

			cb(ss, pkg0);
251
252
		}
	}
253
}
254

255
256
257
258
259
260
261
262
263
264
265
266
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);
267

268
269
270
271
272
273
		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 &&
274
				    apk_dep_is_satisfied(dep, pkg))
275
276
277
278
279
280
281
282
283
284
285
					break;
			}
			if (k >= pkg0->install_if->num)
				continue;

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

286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
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
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
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,
		int lock_score,
		struct apk_score *_score)
{
	struct apk_name *name = pkg->name;
	struct apk_package_state *ps = pkg_to_ps(pkg);
	struct apk_score score;
	unsigned short name_flags;
	unsigned int repos;
	unsigned short preferred_pinning, allowed_pinning;
	unsigned int preferred_repos, allowed_repos;

	/* effective dynamic flags */
	name_flags = ns->solver_flags_local | ns->solver_flags_inherited | ss->solver_flags;

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

	if ((name_flags & APK_SOLVERF_AVAILABLE) && (pkg->repos == 0)) {
		score.non_preferred_actions ++;
		score.preference += name->pkgs->num;
	} else if (lock_score && !(name_flags & APK_SOLVERF_UPGRADE)) {
		/* not upgrading: it is not preferred to change package */
		struct apk_name_state *ns = name_to_ns(name);
		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++;

	if (lock_score) {
		allowed_pinning = ns->allowed_pinning | preferred_pinning;
		allowed_repos = get_pinning_mask_repos(ss->db, allowed_pinning);

		if (!(repos & allowed_repos))
			score.non_preferred_actions += 2;
	}

	*_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;

	/* FIXME: should not use absolute topology score */
	get_topology_score(ss, ns, pkg, 1, &score);
	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;

		get_topology_score(ss, ns, pkg0, 1, &score0);
		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++;
	}
}

425
426
427
static void sort_hard_dependencies(struct apk_solver_state *ss, struct apk_package *pkg)
{
	struct apk_package_state *ps;
428
	struct apk_name_state *ns;
429
430
431
432
433

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

	ps = pkg_to_ps(pkg);
434
	if (ps->topology_soft)
435
		return;
436
	pkg->topology_hard = -1;
437
	ps->topology_soft = -1;
438
	calculate_pkg_preference(pkg);
439
440
441
442
443

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

444
445
446
447
448
449
450
451
	ss->max_decisions++;

	ns = name_to_ns(pkg->name);
	if (!ns->decision_counted) {
		ss->max_decisions++;
		ns->decision_counted = 1;
	}

452
	ps->topology_soft = pkg->topology_hard = ++ss->num_topology_positions;
453
	dbg_printf(PKG_VER_FMT ": topology_hard=%d\n",
454
		   PKG_VER_PRINTF(pkg), pkg->topology_hard);
455
456
457
458
459
460
461
462
463
}

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);
464
	if (ps->topology_soft != pkg->topology_hard)
465
		return;
Timo Teräs's avatar
Timo Teräs committed
466
	ps->topology_soft = -1;
467
468
469
470
471
472
473
474
475

	/* 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);
476
477
478
479
480
481
482
}

static void sort_name(struct apk_solver_state *ss, struct apk_name *name)
{
	int i;

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

Timo Teräs's avatar
Timo Teräs committed
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
static void foreach_locked_reverse_dependency(
	struct apk_name *name,
	void (*cb)(struct apk_package *rdepend, void *ctx), void *ctx)
{
	int i, j;

	if (name == NULL)
		return;

	for (i = 0; i < name->rdepends->num; i++) {
		struct apk_name *name0 = name->rdepends->item[i];
		struct apk_name_state *ns0 = name_to_ns(name0);
		struct apk_package *pkg0 = ns0->chosen;

		if (!ns0->locked || ns0->chosen == NULL)
			continue;

		for (j = 0; j < pkg0->depends->num; j++) {
			struct apk_dependency *dep = &pkg0->depends->item[j];
			if (dep->name == name)
				break;
		}
		if (j >= pkg0->depends->num)
			continue;

		cb(pkg0, ctx);
	}
513
514
}

515
516
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))
517
{
518
	int i;
519
	for (i = 0; i < deps->num; i++)
520
		func(ss, &deps->item[i]);
521
522
}

523
524
static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg)
{
Timo Teräs's avatar
Timo Teräs committed
525
	struct apk_name_state *ns;
526
527
528
529
530
	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
531
		ns = name_to_ns(dep->name);
Timo Teräs's avatar
Timo Teräs committed
532
		if (!ns->locked || !apk_dep_is_satisfied(dep, ns->chosen))
533
534
535
536
537
538
			missing++;
	}

	return missing;
}

539
static int check_if_package_unavailable(struct apk_solver_state *ss, struct apk_package *pkg, int do_check)
Timo Teräs's avatar
Timo Teräs committed
540
541
542
543
544
545
546
547
548
549
550
551
{
	struct apk_name *name = pkg->name;
	struct apk_package_state *ps = pkg_to_ps(pkg);
	struct apk_name_state *ns = name_to_ns(name);

	/* installed and no-reinstall required? no check needed. */
	if ((pkg->ipkg != NULL) &&
	    ((ns->solver_flags_local | ns->solver_flags_inherited |
	      ss->solver_flags) & APK_SOLVERF_REINSTALL) == 0)
		return 0;

	/* done already? */
552
	if (ps->availability_checked && !do_check)
Timo Teräs's avatar
Timo Teräs committed
553
554
555
556
557
558
559
560
561
562
		return ps->unavailable;

	/* and it's not available, we can't use it */
	if (!pkg_available(ss->db, pkg))
		ps->unavailable = 1;

	ps->availability_checked = 1;
	return ps->unavailable;
}

563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
static void foreach_common_dependency(
		struct apk_solver_state *ss, struct apk_name *name,
		void (*cb)(struct apk_solver_state *ss, struct apk_name *common_dependency))
{
	struct apk_name *name0;
	struct apk_name_state *ns0;
	struct apk_package *pkg;
	struct apk_package_state *ps;
	struct apk_dependency *dep;
	int i, j, first_found = -1, last_found = 0;

	for (i = 0; i < name->pkgs->num; i++) {
		pkg = name->pkgs->item[i];
		ps = pkg_to_ps(pkg);
		if (ps == NULL || ps->locked)
			continue;
		if (first_found == -1)
			first_found = i;
		for (j = 0; j < pkg->depends->num; j++) {
			dep = &pkg->depends->item[j];
			if (dep->optional)
				continue;
			name0 = dep->name;
			ns0   = name_to_ns(name0);
			if (ns0->merge_index == last_found)
				ns0->merge_index = i + 1;
		}
		last_found = i + 1;
	}
	if (first_found == -1)
		return;

	pkg = name->pkgs->item[first_found];
	for (j = 0; j < pkg->depends->num; j++) {
		dep = &pkg->depends->item[j];
		if (dep->optional)
			continue;
		name0 = dep->name;
		ns0   = name_to_ns(name0);
		if (ns0->merge_index == last_found)
			cb(ss, name0);
		ns0->merge_index = 0;
	}
}

#if 0
static void prepare_name(struct apk_solver_state *ss, struct apk_name *name)
{
	struct apk_name_state *ns = name_to_ns(name);
	int i, j;

	if (ns->prepared)
		return;
	ns->prepared = 1;

	for (i = 0; i < name->pkgs->num; i++) {
		struct apk_package *pkg = name->pkgs->item[i];
		if (pkg_to_ps(pkg) == NULL)
			continue;
		for (j = 0; j < pkg->depends->num; j++) {
			struct apk_dependency *dep = &pkg->depends->item[j];
			prepare_name(ss, dep->name);
		}
	}
}
#endif

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){
		.conflicts = ns->requirers + ns->prerequires,
		.preference = name->pkgs->num,
	};
}

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

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

651
652
653
	subscore(&ss->minimum_penalty, &ns->minimum_penalty);
	ns->minimum_penalty = (struct apk_score) { 0, 0 };

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

660
		if (ps0 == NULL || ps0->locked ||
Timo Teräs's avatar
Timo Teräs committed
661
		    ss->topology_position < pkg0->topology_hard ||
662
		    check_if_package_unavailable(ss, pkg0, 0))
Timo Teräs's avatar
Timo Teräs committed
663
664
			continue;

665
		/* preferred - currently most optimal for end solution */
666
667
668
669
670
		/* FIXME: should not use absolute topology score */
		get_topology_score(ss, ns, pkg0, 1, &pkg0_score);

		if (preferred_pkg == NULL ||
		    cmpscore(&pkg0_score, &preferred_score) < 0) {
671
			preferred_pkg = pkg0;
672
			preferred_score = pkg0_score;
673
674
		}

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

		options++;
683
	}
684

685
686
	if (ns->prerequires == 0 && ns->requirers == 0 && ns->install_ifs == 0) {
		/* No one really needs this name (anymore). */
687
688
689
		if (list_hashed(&ns->unsolved_list)) {
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
690
		}
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
		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);

	dbg_printf("%s:  min.pen. " SCORE_FMT ", %d prerequirers, %d requirers, %d install_ifs, %d options (next topology %d)\n",
		   name->name,
		   SCORE_PRINTF(&ns->minimum_penalty),
		   ns->prerequires, ns->requirers, ns->install_ifs,
		   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
715

716
717
718
	if (options == 0) {
		ss->impossible_constraints = 1;
		dbg_printf("%s: impossible constraints\n", name->name);
719
720
	}

721
	return options;
722
723
}

724
725
726
727
static void trigger_install_if(struct apk_solver_state *ss,
			       struct apk_package *pkg)
{
	if (install_if_missing(ss, pkg) == 0) {
Timo Teräs's avatar
Timo Teräs committed
728
		struct apk_name_state *ns = ns = name_to_ns(pkg->name);
729
730
731
732

		dbg_printf("trigger_install_if: " PKG_VER_FMT " triggered\n",
			   PKG_VER_PRINTF(pkg));
		ns->install_ifs++;
Timo Teräs's avatar
Timo Teräs committed
733
		update_name_state(ss, pkg->name);
734
735
736
737
738
739
740
	}
}

static void untrigger_install_if(struct apk_solver_state *ss,
			       struct apk_package *pkg)
{
	if (install_if_missing(ss, pkg) != 1) {
Timo Teräs's avatar
Timo Teräs committed
741
		struct apk_name_state *ns = name_to_ns(pkg->name);
742
743
744
745

		dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n",
			   PKG_VER_PRINTF(pkg));
		ns->install_ifs--;
Timo Teräs's avatar
Timo Teräs committed
746
		update_name_state(ss, pkg->name);
747
748
749
	}
}

750
751
752
753
754
755
756
757
758
759
760
761
762
763
static void increment_prerequires(struct apk_solver_state *ss, struct apk_name *name)
{
	struct apk_name_state *ns = name_to_ns(name);
	ns->prerequires++;
	update_name_state(ss, name);
}

static void decrement_prerequires(struct apk_solver_state *ss, struct apk_name *name)
{
	struct apk_name_state *ns = name_to_ns(name);
	ns->prerequires--;
	update_name_state(ss, name);
}

Timo Teräs's avatar
Timo Teräs committed
764
static solver_result_t apply_decision(struct apk_solver_state *ss,
765
				      struct apk_decision *d)
766
{
767
	struct apk_name *name = decision_to_name(d);
Timo Teräs's avatar
Timo Teräs committed
768
	struct apk_name_state *ns = name_to_ns(name);
769
770
	struct apk_package *pkg = decision_to_pkg(d);
	struct apk_score score;
771

772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
	ss->impossible_constraints = 0;
	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
794
795
		}

796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
		if (d->type == DECISION_ASSIGN) {
			subscore(&ss->minimum_penalty, &ns->minimum_penalty);
			ns->minimum_penalty = (struct apk_score) { 0 };

			get_topology_score(ss, ns, pkg, 1, &score);
			addscore(&ss->score, &score);

			if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) >= 0 ||
			    check_if_package_unavailable(ss, pkg, 1)) {
				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);
				return SOLVERR_PRUNED;
			}
814

815
816
817
			ps->install_applied = 1;
			ss->assigned_names++;
			ns->chosen = pkg;
818

819
820
821
822
823
824
825
			ns->locked = 1;
			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);
		}
826
	} else {
827
828
829
830
831
		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
832
			subscore(&ss->minimum_penalty, &ns->minimum_penalty);
833
			ns->minimum_penalty = (struct apk_score) { 0 };
Timo Teräs's avatar
Timo Teräs committed
834

835
836
			get_unassigned_score(name, &score);
			addscore(&ss->score, &score);
Timo Teräs's avatar
Timo Teräs committed
837

838
			ns->chosen = NULL;
Timo Teräs's avatar
Timo Teräs committed
839
			ns->locked = 1;
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
		} else {
			ns->none_excluded = 1;
		}
	}

	if (ss->impossible_constraints)
		return SOLVERR_PRUNED;

	if (d->type == DECISION_EXCLUDE) {
		foreach_common_dependency(ss, name, increment_prerequires);

		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
858
859
860
861
		}
	}

	if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) >= 0) {
862
863
864
865
866
867
		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
868
		return SOLVERR_PRUNED;
869
	}
Timo Teräs's avatar
Timo Teräs committed
870
871

	return SOLVERR_EXPAND;
872
873
874
}

static void undo_decision(struct apk_solver_state *ss,
875
			  struct apk_decision *d)
876
{
877
	struct apk_name *name = decision_to_name(d);
878
	struct apk_name_state *ns = name_to_ns(name);
879
880
	struct apk_package *pkg = decision_to_pkg(d);
	struct apk_score score;
881

882
883
884
	if (d->type == DECISION_EXCLUDE) {
		foreach_common_dependency(ss, name, decrement_prerequires);
	}
885

886
887
	if (pkg != NULL) {
		struct apk_package_state *ps = pkg_to_ps(pkg);
888

889
890
891
892
893
894
895
896
897
898
		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;
		}
899

900
		if (ps->install_applied) {
Timo Teräs's avatar
Timo Teräs committed
901
902
903
904
			ps->install_applied = 0;
			ss->assigned_names--;
			foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
			foreach_dependency(ss, pkg->depends, undo_constraint);
905

906
907
			get_topology_score(ss, ns, pkg, 1, &score);
			subscore(&ss->score, &score);
908
		}
909
		ps->locked = 0;
Timo Teräs's avatar
Timo Teräs committed
910
	} else {
911
912
913
914
915
916
917
918
919
		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;
920
		}
921
	}
922

923
924
	ns->locked = 0;
	ns->chosen = NULL;
925

926
	update_name_state(ss, name);
927
928
}

929
930
931
932
933
934
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)
935
{
936
	struct apk_decision *d;
937

938
939
	ASSERT(ss->num_decisions <= ss->max_decisions,
	       "Decision tree overflow.\n");
940

941
942
943
944
945
946
947
948
949
950
951
952
	ss->num_decisions++;
	d = &ss->decisions[ss->num_decisions];

#ifdef DEBUG_CHECKS
	d->saved_score = ss->score;
#endif
	d->type = primary_decision;
	d->branching_point = branching_point;
	d->topology_position = topology_position;
	if (pkg == NULL) {
		d->name = name;
		d->no_package = 1;
953
	} else {
954
955
		d->pkg = pkg;
		d->no_package = 0;
956
	}
957

958
	return apply_decision(ss, d);
959
960
961
962
}

static int next_branch(struct apk_solver_state *ss)
{
963
964
	while (ss->num_decisions > 0) {
		struct apk_decision *d = &ss->decisions[ss->num_decisions];
965

966
		undo_decision(ss, d);
967

968
969
970
971
972
973
#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));
#endif
974

975
976
977
978
		if (d->branching_point == BRANCH_YES) {
			d->branching_point = BRANCH_NO;
			d->type = (d->type == DECISION_ASSIGN) ? DECISION_EXCLUDE : DECISION_ASSIGN;
			return apply_decision(ss, d);
979
		}
980
981

		ss->num_decisions--;
982
	}
983

Timo Teräs's avatar
Timo Teräs committed
984
985
	dbg_printf("-->next_branch: no more branches\n");
	return SOLVERR_STOP;
986
987
}

Timo Teräs's avatar
Timo Teräs committed
988
989
990
991
992
993
994
995
static void inherit_name_state(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);

	tns->solver_flags_inherited |=
		fns->solver_flags_inherited |
		(fns->solver_flags_local & fns->solver_flags_local_mask);
996
997

	tns->allowed_pinning |= fns->allowed_pinning | fns->preferred_pinning;
Timo Teräs's avatar
Timo Teräs committed
998
999
1000
}

static void inherit_name_state_wrapper(struct apk_package *rdepend, void *ctx)