# [Aptitude-devel] r3019 - branches/aptitude-0.3/aptitude/src/generic/problemresolver

Daniel Burrows dburrows@costa.debian.org
Thu, 21 Apr 2005 00:57:55 +0000

Author: dburrows
Date: Thu Apr 21 00:57:54 2005
New Revision: 3019

Modified:
branches/aptitude-0.3/aptitude/src/generic/problemresolver/model.tex
Log:

Modified: branches/aptitude-0.3/aptitude/src/generic/problemresolver/model.tex
==============================================================================
--- branches/aptitude-0.3/aptitude/src/generic/problemresolver/model.tex	(original)
+++ branches/aptitude-0.3/aptitude/src/generic/problemresolver/model.tex	Thu Apr 21 00:57:54 2005
@@ -26,7 +26,6 @@
\title{Modelling and Resolving Software Dependencies}

\newcommand{\pkg}[1]{\text{\url{#1}}}
-\newcommand{\apt}{\pkg{apt}}

\renewcommand{\P}{\mathcal{P}}
\newcommand{\V}{\mathcal{V}}
@@ -90,17 +89,19 @@
upgrade his or her entire operating system, generally indicating this
fact by a slew of cascading error messages.

-As a result of this dependency hell'', a new generation of automated
-tools, such as \apt and \pkg{up2date}, was developed.  These
-tools maintain a database of software installed on the user's system,
-along with software available from any number of remote sites.  To
-install or remove a piece of software, the user issues a request to,
-for instance, install wesnoth'' or upgrade kmail''.  The
+As a result of this so-called dependency hell'', new and more
+automated tools, such as \pkg{apt} and \pkg{up2date}, were developed.
+These tools maintain a database of software installed on the user's
+system, along with software available from any number of remote sites.
+To install or remove a piece of software, the user issues a request
+to, for instance, install wesnoth'' or upgrade kmail''.  The
installation tool will proceed to find a set of package installations
or removals which leads to a consistent result.  Typically, it then
presents this list of actions to the user and prompts for
confirmation; the user can either accept the proposed solution, or
-reject it and proceed to fix the problem in a fully manual way.
+reject it and proceed to fix the problem in a fully manual way.  Once
+the user is satisfied with the proposed changes, the tool will

This approach has two major drawbacks:

@@ -109,10 +110,10 @@
leave it'' proposition: there is no way for the user to ask the
algorithm to find another solution.  This means that if the
algorithm makes a poor or undesired choice (which, as I will argue
-  below, will inevitably occur sometimes) the user is forced to fall
-  back to fully manual operation.
+  below, will inevitably occur from time to time) the user is forced
+  to fall back to fully manual operation.

-\item In at least some cases (particularly \apt), the algorithm used
+\item In at least some cases (particularly \pkg{apt}), the algorithm used
in resolving dependency conflicts deals poorly -- which is a
euphemism for not at all'' -- when there are more than two
versions of a package to choose from\footnote{More precisely, if
@@ -130,10 +131,11 @@
operate on packages to become strewn with complex iteration constructs
and unpleasant corner cases.  Although some attempts have been made to
find general models of package dependencies (for instance, the
-internal structures of \apt can represent either Debian or Red Hat
-packages), the models with which I am familiar work by taking a
-greatest upper bound'' of the systems that they cover, leading to an
-even more convoluted architecture.
+internal structures of \pkg{apt} can represent either Debian or Red
+Hat packages), the models with which I am familiar work by taking a
+greatest upper bound'' of the systems that they cover, leading to a
+generic framework that is, if anything, even more convoluted than the
+individual package systems that it covers.

\begin{note}
I have not yet performed an extensive survey of package systems, and
@@ -143,12 +145,31 @@

\section{Example: the Debian Package System}

+The Debian package system is implemented by a low-level tool known as
+\pkg{dpkg}.  Debian packages are files with the extension \url{.deb};
+\pkg{dpkg} can install a \url{.deb} file that has already been
+retrieved, or remove a package that is currently installed on the
+system.  If dependency constraints are violated, \pkg{dpkg} will print
+errors messages and abort the installation after unpacking the
+packages.
+
+The usual user interface to the package system is through one of the
+programs in the \pkg{apt} suite.  \pkg{apt} is a high-level library
+which allows C++ programs to examine the set of installed packages,
+determine what actions are to be performed, and execute these actions
+install them).  \pkg{apt}-based installation tools typically refuse to
+even begin any actions that will result in an inconsistent system
+state, and all of them provide a basic algorithm that resolves
+inconsistencies by adjusting package states until all dependencies are
+fixed.
+
In the Debian package system, each package may have one or more
versions, but at most one version of each package may be installed at
any given time.  The basic relationships between packages are
\emph{dependencies} and \emph{conflicts}.  For instance, version
6.14.00-1 of the \pkg{tcsh} command shell depends on version
-2.3.2.ds-4 or greater of the \pkg{libc6} package, and version 5.4-1 or
+2.3.2.ds-4 or greater of the \pkg{libc6} package and version 5.4-1 or
greater of the \pkg{libncurses5} package: it may not be installed
unless an appropriate version of each of these package is installed.
On the other hand, the same package conflicts with all versions of the