The core atpm algorithm is not... quite right

[drewcrawford]

So, I'm hitting some edge cases in our core atpm algorithm and I think we have some design issues.

Notation

I use A->B to mean "A depends on B"

Greedy approach is insufficient

Currently our approach to dependency resolution is "greedy", that is we proceed vaguely as follows:

1. Parse A's manifest, learn A->B, A->C
2. Choose a version of B
3. Parse B's manifest, find no dependencies
4. Parse C's manifest, learn C->B, but with particular version constraints on B
5. If the version constraints were not satisfied by the earlier choice in 2, fail.
6. There may be a version of B that satisfies both requirement 2 and 4, but because 2 was processed first, we never "backtrack" to a version of B that also meets requirement 4.

It's not clear to me what the right solution here is. Fundamentally, we are not able to see the path A->C->B before we fetch C, so we cannot merely reorder them up front to resolve the issue. Nor can we know, when we hit condition 6, whether or not a satisfactory version of B exists, because the satisfactory version of B may introduce new dependencies, violating 3 and altering the system further.

Perhaps I need to research how other people solve this problem, but the obvious algorithms to me are to backtrack and try again, which has awful worst-case performance and may not even halt (!)

Atlock

The next problem is that we have an interaction with the above and the atlock.

I believe we currently ignore the atlock completely for packages that aren't the outermost, which may be the most sensible thing we can do. However I don't think we've thought through the details:

1. Suppose we have an end-user application, App
2. The application depends on two libraries, Logging and Network
3. Network also depends on Logging
4. Network developers are aware of some bugs in new Logging versions and so they pin to a particular commit in Network/build.atlock
5. App developers will see no effect of this, because external/Network/build.atlock is not consulted during atpm fetch of App.
6. They are then running Network in an unsupported configuration and who knows what happens now.

I see no obvious solution here either.

ping @owensd @dunkelstern

[dunkelstern]

Concerning atlock: This is by design, only the toplevel atlock is used so the user of the libs can fix a conflict by pinning a specific version. When a sub-library finds a bug in a dependency it is supposed to use the follow up version (x.y.z+1 or x.y+1.z) as it's dependency. If you have to pin a commit there you'll have to manually specify that in a readme or something currently. So the problem with the greedy approach can be fixed by pinning on the toplevel (which is not optimal but workable)