Support 'osgi' resolver as an alternative to P2 resolver

[laeubi]

Currently tycho uses a split approach:

1. It resolves dependencies using P2 to get the order of projects and there preliminary requirements
2. It starts an OSGi resolve process to determine the package wires to enable classpath restrictions and find some problems that P2 might not detect

This seems a bit strange and as we effectively want to build osgi bundles we probably could simply merge these two steps into one:

http://docs.osgi.org/specification/osgi.core/7.0.0/service.resolver.html

[mickaelistria]

Many modules (features, p2 repos...) are not OSGi bundles and do not need/won't work with the OSGi resolution. The OSGi resolution could be bound to classpath computation, as a later step in the initialize phase for the module, like what you changed recently.

[laeubi]

Many modules (features, p2 repos...) are not OSGi bundles and do not need/won't work with the OSGi resolution.

The OSGi resolver could work with that as well as effectively all of these are just items having some requirements and providing some capabilities. Actually P2 uses this concept as well.

One advantage is, that you can do resolve things dynamically later on.

[mickaelistria]

If you can basically replace p2 with OSGi resolver, why not. But I believe that p2 is by design a better fit for the issue of provisioning because it is understanding SAT problems which I don't believe OSGi resolver can do. I'm afraid there are some restrictions to OSGi compiler that wouldn't make it work for the more general case of p2.

[laeubi]

because it is understanding SAT problems which I don't believe OSGi resolver can do

Why do you think so? Quoted from the spec:

Resolving transitive dependencies is a non-trivial process that requires careful design to achieve the required performance since the underlying problem is NP-complete.

Even though the spec don't mentioned SAT it actually is a SAT problem the resolver must solve. And given that P2 do not support e.g. use-clause and alike it seems the OSGi-resolve can even solve more problems?

If you can basically replace p2 with OSGi resolver, why not.

That's the purpose of this, to find what might not be replaceable (I don't have any case) but nothing that will happen right now, just one idea to make tycho even more flexible ...

[mickaelistria]

I can't tell for sure. I think @tjwatson expressed some concern about the possibility of replacing most of p2 by the OSGi resolver recently. I'm not sure about the details though; however I would trust whatever Thomas suggests is possible/profitable or not here.

[tjwatson]

Michael is likely remembering my recent comment in p2 bug 525368 Comment 11

For literally decades, we have been tackling the mp-hard problem in the OSGi resolver impl. Long ago we thought the SAT solver was a good fit to solve the problem but many people from the past (including Pascal Rapicult with some help from SAT4J maintainer Daniel Le Berre and more recently by Todor Boev in the bug mentioned above) have looked at how to encode the OSGi uses directive concept into the necessary boolean constraint "equation" to make it fit into a SAT4J solution. So far the issue has proven to be complex and may technically not be possible, but I am no expert on manipulating the data for usage of a SAT solver.

My main concern with replacing p2 resolver with the OSGi resolver is that the OSGi resolver still gets into situations that throw it into what seems like an endless attempt to find a solution. The framework eventual gives up and times out if this occurs and it tries to reduce the problem by resolver "smaller" groups of bundles. My worry is that for provisioning the pool of bundles being presented to the resolution problem can potentially be much greater than in the OSGi Framework case where we only have a finite set of bundles installed to resolve.

[laeubi]

@tjwatson thanks for the insight. Maybe both approaches could profit from each others? e.g. I can think of a two step process where first (using sat4j) a first solution is derived that for example include duplicate providers for a package, and then the part in OSGi resolver could kick in (what does it use to solve this problem?) could fine tune the result to take additional constraints into consideration?

If this then is all packed into one ResolverService implementation (that probably could even work without OSGi running!) that both the P2+Equinox resolver use under the hood would speedup start-up times and makes p2 resolving more reliable without the effort of having two distinct (maybe diverging) implementation approaches?