Create an entirely new dependency resolver to help solve #22 and #23 becauseā€¦

Authored by ouwerkerk on Mar 3 2019, 8:31 PM.

Description

Create an entirely new dependency resolver to help solve #22 and #23 because, well, why not?

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. Check if any circular dependencies were expressed, and if so abort dependency resolution with an error to avoid infinite loops
  3. 'Copy up' dependency information: walk the graph and for each node produce a complete map of all of its (transitive) dependencies.
  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(): errors can simply be dealt with by returning an error code/object.
  • 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.

Details

Committed
ouwerkerkMar 31 2019, 11:07 AM
Parents
R365:5ee43214d42b: Fix typo: rename the Qt 5 module set ('qt5' -> 'Qt5').
Branches
Unknown
Tags
Unknown