RangeDependencies

From APIDesign

Revision as of 07:21, 17 October 2009 by JaroslavTulach (Talk | contribs)
Jump to: navigation, search

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 some.library \in [ 1.4.3, 2.0).

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 some.library \in [1.4.3, 1.4.3]. And also it is flexible as one can also depend on a smaller range of versions some.library \in [1.4.3, 1.5). Last, but not least this solution also supports some level of cluelessness as it builds on something every programmer must have heard of at 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!

Well, it seems that OSGi comrades made a mistake by choosing RangeDependencies. They created something that is flexible, as flexible that it is no longer manageable. Not only when one starts to deal with TransitivityOfIncompatibleChange, but even in regular situations.

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

  1. Mi which is present in two incompatible versions
  2. Fj 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 Fj 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 Mi define two compatible versions: M^i_{1.1} and M^i_{1.2}
  2. use strict range for dependencies of Fj, so F^j_{1.1} depends on M^i \in [1.1, 1.1] or F^j_{1.2} depends on M^i \in [1.2, 1.2]
  3. single module T continue to depend on classical range of F^j \in [1.0, 2.0)

This is scenario following accepted practices of DistributedDevelopment. There is one team providing various versions of module Mi and that teams does its best to keep BackwardCompatibility. Its versioning follows the traditional way to denote compatible versions - e.g. the first major number stays the same, the second minor one is incremented.

Yet there is some other distant team producing module(s) Fj and this team (or his quality department) is afraid of signing black 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 now facing an NP-Complete problem.

Retrieved from "http://wiki.apidesign.org/wiki/RangeDependencies"
Personal tools
buy