From e4c65886dd1758657ccf58e14523c2da57f2c98a Mon Sep 17 00:00:00 2001 From: Timo Teräs Date: Wed, 19 Jun 2013 20:46:53 +0300 Subject: solver: properly order deletion of unneeded packages --- src/apk_solver_data.h | 3 +- src/solver.c | 200 ++++++++++++++++++++++++++++++++------------------ 2 files changed, 130 insertions(+), 73 deletions(-) (limited to 'src') diff --git a/src/apk_solver_data.h b/src/apk_solver_data.h index e259dbf..cf7a3bd 100644 --- a/src/apk_solver_data.h +++ b/src/apk_solver_data.h @@ -26,11 +26,10 @@ struct apk_solver_name_state { unsigned short merge_provides; unsigned short max_dep_chain; unsigned seen : 1; - unsigned in_world_dependency : 1; + unsigned locked : 1; unsigned in_changeset : 1; unsigned reevaluate_deps : 1; unsigned reevaluate_iif : 1; - unsigned locked : 1; unsigned has_iif : 1; unsigned has_options : 1; unsigned reverse_deps_done : 1; diff --git a/src/solver.c b/src/solver.c index 1df029b..d6ebc0e 100644 --- a/src/solver.c +++ b/src/solver.c @@ -35,7 +35,6 @@ struct apk_solver_state { struct list_head dirty_head; struct list_head unresolved_head; unsigned int errors; - unsigned int num_selections, num_solution_entries; unsigned int solver_flags_inherit; unsigned int pinning_inherit; unsigned int default_repos; @@ -634,8 +633,6 @@ static void select_package(struct apk_solver_state *ss, struct apk_name *name) apply_constraint(ss, pkg, d); ss->solver_flags_inherit = 0; ss->pinning_inherit = 0; - - ss->num_selections++; } else { dbg_printf("selecting: %s [unassigned]\n", name->name); assign_name(ss, name, provider_none); @@ -643,56 +640,69 @@ static void select_package(struct apk_solver_state *ss, struct apk_name *name) } } -static void generate_change_dep(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep); -static void generate_change_iif(struct apk_solver_state *ss, struct apk_name *name); - -static void generate_change(struct apk_solver_state *ss, struct apk_name *name) +static void record_change(struct apk_solver_state *ss, struct apk_package *opkg, struct apk_package *npkg) { - struct apk_name **pname; - struct apk_package *pkg = name->ss.chosen.pkg, *opkg; struct apk_changeset *changeset = ss->changeset; struct apk_change *change; - struct apk_dependency *d; - if (pkg == NULL) - return; - - if (pkg->ss.in_changeset) - return; - pkg->ss.in_changeset = 1; - pkg->name->ss.in_changeset = 1; - - foreach_array_item(d, pkg->depends) - generate_change_dep(ss, pkg, d); - - 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 = apk_change_array_add(&changeset->changes); *change = (struct apk_change) { .old_pkg = opkg, .old_repository_tag = opkg ? opkg->ipkg->repository_tag : 0, - .new_pkg = pkg, - .new_repository_tag = get_tag(ss->db, pkg->ss.pinning_allowed, get_pkg_repos(ss->db, pkg)), - .reinstall = !!(pkg->ss.solver_flags & APK_SOLVERF_REINSTALL), + .new_pkg = npkg, + .new_repository_tag = npkg ? get_tag(ss->db, npkg->ss.pinning_allowed, get_pkg_repos(ss->db, npkg)) : 0, + .reinstall = npkg ? !!(npkg->ss.solver_flags & APK_SOLVERF_REINSTALL) : 0, }; - if (change->new_pkg == NULL) + if (npkg == NULL) changeset->num_remove++; - else if (change->old_pkg == NULL) + else if (opkg == NULL) changeset->num_install++; - else if (change->new_pkg != change->old_pkg || change->reinstall || - change->new_repository_tag != change->old_repository_tag) + else if (npkg != opkg || change->reinstall || change->new_repository_tag != change->old_repository_tag) changeset->num_adjust++; +} - foreach_array_item(pname, pkg->name->rinstall_if) - generate_change_iif(ss, *pname); +static void cset_gen_name_change(struct apk_solver_state *ss, struct apk_name *name); +static void cset_gen_name_remove(struct apk_solver_state *ss, struct apk_package *pkg); +static void cset_gen_dep(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep); + +static void cset_track_deps_added(struct apk_dependency_array *deps) +{ + struct apk_dependency *d; + + foreach_array_item(d, deps) + if (!d->conflict) + d->name->ss.requirers++; +} + +static void cset_track_deps_removed(struct apk_solver_state *ss, struct apk_package *pkg) +{ + struct apk_dependency *d; + struct apk_package *pkg0; + + foreach_array_item(d, pkg->depends) { + if (d->conflict) + continue; + d->name->ss.requirers--; + if (d->name->ss.requirers > 0) + continue; + pkg0 = apk_pkg_get_installed(d->name); + if (pkg0 != NULL) + cset_gen_name_remove(ss, pkg0); + } +} + +static void cset_check_removal_by_deps(struct apk_solver_state *ss, struct apk_package *pkg) +{ + if (pkg->name->ss.requirers == 0) + cset_gen_name_remove(ss, pkg); } -static void generate_change_iif(struct apk_solver_state *ss, struct apk_name *name) +static void cset_check_install_by_iif(struct apk_solver_state *ss, struct apk_name *name) { struct apk_package *pkg = name->ss.chosen.pkg; struct apk_dependency *dep0; - if (pkg == NULL || !name->ss.seen) + if (pkg == NULL || !name->ss.seen || name->ss.in_changeset) return; foreach_array_item(dep0, pkg->install_if) { @@ -702,11 +712,77 @@ static void generate_change_iif(struct apk_solver_state *ss, struct apk_name *na if (!apk_dep_is_provided(dep0, &name0->ss.chosen)) return; } + cset_gen_name_change(ss, name); +} + +static void cset_check_removal_by_iif(struct apk_solver_state *ss, struct apk_name *name) +{ + struct apk_package *pkg; + struct apk_dependency *dep0; - generate_change(ss, name); + if (name->ss.in_changeset || name->ss.chosen.pkg != NULL) + return; + + pkg = apk_pkg_get_installed(name); + if (pkg == NULL) + return; + + foreach_array_item(dep0, pkg->install_if) { + if (dep0->name->ss.in_changeset && + dep0->name->ss.chosen.pkg == NULL) { + cset_check_removal_by_deps(ss, pkg); + return; + } + } +} + +static void cset_gen_name_change(struct apk_solver_state *ss, struct apk_name *name) +{ + struct apk_name **pname; + struct apk_package *pkg = name->ss.chosen.pkg, *opkg; + struct apk_dependency *d; + + if (pkg == NULL || pkg->ss.in_changeset) + return; + + pkg->ss.in_changeset = 1; + pkg->name->ss.in_changeset = 1; + + opkg = apk_pkg_get_installed(pkg->name); + if (opkg) { + foreach_array_item(pname, opkg->name->rinstall_if) + cset_check_removal_by_iif(ss, *pname); + } + + foreach_array_item(d, pkg->depends) + cset_gen_dep(ss, pkg, d); + + dbg_printf("Selecting: "PKG_VER_FMT"%s\n", PKG_VER_PRINTF(pkg), pkg->ss.available ? "" : " [NOT AVAILABLE]"); + record_change(ss, opkg, pkg); + + foreach_array_item(pname, pkg->name->rinstall_if) + cset_check_install_by_iif(ss, *pname); + + cset_track_deps_added(pkg->depends); + if (opkg) + cset_track_deps_removed(ss, opkg); +} + +static void cset_gen_name_remove(struct apk_solver_state *ss, struct apk_package *pkg) +{ + struct apk_name *name = pkg->name, **pname; + + if (name->ss.chosen.pkg != NULL || name->ss.in_changeset) + return; + + name->ss.in_changeset = 1; + foreach_array_item(pname, pkg->name->rinstall_if) + cset_check_removal_by_iif(ss, *pname); + record_change(ss, pkg, NULL); + cset_track_deps_removed(ss, pkg); } -static void generate_change_dep(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep) +static void cset_gen_dep(struct apk_solver_state *ss, struct apk_package *ppkg, struct apk_dependency *dep) { struct apk_name *name = dep->name; struct apk_package *pkg = name->ss.chosen.pkg; @@ -714,7 +790,7 @@ static void generate_change_dep(struct apk_solver_state *ss, struct apk_package if (!apk_dep_is_provided(dep, &name->ss.chosen)) mark_error(ss, ppkg); - generate_change(ss, name); + cset_gen_name_change(ss, name); if (pkg && pkg->ss.error) mark_error(ss, ppkg); @@ -726,42 +802,25 @@ static void generate_changeset(struct apk_solver_state *ss, struct apk_dependenc struct apk_installed_package *ipkg; struct apk_dependency *d; - 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++; - } + apk_change_array_init(&changeset->changes); + + list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list) + ipkg->pkg->name->ss.requirers = 0; + list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list) + cset_track_deps_added(ipkg->pkg->depends); + list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list) + cset_check_removal_by_deps(ss, ipkg->pkg); - apk_change_array_resize(&ss->changeset->changes, ss->num_selections); foreach_array_item(d, world) - generate_change_dep(ss, NULL, d); - - /* 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++; - } - } + cset_gen_dep(ss, NULL, d); - changeset->num_total_changes = changeset->num_install + changeset->num_remove + changeset->num_adjust; + list_for_each_entry(ipkg, &ss->db->installed.packages, installed_pkgs_list) + cset_gen_name_remove(ss, ipkg->pkg); -#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 + changeset->num_total_changes = + changeset->num_install + + changeset->num_remove + + changeset->num_adjust; } static int free_state(apk_hash_item item, void *ctx) @@ -803,7 +862,6 @@ restart: if (d->broken) continue; name = d->name; - name->ss.in_world_dependency = 1; discover_name(ss, d->name); ss->pinning_inherit = BIT(d->repository_tag); apply_constraint(ss, NULL, d); -- cgit v1.2.3-70-g09d2