Send patches - preferably formatted by git format-patch - to patches at archlinux32 dot org.
summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAndrew Gregory <andrew.gregory.8@gmail.com>2016-05-23 08:27:29 -0400
committerAndrew Gregory <andrew.gregory.8@gmail.com>2017-05-08 23:27:40 -0400
commitf31792adb5fc9ba9a4c6f14a6520282702f17b71 (patch)
treeb0dc04d61414606dc31a16bb006f4be81e65a28a
parentf84d0a8282543d2fd6fe0e8c3986ec17292bdf2a (diff)
recursedeps: include cyclic dependencies
Cyclic dependencies (A depends on B, B depends on A) were not selected because neither package could be removed individually, so can_remove_package would always return false for both. By preselecting all dependencies then filtering back out any dependencies still required by any packages that will not be uninstalled, groups of unneeded cyclic dependencies can be found. Fixes FS#41031 Signed-off-by: Andrew Gregory <andrew.gregory.8@gmail.com> Signed-off-by: Allan McRae <allan@archlinux.org> (cherry picked from commit 6ac2ee21b30f3c5f331d19349f96bb8e5b020b47)
-rw-r--r--lib/libalpm/deps.c104
-rw-r--r--test/pacman/tests/TESTS1
-rw-r--r--test/pacman/tests/remove-recursive-cycle.py41
3 files changed, 94 insertions, 52 deletions
diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c
index c35a2752..ae5d60bc 100644
--- a/lib/libalpm/deps.c
+++ b/lib/libalpm/deps.c
@@ -551,44 +551,29 @@ error:
return NULL;
}
-/* These parameters are messy. We check if this package, given a list of
- * targets and a db is safe to remove. We do NOT remove it if it is in the
- * target list, or if the package was explicitly installed and
- * include_explicit == 0 */
-static int can_remove_package(alpm_db_t *db, alpm_pkg_t *pkg,
- alpm_list_t *targets, int include_explicit)
+/** Move package dependencies from one list to another
+ * @param from list to scan for dependencies
+ * @param to list to add dependencies to
+ * @param pkg package whose dependencies are moved
+ * @param explicit if 0, explicitly installed packages are not moved
+ */
+static void _alpm_select_depends(alpm_list_t **from, alpm_list_t **to,
+ alpm_pkg_t *pkg, int explicit)
{
- alpm_list_t *i;
-
- if(alpm_pkg_find(targets, pkg->name)) {
- return 0;
- }
-
- if(!include_explicit) {
- /* see if it was explicitly installed */
- if(alpm_pkg_get_reason(pkg) == ALPM_PKG_REASON_EXPLICIT) {
- _alpm_log(db->handle, ALPM_LOG_DEBUG,
- "excluding %s -- explicitly installed\n", pkg->name);
- return 0;
+ alpm_list_t *i, *next;
+ if(!alpm_pkg_get_depends(pkg)) {
+ return;
+ }
+ for(i = *from; i; i = next) {
+ alpm_pkg_t *deppkg = i->data;
+ next = i->next;
+ if((explicit || alpm_pkg_get_reason(deppkg) != ALPM_PKG_REASON_EXPLICIT)
+ && _alpm_pkg_depends_on(pkg, deppkg)) {
+ *to = alpm_list_add(*to, deppkg);
+ *from = alpm_list_remove_item(*from, i);
+ free(i);
}
}
-
- /* TODO: checkdeps could be used here, it handles multiple providers
- * better, but that also makes it slower.
- * Also this would require to first add the package to the targets list,
- * then call checkdeps with it, then remove the package from the targets list
- * if checkdeps detected it would break something */
-
- /* see if other packages need it */
- for(i = _alpm_db_get_pkgcache(db); i; i = i->next) {
- alpm_pkg_t *lpkg = i->data;
- if(_alpm_pkg_depends_on(lpkg, pkg) && !alpm_pkg_find(targets, lpkg->name)) {
- return 0;
- }
- }
-
- /* it's ok to remove */
- return 1;
}
/**
@@ -604,31 +589,46 @@ static int can_remove_package(alpm_db_t *db, alpm_pkg_t *pkg,
*/
int _alpm_recursedeps(alpm_db_t *db, alpm_list_t **targs, int include_explicit)
{
- alpm_list_t *i, *j;
+ alpm_list_t *i, *keep, *rem = NULL;
if(db == NULL || targs == NULL) {
return -1;
}
+ keep = alpm_list_copy(_alpm_db_get_pkgcache(db));
for(i = *targs; i; i = i->next) {
- alpm_pkg_t *pkg = i->data;
- for(j = _alpm_db_get_pkgcache(db); j; j = j->next) {
- alpm_pkg_t *deppkg = j->data;
- if(_alpm_pkg_depends_on(pkg, deppkg)
- && can_remove_package(db, deppkg, *targs, include_explicit)) {
- alpm_pkg_t *copy = NULL;
- _alpm_log(db->handle, ALPM_LOG_DEBUG, "adding '%s' to the targets\n",
- deppkg->name);
- /* add it to the target list */
- if(_alpm_pkg_dup(deppkg, &copy)) {
- /* we return memory on "non-fatal" error in _alpm_pkg_dup */
- _alpm_pkg_free(copy);
- return -1;
- }
- *targs = alpm_list_add(*targs, copy);
- }
+ keep = alpm_list_remove(keep, i->data, _alpm_pkg_cmp, NULL);
+ }
+
+ /* recursively select all dependencies for removal */
+ for(i = *targs; i; i = i->next) {
+ _alpm_select_depends(&keep, &rem, i->data, include_explicit);
+ }
+ for(i = rem; i; i = i->next) {
+ _alpm_select_depends(&keep, &rem, i->data, include_explicit);
+ }
+
+ /* recursively select any still needed packages to keep */
+ for(i = keep; i && rem; i = i->next) {
+ _alpm_select_depends(&rem, &keep, i->data, 1);
+ }
+ alpm_list_free(keep);
+
+ /* copy selected packages into the target list */
+ for(i = rem; i; i = i->next) {
+ alpm_pkg_t *pkg = i->data, *copy = NULL;
+ _alpm_log(db->handle, ALPM_LOG_DEBUG,
+ "adding '%s' to the targets\n", pkg->name);
+ if(_alpm_pkg_dup(pkg, &copy)) {
+ /* we return memory on "non-fatal" error in _alpm_pkg_dup */
+ _alpm_pkg_free(copy);
+ alpm_list_free(rem);
+ return -1;
}
+ *targs = alpm_list_add(*targs, copy);
}
+ alpm_list_free(rem);
+
return 0;
}
diff --git a/test/pacman/tests/TESTS b/test/pacman/tests/TESTS
index 9c330203..45ebabb2 100644
--- a/test/pacman/tests/TESTS
+++ b/test/pacman/tests/TESTS
@@ -109,6 +109,7 @@ TESTS += test/pacman/tests/querycheck002.py
TESTS += test/pacman/tests/querycheck_fast_file_type.py
TESTS += test/pacman/tests/reason001.py
TESTS += test/pacman/tests/remove-assumeinstalled.py
+TESTS += test/pacman/tests/remove-recursive-cycle.py
TESTS += test/pacman/tests/remove001.py
TESTS += test/pacman/tests/remove002.py
TESTS += test/pacman/tests/remove010.py
diff --git a/test/pacman/tests/remove-recursive-cycle.py b/test/pacman/tests/remove-recursive-cycle.py
new file mode 100644
index 00000000..b9864c87
--- /dev/null
+++ b/test/pacman/tests/remove-recursive-cycle.py
@@ -0,0 +1,41 @@
+self.description = "Recursively remove a package with cyclical dependencies"
+
+lpkg1 = pmpkg('pkg1')
+self.addpkg2db('local', lpkg1)
+lpkg1.depends = [ 'dep1' ]
+
+lpkg2 = pmpkg('pkg2')
+self.addpkg2db('local', lpkg2)
+lpkg2.depends = [ 'dep3' ]
+
+# cyclic dependency 1
+ldep1 = pmpkg('dep1')
+self.addpkg2db('local', ldep1)
+ldep1.depends = [ 'dep2', 'dep3', 'dep4' ]
+ldep1.reason = 1
+
+# cyclic dependency 2
+ldep2 = pmpkg('dep2')
+self.addpkg2db('local', ldep2)
+ldep2.depends = [ 'dep1' ]
+ldep2.reason = 1
+
+# dependency required by another package
+ldep3 = pmpkg('dep3')
+self.addpkg2db('local', ldep3)
+ldep3.reason = 1
+
+# explicitly installed dependency
+ldep4 = pmpkg('dep4')
+self.addpkg2db('local', ldep4)
+ldep4.reason = 0
+
+self.args = "-Rs pkg1"
+
+self.addrule("PACMAN_RETCODE=0")
+self.addrule("PKG_EXIST=pkg2")
+self.addrule("PKG_EXIST=dep3")
+self.addrule("PKG_EXIST=dep4")
+self.addrule("!PKG_EXIST=pkg1")
+self.addrule("!PKG_EXIST=dep1")
+self.addrule("!PKG_EXIST=dep2")