bundler/bundler — pull request #2726 by Who828 (2013-11-22 04:07:33+00:00)
Title: Implemented an iterative version of Bundler's dependency resolving algorithm

Hey folks,

I reimplemented the Bundler's dependency resolving algorithm iteratively as it was giving stack overflow errors for lot of people. Also this implementation is much more easier to understand than the previous one (catch and throw to unwind recursion!). The main crux of this algorithm is to rely on a stack and create a struct to handle the state of requirement and activated gems. (basically create a data structure to handle the call stack). It's still using the original BFS search, so no changes there.

I also took the time to fix bugs #2532 and #2464 and included the spec written by Hemant (@gnufied) to make sure its 100% fixed. I have also included a complex conflict spec because my algorithm passed all the bundler specs but failed this one (now its passing, of course).

My implementation is based on the Rubygems version of Resolver, if I didn't have that code as reference I don't think I would have been able to come up this algorithm. (Thank you so much @evanphx!), I have also deleted the unneeded code because of this algorithm. (mainly the safe_catch code and its specs)

I think I can still do the following,

1. Add more comments (if needed)
2. Refactor the code (now that I finally understand it)
3. Test the performance (it shouldn't have degraded)

However, I wanted to showcase this work to the Bundler's team. Since this algorithm is a core part of Bundler and the correctness of this algorithm triumphs everything else.

I just wanted to see if you folks are happy with the work and if I didn't miss any corner cases.

PS: This is my first non-trivial opensource patch, I am very nervous at the moment!