Some packages with large dependency trees cause tpkg to hit the 10000 solution limit

[jheiss]

I've seen a few reports now of various packages, tending to have fairly large dependency trees, where attempts to install the package sometimes cause tpkg to hit the 10000 checked solution limit before it finds an acceptable solution.

Usually the problem is encountered when few to none of the dependencies are already installed. I've generally been able to work around that by manually installing some of the dependencies, thus reducing the size of the problem that tpkg has to solve when installing the main package.

I suspect this is due to the dependency resolution code in tpkg using a nil value at the start of the array of possible packages to indicate that there is no acceptable version of that package currently installed. (This is done to ensure that already installed packages score higher than not installed packages.) This causes tpkg to have to check a lot of solutions involving a 'nil' entry for that particular package and discard them, before eventually getting to possible solutions using later items in the array.

Was: https://sourceforge.net/apps/trac/tpkg/ticket/22

[jheiss]

Pasting in an email I sent a user who asked about this problem since it contains a bit more detail about the issue:

The problem is that tpkg is spending a bunch of time checking bogus combinations of packages because it has to exclude all solution variations which involve the possibility of one or more of the dependencies being currently installed, even if there is no version of that dependency currently installed.

I.e. imagine you have nothing installed and ask tpkg to install pkgA, which depends on pkgB and pkgC. tpkg will build up arrays of candidate packages sorted as follows:

	pkgA	pkgB	pkgC
0	nil	nil	nil
1	pkgA-2.0.tpkg	pkgB-2.0.tpkg	pkgC-2.0.tpkg
2	pkgA-1.0.tpkg	pkgB-1.0.tpkg	pkgC-1.0.tpkg

tpkg will test [pkgA-2.0.tpkg, pkgB-2.0.tpkg, nil], [pkgA-2.0.tpkg, nil, pkgC-2.0.tpkg], etc. before getting to the valid solution of [pkgA-2.0.tpkg, pkgB-2.0.tpkg, pkgC-2.0.tpkg]. If the number of dependencies is large then the number of bogus combinations is quite large.

As noted in the ticket the nils are inserted into the array to ensure that currently installed packages score higher than not-installed packages. If you had the 1.0 packages installed the arrays would instead look like:

	pkgA	pkgB	pkgC
0	pkgA-1.0.tpkg (installed)	pkgB-1.0.tpkg (installed)	pkgC-1.0.tpkg (installed)
1	pkgA-2.0.tpkg (in repository)	pkgB-2.0.tpkg (in repository)	pkgC-2.0.tpkg (in repository)
2	pkgA-1.0.tpkg (in repository)	pkgB-1.0.tpkg (in repository)	pkgC-1.0.tpkg (in repository)

That ensure that the currently installed versions score higher unless you specifically tell tpkg that you want it to upgrade one of those packages.

Fixing this involves modifying tpkg's dependency solving algorithm to somehow prefer installed packages without having to push nils at the start of the possible solution array if there isn't a version currently installed. I haven't had time to sit down and figure out a way to do that.

Was: https://sourceforge.net/apps/trac/tpkg/ticket/22#comment:1

[jheiss]

I have generally thought of the dependency tree as a graph and assumed that there was some graph algorithm that could be applied to find the best solution.

I just stumbled across the system being used now with RPMs, which instead treats dependency resolution as a Boolean Satisfiability Problem

https://www.youtube.com/watch?v=Z8ArpGRbxTM
https://files.opensuse.org/opensuse/en/b/b9/Fosdem2008-solver.pdf
https://en.opensuse.org/openSUSE:Libzypp%20satsolver
https://github.com/openSUSE/libsolv

[jheiss]

https://github.com/CocoaPods/Molinillo

[jheiss]

https://research.swtch.com/vgo-mvs