JigsawServices

From APIDesign

Revision as of 09:11, 21 June 2012

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.

NP-Complete Services

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 nptest {
  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 - it does not resolve, conflicts with some dependencies of A1
3. Try B1 - it does not resolve, conflicts with some dependencies of A1
4. Try B2 - it does not resolve, conflicts with some dependencies of A1

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?

Optional Services

The "solution" to eliminate the NP-Complete nature of the problem is to use only optional services. Let's modify the previous example a bit:

module nptest {
  requires optional service a;
  requires optional service b;
}

this new definition instructs the system to try hard to provide implementations for services a and b, but if there are none, it is not a problem. That is why let simulate the previous resolution algorithm with modules A1, A2, B1 and B2 in the new scenario:

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

is not this the same? Well, yes, the computation is the same. But the result is different. Instead of aborting the execution because not all dependencies of nptest module can be satisfied, Jigsaw executes the system with nptest and A1 modules enabled. The module nptest claimed it can live without service b, so it needs to deal with it somehow during execution.

Trivial and NP-Completeness is gone.

Providing a Hint

Of course, some may argue and everyone can see that there is a better (in sense of richer) configuration to satisfy the previous example. If the Jigsaw runs with nptest, A2 and B1 the pleasure of execution is likely to be higher. What can we do to help Jigsaw to prefer such configuration and still not fall into NP-Complete trap?

There should be a way to provide hints. A developer (or a deployer) of the application should be able to tell Jigsaw to try module A2 when it seeks for provider of service a first. And that is all. Heuréka!