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")