[pacman-dev] [PATCH] Initial draft of package cycle removal
Ashley Whetter
ashley at awhetter.co.uk
Sun May 8 15:08:58 UTC 2016
---
lib/libalpm/deps.c | 224 ++++++++++++++++++++++++---
test/pacman/tests/TESTS | 1 +
test/pacman/tests/remove-dependency-cycle.py | 25 +++
3 files changed, 231 insertions(+), 19 deletions(-)
create mode 100644 test/pacman/tests/remove-dependency-cycle.py
diff --git a/lib/libalpm/deps.c b/lib/libalpm/deps.c
index c35a275..5ee5137 100644
--- a/lib/libalpm/deps.c
+++ b/lib/libalpm/deps.c
@@ -591,6 +591,191 @@ static int can_remove_package(alpm_db_t *db, alpm_pkg_t *pkg,
return 1;
}
+// TODO: Write test for multi entry graph (ie two targets depend on a package
+// each which depend on a cycle.
+// TODO: Test the removal of a package belonging to a cycle isn't removed
+int _alpm_find_cycles(alpm_graph_t *v, alpm_list_t **path)
+{
+ v->state = -1;
+ *path = alpm_list_add(*path, v->data);
+
+ for(alpm_list_t *child_i= v->children; child_i; child_i = child_i->next) {
+ alpm_graph_t *child = child_i->data;
+ if(child->state == -1) {
+ alpm_pkg_t *child_pkg = child->data;
+ if (child_pkg->removes) {
+ /* A cycle has already been identified on this package.
+ * Note that a single package that's part of two cycles is unsupported.
+ * Not just because of this check but because this method of cycle
+ * detection does not support figure of 8 dependency cycles due to only
+ * adding the currently detected cycle to each packages removes list,
+ * not every cycle that every package in the cycle belongs to.
+ */
+ continue;
+ }
+
+ alpm_list_t *cycle_pkgs;
+
+ for(cycle_pkgs = *path; cycle_pkgs; cycle_pkgs = cycle_pkgs->next) {
+ alpm_pkg_t *cycle_pkg = cycle_pkgs->data;
+ if(cycle_pkg->name_hash == child_pkg->name_hash) {
+ break;
+ }
+ }
+
+ if (cycle_pkgs == NULL) {
+ /* False alarm. We've seen this node before but on a different path.
+ * Therefore the node has already been processed. */
+ continue;
+ }
+
+ /* Store the cycle in the removes of each package */
+ for(alpm_list_t *i = cycle_pkgs; i; i = i->next) {
+ alpm_pkg_t *cycle_pkg = i->data;
+
+ cycle_pkgs = alpm_list_remove_item(cycle_pkgs, i);
+
+ alpm_list_t *removes = alpm_list_copy(cycle_pkgs);
+
+ cycle_pkg->removes = alpm_list_join(cycle_pkg->removes, removes);
+
+ /* Reinsert cycle_pkg into the list */
+ if (i->next == NULL) {
+ /* i was the last item in the list */
+ i->prev->next = i;
+ cycle_pkgs->prev = i;
+ }
+ else if (i->next == cycle_pkgs) {
+ /* i was the first item in the list */
+ cycle_pkgs->prev = i;
+ cycle_pkgs = i;
+ }
+ else {
+ /* i was in the middle of the list somewhere */
+ i->next->prev = i;
+ i->prev->next = i;
+ }
+ }
+ }
+ else {
+ if(_alpm_find_cycles(child, path)) {
+ return 1;
+ }
+ }
+ }
+
+ *path = alpm_list_remove_item(*path, alpm_list_last(*path));
+
+ return 0;
+}
+
+void _alpm_graph_unvisit_all(alpm_graph_t *v)
+{
+ if (v->state == 0) {
+ return;
+ }
+
+ v->state = 0;
+ for(alpm_list_t *child_i = v->children; child_i; child_i = child_i->next) {
+ alpm_graph_t *child = child_i->data;
+ if(child->state) {
+ _alpm_graph_unvisit_all(child);
+ }
+ }
+}
+
+/**
+ * @brief Checks that a cycle can be removed.
+ * In its `removes` list,
+ * a cycle package should have a list of the other packages in the cycle.
+ *
+ * A cycle can be removed if no packages outside of the cycle depend on any
+ * packages in the cycle.
+ *
+ * @param TODO
+ * @returns true if the cycle can be removed. false otherwise.
+ */
+int _can_remove_cycle(alpm_db_t *db, alpm_pkg_t *cycle_pkg, alpm_list_t *targs,
+ int include_explicit)
+{
+ alpm_list_t *to_check = alpm_list_copy(cycle_pkg->removes);
+ to_check = alpm_list_add(to_check, cycle_pkg);
+ int retval = 1;
+
+ _alpm_log(db->handle, ALPM_LOG_DEBUG, "checks\n");
+ for(alpm_list_t *i = to_check; i; i = i->next) {
+ alpm_pkg_t *pkg = i->data;
+ /*_alpm_log(db->handle, ALPM_LOG_DEBUG, "checking if '%s' can be removed\n",
+ pkg->name);*/
+
+ /* Pretend we are removing the rest of the cycle */
+ alpm_list_t *targs_with_cycle = alpm_list_copy(targs);
+ alpm_list_t *cycle_pkgs = alpm_list_copy(pkg->removes);
+ targs_with_cycle = alpm_list_join(targs_with_cycle, cycle_pkgs);
+
+ int can_rm = can_remove_package(db, pkg, targs_with_cycle, include_explicit);
+
+ alpm_list_free(targs_with_cycle);
+
+ if (!can_rm) {
+ //_alpm_log(db->handle, ALPM_LOG_DEBUG, "It can't\n");
+ retval = 0;
+ break;
+ }
+ //_alpm_log(db->handle, ALPM_LOG_DEBUG, "It can!\n");
+ }
+
+ /* Cleanup the creation of to_check */
+ alpm_list_free(to_check);
+
+ return retval;
+}
+
+int _alpm_find_removables(alpm_db_t *db, alpm_graph_t *v, alpm_list_t **targs, int include_explicit)
+{
+ if (v->state) {
+ return 0;
+ }
+
+ v->state = -1;
+ alpm_pkg_t *pkg = v->data;
+
+ alpm_list_t *to_remove = NULL;
+ if(pkg->removes != NULL) {
+ if(_can_remove_cycle(db, pkg, *targs, include_explicit)) {
+ to_remove = alpm_list_add(to_remove, pkg);
+ to_remove = alpm_list_join(to_remove, alpm_list_copy(pkg->removes));
+ }
+ }
+ else if(can_remove_package(db, pkg, *targs, include_explicit)) {
+ to_remove = alpm_list_add(to_remove, pkg);
+ }
+
+ for(alpm_list_t *k = to_remove; k; k = k->next) {
+ alpm_pkg_t *rm_pkg = k->data;
+ alpm_pkg_t *copy = NULL;
+ _alpm_log(db->handle, ALPM_LOG_DEBUG, "adding '%s' to the targets\n",
+ rm_pkg->name);
+ /* add it to the target list */
+ if(_alpm_pkg_dup(rm_pkg, ©)) {
+ /* we return memory on "non-fatal" error in _alpm_pkg_dup */
+ _alpm_pkg_free(copy);
+
+ alpm_list_free(to_remove);
+ return -1;
+ }
+ *targs = alpm_list_add(*targs, copy);
+ }
+
+ alpm_list_free(to_remove);
+
+ for(alpm_list_t *child = v->children; child; child = child->next) {
+ _alpm_find_removables(db, child->data, targs, include_explicit);
+ }
+
+ return 0;
+}
+
/**
* @brief Adds unneeded dependencies to an existing list of packages.
* By unneeded, we mean dependencies that are only required by packages in the
@@ -604,32 +789,33 @@ 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 *vertices;
+ int retval = 0;
if(db == NULL || targs == NULL) {
return -1;
}
- 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, ©)) {
- /* we return memory on "non-fatal" error in _alpm_pkg_dup */
- _alpm_pkg_free(copy);
- return -1;
- }
- *targs = alpm_list_add(*targs, copy);
- }
+ vertices = dep_graph_init(db->handle, *targs, NULL);
+ for(alpm_list_t *v_i = vertices; v_i; v_i = v_i->next) {
+ alpm_graph_t *v = v_i->data;
+ alpm_list_t *path = NULL;
+
+ if (_alpm_find_cycles(v, &path)) {
+ retval = -2;
+ goto cleanup;
}
+
+ _alpm_graph_unvisit_all(v);
+ _alpm_find_removables(db, v, targs, include_explicit);
+ _alpm_graph_unvisit_all(v);
}
- return 0;
+
+cleanup:
+ alpm_list_free_inner(vertices, _alpm_graph_free);
+ alpm_list_free(vertices);
+
+ return retval;
}
/**
diff --git a/test/pacman/tests/TESTS b/test/pacman/tests/TESTS
index 62d1f2a..eee845f 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-dependency-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-dependency-cycle.py b/test/pacman/tests/remove-dependency-cycle.py
new file mode 100644
index 0000000..a4769de
--- /dev/null
+++ b/test/pacman/tests/remove-dependency-cycle.py
@@ -0,0 +1,25 @@
+self.description = "Recursively removing a package depending on a cycle removes the cycle"
+
+cycle_dep1 = pmpkg("cycle_dep1")
+self.addpkg2db("local", cycle_dep1)
+
+cycle_pkg1 = pmpkg("cycle_pkg1")
+cycle_pkg2 = pmpkg("cycle_pkg2")
+
+cycle_pkg1.depends = ["cycle_dep1", "cycle_pkg2"]
+cycle_pkg2.depends= ["cycle_pkg1"]
+
+self.addpkg2db("local", cycle_pkg1)
+self.addpkg2db("local", cycle_pkg2)
+
+removal_target = pmpkg("removal_target")
+removal_target.depends = ["cycle_pkg1"]
+self.addpkg2db("local", removal_target)
+
+self.args = "-Rss removal_target"
+
+self.addrule("PACMAN_RETCODE=0")
+self.addrule("!PKG_EXIST=cycle_dep1")
+self.addrule("!PKG_EXIST=cycle_pkg1")
+self.addrule("!PKG_EXIST=cycle_pkg2")
+self.addrule("!PKG_EXIST=removal_target")
--
2.8.0
More information about the pacman-dev
mailing list