summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/solver.c112
-rw-r--r--test/basic.installed213
-rw-r--r--test/basic5.expect2
-rw-r--r--test/basic5.test1
-rw-r--r--test/basic6.expect0
-rw-r--r--test/basic6.test1
6 files changed, 72 insertions, 57 deletions
diff --git a/src/solver.c b/src/solver.c
index 71cdccc..141b937 100644
--- a/src/solver.c
+++ b/src/solver.c
@@ -38,7 +38,6 @@ struct apk_package_state {
struct apk_name_state {
struct list_head unsolved_list;
struct apk_package *chosen;
- struct apk_package *preferred;
unsigned short requirers;
};
@@ -82,53 +81,62 @@ static int foreach_dependency(struct apk_solver_state *ss, struct apk_dependency
return r;
}
-static void calculate_preferred(struct apk_database *db,
- struct apk_name *name,
- struct apk_name_state *ns)
+static int inline can_consider_package(struct apk_solver_state *ss, struct apk_package *pkg)
{
- struct apk_package *installed = NULL, *latest = NULL;
+ struct apk_package_state *ps = &ss->pkg_state[pkg->topology_sort];
+ if (pkg->topology_sort >= ss->topology_position)
+ return FALSE;
+ if (ps->conflicts)
+ return FALSE;
+ return TRUE;
+}
+
+static int is_pkg_preferred(struct apk_solver_state *ss, struct apk_package *pkg)
+{
+ struct apk_name *name = pkg->name;
int i;
- /* Get latest and installed packages */
+ if (!(apk_flags & APK_UPGRADE)) {
+ /* not upgrading, prefer the installed package; unless we
+ * need additional availability checks */
+ if (pkg->ipkg != NULL) {
+ if (pkg->repos != 0 ||
+ !(apk_flags & APK_PREFER_AVAILABLE))
+ return TRUE;
+ }
+ }
+
+ /* 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 *pkg = name->pkgs->item[i];
+ struct apk_package *pkg0 = name->pkgs->item[i];
- if (pkg->ipkg != NULL)
- installed = pkg;
- else if (!pkg_available(db, pkg))
- continue;
- if (latest == NULL) {
- latest = pkg;
+ if (pkg0 == pkg || !can_consider_package(ss, pkg0))
continue;
- }
- if ((apk_flags & APK_PREFER_AVAILABLE) ||
- (name->flags & APK_NAME_REINSTALL)) {
- if (latest->repos != 0 && pkg->repos == 0)
- continue;
- if (latest->repos == 0 && pkg->repos != 0) {
- latest = pkg;
+ if (apk_flags & APK_PREFER_AVAILABLE) {
+ /* pkg available, pkg0 not */
+ if (pkg->repos != 0 && pkg0->repos == 0)
continue;
- }
- /* Otherwise both are not available, or both are
- * available and we just compare the versions then */
+ /* pkg0 available, pkg not */
+ if (pkg0->repos != 0 && pkg->repos == 0)
+ return FALSE;
}
- if (apk_pkg_version_compare(pkg, latest) == APK_VERSION_GREATER)
- latest = pkg;
- }
- /* Choose the best looking candidate. */
- if (apk_flags & APK_UPGRADE) {
- ns->preferred = latest;
- } else {
- if (installed != NULL &&
- (installed->repos != 0 ||
- !(name->flags & APK_NAME_REINSTALL)))
- ns->preferred = installed;
- else
- ns->preferred = latest;
+ if (!(apk_flags & APK_UPGRADE)) {
+ /* not upgrading, prefer the installed package */
+ if (pkg0->ipkg != NULL)
+ return FALSE;
+ }
+
+ /* upgrading, or neither of the package is installed, so
+ * we just fall back comparing to versions */
+ if (apk_pkg_version_compare(pkg0, pkg) == APK_VERSION_GREATER)
+ return FALSE;
}
+ /* no package greater than the selected */
+ return TRUE;
}
static int update_name_state(struct apk_solver_state *ss,
@@ -139,10 +147,8 @@ static int update_name_state(struct apk_solver_state *ss,
for (i = 0; i < name->pkgs->num; i++) {
struct apk_package *pkg0 = name->pkgs->item[i];
- struct apk_package_state *ps0 = &ss->pkg_state[pkg0->topology_sort];
- if (pkg0->topology_sort >= ss->topology_position ||
- ps0->conflicts != 0)
+ if (!can_consider_package(ss, pkg0))
continue;
options++;
@@ -274,12 +280,8 @@ static int apply_constraint(struct apk_solver_state *ss, struct apk_dependency *
struct apk_package *pkg0 = name->pkgs->item[i];
struct apk_package_state *ps0 = &ss->pkg_state[pkg0->topology_sort];
- if (pkg0->topology_sort >= ss->topology_position) {
- dbg_printf(PKG_VER_FMT ": topology skip %d > %d\n",
- PKG_VER_PRINTF(pkg0),
- pkg0->topology_sort, ss->topology_position);
+ if (pkg0->topology_sort >= ss->topology_position)
continue;
- }
if (!apk_dep_is_satisfied(dep, pkg0)) {
ps0->conflicts++;
@@ -407,14 +409,10 @@ static int expand_branch(struct apk_solver_state *ss)
ns = &ss->name_state[pkg0->name->id];
dbg_printf("expand_branch: %s %d\n", pkg0->name->name, pkg0->topology_sort);
- /* Is there something we can still use? */
- if (ns->preferred == NULL)
- calculate_preferred(ss->db, pkg0->name, ns);
-
r = push_decision(ss, pkg0,
- (pkg0 == ns->preferred) ?
- (APK_PKGSTF_INSTALL | APK_PKGSTF_BRANCH) :
- (APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH));
+ is_pkg_preferred(ss, pkg0) ?
+ (APK_PKGSTF_INSTALL | APK_PKGSTF_BRANCH) :
+ (APK_PKGSTF_NOINSTALL | APK_PKGSTF_BRANCH));
if (/*no_error_reporting &&*/ r)
return r;
@@ -462,14 +460,14 @@ int apk_solver_solve(struct apk_database *db, struct apk_dependency_array *world
r = foreach_dependency(ss, world, apply_constraint);
while (r == 0) {
if (expand_branch(ss) == 0) {
- /* found solution*/
- /* FIXME: we should check other permutations if they
- * have smaller cost to find optimal changeset */
+ /* found solution - it is optimal because we permutate
+ * each preferred local option first, and permutations
+ * happen in topologally sorted order. */
break;
- } else {
- /* conflicting constraints -- backtrack */
- r = next_branch(ss);
}
+
+ /* conflicting constraints -- backtrack */
+ r = next_branch(ss);
}
/* collect packages */
diff --git a/test/basic.installed2 b/test/basic.installed2
new file mode 100644
index 0000000..f5fb530
--- /dev/null
+++ b/test/basic.installed2
@@ -0,0 +1,13 @@
+C:Q1EyN5AdpAOBJWKMR89pdfC66o+OE=
+P:a
+V:2
+S:1
+I:1
+D:b
+
+C:Q1C4uoV7SdMdDdfg4OCVmI71D8HIA=
+P:b
+V:2
+S:1
+I:1
+
diff --git a/test/basic5.expect b/test/basic5.expect
new file mode 100644
index 0000000..269ff0c
--- /dev/null
+++ b/test/basic5.expect
@@ -0,0 +1,2 @@
+Replacing a (2 -> 2)
+Replacing b (2 -> 2)
diff --git a/test/basic5.test b/test/basic5.test
new file mode 100644
index 0000000..6e69db3
--- /dev/null
+++ b/test/basic5.test
@@ -0,0 +1 @@
+--raw-repository basic.repo --installed basic.installed2 -a a
diff --git a/test/basic6.expect b/test/basic6.expect
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/basic6.expect
diff --git a/test/basic6.test b/test/basic6.test
new file mode 100644
index 0000000..2a644c2
--- /dev/null
+++ b/test/basic6.test
@@ -0,0 +1 @@
+--raw-repository basic.repo --installed basic.installed2 a
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2024-12-29 13:55:10 +0000