JigsawServices

From APIDesign

Dependencies in modular systems are subject to NP-Complete problems: 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 for Jigsaw that is not inherently NP-Complete.

Here are slides from my 2012 presentation on this topic.

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 as the previous case? 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 selects nptest, A2 and B1 modules 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. Here is the resolution example:

1. Try A2 - We got a hint to try A2 first when somebody needs implementation of service a. It resolves (as A1 is disabled)
2. Try B1 - good, it resolves now (as A1 is disabled and A2 has more suitable dependencies)

And that is all. Useful and simple to resolve dependency system for Java modularity has just been born. Heuréka!

Language Change

So the problematic case is 'requires service constraint. We need to avoid its current form and always require a hint. Here is my proposal how to do it:

module M1 {
  requires service S with default M2@1.6;
}

Not a big change, but it makes huge impact. The NP-Completeness is gone. Whenever somebody wants to compile against module M1, we also have to verify that the module M2 at revision 1.6 can be enabled. This is trivial polynomial check that can easily be done by JavaC.

<comments/>