I did say you could get pretty far, not that you could solve the problem.
The closest I’ve seen to solving the problem, although not cross-platform, is RPM. So let me write a bit about prior art, for inspiration:
RPM packages have “virtual provides”, a full-fledged variant of Provides-Dist, which allow packages to claim multiple names. Traditionally, parentheses are used for alternate namespaces. For example, you can install pip with:
# dnf install python3-pip # (actual package name)
# dnf install python3.10-pip # (alias)
# sudo dnf install 'python3dist(pip)' # (PyPI name)
# sudo dnf install /usr/bin/pip # (Files are virtual provides too)
And you can also do:
# sudo dnf install pkgconfig(lapack) # (pkgconfig name for a native library)
# sudo dnf install crate(starship) # (Rust crate name)
Some of these aren’t human-friendly, but they do make automatic dependency generators for the various ecosystems relatively easy. At least for the ecosystems that can be automated easily :)
Well, there’s one other crucial feature: arbitrary expressions in requirements, to express that you need “this or that”. There’s and/or for that, but turns out you also need if, with, unless: rpm.org - Boolean Dependencies
The resolver and the package indexes support that.
Add that to a cross-platform system, and, done!
Or start small and leave the hairy cases unsolved for now.
I didn’t know about this issue, but FWIW, Honza Horák happens to be my manager.