summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTimo Teräs <timo.teras@iki.fi>2013-06-19 20:46:53 +0300
committerTimo Teräs <timo.teras@iki.fi>2013-06-19 20:46:53 +0300
commite4c65886dd1758657ccf58e14523c2da57f2c98a (patch)
tree6842207633bf2edebd1b3c935c5750ad0a8f6996
parent81152df214dab4866f2076ef2eba04e78dbec1ab (diff)
solver: properly order deletion of unneeded packages
-rw-r--r--src/apk_solver_data.h3
-rw-r--r--src/solver.c200
-rw-r--r--test/basic14.test9
-rw-r--r--test/installif1.installed27
-rw-r--r--test/installif4.test11
-rw-r--r--test/pinning10.test4
6 files changed, 179 insertions, 75 deletions
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);
diff --git a/test/basic14.test b/test/basic14.test
new file mode 100644
index 0000000..bce402c
--- /dev/null
+++ b/test/basic14.test
@@ -0,0 +1,9 @@
+@ARGS
+--test-repo basic.repo
+--test-instdb basic.installed2
+--test-world a
+del a
+@EXPECT
+(1/2) Purging a (2)
+(2/2) Purging b (2)
+OK: 0 MiB in 2 packages
diff --git a/test/installif1.installed b/test/installif1.installed
new file mode 100644
index 0000000..551e65a
--- /dev/null
+++ b/test/installif1.installed
@@ -0,0 +1,27 @@
+C:Q1EyN5AdpAOBJWKMR89pp/C66o+OE=
+P:app
+V:1
+S:1
+I:1
+D:lib
+
+C:Q1eVpkasfqZAukAXFYbgwt4xAMZWU=
+P:lib
+V:1
+S:1
+I:1
+
+C:Q1C4uoV7SdMdDhYg4OCVmI71D8HIA=
+P:foo
+V:1
+S:1
+I:1
+
+C:Q16m4HrGizBiH4lG6Mxd5EL239L2U=
+P:appiif1
+V:1
+S:1
+I:1
+D:app
+i:app foo
+
diff --git a/test/installif4.test b/test/installif4.test
new file mode 100644
index 0000000..d3f54ee
--- /dev/null
+++ b/test/installif4.test
@@ -0,0 +1,11 @@
+@ARGS
+--test-repo installif1.repo
+--test-instdb installif1.installed
+--test-world app
+del app
+@EXPECT
+(1/4) Purging appiif1 (1)
+(2/4) Purging app (1)
+(3/4) Purging lib (1)
+(4/4) Purging foo (1)
+OK: 0 MiB in 4 packages
diff --git a/test/pinning10.test b/test/pinning10.test
index f8f6763..6097f99 100644
--- a/test/pinning10.test
+++ b/test/pinning10.test
@@ -5,6 +5,6 @@
--test-world "a@testing"
add a
@EXPECT
-(1/2) Downgrading a (3 -> 2)
-(2/2) Purging c (3)
+(1/2) Purging c (3)
+(2/2) Downgrading a (3 -> 2)
OK: 0 MiB in 3 packages