solver, dot: elementary provides fixes

implementation is still not near finished, but now at least it
can handle it to a minimum degree. many cases are not done right
yet, though. ref #574.

4 files changed, 108 insertions, 57 deletions

diff --git a/src/apk_database.h b/src/apk_database.h
index 2dbf043..137063b 100644
--- a/src/apk_database.h
+++ b/src/apk_database.h
@@ -78,8 +78,8 @@ struct apk_db_dir_instance {
 	gid_t gid;
 };
 
-#define PROVIDER_FMT		"%s-"BLOB_FMT
-#define PROVIDER_PRINTF(p)	(p)->pkg->name->name, BLOB_PRINTF(*(p)->version)
+#define PROVIDER_FMT		"%s%s"BLOB_FMT
+#define PROVIDER_PRINTF(n,p)	(n)->name, (p)->version->len ? "-" : "", BLOB_PRINTF(*(p)->version)
 
 struct apk_provider {
 	struct apk_package *pkg;
diff --git a/src/database.c b/src/database.c
index ed8b8ee..ae6810b 100644
--- a/src/database.c
+++ b/src/database.c
@@ -518,9 +518,15 @@ riif_done:
 	return;
 }
 
+static inline void add_provider(struct apk_name *name, struct apk_provider p)
+{
+	*apk_provider_array_add(&name->providers) = p;
+}
+
 struct apk_package *apk_db_pkg_add(struct apk_database *db, struct apk_package *pkg)
 {
 	struct apk_package *idb;
+	int i;
 
 	if (pkg->license == NULL)
 		pkg->license = apk_blob_atomize(APK_BLOB_NULL);
@@ -529,8 +535,11 @@ struct apk_package *apk_db_pkg_add(struct apk_database *db, struct apk_package *
 	if (idb == NULL) {
 		idb = pkg;
 		apk_hash_insert(&db->available.packages, pkg);
-		*apk_provider_array_add(&pkg->name->providers) =
-			APK_PROVIDER_FROM_PACKAGE(pkg);
+		add_provider(pkg->name, APK_PROVIDER_FROM_PACKAGE(pkg));
+		for (i = 0; i < pkg->provides->num; i++) {
+			struct apk_dependency *dep = &pkg->provides->item[i];
+			add_provider(dep->name, APK_PROVIDER_FROM_PROVIDES(pkg, dep));
+		}
 		apk_db_pkg_rdepends(db, pkg);
 	} else {
 		idb->repos |= pkg->repos;
diff --git a/src/dot.c b/src/dot.c
index 35426a2..eed4fbb 100644
--- a/src/dot.c
+++ b/src/dot.c
@@ -49,6 +49,19 @@ static void start_graph(struct dot_ctx *ctx)
 		"  node [shape=box];\n");
 }
 
+static void dump_name(struct dot_ctx *ctx, struct apk_name *name)
+{
+	if (name->state_int)
+		return;
+	name->state_int = 1;
+
+	if (name->providers->num == 0) {
+		start_graph(ctx);
+		printf("  \"%s\" [style=dashed, color=red, fontcolor=red, shape=octagon];\n",
+			name->name);
+	}
+}
+
 static int dump_pkg(struct dot_ctx *ctx, struct apk_package *pkg)
 {
 	int i, j, r, ret = 0;
@@ -66,40 +79,33 @@ static int dump_pkg(struct dot_ctx *ctx, struct apk_package *pkg)
 		struct apk_dependency *dep = &pkg->depends->item[i];
 		struct apk_name *name = dep->name;
 
+		dump_name(ctx, name);
+
 		if (name->providers->num == 0) {
-			start_graph(ctx);
 			printf("  \"" PKG_VER_FMT "\" -> \"%s\" [color=red];\n",
-				PKG_VER_PRINTF(pkg),
-				name->name);
-			if (!name->state_int) {
-				printf("  \"%s\" [style=dashed, color=red, fontcolor=red, shape=octagon];\n",
-					name->name);
-				name->state_int = 1;
-			}
-		} else {
-			for (j = 0; j < name->providers->num; j++) {
-				struct apk_provider *p0 = &name->providers->item[j];
-
-				if (!apk_dep_is_provided(dep, p0))
-					continue;
-
-				r = dump_pkg(ctx, p0->pkg);
-				ret += r;
-				if (r || (!ctx->errors_only)) {
-					start_graph(ctx);
-
-					if (p0->pkg->name != dep->name) {
-						/* provided package */
-						printf("  \"" PROVIDER_FMT "\" -> \"" PKG_VER_FMT "\"[arrowhead=inv,color=green];\n",
-							PROVIDER_PRINTF(p0),
-							PKG_VER_PRINTF(p0->pkg));
-					}
-
-					printf("  \"" PKG_VER_FMT "\" -> \"" PROVIDER_FMT "\"%s;\n",
-						PKG_VER_PRINTF(pkg),
-						PROVIDER_PRINTF(p0),
-						r ? "[color=red]" : "");
-				}
+				PKG_VER_PRINTF(pkg), name->name);
+			continue;
+		}
+
+		for (j = 0; j < name->providers->num; j++) {
+			struct apk_provider *p0 = &name->providers->item[j];
+
+			if (!apk_dep_is_provided(dep, p0))
+				continue;
+
+			r = dump_pkg(ctx, p0->pkg);
+			ret += r;
+			if (r || (!ctx->errors_only)) {
+				start_graph(ctx);
+
+				printf("  \"" PKG_VER_FMT "\" -> \"" PKG_VER_FMT "\"[",
+					PKG_VER_PRINTF(pkg),
+					PKG_VER_PRINTF(p0->pkg));
+				if (r)
+					printf("color=red,");
+				if (p0->pkg->name != dep->name)
+					printf("arrowhead=inv,label=\"%s\",", dep->name->name);
+				printf("];\n");
 			}
 		}
 	}
diff --git a/src/solver.c b/src/solver.c
index 939676b..c3f4ba9 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -18,7 +18,7 @@
 #include "apk_print.h"
 
 //#define DEBUG_PRINT
-//#define DEBUG_CHECKS
+#define DEBUG_CHECKS
 
 #ifdef DEBUG_PRINT
 #include <stdio.h>
@@ -391,7 +391,7 @@ static int get_topology_score(
 	if (!(repos & preferred_repos))
 		score.non_preferred_pinnings++;
 
-	if (ns->locked || (ns->allowed_pinning | ns->maybe_pinning) == ns->allowed_pinning) {
+	if (ps->locked || (ns->allowed_pinning | ns->maybe_pinning) == ns->allowed_pinning) {
 		allowed_pinning = ns->allowed_pinning | preferred_pinning | APK_DEFAULT_PINNING_MASK;
 		allowed_repos = get_pinning_mask_repos(ss->db, allowed_pinning);
 		if (!(repos & allowed_repos)) {
@@ -485,8 +485,10 @@ static void calculate_pkg_preference(struct apk_package *pkg)
 	/* FIXME: consider all provided names too */
 }
 
-static void count_name(struct apk_solver_state *ss, struct apk_name_state *ns)
+static void count_name(struct apk_solver_state *ss, struct apk_name *name)
 {
+	struct apk_name_state *ns = name_to_ns_alloc(name);
+
 	if (!ns->decision_counted) {
 		ss->max_decisions++;
 		ns->decision_counted = 1;
@@ -496,7 +498,7 @@ static void count_name(struct apk_solver_state *ss, struct apk_name_state *ns)
 static void sort_hard_dependencies(struct apk_solver_state *ss, struct apk_package *pkg)
 {
 	struct apk_package_state *ps;
-	struct apk_name_state *ns;
+	int i;
 
 	if (pkg->state_ptr == NULL)
 		pkg->state_ptr = calloc(1, sizeof(struct apk_package_state));
@@ -513,8 +515,9 @@ static void sort_hard_dependencies(struct apk_solver_state *ss, struct apk_packa
 	foreach_dependency_pkg(ss, pkg->install_if, sort_hard_dependencies);
 
 	ss->max_decisions++;
-	ns = name_to_ns_alloc(pkg->name);
-	count_name(ss, ns);
+	count_name(ss, pkg->name);
+	for (i = 0; i < pkg->provides->num; i++)
+		count_name(ss, pkg->provides->item[i].name);
 
 	ps->topology_soft = pkg->topology_hard = ++ss->num_topology_positions;
 	dbg_printf(PKG_VER_FMT ": topology_hard=%d\n",
@@ -584,7 +587,7 @@ static void sort_name(struct apk_solver_state *ss, struct apk_name *name)
 	for (i = 0; i < name->providers->num; i++)
 		sort_soft_dependencies(ss, name->providers->item[i].pkg);
 
-	count_name(ss, ns);
+	count_name(ss, name);
 	recalculate_maybe(ss, name,
 			  ns->solver_flags_local & ns->solver_flags_local_mask,
 			  ns->maybe_pinning);
@@ -664,7 +667,8 @@ static void demote_name(struct apk_solver_state *ss, struct apk_name *name)
 			dbg_printf("%s: not required\n", name->name);
 		}
 	} else {
-		ns->name_touched = 1;
+		/* still needed, put back to list */
+		promote_name(ss, name);
 	}
 }
 
@@ -746,6 +750,33 @@ static void untrigger_install_if(struct apk_solver_state *ss,
 	}
 }
 
+static inline void assign_name(
+	struct apk_solver_state *ss, struct apk_name *name, struct apk_provider p)
+{
+	struct apk_name_state *ns = name_to_ns(name);
+
+	ASSERT(!ns->locked, "Assigning locked name");
+	ns->locked = 1;
+	ns->chosen = p;
+	if (list_hashed(&ns->unsolved_list)) {
+		list_del(&ns->unsolved_list);
+		list_init(&ns->unsolved_list);
+	}
+}
+
+static inline void unassign_name(struct apk_solver_state *ss, struct apk_name *name)
+{
+	struct apk_name_state *ns = name_to_ns(name);
+
+	ASSERT(ns->locked, "Unassigning unlocked name");
+	ns->locked = 0;
+	ns->chosen = CHOSEN_NONE;
+	ns->name_touched = 1;
+
+	demote_name(ss, name);
+}
+
+
 static solver_result_t apply_decision(struct apk_solver_state *ss,
 				      struct apk_decision *d)
 {
@@ -753,6 +784,7 @@ static solver_result_t apply_decision(struct apk_solver_state *ss,
 	struct apk_name_state *ns = name_to_ns(name);
 	struct apk_package *pkg = decision_to_pkg(d);
 	struct apk_score score;
+	int i;
 
 	ns->name_touched = 1;
 	if (pkg != NULL) {
@@ -782,7 +814,6 @@ static solver_result_t apply_decision(struct apk_solver_state *ss,
 			subscore(&ss->minimum_penalty, &ns->minimum_penalty);
 			ns->minimum_penalty = (struct apk_score) { .score = 0 };
 
-			ns->locked = 1;
 			get_topology_score(ss, ns, pkg, &score);
 			addscore(&ss->score, &score);
 
@@ -794,16 +825,16 @@ static solver_result_t apply_decision(struct apk_solver_state *ss,
 					   SCORE_PRINTF(&ss->best_score));
 
 				subscore(&ss->score, &score);
-				ns->locked = 0;
 
 				return SOLVERR_PRUNED;
 			}
 
 			ss->assigned_names++;
-			ns->chosen = APK_PROVIDER_FROM_PACKAGE(pkg);
-
-			list_del(&ns->unsolved_list);
-			list_init(&ns->unsolved_list);
+			assign_name(ss, name, APK_PROVIDER_FROM_PACKAGE(pkg));
+			for (i = 0; i < pkg->provides->num; i++) {
+				struct apk_dependency *p = &pkg->provides->item[i];
+				assign_name(ss, p->name, APK_PROVIDER_FROM_PROVIDES(pkg, p));
+			}
 
 			foreach_dependency(ss, pkg->depends, apply_constraint);
 			foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
@@ -849,6 +880,7 @@ static void undo_decision(struct apk_solver_state *ss,
 	struct apk_name_state *ns = name_to_ns(name);
 	struct apk_package *pkg = decision_to_pkg(d);
 	struct apk_score score;
+	int i;
 
 	ns->name_touched = 1;
 
@@ -867,12 +899,18 @@ static void undo_decision(struct apk_solver_state *ss,
 		}
 
 		if (ns->locked) {
-			ss->assigned_names--;
 			foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
 			foreach_dependency(ss, pkg->depends, undo_constraint);
 
 			get_topology_score(ss, ns, pkg, &score);
 			subscore(&ss->score, &score);
+
+			unassign_name(ss, name);
+			for (i = 0; i < pkg->provides->num; i++) {
+				struct apk_dependency *p = &pkg->provides->item[i];
+				unassign_name(ss, p->name);
+			}
+			ss->assigned_names--;
 		}
 		ps->locked = 0;
 	} else {
@@ -886,13 +924,11 @@ static void undo_decision(struct apk_solver_state *ss,
 		} else {
 			ns->none_excluded = 0;
 		}
-	}
 
-	ns->locked = 0;
-	ns->chosen = CHOSEN_NONE;
-
-	/* Put back the name to unsolved list */
-	promote_name(ss, name);
+		/* Put back the name to unsolved list */
+		ns->locked = 0;
+		promote_name(ss, name);
+	}
 }
 
 static solver_result_t push_decision(struct apk_solver_state *ss,