solver, test: make conflicts unconditional

Solver will now never report partial solution where a conflict
constraint is not satisfied. The is because with --force we might
install the partial solution; and if conflicted packages were to
be installed we might have extra trouble.

9 files changed, 66 insertions, 51 deletions

diff --git a/src/add.c b/src/add.c
index 2afe834..f4d4413 100644
--- a/src/add.c
+++ b/src/add.c
@@ -75,8 +75,8 @@ static int add_main(void *ctx, struct apk_database *db, int argc, char **argv)
 			return -1;
 
 		apk_blob_pull_dep(&b, db, &virtdep);
-		if (APK_BLOB_IS_NULL(b) ||
-		    virtdep.result_mask != APK_DEPMASK_REQUIRE ||
+		if (APK_BLOB_IS_NULL(b) || virtdep.conflict ||
+		    virtdep.result_mask != APK_DEPMASK_ANY ||
 		    virtdep.version != &apk_null_blob) {
 			apk_error("%s: bad package specifier");
 			return -1;
diff --git a/src/apk_package.h b/src/apk_package.h
index 070caa8..bd2bbe3 100644
--- a/src/apk_package.h
+++ b/src/apk_package.h
@@ -61,7 +61,7 @@ struct apk_dependency {
 	struct apk_name *name;
 	apk_blob_t *version;
 	unsigned short repository_tag;
-	unsigned optional : 1;
+	unsigned conflict : 1;
 	unsigned result_mask : 3;
 };
 APK_ARRAY(apk_dependency_array, struct apk_dependency);
diff --git a/src/apk_version.h b/src/apk_version.h
index 2afd7b0..dcbf20f 100644
--- a/src/apk_version.h
+++ b/src/apk_version.h
@@ -18,8 +18,7 @@
 #define APK_VERSION_LESS		2
 #define APK_VERSION_GREATER		4
 
-#define APK_DEPMASK_CONFLICT	(0)
-#define APK_DEPMASK_REQUIRE	(APK_VERSION_EQUAL|APK_VERSION_LESS|\
+#define APK_DEPMASK_ANY		(APK_VERSION_EQUAL|APK_VERSION_LESS|\
 				 APK_VERSION_GREATER)
 #define APK_DEPMASK_CHECKSUM	(APK_VERSION_LESS|APK_VERSION_GREATER)
 
diff --git a/src/fetch.c b/src/fetch.c
index 325249d..adc0027 100644
--- a/src/fetch.c
+++ b/src/fetch.c
@@ -177,7 +177,7 @@ static int fetch_main(void *ctx, struct apk_database *db, int argc, char **argv)
 		struct apk_dependency dep = (struct apk_dependency) {
 			.name = apk_db_get_name(db, APK_BLOB_STR(argv[i])),
 			.version = apk_blob_atomize(APK_BLOB_NULL),
-			.result_mask = APK_DEPMASK_REQUIRE,
+			.result_mask = APK_DEPMASK_ANY,
 		};
 
 		if (fctx->flags & FETCH_RECURSIVE) {
diff --git a/src/info.c b/src/info.c
index c21da50..94a3047 100644
--- a/src/info.c
+++ b/src/info.c
@@ -118,7 +118,7 @@ static int info_who_owns(struct info_ctx *ctx, struct apk_database *db,
 			dep = (struct apk_dependency) {
 				.name = pkg->name,
 				.version = apk_blob_atomize(APK_BLOB_NULL),
-				.result_mask = APK_DEPMASK_REQUIRE,
+				.result_mask = APK_DEPMASK_ANY,
 			};
 			apk_deps_add(&deps, &dep);
 		} else {
diff --git a/src/package.c b/src/package.c
index 5446803..1dd83e3 100644
--- a/src/package.c
+++ b/src/package.c
@@ -218,7 +218,7 @@ void apk_blob_pull_dep(apk_blob_t *b, struct apk_database *db, struct apk_depend
 {
 	struct apk_name *name;
 	apk_blob_t bdep, bname, bop, bver = APK_BLOB_NULL, btag;
-	int mask = APK_DEPMASK_REQUIRE, optional = 0, tag = 0;
+	int mask = APK_DEPMASK_ANY, conflict = 0, tag = 0;
 
 	/* [!]name[<,<=,=,>=,>,><]ver */
 	if (APK_BLOB_IS_NULL(*b))
@@ -240,7 +240,7 @@ void apk_blob_pull_dep(apk_blob_t *b, struct apk_database *db, struct apk_depend
 	if (bdep.ptr[0] == '!') {
 		bdep.ptr++;
 		bdep.len--;
-		optional = 1;
+		conflict = 1;
 	}
 
 	if (apk_blob_cspn(bdep, apk_spn_dependency_comparer, &bname, &bop)) {
@@ -281,15 +281,12 @@ void apk_blob_pull_dep(apk_blob_t *b, struct apk_database *db, struct apk_depend
 	if (name == NULL)
 		goto fail;
 
-	if (optional)
-		mask ^= APK_DEPMASK_REQUIRE;
-
 	*dep = (struct apk_dependency){
 		.name = name,
 		.version = apk_blob_atomize_dup(bver),
 		.repository_tag = tag,
 		.result_mask = mask,
-		.optional = optional,
+		.conflict = conflict,
 	};
 	return;
 fail:
@@ -340,46 +337,44 @@ static int apk_dep_match_checksum(struct apk_dependency *dep, struct apk_package
 
 int apk_dep_is_provided(struct apk_dependency *dep, struct apk_provider *p)
 {
-	if (p == NULL)
-		return dep->optional;
+	if (p == NULL || p->pkg == NULL)
+		return dep->conflict;
 
 	switch (dep->result_mask) {
 	case APK_DEPMASK_CHECKSUM:
 		return apk_dep_match_checksum(dep, p->pkg);
-	case APK_DEPMASK_CONFLICT:
-		return 0;
-	case APK_DEPMASK_REQUIRE:
-		return 1;
+	case APK_DEPMASK_ANY:
+		return !dep->conflict;
 	default:
+		if (p->version == &apk_null_blob)
+			return dep->conflict;
 		if (apk_version_compare_blob(*p->version, *dep->version)
 		    & dep->result_mask)
-			return 1;
-		return 0;
+			return !dep->conflict;
+		return dep->conflict;
 	}
-	return 0;
+	return dep->conflict;
 }
 
 int apk_dep_is_materialized(struct apk_dependency *dep, struct apk_package *pkg)
 {
 	if (pkg == NULL)
-		return dep->optional;
+		return dep->conflict;
 	if (dep->name != pkg->name)
-		return 0;
+		return dep->conflict;
 
 	switch (dep->result_mask) {
 	case APK_DEPMASK_CHECKSUM:
 		return apk_dep_match_checksum(dep, pkg);
-	case APK_DEPMASK_CONFLICT:
-		return 0;
-	case APK_DEPMASK_REQUIRE:
-		return 1;
+	case APK_DEPMASK_ANY:
+		return !dep->conflict;
 	default:
 		if (apk_version_compare_blob(*pkg->version, *dep->version)
 		    & dep->result_mask)
-			return 1;
-		return 0;
+			return !dep->conflict;
+		return dep->conflict;
 	}
-	return 0;
+	return dep->conflict;
 }
 
 int apk_dep_is_materialized_or_provided(struct apk_dependency *dep, struct apk_package *pkg)
@@ -387,7 +382,7 @@ int apk_dep_is_materialized_or_provided(struct apk_dependency *dep, struct apk_p
 	int i;
 
 	if (pkg == NULL)
-		return dep->optional;
+		return dep->conflict;
 
 	if (dep->name == pkg->name)
 		return apk_dep_is_materialized(dep, pkg);
@@ -401,17 +396,15 @@ int apk_dep_is_materialized_or_provided(struct apk_dependency *dep, struct apk_p
 		return apk_dep_is_provided(dep, &p);
 	}
 
-	return dep->optional;
+	return dep->conflict;
 }
 
 void apk_blob_push_dep(apk_blob_t *to, struct apk_database *db, struct apk_dependency *dep)
 {
 	int result_mask = dep->result_mask;
 
-	if (dep->optional) {
+	if (dep->conflict)
 		apk_blob_push_blob(to, APK_BLOB_PTR_LEN("!", 1));
-		result_mask ^= APK_DEPMASK_REQUIRE;
-	}
 
 	apk_blob_push_blob(to, APK_BLOB_STR(dep->name->name));
 	if (dep->repository_tag && db != NULL) {
diff --git a/src/solver.c b/src/solver.c
index b50380b..7420359 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -96,7 +96,9 @@ struct apk_package_state {
 	unsigned short inherited_upgrade;
 	unsigned short inherited_reinstall;
 
-	unsigned short conflicts;
+	unsigned short must_not;
+	unsigned short incompat_dep;
+
 	unsigned char preference;
 	unsigned handle_install_if : 1;
 	unsigned allowed : 1;
@@ -152,6 +154,7 @@ struct apk_solver_state {
 	struct apk_score best_score;
 
 	unsigned solver_flags : 4;
+	unsigned impossible_state : 1;
 };
 
 typedef enum {
@@ -367,7 +370,7 @@ static int get_topology_score(
 	int score_locked = TRUE, sticky_installed = FALSE;
 
 	score = (struct apk_score) {
-		.conflicts = ps->conflicts,
+		.conflicts = ps->incompat_dep,
 		.preference = ps->preference,
 	};
 
@@ -796,6 +799,7 @@ static solver_result_t apply_decision(struct apk_solver_state *ss,
 	struct apk_score score;
 	int i;
 
+	ss->impossible_state = 0;
 	ns->name_touched = 1;
 	if (pkg != NULL) {
 		struct apk_package_state *ps = pkg_to_ps(pkg);
@@ -855,6 +859,13 @@ static solver_result_t apply_decision(struct apk_solver_state *ss,
 		}
 	}
 
+	if (ss->impossible_state) {
+		dbg_printf("%s: %s impossible constraints\n",
+			name->name,
+			(d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
+		return SOLVERR_PRUNED;
+	}
+
 	if (cmpscore(&ss->score, &ss->best_score) >= 0) {
 		dbg_printf("%s: %s penalty too big: "SCORE_FMT">="SCORE_FMT"\n",
 			name->name,
@@ -1024,13 +1035,18 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
 		else
 			dbg_printf("%s: locked to empty\n",
 				   name->name);
-		if (!apk_dep_is_provided(dep, &ns->chosen))
+		if (!apk_dep_is_provided(dep, &ns->chosen)) {
+			dbg_printf("%s: constraint violation %d\n",
+				   name->name, strength);
 			ss->score.conflicts += strength;
+			if (dep->conflict)
+				ss->impossible_state = 1;
+		}
 		return;
 	}
 
 	if (name->providers->num == 0) {
-		if (!dep->optional)
+		if (!dep->conflict)
 			ss->score.conflicts += strength;
 		return;
 	}
@@ -1045,10 +1061,14 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
 			continue;
 
 		if (!apk_dep_is_provided(dep, p0)) {
-			ps0->conflicts++;
+			if (dep->conflict)
+				ps0->must_not++;
+			else
+				ps0->incompat_dep++;
+
 			dbg_printf(PKG_VER_FMT ": conflicts++ -> %d\n",
 				   PKG_VER_PRINTF(pkg0),
-				   ps0->conflicts);
+				   ps0->must_not);
 			changed |= 1;
 		} else if (requirer_pkg != NULL) {
 			dbg_printf(PKG_VER_FMT ": inheriting flags and pinning from"PKG_VER_FMT"\n",
@@ -1061,7 +1081,7 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
 	if (changed)
 		ns->last_touched_decision = ss->num_decisions;
 
-	if (!dep->optional)
+	if (!dep->conflict)
 		ns->requirers += strength;
 
 	promote_name(ss, name);
@@ -1096,7 +1116,7 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
 		return;
 	}
 	if (name->providers->num == 0) {
-		if (!dep->optional)
+		if (!dep->conflict)
 			ss->score.conflicts -= strength;
 		return;
 	}
@@ -1111,10 +1131,13 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
 			continue;
 
 		if (!apk_dep_is_provided(dep, p0)) {
-			ps0->conflicts--;
+			if (dep->conflict)
+				ps0->must_not--;
+			else
+				ps0->incompat_dep--;
 			dbg_printf(PKG_VER_FMT ": conflicts-- -> %d\n",
 				   PKG_VER_PRINTF(pkg0),
-				   ps0->conflicts);
+				   ps0->must_not);
 		} else if (requirer_pkg != NULL) {
 			dbg_printf(PKG_VER_FMT ": uninheriting flags and pinning from "PKG_VER_FMT"\n",
 				   PKG_VER_PRINTF(pkg0),
@@ -1130,7 +1153,7 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
 	if (ns->last_touched_decision > ss->num_decisions)
 		ns->last_touched_decision = ss->num_decisions;
 
-	if (!dep->optional)
+	if (!dep->conflict)
 		ns->requirers -= strength;
 
 	demote_name(ss, name);
@@ -1163,7 +1186,7 @@ static int reconsider_name(struct apk_solver_state *ss, struct apk_name *name)
 		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
 		struct apk_score pkg0_score;
 
-		if (ps0 == NULL || ps0->locked ||
+		if (ps0 == NULL || ps0->locked || ps0->must_not ||
 		    ss->topology_position < pkg0->topology_hard ||
 		    (pkg0->ipkg == NULL && (!ps0->allowed || !pkg_available(ss->db, pkg0))))
 			continue;
@@ -1274,7 +1297,7 @@ static int expand_branch(struct apk_solver_state *ss)
 
 	if (!ns->none_excluded) {
 		struct apk_package_state *ps0 = pkg_to_ps(pkg0);
-		if (ps0->conflicts > ns->requirers)
+		if (ps0->incompat_dep > ns->requirers)
 			primary_decision = DECISION_ASSIGN;
 		else
 			primary_decision = DECISION_EXCLUDE;
diff --git a/src/upgrade.c b/src/upgrade.c
index 1185079..914f019 100644
--- a/src/upgrade.c
+++ b/src/upgrade.c
@@ -114,7 +114,7 @@ static int upgrade_main(void *ctx, struct apk_database *db, int argc, char **arg
 		for (i = 0; i < world->num; i++) {
 			struct apk_dependency *dep = &world->item[i];
 			if (dep->result_mask == APK_DEPMASK_CHECKSUM) {
-				dep->result_mask = APK_DEPMASK_REQUIRE;
+				dep->result_mask = APK_DEPMASK_ANY;
 				dep->version = apk_blob_atomize(APK_BLOB_NULL);
 			}
 		}
diff --git a/test/conflict2.test b/test/conflict2.test
index 8235e9c..9cd4a85 100644
--- a/test/conflict2.test
+++ b/test/conflict2.test
@@ -3,4 +3,4 @@
 add a b>1
 @EXPECT
 ERROR: 1 unsatisfiable dependencies:
-  a-1: !b>1
+  world: a