def resolve(reqs, activated, depth = 0)
def resolve(reqs, activated, depth = 0)
# If the requirements are empty, then we are in a success state. Aka, all
# gem dependencies have been resolved.
safe_throw :success, successify(activated) if reqs.empty?
indicate_progress
debug { print "\e[2J\e[f" ; "==== Iterating ====\n\n" }
# Sort dependencies so that the ones that are easiest to resolve are first.
# Easiest to resolve is defined by:
# 1) Is this gem already activated?
# 2) Do the version requirements include prereleased gems?
# 3) Sort by number of gems available in the source.
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") }
activated = activated.dup
# Pull off the first requirement so that we can resolve it
current = reqs.shift
$stderr.puts "#{' ' * depth}#{current}" if ENV['DEBUG_RESOLVER_TREE']
debug { "Attempting:\n #{current}"}
# Check if the gem has already been activated, if it has, we will make sure
# that the currently activated gem satisfies the requirement.
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)
# Since the current requirement is satisfied, we can continue resolving
# the remaining requirements.
# I have no idea if this is the right way to do it, but let's see if it works
# The current requirement might activate some other platforms, so let's try
# adding those requirements here.
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
resolve(reqs, activated, depth + 1)
else
debug { " * [FAIL] Already activated" }
@errors[existing.name] = [existing, current]
debug { current.required_by.map {|d| " * #{d.name} (#{d.requirement})" }.join("\n") }
# debug { " * All current conflicts:\n" + @errors.keys.map { |c| " - #{c}" }.join("\n") }
# Since the current requirement conflicts with an activated gem, we need
# to backtrack to the current requirement's parent and try another version
# of it (maybe the current requirement won't be present anymore). If the
# current requirement is a root level requirement, we need to jump back to
# where the conflicting gem was activated.
parent = current.required_by.last
# `existing` could not respond to required_by if it is part of the base set
# of specs that was passed to the resolver (aka, instance of LazySpecification)
parent ||= existing.required_by.last if existing.respond_to?(:required_by)
# We track the spot where the current gem was activated because we need
# to keep a list of every spot a failure happened.
if parent && parent.name != 'bundler'
debug { " -> Jumping to: #{parent.name}" }
required_by = existing.respond_to?(:required_by) && existing.required_by.last
safe_throw parent.name, required_by && required_by.name
else
# The original set of dependencies conflict with the base set of specs
# passed to the resolver. This is by definition an impossible resolve.
raise version_conflict
end
end
else
# There are no activated gems for the current requirement, so we are going
# to find all gems that match the current requirement and try them in decending
# order. We also need to keep a set of all conflicts that happen while trying
# this gem. This is so that if no versions work, we can figure out the best
# place to backtrack to.
conflicts = Set.new
# Fetch all gem versions matching the requirement
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]
end
end
matching_versions.reverse_each do |spec_group|
conflict = resolve_requirement(spec_group, current, reqs.dup, activated.dup, depth)
conflicts << conflict if conflict
end
# We throw the conflict up the dependency chain if it has not been
# resolved (in @errors), thus avoiding branches of the tree that have no effect
# on this conflict. Note that if the tree has multiple conflicts, we don't
# care which one we throw, as long as we get out safe
if !current.required_by.empty? && !conflicts.empty?
@errors.reverse_each do |req_name, pair|
if conflicts.include?(req_name)
# Choose the closest pivot in the stack that will affect the conflict
errorpivot = (@stack & [req_name, current.required_by.last.name]).last
debug { " -> Jumping to: #{errorpivot}" }
safe_throw errorpivot, req_name
end
end
end
# If the current requirement is a root level gem and we have conflicts, we
# can figure out the best spot to backtrack to.
if current.required_by.empty? && !conflicts.empty?
# Check the current "catch" stack for the first one that is included in the
# conflicts set. That is where the parent of the conflicting gem was required.
# By jumping back to this spot, we can try other version of the parent of
# the conflicting gem, hopefully finding a combination that activates correctly.
@stack.reverse_each do |savepoint|
if conflicts.include?(savepoint)
debug { " -> Jumping to: #{savepoint}" }
safe_throw savepoint
end
end
end
end
end