solver: calculate branch minimum penalty early

Previously we would cache the penalty when evaluating the final
solution, and adding that until we backtrack to first topology
position changing that penalty. However, we can just keep track
of minimum penalty based on name state, and add it. This allows
us to bail out early on bad branches because we know in advance
how things will turn out.

2 files changed, 99 insertions, 56 deletions

diff --git a/src/solver.c b/src/solver.c
index 9231fd9..5f1c635 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -46,6 +46,7 @@ struct apk_name_state {
 	struct list_head unsolved_list;
 	struct apk_name *name;
 	struct apk_package *chosen;
+	struct apk_score minimum_penalty;
 	unsigned int topology_last_touched;
 	unsigned int allowed_repos, preferred_repos;
 	unsigned short requirers;
@@ -67,10 +68,9 @@ struct apk_solver_state {
 	struct list_head unsolved_list_head;
 	struct apk_package *latest_decision;
 	unsigned int topology_position;
-	unsigned int penalty_topology;
 	unsigned int assigned_names;
 	struct apk_score score;
-	struct apk_score penalty_score;
+	struct apk_score minimum_penalty;
 
 	unsigned int solver_flags : 4;
 	unsigned int refresh_name_states : 1;
@@ -84,6 +84,44 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
 static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
 			  int flags);
 
+static void addscore(struct apk_score *a, struct apk_score *b)
+{
+	a->unsatisfiable += b->unsatisfiable;
+	a->preference += b->preference;
+}
+
+static void subscore(struct apk_score *a, struct apk_score *b)
+{
+	a->unsatisfiable -= b->unsatisfiable;
+	a->preference -= b->preference;
+}
+
+static int cmpscore(struct apk_score *a, struct apk_score *b)
+{
+	if (a->unsatisfiable < b->unsatisfiable)
+		return -1;
+	if (a->unsatisfiable > b->unsatisfiable)
+		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;
+}
+
 static struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
 {
 	return (struct apk_package_state*) pkg->state_ptr;
@@ -327,6 +365,12 @@ static int compare_package_preference(unsigned short solver_flags,
 		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);
 }
@@ -388,11 +432,19 @@ static int install_if_missing(struct apk_solver_state *ss, struct apk_package *p
 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;
+	struct apk_package *best_pkg = NULL, *preferred_pkg = NULL;
+	struct apk_package_state *preferred_ps = NULL;
 	unsigned int best_topology = 0;
 	unsigned int allowed_repos = ns->allowed_repos | ss->db->repo_tags[0].allowed_repos;
+	unsigned int preferred_repos = ns->preferred_repos;
+	unsigned short name_flags = ns->solver_flags_local
+		| ns->solver_flags_inherited
+		| ss->solver_flags;
 	int i, options = 0, skipped_options = 0;
 
+	subscore(&ss->minimum_penalty, &ns->minimum_penalty);
+	ns->minimum_penalty = (struct apk_score) { 0, 0 };
+
 	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);
@@ -408,6 +460,16 @@ static int update_name_state(struct apk_solver_state *ss, struct apk_name *name)
 			continue;
 		}
 
+		if ((preferred_pkg == NULL) ||
+		    (ps0->conflicts < preferred_ps->conflicts) ||
+		    (ps0->conflicts == preferred_ps->conflicts &&
+		     compare_package_preference(name_flags,
+					        preferred_repos,
+					        pkg0, preferred_pkg) > 0)) {
+			preferred_pkg = pkg0;
+			preferred_ps = ps0;
+		}
+
 		if (ns->requirers == 0 && ns->install_ifs != 0 &&
 		    install_if_missing(ss, pkg0)) {
 			skipped_options++;
@@ -447,8 +509,22 @@ static int update_name_state(struct apk_solver_state *ss, struct apk_name *name)
 			   best_topology);
 		if (!list_hashed(&ns->unsolved_list))
 			list_add(&ns->unsolved_list, &ss->unsolved_list_head);
-		if (!ns->locked)
+		if (!ns->locked) {
 			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),
+				};
+			} else {
+				ns->minimum_penalty = (struct apk_score) {
+					.unsatisfiable = ns->requirers,
+					.preference = name->pkgs->num,
+				};
+			}
+			addscore(&ss->minimum_penalty, &ns->minimum_penalty);
+		}
 	}
 
 	return options + skipped_options;
@@ -557,8 +633,10 @@ static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
 	}
 	ss->latest_decision = pkg;
 
-	dbg_printf("push_decision: adding new BRANCH at topology_position %d\n",
-		   ss->topology_position);
+	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->flags & APK_PKGSTF_INSTALLIF)
 		dbg_printf("triggers due to " PKG_VER_FMT "\n",
@@ -585,11 +663,11 @@ static int next_branch(struct apk_solver_state *ss)
 			ss->latest_decision = ps->backtrack;
 			ss->refresh_name_states = 1;
 		} else {
+			undo_decision(ss, pkg, ps);
+
 			dbg_printf("next_branch: swapping BRANCH at topology_position %d\n",
 				   ss->topology_position);
 
-			undo_decision(ss, pkg, ps);
-
 			ps->flags |= APK_PKGSTF_ALT_BRANCH;
 			ps->flags ^= APK_PKGSTF_INSTALL;
 
@@ -765,26 +843,17 @@ static int expand_branch(struct apk_solver_state *ss)
 	}
 	ss->refresh_name_states = 0;
 	if (pkg0 == NULL) {
-		struct apk_score penalty_score = {0,0};
-		int penalty_topology = 0;
-
 		list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
-			if (!ns->locked) {
-				penalty_score.unsatisfiable += ns->requirers;
-				penalty_score.preference += ns->name->pkgs->num;
-				if (penalty_topology < ns->topology_last_touched)
-					penalty_topology = ns->topology_last_touched;
-			}
-		}
-		if (ss->penalty_topology < penalty_topology) {
-			ss->penalty_topology = penalty_topology;
-			ss->penalty_score = penalty_score;
+			if (ns->locked)
+				continue;
+
+			ss->score.unsatisfiable += ns->requirers;
+			ss->score.preference += ns->name->pkgs->num;
 		}
-		ss->score.unsatisfiable += penalty_score.unsatisfiable;
-		ss->score.preference    += penalty_score.preference;
 
 		dbg_printf("expand_branch: list is empty (%d unsatisfied)\n",
 			   ss->score.unsatisfiable);
+
 		return 1;
 	}
 
@@ -963,32 +1032,6 @@ static void apk_solver_free(struct apk_database *db)
 	apk_hash_foreach(&db->available.packages, free_package, NULL);
 }
 
-static int cmpscore(struct apk_score *a, struct apk_score *b)
-{
-	if (a->unsatisfiable < b->unsatisfiable)
-		return -1;
-	if (a->unsatisfiable > b->unsatisfiable)
-		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;
-}
-
 int apk_solver_solve(struct apk_database *db,
 		     unsigned short solver_flags,
 		     struct apk_dependency_array *world,
@@ -1015,13 +1058,12 @@ int apk_solver_solve(struct apk_database *db,
 	foreach_dependency(ss, world, apply_constraint);
 	zero_score = ss->score;
 
-	do {
-		if (ss->topology_position <= ss->penalty_topology) {
-			ss->penalty_score = zero_score;
-			ss->penalty_topology = 0;
-		}
+	dbg_printf("solver_solve: zero score: %d unsatisfiable, %d preference\n",
+		   zero_score.unsatisfiable,
+		   zero_score.preference);
 
-		if (cmpscore2(&ss->score, &ss->penalty_score, &ss->best_score) < 0) {
+	do {
+		if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) < 0) {
 			r = expand_branch(ss);
 			if (r) {
 				dbg_printf("solution with: %d unsatisfiable, %d preference\n",
diff --git a/test/error2.expect b/test/error2.expect
index 7faac5e..65d0093 100644
--- a/test/error2.expect
+++ b/test/error2.expect
@@ -1,2 +1,3 @@
-1 unsatisfiable dependencies (solution with 4 names)
+2 unsatisfiable dependencies (solution with 4 names)
 world: d<1.5
+b-1: d<2.0