Hello,
With APT::Get::Build-Dep-Automatic "apt-get autoremove" does not
remove packages pulled in by provides. The extended_states file gets a
wrong entry for the virtual package, instead of the real one.

(SID)root:/# DEBIAN_FRONTEND=noninteractive  apt-get build-dep exim4
Reading package lists... Done
Building dependency tree
Reading state information... Done
Note, selecting libmysqlclient-dev instead of libmysqlclient15-dev
[...]
Setting up libmysqlclient-dev (5.1.40-1) ...
[...]
(SID)root:/# grep -A1 mysql /var/lib/apt/extended_states
Package: mysql-common
Auto-Installed: 1
--
Package: libaprutil1-dbd-mysql
Auto-Installed: 1
--
Package: libmysqlclient16
Auto-Installed: 1
--
Package: libmysqlclient15-dev
Auto-Installed: 1
[...]
SID)root:/# dpkg -l 'libmysqlclient*dev' | grep ^ii
ii  libmysqlclient-dev 5.1.40-1  MySQL database development files
(SID)root:/# DEBIAN_FRONTEND=noninteractive  apt-get  --purge  autoremove
[...]
(SID)root:/# dpkg -l 'libmysqlclient*dev' | grep ^ii
ii  libmysqlclient-dev 5.1.40-1    MySQL database development files
(SID)root:/# grep -A1 mysql /var/lib/apt/extended_states
Package: mysql-common
Auto-Installed: 1
--
Package: libaprutil1-dbd-mysql
Auto-Installed: 1
--
Package: libmysqlclient16
Auto-Installed: 1

cu andreas

Control: found -1 2.6.1
to build-dep. For instance, after the upgrade to bookworm and
"apt autoremove --purge".

joooj:~> aptitude why gcc-8-base
i   devscripts   Recommends pristine-tar
i A pristine-tar Depends    pbzip2
i A pbzip2       Depends    libgcc1 (>= 1:3.0)
i A libgcc1      Depends    gcc-8-base (= 8.3.0-6)

even though libgcc1 is no longer in the archive. It is actually
provided by libgcc-s1 (which does not depend on gcc-8-base):

joooj:~> dpkg -s libgcc-s1
Package: libgcc-s1
[...]
Version: 12.2.0-14
Replaces: libgcc1 (<< 1:10)
Provides: libgcc1 (= 1:12.2.0-14)
[...]

So, as it was installed automatically ("A"), it should have been
removed by "apt autoremove".