solver protocol (EDSP): first draft

[ntk/apt.git] / doc / apt-solver-protocol.mdwn

** TENTATIVE PROPOSAL, VERY VERY VERY DRAFT **

# APT External Dependency Solver Protocol (EDSP) - version 0.1

This document describes the communication protocol between APT and
external dependency solvers. The protocol is called APT EDSP, for "APT
External Dependency Solver Protocol".


## Components

- **APT**: we know this one.
- APT is equipped with its own **internal solver** for dependencies,
  which is identified by the string `internal`.
- **External solver**: an *external* software component able to resolve
  dependencies on behalf of APT. Each external solver is identified by
  an unique string (other than `internal`) called the solver **name**.

At each interaction with APT, a single solver is in use.  When there is
a total of 2 or more solvers, internals or externals, the user can
choose which one to use.


## Installation

Each external solver is installed as a file under
`/usr/lib/apt/solvers`. The naming scheme is
`/usr/lib/apt/solvers/NAME`, where `NAME` is the name of the external
solver.

Each file under `/usr/lib/apt/solvers` corresponding to an external
solver must be executable.

No non-solver files must be installed under `/usr/lib/apt/solvers`, so
that an index of available external solvers can be obtained by simply
looking at the content of that directory.


## Configuration

Several APT options can be used to affect dependency solving in APT. An
overview of them is given below. Please refer to proper APT
configuration documentation for more, and more up to date, information.

- **APT::Solver::Name**: the name of the solver to be used for
  dependency solving. Defaults to `internal`

- **APT::Solver::Strict-Pinning**: whether pinning must be strictly
  respected (as the internal solver does) or can be slightly deviated
  from. Defaults to `yes`.

- **APT::Solver::Preferences**: solver-specific user preferences used
  during dependency solving. Check your solver documentation for what is
  supported here. Default to empty.


## Protocol

When configured to use an external solver, APT will resort to it to
decide which packages should be installed or removed.

The interaction happens **in batch**: APT will invoke the external
solver passing the current status of installed and available packages,
as well as the user request to alter the set of installed packages. The
external solver will compute a new complete set of installed packages
and gives APT a "diff" listing of which *additional* packages should be
installed and of which currently installed packages should be
*removed*. (Note: the order in which those actions have to be performed
will be up to APT to decide.)

External solvers are invoked by executing them. Communications happens
via the file descriptors: **stdin** (standard input) and **stdout**
(standard output). stderr is not used by the EDSP protocol. Solvers can
therefore use stderr to dump debugging information that could be
inspected separately.

After invocation, the protocol passes through 3 separate phases:

1. APT send to the solver a dependency solving **scenario**
2. The solver solves dependencies. No communication with APT happens
   during this phase.
3. The solver sends back to APT an **answer**, i.e. either a *solution*
   or an *error* report.


### Scenario

A scenario is a text file encoded in a format very similar to the "Deb
822" format (AKA "the format used by Debian `Packages` files"). A
scenario consists of two distinct parts: a **request** and a **package
universe**, occurring in that order. The request consists of a single
Deb 822 stanza, while the package universe consists of several such
stanzas. All stanzas occurring in a scenario are separated by an empty
line.


#### Request

Within a dependency solving scenario, a request represents the action on
installed packages requested by the user.

A request is a single Deb 822 stanza opened by a mandatory Request field
and followed by a mixture of action and preference fields.

The value of the **Request:** field is a string describing the EDSP
protocol which will be used to communicate. At present, the string must
be `EDSP 0.1`.

a unique request identifier, such as an
UUID. Request fields are mainly used to identify the beginning of a
request stanza; their actual values are otherwise not used by the EDSP
protocol.

The following **action fields** are supported in request stanzas:

- **Install:** (optional, defaults to the empty string) A space
  separated list of package names, with *no version attached*, to
  install. This field denotes a list of packages that the user wants to
  install, usually via an APT `install` request.

- **Remove:** (optional, defaults to the empty string) Same syntax of
  Install. This field denotes a list of packages that the user wants to
  remove, usually via APT `remove` or `purge` requests.

- **Upgrade:** (optional, defaults to `no`). Allowed values: `yes`,
  `no`. When set to `yes`, an upgrade of all installed packages has been
  requested, usually via an APT `upgrade` request.

- **Dist-Upgrade:** (optional, defaults to `no`). Allowed values: `yes`,
  `no`. Same as Upgrade, but for APT `dist-upgrade` requests.

- **Autoremove:** (optional, defaults to `no`). Allowed values: `yes`,
  `no`. When set to `yes`, a clean up of unused automatically installed
  packages has been requested, usually via an APT `autoremove` request.

The following **preference fields** are supported in request stanzas:

- **Strict-Pinning:** (optional, defaults to `yes`). Allowed values:
  `yes`, `no`. When set to `yes`, APT pinning is strict, in the sense
  that the solver must not propose to install packages which are not APT
  candidates (see the `APT-Pin` and `APT-Candidate` fields in the
  package universe). When set to `no`, the solver does only a best
  effort attempt to install APT candidates. Usually, the value of this
  field comes from the `APT::Solver::Strict-Pinning` configuration
  option.

- **Preferences:** a solver-specific optimization string, usually coming
  from the `APT::Solver::Preferences` configuration option.


#### Package universe

A package universe is a list of Deb 822 stanzas, one per package, called
**package stanzas**. Each package stanzas starts with a Package
field. The following fields are supported in package stanzas:

- All fields supported by Debian Packages file (see one of the
  `/var/lib/apt/lists/*Packages` file for an example), *with the
  exception of the Description field* that is not allowed.
  
  Among those fields, the following are mandatory: Package, Version,
  Architecture.

- **Installed:** (optional, default value `no`). Allowed values: `yes`,
  `no`. When set to `yes`, the corresponding package is currently
  installed.

  ##TODO## changed with respect to current prototype, which uses Status

- **APT-ID:** (mandatory). Unique package identifier, according to APT.

- **APT-Pin:** (mandatory). Must be a non-negative integer. Package pin
  value, according to current APT policy.

- **APT-Candidate:** (optional, default value `no`). Allowed values:
  `yes`, `no`. When set to `yes`, the corresponding package is granted
  to have the highest pinning value among all the packages having the
  same name.
  
  ##TODO## what about multi-arch? is the pin value granted to be the
  higest also across different architectures?
  

### Answer

An answer from the external solver to APT is either a *solution* or an
*error*.

The following invariant on **exit codes** must hold true. When the
external solver is *able to find a solution*, it will write the solution
to standard output and then exit with an exit code of 0. When the
external solver is *unable to find a solution* (and aware of that), it
will write an error to standard output and then exit with an exit code
of 0. An exit code other than 0 will be interpreted as a solver crash
with no meaningful error about dependency resolution to convey to the
user.


#### Solution

A solution is a single Deb 822 stanza, starting with the field
Solution. The following fields are supported in solution stanzas:

- **Solution:** (mandatory). The value of this field is ignored,
  although it should be a unique solution identifier, such as a UUID.

- **Install:** (optional, defaults to the empty string). A space
  separated list of strings of the form `PACKAGE=VERSION` where
  `PACKAGE` is a package name and `VERSION` is an available version of
  that package. The list denotes a set of packages that must be
  installed to satisfy user request.

- **Remove:** (optional, defaults to the empty string). Same as Install,
  but denoting a set of packages that must be removed to satisfy user
  request.


#### Error

An error is a single Deb 822 stanza, starting the field Error. The
following fields are supported in error stanzas:

- **Error:** (mandatory). The value of this field is ignored, although
  it should be a unique error identifier, such as a UUID.

- **Message:** (mandatory). The value of this field is a text string,
  meant to be read by humans, that explains the cause of the solver
  error.

  ##TODO## can we support line continuations throughout this format? If
  yes, they might come handy both for error stanzas and for solution
  stanzas (which might have very long install/remove lines)


** TENTATIVE PROPOSAL, VERY VERY VERY DRAFT **