aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTimo Teräs <timo.teras@iki.fi>2012-01-17 13:54:33 +0200
committerTimo Teräs <timo.teras@iki.fi>2012-01-17 14:18:02 +0200
commit12183024fd6bce3b06f1fab843dd8781dd35e036 (patch)
treea621ec7b65d37f011b15d22612df119404ee21be
parent60ee61162053054bb4abe7e0260734fd53532401 (diff)
downloadapk-tools-12183024fd6bce3b06f1fab843dd8781dd35e036.tar.gz
apk-tools-12183024fd6bce3b06f1fab843dd8781dd35e036.tar.bz2
apk-tools-12183024fd6bce3b06f1fab843dd8781dd35e036.tar.xz
solver: calculate branch minimum penalty early
Previously we would cache the penalty when evaluating the final solution, and adding that until we backtrack to first topology position changing that penalty. However, we can just keep track of minimum penalty based on name state, and add it. This allows us to bail out early on bad branches because we know in advance how things will turn out.
-rw-r--r--src/solver.c152
-rw-r--r--test/error2.expect3
2 files changed, 99 insertions, 56 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",
diff --git a/test/error2.expect b/test/error2.expect
index 7faac5e..65d0093 100644
--- a/test/error2.expect
+++ b/test/error2.expect
@@ -1,2 +1,3 @@
-1 unsatisfiable dependencies (solution with 4 names)
+2 unsatisfiable dependencies (solution with 4 names)
world: d<1.5
+b-1: d<2.0