solver.c 37.4 KB
Newer Older
1
2
3
/* solver.c - Alpine Package Keeper (APK)
 * A backtracking, forward checking dependency graph solver.
 *
4
 * Copyright (C) 2008-2011 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
23
24
25
26
27
#if 0
#include <stdio.h>
#define dbg_printf(args...) fprintf(stderr, args)
#else
#define dbg_printf(args...)
#endif

#define APK_PKGSTF_NOINSTALL		0
#define APK_PKGSTF_INSTALL		1
Timo Teräs's avatar
Timo Teräs committed
28
29
30
31
32
33
34
35
#define APK_PKGSTF_ALT_BRANCH		2
#define APK_PKGSTF_INSTALLIF		4
#define APK_PKGSTF_DECIDED		8

struct apk_score {
	unsigned short unsatisfiable;
	unsigned short preference;
};
36
37
38

struct apk_package_state {
	struct apk_package *backtrack;
39
	unsigned int topology_soft;
Timo Teräs's avatar
Timo Teräs committed
40
	struct apk_score saved_score;
41
42
43
44
45
46
	unsigned short flags;
	unsigned short conflicts;
};

struct apk_name_state {
	struct list_head unsolved_list;
Timo Teräs's avatar
Timo Teräs committed
47
	struct apk_name *name;
48
	struct apk_package *chosen;
49
	unsigned int topology_last_touched;
50
	unsigned int allowed_repos, preferred_repos;
51
	unsigned short requirers;
52
	unsigned short install_ifs;
Timo Teräs's avatar
Timo Teräs committed
53
54
55
56
57
58
59

	unsigned int solver_flags_local : 4;
	unsigned int solver_flags_local_mask : 4;
	unsigned int solver_flags_inherited : 4;

	unsigned int availability_checked : 1;
	unsigned int locked : 1;
Timo Teräs's avatar
Timo Teräs committed
60
	unsigned int in_changeset : 1;
61
62
63
64
};

struct apk_solver_state {
	struct apk_database *db;
65
66
	unsigned num_topology_positions;

67
68
69
	struct list_head unsolved_list_head;
	struct apk_package *latest_decision;
	unsigned int topology_position;
70
	unsigned int penalty_topology;
71
	unsigned int assigned_names;
Timo Teräs's avatar
Timo Teräs committed
72
	struct apk_score score;
73
	struct apk_score penalty_score;
74

Timo Teräs's avatar
Timo Teräs committed
75
76
	unsigned int solver_flags : 4;
	unsigned int refresh_name_states : 1;
Timo Teräs's avatar
Timo Teräs committed
77

78
	struct apk_package_array *best_solution;
Timo Teräs's avatar
Timo Teräs committed
79
	struct apk_score best_score;
80
81
};

82
83
84
85
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);
static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
			  int flags);
86

Timo Teräs's avatar
Timo Teräs committed
87
static struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
88
89
90
91
{
	return (struct apk_package_state*) pkg->state_ptr;
}

Timo Teräs's avatar
Timo Teräs committed
92
93
static struct apk_name_state *name_to_ns(struct apk_name *name)
{
Timo Teräs's avatar
Timo Teräs committed
94
95
96
97
98
99
100
101
102
103
	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
104
105
}

106
107
108
109
110
111
112
113
114
115
116
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;
}

117
118
119
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))
120
121
122
{
	int i, j;

123
124
125
	/* And sort the main dependencies */
	for (i = 0; i < depends->num; i++) {
		struct apk_dependency *dep = &depends->item[i];
126
127
128
129
		struct apk_name *name0 = dep->name;

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

131
			/* conflict depends on all to be not installed */
132
			if (!apk_dep_is_satisfied(dep, pkg0))
133
				continue;
134
135

			cb(ss, pkg0);
136
137
		}
	}
138
}
139

140
141
142
143
144
145
146
147
148
149
150
151
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);
152

153
154
155
156
157
158
		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 &&
159
				    apk_dep_is_satisfied(dep, pkg))
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
					break;
			}
			if (k >= pkg0->install_if->num)
				continue;

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

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

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

	ps = pkg_to_ps(pkg);
179
	if (ps->topology_soft)
180
		return;
181
	pkg->topology_hard = -1;
182
	ps->topology_soft = -1;
183
184
185
186
187

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

188
	ps->topology_soft = pkg->topology_hard = ++ss->num_topology_positions;
189
	dbg_printf(PKG_VER_FMT ": topology_hard=%d\n",
190
		   PKG_VER_PRINTF(pkg), pkg->topology_hard);
191
192
193
194
195
196
197
198
199
}

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);
200
	if (ps->topology_soft != pkg->topology_hard)
201
		return;
Timo Teräs's avatar
Timo Teräs committed
202
	ps->topology_soft = -1;
203
204
205
206
207
208
209
210
211

	/* 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);
212
213
214
215
216
217
218
}

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

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

222
223
224
225
226
static void prepare_name(struct apk_solver_state *ss, struct apk_name *name,
			 struct apk_name_state *ns)
{
	int i;

Timo Teräs's avatar
Timo Teräs committed
227
	if (ns->availability_checked)
228
229
230
231
		return;

	for (i = 0; i < name->pkgs->num; i++) {
		struct apk_package *pkg = name->pkgs->item[i];
232
		struct apk_package_state *ps = pkg_to_ps(pkg);
Timo Teräs's avatar
Timo Teräs committed
233
		struct apk_name_state *ns = name_to_ns(pkg->name);
234
235

		/* if package is needed for (re-)install */
Timo Teräs's avatar
Timo Teräs committed
236
		if ((pkg->ipkg == NULL) ||
Timo Teräs's avatar
Timo Teräs committed
237
238
		    ((ns->solver_flags_local | ns->solver_flags_inherited |
		      ss->solver_flags) & APK_SOLVERF_REINSTALL)) {
239
240
			/* and it's not available, we can't use it */
			if (!pkg_available(ss->db, pkg))
241
				ps->conflicts = 1024;
242
243
244
		}
	}

Timo Teräs's avatar
Timo Teräs committed
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
	ns->availability_checked = 1;
}

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);
	}
275
276
}

277
278
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))
279
{
280
	int i;
281
	for (i = 0; i < deps->num; i++)
282
		func(ss, &deps->item[i]);
283
284
}

Timo Teräs's avatar
Timo Teräs committed
285
static int compare_package_preference(unsigned short solver_flags,
286
				      unsigned int preferred_repos,
Timo Teräs's avatar
Timo Teräs committed
287
288
289
				      struct apk_package *pkgA,
				      struct apk_package *pkgB)
{
290
	/* preferred repository pinning */
Timo Teräs's avatar
Timo Teräs committed
291
292
	if ((pkgA->ipkg || pkgA->filename || (pkgA->repos & preferred_repos)) &&
	    !(pkgB->ipkg || pkgB->filename || (pkgB->repos & preferred_repos)))
293
		return 1;
Timo Teräs's avatar
Timo Teräs committed
294
295
	if ((pkgB->ipkg || pkgA->filename || (pkgB->repos & preferred_repos)) &&
	    !(pkgA->ipkg || pkgB->filename || (pkgA->repos & preferred_repos)))
296
297
		return -1;

Timo Teräs's avatar
Timo Teräs committed
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
	if (solver_flags & APK_SOLVERF_AVAILABLE) {
		if (pkgA->repos != 0 && pkgB->repos == 0)
			return 1;
		if (pkgB->repos != 0 && pkgA->repos == 0)
			return -1;
	}

	if (!(solver_flags & APK_SOLVERF_UPGRADE)) {
		/* not upgrading, prefer the installed package */
		if (pkgA->ipkg != NULL && pkgB->ipkg == NULL)
			return 1;
		if (pkgB->ipkg != NULL && pkgA->ipkg == NULL)
			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 one with lowest available repository */
	return ffsl(pkgB->repos) - ffsl(pkgA->repos);
}

static int get_preference(struct apk_solver_state *ss,
			  struct apk_package *pkg,
			  int installable_only)
329
330
{
	struct apk_name *name = pkg->name;
331
	struct apk_name_state *ns = name_to_ns(name);
Timo Teräs's avatar
Timo Teräs committed
332
333
334
	unsigned short name_flags = ns->solver_flags_local
		| ns->solver_flags_inherited
		| ss->solver_flags;
335
	unsigned int preferred_repos = ns->preferred_repos | ss->db->repo_tags[0].allowed_repos;
Timo Teräs's avatar
Timo Teräs committed
336
337
	unsigned short preference = 0;
	int i;
338

339
	for (i = 0; i < name->pkgs->num; i++) {
340
		struct apk_package *pkg0 = name->pkgs->item[i];
341
		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
342

Timo Teräs's avatar
Timo Teräs committed
343
		if (pkg0 == pkg || ps0 == NULL)
344
345
			continue;

346
347
348
		if (compare_package_preference(name_flags,
					       preferred_repos,
					       pkg, pkg0) < 0) {
Timo Teräs's avatar
Timo Teräs committed
349
350
351
352
353
354
			if (installable_only) {
				if (ss->topology_position > pkg0->topology_hard &&
				    !(ps0->flags & APK_PKGSTF_DECIDED))
					preference++;
			} else
				preference++;
355
356
357
		}
	}

Timo Teräs's avatar
Timo Teräs committed
358
	return preference;
359
360
}

361
362
static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg)
{
Timo Teräs's avatar
Timo Teräs committed
363
	struct apk_name_state *ns;
364
365
366
367
368
	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
369
		ns = name_to_ns(dep->name);
Timo Teräs's avatar
Timo Teräs committed
370
		if (!ns->locked || !apk_dep_is_satisfied(dep, ns->chosen))
371
372
373
374
375
376
			missing++;
	}

	return missing;
}

Timo Teräs's avatar
Timo Teräs committed
377
static int update_name_state(struct apk_solver_state *ss, struct apk_name *name)
378
{
Timo Teräs's avatar
Timo Teräs committed
379
	struct apk_name_state *ns = name_to_ns(name);
380
381
	struct apk_package *best_pkg = NULL;
	unsigned int best_topology = 0;
382
	unsigned int allowed_repos = ns->allowed_repos | ss->db->repo_tags[0].allowed_repos;
383
	int i, options = 0, skipped_options = 0;
384
385
386

	for (i = 0; i < name->pkgs->num; i++) {
		struct apk_package *pkg0 = name->pkgs->item[i];
387
		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
388

389
		if (ps0 == NULL ||
390
		    pkg0->topology_hard >= ss->topology_position ||
391
		    (ps0->flags & APK_PKGSTF_DECIDED))
392
393
			continue;

Timo Teräs's avatar
Timo Teräs committed
394
395
396
397
398
399
		if ((pkg0->repos != 0) && (pkg0->ipkg == NULL) && (pkg0->filename == NULL) &&
		    !(pkg0->repos & allowed_repos)) {
			skipped_options++;
			continue;
		}

400
401
402
403
404
405
		if (ns->requirers == 0 && ns->install_ifs != 0 &&
		    install_if_missing(ss, pkg0)) {
			skipped_options++;
			continue;
		}

406
		options++;
407
408
409
		if (ps0->topology_soft < ss->topology_position &&
		    ps0->topology_soft > best_topology)
			best_pkg = pkg0, best_topology = ps0->topology_soft;
410
411
		else if (pkg0->topology_hard > best_topology)
			best_pkg = pkg0, best_topology = pkg0->topology_hard;
412
	}
413

414
	if (skipped_options == 0 && options == 0) {
Timo Teräs's avatar
Timo Teräs committed
415
416
417
418
		if (!ns->locked) {
			ss->score.unsatisfiable += ns->requirers;
			ss->score.preference += name->pkgs->num;
		}
419
420
421
422
423
424
		ns->locked = 1;
		ns->chosen = NULL;
	} else {
		ns->locked = 0;
	}

Timo Teräs's avatar
Timo Teräs committed
425
	if (ns->requirers == 0 && ns->install_ifs == 0) {
426
427
428
429
430
		if (list_hashed(&ns->unsolved_list)) {
			list_del(&ns->unsolved_list);
			list_init(&ns->unsolved_list);
			ns->chosen = NULL;
		}
431
432
		dbg_printf("%s: deleted from unsolved: %d requirers, %d install_ifs, %d options, %d skipped\n",
			   name->name, ns->requirers, ns->install_ifs, options, skipped_options);
433
	} else {
434
435
436
		dbg_printf("%s: added to unsolved: %d requirers, %d install_ifs, %d options (next topology %d)\n",
			   name->name, ns->requirers, ns->install_ifs, options,
			   best_topology);
437
438
		if (!list_hashed(&ns->unsolved_list))
			list_add(&ns->unsolved_list, &ss->unsolved_list_head);
Timo Teräs's avatar
Timo Teräs committed
439
440
		if (!ns->locked)
			ns->chosen = best_pkg;
441
442
	}

443
	return options + skipped_options;
444
445
}

446
447
448
449
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
450
		struct apk_name_state *ns = ns = name_to_ns(pkg->name);
451
452
453

		dbg_printf("trigger_install_if: " PKG_VER_FMT " triggered\n",
			   PKG_VER_PRINTF(pkg));
454
		ns->topology_last_touched = ss->topology_position;
455
		ns->install_ifs++;
Timo Teräs's avatar
Timo Teräs committed
456
		update_name_state(ss, pkg->name);
457
458
459
460
461
462
463
	}
}

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
464
		struct apk_name_state *ns = name_to_ns(pkg->name);
465
466
467

		dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n",
			   PKG_VER_PRINTF(pkg));
468
		ns->topology_last_touched = ss->topology_position;
469
		ns->install_ifs--;
Timo Teräs's avatar
Timo Teräs committed
470
		update_name_state(ss, pkg->name);
471
472
473
	}
}

474
475
476
static void apply_decision(struct apk_solver_state *ss,
			   struct apk_package *pkg,
			   struct apk_package_state *ps)
477
{
Timo Teräs's avatar
Timo Teräs committed
478
	struct apk_name_state *ns = name_to_ns(pkg->name);
479
480
481
482
483
484

	dbg_printf("apply_decision: " PKG_VER_FMT " %s\n", PKG_VER_PRINTF(pkg),
		   (ps->flags & APK_PKGSTF_INSTALL) ? "INSTALL" : "NO_INSTALL");

	if (ps->flags & APK_PKGSTF_INSTALL) {
		ss->assigned_names++;
Timo Teräs's avatar
Timo Teräs committed
485
486
		ss->score.unsatisfiable += ps->conflicts;
		ss->score.preference += get_preference(ss, pkg, FALSE);
487
		ns->chosen = pkg;
Timo Teräs's avatar
Timo Teräs committed
488
		ns->locked = 1;
489
490
491
492
493
494
495

		list_del(&ns->unsolved_list);
		list_init(&ns->unsolved_list);
		dbg_printf("%s: deleting from unsolved list\n",
			   pkg->name->name);

		foreach_dependency(ss, pkg->depends, apply_constraint);
496
		foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
497
	} else {
Timo Teräs's avatar
Timo Teräs committed
498
		update_name_state(ss, pkg->name);
499
500
501
502
503
504
505
	}
}

static void undo_decision(struct apk_solver_state *ss,
			  struct apk_package *pkg,
			  struct apk_package_state *ps)
{
Timo Teräs's avatar
Timo Teräs committed
506
	struct apk_name_state *ns = name_to_ns(pkg->name);
507
508
509
510

	dbg_printf("undo_decision: " PKG_VER_FMT " %s\n", PKG_VER_PRINTF(pkg),
		   (ps->flags & APK_PKGSTF_INSTALL) ? "INSTALL" : "NO_INSTALL");

511
512
513
	if (ps->flags & APK_PKGSTF_INSTALLIF)
		ss->topology_position = ps->topology_soft;
	else
514
		ss->topology_position = pkg->topology_hard;
515

516
517
	if (ps->flags & APK_PKGSTF_INSTALL) {
		ss->assigned_names--;
518
519

		foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
520
521
		foreach_dependency(ss, pkg->depends, undo_constraint);

Timo Teräs's avatar
Timo Teräs committed
522
		ns->locked = 0;
523
		ns->chosen = NULL;
524
	}
525

Timo Teräs's avatar
Timo Teräs committed
526
	ss->score = ps->saved_score;
Timo Teräs's avatar
Timo Teräs committed
527
	update_name_state(ss, pkg->name);
528
529
}

530
531
static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
			  int flags)
532
{
533
	struct apk_package_state *ps = pkg_to_ps(pkg);
534
535

	ps->backtrack = ss->latest_decision;
536
	ps->flags = flags | APK_PKGSTF_DECIDED;
Timo Teräs's avatar
Timo Teräs committed
537
	ps->saved_score = ss->score;
538
539
540
541
542
543
544

	if (ps->topology_soft < ss->topology_position) {
		if (flags & APK_PKGSTF_INSTALL)
			ps->flags |= APK_PKGSTF_INSTALLIF;
		ss->topology_position = ps->topology_soft;
	} else {
		ps->flags &= ~APK_PKGSTF_INSTALLIF;
545
		ss->topology_position = pkg->topology_hard;
546
	}
547
	ss->latest_decision = pkg;
548

Timo Teräs's avatar
Timo Teräs committed
549
550
	dbg_printf("push_decision: adding new BRANCH at topology_position %d\n",
		   ss->topology_position);
551

552
553
554
555
	if (ps->flags & APK_PKGSTF_INSTALLIF)
		dbg_printf("triggers due to " PKG_VER_FMT "\n",
			   PKG_VER_PRINTF(pkg));

556
	apply_decision(ss, pkg, ps);
557
558
559
560
561
562
563
}

static int next_branch(struct apk_solver_state *ss)
{
	struct apk_package *pkg;
	struct apk_package_state *ps;

564
	while (ss->latest_decision != NULL) {
565
		pkg = ss->latest_decision;
566
		ps = pkg_to_ps(pkg);
567
568
569
570

		if (ps->flags & APK_PKGSTF_ALT_BRANCH) {
			dbg_printf("next_branch: undo decision at topology_position %d\n",
				   ss->topology_position);
571
			ps->flags &= ~(APK_PKGSTF_ALT_BRANCH | APK_PKGSTF_DECIDED);
Timo Teräs's avatar
Timo Teräs committed
572
573
			undo_decision(ss, pkg, ps);

574
			ss->latest_decision = ps->backtrack;
Timo Teräs's avatar
Timo Teräs committed
575
			ss->refresh_name_states = 1;
576
577
578
579
		} else {
			dbg_printf("next_branch: swapping BRANCH at topology_position %d\n",
				   ss->topology_position);

Timo Teräs's avatar
Timo Teräs committed
580
581
			undo_decision(ss, pkg, ps);

582
583
584
			ps->flags |= APK_PKGSTF_ALT_BRANCH;
			ps->flags ^= APK_PKGSTF_INSTALL;

585
586
			apply_decision(ss, pkg, ps);
			return 0;
587
588
		}
	}
589
590
591

	dbg_printf("next_branch: no more branches\n");
	return 1;
592
593
}

Timo Teräs's avatar
Timo Teräs committed
594
595
596
597
598
599
600
601
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);
602
	tns->allowed_repos |= fns->allowed_repos;
Timo Teräs's avatar
Timo Teräs committed
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
}

static void inherit_name_state_wrapper(struct apk_package *rdepend, void *ctx)
{
	struct apk_name *name = (struct apk_name *) ctx;
	inherit_name_state(name, rdepend->name);
}

static int has_inherited_state(struct apk_name *name)
{
	struct apk_name_state *ns = name_to_ns(name);

	if (name == NULL)
		return 0;
	if (ns->solver_flags_inherited || (ns->solver_flags_local & ns->solver_flags_local_mask))
		return 1;
619
620
	if (ns->allowed_repos)
		return 1;
Timo Teräs's avatar
Timo Teräs committed
621
622
623
624
625
626
627
628
	return 0;
}

static void recalculate_inherted_name_state(struct apk_name *name)
{
	struct apk_name_state *ns = name_to_ns(name);

	ns->solver_flags_inherited = 0;
629
	ns->allowed_repos = 0;
Timo Teräs's avatar
Timo Teräs committed
630
631
632
	foreach_locked_reverse_dependency(name, inherit_name_state_wrapper, name);
}

633
static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
634
635
{
	struct apk_name *name = dep->name;
Timo Teräs's avatar
Timo Teräs committed
636
	struct apk_name_state *ns = name_to_ns(name);
637
	int i;
638

639
	prepare_name(ss, name, ns);
640

Timo Teräs's avatar
Timo Teräs committed
641
	if (ns->locked) {
Timo Teräs's avatar
Timo Teräs committed
642
643
644
645
646
647
		if (ns->chosen)
			dbg_printf("%s: locked to " PKG_VER_FMT " already\n",
				   dep->name->name, PKG_VER_PRINTF(ns->chosen));
		else
			dbg_printf("%s: locked to empty\n",
				   dep->name->name);
648
		if (!apk_dep_is_satisfied(dep, ns->chosen))
Timo Teräs's avatar
Timo Teräs committed
649
			ss->score.unsatisfiable++;
650
651
652
		return;
	}

653
654
655
656
657
658
659
660
661
662
	if (dep->repository_tag) {
		unsigned int allowed_repos;

		dbg_printf("%s: enabling repository tag %d\n",
			   dep->name->name, dep->repository_tag);
		allowed_repos = ss->db->repo_tags[dep->repository_tag].allowed_repos;
		ns->allowed_repos |= allowed_repos;
		ns->preferred_repos |= allowed_repos;
	}

663
664
	for (i = 0; i < name->pkgs->num; i++) {
		struct apk_package *pkg0 = name->pkgs->item[i];
665
		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
666

667
		if (ps0 == NULL ||
668
		    pkg0->topology_hard >= ss->topology_position)
669
670
671
672
673
674
675
676
677
678
			continue;

		if (!apk_dep_is_satisfied(dep, pkg0)) {
			ps0->conflicts++;
			dbg_printf(PKG_VER_FMT ": conflicts++ -> %d\n",
				   PKG_VER_PRINTF(pkg0),
				   ps0->conflicts);
		}
	}

Timo Teräs's avatar
Timo Teräs committed
679
680
681
	if (ss->latest_decision != NULL)
		inherit_name_state(name, ss->latest_decision->name);

682
	if (!dep->optional)
Timo Teräs's avatar
Timo Teräs committed
683
		ns->requirers++;
684
685
	ns->topology_last_touched = ss->topology_position;

Timo Teräs's avatar
Timo Teräs committed
686
	update_name_state(ss, name);
687
688
}

689
static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
690
691
{
	struct apk_name *name = dep->name;
Timo Teräs's avatar
Timo Teräs committed
692
	struct apk_name_state *ns = name_to_ns(name);
693
694
	int i;

Timo Teräs's avatar
Timo Teräs committed
695
	if (ns->locked) {
696
697
698
699
700
701
702
		if (ns->chosen != NULL) {
			dbg_printf(PKG_VER_FMT " selected already for %s\n",
				   PKG_VER_PRINTF(ns->chosen), dep->name->name);
		} else {
			dbg_printf("%s selected to not be satisfied\n",
				   dep->name->name);
		}
703
704
		return;
	}
705
706
707

	for (i = 0; i < name->pkgs->num; i++) {
		struct apk_package *pkg0 = name->pkgs->item[i];
708
		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
709

710
		if (pkg0->topology_hard >= ss->topology_position)
711
712
713
714
715
716
717
718
719
720
			continue;

		if (!apk_dep_is_satisfied(dep, pkg0)) {
			ps0->conflicts--;
			dbg_printf(PKG_VER_FMT ": conflicts-- -> %d\n",
				   PKG_VER_PRINTF(pkg0),
				   ps0->conflicts);
		}
	}

Timo Teräs's avatar
Timo Teräs committed
721
722
723
	if (ss->latest_decision && has_inherited_state(ss->latest_decision->name))
		recalculate_inherted_name_state(name);

724
	if (!dep->optional)
Timo Teräs's avatar
Timo Teräs committed
725
		ns->requirers--;
726
727
	ns->topology_last_touched = ss->topology_position;

Timo Teräs's avatar
Timo Teräs committed
728
	update_name_state(ss, name);
729
730
731
732
}

static int expand_branch(struct apk_solver_state *ss)
{
733
734
	struct apk_name_state *ns;
	struct apk_package *pkg0 = NULL;
735
	unsigned int topology0 = 0;
Timo Teräs's avatar
Timo Teräs committed
736
	int flags;
737
738
739

	/* FIXME: change unsolved_list to a priority queue */
	list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
Timo Teräs's avatar
Timo Teräs committed
740
741
742
		if (ss->refresh_name_states)
			update_name_state(ss, ns->name);

743
744
745
746
747
748
749
750
751
		/* ns->chosen can be NULL if the name has only install_if
		 * requirers that got later conflicted, but it still has
		 * other options that can get activated later due to more
		 * complicated install_if rules in some other package. */
		if (ns->chosen == NULL)
			continue;
		if (pkg_to_ps(ns->chosen)->topology_soft < ss->topology_position &&
		    pkg_to_ps(ns->chosen)->topology_soft > topology0)
			pkg0 = ns->chosen, topology0 = pkg_to_ps(pkg0)->topology_soft;
752
753
		else if (ns->chosen->topology_hard > topology0)
			pkg0 = ns->chosen, topology0 = pkg0->topology_hard;
754
	}
Timo Teräs's avatar
Timo Teräs committed
755
	ss->refresh_name_states = 0;
756
	if (pkg0 == NULL) {
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
		struct apk_score penalty_score = {0,0};
		int penalty_topology = 0;

		list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
			if (!ns->locked) {
				penalty_score.unsatisfiable += ns->requirers;
				penalty_score.preference += ns->name->pkgs->num;
				if (penalty_topology < ns->topology_last_touched)
					penalty_topology = ns->topology_last_touched;
			}
		}
		if (ss->penalty_topology < penalty_topology) {
			ss->penalty_topology = penalty_topology;
			ss->penalty_score = penalty_score;
		}
		ss->score.unsatisfiable += penalty_score.unsatisfiable;
		ss->score.preference    += penalty_score.preference;

775
		dbg_printf("expand_branch: list is empty (%d unsatisfied)\n",
Timo Teräs's avatar
Timo Teräs committed
776
			   ss->score.unsatisfiable);
777
778
		return 1;
	}
779

780
781
	/* someone needs to provide this name -- find next eligible
	 * provider candidate */
Timo Teräs's avatar
Timo Teräs committed
782
	ns = name_to_ns(pkg0->name);
783
	dbg_printf("expand_branch: %s\n", pkg0->name->name);
784

Timo Teräs's avatar
Timo Teräs committed
785
786
787
788
789
	if (get_preference(ss, pkg0, TRUE) == 0)
		flags = APK_PKGSTF_INSTALL;
	else
		flags = APK_PKGSTF_NOINSTALL;
	push_decision(ss, pkg0, flags);
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804

	return 0;
}

static void record_solution(struct apk_solver_state *ss)
{
	struct apk_package *pkg;
	struct apk_package_state *ps;
	int i;

	apk_package_array_resize(&ss->best_solution, ss->assigned_names);

	i = 0;
	pkg = ss->latest_decision;
	while (pkg != NULL) {
805
		ps = pkg_to_ps(pkg);
806
807
808
		if (ps->flags & APK_PKGSTF_INSTALL) {
			if (i >= ss->assigned_names)
				abort();
809
			ss->best_solution->item[i++] = pkg;
810
		}
811
812
813
814
815
816
817

		dbg_printf("record_solution: " PKG_VER_FMT ": %sINSTALL\n",
			   PKG_VER_PRINTF(pkg),
			   (ps->flags & APK_PKGSTF_INSTALL) ? "" : "NO_");

		pkg = ps->backtrack;
	}
818
	apk_package_array_resize(&ss->best_solution, i);
Timo Teräs's avatar
Timo Teräs committed
819
	ss->best_score = ss->score;
820
821
822
823
824
825
826
827
}

static int compare_package_name(const void *p1, const void *p2)
{
	const struct apk_package **c1 = (const struct apk_package **) p1;
	const struct apk_package **c2 = (const struct apk_package **) p2;

	return strcmp((*c1)->name->name, (*c2)->name->name);
828
829
}

Timo Teräs's avatar
Timo Teräs committed
830
831
832
833
834
835
836
837
static int compare_change(const void *p1, const void *p2)
{
	const struct apk_change *c1 = (const struct apk_change *) p1;
	const struct apk_change *c2 = (const struct apk_change *) p2;

	if (c1->newpkg == NULL) {
		if (c2->newpkg == NULL)
			/* both deleted - reverse topology order */
838
839
			return  c2->oldpkg->topology_hard -
				c1->oldpkg->topology_hard;
Timo Teräs's avatar
Timo Teräs committed
840
841
842
843
844
845
846
847

		/* c1 deleted, c2 installed -> c2 first*/
		return -1;
	}
	if (c2->newpkg == NULL)
		/* c1 installed, c2 deleted -> c1 first*/
		return 1;

848
849
	return  c1->newpkg->topology_hard -
		c2->newpkg->topology_hard;
Timo Teräs's avatar
Timo Teräs committed
850
851
852
853
}

static int generate_changeset(struct apk_database *db,
			      struct apk_package_array *solution,
854
855
			      struct apk_changeset *changeset,
			      unsigned short solver_flags)
Timo Teräs's avatar
Timo Teräs committed
856
857
858
859
860
861
862
863
864
865
{
	struct apk_name *name;
	struct apk_name_state *ns;
	struct apk_package *pkg, *pkg0;
	struct apk_installed_package *ipkg;
	int i, j, num_installs = 0, num_removed = 0, ci = 0;

	/* calculate change set size */
	for (i = 0; i < solution->num; i++) {
		pkg = solution->item[i];
Timo Teräs's avatar
Timo Teräs committed
866
		ns = name_to_ns(pkg->name);
Timo Teräs's avatar
Timo Teräs committed
867
868
		ns->chosen = pkg;
		ns->in_changeset = 1;
Timo Teräs's avatar
Timo Teräs committed
869
		if ((pkg->ipkg == NULL) ||
Timo Teräs's avatar
Timo Teräs committed
870
871
		    ((ns->solver_flags_local | ns->solver_flags_inherited |
		      solver_flags) & APK_SOLVERF_REINSTALL))
Timo Teräs's avatar
Timo Teräs committed
872
873
874
875
876
			num_installs++;
	}
	list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
		name = ipkg->pkg->name;
		ns = name_to_ns(name);
Timo Teräs's avatar
Timo Teräs committed
877
		if ((ns->chosen == NULL) || !ns->in_changeset)
Timo Teräs's avatar
Timo Teräs committed
878
879
880
881
882
883
884
885
			num_removed++;
	}

	/* construct changeset */
	apk_change_array_resize(&changeset->changes, num_installs + num_removed);
	list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
		name = ipkg->pkg->name;
		ns = name_to_ns(name);
Timo Teräs's avatar
Timo Teräs committed
886
		if ((ns->chosen == NULL) || !ns->in_changeset) {
Timo Teräs's avatar
Timo Teräs committed
887
888
889
890
891
892
893
			changeset->changes->item[ci].oldpkg = ipkg->pkg;
			ci++;
		}
	}
	for (i = 0; i < solution->num; i++) {
		pkg = solution->item[i];
		name = pkg->name;
Timo Teräs's avatar
Timo Teräs committed
894
		ns = name_to_ns(name);
Timo Teräs's avatar
Timo Teräs committed
895
896

		if ((pkg->ipkg == NULL) ||
Timo Teräs's avatar
Timo Teräs committed
897
898
		    ((ns->solver_flags_local | ns->solver_flags_inherited |
		      solver_flags) & APK_SOLVERF_REINSTALL)) {
Timo Teräs's avatar
Timo Teräs committed
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
			for (j = 0; j < name->pkgs->num; j++) {
				pkg0 = name->pkgs->item[j];
				if (pkg0->ipkg == NULL)
					continue;
				changeset->changes->item[ci].oldpkg = pkg0;
				break;
			}
			changeset->changes->item[ci].newpkg = pkg;
			ci++;
		}
	}

	/* sort changeset to topology order */
	qsort(changeset->changes->item, changeset->changes->num,
	      sizeof(struct apk_change), compare_change);

	return 0;
}

static int free_state(apk_hash_item item, void *ctx)
{
	struct apk_name *name = (struct apk_name *) item;

	if (name->state_ptr != NULL) {
		free(name->state_ptr);
		name->state_ptr = NULL;
	}
	return 0;
}

929
930
931
932
933
934
935
936
937
938
939
static int free_package(apk_hash_item item, void *ctx)
{
	struct apk_package *pkg = (struct apk_package *) item;

	if (pkg->state_ptr != NULL) {
		free(pkg->state_ptr);
		pkg->state_ptr = NULL;
	}
	return 0;
}

940
void apk_solver_set_name_flags(struct apk_name *name,
Timo Teräs's avatar
Timo Teräs committed
941
942
			       unsigned short solver_flags,
			       unsigned short solver_flags_inheritable)
943
944
{
	struct apk_name_state *ns = name_to_ns(name);
Timo Teräs's avatar
Timo Teräs committed
945
946
	ns->solver_flags_local = solver_flags;
	ns->solver_flags_local_mask = solver_flags_inheritable;
947
948
}

949
950
951
952
953
954
static void apk_solver_free(struct apk_database *db)
{
	apk_hash_foreach(&db->available.names, free_state, NULL);
	apk_hash_foreach(&db->available.packages, free_package, NULL);
}

Timo Teräs's avatar
Timo Teräs committed
955
956
957
958
959
960
961
962
963
964
965
966
967
static int cmpscore(struct apk_score *a, struct apk_score *b)
{
	if (a->unsatisfiable < b->unsatisfiable)
		return -1;
	if (a->unsatisfiable > b->unsatisfiable)
		return 1;
	if (a->preference < b->preference)
		return -1;
	if (a->preference > b->preference)
		return 1;
	return 0;
}

968
969
970
971
972
973
974
975
976
977
978
979
980
static int cmpscore2(struct apk_score *a1, struct apk_score *a2, struct apk_score *b)
{
	if (a1->unsatisfiable+a2->unsatisfiable < b->unsatisfiable)
		return -1;
	if (a1->unsatisfiable+a2->unsatisfiable > b->unsatisfiable)
		return 1;
	if (a1->preference+a2->preference < b->preference)
		return -1;
	if (a1->preference+a2->preference > b->preference)
		return 1;
	return 0;
}

Timo Teräs's avatar
Timo Teräs committed
981
982
983
984
985
int apk_solver_solve(struct apk_database *db,
		     unsigned short solver_flags,
		     struct apk_dependency_array *world,
		     struct apk_package_array **solution,
		     struct apk_changeset *changeset)
986
987
{
	struct apk_solver_state *ss;
Timo Teräs's avatar
Timo Teräs committed
988
	struct apk_installed_package *ipkg;
989
	struct apk_score zero_score;
990
	int i, r;
991
992
993

	ss = calloc(1, sizeof(struct apk_solver_state));
	ss->db = db;
Timo Teräs's avatar
Timo Teräs committed
994
	ss->solver_flags = solver_flags;
995
	ss->topology_position = -1;
Timo Teräs's avatar
Timo Teräs committed
996
	ss->best_score = (struct apk_score){ .unsatisfiable = -1, .preference = -1 };
997
	list_init(&ss->unsolved_list_head);
998
999
1000

	for (i = 0; i < world->num; i++)
		sort_name(ss, world->item[i].name);
Timo Teräs's avatar
Timo Teräs committed
1001
1002
	list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list)
		sort_name(ss, ipkg->pkg->name);
1003

1004
	foreach_dependency(ss, world, apply_constraint);
1005
1006
	zero_score = ss->score;

1007
	do {
1008
1009
1010
1011
1012
1013
		if (ss->topology_position <= ss->penalty_topology) {
			ss->penalty_score = zero_score;
			ss->penalty_topology = 0;
		}

		if (cmpscore2(&ss->score, &ss->penalty_score, &ss->best_score) < 0) {
1014
1015
			r = expand_branch(ss);
			if (r) {
Timo Teräs's avatar
Timo Teräs committed
1016
1017
1018
1019
1020
1021
1022
				dbg_printf("solution with: %d unsatisfiable, %d preference\n",
					   ss->score.unsatisfiable,
					   ss->score.preference);

				if (cmpscore(&ss->score, &ss->best_score) < 0)
					record_solution(ss);

1023
				if (cmpscore(&zero_score, &ss->score) >= 0) {
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
					/* found solution - it is optimal because we permutate
					 * each preferred local option first, and permutations
					 * happen in topologally sorted order. */
					r = 0;
					break;
				}
				r = next_branch(ss);
			}
		} else {
			r = next_branch(ss);
1034
		}
1035
	} while (r == 0);
1036
1037

	/* collect packages */
1038
1039
1040
1041
1042
	if (changeset != NULL) {
		generate_changeset(db, ss->best_solution, changeset,
				   ss->solver_flags);
	}
	if (solution != NULL) {
1043
1044
		qsort(ss->best_solution->item, ss->best_solution->num,
		      sizeof(struct apk_package *), compare_package_name);
Timo Teräs's avatar
Timo Teräs committed
1045
		*solution = ss->best_solution;
1046
	} else {
Timo Teräs's avatar
Timo Teräs committed
1047
		apk_package_array_free(&ss->best_solution);
1048
1049
	}
	r = ss->best_score.unsatisfiable;
1050
	apk_solver_free(db);
1051
1052
1053
1054
1055
	free(ss);

	return r;
}

Timo Teräs's avatar
Timo Teräs committed
1056
1057
1058
static void print_change(struct apk_database *db,
			 struct apk_change *change,
			 int cur, int total)
1059
{
Timo Teräs's avatar
Timo Teräs committed
1060
1061
1062
1063
1064
1065
	struct apk_name *name;
	struct apk_package *oldpkg = change->oldpkg;
	struct apk_package *newpkg = change->newpkg;
	const char *msg = NULL;
	char status[64];
	int r;
1066

Timo Teräs's avatar
Timo Teräs committed
1067
1068
	snprintf(status, sizeof(status), "(%i/%i)", cur+1, total);
	status[sizeof(status) - 1] = '\0';
1069

Timo Teräs's avatar
Timo Teräs committed
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
	if (oldpkg != NULL)
		name = oldpkg->name;
	else
		name = newpkg->name;

	if (oldpkg == NULL) {
		apk_message("%s Installing %s (" BLOB_FMT ")",
			    status, name->name,
			    BLOB_PRINTF(*newpkg->version));
	} else if (newpkg == NULL) {
		apk_message("%s Purging %s (" BLOB_FMT ")",
			    status, name->name,
			    BLOB_PRINTF(*oldpkg->version));
	} else {
		r = apk_pkg_version_compare(newpkg, oldpkg);
		switch (r) {
		case APK_VERSION_LESS:
			msg = "Downgrading";
			break;
		case APK_VERSION_EQUAL:
			if (newpkg == oldpkg)
				msg = "Re-installing";
			else
				msg = "Replacing";
			break;
		case APK_VERSION_GREATER:
			msg = "Upgrading";
			break;
		}
		apk_message("%s %s %s (" BLOB_FMT " -> " BLOB_FMT ")",
			    status, msg, name->name,
			    BLOB_PRINTF(*oldpkg->version),
			    BLOB_PRINTF(*newpkg->version));
1103
	}
Timo Teräs's avatar
Timo Teräs committed
1104
}
1105

Timo Teräs's avatar
Timo Teräs committed
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
struct apk_stats {
	unsigned int bytes;
	unsigned int packages;
};

static void count_change(struct apk_change *change, struct apk_stats *stats)
{
	if (change->newpkg != NULL) {
		stats->bytes += change->newpkg->installed_size;
		stats->packages ++;
	}
	if (change->oldpkg != NULL)
		stats->packages ++;
}

static void draw_progress(int percent)
{
	const int bar_width = apk_get_screen_width() - 7;
	int i;

	fprintf(stderr, "\e7%3i%% [", percent);
	for (i = 0; i < bar_width * percent / 100; i++)
		fputc('#', stderr);
	for (; i < bar_width; i++)
		fputc(' ', stderr);
	fputc(']', stderr);
	fflush(stderr);
	fputs("\e8\e[0K", stderr);
1134
1135
}

Timo Teräs's avatar
Timo Teräs committed
1136
1137
1138
1139
1140
1141
1142
1143
struct progress {
	struct apk_stats done;
	struct apk_stats total;
	struct apk_package *pkg;
	size_t count;
};

static void progress_cb(void *ctx, size_t progress)
1144
{
Timo Teräs's avatar
Timo Teräs committed
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
	struct progress *prog = (struct progress *) ctx;
	size_t partial = 0, count;

	if (prog->pkg != NULL)
		partial = muldiv(progress, prog->pkg->installed_size, APK_PROGRESS_SCALE);

        count = muldiv(100, prog->done.bytes + prog->done.packages + partial,
		       prog->total.bytes + prog->total.packages);

	if (prog->count != count)
		draw_progress(count);
	prog->count = count;
}

static int dump_packages(struct apk_changeset *changeset,
			 int (*cmp)(struct apk_change *change),
			 const char *msg)
{
	struct apk_change *change;
1164
	struct apk_name *name;
1165
	struct apk_indent indent = { .indent = 2 };
Timo Teräs's avatar
Timo Teräs committed
1166
	int match = 0, i;
1167

Timo Teräs's avatar
Timo Teräs committed
1168
1169
1170
1171
1172
	for (i = 0; i < changeset->changes->num; i++) {
		change = &changeset->changes->item[i];
		if (!cmp(change))
			continue;
		if (match == 0)
1173
			printf("%s:\n", msg);
Timo Teräs's avatar
Timo Teräs committed
1174
1175
1176
1177
1178
1179
1180
		if (change->newpkg != NULL)
			name = change->newpkg->name;
		else
			name = change->oldpkg->name;

		apk_print_indented(&indent, APK_BLOB_STR(name->name));
		match++;
1181
	}
Timo Teräs's avatar
Timo Teräs committed
1182
1183
1184
1185
	if (match)
		printf("\n");
	return match;
}
1186

Timo Teräs's avatar
Timo Teräs committed
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212 </