diff options
Diffstat (limited to 'lib/rubygems/dependency_resolver.rb')
| -rw-r--r-- | lib/rubygems/dependency_resolver.rb | 721 |
1 files changed, 200 insertions, 521 deletions
diff --git a/lib/rubygems/dependency_resolver.rb b/lib/rubygems/dependency_resolver.rb index 66f55eb9ad..abce692920 100644 --- a/lib/rubygems/dependency_resolver.rb +++ b/lib/rubygems/dependency_resolver.rb @@ -1,575 +1,254 @@ require 'rubygems' require 'rubygems/dependency' require 'rubygems/exceptions' +require 'rubygems/util/list' require 'uri' require 'net/http' -module Gem +## +# 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. - # Raised when a DependencyConflict reaches the toplevel. - # Indicates which dependencies were incompatible. - # - class DependencyResolutionError < Gem::Exception - def initialize(conflict) - @conflict = conflict - a, b = conflicting_dependencies +class Gem::DependencyResolver - super "unable to resolve conflicting dependencies '#{a}' and '#{b}'" - end + ## + # Contains all the conflicts encountered while doing resolution - attr_reader :conflict + attr_reader :conflicts - def conflicting_dependencies - @conflict.conflicting_dependencies - end - end + attr_accessor :development - # Raised when a dependency requests a gem for which there is - # no spec. - # - class UnsatisfiableDepedencyError < Gem::Exception - def initialize(dep) - super "unable to find any gem matching dependency '#{dep}'" + attr_reader :missing - @dependency = dep - end + ## + # When a missing dependency, don't stop. Just go on and record what was + # missing. - attr_reader :dependency - end + attr_accessor :soft_missing - # Raised when dependencies conflict and create the inability to - # find a valid possible spec for a request. - # - class ImpossibleDependenciesError < Gem::Exception - def initialize(request, conflicts) - s = conflicts.size == 1 ? "" : "s" - super "detected #{conflicts.size} conflict#{s} with dependency '#{request.dependency}'" - @request = request - @conflicts = conflicts - end + def self.compose_sets *sets + Gem::DependencyResolver::ComposedSet.new(*sets) + end - def dependency - @request.dependency - end + ## + # Provide a DependencyResolver that queries only against the already + # installed gems. - attr_reader :conflicts + def self.for_current_gems needed + new needed, Gem::DependencyResolver::CurrentSet.new end - # 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. + ## + # Create DependencyResolver object which will resolve the tree starting + # with +needed+ Depedency objects. # - class DependencyResolver - - # Represents a specification retrieved via the rubygems.org - # API. This is used to avoid having to load the full - # Specification object when all we need is the name, version, - # and dependencies. - # - class APISpecification - attr_reader :set # :nodoc: - - def initialize(set, api_data) - @set = set - @name = api_data[:name] - @version = Gem::Version.new api_data[:number] - @dependencies = api_data[:dependencies].map do |name, ver| - Gem::Dependency.new name, ver.split(/\s*,\s*/) - end - end - - attr_reader :name, :version, :dependencies - - def == other # :nodoc: - self.class === other and - @set == other.set and - @name == other.name and - @version == other.version and - @dependencies == other.dependencies - end - - def full_name - "#{@name}-#{@version}" - end - end - - # The global rubygems pool, available via the rubygems.org API. - # Returns instances of APISpecification. - # - class APISet - def initialize - @data = Hash.new { |h,k| h[k] = [] } - @dep_uri = URI 'https://rubygems.org/api/v1/dependencies' - end - - # Return data for all versions of the gem +name+. - # - def versions(name) - if @data.key?(name) - return @data[name] - end - - uri = @dep_uri + "?gems=#{name}" - str = Gem::RemoteFetcher.fetcher.fetch_path uri - - Marshal.load(str).each do |ver| - @data[ver[:name]] << ver - end - - @data[name] - end - - # Return an array of APISpecification objects matching - # DependencyRequest +req+. - # - def find_all(req) - res = [] - - versions(req.name).each do |ver| - if req.dependency.match? req.name, ver[:number] - res << APISpecification.new(self, ver) - end - end - - res - end - - # A hint run by the resolver to allow the Set to fetch - # data for DependencyRequests +reqs+. - # - def prefetch(reqs) - names = reqs.map { |r| r.dependency.name } - needed = names.find_all { |d| !@data.key?(d) } - - return if needed.empty? - - uri = @dep_uri + "?gems=#{needed.sort.join ','}" - str = Gem::RemoteFetcher.fetcher.fetch_path uri - - Marshal.load(str).each do |ver| - @data[ver[:name]] << ver - end - end - end - - # Represents a possible Specification object returned - # from IndexSet. Used to delay needed to download full - # Specification objects when only the +name+ and +version+ - # are needed. - # - class IndexSpecification - def initialize(set, name, version, source, plat) - @set = set - @name = name - @version = version - @source = source - @platform = plat - - @spec = nil - end - - attr_reader :name, :version, :source - - def full_name - "#{@name}-#{@version}" - end - - def spec - @spec ||= @set.load_spec(@name, @version, @source) - end - - def dependencies - spec.dependencies - end - end - - # The global rubygems pool represented via the traditional - # source index. - # - class IndexSet - def initialize - @f = Gem::SpecFetcher.fetcher - - @all = Hash.new { |h,k| h[k] = [] } - - list, _ = @f.available_specs(:released) - list.each do |uri, specs| - specs.each do |n| - @all[n.name] << [uri, n] - end - end - - @specs = {} - end - - # Return an array of IndexSpecification objects matching - # DependencyRequest +req+. - # - def find_all(req) - res = [] - - name = req.dependency.name - - @all[name].each do |uri, n| - if req.dependency.match? n - res << IndexSpecification.new(self, n.name, n.version, - uri, n.platform) - end - end - - res - end - - # No prefetching needed since we load the whole index in - # initially. - # - def prefetch(gems) - end - - # Called from IndexSpecification to get a true Specification - # object. - # - def load_spec(name, ver, source) - key = "#{name}-#{ver}" - @specs[key] ||= source.fetch_spec(Gem::NameTuple.new(name, ver)) - end - end - - # A set which represents the installed gems. Respects - # all the normal settings that control where to look - # for installed gems. - # - class CurrentSet - def find_all(req) - req.dependency.matching_specs - end - - def prefetch(gems) - end - end + # +set+ is an object that provides where to look for specifications to + # satisify the Dependencies. This defaults to IndexSet, which will query + # rubygems.org. + + def initialize needed, set = nil + @set = set || Gem::DependencyResolver::IndexSet.new + @needed = needed + + @conflicts = nil + @development = false + @missing = [] + @soft_missing = false + end - # Create DependencyResolver object which will resolve - # the tree starting with +needed+ Depedency objects. - # - # +set+ is an object that provides where to look for - # specifications to satisify the Dependencies. This - # defaults to IndexSet, which will query rubygems.org. - # - def initialize(needed, set=IndexSet.new) - @set = set || IndexSet.new # Allow nil to mean IndexSet - @needed = needed - - @conflicts = nil + def requests s, act, reqs=nil + s.dependencies.reverse_each do |d| + next if d.type == :development and not @development + reqs = Gem::List.new Gem::DependencyResolver::DependencyRequest.new(d, act), reqs end - # Provide a DependencyResolver that queries only against - # the already installed gems. - # - def self.for_current_gems(needed) - new needed, CurrentSet.new - end + @set.prefetch reqs - # Contains all the conflicts encountered while doing resolution - # - attr_reader :conflicts + reqs + end - # Proceed with resolution! Returns an array of ActivationRequest - # objects. - # - def resolve - @conflicts = [] + ## + # Proceed with resolution! Returns an array of ActivationRequest objects. - needed = @needed.map { |n| DependencyRequest.new(n, nil) } + def resolve + @conflicts = [] - res = resolve_for needed, [] + needed = nil - if res.kind_of? DependencyConflict - raise DependencyResolutionError.new(res) - end + @needed.reverse_each do |n| + request = Gem::DependencyResolver::DependencyRequest.new n, nil - res + needed = Gem::List.new request, needed end - # Used internally to indicate that a dependency conflicted - # with a spec that would be activated. - # - class DependencyConflict - def initialize(dependency, activated, failed_dep=dependency) - @dependency = dependency - @activated = activated - @failed_dep = failed_dep - end - - attr_reader :dependency, :activated + res = resolve_for needed, nil - # Return the Specification that listed the dependency - # - def requester - @failed_dep.requester - end - - def for_spec?(spec) - @dependency.name == spec.name - end + raise Gem::DependencyResolutionError, res if + res.kind_of? Gem::DependencyResolver::DependencyConflict - # Return the 2 dependency objects that conflicted - # - def conflicting_dependencies - [@failed_dep.dependency, @activated.request.dependency] - end - end - - # Used Internally. Wraps a Depedency object to also track - # which spec contained the Dependency. - # - class DependencyRequest - def initialize(dep, act) - @dependency = dep - @requester = act - end - - attr_reader :dependency, :requester - - def name - @dependency.name - end - - def matches_spec?(spec) - @dependency.matches_spec? spec - end - - def to_s - @dependency.to_s - end + res.to_a + end - def ==(other) - case other - when Dependency - @dependency == other - when DependencyRequest - @dependency == other.dependency && @requester == other.requester + ## + # 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 + while needed + dep = needed.value + needed = needed.tail + + # 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 + + # 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 - false + depreq = existing.request.requester.request + conflict = + Gem::DependencyResolver::DependencyConflict.new depreq, existing, dep end - end - end - - # Specifies a Specification object that should be activated. - # Also contains a dependency that was used to introduce this - # activation. - # - class ActivationRequest - def initialize(spec, req, others_possible=true) - @spec = spec - @request = req - @others_possible = others_possible - end - - attr_reader :spec, :request - - # Indicate if this activation is one of a set of possible - # requests for the same Dependency request. - # - def others_possible? - @others_possible - end - - # Return the ActivationRequest that contained the dependency - # that we were activated for. - # - def parent - @request.requester - end + @conflicts << conflict - def name - @spec.name + return conflict end - def full_name - @spec.full_name - end - - def version - @spec.version - end - - def full_spec - Gem::Specification === @spec ? @spec : @spec.spec - end - - def download(path) - if @spec.respond_to? :source - source = @spec.source - else - source = Gem.sources.first - end - - Gem.ensure_gem_subdirectories path + # Get a list of all specs that satisfy dep and platform + possible = @set.find_all dep + possible = select_local_platforms possible - source.download full_spec, path - end + case possible.size + when 0 + @missing << dep - def ==(other) - case other - when Gem::Specification - @spec == other - when ActivationRequest - @spec == other.spec && @request == other.request - else - false + unless @soft_missing + # If there are none, then our work here is done. + raise Gem::UnsatisfiableDependencyError, dep end - end - - ## - # Indicates if the requested gem has already been installed. - - def installed? - this_spec = full_spec - - Gem::Specification.any? do |s| - s == this_spec + when 1 + # If there is one, then we just add it to specs + # and process the specs dependencies by adding + # them to needed. + + spec = possible.first + act = Gem::DependencyResolver::ActivationRequest.new spec, dep, false + + 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) + else + # There are multiple specs for this dep. This is + # the case that this class is built to handle. + + # 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 - end - end - def requests(s, act) - reqs = [] - s.dependencies.each do |d| - next unless d.type == :runtime - reqs << DependencyRequest.new(d, act) - end - - @set.prefetch(reqs) - - reqs - 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) - until needed.empty? - dep = needed.shift - - # If there is already a spec activated for the requested name... - if 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 - - # 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 = DependencyConflict.new(dep, existing) + # 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. + # + # We use an until loop rather than #reverse_each + # 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) + + res = resolve_for try, Gem::List.prepend(specs, act) + + # While trying to resolve these dependencies, there may + # be a conflict! + + 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 + + # 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 - depreq = existing.request.requester.request - conflict = DependencyConflict.new(depreq, existing, dep) + # No conflict, return the specs + return res end - @conflicts << conflict - - return conflict end - # Get a list of all specs that satisfy dep - possible = @set.find_all(dep) + # 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) + end + end - case possible.size - when 0 - # If there are none, then our work here is done. - raise UnsatisfiableDepedencyError.new(dep) - when 1 - # If there is one, then we just add it to specs - # and process the specs dependencies by adding - # them to needed. - - spec = possible.first - act = ActivationRequest.new(spec, dep, false) - - 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 - else - # There are multiple specs for this dep. This is - # the case that this class is built to handle. - - # Sort them so that we try the highest versions - # first. - possible = possible.sort_by { |s| s.version } - - # 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. - # - # We use an until loop rather than #reverse_each - # 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 = ActivationRequest.new(s, dep) - - try = requests(s, act) + needed - - res = resolve_for(try, specs + [act]) - - # While trying to resolve these dependencies, there may - # be a conflict! - - if res.kind_of? 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 - - # 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 + specs + 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 ImpossibleDependenciesError.new(dep, conflicts) - end - end + ## + # Returns the gems in +specs+ that match the local platform. - specs + def select_local_platforms specs # :nodoc: + specs.select do |spec| + Gem::Platform.match spec.platform end end + end + +require 'rubygems/dependency_resolver/api_set' +require 'rubygems/dependency_resolver/api_specification' +require 'rubygems/dependency_resolver/activation_request' +require 'rubygems/dependency_resolver/composed_set' +require 'rubygems/dependency_resolver/current_set' +require 'rubygems/dependency_resolver/dependency_conflict' +require 'rubygems/dependency_resolver/dependency_request' +require 'rubygems/dependency_resolver/index_set' +require 'rubygems/dependency_resolver/index_specification' +require 'rubygems/dependency_resolver/installed_specification' +require 'rubygems/dependency_resolver/installer_set' + |