diff options
Diffstat (limited to 'lib/rubygems/dependency_resolver.rb')
| -rw-r--r-- | lib/rubygems/dependency_resolver.rb | 562 |
1 files changed, 562 insertions, 0 deletions
diff --git a/lib/rubygems/dependency_resolver.rb b/lib/rubygems/dependency_resolver.rb new file mode 100644 index 0000000000..b841674d43 --- /dev/null +++ b/lib/rubygems/dependency_resolver.rb @@ -0,0 +1,562 @@ +require 'rubygems' +require 'rubygems/dependency' +require 'rubygems/exceptions' + +require 'uri' +require 'net/http' + +module Gem + + # 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 + + super "unable to resolve conflicting dependencies '#{a}' and '#{b}'" + end + + attr_reader :conflict + + def conflicting_dependencies + @conflict.conflicting_dependencies + end + end + + # 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}'" + + @dependency = dep + end + + attr_reader :dependency + 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 + + def dependency + @request.dependency + end + + attr_reader :conflicts + 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. + # + 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 + 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 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] = [] } + end + + # Return data for all versions of the gem +name+. + # + def versions(name) + if @data.key?(name) + return @data[name] + end + + u = URI.parse "http://rubygems.org/api/v1/dependencies?gems=#{name}" + str = Net::HTTP.get(u) + + 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? + + u = URI.parse "http://rubygems.org/api/v1/dependencies?gems=#{needed.join ','}" + str = Net::HTTP.get(u) + + 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 + + # 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.dep && @requester == other.requester + else + false + 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 + + 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 + + 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 + + ## + # 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 + + 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) + else + depreq = existing.request.requester.request + conflict = DependencyConflict.new(depreq, existing, dep) + 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 + end + + specs + end + end +end |