(Complete) range dependencies back in the game?

[Jesse Glick]

On 01/08/2012 11:44 AM, Jaroslav Tulach wrote:
> http://wiki.apidesign.org/wiki/RangeDependenciesAnalysed

"It does not make much sense to have higher upper bound of dependency on C higher than any existing upper bound on C among reused libraries (thus s <= q)" - I disagree 
that this does not make sense.

Let us say that C has both an API and an SPI; the API is kept quite stable but the SPI is frequently rewritten (and the handful of implementations are expected to keep 
up). So pretend C is DOM, and API clients normally use ranges like [1.2,2) ("DOM 2 or any foreseeable compatible release") whereas SPI implementations normally use ranges 
like [1.2,1.3) ("DOM 2 but not 3").

Now pretend B is a library for XML persistence of Java objects, and during one serialization mode it creates flyweight org.w3c.dom.Document's. Versions 1.0 through 1.3, 
written back when DOM 2 ruled the land, declares [1.2,1.3); version 1.4 and later implement DOM 3 so declare [1.3,1.4) but are otherwise fully compatible for callers.

Finally say A is an application which uses XML serialization for some preferences storage, and also uses DOM quite independently for dealing with REST clients. So it 
would like to declare B@[1.0,2) and C@[1.2,2): it uses only the basic initial serialization API, and can work with any known DOM release.

The fact that B at 1.0 is incompatible with C at 1.3 does not trouble the author of A; the app would work fine with B at 1.5 and C at 1.3 as well. If the compiler silently converted 
the dep on C@[1.2,2) to C@[1.2,1.3), it would effectively mean that B at 1.4 could not be used even if it had numerous bug fixes, which is generally not what you want. It 
could instead just reject A's attempted expression of what its actual dependency ranges are, with some sort of error message TBD, and the author of A would (after some 
trial and error) eventually give up on supporting older libraries and request B@[1.4,2) and C[1.3,2).

This switch would be rather artificial: the originally attempted dependency declaration was logically sound, and a module system using a SAT solver would not have 
difficulty linking A with either newer or older libraries according to what is available. (An organization which decided it hated the DOM 3 license might forbid it from 
being installed, in which case you would like to be able to run A with B at 1.3 and C at 1.2.)

Indeed if A does not use XML namespaces in its REST API, it could as well declare C@[1.1,2) even knowing that current versions of B require at least C at 1.2; a future 
version of B might stop needing to implement DOM and (if it did not use namespaces either) might declare C@[1.1,2), in which case B at 1.7 C at 1.1 would be a valid 
configuration too. Obviously this is a less likely scenario, but it shows that "[t]his definition seems to make sense from the point of lower bound" is not so obvious either.


On this topic, I think the definition of complete repository is unnecessarily strict; there is no reason apparent to me why [r,s) must be a subrange of [p,q), though it 
does at least need to overlap (and probably a version of C in that intersection must actually be present in the repo). Where in the proof is the assumption of subranges 
used? You only check whether cr is empty, which it would be in the attempted conversion to 3-SAT. It seems that A could express any dependency on C it likes, and trying 
to compile A would either work or not work, according to whether its dep on C has at least some overlap with that of the earliest versions of its other dependencies.


By the way, you do not really discuss selecting a configuration at install time in a complete repository. [1] does not seem to apply to arbitrary range dependencies. 
Probably you can start with a configuration using the lower bounds of all dependencies as determined during compilation, then iteratively try raising the version of each 
module individually so long as doing so continues to result in a valid configuration - i.e. pick a locally maximal configuration. This is polynomial.


[1] http://wiki.apidesign.org/wiki/LibraryWithoutImplicitExportIsPolynomial#Merge_of_Configurations