RangeDependencies

From APIDesign

Revision as of 19:56, 18 October 2009

Dependencies are important part of every Module system. Dependencies are here to abstract the complex relationship between a module and environment it needs for its own execution, compilation, linkage, etc. Dependencies are always a simplification of the real requirements, but that does not stop people from inventing new and new ways how to specify them more precisely.

It has already been discussed that dependency needs some lower bound (the moment when the needed API is first introduced) and also some higher bound (as incompatible changes are so often). How do we formalize it? Well, let's use some mathematics and describe dependencies as interval! As a result a dependency on any compatible version 1.4.3 and later, would be written as .

This looks like a very good solution. It is also very rationalistic. It is reusing knowledge gained by mathematics in past and thus it cannot be wrong! Moreover it is general enough - one can use the same notation to express equality dependency by writing . And also it is flexible as one can also depend on a smaller range of versions . Last, but not least this solution also supports some level of cluelessness as it builds on something every programmer must have heart of during own school days.

No wonder that everyone one who wants to be seen as providing well designed, deeply thought out, powerful and theoretically backed solution will choose intervals. This is probably the reason why OSGi decided to use this kind of dependencies.

Too Much Flexibility will Kill You!

Although it may seem flexible, overusing RangeDependencies may lead to system that is too complex and almost no longer manageable. What traditionally happens only when people release incompatible versions (due to TransitivityOfIncompatibleChange) can suddenly happen in regular situations.

The proof claiming that managing module dependencies is NP-Complete operates with three types of modules:

1. Mⁱ which is present in two incompatible versions
2. F^j which is present in three compatible versions
3. a single module T

The claim is made that finding whether module T can be enabled is NP-Complete.

One of the most profound critiques however argues that it is wrong if three compatible versions of module F^j depend on incompatible versions of some other modules. This is valid observation, yet one can easily address it using RangeDependencies!

1. instead of two incompatible versions of Mⁱ define two compatible versions: and
2. use strict range for dependencies of F^j, so depends on or depends on
3. single module T continue to depend on classical range of

This scenario describes accepted practices of DistributedDevelopment. Imagine, there is one team providing various versions of module Mⁱ. This team does its best to keep BackwardCompatibility. It is using versioning in the traditional way to denote compatible versions - e.g. the first major number stays the same, the second minor one is incremented with each new, compatible version.

Yet there is some other distant team producing module(s) F^j and this team (or its quality department) is afraid of signing blank checks and trusting the M-team to produce compatible versions. Thus they use restricted RangeDependency to require just subset of the versions (only those known during testing).

This is all that needs to happen. No incompatibilities, just a simple use of RangeDependencies and we are now facing an NP-Complete problem. This probably explains why there is 3SAT solver behind Equinox. Finding the right setup of modules depending on each other with RangeDependencies can be really hard. NP-Completely hard.