Here is an outline of a test case for some corner cases for using dependency types (#378) to allow build-only dependencies to be resolved separately from other, unrelated, instances of the package in the DAG. The use case is for something like a package A which uses scons to build which brings in, say python@2. Another package, X depends on A and B, but B depends on python@3. Currently, the DAG will fail to resolve due to the python incompatibilities even though they do not strictly conflict.

@tgamblin @dhandeo @eschnett @citibeth

Suppose we are looking to install a package R. Here is the dependency graph for R:

First, when traversing the DAG, we get this information:

Name    Type    Parent
----    ----    ------
R       b,l,r
D₁      b,l     R
B₁~X    b       D₁
L₁      b,l     D₁
B₁      b       L₁
L₂      b,l     L₁
D₂      b,l     R
B₁+X    b       D₂

When traversing, we add specs to the resolution map M unless we find specs which match Type = {b} ∧ Parent ≠ R. For each such case, we make a new resolution map Mₖ and add the non-root traversal over its parent for {link, run} dependencies over D₁'s {build, link} dependencies. This query creates a map for all specs which will need to be loaded during D₁'s build. Here, this equates to {L₁, B₁, B₁~X, L₂}. There will be another resolution multimap for the B₁+X dependency of D₂ containing {B₁+X}.

Here is a snapshot of the dependency resolution maps after the initial traversal:

M: {D₁, L₁, B₁, D₂, L₂}
M₁: {L₁, B₁, B₁~X, L₂}
M₂: {B₁+X}

Now we must resolve each Mₖ against M. However, we must choose an order in which to do so. I'm not sure of a fool-proof way to do this, but a sensible one seems to be to sort the maps based on how many entries are contained in the map which are shared with M and have multiple specs with that Mₖ. Here is the reasoning as to why such a sort is necessary:

Suppose we choose to resolve M₂ against M first. This would force B₁ from L₁ to have the +X feature. When we then go to resolve M₁ itself, we will get a conflict between D₁'s build dependency of B₁~X and the B₁ required by L₁ and the resolution fails (which is the case as it is now, but the problem is that there is a solution).

Whatever heuristic we end up using, it has to at least do this (we may also try backtracking to try other sort orders, but this is O(n!) in the number of secondary resolution maps created, so avoiding that is best (there are ways that can probably be used to determine that one map can't be resolved after another[1], but that isn't going to help that much).

So in resolving M₁ against M, we determine that B₁ in M must be ~X. When we resolve M₂, there is no internal problems, but it cannot use the same B₁ as the main build, so it is possible to just build a second B₁ and use it just for D₂'s build.

[1]Namely when the second resolution fails, the second cannot follow the first. If any first resolution fails, there is no solution.

As a further enhancement, we can, before merging in any Mₖ, resolve M against the set of all installed packages. If any dependency is satisfied there, we can ignore any Mₖ which is made for that dependency (since we do not need to build it ourselves, none of its build dependencies can "spoil" our main package's dependency resolution). However, we must be able to successfully resolve all such installed dependencies together. I'm not sure what the failure mode of such a resolution should be. Do we kick out certain specs? If so, which ones? Kick out all such dependencies (seems harsh)? Fail with a message that X and Y conflict, so either specify ^X/<X_hash>, ^Y/<Y_hash>, or at least one of ^X/new and ^Y/new (the / sigil meaning "look for an installed hash" from #360 with new meaning don't look for an installed hash)? It gets messy quickly.