From 99145e2c0dc0b5b3b5a2a72fb1bff140d1f583f3 Mon Sep 17 00:00:00 2001 From: Timo Teräs Date: Fri, 24 Feb 2012 15:50:39 +0200 Subject: all: introduce apk_provides and use it in apk_name in preparation for provides support. implements also some dependency satisfaction helper routines. ref #574. --- src/solver.c | 152 +++++++++++++++++++++++++++++++---------------------------- 1 file changed, 79 insertions(+), 73 deletions(-) (limited to 'src/solver.c') diff --git a/src/solver.c b/src/solver.c index 9875dda..939676b 100644 --- a/src/solver.c +++ b/src/solver.c @@ -93,10 +93,12 @@ struct apk_package_state { unsigned locked : 1; }; +#define CHOSEN_NONE (struct apk_provider) { .pkg = NULL, .version = NULL } + struct apk_name_state { struct list_head unsolved_list; struct apk_name *name; - struct apk_package *chosen; + struct apk_provider chosen; struct apk_score minimum_penalty; unsigned short requirers; @@ -244,8 +246,8 @@ static struct apk_name_state *name_to_ns_alloc(struct apk_name *name) if (name->state_ptr == NULL) { ns = calloc(1, sizeof(struct apk_name_state)); ns->name = name; - for (i = 0; i < name->pkgs->num; i++) { - if (name->pkgs->item[i]->repos != 0) { + for (i = 0; i < name->providers->num; i++) { + if (name->providers->item[i].pkg->repos != 0) { ns->has_available_pkgs = 1; break; } @@ -282,14 +284,14 @@ static void foreach_dependency_pkg( struct apk_dependency *dep = &depends->item[i]; struct apk_name *name0 = dep->name; - for (j = 0; j < name0->pkgs->num; j++) { - struct apk_package *pkg0 = name0->pkgs->item[j]; + for (j = 0; j < name0->providers->num; j++) { + struct apk_provider *p0 = &name0->providers->item[j]; /* conflict depends on all to be not installed */ - if (!apk_dep_is_satisfied(dep, pkg0)) + if (!apk_dep_is_provided(dep, p0)) continue; - cb(ss, pkg0); + cb(ss, p0->pkg); } } } @@ -307,20 +309,21 @@ static void foreach_rinstall_if_pkg( dbg_printf(PKG_VER_FMT ": rinstall_if %s\n", PKG_VER_PRINTF(pkg), name0->name); - for (j = 0; j < name0->pkgs->num; j++) { - struct apk_package *pkg0 = name0->pkgs->item[j]; + for (j = 0; j < name0->providers->num; j++) { + struct apk_provider *p0 = &name0->providers->item[j]; + + for (k = 0; k < p0->pkg->install_if->num; k++) { + struct apk_dependency *dep = &p0->pkg->install_if->item[k]; - for (k = 0; k < pkg0->install_if->num; k++) { - struct apk_dependency *dep = &pkg0->install_if->item[k]; if (dep->name == name && - apk_dep_is_satisfied(dep, pkg)) + apk_dep_is_provided(dep, p0)) break; } - if (k >= pkg0->install_if->num) + if (k >= p0->pkg->install_if->num) continue; /* pkg depends (via install_if) on pkg0 */ - cb(ss, pkg0); + cb(ss, p0->pkg); } } } @@ -413,8 +416,8 @@ static int is_topology_optimum(struct apk_solver_state *ss, int i; get_topology_score(ss, ns, pkg, &score); - for (i = 0; i < name->pkgs->num; i++) { - struct apk_package *pkg0 = name->pkgs->item[i]; + for (i = 0; i < name->providers->num; i++) { + struct apk_package *pkg0 = name->providers->item[i].pkg; struct apk_package_state *ps0 = pkg_to_ps(pkg0); struct apk_score score0; @@ -434,9 +437,12 @@ static int is_topology_optimum(struct apk_solver_state *ss, } static int compare_absolute_package_preference( - struct apk_package *pkgA, - struct apk_package *pkgB) + struct apk_provider *pA, + struct apk_provider *pB) { + struct apk_package *pkgA = pA->pkg; + struct apk_package *pkgB = pB->pkg; + /* specified on command line directly */ if (pkgA->filename && !pkgB->filename) return 1; @@ -445,7 +451,7 @@ static int compare_absolute_package_preference( /* upgrading, or neither of the package is installed, so * we just fall back comparing to versions */ - switch (apk_pkg_version_compare(pkgA, pkgB)) { + switch (apk_version_compare_blob(*pA->version, *pB->version)) { case APK_VERSION_GREATER: return 1; case APK_VERSION_LESS: @@ -466,15 +472,17 @@ static void calculate_pkg_preference(struct apk_package *pkg) { struct apk_name *name = pkg->name; struct apk_package_state *ps = pkg_to_ps(pkg); + struct apk_provider p = APK_PROVIDER_FROM_PACKAGE(pkg); int i; - for (i = 0; i < name->pkgs->num; i++) { - struct apk_package *pkg0 = name->pkgs->item[i]; - if (pkg == pkg0) + for (i = 0; i < name->providers->num; i++) { + struct apk_provider *p0 = &name->providers->item[i]; + if (pkg == p0->pkg) continue; - if (compare_absolute_package_preference(pkg, pkg0) < 0) + if (compare_absolute_package_preference(&p, p0) < 0) ps->preference++; } + /* FIXME: consider all provided names too */ } static void count_name(struct apk_solver_state *ss, struct apk_name_state *ns) @@ -552,8 +560,8 @@ static void recalculate_maybe(struct apk_solver_state *ss, struct apk_name *name if (!propagate) return; - for (i = 0; i < name->pkgs->num; i++) { - struct apk_package *pkg = name->pkgs->item[i]; + for (i = 0; i < name->providers->num; i++) { + struct apk_package *pkg = name->providers->item[i].pkg; for (j = 0; j < pkg->depends->num; j++) { struct apk_dependency *dep = &pkg->depends->item[j]; @@ -573,8 +581,8 @@ static void sort_name(struct apk_solver_state *ss, struct apk_name *name) struct apk_name_state *ns = name_to_ns_alloc(name); int i; - for (i = 0; i < name->pkgs->num; i++) - sort_soft_dependencies(ss, name->pkgs->item[i]); + for (i = 0; i < name->providers->num; i++) + sort_soft_dependencies(ss, name->providers->item[i].pkg); count_name(ss, ns); recalculate_maybe(ss, name, @@ -602,7 +610,8 @@ static int install_if_missing(struct apk_solver_state *ss, struct apk_package *p /* ns can be NULL, if the install_if has a name with * no packages */ - if (ns == NULL || !ns->locked || !apk_dep_is_satisfied(dep, ns->chosen)) + if (ns == NULL || !ns->locked || + !apk_dep_is_provided(dep, &ns->chosen)) missing++; } @@ -615,7 +624,7 @@ static void get_unassigned_score(struct apk_name *name, struct apk_score *score) *score = (struct apk_score){ .conflicts = ns->requirers, - .preference = name->pkgs->num, + .preference = name->providers->num, }; } @@ -645,7 +654,7 @@ static void demote_name(struct apk_solver_state *ss, struct apk_name *name) /* remove cached information */ subscore(&ss->minimum_penalty, &ns->minimum_penalty); ns->minimum_penalty = (struct apk_score) { .score = 0 }; - ns->chosen = NULL; + ns->chosen = CHOSEN_NONE; /* and remove list, or request refresh */ if (ns->requirers == 0 && ns->install_ifs == 0) { @@ -791,7 +800,7 @@ static solver_result_t apply_decision(struct apk_solver_state *ss, } ss->assigned_names++; - ns->chosen = pkg; + ns->chosen = APK_PROVIDER_FROM_PACKAGE(pkg); list_del(&ns->unsolved_list); list_init(&ns->unsolved_list); @@ -811,7 +820,7 @@ static solver_result_t apply_decision(struct apk_solver_state *ss, get_unassigned_score(name, &score); addscore(&ss->score, &score); - ns->chosen = NULL; + ns->chosen = CHOSEN_NONE; ns->locked = 1; list_del(&ns->unsolved_list); list_init(&ns->unsolved_list); @@ -880,7 +889,7 @@ static void undo_decision(struct apk_solver_state *ss, } ns->locked = 0; - ns->chosen = NULL; + ns->chosen = CHOSEN_NONE; /* Put back the name to unsolved list */ promote_name(ss, name); @@ -974,17 +983,17 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency } if (ns->locked) { - if (ns->chosen) + if (ns->chosen.pkg) dbg_printf("%s: locked to " PKG_VER_FMT " already\n", - name->name, PKG_VER_PRINTF(ns->chosen)); + name->name, PKG_VER_PRINTF(ns->chosen.pkg)); else dbg_printf("%s: locked to empty\n", name->name); - if (!apk_dep_is_satisfied(dep, ns->chosen)) + if (!apk_dep_is_provided(dep, &ns->chosen)) ss->score.conflicts += strength; return; } - if (name->pkgs->num == 0) { + if (name->providers->num == 0) { if (!dep->optional) ss->score.conflicts += strength; return; @@ -1007,15 +1016,16 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency ns->last_touched_decision = ss->num_decisions; } - for (i = 0; i < name->pkgs->num; i++) { - struct apk_package *pkg0 = name->pkgs->item[i]; + for (i = 0; i < name->providers->num; i++) { + struct apk_provider *p0 = &name->providers->item[i]; + struct apk_package *pkg0 = p0->pkg; struct apk_package_state *ps0 = pkg_to_ps(pkg0); if (ps0 == NULL || ps0->locked || ss->topology_position < pkg0->topology_hard) continue; - if (!apk_dep_is_satisfied(dep, pkg0)) { + if (!apk_dep_is_provided(dep, p0)) { ps0->conflicts++; dbg_printf(PKG_VER_FMT ": conflicts++ -> %d\n", PKG_VER_PRINTF(pkg0), @@ -1044,18 +1054,18 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency * } if (ns->locked) { - if (ns->chosen != NULL) { + if (ns->chosen.pkg != NULL) { dbg_printf(PKG_VER_FMT " selected already for %s\n", - PKG_VER_PRINTF(ns->chosen), name->name); + PKG_VER_PRINTF(ns->chosen.pkg), name->name); } else { dbg_printf("%s selected to not be satisfied\n", name->name); } - if (!apk_dep_is_satisfied(dep, ns->chosen)) + if (!apk_dep_is_provided(dep, &ns->chosen)) ss->score.conflicts -= strength; return; } - if (name->pkgs->num == 0) { + if (name->providers->num == 0) { if (!dep->optional) ss->score.conflicts -= strength; return; @@ -1074,15 +1084,16 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency * ns->last_touched_decision = ss->num_decisions; } - for (i = 0; i < name->pkgs->num; i++) { - struct apk_package *pkg0 = name->pkgs->item[i]; + for (i = 0; i < name->providers->num; i++) { + struct apk_provider *p0 = &name->providers->item[i]; + struct apk_package *pkg0 = p0->pkg; struct apk_package_state *ps0 = pkg_to_ps(pkg0); if (ps0 == NULL || ps0->locked || ss->topology_position < pkg0->topology_hard) continue; - if (!apk_dep_is_satisfied(dep, pkg0)) { + if (!apk_dep_is_provided(dep, p0)) { ps0->conflicts--; dbg_printf(PKG_VER_FMT ": conflicts-- -> %d\n", PKG_VER_PRINTF(pkg0), @@ -1100,7 +1111,7 @@ static int reconsider_name(struct apk_solver_state *ss, struct apk_name *name) { struct apk_name_state *ns = name_to_ns(name); struct apk_score minscore, score; - struct apk_package *next_pkg = NULL; + struct apk_provider *next_p = NULL; unsigned int next_topology = 0, options = 0; int i, score_locked = FALSE; @@ -1124,8 +1135,9 @@ static int reconsider_name(struct apk_solver_state *ss, struct apk_name *name) minscore.score = -1; } - for (i = 0; i < name->pkgs->num; i++) { - struct apk_package *pkg0 = name->pkgs->item[i]; + for (i = 0; i < name->providers->num; i++) { + struct apk_provider *p0 = &name->providers->item[i]; + struct apk_package *pkg0 = p0->pkg; struct apk_package_state *ps0 = pkg_to_ps(pkg0); struct apk_score pkg0_score; @@ -1147,9 +1159,9 @@ static int reconsider_name(struct apk_solver_state *ss, struct apk_name *name) /* next in topology order - next to get locked in */ if (ps0->topology_soft < ss->topology_position && ps0->topology_soft > next_topology) - next_pkg = pkg0, next_topology = ps0->topology_soft; + next_p = p0, next_topology = ps0->topology_soft; else if (pkg0->topology_hard > next_topology) - next_pkg = pkg0, next_topology = pkg0->topology_hard; + next_p = p0, next_topology = pkg0->topology_hard; options++; } @@ -1164,15 +1176,15 @@ static int reconsider_name(struct apk_solver_state *ss, struct apk_name *name) } else if (options == 1 && score_locked && ns->none_excluded) { dbg_printf("reconsider_name: %s: only one choice left with known score, locking.\n", name->name); - return push_decision(ss, name, next_pkg, DECISION_ASSIGN, BRANCH_NO, FALSE); + return push_decision(ss, name, next_p->pkg, DECISION_ASSIGN, BRANCH_NO, FALSE); } - ns->chosen = next_pkg; + ns->chosen = *next_p; ns->minimum_penalty = minscore; addscore(&ss->minimum_penalty, &ns->minimum_penalty); dbg_printf("reconsider_name: %s: min penalty " SCORE_FMT ", next_pkg=%p\n", - name->name, SCORE_PRINTF(&minscore), next_pkg); + name->name, SCORE_PRINTF(&minscore), next_p->pkg); return SOLVERR_SOLUTION; } @@ -1197,11 +1209,11 @@ static int expand_branch(struct apk_solver_state *ss) return r; ns->name_touched = 0; } - if (pkg_to_ps(ns->chosen)->topology_soft < ss->topology_position && - pkg_to_ps(ns->chosen)->topology_soft > topology0) - pkg0 = ns->chosen, topology0 = pkg_to_ps(pkg0)->topology_soft; - else if (ns->chosen->topology_hard > topology0) - pkg0 = ns->chosen, topology0 = pkg0->topology_hard; + if (pkg_to_ps(ns->chosen.pkg)->topology_soft < ss->topology_position && + pkg_to_ps(ns->chosen.pkg)->topology_soft > topology0) + pkg0 = ns->chosen.pkg, topology0 = pkg_to_ps(pkg0)->topology_soft; + else if (ns->chosen.pkg->topology_hard > topology0) + pkg0 = ns->chosen.pkg, topology0 = pkg0->topology_hard; } if (pkg0 == NULL) { dbg_printf("expand_branch: solution with score "SCORE_FMT"\n", @@ -1355,15 +1367,15 @@ static int generate_changeset(struct apk_database *db, { struct apk_name *name; struct apk_name_state *ns; - struct apk_package *pkg, *pkg0; + struct apk_package *pkg; struct apk_installed_package *ipkg; - int i, j, num_installs = 0, num_removed = 0, ci = 0; + int i, num_installs = 0, num_removed = 0, ci = 0; /* calculate change set size */ for (i = 0; i < solution->num; i++) { pkg = solution->item[i].pkg; ns = name_to_ns(pkg->name); - ns->chosen = pkg; + ns->chosen = APK_PROVIDER_FROM_PACKAGE(pkg); ns->in_changeset = 1; if ((pkg->ipkg == NULL) || solution->item[i].reinstall || @@ -1373,7 +1385,7 @@ static int generate_changeset(struct apk_database *db, list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) { name = ipkg->pkg->name; ns = name_to_ns(name); - if ((ns->chosen == NULL) || !ns->in_changeset) + if ((ns->chosen.pkg == NULL) || !ns->in_changeset) num_removed++; } @@ -1382,7 +1394,7 @@ static int generate_changeset(struct apk_database *db, list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) { name = ipkg->pkg->name; ns = name_to_ns(name); - if ((ns->chosen == NULL) || !ns->in_changeset) { + if ((ns->chosen.pkg == NULL) || !ns->in_changeset) { changeset->changes->item[ci].oldpkg = ipkg->pkg; ci++; } @@ -1395,13 +1407,7 @@ static int generate_changeset(struct apk_database *db, if ((pkg->ipkg == NULL) || solution->item[i].reinstall || solution->item[i].repository_tag != pkg->ipkg->repository_tag){ - for (j = 0; j < name->pkgs->num; j++) { - pkg0 = name->pkgs->item[j]; - if (pkg0->ipkg == NULL) - continue; - changeset->changes->item[ci].oldpkg = pkg0; - break; - } + changeset->changes->item[ci].oldpkg = apk_pkg_get_installed(name); changeset->changes->item[ci].newpkg = pkg; changeset->changes->item[ci].repository_tag = solution->item[i].repository_tag; changeset->changes->item[ci].reinstall = solution->item[i].reinstall; @@ -1887,7 +1893,7 @@ static void print_dep_errors(struct apk_database *db, char *label, struct apk_de struct apk_dependency *dep = &deps->item[i]; struct apk_package *pkg = (struct apk_package*) dep->name->state_ptr; - if (apk_dep_is_satisfied(dep, pkg)) + if (apk_dep_is_materialized_or_provided(dep, pkg)) continue; if (print_label) { -- cgit v1.2.3-60-g2f50