apt-cudf bridges apt-get with external CUDF solvers. It implements a translator from the EDSP format to the CUDF format, invokes an external solver, and transmits back to apt-get the outcome using the EDSP format.
This primer applies to version of apt-cudf.
apt-getStarting from release 0.9.x, apt-get is able to use external solvers via the EDSP protocol. In order to use apt-get with an external solver you need to have installed , besides apt itself, the package apt-cudf and at least one solver package. Currently available solver packages in debian are aspcud, mccs, and packup.
The integration of CUDF solvers in apt-get is transparent from the user’s perspective. To invoke an external solver you just have to pass the option –solver to apt-get, followed by the name of the CUDF solver to use. These solvers use different technologies and can provide slightly different solutions.
Using an external CUDF solver does not require any other particular action from the user. The –simulate (or -s) option is used here to make apt-get just display the action it would perform, without actually performing it:
$apt-get --simulate --solver aspcud install gnome
NOTE: This is only a simulation!
apt-get needs root privileges for real execution.
Keep also in mind that locking is deactivated,
so don't depend on the relevance to the real current situation!
Reading package lists... Done
Building dependency tree
Reading state information... Done
Execute external solver... Done
The following extra packages will be installed:
[...]Depending on the solver, the invocation of an external solver can take longer then the apt-get internal solver. This difference is to due to the additional conversion step from EDSP to CUDF and back, plus the effective solving time.
apt-get itself ships two EDSP-compatible tools:
internal (since release 0.8.x) refers to the internal apt-get dependency solver;
dump is not a real solver but just dumps the EDSP document into the text file /tmp/dump.edsp.
For example, the following invocation is equivalent to invoking apt-get without the –solver argument:
apt-get install --solver internal <package-to-be-installed>CUDF-based solvers understand user preferences and use them to select a best solution. Compared with apt-get, this gives the user a greater flexibility to define “optimal” solutions for installation problems, for instance to minimize the number of new packages that are installed, or to minimize the total installation size the packages to upgrade.
Each CUDF solver understands a basic optimization language, and some of them implement extensions to this basic language to implement more sophisticated optimization criteria. apt-cudf, that is the bridge between apt-get and the CUDF solver, associates to each apt-get command an optimization criterion that can be either configured at each invocation using one apt-get configuration option or by using the configuration file (/etc/apt-cudf.conf ) of apt-cudf (see Section 4.1.2 for their precise meaning):
solver: *
upgrade: -count(new),-count(removed),-count(notuptodate)
dist-upgrade: -count(notuptodate),-count(new)
install: -count(removed),-count(changed)
remove: -count(removed),-count(changed)
trendy: -count(removed),-count(notuptodate),-count(unsat_recommends),-count(new)
paranoid: -count(removed),-count(changed)The field solver defines the (comma-separated) list of solvers to which this stanza applies. The symbol “*” indicates that this stanza applies to all solvers that do not have a specific stanza.
Each field of the stanza defines the default optimization criterion. If one field name coincides with a standard apt-get action, like install, remove, upgrade or dist-upgrade, then the corresponding criterion will be used by the external solver. Otherwise, the field is interpreted as a short-cut definition that can be used on the apt-get command line.
Using the configuration option of apt-get APT::Solver::aspcud::Preferences, the user can pass a specific optimization criterion on the command line overwriting the default. For example :
apt-get -s --solver aspcud install totem -o "APT::Solver::aspcud::Preferences=trendy"The measurements that may be used in optimization criteria are taken on selected sets of packages in order to measure the quality of a proposed solution. In this context, when we speak of package we mean a package in a specific version. That is, a package with name p and version 1 is considered a different package then the one with the same name p and different version 2. We will denote with I the set of packages (always name and version) that are initially in state installed on the machine, and with S the set of packages that are in state installed as a result of the apt-get action.
the set S
the symmetric difference between I and S, that is the set of packages that are either in I and not in S, or in S and not in I.
the set of packages in S for which no package with the same name is in I.
the set of packages in I for which no package with the same name is in S.
the set of of packages in S for which a package with the same name but smaller version is in I.
the set of of packages in S for which a package with the same name but greater version is in I.
Several ways to measure sets are defined. All these measurements yield an integer value. Here, X can be any of the sets defined above:
the number of elements of set X
where f is an integer package property. Yields the sum of all f-values of all the packages in X.
Example: sum(solution,Installed-Size) is the size taken up by all installed packages when the apt-get action has succeeded (as declared in the Packages file).
the number of packages in X whose version is not the latest version.
Example: notuptodate(solution) is the number of packages that will be installed when the apt-get action has succeeded, but not in their latest version.
this is the number of recommended packages in X that are not in S (or not satisfied in S, in case the recommendation uses alternatives).
For instance, if package a recommends b, c|d|e, e|f|g, b|g, h and if S is {a, e, f, h} then one would obtain for the package a alone a value of 2 for unsat_recommends since the 2nd, 3rd and 5th disjunct of the recommendation are satisfied, and the 1st and 4th disjunct are not. If no other package in X contains recommendations that means that, in that case, unsat_recommends(X)=2.
where f1 and f2 are integer or string properties. This is the number of of different pairs (x.f1, x.f2) for packages x in X, minus the number of different values x.f1 for packages x in X.
In other words, we cluster the packages in X according to their values at the properties f1 and f2 and count the number of clusters, yielding a value v1. Then we do the same when clustering only by the property g1, yielding a value v2. The value returned is v1-v2.
An optimization criterion is a comma-separated list of signed measurements.
A measurement signed with + means that we seek to maximize this value, a measurement signed with − that we seek to minimize this value. To compare two possible solutions we use the signed measurements from left to right. If both measurements yield the same value on both solutions then we continue with the next signed measurement (or conclude that both solutions are equally good in case we are at the end of the list). If the measurements are different on both solutions then we use this measurement to decide which of the solutions is the better one.
Example 1: -count(removed), -count(changed), sometimes called the paranoid criterion. It means that we seek to remove as few packages as possible. If there are several solutions with the same number of packages to remove then we chose the one which changes the least number of packages.
Example 2: -count(removed),-count(notuptodate),-count(unsat_recommends),-count(new), sometimes called the trendy criterion. Here we use the following priority list of criteria:
remove as few packages as possible
have as few packages as possible in a version which is not the latest version
have as few as possible recommendations of packages that are not satisfied
install as few new packages as possible.
When a package is available in more than one version, apt-get uses a mechanism known as pinning to decide which version should be installed. However, since this mechanism determines early in the process which package versions must be considered and which package versions should be ignored, it has also the consequence of considerably limiting the search space. This might lead to apt-get with its internal solver not finding a solution even if one might exist when all packages are considered.
Anther consequence of the strict pinning policy of apt-get is that if a package is specified on the command line with version or suite annotations, overwriting the pinning strategy for this package, but not for its dependencies, then the solver might not be able to find a solution because not all packages are available.
To circumvent this restriction and to allow the underlying solver to explore the entire search space, apt-get can be configured to let the CUDF solver ignore the pinning annotation.
The option APT::Solver::Strict-Pinning, when used in conjunction with an external solver, tells apt-get to ignore pinning information when solving dependencies. This may allow the external solver to find a solution that is not found by the apt-get internal solver.
Without relaxing the way that pinning information are encoded, apt-cudf with an external CUDF solver would be effectively unable to do better then apt-get because important information is lost on the way. In order to overcome this limitation, apt-cudf has the ability to reconstruct the user request and to use this information to provide a possible solution. To this end, apt-cudf reads an environment variable, named APT_GET_CUDF_CMDLINE which the user can pass along containing the invocation of apt-get.
To make it straightforward for the user, a very simple script called apt-cudf-get is provided by the apt-cudf package.
#!/bin/sh
export APT_GET_CUDF_CMDLINE="apt-get $* -o APT::Solver::Strict-Pinning=\"false\""
apt-get $* -o APT::Solver::Strict-Pinning="false"The wrapper is invoked using the same commands as apt-get:
apt-cudf-get -s --solver aspcud install totem \
-o "APT::Solver::aspcud::Preferences=-count(new),-count(changed)"