summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/solver.c98
1 files changed, 57 insertions, 41 deletions
diff --git a/src/solver.c b/src/solver.c
index fbe50e8..7d5a5b3 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -35,7 +35,6 @@ struct apk_score {
struct apk_package_state {
struct apk_package *backtrack;
unsigned int topology_soft;
- struct apk_score saved_score;
unsigned short conflicts;
unsigned availability_checked : 1;
unsigned unavailable : 1;
@@ -441,7 +440,7 @@ static int install_if_missing(struct apk_solver_state *ss, struct apk_package *p
return missing;
}
-static int check_if_package_unavailable(struct apk_solver_state *ss, struct apk_package *pkg)
+static int check_if_package_unavailable(struct apk_solver_state *ss, struct apk_package *pkg, int do_check)
{
struct apk_name *name = pkg->name;
struct apk_package_state *ps = pkg_to_ps(pkg);
@@ -454,7 +453,7 @@ static int check_if_package_unavailable(struct apk_solver_state *ss, struct apk_
return 0;
/* done already? */
- if (ps->availability_checked)
+ if (ps->availability_checked && !do_check)
return ps->unavailable;
/* and it's not available, we can't use it */
@@ -499,7 +498,7 @@ static int update_name_state(struct apk_solver_state *ss, struct apk_name *name)
if (ps0 == NULL ||
ss->topology_position < pkg0->topology_hard ||
ps0->locked ||
- check_if_package_unavailable(ss, pkg0))
+ check_if_package_unavailable(ss, pkg0, 0))
continue;
options++;
@@ -600,21 +599,21 @@ static solver_result_t apply_decision(struct apk_solver_state *ss,
{
struct apk_name *name = pkg->name;
struct apk_name_state *ns = name_to_ns(name);
+ unsigned short preference;
dbg_printf("-->apply_decision: " PKG_VER_FMT " %s\n", PKG_VER_PRINTF(pkg),
(ps->flags & APK_PKGSTF_INSTALL) ? "INSTALL" : "NO_INSTALL");
if (ps->flags & APK_PKGSTF_INSTALL) {
- unsigned short preference;
-
subscore(&ss->minimum_penalty, &ns->minimum_penalty);
ns->minimum_penalty = (struct apk_score) { 0, 0 };
preference = get_preference(ss, pkg, FALSE);
ss->score.unsatisfiable += ps->conflicts;
ss->score.preference += preference;
- if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) >= 0) {
- dbg_printf("install causing {%d,%d}, penalty too big: {%d,%d}+{%d,%d}>={%d,%d}\n",
+ if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) >= 0 ||
+ check_if_package_unavailable(ss, pkg, 1)) {
+ dbg_printf("install causing {%d,%d}, penalty too big (or unavailable %d): {%d,%d}+{%d,%d}>={%d,%d}\n",
ps->conflicts, preference,
ss->score.unsatisfiable, ss->score.preference,
ss->minimum_penalty.unsatisfiable, ss->minimum_penalty.preference,
@@ -639,7 +638,7 @@ static solver_result_t apply_decision(struct apk_solver_state *ss,
foreach_dependency(ss, pkg->depends, apply_constraint);
foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
} else {
- if (ns->locked == 0 && update_name_state(ss, pkg->name) == 0) {
+ if (update_name_state(ss, pkg->name) == 0) {
subscore(&ss->minimum_penalty, &ns->minimum_penalty);
ns->minimum_penalty = (struct apk_score) { 0, 0 };
@@ -668,7 +667,8 @@ static void undo_decision(struct apk_solver_state *ss,
struct apk_package *pkg,
struct apk_package_state *ps)
{
- struct apk_name_state *ns = name_to_ns(pkg->name);
+ struct apk_name *name = pkg->name;
+ struct apk_name_state *ns = name_to_ns(name);
dbg_printf("-->undo_decision: " PKG_VER_FMT " %s\n", PKG_VER_PRINTF(pkg),
(ps->flags & APK_PKGSTF_INSTALL) ? "INSTALL" : "NO_INSTALL");
@@ -680,22 +680,28 @@ static void undo_decision(struct apk_solver_state *ss,
if (ps->flags & APK_PKGSTF_INSTALL) {
if (ps->install_applied) {
+ unsigned short preference;
+
ps->install_applied = 0;
ss->assigned_names--;
foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
foreach_dependency(ss, pkg->depends, undo_constraint);
- }
- ns->locked = 0;
- ns->chosen = NULL;
+ preference = get_preference(ss, pkg, FALSE);
+ ss->score.unsatisfiable -= ps->conflicts;
+ ss->score.preference -= preference;
+ }
} else {
- /* UNINSTALL decision removed - either name is unlocked
- * or locked to none */
- ns->locked = 0;
- ns->chosen = NULL;
+ if (ns->locked) {
+ /* UNINSTALL decision removed - either name is unlocked
+ * or locked to none */
+ ss->score.unsatisfiable -= ns->requirers;
+ ss->score.preference -= name->pkgs->num;
+ }
}
+ ns->locked = 0;
+ ns->chosen = NULL;
- ss->score = ps->saved_score;
update_name_state(ss, pkg->name);
}
@@ -705,16 +711,15 @@ static solver_result_t push_decision(struct apk_solver_state *ss, struct apk_pac
struct apk_package_state *ps = pkg_to_ps(pkg);
ps->backtrack = ss->latest_decision;
- ps->locked = 1;
ps->flags = flags;
- ps->saved_score = ss->score;
+ ps->locked = 1;
+ ps->handle_install_if = 0;
if (ps->topology_soft < ss->topology_position) {
if (flags & APK_PKGSTF_INSTALL)
ps->handle_install_if = 1;
ss->topology_position = ps->topology_soft;
} else {
- ps->handle_install_if = 0;
ss->topology_position = pkg->topology_hard;
}
ss->latest_decision = pkg;
@@ -814,14 +819,19 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
if (ns->locked) {
if (ns->chosen)
dbg_printf("%s: locked to " PKG_VER_FMT " already\n",
- dep->name->name, PKG_VER_PRINTF(ns->chosen));
+ name->name, PKG_VER_PRINTF(ns->chosen));
else
dbg_printf("%s: locked to empty\n",
- dep->name->name);
+ name->name);
if (!apk_dep_is_satisfied(dep, ns->chosen))
ss->score.unsatisfiable++;
return;
}
+ if (name->pkgs->num == 0) {
+ if (!dep->optional)
+ ss->score.unsatisfiable++;
+ return;
+ }
if (dep->repository_tag) {
dbg_printf("%s: adding pinnings %d\n",
@@ -830,6 +840,12 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
ns->allowed_pinning |= BIT(dep->repository_tag);
}
+ if (ss->latest_decision != NULL) {
+ dbg_printf("%s: inheriting flags and pinning from %s\n",
+ name->name, ss->latest_decision->name->name);
+ inherit_name_state(name, ss->latest_decision->name);
+ }
+
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);
@@ -846,12 +862,6 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
}
}
- if (ss->latest_decision != NULL) {
- dbg_printf("%s: inheriting flags and pinning from %s\n",
- name->name, ss->latest_decision->name->name);
- inherit_name_state(name, ss->latest_decision->name);
- }
-
if (!dep->optional)
ns->requirers++;
@@ -867,11 +877,18 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
if (ns->locked) {
if (ns->chosen != NULL) {
dbg_printf(PKG_VER_FMT " selected already for %s\n",
- PKG_VER_PRINTF(ns->chosen), dep->name->name);
+ PKG_VER_PRINTF(ns->chosen), name->name);
} else {
dbg_printf("%s selected to not be satisfied\n",
- dep->name->name);
+ name->name);
}
+ if (!apk_dep_is_satisfied(dep, ns->chosen))
+ ss->score.unsatisfiable--;
+ return;
+ }
+ if (name->pkgs->num == 0) {
+ if (!dep->optional)
+ ss->score.unsatisfiable--;
return;
}
@@ -919,13 +936,6 @@ static int expand_branch(struct apk_solver_state *ss)
pkg0 = ns->chosen, topology0 = pkg0->topology_hard;
}
if (pkg0 == NULL) {
- list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
- if (ns->locked)
- continue;
- ss->score.unsatisfiable += ns->requirers;
- ss->score.preference += ns->name->pkgs->num;
- }
-
dbg_printf("expand_branch: list is empty (%d unsatisfied)\n",
ss->score.unsatisfiable);
return SOLVERR_SOLUTION;
@@ -1011,7 +1021,6 @@ static void record_solution(struct apk_solver_state *ss)
pkg = ps->backtrack;
}
apk_solution_array_resize(&ss->best_solution, i);
- ss->best_score = ss->score;
}
static int compare_solution_entry(const void *p1, const void *p2)
@@ -1185,14 +1194,21 @@ int apk_solver_solve(struct apk_database *db,
/* need EXPAND if here, can return SOLUTION|PRUNED|EXPAND */
r = expand_branch(ss);
if (r == SOLVERR_SOLUTION) {
+ struct apk_score score;
+
dbg_printf("solution with: %d unsatisfiable, %d preference\n",
ss->score.unsatisfiable,
ss->score.preference);
- if (cmpscore(&ss->score, &ss->best_score) < 0)
+ score = ss->score;
+ addscore(&score, &ss->minimum_penalty);
+
+ if (cmpscore(&score, &ss->best_score) < 0) {
record_solution(ss);
+ ss->best_score = score;
+ }
- if (cmpscore(&zero_score, &ss->score) >= 0) {
+ if (cmpscore(&zero_score, &score) >= 0) {
/* found solution - it is optimal because we permutate
* each preferred local option first, and permutations
* happen in topologally sorted order. */
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2024-11-03 00:45:12 +0000