Increase recursion limits from 100 to 3000

If you install dpkg on an empty status file with all recommends and
suggests apt wants to install 4000+ packages. The deepest chain
seemingly being 236 steps long. And dpkg isn't even the worst (~259).

That is a problem as libapt has a hardcoded recursion limit for
MarkInstall and friends … set to 100. We are saved by the fact that
chains without suggests are much shorter (dpkg has 5, max seems ~43),
but I ignored Conflicts in these chains, which typically trigger
upgrades, so if two of the worst are chained together we suddenly get
dangerously close to the limit still.

So, lets just increase the limit into oblivion as it is really just a
safety measure we should not be running into to begin with. MarkPackage
was running years without it after all. 3000 is picked as a nice number
as any other and because it is roughly the half of the stack crashs I
saw previously in this branch.

3 files changed, 78 insertions, 5 deletions

diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index 7c14d0e05..460fb296e 100644
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -894,8 +894,8 @@ static char const* PrintMode(char const mode)
 static bool IsModeChangeOk(pkgDepCache &Cache, pkgDepCache::ModeList const mode, pkgCache::PkgIterator const &Pkg,
 			   unsigned long const Depth, bool const FromUser, bool const DebugMarker)
 {
-   // we are not trying to hard…
-   if (unlikely(Depth > 100))
+   // we are not trying too hard…
+   if (unlikely(Depth > 3000))
       return false;
 
    // general sanity
@@ -2249,8 +2249,8 @@ static bool MarkPackage(pkgCache::PkgIterator const &Pkg,
       return true;
    }
 
-   // we are not trying to hard…
-   if (unlikely(Depth > 100))
+   // we are not trying too hard…
+   if (unlikely(Depth > 3000))
       return false;
 
    PkgState[Pkg->ID].Marked = true;
diff --git a/test/interactive-helper/CMakeLists.txt b/test/interactive-helper/CMakeLists.txt
index 565474afd..fff47300b 100644
--- a/test/interactive-helper/CMakeLists.txt
+++ b/test/interactive-helper/CMakeLists.txt
@@ -11,7 +11,8 @@ target_link_libraries(aptdropprivs apt-pkg)
 add_executable(test_fileutl test_fileutl.cc)
 target_link_libraries(test_fileutl apt-pkg)
 add_executable(createdeb-cve-2020-27350 createdeb-cve-2020-27350.cc)
-
+add_executable(longest-dependency-chain longest-dependency-chain.cc)
+target_link_libraries(longest-dependency-chain apt-pkg apt-private)
 
 add_library(noprofile SHARED libnoprofile.c)
 target_link_libraries(noprofile ${CMAKE_DL_LIBS})
diff --git a/test/interactive-helper/longest-dependency-chain.cc b/test/interactive-helper/longest-dependency-chain.cc
new file mode 100644
index 000000000..3da722a5b
--- /dev/null
+++ b/test/interactive-helper/longest-dependency-chain.cc
@@ -0,0 +1,72 @@
+#include <config.h>
+
+#include <apt-pkg/cachefile.h>
+#include <apt-pkg/pkgsystem.h>
+#include <apt-private/private-cmndline.h>
+
+#include <iostream>
+
+static bool ShowHelp(CommandLine &)					/*{{{*/
+{
+   std::cout <<
+    "Usage: longest-dependecy-chain [options]\n"
+      "\n"
+      "Tries to find the longest dependency chain available in the data\n"
+      "assuming an empty status file, no conflicts, all or-group members\n"
+      "are followed and discovery order matters. In other words:\n"
+      "The found length might very well be too short and not realistic.\n"
+      "It is also not implemented very intelligently, so it runs forever.\n";
+   return true;
+}
+									/*}}}*/
+static std::vector<aptDispatchWithHelp> GetCommands()			/*{{{*/
+{
+   return {
+      {nullptr, nullptr, nullptr}
+   };
+}
+									/*}}}*/
+static size_t findLongestInstallChain(pkgDepCache &Cache, pkgCache::PkgIterator const &Pkg, std::vector<bool> &installed)/*{{{*/
+{
+   if (installed[Pkg->ID])
+      return 0;
+   installed[Pkg->ID] = true;
+
+   auto const Ver = Cache.GetCandidateVersion(Pkg);
+   if (Ver.end())
+      return 0;
+
+   size_t maxdepth = 0;
+   for (auto D = Ver.DependsList(); not D.end(); ++D)
+      if (D->Type == pkgCache::Dep::Depends ||
+	    D->Type == pkgCache::Dep::PreDepends ||
+	    D->Type == pkgCache::Dep::Recommends ||
+	    D->Type == pkgCache::Dep::Suggests)
+	 maxdepth = std::max(maxdepth, findLongestInstallChain(Cache, D.TargetPkg(), installed));
+   return maxdepth + 1;
+}
+									/*}}}*/
+int main(int argc,const char *argv[])					/*{{{*/
+{
+   CommandLine CmdL;
+   auto const Cmds = ParseCommandLine(CmdL, APT_CMD::APT_SORTPKG, &_config, &_system, argc, argv, &ShowHelp, &GetCommands);
+   _config->Set("dir::state::status", "/dev/null");
+
+   pkgCacheFile CacheFile;
+   CacheFile.InhibitActionGroups(true);
+   pkgDepCache * const Cache = CacheFile.GetDepCache();
+   if (unlikely(Cache == nullptr))
+      return DispatchCommandLine(CmdL, Cmds);
+
+   size_t maxdepth = 0;
+   for (auto P = Cache->PkgBegin(); not P.end(); ++P)
+   {
+      std::vector<bool> installed(Cache->Head().PackageCount, false);
+      auto const depth = findLongestInstallChain(*Cache, P, installed);
+      std::cout << depth << ' ' << P.FullName() << '\n';
+      maxdepth = std::max(maxdepth, depth);
+   }
+
+   return 0;
+}
+									/*}}}*/