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;
+}
+									/*}}}*/