summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTimo Teräs <timo.teras@iki.fi>2012-02-18 11:54:17 +0200
committerTimo Teräs <timo.teras@iki.fi>2012-02-20 13:02:09 +0200
commit6ae573887df6722a94ba589a7ee1675e7ea573d6 (patch)
tree5f563a8e10a1692ecf4120289e6f51787e9e1ba5
parenta9d526836e1160b2233bf26a2d1dd6584dec5dd4 (diff)
downloadapk-tools-6ae573887df6722a94ba589a7ee1675e7ea573d6.tar.gz
apk-tools-6ae573887df6722a94ba589a7ee1675e7ea573d6.tar.bz2
apk-tools-6ae573887df6722a94ba589a7ee1675e7ea573d6.tar.xz
apk-tools-6ae573887df6722a94ba589a7ee1675e7ea573d6.zip
solver: rewrite backtracking and scoring system
* properly do absolute scoring now, the previous scoring where preference could get reduced could have caused incorrect early pruning of search tree * backtracking is now separated from package state, and first branching point is the decision if a name is left unassigned or if something _has_ to be assigned. this allows multiple future search tree optimizations like handling of common dependencies early. * merge common dependency names early to provide deeper forward checking.
-rw-r--r--src/apk_defines.h5
-rw-r--r--src/solver.c1096
2 files changed, 695 insertions, 406 deletions
diff --git a/src/apk_defines.h b/src/apk_defines.h
index 3c72c73..2ef0c3b 100644
--- a/src/apk_defines.h
+++ b/src/apk_defines.h
@@ -257,6 +257,11 @@ static inline int list_hashed(const struct list_head *n)
return n->next != n && n->next != NULL;
}
+static inline int list_empty(const struct list_head *n)
+{
+ return n->next == n;
+}
+
#define list_entry(ptr, type, member) container_of(ptr,type,member)
#define list_for_each(pos, head) \
diff --git a/src/solver.c b/src/solver.c
index 0283791..a27b4d4 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -1,7 +1,7 @@
/* solver.c - Alpine Package Keeper (APK)
* A backtracking, forward checking dependency graph solver.
*
- * Copyright (C) 2008-2011 Timo Teräs <timo.teras@iki.fi>
+ * Copyright (C) 2008-2012 Timo Teräs <timo.teras@iki.fi>
* All rights reserved.
*
* This program is free software; you can redistribute it and/or modify it
@@ -16,68 +16,116 @@
#include "apk_print.h"
-#if 0
+//#define DEBUG_PRINT
+#define DEBUG_CHECKS
+
+#ifdef DEBUG_PRINT
#include <stdio.h>
#define dbg_printf(args...) fprintf(stderr, args)
#else
#define dbg_printf(args...)
#endif
-#define APK_PKGSTF_NOINSTALL 0
-#define APK_PKGSTF_INSTALL 1
-#define APK_PKGSTF_ALT_BRANCH 2
+#if defined(DEBUG_PRINT) || defined(DEBUG_CHECKS)
+#define ASSERT(cond, fmt...) \
+ if (!(cond)) { fprintf(stderr, fmt); *(char*)NULL = 0; }
+#else
+#define ASSERT(cond, fmt...)
+#endif
struct apk_score {
- unsigned short unsatisfiable;
+ unsigned short conflicts;
+ unsigned short non_preferred_actions;
unsigned short preference;
};
+#define SCORE_FMT "{%d/%d/%d}"
+#define SCORE_PRINTF(s) (s)->conflicts, (s)->non_preferred_actions, (s)->preference
+
+enum {
+ DECISION_ASSIGN = 0,
+ DECISION_EXCLUDE
+};
+
+enum {
+ BRANCH_NO,
+ BRANCH_YES,
+};
+
+struct apk_decision {
+ union {
+ struct apk_name *name;
+ struct apk_package *pkg;
+ };
+#ifdef DEBUG_CHECKS
+ struct apk_score saved_score;
+#endif
+
+ unsigned no_package : 1;
+ unsigned type : 1;
+ unsigned branching_point : 1;
+ unsigned topology_position : 1;
+};
+
struct apk_package_state {
- struct apk_package *backtrack;
unsigned int topology_soft;
unsigned short conflicts;
+ unsigned char preference;
unsigned availability_checked : 1;
unsigned unavailable : 1;
unsigned install_applied : 1;
unsigned handle_install_if : 1;
unsigned locked : 1;
- unsigned flags : 2;
};
struct apk_name_state {
struct list_head unsolved_list;
struct apk_name *name;
struct apk_package *chosen;
+
struct apk_score minimum_penalty;
+ unsigned short merge_index;
+ unsigned short prerequires;
unsigned short requirers;
unsigned short install_ifs;
unsigned short preferred_pinning;
unsigned short allowed_pinning;
- unsigned int solver_flags_local : 4;
- unsigned int solver_flags_local_mask : 4;
- unsigned int solver_flags_inherited : 4;
+ unsigned solver_flags_local : 4;
+ unsigned solver_flags_local_mask : 4;
+ unsigned solver_flags_inherited : 4;
- unsigned int locked : 1;
- unsigned int in_changeset : 1;
+ /* one time prepare/finish flags */
+ unsigned decision_counted : 1;
+ unsigned originally_installed : 1;
+ unsigned prepared : 1;
+ unsigned in_changeset : 1;
+
+ /* dynamic state flags */
+ unsigned none_excluded : 1;
+ unsigned locked : 1;
};
struct apk_solver_state {
struct apk_database *db;
- unsigned num_topology_positions;
+ struct apk_decision *decisions;
struct list_head unsolved_list_head;
- struct apk_package *latest_decision;
+
+ unsigned int num_topology_positions;
+ unsigned int num_decisions, max_decisions;
unsigned int topology_position;
unsigned int assigned_names;
- struct apk_score score;
- struct apk_score minimum_penalty;
-
- unsigned int solver_flags : 4;
struct apk_solution_array *best_solution;
+
+ struct apk_score score;
+ struct apk_score minimum_penalty;
struct apk_score best_score;
+
+ unsigned solver_flags : 4;
+ unsigned impossible_constraints : 1;
};
typedef enum {
@@ -89,45 +137,66 @@ typedef enum {
static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep);
static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *dep);
-static solver_result_t push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
- int flags);
+static solver_result_t push_decision(struct apk_solver_state *ss,
+ struct apk_name *name,
+ struct apk_package *pkg,
+ int primary_decision,
+ int branching_point,
+ int topology_position);
static void addscore(struct apk_score *a, struct apk_score *b)
{
- a->unsatisfiable += b->unsatisfiable;
+ a->conflicts += b->conflicts;
+ a->non_preferred_actions += b->non_preferred_actions;
a->preference += b->preference;
}
static void subscore(struct apk_score *a, struct apk_score *b)
{
- a->unsatisfiable -= b->unsatisfiable;
+ a->conflicts -= b->conflicts;
+ a->non_preferred_actions -= b->non_preferred_actions;
a->preference -= b->preference;
}
static int cmpscore(struct apk_score *a, struct apk_score *b)
{
- if (a->unsatisfiable < b->unsatisfiable)
+ if (a->conflicts < b->conflicts)
+ return -1;
+ if (a->conflicts > b->conflicts)
+ return 1;
+
+ if (a->non_preferred_actions < b->non_preferred_actions)
return -1;
- if (a->unsatisfiable > b->unsatisfiable)
+ if (a->non_preferred_actions > b->non_preferred_actions)
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;
+ struct apk_score tmp = *a1;
+ addscore(&tmp, a2);
+ return cmpscore(&tmp, b);
+}
+
+static struct apk_name *decision_to_name(struct apk_decision *d)
+{
+ if (d->no_package)
+ return d->name;
+ return d->pkg->name;
+}
+
+static struct apk_package *decision_to_pkg(struct apk_decision *d)
+{
+ if (d->no_package)
+ return NULL;
+ return d->pkg;
}
static struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
@@ -214,9 +283,149 @@ static void foreach_rinstall_if_pkg(
}
}
+static unsigned int get_pinning_mask_repos(struct apk_database *db, unsigned short pinning_mask)
+{
+ unsigned int repository_mask = 0;
+ int i;
+
+ for (i = 0; i < db->num_repo_tags && pinning_mask; i++) {
+ if (!(BIT(i) & pinning_mask))
+ continue;
+ pinning_mask &= ~BIT(i);
+ repository_mask |= db->repo_tags[i].allowed_repos;
+ }
+ return repository_mask;
+}
+
+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)) {
+ /* 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++;
+ }
+
+ repos = pkg->repos | (pkg->ipkg ? ss->db->repo_tags[pkg->ipkg->repository_tag].allowed_repos : 0);
+ preferred_pinning = ns->preferred_pinning ?: APK_DEFAULT_PINNING_MASK;
+ preferred_repos = get_pinning_mask_repos(ss->db, preferred_pinning);
+
+ if (!(repos & preferred_repos))
+ score.non_preferred_actions++;
+
+ if (lock_score) {
+ 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 = score;
+}
+
+static int is_topology_optimum(struct apk_solver_state *ss,
+ struct apk_package *pkg)
+{
+ struct apk_name *name = pkg->name;
+ struct apk_name_state *ns = name_to_ns(name);
+ struct apk_score score;
+ int i;
+
+ /* FIXME: should not use absolute topology score */
+ get_topology_score(ss, ns, pkg, 1, &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);
+ struct apk_score score0;
+
+ if (pkg0 == pkg)
+ continue;
+
+ if (ps0 == NULL || ps0->locked ||
+ ss->topology_position < pkg->topology_hard)
+ continue;
+
+ get_topology_score(ss, ns, pkg0, 1, &score0);
+ if (cmpscore(&score0, &score) < 0)
+ return 0;
+ }
+
+ return 1;
+}
+
+static int compare_absolute_package_preference(
+ struct apk_package *pkgA,
+ struct apk_package *pkgB)
+{
+ /* specified on command line directly */
+ if (pkgA->filename && !pkgB->filename)
+ return 1;
+ if (pkgB->filename && !pkgA->filename)
+ return -1;
+
+ /* upgrading, or neither of the package is installed, so
+ * we just fall back comparing to versions */
+ switch (apk_pkg_version_compare(pkgA, pkgB)) {
+ case APK_VERSION_GREATER:
+ return 1;
+ case APK_VERSION_LESS:
+ return -1;
+ }
+
+ /* 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);
+}
+
+static void calculate_pkg_preference(struct apk_package *pkg)
+{
+ struct apk_name *name = pkg->name;
+ struct apk_package_state *ps = pkg_to_ps(pkg);
+ int i;
+
+ for (i = 0; i < name->pkgs->num; i++) {
+ struct apk_package *pkg0 = name->pkgs->item[i];
+ if (pkg == pkg0)
+ continue;
+ if (compare_absolute_package_preference(pkg, pkg0) < 0)
+ ps->preference++;
+ }
+}
+
static void sort_hard_dependencies(struct apk_solver_state *ss, struct apk_package *pkg)
{
struct apk_package_state *ps;
+ struct apk_name_state *ns;
if (pkg->state_ptr == NULL)
pkg->state_ptr = calloc(1, sizeof(struct apk_package_state));
@@ -226,11 +435,20 @@ static void sort_hard_dependencies(struct apk_solver_state *ss, struct apk_packa
return;
pkg->topology_hard = -1;
ps->topology_soft = -1;
+ calculate_pkg_preference(pkg);
/* Consider hard dependencies only */
foreach_dependency_pkg(ss, pkg->depends, sort_hard_dependencies);
foreach_dependency_pkg(ss, pkg->install_if, sort_hard_dependencies);
+ ss->max_decisions++;
+
+ ns = name_to_ns(pkg->name);
+ if (!ns->decision_counted) {
+ ss->max_decisions++;
+ ns->decision_counted = 1;
+ }
+
ps->topology_soft = pkg->topology_hard = ++ss->num_topology_positions;
dbg_printf(PKG_VER_FMT ": topology_hard=%d\n",
PKG_VER_PRINTF(pkg), pkg->topology_hard);
@@ -302,128 +520,6 @@ static void foreach_dependency(struct apk_solver_state *ss, struct apk_dependenc
func(ss, &deps->item[i]);
}
-static unsigned int get_pinning_mask_repos(struct apk_database *db, unsigned short pinning_mask)
-{
- unsigned int repository_mask = 0;
- int i;
-
- for (i = 0; i < db->num_repo_tags && pinning_mask; i++) {
- if (!(BIT(i) & pinning_mask))
- continue;
- pinning_mask &= ~BIT(i);
- repository_mask |= db->repo_tags[i].allowed_repos;
- }
- return repository_mask;
-}
-
-static int compare_package_preference(unsigned short solver_flags,
- unsigned int preferred_repos,
- unsigned int allowed_repos,
- struct apk_package *pkgA,
- struct apk_package *pkgB,
- struct apk_database *db)
-{
- unsigned int a_repos, b_repos;
-
- /* specified on command line directly */
- if (pkgA->filename && !pkgB->filename)
- return 1;
- if (pkgB->filename && !pkgA->filename)
- return -1;
-
- /* Is there a difference in pinning preference? */
- a_repos = pkgA->repos | (pkgA->ipkg ? db->repo_tags[pkgA->ipkg->repository_tag].allowed_repos : 0);
- b_repos = pkgB->repos | (pkgB->ipkg ? db->repo_tags[pkgB->ipkg->repository_tag].allowed_repos : 0);
- if ((a_repos & preferred_repos) && !(b_repos & preferred_repos))
- return 1;
- if ((b_repos & preferred_repos) && !(a_repos & preferred_repos))
- return -1;
-
- /* Difference in allowed repositories? */
- if ((a_repos & allowed_repos) && !(b_repos & allowed_repos))
- return 1;
- if ((b_repos & allowed_repos) && !(a_repos & allowed_repos))
- return -1;
-
- if (solver_flags & APK_SOLVERF_AVAILABLE) {
- if (pkgA->repos != 0 && pkgB->repos == 0)
- return 1;
- if (pkgB->repos != 0 && pkgA->repos == 0)
- return -1;
- }
-
- if (!(solver_flags & APK_SOLVERF_UPGRADE)) {
- /* not upgrading, prefer the installed package */
- if (pkgA->ipkg != NULL && pkgB->ipkg == NULL)
- return 1;
- if (pkgB->ipkg != NULL && pkgA->ipkg == NULL)
- return -1;
- }
-
- /* upgrading, or neither of the package is installed, so
- * we just fall back comparing to versions */
- switch (apk_pkg_version_compare(pkgA, pkgB)) {
- case APK_VERSION_GREATER:
- return 1;
- case APK_VERSION_LESS:
- 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);
-}
-
-static int get_preference(struct apk_solver_state *ss,
- struct apk_package *pkg,
- int installable_only)
-{
- struct apk_name *name = pkg->name;
- struct apk_name_state *ns = name_to_ns(name);
- unsigned short name_flags = ns->solver_flags_local
- | ns->solver_flags_inherited
- | ss->solver_flags;
- unsigned short preferred_pinning, allowed_pinning;
- unsigned int preferred_repos, allowed_repos;
- unsigned short preference = 0;
- int i, r;
-
- preferred_pinning = ns->preferred_pinning ?: APK_DEFAULT_PINNING_MASK;
- preferred_repos = get_pinning_mask_repos(ss->db, preferred_pinning);
- allowed_pinning = ns->allowed_pinning | preferred_pinning;
- if (preferred_pinning != allowed_pinning)
- allowed_repos = get_pinning_mask_repos(ss->db, allowed_pinning);
- else
- allowed_repos = preferred_repos;
-
- 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);
-
- if (pkg0 == pkg || ps0 == NULL)
- continue;
-
- if (installable_only &&
- (ss->topology_position < pkg0->topology_hard ||
- ps0->locked))
- continue;
-
- r = compare_package_preference(name_flags,
- preferred_repos,
- allowed_repos,
- pkg, pkg0, ss->db);
- if (r < 0)
- preference += -r;
- }
-
- return preference;
-}
-
static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg)
{
struct apk_name_state *ns;
@@ -464,55 +560,116 @@ static int check_if_package_unavailable(struct apk_solver_state *ss, struct apk_
return ps->unavailable;
}
+static void foreach_common_dependency(
+ struct apk_solver_state *ss, struct apk_name *name,
+ void (*cb)(struct apk_solver_state *ss, struct apk_name *common_dependency))
+{
+ struct apk_name *name0;
+ struct apk_name_state *ns0;
+ struct apk_package *pkg;
+ struct apk_package_state *ps;
+ struct apk_dependency *dep;
+ int i, j, first_found = -1, last_found = 0;
+
+ for (i = 0; i < name->pkgs->num; i++) {
+ pkg = name->pkgs->item[i];
+ ps = pkg_to_ps(pkg);
+ if (ps == NULL || ps->locked)
+ continue;
+ if (first_found == -1)
+ first_found = i;
+ for (j = 0; j < pkg->depends->num; j++) {
+ dep = &pkg->depends->item[j];
+ if (dep->optional)
+ continue;
+ name0 = dep->name;
+ ns0 = name_to_ns(name0);
+ if (ns0->merge_index == last_found)
+ ns0->merge_index = i + 1;
+ }
+ last_found = i + 1;
+ }
+ if (first_found == -1)
+ return;
+
+ pkg = name->pkgs->item[first_found];
+ for (j = 0; j < pkg->depends->num; j++) {
+ dep = &pkg->depends->item[j];
+ if (dep->optional)
+ continue;
+ name0 = dep->name;
+ ns0 = name_to_ns(name0);
+ if (ns0->merge_index == last_found)
+ cb(ss, name0);
+ ns0->merge_index = 0;
+ }
+}
+
+#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,
+ .preference = name->pkgs->num,
+ };
+}
+
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, *preferred_pkg = NULL;
- struct apk_package_state *preferred_ps = NULL;
+ struct apk_score preferred_score;
unsigned int best_topology = 0;
- unsigned short name_flags = ns->solver_flags_local
- | ns->solver_flags_inherited
- | ss->solver_flags;
- unsigned short preferred_pinning, allowed_pinning;
- unsigned int preferred_repos, allowed_repos;
int i, options = 0;
if (ns->locked)
return ns->chosen != NULL;
- preferred_pinning = ns->preferred_pinning ?: APK_DEFAULT_PINNING_MASK;
- preferred_repos = get_pinning_mask_repos(ss->db, preferred_pinning);
- allowed_pinning = ns->allowed_pinning | preferred_pinning;
- if (preferred_pinning != allowed_pinning)
- allowed_repos = get_pinning_mask_repos(ss->db, allowed_pinning);
- else
- allowed_repos = preferred_repos;
-
subscore(&ss->minimum_penalty, &ns->minimum_penalty);
ns->minimum_penalty = (struct apk_score) { 0, 0 };
+ get_unassigned_score(name, &preferred_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);
+ struct apk_score pkg0_score;
- if (ps0 == NULL ||
+ if (ps0 == NULL || ps0->locked ||
ss->topology_position < pkg0->topology_hard ||
- ps0->locked ||
check_if_package_unavailable(ss, pkg0, 0))
continue;
- options++;
-
/* preferred - currently most optimal for end solution */
- if ((preferred_pkg == NULL) ||
- (ps0->conflicts < preferred_ps->conflicts) ||
- (ps0->conflicts == preferred_ps->conflicts &&
- compare_package_preference(name_flags,
- preferred_repos,
- allowed_repos,
- pkg0, preferred_pkg, ss->db) > 0)) {
+ /* FIXME: should not use absolute topology score */
+ get_topology_score(ss, ns, pkg0, 1, &pkg0_score);
+
+ if (preferred_pkg == NULL ||
+ cmpscore(&pkg0_score, &preferred_score) < 0) {
preferred_pkg = pkg0;
- preferred_ps = ps0;
+ preferred_score = pkg0_score;
}
/* next in topology order - next to get locked in */
@@ -521,47 +678,44 @@ static int update_name_state(struct apk_solver_state *ss, struct apk_name *name)
best_pkg = pkg0, best_topology = ps0->topology_soft;
else if (pkg0->topology_hard > best_topology)
best_pkg = pkg0, best_topology = pkg0->topology_hard;
+
+ options++;
}
- if (ns->requirers == 0 && ns->install_ifs == 0) {
+ if (ns->prerequires == 0 && ns->requirers == 0 && ns->install_ifs == 0) {
+ /* No one really needs this name (anymore). */
if (list_hashed(&ns->unsolved_list)) {
list_del(&ns->unsolved_list);
list_init(&ns->unsolved_list);
- ns->chosen = NULL;
- }
- dbg_printf("%s: deleted from unsolved: %d requirers, %d install_ifs, %d options\n",
- name->name, ns->requirers, ns->install_ifs, options);
- } else {
- if (!list_hashed(&ns->unsolved_list))
- list_add(&ns->unsolved_list, &ss->unsolved_list_head);
-
- 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),
- };
- dbg_printf("%s: min.penalty for name {%d, %d} from pkg " PKG_VER_FMT "\n",
- name->name,
- ns->minimum_penalty.unsatisfiable,
- ns->minimum_penalty.preference,
- PKG_VER_PRINTF(preferred_pkg));
- } else {
- ns->minimum_penalty = (struct apk_score) {
- .unsatisfiable = ns->requirers,
- .preference = name->pkgs->num,
- };
- dbg_printf("%s: min.penalty for name {%d, %d} from no pkg\n",
- name->name,
- ns->minimum_penalty.unsatisfiable,
- ns->minimum_penalty.preference);
}
- addscore(&ss->minimum_penalty, &ns->minimum_penalty);
+ ns->chosen = NULL;
+ dbg_printf("%s: not required\n", name->name);
+ return options + 1;
+ }
- dbg_printf("%s: added to unsolved: %d requirers, %d install_ifs, %d options (next topology %d)\n",
- name->name, ns->requirers, ns->install_ifs,
- options, best_topology);
+ if (!list_hashed(&ns->unsolved_list))
+ list_add_tail(&ns->unsolved_list, &ss->unsolved_list_head);
+
+ /* So far decided that something will be installed for this
+ * name. So assign the minimum penalty, and next position. */
+ ns->chosen = best_pkg;
+ ns->minimum_penalty = preferred_score;
+ addscore(&ss->minimum_penalty, &ns->minimum_penalty);
+
+ dbg_printf("%s: min.pen. " SCORE_FMT ", %d prerequirers, %d requirers, %d install_ifs, %d options (next topology %d)\n",
+ name->name,
+ SCORE_PRINTF(&ns->minimum_penalty),
+ ns->prerequires, ns->requirers, ns->install_ifs,
+ options, best_topology);
+
+ if (!ns->none_excluded) {
+ dbg_printf("%s: none not excluded yet\n", name->name);
+ return options + 1;
+ }
+
+ if (options == 0) {
+ ss->impossible_constraints = 1;
+ dbg_printf("%s: impossible constraints\n", name->name);
}
return options;
@@ -593,70 +747,124 @@ static void untrigger_install_if(struct apk_solver_state *ss,
}
}
+static void increment_prerequires(struct apk_solver_state *ss, struct apk_name *name)
+{
+ struct apk_name_state *ns = name_to_ns(name);
+ ns->prerequires++;
+ update_name_state(ss, name);
+}
+
+static void decrement_prerequires(struct apk_solver_state *ss, struct apk_name *name)
+{
+ struct apk_name_state *ns = name_to_ns(name);
+ ns->prerequires--;
+ update_name_state(ss, name);
+}
+
static solver_result_t apply_decision(struct apk_solver_state *ss,
- struct apk_package *pkg,
- struct apk_package_state *ps)
+ struct apk_decision *d)
{
- struct apk_name *name = pkg->name;
+ struct apk_name *name = decision_to_name(d);
struct apk_name_state *ns = name_to_ns(name);
- unsigned short preference;
+ struct apk_package *pkg = decision_to_pkg(d);
+ struct apk_score score;
- 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) {
- 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 ||
- 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,
- ss->best_score.unsatisfiable, ss->best_score.preference
- );
-
- ss->score.unsatisfiable -= ps->conflicts;
- ss->score.preference -= preference;
- return SOLVERR_PRUNED;
+ ss->impossible_constraints = 0;
+ if (pkg != NULL) {
+ struct apk_package_state *ps = pkg_to_ps(pkg);
+
+ dbg_printf("-->apply_decision: " PKG_VER_FMT " %s\n",
+ PKG_VER_PRINTF(pkg),
+ (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
+
+ ps->locked = 1;
+ ps->handle_install_if = 0;
+
+ if (d->topology_position) {
+ if (ps->topology_soft < ss->topology_position) {
+ if (d->type == DECISION_ASSIGN) {
+ ps->handle_install_if = 1;
+ dbg_printf("triggers due to " PKG_VER_FMT "\n",
+ PKG_VER_PRINTF(pkg));
+ }
+ ss->topology_position = ps->topology_soft;
+ } else {
+ ss->topology_position = pkg->topology_hard;
+ }
}
- ps->install_applied = 1;
- ss->assigned_names++;
- ns->chosen = pkg;
- ns->locked = 1;
+ if (d->type == DECISION_ASSIGN) {
+ subscore(&ss->minimum_penalty, &ns->minimum_penalty);
+ ns->minimum_penalty = (struct apk_score) { 0 };
+
+ get_topology_score(ss, ns, pkg, 1, &score);
+ addscore(&ss->score, &score);
+
+ if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) >= 0 ||
+ check_if_package_unavailable(ss, pkg, 1)) {
+ dbg_printf("install causing "SCORE_FMT", penalty too big: "SCORE_FMT"+"SCORE_FMT">="SCORE_FMT"\n",
+ SCORE_PRINTF(&score),
+ SCORE_PRINTF(&ss->score),
+ SCORE_PRINTF(&ss->minimum_penalty),
+ SCORE_PRINTF(&ss->best_score));
+
+ subscore(&ss->score, &score);
+ return SOLVERR_PRUNED;
+ }
+
+ ps->install_applied = 1;
+ ss->assigned_names++;
+ ns->chosen = pkg;
- list_del(&ns->unsolved_list);
- list_init(&ns->unsolved_list);
- dbg_printf("%s: deleting from unsolved list\n",
- pkg->name->name);
+ ns->locked = 1;
+ list_del(&ns->unsolved_list);
+ list_init(&ns->unsolved_list);
- foreach_dependency(ss, pkg->depends, apply_constraint);
- foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
+ foreach_dependency(ss, pkg->depends, apply_constraint);
+ foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
+ }
} else {
- if (update_name_state(ss, pkg->name) == 0) {
+ dbg_printf("-->apply_decision: %s %s NOTHING\n",
+ name->name,
+ (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
+
+ if (d->type == DECISION_ASSIGN) {
subscore(&ss->minimum_penalty, &ns->minimum_penalty);
- ns->minimum_penalty = (struct apk_score) { 0, 0 };
+ ns->minimum_penalty = (struct apk_score) { 0 };
- dbg_printf("%s: out of candidates, locking to none\n",
- pkg->name->name);
+ get_unassigned_score(name, &score);
+ addscore(&ss->score, &score);
- ss->score.unsatisfiable += ns->requirers;
- ss->score.preference += name->pkgs->num;
+ ns->chosen = NULL;
ns->locked = 1;
+ list_del(&ns->unsolved_list);
+ list_init(&ns->unsolved_list);
+ } else {
+ ns->none_excluded = 1;
+ }
+ }
+
+ if (ss->impossible_constraints)
+ return SOLVERR_PRUNED;
+
+ if (d->type == DECISION_EXCLUDE) {
+ foreach_common_dependency(ss, name, increment_prerequires);
+
+ if (update_name_state(ss, name) == 0) {
+ dbg_printf("%s: %s would prune name to empty\n",
+ name->name,
+ (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
+ return SOLVERR_PRUNED;
}
}
if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) >= 0) {
- dbg_printf("install/uninstall finished penalty too big: {%d,%d}+{%d,%d}>={%d,%d}\n",
- ss->score.unsatisfiable, ss->score.preference,
- ss->minimum_penalty.unsatisfiable, ss->minimum_penalty.preference,
- ss->best_score.unsatisfiable, ss->best_score.preference
- );
+ dbg_printf("%s: %s penalty too big: "SCORE_FMT"+"SCORE_FMT">="SCORE_FMT"\n",
+ name->name,
+ (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE",
+ SCORE_PRINTF(&ss->score),
+ SCORE_PRINTF(&ss->minimum_penalty),
+ SCORE_PRINTF(&ss->best_score));
return SOLVERR_PRUNED;
}
@@ -664,106 +872,113 @@ static solver_result_t apply_decision(struct apk_solver_state *ss,
}
static void undo_decision(struct apk_solver_state *ss,
- struct apk_package *pkg,
- struct apk_package_state *ps)
+ struct apk_decision *d)
{
- struct apk_name *name = pkg->name;
+ struct apk_name *name = decision_to_name(d);
struct apk_name_state *ns = name_to_ns(name);
+ struct apk_package *pkg = decision_to_pkg(d);
+ struct apk_score score;
- dbg_printf("-->undo_decision: " PKG_VER_FMT " %s\n", PKG_VER_PRINTF(pkg),
- (ps->flags & APK_PKGSTF_INSTALL) ? "INSTALL" : "NO_INSTALL");
+ if (d->type == DECISION_EXCLUDE) {
+ foreach_common_dependency(ss, name, decrement_prerequires);
+ }
- if (ps->handle_install_if)
- ss->topology_position = ps->topology_soft;
- else
- ss->topology_position = pkg->topology_hard;
+ if (pkg != NULL) {
+ struct apk_package_state *ps = pkg_to_ps(pkg);
- if (ps->flags & APK_PKGSTF_INSTALL) {
- if (ps->install_applied) {
- unsigned short preference;
+ dbg_printf("-->undo_decision: " PKG_VER_FMT " %s\n",
+ PKG_VER_PRINTF(pkg),
+ (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
+
+ if (d->topology_position) {
+ if (ps->handle_install_if)
+ ss->topology_position = ps->topology_soft;
+ else
+ ss->topology_position = pkg->topology_hard;
+ }
+ if (ps->install_applied) {
ps->install_applied = 0;
ss->assigned_names--;
foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
foreach_dependency(ss, pkg->depends, undo_constraint);
- preference = get_preference(ss, pkg, FALSE);
- ss->score.unsatisfiable -= ps->conflicts;
- ss->score.preference -= preference;
+ get_topology_score(ss, ns, pkg, 1, &score);
+ subscore(&ss->score, &score);
}
+ ps->locked = 0;
} else {
- 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;
+ dbg_printf("-->undo_decision: %s %s NOTHING\n",
+ name->name,
+ (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
+
+ if (d->type == DECISION_ASSIGN) {
+ get_unassigned_score(name, &score);
+ subscore(&ss->score, &score);
+ } else {
+ ns->none_excluded = 0;
}
}
+
ns->locked = 0;
ns->chosen = NULL;
- update_name_state(ss, pkg->name);
+ update_name_state(ss, name);
}
-static solver_result_t push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
- int flags)
+static solver_result_t push_decision(struct apk_solver_state *ss,
+ struct apk_name *name,
+ struct apk_package *pkg,
+ int primary_decision,
+ int branching_point,
+ int topology_position)
{
- struct apk_package_state *ps = pkg_to_ps(pkg);
+ struct apk_decision *d;
- ps->backtrack = ss->latest_decision;
- ps->flags = flags;
- ps->locked = 1;
- ps->handle_install_if = 0;
+ ASSERT(ss->num_decisions <= ss->max_decisions,
+ "Decision tree overflow.\n");
- if (ps->topology_soft < ss->topology_position) {
- if (flags & APK_PKGSTF_INSTALL)
- ps->handle_install_if = 1;
- ss->topology_position = ps->topology_soft;
+ ss->num_decisions++;
+ d = &ss->decisions[ss->num_decisions];
+
+#ifdef DEBUG_CHECKS
+ d->saved_score = ss->score;
+#endif
+ d->type = primary_decision;
+ d->branching_point = branching_point;
+ d->topology_position = topology_position;
+ if (pkg == NULL) {
+ d->name = name;
+ d->no_package = 1;
} else {
- ss->topology_position = pkg->topology_hard;
+ d->pkg = pkg;
+ d->no_package = 0;
}
- ss->latest_decision = pkg;
-
- 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->handle_install_if)
- dbg_printf("triggers due to " PKG_VER_FMT "\n",
- PKG_VER_PRINTF(pkg));
-
- return apply_decision(ss, pkg, ps);
+ return apply_decision(ss, d);
}
static int next_branch(struct apk_solver_state *ss)
{
- struct apk_package *pkg;
- struct apk_package_state *ps;
-
- while (ss->latest_decision != NULL) {
- pkg = ss->latest_decision;
- ps = pkg_to_ps(pkg);
+ while (ss->num_decisions > 0) {
+ struct apk_decision *d = &ss->decisions[ss->num_decisions];
- if (ps->flags & APK_PKGSTF_ALT_BRANCH) {
- dbg_printf("-->next_branch: undo decision at topology_position %d\n",
- ss->topology_position);
- ps->flags &= ~APK_PKGSTF_ALT_BRANCH;
- ps->locked = 0;
- undo_decision(ss, pkg, ps);
-
- ss->latest_decision = ps->backtrack;
- } else {
- dbg_printf("-->next_branch: swapping BRANCH at topology_position %d\n",
- ss->topology_position);
+ undo_decision(ss, d);
- undo_decision(ss, pkg, ps);
-
- ps->flags |= APK_PKGSTF_ALT_BRANCH;
- ps->flags ^= APK_PKGSTF_INSTALL;
+#ifdef DEBUG_CHECKS
+ ASSERT(cmpscore(&d->saved_score, &ss->score) == 0,
+ "ERROR! saved_score "SCORE_FMT" != score "SCORE_FMT"\n",
+ SCORE_PRINTF(&d->saved_score),
+ SCORE_PRINTF(&ss->score));
+#endif
- return apply_decision(ss, pkg, ps);
+ if (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);
}
+
+ ss->num_decisions--;
}
dbg_printf("-->next_branch: no more branches\n");
@@ -824,12 +1039,12 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
dbg_printf("%s: locked to empty\n",
name->name);
if (!apk_dep_is_satisfied(dep, ns->chosen))
- ss->score.unsatisfiable++;
+ ss->score.conflicts++;
return;
}
if (name->pkgs->num == 0) {
if (!dep->optional)
- ss->score.unsatisfiable++;
+ ss->score.conflicts++;
return;
}
@@ -840,18 +1055,19 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
ns->allowed_pinning |= BIT(dep->repository_tag);
}
- if (ss->latest_decision != NULL) {
+ 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, ss->latest_decision->name->name);
- inherit_name_state(name, ss->latest_decision->name);
+ name->name, name0->name);
+ inherit_name_state(name, name0);
}
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);
- if (ps0 == NULL ||
- pkg0->topology_hard >= ss->topology_position)
+ if (ps0 == NULL || ps0->locked ||
+ ss->topology_position < pkg0->topology_hard)
continue;
if (!apk_dep_is_satisfied(dep, pkg0)) {
@@ -863,7 +1079,7 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
}
if (!dep->optional)
- ns->requirers++;
+ ns->requirers++;
update_name_state(ss, name);
}
@@ -883,12 +1099,12 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
name->name);
}
if (!apk_dep_is_satisfied(dep, ns->chosen))
- ss->score.unsatisfiable--;
+ ss->score.conflicts--;
return;
}
if (name->pkgs->num == 0) {
if (!dep->optional)
- ss->score.unsatisfiable--;
+ ss->score.conflicts--;
return;
}
@@ -896,7 +1112,8 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
struct apk_package *pkg0 = name->pkgs->item[i];
struct apk_package_state *ps0 = pkg_to_ps(pkg0);
- if (pkg0->topology_hard >= ss->topology_position)
+ if (ps0 == NULL || ps0->locked ||
+ ss->topology_position < pkg0->topology_hard)
continue;
if (!apk_dep_is_satisfied(dep, pkg0)) {
@@ -907,7 +1124,8 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
}
}
- if (ss->latest_decision && has_inherited_state(ss->latest_decision->name))
+ if (ss->num_decisions > 0 &&
+ has_inherited_state(decision_to_name(&ss->decisions[ss->num_decisions])))
recalculate_inherted_name_state(name);
if (!dep->optional)
@@ -918,54 +1136,110 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *
static int expand_branch(struct apk_solver_state *ss)
{
+ struct apk_name *name;
struct apk_name_state *ns;
struct apk_package *pkg0 = NULL;
- unsigned int topology0 = 0;
+ unsigned int i, topology0 = 0;
unsigned short allowed_pinning, preferred_pinning;
unsigned int allowed_repos;
- int flags;
+ int primary_decision, branching_point;
/* FIXME: change unsolved_list to a priority queue */
list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
- if (ns->chosen == NULL)
- continue;
+ struct apk_score score;
+ struct apk_score pkgscore;
+
+ name = ns->name;
+
+ /* no options left */
+ if (ns->chosen == NULL) {
+ if (ns->none_excluded)
+ return SOLVERR_PRUNED;
+ return push_decision(ss, name, NULL, DECISION_ASSIGN, BRANCH_NO, FALSE);
+ }
+
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;
+
+ score = ss->score;
+ subscore(&score, &ns->minimum_penalty);
+
+ if (!ns->none_excluded) {
+ get_unassigned_score(name, &pkgscore);
+ if (cmpscore2(&score, &pkgscore, &ss->best_score) >= 0)
+ return push_decision(ss, name, NULL, DECISION_EXCLUDE, BRANCH_NO, FALSE);
+ }
+
+ 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);
+
+ if (ps0 == NULL || ps0->locked ||
+ ss->topology_position < pkg0->topology_hard)
+ continue;
+
+ get_topology_score(ss, ns, pkg0, 0, &pkgscore);
+ if (cmpscore2(&score, &pkgscore, &ss->best_score) >= 0)
+ return push_decision(ss, name, pkg0, DECISION_EXCLUDE, BRANCH_NO, FALSE);
+ }
+
}
if (pkg0 == NULL) {
- dbg_printf("expand_branch: list is empty (%d unsatisfied)\n",
- ss->score.unsatisfiable);
+ dbg_printf("expand_branch: solution with score "SCORE_FMT"\n",
+ SCORE_PRINTF(&ss->score));
return SOLVERR_SOLUTION;
}
/* someone needs to provide this name -- find next eligible
* provider candidate */
- ns = name_to_ns(pkg0->name);
- dbg_printf("expand_branch: %s\n", pkg0->name->name);
+ 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);
+ if (ps0->conflicts > ns->requirers)
+ primary_decision = DECISION_ASSIGN;
+ else
+ primary_decision = DECISION_EXCLUDE;
+ return push_decision(ss, name, NULL, primary_decision, BRANCH_YES, FALSE);
+ }
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);
- if ((pkg0->repos != 0) && (pkg0->ipkg == NULL) &&
- (pkg0->filename == NULL) && !(pkg0->repos & allowed_repos)) {
+ if ((pkg0->repos != 0) && !(pkg0->repos & allowed_repos)) {
/* pinning has not enabled the package */
- flags = APK_PKGSTF_NOINSTALL | APK_PKGSTF_ALT_BRANCH;
+ primary_decision = DECISION_EXCLUDE;
+ /* but if it is installed, we might consider it */
+ if ((pkg0->ipkg == NULL) && (pkg0->filename == NULL))
+ branching_point = BRANCH_NO;
+ else
+ branching_point = BRANCH_YES;
} else if (ns->requirers == 0 && ns->install_ifs != 0 &&
install_if_missing(ss, pkg0)) {
/* not directly required, and package specific
* install_if never triggered */
- flags = APK_PKGSTF_NOINSTALL | APK_PKGSTF_ALT_BRANCH;
- } else if (get_preference(ss, pkg0, TRUE) == 0) {
- flags = APK_PKGSTF_INSTALL;
+ primary_decision = DECISION_EXCLUDE;
+ branching_point = BRANCH_NO;
+ } else if (is_topology_optimum(ss, pkg0)) {
+ primary_decision = DECISION_ASSIGN;
+ branching_point = BRANCH_YES;
} else {
- flags = APK_PKGSTF_NOINSTALL;
+ primary_decision = DECISION_EXCLUDE;
+ branching_point = BRANCH_YES;
}
- return push_decision(ss, pkg0, flags);
+ return push_decision(ss, pkg0->name, pkg0,
+ primary_decision, branching_point, TRUE);
}
static int get_tag(struct apk_database *db, unsigned short pinning_mask, unsigned int repos)
@@ -984,43 +1258,44 @@ static int get_tag(struct apk_database *db, unsigned short pinning_mask, unsigne
static void record_solution(struct apk_solver_state *ss)
{
struct apk_database *db = ss->db;
- struct apk_package *pkg;
- struct apk_package_state *ps;
struct apk_name_state *ns;
- int i;
+ int i, n;
apk_solution_array_resize(&ss->best_solution, ss->assigned_names);
- i = 0;
- pkg = ss->latest_decision;
- while (pkg != NULL) {
- ps = pkg_to_ps(pkg);
- ns = name_to_ns(pkg->name);
- if (ps->flags & APK_PKGSTF_INSTALL) {
- unsigned short pinning;
- unsigned int repos;
-
- if (i >= ss->assigned_names)
- abort();
-
- pinning = ns->allowed_pinning | ns->preferred_pinning | APK_DEFAULT_PINNING_MASK;
- repos = pkg->repos | (pkg->ipkg ? db->repo_tags[pkg->ipkg->repository_tag].allowed_repos : 0);
-
- ss->best_solution->item[i++] = (struct apk_solution_entry){
- .pkg = pkg,
- .reinstall = !!((ns->solver_flags_local | ns->solver_flags_inherited |
- ss->solver_flags) & APK_SOLVERF_REINSTALL),
- .repository_tag = get_tag(db, pinning, repos),
- };
+ n = 0;
+ for (i = ss->num_decisions; i > 0; i--) {
+ struct apk_decision *d = &ss->decisions[i];
+ struct apk_package *pkg = decision_to_pkg(d);
+ unsigned short pinning;
+ unsigned int repos;
+
+ if (pkg == NULL) {
+ dbg_printf("record_solution: %s: NOTHING\n",
+ decision_to_name(d)->name);
+ continue;
}
- dbg_printf("record_solution: " PKG_VER_FMT ": %sINSTALL\n",
+ dbg_printf("record_solution: " PKG_VER_FMT ": %s\n",
PKG_VER_PRINTF(pkg),
- (ps->flags & APK_PKGSTF_INSTALL) ? "" : "NO_");
+ d->type == DECISION_ASSIGN ? "INSTALL" : "no install");
- pkg = ps->backtrack;
+ if (d->type != DECISION_ASSIGN)
+ continue;
+
+ ns = name_to_ns(pkg->name);
+ pinning = ns->allowed_pinning | ns->preferred_pinning | APK_DEFAULT_PINNING_MASK;
+ repos = pkg->repos | (pkg->ipkg ? db->repo_tags[pkg->ipkg->repository_tag].allowed_repos : 0);
+
+ 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),
+ .repository_tag = get_tag(db, pinning, repos),
+ };
}
- apk_solution_array_resize(&ss->best_solution, i);
+ apk_solution_array_resize(&ss->best_solution, n);
}
static int compare_solution_entry(const void *p1, const void *p2)
@@ -1125,9 +1400,10 @@ static int generate_changeset(struct apk_database *db,
static int free_state(apk_hash_item item, void *ctx)
{
struct apk_name *name = (struct apk_name *) item;
+ struct apk_name_state *ns = (struct apk_name_state *) name->state_ptr;
- if (name->state_ptr != NULL) {
- free(name->state_ptr);
+ if (ns != NULL) {
+ free(ns);
name->state_ptr = NULL;
}
return 0;
@@ -1167,7 +1443,6 @@ int apk_solver_solve(struct apk_database *db,
{
struct apk_solver_state *ss;
struct apk_installed_package *ipkg;
- struct apk_score zero_score;
solver_result_t r = SOLVERR_STOP;
int i;
@@ -1175,20 +1450,30 @@ int apk_solver_solve(struct apk_database *db,
ss->db = db;
ss->solver_flags = solver_flags;
ss->topology_position = -1;
- ss->best_score = (struct apk_score){ .unsatisfiable = -1, .preference = -1 };
+ ss->best_score = (struct apk_score){
+ .conflicts = -1,
+ .non_preferred_actions = -1,
+ .preference = -1,
+ };
list_init(&ss->unsolved_list_head);
for (i = 0; i < world->num; i++)
sort_name(ss, world->item[i].name);
- list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list)
+ list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
sort_name(ss, ipkg->pkg->name);
+ name_to_ns(ipkg->pkg->name)->originally_installed = 1;
+ }
+#if 0
+ for (i = 0; i < world->num; i++)
+ prepare_name(ss, world->item[i].name);
+ list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list)
+ prepare_name(ss, ipkg->pkg->name);
+#endif
- foreach_dependency(ss, world, apply_constraint);
- zero_score = ss->score;
+ ss->max_decisions ++;
+ ss->decisions = calloc(1, sizeof(struct apk_decision[ss->max_decisions]));
- dbg_printf("solver_solve: zero score: %d unsatisfiable, %d preference\n",
- zero_score.unsatisfiable,
- zero_score.preference);
+ foreach_dependency(ss, world, apply_constraint);
do {
/* need EXPAND if here, can return SOLUTION|PRUNED|EXPAND */
@@ -1196,24 +1481,18 @@ int apk_solver_solve(struct apk_database *db,
if (r == SOLVERR_SOLUTION) {
struct apk_score score;
- dbg_printf("solution with: %d unsatisfiable, %d preference\n",
- ss->score.unsatisfiable,
- ss->score.preference);
-
score = ss->score;
addscore(&score, &ss->minimum_penalty);
if (cmpscore(&score, &ss->best_score) < 0) {
+ dbg_printf("updating best score "SCORE_FMT" (was: "SCORE_FMT")\n",
+ SCORE_PRINTF(&score),
+ SCORE_PRINTF(&ss->best_score));
+
record_solution(ss);
ss->best_score = score;
}
- 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. */
- break;
- }
r = SOLVERR_PRUNED;
}
/* next_branch() returns PRUNED, STOP or EXPAND */
@@ -1223,6 +1502,10 @@ int apk_solver_solve(struct apk_database *db,
} while (r != SOLVERR_STOP);
/* collect packages */
+ dbg_printf("finished. best score "SCORE_FMT". solution has %d packages.\n",
+ SCORE_PRINTF(&ss->best_score),
+ ss->best_solution->num);
+
if (changeset != NULL) {
generate_changeset(db, ss->best_solution, changeset,
ss->solver_flags);
@@ -1234,8 +1517,9 @@ int apk_solver_solve(struct apk_database *db,
} else {
apk_solution_array_free(&ss->best_solution);
}
- i = ss->best_score.unsatisfiable;
+ i = ss->best_score.conflicts;
apk_solver_free(db);
+ free(ss->decisions);
free(ss);
return i;