Skip to content

A new dependency resolver

Johan Ouwerkerk requested to merge a-new-dependency-resolver-why-not into master

Create an entire new dependency resolver to help solve #22 (closed) and #23 (closed) because, well, why not?

Or rather: I felt that issue #23 (closed) was sufficiently 'nasty' that, well, drastic action might be required. I did not see how I could modify to 'fix' the old dependency resolver to cope with Qt5 and given that the failure mode of #23 (closed) seemed so bizarre and inexplicable to me I did not 'trust' that code to be all that solid in the first place. Also, it seemed a pity that the output of the old dependency resolver basically threw away all the information so it could not be used for introspection features easily.

So, a new dependency resolver then. The new one tries to be simpler in that the work is split into more distinct steps. Instead of returning a list of modules sorted into build-order, it returns a graph (a hash keyed by module name).

Additional functions are provided to:

  • convert the graph into a sorted list of modules in build order
  • walk the graph as a tree (for introspection)

The new approach for dependency resolution works in multiple distinct steps:

  1. Resolve the entire set of modules, and construct the graph data structure
  2. Break certain well-known dependency cycles due to imperfect metadata.
  3. Check if any circular dependencies remain
  4. Vote for dependencies, by which each module 'upvotes' its dependencies (directly or indirectly through transitive dependencies). This effectively creates a complete map of back edges for each module in the graph. The vote is used for sorting into build order: the more popular modules should get sorted first.

The new approach may be said to have the following advantages:

  • It does not need to croak_internal() as often: errors can simply be dealt with by returning an error code/object. This is particularly important for the make-it-mojo effort: it would be rather bad if dependency resolution failure meant the entire kdesrc-build server process croaked there and then.
  • The graph structure is exposed and permits much better introspection of what kdesrc-build is doing with dependencies.
  • Subjectively: by using distinct steps there is less seemingly unrelated interaction between various functions going on.
  • It should therefore be relatively easy to write good unit tests for the functions without requiring much outside setup/mocking. (I know nothing about writing unit tests in Perl.)
Edited by Michael Pyne

Merge request reports