diff options
| -rw-r--r-- | src/apk_version.h | 1 | ||||
| -rw-r--r-- | src/package.c | 13 | ||||
| -rw-r--r-- | src/solver.c | 364 |
3 files changed, 227 insertions, 151 deletions
diff --git a/src/apk_version.h b/src/apk_version.h index 514fea9..2afd7b0 100644 --- a/src/apk_version.h +++ b/src/apk_version.h @@ -18,6 +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|\ APK_VERSION_GREATER) #define APK_DEPMASK_CHECKSUM (APK_VERSION_LESS|APK_VERSION_GREATER) diff --git a/src/package.c b/src/package.c index a162038..7cefc74 100644 --- a/src/package.c +++ b/src/package.c @@ -316,17 +316,26 @@ int apk_dep_is_satisfied(struct apk_dependency *dep, struct apk_package *pkg) return dep->optional; if (dep->name != pkg->name) return 0; - if (dep->result_mask == APK_DEPMASK_CHECKSUM) { + + switch (dep->result_mask) { + case APK_DEPMASK_CHECKSUM: { struct apk_checksum csum; apk_blob_t b = *dep->version; apk_blob_pull_csum(&b, &csum); if (apk_checksum_compare(&csum, &pkg->csum) == 0) return 1; - } else { + break; + } + case APK_DEPMASK_CONFLICT: + return 0; + case APK_DEPMASK_REQUIRE: + return 1; + default: if (apk_version_compare_blob(*pkg->version, *dep->version) & dep->result_mask) return 1; + break; } return 0; } diff --git a/src/solver.c b/src/solver.c index a27b4d4..7c3679c 100644 --- a/src/solver.c +++ b/src/solver.c @@ -65,6 +65,7 @@ struct apk_decision { unsigned type : 1; unsigned branching_point : 1; unsigned topology_position : 1; + unsigned found_solution : 1; }; struct apk_package_state { @@ -89,22 +90,32 @@ struct apk_name_state { unsigned short requirers; unsigned short install_ifs; + /* set on startup */ unsigned short preferred_pinning; + unsigned short maybe_pinning; + + /* dynamic */ + unsigned int last_touched_decision; unsigned short allowed_pinning; + unsigned short inherited_pinning[APK_MAX_TAGS]; + unsigned short inherited_upgrade; + unsigned short inherited_reinstall; + /* one time prepare/finish flags */ unsigned solver_flags_local : 4; unsigned solver_flags_local_mask : 4; - unsigned solver_flags_inherited : 4; + unsigned solver_flags_maybe : 4; - /* one time prepare/finish flags */ unsigned decision_counted : 1; unsigned originally_installed : 1; + unsigned has_available_pkgs : 1; unsigned prepared : 1; unsigned in_changeset : 1; /* dynamic state flags */ unsigned none_excluded : 1; unsigned locked : 1; + unsigned name_touched : 1; }; struct apk_solver_state { @@ -125,7 +136,6 @@ struct apk_solver_state { struct apk_score best_score; unsigned solver_flags : 4; - unsigned impossible_constraints : 1; }; typedef enum { @@ -158,7 +168,7 @@ static void subscore(struct apk_score *a, struct apk_score *b) a->preference -= b->preference; } -static int cmpscore(struct apk_score *a, struct apk_score *b) +static inline int cmpscore(struct apk_score *a, struct apk_score *b) { if (a->conflicts < b->conflicts) return -1; @@ -178,11 +188,24 @@ static int cmpscore(struct apk_score *a, struct apk_score *b) return 0; } -static int cmpscore2(struct apk_score *a1, struct apk_score *a2, struct apk_score *b) +static inline int cmpscore2(struct apk_score *a1, struct apk_score *a2, struct apk_score *b) { - struct apk_score tmp = *a1; - addscore(&tmp, a2); - return cmpscore(&tmp, b); + if (a1->conflicts + a2->conflicts < b->conflicts) + return -1; + if (a1->conflicts + a2->conflicts > b->conflicts) + return 1; + + if (a1->non_preferred_actions + a2->non_preferred_actions < b->non_preferred_actions) + return -1; + if (a1->non_preferred_actions + a2->non_preferred_actions > b->non_preferred_actions) + return 1; + + if (a1->preference + a2->preference < b->preference) + return -1; + if (a1->preference + a2->preference > b->preference) + return 1; + + return 0; } static struct apk_name *decision_to_name(struct apk_decision *d) @@ -206,11 +229,23 @@ static struct apk_package_state *pkg_to_ps(struct apk_package *pkg) static struct apk_name_state *name_to_ns(struct apk_name *name) { + return (struct apk_name_state*) name->state_ptr; +} + +static struct apk_name_state *name_to_ns_alloc(struct apk_name *name) +{ struct apk_name_state *ns; + int i; 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) { + ns->has_available_pkgs = 1; + break; + } + } name->state_ptr = ns; } else { ns = (struct apk_name_state*) name->state_ptr; @@ -301,31 +336,27 @@ static void get_topology_score( struct apk_solver_state *ss, struct apk_name_state *ns, struct apk_package *pkg, - int lock_score, struct apk_score *_score) { - struct apk_name *name = pkg->name; struct apk_package_state *ps = pkg_to_ps(pkg); struct apk_score score; - unsigned short name_flags; unsigned int repos; unsigned short preferred_pinning, allowed_pinning; unsigned int preferred_repos, allowed_repos; - /* effective dynamic flags */ - name_flags = ns->solver_flags_local | ns->solver_flags_inherited | ss->solver_flags; - score = (struct apk_score) { .conflicts = ps->conflicts, .preference = ps->preference, }; - if ((name_flags & APK_SOLVERF_AVAILABLE) && (pkg->repos == 0)) { - score.non_preferred_actions ++; - score.preference += name->pkgs->num; - } else if (lock_score && !(name_flags & APK_SOLVERF_UPGRADE)) { + if (ss->solver_flags & APK_SOLVERF_AVAILABLE) { + /* not upgrading: it is not preferred to change package */ + if ((pkg->repos == 0) && ns->has_available_pkgs) + score.non_preferred_actions++; + } else if ((ns->inherited_upgrade) == 0 && + ((ns->solver_flags_local|ss->solver_flags) & APK_SOLVERF_UPGRADE) == 0 && + ((ns->solver_flags_maybe & APK_SOLVERF_UPGRADE) == 0 || (ps->locked))) { /* not upgrading: it is not preferred to change package */ - struct apk_name_state *ns = name_to_ns(name); if (pkg->ipkg == NULL && ns->originally_installed) score.non_preferred_actions++; } @@ -337,12 +368,11 @@ static void get_topology_score( if (!(repos & preferred_repos)) score.non_preferred_actions++; - if (lock_score) { + if (ns->locked || (ns->allowed_pinning | ns->maybe_pinning) == ns->allowed_pinning) { allowed_pinning = ns->allowed_pinning | preferred_pinning; allowed_repos = get_pinning_mask_repos(ss->db, allowed_pinning); - if (!(repos & allowed_repos)) - score.non_preferred_actions += 2; + score.non_preferred_actions+=2; } *_score = score; @@ -356,8 +386,7 @@ static int is_topology_optimum(struct apk_solver_state *ss, struct apk_score score; int i; - /* FIXME: should not use absolute topology score */ - get_topology_score(ss, ns, pkg, 1, &score); + get_topology_score(ss, ns, pkg, &score); for (i = 0; i < name->pkgs->num; i++) { struct apk_package *pkg0 = name->pkgs->item[i]; struct apk_package_state *ps0 = pkg_to_ps(pkg0); @@ -370,7 +399,7 @@ static int is_topology_optimum(struct apk_solver_state *ss, ss->topology_position < pkg->topology_hard) continue; - get_topology_score(ss, ns, pkg0, 1, &score0); + get_topology_score(ss, ns, pkg0, &score0); if (cmpscore(&score0, &score) < 0) return 0; } @@ -443,7 +472,7 @@ static void sort_hard_dependencies(struct apk_solver_state *ss, struct apk_packa ss->max_decisions++; - ns = name_to_ns(pkg->name); + ns = name_to_ns_alloc(pkg->name); if (!ns->decision_counted) { ss->max_decisions++; ns->decision_counted = 1; @@ -475,43 +504,53 @@ static void sort_soft_dependencies(struct apk_solver_state *ss, struct apk_packa PKG_VER_PRINTF(pkg), ps->topology_soft); } -static void sort_name(struct apk_solver_state *ss, struct apk_name *name) -{ - int i; - - for (i = 0; i < name->pkgs->num; i++) - sort_soft_dependencies(ss, name->pkgs->item[i]); -} - -static void foreach_locked_reverse_dependency( - struct apk_name *name, - void (*cb)(struct apk_package *rdepend, void *ctx), void *ctx) +static void recalculate_maybe(struct apk_solver_state *ss, struct apk_name *name, + unsigned short flags, unsigned short pinning) { + struct apk_name_state *ns = name_to_ns_alloc(name); + int propagate = FALSE; int i, j; - if (name == NULL) + if ((ns->maybe_pinning & pinning) != pinning) { + ns->maybe_pinning |= pinning; + propagate = TRUE; + } + if ((ns->solver_flags_maybe & flags) != flags) { + ns->solver_flags_maybe |= flags; + propagate = TRUE; + } + if (!propagate) return; - for (i = 0; i < name->rdepends->num; i++) { - struct apk_name *name0 = name->rdepends->item[i]; - struct apk_name_state *ns0 = name_to_ns(name0); - struct apk_package *pkg0 = ns0->chosen; - - if (!ns0->locked || ns0->chosen == NULL) - continue; + for (i = 0; i < name->pkgs->num; i++) { + struct apk_package *pkg = name->pkgs->item[i]; - for (j = 0; j < pkg0->depends->num; j++) { - struct apk_dependency *dep = &pkg0->depends->item[j]; - if (dep->name == name) - break; + for (j = 0; j < pkg->depends->num; j++) { + struct apk_dependency *dep = &pkg->depends->item[j]; + struct apk_name *name0 = dep->name; + recalculate_maybe(ss, name0, flags, pinning); } - if (j >= pkg0->depends->num) - continue; + } - cb(pkg0, ctx); + for (i = 0; i < name->rinstall_if->num; i++) { + struct apk_name *name0 = name->rinstall_if->item[i]; + recalculate_maybe(ss, name0, flags, pinning); } } +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]); + + recalculate_maybe(ss, name, + ns->solver_flags_local & ns->solver_flags_local_mask, + ns->maybe_pinning); +} + static void foreach_dependency(struct apk_solver_state *ss, struct apk_dependency_array *deps, void (*func)(struct apk_solver_state *ss, struct apk_dependency *dep)) { @@ -543,9 +582,8 @@ static int check_if_package_unavailable(struct apk_solver_state *ss, struct apk_ struct apk_name_state *ns = name_to_ns(name); /* installed and no-reinstall required? no check needed. */ - if ((pkg->ipkg != NULL) && - ((ns->solver_flags_local | ns->solver_flags_inherited | - ss->solver_flags) & APK_SOLVERF_REINSTALL) == 0) + if ((pkg->ipkg != NULL) && (ns->inherited_reinstall == 0) && + ((ns->solver_flags_local|ss->solver_flags) & APK_SOLVERF_REINSTALL) == 0) return 0; /* done already? */ @@ -605,34 +643,13 @@ static void foreach_common_dependency( } } -#if 0 -static void prepare_name(struct apk_solver_state *ss, struct apk_name *name) -{ - struct apk_name_state *ns = name_to_ns(name); - int i, j; - - if (ns->prepared) - return; - ns->prepared = 1; - - for (i = 0; i < name->pkgs->num; i++) { - struct apk_package *pkg = name->pkgs->item[i]; - if (pkg_to_ps(pkg) == NULL) - continue; - for (j = 0; j < pkg->depends->num; j++) { - struct apk_dependency *dep = &pkg->depends->item[j]; - prepare_name(ss, dep->name); - } - } -} -#endif - static void get_unassigned_score(struct apk_name *name, struct apk_score *score) { struct apk_name_state *ns = name_to_ns(name); *score = (struct apk_score){ - .conflicts = ns->requirers + ns->prerequires, + .conflicts = ns->requirers ? : (ns->prerequires ? 1 : 0), + .non_preferred_actions = 1, .preference = name->pkgs->num, }; } @@ -651,6 +668,8 @@ static int update_name_state(struct apk_solver_state *ss, struct apk_name *name) subscore(&ss->minimum_penalty, &ns->minimum_penalty); ns->minimum_penalty = (struct apk_score) { 0, 0 }; + ns->name_touched = 1; + get_unassigned_score(name, &preferred_score); for (i = 0; i < name->pkgs->num; i++) { struct apk_package *pkg0 = name->pkgs->item[i]; @@ -663,8 +682,7 @@ static int update_name_state(struct apk_solver_state *ss, struct apk_name *name) continue; /* preferred - currently most optimal for end solution */ - /* FIXME: should not use absolute topology score */ - get_topology_score(ss, ns, pkg0, 1, &pkg0_score); + get_topology_score(ss, ns, pkg0, &pkg0_score); if (preferred_pkg == NULL || cmpscore(&pkg0_score, &preferred_score) < 0) { @@ -713,23 +731,68 @@ static int update_name_state(struct apk_solver_state *ss, struct apk_name *name) return options + 1; } - if (options == 0) { - ss->impossible_constraints = 1; - dbg_printf("%s: impossible constraints\n", name->name); + return options; +} + +static void inherit_name_state(struct apk_database *db, struct apk_name *to, struct apk_name *from) +{ + struct apk_name_state *tns = name_to_ns(to); + struct apk_name_state *fns = name_to_ns(from); + int i; + + if ((fns->solver_flags_local & fns->solver_flags_local_mask & APK_SOLVERF_REINSTALL) || + fns->inherited_reinstall) + tns->inherited_reinstall++; + + if ((fns->solver_flags_local & fns->solver_flags_local_mask & APK_SOLVERF_UPGRADE) || + fns->inherited_upgrade) + tns->inherited_upgrade++; + + if (fns->allowed_pinning) { + for (i = 0; i < db->num_repo_tags; i++) { + if (!(fns->allowed_pinning & BIT(i))) + continue; + if (tns->inherited_pinning[i]++ == 0) + tns->allowed_pinning |= BIT(i); + } } +} - return options; +static void uninherit_name_state(struct apk_database *db, struct apk_name *to, struct apk_name *from) +{ + struct apk_name_state *tns = name_to_ns(to); + struct apk_name_state *fns = name_to_ns(from); + int i; + + if ((fns->solver_flags_local & fns->solver_flags_local_mask & APK_SOLVERF_REINSTALL) || + fns->inherited_reinstall) + tns->inherited_reinstall--; + + if ((fns->solver_flags_local & fns->solver_flags_local_mask & APK_SOLVERF_UPGRADE) || + fns->inherited_upgrade) + tns->inherited_upgrade--; + + if (fns->allowed_pinning) { + for (i = 0; i < db->num_repo_tags; i++) { + if (!(fns->allowed_pinning & BIT(i))) + continue; + if (--tns->inherited_pinning[i] == 0) + tns->allowed_pinning &= ~BIT(i); + } + } } static void trigger_install_if(struct apk_solver_state *ss, struct apk_package *pkg) { if (install_if_missing(ss, pkg) == 0) { + struct apk_name *name0 = decision_to_name(&ss->decisions[ss->num_decisions]); struct apk_name_state *ns = ns = name_to_ns(pkg->name); dbg_printf("trigger_install_if: " PKG_VER_FMT " triggered\n", PKG_VER_PRINTF(pkg)); ns->install_ifs++; + inherit_name_state(ss->db, pkg->name, name0); update_name_state(ss, pkg->name); } } @@ -738,26 +801,34 @@ static void untrigger_install_if(struct apk_solver_state *ss, struct apk_package *pkg) { if (install_if_missing(ss, pkg) != 1) { + struct apk_name *name0 = decision_to_name(&ss->decisions[ss->num_decisions]); struct apk_name_state *ns = name_to_ns(pkg->name); dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n", PKG_VER_PRINTF(pkg)); ns->install_ifs--; + uninherit_name_state(ss->db, pkg->name, name0); update_name_state(ss, pkg->name); } } static void increment_prerequires(struct apk_solver_state *ss, struct apk_name *name) { + struct apk_name *name0 = decision_to_name(&ss->decisions[ss->num_decisions]); struct apk_name_state *ns = name_to_ns(name); + ns->prerequires++; + inherit_name_state(ss->db, name, name0); update_name_state(ss, name); } static void decrement_prerequires(struct apk_solver_state *ss, struct apk_name *name) { + struct apk_name *name0 = decision_to_name(&ss->decisions[ss->num_decisions]); struct apk_name_state *ns = name_to_ns(name); + ns->prerequires--; + uninherit_name_state(ss->db, name, name0); update_name_state(ss, name); } @@ -769,7 +840,7 @@ static solver_result_t apply_decision(struct apk_solver_state *ss, struct apk_package *pkg = decision_to_pkg(d); struct apk_score score; - ss->impossible_constraints = 0; + ns->name_touched = 1; if (pkg != NULL) { struct apk_package_state *ps = pkg_to_ps(pkg); @@ -797,7 +868,8 @@ static solver_result_t apply_decision(struct apk_solver_state *ss, subscore(&ss->minimum_penalty, &ns->minimum_penalty); ns->minimum_penalty = (struct apk_score) { 0 }; - get_topology_score(ss, ns, pkg, 1, &score); + ns->locked = 1; + get_topology_score(ss, ns, pkg, &score); addscore(&ss->score, &score); if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) >= 0 || @@ -809,6 +881,8 @@ 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; } @@ -816,7 +890,6 @@ static solver_result_t apply_decision(struct apk_solver_state *ss, ss->assigned_names++; ns->chosen = pkg; - ns->locked = 1; list_del(&ns->unsolved_list); list_init(&ns->unsolved_list); @@ -844,9 +917,6 @@ static solver_result_t apply_decision(struct apk_solver_state *ss, } } - if (ss->impossible_constraints) - return SOLVERR_PRUNED; - if (d->type == DECISION_EXCLUDE) { foreach_common_dependency(ss, name, increment_prerequires); @@ -879,6 +949,7 @@ static void undo_decision(struct apk_solver_state *ss, struct apk_package *pkg = decision_to_pkg(d); struct apk_score score; + ns->name_touched = 1; if (d->type == DECISION_EXCLUDE) { foreach_common_dependency(ss, name, decrement_prerequires); } @@ -903,7 +974,7 @@ static void undo_decision(struct apk_solver_state *ss, foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if); foreach_dependency(ss, pkg->depends, undo_constraint); - get_topology_score(ss, ns, pkg, 1, &score); + get_topology_score(ss, ns, pkg, &score); subscore(&ss->score, &score); } ps->locked = 0; @@ -947,6 +1018,7 @@ static solver_result_t push_decision(struct apk_solver_state *ss, d->type = primary_decision; d->branching_point = branching_point; d->topology_position = topology_position; + d->found_solution = 0; if (pkg == NULL) { d->name = name; d->no_package = 1; @@ -960,6 +1032,8 @@ static solver_result_t push_decision(struct apk_solver_state *ss, static int next_branch(struct apk_solver_state *ss) { + unsigned int backup_until = ss->num_decisions; + while (ss->num_decisions > 0) { struct apk_decision *d = &ss->decisions[ss->num_decisions]; @@ -972,12 +1046,20 @@ static int next_branch(struct apk_solver_state *ss) SCORE_PRINTF(&ss->score)); #endif - if (d->branching_point == BRANCH_YES) { + if (backup_until >= ss->num_decisions && + d->branching_point == BRANCH_YES) { d->branching_point = BRANCH_NO; d->type = (d->type == DECISION_ASSIGN) ? DECISION_EXCLUDE : DECISION_ASSIGN; return apply_decision(ss, d); } + if (d->no_package && !d->found_solution) { + struct apk_name *name = decision_to_name(d); + struct apk_name_state *ns = name_to_ns(name); + if (ns->last_touched_decision < backup_until) + backup_until = ns->last_touched_decision; + } + ss->num_decisions--; } @@ -985,46 +1067,6 @@ static int next_branch(struct apk_solver_state *ss) return SOLVERR_STOP; } -static void inherit_name_state(struct apk_name *to, struct apk_name *from) -{ - struct apk_name_state *tns = name_to_ns(to); - struct apk_name_state *fns = name_to_ns(from); - - tns->solver_flags_inherited |= - fns->solver_flags_inherited | - (fns->solver_flags_local & fns->solver_flags_local_mask); - - tns->allowed_pinning |= fns->allowed_pinning | fns->preferred_pinning; -} - -static void inherit_name_state_wrapper(struct apk_package *rdepend, void *ctx) -{ - struct apk_name *name = (struct apk_name *) ctx; - inherit_name_state(name, rdepend->name); -} - -static int has_inherited_state(struct apk_name *name) -{ - struct apk_name_state *ns = name_to_ns(name); - - if (name == NULL) - return 0; - if (ns->solver_flags_inherited || (ns->solver_flags_local & ns->solver_flags_local_mask)) - return 1; - if (ns->allowed_pinning) - return 1; - return 0; -} - -static void recalculate_inherted_name_state(struct apk_name *name) -{ - struct apk_name_state *ns = name_to_ns(name); - - ns->solver_flags_inherited = 0; - ns->allowed_pinning = 0; - foreach_locked_reverse_dependency(name, inherit_name_state_wrapper, name); -} - static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep) { struct apk_name *name = dep->name; @@ -1053,13 +1095,16 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency dep->name->name, dep->repository_tag); ns->preferred_pinning = BIT(dep->repository_tag); ns->allowed_pinning |= BIT(dep->repository_tag); + ns->inherited_pinning[dep->repository_tag]++; + recalculate_maybe(ss, name, 0, ns->allowed_pinning); } if (ss->num_decisions > 0) { struct apk_name *name0 = decision_to_name(&ss->decisions[ss->num_decisions]); dbg_printf("%s: inheriting flags and pinning from %s\n", name->name, name0->name); - inherit_name_state(name, name0); + inherit_name_state(ss->db, name, name0); + ns->last_touched_decision = ss->num_decisions; } for (i = 0; i < name->pkgs->num; i++) { @@ -1108,6 +1153,19 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency * return; } + if (ss->num_decisions > 0) { + struct apk_name *name0 = decision_to_name(&ss->decisions[ss->num_decisions]); + dbg_printf("%s: uninheriting flags and pinning from %s\n", + name->name, name0->name); + uninherit_name_state(ss->db, name, name0); + /* note: for perfection, we should revert here to the + * *previous* value, but that'd require keeping track + * of it which would require dynamic memory allocations. + * in practice this is good enough. */ + if (ns->last_touched_decision > ss->num_decisions) + ns->last_touched_decision = ss->num_decisions; + } + for (i = 0; i < name->pkgs->num; i++) { struct apk_package *pkg0 = name->pkgs->item[i]; struct apk_package_state *ps0 = pkg_to_ps(pkg0); @@ -1124,10 +1182,6 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency * } } - if (ss->num_decisions > 0 && - has_inherited_state(decision_to_name(&ss->decisions[ss->num_decisions]))) - recalculate_inherted_name_state(name); - if (!dep->optional) ns->requirers--; @@ -1164,13 +1218,24 @@ static int expand_branch(struct apk_solver_state *ss) else if (ns->chosen->topology_hard > topology0) pkg0 = ns->chosen, topology0 = pkg0->topology_hard; + if (!ns->name_touched) + continue; + ns->name_touched = 0; + score = ss->score; + addscore(&score, &ss->minimum_penalty); subscore(&score, &ns->minimum_penalty); if (!ns->none_excluded) { get_unassigned_score(name, &pkgscore); - if (cmpscore2(&score, &pkgscore, &ss->best_score) >= 0) + if (cmpscore2(&score, &pkgscore, &ss->best_score) >= 0) { + dbg_printf("%s: pruning none, score too high "SCORE_FMT"+"SCORE_FMT">="SCORE_FMT"\n", + name->name, + SCORE_PRINTF(&score), + SCORE_PRINTF(&pkgscore), + SCORE_PRINTF(&ss->best_score)); return push_decision(ss, name, NULL, DECISION_EXCLUDE, BRANCH_NO, FALSE); + } } for (i = 0; i < name->pkgs->num; i++) { @@ -1181,7 +1246,7 @@ static int expand_branch(struct apk_solver_state *ss) ss->topology_position < pkg0->topology_hard) continue; - get_topology_score(ss, ns, pkg0, 0, &pkgscore); + get_topology_score(ss, ns, pkg0, &pkgscore); if (cmpscore2(&score, &pkgscore, &ss->best_score) >= 0) return push_decision(ss, name, pkg0, DECISION_EXCLUDE, BRANCH_NO, FALSE); } @@ -1197,11 +1262,6 @@ static int expand_branch(struct apk_solver_state *ss) * provider candidate */ name = pkg0->name; ns = name_to_ns(name); - dbg_printf("expand_branch: %-30s score: "SCORE_FMT"\tminpenalty: "SCORE_FMT"\tbest: "SCORE_FMT"\n", - pkg0->name->name, - SCORE_PRINTF(&ss->score), - SCORE_PRINTF(&ss->minimum_penalty), - SCORE_PRINTF(&ss->best_score)); if (!ns->none_excluded) { struct apk_package_state *ps0 = pkg_to_ps(pkg0); @@ -1212,6 +1272,12 @@ static int expand_branch(struct apk_solver_state *ss) return push_decision(ss, name, NULL, primary_decision, BRANCH_YES, FALSE); } + dbg_printf("expand_branch: "PKG_VER_FMT" score: "SCORE_FMT"\tminpenalty: "SCORE_FMT"\tbest: "SCORE_FMT"\n", + PKG_VER_PRINTF(pkg0), + SCORE_PRINTF(&ss->score), + SCORE_PRINTF(&ss->minimum_penalty), + SCORE_PRINTF(&ss->best_score)); + preferred_pinning = ns->preferred_pinning ?: APK_DEFAULT_PINNING_MASK; allowed_pinning = ns->allowed_pinning | preferred_pinning; allowed_repos = get_pinning_mask_repos(ss->db, allowed_pinning); @@ -1270,6 +1336,8 @@ static void record_solution(struct apk_solver_state *ss) unsigned short pinning; unsigned int repos; + d->found_solution = 1; + if (pkg == NULL) { dbg_printf("record_solution: %s: NOTHING\n", decision_to_name(d)->name); @@ -1290,8 +1358,8 @@ static void record_solution(struct apk_solver_state *ss) ASSERT(n < ss->assigned_names, "Name assignment overflow\n"); ss->best_solution->item[n++] = (struct apk_solution_entry){ .pkg = pkg, - .reinstall = !!((ns->solver_flags_local | ns->solver_flags_inherited | - ss->solver_flags) & APK_SOLVERF_REINSTALL), + .reinstall = ns->inherited_reinstall || + ((ns->solver_flags_local | ss->solver_flags) & APK_SOLVERF_REINSTALL), .repository_tag = get_tag(db, pinning, repos), }; } @@ -1424,7 +1492,7 @@ void apk_solver_set_name_flags(struct apk_name *name, unsigned short solver_flags, unsigned short solver_flags_inheritable) { - struct apk_name_state *ns = name_to_ns(name); + struct apk_name_state *ns = name_to_ns_alloc(name); ns->solver_flags_local = solver_flags; ns->solver_flags_local_mask = solver_flags_inheritable; } @@ -1452,8 +1520,6 @@ int apk_solver_solve(struct apk_database *db, ss->topology_position = -1; ss->best_score = (struct apk_score){ .conflicts = -1, - .non_preferred_actions = -1, - .preference = -1, }; list_init(&ss->unsolved_list_head); |