diff options
Diffstat (limited to 'src/solver.c')
| -rw-r--r-- | src/solver.c | 2248 |
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; } |