[pacman-dev] [PATCH] Initial draft of package cycle removal

[Andrew Gregory]

On 05/08/16 at 04:08pm, Ashley Whetter wrote:
> ---
>  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

This is way more complicated than necessary.  For larger, more
complex, dependency chains the performance degrades significantly and
it gives incorrect results.  I still think the best solution is to
just select the entire dependency chain then filter out packages
required by packages we won't be uninstalling.  I've pushed an initial
draft to my recursedeps branch:
https://github.com/andrewgregory/pacman/commits/recursedeps

I modified your test to be more strenuous in order to compare
performance and got the following results:

 origin/master:         0.11s FAIL
 awhetter/recursedeps: 22.71s FAIL (only passes with limit < 4)
 apg/recursedeps:       0.20s PASS

Unless there's something critically wrong with my patch, I think using
a graph to detect cycles is a dead-end.

The modified test:

 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", "pkg1"]
 self.addpkg2db("local", removal_target)
 
 limit = 1000
 self.addpkg2db("local", pmpkg("pkg%d" % 0))
 self.addpkg2db("local", pmpkg("pkg%d" % limit))
 for i in xrange(1, limit):
     pkg = pmpkg("pkg%d" % i)
     pkg.depends = [ "pkg%d" % (i - 1), "pkg%d" % (i + 1) ]
     self.addpkg2db("local", pkg)
 
 outsider = pmpkg("outsider")
 outsider.depends = [ "pkg%d" % (limit - 0) ]
 self.addpkg2db("local", outsider)
 
 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=pkg0")
 self.addrule("!PKG_EXIST=pkg1")
 self.addrule("!PKG_EXIST=pkg%d" % (limit - 1))
 self.addrule("!PKG_EXIST=removal_target")
 self.addrule("PKG_EXIST=pkg%d" % limit)
 self.addrule("PKG_EXIST=outsider")