class Bundler::Resolver

def resolve(reqs, activated)
  states = []
  depth = 0
  conflicts = Set.new
  until reqs.empty?
    indicate_progress
    debug { print "\e[2J\e[f" ; "==== Iterating ====\n\n" }
    reqs = reqs.sort_by do |a|
      [ activated[a.name] ? 0 : 1,
        a.requirement.prerelease? ? 0 : 1,
        @errors[a.name]   ? 0 : 1,
        activated[a.name] ? 0 : @gems_size[a] ]
    end
    debug { "Activated:\n" + activated.values.map {|a| "  #{a}" }.join("\n") }
    debug { "Requirements:\n" + reqs.map {|r| "  #{r}"}.join("\n") }
    current = reqs.shift
    $stderr.puts "#{' ' * depth}#{current}" if ENV['DEBUG_RESOLVER_TREE']
    debug { "Attempting:\n  #{current}"}
    existing = activated[current.name]
    if existing || current.name == 'bundler'
      # Force the current
      if current.name == 'bundler' && !existing
        existing = search(DepProxy.new(Gem::Dependency.new('bundler', VERSION), Gem::Platform::RUBY)).first
        raise GemNotFound, %Q{Bundler could not find gem "bundler" (#{VERSION})} unless existing
        existing.required_by << existing
        activated['bundler'] = existing
      end
      if current.requirement.satisfied_by?(existing.version)
        debug { "    * [SUCCESS] Already activated" }
        @errors.delete(existing.name)
        dependencies = existing.activate_platform(current.__platform)
        reqs.concat dependencies
        dependencies.each do |dep|
          next if dep.type == :development
          @gems_size[dep] ||= gems_size(dep)
        end
        depth += 1
        next
      else
        debug { "    * [FAIL] Already activated" }
        @errors[existing.name] = [existing, current]
        conflicts << current.name
        parent = current.required_by.last
        if existing.respond_to?(:required_by)
          parent = handle_conflict(current, states, existing.required_by[-2]) unless other_possible?(parent, states)
        else
          parent = handle_conflict(current, states) unless other_possible?(parent, states)
        end
        if parent.nil? && !conflicts.empty?
          parent = states.reverse.detect { |i| conflicts.include?(i.name) && state_any?(i)}
        end
        raise version_conflict if parent.nil? || parent.name == 'bundler'
        reqs, activated, depth, conflicts = resolve_conflict(parent, states)
      end
    else
      matching_versions = search(current)
      # If we found no versions that match the current requirement
      if matching_versions.empty?
        # If this is a top-level Gemfile requirement
        if current.required_by.empty?
          if base = @base[current.name] and !base.empty?
            version = base.first.version
            message = "You have requested:\n" \
              "  #{current.name} #{current.requirement}\n\n" \
              "The bundle currently has #{current.name} locked at #{version}.\n" \
              "Try running `bundle update #{current.name}`"
          elsif current.source
            name = current.name
            versions = @source_requirements[name][name].map { |s| s.version }
            message  = "Could not find gem '#{current}' in #{current.source}.\n"
            if versions.any?
              message << "Source contains '#{name}' at: #{versions.join(', ')}"
            else
              message << "Source does not contain any versions of '#{current}'"
            end
          else
            message = "Could not find gem '#{current}' "
            if @index.source_types.include?(Bundler::Source::Rubygems)
              message << "in any of the gem sources listed in your Gemfile."
            else
              message << "in the gems available on this machine."
            end
          end
          raise GemNotFound, message
          # This is not a top-level Gemfile requirement
        else
          @errors[current.name] = [nil, current]
          parent = handle_conflict(current, states)
          reqs, activated, depth = resolve_conflict(parent, states)
          next
        end
      end
      state = State.new(reqs.dup, activated.dup, current, matching_versions, depth, conflicts)
      states << state
      requirement = state.possibles.pop
      activate_gem(reqs, activated, requirement, current)
    end
  end
  successify(activated)
end