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.

1 files changed, 386 insertions, 124 deletions

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