NP-Completeness Re: How to drain your laptop battery using Jigsaw

[mark.reinhold at oracle.com]

Thanks (to both you and Jesse) for raising this issue.  I'm not at all
surprised that our current resolver can be pushed into pathological
run-time behavior.  It's critical that we understand the complexity of
what we're trying to build, even if we ultimately decide to live with
it rather than reduce it.

I've skimmed your proof (I won't have time to study it in detail until
after the holidays), and one question I have so far is this: Is saying
"supports implicit re-export on an implicit base" just another way of
saying "only one version of any particular module of a given name is
allowed"?  You use the term "implicit re-export", but your proof of
course doesn't actually consider what types are or are not re-exported,
so I'm a bit confused by this terminology.

On your LibraryWithoutImplicitExportIsPolynomial [1] page you define the
concept of a "complete" repository, in which the transitive dependencies
of all modules are explicitly enumerated.  You suggest that the set of a
module's transitive dependencies could be generated at compile time, but
doesn't that mean that you'd still have to run a general -- and possibly
NP-complete -- resolution algorithm at compile time in order to compute
that set?

As to the potential solutions, renaming a module in the case of an
incompatible change is a bit ugly, but it's worth exploring further.
It basically amounts to moving the major version number into the module
name, which is already a common practice in native packaging systems.

I agree that the module system must pick a version of each module to load
such that all dependences are satisfied for the reason you state, i.e., a
single repository (= library) can contain modules for many applications.

Finally, to the big question of whether Jigsaw should try to avoid
NP-completeness: I'd prefer to avoid it, but I'm willing to accept it.
Plenty of existing systems seem to work just fine in the face of this
theoretical complexity (e.g., OSGi, Debian, RPM), and in many scenarios
Jigsaw will never do resolution at run time anyway.

(I suppose this places me firmly on the Western side of your Ocean, but
 with a keen eye toward the East.)

- Mark


[1] http://wiki.apidesign.org/index.php?title=LibraryWithoutImplicitExportIsPolynomial&useskin=monobook