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);