From c7e368aafe099dcd966cf5994ae7fb418d268278 Mon Sep 17 00:00:00 2001
From: David Kalnischkies <david@kalnischkies.de>
Date: Sat, 28 Aug 2021 15:55:09 +0200
Subject: Stop autoremover from endlessly exploring cyclic providers

fullyExplored is needed to keep track of having explored all providers
of a package name, while Marked is tracking if we have explored a given
real package (along its chosen version), so we should stop MarkPackage
from exploring a (real) package if it is marked and let fullyExplored
only guard the looping over the individual dependencies.

The testcase is deceptively simple, but in practice only an ecosystem
like rust who makes heavy use of cyclic dependency relations intermixed
with versioned provides actually triggers this as seen by the buggy code
being in use for four months in Debian and Ubuntu development releases.
(easier to trigger if most packages are marked manual installed)

Note that the testcase is successful already due to the earlier changes
as we exit the recursion eventually and all packages are marked as they
need to be already, but this fix does work standalone as well.

Closes: #992993
---
 apt-pkg/depcache.cc                            |  2 +-
 test/integration/test-bug-992993-marked-cycles | 30 ++++++++++++++++++++++++++
 2 files changed, 31 insertions(+), 1 deletion(-)
 create mode 100755 test/integration/test-bug-992993-marked-cycles

diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index 76e8f5357..7c14d0e05 100644
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -2240,7 +2240,7 @@ static bool MarkPackage(pkgCache::PkgIterator const &Pkg,
 			std::unique_ptr<APT::CacheFilter::Matcher> &IsAVersionedKernelPackage,
 			std::unique_ptr<APT::CacheFilter::Matcher> &IsProtectedKernelPackage)
 {
-   if (Ver.end() || (fullyExplored[Pkg->ID] && PkgState[Pkg->ID].Marked))
+   if (Ver.end() || PkgState[Pkg->ID].Marked)
       return true;
 
    if (IsPkgInBoringState(Pkg, PkgState))
diff --git a/test/integration/test-bug-992993-marked-cycles b/test/integration/test-bug-992993-marked-cycles
new file mode 100755
index 000000000..a569040cf
--- /dev/null
+++ b/test/integration/test-bug-992993-marked-cycles
@@ -0,0 +1,30 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+setupenvironment
+configarchitecture 'amd64'
+
+insertinstalledpackage 'librust-nom-4-dev' 'all' '4.2.3-3' 'Provides: librust-nom-dev (= 4.2.3-3)'
+insertinstalledpackage 'librust-nom-dev' 'all' '5.0.1-4' 'Depends: librust-nom+default-dev (= 5.0.1-4)'
+insertinstalledpackage 'librust-nom+default-dev ' 'all' '5.0.1-4' 'Depends: librust-nom-dev (= 5.0.1-4)'
+insertinstalledpackage 'librust-nom-4+std-dev' 'all' '4.2.3-3' 'Provides: librust-nom+default-dev (= 4.2.3-3)'
+
+insertinstalledpackage 'foo' 'all' '1' 'Depends: librust-nom-4-dev, librust-nom-dev, librust-nom-4+std-dev'
+
+for AUTO in '' 'librust-nom-4-dev' 'librust*' 'foo' '.*'; do
+	msgmsg 'Running test with these packages marked auto:' "$AUTO"
+	testsuccess aptmark manual '.*'
+	if [ -n "$AUTO" ]; then
+		testsuccess aptmark auto "$AUTO"
+	fi
+
+	testsuccess aptget check
+	testsuccess aptget autoremove -s
+
+	testsuccess aptget upgrade
+	testsuccess aptget full-upgrade
+
+	testsuccess apt show foo
+done
-- 
cgit v1.2.3-70-g09d2