== Can we live with Complete Repositories? ==

== Can we live with Complete Repositories? ==

Some may say that ''complete repositories'' are not practical and they are hard to maintain. This may be correct when it is not easy to identify that one reuses a feature re-exported by some module. For example in case of [[BackwardCompatibility#Functional Compatibility|functional compatibility]] one can depend on behaviour of a deeply hidden module (which is re-exported without direct dependency) and this is hard to identify.

Some may say that ''complete repositories'' are not practical and they are hard to maintain. This may be correct when it is not easy to identify that one reuses a feature re-exported by some module. For example in case of [[Functional compatibility]] one can depend on behaviour of a deeply hidden module (which is re-exported without direct dependency) and this is hard to identify.

On the other hand, there are other kind of [[BackwardCompatibility]] where ''complete repositories'' are natural. During compilation one needs all the module [[JAR]]s or header files to be present, not just those that one directly depends on. Even if one includes just '''java.applet''' module (in the proposed [[Modular Java SE]]), one also needs '''java.awt''' because the [http://java.sun.com/javase/6/docs/api/java/applet/Applet.html Applet] class extends (e.g. re-exports) classes from the '''java.awt''' module. The same applies to [[C]]'s use of ''stdio.h'' - it also needs bunch of other include files.

On the other hand, there are other kind of [[BackwardCompatibility]] where ''complete repositories'' are natural. During compilation one needs all the module [[JAR]]s or header files to be present, not just those that one directly depends on. Even if one includes just '''java.applet''' module (in the proposed [[Modular Java SE]]), one also needs '''java.awt''' because the [http://java.sun.com/javase/6/docs/api/java/applet/Applet.html Applet] class extends (e.g. re-exports) classes from the '''java.awt''' module. The same applies to [[C]]'s use of ''stdio.h'' - it also needs bunch of other include files.

The [[LibraryReExportIsNPComplete]] outlined the problem one has to face when practicing [[DistributedDevelopment]]. The [[LibraryReExportIsNPComplete|page]] also proved that in its global scope the problem is [[NP-Complete]] as any [[3SAT]] problem can be transformed to it.

The [[LibraryReExportIsNPComplete]] outlined the problem one has to face when practicing [[DistributedDevelopment]]. The [[LibraryReExportIsNPComplete|page]] also proved that in its global scope the problem is [[NP-Complete]] as any [[3SAT]] problem can be transformed to it.

# '''module without dependencies''' - in almost any system there is at least one ''base'' module that does not have any dependencies. Computing set of dependencies of such module during compilation is obviously a constant operation.

# '''module without dependencies''' - in almost any system there is at least one ''base'' module that does not have any dependencies. Computing set of dependencies of such module during compilation is obviously a constant operation.

# when '''compiling a module <math>M</math>''' with direct dependencies on <math>M_1, ..., M_n</math>. We can assume that <math>M_1, ..., M_n</math> have all their transitive dependencies already resolved (otherwise we would not have them in our complete repository). Let's now collect all transitive dependencies of <math>M_1, ..., M_n</math> into a set and verify whether they are all consistent. This has already been explorered in [[#Merge of Configurations|merge of configurations]] section and is known to be polynomial.

# when '''compiling a module <math>M</math>''' with direct dependencies on <math>M_1, ..., M_n</math>. We can assume that <math>M_1, ..., M_n</math> have all their transitive dependencies explicitly enumerated (otherwise they could not be part of the ''complete repository''). Let's now collect all transitive dependencies of <math>M_1, ..., M_n</math> into a set and verify whether they are all consistent. This has already been explorered in [[#Merge of Configurations|merge of configurations]] section and is known to be polynomial.

In case the merged configuration of <math>M_1, ..., M_n</math> are consistent, we have new, polynomially sized (at most n times maximal size of configuration of individual module) configuration for module <math>M</math>. If the merged configuration is not consistent, the compilation should fail (in polynomial time) and the module <math>M</math> should not be created at all. As a result the [[NP-Complete]] threat is eliminated during compilation.

In case the merged configuration of <math>M_1, ..., M_n</math> are consistent, we have new, polynomially sized (at most n times maximal size of configuration of individual module) configuration for module <math>M</math>. If the merged configuration is not consistent, the compilation should fail (in polynomial time) and the module <math>M</math> should not be created at all. As a result the [[NP-Complete]] threat is eliminated during compilation.

# '''module without dependencies''' - in almost any system there is at least one ''base'' module that does not have any dependencies. Computing set of dependencies of such module during compilation is obviously a constant operation.

# '''module without dependencies''' - in almost any system there is at least one ''base'' module that does not have any dependencies. Computing set of dependencies of such module during compilation is obviously a constant operation.

# when compiling a module <math>M</math> with direct dependencies on <math>M_1, ..., M_n</math>. We can assume that <math>M_1, ..., M_n</math> have all their transitive dependencies already resolved (otherwise we would not have them in our complete repository). Let's now collect all transitive dependencies of <math>M_1, ..., M_n</math> into a set and verify whether they are all consistent. This has already been explorered in [[#Merge of Configurations|merge of configurations]] section and is known to be polynomial.

# when '''compiling a module <math>M</math>''' with direct dependencies on <math>M_1, ..., M_n</math>. We can assume that <math>M_1, ..., M_n</math> have all their transitive dependencies already resolved (otherwise we would not have them in our complete repository). Let's now collect all transitive dependencies of <math>M_1, ..., M_n</math> into a set and verify whether they are all consistent. This has already been explorered in [[#Merge of Configurations|merge of configurations]] section and is known to be polynomial.

In case the merged configuration of <math>M_1, ..., M_n</math> are consistent, we have new, polynomially sized (at most n times maximal size of configuration of individual module) configuration for module <math>M</math>. If the merged configuration is not consistent, the compilation should fail (in polynomial time) and the module <math>M</math> should not be created at all. As a result the [[NP-Complete]] threat is eliminated during compilation.

In case the merged configuration of <math>M_1, ..., M_n</math> are consistent, we have new, polynomially sized (at most n times maximal size of configuration of individual module) configuration for module <math>M</math>. If the merged configuration is not consistent, the compilation should fail (in polynomial time) and the module <math>M</math> should not be created at all. As a result the [[NP-Complete]] threat is eliminated during compilation.

# '''module without dependencies''' - in almost any system there is at least one ''base'' module that does not have any dependencies. Computing set of dependencies of such module during compilation is obviously a constant operation.

# '''module without dependencies''' - in almost any system there is at least one ''base'' module that does not have any dependencies. Computing set of dependencies of such module during compilation is obviously a constant operation.

# when compiling a module <math>M</math> with direct dependencies on <math>M_1, ..., M_n</math>. We can assume that <math>M_1, ..., M_n</math> have all their transitive dependencies already resolved. Let's now collect all transitive dependencies of <math>M_1, ..., M_n</math> into a set and verify whether they are all consistent. This has already been explorered in [[#Merge of Configurations|merge of configurations]] section and is known to be polynomial.

# when compiling a module <math>M</math> with direct dependencies on <math>M_1, ..., M_n</math>. We can assume that <math>M_1, ..., M_n</math> have all their transitive dependencies already resolved (otherwise we would not have them in our complete repository). Let's now collect all transitive dependencies of <math>M_1, ..., M_n</math> into a set and verify whether they are all consistent. This has already been explorered in [[#Merge of Configurations|merge of configurations]] section and is known to be polynomial.

In case the merged configuration of <math>M_1, ..., M_n</math> are consistent, we have new, polynomially sized (at most n times maximal size of configuration of individual module) configuration for module <math>M</math>. If the merged configuration is not consistent, the compilation should fail (in polynomial time) and the module <math>M</math> should not be created at all. As a result the [[NP-Complete]] threat is eliminated during compilation.

In case the merged configuration of <math>M_1, ..., M_n</math> are consistent, we have new, polynomially sized (at most n times maximal size of configuration of individual module) configuration for module <math>M</math>. If the merged configuration is not consistent, the compilation should fail (in polynomial time) and the module <math>M</math> should not be created at all. As a result the [[NP-Complete]] threat is eliminated during compilation.

The complexity of the above algorithm is polynomial. The fact that configuration produced by it satisfies all the module dependencies is obvious. The proof that if the algorithm gives up, there is no configuration in the ''complete repository'' to satisfy all the modules dependencies is left for reader's consideration.

The complexity of the above algorithm is polynomial. The fact that configuration produced by it satisfies all the module dependencies is obvious. The proof that if the algorithm gives up, there is no configuration in the ''complete repository'' to satisfy all the modules dependencies is left for reader's consideration.

== Conclusion ==

== Conclusion ==

A repository <math>R=(M,D)</math> is said to be ''complete'' if '''the transitive dependencies are explicitly enumerated''':

A repository <math>R=(M,D)</math> is said to be ''complete'' if '''the transitive dependencies are explicitly enumerated''':

# <math>A_{x.y} \rightarrow B_{u.v} \in D \wedge \exist w >= v B_{u.w} \gg C_{p.q} \in D \Rightarrow \exists r <= q A_{x.y} \rightarrow C_{p.r} \in D</math>

# <math>A_{x.y} \rightarrow B_{u.v} \in D \wedge \exist (w >= v) B_{u.w} \gg C_{p.q} \in D \Rightarrow \exists (r <= q) A_{x.y} \rightarrow C_{p.r} \in D</math>

In the above the symbol <math>\rightarrow</math> may mean dependency with re-export (e.g. <math>\gg</math>) or dependency without re-export (e.g. <math>></math>).

In the above the symbol <math>\rightarrow</math> may mean dependency with re-export (e.g. <math>\gg</math>) or dependency without re-export (e.g. <math>></math>).

The way to fight with [[NP-Complete]] nature of [[LibraryReExportIsNPComplete|Module Dependency Problem]] is to generate ''complete repositories''. It is easy to create such repositories when one is primarily interested in coherent linkage of modules. All that is necessary is to modify our compilers to require (or infer and record) properly specified dependencies on all re-exported modules one is using, not just on the top level module that re-exports them.

The way to fight with [[NP-Complete]] nature of [[LibraryReExportIsNPComplete|Module Dependency Problem]] is to generate ''complete repositories''. It is easy to create such repositories when one is primarily interested in coherent linkage of modules. All that is necessary is to modify our compilers to require (or infer and record) properly specified dependencies on all re-exported modules one is using, not just on the top level module that re-exports them.

== Merge of Configurations ==

== Merge of Configurations ==

One additional issue needs consideration. When starting a system, one often needs to enable more than a single module. Some [[modular systems]] provide good enough isolation, so running modules can use incompatible versions safely. However some systems require that each module is present in just a single version. The question then is: Is it easy to find out whether a set of modules can be enabled together (while only a single version of a module is present)?

One additional issue needs consideration. When starting a system, one often needs to enable more than a single module. Some [[module system]]s provide good enough isolation, so running modules can use incompatible versions safely. However some systems require that each module is present in just a single version. The question then is: Is it easy to find out whether a set of modules can be enabled together (while only a single version of a module is present)?

Each module is equipped with a configuration (created during compilation). So the problem of enabling more modules reduces to a question whether, given a set of configurations one can find one which satisfies dependencies of all modules. This would be [[NP-Complete]] in common module repository, but in ''complete repositories'' this is a polynomial problem.

Each module is equipped with a configuration (created during compilation). So the problem of enabling more modules reduces to a question whether, given a set of configurations one can find one which satisfies dependencies of all modules. This would be [[NP-Complete]] in common module repository, but in ''complete repositories'' this is a polynomial problem.

Just visit all the dependencies of all modules and if there is a dependency on module <math>A_{x.y}</math> and <math>A_{p.q}</math>, then:

Just visit all the dependencies of all modules and if there is a dependency on module <math>A_{x.y}</math> and <math>A_{p.q}</math>, then:

# '''choose most recent version''': if <math>x \eq p</math> keep just <math>A_{x.max(q, y)}</math>

# '''choose most recent version''': if <math>x = p</math> keep just <math>A_{x.max(q, y)}</math>

# '''detect incompatibilities''': if <math>x \neq p</math> then give up

# '''detect incompatibilities''': if <math>x \neq p</math> then give up

As the compilation is closely tight to linkage (and ability to link defines [[BinaryCompatibility]]), it is easy to generate ''complete repository'' of modules that can later be easily assembled and linked for execution in polynomial time.

As the compilation is closely tight to linkage (and ability to link defines [[BinaryCompatibility]]), it is easy to generate ''complete repository'' of modules that can later be easily assembled and linked for execution in polynomial time.

== Conclusion ==

== Conclusion ==

The way to fight with [[NP-Complete]] nature of [[LibraryReExportIsNPComplete|Module Dependency Problem]] is to generate ''complete repositories''. It is easy to create such repositories when one is primarily interested in coherent linkage of modules. All that is necessary is to modify our compilers to require (or infer and record) properly specified dependencies on all re-exported modules one is using, not just on the top level module that re-exports them.

The way to fight with [[NP-Complete]] nature of [[LibraryReExportIsNPComplete|Module Dependency Problem]] is to generate ''complete repositories''. It is easy to create such repositories when one is primarily interested in coherent linkage of modules. All that is necessary is to modify our compilers to require (or infer and record) properly specified dependencies on all re-exported modules one is using, not just on the top level module that re-exports them.