Improved Package Resolution Algorithm

[DavePearce]

(@altmattr this may interest you)

Currently, the manner which packages are resolved is problematic. Specifically, when we have two packages which depend on different versions of a third. This is the classic problem of transitive dependencies, of course!! Currently, the resolution algorithm activates all versions of a given dependency. This completely fails because Whiley currently has no support for handling multiple versions of a given package. Hence, you can't tell which version you are actually compiling against and I don't even know which one will be generated.

Maven (see [1]):

Maven picks the "nearest definition". That is, it uses the version of the closest dependency to your project in the tree of dependencies. You can always guarantee a version by declaring it explicitly in your project's POM

NPM (see here):

This package manager makes little effort to handle resolution, and appears to simply allow different versions of a package to coexist.

Cargo (see here):

This appears to allow different versions of a package to coexist. However, it doesn't allow multiple versions which semver compatible to coexist. The algorithm is employ is a relatively simple DFS approach. There are some "bombs" which can explode the amount of work it performs (see here).

Rust also employs the Cargo.lock file which helps to mitigate the cost of solving the dependency graph. Specifically, this maps out all the packages which are activated.

Thoughts

Overall, Rust seems to have a sensible approach. However, a critical aspect of this is that it allows multiple activations of the same package (provided they are semver incompatible). For example, v2.x can be activated alongside v1.x. This means adding support for multiple package activations to Whiley.

[DavePearce]

Perhaps the starting point is to (initially) stick with a very simple resolution algorithm that activates all dependencies. Then, we make this work. That means:

1. (Compilation) When compiling against a package, we only ever have one instance in the visible name space.
2. (Name Mangling) When generating code for a client of some package, we need to know exactly what version of that package we are generating code for. Then, we embed the version number into the name mangle (somehow).
3. (Code Generation) When generating code, we need some way to enumerate all packages and versions.

This requires some reasonable changes to the current build process.

[DavePearce]

At this stage, have implemented a simplistic approach:

• A master index exists now for the remote repository
• When a given package is requested, the latest compatible version is always chosen. For example, if v1.0.2 was requested and the latest version of the package was v1.2.4 then the latter would always be chosen.

There are some issues here, however. Firstly, one cannot fix a specific version of a library. Secondly, version conflicts are not supported gracefully (i.e. when different major versions of a package are requested). However, at the same time, it does resolve the major outstanding issue with the versioning system: that of transitively updating all libraries to use the latest version of a library.