From dec409c6d4f07b1d25fb8bd98fb1318f6c442f8c Mon Sep 17 00:00:00 2001
From: Timo Teräs <timo.teras@iki.fi>
Date: Fri, 5 Oct 2012 17:26:53 +0300
Subject: solver: fix back jumping once more

---
 src/solver.c | 50 +++++++++++++++++++++++++++++++++-----------------
 1 file changed, 33 insertions(+), 17 deletions(-)

(limited to 'src/solver.c')

diff --git a/src/solver.c b/src/solver.c
index 1f70fae..ac3200f 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -72,13 +72,17 @@ enum {
 
 struct apk_decision {
 	struct apk_name *name;
-	struct apk_package *pkg;
+	union {
+		struct apk_package *pkg;
+		unsigned backup_until;
+	};
 #ifdef DEBUG_CHECKS
 	struct apk_score saved_score;
 	unsigned short saved_requirers;
 #endif
 
 	unsigned type : 1;
+	unsigned has_package : 1;
 	unsigned branching_point : 1;
 	unsigned topology_position : 1;
 	unsigned found_solution : 1;
@@ -204,6 +208,11 @@ static struct apk_package_state *pkg_to_ps_alloc(struct apk_package *pkg)
 	return pkg_to_ps(pkg);
 }
 
+static inline struct apk_package *decision_to_pkg(struct apk_decision *d)
+{
+	return d->has_package ? d->pkg : NULL;
+}
+
 static inline int pkg_available(struct apk_database *db, struct apk_package *pkg)
 {
 	/* virtual packages - only deps used; no real .apk */
@@ -721,7 +730,7 @@ static solver_result_t apply_decision(struct apk_solver_state *ss,
 				      struct apk_decision *d)
 {
 	struct apk_name *name = d->name;
-	struct apk_package *pkg = d->pkg;
+	struct apk_package *pkg = decision_to_pkg(d);
 	struct apk_score score;
 	int i;
 
@@ -811,7 +820,7 @@ static void undo_decision(struct apk_solver_state *ss,
 			  struct apk_decision *d)
 {
 	struct apk_name *name = d->name;
-	struct apk_package *pkg = d->pkg;
+	struct apk_package *pkg = decision_to_pkg(d);
 	struct apk_score score;
 	int i;
 
@@ -894,7 +903,13 @@ static solver_result_t push_decision(struct apk_solver_state *ss,
 	d->topology_position = topology_position;
 	d->found_solution = 0;
 	d->name = name;
-	d->pkg = pkg;
+	if (pkg) {
+		d->has_package = 1;
+		d->pkg = pkg;
+	} else {
+		d->has_package = 0;
+		d->backup_until = name->ss.last_touched_decision;
+	}
 
 	return apply_decision(ss, d);
 }
@@ -930,9 +945,11 @@ static int next_branch(struct apk_solver_state *ss)
 					name->name, backup_until, ss->num_decisions);
 		}
 
-		if (d->pkg == NULL && !d->found_solution) {
-			if (name->ss.last_touched_decision < backup_until)
-				backup_until = name->ss.last_touched_decision;
+		/* When undoing the initial "exclude none" decision, check if
+		 * we can backjump. */
+		if (d->has_package == 0 && !d->found_solution) {
+			if (d->backup_until && backup_until > d->backup_until)
+				backup_until = d->backup_until;
 		}
 
 		ss->num_decisions--;
@@ -950,7 +967,7 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
 
 	if (ss->num_decisions > 0) {
 		requirer_name = ss->decisions[ss->num_decisions].name;
-		requirer_pkg  = ss->decisions[ss->num_decisions].pkg;
+		requirer_pkg  = decision_to_pkg(&ss->decisions[ss->num_decisions]);
 		/* FIXME: should probably take into account the requirer
 		 * package's provided name's 'requirer strength' */
 		strength = requirer_name->ss.requirers ?: 1;
@@ -1010,7 +1027,7 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
 		}
 	}
 
-	if (changed)
+	if (name->ss.last_touched_decision == 0 || changed)
 		name->ss.last_touched_decision = ss->num_decisions;
 
 	if (!dep->conflict) {
@@ -1029,7 +1046,7 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
 
 	if (ss->num_decisions > 0) {
 		requirer_name = ss->decisions[ss->num_decisions].name;
-		requirer_pkg  = ss->decisions[ss->num_decisions].pkg;
+		requirer_pkg  = decision_to_pkg(&ss->decisions[ss->num_decisions]);
 		strength = requirer_name->ss.requirers ?: 1;
 	} else {
 		strength = 1;
@@ -1082,10 +1099,10 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
 
 	/* note: for perfection, we should revert here to the
 	 * *previous* value, but that'd require keeping track
-	 * of it which would require dynamic memory allocations.
-	 * in practice this is good enough. */
-	if (name->ss.last_touched_decision > ss->num_decisions)
-		name->ss.last_touched_decision = ss->num_decisions;
+	 * of it which would require dynamic memory allocations
+	 * or additional solver state field in apk_dependency
+	 * to store it (or hefty recalculations). */
+	name->ss.last_touched_decision = 0;
 
 	if (requirer_name && requirer_name->ss.requirers != strength) {
 		dbg_printf("requirer %s, dependency %s: strength mismatch %d != %d\n",
@@ -1308,7 +1325,7 @@ static void record_solution(struct apk_solver_state *ss)
 	for (i = ss->num_decisions; i > 0; i--) {
 		struct apk_decision *d = &ss->decisions[i];
 		struct apk_name *name = d->name;
-		struct apk_package *pkg = d->pkg;
+		struct apk_package *pkg = decision_to_pkg(d);
 		struct apk_package_state *ps;
 		unsigned short pinning;
 		unsigned int repos;
@@ -1316,8 +1333,7 @@ static void record_solution(struct apk_solver_state *ss)
 		d->found_solution = 1;
 
 		if (pkg == NULL) {
-			dbg_printf("record_solution: %s: NOTHING\n",
-				   decision_to_name(d)->name);
+			dbg_printf("record_solution: %s: NOTHING\n", name->name);
 			continue;
 		}
 
-- 
cgit v1.2.3-70-g09d2