diff options
Diffstat (limited to 'lib/rubygems/resolver.rb')
-rw-r--r-- | lib/rubygems/resolver.rb | 286 |
1 files changed, 44 insertions, 242 deletions
diff --git a/lib/rubygems/resolver.rb b/lib/rubygems/resolver.rb index ef17d682ac..dcd1ade0d6 100644 --- a/lib/rubygems/resolver.rb +++ b/lib/rubygems/resolver.rb @@ -12,6 +12,7 @@ require 'net/http' # all the requirements. class Gem::Resolver + require 'rubygems/resolver/molinillo' ## # If the DEBUG_RESOLVER environment variable is set then debugging mode is @@ -20,13 +21,6 @@ class Gem::Resolver DEBUG_RESOLVER = !ENV['DEBUG_RESOLVER'].nil? - require 'pp' if DEBUG_RESOLVER - - ## - # Contains all the conflicts encountered while doing resolution - - attr_reader :conflicts - ## # Set to true if all development dependencies should be considered. @@ -110,7 +104,6 @@ class Gem::Resolver @set = set || Gem::Resolver::IndexSet.new @needed = needed - @conflicts = [] @development = false @development_shallow = false @ignore_dependencies = false @@ -153,7 +146,7 @@ class Gem::Resolver return spec, activation_request end - def requests s, act, reqs=nil # :nodoc: + def requests s, act, reqs=[] # :nodoc: return reqs if @ignore_dependencies s.fetch_development_dependencies if @development @@ -165,7 +158,7 @@ class Gem::Resolver next if d.type == :development and @development_shallow and act.parent - reqs.add Gem::Resolver::DependencyRequest.new(d, act) + reqs << Gem::Resolver::DependencyRequest.new(d, act) @stats.requirement! end @@ -176,29 +169,27 @@ class Gem::Resolver reqs end - ## - # Proceed with resolution! Returns an array of ActivationRequest objects. - - def resolve - @conflicts = [] - - needed = Gem::Resolver::RequirementList.new + include Molinillo::UI - @needed.reverse_each do |n| - request = Gem::Resolver::DependencyRequest.new n, nil - - needed.add request - @stats.requirement! - end + def output + @output ||= debug? ? $stdout : File.open('/dev/null', 'w') + end - @stats.record_requirements needed + def debug? + DEBUG_RESOLVER + end - res = resolve_for needed, nil + include Molinillo::SpecificationProvider - raise Gem::DependencyResolutionError, res if - res.kind_of? Gem::Resolver::Conflict + ## + # Proceed with resolution! Returns an array of ActivationRequest objects. - res.to_a + def resolve + locking_dg = Molinillo::DependencyGraph.new + Molinillo::Resolver.new(self, self).resolve(@needed.map { |d| DependencyRequest.new d, nil }, locking_dg).tsort.map(&:payload) + rescue Molinillo::VersionConflict => e + conflict = e.conflicts.values.first + raise Gem::DependencyResolutionError, Conflict.new(conflict.requirement_trees.first.first, conflict.existing, conflict.requirement) end ## @@ -221,232 +212,44 @@ class Gem::Resolver return matching_platform, all end - def handle_conflict(dep, existing) # :nodoc: - # 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, if there was a requester, issue it on the requester's - # request itself. - # Finally, if the existing request has no requester (toplevel) unwind to - # it anyway. - - if existing.others_possible? - conflict = - Gem::Resolver::Conflict.new dep, existing - elsif dep.requester - depreq = dep.requester.request - conflict = - Gem::Resolver::Conflict.new depreq, existing, dep - elsif existing.request.requester.nil? - conflict = - Gem::Resolver::Conflict.new dep, existing - else - raise Gem::DependencyError, "Unable to figure out how to unwind conflict" - 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 # :nodoc: - # The State objects that are used to attempt the activation tree. - states = [] - - while !needed.empty? - @stats.iteration! - - dep = needed.remove - explain :try, [dep, dep.requester ? dep.requester.request : :toplevel] - explain_list(:next5) { needed.next5 } - explain_list(:specs) { Array(specs).map { |x| x.full_name }.sort } - - # 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 - - return conflict unless dep.requester - - explain :conflict, dep, :existing, existing.full_name - - depreq = dep.requester.request - - state = nil - until states.empty? - x = states.pop - - i = existing.request.requester - explain :consider, x.spec.full_name, [depreq.name, dep.name, i ? i.name : :top] - - if x.spec.name == depreq.name or - x.spec.name == dep.name or - (i && (i.name == x.spec.name)) - explain :found, x.spec.full_name - state = x - break - end - end - - return conflict unless state - - @stats.backtracking! - - needed, specs = resolve_for_conflict needed, specs, state - - states << state unless state.possibles.empty? - - next - end - - matching, all = find_possible dep + # Returns the gems in +specs+ that match the local platform. - 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 + def select_local_platforms specs # :nodoc: + specs.select do |spec| + Gem::Platform.installable? spec 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.dup - 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] + def search_for(dependency) + possibles, all = find_possible(dependency) + if !@soft_missing && possibles.empty? + @missing << dependency + exc = Gem::UnsatisfiableDependencyError.new dependency, all + exc.errors = @set.errors + raise exc 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, []) - - @stats.record_depth states - - explain :states, states.map { |s| s.dep } - - needed = requests spec, act, needed - specs = Gem::List.prepend specs, act - - return needed, specs + possibles.sort_by { |s| [s.source, s.version, s.platform == Gem::Platform.local.to_s ? 1 : 0] }. + map { |s| ActivationRequest.new s, dependency, [] } 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 + def dependencies_for(specification) + return [] if @ignore_dependencies + spec = specification.spec + requests(spec, specification) 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 - exc = Gem::UnsatisfiableDependencyError.new dep, platform_mismatch - exc.errors = @set.errors - - raise exc - end + def requirement_satisfied_by?(requirement, activated, spec) + requirement.matches_spec? spec end - ## - # Returns the gems in +specs+ that match the local platform. + def name_for(dependency) + dependency.name + end - def select_local_platforms specs # :nodoc: - specs.select do |spec| - Gem::Platform.installable? spec - end + def allow_missing?(dependency) + @missing << dependency + @soft_missing end end @@ -482,4 +285,3 @@ require 'rubygems/resolver/installed_specification' require 'rubygems/resolver/local_specification' require 'rubygems/resolver/lock_specification' require 'rubygems/resolver/vendor_specification' - |