Home / ubuntu / Questions / 1508011
Accepted
charmoniumQ
Asked: 2024-03-20 04:02:33 +0800 CST

What dependency solver does APT use?

  • 772

I noticed packages have version constraints in their metadata (e.g., git). What algorithm does APT use to satisfy these dependencies?

E.g., Spack uses Clingo as its dependency solver, Conda and Mamba use libsolv, Pip uses its own custom backtracking solver.

apt

1 Answers

  1. Best Answer

    APT pre-dates the idea of dependency resolution being an interesting property of a system to be studied independently of the program which performs the dependency resolution, so APT's dependency resolution algorithm is basically: "Whatever the source code of APT happens to do".

    In particular, APT was (one of) the first package manager(s) to provide dependency resolution at all, so there was no reason to discuss its algorithm independent of APT and, for example, compare it to RPM's, because RPM didn't have dependency resolution.

    Now, of course, the developers of APT haven't just coded this up randomly, but my point is: the algorithm doesn't have a name, because at the time, it was the only one, and so there was no reason to talk about the algorithm without also talking about APT and vice versa.

    There is a little bit of information in the README section about Debugging:

    Dependency resolution

    APT works in its internal resolver in two stages: First all packages are visited and marked for installation, keep back or removal. Option Debug::pkgDepCache::Marker shows this. This also decides which packages are to be installed to satisfy dependencies, which can be seen by Debug::pkgDepCache::AutoInstall. After this is done, we might be in a situation in which two packages want to be installed, but only one of them can be. It is the job of the pkgProblemResolver to decide which of two packages 'wins' and can therefore decide what has to happen. You can see the contenders as well as their fight and the resulting resolution with Debug::pkgProblemResolver.

    Here's a fun little comment from the source code:

    /* ######################################################################

   Algorithms - A set of misc algorithms

   The pkgProblemResolver class has become insanely complex and
   very sophisticated, it handles every test case I have thrown at it
   to my satisfaction. Understanding exactly why all the steps the class
   does are required is difficult and changing though not very risky
   may result in other cases not working.
   
   ##################################################################### */

    The blog article Debian APT dependency resolver in Rinzwind's comment goes into a lot more detail. It was written by a package maintainer who was confused about a strange thing that happened with their package, and dives into minute details of the algorithm.

    • 5