summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/solver.c152
1 files changed, 97 insertions, 55 deletions
diff --git a/src/solver.c b/src/solver.c
index 9231fd9..5f1c635 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -46,6 +46,7 @@ struct apk_name_state {
struct list_head unsolved_list;
struct apk_name *name;
struct apk_package *chosen;
+ struct apk_score minimum_penalty;
unsigned int topology_last_touched;
unsigned int allowed_repos, preferred_repos;
unsigned short requirers;
@@ -67,10 +68,9 @@ struct apk_solver_state {
struct list_head unsolved_list_head;
struct apk_package *latest_decision;
unsigned int topology_position;
- unsigned int penalty_topology;
unsigned int assigned_names;
struct apk_score score;
- struct apk_score penalty_score;
+ struct apk_score minimum_penalty;
unsigned int solver_flags : 4;
unsigned int refresh_name_states : 1;
@@ -84,6 +84,44 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
int flags);
+static void addscore(struct apk_score *a, struct apk_score *b)
+{
+ a->unsatisfiable += b->unsatisfiable;
+ a->preference += b->preference;
+}
+
+static void subscore(struct apk_score *a, struct apk_score *b)
+{
+ a->unsatisfiable -= b->unsatisfiable;
+ a->preference -= b->preference;
+}
+
+static int cmpscore(struct apk_score *a, struct apk_score *b)
+{
+ if (a->unsatisfiable < b->unsatisfiable)
+ return -1;
+ if (a->unsatisfiable > b->unsatisfiable)
+ return 1;
+ if (a->preference < b->preference)
+ return -1;
+ if (a->preference > b->preference)
+ return 1;
+ return 0;
+}
+
+static int cmpscore2(struct apk_score *a1, struct apk_score *a2, struct apk_score *b)
+{
+ if (a1->unsatisfiable+a2->unsatisfiable < b->unsatisfiable)
+ return -1;
+ if (a1->unsatisfiable+a2->unsatisfiable > b->unsatisfiable)
+ 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_package_state *pkg_to_ps(struct apk_package *pkg)
{
return (struct apk_package_state*) pkg->state_ptr;
@@ -327,6 +365,12 @@ static int compare_package_preference(unsigned short solver_flags,
return -1;
}
+ /* upgrading, prefer the installed package */
+ if (pkgA->ipkg != NULL && pkgB->ipkg == NULL)
+ return 1;
+ if (pkgB->ipkg != NULL && pkgA->ipkg == NULL)
+ return -1;
+
/* prefer the one with lowest available repository */
return ffsl(pkgB->repos) - ffsl(pkgA->repos);
}
@@ -388,11 +432,19 @@ static int install_if_missing(struct apk_solver_state *ss, struct apk_package *p
static int update_name_state(struct apk_solver_state *ss, struct apk_name *name)
{
struct apk_name_state *ns = name_to_ns(name);
- struct apk_package *best_pkg = NULL;
+ struct apk_package *best_pkg = NULL, *preferred_pkg = NULL;
+ struct apk_package_state *preferred_ps = NULL;
unsigned int best_topology = 0;
unsigned int allowed_repos = ns->allowed_repos | ss->db->repo_tags[0].allowed_repos;
+ unsigned int preferred_repos = ns->preferred_repos;
+ unsigned short name_flags = ns->solver_flags_local
+ | ns->solver_flags_inherited
+ | ss->solver_flags;
int i, options = 0, skipped_options = 0;
+ subscore(&ss->minimum_penalty, &ns->minimum_penalty);
+ ns->minimum_penalty = (struct apk_score) { 0, 0 };
+
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);
@@ -408,6 +460,16 @@ static int update_name_state(struct apk_solver_state *ss, struct apk_name *name)
continue;
}
+ if ((preferred_pkg == NULL) ||
+ (ps0->conflicts < preferred_ps->conflicts) ||
+ (ps0->conflicts == preferred_ps->conflicts &&
+ compare_package_preference(name_flags,
+ preferred_repos,
+ pkg0, preferred_pkg) > 0)) {
+ preferred_pkg = pkg0;
+ preferred_ps = ps0;
+ }
+
if (ns->requirers == 0 && ns->install_ifs != 0 &&
install_if_missing(ss, pkg0)) {
skipped_options++;
@@ -447,8 +509,22 @@ static int update_name_state(struct apk_solver_state *ss, struct apk_name *name)
best_topology);
if (!list_hashed(&ns->unsolved_list))
list_add(&ns->unsolved_list, &ss->unsolved_list_head);
- if (!ns->locked)
+ if (!ns->locked) {
ns->chosen = best_pkg;
+ if (preferred_pkg != NULL &&
+ preferred_ps->conflicts < ns->requirers) {
+ ns->minimum_penalty = (struct apk_score) {
+ .unsatisfiable = preferred_ps->conflicts,
+ .preference = get_preference(ss, preferred_pkg, FALSE),
+ };
+ } else {
+ ns->minimum_penalty = (struct apk_score) {
+ .unsatisfiable = ns->requirers,
+ .preference = name->pkgs->num,
+ };
+ }
+ addscore(&ss->minimum_penalty, &ns->minimum_penalty);
+ }
}
return options + skipped_options;
@@ -557,8 +633,10 @@ static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
}
ss->latest_decision = pkg;
- dbg_printf("push_decision: adding new BRANCH at topology_position %d\n",
- ss->topology_position);
+ dbg_printf("push_decision: adding new BRANCH at topology_position %d (score: unsatisfied %d, preference %d)\n",
+ ss->topology_position,
+ ss->score.unsatisfiable,
+ ss->score.preference);
if (ps->flags & APK_PKGSTF_INSTALLIF)
dbg_printf("triggers due to " PKG_VER_FMT "\n",
@@ -585,11 +663,11 @@ static int next_branch(struct apk_solver_state *ss)
ss->latest_decision = ps->backtrack;
ss->refresh_name_states = 1;
} else {
+ undo_decision(ss, pkg, ps);
+
dbg_printf("next_branch: swapping BRANCH at topology_position %d\n",
ss->topology_position);
- undo_decision(ss, pkg, ps);
-
ps->flags |= APK_PKGSTF_ALT_BRANCH;
ps->flags ^= APK_PKGSTF_INSTALL;
@@ -765,26 +843,17 @@ static int expand_branch(struct apk_solver_state *ss)
}
ss->refresh_name_states = 0;
if (pkg0 == NULL) {
- struct apk_score penalty_score = {0,0};
- int penalty_topology = 0;
-
list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
- if (!ns->locked) {
- penalty_score.unsatisfiable += ns->requirers;
- penalty_score.preference += ns->name->pkgs->num;
- if (penalty_topology < ns->topology_last_touched)
- penalty_topology = ns->topology_last_touched;
- }
- }
- if (ss->penalty_topology < penalty_topology) {
- ss->penalty_topology = penalty_topology;
- ss->penalty_score = penalty_score;
+ if (ns->locked)
+ continue;
+
+ ss->score.unsatisfiable += ns->requirers;
+ ss->score.preference += ns->name->pkgs->num;
}
- ss->score.unsatisfiable += penalty_score.unsatisfiable;
- ss->score.preference += penalty_score.preference;
dbg_printf("expand_branch: list is empty (%d unsatisfied)\n",
ss->score.unsatisfiable);
+
return 1;
}
@@ -963,32 +1032,6 @@ static void apk_solver_free(struct apk_database *db)
apk_hash_foreach(&db->available.packages, free_package, NULL);
}
-static int cmpscore(struct apk_score *a, struct apk_score *b)
-{
- if (a->unsatisfiable < b->unsatisfiable)
- return -1;
- if (a->unsatisfiable > b->unsatisfiable)
- return 1;
- if (a->preference < b->preference)
- return -1;
- if (a->preference > b->preference)
- return 1;
- return 0;
-}
-
-static int cmpscore2(struct apk_score *a1, struct apk_score *a2, struct apk_score *b)
-{
- if (a1->unsatisfiable+a2->unsatisfiable < b->unsatisfiable)
- return -1;
- if (a1->unsatisfiable+a2->unsatisfiable > b->unsatisfiable)
- return 1;
- if (a1->preference+a2->preference < b->preference)
- return -1;
- if (a1->preference+a2->preference > b->preference)
- return 1;
- return 0;
-}
-
int apk_solver_solve(struct apk_database *db,
unsigned short solver_flags,
struct apk_dependency_array *world,
@@ -1015,13 +1058,12 @@ int apk_solver_solve(struct apk_database *db,
foreach_dependency(ss, world, apply_constraint);
zero_score = ss->score;
- do {
- if (ss->topology_position <= ss->penalty_topology) {
- ss->penalty_score = zero_score;
- ss->penalty_topology = 0;
- }
+ dbg_printf("solver_solve: zero score: %d unsatisfiable, %d preference\n",
+ zero_score.unsatisfiable,
+ zero_score.preference);
- if (cmpscore2(&ss->score, &ss->penalty_score, &ss->best_score) < 0) {
+ do {
+ if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) < 0) {
r = expand_branch(ss);
if (r) {
dbg_printf("solution with: %d unsatisfiable, %d preference\n",
generated by cgit v1.2.3-60-g2f50 (git 2.42.0) at 2024-07-24 01:21:19 +0000