summaryrefslogtreecommitdiff
path: root/src/solver.c
diff options
context:
space:
mode:
authorTimo Teräs <timo.teras@iki.fi>2013-06-11 14:06:06 +0300
committerTimo Teräs <timo.teras@iki.fi>2013-06-13 18:22:00 +0300
commitb8c44536ca911418fee1c9ab4eecbb913a1ca852 (patch)
treea89e68b12f4d3daf089c475beeb71c53ffb8cc3a /src/solver.c
parentf292a858677ae0e1af8910ffbd4b338f4b36c18b (diff)
downloadapk-tools-b8c44536ca911418fee1c9ab4eecbb913a1ca852.tar.gz
apk-tools-b8c44536ca911418fee1c9ab4eecbb913a1ca852.tar.bz2
apk-tools-b8c44536ca911418fee1c9ab4eecbb913a1ca852.tar.xz
apk-tools-b8c44536ca911418fee1c9ab4eecbb913a1ca852.zip
solver: rewrite as deductive solver -- core features
Implementing basic dependency handling, install_if and awareness of pinning.
Diffstat (limited to 'src/solver.c')
-rw-r--r--src/solver.c2248
1 files changed, 418 insertions, 1830 deletions
diff --git a/src/solver.c b/src/solver.c
index 24ee5a9..1e301e7 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.
+ * Up- and down-propagating, forwarding checking, deductive dependency solver.
*
- * Copyright (C) 2008-2012 Timo Teräs <timo.teras@iki.fi>
+ * Copyright (C) 2008-2013 Timo Teräs <timo.teras@iki.fi>
* All rights reserved.
*
* This program is free software; you can redistribute it and/or modify it
@@ -19,7 +19,6 @@
#include "apk_print.h"
//#define DEBUG_PRINT
-#define DEBUG_CHECKS
#ifdef DEBUG_PRINT
#include <stdio.h>
@@ -28,2029 +27,618 @@
#define dbg_printf(args...)
#endif
-#if defined(DEBUG_PRINT) || defined(DEBUG_CHECKS)
-#define ASSERT(cond, fmt...) \
- if (!(cond)) { apk_error(fmt); *(char*)NULL = 0; }
-#else
-#define ASSERT(cond, fmt...)
-#endif
-
-#define SCORE_ZERO (struct apk_score) { .unsatisfied = 0 }
-#define SCORE_MAX (struct apk_score) { .unsatisfied = -1 }
-#define SCORE_FMT "{%d/%d/%d,%d}"
-#define SCORE_PRINTF(s) (s)->unsatisfied, (s)->non_preferred_actions, (s)->non_preferred_pinnings, (s)->preference
-
-enum {
- DECISION_ASSIGN = 0,
- DECISION_EXCLUDE
-};
-
-enum {
- BRANCH_NO,
- BRANCH_YES,
-};
-
-struct apk_decision {
- struct apk_name *name;
- union {
- struct apk_package *pkg;
- unsigned backup_until;
- };
-#ifdef DEBUG_CHECKS
- struct apk_score saved_score;
- unsigned short saved_requirers;
-#endif
- unsigned short requirers;
- unsigned type : 1;
- unsigned has_package : 1;
- unsigned branching_point : 1;
- unsigned topology_position : 1;
- unsigned found_solution : 1;
-};
-
-struct apk_package_state {
- /* set on startup */
- unsigned int topology_soft;
- unsigned short allowed_pinning_maybe;
-
- /* dynamic */
- unsigned short allowed_pinning;
- unsigned short inherited_pinning[APK_MAX_TAGS];
- unsigned short inherited_upgrade;
- unsigned short inherited_reinstall;
-
- unsigned short conflicts;
- unsigned short unsatisfied;
-
- unsigned char preference;
- unsigned handle_install_if : 1;
- unsigned allowed : 1;
- unsigned locked : 1;
-
- unsigned solver_flags_maybe : 4;
-};
-
-#define CHOSEN_NONE (struct apk_provider) { .pkg = NULL, .version = NULL }
+#define ASSERT(cond, fmt...) if (!(cond)) { apk_error(fmt); *(char*)NULL = 0; }
struct apk_solver_state {
struct apk_database *db;
- struct apk_decision *decisions;
-
- struct list_head unsolved_list_head;
-
- unsigned int num_topology_positions;
- unsigned int num_decisions, max_decisions;
- unsigned int topology_position;
- unsigned int assigned_names;
-
- struct apk_solution_array *best_solution;
-
- struct apk_score score;
- struct apk_score best_score;
- struct apk_score minimum_penalty;
+ struct apk_changeset *changeset;
+ struct list_head dirty_head;
+ struct list_head unresolved_head;
+ unsigned int solver_flags;
+ unsigned int errors;
+ unsigned int num_selections, num_solution_entries;
+};
- unsigned solver_flags : 4;
- unsigned impossible_state : 1;
+static struct apk_provider provider_none = {
+ .pkg = NULL,
+ .version = &apk_null_blob
};
-typedef enum {
- SOLVERR_SOLUTION = 0,
- SOLVERR_PRUNED,
- SOLVERR_EXPAND,
- SOLVERR_STOP,
-} solver_result_t;
-
-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_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)
+void apk_solver_set_name_flags(struct apk_name *name,
+ unsigned short solver_flags,
+ unsigned short solver_flags_inheritable)
{
- struct apk_score orig = *a;
-
- a->unsatisfied += b->unsatisfied;
- a->non_preferred_actions += b->non_preferred_actions;
- a->non_preferred_pinnings += b->non_preferred_pinnings;
- a->preference += b->preference;
-
- ASSERT(a->unsatisfied >= orig.unsatisfied, "Unsatisfied overflow");
- ASSERT(a->non_preferred_actions >= orig.non_preferred_actions, "Preferred action overflow");
- ASSERT(a->non_preferred_pinnings >= orig.non_preferred_pinnings, "Preferred pinning overflow");
- ASSERT(a->preference >= orig.preference, "Preference overflow");
}
-static void subscore(struct apk_score *a, struct apk_score *b)
+static void foreach_dependency(struct apk_solver_state *ss, struct apk_dependency_array *deps,
+ void (*func)(struct apk_solver_state *ss, struct apk_dependency *dep))
{
- struct apk_score orig = *a;
-
- a->unsatisfied -= b->unsatisfied;
- a->non_preferred_actions -= b->non_preferred_actions;
- a->non_preferred_pinnings -= b->non_preferred_pinnings;
- a->preference -= b->preference;
-
- ASSERT(a->unsatisfied <= orig.unsatisfied, "Unsatisfied underflow");
- ASSERT(a->non_preferred_actions <= orig.non_preferred_actions, "Preferred action underflow");
- ASSERT(a->non_preferred_pinnings <= orig.non_preferred_pinnings, "Preferred pinning overflow");
- ASSERT(a->preference <= orig.preference, "Preference underflow");
+ int i;
+ for (i = 0; i < deps->num; i++)
+ func(ss, &deps->item[i]);
}
-static inline int cmpscore(struct apk_score *a, struct apk_score *b)
+static void foreach_name(struct apk_solver_state *ss, struct apk_name_array *names,
+ void (*func)(struct apk_solver_state *ss, struct apk_name *name))
{
- if (a->unsatisfied != b->unsatisfied)
- return a->unsatisfied < b->unsatisfied ? -1 : 1;
- if (a->non_preferred_actions != b->non_preferred_actions)
- return a->non_preferred_actions < b->non_preferred_actions ? -1 : 1;
- if (a->non_preferred_pinnings != b->non_preferred_pinnings)
- return a->non_preferred_pinnings < b->non_preferred_pinnings ? -1 : 1;
- if (a->preference != b->preference)
- return a->preference < b->preference ? -1 : 1;
- return 0;
+ int i;
+ for (i = 0; i < names->num; i++)
+ if (names->item[i]->ss.seen)
+ func(ss, names->item[i]);
}
-static inline int cmpscore2(struct apk_score *a1, struct apk_score *a2, struct apk_score *b)
+static void queue_dirty(struct apk_solver_state *ss, struct apk_name *name)
{
- struct apk_score a = *a1;
- addscore(&a, a2);
- return cmpscore(&a, b);
-}
+ if (list_hashed(&name->ss.dirty_list) || name->ss.locked ||
+ (name->ss.requirers == 0 && !name->ss.reevaluate_iif))
+ return;
-static struct apk_package_state *pkg_to_ps(struct apk_package *pkg)
-{
- return (struct apk_package_state*) pkg->state_ptr;
+ dbg_printf("queue_dirty: %s\n", name->name);
+ list_add_tail(&name->ss.dirty_list, &ss->dirty_head);
}
-static struct apk_package_state *pkg_to_ps_alloc(struct apk_package *pkg)
+static void queue_unresolved(struct apk_solver_state *ss, struct apk_name *name)
{
- if (pkg->state_ptr == NULL)
- pkg->state_ptr = calloc(1, sizeof(struct apk_package_state));
- return pkg_to_ps(pkg);
-}
+ int want;
-static inline struct apk_package *decision_to_pkg(struct apk_decision *d)
-{
- return d->has_package ? d->pkg : NULL;
-}
+ if (name->ss.locked)
+ return;
-static inline int pkg_available(struct apk_database *db, struct apk_package *pkg)
-{
- if (pkg->repos & db->available_repos)
- return TRUE;
- return FALSE;
+ want = (name->ss.requirers > 0) || (name->ss.has_iif);
+ dbg_printf("queue_unresolved: %s, want=%d\n", name->name, want);
+ if (want && !list_hashed(&name->ss.unresolved_list))
+ list_add(&name->ss.unresolved_list, &ss->unresolved_head);
+ else if (!want && list_hashed(&name->ss.unresolved_list))
+ list_del_init(&name->ss.unresolved_list);
}
-static void foreach_dependency_pkg(
- struct apk_solver_state *ss, struct apk_package *parent_package, struct apk_dependency_array *depends,
- void (*cb)(struct apk_solver_state *ss, struct apk_package *dependency, struct apk_package *parent_package))
+static void reevaluate_deps(struct apk_solver_state *ss, struct apk_name *name)
{
- int i, j;
-
- /* And sort the main dependencies */
- for (i = 0; i < depends->num; i++) {
- struct apk_dependency *dep = &depends->item[i];
- struct apk_name *name0 = dep->name;
-
- for (j = 0; j < name0->providers->num; j++) {
- struct apk_provider *p0 = &name0->providers->item[j];
-
- /* conflict depends on all to be not installed */
- if (!apk_dep_is_provided(dep, p0))
- continue;
-
- cb(ss, p0->pkg, parent_package);
- }
- }
+ name->ss.reevaluate_deps = 1;
+ queue_dirty(ss, name);
}
-static void foreach_rinstall_if_pkg(
- struct apk_solver_state *ss, struct apk_package *pkg,
- void (*cb)(struct apk_solver_state *ss, struct apk_package *rinstall_if, struct apk_package *parent_pkg))
+static void reevaluate_installif(struct apk_solver_state *ss, struct apk_name *name)
{
- struct apk_name *name = pkg->name;
- int i, j, k;
-
- for (i = 0; i < pkg->name->rinstall_if->num; i++) {
- struct apk_name *name0 = pkg->name->rinstall_if->item[i];
-
- dbg_printf(PKG_VER_FMT ": rinstall_if %s\n",
- PKG_VER_PRINTF(pkg), name0->name);
-
- for (j = 0; j < name0->providers->num; j++) {
- struct apk_provider *p0 = &name0->providers->item[j];
-
- for (k = 0; k < p0->pkg->install_if->num; k++) {
- struct apk_dependency *dep = &p0->pkg->install_if->item[k];
-
- if (dep->name == name &&
- apk_dep_is_provided(dep, p0))
- break;
- }
- if (k >= p0->pkg->install_if->num)
- continue;
-
- /* pkg depends (via install_if) on pkg0 */
- cb(ss, p0->pkg, pkg);
- }
- }
+ name->ss.reevaluate_iif = 1;
+ queue_dirty(ss, name);
}
-static unsigned int get_pinning_mask_repos(struct apk_database *db, unsigned short pinning_mask)
+static void disqualify_package(struct apk_solver_state *ss, struct apk_package *pkg, const char *reason)
{
- 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 get_topology_score(
- struct apk_solver_state *ss,
- struct apk_name *name,
- struct apk_package *pkg,
- struct apk_score *_score)
-{
- struct apk_package_state *ps = pkg_to_ps(pkg);
- struct apk_score score;
- unsigned int repos;
- unsigned short preferred_pinning, allowed_pinning;
- unsigned int preferred_repos, allowed_repos;
- int score_locked = TRUE, sticky_installed = FALSE;
-
- score = (struct apk_score) {
- .unsatisfied = ps->unsatisfied,
- .preference = ps->preference,
- };
-
- if (ss->solver_flags & APK_SOLVERF_AVAILABLE) {
- /* available preferred */
- if ((pkg->repos == 0) && name->ss.has_available_pkgs)
- score.non_preferred_actions++;
- } else if (ps->inherited_reinstall ||
- (((name->ss.solver_flags_local|ss->solver_flags) & APK_SOLVERF_REINSTALL))) {
- /* reinstall requested, but not available */
- if (!pkg_available(ss->db, pkg))
- score.non_preferred_actions++;
- } else if (ps->inherited_upgrade ||
- ((name->ss.solver_flags_local|ss->solver_flags) & APK_SOLVERF_UPGRADE)) {
- /* upgrading - score is just locked here */
- } else if ((ps->inherited_upgrade == 0) &&
- ((name->ss.solver_flags_local|ss->solver_flags) & APK_SOLVERF_UPGRADE) == 0 &&
- ((ps->solver_flags_maybe & APK_SOLVERF_UPGRADE) == 0 || (ps->locked))) {
- /* not upgrading: it is not preferred to change package */
- if (pkg->ipkg == NULL && name->ss.originally_installed)
- score.non_preferred_actions++;
- else
- sticky_installed = TRUE;
- } else {
- score_locked = FALSE;
- }
-
- repos = pkg->repos | (pkg->ipkg ? ss->db->repo_tags[pkg->ipkg->repository_tag].allowed_repos : 0);
- preferred_pinning = name->ss.preferred_pinning ?: APK_DEFAULT_PINNING_MASK;
- preferred_repos = get_pinning_mask_repos(ss->db, preferred_pinning);
-
- if (!(repos & preferred_repos))
- score.non_preferred_pinnings++;
-
- if (ps->locked || (ps->allowed_pinning | ps->allowed_pinning_maybe) == ps->allowed_pinning) {
- allowed_pinning = ps->allowed_pinning | preferred_pinning | APK_DEFAULT_PINNING_MASK;
- allowed_repos = get_pinning_mask_repos(ss->db, allowed_pinning);
- if (!(repos & allowed_repos)) {
- if (sticky_installed)
- score.non_preferred_actions++;
- score.non_preferred_pinnings += 16;
- }
- } else {
- score_locked = FALSE;
- }
+ dbg_printf("disqualify_package: " PKG_VER_FMT " (%s)\n", PKG_VER_PRINTF(pkg), reason);
+ pkg->ss.available = 0;
- *_score = score;
- return score_locked;
+ foreach_name(ss, pkg->name->rdepends, reevaluate_deps);
+ for (i = 0; i < pkg->provides->num; i++)
+ foreach_name(ss, pkg->provides->item[i].name->rdepends, reevaluate_deps);
+ foreach_name(ss, pkg->name->rinstall_if, reevaluate_installif);
}
-static int compare_absolute_package_preference(
- struct apk_provider *pA,
- struct apk_provider *pB)
+static int dependency_satisfiable(struct apk_solver_state *ss, struct apk_dependency *dep)
{
- struct apk_package *pkgA = pA->pkg;
- struct apk_package *pkgB = pB->pkg;
-
- /* 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_version_compare_blob(*pA->version, *pB->version)) {
- 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;
+ struct apk_name *name = dep->name;
+ int i;
- /* prefer the one with lowest available repository */
- return ffsl(pkgB->repos) - ffsl(pkgA->repos);
-}
+ if (name->ss.locked)
+ return apk_dep_is_provided(dep, &name->ss.chosen);
-static void calculate_pkg_preference(struct apk_package *pkg)
-{
- struct apk_name *name = pkg->name;
- struct apk_package_state *ps = pkg_to_ps(pkg);
- struct apk_provider p = APK_PROVIDER_FROM_PACKAGE(pkg);
- int i, j;
+ if (name->ss.requirers == 0 && apk_dep_is_provided(dep, &provider_none))
+ return TRUE;
for (i = 0; i < name->providers->num; i++) {
- struct apk_provider *p0 = &name->providers->item[i];
- if (pkg == p0->pkg)
- continue;
- if (compare_absolute_package_preference(&p, p0) < 0)
- ps->preference++;
- }
- for (i = 0; i < pkg->provides->num; i++) {
- struct apk_dependency *d0 = &pkg->provides->item[i];
- if (d0->version == &apk_null_blob)
+ struct apk_package *pkg = name->providers->item[i].pkg;
+ if (!pkg->ss.available)
continue;
- for (j = 0; j < d0->name->providers->num; j++) {
- struct apk_provider *p0 = &d0->name->providers->item[j];
- if (name == p0->pkg->name)
- continue;
- if (compare_absolute_package_preference(&p, p0) < 0)
- ps->preference++;
- }
+ if (apk_dep_is_provided(dep, &name->providers->item[i]))
+ return TRUE;
}
- dbg_printf(PKG_VER_FMT ": preference=%d\n", PKG_VER_PRINTF(pkg), ps->preference);
-}
-
-static void count_name(struct apk_solver_state *ss, struct apk_name *name)
-{
- if (!name->ss.decision_counted) {
- ss->max_decisions++;
- name->ss.decision_counted = 1;
- }
-}
-
-static void sort_hard_dependencies(struct apk_solver_state *ss,
- struct apk_package *pkg,
- struct apk_package *parent_pkg)
-{
- struct apk_name *name = pkg->name;
- struct apk_package_state *ps;
- int i;
-
- ps = pkg_to_ps_alloc(pkg);
- if (ps->topology_soft)
- return;
- pkg->topology_hard = -1;
- ps->topology_soft = -1;
-
- calculate_pkg_preference(pkg);
-
- /* Consider hard dependencies only */
- foreach_dependency_pkg(ss, pkg, pkg->depends, sort_hard_dependencies);
- foreach_dependency_pkg(ss, pkg, pkg->install_if, sort_hard_dependencies);
-
- ss->max_decisions++;
- name->ss.has_available_pkgs = 1;
- count_name(ss, name);
- for (i = 0; i < pkg->provides->num; i++) {
- pkg->provides->item[i].name->ss.has_available_pkgs = 1;
- count_name(ss, pkg->provides->item[i].name);
- }
-
- 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);
-}
-
-static void sort_soft_dependencies(struct apk_solver_state *ss,
- struct apk_package *pkg,
- struct apk_package *parent_pkg)
-{
- struct apk_package_state *ps;
- struct apk_package_state *parent_ps;
-
- sort_hard_dependencies(ss, pkg, parent_pkg);
-
- ps = pkg_to_ps(pkg);
- if (ps->topology_soft != pkg->topology_hard)
- return;
- ps->topology_soft = -1;
-
- /* Update state */
- parent_ps = pkg_to_ps(parent_pkg);
- ps->allowed_pinning_maybe |= parent_ps->allowed_pinning_maybe;
- ps->solver_flags_maybe |= parent_ps->solver_flags_maybe;
-
- /* Soft reverse dependencies aka. install_if */
- foreach_rinstall_if_pkg(ss, pkg, sort_hard_dependencies);
- foreach_dependency_pkg(ss, pkg, pkg->depends, sort_soft_dependencies);
-
- /* Assign a topology sorting order */
- ps->topology_soft = ++ss->num_topology_positions;
- dbg_printf(PKG_VER_FMT ": topology_soft=%d\n",
- PKG_VER_PRINTF(pkg), ps->topology_soft);
+ return FALSE;
}
-static void update_allowed(struct apk_database *db, struct apk_package *pkg)
+static void discover_name(struct apk_solver_state *ss, struct apk_name *name);
+static void discover_names(struct apk_solver_state *ss, struct apk_dependency *dep)
{
- struct apk_package_state *ps = pkg_to_ps(pkg);
- unsigned int repos;
-
- repos = pkg->repos | (pkg->ipkg ? db->repo_tags[pkg->ipkg->repository_tag].allowed_repos : 0);
- if (repos & get_pinning_mask_repos(db, ps->allowed_pinning | APK_DEFAULT_PINNING_MASK))
- ps->allowed = 1;
- else
- ps->allowed = 0;
+ discover_name(ss, dep->name);
}
-static void sort_name(struct apk_solver_state *ss, struct apk_name *name)
+static void discover_name(struct apk_solver_state *ss, struct apk_name *name)
{
+ struct apk_database *db = ss->db;
int i, j;
+ unsigned long mask = apk_db_get_pinning_mask_repos(ss->db, APK_DEFAULT_PINNING_MASK);
+ if (name->ss.seen)
+ return;
+ name->ss.seen = 1;
for (i = 0; i < name->providers->num; i++) {
struct apk_package *pkg = name->providers->item[i].pkg;
- struct apk_package_state *ps = pkg_to_ps_alloc(pkg);
- unsigned short allowed_pinning;
-
- ps->allowed_pinning |= name->ss.preferred_pinning;
- ps->allowed_pinning_maybe |= name->ss.preferred_pinning;
-
- allowed_pinning = ps->allowed_pinning;
- for (j = 0; allowed_pinning; j++) {
- if (!(allowed_pinning & BIT(j)))
- continue;
- allowed_pinning &= ~BIT(j);
- ps->inherited_pinning[j]++;
- }
- update_allowed(ss->db, pkg);
- sort_soft_dependencies(ss, name->providers->item[i].pkg, pkg);
+ if (pkg->ss.seen)
+ continue;
+ pkg->ss.seen = 1;
+ if ((pkg->ipkg != NULL) ||
+ (pkg->repos & db->available_repos & mask))
+ pkg->ss.available = 1;
+ foreach_dependency(ss, pkg->depends, discover_names);
+ for (j = 0; j < pkg->depends->num; j++)
+ pkg->ss.max_dep_chain = max(pkg->ss.max_dep_chain, name->ss.max_dep_chain+1);
+ name->ss.max_dep_chain = max(name->ss.max_dep_chain, pkg->ss.max_dep_chain);
}
+ /* Can't use foreach_name, as it checks the seen flag */
+ for (i = 0; i < name->rinstall_if->num; i++)
+ discover_name(ss, name->rinstall_if->item[i]);
}
-static void foreach_dependency(struct apk_solver_state *ss, struct apk_dependency_array *deps,
- void (*func)(struct apk_solver_state *ss, struct apk_dependency *dep))
+static void name_requirers_changed(struct apk_solver_state *ss, struct apk_name *name)
{
- int i;
- for (i = 0; i < deps->num; i++)
- func(ss, &deps->item[i]);
+ queue_unresolved(ss, name);
+ foreach_name(ss, name->rinstall_if, reevaluate_installif);
+ queue_dirty(ss, name);
}
-static int install_if_missing(struct apk_solver_state *ss, struct apk_package *pkg, struct apk_name *exclude)
+static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
{
- int i, missing = 0;
-
- for (i = 0; i < pkg->install_if->num; i++) {
- struct apk_dependency *dep = &pkg->install_if->item[i];
- struct apk_name *name = dep->name;
+ struct apk_name *name = dep->name;
+ int i;
- if (name == exclude ||
- !name->ss.locked || !apk_dep_is_provided(dep, &name->ss.chosen))
- missing++;
- }
+ dbg_printf("apply_constraint: %s%s%s" BLOB_FMT "\n",
+ dep->conflict ? "!" : "",
+ name->name,
+ apk_version_op_string(dep->result_mask),
+ BLOB_PRINTF(*dep->version));
- return missing;
-}
+ name->ss.requirers += !dep->conflict;
+ name_requirers_changed(ss, name);
-static void get_unassigned_score(struct apk_name *name, struct apk_score *score)
-{
- *score = (struct apk_score){
- .unsatisfied = name->ss.requirers,
- .preference = name->providers->num,
- };
-}
-
-static void promote_name(struct apk_solver_state *ss, struct apk_name *name)
-{
- if (name->ss.locked)
- return;
+ for (i = 0; i < name->providers->num; i++) {
+ struct apk_provider *p0 = &name->providers->item[i];
+ struct apk_package *pkg0 = p0->pkg;
+ int is_provided;
- /* queue for handling if needed */
- if (!list_hashed(&name->ss.unsolved_list))
- list_add_tail(&name->ss.unsolved_list, &ss->unsolved_list_head);
+ is_provided = apk_dep_is_provided(dep, p0);
+ dbg_printf("apply_constraint: provider: %s-" BLOB_FMT ": %d\n",
+ pkg0->name->name, BLOB_PRINTF(*p0->version), is_provided);
- /* update info, but no cached information flush is required, as
- * minimum_penalty can only go up */
- name->ss.name_touched = 1;
+ pkg0->ss.conflicts += !is_provided;
+ if (unlikely(pkg0->ss.available && pkg0->ss.conflicts))
+ disqualify_package(ss, pkg0, "conflicting dependency");
+ }
}
-static void demote_name(struct apk_solver_state *ss, struct apk_name *name)
+static void reconsider_name(struct apk_solver_state *ss, struct apk_name *name)
{
- if (name->ss.locked)
- return;
+ struct apk_name *name0;
+ struct apk_dependency *dep;
+ struct apk_package *pkg;
+ int i, j, reevaluate_deps, reevaluate_iif;
+ int first_candidate = -1, last_candidate = 0;
+ int num_options = 0, has_iif = 0;
- /* remove cached information */
- name->ss.chosen = CHOSEN_NONE;
+ dbg_printf("reconsider_name: %s\n", name->name);
- /* and remove list, or request refresh */
- if (name->ss.requirers == 0 && name->ss.install_ifs == 0) {
- if (list_hashed(&name->ss.unsolved_list)) {
- list_del(&name->ss.unsolved_list);
- list_init(&name->ss.unsolved_list);
- dbg_printf("%s: not required\n", name->name);
- }
- } else {
- /* still needed, put back to list */
- promote_name(ss, name);
- }
-}
+ reevaluate_deps = name->ss.reevaluate_deps;
+ name->ss.reevaluate_deps = 0;
-static int inherit_package_state(struct apk_database *db, struct apk_package *to, struct apk_package *from)
-{
- struct apk_name *fname = from->name;
- struct apk_package_state *tps = pkg_to_ps(to);
- struct apk_package_state *fps = pkg_to_ps(from);
- int i, changed = 0;
-
- if ((fname->ss.solver_flags_inheritable & APK_SOLVERF_REINSTALL) ||
- fps->inherited_reinstall) {
- tps->inherited_reinstall++;
- changed = 1;
- }
+ reevaluate_iif = name->ss.reevaluate_iif;
+ name->ss.reevaluate_iif = 0;
- if ((fname->ss.solver_flags_inheritable & APK_SOLVERF_UPGRADE) ||
- fps->inherited_upgrade) {
- tps->inherited_upgrade++;
- changed = 1;
- }
+ /* propagate down by merging common dependencies and
+ * applying new constraints */
+ for (i = 0; i < name->providers->num; i++) {
+ struct apk_provider *p0 = &name->providers->item[i];
+ struct apk_package *pkg = p0->pkg;
- if (fps->allowed_pinning) {
- unsigned short allowed_pinning = fps->allowed_pinning;
- for (i = 0; allowed_pinning && i < db->num_repo_tags; i++) {
- if (!(allowed_pinning & BIT(i)))
+ /* check if this pkg's dependencies have become unsatisfiable */
+ if (reevaluate_deps) {
+ if (!pkg->ss.available)
continue;
- allowed_pinning &= ~BIT(i);
- if (tps->inherited_pinning[i]++ == 0) {
- tps->allowed_pinning |= BIT(i);
- changed = 2;
+ for (j = 0; j < pkg->depends->num; j++) {
+ dep = &pkg->depends->item[j];
+ if (!dependency_satisfiable(ss, dep)) {
+ disqualify_package(ss, pkg, "dependency no longer satisfiable");
+ break;
+ }
}
}
- if (changed == 2)
- update_allowed(db, to);
- }
-
- return changed;
-}
+ if (!pkg->ss.available)
+ continue;
-static void uninherit_package_state(struct apk_database *db, struct apk_package *to, struct apk_package *from)
-{
- struct apk_name *fname = from->name;
- struct apk_package_state *tps = pkg_to_ps(to);
- struct apk_package_state *fps = pkg_to_ps(from);
- int i, changed = 0;
-
- if ((fname->ss.solver_flags_inheritable & APK_SOLVERF_REINSTALL) ||
- fps->inherited_reinstall)
- tps->inherited_reinstall--;
-
- if ((fname->ss.solver_flags_inheritable & APK_SOLVERF_UPGRADE) ||
- fps->inherited_upgrade)
- tps->inherited_upgrade--;
-
- if (fps->allowed_pinning) {
- unsigned short allowed_pinning = fps->allowed_pinning;
- for (i = 0; allowed_pinning && i < db->num_repo_tags; i++) {
- if (!(allowed_pinning & BIT(i)))
- continue;
- allowed_pinning &= ~BIT(i);
- if (--tps->inherited_pinning[i] == 0) {
- tps->allowed_pinning &= ~BIT(i);
- changed = 2;
+ if (reevaluate_iif) {
+ for (j = 0; j < pkg->install_if->num; j++) {
+ dep = &pkg->install_if->item[j];
+ if (!dependency_satisfiable(ss, dep))
+ break;
}
+ pkg->ss.iif_triggered = (j >= pkg->install_if->num);
+ has_iif |= pkg->ss.iif_triggered;
}
- if (changed == 2)
- update_allowed(db, to);
- }
-}
-
-static void trigger_install_if(struct apk_solver_state *ss,
- struct apk_package *pkg,
- struct apk_package *parent_pkg)
-{
- struct apk_name *name = pkg->name;
-
- if (install_if_missing(ss, pkg, NULL) != 0)
- return;
-
- dbg_printf("trigger_install_if: " PKG_VER_FMT " triggered\n",
- PKG_VER_PRINTF(pkg));
- name->ss.install_ifs++;
- inherit_package_state(ss->db, pkg, parent_pkg);
- promote_name(ss, name);
-}
-
-static void untrigger_install_if(struct apk_solver_state *ss,
- struct apk_package *pkg,
- struct apk_package *parent_pkg)
-{
- struct apk_name *name = pkg->name;
-
- if (install_if_missing(ss, pkg, parent_pkg->name) != 0)
- return;
- dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n",
- PKG_VER_PRINTF(pkg));
- name->ss.install_ifs--;
- uninherit_package_state(ss->db, pkg, parent_pkg);
- demote_name(ss, name);
-}
+ if (name->ss.requirers == 0 && !pkg->ss.iif_triggered)
+ continue;
-static inline void assign_name(
- struct apk_solver_state *ss, struct apk_name *name, struct apk_provider p)
-{
- if (name->ss.locked &&
- (p.version != &apk_null_blob || name->ss.chosen.version != &apk_null_blob)) {
- /* Assigning locked name with version is a problem;
- * generally package providing same name twice */
- dbg_printf("%s: re-provided by %s\n", name->name, p.pkg->name->name);
- name->ss.locked++;
- ss->impossible_state = 1;
- return;
- }
- if (!name->ss.locked) {
- struct apk_package *pkg = p.pkg;
-
- subscore(&ss->minimum_penalty, &name->ss.minimum_penalty);
- name->ss.minimum_penalty = SCORE_ZERO;
- name->ss.chosen = p;
-
- if (name->ss.requirers) {
- struct apk_score score;
- if (pkg != NULL)
- get_topology_score(ss, name, pkg, &score);
- else
- get_unassigned_score(name, &score);
- addscore(&ss->score, &score);
- }
- }
- name->ss.locked++;
- if (list_hashed(&name->ss.unsolved_list)) {
- list_del(&name->ss.unsolved_list);
- list_init(&name->ss.unsolved_list);
- }
-}
+ num_options++;
-static inline void unassign_name(struct apk_solver_state *ss, struct apk_name *name)
-{
- ASSERT(name->ss.locked, "Unassigning unlocked name %s", name->name);
- name->ss.locked--;
- if (name->ss.locked == 0) {
- struct apk_package *pkg = name->ss.chosen.pkg;
-
- name->ss.chosen = CHOSEN_NONE;
- name->ss.name_touched = 1;
- demote_name(ss, name);
-
- if (name->ss.requirers) {
- struct apk_score score;
- if (pkg != NULL)
- get_topology_score(ss, name, pkg, &score);
- else
- get_unassigned_score(name, &score);
- subscore(&ss->score, &score);
+ /* merge common dependencies */
+ if (first_candidate == -1)
+ first_candidate = i;
+ for (j = 0; j < pkg->depends->num; j++) {
+ dep = &pkg->depends->item[j];
+ if (dep->conflict /*&& dep->result_mask != APK_DEPMASK_ANY*/)
+ continue;
+ name0 = dep->name;
+ if (name0->ss.merge_index == last_candidate)
+ name0->ss.merge_index = i + 1;
+ }
+ last_candidate = i + 1;
+ }
+ name->ss.has_options = (num_options > 1);
+ name->ss.has_iif = has_iif;
+ queue_unresolved(ss, name);
+
+ if (first_candidate != -1) {
+ /* TODO: could merge versioning bits too */
+ /* propagate down common dependencies */
+ pkg = name->providers->item[first_candidate].pkg;
+ for (j = 0; j < pkg->depends->num; j++) {
+ dep = &pkg->depends->item[j];
+ if (dep->conflict && dep->result_mask != APK_DEPMASK_ANY)
+ continue;
+ name0 = dep->name;
+ if (name0->ss.merge_index == last_candidate) {
+ /* common dependency name with all */
+ if (name0->ss.requirers == 0) {
+ dbg_printf("%s common dependency: %s\n",
+ name->name, name0->name);
+ name0->ss.requirers++;
+ name_requirers_changed(ss, name0);
+ }
+ }
+ name0->ss.merge_index = 0;
}
}
+ dbg_printf("reconsider_name: %s [finished]\n", name->name);
}
-static solver_result_t apply_decision(struct apk_solver_state *ss,
- struct apk_decision *d)
+static int compare_providers(struct apk_solver_state *ss,
+ struct apk_provider *pA, struct apk_provider *pB)
{
- struct apk_name *name = d->name;
- struct apk_package *pkg = decision_to_pkg(d);
- int i;
-
- ss->impossible_state = 0;
- name->ss.name_touched = 1;
- 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");
-
- for (i = 0; i < pkg->provides->num; i++)
- pkg->provides->item[i].name->ss.name_touched = 1;
-
- ps->locked = 1;
+ struct apk_database *db = ss->db;
+ struct apk_package *pkgA = pA->pkg, *pkgB = pB->pkg;
+ int r;
- if (d->type == DECISION_ASSIGN &&
- ps->topology_soft < ss->topology_position) {
- ps->handle_install_if = 1;
- dbg_printf("triggers due to " PKG_VER_FMT "\n",
- PKG_VER_PRINTF(pkg));
- } else {
- ps->handle_install_if = 0;
- }
+ /* Prefer existing package */
+ if (pkgA == NULL || pkgB == NULL)
+ return (pkgA != NULL) - (pkgB != NULL);
- if (d->topology_position) {
- if (ps->topology_soft < ss->topology_position)
- ss->topology_position = ps->topology_soft;
- else
- ss->topology_position = pkg->topology_hard;
- }
-
- if (d->type == DECISION_ASSIGN) {
- ss->assigned_names++;
- assign_name(ss, name, APK_PROVIDER_FROM_PACKAGE(pkg));
- for (i = 0; i < pkg->provides->num; i++) {
- struct apk_dependency *p = &pkg->provides->item[i];
- assign_name(ss, p->name, APK_PROVIDER_FROM_PROVIDES(pkg, p));
- }
+ /* Prefer without errors */
+ r = (int)pkgA->ss.available - (int)pkgB->ss.available;
+ if (r)
+ return r;
- foreach_dependency(ss, pkg->depends, apply_constraint);
- if (ps->handle_install_if)
- foreach_rinstall_if_pkg(ss, pkg, trigger_install_if);
- }
- } else {
- dbg_printf("-->apply_decision: %s %s NOTHING\n",
- name->name,
- (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
-
- if (d->type == DECISION_ASSIGN) {
- assign_name(ss, name, CHOSEN_NONE);
- } else {
- name->ss.none_excluded = 1;
- }
+ /* Prefer available */
+ if (ss->solver_flags & APK_SOLVERF_AVAILABLE) {
+ r = !!(pkgA->repos & db->available_repos) -
+ !!(pkgB->repos & db->available_repos);
+ if (r)
+ return r;
}
- if (ss->impossible_state) {
- dbg_printf("%s: %s impossible constraints\n",
- name->name,
- (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
- return SOLVERR_PRUNED;
+ /* Prefer installed */
+ /* FIXME: check-per-name flags here too */
+ if (!(ss->solver_flags & APK_SOLVERF_UPGRADE)) {
+ r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
+ if (r)
+ return r;
}
- if (cmpscore2(&ss->score, &ss->minimum_penalty, &ss->best_score) >= 0) {
- 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;
+ /* Select latest by requested name */
+ switch (apk_version_compare_blob(*pA->version, *pB->version)) {
+ case APK_VERSION_LESS:
+ return -1;
+ case APK_VERSION_GREATER:
+ return 1;
}
- return SOLVERR_EXPAND;
-}
-
-static void undo_decision(struct apk_solver_state *ss,
- struct apk_decision *d)
-{
- struct apk_name *name = d->name;
- struct apk_package *pkg = decision_to_pkg(d);
- int i;
-
- name->ss.name_touched = 1;
-
- if (pkg != NULL) {
- struct apk_package_state *ps = pkg_to_ps(pkg);
-
- 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;
- }
-
- for (i = 0; i < pkg->provides->num; i++)
- pkg->provides->item[i].name->ss.name_touched = 1;
-
- if (d->type == DECISION_ASSIGN) {
- if (ps->handle_install_if)
- foreach_rinstall_if_pkg(ss, pkg, untrigger_install_if);
- foreach_dependency(ss, pkg->depends, undo_constraint);
-
- unassign_name(ss, pkg->name);
- for (i = 0; i < pkg->provides->num; i++) {
- struct apk_dependency *p = &pkg->provides->item[i];
- unassign_name(ss, p->name);
- }
- ss->assigned_names--;
- }
- ps->locked = 0;
- } else {
- dbg_printf("-->undo_decision: %s %s NOTHING\n",
- name->name,
- (d->type == DECISION_ASSIGN) ? "ASSIGN" : "EXCLUDE");
-
- if (d->type == DECISION_ASSIGN) {
- unassign_name(ss, name);
- } else {
- name->ss.none_excluded = 0;
+ /* Select latest by principal name */
+ if (pkgA->name == pkgB->name) {
+ switch (apk_version_compare_blob(*pkgA->version, *pkgB->version)) {
+ case APK_VERSION_LESS:
+ return -1;
+ case APK_VERSION_GREATER:
+ return 1;
}
-
- /* Put back the name to unsolved list */
- promote_name(ss, name);
- }
-}
-
-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_decision *d;
- int i;
-
- ASSERT(ss->num_decisions <= ss->max_decisions,
- "Decision tree overflow.");
-
- ss->num_decisions++;
- d = &ss->decisions[ss->num_decisions];
-
-#ifdef DEBUG_CHECKS
- dbg_printf("Saving score ("SCORE_FMT") and requirers (%d) for %s\n",
- SCORE_PRINTF(&ss->score), name->ss.requirers, name->name);
- d->saved_score = ss->score;
- d->saved_requirers = name->ss.requirers;
-#endif
- d->type = primary_decision;
- d->branching_point = branching_point;
- d->topology_position = topology_position;
- d->found_solution = 0;
- d->name = name;
- d->requirers = name->ss.requirers;
- if (pkg) {
- d->has_package = 1;
- d->pkg = pkg;
- for (i = 0; i < pkg->provides->num; i++)
- d->requirers += pkg->provides->item[i].name->ss.requirers;
- } else {
- d->has_package = 0;
- d->backup_until = name->ss.last_touched_decision;
}
- return apply_decision(ss, d);
-}
-
-static int next_branch(struct apk_solver_state *ss)
-{
- unsigned int backup_until = ss->num_decisions;
-
- while (ss->num_decisions > 0) {
- struct apk_decision *d = &ss->decisions[ss->num_decisions];
- struct apk_name *name = d->name;
-
- undo_decision(ss, d);
-
-#ifdef DEBUG_CHECKS
- ASSERT(cmpscore(&d->saved_score, &ss->score) == 0,
- "Saved_score "SCORE_FMT" != score "SCORE_FMT,
- SCORE_PRINTF(&d->saved_score),
- SCORE_PRINTF(&ss->score));
- ASSERT(d->saved_requirers == name->ss.requirers,
- "Requirers not restored between decisions (%s), %d != %d",
- name->name, d->saved_requirers, name->ss.requirers);
-#endif
-
- if (backup_until >= ss->num_decisions &&
- 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);
- } else if (d->branching_point == BRANCH_YES) {
- dbg_printf("skipping %s, %d < %d\n",
- name->name, backup_until, ss->num_decisions);
- }
-
- /* When undoing the initial "exclude none" decision, check if
- * we can backjump. */
- if (d->has_package == 0 && !d->found_solution) {
- if (d->backup_until && d->backup_until < backup_until) {
- backup_until = d->backup_until;
- /* We can't backtrack over the immediate
- * EXCLUDE decisions, as they are in a sense
- * part of the bundle. */
- while (backup_until < ss->num_decisions &&
- !ss->decisions[backup_until+1].has_package)
- backup_until++;
- }
- }
-
- ss->num_decisions--;
- }
+ /* Prefer installed (matches here if upgrading) */
+ r = (pkgA->ipkg != NULL) - (pkgB->ipkg != NULL);
+ if (r)
+ return r;
- dbg_printf("-->next_branch: no more branches\n");
- return SOLVERR_STOP;
+ /* Prefer lowest available repository */
+ return ffsl(pkgB->repos) - ffsl(pkgA->repos);
}
-static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
+static inline void assign_name(struct apk_solver_state *ss, struct apk_name *name, struct apk_provider p)
{
- struct apk_decision *d = &ss->decisions[ss->num_decisions];
- struct apk_package *requirer_pkg = decision_to_pkg(d);
- struct apk_name *name = dep->name;
- int i, changed = 0, strength = d->requirers;
-
- dbg_printf("--->apply_constraint: %s (strength %d)\n", name->name, strength);
+ int i;
if (name->ss.locked) {
- if (name->ss.chosen.pkg)
- dbg_printf("%s: locked to " PKG_VER_FMT " already\n",
- name->name, PKG_VER_PRINTF(name->ss.chosen.pkg));
- else
- dbg_printf("%s: locked to empty\n",
- name->name);
- if (!apk_dep_is_provided(dep, &name->ss.chosen)) {
- dbg_printf("%s: constraint violation %d\n",
- name->name, strength);
- ss->score.unsatisfied += strength;
- if (dep->conflict)
- ss->impossible_state = 1;
- }
- return;
- }
-
- if (name->providers->num == 0) {
- if (!dep->conflict)
- ss->score.unsatisfied += strength;
+ /* If both are providing this name without version, it's ok */
+ if (p.version == &apk_null_blob &&
+ name->ss.chosen.version == &apk_null_blob)
+ return;
+ /* Othewise providing locked item is an error */
+ ss->errors++;
return;
}
- for (i = 0; i < name->providers->num; i++) {
- struct apk_provider *p0 = &name->providers->item[i];
- struct apk_package *pkg0 = p0->pkg;
- struct apk_package_state *ps0 = pkg_to_ps(pkg0);
-
- if (ps0 == NULL || ps0->locked ||
- ss->topology_position < pkg0->topology_hard)
- continue;
+ dbg_printf("assign %s to "PKG_VER_FMT"\n", name->name, PKG_VER_PRINTF(p.pkg));
- if (!apk_dep_is_provided(dep, p0)) {
- if (dep->conflict)
- ps0->conflicts++;
- else
- ps0->unsatisfied++;
-
- dbg_printf(PKG_VER_FMT ": conflicts++ -> %d\n",
- PKG_VER_PRINTF(pkg0),
- ps0->conflicts);
- changed |= 1;
- } else if (requirer_pkg != NULL) {
- dbg_printf(PKG_VER_FMT ": inheriting flags and pinning from "PKG_VER_FMT"\n",
- PKG_VER_PRINTF(pkg0),
- PKG_VER_PRINTF(requirer_pkg));
- changed |= inherit_package_state(ss->db, pkg0, requirer_pkg);
- }
- }
-
- if (name->ss.last_touched_decision == 0 || changed) {
- dep->solver_state = name->ss.last_touched_decision + 1;
- name->ss.last_touched_decision = ss->num_decisions;
- }
-
- if (!dep->conflict) {
- dbg_printf("%s requirers += %d\n", name->name, strength);
- name->ss.requirers += strength;
- }
-
- promote_name(ss, name);
-}
-
-static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *dep)
-{
- struct apk_decision *d = &ss->decisions[ss->num_decisions];
- struct apk_name *name = dep->name;
- struct apk_package *requirer_pkg = decision_to_pkg(d);
- int i, strength = d->requirers;
-
- dbg_printf("--->undo_constraint: %s (strength %d)\n", name->name, strength);
-
- if (name->ss.locked) {
- if (name->ss.chosen.pkg != NULL) {
- dbg_printf(PKG_VER_FMT " selected already for %s\n",
- PKG_VER_PRINTF(name->ss.chosen.pkg), name->name);
- } else {
- dbg_printf("%s selected to not be satisfied\n",
- name->name);
- }
- if (!apk_dep_is_provided(dep, &name->ss.chosen))
- ss->score.unsatisfied -= strength;
- return;
- }
- if (name->providers->num == 0) {
- if (!dep->conflict)
- ss->score.unsatisfied -= strength;
- return;
- }
+ name->ss.locked = 1;
+ name->ss.chosen = p;
+ if (list_hashed(&name->ss.unresolved_list))
+ list_del(&name->ss.unresolved_list);
+ if (list_hashed(&name->ss.dirty_list))
+ list_del(&name->ss.dirty_list);
+ /* disqualify all conflicting packages */
for (i = 0; i < name->providers->num; i++) {
- struct apk_provider *p0 = &name->providers->item[i];
- struct apk_package *pkg0 = p0->pkg;
- struct apk_package_state *ps0 = pkg_to_ps(pkg0);
-
- if (ps0 == NULL || ps0->locked ||
- ss->topology_position < pkg0->topology_hard)
+ if (name->providers->item[i].pkg == p.pkg)
continue;
-
- if (!apk_dep_is_provided(dep, p0)) {
- if (dep->conflict)
- ps0->conflicts--;
- else
- ps0->unsatisfied--;
- dbg_printf(PKG_VER_FMT ": conflicts-- -> %d\n",
- PKG_VER_PRINTF(pkg0),
- ps0->conflicts);
- } else if (requirer_pkg != NULL) {
- dbg_printf(PKG_VER_FMT ": uninheriting flags and pinning from "PKG_VER_FMT"\n",
- PKG_VER_PRINTF(pkg0),
- PKG_VER_PRINTF(requirer_pkg));
- uninherit_package_state(ss->db, pkg0, requirer_pkg);
- }
- }
-
- if (dep->solver_state) {
- name->ss.last_touched_decision = dep->solver_state - 1;
- dep->solver_state = 0;
- }
-
- if (!dep->conflict) {
- name->ss.requirers -= strength;
- dbg_printf("%s requirers -= %d\n", name->name, strength);
+ if (p.version == &apk_null_blob &&
+ name->providers->item[i].version == &apk_null_blob)
+ continue;
+ disqualify_package(ss, name->providers->item[i].pkg,
+ "conflicting provides");
}
- demote_name(ss, name);
+ foreach_name(ss, name->rdepends, reevaluate_deps);
}
-static int reconsider_name(struct apk_solver_state *ss, struct apk_name *name)
+static void select_package(struct apk_solver_state *ss, struct apk_name *name)
{
- struct apk_provider *next_p = NULL, *best_p = NULL;
- unsigned int next_topology = 0, options = 0;
- int i, j, score_locked = FALSE;
- struct apk_score best_score = SCORE_MAX;
- struct apk_score ss_score;
-
- subscore(&ss->minimum_penalty, &name->ss.minimum_penalty);
- name->ss.minimum_penalty = SCORE_ZERO;
-
- ss_score = ss->score;
- addscore(&ss_score, &ss->minimum_penalty);
-
- if (!name->ss.none_excluded) {
- struct apk_score minscore;
- get_unassigned_score(name, &minscore);
- if (cmpscore2(&ss_score, &minscore, &ss->best_score) >= 0) {
- dbg_printf("%s: pruning none, score too high "SCORE_FMT"+"SCORE_FMT">="SCORE_FMT"\n",
- name->name,
- SCORE_PRINTF(&ss_score),
- SCORE_PRINTF(&minscore),
- SCORE_PRINTF(&ss->best_score));
- return push_decision(ss, name, NULL, DECISION_EXCLUDE, BRANCH_NO, FALSE);
- }
-
- return push_decision(ss, name, NULL, DECISION_EXCLUDE, BRANCH_YES, FALSE);
- }
+ struct apk_provider chosen = { NULL, &apk_null_blob };
+ struct apk_package *pkg = NULL;
+ int i;
- for (i = 0; i < name->providers->num; i++) {
- struct apk_provider *p0 = &name->providers->item[i];
- struct apk_package *pkg0 = p0->pkg;
- struct apk_package_state *ps0 = pkg_to_ps(pkg0);
- struct apk_score pkg0_score;
+ dbg_printf("select_package: %s\n", name->name);
- if (ps0 == NULL || ps0->locked || ps0->conflicts ||
- ss->topology_position < pkg0->topology_hard ||
- (pkg0->ipkg == NULL && pkg0->filename == NULL &&
- (!ps0->allowed || !pkg_available(ss->db, pkg0))))
- continue;
-
- for (j = 0; j < pkg0->provides->num; j++) {
- struct apk_dependency *p00 = &pkg0->provides->item[j];
- if (!p00->name->ss.locked)
+ if (name->ss.requirers || name->ss.has_iif) {
+ for (i = 0; i < name->providers->num; i++) {
+ if (name->ss.requirers == 0 && !name->providers->item[i].pkg->ss.iif_triggered)
continue;
- if (p00->name->ss.chosen.version != &apk_null_blob ||
- p00->version != &apk_null_blob) {
- dbg_printf("reconsider_name: "PKG_VER_FMT": pruning due to provides (%s) conflict\n",
- PKG_VER_PRINTF(pkg0), p00->name->name);
- return push_decision(ss, name, pkg0, DECISION_EXCLUDE, BRANCH_NO, FALSE);
- }
+ if (compare_providers(ss, &name->providers->item[i], &chosen) > 0)
+ chosen = name->providers->item[i];
}
-
- score_locked = get_topology_score(ss, name, pkg0, &pkg0_score);
-
- /* viable alternative? */
- if (cmpscore2(&ss_score, &pkg0_score, &ss->best_score) >= 0) {
- dbg_printf("reconsider_name: "PKG_VER_FMT": pruning due to score "SCORE_FMT"+"SCORE_FMT">="SCORE_FMT"\n",
- PKG_VER_PRINTF(pkg0),
- SCORE_PRINTF(&ss_score), SCORE_PRINTF(&pkg0_score),
- SCORE_PRINTF(&ss->best_score));
- return push_decision(ss, name, pkg0, DECISION_EXCLUDE, BRANCH_NO, FALSE);
- }
-
- if (cmpscore(&pkg0_score, &best_score) < 0) {
- best_score = pkg0_score;
- best_p = p0;
- }
-
- /* next in topology order - next to get locked in */
- if (ps0->topology_soft < ss->topology_position &&
- ps0->topology_soft > next_topology)
- next_p = p0, next_topology = ps0->topology_soft;
- else if (pkg0->topology_hard > next_topology)
- next_p = p0, next_topology = pkg0->topology_hard;
-
- options++;
- }
-
- /* no options left */
- if (options == 0) {
- if (name->ss.none_excluded) {
- dbg_printf("reconsider_name: %s: no options pruning branch\n",
- name->name);
- return SOLVERR_PRUNED;
- }
- dbg_printf("reconsider_name: %s: no options locking none\n",
- name->name);
- return push_decision(ss, name, NULL, DECISION_ASSIGN, BRANCH_NO, FALSE);
- } else if (options == 1 && score_locked && name->ss.none_excluded && name == next_p->pkg->name) {
- dbg_printf("reconsider_name: %s: only one choice left with known score, locking.\n",
- name->name);
- return push_decision(ss, name, next_p->pkg, DECISION_ASSIGN, BRANCH_NO, FALSE);
- }
-
- name->ss.chosen = *next_p;
- name->ss.preferred_chosen = (best_p == next_p);
- name->ss.minimum_penalty = best_score;
- addscore(&ss->minimum_penalty, &best_score);
- for (i = 0; i < best_p->pkg->provides->num; i++) {
- struct apk_dependency *p = &best_p->pkg->provides->item[i];
- get_topology_score(ss, p->name, best_p->pkg, &best_score);
- addscore(&ss->minimum_penalty, &best_score);
}
- dbg_printf("reconsider_name: %s: next_pkg="PKG_VER_FMT", preferred_chosen=%d\n",
- name->name, PKG_VER_PRINTF(next_p->pkg), name->ss.preferred_chosen);
-
- return SOLVERR_SOLUTION;
-}
-
-static int expand_branch(struct apk_solver_state *ss)
-{
- struct apk_name *name0 = NULL, *name;
- struct apk_package *pkg0 = NULL;
- struct apk_package_state *ps0;
- unsigned int r, topology0 = 0;
- int primary_decision, branching_point;
- int can_install = FALSE;
-
- list_for_each_entry(name, &ss->unsolved_list_head, ss.unsolved_list) {
- struct apk_package *cpkg;
- struct apk_package_state *cps;
-
- if (name->ss.name_touched) {
- dbg_printf("%s: reconsidering things\n",
- name->name);
- r = reconsider_name(ss, name);
- if (r != SOLVERR_SOLUTION)
- return r;
- name->ss.name_touched = 0;
- }
- cpkg = name->ss.chosen.pkg;
- cps = pkg_to_ps(cpkg);
- if (cps->topology_soft < ss->topology_position &&
- cps->topology_soft >= topology0) {
- topology0 = cps->topology_soft;
- } else if (cpkg->topology_hard >= topology0) {
- topology0 = cpkg->topology_hard;
- } else {
- continue;
- }
- if (pkg0 != cpkg) {
- can_install = FALSE;
- name0 = name;
+ pkg = chosen.pkg;
+ if (pkg) {
+ if (chosen.version == &apk_null_blob) {
+ /* Pure virtual package */
+ assign_name(ss, name, provider_none);
+ ss->errors++;
+ return;
}
- pkg0 = cpkg;
- if (name->ss.chosen.version != &apk_null_blob) {
- can_install |= TRUE;
- name0 = name;
+ if (!pkg->ss.available)
+ ss->errors++;
+ dbg_printf("selecting: " PKG_VER_FMT ", available: %d\n", PKG_VER_PRINTF(pkg), pkg->ss.available);
+ assign_name(ss, pkg->name, APK_PROVIDER_FROM_PACKAGE(pkg));
+ for (i = 0; i < pkg->provides->num; i++) {
+ struct apk_dependency *p = &pkg->provides->item[i];
+ assign_name(ss, p->name, APK_PROVIDER_FROM_PROVIDES(pkg, p));
}
- }
- if (name0 == NULL || pkg0 == NULL) {
- 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 */
- ps0 = pkg_to_ps(pkg0);
- name = name0;
-
- if (!name->ss.none_excluded) {
- struct apk_package_state *ps0 = pkg_to_ps(pkg0);
- if (ps0->unsatisfied > name->ss.requirers)
- primary_decision = DECISION_ASSIGN;
- else
- primary_decision = DECISION_EXCLUDE;
- return push_decision(ss, name, NULL, primary_decision, BRANCH_YES, FALSE);
- }
-
- if (!can_install) {
- /* provides with no version; not eglible to auto install */
- dbg_printf("expand_branch: "PKG_VER_FMT" not installable. excluding.",
- PKG_VER_PRINTF(pkg0));
- return push_decision(ss, pkg0->name, pkg0, DECISION_EXCLUDE, BRANCH_NO, TRUE);
- }
-
- dbg_printf("expand_branch: "PKG_VER_FMT" score: "SCORE_FMT"+"SCORE_FMT"\tbest: "SCORE_FMT"\n",
- PKG_VER_PRINTF(pkg0),
- SCORE_PRINTF(&ss->score),
- SCORE_PRINTF(&ss->minimum_penalty),
- SCORE_PRINTF(&ss->best_score));
-
- if (!ps0->allowed) {
- /* pinning has not enabled the package */
- 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 (name->ss.requirers == 0 && name->ss.install_ifs != 0 &&
- install_if_missing(ss, pkg0, NULL)) {
- /* not directly required, and package specific
- * install_if never triggered */
- primary_decision = DECISION_EXCLUDE;
- branching_point = BRANCH_NO;
- } else if (name->ss.preferred_chosen) {
- primary_decision = DECISION_ASSIGN;
- branching_point = BRANCH_YES;
+ foreach_dependency(ss, pkg->depends, apply_constraint);
+ ss->num_selections++;
} else {
- primary_decision = DECISION_EXCLUDE;
- branching_point = BRANCH_YES;
+ dbg_printf("selecting: %s [unassigned]\n", name->name);
+ assign_name(ss, name, provider_none);
+ if (name->ss.requirers)
+ ss->errors++;
}
-
- 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)
-{
- int i;
+static void generate_change_dep(struct apk_solver_state *ss, struct apk_dependency *dep);
+static void generate_change_iif(struct apk_solver_state *ss, struct apk_name *name);
- for (i = 0; i < db->num_repo_tags; i++) {
- if (!(BIT(i) & pinning_mask))
- continue;
- if (db->repo_tags[i].allowed_repos & repos)
- return i;
- }
- return APK_DEFAULT_REPOSITORY_TAG;
-}
-
-static void record_solution(struct apk_solver_state *ss)
+static void generate_change(struct apk_solver_state *ss, struct apk_name *name)
{
- struct apk_database *db = ss->db;
- int i, n;
+ struct apk_package *pkg = name->ss.chosen.pkg, *opkg;
+ struct apk_changeset *changeset = ss->changeset;
+ struct apk_change *change;
- apk_solution_array_resize(&ss->best_solution, ss->assigned_names);
+ if (pkg == NULL)
+ return;
- n = 0;
- for (i = ss->num_decisions; i > 0; i--) {
- struct apk_decision *d = &ss->decisions[i];
- struct apk_name *name = d->name;
- struct apk_package *pkg = decision_to_pkg(d);
- struct apk_package_state *ps;
- unsigned short pinning;
- unsigned int repos;
+ if (pkg->ss.in_changeset)
+ return;
+ pkg->ss.in_changeset = 1;
+ pkg->name->ss.in_changeset = 1;
+
+ foreach_dependency(ss, pkg->depends, generate_change_dep);
+
+ change = &changeset->changes->item[ss->num_solution_entries++];
+ dbg_printf("Selecting: "PKG_VER_FMT"%s\n", PKG_VER_PRINTF(pkg), pkg->ss.available ? "" : " [NOT AVAILABLE]");
+ opkg = apk_pkg_get_installed(pkg->name);
+ *change = (struct apk_change) {
+ .old_pkg = opkg,
+ .old_repository_tag = opkg ? opkg->ipkg->repository_tag : 0,
+ .new_pkg = pkg,
+ .new_repository_tag = pkg->ipkg ? pkg->ipkg->repository_tag : 0,
+#if 0
+ /* FIXME: setup reinstall and repository_tag for solution */
+ .reinstall = ps->inherited_reinstall ||
+ ((name->ss.solver_flags_local | ss->solver_flags) & APK_SOLVERF_REINSTALL),
+ .repository_tag = get_tag(db, pinning, repos),
+#endif
+ };
+ if (change->new_pkg == NULL)
+ changeset->num_remove++;
+ else if (change->old_pkg == NULL)
+ changeset->num_install++;
+ else if (change->new_pkg != change->old_pkg || change->reinstall ||
+ change->new_repository_tag != change->old_repository_tag)
+ changeset->num_adjust++;
- d->found_solution = 1;
+ foreach_name(ss, pkg->name->rinstall_if, generate_change_iif);
+}
- if (pkg == NULL) {
- dbg_printf("record_solution: %s: NOTHING\n", name->name);
- continue;
- }
+static void generate_change_iif(struct apk_solver_state *ss, struct apk_name *name)
+{
+ struct apk_package *pkg = name->ss.chosen.pkg;
+ int i;
- dbg_printf("record_solution: " PKG_VER_FMT ": %s\n",
- PKG_VER_PRINTF(pkg),
- d->type == DECISION_ASSIGN ? "INSTALL" : "no install");
+ if (pkg == NULL)
+ return;
- if (d->type != DECISION_ASSIGN)
- continue;
+ for (i = 0; i < pkg->install_if->num; i++) {
+ struct apk_dependency *dep0 = &pkg->install_if->item[i];
+ struct apk_name *name0 = dep0->name;
- ps = pkg_to_ps(pkg);
- pinning = ps->allowed_pinning | name->ss.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");
- ss->best_solution->item[n++] = (struct apk_solution_entry){
- .pkg = pkg,
- .reinstall = ps->inherited_reinstall ||
- ((name->ss.solver_flags_local | ss->solver_flags) & APK_SOLVERF_REINSTALL),
- .repository_tag = get_tag(db, pinning, repos),
- };
+ if (!name0->ss.in_changeset)
+ return;
+ if (!apk_dep_is_provided(dep0, &name0->ss.chosen))
+ return;
}
- apk_solution_array_resize(&ss->best_solution, n);
-}
-static int compare_solution_entry(const void *p1, const void *p2)
-{
- const struct apk_solution_entry *c1 = (const struct apk_solution_entry *) p1;
- const struct apk_solution_entry *c2 = (const struct apk_solution_entry *) p2;
-
- return strcmp(c1->pkg->name->name, c2->pkg->name->name);
+ generate_change(ss, name);
}
-static int compare_change(const void *p1, const void *p2)
+static void generate_change_dep(struct apk_solver_state *ss, struct apk_dependency *dep)
{
- const struct apk_change *c1 = (const struct apk_change *) p1;
- const struct apk_change *c2 = (const struct apk_change *) p2;
-
- if (c1->newpkg == NULL) {
- if (c2->newpkg == NULL) {
- /* both deleted - reverse topology order */
- return c2->oldpkg->topology_hard -
- c1->oldpkg->topology_hard;
- }
+ struct apk_name *name = dep->name;
- /* c1 deleted, c2 installed -> c2 first*/
- return 1;
- }
- if (c2->newpkg == NULL)
- /* c1 installed, c2 deleted -> c1 first*/
- return -1;
+ if (!apk_dep_is_provided(dep, &name->ss.chosen))
+ ss->errors++;
- return c1->newpkg->topology_hard -
- c2->newpkg->topology_hard;
+ generate_change(ss, name);
}
-static int generate_changeset(struct apk_database *db,
- struct apk_solution_array *solution,
- struct apk_changeset *changeset,
- unsigned short solver_flags)
+static void generate_changeset(struct apk_solver_state *ss, struct apk_dependency_array *world)
{
- struct apk_name *name;
- struct apk_package *pkg;
+ struct apk_changeset *changeset = ss->changeset;
struct apk_installed_package *ipkg;
- int i, num_installs = 0, num_removed = 0, ci = 0;
-
- /* calculate change set size */
- for (i = 0; i < solution->num; i++) {
- pkg = solution->item[i].pkg;
- name = pkg->name;
- name->ss.chosen = APK_PROVIDER_FROM_PACKAGE(pkg);
- name->ss.in_changeset = 1;
- if ((pkg->ipkg == NULL) ||
- solution->item[i].reinstall ||
- solution->item[i].repository_tag != pkg->ipkg->repository_tag)
- num_installs++;
- }
- list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
- name = ipkg->pkg->name;
- if ((name->ss.chosen.pkg == NULL) || !name->ss.in_changeset)
- num_removed++;
- }
- /* construct changeset */
- apk_change_array_resize(&changeset->changes, num_installs + num_removed);
- list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
- name = ipkg->pkg->name;
- if ((name->ss.chosen.pkg == NULL) || !name->ss.in_changeset) {
- changeset->changes->item[ci].oldpkg = ipkg->pkg;
- ci++;
- }
+ list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list) {
+ struct apk_name *name = ipkg->pkg->name;
+ if (name->ss.chosen.pkg == NULL && !name->ss.locked)
+ ss->num_selections++;
}
- for (i = 0; i < solution->num; i++) {
- pkg = solution->item[i].pkg;
- name = pkg->name;
-
- if ((pkg->ipkg == NULL) ||
- solution->item[i].reinstall ||
- solution->item[i].repository_tag != pkg->ipkg->repository_tag){
- changeset->changes->item[ci].oldpkg = apk_pkg_get_installed(name);
- changeset->changes->item[ci].newpkg = pkg;
- changeset->changes->item[ci].repository_tag = solution->item[i].repository_tag;
- changeset->changes->item[ci].reinstall = solution->item[i].reinstall;
- ci++;
+
+ apk_change_array_resize(&ss->changeset->changes, ss->num_selections);
+ foreach_dependency(ss, world, generate_change_dep);
+
+ /* FIXME: could order better the removals of unneeded packages */
+ list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list) {
+ struct apk_name *name = ipkg->pkg->name;
+ if (name->ss.chosen.pkg == NULL && !name->ss.in_changeset) {
+ struct apk_change *change = &changeset->changes->item[ss->num_solution_entries++];
+ *change = (struct apk_change) {
+ .old_pkg = ipkg->pkg,
+ .new_pkg = NULL,
+ };
+ changeset->num_remove++;
}
}
- /* sort changeset to topology order */
- qsort(changeset->changes->item, changeset->changes->num,
- sizeof(struct apk_change), compare_change);
+ changeset->num_total_changes = changeset->num_install + changeset->num_remove + changeset->num_adjust;
- return 0;
+#if 1
+ /* FIXME: calculate num_solution_entries correctly */
+ ASSERT(ss->num_solution_entries <= changeset->changes->num,
+ "Got %d changes, but expected %d\n",
+ ss->num_solution_entries, changeset->changes->num);
+ apk_change_array_resize(&ss->changeset->changes, ss->num_solution_entries);
+#else
+ ASSERT(ss->num_solution_entries == changeset->changes->num,
+ "Got %d changes, but expected %d\n",
+ ss->num_solution_entries, changeset->changes->num);
+#endif
}
static int free_state(apk_hash_item item, void *ctx)
{
struct apk_name *name = (struct apk_name *) item;
-
- ASSERT(name->ss.requirers == 0, "Requirers is not zero after cleanup");
memset(&name->ss, 0, sizeof(name->ss));
-
return 0;
}
static int free_package(apk_hash_item item, void *ctx)
{
struct apk_package *pkg = (struct apk_package *) item;
-
- if (pkg->state_ptr != NULL) {
- free(pkg->state_ptr);
- pkg->state_ptr = NULL;
- }
+ memset(&pkg->ss, 0, sizeof(pkg->ss));
return 0;
}
-void apk_solver_set_name_flags(struct apk_name *name,
- unsigned short solver_flags,
- unsigned short solver_flags_inheritable)
-{
- name->ss.solver_flags_local = solver_flags;
- name->ss.solver_flags_inheritable = solver_flags & solver_flags_inheritable;
-}
-
-static void apk_solver_free(struct apk_database *db)
-{
- apk_hash_foreach(&db->available.names, free_state, NULL);
- apk_hash_foreach(&db->available.packages, free_package, NULL);
-}
-
int apk_solver_solve(struct apk_database *db,
unsigned short solver_flags,
struct apk_dependency_array *world,
- struct apk_solution_array **solution,
struct apk_changeset *changeset)
{
- struct apk_solver_state *ss;
- struct apk_installed_package *ipkg;
- solver_result_t r = SOLVERR_STOP;
+ struct apk_name *name, *name0;
+ struct apk_solver_state ss_data, *ss = &ss_data;
int i;
- ss = calloc(1, sizeof(struct apk_solver_state));
+ memset(ss, 0, sizeof(*ss));
ss->db = db;
+ ss->changeset = changeset;
ss->solver_flags = solver_flags;
- ss->topology_position = -1;
- ss->best_score = SCORE_MAX;
- list_init(&ss->unsolved_list_head);
+ list_init(&ss->dirty_head);
+ list_init(&ss->unresolved_head);
+
+ foreach_dependency(ss, world, discover_names);
+
+ /* FIXME: If filename specified, force to use it */
+ dbg_printf("applying world\n");
for (i = 0; i < world->num; i++) {
struct apk_dependency *dep = &world->item[i];
- struct apk_name *name = dep->name;
-
- dbg_printf("%s: adding pinnings %d\n", name->name, dep->repository_tag);
+ name = dep->name;
name->ss.in_world_dependency = 1;
name->ss.preferred_pinning = BIT(dep->repository_tag);
-
- sort_name(ss, name);
+ apply_constraint(ss, dep);
}
- list_for_each_entry(ipkg, &db->installed.packages, installed_pkgs_list) {
- sort_name(ss, ipkg->pkg->name);
- ipkg->pkg->name->ss.originally_installed = 1;
- }
-
- ss->max_decisions ++;
- ss->decisions = calloc(1, sizeof(struct apk_decision[ss->max_decisions]));
-
- /* "Initial decision" is used as dummy for world constraints. */
- ss->decisions[0].requirers = 1;
- foreach_dependency(ss, world, apply_constraint);
+ dbg_printf("applying world [finished]\n");
do {
- /* need EXPAND if here, can return SOLUTION|PRUNED|EXPAND */
- r = expand_branch(ss);
- if (r == SOLVERR_SOLUTION) {
- if (cmpscore(&ss->score, &ss->best_score) < 0) {
- dbg_printf("updating best score "SCORE_FMT" (was: "SCORE_FMT")\n",
- SCORE_PRINTF(&ss->score),
- SCORE_PRINTF(&ss->best_score));
-
- record_solution(ss);
- ss->best_score = ss->score;
- }
-
- r = SOLVERR_PRUNED;
- }
- /* next_branch() returns PRUNED, STOP or EXPAND */
- while (r == SOLVERR_PRUNED)
- r = next_branch(ss);
- /* STOP or EXPAND */
- } while (r != SOLVERR_STOP);
-
-#ifdef DEBUG_CHECKS
- foreach_dependency(ss, world, undo_constraint);
-#endif
-
-
- if (ss->best_solution == NULL) {
- apk_error("Internal error: no solution at all found.");
- return -1;
- }
-
- /* collect packages */
- dbg_printf("finished. best score "SCORE_FMT". solution has %zu packages.\n",
- SCORE_PRINTF(&ss->best_score),
- ss->best_solution->num);
-
- if (changeset != NULL) {
- generate_changeset(db, ss->best_solution, changeset,
- ss->solver_flags);
- }
- if (solution != NULL) {
- qsort(ss->best_solution->item, ss->best_solution->num,
- sizeof(struct apk_solution_entry), compare_solution_entry);
- *solution = ss->best_solution;
- } else {
- apk_solution_array_free(&ss->best_solution);
- }
- i = ss->best_score.unsatisfied;
- apk_solver_free(db);
- free(ss->decisions);
- free(ss);
-
- return i;
-}
-
-static void print_change(struct apk_database *db,
- struct apk_change *change,
- int cur, int total)
-{
- struct apk_name *name;
- struct apk_package *oldpkg = change->oldpkg;
- struct apk_package *newpkg = change->newpkg;
- const char *msg = NULL;
- char status[32], n[512], *nameptr;
- apk_blob_t *oneversion = NULL;
- int r;
-
- snprintf(status, sizeof(status), "(%i/%i)", cur+1, total);
- status[sizeof(status) - 1] = 0;
-
- name = newpkg ? newpkg->name : oldpkg->name;
- if (change->repository_tag > 0) {
- snprintf(n, sizeof(n), "%s@" BLOB_FMT,
- name->name,
- BLOB_PRINTF(*db->repo_tags[change->repository_tag].name));
- n[sizeof(n) - 1] = 0;
- nameptr = n;
- } else {
- nameptr = name->name;
- }
-
- if (oldpkg == NULL) {
- msg = "Installing";
- oneversion = newpkg->version;
- } else if (newpkg == NULL) {
- msg = "Purging";
- oneversion = oldpkg->version;
- } else if (newpkg == oldpkg) {
- if (change->reinstall) {
- if (pkg_available(db, change->newpkg))
- msg = "Re-installing";
- else
- msg = "[APK unavailable, skipped] Re-installing";
- } else {
- msg = "Updating pinning";
+ while (!list_empty(&ss->dirty_head)) {
+ name = list_pop(&ss->dirty_head, struct apk_name, ss.dirty_list);
+ reconsider_name(ss, name);
}
- oneversion = newpkg->version;
- } else {
- r = apk_pkg_version_compare(newpkg, oldpkg);
- switch (r) {
- case APK_VERSION_LESS:
- msg = "Downgrading";
- break;
- case APK_VERSION_EQUAL:
- msg = "Replacing";
- break;
- case APK_VERSION_GREATER:
- msg = "Upgrading";
- break;
- }
- }
- if (oneversion) {
- apk_message("%s %s %s (" BLOB_FMT ")",
- status, msg, nameptr,
- BLOB_PRINTF(*oneversion));
- } else {
- apk_message("%s %s %s (" BLOB_FMT " -> " BLOB_FMT ")",
- status, msg, nameptr,
- BLOB_PRINTF(*oldpkg->version),
- BLOB_PRINTF(*newpkg->version));
- }
-}
-
-struct apk_stats {
- unsigned int bytes;
- unsigned int packages;
-};
-
-static void count_change(struct apk_change *change, struct apk_stats *stats)
-{
- if (change->newpkg != NULL) {
- stats->bytes += change->newpkg->installed_size;
- stats->packages ++;
- }
- if (change->oldpkg != NULL)
- stats->packages ++;
-}
-
-static void draw_progress(int percent)
-{
- const int bar_width = apk_get_screen_width() - 7;
- int i;
-
- fprintf(stderr, "\e7%3i%% [", percent);
- for (i = 0; i < bar_width * percent / 100; i++)
- fputc('#', stderr);
- for (; i < bar_width; i++)
- fputc(' ', stderr);
- fputc(']', stderr);
- fflush(stderr);
- fputs("\e8\e[0K", stderr);
-}
-
-struct progress {
- struct apk_stats done;
- struct apk_stats total;
- struct apk_package *pkg;
- size_t percent;
- int progress_fd;
-};
-
-static void update_progress(struct progress *prog, size_t percent)
-{
- if (prog->percent == percent)
- return;
- prog->percent = percent;
- if (apk_flags & APK_PROGRESS)
- draw_progress(percent);
- if (prog->progress_fd != 0) {
- char buf[8];
- size_t n = snprintf(buf, sizeof(buf), "%zu\n", percent);
- write(prog->progress_fd, buf, n);
- }
-}
-
-static void progress_cb(void *ctx, size_t pkg_percent)
-{
- struct progress *prog = (struct progress *) ctx;
- size_t partial = 0, percent;
-
- if (prog->pkg != NULL)
- partial = muldiv(pkg_percent, prog->pkg->installed_size, APK_PROGRESS_SCALE);
- percent = muldiv(100, prog->done.bytes + prog->done.packages + partial,
- prog->total.bytes + prog->total.packages);
- update_progress(prog, percent);
-}
-static int dump_packages(struct apk_changeset *changeset,
- int (*cmp)(struct apk_change *change),
- const char *msg)
-{
- struct apk_change *change;
- struct apk_name *name;
- struct apk_indent indent = { .indent = 2 };
- int match = 0, i;
-
- for (i = 0; i < changeset->changes->num; i++) {
- change = &changeset->changes->item[i];
- if (!cmp(change))
- continue;
- if (match == 0)
- printf("%s:\n", msg);
- if (change->newpkg != NULL)
- name = change->newpkg->name;
- else
- name = change->oldpkg->name;
-
- apk_print_indented(&indent, APK_BLOB_STR(name->name));
- match++;
- }
- if (match)
- printf("\n");
- return match;
-}
-
-static int cmp_remove(struct apk_change *change)
-{
- return change->newpkg == NULL;
-}
-
-static int cmp_new(struct apk_change *change)
-{
- return change->oldpkg == NULL;
-}
-
-static int cmp_downgrade(struct apk_change *change)
-{
- if (change->newpkg == NULL || change->oldpkg == NULL)
- return 0;
- if (apk_pkg_version_compare(change->newpkg, change->oldpkg)
- & APK_VERSION_LESS)
- return 1;
- return 0;
-}
-
-static int cmp_upgrade(struct apk_change *change)
-{
- if (change->newpkg == NULL || change->oldpkg == NULL)
- return 0;
-
- /* Count swapping package as upgrade too - this can happen if
- * same package version is used after it was rebuilt against
- * newer libraries. Basically, different (and probably newer)
- * package, but equal version number. */
- if ((apk_pkg_version_compare(change->newpkg, change->oldpkg) &
- (APK_VERSION_GREATER | APK_VERSION_EQUAL)) &&
- (change->newpkg != change->oldpkg))
- return 1;
-
- return 0;
-}
-
-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;
-
- return pkg1->topology_hard - pkg2->topology_hard;
-}
-
-static void run_triggers(struct apk_database *db)
-{
- struct apk_package_array *pkgs;
- int i;
-
- pkgs = apk_db_get_pending_triggers(db);
- if (pkgs == NULL || pkgs->num == 0)
- return;
-
- qsort(pkgs->item, pkgs->num, sizeof(struct apk_package *),
- compare_package_topology);
-
- for (i = 0; i < pkgs->num; i++) {
- struct apk_package *pkg = pkgs->item[i];
- struct apk_installed_package *ipkg = pkg->ipkg;
-
- *apk_string_array_add(&ipkg->pending_triggers) = NULL;
- apk_ipkg_run_script(ipkg, db, APK_SCRIPT_TRIGGER,
- ipkg->pending_triggers->item);
- apk_string_array_free(&ipkg->pending_triggers);
- }
- apk_package_array_free(&pkgs);
-}
-
-int apk_solver_commit_changeset(struct apk_database *db,
- struct apk_changeset *changeset,
- struct apk_dependency_array *world)
-{
- struct progress prog;
- struct apk_change *change;
- int i, r = 0, size_diff = 0, size_unit;
-
- if (apk_db_check_world(db, world) != 0) {
- apk_error("Not committing changes due to missing repository tags. Use --force to override.");
- return -1;
- }
-
- if (changeset->changes == NULL)
- goto all_done;
-
- /* Count what needs to be done */
- memset(&prog, 0, sizeof(prog));
- prog.progress_fd = db->progress_fd;
- for (i = 0; i < changeset->changes->num; i++) {
- change = &changeset->changes->item[i];
- count_change(change, &prog.total);
- if (change->newpkg)
- size_diff += change->newpkg->installed_size;
- if (change->oldpkg)
- size_diff -= change->oldpkg->installed_size;
- }
- size_diff /= 1024;
- size_unit = 'K';
- if (abs(size_diff) > 10000) {
- size_diff /= 1024;
- size_unit = 'M';
- }
-
- if (apk_verbosity > 1 || (apk_flags & APK_INTERACTIVE)) {
- r = dump_packages(changeset, cmp_remove,
- "The following packages will be REMOVED");
- r += dump_packages(changeset, cmp_downgrade,
- "The following packages will be DOWNGRADED");
- if (r || (apk_flags & APK_INTERACTIVE) || apk_verbosity > 2) {
- dump_packages(changeset, cmp_new,
- "The following NEW packages will be installed");
- dump_packages(changeset, cmp_upgrade,
- "The following packages will be upgraded");
- printf("After this operation, %d %ciB of %s\n",
- abs(size_diff), size_unit,
- (size_diff < 0) ?
- "disk space will be freed." :
- "additional disk space will be used.");
- }
- if (changeset->changes->num > 0 &&
- (apk_flags & APK_INTERACTIVE)) {
- printf("Do you want to continue [Y/n]? ");
- fflush(stdout);
- r = fgetc(stdin);
- if (r != 'y' && r != 'Y' && r != '\n')
- return -1;
- }
- }
-
- /* Go through changes */
- r = 0;
- for (i = 0; i < changeset->changes->num; i++) {
- change = &changeset->changes->item[i];
-
- print_change(db, change, i, changeset->changes->num);
- prog.pkg = change->newpkg;
- progress_cb(&prog, 0);
-
- if (!(apk_flags & APK_SIMULATE)) {
- if (change->oldpkg != change->newpkg ||
- (change->reinstall && pkg_available(db, change->newpkg)))
- r = apk_db_install_pkg(db,
- change->oldpkg, change->newpkg,
- progress_cb, &prog);
- if (r != 0)
+ name = NULL;
+ list_for_each_entry(name0, &ss->unresolved_head, ss.unresolved_list) {
+ if (!name0->ss.has_options && name0->ss.requirers > 0) {
+ name = name0;
break;
- if (change->newpkg)
- change->newpkg->ipkg->repository_tag = change->repository_tag;
- }
-
- count_change(change, &prog.done);
- }
- update_progress(&prog, 100);
-
- run_triggers(db);
-
-all_done:
- apk_dependency_array_copy(&db->world, world);
- apk_db_write_config(db);
-
- if (r == 0 && !db->performing_self_update) {
- if (apk_verbosity > 1) {
- apk_message("OK: %d packages, %d dirs, %d files, %zu MiB",
- db->installed.stats.packages,
- db->installed.stats.dirs,
- db->installed.stats.files,
- db->installed.stats.bytes / (1024 * 1024));
- } else {
- apk_message("OK: %zu MiB in %d packages",
- db->installed.stats.bytes / (1024 * 1024),
- db->installed.stats.packages);
- }
- }
-
- return r;
-}
-
-static void add_name_if_virtual(struct apk_name_array **names, struct apk_name *name)
-{
- int i;
-
- if (name->state_int == 1)
- return;
- name->state_int = 1;
-
- if (name->providers->num == 0)
- return;
-
- for (i = 0; i < name->providers->num; i++)
- if (name->providers->item[i].pkg->name == name)
- return;
-
- *apk_name_array_add(names) = name;
-}
-
-static void print_dep_errors(struct apk_database *db, char *label,
- struct apk_dependency_array *deps,
- struct apk_name_array **names)
-{
- int i, print_label = 1;
- char buf[256];
- apk_blob_t p;
- struct apk_indent indent;
-
- for (i = 0; i < deps->num; i++) {
- struct apk_dependency *dep = &deps->item[i];
- struct apk_package *pkg = NULL;
-
- if (dep->name->state_int != 1)
- pkg = (struct apk_package*) dep->name->state_ptr;
-
- if (apk_dep_is_materialized_or_provided(dep, pkg))
- continue;
-
- if (pkg == NULL)
- add_name_if_virtual(names, dep->name);
-
- if (print_label) {
- print_label = 0;
- indent.x = printf(" %s:", label);
- indent.indent = indent.x + 1;
- }
- p = APK_BLOB_BUF(buf);
- apk_blob_push_dep(&p, db, dep);
- p = apk_blob_pushed(APK_BLOB_BUF(buf), p);
- apk_print_indented(&indent, p);
- }
- if (!print_label)
- printf("\n");
-}
-
-void apk_solver_print_errors(struct apk_database *db,
- struct apk_solution_array *solution,
- struct apk_dependency_array *world,
- int unsatisfiable)
-{
- struct apk_name_array *names;
- char pkgtext[256];
- int i, j;
-
- /* negative for hard failure without partial solution */
- if (unsatisfiable <= 0)
- return;
-
- apk_name_array_init(&names);
- apk_error("%d unsatisfiable dependencies:", unsatisfiable);
-
- for (i = 0; i < solution->num; i++) {
- struct apk_package *pkg = solution->item[i].pkg;
- pkg->name->state_ptr = pkg;
- for (j = 0; j < pkg->provides->num; j++) {
- if (pkg->provides->item[j].version == &apk_null_blob)
+ }
+ if (name == NULL)
+ goto prefer;
+ if (name->ss.requirers > 0 && name0->ss.requirers == 0)
continue;
- pkg->provides->item[j].name->state_ptr = pkg;
- }
- }
-
- print_dep_errors(db, "world", world, &names);
- for (i = 0; i < solution->num; i++) {
- struct apk_package *pkg = solution->item[i].pkg;
- snprintf(pkgtext, sizeof(pkgtext), PKG_VER_FMT, PKG_VER_PRINTF(pkg));
- print_dep_errors(db, pkgtext, pkg->depends, &names);
- }
-
- for (i = 0; i < names->num; i++) {
- struct apk_indent indent;
- struct apk_name *name = names->item[i];
-
- printf("\n %s is a virtual package provided by:\n ", name->name);
- indent.x = 4;
- indent.indent = 4;
-
- for (j = 0; j < name->providers->num; j++) {
- struct apk_package *pkg = name->providers->item[j].pkg;
- snprintf(pkgtext, sizeof(pkgtext), PKG_VER_FMT, PKG_VER_PRINTF(pkg));
- apk_print_indented(&indent, APK_BLOB_STR(pkgtext));
+ if (name->ss.requirers == 0 && name0->ss.requirers > 0)
+ goto prefer;
+ if (name0->ss.max_dep_chain > name->ss.max_dep_chain)
+ goto prefer;
+ continue;
+ prefer:
+ name = name0;
}
- printf("\n");
- }
- apk_name_array_free(&names);
-}
+ if (name == NULL)
+ break;
-int apk_solver_commit(struct apk_database *db,
- unsigned short solver_flags,
- struct apk_dependency_array *world)
-{
- struct apk_changeset changeset = {};
- struct apk_solution_array *solution = NULL;
- int r;
+ select_package(ss, name);
+ } while (1);
- if (apk_db_check_world(db, world) != 0) {
- apk_error("Not committing changes due to missing repository tags. Use --force to override.");
- return -1;
- }
+ generate_changeset(ss, world);
- r = apk_solver_solve(db, solver_flags,
- world, &solution, &changeset);
- if (r < 0)
- return r;
+ apk_hash_foreach(&db->available.names, free_state, NULL);
+ apk_hash_foreach(&db->available.packages, free_package, NULL);
- if (r == 0 || (apk_flags & APK_FORCE)) {
- /* Success -- or forced installation of bad graph */
- r = apk_solver_commit_changeset(db, &changeset, world);
- } else {
- /* Failure -- print errors */
- apk_solver_print_errors(db, solution, world, r);
- }
- apk_solution_array_free(&solution);
- apk_change_array_free(&changeset.changes);
+ dbg_printf("solver done, errors=%d\n", ss->errors);
- return r;
+ return ss->errors;
}