dependency_resolver.rb [plain text]
require 'rubygems'
require 'rubygems/dependency'
require 'rubygems/exceptions'
require 'uri'
require 'net/http'
module Gem
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
class UnsatisfiableDepedencyError < Gem::Exception
def initialize(dep)
super "unable to find any gem matching dependency '#{dep}'"
@dependency = dep
end
attr_reader :dependency
end
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
class DependencyResolver
class APISpecification
attr_reader :set
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
class APISet
def initialize
@data = Hash.new { |h,k| h[k] = [] }
@dep_uri = URI 'https://rubygems.org/api/v1/dependencies'
end
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
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
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
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
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
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
def prefetch(gems)
end
def load_spec(name, ver, source)
key = "#{name}-#{ver}"
@specs[key] ||= source.fetch_spec(Gem::NameTuple.new(name, ver))
end
end
class CurrentSet
def find_all(req)
req.dependency.matching_specs
end
def prefetch(gems)
end
end
def initialize(needed, set=IndexSet.new)
@set = set || IndexSet.new @needed = needed
@conflicts = nil
end
def self.for_current_gems(needed)
new needed, CurrentSet.new
end
attr_reader :conflicts
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
class DependencyConflict
def initialize(dependency, activated, failed_dep=dependency)
@dependency = dependency
@activated = activated
@failed_dep = failed_dep
end
attr_reader :dependency, :activated
def requester
@failed_dep.requester
end
def for_spec?(spec)
@dependency.name == spec.name
end
def conflicting_dependencies
[@failed_dep.dependency, @activated.request.dependency]
end
end
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
end
end
class ActivationRequest
def initialize(spec, req, others_possible=true)
@spec = spec
@request = req
@others_possible = others_possible
end
attr_reader :spec, :request
def others_possible?
@others_possible
end
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
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
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
def resolve_for(needed, specs)
until needed.empty?
dep = needed.shift
if existing = specs.find { |s| dep.name == s.name }
next if dep.matches_spec? existing
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
possible = @set.find_all(dep)
case possible.size
when 0
raise UnsatisfiableDepedencyError.new(dep)
when 1
spec = possible.first
act = ActivationRequest.new(spec, dep, false)
specs << act
needed = requests(spec, act) + needed
else
possible = possible.sort_by { |s| s.version }
conflicts = []
until possible.empty?
s = possible.pop
act = ActivationRequest.new(s, dep)
try = requests(s, act) + needed
res = resolve_for(try, specs + [act])
if res.kind_of? DependencyConflict
return res unless res.for_spec? s
conflicts << [s, res]
possible.delete_if { |x| !res.dependency.matches_spec? x }
else
return res
end
end
raise ImpossibleDependenciesError.new(dep, conflicts)
end
end
specs
end
end
end