* lib/rubygems/dependency_resolver.rb: Switch the iterative resolver

  algorithm from recursive to iterative to avoid possible
  SystemStackError.


git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@42969 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

2 files changed, 92 insertions, 59 deletions

diff --git a/ChangeLog b/ChangeLog
index e0d852e192..a5d813501f 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+Thu Sep 19 06:39:40 2013  Eric Hodel  <drbrain@segment7.net>
+
+	* lib/rubygems/dependency_resolver.rb:  Switch the iterative resolver
+	  algorithm from recursive to iterative to avoid possible
+	  SystemStackError.
+
 Thu Sep 19 06:29:30 2013  Eric Hodel  <drbrain@segment7.net>
 
 	* lib/rubygems:  Update to RubyGems 2.2.0.preview.1
diff --git a/lib/rubygems/dependency_resolver.rb b/lib/rubygems/dependency_resolver.rb
index abce692920..9f3af38ae5 100644
--- a/lib/rubygems/dependency_resolver.rb
+++ b/lib/rubygems/dependency_resolver.rb
@@ -92,12 +92,52 @@ class Gem::DependencyResolver
     res.to_a
   end
 
+  def handle_conflict(dep, existing)
+    # There is a conflict! We return the conflict
+    # object which will be seen by the caller and be
+    # handled at the right level.
+
+    # If the existing activation indicates that there
+    # are other possibles for it, then issue the conflict
+    # on the dep for the activation itself. Otherwise, issue
+    # it on the requester's request itself.
+    #
+    if existing.others_possible?
+      conflict =
+        Gem::DependencyResolver::DependencyConflict.new dep, existing
+    else
+      depreq = existing.request.requester.request
+      conflict =
+        Gem::DependencyResolver::DependencyConflict.new depreq, existing, dep
+    end
+
+    @conflicts << conflict
+
+    return conflict
+  end
+
+  # Contains the state for attempting activation of a set of possible specs.
+  # +needed+ is a Gem::List of DependencyRequest objects that, well, need
+  # to be satisfied.
+  # +specs+ is the List of ActivationRequest that are being tested.
+  # +dep+ is the DepedencyRequest that was used to generate this state.
+  # +spec+ is the Specification for this state.
+  # +possible+ is List of DependencyRequest objects that can be tried to
+  # find a  complete set.
+  # +conflicts+ is a [DependencyRequest, DependencyConflict] hit tried to
+  # activate the state.
+  #
+  State = Struct.new(:needed, :specs, :dep, :spec, :possibles, :conflicts)
+
   ##
   # The meat of the algorithm. Given +needed+ DependencyRequest objects and
   # +specs+ being a list to ActivationRequest, calculate a new list of
   # ActivationRequest objects.
 
   def resolve_for needed, specs
+    # The State objects that are used to attempt the activation tree.
+    states = []
+
     while needed
       dep = needed.value
       needed = needed.tail
@@ -109,26 +149,46 @@ class Gem::DependencyResolver
         # existing spec.
         next if dep.matches_spec? existing
 
-        # There is a conflict! We return the conflict
-        # object which will be seen by the caller and be
-        # handled at the right level.
+        conflict = handle_conflict dep, existing
 
-        # If the existing activation indicates that there
-        # are other possibles for it, then issue the conflict
-        # on the dep for the activation itself. Otherwise, issue
-        # it on the requester's request itself.
-        #
-        if existing.others_possible?
-          conflict =
-            Gem::DependencyResolver::DependencyConflict.new dep, existing
-        else
-          depreq = existing.request.requester.request
-          conflict =
-            Gem::DependencyResolver::DependencyConflict.new depreq, existing, dep
+        # Look through the state array and pop State objects
+        # until we get back to the State that matches the conflict
+        # so that we can try other possible sets.
+
+        i = nil
+
+        until states.empty?
+          if conflict.for_spec? states.last.spec
+            i = states.last
+            i.conflicts << [i.spec, conflict]
+            break
+          else
+            states.pop
+          end
         end
-        @conflicts << conflict
 
-        return conflict
+        if i
+          # We exhausted the possibles so it's definitely not going to
+          # work out, bail out.
+
+          if i.possibles.empty?
+            raise Gem::ImpossibleDependenciesError.new(i.dep, i.conflicts)
+          end
+
+          spec = i.possibles.pop
+
+          # Recursively call #resolve_for with this spec
+          # and add it's dependencies into the picture...
+
+          act = Gem::DependencyResolver::ActivationRequest.new spec, i.dep
+
+          needed = requests(spec, act, i.needed)
+          specs = Gem::List.prepend(i.specs, act)
+
+          next
+        else
+          return conflict
+        end
       end
 
       # Get a list of all specs that satisfy dep and platform
@@ -169,10 +229,6 @@ class Gem::DependencyResolver
           [s.source, s.version, s.platform == Gem::Platform::RUBY ? -1 : 1]
         end
 
-        # We track the conflicts seen so that we can report them
-        # to help the user figure out how to fix the situation.
-        conflicts = []
-
         # To figure out which to pick, we keep resolving
         # given each one being activated and if there isn't
         # a conflict, we know we've found a full set.
@@ -181,48 +237,19 @@ class Gem::DependencyResolver
         # to keep the stack short since we're using a recursive
         # algorithm.
         #
-        until possible.empty?
-          s = possible.pop
-
-          # Recursively call #resolve_for with this spec
-          # and add it's dependencies into the picture...
-
-          act = Gem::DependencyResolver::ActivationRequest.new s, dep
-
-          try = requests(s, act, needed)
+        spec = possible.pop
 
-          res = resolve_for try, Gem::List.prepend(specs, act)
+        # We're may need to try all of +possible+, so we setup
+        # state to unwind back to current +needed+ and +specs+
+        # so we can try another. This is code is what makes the above
+        # code in conflict resolution possible.
 
-          # While trying to resolve these dependencies, there may
-          # be a conflict!
+        act = Gem::DependencyResolver::ActivationRequest.new spec, dep
 
-          if res.kind_of? Gem::DependencyResolver::DependencyConflict
-            # The conflict might be created not by this invocation
-            # but rather one up the stack, so if we can't attempt
-            # to resolve this conflict (conflict isn't with the spec +s+)
-            # then just return it so the caller can try to sort it out.
-            return res unless res.for_spec? s
+        states << State.new(needed, specs, dep, spec, possible, [])
 
-            # Otherwise, this is a conflict that we can attempt to fix
-            conflicts << [s, res]
-
-            # Optimization:
-            #
-            # Because the conflict indicates the dependency that trigger
-            # it, we can prune possible based on this new information.
-            #
-            # This cuts down on the number of iterations needed.
-            possible.delete_if { |x| !res.dependency.matches_spec? x }
-          else
-            # No conflict, return the specs
-            return res
-          end
-        end
-
-        # We tried all possibles and nothing worked, so we let the user
-        # know and include as much information about the problem since
-        # the user is going to have to take action to fix this.
-        raise Gem::ImpossibleDependenciesError.new(dep, conflicts)
+        needed = requests(spec, act, needed)
+        specs = Gem::List.prepend(specs, act)
       end
     end