How to drain your laptop battery using Jigsaw

[Jesse Glick]

My colleague Yarda Tulach had investigated module systems supporting version ranges, and wrote up a formal proof [1] that picking one version of each of several modules 
in a repository such that all dependencies are satisfied is in general NP-complete. I decided to verify that Jigsaw suffers from this problem.

The attached program, run against a recent Jigsaw build (8c6429c279e7), starts consuming many seconds of CPU time per round (effectively hanging) somewhere around 9 
variables (depending on the random seed), mostly running in Resolver.resolve according to a profiler. The randomized nature of the test and the clause count is designed 
to stress the system, of course.

Possible resolutions to this problem include:

1. Drop the requirement that module dependencies may include version ranges or otherwise permit incompatible changes to be marked, so that a dependency is always on some 
version or later. This seems unsatisfactory.

2. Drop the requirement that the module system pick a version of each module to load such that all dependencies are satisfied. For example: just try to load the newest 
available version of each module, and if any dependencies are in fact unsatisfied, report an error and ask the user to override one or more module versions manually.

3. Rewrite Resolver using something like SAT4J, or even leave it as it is, and just document that pathological cases can result in unbounded execution time.

4. Require that a new release of any module which uses an incompatible version of some dependency (even if used only internally) is itself marked incompatible. This seems 
unsatisfactory since it breaks encapsulation - I should not be forced to label my new widely used graphics toolkit 2.0 rather than 1.1 merely because I started to use a 
refactored version of some math library after 1.0 was released. Also it is unclear how you would enforce this constraint so long as Jigsaw assigns no semantics to version 
numbers except that they are totally ordered.

5. Permit multiple versions of a module to be loaded so long as class spaces remain consistent - resolving such configurations when needed - and only require that a new 
release of a module whose public signature refers to an incompatible version of some dependency is itself marked incompatible. (Whether 'requires public' is used does not 
matter.) More palatable than #4 but still forces a cascade of incompatibility, even when the incompatible change in the dependency is unrelated to this module's usage of 
it. Like #4, enforcement would require stronger version semantics.

Yarda please step in if I misrepresented any of these options.


[1] http://wiki.apidesign.org/wiki/LibraryReExportIsNPComplete