diff options
Diffstat (limited to 'lib/rubygems/dependency_resolver.rb')
| -rw-r--r-- | lib/rubygems/dependency_resolver.rb | 721 |
1 files changed, 521 insertions, 200 deletions
diff --git a/lib/rubygems/dependency_resolver.rb b/lib/rubygems/dependency_resolver.rb index abce692920..66f55eb9ad 100644 --- a/lib/rubygems/dependency_resolver.rb +++ b/lib/rubygems/dependency_resolver.rb @@ -1,254 +1,575 @@ 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. +module Gem -class Gem::DependencyResolver - - ## - # Contains all the conflicts encountered while doing resolution + # 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 - attr_reader :conflicts + super "unable to resolve conflicting dependencies '#{a}' and '#{b}'" + end - attr_accessor :development + attr_reader :conflict - attr_reader :missing + def conflicting_dependencies + @conflict.conflicting_dependencies + end + end - ## - # When a missing dependency, don't stop. Just go on and record what was - # missing. + # 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_accessor :soft_missing + @dependency = dep + end - def self.compose_sets *sets - Gem::DependencyResolver::ComposedSet.new(*sets) + attr_reader :dependency end - ## - # Provide a DependencyResolver that queries only against the already - # installed gems. + # 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 dependency + @request.dependency + end - def self.for_current_gems needed - new needed, Gem::DependencyResolver::CurrentSet.new + attr_reader :conflicts end - ## - # Create DependencyResolver object which will resolve the tree starting - # with +needed+ Depedency objects. + # 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. # - # +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 + 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 - 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 + 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 - @set.prefetch reqs + # 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 - reqs - end + # Return data for all versions of the gem +name+. + # + def versions(name) + if @data.key?(name) + return @data[name] + end - ## - # Proceed with resolution! Returns an array of ActivationRequest objects. + uri = @dep_uri + "?gems=#{name}" + str = Gem::RemoteFetcher.fetcher.fetch_path uri - def resolve - @conflicts = [] + Marshal.load(str).each do |ver| + @data[ver[:name]] << ver + end - needed = nil + @data[name] + end - @needed.reverse_each do |n| - request = Gem::DependencyResolver::DependencyRequest.new n, nil + # Return an array of APISpecification objects matching + # DependencyRequest +req+. + # + def find_all(req) + res = [] - needed = Gem::List.new request, needed + 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 - res = resolve_for needed, nil + # 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 - raise Gem::DependencyResolutionError, res if - res.kind_of? Gem::DependencyResolver::DependencyConflict + attr_reader :name, :version, :source - res.to_a - end + def full_name + "#{@name}-#{@version}" + 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 - 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 - depreq = existing.request.requester.request - conflict = - Gem::DependencyResolver::DependencyConflict.new depreq, existing, dep + 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 - @conflicts << conflict - return conflict + @specs = {} end - # Get a list of all specs that satisfy dep and platform - possible = @set.find_all dep - possible = select_local_platforms possible + # Return an array of IndexSpecification objects matching + # DependencyRequest +req+. + # + def find_all(req) + res = [] - case possible.size - when 0 - @missing << dep + name = req.dependency.name - unless @soft_missing - # If there are none, then our work here is done. - raise Gem::UnsatisfiableDependencyError, dep + @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 + + # 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 + end + + # Provide a DependencyResolver that queries only against + # the already installed gems. + # + def self.for_current_gems(needed) + new needed, CurrentSet.new + end + + # Contains all the conflicts encountered while doing resolution + # + attr_reader :conflicts + + # Proceed with resolution! Returns an array of ActivationRequest + # objects. + # + def resolve + @conflicts = [] + + needed = @needed.map { |n| DependencyRequest.new(n, nil) } + + res = resolve_for needed, [] + + if res.kind_of? DependencyConflict + raise DependencyResolutionError.new(res) + end + + res + 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 + + # Return the Specification that listed the dependency + # + def requester + @failed_dep.requester + end + + def for_spec?(spec) + @dependency.name == spec.name + end + + # 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 + + def ==(other) + case other + when Dependency + @dependency == other + when DependencyRequest + @dependency == other.dependency && @requester == other.requester + else + false end - 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 + + # 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 + + def name + @spec.name + 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 - # 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 - # No conflict, return the specs - return res - end + Gem.ensure_gem_subdirectories path + + source.download full_spec, path + end + + def ==(other) + case other + when Gem::Specification + @spec == other + when ActivationRequest + @spec == other.spec && @request == other.request + else + false end + 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 Gem::ImpossibleDependenciesError.new(dep, conflicts) + ## + # Indicates if the requested gem has already been installed. + + def installed? + this_spec = full_spec + + Gem::Specification.any? do |s| + s == this_spec + end end end - specs - end + def requests(s, act) + reqs = [] + s.dependencies.each do |d| + next unless d.type == :runtime + reqs << DependencyRequest.new(d, act) + end - ## - # Returns the gems in +specs+ that match the local platform. + @set.prefetch(reqs) - def select_local_platforms specs # :nodoc: - specs.select do |spec| - Gem::Platform.match spec.platform + reqs end - 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) + 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) + else + depreq = existing.request.requester.request + conflict = DependencyConflict.new(depreq, existing, dep) + end + @conflicts << conflict -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' + return conflict + end + + # Get a list of all specs that satisfy dep + possible = @set.find_all(dep) + 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 + + # 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 + + specs + end + end +end |