If package A replaces virtual package B, and B is provided by A, then package A upgrades will fail. The upgrade will fail since the old version of package A is removed twice: first (incorrectly) on pkg_remove_installed_replacees, then during the upgrade operation. Package A should not be added to the replacees list. Problem is present in both solvers (internal and libsolv).
Actually this failure is only present on the internal solver. The libsolv backend does it's own resolution Provides/Replaces/Conflicts.
fixed by 7885da3974de2df1baba220200d55920fb530e25