summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/solver.c187
-rw-r--r--src/test.c2
-rw-r--r--test/error1.expect5
-rw-r--r--test/error2.expect2
-rw-r--r--test/error3.expect4
-rw-r--r--test/error5.expect5
6 files changed, 120 insertions, 85 deletions
diff --git a/src/solver.c b/src/solver.c
index 8832c23..49cfc79 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -26,17 +26,21 @@
#define APK_PKGSTF_NOINSTALL 0
#define APK_PKGSTF_INSTALL 1
-#define APK_PKGSTF_BRANCH 2
-#define APK_PKGSTF_ALT_BRANCH 4
-#define APK_PKGSTF_INSTALLIF 8
-#define APK_PKGSTF_DECIDED 16
+#define APK_PKGSTF_ALT_BRANCH 2
+#define APK_PKGSTF_INSTALLIF 4
+#define APK_PKGSTF_DECIDED 8
+
+struct apk_score {
+ unsigned short unsatisfiable;
+ unsigned short preference;
+};
struct apk_package_state {
struct apk_package *backtrack;
unsigned int topology_soft;
+ struct apk_score saved_score;
unsigned short flags;
unsigned short conflicts;
- unsigned short cur_unsatisfiable;
};
struct apk_name_state {
@@ -52,6 +56,7 @@ struct apk_name_state {
unsigned int availability_checked : 1;
unsigned int locked : 1;
+ unsigned int in_changeset : 1;
};
struct apk_solver_state {
@@ -62,13 +67,13 @@ struct apk_solver_state {
struct apk_package *latest_decision;
unsigned int topology_position;
unsigned int assigned_names;
- unsigned short cur_unsatisfiable;
+ struct apk_score score;
unsigned int solver_flags : 4;
unsigned int refresh_name_states : 1;
struct apk_package_array *best_solution;
- unsigned short best_unsatisfiable;
+ struct apk_score best_score;
};
static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep);
@@ -276,59 +281,68 @@ static void foreach_dependency(struct apk_solver_state *ss, struct apk_dependenc
func(ss, &deps->item[i]);
}
-static int get_pkg_expansion_flags(struct apk_solver_state *ss, struct apk_package *pkg)
+static int compare_package_preference(unsigned short solver_flags,
+ struct apk_package *pkgA,
+ struct apk_package *pkgB)
+{
+ 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;
+ }
+
+ /* 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);
- int i, options = 0;
+ unsigned short name_flags = ns->solver_flags_local
+ | ns->solver_flags_inherited
+ | ss->solver_flags;
+ unsigned short preference = 0;
+ int i;
- /* check if the suggested package is the most preferred one of
- * available packages for the 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);
- if (pkg0 == pkg || ps0 == NULL ||
- pkg0->topology_hard > ss->topology_position ||
- (ps0->flags & APK_PKGSTF_DECIDED) ||
- ps0->conflicts != 0)
+ if (pkg0 == pkg || ps0 == NULL)
continue;
- options++;
-
- if ((ns->solver_flags_local | ns->solver_flags_inherited |
- ss->solver_flags) & APK_SOLVERF_AVAILABLE) {
- /* pkg available, pkg0 not */
- if (pkg->repos != 0 && pkg0->repos == 0)
- continue;
- /* pkg0 available, pkg not */
- if (pkg0->repos != 0 && pkg->repos == 0)
- return APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH;
+ if (compare_package_preference(name_flags, pkg, pkg0) < 0) {
+ if (installable_only) {
+ if (ss->topology_position > pkg0->topology_hard &&
+ !(ps0->flags & APK_PKGSTF_DECIDED))
+ preference++;
+ } else
+ preference++;
}
-
- if ((ns->solver_flags_local | ns->solver_flags_inherited |
- ss->solver_flags) & APK_SOLVERF_UPGRADE) {
- /* upgrading, or neither of the package is installed, so
- * we just fall back comparing to versions */
- switch (apk_pkg_version_compare(pkg0, pkg)) {
- case APK_VERSION_GREATER:
- return APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH;
- case APK_VERSION_LESS:
- continue;
- }
- }
-
- /* not upgrading, prefer the installed package */
- if (pkg->ipkg == NULL && pkg0->ipkg != NULL)
- return APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH;
}
- /* no package greater than the selected */
- if (options)
- return APK_PKGSTF_INSTALL | APK_PKGSTF_BRANCH;
-
- /* no other choice */
- return APK_PKGSTF_INSTALL;
+ return preference;
}
static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg)
@@ -378,8 +392,10 @@ static int update_name_state(struct apk_solver_state *ss, struct apk_name *name)
}
if (skipped_options == 0 && options == 0) {
- if (!ns->locked)
- ss->cur_unsatisfiable += ns->requirers;
+ if (!ns->locked) {
+ ss->score.unsatisfiable += ns->requirers;
+ ss->score.preference += name->pkgs->num;
+ }
ns->locked = 1;
ns->chosen = NULL;
} else {
@@ -443,7 +459,8 @@ static void apply_decision(struct apk_solver_state *ss,
if (ps->flags & APK_PKGSTF_INSTALL) {
ss->assigned_names++;
- ss->cur_unsatisfiable += ps->conflicts;
+ ss->score.unsatisfiable += ps->conflicts;
+ ss->score.preference += get_preference(ss, pkg, FALSE);
ns->chosen = pkg;
ns->locked = 1;
@@ -483,7 +500,7 @@ static void undo_decision(struct apk_solver_state *ss,
ns->chosen = NULL;
}
- ss->cur_unsatisfiable = ps->cur_unsatisfiable;
+ ss->score = ps->saved_score;
update_name_state(ss, pkg->name);
}
@@ -494,7 +511,7 @@ static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
ps->backtrack = ss->latest_decision;
ps->flags = flags | APK_PKGSTF_DECIDED;
- ps->cur_unsatisfiable = ss->cur_unsatisfiable;
+ ps->saved_score = ss->score;
if (ps->topology_soft < ss->topology_position) {
if (flags & APK_PKGSTF_INSTALL)
@@ -506,11 +523,8 @@ static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg,
}
ss->latest_decision = pkg;
- if (flags & APK_PKGSTF_BRANCH) {
- dbg_printf("push_decision: adding new BRANCH at topology_position %d\n",
- ss->topology_position);
- } else
- ps->flags |= APK_PKGSTF_ALT_BRANCH;
+ dbg_printf("push_decision: adding new BRANCH at topology_position %d\n",
+ ss->topology_position);
if (ps->flags & APK_PKGSTF_INSTALLIF)
dbg_printf("triggers due to " PKG_VER_FMT "\n",
@@ -598,7 +612,7 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency
dbg_printf(PKG_VER_FMT " selected already for %s\n",
PKG_VER_PRINTF(ns->chosen), dep->name->name);
if (!apk_dep_is_satisfied(dep, ns->chosen))
- ss->cur_unsatisfiable++;
+ ss->score.unsatisfiable++;
return;
}
@@ -671,6 +685,7 @@ static int expand_branch(struct apk_solver_state *ss)
struct apk_name_state *ns;
struct apk_package *pkg0 = NULL;
unsigned int topology0 = 0;
+ int flags;
/* FIXME: change unsolved_list to a priority queue */
list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) {
@@ -692,7 +707,7 @@ static int expand_branch(struct apk_solver_state *ss)
ss->refresh_name_states = 0;
if (pkg0 == NULL) {
dbg_printf("expand_branch: list is empty (%d unsatisfied)\n",
- ss->cur_unsatisfiable);
+ ss->score.unsatisfiable);
return 1;
}
@@ -701,7 +716,11 @@ static int expand_branch(struct apk_solver_state *ss)
ns = name_to_ns(pkg0->name);
dbg_printf("expand_branch: %s\n", pkg0->name->name);
- push_decision(ss, pkg0, get_pkg_expansion_flags(ss, pkg0));
+ if (get_preference(ss, pkg0, TRUE) == 0)
+ flags = APK_PKGSTF_INSTALL;
+ else
+ flags = APK_PKGSTF_NOINSTALL;
+ push_decision(ss, pkg0, flags);
return 0;
}
@@ -731,7 +750,7 @@ static void record_solution(struct apk_solver_state *ss)
pkg = ps->backtrack;
}
apk_package_array_resize(&ss->best_solution, i);
- ss->best_unsatisfiable = ss->cur_unsatisfiable;
+ ss->best_score = ss->score;
}
static int compare_package_name(const void *p1, const void *p2)
@@ -779,6 +798,8 @@ static int generate_changeset(struct apk_database *db,
for (i = 0; i < solution->num; i++) {
pkg = solution->item[i];
ns = name_to_ns(pkg->name);
+ ns->chosen = pkg;
+ ns->in_changeset = 1;
if ((pkg->ipkg == NULL) ||
((ns->solver_flags_local | ns->solver_flags_inherited |
solver_flags) & APK_SOLVERF_REINSTALL))
@@ -787,7 +808,7 @@ static int generate_changeset(struct apk_database *db,
list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
name = ipkg->pkg->name;
ns = name_to_ns(name);
- if ((ns->chosen == NULL) || !ns->locked)
+ if ((ns->chosen == NULL) || !ns->in_changeset)
num_removed++;
}
@@ -796,7 +817,7 @@ static int generate_changeset(struct apk_database *db,
list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
name = ipkg->pkg->name;
ns = name_to_ns(name);
- if ((ns->chosen == NULL) || !ns->locked) {
+ if ((ns->chosen == NULL) || !ns->in_changeset) {
changeset->changes->item[ci].oldpkg = ipkg->pkg;
ci++;
}
@@ -865,6 +886,19 @@ 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;
+}
+
int apk_solver_solve(struct apk_database *db,
unsigned short solver_flags,
struct apk_dependency_array *world,
@@ -879,7 +913,7 @@ int apk_solver_solve(struct apk_database *db,
ss->db = db;
ss->solver_flags = solver_flags;
ss->topology_position = -1;
- ss->best_unsatisfiable = -1;
+ ss->best_score = (struct apk_score){ .unsatisfiable = -1, .preference = -1 };
list_init(&ss->unsolved_list_head);
for (i = 0; i < world->num; i++)
@@ -889,20 +923,24 @@ int apk_solver_solve(struct apk_database *db,
foreach_dependency(ss, world, apply_constraint);
do {
- if (ss->cur_unsatisfiable < ss->best_unsatisfiable) {
+ if (cmpscore(&ss->score, &ss->best_score) < 0) {
r = expand_branch(ss);
if (r) {
- dbg_printf("solution with %d unsatisfiable\n",
- ss->cur_unsatisfiable);
- if (ss->cur_unsatisfiable == 0) {
+ dbg_printf("solution with: %d unsatisfiable, %d preference\n",
+ ss->score.unsatisfiable,
+ ss->score.preference);
+
+ if (cmpscore(&ss->score, &ss->best_score) < 0)
+ record_solution(ss);
+
+ if (ss->score.unsatisfiable == 0 &&
+ ss->score.preference == 0) {
/* found solution - it is optimal because we permutate
* each preferred local option first, and permutations
* happen in topologally sorted order. */
r = 0;
break;
}
- if (ss->cur_unsatisfiable < ss->best_unsatisfiable)
- record_solution(ss);
r = next_branch(ss);
}
} else {
@@ -911,8 +949,7 @@ int apk_solver_solve(struct apk_database *db,
} while (r == 0);
/* collect packages */
- if (r == 0 && ss->cur_unsatisfiable == 0) {
- record_solution(ss);
+ if (ss->best_score.unsatisfiable == 0) {
if (changeset != NULL)
generate_changeset(db, ss->best_solution, changeset,
ss->solver_flags);
@@ -920,7 +957,7 @@ int apk_solver_solve(struct apk_database *db,
} else {
qsort(ss->best_solution->item, ss->best_solution->num,
sizeof(struct apk_package *), compare_package_name);
- r = ss->best_unsatisfiable;
+ r = ss->best_score.unsatisfiable;
}
if (solution != NULL)
@@ -1102,7 +1139,7 @@ static int cmp_upgrade(struct apk_change *change)
return 0;
}
-static int compare_package(const void *p1, const void *p2)
+static int compare_package_topology(const void *p1, const void *p2)
{
struct apk_package *pkg1 = *(struct apk_package **) p1;
struct apk_package *pkg2 = *(struct apk_package **) p2;
@@ -1120,7 +1157,7 @@ static void run_triggers(struct apk_database *db)
return;
qsort(pkgs->item, pkgs->num, sizeof(struct apk_package *),
- compare_package);
+ compare_package_topology);
for (i = 0; i < pkgs->num; i++) {
struct apk_package *pkg = pkgs->item[i];
diff --git a/src/test.c b/src/test.c
index 69fc4d3..dec5bb0 100644
--- a/src/test.c
+++ b/src/test.c
@@ -101,7 +101,7 @@ static void print_dep_errors(char *label, struct apk_dependency_array *deps)
struct apk_dependency *dep = &deps->item[i];
struct apk_package *pkg = dep->name->state_ptr;
- if (pkg != NULL && apk_dep_is_satisfied(dep, pkg))
+ if (apk_dep_is_satisfied(dep, pkg))
continue;
if (print_label) {
diff --git a/test/error1.expect b/test/error1.expect
index 6f340f1..ddd4f4f 100644
--- a/test/error1.expect
+++ b/test/error1.expect
@@ -1,3 +1,2 @@
-2 unsatisfiable dependencies (solution with 4 names)
-world: d>1.5
-c-1: d>1.0
+1 unsatisfiable dependencies (solution with 4 names)
+b-1: d<2.0
diff --git a/test/error2.expect b/test/error2.expect
index 5ab9023..7faac5e 100644
--- a/test/error2.expect
+++ b/test/error2.expect
@@ -1,2 +1,2 @@
1 unsatisfiable dependencies (solution with 4 names)
-c-1: d>1.0
+world: d<1.5
diff --git a/test/error3.expect b/test/error3.expect
index 55be962..d04f76e 100644
--- a/test/error3.expect
+++ b/test/error3.expect
@@ -1,2 +1,2 @@
-1 unsatisfiable dependencies (solution with 4 names)
-world: !b
+1 unsatisfiable dependencies (solution with 3 names)
+a-3: b
diff --git a/test/error5.expect b/test/error5.expect
index 553ecf3..ddd4f4f 100644
--- a/test/error5.expect
+++ b/test/error5.expect
@@ -1,3 +1,2 @@
-2 unsatisfiable dependencies (solution with 4 names)
-a-3: d>1.5
-c-1: d>1.0
+1 unsatisfiable dependencies (solution with 4 names)
+b-1: d<2.0