solver.c 53.7 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
76
77
78
79
80
81
#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;
82
	unsigned found_solution : 1;
83
84
};

85
struct apk_package_state {
86
	unsigned int topology_soft;
87
	unsigned short conflicts;
88
	unsigned char preference;
Timo Teräs's avatar
Timo Teräs committed
89
90
	unsigned availability_checked : 1;
	unsigned unavailable : 1;
91
92
	unsigned handle_install_if : 1;
	unsigned locked : 1;
93
94
95
96
};

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

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

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

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

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

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

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

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

138
	struct list_head unsolved_list_head;
139
140
141

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

145
	struct apk_solution_array *best_solution;
146
147
148

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

	unsigned solver_flags : 4;
152
153
};

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

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

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

static void subscore(struct apk_score *a, struct apk_score *b)
{
180
181
	a->conflicts -= b->conflicts;
	a->non_preferred_actions -= b->non_preferred_actions;
182
183
184
	a->preference -= b->preference;
}

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

	if (a->non_preferred_actions < b->non_preferred_actions)
193
		return -1;
194
	if (a->non_preferred_actions > b->non_preferred_actions)
195
		return 1;
196

197
198
199
200
	if (a->preference < b->preference)
		return -1;
	if (a->preference > b->preference)
		return 1;
201

202
203
204
	return 0;
}

205
static inline int cmpscore2(struct apk_score *a1, struct apk_score *a2, struct apk_score *b)
206
{
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
	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;
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
248
249
250
#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
251
252
253
254
255
256
257
258
259
260
261
262
263

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;
264
265
}

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

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

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

297
298
299
300
301
302
303
304
305
306
307
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;
}

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
397
398
399
	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++;
	} else if ((ns->inherited_upgrade) == 0 &&
		   ((ns->solver_flags_local|ss->solver_flags) & APK_SOLVERF_UPGRADE) == 0 &&
		   ((ns->solver_flags_maybe & APK_SOLVERF_UPGRADE) == 0 || (ps->locked))) {
400
401
402
403
404
405
406
407
408
409
410
411
		/* 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++;

412
	if (ns->locked || (ns->allowed_pinning | ns->maybe_pinning) == ns->allowed_pinning) {
413
414
415
		allowed_pinning = ns->allowed_pinning | preferred_pinning;
		allowed_repos = get_pinning_mask_repos(ss->db, allowed_pinning);
		if (!(repos & allowed_repos))
416
			score.non_preferred_actions+=2;
417
418
419
420
421
422
423
424
425
426
427
428
429
	}

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

430
	get_topology_score(ss, ns, pkg, &score);
431
432
433
434
435
436
437
438
439
440
441
442
	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;

443
		get_topology_score(ss, ns, pkg0, &score0);
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
		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++;
	}
}

495
496
497
static void sort_hard_dependencies(struct apk_solver_state *ss, struct apk_package *pkg)
{
	struct apk_package_state *ps;
498
	struct apk_name_state *ns;
499
500
501
502
503

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

	ps = pkg_to_ps(pkg);
504
	if (ps->topology_soft)
505
		return;
506
	pkg->topology_hard = -1;
507
	ps->topology_soft = -1;
508
	calculate_pkg_preference(pkg);
509
510
511
512
513

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

514
515
	ss->max_decisions++;

516
	ns = name_to_ns_alloc(pkg->name);
517
518
519
520
521
	if (!ns->decision_counted) {
		ss->max_decisions++;
		ns->decision_counted = 1;
	}

522
	ps->topology_soft = pkg->topology_hard = ++ss->num_topology_positions;
523
	dbg_printf(PKG_VER_FMT ": topology_hard=%d\n",
524
		   PKG_VER_PRINTF(pkg), pkg->topology_hard);
525
526
527
528
529
530
531
532
533
}

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);
534
	if (ps->topology_soft != pkg->topology_hard)
535
		return;
Timo Teräs's avatar
Timo Teräs committed
536
	ps->topology_soft = -1;
537
538
539
540
541
542
543
544
545

	/* 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);
546
547
}

548
549
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
550
{
551
552
	struct apk_name_state *ns = name_to_ns_alloc(name);
	int propagate = FALSE;
Timo Teräs's avatar
Timo Teräs committed
553
554
	int i, j;

555
556
557
558
559
560
561
562
563
	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
564
565
		return;

566
567
	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
568

569
570
571
572
		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
573
		}
574
	}
Timo Teräs's avatar
Timo Teräs committed
575

576
577
578
	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
579
	}
580
581
}

582
583
584
585
586
587
588
589
590
591
592
593
594
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]);

	recalculate_maybe(ss, name,
			  ns->solver_flags_local & ns->solver_flags_local_mask,
			  ns->maybe_pinning);
}

595
596
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))
597
{
598
	int i;
599
	for (i = 0; i < deps->num; i++)
600
		func(ss, &deps->item[i]);
601
602
}

603
604
static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg)
{
Timo Teräs's avatar
Timo Teräs committed
605
	struct apk_name_state *ns;
606
607
608
609
610
	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
611
		ns = name_to_ns(dep->name);
Timo Teräs's avatar
Timo Teräs committed
612
		if (!ns->locked || !apk_dep_is_satisfied(dep, ns->chosen))
613
614
615
616
617
618
			missing++;
	}

	return missing;
}

619
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
620
621
622
623
624
625
{
	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. */
626
627
	if ((pkg->ipkg != NULL) && (ns->inherited_reinstall == 0) &&
	    ((ns->solver_flags_local|ss->solver_flags) & APK_SOLVERF_REINSTALL) == 0)
Timo Teräs's avatar
Timo Teräs committed
628
629
630
		return 0;

	/* done already? */
631
	if (ps->availability_checked && !do_check)
Timo Teräs's avatar
Timo Teräs committed
632
633
634
635
636
637
638
639
640
641
		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;
}

642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
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;
	}
}

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){
692
693
		.conflicts = ns->requirers ? : (ns->prerequires ? 1 : 0),
		.non_preferred_actions = 1,
694
695
696
697
		.preference = name->pkgs->num,
	};
}

Timo Teräs's avatar
Timo Teräs committed
698
static int update_name_state(struct apk_solver_state *ss, struct apk_name *name)
699
{
Timo Teräs's avatar
Timo Teräs committed
700
	struct apk_name_state *ns = name_to_ns(name);
701
	struct apk_package *best_pkg = NULL, *preferred_pkg = NULL;
702
	struct apk_score preferred_score;
703
	unsigned int best_topology = 0;
704
	int i, options = 0;
705

Timo Teräs's avatar
Timo Teräs committed
706
707
708
	if (ns->locked)
		return ns->chosen != NULL;

709
	subscore(&ss->minimum_penalty, &ns->minimum_penalty);
710
	ns->minimum_penalty = (struct apk_score) { .score = 0 };
711

712
713
	ns->name_touched = 1;

714
	get_unassigned_score(name, &preferred_score);
715
716
	for (i = 0; i < name->pkgs->num; i++) {
		struct apk_package *pkg0 = name->pkgs->item[i];
717
		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
718
		struct apk_score pkg0_score;
719

720
		if (ps0 == NULL || ps0->locked ||
Timo Teräs's avatar
Timo Teräs committed
721
		    ss->topology_position < pkg0->topology_hard ||
722
		    check_if_package_unavailable(ss, pkg0, 0))
Timo Teräs's avatar
Timo Teräs committed
723
724
			continue;

725
		/* preferred - currently most optimal for end solution */
726
		get_topology_score(ss, ns, pkg0, &pkg0_score);
727
728
729

		if (preferred_pkg == NULL ||
		    cmpscore(&pkg0_score, &preferred_score) < 0) {
730
			preferred_pkg = pkg0;
731
			preferred_score = pkg0_score;
732
733
		}

734
		/* next in topology order - next to get locked in */
735
736
737
		if (ps0->topology_soft < ss->topology_position &&
		    ps0->topology_soft > best_topology)
			best_pkg = pkg0, best_topology = ps0->topology_soft;
738
739
		else if (pkg0->topology_hard > best_topology)
			best_pkg = pkg0, best_topology = pkg0->topology_hard;
740
741

		options++;
742
	}
743

744
745
	if (ns->prerequires == 0 && ns->requirers == 0 && ns->install_ifs == 0) {
		/* No one really needs this name (anymore). */
746
747
748
		if (list_hashed(&ns->unsolved_list)) {
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
749
		}
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
		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
774

775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
	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);
		}
799
	}
800
}
801

802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
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);
		}
	}
824
825
}

826
827
828
829
static void trigger_install_if(struct apk_solver_state *ss,
			       struct apk_package *pkg)
{
	if (install_if_missing(ss, pkg) == 0) {
830
		struct apk_name *name0 = decision_to_name(&ss->decisions[ss->num_decisions]);
Timo Teräs's avatar
Timo Teräs committed
831
		struct apk_name_state *ns = ns = name_to_ns(pkg->name);
832
833
834
835

		dbg_printf("trigger_install_if: " PKG_VER_FMT " triggered\n",
			   PKG_VER_PRINTF(pkg));
		ns->install_ifs++;
836
		inherit_name_state(ss->db, pkg->name, name0);
Timo Teräs's avatar
Timo Teräs committed
837
		update_name_state(ss, pkg->name);
838
839
840
841
842
843
844
	}
}

static void untrigger_install_if(struct apk_solver_state *ss,
			       struct apk_package *pkg)
{
	if (install_if_missing(ss, pkg) != 1) {
845
		struct apk_name *name0 = decision_to_name(&ss->decisions[ss->num_decisions]);
Timo Teräs's avatar
Timo Teräs committed
846
		struct apk_name_state *ns = name_to_ns(pkg->name);
847
848
849
850

		dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n",
			   PKG_VER_PRINTF(pkg));
		ns->install_ifs--;
851
		uninherit_name_state(ss->db, pkg->name, name0);
Timo Teräs's avatar
Timo Teräs committed
852
		update_name_state(ss, pkg->name);
853
854
855
	}
}

856
857
static void increment_prerequires(struct apk_solver_state *ss, struct apk_name *name)
{
858
	struct apk_name *name0 = decision_to_name(&ss->decisions[ss->num_decisions]);
859
	struct apk_name_state *ns = name_to_ns(name);
860

861
	ns->prerequires++;
862
	inherit_name_state(ss->db, name, name0);
863
864
865
866
867
	update_name_state(ss, name);
}

static void decrement_prerequires(struct apk_solver_state *ss, struct apk_name *name)
{
868
	struct apk_name *name0 = decision_to_name(&ss->decisions[ss->num_decisions]);
869
	struct apk_name_state *ns = name_to_ns(name);
870

871
	ns->prerequires--;
872
	uninherit_name_state(ss->db, name, name0);
873
874
875
	update_name_state(ss, name);
}

Timo Teräs's avatar
Timo Teräs committed
876
static solver_result_t apply_decision(struct apk_solver_state *ss,
877
				      struct apk_decision *d)
878
{
879
	struct apk_name *name = decision_to_name(d);
Timo Teräs's avatar
Timo Teräs committed
880
	struct apk_name_state *ns = name_to_ns(name);
881
882
	struct apk_package *pkg = decision_to_pkg(d);
	struct apk_score score;
883

884
	ns->name_touched = 1;
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
	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
906
907
		}

908
909
		if (d->type == DECISION_ASSIGN) {
			subscore(&ss->minimum_penalty, &ns->minimum_penalty);
910
			ns->minimum_penalty = (struct apk_score) { .score = 0 };
911

912
913
			ns->locked = 1;
			get_topology_score(ss, ns, pkg, &score);
914
915
916
917
918
919
920
921
922
923
924
			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);
925
926
				ns->locked = 0;

927
928
				return SOLVERR_PRUNED;
			}
929

930
931
			ss->assigned_names++;
			ns->chosen = pkg;
932

933
934
935
936
937
938
			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);
		}
939
	} else {
940
941
942
943
944
		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
945
			subscore(&ss->minimum_penalty, &ns->minimum_penalty);
946
			ns->minimum_penalty = (struct apk_score) { .score = 0 };
Timo Teräs's avatar
Timo Teräs committed
947

948
949
			get_unassigned_score(name, &score);
			addscore(&ss->score, &score);
Timo Teräs's avatar
Timo Teräs committed
950

951
			ns->chosen = NULL;
Timo Teräs's avatar
Timo Teräs committed
952
			ns->locked = 1;
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
		} else {
			ns->none_excluded = 1;
		}
	}

	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
968
969
970
971
		}
	}

	if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) >= 0) {
972
973
974
975
976
977
		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
978
		return SOLVERR_PRUNED;
979
	}
Timo Teräs's avatar
Timo Teräs committed
980
981

	return SOLVERR_EXPAND;
982
983
984
}

static void undo_decision(struct apk_solver_state *ss,
985
			  struct apk_decision *d)
986
{
987
	struct apk_name *name = decision_to_name(d);
988
	struct apk_name_state *ns = name_to_ns(name);
989
990
	struct apk_package *pkg = decision_to_pkg(d);
	struct apk_score score;
991

992
	ns->name_touched = 1;
993
994
995
	if (d->type == DECISION_EXCLUDE) {
		foreach_common_dependency(ss, name, decrement_prerequires);
	}
996

997
998
	if (pkg != NULL) {
		struct apk_package_state *ps = pkg_to_ps(pkg);
999

1000
		dbg_printf("-->undo_decision: " PKG_VER_FMT " %s\n",