FS#41031 - pacman -Rs misses some unneeded dependencies in case of dependency cycle

Attached to Project: Pacman
Opened by Nagy Gabor (combo) - Sunday, 29 June 2014, 11:34 GMT
Last edited by Andrew Gregory (andrewgregory) - Wednesday, 30 November 2016, 20:26 GMT
Task Type Bug Report
Category General
Status Closed
Assigned To Andrew Gregory (andrewgregory)
Architecture All
Severity Low
Priority Normal
Reported Version 4.1.2
Due in Version 5.1.0
Due Date Undecided
Percent Complete 100%
Votes 0
Private No


Pacman v4.1.2 - libalpm v8.0.2

Steps to Reproduce:
On a pure 64 bit system do

$ pacman -S skype
$ pacman -Rs skype

This installs 64 packages, but removes only 51.

The details are in the attached log files.
This task depends upon

Closed by  Andrew Gregory (andrewgregory)
Wednesday, 30 November 2016, 20:26 GMT
Reason for closing:  Fixed
Additional comments about closing:  Fixed in git 6ac2ee21b30f3c5f331d19349f96bb8e5b020b47
Comment by Allan McRae (Allan) - Sunday, 29 June 2014, 12:10 GMT
The left behind packages are not even detected by "pacman -Qqtd" because of the dependency cycle - this is two packages depending on each other plus their dependencies.
Comment by Nagy Gabor (combo) - Sunday, 29 June 2014, 17:36 GMT
Well, I think it is far from trivial to fix this.

Theoretically, what we need is to compute the strongly connected components of the ("recursive") dependencies of the to-be-removed packages in the dependency graph of installed packages, and treat such a strongly connected component as one package (when there is no dependency cycle, these components are indeed consist of one package). This needs a notable amount of code added, as well as additional running time with -Rs. (Moreover, provisions make our lives more difficult, as usual.)

The fix of the "A depend on B, B depend on A" case would be simpler, but only a half solution.

I don't really see why we have dependency cycles in our repos at all. For example, in the above case, the packages A and B should be merged, and the "bigger" one should provide the "smaller" one.
Comment by Andrew Gregory (andrewgregory) - Sunday, 29 June 2014, 22:24 GMT
It might be easier to reverse how we calculate removable dependencies. Instead of adding packages not required by anything else and trying to detect these cycles, go ahead and select all dependencies and then filter out the ones required by packages not part of the transaction.
Comment by John (graysky) - Wednesday, 30 November 2016, 19:33 GMT
Another example is installing deluge and then removing it which leaves behind a number of python2 dependencies that the original install operation pulled in related to python2-twisted. These were not present on the system before installing deluge but python2-twisted is an optdep of another package already on the system (avahi in this case).

1) `pacman -S deluge` pulls in 21 python2-* dependencies
2) `pacman -Rs deluge` only removes 16 of them. The remaining 5 need to be removed by removing python2-twisted.

After these two transactions, python2-twisted and its dependencies are left behind and they were not present before installing deluge:

# pacman -Rs python2[TAB]
python2 python2-constantly python2-twisted
python2-click python2-incremental python2-zope-interface