Arch Linux

I'd be fine with #1, something more to the effect of "No package found, but X provides Y"

This is mainly a %REPLACES% problem imho. Currently that is used with -Su only, however it would be useful with -S too.
If foo replaces bar, but foo doesn't provide bar (because foo is an other concept), and if you do a "pacman -S bar", you will simply won't be informed about the fact you should change your favourite bar package to foo.

Nagy, I think that's quite off topic, and it goes a bit in the opposite direction of what stonecrest is asking : not confusing the user by installing a package he didn't request.
And anyway, I don't think your example makes much sense. When a package replaces another, it usually provides it as well, otherwise it wouldn't really be a replacement, and it could break dependencies. And besides, the deprecated package has no reason to stay and is usually deleted from the repos, so you can't -S it.

Now about the report :
I'm fine with 1, but I'm afraid it's not possible for 3.1, which is in string freeze, right?
I could be fine with 2 too, but in this case, the user needs an easy way to get the list of providers.

Xavier, we probably interpret -S differently, in my definition it is primarily a package _upgrade_ (not package adding); and %REPLACES% can define tricky upgrades.

Let me go back to stonecrest's example:
He has scrollkeeper installed, which is officially replaced by rarian.

Case 1. He wants to _upgrade_ scrollkeeper, but now that is a provision only. If rarian doesn't conflict with scrollkeeper (can happen), the old scrollkeeper won't be removed so will become a spam.

You said, "not confusing the user by installing a package he didn't request.". I agree here, so I suggest this: "rarian replaces scrollkeeper. Do you want to replace scrollkeeper with rarian? [Y/n]", so do the same as with -Su.

"And anyway, I don't think your example makes much sense."
Imagine the following example: Your distro makes a radical change, for example foo=dpkg and bar=pacman (I know, that this is a very bad example, replace pacman; but I hope, you understand what I want to say); that's why I wrote foo is an other concept, so that is not "compatible" with bar, but an _alternative_.

Case 2. If user wants to _add_ scrollkeeper then I also vote for no-autoresolve, just give a warning, as stonecrest suggested.

Actually, my example was case 2. I wasn't upgrading scrollkeeper, I was installing it. And indeed, I think installing a provide is _MUCH_ more common than upgrading one. Because when you upgrade, you typically just do a -Su; how often do you do a -S with the package name to upgrade it?

I don't know that the two cases necessarily have to be handled differently, I'd personally be okay with the same warning in both cases.

I agree with stonecrest.

Attaching a patch that does #1 when there is just one provider, and #2 when there are multiple providers.

Due to the string change, this has to wait until 3.1.1, but I would guess it is good to apply.