summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTimo Teräs <timo.teras@iki.fi>2012-02-24 18:27:55 +0200
committerTimo Teräs <timo.teras@iki.fi>2012-02-24 18:29:30 +0200
commit12bdec38a376f787a8aa621c965b561387b445ce (patch)
tree055074fe2eb53047f62282ab11dc8ecc4dadd06a
parent99145e2c0dc0b5b3b5a2a72fb1bff140d1f583f3 (diff)
downloadapk-tools-12bdec38a376f787a8aa621c965b561387b445ce.tar.gz
apk-tools-12bdec38a376f787a8aa621c965b561387b445ce.tar.bz2
apk-tools-12bdec38a376f787a8aa621c965b561387b445ce.tar.xz
apk-tools-12bdec38a376f787a8aa621c965b561387b445ce.zip
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.
-rw-r--r--src/apk_database.h4
-rw-r--r--src/database.c13
-rw-r--r--src/dot.c70
-rw-r--r--src/solver.c78
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,