berkshelf/solve — pull request #30 by grobie (2014-01-01 23:44:00+00:00)
Title: [WIP] Fix factorial runtime behavior

The current implementation of the solver has a worst case runtime behavior of `O(n!)`, where every combination of artifacts is built in order to find a solution. More specifically, it's the product of available versions of all demanded artifacts.

For example, if there are two artifacts `a` and `b` and `a` has one available version `1.0.0` and `b` has two available versions `0.1.0` and `0.2.0` there are two different combinations to test. If we add another artifact `c` with three versions `0.1.0`, `0.2.0` and `0.3.0` we already have 6 combinations. Assuming there are artifacts with an infinite number of versions - in reality there is probably some upper bound here - we'll get a factorial runtime behavior.

Here is a more or less minimal `Berksfile` (Berkshelf v3) for which the solver won't find a solution in a reasonable time:

```
source 'https://api.berkshelf.com'

cookbook 'apache2'
cookbook 'apt'
cookbook 'build-essential'
cookbook 'mysql'
cookbook 'nginx'
cookbook 'quax-foo-bar'
```

The last cookbook / demand is missing and will force the solver to build every combination of available cookbook versions. While it might be possible to add an earlier detection for missing artifacts, it'll always be possible to construct a graph which will result in the worst case behavior. For example, two demands at the beginning and end of the sorted list of demands could have an impossible constraint on a artifact. This will also result in unwinding and rebuilding all combinations of artifacts in between. See the attached test for such an example.

I found several smaller and bigger problems in the current implementation which are partly fixable, but in the end I think replacing the current implementation with an approach which is not bound to the number of available artifacts to detect impossible solutions will be more beneficial. I started to scratch something out and hope to find enough time today/tomorrow to push it here.