diff options
Diffstat (limited to 'lib/rubygems/resolver.rb')
-rw-r--r-- | lib/rubygems/resolver.rb | 388 |
1 files changed, 388 insertions, 0 deletions
diff --git a/lib/rubygems/resolver.rb b/lib/rubygems/resolver.rb new file mode 100644 index 0000000000..2669cc4f24 --- /dev/null +++ b/lib/rubygems/resolver.rb @@ -0,0 +1,388 @@ +require 'rubygems' +require 'rubygems/dependency' +require 'rubygems/exceptions' +require 'rubygems/util/list' + +require 'uri' +require 'net/http' + +## +# Given a set of Gem::Dependency objects as +needed+ and a way to query the +# set of available specs via +set+, calculates a set of ActivationRequest +# objects which indicate all the specs that should be activated to meet the +# all the requirements. + +class Gem::Resolver + + ## + # Contains all the conflicts encountered while doing resolution + + attr_reader :conflicts + + attr_accessor :development + + attr_reader :missing + + ## + # When a missing dependency, don't stop. Just go on and record what was + # missing. + + attr_accessor :soft_missing + + def self.compose_sets *sets + sets.compact! + + case sets.length + when 0 then + raise ArgumentError, 'one set in the composition must be non-nil' + when 1 then + sets.first + else + Gem::Resolver::ComposedSet.new(*sets) + end + end + + ## + # Provide a Resolver that queries only against the already + # installed gems. + + def self.for_current_gems needed + new needed, Gem::Resolver::CurrentSet.new + end + + ## + # Create Resolver object which will resolve the tree starting + # with +needed+ Dependency objects. + # + # +set+ is an object that provides where to look for specifications to + # satisfy the Dependencies. This defaults to IndexSet, which will query + # rubygems.org. + + def initialize needed, set = nil + @set = set || Gem::Resolver::IndexSet.new + @needed = needed + + @conflicts = [] + @development = false + @missing = [] + @soft_missing = false + end + + DEBUG_RESOLVER = !ENV['DEBUG_RESOLVER'].nil? + + def explain(stage, *data) + if DEBUG_RESOLVER + d = data.map { |x| x.inspect }.join(", ") + STDOUT.printf "%20s %s\n", stage.to_s.upcase, d + end + end + + ## + # Creates an ActivationRequest for the given +dep+ and the last +possible+ + # specification. + # + # Returns the Specification and the ActivationRequest + + def activation_request dep, possible # :nodoc: + spec = possible.pop + + explain :activate, [spec.full_name, possible.size] + + activation_request = + Gem::Resolver::ActivationRequest.new spec, dep, possible + + return spec, activation_request + end + + def requests s, act, reqs=nil + s.dependencies.reverse_each do |d| + next if d.type == :development and not @development + reqs.add Gem::Resolver::DependencyRequest.new(d, act) + end + + @set.prefetch reqs + + reqs + end + + ## + # Proceed with resolution! Returns an array of ActivationRequest objects. + + def resolve + @conflicts = [] + + needed = RequirementList.new + + @needed.reverse_each do |n| + request = Gem::Resolver::DependencyRequest.new n, nil + + needed.add request + end + + res = resolve_for needed, nil + + raise Gem::DependencyResolutionError, res if + res.kind_of? Gem::Resolver::Conflict + + res.to_a + end + + ## + # Finds the State in +states+ that matches the +conflict+ so that we can try + # other possible sets. + # + # If no good candidate is found, the first state is tried. + + def find_conflict_state conflict, states # :nodoc: + rejected = [] + + until states.empty? do + state = states.pop + + explain :consider, state.dep, conflict.failed_dep + + if conflict.for_spec? state.spec + state.conflicts << [state.spec, conflict] + return state + end + + rejected << state + end + + return rejected.shift + ensure + rejected = rejected.concat states + states.replace rejected + end + + ## + # Extracts the specifications that may be able to fulfill +dependency+ and + # returns those that match the local platform and all those that match. + + def find_possible dependency # :nodoc: + all = @set.find_all dependency + matching_platform = select_local_platforms all + + return matching_platform, all + 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 dependency for the activation itself. + # Otherwise, issue it on the requester's request itself. + if existing.others_possible? or existing.request.requester.nil? then + conflict = + Gem::Resolver::Conflict.new dep, existing + else + depreq = dep.requester.request + conflict = + Gem::Resolver::Conflict.new depreq, existing, dep + end + + @conflicts << conflict unless @conflicts.include? 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 DependencyRequest 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, Conflict] hit tried to + # activate the state. + # + State = Struct.new(:needed, :specs, :dep, :spec, :possibles, :conflicts) do + def summary # :nodoc: + nd = needed.map { |s| s.to_s }.sort if nd + + if specs then + ss = specs.map { |s| s.full_name }.sort + ss.unshift ss.length + end + + d = dep.to_s + d << " from #{dep.requester.full_name}" if dep.requester + + ps = possibles.map { |p| p.full_name }.sort + ps.unshift ps.length + + cs = conflicts.map do |(s, c)| + [s.full_name, c.conflicting_dependencies.map { |cd| cd.to_s }] + end + + { :needed => nd, :specs => ss, :dep => d, :spec => spec.full_name, + :possibles => ps, :conflicts => cs } + end + end + + ## + # 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.empty? + dep = needed.remove + explain :try, [dep, dep.requester ? dep.requester.request : :toplevel] + + # If there is already a spec activated for the requested name... + if specs && existing = specs.find { |s| dep.name == s.name } + # then we're done since this new dep matches the existing spec. + next if dep.matches_spec? existing + + conflict = handle_conflict dep, existing + explain :conflict, conflict.explain + + state = find_conflict_state conflict, states + + return conflict unless state + + needed, specs = resolve_for_conflict needed, specs, state + + states << state unless state.possibles.empty? + + next + end + + matching, all = find_possible dep + + case matching.size + when 0 + resolve_for_zero dep, all + when 1 + needed, specs = + resolve_for_single needed, specs, dep, matching + else + needed, specs = + resolve_for_multiple needed, specs, states, dep, matching + end + end + + specs + end + + ## + # Rewinds +needed+ and +specs+ to a previous state in +state+ for a conflict + # between +dep+ and +existing+. + + def resolve_for_conflict needed, specs, state # :nodoc: + # We exhausted the possibles so it's definitely not going to work out, + # bail out. + raise Gem::ImpossibleDependenciesError.new state.dep, state.conflicts if + state.possibles.empty? + + # Retry resolution with this spec and add it's dependencies + spec, act = activation_request state.dep, state.possibles + + needed = requests spec, act, state.needed + specs = Gem::List.prepend state.specs, act + + return needed, specs + end + + ## + # There are multiple +possible+ specifications for this +dep+. Updates + # +needed+, +specs+ and +states+ for further resolution of the +possible+ + # choices. + + def resolve_for_multiple needed, specs, states, dep, possible # :nodoc: + # Sort them so that we try the highest versions first. + possible = possible.sort_by do |s| + [s.source, s.version, s.platform == Gem::Platform::RUBY ? -1 : 1] + end + + spec, act = activation_request dep, possible + + # We 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 conflict resolution possible. + states << State.new(needed.dup, specs, dep, spec, possible, []) + + explain :states, states.map { |s| s.dep } + + needed = requests spec, act, needed + specs = Gem::List.prepend specs, act + + return needed, specs + end + + ## + # Add the spec from the +possible+ list to +specs+ and process the spec's + # dependencies by adding them to +needed+. + + def resolve_for_single needed, specs, dep, possible # :nodoc: + spec, act = activation_request dep, possible + + specs = Gem::List.prepend specs, act + + # Put the deps for at the beginning of needed + # rather than the end to match the depth first + # searching done by the multiple case code below. + # + # This keeps the error messages consistent. + needed = requests spec, act, needed + + return needed, specs + end + + ## + # When there are no possible specifications for +dep+ our work is done. + + def resolve_for_zero dep, platform_mismatch # :nodoc: + @missing << dep + + unless @soft_missing + raise Gem::UnsatisfiableDependencyError.new(dep, platform_mismatch) + end + end + + ## + # Returns the gems in +specs+ that match the local platform. + + def select_local_platforms specs # :nodoc: + specs.select do |spec| + Gem::Platform.installable? spec + end + end + +end + +## +# TODO remove in RubyGems 3 + +Gem::DependencyResolver = Gem::Resolver # :nodoc: + +require 'rubygems/resolver/activation_request' +require 'rubygems/resolver/conflict' +require 'rubygems/resolver/dependency_request' +require 'rubygems/resolver/requirement_list' + +require 'rubygems/resolver/set' +require 'rubygems/resolver/api_set' +require 'rubygems/resolver/composed_set' +require 'rubygems/resolver/best_set' +require 'rubygems/resolver/current_set' +require 'rubygems/resolver/git_set' +require 'rubygems/resolver/index_set' +require 'rubygems/resolver/installer_set' +require 'rubygems/resolver/lock_set' +require 'rubygems/resolver/vendor_set' + +require 'rubygems/resolver/specification' +require 'rubygems/resolver/spec_specification' +require 'rubygems/resolver/api_specification' +require 'rubygems/resolver/git_specification' +require 'rubygems/resolver/index_specification' +require 'rubygems/resolver/installed_specification' +require 'rubygems/resolver/vendor_specification' + |