lib/rubygems/dependency_resolver.rb in rubygems-update-2.0.17 vs lib/rubygems/dependency_resolver.rb in rubygems-update-2.1.0.rc.1
- old
+ new
@@ -1,575 +1,240 @@
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
+ attr_accessor :soft_missing
+
+ def self.compose_sets *sets
+ Gem::DependencyResolver::ComposedSet.new(*sets)
end
- # 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
+ ##
+ # Provide a DependencyResolver that queries only against the already
+ # installed gems.
- def dependency
- @request.dependency
- end
-
- 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
+ # +set+ is an object that provides where to look for specifications to
+ # satisify the Dependencies. This defaults to IndexSet, which will query
+ # rubygems.org.
- # 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 needed, set = nil
+ @set = set || Gem::DependencyResolver::IndexSet.new
+ @needed = needed
- 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
+ @conflicts = nil
+ @development = false
+ @missing = []
+ @soft_missing = false
+ 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
+ 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
- # 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
+ @set.prefetch reqs
- # Return data for all versions of the gem +name+.
- #
- def versions(name)
- if @data.key?(name)
- return @data[name]
- end
+ reqs
+ end
- uri = @dep_uri + "?gems=#{name}"
- str = Gem::RemoteFetcher.fetcher.fetch_path uri
+ ##
+ # Proceed with resolution! Returns an array of ActivationRequest objects.
- Marshal.load(str).each do |ver|
- @data[ver[:name]] << ver
- end
+ def resolve
+ @conflicts = []
- @data[name]
- end
+ needed = nil
- # 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
+ @needed.reverse_each do |n|
+ needed = Gem::List.new(Gem::DependencyResolver::DependencyRequest.new(n, nil), needed)
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
+ res = resolve_for needed, nil
- @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 spec
- @spec ||= @set.load_spec(@name, @version, @source)
- end
+ def resolve_for needed, specs
+ while needed
+ dep = needed.value
+ needed = needed.tail
- def dependencies
- spec.dependencies
- end
- end
+ # If there is already a spec activated for the requested name...
+ if specs && existing = specs.find { |s| dep.name == s.name }
- # The global rubygems pool represented via the traditional
- # source index.
- #
- class IndexSet
- def initialize
- @f = Gem::SpecFetcher.fetcher
+ # then we're done since this new dep matches the
+ # existing spec.
+ next if dep.matches_spec? existing
- @all = Hash.new { |h,k| h[k] = [] }
+ # There is a conflict! We return the conflict
+ # object which will be seen by the caller and be
+ # handled at the right level.
- 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
-
- # 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
+ # 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
+ @conflicts << conflict
- # 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
+ return conflict
end
- attr_reader :spec, :request
+ # Get a list of all specs that satisfy dep
+ possible = @set.find_all dep
- # Indicate if this activation is one of a set of possible
- # requests for the same Dependency request.
- #
- def others_possible?
- @others_possible
- end
+ case possible.size
+ when 0
+ @missing << dep
- # 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
+ unless @soft_missing
+ # If there are none, then our work here is done.
+ raise Gem::UnsatisfiableDependencyError, dep
end
+ when 1
+ # If there is one, then we just add it to specs
+ # and process the specs dependencies by adding
+ # them to needed.
- Gem.ensure_gem_subdirectories path
+ spec = possible.first
+ act = Gem::DependencyResolver::ActivationRequest.new spec, dep, false
- source.download full_spec, path
- end
+ specs = Gem::List.prepend specs, act
- def ==(other)
- case other
- when Gem::Specification
- @spec == other
- when ActivationRequest
- @spec == other.spec && @request == other.request
- else
- false
- end
- end
+ # 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.
- ##
- # Indicates if the requested gem has already been installed.
+ # Sort them so that we try the highest versions
+ # first.
+ possible = possible.sort_by { |s| [s.source, s.version] }
- def installed?
- this_spec = full_spec
+ # We track the conflicts seen so that we can report them
+ # to help the user figure out how to fix the situation.
+ conflicts = []
- Gem::Specification.any? do |s|
- s == this_spec
- end
- end
- end
+ # 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
- def requests(s, act)
- reqs = []
- s.dependencies.each do |d|
- next unless d.type == :runtime
- reqs << DependencyRequest.new(d, act)
- end
+ # Recursively call #resolve_for with this spec
+ # and add it's dependencies into the picture...
- @set.prefetch(reqs)
+ act = Gem::DependencyResolver::ActivationRequest.new s, dep
- reqs
- end
+ try = requests(s, act, needed)
- # 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
+ res = resolve_for try, Gem::List.prepend(specs, act)
- # If there is already a spec activated for the requested name...
- if existing = specs.find { |s| dep.name == s.name }
+ # While trying to resolve these dependencies, there may
+ # be a conflict!
- # then we're done since this new dep matches the
- # existing spec.
- next if dep.matches_spec? existing
+ 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
- # There is a conflict! We return the conflict
- # object which will be seen by the caller and be
- # handled at the right level.
+ # Otherwise, this is a conflict that we can attempt to fix
+ conflicts << [s, res]
- # 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)
+ # 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)
-
- 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
+ # 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
-
- specs
end
+
+ specs
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'
+