From 012bcbe41c045a00e112608fe9dac4097d90dc1e Mon Sep 17 00:00:00 2001 From: Timo Teräs Date: Thu, 22 Sep 2011 13:09:23 +0300 Subject: solver: fix backtracking We need to refresh all name states after backtracking as options that were excluding due to topology ordering might have become available. --- src/solver.c | 65 ++++++++++++++++++++++++++++++------------------------------ 1 file changed, 33 insertions(+), 32 deletions(-) diff --git a/src/solver.c b/src/solver.c index e6f0cc52ee9..1f38136574c 100644 --- a/src/solver.c +++ b/src/solver.c @@ -41,6 +41,7 @@ struct apk_package_state { struct apk_name_state { struct list_head unsolved_list; + struct apk_name *name; struct apk_package *chosen; unsigned short requirers; unsigned short install_ifs; @@ -51,7 +52,6 @@ struct apk_name_state { unsigned int availability_checked : 1; unsigned int locked : 1; - unsigned int no_options : 1; }; struct apk_solver_state { @@ -64,7 +64,8 @@ struct apk_solver_state { unsigned int assigned_names; unsigned short cur_unsatisfiable; - unsigned short solver_flags; + unsigned int solver_flags : 4; + unsigned int refresh_name_states : 1; struct apk_package_array *best_solution; unsigned short best_unsatisfiable; @@ -82,9 +83,16 @@ static struct apk_package_state *pkg_to_ps(struct apk_package *pkg) static struct apk_name_state *name_to_ns(struct apk_name *name) { - if (name->state_ptr == NULL) - name->state_ptr = calloc(1, sizeof(struct apk_name_state)); - return (struct apk_name_state*) name->state_ptr; + struct apk_name_state *ns; + + if (name->state_ptr == NULL) { + ns = calloc(1, sizeof(struct apk_name_state)); + ns->name = name; + name->state_ptr = ns; + } else { + ns = (struct apk_name_state*) name->state_ptr; + } + return ns; } static inline int pkg_available(struct apk_database *db, struct apk_package *pkg) @@ -339,16 +347,13 @@ static int install_if_missing(struct apk_solver_state *ss, struct apk_package *p return missing; } -static int update_name_state(struct apk_solver_state *ss, - struct apk_name *name, struct apk_name_state *ns, - int requirers_adjustment) +static int update_name_state(struct apk_solver_state *ss, struct apk_name *name) { + struct apk_name_state *ns = name_to_ns(name); struct apk_package *best_pkg = NULL; unsigned int best_topology = 0; int i, options = 0, skipped_options = 0; - ns->requirers += requirers_adjustment; - for (i = 0; i < name->pkgs->num; i++) { struct apk_package *pkg0 = name->pkgs->item[i]; struct apk_package_state *ps0 = pkg_to_ps(pkg0); @@ -372,20 +377,7 @@ static int update_name_state(struct apk_solver_state *ss, best_pkg = pkg0, best_topology = pkg0->topology_hard; } - if (options == 0 && skipped_options == 0) { - if (!ns->no_options) { - ss->cur_unsatisfiable += ns->requirers; - if (ns->install_ifs) - ss->cur_unsatisfiable++; - ns->no_options = 1; - } else if (requirers_adjustment > 0) { - ss->cur_unsatisfiable += requirers_adjustment; - } - } else - ns->no_options = 0; - - if ((options == 0 && skipped_options == 0) || - (ns->requirers == 0 && ns->install_ifs == 0)) { + if (ns->requirers == 0 && ns->install_ifs == 0) { if (list_hashed(&ns->unsolved_list)) { list_del(&ns->unsolved_list); list_init(&ns->unsolved_list); @@ -414,7 +406,7 @@ static void trigger_install_if(struct apk_solver_state *ss, dbg_printf("trigger_install_if: " PKG_VER_FMT " triggered\n", PKG_VER_PRINTF(pkg)); ns->install_ifs++; - update_name_state(ss, pkg->name, ns, 0); + update_name_state(ss, pkg->name); } } @@ -427,7 +419,7 @@ static void untrigger_install_if(struct apk_solver_state *ss, dbg_printf("untrigger_install_if: " PKG_VER_FMT " no longer triggered\n", PKG_VER_PRINTF(pkg)); ns->install_ifs--; - update_name_state(ss, pkg->name, ns, 0); + update_name_state(ss, pkg->name); } } @@ -454,7 +446,7 @@ static void apply_decision(struct apk_solver_state *ss, foreach_dependency(ss, pkg->depends, apply_constraint); foreach_rinstall_if_pkg(ss, pkg, trigger_install_if); } else { - update_name_state(ss, pkg->name, ns, 0); + update_name_state(ss, pkg->name); } } @@ -483,7 +475,7 @@ static void undo_decision(struct apk_solver_state *ss, } ss->cur_unsatisfiable = ps->cur_unsatisfiable; - update_name_state(ss, pkg->name, ns, 0); + update_name_state(ss, pkg->name); } static void push_decision(struct apk_solver_state *ss, struct apk_package *pkg, @@ -533,6 +525,7 @@ static int next_branch(struct apk_solver_state *ss) ss->topology_position); ps->flags &= ~(APK_PKGSTF_ALT_BRANCH | APK_PKGSTF_DECIDED); ss->latest_decision = ps->backtrack; + ss->refresh_name_states = 1; } else { dbg_printf("next_branch: swapping BRANCH at topology_position %d\n", ss->topology_position); @@ -619,8 +612,9 @@ static void apply_constraint(struct apk_solver_state *ss, struct apk_dependency if (ss->latest_decision != NULL) inherit_name_state(name, ss->latest_decision->name); - update_name_state(ss, name, ns, - (dep->result_mask != APK_DEPMASK_CONFLICT) ? 1 : 0); + if (dep->result_mask != APK_DEPMASK_CONFLICT) + ns->requirers++; + update_name_state(ss, name); } static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency *dep) @@ -653,8 +647,9 @@ static void undo_constraint(struct apk_solver_state *ss, struct apk_dependency * if (ss->latest_decision && has_inherited_state(ss->latest_decision->name)) recalculate_inherted_name_state(name); - update_name_state(ss, name, ns, - (dep->result_mask != APK_DEPMASK_CONFLICT) ? -1 : 0); + if (dep->result_mask != APK_DEPMASK_CONFLICT) + ns->requirers--; + update_name_state(ss, name); } static int expand_branch(struct apk_solver_state *ss) @@ -665,6 +660,9 @@ static int expand_branch(struct apk_solver_state *ss) /* FIXME: change unsolved_list to a priority queue */ list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) { + if (ss->refresh_name_states) + update_name_state(ss, ns->name); + /* ns->chosen can be NULL if the name has only install_if * requirers that got later conflicted, but it still has * other options that can get activated later due to more @@ -677,7 +675,10 @@ static int expand_branch(struct apk_solver_state *ss) else if (ns->chosen->topology_hard > topology0) pkg0 = ns->chosen, topology0 = pkg0->topology_hard; } + ss->refresh_name_states = 0; if (pkg0 == NULL) { + list_for_each_entry(ns, &ss->unsolved_list_head, unsolved_list) + ss->cur_unsatisfiable += ns->requirers; dbg_printf("expand_branch: list is empty (%d unsatisfied)\n", ss->cur_unsatisfiable); return 1; -- cgit v1.2.3