apt.install(): a lone `Provides:` match silently outranks a real, identically-named package (e.g. `libavcodec-extra61` chosen over `libavcodec61`)

[wiest]

Summary

_resolve_package() in apt/private/apt_dep_resolver.bzl checks a name against the
virtual-package (Provides:) table before ever checking whether a real package with
that exact name exists. When exactly one other package provides the requested name, it's
returned immediately (if len(candidates) == 1: return (candidates[0], warning)) — even
when a real package of that literal name also exists in the same suite.

This bites any dependency on a package that Debian also ships an "-extra"/alternate build
of, since those bundles declare Provides: <base> (= <same version>) +
Conflicts: <base> precisely so a human can opt in to the alternative — not so a
resolver silently substitutes it for an ordinary dependency on the base package.

Reproduction

Debian trixie, ffmpeg (7:7.1.3-0+deb13u1). Its actual Depends: (from the Packages
index) asks for the plain packages, no | alternatives:

Depends: libavcodec61 (>= 7:7.1), libavdevice61 (>= 7:7.0), libavfilter10 (>= 7:7.0),
 libavformat61 (>= 7:7.0), libavutil59 (>= 7:7.1), libc6 (>= 2.35),
 libplacebo349 (>= 7.349.0), libpostproc58 (>= 7:7.0), libsdl2-2.0-0 (>= 2.0.12),
 libswresample5 (>= 7:7.0), libswscale8 (>= 7:7.0)

libavcodec-extra61 (same source, same version) declares:

Provides: libavcodec61 (= 7:7.1.3-0+deb13u1)
Conflicts: libavcodec61

apt.sources_list(
    types = ["deb"],
    uris = ["https://snapshot-cloudflare.debian.org/archive/debian/20260223T142455Z"],
    suites = ["trixie"],
    components = ["main"],
    architectures = ["amd64"],
)
apt.install(
    dependency_set = "repro",
    packages = ["ffmpeg"],
    suites = ["trixie"],
)
use_repo(apt, "repro")

bazel build @repro//:flat resolves libavcodec61 → libavcodec-extra61,
libavfilter10 → libavfilter-extra10, libsdl2-2.0-0 → libsdl2-compat, and pulls in
a large, unwanted closure (tesseract/OCR, libblas/liblapack, pipewire, ...) instead of the
package ffmpeg actually depends on. The resulting ffmpeg binary fails at load time
(error while loading shared libraries: libblas.so.3: cannot open shared object file)
because libavfilter-extra10's dependency chain needs libblas3/liblapack3, which hits
a separate, already-known gap (#76) — but the root problem here is that ffmpeg should
never have been linked against the -extra closure in the first place.

Reproduced identically on both 0.8.0 and 0.9.4/0.9.5 (the resolver logic in
apt_dep_resolver.bzl is unchanged across 0.9.4 → 0.9.5), so this isn't new in the
bzlmod rewrite — it's just newly visible whenever a lockfile gets regenerated against a
snapshot where the identical-version Provides+Conflicts pairing exists.

Root cause

# apt/private/apt_dep_resolver.bzl
def _resolve_package(state, name, version, arch, suites = None):
    virtual_packages_for_arch = state.repository.virtual_packages(name = name, arch = arch, suites = suites)
    virtual_packages_for_all = state.repository.virtual_packages(name = name, arch = "all", suites = suites)
    virtual_packages = virtual_packages_for_arch + virtual_packages_for_all

    candidates = [package for (package, provided_version) in virtual_packages if ...]

    if len(candidates) == 1:
        return (candidates[0], warning)   # <-- never checks for a real package literally named `name`

virtual_packages(name=name, ...) only returns packages whose Provides: mentions
name — a real package doesn't register itself there. So when exactly one other package
provides name, it wins outright, regardless of whether name is also a real package.
Real apt/dpkg never do this: Provides is for genuinely virtual names
(mail-transport-agent, www-browser, ...) with no package of their own; a same-named
real package always wins over one that merely provides that name.

Suggested fix (patch attached, tested)

Only take the len(candidates) == 1 shortcut when there is no real package literally
named name; otherwise fall through to the existing real-package lookup further down in
the same function (which already runs state.repository.package_versions(name = name, ...)).

     if len(candidates) == 1:
-        return (candidates[0], warning)
+        if candidates[0]["Package"] != name and (
+            state.repository.package_versions(name = name, arch = arch, suites = suites) or
+            state.repository.package_versions(name = name, arch = "all", suites = suites)
+        ):
+            pass  # fall through to the real-package lookup below
+        else:
+            return (candidates[0], warning)

Verified against the ffmpeg/trixie repro above: with the patch, libavcodec61,
libavfilter10, libsdl2-2.0-0 resolve correctly, the -extra/tesseract/pipewire
closure disappears entirely, and the built ffmpeg runs.

Happy to open this as a PR if useful — currently carrying it as a
single_version_override patch in our own MODULE.bazel in the meantime.

Related but distinct

#76 (open) is about the same symptom (libblas.so.3/liblapack.so.3 "cannot open
shared object file") but a different cause — rules_distroless not running .deb
postinst/update-alternatives. That gap is real and separate; this issue is about why
libblas3/liblapack3 end up in the closure of a plain ffmpeg install at all when
they shouldn't.