Consider leveraging solve ruby constraint solver

[patcon]

I'm sure you've seen berkshelf using it, but just wanted to create a stub

https://github.com/reset/solve

[yfeldblum]

I have taken a look at Solve, and have actually culled a few ideas from and done some optimizations based on Solve.

But from what I can tell, the Solve library requires that the calling program have the entire constraints graph in-memory up-front.

From what I can tell, Berkshelf does not perform a complete resolution over the entire graph. It does not consider all possible versions of all possible cookbooks in all the sources. It fetches some dependencies up-front and caches them, but ultimately performs a resolution only over the cached dependencies.

Librarian does not have the entire constraints graph in-memory up-front. In fact, the Librarian resolver can add new vertices and edges to the constraint graph during the constraint-solving (dependency-resolving) process. This lets the Librarian resolver perform a complete resolution over the entire constraints graph, without having the entire graph in-memory up-front.

The reason this matters is that the Opscode Community Site does not have an API suitable for dependency-resolvers. There is no way to fetch, via the API, the dependencies of any version of any cookbook. To get that data, one must download and unpack the whole cookbook and read the cookbook's metadata file. In order for Librarian to do a full resolution, it would need to either download and unpack a very large number of cookbooks up-front, or download cookbooks lazily on-demand. It does the second.

[patcon]

Thanks very much for the explanation Jay!