Direct Acyclic Dependency Graph
When building a package, it is expected that the maintainer of the package will define a set of dependencies so when installing the package, it works first time.
The dependencies are defined using the Depends field. This is a list of package names with version and architectures constraints (although in a binary package the architecture constraints in the Depends are removed.) In most cases package dependencies do not require a version or architecture constraint, so it is just a package name.
There is an example for a package named "gui" that makes use of Qt and libxml++, it would look something like this:
Depends: qt (> 1.4), libxml++ (> 1.2)
Although the libxml++ depends on libxml2, and libxml2 depends on iconv, this is not part of the gui package Depends because those are not direct dependencies of the gui package. They will automatically be inferred as required when installing the gui package though.
wpkg has the ability to implicitly install packages that are needed. If you run the command line:
wpkg --install gui_1.2.3_win32-i386.deb --repository more-packages
Then the qt and libxml++ libraries will also be installed if they are not installed yet and are available in the repository (the more-packages directory.) In order to ensure a proper environment, the tool creates a set of directed acyclic dependency graphs and it chooses the one with the newest version of all the modules that it is allowed to use.
In some cases the newest version cannot be used. For example, say you have a package X that works with version 1.x of package Y. When the package Y releases version 2.x, X breaks. What you do is add a constraint in X saying that any package Y version 2.x or larger is not compatible.
Depends: Y (< 2)
In this case, when building the directed acyclic graph of dependencies, the package Y_2.1_arch.deb would actually be refused (marked as invalid.)
When you have a large number of modules, many of which have version constraints, you can run in a problem where multiple packages depend on multiple versions of other packages.
Say you have modules A, B, and C and require the dependencies X and Y. As wpkg searches for dependencies, it finds 3 X's(X1, X2, and X3) and 3 Y's (Y1, Y2, and Y3).
Because of all the constraints, you may end up with two graphs that include the following:
- First graph: X2 and Y3
- Second graph: X3 and Y1
By default we select a graph because it has all the newest package versions. However, in this case the computer has a dilemma. It cannot know whether it is better to have (X2, Y3) or (X3, Y1).
