solver: rewrite backtracking and scoring system

* properly do absolute scoring now, the previous scoring where
  preference could get reduced could have caused incorrect early
  pruning of search tree

* backtracking is now separated from package state, and first
  branching point is the decision if a name is left unassigned
  or if something _has_ to be assigned. this allows multiple future
  search tree optimizations like handling of common dependencies
  early.

* merge common dependency names early to provide deeper forward
  checking.

2 files changed, 695 insertions, 406 deletions

diff --git a/src/apk_defines.h b/src/apk_defines.h
index 3c72c73..2ef0c3b 100644
--- a/src/apk_defines.h
+++ b/src/apk_defines.h
@@ -257,6 +257,11 @@ static inline int list_hashed(const struct list_head *n)
 	return n->next != n && n->next != NULL;
 }
 
+static inline int list_empty(const struct list_head *n)
+{
+	return n->next == n;
+}
+
 #define list_entry(ptr, type, member) container_of(ptr,type,member)
 
 #define list_for_each(pos, head) \
diff --git a/src/solver.c b/src/solver.c
index 0283791..a27b4d4 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -1,7 +1,7 @@
 /* solver.c - Alpine Package Keeper (APK)
  * A backtracking, forward checking dependency graph solver.
  *
- * Copyright (C) 2008-2011 Timo Teräs <timo.teras@iki.fi>
+ * Copyright (C) 2008-2012 Timo Teräs <timo.teras@iki.fi>
  * All rights reserved.
  *
  * This program is free software; you can redistribute it and/or modify it
@@ -16,68 +16,116 @@
 
 #include "apk_print.h"
 
-#if 0
+//#define DEBUG_PRINT
+#define DEBUG_CHECKS
+
+#ifdef DEBUG_PRINT
 #include <stdio.h>
 #define dbg_printf(args...) fprintf(stderr, args)
 #else
 #define dbg_printf(args...)
 #endif
 
-#define APK_PKGSTF_NOINSTALL		0
-#define APK_PKGSTF_INSTALL		1
-#define APK_PKGSTF_ALT_BRANCH		2
+#if defined(DEBUG_PRINT) || defined(DEBUG_CHECKS)
+#define ASSERT(cond, fmt...) \
+	if (!(cond)) { fprintf(stderr, fmt); *(char*)NULL = 0; }
+#else
+#define ASSERT(cond, fmt...)
+#endif
 
 struct apk_score {
-	unsigned short unsatisfiable;
+	unsigned short conflicts;
+	unsigned short non_preferred_actions;
 	unsigned short preference;
 };
 
+#define SCORE_FMT		"{%d/%d/%d}"
+#define SCORE_PRINTF(s)		(s)->conflicts, (s)->non_preferred_actions, (s)->preference
+
+enum {
+	DECISION_ASSIGN = 0,
+	DECISION_EXCLUDE
+};
+
+enum {
+	BRANCH_NO,
+	BRANCH_YES,
+};
+
+struct apk_decision {
+	union {
+		struct apk_name *name;
+		struct apk_package *pkg;
+	};
+#ifdef DEBUG_CHECKS
+	struct apk_score saved_score;
+#endif
+
+	unsigned no_package : 1;
+	unsigned type : 1;
+	unsigned branching_point : 1;
+	unsigned topology_position : 1;
+};
+
 struct apk_package_state {
-	struct apk_package *backtrack;
 	unsigned int topology_soft;
 	unsigned short conflicts;
+	unsigned char preference;
 	unsigned availability_checked : 1;
 	unsigned unavailable : 1;
 	unsigned install_applied : 1;
 	unsigned handle_install_if : 1;
 	unsigned locked : 1;
-	unsigned flags : 2;
 };
 
 struct apk_name_state {
 	struct list_head unsolved_list;
 	struct apk_name *name;
 	struct apk_package *chosen;
+
 	struct apk_score minimum_penalty;
+	unsigned short merge_index;
+	unsigned short prerequires;
 	unsigned short requirers;
 	unsigned short install_ifs;
 
 	unsigned short preferred_pinning;
 	unsigned short allowed_pinning;
 
-	unsigned int solver_flags_local : 4;
-	unsigned int solver_flags_local_mask : 4;
-	unsigned int solver_flags_inherited : 4;
+	unsigned solver_flags_local : 4;
+	unsigned solver_flags_local_mask : 4;
+	unsigned solver_flags_inherited : 4;
 
-	unsigned int locked : 1;
-	unsigned int in_changeset : 1;
+	/* one time prepare/finish flags */
+	unsigned decision_counted : 1;
+	unsigned originally_installed : 1;
+	unsigned prepared : 1;
+	unsigned in_changeset : 1;
+
+	/* dynamic state flags */
+	unsigned none_excluded : 1;
+	unsigned locked : 1;
 };
 
 struct apk_solver_state {
 	struct apk_database *db;
-	unsigned num_topology_positions;
+	struct apk_decision *decisions;
 
 	struct list_head unsolved_list_head;
-	struct apk_package *latest_decision;
+
+	unsigned int num_topology_positions;
+	unsigned int num_decisions, max_decisions;
 	unsigned int topology_position;
 	unsigned int assigned_names;
-	struct apk_score score;
-	struct apk_score minimum_penalty;
-
-	unsigned int solver_flags : 4;
 
 	struct apk_solution_array *best_solution;
+
+	struct apk_score score;
+	struct apk_score minimum_penalty;
 	struct apk_score best_score;
+
+	unsigned solver_flags : 4;
+	unsigned impossible_constraints : 1;
 };
 
 typedef enum {
@@ -89,45 +137,66 @@ typedef enum {
 
 static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep);
 static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *dep);
-static solver_result_t push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
-				     int flags);
+static solver_result_t push_decision(struct apk_solver_state *ss,
+				     struct apk_name *name,
+				     struct apk_package *pkg,
+				     int primary_decision,
+				     int branching_point,
+				     int topology_position);
 
 static void addscore(struct apk_score *a, struct apk_score *b)
 {
-	a->unsatisfiable += b->unsatisfiable;
+	a->conflicts += b->conflicts;
+	a->non_preferred_actions += b->non_preferred_actions;
 	a->preference += b->preference;
 }
 
 static void subscore(struct apk_score *a, struct apk_score *b)
 {
-	a->unsatisfiable -= b->unsatisfiable;
+	a->conflicts -= b->conflicts;
+	a->non_preferred_actions -= b->non_preferred_actions;
 	a->preference -= b->preference;
 }
 
 static int cmpscore(struct apk_score *a, struct apk_score *b)
 {
-	if (a->unsatisfiable < b->unsatisfiable)
+	if (a->conflicts < b->conflicts)
+		return -1;
+	if (a->conflicts > b->conflicts)
+		return 1;
+
+	if (a->non_preferred_actions < b->non_preferred_actions)
 		return -1;
-	if (a->unsatisfiable > b->unsatisfiable)
+	if (a->non_preferred_actions > b->non_preferred_actions)
 		return 1;
+
 	if (a->preference < b->preference)
 		return -1;
 	if (a->preference > b->preference)
 		return 1;
+
 	return 0;
 }
 
 static int cmpscore2(struct apk_score *a1, struct apk_score *a2, struct apk_score *b)
 {
-	if (a1->unsatisfiable+a2->unsatisfiable < b->unsatisfiable)
-		return -1;
-	if (a1->unsatisfiable+a2->unsatisfiable > b->unsatisfiable)
-		return 1;
-	if (a1->preference+a2->preference < b->preference)
-		return -1;
-	if (a1->preference+a2->preference > b->preference)
-		return 1;
-	return 0;
+	struct apk_score tmp = *a1;
+	addscore(&tmp, a2);
+	return cmpscore(&tmp, b);
+}
+
+static struct apk_name *decision_to_name(struct apk_decision *d)
+{
+	if (d->no_package)
+		return d->name;
+	return d->pkg->name;
+}
+
+static struct apk_package *decision_to_pkg(struct apk_decision *d)
+{
+	if (d->no_package)
+		return NULL;
+	return d->pkg;
 }
 
 static struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
@@ -214,9 +283,149 @@ static void foreach_rinstall_if_pkg(
 	}
 }
 
+static unsigned int get_pinning_mask_repos(struct apk_database *db, unsigned short pinning_mask)
+{
+	unsigned int repository_mask = 0;
+	int i;
+
+	for (i = 0; i < db->num_repo_tags && pinning_mask; i++) {
+		if (!(BIT(i) & pinning_mask))
+			continue;
+		pinning_mask &= ~BIT(i);
+		repository_mask |= db->repo_tags[i].allowed_repos;
+	}
+	return repository_mask;
+}
+
+static void get_topology_score(
+		struct apk_solver_state *ss,
+		struct apk_name_state *ns,
+		struct apk_package *pkg,
+		int lock_score,
+		struct apk_score *_score)
+{
+	struct apk_name *name = pkg->name;
+	struct apk_package_state *ps = pkg_to_ps(pkg);
+	struct apk_score score;
+	unsigned short name_flags;
+	unsigned int repos;
+	unsigned short preferred_pinning, allowed_pinning;
+	unsigned int preferred_repos, allowed_repos;
+
+	/* effective dynamic flags */
+	name_flags = ns->solver_flags_local | ns->solver_flags_inherited | ss->solver_flags;
+
+	score = (struct apk_score) {
+		.conflicts = ps->conflicts,
+		.preference = ps->preference,
+	};
+
+	if ((name_flags & APK_SOLVERF_AVAILABLE) && (pkg->repos == 0)) {
+		score.non_preferred_actions ++;
+		score.preference += name->pkgs->num;
+	} else if (lock_score && !(name_flags & APK_SOLVERF_UPGRADE)) {
+		/* not upgrading: it is not preferred to change package */
+		struct apk_name_state *ns = name_to_ns(name);
+		if (pkg->ipkg == NULL && ns->originally_installed)
+			score.non_preferred_actions++;
+	}
+
+	repos = pkg->repos | (pkg->ipkg ? ss->db->repo_tags[pkg->ipkg->repository_tag].allowed_repos : 0);
+	preferred_pinning = ns->preferred_pinning ?: APK_DEFAULT_PINNING_MASK;
+	preferred_repos = get_pinning_mask_repos(ss->db, preferred_pinning);
+
+	if (!(repos & preferred_repos))
+		score.non_preferred_actions++;
+
+	if (lock_score) {
+		allowed_pinning = ns->allowed_pinning | preferred_pinning;
+		allowed_repos = get_pinning_mask_repos(ss->db, allowed_pinning);
+
+		if (!(repos & allowed_repos))
+			score.non_preferred_actions += 2;
+	}
+
+	*_score = score;
+}
+
+static int is_topology_optimum(struct apk_solver_state *ss,
+			       struct apk_package *pkg)
+{
+	struct apk_name *name = pkg->name;
+	struct apk_name_state *ns = name_to_ns(name);
+	struct apk_score score;
+	int i;
+
+	/* FIXME: should not use absolute topology score */
+	get_topology_score(ss, ns, pkg, 1, &score);
+	for (i = 0; i < name->pkgs->num; i++) {
+		struct apk_package *pkg0 = name->pkgs->item[i];
+		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
+		struct apk_score score0;
+
+		if (pkg0 == pkg)
+			continue;
+
+		if (ps0 == NULL || ps0->locked ||
+		    ss->topology_position < pkg->topology_hard)
+			continue;
+
+		get_topology_score(ss, ns, pkg0, 1, &score0);
+		if (cmpscore(&score0, &score) < 0)
+			return 0;
+	}
+
+	return 1;
+}
+
+static int compare_absolute_package_preference(
+		struct apk_package *pkgA,
+		struct apk_package *pkgB)
+{
+	/* specified on command line directly */
+	if (pkgA->filename && !pkgB->filename)
+		return 1;
+	if (pkgB->filename && !pkgA->filename)
+		return -1;
+
+	/* upgrading, or neither of the package is installed, so
+	 * we just fall back comparing to versions */
+	switch (apk_pkg_version_compare(pkgA, pkgB)) {
+	case APK_VERSION_GREATER:
+		return 1;
+	case APK_VERSION_LESS:
+		return -1;
+	}
+
+	/* prefer the installed package */
+	if (pkgA->ipkg != NULL && pkgB->ipkg == NULL)
+		return 1;
+	if (pkgB->ipkg != NULL && pkgA->ipkg == NULL)
+		return -1;
+
+	/* prefer the one with lowest available repository */
+	return ffsl(pkgB->repos) - ffsl(pkgA->repos);
+}
+
+static void calculate_pkg_preference(struct apk_package *pkg)
+{
+	struct apk_name *name = pkg->name;
+	struct apk_package_state *ps = pkg_to_ps(pkg);
+	int i;
+
+	for (i = 0; i < name->pkgs->num; i++) {
+		struct apk_package *pkg0 = name->pkgs->item[i];
+		if (pkg == pkg0)
+			continue;
+		if (compare_absolute_package_preference(pkg, pkg0) < 0)
+			ps->preference++;
+	}
+}
+
 static void sort_hard_dependencies(struct apk_solver_state *ss, struct apk_package *pkg)
 {
 	struct apk_package_state *ps;
+	struct apk_name_state *ns;
 
 	if (pkg->state_ptr == NULL)
 		pkg->state_ptr = calloc(1, sizeof(struct apk_package_state));
@@ -226,11 +435,20 @@ static void sort_hard_dependencies(struct apk_solver_state *ss, struct apk_packa
 		return;
 	pkg->topology_hard = -1;
 	ps->topology_soft = -1;
+	calculate_pkg_preference(pkg);
 
 	/* Consider hard dependencies only */
 	foreach_dependency_pkg(ss, pkg->depends, sort_hard_dependencies);
 	foreach_dependency_pkg(ss, pkg->install_if, sort_hard_dependencies);
 
+	ss->max_decisions++;
+
+	ns = name_to_ns(pkg->name);
+	if (!ns->decision_counted) {
+		ss->max_decisions++;
+		ns->decision_counted = 1;
+	}
+
 	ps->topology_soft = pkg->topology_hard = ++ss->num_topology_positions;
 	dbg_printf(PKG_VER_FMT ": topology_hard=%d\n",
 		   PKG_VER_PRINTF(pkg), pkg->topology_hard);
@@ -302,128 +520,6 @@ static void foreach_dependency(struct apk_solver_state *ss, struct apk_dependenc
 		func(ss, &deps->item[i]);
 }
 
-static unsigned int get_pinning_mask_repos(struct apk_database *db, unsigned short pinning_mask)
-{
-	unsigned int repository_mask = 0;
-	int i;
-
-	for (i = 0; i < db->num_repo_tags && pinning_mask; i++) {
-		if (!(BIT(i) & pinning_mask))
-			continue;
-		pinning_mask &= ~BIT(i);
-		repository_mask |= db->repo_tags[i].allowed_repos;
-	}
-	return repository_mask;
-}
-
-static int compare_package_preference(unsigned short solver_flags,
-				      unsigned int preferred_repos,
-				      unsigned int allowed_repos,
-				      struct apk_package *pkgA,
-				      struct apk_package *pkgB,
-				      struct apk_database *db)
-{
-	unsigned int a_repos, b_repos;
-
-	/* specified on command line directly */
-	if (pkgA->filename && !pkgB->filename)
-		return 1;
-	if (pkgB->filename && !pkgA->filename)
-		return -1;
-
-	/* Is there a difference in pinning preference? */
-	a_repos = pkgA->repos | (pkgA->ipkg ? db->repo_tags[pkgA->ipkg->repository_tag].allowed_repos : 0);
-	b_repos = pkgB->repos | (pkgB->ipkg ? db->repo_tags[pkgB->ipkg->repository_tag].allowed_repos : 0);
-	if ((a_repos & preferred_repos) && !(b_repos & preferred_repos))
-		return 1;
-	if ((b_repos & preferred_repos) && !(a_repos & preferred_repos))
-		return -1;
-
-	/* Difference in allowed repositories? */
-	if ((a_repos & allowed_repos) && !(b_repos & allowed_repos))
-		return 1;
-	if ((b_repos & allowed_repos) && !(a_repos & allowed_repos))
-		return -1;
-
-	if (solver_flags & APK_SOLVERF_AVAILABLE) {
-		if (pkgA->repos != 0 && pkgB->repos == 0)
-			return 1;
-		if (pkgB->repos != 0 && pkgA->repos == 0)
-			return -1;
-	}
-
-	if (!(solver_flags & APK_SOLVERF_UPGRADE)) {
-		/* not upgrading, prefer the installed package */
-		if (pkgA->ipkg != NULL && pkgB->ipkg == NULL)
-			return 1;
-		if (pkgB->ipkg != NULL && pkgA->ipkg == NULL)
-			return -1;
-	}
-
-	/* upgrading, or neither of the package is installed, so
-	 * we just fall back comparing to versions */
-	switch (apk_pkg_version_compare(pkgA, pkgB)) {
-	case APK_VERSION_GREATER:
-		return 1;
-	case APK_VERSION_LESS:
-		return -1;
-	}
-
-	/* upgrading, prefer the installed package */
-	if (pkgA->ipkg != NULL && pkgB->ipkg == NULL)
-		return 1;
-	if (pkgB->ipkg != NULL && pkgA->ipkg == NULL)
-		return -1;
-
-	/* prefer the one with lowest available repository */
-	return ffsl(pkgB->repos) - ffsl(pkgA->repos);
-}
-
-static int get_preference(struct apk_solver_state *ss,
-			  struct apk_package *pkg,
-			  int installable_only)
-{
-	struct apk_name *name = pkg->name;
-	struct apk_name_state *ns = name_to_ns(name);
-	unsigned short name_flags = ns->solver_flags_local
-		| ns->solver_flags_inherited
-		| ss->solver_flags;
-	unsigned short preferred_pinning, allowed_pinning;
-	unsigned int preferred_repos, allowed_repos;
-	unsigned short preference = 0;
-	int i, r;
-
-	preferred_pinning = ns->preferred_pinning ?: APK_DEFAULT_PINNING_MASK;
-	preferred_repos = get_pinning_mask_repos(ss->db, preferred_pinning);
-	allowed_pinning = ns->allowed_pinning | preferred_pinning;
-	if (preferred_pinning != allowed_pinning)
-		allowed_repos = get_pinning_mask_repos(ss->db, allowed_pinning);
-	else
-		allowed_repos = preferred_repos;
-
-	for (i = 0; i < name->pkgs->num; i++) {
-		struct apk_package *pkg0 = name->pkgs->item[i];
-		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
-
-		if (pkg0 == pkg || ps0 == NULL)
-			continue;
-
-		if (installable_only &&
-		    (ss->topology_position < pkg0->topology_hard ||
-		     ps0->locked))
-			continue;
-
-		r = compare_package_preference(name_flags,
-					       preferred_repos,
-					       allowed_repos,
-					       pkg, pkg0, ss->db);
-		if (r < 0)
-			preference += -r;
-	}
-
-	return preference;
-}
-
 static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg)
 {
 	struct apk_name_state *ns;
@@ -464,55 +560,116 @@ static int check_if_package_unavailable(struct apk_solver_state *ss, struct apk_
 	return ps->unavailable;
 }
 
+static void foreach_common_dependency(
+		struct apk_solver_state *ss, struct apk_name *name,
+		void (*cb)(struct apk_solver_state *ss, struct apk_name *common_dependency))
+{
+	struct apk_name *name0;
+	struct apk_name_state *ns0;
+	struct apk_package *pkg;
+	struct apk_package_state *ps;
+	struct apk_dependency *dep;
+	int i, j, first_found = -1, last_found = 0;
+
+	for (i = 0; i < name->pkgs->num; i++) {
+		pkg = name->pkgs->item[i];
+		ps = pkg_to_ps(pkg);
+		if (ps == NULL || ps->locked)
+			continue;
+		if (first_found == -1)
+			first_found = i;
+		for (j = 0; j < pkg->depends->num; j++) {
+			dep = &pkg->depends->item[j];
+			if (dep->optional)
+				continue;
+			name0 = dep->name;
+			ns0   = name_to_ns(name0);
+			if (ns0->merge_index == last_found)
+				ns0->merge_index = i + 1;
+		}
+		last_found = i + 1;
+	}
+	if (first_found == -1)
+		return;
+
+	pkg = name->pkgs->item[first_found];
+	for (j = 0; j < pkg->depends->num; j++) {
+		dep = &pkg->depends->item[j];
+		if (dep->optional)
+			continue;
+		name0 = dep->name;
+		ns0   = name_to_ns(name0);
+		if (ns0->merge_index == last_found)
+			cb(ss, name0);
+		ns0->merge_index = 0;
+	}
+}
+
+#if 0
+static void prepare_name(struct apk_solver_state *ss, struct apk_name *name)
+{
+	struct apk_name_state *ns = name_to_ns(name);
+	int i, j;
+
+	if (ns->prepared)
+		return;
+	ns->prepared = 1;
+
+	for (i = 0; i < name->pkgs->num; i++) {
+		struct apk_package *pkg = name->pkgs->item[i];
+		if (pkg_to_ps(pkg) == NULL)
+			continue;
+		for (j = 0; j < pkg->depends->num; j++) {
+			struct apk_dependency *dep = &pkg->depends->item[j];
+			prepare_name(ss, dep->name);
+		}
+	}
+}
+#endif
+
+static void get_unassigned_score(struct apk_name *name, struct apk_score *score)
+{
+	struct apk_name_state *ns = name_to_ns(name);
+
+	*score = (struct apk_score){
+		.conflicts = ns->requirers + ns->prerequires,
+		.preference = name->pkgs->num,
+	};
+}
+
 static int update_name_state(struct apk_solver_state *ss, struct apk_name *name)
 {
 	struct apk_name_state *ns = name_to_ns(name);
 	struct apk_package *best_pkg = NULL, *preferred_pkg = NULL;
-	struct apk_package_state *preferred_ps = NULL;
+	struct apk_score preferred_score;
 	unsigned int best_topology = 0;
-	unsigned short name_flags = ns->solver_flags_local
-		| ns->solver_flags_inherited
-		| ss->solver_flags;
-	unsigned short preferred_pinning, allowed_pinning;
-	unsigned int preferred_repos, allowed_repos;
 	int i, options = 0;
 
 	if (ns->locked)
 		return ns->chosen != NULL;
 
-	preferred_pinning = ns->preferred_pinning ?: APK_DEFAULT_PINNING_MASK;
-	preferred_repos = get_pinning_mask_repos(ss->db, preferred_pinning);
-	allowed_pinning = ns->allowed_pinning | preferred_pinning;
-	if (preferred_pinning != allowed_pinning)
-		allowed_repos = get_pinning_mask_repos(ss->db, allowed_pinning);
-	else
-		allowed_repos = preferred_repos;
-
 	subscore(&ss->minimum_penalty, &ns->minimum_penalty);
 	ns->minimum_penalty = (struct apk_score) { 0, 0 };
 
+	get_unassigned_score(name, &preferred_score);
 	for (i = 0; i < name->pkgs->num; i++) {
 		struct apk_package *pkg0 = name->pkgs->item[i];
 		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
+		struct apk_score pkg0_score;
 
-		if (ps0 == NULL ||
+		if (ps0 == NULL || ps0->locked ||
 		    ss->topology_position < pkg0->topology_hard ||
-		    ps0->locked ||
 		    check_if_package_unavailable(ss, pkg0, 0))
 			continue;
 
-		options++;
-
 		/* preferred - currently most optimal for end solution */
-		if ((preferred_pkg == NULL) ||
-		    (ps0->conflicts < preferred_ps->conflicts) ||
-		    (ps0->conflicts == preferred_ps->conflicts &&
-		     compare_package_preference(name_flags,
-						preferred_repos,
-						allowed_repos,
-						pkg0, preferred_pkg, ss->db) > 0)) {
+		/* FIXME: should not use absolute topology score */
+		get_topology_score(ss, ns, pkg0, 1, &pkg0_score);
+
+		if (preferred_pkg == NULL ||
+		    cmpscore(&pkg0_score, &preferred_score) < 0) {
 			preferred_pkg = pkg0;
-			preferred_ps = ps0;
+			preferred_score = pkg0_score;
 		}
 
 		/* next in topology order - next to get locked in */
@@ -521,47 +678,44 @@ static int update_name_state(struct apk_solver_state *ss, struct apk_name *name)
 			best_pkg = pkg0, best_topology = ps0->topology_soft;
 		else if (pkg0->topology_hard > best_topology)
 			best_pkg = pkg0, best_topology = pkg0->topology_hard;
+
+		options++;
 	}
 
-	if (ns->requirers == 0 && ns->install_ifs == 0) {
+	if (ns->prerequires == 0 && ns->requirers == 0 && ns->install_ifs == 0) {
+		/* No one really needs this name (anymore). */
 		if (list_hashed(&ns->unsolved_list)) {
 			list_del(&ns->unsolved_list);
 			list_init(&ns->unsolved_list);
-			ns->chosen = NULL;
-		}
-		dbg_printf("%s: deleted from unsolved: %d requirers, %d install_ifs, %d options\n",
-			   name->name, ns->requirers, ns->install_ifs, options);
-	} else {
-		if (!list_hashed(&ns->unsolved_list))
-			list_add(&ns->unsolved_list, &ss->unsolved_list_head);
-
-		ns->chosen = best_pkg;
-		if (preferred_pkg != NULL &&
-		    preferred_ps->conflicts < ns->requirers) {
-			ns->minimum_penalty = (struct apk_score) {
-				.unsatisfiable = preferred_ps->conflicts,
-				.preference = get_preference(ss, preferred_pkg, FALSE),
-			};
-			dbg_printf("%s: min.penalty for name {%d, %d} from pkg " PKG_VER_FMT "\n",
-				   name->name,
-				   ns->minimum_penalty.unsatisfiable,
-				   ns->minimum_penalty.preference,
-				   PKG_VER_PRINTF(preferred_pkg));
-		} else {
-			ns->minimum_penalty = (struct apk_score) {
-				.unsatisfiable = ns->requirers,
-				.preference = name->pkgs->num,
-			};
-			dbg_printf("%s: min.penalty for name {%d, %d} from no pkg\n",
-				   name->name,
-				   ns->minimum_penalty.unsatisfiable,
-				   ns->minimum_penalty.preference);
 		}
-		addscore(&ss->minimum_penalty, &ns->minimum_penalty);
+		ns->chosen = NULL;
+		dbg_printf("%s: not required\n", name->name);
+		return options + 1;
+	}
 
-		dbg_printf("%s: added to unsolved: %d requirers, %d install_ifs, %d options (next topology %d)\n",
-			   name->name, ns->requirers, ns->install_ifs,
-			   options, best_topology);
+	if (!list_hashed(&ns->unsolved_list))
+		list_add_tail(&ns->unsolved_list, &ss->unsolved_list_head);
+
+	/* So far decided that something will be installed for this
+	 * name. So assign the minimum penalty, and next position. */
+	ns->chosen = best_pkg;
+	ns->minimum_penalty = preferred_score;
+	addscore(&ss->minimum_penalty, &ns->minimum_penalty);
+
+	dbg_printf("%s:  min.pen. " SCORE_FMT ", %d prerequirers, %d requirers, %d install_ifs, %d options (next topology %d)\n",
+		   name->name,
+		   SCORE_PRINTF(&ns->minimum_penalty),
+		   ns->prerequires, ns->requirers, ns->install_ifs,
+		   options, best_topology);
+
+	if (!ns->none_excluded) {
+		dbg_printf("%s: none not excluded yet\n", name->name);
+		return options + 1;
+	}
+
+	if (options == 0) {
+		ss->impossible_constraints = 1;
+		dbg_printf("%s: impossible constraints\n", name->name);
 	}
 
 	return options;
@@ -593,70 +747,124 @@ static void untrigger_install_if(struct apk_solver_state *ss,
 	}
 }
 
+static void increment_prerequires(struct apk_solver_state *ss, struct apk_name *name)
+{
+	struct apk_name_state *ns = name_to_ns(name);
+	ns->prerequires++;
+	update_name_state(ss, name);
+}
+
+static void decrement_prerequires(struct apk_solver_state *ss, struct apk_name *name)
+{
+	struct apk_name_state *ns = name_to_ns(name);
+	ns->prerequires--;
+	update_name_state(ss, name);
+}
+
 static solver_result_t apply_decision(struct apk_solver_state *ss,
-				      struct apk_package *pkg,
-				      struct apk_package_state *ps)
+				      struct apk_decision *d)
 {
-	struct apk_name *name = pkg->name;
+	struct apk_name *name = decision_to_name(d);
 	struct apk_name_state *ns = name_to_ns(name);
-	unsigned short preference;
+	struct apk_package *pkg = decision_to_pkg(d);
+	struct apk_score score;
 
-	dbg_printf("-->apply_decision: " PKG_VER_FMT " %s\n", PKG_VER_PRINTF(pkg),
-		   (ps->flags & APK_PKGSTF_INSTALL) ? "INSTALL" : "NO_INSTALL");
-
-	if (ps->flags & APK_PKGSTF_INSTALL) {
-		subscore(&ss->minimum_penalty, &ns->minimum_penalty);
-		ns->minimum_penalty = (struct apk_score) { 0, 0 };
-
-		preference = get_preference(ss, pkg, FALSE);
-		ss->score.unsatisfiable += ps->conflicts;
-		ss->score.preference += preference;
-		if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) >= 0 ||
-		    check_if_package_unavailable(ss, pkg, 1)) {
-			dbg_printf("install causing {%d,%d}, penalty too big (or unavailable %d): {%d,%d}+{%d,%d}>={%d,%d}\n",
-				ps->conflicts, preference,
-				ss->score.unsatisfiable, ss->score.preference,
-				ss->minimum_penalty.unsatisfiable, ss->minimum_penalty.preference,
-				ss->best_score.unsatisfiable, ss->best_score.preference
-				);
-
-			ss->score.unsatisfiable -= ps->conflicts;
-			ss->score.preference -= preference;
-			return SOLVERR_PRUNED;
+	ss->impossible_constraints = 0;
+	if (pkg != NULL) {
+		struct apk_package_state *ps = pkg_to_ps(pkg);
+
+		dbg_printf("-->apply_decision: " PKG_VER_FMT " %s\n",
+			   PKG_VER_PRINTF(pkg),
+			   (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
+
+		ps->locked = 1;
+		ps->handle_install_if = 0;
+
+		if (d->topology_position) {
+			if (ps->topology_soft < ss->topology_position) {
+				if (d->type == DECISION_ASSIGN) {
+					ps->handle_install_if = 1;
+					dbg_printf("triggers due to " PKG_VER_FMT "\n",
+						   PKG_VER_PRINTF(pkg));
+				}
+				ss->topology_position = ps->topology_soft;
+			} else {
+				ss->topology_position = pkg->topology_hard;
+			}
 		}
 
-		ps->install_applied = 1;
-		ss->assigned_names++;
-		ns->chosen = pkg;
-		ns->locked = 1;
+		if (d->type == DECISION_ASSIGN) {
+			subscore(&ss->minimum_penalty, &ns->minimum_penalty);
+			ns->minimum_penalty = (struct apk_score) { 0 };
+
+			get_topology_score(ss, ns, pkg, 1, &score);
+			addscore(&ss->score, &score);
+
+			if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) >= 0 ||
+			    check_if_package_unavailable(ss, pkg, 1)) {
+				dbg_printf("install causing "SCORE_FMT", penalty too big: "SCORE_FMT"+"SCORE_FMT">="SCORE_FMT"\n",
+					   SCORE_PRINTF(&score),
+					   SCORE_PRINTF(&ss->score),
+					   SCORE_PRINTF(&ss->minimum_penalty),
+					   SCORE_PRINTF(&ss->best_score));
+
+				subscore(&ss->score, &score);
+				return SOLVERR_PRUNED;
+			}
+
+			ps->install_applied = 1;
+			ss->assigned_names++;
+			ns->chosen = pkg;
 
-		list_del(&ns->unsolved_list);
-		list_init(&ns->unsolved_list);
-		dbg_printf("%s: deleting from unsolved list\n",
-			   pkg->name->name);
+			ns->locked = 1;
+			list_del(&ns->unsolved_list);
+			list_init(&ns->unsolved_list);
 
-		foreach_dependency(ss, pkg->depends, apply_constraint);
-		foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
+			foreach_dependency(ss, pkg->depends, apply_constraint);
+			foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
+		}
 	} else {
-		if (update_name_state(ss, pkg->name) == 0) {
+		dbg_printf("-->apply_decision: %s %s NOTHING\n",
+			   name->name,
+			   (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
+
+		if (d->type == DECISION_ASSIGN) {
 			subscore(&ss->minimum_penalty, &ns->minimum_penalty);
-			ns->minimum_penalty = (struct apk_score) { 0, 0 };
+			ns->minimum_penalty = (struct apk_score) { 0 };
 
-			dbg_printf("%s: out of candidates, locking to none\n",
-				   pkg->name->name);
+			get_unassigned_score(name, &score);
+			addscore(&ss->score, &score);
 
-			ss->score.unsatisfiable += ns->requirers;
-			ss->score.preference += name->pkgs->num;
+			ns->chosen = NULL;
 			ns->locked = 1;
+			list_del(&ns->unsolved_list);
+			list_init(&ns->unsolved_list);
+		} else {
+			ns->none_excluded = 1;
+		}
+	}
+
+	if (ss->impossible_constraints)
+		return SOLVERR_PRUNED;
+
+	if (d->type == DECISION_EXCLUDE) {
+		foreach_common_dependency(ss, name, increment_prerequires);
+
+		if (update_name_state(ss, name) == 0) {
+			dbg_printf("%s: %s would prune name to empty\n",
+				name->name,
+				(d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
+			return SOLVERR_PRUNED;
 		}
 	}
 
 	if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) >= 0) {
-		dbg_printf("install/uninstall finished penalty too big: {%d,%d}+{%d,%d}>={%d,%d}\n",
-			ss->score.unsatisfiable, ss->score.preference,
-			ss->minimum_penalty.unsatisfiable, ss->minimum_penalty.preference,
-			ss->best_score.unsatisfiable, ss->best_score.preference
-			);
+		dbg_printf("%s: %s penalty too big: "SCORE_FMT"+"SCORE_FMT">="SCORE_FMT"\n",
+			name->name,
+			(d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE",
+			SCORE_PRINTF(&ss->score),
+			SCORE_PRINTF(&ss->minimum_penalty),
+			SCORE_PRINTF(&ss->best_score));
 		return SOLVERR_PRUNED;
 	}
 
@@ -664,106 +872,113 @@ static solver_result_t apply_decision(struct apk_solver_state *ss,
 }
 
 static void undo_decision(struct apk_solver_state *ss,
-			  struct apk_package *pkg,
-			  struct apk_package_state *ps)
+			  struct apk_decision *d)
 {
-	struct apk_name *name = pkg->name;
+	struct apk_name *name = decision_to_name(d);
 	struct apk_name_state *ns = name_to_ns(name);
+	struct apk_package *pkg = decision_to_pkg(d);
+	struct apk_score score;
 
-	dbg_printf("-->undo_decision: " PKG_VER_FMT " %s\n", PKG_VER_PRINTF(pkg),
-		   (ps->flags & APK_PKGSTF_INSTALL) ? "INSTALL" : "NO_INSTALL");
+	if (d->type == DECISION_EXCLUDE) {
+		foreach_common_dependency(ss, name, decrement_prerequires);
+	}
 
-	if (ps->handle_install_if)
-		ss->topology_position = ps->topology_soft;
-	else
-		ss->topology_position = pkg->topology_hard;
+	if (pkg != NULL) {
+		struct apk_package_state *ps = pkg_to_ps(pkg);
 
-	if (ps->flags & APK_PKGSTF_INSTALL) {
-		if (ps->install_applied) {
-			unsigned short preference;
+		dbg_printf("-->undo_decision: " PKG_VER_FMT " %s\n",
+			   PKG_VER_PRINTF(pkg),
+			   (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
+
+		if (d->topology_position) {
+			if (ps->handle_install_if)
+				ss->topology_position = ps->topology_soft;
+			else
+				ss->topology_position = pkg->topology_hard;
+		}
 
+		if (ps->install_applied) {
 			ps->install_applied = 0;
 			ss->assigned_names--;
 			foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
 			foreach_dependency(ss, pkg->depends, undo_constraint);
 
-			preference = get_preference(ss, pkg, FALSE);
-			ss->score.unsatisfiable -= ps->conflicts;
-			ss->score.preference -= preference;
+			get_topology_score(ss, ns, pkg, 1, &score);
+			subscore(&ss->score, &score);
 		}
+		ps->locked = 0;
 	} else {
-		if (ns->locked) {
-			/* UNINSTALL decision removed - either name is unlocked
-			 * or locked to none */
-			ss->score.unsatisfiable -= ns->requirers;
-			ss->score.preference -= name->pkgs->num;
+		dbg_printf("-->undo_decision: %s %s NOTHING\n",
+			   name->name,
+			   (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
+
+		if (d->type == DECISION_ASSIGN) {
+			get_unassigned_score(name, &score);
+			subscore(&ss->score, &score);
+		} else {
+			ns->none_excluded = 0;
 		}
 	}
+
 	ns->locked = 0;
 	ns->chosen = NULL;
 
-	update_name_state(ss, pkg->name);
+	update_name_state(ss, name);
 }
 
-static solver_result_t push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
-				     int flags)
+static solver_result_t push_decision(struct apk_solver_state *ss,
+				     struct apk_name *name,
+				     struct apk_package *pkg,
+				     int primary_decision,
+				     int branching_point,
+				     int topology_position)
 {
-	struct apk_package_state *ps = pkg_to_ps(pkg);
+	struct apk_decision *d;
 
-	ps->backtrack = ss->latest_decision;
-	ps->flags = flags;
-	ps->locked = 1;
-	ps->handle_install_if = 0;
+	ASSERT(ss->num_decisions <= ss->max_decisions,
+	       "Decision tree overflow.\n");
 
-	if (ps->topology_soft < ss->topology_position) {
-		if (flags & APK_PKGSTF_INSTALL)
-			ps->handle_install_if = 1;
-		ss->topology_position = ps->topology_soft;
+	ss->num_decisions++;
+	d = &ss->decisions[ss->num_decisions];
+
+#ifdef DEBUG_CHECKS
+	d->saved_score = ss->score;
+#endif
+	d->type = primary_decision;
+	d->branching_point = branching_point;
+	d->topology_position = topology_position;
+	if (pkg == NULL) {
+		d->name = name;
+		d->no_package = 1;
 	} else {
-		ss->topology_position = pkg->topology_hard;
+		d->pkg = pkg;
+		d->no_package = 0;
 	}
-	ss->latest_decision = pkg;
-
-	dbg_printf("-->push_decision: adding new BRANCH at topology_position %d (score: unsatisfied %d, preference %d)\n",
-		   ss->topology_position,
-		   ss->score.unsatisfiable,
-		   ss->score.preference);
 
-	if (ps->handle_install_if)
-		dbg_printf("triggers due to " PKG_VER_FMT "\n",
-			   PKG_VER_PRINTF(pkg));
-
-	return apply_decision(ss, pkg, ps);
+	return apply_decision(ss, d);
 }
 
 static int next_branch(struct apk_solver_state *ss)
 {
-	struct apk_package *pkg;
-	struct apk_package_state *ps;
-
-	while (ss->latest_decision != NULL) {
-		pkg = ss->latest_decision;
-		ps = pkg_to_ps(pkg);
+	while (ss->num_decisions > 0) {
+		struct apk_decision *d = &ss->decisions[ss->num_decisions];
 
-		if (ps->flags & APK_PKGSTF_ALT_BRANCH) {
-			dbg_printf("-->next_branch: undo decision at topology_position %d\n",
-				   ss->topology_position);
-			ps->flags &= ~APK_PKGSTF_ALT_BRANCH;
-			ps->locked = 0;
-			undo_decision(ss, pkg, ps);
-
-			ss->latest_decision = ps->backtrack;
-		} else {
-			dbg_printf("-->next_branch: swapping BRANCH at topology_position %d\n",
-				   ss->topology_position);
+		undo_decision(ss, d);
 
-			undo_decision(ss, pkg, ps);
-
-			ps->flags |= APK_PKGSTF_ALT_BRANCH;
-			ps->flags ^= APK_PKGSTF_INSTALL;
+#ifdef DEBUG_CHECKS
+		ASSERT(cmpscore(&d->saved_score, &ss->score) == 0,
+			"ERROR! saved_score "SCORE_FMT" != score "SCORE_FMT"\n",
+			SCORE_PRINTF(&d->saved_score),
+			SCORE_PRINTF(&ss->score));
+#endif
 
-			return apply_decision(ss, pkg, ps);
+		if (d->branching_point == BRANCH_YES) {
+			d->branching_point = BRANCH_NO;
+			d->type = (d->type == DECISION_ASSIGN) ? DECISION_EXCLUDE : DECISION_ASSIGN;
+			return apply_decision(ss, d);
 		}
+
+		ss->num_decisions--;
 	}
 
 	dbg_printf("-->next_branch: no more branches\n");
@@ -824,12 +1039,12 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
 			dbg_printf("%s: locked to empty\n",
 				   name->name);
 		if (!apk_dep_is_satisfied(dep, ns->chosen))
-			ss->score.unsatisfiable++;
+			ss->score.conflicts++;
 		return;
 	}
 	if (name->pkgs->num == 0) {
 		if (!dep->optional)
-			ss->score.unsatisfiable++;
+			ss->score.conflicts++;
 		return;
 	}
 
@@ -840,18 +1055,19 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
 		ns->allowed_pinning |= BIT(dep->repository_tag);
 	}
 
-	if (ss->latest_decision != NULL) {
+	if (ss->num_decisions > 0) {
+		struct apk_name *name0 = decision_to_name(&ss->decisions[ss->num_decisions]);
 		dbg_printf("%s: inheriting flags and pinning from %s\n",
-			   name->name, ss->latest_decision->name->name);
-		inherit_name_state(name, ss->latest_decision->name);
+			   name->name, name0->name);
+		inherit_name_state(name, name0);
 	}
 
 	for (i = 0; i < name->pkgs->num; i++) {
 		struct apk_package *pkg0 = name->pkgs->item[i];
 		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
 
-		if (ps0 == NULL ||
-		    pkg0->topology_hard >= ss->topology_position)
+		if (ps0 == NULL || ps0->locked ||
+		    ss->topology_position < pkg0->topology_hard)
 			continue;
 
 		if (!apk_dep_is_satisfied(dep, pkg0)) {
@@ -863,7 +1079,7 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
 	}
 
 	if (!dep->optional)
-		ns->requirers++;
+		ns->requirers++; 
 
 	update_name_state(ss, name);
 }
@@ -883,12 +1099,12 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
 				   name->name);
 		}
 		if (!apk_dep_is_satisfied(dep, ns->chosen))
-			ss->score.unsatisfiable--;
+			ss->score.conflicts--;
 		return;
 	}
 	if (name->pkgs->num == 0) {
 		if (!dep->optional)
-			ss->score.unsatisfiable--;
+			ss->score.conflicts--;
 		return;
 	}
 
@@ -896,7 +1112,8 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
 		struct apk_package *pkg0 = name->pkgs->item[i];
 		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
 
-		if (pkg0->topology_hard >= ss->topology_position)
+		if (ps0 == NULL || ps0->locked ||
+		    ss->topology_position < pkg0->topology_hard)
 			continue;
 
 		if (!apk_dep_is_satisfied(dep, pkg0)) {
@@ -907,7 +1124,8 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
 		}
 	}
 
-	if (ss->latest_decision && has_inherited_state(ss->latest_decision->name))
+	if (ss->num_decisions > 0 &&
+	    has_inherited_state(decision_to_name(&ss->decisions[ss->num_decisions])))
 		recalculate_inherted_name_state(name);
 
 	if (!dep->optional)
@@ -918,54 +1136,110 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
 
 static int expand_branch(struct apk_solver_state *ss)
 {
+	struct apk_name *name;
 	struct apk_name_state *ns;
 	struct apk_package *pkg0 = NULL;
-	unsigned int topology0 = 0;
+	unsigned int i, topology0 = 0;
 	unsigned short allowed_pinning, preferred_pinning;
 	unsigned int allowed_repos;
-	int flags;
+	int primary_decision, branching_point;
 
 	/* FIXME: change unsolved_list to a priority queue */
 	list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
-		if (ns->chosen == NULL)
-			continue;
+		struct apk_score score;
+		struct apk_score pkgscore;
+
+		name = ns->name;
+
+		/* no options left */
+		if (ns->chosen == NULL) {
+			if (ns->none_excluded)
+				return SOLVERR_PRUNED;
+			return push_decision(ss, name, NULL, DECISION_ASSIGN, BRANCH_NO, FALSE);
+		}
+
 		if (pkg_to_ps(ns->chosen)->topology_soft < ss->topology_position &&
 		    pkg_to_ps(ns->chosen)->topology_soft > topology0)
 			pkg0 = ns->chosen, topology0 = pkg_to_ps(pkg0)->topology_soft;
 		else if (ns->chosen->topology_hard > topology0)
 			pkg0 = ns->chosen, topology0 = pkg0->topology_hard;
+
+		score = ss->score;
+		subscore(&score, &ns->minimum_penalty);
+
+		if (!ns->none_excluded) {
+			get_unassigned_score(name, &pkgscore);
+			if (cmpscore2(&score, &pkgscore, &ss->best_score) >= 0)
+				return push_decision(ss, name, NULL, DECISION_EXCLUDE, BRANCH_NO, FALSE);
+		}
+
+		for (i = 0; i < name->pkgs->num; i++) {
+			struct apk_package *pkg0 = name->pkgs->item[i];
+			struct apk_package_state *ps0 = pkg_to_ps(pkg0);
+
+			if (ps0 == NULL || ps0->locked ||
+			    ss->topology_position < pkg0->topology_hard)
+				continue;
+
+			get_topology_score(ss, ns, pkg0, 0, &pkgscore);
+			if (cmpscore2(&score, &pkgscore, &ss->best_score) >= 0)
+				return push_decision(ss, name, pkg0, DECISION_EXCLUDE, BRANCH_NO, FALSE);
+		}
+
 	}
 	if (pkg0 == NULL) {
-		dbg_printf("expand_branch: list is empty (%d unsatisfied)\n",
-			   ss->score.unsatisfiable);
+		dbg_printf("expand_branch: solution with score "SCORE_FMT"\n",
+			   SCORE_PRINTF(&ss->score));
 		return SOLVERR_SOLUTION;
 	}
 
 	/* someone needs to provide this name -- find next eligible
 	 * provider candidate */
-	ns = name_to_ns(pkg0->name);
-	dbg_printf("expand_branch: %s\n", pkg0->name->name);
+	name = pkg0->name;
+	ns = name_to_ns(name);
+	dbg_printf("expand_branch: %-30s score: "SCORE_FMT"\tminpenalty: "SCORE_FMT"\tbest: "SCORE_FMT"\n",
+		pkg0->name->name,
+		SCORE_PRINTF(&ss->score),
+		SCORE_PRINTF(&ss->minimum_penalty),
+		SCORE_PRINTF(&ss->best_score));
+
+	if (!ns->none_excluded) {
+		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
+		if (ps0->conflicts > ns->requirers)
+			primary_decision = DECISION_ASSIGN;
+		else
+			primary_decision = DECISION_EXCLUDE;
+		return push_decision(ss, name, NULL, primary_decision, BRANCH_YES, FALSE);
+	}
 
 	preferred_pinning = ns->preferred_pinning ?: APK_DEFAULT_PINNING_MASK;
 	allowed_pinning = ns->allowed_pinning | preferred_pinning;
 	allowed_repos = get_pinning_mask_repos(ss->db, allowed_pinning);
 
-	if ((pkg0->repos != 0) && (pkg0->ipkg == NULL) &&
-	    (pkg0->filename == NULL) && !(pkg0->repos & allowed_repos)) {
+	if ((pkg0->repos != 0) && !(pkg0->repos & allowed_repos)) {
 		/* pinning has not enabled the package */
-		flags = APK_PKGSTF_NOINSTALL | APK_PKGSTF_ALT_BRANCH;
+		primary_decision = DECISION_EXCLUDE;
+		/* but if it is installed, we might consider it */
+		if ((pkg0->ipkg == NULL) && (pkg0->filename == NULL))
+			branching_point = BRANCH_NO;
+		else
+			branching_point = BRANCH_YES;
 	} else if (ns->requirers == 0 && ns->install_ifs != 0 &&
 		   install_if_missing(ss, pkg0)) {
 		/* not directly required, and package specific
 		 * install_if never triggered */
-		flags = APK_PKGSTF_NOINSTALL | APK_PKGSTF_ALT_BRANCH;
-	} else if (get_preference(ss, pkg0, TRUE) == 0) {
-		flags = APK_PKGSTF_INSTALL;
+		primary_decision = DECISION_EXCLUDE;
+		branching_point = BRANCH_NO;
+	} else if (is_topology_optimum(ss, pkg0)) {
+		primary_decision = DECISION_ASSIGN;
+		branching_point = BRANCH_YES;
 	} else {
-		flags = APK_PKGSTF_NOINSTALL;
+		primary_decision = DECISION_EXCLUDE;
+		branching_point = BRANCH_YES;
 	}
 
-	return push_decision(ss, pkg0, flags);
+	return push_decision(ss, pkg0->name, pkg0,
+			     primary_decision, branching_point, TRUE);
 }
 
 static int get_tag(struct apk_database *db, unsigned short pinning_mask, unsigned int repos)
@@ -984,43 +1258,44 @@ static int get_tag(struct apk_database *db, unsigned short pinning_mask, unsigne
 static void record_solution(struct apk_solver_state *ss)
 {
 	struct apk_database *db = ss->db;
-	struct apk_package *pkg;
-	struct apk_package_state *ps;
 	struct apk_name_state *ns;
-	int i;
+	int i, n;
 
 	apk_solution_array_resize(&ss->best_solution, ss->assigned_names);
 
-	i = 0;
-	pkg = ss->latest_decision;
-	while (pkg != NULL) {
-		ps = pkg_to_ps(pkg);
-		ns = name_to_ns(pkg->name);
-		if (ps->flags & APK_PKGSTF_INSTALL) {
-			unsigned short pinning;
-			unsigned int repos;
-
-			if (i >= ss->assigned_names)
-				abort();
-
-			pinning = ns->allowed_pinning | ns->preferred_pinning | APK_DEFAULT_PINNING_MASK;
-			repos = pkg->repos | (pkg->ipkg ? db->repo_tags[pkg->ipkg->repository_tag].allowed_repos : 0);
-
-			ss->best_solution->item[i++] = (struct apk_solution_entry){
-				.pkg = pkg,
-				.reinstall = !!((ns->solver_flags_local | ns->solver_flags_inherited |
-					         ss->solver_flags) & APK_SOLVERF_REINSTALL),
-				.repository_tag = get_tag(db, pinning, repos),
-			};
+	n = 0;
+	for (i = ss->num_decisions; i > 0; i--) {
+		struct apk_decision *d = &ss->decisions[i];
+		struct apk_package *pkg = decision_to_pkg(d);
+		unsigned short pinning;
+		unsigned int repos;
+
+		if (pkg == NULL) {
+			dbg_printf("record_solution: %s: NOTHING\n",
+				   decision_to_name(d)->name);
+			continue;
 		}
 
-		dbg_printf("record_solution: " PKG_VER_FMT ": %sINSTALL\n",
+		dbg_printf("record_solution: " PKG_VER_FMT ": %s\n",
 			   PKG_VER_PRINTF(pkg),
-			   (ps->flags & APK_PKGSTF_INSTALL) ? "" : "NO_");
+			   d->type == DECISION_ASSIGN ? "INSTALL" : "no install");
 
-		pkg = ps->backtrack;
+		if (d->type != DECISION_ASSIGN)
+			continue;
+
+		ns = name_to_ns(pkg->name);
+		pinning = ns->allowed_pinning | ns->preferred_pinning | APK_DEFAULT_PINNING_MASK;
+		repos = pkg->repos | (pkg->ipkg ? db->repo_tags[pkg->ipkg->repository_tag].allowed_repos : 0);
+
+		ASSERT(n < ss->assigned_names, "Name assignment overflow\n");
+		ss->best_solution->item[n++] = (struct apk_solution_entry){
+			.pkg = pkg,
+			.reinstall = !!((ns->solver_flags_local | ns->solver_flags_inherited |
+					 ss->solver_flags) & APK_SOLVERF_REINSTALL),
+			.repository_tag = get_tag(db, pinning, repos),
+		};
 	}
-	apk_solution_array_resize(&ss->best_solution, i);
+	apk_solution_array_resize(&ss->best_solution, n);
 }
 
 static int compare_solution_entry(const void *p1, const void *p2)
@@ -1125,9 +1400,10 @@ static int generate_changeset(struct apk_database *db,
 static int free_state(apk_hash_item item, void *ctx)
 {
 	struct apk_name *name = (struct apk_name *) item;
+	struct apk_name_state *ns = (struct apk_name_state *) name->state_ptr;
 
-	if (name->state_ptr != NULL) {
-		free(name->state_ptr);
+	if (ns != NULL) {
+		free(ns);
 		name->state_ptr = NULL;
 	}
 	return 0;
@@ -1167,7 +1443,6 @@ int apk_solver_solve(struct apk_database *db,
 {
 	struct apk_solver_state *ss;
 	struct apk_installed_package *ipkg;
-	struct apk_score zero_score;
 	solver_result_t r = SOLVERR_STOP;
 	int i;
 
@@ -1175,20 +1450,30 @@ int apk_solver_solve(struct apk_database *db,
 	ss->db = db;
 	ss->solver_flags = solver_flags;
 	ss->topology_position = -1;
-	ss->best_score = (struct apk_score){ .unsatisfiable = -1, .preference = -1 };
+	ss->best_score = (struct apk_score){
+		.conflicts = -1,
+		.non_preferred_actions = -1,
+		.preference = -1,
+	};
 	list_init(&ss->unsolved_list_head);
 
 	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)
+	list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
 		sort_name(ss, ipkg->pkg->name);
+		name_to_ns(ipkg->pkg->name)->originally_installed = 1;
+	}
+#if 0
+	for (i = 0; i < world->num; i++)
+		prepare_name(ss, world->item[i].name);
+	list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list)
+		prepare_name(ss, ipkg->pkg->name);
+#endif
 
-	foreach_dependency(ss, world, apply_constraint);
-	zero_score = ss->score;
+	ss->max_decisions ++;
+	ss->decisions = calloc(1, sizeof(struct apk_decision[ss->max_decisions]));
 
-	dbg_printf("solver_solve: zero score: %d unsatisfiable, %d preference\n",
-		   zero_score.unsatisfiable,
-		   zero_score.preference);
+	foreach_dependency(ss, world, apply_constraint);
 
 	do {
 		/* need EXPAND if here, can return SOLUTION|PRUNED|EXPAND */
@@ -1196,24 +1481,18 @@ int apk_solver_solve(struct apk_database *db,
 		if (r == SOLVERR_SOLUTION) {
 			struct apk_score score;
 
-			dbg_printf("solution with: %d unsatisfiable, %d preference\n",
-				   ss->score.unsatisfiable,
-				   ss->score.preference);
-
 			score = ss->score;
 			addscore(&score, &ss->minimum_penalty);
 
 			if (cmpscore(&score, &ss->best_score) < 0) {
+				dbg_printf("updating best score "SCORE_FMT" (was: "SCORE_FMT")\n",
+					SCORE_PRINTF(&score),
+					SCORE_PRINTF(&ss->best_score));
+
 				record_solution(ss);
 				ss->best_score = score;
 			}
 
-			if (cmpscore(&zero_score, &score) >= 0) {
-				/* found solution - it is optimal because we permutate
-				 * each preferred local option first, and permutations
-				 * happen in topologally sorted order. */
-				break;
-			}
 			r = SOLVERR_PRUNED;
 		}
 		/* next_branch() returns PRUNED, STOP or EXPAND */
@@ -1223,6 +1502,10 @@ int apk_solver_solve(struct apk_database *db,
 	} while (r != SOLVERR_STOP);
 
 	/* collect packages */
+	dbg_printf("finished. best score "SCORE_FMT". solution has %d packages.\n",
+		SCORE_PRINTF(&ss->best_score),
+		ss->best_solution->num);
+
 	if (changeset != NULL) {
 		generate_changeset(db, ss->best_solution, changeset,
 				   ss->solver_flags);
@@ -1234,8 +1517,9 @@ int apk_solver_solve(struct apk_database *db,
 	} else {
 		apk_solution_array_free(&ss->best_solution);
 	}
-	i = ss->best_score.unsatisfiable;
+	i = ss->best_score.conflicts;
 	apk_solver_free(db);
+	free(ss->decisions);
 	free(ss);
 
 	return i;