state: rework changeset calculation algorithm

Calculate changesets directly by stabilizating the package graph instead of
recalculating the whole graph and then diffing (similar approach as seen
in 'smart' package manager). The algorithm is not complete: defferred
search space forking is missing. So you don't always get a solution on
complex graphs.

Benefits:
- usually the search state tree is smaller (less memory used)
- speed relational to changeset size, not database size (usually faster)
- touch only packages related to users request (can work on partitially
  broken state; upgrades only necessary packages, fixes #7)

Also implemented:
- command prompt to confirm operation if packages are deleted or downgraded
- requesting deletion of package suggests removal of all packages depending
  on the package being removed (you'll get list of packages that also get
  removed if you want package X removed)
- option --simulate to see what would have been done (mainly for testing)
- an untested implementation of versioned dependencies and conflicts

A lot has changed, so expect new bugs too.

13 files changed, 581 insertions, 236 deletions

diff --git a/src/add.c b/src/add.c
index 7aa0b23..77abc3b 100644
--- a/src/add.c
+++ b/src/add.c
@@ -13,6 +13,7 @@
 #include <stdio.h>
 #include "apk_applet.h"
 #include "apk_database.h"
+#include "apk_state.h"
 
 struct add_ctx {
 	unsigned int open_flags;
@@ -27,7 +28,7 @@ static int add_parse(void *ctx, int optch, int optindex, const char *optarg)
 		actx->open_flags |= APK_OPENF_CREATE;
 		break;
 	case 'u':
-		apk_upgrade = 1;
+		apk_flags |= APK_UPGRADE;
 		break;
 	default:
 		return -1;
@@ -39,12 +40,14 @@ static int add_main(void *ctx, int argc, char **argv)
 {
 	struct add_ctx *actx = (struct add_ctx *) ctx;
 	struct apk_database db;
-	int i, r, ret = 1;
+	struct apk_state *state;
+	int i, r;
 
 	r = apk_db_open(&db, apk_root, actx->open_flags | APK_OPENF_WRITE);
 	if (r != 0)
 		return r;
 
+	state = apk_state_new(&db);
 	for (i = 0; i < argc; i++) {
 		struct apk_dependency dep;
 
@@ -59,20 +62,29 @@ static int add_main(void *ctx, int argc, char **argv)
 
 			dep = (struct apk_dependency) {
 				.name = pkg->name,
-				.min_version = pkg->version,
-				.max_version = pkg->version,
+				.version = pkg->version,
+				.result_mask = APK_VERSION_EQUAL,
 			};
 		} else {
 			dep = (struct apk_dependency) {
 				.name = apk_db_get_name(&db, APK_BLOB_STR(argv[i])),
+				.result_mask = APK_DEPMASK_REQUIRE,
 			};
 		}
 		apk_deps_add(&db.world, &dep);
+		dep.name->flags |= APK_NAME_TOPLEVEL;
+
+		r = apk_state_lock_dependency(state, &dep);
+		if (r != 0) {
+			apk_error("Unable to install '%s'", dep.name->name);
+			goto err;
+		}
 	}
-	ret = apk_db_recalculate_and_commit(&db);
+	r = apk_state_commit(state, &db);
 err:
+	apk_state_unref(state);
 	apk_db_close(&db);
-	return ret;
+	return r;
 }
 
 static struct option add_options[] = {
diff --git a/src/apk.c b/src/apk.c
index 8ad4200..21e4359 100644
--- a/src/apk.c
+++ b/src/apk.c
@@ -23,9 +23,8 @@
 
 const char *apk_root;
 struct apk_repository_url apk_repository_list;
-int apk_verbosity = 1, apk_progress = 0, apk_upgrade = 0;
-int apk_clean = 0, apk_force = 0;
-int apk_cwd_fd;
+int apk_verbosity = 1, apk_cwd_fd;
+unsigned int apk_flags = 0;
 
 void apk_log(const char *prefix, const char *format, ...)
 {
@@ -111,16 +110,17 @@ static struct apk_repository_url *apk_repository_new(const char *url)
 	return r;
 }
 
-#define NUM_GENERIC_OPTS 8
+#define NUM_GENERIC_OPTS 9
 static struct option generic_options[32] = {
 	{ "root",		required_argument,	NULL, 'p' },
 	{ "repository",		required_argument,	NULL, 'X' },
 	{ "quiet",		no_argument,		NULL, 'q' },
 	{ "verbose",		no_argument,		NULL, 'v' },
 	{ "version",		no_argument,		NULL, 'V' },
-	{ "progress",		no_argument,		&apk_progress,	1 },
-	{ "clean-protected",	no_argument,		&apk_clean,	1 },
-	{ "force",		no_argument,		&apk_force,	1 },
+	{ "progress",		no_argument,		NULL, 0x101 },
+	{ "clean-protected",	no_argument,		NULL, 0x102 },
+	{ "force",		no_argument,		NULL, 0x103 },
+	{ "simulate",		no_argument,		NULL, 0x104 },
 };
 
 int main(int argc, char **argv)
@@ -181,6 +181,17 @@ int main(int argc, char **argv)
 			break;
 		case 'V':
 			return version();
+		case 0x101:
+			apk_flags |= APK_PROGRESS;
+			break;
+		case 0x102:
+			apk_flags |= APK_CLEAN_PROTECTED;
+			break;
+		case 0x103:
+			apk_flags |= APK_FORCE;
+			break;
+		case 0x104:
+			apk_flags |= APK_SIMULATE;
 			break;
 		default:
 			if (applet == NULL || applet->parse == NULL)
diff --git a/src/apk_database.h b/src/apk_database.h
index 59f1f8a..b7d0eed 100644
--- a/src/apk_database.h
+++ b/src/apk_database.h
@@ -54,8 +54,12 @@ struct apk_db_dir_instance {
 	gid_t gid;
 };
 
+#define APK_NAME_TOPLEVEL	0x0001
+
 struct apk_name {
 	apk_hash_node hash_node;
+	unsigned int id;
+	unsigned int flags;
 	char *name;
 	struct apk_package_array *pkgs;
 	struct apk_name_array *rdepends;
@@ -68,7 +72,7 @@ struct apk_repository {
 struct apk_database {
 	char *root;
 	int root_fd, lock_fd;
-	unsigned pkg_id, num_repos;
+	unsigned name_id, num_repos;
 
 	struct apk_dependency_array *world;
 	struct apk_string_array *protected_paths;
@@ -109,6 +113,7 @@ struct apk_db_file *apk_db_file_query(struct apk_database *db,
 #define APK_OPENF_CREATE	0x0002
 
 int apk_db_open(struct apk_database *db, const char *root, unsigned int flags);
+int apk_db_write_config(struct apk_database *db);
 void apk_db_close(struct apk_database *db);
 
 struct apk_package *apk_db_pkg_add_file(struct apk_database *db, const char *file);
@@ -118,8 +123,6 @@ struct apk_package *apk_db_get_file_owner(struct apk_database *db, apk_blob_t fi
 int apk_db_index_write(struct apk_database *db, struct apk_ostream *os);
 
 int apk_db_add_repository(apk_database_t db, apk_blob_t repository);
-int apk_db_recalculate_and_commit(struct apk_database *db);
-
 int apk_db_install_pkg(struct apk_database *db,
 		       struct apk_package *oldpkg,
 		       struct apk_package *newpkg,
diff --git a/src/apk_defines.h b/src/apk_defines.h
index 4a42b16..e8029de 100644
--- a/src/apk_defines.h
+++ b/src/apk_defines.h
@@ -50,8 +50,14 @@ extern csum_t bad_checksum;
 #define csum_valid(buf)			memcmp(buf, bad_checksum, sizeof(csum_t))
 #endif
 
-extern int apk_cwd_fd, apk_verbosity, apk_progress, apk_upgrade;
-extern int apk_clean, apk_force;
+extern int apk_cwd_fd, apk_verbosity;
+extern unsigned int apk_flags;
+
+#define APK_FORCE		0x0001
+#define APK_SIMULATE		0x0002
+#define APK_CLEAN_PROTECTED	0x0004
+#define APK_PROGRESS		0x0008
+#define APK_UPGRADE		0x0010
 
 #define apk_error(args...)	apk_log("ERROR: ", args);
 #define apk_warning(args...)	if (apk_verbosity > 0) { apk_log("WARNING: ", args); }
diff --git a/src/apk_package.h b/src/apk_package.h
index bf0ae95..8ce7e9f 100644
--- a/src/apk_package.h
+++ b/src/apk_package.h
@@ -28,6 +28,9 @@ struct apk_name;
 #define APK_SCRIPT_PRE_UPGRADE		5
 #define APK_SCRIPT_POST_UPGRADE		6
 
+#define APK_PKG_NOT_INSTALLED		0
+#define APK_PKG_INSTALLED		1
+
 struct apk_script {
 	struct hlist_node script_list;
 	unsigned int type;
@@ -35,10 +38,14 @@ struct apk_script {
 	char script[];
 };
 
+#define APK_DEPMASK_REQUIRE	(APK_VERSION_EQUAL|APK_VERSION_LESS|\
+				 APK_VERSION_GREATER)
+#define APK_DEPMASK_CONFLICT	(0)
+
 struct apk_dependency {
 	struct apk_name *name;
-	char *min_version;
-	char *max_version;
+	int result_mask;
+	char *version;
 };
 APK_ARRAY(apk_dependency_array, struct apk_dependency);
 
@@ -46,7 +53,7 @@ struct apk_package {
 	apk_hash_node hash_node;
 
 	csum_t csum;
-	unsigned id, repos;
+	unsigned repos;
 	struct apk_name *name;
 	char *version;
 	char *url, *description, *license;
diff --git a/src/apk_state.h b/src/apk_state.h
index d89af98..d065411 100644
--- a/src/apk_state.h
+++ b/src/apk_state.h
@@ -14,43 +14,17 @@
 
 #include "apk_database.h"
 
-#define APK_STATE_NOT_CONSIDERED		0
-#define APK_STATE_INSTALL			1
-#define APK_STATE_NO_INSTALL			2
-
-struct apk_change {
-	struct list_head change_list;
-	struct apk_package *oldpkg;
-	struct apk_package *newpkg;
-};
-
-struct apk_state {
-	int refs;
-	struct list_head change_list_head;
-	unsigned char bitarray[];
-};
-
-struct apk_deferred_state {
-	unsigned int preference;
-	struct apk_package *deferred_install;
-	/* struct apk_pkg_name_queue *install_queue; */
-	struct apk_state *state;
-};
+struct apk_state;
 
 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);
 
 int apk_state_commit(struct apk_state *state, struct apk_database *db);
-
-int apk_state_satisfy_deps(struct apk_state *state,
-			   struct apk_dependency_array *deps);
-int apk_state_purge_unneeded(struct apk_state *state,
-			     struct apk_database *db);
-
-int apk_state_pkg_install(struct apk_state *state,
-			  struct apk_package *pkg);
-int apk_state_pkg_is_installed(struct apk_state *state,
-			       struct apk_package *pkg);
+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/apk_version.h b/src/apk_version.h
index e0b5a37..7650864 100644
--- a/src/apk_version.h
+++ b/src/apk_version.h
@@ -14,11 +14,9 @@
 
 #include "apk_blob.h"
 
-#define APK_VERSION_LESS		-1
-#define APK_VERSION_EQUAL		0
-#define APK_VERSION_GREATER		1
-
-#define APK_VERSION_RESULT_MASK(r)	(1 << ((r)+1))
+#define APK_VERSION_EQUAL		1
+#define APK_VERSION_LESS		2
+#define APK_VERSION_GREATER		4
 
 int apk_version_validate(apk_blob_t ver);
 int apk_version_compare(apk_blob_t a, apk_blob_t b);
diff --git a/src/database.c b/src/database.c
index 5506ebb..9bf34ba 100644
--- a/src/database.c
+++ b/src/database.c
@@ -154,6 +154,7 @@ 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_hash_insert(&db->available.names, pn);
 
 	return pn;
@@ -355,7 +356,6 @@ static struct apk_package *apk_db_pkg_add(struct apk_database *db, struct apk_pa
 	idb = apk_hash_get(&db->available.packages, APK_BLOB_BUF(pkg->csum));
 	if (idb == NULL) {
 		idb = pkg;
-		pkg->id = db->pkg_id++;
 		apk_hash_insert(&db->available.packages, pkg);
 		*apk_package_array_add(&pkg->name->pkgs) = pkg;
 		apk_db_pkg_rdepends(db, pkg);
@@ -393,7 +393,7 @@ static int apk_db_index_read(struct apk_database *db, struct apk_istream *is, in
 				if (repo != -1)
 					pkg->repos |= BIT(repo);
 				else
-					apk_pkg_set_state(db, pkg, APK_STATE_INSTALL);
+					apk_pkg_set_state(db, pkg, APK_PKG_INSTALLED);
 
 				if (apk_db_pkg_add(db, pkg) != pkg && repo == -1) {
 					apk_error("Installed database load failed");
@@ -573,6 +573,7 @@ static int apk_db_read_state(struct apk_database *db)
 {
 	struct apk_istream *is;
 	apk_blob_t blob;
+	int i;
 
 	/* Read:
 	 * 1. installed repository
@@ -590,6 +591,9 @@ static int apk_db_read_state(struct apk_database *db)
 	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;
+
 	is = apk_istream_from_file("var/lib/apk/installed");
 	if (is != NULL) {
 		apk_db_index_read(db, is, -1);
@@ -742,7 +746,7 @@ struct write_ctx {
 	int fd;
 };
 
-static int apk_db_write_config(struct apk_database *db)
+int apk_db_write_config(struct apk_database *db)
 {
 	struct apk_ostream *os;
 
@@ -919,39 +923,6 @@ int apk_db_add_repository(apk_database_t _db, apk_blob_t repository)
 	return 0;
 }
 
-int apk_db_recalculate_and_commit(struct apk_database *db)
-{
-	struct apk_state *state;
-	int r;
-
-	state = apk_state_new(db);
-	r = apk_state_satisfy_deps(state, db->world);
-	if (r == 0) {
-		r = apk_state_purge_unneeded(state, db);
-		if (r != 0) {
-			apk_error("Failed to clean up state");
-			return r;
-		}
-
-		r = apk_state_commit(state, db);
-		if (r != 0) {
-			apk_error("Failed to commit changes");
-			return r;
-		}
-		apk_db_write_config(db);
-
-		apk_message("OK: %d packages, %d dirs, %d files",
-			    db->installed.stats.packages,
-			    db->installed.stats.dirs,
-			    db->installed.stats.files);
-	} else {
-		apk_error("Failed to build installation graph");
-	}
-	apk_state_unref(state);
-
-	return r;
-}
-
 static void extract_cb(void *_ctx, size_t progress)
 {
 	struct install_ctx *ctx = (struct install_ctx *) _ctx;
@@ -1069,7 +1040,7 @@ static int apk_db_install_archive_entry(void *_ctx,
 		if (file->diri != diri) {
 			opkg = file->diri->pkg;
 			if (opkg->name != pkg->name) {
-				if (!apk_force) {
+				if (!(apk_flags & APK_FORCE)) {
 					apk_error("%s: Trying to overwrite %s "
 						  "owned by %s.\n",
 						  pkg->name->name, ae->name,
@@ -1093,7 +1064,7 @@ static int apk_db_install_archive_entry(void *_ctx,
 		    (memcmp(file->csum, fi.csum, sizeof(csum_t)) != 0 ||
 		     !csum_valid(file->csum))) {
 			/* Protected file. Extract to separate place */
-			if (!apk_clean) {
+			if (!(apk_flags & APK_CLEAN_PROTECTED)) {
 				snprintf(alt_name, sizeof(alt_name),
 					 "%s/%s.apk-new",
 					 diri->dir->dirname, file->filename);
@@ -1160,7 +1131,7 @@ static void apk_db_purge_pkg(struct apk_database *db,
 		__hlist_del(dc, &pkg->owned_dirs.first);
 		apk_db_diri_free(db, diri);
 	}
-	apk_pkg_set_state(db, pkg, APK_STATE_NO_INSTALL);
+	apk_pkg_set_state(db, pkg, APK_PKG_NOT_INSTALLED);
 }
 
 int apk_db_install_pkg(struct apk_database *db,
@@ -1229,7 +1200,7 @@ int apk_db_install_pkg(struct apk_database *db,
 
 	bs->close(bs, csum, NULL);
 
-	apk_pkg_set_state(db, newpkg, APK_STATE_INSTALL);
+	apk_pkg_set_state(db, newpkg, APK_PKG_INSTALLED);
 
 	if (memcmp(csum, newpkg->csum, sizeof(csum)) != 0)
 		apk_warning("%s-%s: checksum does not match",
diff --git a/src/del.c b/src/del.c
index 3e480a9..e980d71 100644
--- a/src/del.c
+++ b/src/del.c
@@ -11,12 +11,15 @@
 
 #include <stdio.h>
 #include "apk_applet.h"
+#include "apk_state.h"
 #include "apk_database.h"
 
 static int del_main(void *ctx, int argc, char **argv)
 {
 	struct apk_database db;
-	int i, j;
+	struct apk_state *state;
+	struct apk_name *name;
+	int i, j, r;
 
 	if (apk_db_open(&db, apk_root, APK_OPENF_WRITE) < 0)
 		return -1;
@@ -24,7 +27,13 @@ static int del_main(void *ctx, int argc, char **argv)
 	if (db.world == NULL)
 		goto out;
 
+	state = apk_state_new(&db);
 	for (i = 0; i < argc; i++) {
+		struct apk_dependency dep;
+
+		name = apk_db_get_name(&db, APK_BLOB_STR(argv[i]));
+
+		/* Remove from world, so we get proper changeset */
 		for (j = 0; j < db.world->num; j++) {
 			if (strcmp(db.world->item[j].name->name,
 				   argv[i]) == 0) {
@@ -34,13 +43,26 @@ static int del_main(void *ctx, int argc, char **argv)
 					apk_dependency_array_resize(db.world, db.world->num-1);
 			}
 		}
-	}
+		name->flags &= ~APK_NAME_TOPLEVEL;
 
-	apk_db_recalculate_and_commit(&db);
+		dep = (struct apk_dependency) {
+			.name = name,
+			.result_mask = APK_DEPMASK_CONFLICT,
+		};
+
+		r = apk_state_lock_dependency(state, &dep);
+		if (r != 0) {
+			apk_error("Unable to remove '%s'", name->name);
+			goto err;
+		}
+	}
+	r = apk_state_commit(state, &db);
+err:
+	apk_state_unref(state);
 out:
 	apk_db_close(&db);
 
-	return 0;
+	return r;
 }
 
 static struct apk_applet apk_del = {
diff --git a/src/info.c b/src/info.c
index c7a05f8..4bc3ddb 100644
--- a/src/info.c
+++ b/src/info.c
@@ -50,7 +50,7 @@ static int info_exists(struct info_ctx *ctx, struct apk_database *db,
 			return 1;
 
 		for (j = 0; j < name->pkgs->num; j++) {
-			if (apk_pkg_get_state(name->pkgs->item[j]) == APK_STATE_INSTALL)
+			if (apk_pkg_get_state(name->pkgs->item[j]) == APK_PKG_INSTALLED)
 				break;
 		}
 		if (j >= name->pkgs->num)
@@ -76,6 +76,7 @@ static int info_who_owns(struct info_ctx *ctx, struct apk_database *db,
 		if (apk_verbosity < 1) {
 			dep = (struct apk_dependency) {
 				.name = pkg->name,
+				.result_mask = APK_DEPMASK_REQUIRE,
 			};
 			apk_deps_add(&deps, &dep);
 		} else {
@@ -107,7 +108,7 @@ static int info_package(struct info_ctx *ctx, struct apk_database *db,
 		}
 		for (j = 0; j < name->pkgs->num; j++) {
 			struct apk_package *pkg = name->pkgs->item[j];
-			if (apk_pkg_get_state(pkg) == APK_STATE_INSTALL)
+			if (apk_pkg_get_state(pkg) == APK_PKG_INSTALLED)
 				ctx->subaction(pkg);
 		}
 	}
@@ -172,7 +173,7 @@ static void info_print_required_by(struct apk_package *pkg)
 		for (j = 0; j < name0->pkgs->num; j++) {
 			struct apk_package *pkg0 = name0->pkgs->item[j];
 
-			if (apk_pkg_get_state(pkg0) != APK_STATE_INSTALL ||
+			if (apk_pkg_get_state(pkg0) != APK_PKG_INSTALLED ||
 			    pkg0->depends == NULL)
 				continue;
 			for (k = 0; k < pkg0->depends->num; k++) {
diff --git a/src/package.c b/src/package.c
index 4d9f33d..4c282f8 100644
--- a/src/package.c
+++ b/src/package.c
@@ -100,10 +100,46 @@ static int parse_depend(void *ctx, apk_blob_t blob)
 	struct parse_depend_ctx *pctx = (struct parse_depend_ctx *) ctx;
 	struct apk_dependency *dep;
 	struct apk_name *name;
+	apk_blob_t bname, bop, bver = APK_BLOB_NULL;
+	int mask = APK_VERSION_LESS | APK_VERSION_EQUAL | APK_VERSION_GREATER;
 
 	if (blob.len == 0)
 		return 0;
 
+	/* [!]name[<,<=,=,>=,>]ver */
+	if (blob.ptr[0] == '!') {
+		mask = 0;
+		blob.ptr++;
+		blob.len--;
+	}
+	if (apk_blob_cspn(blob, "<>=", &bname, &bop)) {
+		int i;
+
+		if (mask == 0)
+			return -1;
+		if (!apk_blob_spn(bop, "<>=", &bop, &bver))
+			return -1;
+		for (i = 0; i < blob.len; i++) {
+			switch (blob.ptr[i]) {
+			case '<':
+				mask |= APK_VERSION_LESS;
+				break;
+			case '>':
+				mask |= APK_VERSION_GREATER;
+				break;
+			case '=':
+				mask |= APK_VERSION_EQUAL;
+				break;
+			}
+		}
+		if ((mask & (APK_VERSION_LESS|APK_VERSION_GREATER))
+		    == (APK_VERSION_LESS|APK_VERSION_GREATER))
+			return -1;
+
+		if (!apk_version_validate(bver))
+			return -1;
+	}
+
 	name = apk_db_get_name(pctx->db, blob);
 	if (name == NULL)
 		return -1;
@@ -114,6 +150,8 @@ static int parse_depend(void *ctx, apk_blob_t blob)
 
 	*dep = (struct apk_dependency){
 		.name = name,
+		.version = APK_BLOB_IS_NULL(bver) ? NULL : apk_blob_cstr(bver),
+		.result_mask = mask,
 	};
 
 	return 0;
@@ -131,6 +169,24 @@ void apk_deps_parse(struct apk_database *db,
 	apk_blob_for_each_segment(blob, " ", parse_depend, &ctx);
 }
 
+static const char *mask2str(int mask)
+{
+	switch (mask) {
+	case APK_VERSION_LESS:
+		return "<";
+	case APK_VERSION_LESS|APK_VERSION_EQUAL:
+		return "<=";
+	case APK_VERSION_EQUAL:
+		return "=";
+	case APK_VERSION_GREATER|APK_VERSION_EQUAL:
+		return ">=";
+	case APK_VERSION_GREATER:
+		return ">";
+	default:
+		return "?";
+	}
+}
+
 int apk_deps_format(char *buf, int size,
 		    struct apk_dependency_array *depends)
 {
@@ -142,9 +198,25 @@ int apk_deps_format(char *buf, int size,
 	for (i = 0; i < depends->num; i++) {
 		if (i && n < size)
 			buf[n++] = ' ';
-		n += snprintf(&buf[n], size-n,
-			      "%s",
-			      depends->item[i].name->name);
+		switch (depends->item[i].result_mask) {
+		case APK_DEPMASK_CONFLICT:
+			n += snprintf(&buf[n], size-n,
+				      "!%s",
+				      depends->item[i].name->name);
+			break;
+		case APK_DEPMASK_REQUIRE:
+			n += snprintf(&buf[n], size-n,
+				      "%s",
+				      depends->item[i].name->name);
+			break;
+		default:
+			n += snprintf(&buf[n], size-n,
+				      "%s%s%s",
+				      depends->item[i].name->name,
+				      mask2str(depends->item[i].result_mask),
+				      depends->item[i].version);
+			break;
+		}
 	}
 	return n;
 }
@@ -430,21 +502,21 @@ void apk_pkg_free(struct apk_package *pkg)
 int apk_pkg_get_state(struct apk_package *pkg)
 {
 	if (list_hashed(&pkg->installed_pkgs_list))
-		return APK_STATE_INSTALL;
-	return APK_STATE_NO_INSTALL;
+		return APK_PKG_INSTALLED;
+	return APK_PKG_NOT_INSTALLED;
 }
 
 void apk_pkg_set_state(struct apk_database *db, struct apk_package *pkg, int state)
 {
 	switch (state) {
-	case APK_STATE_INSTALL:
+	case APK_PKG_INSTALLED:
 		if (!list_hashed(&pkg->installed_pkgs_list)) {
 			db->installed.stats.packages++;
 			list_add_tail(&pkg->installed_pkgs_list,
 				      &db->installed.packages);
 		}
 		break;
-	case APK_STATE_NO_INSTALL:
+	case APK_PKG_NOT_INSTALLED:
 		if (list_hashed(&pkg->installed_pkgs_list)) {
 			db->installed.stats.packages--;
 			list_del(&pkg->installed_pkgs_list);
diff --git a/src/state.c b/src/state.c
index a6aaf7f..a0abb57 100644
--- a/src/state.c
+++ b/src/state.c
@@ -10,17 +10,129 @@
  */
 
 #include <stdio.h>
+#include <unistd.h>
 #include <malloc.h>
 
 #include "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_name_choices {
+	unsigned short refs, num;
+	struct apk_package *pkgs[];
+};
+
+struct apk_state {
+	int refs;
+	struct list_head change_list_head;
+	apk_name_state_t name[];
+};
+
+#if 0
+struct apk_deferred_state {
+	unsigned int preference;
+	struct apk_state *state;
+};
+#endif
+
+static int inline ns_locked(apk_name_state_t name)
+{
+	if (((intptr_t) name) & 0x1)
+		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) | 0x1);
+}
+
+static struct apk_package *ns_to_pkg(apk_name_state_t name)
+{
+	return (struct apk_package *) (((intptr_t) name) & ~0x1);
+}
+
+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_name *name)
+{
+	struct apk_name_choices *nc;
+
+	if (name->pkgs == NULL)
+		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 *));
+	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));
+}
+
 struct apk_state *apk_state_new(struct apk_database *db)
 {
 	struct apk_state *state;
 	int num_bytes;
 
-	num_bytes = sizeof(struct apk_state) + (db->pkg_id * 2 + 7) / 8;
+	num_bytes = sizeof(struct apk_state) + db->name_id * sizeof(char *);
 	state = (struct apk_state*) calloc(1, num_bytes);
 	state->refs = 1;
 	list_init(&state->change_list_head);
@@ -38,7 +150,6 @@ void apk_state_unref(struct apk_state *state)
 {
 	if (--state->refs > 0)
 		return;
-
 	free(state);
 }
 
@@ -60,22 +171,195 @@ static int apk_state_add_change(struct apk_state *state,
 	return 0;
 }
 
-static void apk_state_set(struct apk_state *state, int pos, int val)
+int apk_state_lock_dependency(struct apk_state *state,
+			      struct apk_dependency *dep)
 {
-	int byte = pos / 4, offs = pos % 4;
+	struct apk_name *name = dep->name;
+	struct apk_name_choices *c;
+        struct apk_package *installed, *latest, *use;
+	int i;
+
+	if (ns_empty(state->name[name->id])) {
+		if (dep->result_mask == APK_DEPMASK_CONFLICT)
+			return apk_state_lock_name(state, name, NULL);
+
+		/* This name has not been visited yet.
+		 * Construct list of candidates. */
+		state->name[name->id] = ns_from_choices(name_choices_new(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 (pkg == NULL) {
+			if (dep->result_mask == APK_DEPMASK_CONFLICT)
+				return 0;
+			return -1;
+		}
+
+		if (apk_version_compare(APK_BLOB_STR(pkg->version),
+					APK_BLOB_STR(dep->version))
+		    & dep->result_mask)
+			return 0;
+
+		return -1;
+	}
+
+	/* Multiple candidates: prune incompatible versions. */
+	c = ns_to_choices(state->name[name->id]);
+	for (i = 0; i < c->num; i++) {
+		if (apk_version_compare(APK_BLOB_STR(c->pkgs[i]->version),
+					APK_BLOB_STR(dep->version))
+		    & dep->result_mask)
+			continue;
+
+		c = name_choices_writable(c);
+		c->pkgs[i] = c->pkgs[c->num - 1];
+		c->num--;
+	}
+	if (c->num == 0) {
+		name_choices_unref(c);
+		return -1;
+	}
+	if (c->num == 1) {
+		struct apk_package *pkg = c->pkgs[0];
+		name_choices_unref(c);
+		state->name[name->id] = NULL;
+		return apk_state_lock_name(state, name, pkg);
+	}
+	state->name[name->id] = ns_from_choices(c);
+
+#if 1
+	/* Get latest and installed packages */
+	for (i = 0; i < c->num; i++) {
+		struct apk_package *pkg = c->pkgs[i];
+
+		if (apk_pkg_get_state(c->pkgs[i]) == APK_PKG_INSTALLED)
+			installed = pkg;
+
+		if (latest == NULL ||
+		    apk_version_compare(APK_BLOB_STR(pkg->version),
+					APK_BLOB_STR(latest->version)) == APK_VERSION_GREATER)
+			latest = pkg;
+	}
 
-	state->bitarray[byte] &= ~(0x3 << (offs * 2));
-	state->bitarray[byte] |= (val & 0x3) << (offs * 2);
+	/* Choose the best looking candidate.
+	 * FIXME: We should instead try all alternatives. */
+	if (apk_flags & APK_UPGRADE) {
+		use = latest;
+	} else {
+		if (installed != NULL)
+			use = installed;
+		else
+			use = latest;
+	}
+	if (use == NULL)
+		return -1;
+
+	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
+}
+
+static int apk_state_fix_package(struct apk_state *state,
+				 struct apk_package *pkg)
+{
+	int i, r;
+
+	for (i = 0; i < pkg->depends->num; i++) {
+		r = apk_state_lock_dependency(state,
+					      &pkg->depends->item[i]);
+		if (r != 0)
+			return -1;
+	}
+	return 0;
 }
 
-static int apk_state_get(struct apk_state *state, int pos)
+int apk_state_lock_name(struct apk_state *state,
+			struct apk_name *name,
+			struct apk_package *newpkg)
 {
-	int byte = pos / 4, offs = pos % 4;
+	struct apk_package *oldpkg = NULL;
+	int i, j, k, r;
+
+	ns_free(state->name[name->id]);
+	state->name[name->id] = ns_from_pkg(newpkg);
+
+	if (name->pkgs != NULL) {
+		for (i = 0; i < name->pkgs->num; i++) {
+			struct apk_package *pkg = name->pkgs->item[i];
 
-	if (state == NULL)
-		return APK_STATE_NOT_CONSIDERED;
+			if (name->pkgs->item[i]->name == name &&
+			    apk_pkg_get_state(name->pkgs->item[i]) == APK_PKG_INSTALLED)
+				oldpkg = pkg;
+		}
+	}
+
+	/* If the chosen package is installed, all is done here */
+	if (oldpkg == newpkg)
+		return 0;
 
-	return (state->bitarray[byte] >> (offs * 2)) & 0x3;
+	/* First we need to make sure the dependants of the old package
+	 * still have their dependencies ok. */
+	if (oldpkg != NULL && oldpkg->name->rdepends != NULL) {
+		for (i = 0; i < name->rdepends->num; i++) {
+			struct apk_name *name0 = name->rdepends->item[i];
+
+			for (j = 0; j < name0->pkgs->num; j++) {
+				struct apk_package *pkg0 = name0->pkgs->item[j];
+
+				if (apk_pkg_get_state(pkg0) != APK_PKG_INSTALLED)
+					continue;
+				if (pkg0->depends == NULL)
+					continue;
+				for (k = 0; k < pkg0->depends->num; k++) {
+					if (pkg0->depends->item[k].name
+					    == name)
+						break;
+				}
+				if (k < pkg0->depends->num) {
+					/* FIXME: Try fixing harder */
+					if (newpkg == NULL) {
+						struct apk_dependency dep;
+						dep = (struct apk_dependency) {
+							.name = name0,
+							.result_mask = APK_DEPMASK_CONFLICT,
+						};
+						r = apk_state_lock_dependency(state, &dep);
+					} else
+						r = apk_state_lock_dependency(state,
+									      &pkg0->depends->item[k]);
+					if (r != 0)
+						return r;
+				}
+			}
+		}
+	}
+
+	/* Check that all other dependencies hold for the new package. */
+	if (newpkg != NULL && newpkg->depends != NULL) {
+		r = apk_state_fix_package(state, newpkg);
+		if (r != 0)
+			return r;
+	}
+
+	/* Track change */
+	r = apk_state_add_change(state, oldpkg, newpkg);
+	if (r != 0)
+		return r;
+
+	return 0;
 }
 
 static void apk_print_change(struct apk_database *db,
@@ -96,7 +380,8 @@ static void apk_print_change(struct apk_database *db,
 			    name->name, newpkg->version);
 	} else if (newpkg == NULL) {
 		apk_message("Purging %s (%s)",
-			    name->name, oldpkg->version);
+			    name->name,
+			    oldpkg->version);
 	} else {
 		r = apk_version_compare(APK_BLOB_STR(newpkg->version),
 					APK_BLOB_STR(oldpkg->version));
@@ -170,144 +455,121 @@ static void progress_cb(void *ctx, size_t progress)
 	prog->count = count;
 }
 
-int apk_state_commit(struct apk_state *state,
-		     struct apk_database *db)
+static int dump_packages(struct apk_state *state,
+			 int (*cmp)(struct apk_change *change),
+			 const char *msg)
 {
-	struct progress prog;
 	struct apk_change *change;
-	int r;
-
-	/* Count what needs to be done */
-	memset(&prog, 0, sizeof(prog));
-	list_for_each_entry(change, &state->change_list_head, change_list)
-		apk_count_change(change, &prog.total);
+	struct apk_name *name;
+	int match = 0;
 
-	/* Go through changes */
 	list_for_each_entry(change, &state->change_list_head, change_list) {
-		apk_print_change(db, change->oldpkg, change->newpkg);
-		prog.pkg = change->newpkg;
-
-		r = apk_db_install_pkg(db, change->oldpkg, change->newpkg,
-				       apk_progress ? progress_cb : NULL,
-				       &prog);
-		if (r != 0)
-			return r;
-
-		apk_count_change(change, &prog.done);
+		if (!cmp(change))
+			continue;
+		if (match == 0)
+			fprintf(stderr, "%s:\n ", msg);
+		if (change->newpkg != NULL)
+			name = change->newpkg->name;
+		else
+			name = change->oldpkg->name;
+
+		fprintf(stderr, " %s%s", name->name,
+			(name->flags & APK_NAME_TOPLEVEL) ? "*" : "");
+		match++;
 	}
-	if (apk_progress)
-		apk_draw_progress(20, 1);
-
-	return 0;
+	if (match)
+		fprintf(stderr, "\n");
+	return match;
 }
 
-int apk_state_satisfy_name(struct apk_state *state,
-			   struct apk_name *name)
+static int cmp_remove(struct apk_change *change)
 {
-	struct apk_package *preferred = NULL, *installed = NULL;
-	int i, r;
-
-	/* Is something already installed? Or figure out the preferred
-	 * package. */
-	for (i = 0; i < name->pkgs->num; i++) {
-		if (apk_state_get(state, name->pkgs->item[i]->id) ==
-		    APK_STATE_INSTALL)
-			return 0;
-
-		if (apk_pkg_get_state(name->pkgs->item[i]) == APK_STATE_INSTALL) {
-			installed = name->pkgs->item[i];
-			if (!apk_upgrade) {
-				preferred = installed;
-				break;
-			}
-		}
-
-		if (preferred == NULL) {
-			preferred = name->pkgs->item[i];
-			continue;
-		}
-
-		if (apk_version_compare(APK_BLOB_STR(name->pkgs->item[i]->version),
-					APK_BLOB_STR(preferred->version)) ==
-		    APK_VERSION_GREATER) {
-			preferred = name->pkgs->item[i];
-			continue;
-		}
-	}
+	return change->newpkg == NULL;
+}
 
-	/* FIXME: current code considers only the prefferred package. */
+static int cmp_new(struct apk_change *change)
+{
+	return change->oldpkg == NULL;
+}
 
-	/* Can we install? */
-	switch (apk_state_get(state, preferred->id)) {
-	case APK_STATE_INSTALL:
+static int cmp_downgrade(struct apk_change *change)
+{
+	if (change->newpkg == NULL || change->oldpkg == NULL)
 		return 0;
-	case APK_STATE_NO_INSTALL:
-		return -1;
-	}
-
-	/* Update state bits and track changes */
-	for (i = 0; i < name->pkgs->num; i++) {
-		if (name->pkgs->item[i] != preferred)
-			apk_state_set(state, name->pkgs->item[i]->id,
-				      APK_STATE_NO_INSTALL);
-	}
-	apk_state_set(state, preferred->id, APK_STATE_INSTALL);
-
-	r = apk_state_satisfy_deps(state, preferred->depends);
-	if (r != 0)
-		return r;
-
-	if (preferred != installed) {
-		r = apk_state_add_change(state, installed, preferred);
-		if (r != 0)
-			return r;
-	}
-
+	if (apk_version_compare(APK_BLOB_STR(change->newpkg->version),
+				APK_BLOB_STR(change->oldpkg->version))
+	    & APK_VERSION_LESS)
+		return 1;
 	return 0;
 }
 
-int apk_state_satisfy_deps(struct apk_state *state,
-			   struct apk_dependency_array *deps)
+static int cmp_upgrade(struct apk_change *change)
 {
-	struct apk_name *name;
-	int r, i;
-
-	if (deps == NULL)
+	if (change->newpkg == NULL || change->oldpkg == NULL)
 		return 0;
-
-	for (i = 0; i < deps->num; i++) {
-		name = deps->item[i].name;
-		if (name->pkgs == NULL) {
-			apk_error("No providers for '%s'", name->name);
-			return -1;
-		}
-		r = apk_state_satisfy_name(state, name);
-		if (r != 0)
-			return r;
-	}
+	if (apk_version_compare(APK_BLOB_STR(change->newpkg->version),
+				APK_BLOB_STR(change->oldpkg->version))
+	    & APK_VERSION_GREATER)
+		return 1;
 	return 0;
 }
 
-int apk_state_purge_unneeded(struct apk_state *state,
-			     struct apk_database *db)
+int apk_state_commit(struct apk_state *state,
+		     struct apk_database *db)
 {
-	struct apk_package *pkg;
+	struct progress prog;
+	struct apk_change *change;
 	int r;
 
-	/* Purge unconsidered packages */
-	list_for_each_entry(pkg, &db->installed.packages, installed_pkgs_list) {
-		switch (apk_state_get(state, pkg->id)) {
-		case APK_STATE_INSTALL:
-		case APK_STATE_NO_INSTALL:
-			break;
-		default:
-			r = apk_state_add_change(state, pkg, NULL);
+	/* Count what needs to be done */
+	memset(&prog, 0, sizeof(prog));
+	list_for_each_entry(change, &state->change_list_head, change_list)
+		apk_count_change(change, &prog.total);
+
+	if (apk_verbosity >= 1) {
+		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_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");
+			fprintf(stderr, "Do you want to continue [Y/n]? ");
+			fflush(stderr);
+			r = fgetc(stdin);
+			if (r != 'y' && r != 'Y')
+				return -1;
+		}
+	}
+
+	/* Go through changes */
+	list_for_each_entry(change, &state->change_list_head, change_list) {
+		apk_print_change(db, change->oldpkg, change->newpkg);
+		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)
 				return r;
-			break;
 		}
+
+		apk_count_change(change, &prog.done);
 	}
+	if (apk_flags & APK_PROGRESS)
+		apk_draw_progress(20, 1);
+
+	if (!(apk_flags & APK_SIMULATE))
+		apk_db_write_config(db);
+
+	apk_message("OK: %d packages, %d dirs, %d files",
+		    db->installed.stats.packages,
+		    db->installed.stats.dirs,
+		    db->installed.stats.files);
 
 	return 0;
 }
-
diff --git a/src/version.c b/src/version.c
index 8594a93..45a9ede 100644
--- a/src/version.c
+++ b/src/version.c
@@ -143,6 +143,12 @@ int apk_version_compare(apk_blob_t a, apk_blob_t b)
 	int at = TOKEN_DIGIT, bt = TOKEN_DIGIT;
 	int av = 0, bv = 0;
 
+	if (APK_BLOB_IS_NULL(a) || APK_BLOB_IS_NULL(b)) {
+		if (APK_BLOB_IS_NULL(a) && APK_BLOB_IS_NULL(b))
+			return APK_VERSION_EQUAL;
+		return APK_VERSION_EQUAL | APK_VERSION_GREATER | APK_VERSION_LESS;
+	}
+
 	while (at == bt && at != TOKEN_END && at != TOKEN_INVALID && av == bv) {
 		av = get_token(&at, &a);
 		bv = get_token(&bt, &b);