Introduce apt why, apt why-not

These are implemented somewhat differently from aptitudes
why and why-not commands: They produce the actual solver
trace for why a particular decision has been taken.

For the why-not case, we need to explicitly discover our
specified package, as if nothing else depends on it in
our graph, it would otherwise always be undiscovered and
conflicts not detected (see e.g. level-3 in the test).

6 files changed, 123 insertions, 0 deletions

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index 620156ac3..abc0af314 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -1267,3 +1267,23 @@ bool APT::Solver::ToDepCache(pkgDepCache &depcache) const
    }
    return true;
 }
+
+// Command-line
+std::string APT::Solver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIterator pkg, bool decision)
+{
+   APT::Solver solver(cache.GetCache(), cache.GetPolicy(), EDSP::Request::Flags(0));
+   // In case nothing has a positive dependency on pkg it may not actually be discovered in a `why-not`
+   // scenario, so make sure we discover it explicitly.
+   solver.Discover(Var(pkg));
+   if (not solver.FromDepCache(cache) || not solver.Solve())
+      return "";
+   std::unordered_set<Var> seen;
+   std::string buf;
+   if (solver[Var(pkg)].decision == Decision::NONE)
+      return strprintf(buf, "%s is undecided\n", pkg.FullName().c_str()), buf;
+   if (decision && solver[Var(pkg)].decision != Decision::MUST)
+      return strprintf(buf, "%s is not actually marked for install\n", pkg.FullName().c_str()), buf;
+   if (not decision && solver[Var(pkg)].decision == Decision::MUST)
+      return strprintf(buf, "%s is actually marked for install\n", pkg.FullName().c_str()), buf;
+   return solver.LongWhyStr(Var(pkg), decision, solver[Var(pkg)].reason, "", seen);
+}
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index 6810df426..43f6ec3a7 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -316,6 +316,9 @@ class Solver
     * \param seen A set of seen objects such that the output does not repeat itself (not for safety, it is acyclic)
     */
    std::string LongWhyStr(Var var, bool decision, const Clause *rclause, std::string prefix, std::unordered_set<Var> &seen) const;
+
+   // \brief Temporary internal API with external linkage for the `apt why` and `apt why-not` commands.
+   APT_PUBLIC static std::string InternalCliWhy(pkgDepCache &depcache, pkgCache::PkgIterator Pkg, bool decision);
 };
 
 }; // namespace APT
diff --git a/cmdline/apt.cc b/cmdline/apt.cc
index af8a95fa5..a876085ce 100644
--- a/cmdline/apt.cc
+++ b/cmdline/apt.cc
@@ -16,6 +16,7 @@
 #include <apt-pkg/error.h>
 #include <apt-pkg/init.h>
 #include <apt-pkg/pkgsystem.h>
+#include <apt-pkg/solver3.h>
 #include <apt-pkg/strutl.h>
 
 #include <apt-private/private-cmndline.h>
@@ -53,6 +54,20 @@ static bool ShowHelp(CommandLine &)					/*{{{*/
    return true;
 }
 									/*}}}*/
+
+static bool DoWhy(CommandLine &CmdL) /*{{{*/
+{
+   pkgCacheFile CacheFile;
+   APT::PackageList pkgset = APT::PackageList::FromCommandLine(CacheFile, CmdL.FileList + 1);
+   bool const decision = strcmp(CmdL.FileList[0], "why") == 0;
+   if (pkgset.size() != 1)
+      return _error->PendingError() ? false : _error->Error("Only a single argument is supported at this time.");
+   if (unlikely(not CacheFile.BuildDepCache()))
+      return false;
+   for (auto pkg : pkgset)
+      std::cout << APT::Solver::InternalCliWhy(CacheFile, pkg, decision) << std::flush;
+   return not _error->PendingError();
+}
 static std::vector<aptDispatchWithHelp> GetCommands()			/*{{{*/
 {
    // advanced commands are left undocumented on purpose
@@ -81,6 +96,8 @@ static std::vector<aptDispatchWithHelp> GetCommands()			/*{{{*/
       {"modernize-sources", &ModernizeSources, _("modernize .list files to .sources files")},
       {"moo", &DoMoo, nullptr},
       {"satisfy", &DoBuildDep, _("satisfy dependency strings")},
+      {"why", &DoWhy, _("produce a reason trace for the current state of the package")},
+      {"why-not", &DoWhy, _("produce a reason trace for the current state of the package")},
 
       // for compat with muscle memory
       {"dist-upgrade", &DoDistUpgrade, nullptr},
diff --git a/debian/libapt-pkg7.0.symbols b/debian/libapt-pkg7.0.symbols
index abcd70e78..cb857b159 100644
--- a/debian/libapt-pkg7.0.symbols
+++ b/debian/libapt-pkg7.0.symbols
@@ -1320,6 +1320,7 @@ libapt-pkg.so.7.0 libapt-pkg7.0 #MINVER#
  (arch=ppc64el|c++)"GlobalError::InsertErrno(GlobalError::MsgType, char const*, char const*, char*&, int, unsigned long&)@APTPKG_7.0" 0.8.11.4
  (arch=armel armhf|c++)"RFC1123StrToTime(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, long long&)@APTPKG_7.0" 1.9.0
  (arch=armel armhf|c++)"TimeRFC1123[abi:cxx11](long long, bool)@APTPKG_7.0" 2.7.14
+ (c++)"APT::Solver::InternalCliWhy[abi:cxx11](pkgDepCache&, pkgCache::PkgIterator, bool)@APTPKG_7.0" 3.1.0~
 # Optional C++ standard library symbols
 # These are inlined libstdc++ symbols and not supposed to be part of our ABI
 # but we cannot stop stuff from linking against it, sigh.
diff --git a/doc/apt.8.xml b/doc/apt.8.xml
index 7af915e89..8dd1d019b 100644
--- a/doc/apt.8.xml
+++ b/doc/apt.8.xml
@@ -121,6 +121,17 @@
      </para></listitem>
      </varlistentry>
 
+     <varlistentry><term><option>why, why-not</option></term>
+     <listitem>
+      <para>These commands print the reasoning path from the solver. They are similar to the equivalent aptitude commands for many use cases, but are different in that they print the actual reason the solver picked rather than the potential strongest path.</para>
+      <para>The <option>why</option> command determines why an installed package is installed. This
+      provides reasonable feedback as to why an automatically installed package is installed; for a
+      manually installed package no other reason is given. If the package is not installed, no reason
+      can be determined.</para>
+      <para>The <option>why-not</option> command determines why a package was determined to not be installable. This
+      may not always yield a result, even if a package is uninstallable.</para>
+      <para>Both commands take a single argument, the name of a package.</para>
+     </listitem></varlistentry>
 
      <varlistentry><term><option>search</option> (&apt-cache;)</term>
      <listitem><para><option>search</option> can be used to search for the given
diff --git a/test/integration/test-apt-cli-why b/test/integration/test-apt-cli-why
new file mode 100755
index 000000000..8a4c94b30
--- /dev/null
+++ b/test/integration/test-apt-cli-why
@@ -0,0 +1,71 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+setupenvironment
+configarchitecture 'amd64'
+
+insertinstalledpackage 'root' 'all' '1' 'Depends: level-1'
+insertinstalledpackage 'level-1' 'all' '1' 'Depends: level-2'
+insertinstalledpackage 'level-2' 'all' '1' 'Depends: level-2'
+insertpackage 'unstable' 'other-level-2' 'all' '1' 'Conflicts: level-2
+Provides: level-2'
+insertpackage 'unstable' 'almost-level-2' 'all' '1' 'Conflicts: level-2'
+insertpackage 'unstable' 'level-3' 'all' '1' 'Conflicts: level-3'
+setupaptarchive
+
+testsuccess aptmark auto level-1 level-2
+
+
+testsuccessequal "level-2:amd64=1 is selected for install because:
+1. root:amd64 is selected for install
+2. root:amd64 Depends level-1
+3. level-1:amd64 Depends level-2
+   [selected level-1:amd64]
+For context, additional choices that could not be installed:
+* In level-1:amd64 Depends level-2:
+  - other-level-2:amd64=1 ->  | other-level-2:amd64
+    but none of the choices are installable:
+    - other-level-2:amd64 is not selected for install because:
+      1-3. level-2:amd64=1 is selected for install as above
+      4. other-level-2:amd64 Conflicts level-2
+      For context, additional choices that could not be installed:
+      * In level-1:amd64 Depends level-2:
+        - other-level-2:amd64=1 is not selected for install as above" apt why level-2
+
+
+testsuccessequal "other-level-2:amd64 is not actually marked for install" apt why other-level-2
+testsuccessequal "other-level-2:amd64 is not selected for install because:
+1. root:amd64 is selected for install
+2. root:amd64 Depends level-1
+3. level-1:amd64 Depends level-2
+   [selected level-2:amd64=1 for install]
+4. other-level-2:amd64 Conflicts level-2
+For context, additional choices that could not be installed:
+* In level-1:amd64 Depends level-2:
+  - other-level-2:amd64=1 ->  | other-level-2:amd64
+    but none of the choices are installable:
+    - other-level-2:amd64 is not selected for install as above" apt why-not other-level-2
+
+testsuccessequal "almost-level-2:amd64 is not actually marked for install" apt why almost-level-2
+testsuccessequal "almost-level-2:amd64 is not selected for install because:
+1. root:amd64 is selected for install
+2. root:amd64 Depends level-1
+3. level-1:amd64 Depends level-2
+   [selected level-2:amd64=1 for install]
+4. almost-level-2:amd64 Conflicts level-2
+   [selected level-2:amd64=1]
+For context, additional choices that could not be installed:
+* In level-1:amd64 Depends level-2:
+  - other-level-2:amd64=1 ->  | other-level-2:amd64
+    but none of the choices are installable:
+    - other-level-2:amd64 is not selected for install because:
+      1-3. level-2:amd64=1 is selected for install as above
+      4. other-level-2:amd64 Conflicts level-2
+      For context, additional choices that could not be installed:
+      * In level-1:amd64 Depends level-2:
+        - other-level-2:amd64=1 is not selected for install as above" apt why-not almost-level-2
+
+
+testsuccessequal "level-3:amd64 is undecided" apt why level-3