JigsawServices

From APIDesign

Jigsaw is a project that modularizes Java core parts with the plan to set an example up the modularity should be done in Java. NetBeans IDE needs to care about Jigsaw, as NetBeans IDE is the primary tooling for OpenJDK. I am interested in the project due to another reason as well: dependencies in modular systems are subject to NP-Complete problems: The LibraryReExportIsNPComplete and for example OSGi suffers from that. It would be amazing, if we could learn from past mistakes and come up with a system of [[dependencies] that is not inherently NP-Complete.

One of the primary suspects for the complexity were range dependencies, but we know now that it is not the real problem. A threat of NP-Completeness still remains in the form of services. Here is a simple sketch showing why system with service dependencies can solve 3SAT. The full proof would be similar to LibraryReExportIsNPComplete. Imagine a module which requires two services:

module base {
  requires service a;
  requires service b;
}

and let's imagine that there are two modules providing service a named A1, 'A2 and there are two modules providing service b named B1, B2. We need to select at least one of the A modules and one of the B modules. But the problem is that while resolving these modules, they may render themselves as mutually incompatible. Imagine:

1. Try A1 - good, it resolves
2. Try A2 - no it does not resolve, conflicts with some dependencies of A1
3. Try B1 - no it does not resolve, conflicts with some dependencies of A1
4. Try B2 - no it does not resolve, conflicts with some dependencies of A2

Time to give up? No, not at all. Let's backtrack and instead of using A1 let's try A2:

1. Try A2 - good, it resolves (as A1 is disabled)
2. Try B1 - good, it resolves now (as A1 is disabled and A2 has more suitable dependencies)

The fact that we have multiple choices and we need to try them in various combinations makes the whole system NP-Complete (as that is basically the 3SAT problem). How could we eliminate NP-Completeness?