diff options
| -rw-r--r-- | src/apk_database.h | 4 | ||||
| -rw-r--r-- | src/database.c | 13 | ||||
| -rw-r--r-- | src/dot.c | 70 | ||||
| -rw-r--r-- | src/solver.c | 78 |
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; @@ -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, |