It would be nice (and a major improvement) to have portage offload the dependency calculation to a solver compatible with the CUDF format http://www.mancoosi.org/cudf/
Is the format capable of expressing subslot-induced rebuilds?
No, not directly. Maybe portage can scan the list of the packages to be installed and add to that list the packages to be rebuilt
FWIW, https://wiki.eclipse.org/Equinox/p2/CUDFResolver at least says "The input and output format is CUDF. This format has been designed by the Mancoosi European project to foster improvements in dependency resolution solvers. Supporting a different format can be done trivially, just contact us."
I went on and read the CUDF specification  and I do not see right away what kind of transformation we could do to be able to handle everything related to USE flags (e.g. user defined toggles, use dependencies), let's take use dependencies:
There is an entry called 'provides' that indicate what a package provides once installed. Which looks like the only thing that can fit with use flags, one maybe can do something like this
provides: www-client/firefox-[flag1] www-client/firefox-[flag2] ...
So basically to prepend the flag name with the package name to make the name unique and referenceable.
A few issues:
- It looks like we cannot write dependencies based on stuff written in "provides"
- Even if we could, so other packages can refer to www-client/firefox-[flag_i] in their dependency string to express a use dependency. But afaik once the package is installed it provides ALL of the things listed there. So if another package conflicts with a specific flag in `www-client/firefox` (a possible use dependency). Then the package simply cannot be installed at all.
Or maybe I didn't spend enough time thinking to figure out how to map Gentoo's dependency problem to CUDF.
CUDF seems to fit well only with binary distributions, it probably needs the attention of Gentoo devs to think this through and make an extension proposal to the format, so we can use it. Maybe I will be able to contribute to that, in the near future.
(In reply to Adel KARA SLIMANE from comment #4)
> I went on and read the CUDF specification  and I do not see right away
> what kind of transformation we could do to be able to handle everything
> related to USE flags (e.g. user defined toggles, use dependencies), let's
> take use dependencies:
> There is an entry called 'provides' that indicate what a package provides
> once installed. Which looks like the only thing that can fit with use flags,
> one maybe can do something like this
> package: www-client/firefox
> provides: www-client/firefox-[flag1] www-client/firefox-[flag2] ...
> So basically to prepend the flag name with the package name to make the name
> unique and referenceable.
> A few issues:
> - It looks like we cannot write dependencies based on stuff written in
depends: solar-collector | huge-battery
>  https://www.mancoosi.org/reports/tr3.pdf