carlhuda/bundler — pull request #2303 by rykov (2013-02-09 03:58:15+00:00)
Title: Optimize conflict resolution to prevent "infinite loop" effect

The current implementation of the Resolver keeps iterating through all the possible permutations of versions until one satisfies all the requirements. This is ok for most cases, but when you have a dependency (like `builder`) in a deep dependency tree with many versions (like `rails => activerecord => activemodel => builder`) that encounters a conflict, Bundler will start trying all the permutations of the tree, which closely imitates the effect of an infinite loop.

This patch prevents iterating on dependency tree branches that don't matter by only traversing up the dependency chain that has generated the conflict.

Note: My understanding of the Resolver is limited, so I hope someone more experienced gives this some more thought before merging.

Possibly related to #2248, #2090, #2273