eipp: implement version 0.1 of the protocol

The very first step in introducing the "external installation planer
protocol" (short: EIPP) as part of my GSoC2016 project.

The description reads: APT-based tools like apt-get, aptitude, synaptic,
… work with the user to figure out how their system should look like
after they are done installing/removing packages and their dependencies.
The actual installation/removal of packages is done by dpkg with the
constrain that dependencies must be fulfilled at any point in time (e.g.
to run maintainer scripts).

Historically APT has a super micro-management approach to this task
which hasn't aged that well over the years mostly ignoring changes in
dpkg and growing into an unmaintainable mess hardly anyone can debug and
everyone fears to touch – especially as more and more requirements are
tacked onto it like handling cycles and triggers, dealing with
"important" packages first, package sources on removable media, touch
minimal groups to be able to interrupt the process if needed (e.g.
unattended-upgrades) which not only sky-rocket complexity but also can
be mutually exclusive as you e.g. can't have minimal groups and minimal
trigger executions at the same time.

7 files changed, 446 insertions, 1 deletions

diff --git a/apt-pkg/edsp.cc b/apt-pkg/edsp.cc
index 6e0a0fc2f..58982ade2 100644
--- a/apt-pkg/edsp.cc
+++ b/apt-pkg/edsp.cc
@@ -1064,3 +1064,183 @@ bool EDSP::ResolveExternal(const char* const solver, pkgDepCache &Cache,
    return ResolveExternal(solver, Cache, flags, Progress);
 }
 									/*}}}*/
+
+bool EIPP::OrderInstall(char const * const solver, pkgDepCache &Cache,	/*{{{*/
+			 unsigned int const flags, OpProgress * const Progress)
+{
+   int solver_in, solver_out;
+   pid_t const solver_pid = ExecuteExternal("planer", solver, "Dir::Bin::Planers", &solver_in, &solver_out);
+   if (solver_pid == 0)
+      return false;
+
+   FileFd output;
+   if (output.OpenDescriptor(solver_in, FileFd::WriteOnly | FileFd::BufferedWrite, true) == false)
+      return _error->Errno("OrderInstall", "Opening planer %s stdin on fd %d for writing failed", solver, solver_in);
+
+   bool Okay = output.Failed() == false;
+   if (Progress != NULL)
+      Progress->OverallProgress(0, 100, 5, _("Execute external planer"));
+   Okay &= EIPP::WriteRequest(Cache, output, flags, Progress);
+   if (Progress != NULL)
+      Progress->OverallProgress(5, 100, 20, _("Execute external planer"));
+   Okay &= EIPP::WriteScenario(Cache, output, Progress);
+   output.Close();
+
+   if (Progress != NULL)
+      Progress->OverallProgress(25, 100, 75, _("Execute external planer"));
+   if (Okay && EIPP::ReadResponse(solver_out, Cache, Progress) == false)
+      return false;
+
+   return ExecWait(solver_pid, solver);
+}
+									/*}}}*/
+bool EIPP::WriteRequest(pkgDepCache &Cache, FileFd &output,		/*{{{*/
+			unsigned int const flags,
+			OpProgress * const Progress)
+{
+   (void)(flags);
+   if (Progress != NULL)
+      Progress->SubProgress(Cache.Head().PackageCount, _("Send request to planer"));
+   unsigned long p = 0;
+   string del, purge, inst, reinst;
+   for (pkgCache::PkgIterator Pkg = Cache.PkgBegin(); Pkg.end() == false; ++Pkg, ++p)
+   {
+      if (Progress != NULL && p % 100 == 0)
+         Progress->Progress(p);
+      string* req;
+      pkgDepCache::StateCache &P = Cache[Pkg];
+      if (P.Purge() == true)
+	 req = &purge;
+      if (P.Delete() == true)
+	 req = &del;
+      else if (P.NewInstall() == true || P.Upgrade() == true)
+	 req = &inst;
+      else if (P.ReInstall() == true)
+	 req = &reinst;
+      else
+	 continue;
+      req->append(" ").append(Pkg.FullName());
+   }
+   bool Okay = WriteOkay(output, "Request: EIPP 0.1\n");
+
+   const char *arch = _config->Find("APT::Architecture").c_str();
+   std::vector<string> archs = APT::Configuration::getArchitectures();
+   WriteOkay(Okay, output, "Architecture: ", arch, "\n",
+	 "Architectures:");
+   for (std::vector<string>::const_iterator a = archs.begin(); a != archs.end(); ++a)
+       WriteOkay(Okay, output, " ", *a);
+   WriteOkay(Okay, output, "\n");
+
+   if (purge.empty() == false)
+      WriteOkay(Okay, output, "Purge:", purge, "\n");
+   if (del.empty() == false)
+      WriteOkay(Okay, output, "Remove:", del, "\n");
+   if (inst.empty() == false)
+      WriteOkay(Okay, output, "Install:", inst, "\n");
+   if (reinst.empty() == false)
+      WriteOkay(Okay, output, "ReInstall:", reinst, "\n");
+   WriteOkay(Okay, output, "Planer: ", _config->Find("APT::Planer", "internal"), "\n");
+   return WriteOkay(Okay, output, "\n");
+}
+									/*}}}*/
+static bool WriteScenarioEIPPVersion(pkgDepCache &Cache, FileFd &output, pkgCache::PkgIterator const &Pkg,/*{{{*/
+				pkgCache::VerIterator const &Ver)
+{
+   bool Okay = true;
+   if (Pkg.CurrentVer() == Ver)
+      switch (Pkg->CurrentState)
+      {
+	 case pkgCache::State::NotInstalled: WriteOkay(Okay, output, "\nStatus: not-installed"); break;
+	 case pkgCache::State::ConfigFiles: WriteOkay(Okay, output, "\nStatus: config-files"); break;
+	 case pkgCache::State::HalfInstalled: WriteOkay(Okay, output, "\nStatus: half-installed"); break;
+	 case pkgCache::State::UnPacked: WriteOkay(Okay, output, "\nStatus: unpacked"); break;
+	 case pkgCache::State::HalfConfigured: WriteOkay(Okay, output, "\nStatus: half-configured"); break;
+	 case pkgCache::State::TriggersAwaited: WriteOkay(Okay, output, "\nStatus: triggers-awaited"); break;
+	 case pkgCache::State::TriggersPending: WriteOkay(Okay, output, "\nStatus: triggers-pending"); break;
+	 case pkgCache::State::Installed: WriteOkay(Okay, output, "\nStatus: installed"); break;
+      }
+   if (Pkg->SelectedState == pkgCache::State::Hold)
+      WriteOkay(Okay, output, "\nHold: yes");
+   // FIXME: Ideally, an EIPP request contains at most two versions (installed and to install)
+   if (Cache.GetCandidateVersion(Pkg) == Ver)
+      WriteOkay(Okay, output, "\nAPT-Candidate: yes");
+   return Okay;
+}
+									/*}}}*/
+// EIPP::WriteScenario - to the given file descriptor			/*{{{*/
+bool EIPP::WriteScenario(pkgDepCache &Cache, FileFd &output, OpProgress * const Progress)
+{
+   if (Progress != NULL)
+      Progress->SubProgress(Cache.Head().VersionCount, _("Send scenario to planer"));
+   unsigned long p = 0;
+   bool Okay = output.Failed() == false;
+   std::vector<std::string> archs = APT::Configuration::getArchitectures();
+   std::vector<bool> pkgset(Cache.Head().VersionCount, true);
+   for (pkgCache::PkgIterator Pkg = Cache.PkgBegin(); Pkg.end() == false && likely(Okay); ++Pkg)
+   {
+      std::string const arch = Pkg.Arch();
+      if (std::find(archs.begin(), archs.end(), arch) == archs.end())
+	 continue;
+      for (pkgCache::VerIterator Ver = Pkg.VersionList(); Ver.end() == false && likely(Okay); ++Ver, ++p)
+      {
+	 Okay &= WriteScenarioVersion(output, Pkg, Ver);
+	 Okay &= WriteScenarioEIPPVersion(Cache, output, Pkg, Ver);
+	 Okay &= WriteScenarioLimitedDependency(output, Ver, pkgset, true);
+	 WriteOkay(Okay, output, "\n");
+	 if (Progress != NULL && p % 100 == 0)
+	    Progress->Progress(p);
+      }
+   }
+   return true;
+}
+									/*}}}*/
+// EIPP::ReadResponse - from the given file descriptor			/*{{{*/
+bool EIPP::ReadResponse(int const input, pkgDepCache &Cache, OpProgress *Progress) {
+   /* We build an map id to mmap offset here
+      In theory we could use the offset as ID, but then VersionCount
+      couldn't be used to create other versionmappings anymore and it
+      would be too easy for a (buggy) solver to segfault APT… */
+   /*
+   unsigned long long const VersionCount = Cache.Head().VersionCount;
+   unsigned long VerIdx[VersionCount];
+   for (pkgCache::PkgIterator P = Cache.PkgBegin(); P.end() == false; ++P) {
+      for (pkgCache::VerIterator V = P.VersionList(); V.end() == false; ++V)
+	 VerIdx[V->ID] = V.Index();
+   }
+   */
+
+   FileFd in;
+   in.OpenDescriptor(input, FileFd::ReadOnly);
+   pkgTagFile response(&in, 100);
+   pkgTagSection section;
+
+   std::set<decltype(Cache.PkgBegin()->ID)> seenOnce;
+   while (response.Step(section) == true) {
+      if (section.Exists("Progress") == true) {
+	 if (Progress != NULL) {
+	    string msg = section.FindS("Message");
+	    if (msg.empty() == true)
+	       msg = _("Prepare for receiving solution");
+	    Progress->SubProgress(100, msg, section.FindI("Percentage", 0));
+	 }
+	 continue;
+      } else if (section.Exists("Error") == true) {
+	 std::string msg = SubstVar(SubstVar(section.FindS("Message"), "\n .\n", "\n\n"), "\n ", "\n");
+	 if (msg.empty() == true) {
+	    msg = _("External planer failed without a proper error message");
+	    _error->Error("%s", msg.c_str());
+	 } else
+	    _error->Error("External planer failed with: %s", msg.substr(0,msg.find('\n')).c_str());
+	 if (Progress != NULL)
+	    Progress->Done();
+	 std::cerr << "The planer encountered an error of type: " << section.FindS("Error") << std::endl;
+	 std::cerr << "The following information might help you to understand what is wrong:" << std::endl;
+	 std::cerr << msg << std::endl << std::endl;
+	 return false;
+      } else {
+	 _error->Warning("Encountered an unexpected section with %d fields", section.Count());
+      }
+   }
+   return true;
+}
+									/*}}}*/
diff --git a/apt-pkg/edsp.h b/apt-pkg/edsp.h
index f1624cd6a..3e0982a56 100644
--- a/apt-pkg/edsp.h
+++ b/apt-pkg/edsp.h
@@ -236,4 +236,16 @@ namespace EDSP								/*{{{*/
 				    bool const autoRemove, OpProgress *Progress = NULL);
 }
 									/*}}}*/
+namespace EIPP								/*{{{*/
+{
+   APT_HIDDEN bool OrderInstall(char const * const solver, pkgDepCache &Cache,
+	 unsigned int const version, OpProgress * const Progress);
+   APT_HIDDEN bool WriteRequest(pkgDepCache &Cache, FileFd &output,
+	 unsigned int const version, OpProgress * const Progress);
+   APT_HIDDEN bool WriteScenario(pkgDepCache &Cache, FileFd &output,
+	 OpProgress * const Progress);
+   APT_HIDDEN bool ReadResponse(int const input, pkgDepCache &Cache,
+	 OpProgress * const Progress);
+}
+									/*}}}*/
 #endif
diff --git a/apt-pkg/packagemanager.cc b/apt-pkg/packagemanager.cc
index 77a6b0e57..8f884eac6 100644
--- a/apt-pkg/packagemanager.cc
+++ b/apt-pkg/packagemanager.cc
@@ -19,6 +19,7 @@
 #include <apt-pkg/orderlist.h>
 #include <apt-pkg/depcache.h>
 #include <apt-pkg/error.h>
+#include <apt-pkg/edsp.h>
 #include <apt-pkg/version.h>
 #include <apt-pkg/acquire-item.h>
 #include <apt-pkg/algorithms.h>
@@ -1036,6 +1037,11 @@ pkgPackageManager::OrderResult pkgPackageManager::OrderInstall()
    if (Debug == true)
       clog << "Beginning to order" << endl;
 
+   std::string const planer = _config->Find("APT::Planer", "internal");
+   if (planer != "internal")
+      if (EIPP::OrderInstall(planer.c_str(), Cache, 0, nullptr) == false)
+	 return Failed;
+
    bool const ordering =
 	_config->FindB("PackageManager::UnpackAll",true) ?
 		List->OrderUnpack(FileNames) : List->OrderCritical();
diff --git a/apt-private/private-cmndline.cc b/apt-private/private-cmndline.cc
index 1d1efc669..839b55964 100644
--- a/apt-private/private-cmndline.cc
+++ b/apt-private/private-cmndline.cc
@@ -186,6 +186,7 @@ static bool addArgumentsAPTGet(std::vector<CommandLine::Args> &Args, char const
       addArg(0, "auto-remove", "APT::Get::AutomaticRemove", 0);
       addArg(0, "reinstall", "APT::Get::ReInstall", 0);
       addArg(0, "solver", "APT::Solver", CommandLine::HasArg);
+      addArg(0, "planer", "APT::Planer", CommandLine::HasArg);
       if (CmdMatches("upgrade"))
       {
          addArg(0, "new-pkgs", "APT::Get::Upgrade-Allow-New", 
diff --git a/debian/apt-doc.docs b/debian/apt-doc.docs
index 6ef985371..dd2a1eee8 100644
--- a/debian/apt-doc.docs
+++ b/debian/apt-doc.docs
@@ -2,4 +2,5 @@ build/docs/guide*
 build/docs/offline*
 README.progress-reporting
 doc/external-dependency-solver-protocol.txt
+doc/external-installation-planer-protocol.txt
 doc/acquire-additional-files.txt
diff --git a/doc/external-installation-planer-protocol.txt b/doc/external-installation-planer-protocol.txt
new file mode 100644
index 000000000..028c4249f
--- /dev/null
+++ b/doc/external-installation-planer-protocol.txt
@@ -0,0 +1,243 @@
+# APT External Installation Planer Protocol (EIPP) - version 0.1
+
+This document describes the communication protocol between APT and
+external installation planer. The protocol is called APT EIPP, for "APT
+External Installation Planer Protocol".
+
+
+## Terminology
+
+In the following we use the term **architecture qualified package name**
+(or *arch-qualified package names* for short) to refer to package
+identifiers of the form "package:arch" where "package" is a package name
+and "arch" a dpkg architecture.
+
+
+## Components
+
+- **APT**: we know this one.
+- APT is equipped with its own **internal planer** for the order of
+  package installation (and removal) which is identified by the string
+  `internal`.
+- **External planer**: an *external* software component able to plan an
+  installation on behalf of APT.
+
+At each interaction with APT, a single planer is in use.  When there is
+a total of 2 or more planers, internals or externals, the user can
+choose which one to use.
+
+Each planer is identified by an unique string, the **planer name**.
+Planer names must be formed using only alphanumeric ASCII characters,
+dashes, and underscores; planer names must start with a lowercase ASCII
+letter.  The special name `internal` denotes APT's internal planer, is
+reserved, and cannot be used by external planers.
+
+
+## Installation
+
+Each external planer is installed as a file under Dir::Bin::Planers (see
+below), which defaults to `/usr/lib/apt/planers`. We will assume in the
+remainder of this section that such a default value is in effect.
+
+The naming scheme is `/usr/lib/apt/planers/NAME`, where `NAME` is the
+name of the external planer.
+
+Each file under `/usr/lib/apt/planers` corresponding to an external
+planer must be executable.
+
+No non-planer files must be installed under `/usr/lib/apt/planers`, so
+that an index of available external planers can be obtained by listing
+the content of that directory.
+
+
+## Configuration
+
+Several APT options can be used to affect installation planing 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::Planer**: the name of the planer to be used for dependency
+  solving. Defaults to `internal`
+
+- **Dir::Bin::Planers**: absolute path of the directory where to look
+  for external solvers. Defaults to `/usr/lib/apt/planers`.
+
+
+## Protocol
+
+When configured to use an external planer, APT will resort to it to
+decide in which order packages should be installed, configured and
+removed.
+
+The interaction happens **in batch**: APT will invoke the external
+planer passing the current status of (half-)installed packages and of
+packages which should be installed, as well as a request denoting the
+packages to install, reinstall, remove and purge.  The external planer
+will compute a valid plan of when and how to call the low-level package
+manager (like dpkg) with each package to satisfy the request.
+
+External planers are invoked by executing them. Communications happens
+via the file descriptors: **stdin** (standard input) and **stdout**
+(standard output). stderr is not used by the EIPP protocol. Planers can
+therefore use stderr to dump debugging information that could be
+inspected separately.
+
+After invocation, the protocol passes through a sequence of phases:
+
+1. APT invokes the external planer
+2. APT send to the planer an installation planer **scenario**
+3. The planer calculates the order. During this phase the planer may
+   send, repeatedly, **progress** information to APT.
+4. The planer sends back to APT an **answer**, i.e. either a *solution*
+   or an *error* report.
+5. The external planer exits
+
+
+### 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 an installation planer scenario, a request represents the action
+on packages requested by the user explicitly as well as potentially
+additions calculated by a dependency resolver which the user has
+accepted.
+
+An installation planer is not allowed to suggest the modification of
+package states (e.g. removing additional packages) even if it can't
+calculate a solution otherwise – the planer must error out in such
+a case. An exception is made for scenarios which contain packages which
+aren't completely installed (like half-installed or trigger-awaiting):
+Solvers are free to move these packages to a fully installed state (but
+are still forbidden to remove them).
+
+A request is a single Deb 822 stanza opened by a mandatory Request field
+and followed by a mixture of action, preference, and global
+configuration fields.
+
+The value of the **Request:** field is a string describing the EIPP
+protocol which will be used to communicate and especially which answers
+APT will understand. At present, the string must be `EIPP 0.1`. Request
+fields are mainly used to identify the beginning of a request stanza;
+their actual values are otherwise not used by the EIPP protocol.
+
+The following **configuration fields** are supported in request stanzas:
+
+- **Architecture:** (mandatory) The name of the *native* architecture on
+  the user machine (see also: `dpkg --print-architecture`)
+
+- **Architectures:** (optional, defaults to the native architecture) A
+  space separated list of *all* architectures known to APT (this is
+  roughly equivalent to the union of `dpkg --print-architecture` and
+  `dpkg --print-foreign-architectures`)
+
+The following **action fields** are supported in request stanzas:
+
+- **Install:** (optional, defaults to the empty string) A space
+  separated list of arch-qualified 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.
+
+- **ReInstall:** (optional, defaults to the empty string) Same syntax of
+  Install. This field denotes a list of packages which are installed,
+  but should be reinstalled again e.g. because files shipped by that
+  package were removed or corrupted accidentally, usually requested via
+  an APT `install` request with the `--reinstall` flag.
+
+The following **preference fields** are supported in request stanzas:
+
+- **Planer:** (optional, defaults to the empty string) a purely
+  informational string specifying to which planer this request was send
+  initially.
+
+
+#### 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:
+
+- The fields Package, Version, Architecture (all mandatory) and
+  Multi-Arch, Pre-Depends, Depends, Conflicts, Breaks, Essential
+  (optional) as they are contained in the dpkg database (see the manpage
+  `dpkg-query (1)`).
+
+- **Status:** (optional, defaults to `uninstalled`). Allowed values are
+  the "package status" names as listed in `dpkg-query (1)` and visible
+  e.g. in the dpkg database as the second value in the space separated
+  list of values in the Status field there. In other words: Neither
+  desired action nor error flags are present in this field in EIPP!
+
+- **APT-ID:** (mandatory). Unique package identifier, according to APT.
+
+
+### Answer
+
+An answer from the external planer to APT is either a *solution* or an
+*error*.
+
+The following invariant on **exit codes** must hold true. When the
+external planer 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 planer is *unable to find a solution* (and is 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 planer
+crash with no meaningful error about dependency resolution to convey to
+the user.
+
+
+#### Solution
+
+  TODO
+
+
+#### 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 planer
+  error.  Message fields might be multi-line, like the Description field
+  in the dpkg database. The first line conveys a short message, which
+  can be explained in more details using subsequent lines.
+
+
+### Progress
+
+During dependency solving, an external planer may send progress
+information to APT using **progress stanzas**. A progress stanza starts
+with the Progress field and might contain the following fields:
+
+- **Progress:** (mandatory). The value of this field is a date and time
+  timestamp, in RFC 2822 format. The timestamp provides a time
+  annotation for the progress report.
+
+- **Percentage:** (optional). An integer from 0 to 100, representing the
+  completion of the installation planning process, as declared by the
+  planer.
+
+- **Message:** (optional). A textual message, meant to be read by the
+  APT user, telling what is going on within the installation planer
+  (e.g. the current phase of planning, as declared by the planer).
+
+
+# Future extensions
+
+Potential future extensions to this protocol are to be discussed on
+deity@lists.debian.org.
diff --git a/test/integration/framework b/test/integration/framework
index 3f7101170..6276ae825 100644
--- a/test/integration/framework
+++ b/test/integration/framework
@@ -302,10 +302,12 @@ setupenvironment() {
 	mkdir -p usr/lib/apt
 	ln -s "${METHODSDIR}" usr/lib/apt/methods
 	if [ "$BUILDDIRECTORY" = "$LIBRARYPATH" ]; then
-		mkdir -p usr/lib/apt/solvers
+		mkdir -p usr/lib/apt/solvers usr/lib/apt/planers
 		ln -s "${BUILDDIRECTORY}/apt-dump-solver" usr/lib/apt/solvers/dump
+		ln -s "${BUILDDIRECTORY}/apt-dump-solver" usr/lib/apt/planers/dump
 		ln -s "${BUILDDIRECTORY}/apt-internal-solver" usr/lib/apt/solvers/apt
 		echo "Dir::Bin::Solvers \"${TMPWORKINGDIRECTORY}/rootdir/usr/lib/apt/solvers\";" > etc/apt/apt.conf.d/externalsolver.conf
+		echo "Dir::Bin::Planers \"${TMPWORKINGDIRECTORY}/rootdir/usr/lib/apt/planers\";" > etc/apt/apt.conf.d/externalplaner.conf
 	fi
         # use the autoremove from the BUILDDIRECTORY if its there, otherwise
         # system