applets: start using solver code

still todo:
  - 'fix' is missing
  - 'del -R' does not work
  - 'upgrade' does not do self-upgrade first

... and a lot of testing.

19 files changed, 533 insertions, 1353 deletions

diff --git a/.gitignore b/.gitignore
index c0c96c7..774f9fb 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,6 +1,7 @@
 src/apk
 src/apk_test
 src/apk.static
+test/*.got
 *.o
 *.d
 *.cmd
diff --git a/src/Makefile b/src/Makefile
index 1405a10..eae7150 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -19,11 +19,11 @@ $(error Build dependencies are not met)
 endif
 
 progs-y			+= apk
-apk-objs		:= apk.o add.o del.o fix.o update.o info.o \
+apk-objs		:= apk.o add.o del.o update.o info.o \
 			   search.o upgrade.o cache.o ver.o index.o fetch.o \
 			   audit.o verify.o dot.o
 
-libapk.so-objs		:= common.o state.o database.o package.o archive.o \
+libapk.so-objs		:= common.o database.o package.o archive.o \
 			   version.o io.o url.o gunzip.o blob.o hash.o print.o \
 			   solver.o
 
diff --git a/src/add.c b/src/add.c
index d63f61d..a572c74 100644
--- a/src/add.c
+++ b/src/add.c
@@ -13,11 +13,12 @@
 #include <stdio.h>
 #include "apk_applet.h"
 #include "apk_database.h"
-#include "apk_state.h"
 #include "apk_print.h"
+#include "apk_solver.h"
 
 struct add_ctx {
 	const char *virtpkg;
+	unsigned short solver_flags;
 };
 
 static int add_parse(void *ctx, struct apk_db_options *dbopts,
@@ -30,7 +31,7 @@ static int add_parse(void *ctx, struct apk_db_options *dbopts,
 		dbopts->open_flags |= APK_OPENF_CREATE;
 		break;
 	case 'u':
-		apk_flags |= APK_UPGRADE;
+		actx->solver_flags |= APK_SOLVERF_UPGRADE;
 		break;
 	case 't':
 		actx->virtpkg = optarg;
@@ -60,11 +61,12 @@ static int non_repository_check(struct apk_database *db)
 static int add_main(void *ctx, struct apk_database *db, int argc, char **argv)
 {
 	struct add_ctx *actx = (struct add_ctx *) ctx;
-	struct apk_state *state = NULL;
 	struct apk_package *virtpkg = NULL;
 	struct apk_dependency virtdep;
-	struct apk_dependency *deps;
-	int i, r = 0, num_deps = 0, errors = 0;
+	struct apk_dependency_array *world = NULL;
+	int i, r = 0;
+
+	apk_dependency_array_copy(&world, db->world);
 
 	if (actx->virtpkg) {
 		if (non_repository_check(db))
@@ -82,13 +84,8 @@ static int add_main(void *ctx, struct apk_database *db, int argc, char **argv)
 		virtpkg->description = strdup("virtual meta package");
 		virtpkg->arch = apk_blob_atomize(APK_BLOB_STR("noarch"));
 		apk_dep_from_pkg(&virtdep, db, virtpkg);
-		virtdep.name->flags |= APK_NAME_TOPLEVEL;
 		virtpkg = apk_db_pkg_add(db, virtpkg);
-		num_deps = 1;
-	} else
-		num_deps = argc;
-
-	deps = alloca(sizeof(struct apk_dependency) * num_deps);
+	}
 
 	for (i = 0; i < argc; i++) {
 		struct apk_dependency dep;
@@ -117,35 +114,15 @@ static int add_main(void *ctx, struct apk_database *db, int argc, char **argv)
 
 		if (virtpkg)
 			apk_deps_add(&virtpkg->depends, &dep);
-		else {
-			deps[i] = dep;
-			deps[i].name->flags |= APK_NAME_TOPLEVEL_OVERRIDE;
-		}
+		else
+			apk_deps_add(&world, &dep);
 	}
 	if (virtpkg)
-		deps[0] = virtdep;
+		apk_deps_add(&world, &virtdep);
 
-	state = apk_state_new(db);
-	if (state == NULL)
-		return -1;
+	r = apk_solver_commit(db, actx->solver_flags, world);
+	apk_dependency_array_free(&world);
 
-	for (i = 0; i < num_deps; i++) {
-		r = apk_state_lock_dependency(state, &deps[i]);
-		if (r == 0) {
-			apk_deps_add(&db->world, &deps[i]);
-			deps[i].name->flags |= APK_NAME_TOPLEVEL;
-		} else {
-			errors++;
-		}
-	}
-	if (errors && !(apk_flags & APK_FORCE)) {
-		apk_state_print_errors(state);
-		r = -1;
-	} else {
-		r = apk_state_commit(state);
-	}
-	if (state != NULL)
-		apk_state_unref(state);
 	return r;
 }
 
diff --git a/src/apk_database.h b/src/apk_database.h
index a077fe2..61ced6c 100644
--- a/src/apk_database.h
+++ b/src/apk_database.h
@@ -81,15 +81,12 @@ struct apk_db_dir_instance {
 	gid_t gid;
 };
 
-#define APK_NAME_TOPLEVEL		0x0001
-#define APK_NAME_REINSTALL		0x0002
-#define APK_NAME_TOPLEVEL_OVERRIDE	0x0004
-#define APK_NAME_VISITED		0x8000
-
 struct apk_name {
 	apk_hash_node hash_node;
-	unsigned int id;
-	unsigned int flags;
+	union {
+		int state_int;
+		void *state_ptr;
+	};
 	char *name;
 	struct apk_package_array *pkgs;
 	struct apk_name_array *rdepends;
@@ -121,7 +118,7 @@ struct apk_db_options {
 struct apk_database {
 	char *root;
 	int root_fd, lock_fd, cache_fd, cachetmp_fd, keys_fd;
-	unsigned name_id, num_repos;
+	unsigned num_repos;
 	const char *cache_dir;
 	char *cache_remount_dir;
 	apk_blob_t *arch;
diff --git a/src/apk_defines.h b/src/apk_defines.h
index b11d181..deb550e 100644
--- a/src/apk_defines.h
+++ b/src/apk_defines.h
@@ -56,14 +56,11 @@ extern char **apk_argv;
 #define APK_SIMULATE		0x0002
 #define APK_CLEAN_PROTECTED	0x0004
 #define APK_PROGRESS		0x0008
-#define APK_UPGRADE		0x0010
 #define APK_RECURSIVE		0x0020
-#define APK_PREFER_AVAILABLE	0x0040
 #define APK_UPDATE_CACHE	0x0080
 #define APK_ALLOW_UNTRUSTED	0x0100
 #define APK_PURGE		0x0200
 #define APK_INTERACTIVE		0x0400
-#define APK_RECURSIVE_DELETE	0x0800
 #define APK_NO_NETWORK		0x1000
 #define APK_OVERLAY_FROM_STDIN	0x2000
 
@@ -108,6 +105,12 @@ void *apk_array_resize(void *array, size_t new_size, size_t elem_size);
 	{								\
 		*a = apk_array_resize(*a, size, sizeof(elem_type_name));\
 	}								\
+	static inline void						\
+	array_type_name##_copy(struct array_type_name **a, struct array_type_name *b)\
+	{								\
+		*a = apk_array_resize(*a, b->num, sizeof(elem_type_name));\
+		memcpy((*a)->item, b->item, b->num * sizeof(elem_type_name));\
+	}								\
 	static inline elem_type_name *					\
 	array_type_name##_add(struct array_type_name **a)		\
 	{								\
diff --git a/src/apk_solver.h b/src/apk_solver.h
index f634b2f..5ab3147 100644
--- a/src/apk_solver.h
+++ b/src/apk_solver.h
@@ -22,12 +22,19 @@ struct apk_changeset {
 	struct apk_change_array *changes;
 };
 
-void apk_solver_sort(struct apk_database *db);
-int apk_solver_solve(struct apk_database *db, struct apk_dependency_array *world,
-		     struct apk_package_array **solution, int allow_errors);
-int apk_solver_generate_changeset(struct apk_database *db,
-				  struct apk_package_array *solution,
-				  struct apk_changeset *changeset);
+#define APK_SOLVERF_UPGRADE		0x0001
+#define APK_SOLVERF_AVAILABLE		0x0002
+#define APK_SOLVERF_REINSTALL		0x0004
+
+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);
+
+int apk_solver_commit(struct apk_database *db,
+		      unsigned short solver_flags,
+		      struct apk_dependency_array *world);
 
 #endif
 
diff --git a/src/apk_state.h b/src/apk_state.h
deleted file mode 100644
index e0df54e..0000000
--- a/src/apk_state.h
+++ /dev/null
@@ -1,47 +0,0 @@
-/* apk_state.h - Alpine Package Keeper (APK)
- *
- * Copyright (C) 2005-2008 Natanael Copa <n@tanael.org>
- * Copyright (C) 2008 Timo Teräs <timo.teras@iki.fi>
- * 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.
- */
-
-#ifndef APK_STATE_H
-#define APK_STATE_H
-
-#include "apk_database.h"
-
-typedef void *apk_name_state_t;
-
-struct apk_change {
-	struct list_head change_list;
-	struct apk_package *oldpkg;
-	struct apk_package *newpkg;
-};
-
-struct apk_state {
-	unsigned int refs, num_names, num_changes;
-	int print_ok;
-	struct apk_database *db;
-	struct list_head change_list_head;
-	struct apk_package_array *conflicts;
-	struct apk_name_array *missing;
-	apk_name_state_t name[];
-};
-
-struct apk_state *apk_state_new(struct apk_database *db);
-struct apk_state *apk_state_dup(struct apk_state *state);
-void apk_state_unref(struct apk_state *state);
-
-void apk_state_print_errors(struct apk_state *state);
-int apk_state_commit(struct apk_state *state);
-int apk_state_lock_dependency(struct apk_state *state,
-			      struct apk_dependency *dep);
-int apk_state_lock_name(struct apk_state *state,
-			struct apk_name *name,
-			struct apk_package *newpkg);
-
-#endif
diff --git a/src/cache.c b/src/cache.c
index ac1fba7..cf468fd 100644
--- a/src/cache.c
+++ b/src/cache.c
@@ -17,36 +17,30 @@
 #include "apk_defines.h"
 #include "apk_applet.h"
 #include "apk_database.h"
-#include "apk_state.h"
 #include "apk_package.h"
 #include "apk_print.h"
+#include "apk_solver.h"
 
 #define CACHE_CLEAN	BIT(0)
 #define CACHE_DOWNLOAD	BIT(1)
 
 static int cache_download(struct apk_database *db)
 {
-	struct apk_state *state;
+	struct apk_changeset changeset;
 	struct apk_change *change;
 	struct apk_package *pkg;
 	struct apk_repository *repo;
 	char item[PATH_MAX], cacheitem[PATH_MAX];
 	int i, r = 0;
 
-	state = apk_state_new(db);
-	if (state == NULL)
-		goto err;
-
-	for (i = 0; i < db->world->num; i++) {
-		r = apk_state_lock_dependency(state, &db->world->item[i]);
-		if (r != 0) {
-			apk_error("Unable to select version for '%s': %d",
-				  db->world->item[i].name->name, r);
-			goto err;
-		}
+	r = apk_solver_solve(db, 0, db->world, NULL, &changeset);
+	if (r != 0) {
+		apk_error("Unable to select packages. Run apk fix.");
+		return r;
 	}
 
-	list_for_each_entry(change, &state->change_list_head, change_list) {
+	for (i = 0; i < changeset.changes->num; i++) {
+		change = &changeset.changes->item[i];
 		pkg = change->newpkg;
 
 		apk_pkg_format_cache(pkg, APK_BLOB_BUF(cacheitem));
@@ -63,9 +57,6 @@ static int cache_download(struct apk_database *db)
 					APK_SIGN_VERIFY_IDENTITY);
 	}
 
-err:
-	if (state != NULL)
-		apk_state_unref(state);
 	return r;
 }
 
diff --git a/src/database.c b/src/database.c
index ade8a90..664d235 100644
--- a/src/database.c
+++ b/src/database.c
@@ -29,7 +29,6 @@
 #include "apk_defines.h"
 #include "apk_package.h"
 #include "apk_database.h"
-#include "apk_state.h"
 #include "apk_applet.h"
 #include "apk_archive.h"
 #include "apk_print.h"
@@ -207,7 +206,6 @@ struct apk_name *apk_db_get_name(struct apk_database *db, apk_blob_t name)
 		return NULL;
 
 	pn->name = apk_blob_cstr(name);
-	pn->id = db->name_id++;
 	apk_package_array_init(&pn->pkgs);
 	apk_name_array_init(&pn->rdepends);
 	apk_name_array_init(&pn->rinstall_if);
@@ -885,7 +883,7 @@ static int apk_db_read_state(struct apk_database *db, int flags)
 	struct apk_istream *is;
 	struct apk_bstream *bs;
 	apk_blob_t blob;
-	int i, r;
+	int r;
 
 	/* Read:
 	 * 1. installed repository
@@ -901,9 +899,6 @@ static int apk_db_read_state(struct apk_database *db, int flags)
 			return -ENOENT;
 		apk_deps_parse(db, &db->world, blob);
 		free(blob.ptr);
-
-		for (i = 0; i < db->world->num; i++)
-			db->world->item[i].name->flags |= APK_NAME_TOPLEVEL;
 	}
 
 	if (!(flags & APK_OPENF_NO_INSTALLED)) {
diff --git a/src/del.c b/src/del.c
index 4c00ade..cbf0686 100644
--- a/src/del.c
+++ b/src/del.c
@@ -11,17 +11,16 @@
 
 #include <stdio.h>
 #include "apk_applet.h"
-#include "apk_state.h"
 #include "apk_database.h"
 #include "apk_print.h"
+#include "apk_solver.h"
 
 static int del_parse(void *ctx, struct apk_db_options *db,
 		     int optch, int optindex, const char *optarg)
 {
 	switch (optch) {
 	case 'r':
-		apk_flags |= APK_RECURSIVE_DELETE;
-		break;
+		/* FIXME: Reimplement recursive delete. */
 	default:
 		return -1;
 	}
@@ -30,40 +29,17 @@ static int del_parse(void *ctx, struct apk_db_options *db,
 
 static int del_main(void *ctx, struct apk_database *db, int argc, char **argv)
 {
-	struct apk_state *state;
 	struct apk_name *name;
+	struct apk_dependency_array *world = NULL;
 	int i, r = 0;
 
+	apk_dependency_array_copy(&world, db->world);
 	for (i = 0; i < argc; i++) {
 		name = apk_db_get_name(db, APK_BLOB_STR(argv[i]));
-		name->flags &= ~APK_NAME_TOPLEVEL;
-		name->flags |= APK_NAME_TOPLEVEL_OVERRIDE;
-		apk_deps_del(&db->world, name);
+		apk_deps_del(&world, name);
 	}
-
-	state = apk_state_new(db);
-	if (state == NULL)
-		goto err;
-
-	for (i = 0; i < argc; i++) {
-		struct apk_dependency dep;
-
-		name = apk_db_get_name(db, APK_BLOB_STR(argv[i]));
-		dep = (struct apk_dependency) {
-			.name = name,
-			.version = apk_blob_atomize(APK_BLOB_NULL),
-			.result_mask = APK_DEPMASK_CONFLICT,
-		};
-
-		r |= apk_state_lock_dependency(state, &dep);
-	}
-	if (r == 0)
-		r = apk_state_commit(state);
-	else
-		apk_state_print_errors(state);
-err:
-	if (state != NULL)
-		apk_state_unref(state);
+	r = apk_solver_commit(db, 0, world);
+	apk_dependency_array_free(&world);
 
 	return r;
 }
diff --git a/src/dot.c b/src/dot.c
index 633954b..18505b0 100644
--- a/src/dot.c
+++ b/src/dot.c
@@ -71,10 +71,10 @@ static int dump_pkg(struct dot_ctx *ctx, struct apk_package *pkg)
 			printf("  \"" PKG_VER_FMT "\" -> \"%s\" [color=red];\n",
 				PKG_VER_PRINTF(pkg),
 				name->name);
-			if (!(name->flags & APK_NAME_VISITED)) {
+			if (!name->state_int) {
 				printf("  \"%s\" [style=dashed, color=red, fontcolor=red, shape=octagon];\n",
 					name->name);
-				name->flags |= APK_NAME_VISITED;
+				name->state_int = 1;
 			}
 		} else {
 			for (j = 0; j < name->pkgs->num; j++) {
diff --git a/src/fetch.c b/src/fetch.c
index 72b481d..f6fbc2e 100644
--- a/src/fetch.c
+++ b/src/fetch.c
@@ -18,7 +18,6 @@
 
 #include "apk_applet.h"
 #include "apk_database.h"
-#include "apk_state.h"
 #include "apk_io.h"
 #include "apk_print.h"
 
@@ -180,6 +179,7 @@ static int fetch_main(void *ctx, struct apk_database *db, int argc, char **argv)
 			.result_mask = APK_DEPMASK_REQUIRE,
 		};
 
+#if 0
 		if (fctx->flags & FETCH_RECURSIVE) {
 			struct apk_state *state;
 			struct apk_change *change;
@@ -203,7 +203,9 @@ static int fetch_main(void *ctx, struct apk_database *db, int argc, char **argv)
 			}
 
 			apk_state_unref(state);
-		} else {
+		} else
+#endif
+		{
 			struct apk_package *pkg = NULL;
 
 			for (j = 0; j < dep.name->pkgs->num; j++)
diff --git a/src/fix.c b/src/fix.c
index 48cab9c..e345134 100644
--- a/src/fix.c
+++ b/src/fix.c
@@ -16,6 +16,8 @@
 #include "apk_state.h"
 #include "apk_print.h"
 
+/* FIXME: reimplement fix applet */
+
 struct fix_ctx {
 	unsigned int reinstall : 1;
 };
diff --git a/src/info.c b/src/info.c
index 3ae51f0..bce7a34 100644
--- a/src/info.c
+++ b/src/info.c
@@ -15,7 +15,6 @@
 #include "apk_applet.h"
 #include "apk_package.h"
 #include "apk_database.h"
-#include "apk_state.h"
 #include "apk_print.h"
 
 struct info_ctx {
diff --git a/src/package.c b/src/package.c
index 28e091b..45a9677 100644
--- a/src/package.c
+++ b/src/package.c
@@ -27,7 +27,6 @@
 #include "apk_archive.h"
 #include "apk_package.h"
 #include "apk_database.h"
-#include "apk_state.h"
 #include "apk_print.h"
 
 void apk_pkg_format_plain(struct apk_package *pkg, apk_blob_t to)
diff --git a/src/search.c b/src/search.c
index 3973552..bc85e2f 100644
--- a/src/search.c
+++ b/src/search.c
@@ -15,7 +15,6 @@
 #include "apk_applet.h"
 #include "apk_package.h"
 #include "apk_database.h"
-#include "apk_state.h"
 
 struct search_ctx {
 	int (*match)(struct apk_package *pkg, const char *str);
diff --git a/src/solver.c b/src/solver.c
index 1f3c394..72eb3e1 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -15,6 +15,8 @@
 #include "apk_package.h"
 #include "apk_solver.h"
 
+#include "apk_print.h"
+
 #if 0
 #include <stdio.h>
 #define dbg_printf(args...) fprintf(stderr, args)
@@ -43,6 +45,7 @@ struct apk_package_state {
 struct apk_name_state {
 	struct list_head unsolved_list;
 	struct apk_package *chosen;
+	unsigned short solver_flags;
 	unsigned short flags;
 	unsigned short requirers;
 	unsigned short install_ifs;
@@ -50,15 +53,14 @@ struct apk_name_state {
 
 struct apk_solver_state {
 	struct apk_database *db;
-	struct apk_name_state *name_state;
 	unsigned num_topology_positions;
 
 	struct list_head unsolved_list_head;
 	struct apk_package *latest_decision;
 	unsigned int topology_position;
 	unsigned int assigned_names;
+	unsigned short solver_flags;
 	unsigned short cur_unsatisfiable;
-	unsigned short allow_errors;
 
 	struct apk_package_array *best_solution;
 	unsigned short best_unsatisfiable;
@@ -69,11 +71,18 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
 static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
 			  int flags);
 
-static inline struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
+static struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
 {
 	return (struct apk_package_state*) pkg->state_ptr;
 }
 
+static struct apk_name_state *name_to_ns(struct apk_name *name)
+{
+	if (name->state_ptr == NULL)
+		name->state_ptr = calloc(1, sizeof(struct apk_name_state));
+	return (struct apk_name_state*) name->state_ptr;
+}
+
 static inline int pkg_available(struct apk_database *db, struct apk_package *pkg)
 {
 	if (pkg->installed_size == 0)
@@ -151,6 +160,7 @@ static void sort_hard_dependencies(struct apk_solver_state *ss, struct apk_packa
 	ps = pkg_to_ps(pkg);
 	if (ps->topology_hard)
 		return;
+	ps->topology_hard = -1;
 
 	/* Consider hard dependencies only */
 	foreach_dependency_pkg(ss, pkg->depends, sort_hard_dependencies);
@@ -170,6 +180,7 @@ static void sort_soft_dependencies(struct apk_solver_state *ss, struct apk_packa
 	ps = pkg_to_ps(pkg);
 	if (ps->topology_soft != ps->topology_hard)
 		return;
+	ps->topology_soft = -1;
 
 	/* Soft reverse dependencies aka. install_if */
 	foreach_rinstall_if_pkg(ss, pkg, sort_hard_dependencies);
@@ -200,9 +211,11 @@ static void prepare_name(struct apk_solver_state *ss, struct apk_name *name,
 	for (i = 0; i < name->pkgs->num; i++) {
 		struct apk_package *pkg = name->pkgs->item[i];
 		struct apk_package_state *ps = pkg_to_ps(pkg);
+		struct apk_name_state *ns = name_to_ns(pkg->name);
 
 		/* if package is needed for (re-)install */
-		if ((name->flags & APK_NAME_REINSTALL) || (pkg->ipkg == NULL)) {
+		if ((pkg->ipkg == NULL) ||
+		    (ns->solver_flags & APK_SOLVERF_REINSTALL)) {
 			/* and it's not available, we can't use it */
 			if (!pkg_available(ss->db, pkg))
 				ps->conflicts++;
@@ -237,7 +250,7 @@ static int get_pkg_expansion_flags(struct apk_solver_state *ss, struct apk_packa
 		    ps0->conflicts != 0)
 			continue;
 
-		if (apk_flags & APK_PREFER_AVAILABLE) {
+		if (ss->solver_flags & APK_SOLVERF_AVAILABLE) {
 			/* pkg available, pkg0 not */
 			if (pkg->repos != 0 && pkg0->repos == 0)
 				continue;
@@ -246,7 +259,7 @@ static int get_pkg_expansion_flags(struct apk_solver_state *ss, struct apk_packa
 				return APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH;
 		}
 
-		if (!(apk_flags & APK_UPGRADE)) {
+		if (!(ss->solver_flags & APK_SOLVERF_UPGRADE)) {
 			/* not upgrading, prefer the installed package */
 			if (pkg->ipkg == NULL && pkg0->ipkg != NULL)
 				return APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH;
@@ -269,13 +282,13 @@ static int get_pkg_expansion_flags(struct apk_solver_state *ss, struct apk_packa
 
 static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg)
 {
-	struct apk_name_state *ns = &ss->name_state[pkg->name->id];
+	struct apk_name_state *ns;
 	int i, missing = 0;
 
 	for (i = 0; i < pkg->install_if->num; i++) {
 		struct apk_dependency *dep = &pkg->install_if->item[i];
 
-		ns = &ss->name_state[dep->name->id];
+		ns = name_to_ns(dep->name);
 		if (!(ns->flags & APK_NAMESTF_LOCKED) ||
 		    !apk_dep_is_satisfied(dep, ns->chosen))
 			missing++;
@@ -354,7 +367,7 @@ static void trigger_install_if(struct apk_solver_state *ss,
 			       struct apk_package *pkg)
 {
 	if (install_if_missing(ss, pkg) == 0) {
-		struct apk_name_state *ns = ns = &ss->name_state[pkg->name->id];
+		struct apk_name_state *ns = ns = name_to_ns(pkg->name);
 
 		dbg_printf("trigger_install_if: " PKG_VER_FMT " triggered\n",
 			   PKG_VER_PRINTF(pkg));
@@ -367,7 +380,7 @@ static void untrigger_install_if(struct apk_solver_state *ss,
 			       struct apk_package *pkg)
 {
 	if (install_if_missing(ss, pkg) != 1) {
-		struct apk_name_state *ns = ns = &ss->name_state[pkg->name->id];
+		struct apk_name_state *ns = name_to_ns(pkg->name);
 
 		dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n",
 			   PKG_VER_PRINTF(pkg));
@@ -380,7 +393,7 @@ static void apply_decision(struct apk_solver_state *ss,
 			   struct apk_package *pkg,
 			   struct apk_package_state *ps)
 {
-	struct apk_name_state *ns = &ss->name_state[pkg->name->id];
+	struct apk_name_state *ns = name_to_ns(pkg->name);
 
 	dbg_printf("apply_decision: " PKG_VER_FMT " %s\n", PKG_VER_PRINTF(pkg),
 		   (ps->flags & APK_PKGSTF_INSTALL) ? "INSTALL" : "NO_INSTALL");
@@ -407,7 +420,7 @@ static void undo_decision(struct apk_solver_state *ss,
 			  struct apk_package *pkg,
 			  struct apk_package_state *ps)
 {
-	struct apk_name_state *ns = &ss->name_state[pkg->name->id];
+	struct apk_name_state *ns = name_to_ns(pkg->name);
 
 	dbg_printf("undo_decision: " PKG_VER_FMT " %s\n", PKG_VER_PRINTF(pkg),
 		   (ps->flags & APK_PKGSTF_INSTALL) ? "INSTALL" : "NO_INSTALL");
@@ -497,7 +510,7 @@ static int next_branch(struct apk_solver_state *ss)
 static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
 {
 	struct apk_name *name = dep->name;
-	struct apk_name_state *ns = &ss->name_state[name->id];
+	struct apk_name_state *ns = name_to_ns(name);
 	int i;
 
 	prepare_name(ss, name, ns);
@@ -533,7 +546,7 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
 static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
 {
 	struct apk_name *name = dep->name;
-	struct apk_name_state *ns = &ss->name_state[name->id];
+	struct apk_name_state *ns = name_to_ns(name);
 	int i;
 
 	if (ns->flags & APK_NAMESTF_LOCKED) {
@@ -589,7 +602,7 @@ static int expand_branch(struct apk_solver_state *ss)
 
 	/* someone needs to provide this name -- find next eligible
 	 * provider candidate */
-	ns = &ss->name_state[pkg0->name->id];
+	ns = name_to_ns(pkg0->name);
 	dbg_printf("expand_branch: %s\n", pkg0->name->name);
 
 	push_decision(ss, pkg0, get_pkg_expansion_flags(ss, pkg0));
@@ -633,27 +646,123 @@ static int compare_package_name(const void *p1, const void *p2)
 	return strcmp((*c1)->name->name, (*c2)->name->name);
 }
 
-int apk_solver_solve(struct apk_database *db, struct apk_dependency_array *world,
-		     struct apk_package_array **solution, int allow_errors)
+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 */
+			return  pkg_to_ps(c2->oldpkg)->topology_hard -
+				pkg_to_ps(c1->oldpkg)->topology_hard;
+
+		/* c1 deleted, c2 installed -> c2 first*/
+		return -1;
+	}
+	if (c2->newpkg == NULL)
+		/* c1 installed, c2 deleted -> c1 first*/
+		return 1;
+
+	return  pkg_to_ps(c1->newpkg)->topology_hard -
+		pkg_to_ps(c2->newpkg)->topology_hard;
+}
+
+static int generate_changeset(struct apk_database *db,
+			      struct apk_package_array *solution,
+			      struct apk_changeset *changeset)
+{
+	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];
+		if ((pkg->ipkg == NULL) ||
+		    (name_to_ns(pkg->name)->solver_flags & APK_SOLVERF_REINSTALL))
+			num_installs++;
+	}
+	list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
+		name = ipkg->pkg->name;
+		ns = name_to_ns(name);
+		if ((ns->chosen == NULL) || !(ns->flags & APK_NAMESTF_LOCKED))
+			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);
+		if ((ns->chosen == NULL) || !(ns->flags & APK_NAMESTF_LOCKED)) {
+			changeset->changes->item[ci].oldpkg = ipkg->pkg;
+			ci++;
+		}
+	}
+	for (i = 0; i < solution->num; i++) {
+		pkg = solution->item[i];
+		name = pkg->name;
+
+		if ((pkg->ipkg == NULL) ||
+		    (name_to_ns(name)->solver_flags & APK_SOLVERF_REINSTALL)) {
+			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;
+}
+
+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)
 {
 	struct apk_solver_state *ss;
+	struct apk_installed_package *ipkg;
 	int i, r;
 
 	ss = calloc(1, sizeof(struct apk_solver_state));
 	ss->db = db;
+	ss->solver_flags = solver_flags;
 	ss->topology_position = -1;
 	ss->best_unsatisfiable = -1;
-	ss->allow_errors = allow_errors;
 	list_init(&ss->unsolved_list_head);
-	ss->name_state = calloc(db->available.names.num_items + 1, sizeof(struct apk_name_state));
 
 	for (i = 0; i < world->num; i++)
 		sort_name(ss, world->item[i].name);
+	list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list)
+		sort_name(ss, ipkg->pkg->name);
 
 	foreach_dependency(ss, world, apply_constraint);
 	do {
-		if (ss->allow_errors ||
-		    ss->cur_unsatisfiable < ss->best_unsatisfiable) {
+		if (ss->cur_unsatisfiable < ss->best_unsatisfiable) {
 			r = expand_branch(ss);
 			if (r) {
 				dbg_printf("solution with %d unsatisfiable\n",
@@ -677,97 +786,352 @@ int apk_solver_solve(struct apk_database *db, struct apk_dependency_array *world
 	/* collect packages */
 	if (r == 0 && ss->cur_unsatisfiable == 0) {
 		record_solution(ss);
-		*solution = ss->best_solution;
+		if (changeset != NULL)
+			generate_changeset(db, ss->best_solution, changeset);
 		r = 0;
-	} else if (ss->allow_errors) {
-		*solution = ss->best_solution;
+	} else {
 		qsort(ss->best_solution->item, ss->best_solution->num,
 		      sizeof(struct apk_package *), compare_package_name);
 		r = ss->best_unsatisfiable;
-	} else
-		r = -1;
+	}
+
+	if (solution != NULL)
+		*solution = ss->best_solution;
+	else
+		apk_package_array_free(&ss->best_solution);
 
-	free(ss->name_state);
+	apk_hash_foreach(&db->available.names, free_state, NULL);
 	free(ss);
 
 	return r;
 }
 
-static int compare_change(const void *p1, const void *p2)
+static void print_change(struct apk_database *db,
+			 struct apk_change *change,
+			 int cur, int total)
 {
-	const struct apk_change *c1 = (const struct apk_change *) p1;
-	const struct apk_change *c2 = (const struct apk_change *) p2;
+	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;
 
-	if (c1->newpkg == NULL) {
-		if (c2->newpkg == NULL)
-			/* both deleted - reverse topology order */
-			return  pkg_to_ps(c2->oldpkg)->topology_hard -
-				pkg_to_ps(c1->oldpkg)->topology_hard;
+	snprintf(status, sizeof(status), "(%i/%i)", cur+1, total);
+	status[sizeof(status) - 1] = '\0';
 
-		/* c1 deleted, c2 installed -> c2 first*/
-		return -1;
+	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));
 	}
-	if (c2->newpkg == NULL)
-		/* c1 installed, c2 deleted -> c1 first*/
-		return 1;
+}
 
-	return  pkg_to_ps(c1->newpkg)->topology_hard -
-		pkg_to_ps(c2->newpkg)->topology_hard;
+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);
 }
 
-int apk_solver_generate_changeset(struct apk_database *db,
-				  struct apk_package_array *solution,
-				  struct apk_changeset *changeset)
+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)
 {
+	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;
 	struct apk_name *name;
-	struct apk_package *pkg, *pkg0;
-	struct apk_installed_package *ipkg;
-	int num_installs = 0, num_removed = 0, ci = 0;
-	int i, j;
+	struct apk_indent indent = { 0, 2 };
+	int match = 0, i;
 
-	/* calculate change set size */
-	for (i = 0; i < solution->num; i++) {
-		pkg = solution->item[i];
-		name = pkg->name;
-		if (pkg->ipkg == NULL || (name->flags & APK_NAME_REINSTALL))
-			num_installs++;
-		name->flags |= APK_NAME_VISITED;
+	for (i = 0; i < changeset->changes->num; i++) {
+		change = &changeset->changes->item[i];
+		if (!cmp(change))
+			continue;
+		if (match == 0)
+			printf("%s:\n ", msg);
+		if (change->newpkg != NULL)
+			name = change->newpkg->name;
+		else
+			name = change->oldpkg->name;
+
+		apk_print_indented(&indent, APK_BLOB_STR(name->name));
+		match++;
 	}
+	if (match)
+		printf("\n");
+	return match;
+}
 
-	list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
-		if (!(ipkg->pkg->name->flags & APK_NAME_VISITED))
-			num_removed++;
+static int cmp_remove(struct apk_change *change)
+{
+	return change->newpkg == NULL;
+}
+
+static int cmp_new(struct apk_change *change)
+{
+	return change->oldpkg == NULL;
+}
+
+static int cmp_downgrade(struct apk_change *change)
+{
+	if (change->newpkg == NULL || change->oldpkg == NULL)
+		return 0;
+	if (apk_pkg_version_compare(change->newpkg, change->oldpkg)
+	    & APK_VERSION_LESS)
+		return 1;
+	return 0;
+}
+
+static int cmp_upgrade(struct apk_change *change)
+{
+	if (change->newpkg == NULL || change->oldpkg == NULL)
+		return 0;
+
+	/* Count swapping package as upgrade too - this can happen if
+	 * same package version is used after it was rebuilt against
+	 * newer libraries. Basically, different (and probably newer)
+	 * package, but equal version number. */
+	if ((apk_pkg_version_compare(change->newpkg, change->oldpkg) &
+	     (APK_VERSION_GREATER | APK_VERSION_EQUAL)) &&
+	    (change->newpkg != change->oldpkg))
+		return 1;
+
+	return 0;
+}
+
+static int commit_changeset(struct apk_database *db,
+			    struct apk_changeset *changeset,
+			    struct apk_dependency_array *world)
+{
+	struct progress prog;
+	struct apk_change *change;
+	int i, r = 0, size_diff = 0;
+
+	/* Count what needs to be done */
+	memset(&prog, 0, sizeof(prog));
+	for (i = 0; i < changeset->changes->num; i++) {
+		change = &changeset->changes->item[i];
+		count_change(change, &prog.total);
+		if (change->newpkg)
+			size_diff += change->newpkg->installed_size;
+		if (change->oldpkg)
+			size_diff -= change->oldpkg->installed_size;
+	}
+	size_diff /= 1024;
+
+	if (apk_verbosity > 1 || (apk_flags & APK_INTERACTIVE)) {
+		r = dump_packages(changeset, cmp_remove,
+				  "The following packages will be REMOVED");
+		r += dump_packages(changeset, cmp_downgrade,
+				   "The following packages will be DOWNGRADED");
+		if (r || (apk_flags & APK_INTERACTIVE) || apk_verbosity > 2) {
+			dump_packages(changeset, cmp_new,
+				      "The following NEW packages will be installed");
+			dump_packages(changeset, cmp_upgrade,
+				      "The following packages will be upgraded");
+			printf("After this operation, %d kB of %s\n", abs(size_diff),
+			       (size_diff < 0) ?
+			       "disk space will be freed." :
+			       "additional disk space will be used.");
+		}
+		if (apk_flags & APK_INTERACTIVE) {
+			printf("Do you want to continue [Y/n]? ");
+			fflush(stdout);
+			r = fgetc(stdin);
+			if (r != 'y' && r != 'Y' && r != '\n')
+				return -1;
+		}
 	}
 
-	/* construct changeset */
-	apk_change_array_resize(&changeset->changes, num_installs + num_removed);
-	list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
-		if (ipkg->pkg->name->flags & APK_NAME_VISITED)
+	/* Go through changes */
+	r = 0;
+	for (i = 0; i < changeset->changes->num; i++) {
+		change = &changeset->changes->item[i];
+
+		print_change(db, change, i, changeset->changes->num);
+		if (apk_flags & APK_PROGRESS)
+			draw_progress(prog.count);
+		prog.pkg = change->newpkg;
+
+		if (!(apk_flags & APK_SIMULATE)) {
+			r = apk_db_install_pkg(db,
+					       change->oldpkg, change->newpkg,
+					       (apk_flags & APK_PROGRESS) ? progress_cb : NULL,
+					       &prog);
+			if (r != 0)
+				break;
+		}
+
+		count_change(change, &prog.done);
+	}
+	if (apk_flags & APK_PROGRESS)
+		draw_progress(100);
+
+	apk_db_run_triggers(db);
+
+	apk_dependency_array_copy(&db->world, world);
+	apk_db_write_config(db);
+
+	if (r == 0) {
+		apk_message("OK: %d packages, %d dirs, %d files",
+			    db->installed.stats.packages,
+			    db->installed.stats.dirs,
+			    db->installed.stats.files);
+	}
+
+	return r;
+}
+
+static void print_dep_errors(char *label, struct apk_dependency_array *deps)
+{
+	int i, print_label = 1;
+	char buf[256];
+	apk_blob_t p;
+	struct apk_indent indent;
+
+	for (i = 0; i < deps->num; i++) {
+		struct apk_dependency *dep = &deps->item[i];
+		struct apk_package *pkg = (struct apk_package*) dep->name->state_ptr;
+
+		if (pkg != NULL && apk_dep_is_satisfied(dep, pkg))
 			continue;
-		changeset->changes->item[ci].oldpkg = ipkg->pkg;
-		ci++;
+
+		if (print_label) {
+			print_label = 0;
+			indent.x = printf("  %s:", label);
+			indent.indent = indent.x + 1;
+		}
+		p = APK_BLOB_BUF(buf);
+		apk_blob_push_dep(&p, dep);
+		p = apk_blob_pushed(APK_BLOB_BUF(buf), p);
+		apk_print_indented(&indent, p);
 	}
+	if (!print_label)
+		printf("\n");
+}
+
+static void print_errors(struct apk_database *db,
+			 struct apk_package_array *solution,
+			 struct apk_dependency_array *world,
+			 int unsatisfiable)
+{
+	int i;
+
+	apk_error("%d unsatisfiable dependencies:", unsatisfiable);
+
 	for (i = 0; i < solution->num; i++) {
-		pkg = solution->item[i];
-		name = pkg->name;
+		struct apk_package *pkg = solution->item[i];
+		pkg->name->state_ptr = pkg;
+	}
 
-		if (pkg->ipkg == NULL || (name->flags & APK_NAME_REINSTALL)) {
-			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++;
-		}
-		name->flags &= ~APK_NAME_VISITED;
+	print_dep_errors("world", world);
+	for (i = 0; i < solution->num; i++) {
+		struct apk_package *pkg = solution->item[i];
+		char pkgtext[256];
+		snprintf(pkgtext, sizeof(pkgtext), PKG_VER_FMT, PKG_VER_PRINTF(solution->item[i]));
+		print_dep_errors(pkgtext, pkg->depends);
 	}
+}
 
-	/* sort changeset to topology order */
-	qsort(changeset->changes->item, changeset->changes->num,
-	      sizeof(struct apk_change), compare_change);
+int apk_solver_commit(struct apk_database *db,
+		      unsigned short solver_flags,
+		      struct apk_dependency_array *world)
+{
+	struct apk_changeset changeset = {};
+	struct apk_package_array *solution = NULL;
+	int r;
 
-	return 0;
+	r = apk_solver_solve(db, solver_flags, world, &solution, &changeset);
+	if (r < 0)
+		return r;
+
+	if (changeset.changes == NULL)
+		apk_change_array_init(&changeset.changes);
+
+	if (r == 0 || (apk_flags & APK_FORCE)) {
+		/* Success -- or forced installation of bad graph */
+		commit_changeset(db, &changeset, world);
+		r = 0;
+	} else {
+		/* Failure -- print errors */
+		print_errors(db, solution, world, r);
+	}
+	apk_package_array_free(&solution);
+
+	return r;
 }
diff --git a/src/state.c b/src/state.c
deleted file mode 100644
index 3889162..0000000
--- a/src/state.c
+++ /dev/null
@@ -1,1059 +0,0 @@
-/* state.c - Alpine Package Keeper (APK)
- *
- * Copyright (C) 2005-2008 Natanael Copa <n@tanael.org>
- * Copyright (C) 2008 Timo Teräs <timo.teras@iki.fi>
- * 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 <stdio.h>
-#include <stdlib.h>
-#include <unistd.h>
-#include <malloc.h>
-
-#include "apk_state.h"
-#include "apk_database.h"
-#include "apk_print.h"
-
-struct apk_name_choices {
-	unsigned short refs, num;
-	struct apk_package *pkgs[];
-};
-
-#if 0
-struct apk_deferred_state {
-	unsigned int preference;
-	struct apk_state *state;
-};
-#endif
-
-int apk_state_prune_dependency(struct apk_state *state,
-			       struct apk_dependency *dep);
-
-#define APK_NS_LOCKED			0x00000001
-#define APK_NS_PENDING			0x00000002
-#define APK_NS_ERROR			0x00000004
-
-static void apk_state_record_conflict(struct apk_state *state,
-				      struct apk_package *pkg)
-{
-	struct apk_name *name = pkg->name;
-
-	state->name[name->id] = (void*) (((intptr_t) pkg) | APK_NS_ERROR | APK_NS_LOCKED);
-	*apk_package_array_add(&state->conflicts) = pkg;
-}
-
-static int inline ns_locked(apk_name_state_t name)
-{
-	if (((intptr_t) name) & APK_NS_LOCKED)
-		return TRUE;
-	return FALSE;
-}
-
-static int inline ns_pending(apk_name_state_t name)
-{
-	if (((intptr_t) name) & APK_NS_PENDING)
-		return TRUE;
-	return FALSE;
-}
-
-static int inline ns_error(apk_name_state_t name)
-{
-	if (((intptr_t) name) & APK_NS_ERROR)
-		return TRUE;
-	return FALSE;
-}
-
-static int ns_empty(apk_name_state_t name)
-{
-	return name == NULL;
-}
-
-static apk_name_state_t ns_from_pkg(struct apk_package *pkg)
-{
-	return (apk_name_state_t) (((intptr_t) pkg) | APK_NS_LOCKED | APK_NS_PENDING);
-}
-
-static apk_name_state_t ns_from_pkg_non_pending(struct apk_package *pkg)
-{
-	return (apk_name_state_t) (((intptr_t) pkg) | APK_NS_LOCKED);
-}
-
-static struct apk_package *ns_to_pkg(apk_name_state_t name)
-{
-	return (struct apk_package *)
-		(((intptr_t) name) & ~(APK_NS_LOCKED | APK_NS_PENDING | APK_NS_ERROR));
-}
-
-static apk_name_state_t ns_from_choices(struct apk_name_choices *nc)
-{
-	if (nc == NULL)
-		return ns_from_pkg(NULL);
-	return (apk_name_state_t) nc;
-}
-
-static struct apk_name_choices *ns_to_choices(apk_name_state_t name)
-{
-	return (struct apk_name_choices *) name;
-}
-
-static struct apk_name_choices *name_choices_new(struct apk_database *db,
-						 struct apk_name *name)
-{
-	struct apk_name_choices *nc;
-	int i, j;
-
-	if (name->pkgs->num == 0)
-		return NULL;
-
-	nc = malloc(sizeof(struct apk_name_choices) +
-		    name->pkgs->num * sizeof(struct apk_package *));
-	if (nc == NULL)
-		return NULL;
-
-	nc->refs = 1;
-	nc->num = name->pkgs->num;
-	memcpy(nc->pkgs, name->pkgs->item,
-	       name->pkgs->num * sizeof(struct apk_package *));
-
-	for (j = 0; j < nc->num; ) {
-		if (nc->pkgs[j]->filename != APK_PKG_UNINSTALLABLE) {
-			j++;
-		} else {
-			nc->pkgs[j] = nc->pkgs[nc->num - 1];
-			nc->num--;
-		}
-	}
-
-	if (name->flags & APK_NAME_TOPLEVEL_OVERRIDE)
-		return nc;
-
-	/* Check for global dependencies */
-	for (i = 0; i < db->world->num; i++) {
-		struct apk_dependency *dep = &db->world->item[i];
-
-		if (dep->name != name)
-			continue;
-
-		if (apk_flags & APK_PREFER_AVAILABLE) {
-			dep->version = apk_blob_atomize(APK_BLOB_NULL);
-			dep->result_mask = APK_DEPMASK_REQUIRE;
-		} else {
-			for (j = 0; j < nc->num; ) {
-				if (apk_dep_is_satisfied(dep, nc->pkgs[j])) {
-					j++;
-				} else {
-					nc->pkgs[j] = nc->pkgs[nc->num - 1];
-					nc->num--;
-				}
-			}
-		}
-		break;
-	}
-
-	return nc;
-}
-
-static void name_choices_unref(struct apk_name_choices *nc)
-{
-	if (--nc->refs == 0)
-		free(nc);
-}
-
-static struct apk_name_choices *name_choices_writable(struct apk_name_choices *nc)
-{
-	struct apk_name_choices *n;
-
-	if (nc->refs == 1)
-		return nc;
-
-	n = malloc(sizeof(struct apk_name_choices) +
-		   nc->num * sizeof(struct apk_package *));
-	if (n == NULL)
-		return NULL;
-
-	n->refs = 1;
-	n->num = nc->num;
-	memcpy(n->pkgs, nc->pkgs, nc->num * sizeof(struct apk_package *));
-	name_choices_unref(nc);
-
-	return n;
-}
-
-static void ns_free(apk_name_state_t name)
-{
-	if (!ns_empty(name) && !ns_locked(name))
-		name_choices_unref(ns_to_choices(name));
-}
-
-static inline int apk_state_pkg_available(struct apk_state *state,
-					  struct apk_package *pkg)
-{
-	if (pkg->ipkg != NULL)
-		return TRUE;
-	if (pkg->installed_size == 0)
-		return TRUE;
-	if (pkg->filename != NULL)
-		return TRUE;
-	if (apk_db_select_repo(state->db, pkg) != NULL)
-		return TRUE;
-	return FALSE;
-}
-
-struct apk_state *apk_state_new(struct apk_database *db)
-{
-	struct apk_state *state;
-	int num_bytes;
-
-	num_bytes = sizeof(struct apk_state) + db->name_id * sizeof(char *);
-	state = (struct apk_state*) calloc(1, num_bytes);
-	state->refs = 1;
-	state->num_names = db->name_id;
-	state->db = db;
-	state->print_ok = 1;
-	list_init(&state->change_list_head);
-
-	apk_name_array_init(&state->missing);
-	apk_package_array_init(&state->conflicts);
-
-	return state;
-}
-
-struct apk_state *apk_state_dup(struct apk_state *state)
-{
-	state->refs++;
-	return state;
-}
-
-void apk_state_unref(struct apk_state *state)
-{
-	if (--state->refs > 0)
-		return;
-
-	apk_package_array_free(&state->conflicts);
-	apk_name_array_free(&state->missing);
-	free(state);
-}
-
-static struct apk_package *get_locked_or_installed_package(
-					struct apk_state *state,
-					struct apk_name *name)
-{
-	int i;
-
-	if (ns_locked(state->name[name->id]))
-		return ns_to_pkg(state->name[name->id]);
-
-	if (!ns_empty(state->name[name->id])) {
-		struct apk_name_choices *ns =
-			ns_to_choices(state->name[name->id]);
-
-		for (i = 0; i < ns->num; i++) {
-			if (ns->pkgs[i]->ipkg != NULL)
-				return ns->pkgs[i];
-		}
-		return NULL;
-	}
-
-	for (i = 0; i < name->pkgs->num; i++) {
-		if (name->pkgs->item[i]->ipkg != NULL)
-			return name->pkgs->item[i];
-	}
-	return NULL;
-}
-
-static int check_dependency(struct apk_state *state,
-			    struct apk_dependency *dep)
-{
-	struct apk_package *pkg;
-
-	pkg = get_locked_or_installed_package(state, dep->name);
-	if (pkg == NULL && dep->result_mask != APK_DEPMASK_CONFLICT)
-		return 0;
-	if (!apk_dep_is_satisfied(dep, pkg))
-		return 0;
-
-	return 1;
-}
-
-static int check_dependency_array(struct apk_state *state,
-				  struct apk_dependency_array *da)
-{
-	int i;
-
-	for (i = 0; i < da->num; i++) {
-		if (!check_dependency(state, &da->item[i]))
-			return 0;
-	}
-
-	return da->num;
-}
-
-static int apk_state_add_change(struct apk_state *state,
-				struct apk_package *oldpkg,
-				struct apk_package *newpkg)
-{
-	struct apk_change *change;
-
-	change = (struct apk_change *) malloc(sizeof(struct apk_change));
-	if (change == NULL)
-		return -1;
-
-	list_init(&change->change_list);
-	list_add_tail(&change->change_list, &state->change_list_head);
-	state->num_changes++;
-	change->oldpkg = oldpkg;
-	change->newpkg = newpkg;
-
-	return 0;
-}
-
-/* returns:
- *   -1 error
- *    0 locked entry matches and is ok
- *   +n this many candidates on apk_name_choices for the name
- */
-int apk_state_prune_dependency(struct apk_state *state,
-			       struct apk_dependency *dep)
-{
-	struct apk_name *name = dep->name;
-	struct apk_name_choices *c;
-	int i;
-
-	if (name->id >= state->num_names)
-		return -1;
-
-	if (ns_empty(state->name[name->id])) {
-		if (dep->result_mask == APK_DEPMASK_CONFLICT) {
-			state->name[name->id] = ns_from_pkg(NULL);
-			return 1;
-		}
-
-		/* This name has not been visited yet.
-		 * Construct list of candidates. */
-		state->name[name->id] = ns_from_choices(name_choices_new(state->db, name));
-	}
-
-	if (ns_locked(state->name[name->id])) {
-		/* Locked: check that selected package provides
-		 * requested version. */
-		struct apk_package *pkg = ns_to_pkg(state->name[name->id]);
-
-		/* Locked to not-installed / remove? */
-		if (ns_error(state->name[name->id])) {
-			return -1;
-		} else if (pkg == NULL) {
-			if (dep->result_mask != APK_DEPMASK_CONFLICT) {
-				if (ns_pending(state->name[name->id])) {
-					state->name[name->id] = ns_from_pkg_non_pending(NULL);
-					*apk_name_array_add(&state->missing) = name;
-				}
-				return -1;
-			}
-		} else {
-			if (!apk_dep_is_satisfied(dep, pkg))
-				return -1;
-		}
-
-		if (ns_pending(state->name[name->id]))
-			return 1;
-
-		return 0;
-	}
-
-	/* Multiple candidates: prune incompatible versions. */
-	c = ns_to_choices(state->name[name->id]);
-	i = 0;
-	while (i < c->num) {
-		if (apk_dep_is_satisfied(dep, c->pkgs[i])) {
-			i++;
-			continue;
-		}
-
-		c = name_choices_writable(c);
-		c->pkgs[i] = c->pkgs[c->num - 1];
-		c->num--;
-	}
-	if (c->num == 1 && apk_state_pkg_available(state, c->pkgs[0])) {
-		struct apk_package *pkg = c->pkgs[0];
-		name_choices_unref(c);
-		state->name[name->id] = ns_from_pkg(pkg);
-		return 1;
-	}
-	if (c->num <= 1) {
-		name_choices_unref(c);
-		state->name[name->id] = ns_from_pkg(NULL);
-		*apk_name_array_add(&state->missing) = name;
-		return -1;
-	}
-
-	state->name[name->id] = ns_from_choices(c);
-	return c->num;
-}
-
-int apk_state_autolock_name(struct apk_state *state, struct apk_name *name,
-			    int install_if)
-{
-	struct apk_name_choices *c;
-	struct apk_package *installed = NULL, *latest = NULL, *use;
-	int i;
-
-	if (ns_pending(state->name[name->id]))
-		return apk_state_lock_name(state, name, ns_to_pkg(state->name[name->id]));
-	if (ns_locked(state->name[name->id]))
-		return 0;
-	if (ns_empty(state->name[name->id])) {
-		/* This name has not been visited yet.
-		 * Construct list of candidates. */
-		state->name[name->id] = ns_from_choices(name_choices_new(state->db, name));
-	}
-
-	c = ns_to_choices(state->name[name->id]);
-#if 1
-	/* Get latest and installed packages */
-	for (i = 0; i < c->num; i++) {
-		struct apk_package *pkg = c->pkgs[i];
-
-		if (install_if &&
-		    !check_dependency_array(state, pkg->install_if))
-			continue;
-
-		if (pkg->ipkg != NULL)
-			installed = pkg;
-		else if (!apk_state_pkg_available(state, pkg))
-			continue;
-
-		if (latest == NULL) {
-			latest = pkg;
-			continue;
-		}
-
-		if ((apk_flags & APK_PREFER_AVAILABLE) ||
-		    (name->flags & APK_NAME_REINSTALL)) {
-			if (latest->repos != 0 && pkg->repos == 0)
-				continue;
-
-			if (latest->repos == 0 && pkg->repos != 0) {
-				latest = pkg;
-				continue;
-			}
-
-			/* Otherwise both are not available, or both are
-			 * available and we just compare the versions then */
-		}
-
-		if (apk_pkg_version_compare(pkg, latest) == APK_VERSION_GREATER)
-			latest = pkg;
-	}
-
-	/* Choose the best looking candidate.
-	 * FIXME: We should instead try all alternatives. */
-	if (apk_flags & APK_UPGRADE) {
-		use = latest;
-	} else {
-		if (installed != NULL &&
-		    (installed->repos != 0 ||
-		     !(name->flags & APK_NAME_REINSTALL)))
-			use = installed;
-		else
-			use = latest;
-	}
-	if (use == NULL)
-		return -2;
-
-	/* Install_if check did not result in package selection change:
-	 * do not lock the package yet as the preferency might change
-	 * later. */
-	if (install_if && use->ipkg != NULL)
-		return 0;
-
-	return apk_state_lock_name(state, name, use);
-#else
-	/* If any of the choices is installed, we are good. Otherwise,
-	 * the caller needs to install this dependency. */
-	for (i = 0; i < c->num; i++)
-		if (apk_pkg_get_state(c->pkgs[i]) == APK_PKG_INSTALLED)
-			return 0;
-
-	/* Queue for deferred solution. */
-	return 0;
-#endif
-}
-
-int apk_state_lock_dependency(struct apk_state *state,
-			      struct apk_dependency *dep)
-{
-	int r;
-
-	r = apk_state_prune_dependency(state, dep);
-	if (r <= 0)
-		return r;
-
-	return apk_state_autolock_name(state, dep->name, FALSE);
-}
-
-static int apk_state_fix_package(struct apk_state *state,
-				 struct apk_package *pkg)
-{
-	int i, r, ret = 0;
-
-	if (pkg == NULL)
-		return 0;
-
-	for (i = 0; i < pkg->depends->num; i++) {
-		if ((pkg->depends->item[i].name->flags & APK_NAME_TOPLEVEL_OVERRIDE) &&
-		    check_dependency(state, &pkg->depends->item[i])) {
-			r = apk_state_prune_dependency(state,
-						       &pkg->depends->item[i]);
-			if (r < 0)
-				ret = -1;
-		} else {
-			r = apk_state_lock_dependency(state,
-						      &pkg->depends->item[i]);
-			if (r != 0)
-				ret = -1;
-		}
-	}
-	return ret;
-}
-
-static int call_if_dependency_broke(struct apk_state *state,
-				    struct apk_package *pkg,
-				    struct apk_name *dep_name,
-				    int (*cb)(struct apk_state *state,
-					      struct apk_package *pkg,
-					      struct apk_dependency *dep,
-					      void *ctx),
-				    void *ctx)
-{
-	struct apk_package *dep_pkg;
-	int k;
-
-	dep_pkg = ns_to_pkg(state->name[dep_name->id]);
-	for (k = 0; k < pkg->depends->num; k++) {
-		struct apk_dependency *dep = &pkg->depends->item[k];
-		if (dep->name != dep_name)
-			continue;
-		if (dep_pkg == NULL &&
-		    dep->result_mask == APK_DEPMASK_CONFLICT)
-			continue;
-		if (dep_pkg != NULL &&
-		    apk_dep_is_satisfied(dep, dep_pkg))
-			continue;
-		return cb(state, pkg, dep, ctx);
-	}
-
-	return 0;
-}
-
-static int for_each_broken_reverse_depency(struct apk_state *state,
-					   struct apk_name *name,
-					   int (*cb)(struct apk_state *state,
-						     struct apk_package *pkg,
-						     struct apk_dependency *dep,
-						     void *ctx),
-					   void *ctx)
-{
-	struct apk_package *pkg0;
-	int i, r;
-
-	for (i = 0; i < name->rdepends->num; i++) {
-		struct apk_name *name0 = name->rdepends->item[i];
-
-		pkg0 = get_locked_or_installed_package(state, name0);
-		if (pkg0 == NULL)
-			continue;
-
-		r = call_if_dependency_broke(state, pkg0, name,
-					     cb, ctx);
-		if (r != 0)
-			return r;
-	}
-
-	return 0;
-}
-
-static int delete_broken_package(struct apk_state *state,
-				 struct apk_package *pkg,
-				 struct apk_dependency *dep,
-				 void *ctx)
-{
-	return apk_state_lock_name(state, pkg->name, NULL);
-}
-
-static int reinstall_broken_package(struct apk_state *state,
-				    struct apk_package *pkg,
-				    struct apk_dependency *dep,
-				    void *ctx)
-
-{
-	struct apk_dependency dep0 = {
-		.name = pkg->name,
-		.version = apk_blob_atomize(APK_BLOB_NULL),
-		.result_mask = APK_DEPMASK_REQUIRE,
-	};
-	return apk_state_lock_dependency(state, &dep0);
-}
-
-int apk_state_lock_name(struct apk_state *state,
-			struct apk_name *name,
-			struct apk_package *newpkg)
-{
-	struct apk_package *oldpkg = NULL;
-	int i, r;
-
-	if (name->id >= state->num_names)
-		return -1;
-
-	ns_free(state->name[name->id]);
-	state->name[name->id] = ns_from_pkg_non_pending(newpkg);
-
-	for (i = 0; i < name->pkgs->num; i++) {
-		struct apk_package *pkg = name->pkgs->item[i];
-		if (name->pkgs->item[i]->name == name &&
-		    pkg->ipkg != NULL)
-			oldpkg = pkg;
-	}
-
-	/* First we need to make sure the dependants of the old package
-	 * still have their dependencies ok. */
-	if (oldpkg != NULL) {
-		r = for_each_broken_reverse_depency(state, name,
-						    newpkg == NULL ?
-						    delete_broken_package :
-						    reinstall_broken_package,
-						    NULL);
-		if (r != 0) {
-			apk_state_record_conflict(state, newpkg);
-			return r;
-		}
-	}
-
-	/* Check that all other dependencies hold for the new package. */
-	r = apk_state_fix_package(state, newpkg);
-	if (r != 0) {
-		apk_state_record_conflict(state, newpkg);
-		return r;
-	}
-
-	/* If the chosen package is installed, all is done here */
-	if ((oldpkg != newpkg) ||
-	    (newpkg != NULL && (newpkg->name->flags & APK_NAME_REINSTALL))) {
-		/* Track change */
-		r = apk_state_add_change(state, oldpkg, newpkg);
-		if (r != 0)
-			return r;
-	}
-
-	/* Check all reverse install_if's */
-	if (newpkg != NULL) {
-		for (i = 0; i < newpkg->name->rinstall_if->num; i++)
-			apk_state_autolock_name(state, newpkg->name->rinstall_if->item[i], TRUE);
-	}
-
-	return 0;
-}
-
-static void apk_print_change(struct apk_database *db,
-			     struct apk_package *oldpkg,
-			     struct apk_package *newpkg,
-			     int num, int total)
-{
-	const char *msg = NULL;
-	int r;
-	struct apk_name *name;
-	char status[64];
-
-	snprintf(status, sizeof(status), "(%i/%i)", num, total);
-	status[sizeof(status) - 1] = '\0';
-
-	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));
-	}
-}
-
-struct apk_stats {
-	unsigned int bytes;
-	unsigned int packages;
-};
-
-static void apk_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 apk_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);
-}
-
-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)
-{
-	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)
-		apk_draw_progress(count);
-	prog->count = count;
-}
-
-static int dump_packages(struct apk_state *state,
-			 int (*cmp)(struct apk_change *change),
-			 const char *msg)
-{
-	struct apk_change *change;
-	struct apk_name *name;
-	struct apk_indent indent = { 0, 2 };
-	char tmp[256];
-	int match = 0, i;
-
-	list_for_each_entry(change, &state->change_list_head, change_list) {
-		if (!cmp(change))
-			continue;
-		if (match == 0)
-			printf("%s:\n ", msg);
-		if (change->newpkg != NULL)
-			name = change->newpkg->name;
-		else
-			name = change->oldpkg->name;
-
-		i = snprintf(tmp, sizeof(tmp), "%s%s", name->name,
-			     (name->flags & APK_NAME_TOPLEVEL) ? "*" : "");
-		apk_print_indented(&indent, APK_BLOB_PTR_LEN(tmp, i));
-		match++;
-	}
-	if (match)
-		printf("\n");
-	return match;
-}
-
-static int cmp_remove(struct apk_change *change)
-{
-	return change->newpkg == NULL;
-}
-
-static int cmp_new(struct apk_change *change)
-{
-	return change->oldpkg == NULL;
-}
-
-static int cmp_downgrade(struct apk_change *change)
-{
-	if (change->newpkg == NULL || change->oldpkg == NULL)
-		return 0;
-	if (apk_pkg_version_compare(change->newpkg, change->oldpkg)
-	    & APK_VERSION_LESS)
-		return 1;
-	return 0;
-}
-
-static int cmp_upgrade(struct apk_change *change)
-{
-	if (change->newpkg == NULL || change->oldpkg == NULL)
-		return 0;
-
-	/* Count swapping package as upgrade too - this can happen if
-	 * same package version is used after it was rebuilt against
-	 * newer libraries. Basically, different (and probably newer)
-	 * package, but equal version number. */
-	if ((apk_pkg_version_compare(change->newpkg, change->oldpkg) &
-	     (APK_VERSION_GREATER | APK_VERSION_EQUAL)) &&
-	    (change->newpkg != change->oldpkg))
-		return 1;
-
-	return 0;
-}
-
-static int fail_if_something_broke(struct apk_state *state,
-				   struct apk_package *pkg,
-				   struct apk_dependency *dep,
-				   void *ctx)
-
-{
-	return 1;
-}
-
-static int apk_state_autoclean(struct apk_state *state,
-			       struct apk_package *pkg)
-{
-	apk_name_state_t oldns;
-	int i, r;
-
-	for (i = 0; i < pkg->depends->num; i++) {
-		struct apk_name *n = pkg->depends->item[i].name;
-
-		if (ns_locked(state->name[n->id]))
-			continue;
-		if (n->flags & APK_NAME_TOPLEVEL)
-			continue;
-
-		oldns = state->name[n->id];
-		state->name[n->id] = ns_from_pkg(NULL);
-		r = for_each_broken_reverse_depency(state, n,
-						    fail_if_something_broke,
-						    NULL);
-		state->name[n->id] = oldns;
-
-		if (r == 0) {
-			r = apk_state_lock_name(state, n, NULL);
-			if (r != 0)
-				return r;
-		}
-	}
-
-	for (i = 0; i < pkg->name->rinstall_if->num; i++) {
-		struct apk_name *n = pkg->name->rinstall_if->item[i];
-
-		if (ns_locked(state->name[n->id]))
-			continue;
-		if (n->flags & APK_NAME_TOPLEVEL)
-			continue;
-
-		r = apk_state_autolock_name(state, n, TRUE);
-		if (r == -2) {
-			r = apk_state_lock_name(state, n, NULL);
-			if (r != 0)
-				return r;
-		}
-	}
-
-	return 0;
-}
-
-struct error_state {
-	struct apk_indent indent;
-	struct apk_package *prevpkg;
-};
-
-static int print_dep(struct apk_state *state,
-		     struct apk_package *pkg,
-		     struct apk_dependency *dep,
-		     void *ctx)
-{
-	struct error_state *es = (struct error_state *) ctx;
-	apk_blob_t blob;
-	char buf[256];
-	int len;
-
-	if (pkg != es->prevpkg) {
-		printf("\n");
-		es->indent.x = 0;
-		len = snprintf(buf, sizeof(buf), PKG_VER_FMT ":",
-			       PKG_VER_PRINTF(pkg));
-		apk_print_indented(&es->indent, APK_BLOB_PTR_LEN(buf, len));
-		es->prevpkg = pkg;
-	}
-
-	blob = APK_BLOB_BUF(buf);
-	apk_blob_push_dep(&blob, dep);
-	blob = apk_blob_pushed(APK_BLOB_BUF(buf), blob);
-	apk_print_indented(&es->indent, blob);
-
-	return 0;
-}
-
-void apk_state_print_errors(struct apk_state *state)
-{
-	struct apk_package *pkg;
-	struct error_state es;
-	int i, j, r;
-
-	for (i = 0; i < state->conflicts->num; i++) {
-		if (i == 0)
-			apk_error("Unable to satisfy all dependencies:");
-
-		es.prevpkg = pkg = state->conflicts->item[i];
-		es.indent.x =
-		printf("  " PKG_VER_FMT ":", PKG_VER_PRINTF(pkg));
-		es.indent.indent = es.indent.x + 1;
-		for (j = 0; j < pkg->depends->num; j++) {
-			r = apk_state_lock_dependency(state,
-						      &pkg->depends->item[j]);
-			if (r != 0)
-				print_dep(state, pkg, &pkg->depends->item[j], &es);
-		}
-
-		/* Print conflicting reverse deps */
-		for_each_broken_reverse_depency(state, pkg->name,
-						print_dep, &es);
-		printf("\n");
-	}
-
-	for (i = 0; i < state->missing->num; i++) {
-		struct apk_name *name = state->missing->item[i];
-		if (i == 0) {
-			apk_error("Missing packages:");
-			es.indent.x = 0;
-			es.indent.indent = 2;
-		}
-		apk_print_indented(&es.indent, APK_BLOB_STR(name->name));
-	}
-	if (i != 0)
-		printf("\n");
-}
-
-int apk_state_commit(struct apk_state *state)
-{
-	struct progress prog;
-	struct apk_change *change;
-	struct apk_database *db = state->db;
-	int n = 0, r = 0, size_diff = 0, toplevel = FALSE, deleteonly = TRUE;
-
-	/* Count what needs to be done */
-	memset(&prog, 0, sizeof(prog));
-	list_for_each_entry(change, &state->change_list_head, change_list) {
-		if (change->newpkg == NULL) {
-			if (change->oldpkg->name->flags & APK_NAME_TOPLEVEL)
-				toplevel = TRUE;
-		} else
-			deleteonly = FALSE;
-		if (change->oldpkg != NULL)
-			apk_state_autoclean(state, change->oldpkg);
-		apk_count_change(change, &prog.total);
-		if (change->newpkg)
-			size_diff += change->newpkg->installed_size;
-		if (change->oldpkg)
-			size_diff -= change->oldpkg->installed_size;
-	}
-	size_diff /= 1024;
-
-	if (toplevel &&
-	    (apk_flags & (APK_INTERACTIVE | APK_RECURSIVE_DELETE)) == 0) {
-		if (!deleteonly)
-			return -1;
-
-		dump_packages(state, cmp_remove,
-			      "The top-level dependencies have been updated "
-			      "but the following packages are not removed");
-		goto update_state;
-	}
-
-	if (apk_verbosity > 1 || (apk_flags & APK_INTERACTIVE)) {
-		r = dump_packages(state, cmp_remove,
-				  "The following packages will be REMOVED");
-		r += dump_packages(state, cmp_downgrade,
-				   "The following packages will be DOWNGRADED");
-		if (r || (apk_flags & APK_INTERACTIVE) || apk_verbosity > 2) {
-			dump_packages(state, cmp_new,
-				      "The following NEW packages will be installed");
-			dump_packages(state, cmp_upgrade,
-				      "The following packages will be upgraded");
-			printf("After this operation, %d kB of %s\n", abs(size_diff),
-			       (size_diff < 0) ?
-			       "disk space will be freed." :
-			       "additional disk space will be used.");
-		}
-		if (apk_flags & APK_INTERACTIVE) {
-			printf("Do you want to continue [Y/n]? ");
-			fflush(stdout);
-			r = fgetc(stdin);
-			if (r != 'y' && r != 'Y' && r != '\n')
-				return -1;
-		}
-	}
-
-	/* Go through changes */
-	r = 0;
-	n = 0;
-	list_for_each_entry(change, &state->change_list_head, change_list) {
-		n++;
-		apk_print_change(db, change->oldpkg, change->newpkg, n, state->num_changes);
-		if (apk_flags & APK_PROGRESS)
-			apk_draw_progress(prog.count);
-		prog.pkg = change->newpkg;
-
-		if (!(apk_flags & APK_SIMULATE)) {
-			r = apk_db_install_pkg(db,
-					       change->oldpkg, change->newpkg,
-					       (apk_flags & APK_PROGRESS) ? progress_cb : NULL,
-					       &prog);
-			if (r != 0)
-				break;
-
-			if (change->oldpkg != NULL &&
-			    change->newpkg == NULL &&
-			    change->oldpkg->name->flags & APK_NAME_TOPLEVEL) {
-				change->oldpkg->name->flags &= ~APK_NAME_TOPLEVEL;
-				apk_deps_del(&db->world, change->oldpkg->name);
-			}
-		}
-
-		apk_count_change(change, &prog.done);
-	}
-	if (apk_flags & APK_PROGRESS)
-		apk_draw_progress(100);
-
-update_state:
-	apk_db_run_triggers(db);
-	apk_db_write_config(db);
-
-	if (r == 0 && state->print_ok)
-		apk_message("OK: %d packages, %d dirs, %d files",
-			    db->installed.stats.packages,
-			    db->installed.stats.dirs,
-			    db->installed.stats.files);
-
-	return r;
-}
diff --git a/src/upgrade.c b/src/upgrade.c
index ec0dc91..5afccfd 100644
--- a/src/upgrade.c
+++ b/src/upgrade.c
@@ -14,15 +14,21 @@
 #include <zlib.h>
 #include "apk_applet.h"
 #include "apk_database.h"
-#include "apk_state.h"
 #include "apk_print.h"
+#include "apk_solver.h"
+
+struct upgrade_ctx {
+	unsigned short solver_flags;
+};
 
 static int upgrade_parse(void *ctx, struct apk_db_options *dbopts,
 			 int optch, int optindex, const char *optarg)
 {
+	struct upgrade_ctx *uctx = (struct upgrade_ctx *) ctx;
+
 	switch (optch) {
 	case 'a':
-		apk_flags |= APK_PREFER_AVAILABLE;
+		uctx->solver_flags |= APK_SOLVERF_AVAILABLE;
 		break;
 	default:
 		return -1;
@@ -30,8 +36,10 @@ static int upgrade_parse(void *ctx, struct apk_db_options *dbopts,
 	return 0;
 }
 
-int apk_do_self_upgrade(struct apk_database *db, struct apk_state *state)
+int apk_do_self_upgrade(struct apk_database *db)
 {
+#if 0
+	/* FIXME: Reimplement self-upgrade. */
 	struct apk_dependency dep;
 	int r;
 
@@ -57,58 +65,24 @@ int apk_do_self_upgrade(struct apk_database *db, struct apk_state *state)
 
 	apk_error("PANIC! Failed to re-execute new apk-tools!");
 	exit(1);
+#else
+	return 0;
+#endif
 }
 
 static int upgrade_main(void *ctx, struct apk_database *db, int argc, char **argv)
 {
-	struct apk_state *state = NULL;
-	struct apk_name_array *missing;
-	int i, r = 0;
-
-	apk_flags |= APK_UPGRADE;
-	apk_name_array_init(&missing);
-
-	state = apk_state_new(db);
-	if (state == NULL)
-		goto err;
+	struct upgrade_ctx *uctx = (struct upgrade_ctx *) ctx;
+	unsigned short solver_flags;
+	int r;
 
-	r = apk_do_self_upgrade(db, state);
-	if (r != 0) {
-		apk_state_print_errors(state);
-		goto err;
-	}
+	solver_flags = APK_SOLVERF_UPGRADE | uctx->solver_flags;
 
-	for (i = 0; i < db->world->num; i++) {
-		struct apk_dependency *dep = &db->world->item[i];
+	r = apk_do_self_upgrade(db);
+	if (r != 0)
+		return r;
 
-		if (dep->name->pkgs->num != 0)
-			r |= apk_state_lock_dependency(state, dep);
-		else
-			*apk_name_array_add(&missing) = dep->name;
-	}
-	if (r == 0) {
-		for (i = 0; i < missing->num; i++) {
-			struct apk_indent indent;
-			struct apk_name *name = missing->item[i];
-
-			if (i == 0) {
-				apk_warning("The following package names no longer exists in repository:");
-				indent.x = 0;
-				indent.indent = 2;
-			}
-			apk_print_indented(&indent, APK_BLOB_STR(name->name));
-		}
-		if (i != 0)
-			printf("\n");
-
-		r = apk_state_commit(state);
-	} else
-		apk_state_print_errors(state);
-err:
-	if (state != NULL)
-		apk_state_unref(state);
-	apk_name_array_free(&missing);
-	return r;
+	return apk_solver_commit(db, solver_flags, db->world);
 }
 
 static struct apk_option upgrade_options[] = {