diff options
Diffstat (limited to 'lib/rubygems/resolver')
49 files changed, 501 insertions, 2389 deletions
diff --git a/lib/rubygems/resolver/activation_request.rb b/lib/rubygems/resolver/activation_request.rb index 135d75d6bc..5c722001b1 100644 --- a/lib/rubygems/resolver/activation_request.rb +++ b/lib/rubygems/resolver/activation_request.rb @@ -1,10 +1,10 @@ # frozen_string_literal: true + ## # Specifies a Specification object that should be activated. Also contains a # dependency that was used to introduce this activation. class Gem::Resolver::ActivationRequest - ## # The parent request for this activation request. @@ -18,27 +18,31 @@ class Gem::Resolver::ActivationRequest ## # Creates a new ActivationRequest that will activate +spec+. The parent # +request+ is used to provide diagnostics in case of conflicts. - # - # +others_possible+ indicates that other specifications may also match this - # activation request. - def initialize spec, request, others_possible = true + def initialize(spec, request) @spec = spec @request = request - @others_possible = others_possible end - def == other # :nodoc: + def ==(other) # :nodoc: case other when Gem::Specification @spec == other when Gem::Resolver::ActivationRequest - @spec == other.spec && @request == other.request + @spec == other.spec else false end end + def eql?(other) + self == other + end + + def hash + @spec.hash + end + ## # Is this activation request for a development dependency? @@ -49,17 +53,15 @@ class Gem::Resolver::ActivationRequest ## # Downloads a gem at +path+ and returns the file path. - def download path + def download(path) Gem.ensure_gem_subdirectories path if @spec.respond_to? :sources exception = nil - path = @spec.sources.find{ |source| - begin - source.download full_spec, path - rescue exception - end - } + path = @spec.sources.find do |source| + source.download full_spec, path + rescue exception + end return path if path raise exception if exception @@ -77,7 +79,7 @@ class Gem::Resolver::ActivationRequest # The full name of the specification to be activated. def full_name - @spec.full_name + name_tuple.full_name end alias_method :to_s, :full_name @@ -90,22 +92,7 @@ class Gem::Resolver::ActivationRequest end def inspect # :nodoc: - others = - case @others_possible - when true then # TODO remove at RubyGems 3 - ' (others possible)' - when false then # TODO remove at RubyGems 3 - nil - else - unless @others_possible.empty? then - others = @others_possible.map { |s| s.full_name } - " (others possible: #{others.join ', '})" - end - end - - '#<%s for %p from %s%s>' % [ - self.class, @spec, @request, others - ] + format("#<%s for %p from %s>", self.class, @spec, @request) end ## @@ -119,7 +106,7 @@ class Gem::Resolver::ActivationRequest this_spec = full_spec Gem::Specification.any? do |s| - s == this_spec + s == this_spec && s.base_dir == this_spec.base_dir end end end @@ -132,19 +119,6 @@ class Gem::Resolver::ActivationRequest end ## - # Indicate if this activation is one of a set of possible - # requests for the same Dependency request. - - def others_possible? - case @others_possible - when true, false then - @others_possible - else - not @others_possible.empty? - end - end - - ## # Return the ActivationRequest that contained the dependency # that we were activated for. @@ -152,27 +126,14 @@ class Gem::Resolver::ActivationRequest @request.requester end - def pretty_print q # :nodoc: - q.group 2, '[Activation request', ']' do + def pretty_print(q) # :nodoc: + q.group 2, "[Activation request", "]" do q.breakable q.pp @spec q.breakable - q.text ' for ' + q.text " for " q.pp @request - - case @others_possible - when false then - when true then - q.breakable - q.text 'others possible' - else - unless @others_possible.empty? then - q.breakable - q.text 'others ' - q.pp @others_possible.map { |s| s.full_name } - end - end end end @@ -183,4 +144,16 @@ class Gem::Resolver::ActivationRequest @spec.version end + ## + # The platform of this activation request's specification + + def platform + @spec.platform + end + + private + + def name_tuple + @name_tuple ||= Gem::NameTuple.new(name, version, platform) + end end diff --git a/lib/rubygems/resolver/api_set.rb b/lib/rubygems/resolver/api_set.rb index ee3046af63..3f443519d8 100644 --- a/lib/rubygems/resolver/api_set.rb +++ b/lib/rubygems/resolver/api_set.rb @@ -1,12 +1,14 @@ # frozen_string_literal: true + ## -# The global rubygems pool, available via the rubygems.org API. +# The global rubygems pool, available via the Compact Index API. # Returns instances of APISpecification. class Gem::Resolver::APISet < Gem::Resolver::Set + autoload :GemParser, File.expand_path("api_set/gem_parser", __dir__) ## - # The URI for the dependency API this APISet uses. + # The URI for the Compact Index API this APISet uses. attr_reader :dep_uri # :nodoc: @@ -21,19 +23,19 @@ class Gem::Resolver::APISet < Gem::Resolver::Set attr_reader :uri ## - # Creates a new APISet that will retrieve gems from +uri+ using the RubyGems - # API URL +dep_uri+ which is described at - # http://guides.rubygems.org/rubygems-org-api + # Creates a new APISet that will retrieve gems from +uri+ using the Compact + # Index API URL +dep_uri+ which is described at + # https://guides.rubygems.org/rubygems-org-compact-index-api - def initialize dep_uri = 'https://rubygems.org/api/v1/dependencies' + def initialize(dep_uri = "https://index.rubygems.org/info/") super() - dep_uri = URI dep_uri unless URI === dep_uri # for ruby 1.8 + dep_uri = Gem::URI dep_uri unless Gem::URI === dep_uri @dep_uri = dep_uri - @uri = dep_uri + '../..' + @uri = dep_uri + ".." - @data = Hash.new { |h,k| h[k] = [] } + @data = Hash.new {|h,k| h[k] = [] } @source = Gem::Source.new @uri @to_fetch = [] @@ -43,7 +45,7 @@ class Gem::Resolver::APISet < Gem::Resolver::Set # Return an array of APISpecification objects matching # DependencyRequest +req+. - def find_all req + def find_all(req) res = [] return res unless @remote @@ -53,7 +55,7 @@ class Gem::Resolver::APISet < Gem::Resolver::Set end versions(req.name).each do |ver| - if req.dependency.match? req.name, ver[:number] + if req.dependency.match? req.name, ver[:number], @prerelease res << Gem::Resolver::APISpecification.new(self, ver) end end @@ -65,41 +67,30 @@ class Gem::Resolver::APISet < Gem::Resolver::Set # A hint run by the resolver to allow the Set to fetch # data for DependencyRequests +reqs+. - def prefetch reqs + def prefetch(reqs) return unless @remote - names = reqs.map { |r| r.dependency.name } + names = reqs.map {|r| r.dependency.name } needed = names - @data.keys - @to_fetch @to_fetch += needed end def prefetch_now # :nodoc: - needed, @to_fetch = @to_fetch, [] - - uri = @dep_uri + "?gems=#{needed.sort.join ','}" - str = Gem::RemoteFetcher.fetcher.fetch_path uri - - loaded = [] - - Marshal.load(str).each do |ver| - name = ver[:name] - - @data[name] << ver - loaded << name - end + needed = @to_fetch + @to_fetch = [] - (needed - loaded).each do |missing| - @data[missing] = [] + needed.sort.each do |name| + versions(name) end end - def pretty_print q # :nodoc: - q.group 2, '[APISet', ']' do + def pretty_print(q) # :nodoc: + q.group 2, "[APISet", "]" do q.breakable q.text "URI: #{@dep_uri}" q.breakable - q.text 'gem names:' + q.text "gem names:" q.pp @data.keys end end @@ -107,20 +98,42 @@ class Gem::Resolver::APISet < Gem::Resolver::Set ## # Return data for all versions of the gem +name+. - def versions name # :nodoc: + def versions(name) # :nodoc: if @data.key?(name) return @data[name] end - uri = @dep_uri + "?gems=#{name}" - str = Gem::RemoteFetcher.fetcher.fetch_path uri + uri = @dep_uri + name + + begin + str = Gem::RemoteFetcher.fetcher.fetch_path uri + rescue Gem::RemoteFetcher::FetchError + @data[name] = [] + else + lines(str).each do |ver| + number, platform, dependencies, requirements = parse_gem(ver) - Marshal.load(str).each do |ver| - @data[ver[:name]] << ver + platform ||= "ruby" + dependencies = dependencies.map {|dep_name, reqs| [dep_name, reqs.join(", ")] } + requirements = requirements.map {|req_name, reqs| [req_name.to_sym, reqs] }.to_h + + @data[name] << { name: name, number: number, platform: platform, dependencies: dependencies, requirements: requirements } + end end @data[name] end -end + private + def lines(str) + lines = str.split("\n") + header = lines.index("---") + header ? lines[header + 1..-1] : lines + end + + def parse_gem(string) + @gem_parser ||= GemParser.new + @gem_parser.parse(string) + end +end diff --git a/lib/rubygems/resolver/api_set/gem_parser.rb b/lib/rubygems/resolver/api_set/gem_parser.rb new file mode 100644 index 0000000000..4d827f4980 --- /dev/null +++ b/lib/rubygems/resolver/api_set/gem_parser.rb @@ -0,0 +1,21 @@ +# frozen_string_literal: true + +class Gem::Resolver::APISet::GemParser + def parse(line) + version_and_platform, rest = line.split(" ", 2) + version, platform = version_and_platform.split("-", 2) + dependencies, requirements = rest.split("|", 2).map! {|s| s.split(",") } if rest + dependencies = dependencies ? dependencies.map! {|d| parse_dependency(d) } : [] + requirements = requirements ? requirements.map! {|d| parse_dependency(d) } : [] + [version, platform, dependencies, requirements] + end + + private + + def parse_dependency(string) + dependency = string.split(":", 2) + dependency[-1] = dependency[-1].split("&") if dependency.size > 1 + dependency[0] = -dependency[0] + dependency + end +end diff --git a/lib/rubygems/resolver/api_specification.rb b/lib/rubygems/resolver/api_specification.rb index 1e22dd0b6f..ccfd6fe084 100644 --- a/lib/rubygems/resolver/api_specification.rb +++ b/lib/rubygems/resolver/api_specification.rb @@ -1,17 +1,28 @@ # frozen_string_literal: true + ## -# Represents a specification retrieved via the rubygems.org API. +# Represents a specification retrieved via the Compact Index API. # # This is used to avoid loading the full Specification object when all we need # is the name, version, and dependencies. class Gem::Resolver::APISpecification < Gem::Resolver::Specification + ## + # We assume that all instances of this class are immutable; + # so avoid duplicated generation for performance. + @@cache = {} + def self.new(set, api_data) + cache_key = [set, api_data] + cache = @@cache[cache_key] + return cache if cache + @@cache[cache_key] = super + end ## - # Creates an APISpecification for the given +set+ from the rubygems.org + # Creates an APISpecification for the given +set+ from the Compact Index API # +api_data+. # - # See http://guides.rubygems.org/rubygems-org-api/#misc_methods for the + # See https://guides.rubygems.org/rubygems-org-compact-index-api for the # format of the +api_data+. def initialize(set, api_data) @@ -19,20 +30,26 @@ class Gem::Resolver::APISpecification < Gem::Resolver::Specification @set = set @name = api_data[:name] - @version = Gem::Version.new api_data[:number] - @platform = Gem::Platform.new api_data[:platform] + @version = Gem::Version.new(api_data[:number]).freeze + @platform = Gem::Platform.new(api_data[:platform]).freeze + @original_platform = api_data[:platform].freeze @dependencies = api_data[:dependencies].map do |name, ver| - Gem::Dependency.new name, ver.split(/\s*,\s*/) - end + Gem::Dependency.new(name, ver.split(/\s*,\s*/)).freeze + end.freeze + @required_ruby_version = Gem::Requirement.new(api_data.dig(:requirements, :ruby)).freeze + @required_rubygems_version = Gem::Requirement.new(api_data.dig(:requirements, :rubygems)).freeze end - def == other # :nodoc: - self.class === other and - @set == other.set and - @name == other.name and - @version == other.version and - @platform == other.platform and - @dependencies == other.dependencies + def ==(other) # :nodoc: + self.class === other && + @set == other.set && + @name == other.name && + @version == other.version && + @platform == other.platform + end + + def hash + @set.hash ^ @name.hash ^ @version.hash ^ @platform.hash end def fetch_development_dependencies # :nodoc: @@ -42,11 +59,11 @@ class Gem::Resolver::APISpecification < Gem::Resolver::Specification end def installable_platform? # :nodoc: - Gem::Platform.match @platform + Gem::Platform.match_gem? @platform, @name end - def pretty_print q # :nodoc: - q.group 2, '[APISpecification', ']' do + def pretty_print(q) # :nodoc: + q.group 2, "[APISpecification", "]" do q.breakable q.text "name: #{name}" @@ -57,7 +74,7 @@ class Gem::Resolver::APISpecification < Gem::Resolver::Specification q.text "platform: #{platform}" q.breakable - q.text 'dependencies:' + q.text "dependencies:" q.breakable q.pp @dependencies @@ -73,7 +90,11 @@ class Gem::Resolver::APISpecification < Gem::Resolver::Specification @spec ||= begin tuple = Gem::NameTuple.new @name, @version, @platform + source.fetch_spec tuple + rescue Gem::RemoteFetcher::FetchError + raise if @original_platform == @platform + tuple = Gem::NameTuple.new @name, @version, @original_platform source.fetch_spec tuple end end @@ -81,6 +102,4 @@ class Gem::Resolver::APISpecification < Gem::Resolver::Specification def source # :nodoc: @set.source end - end - diff --git a/lib/rubygems/resolver/best_set.rb b/lib/rubygems/resolver/best_set.rb index 4479535abe..e647a2c11b 100644 --- a/lib/rubygems/resolver/best_set.rb +++ b/lib/rubygems/resolver/best_set.rb @@ -1,16 +1,16 @@ # frozen_string_literal: true + ## # The BestSet chooses the best available method to query a remote index. # # It combines IndexSet and APISet class Gem::Resolver::BestSet < Gem::Resolver::ComposedSet - ## # Creates a BestSet for the given +sources+ or Gem::sources if none are # specified. +sources+ must be a Gem::SourceList. - def initialize sources = Gem.sources + def initialize(sources = Gem.sources) super() @sources = sources @@ -21,59 +21,29 @@ class Gem::Resolver::BestSet < Gem::Resolver::ComposedSet def pick_sets # :nodoc: @sources.each_source do |source| - @sets << source.dependency_resolver_set + @sets << source.dependency_resolver_set(@prerelease) end end - def find_all req # :nodoc: - pick_sets if @remote and @sets.empty? + def find_all(req) # :nodoc: + pick_sets if @remote && @sets.empty? super - rescue Gem::RemoteFetcher::FetchError => e - replace_failed_api_set e - - retry end - def prefetch reqs # :nodoc: - pick_sets if @remote and @sets.empty? + def prefetch(reqs) # :nodoc: + pick_sets if @remote && @sets.empty? super end - def pretty_print q # :nodoc: - q.group 2, '[BestSet', ']' do + def pretty_print(q) # :nodoc: + q.group 2, "[BestSet", "]" do q.breakable - q.text 'sets:' + q.text "sets:" q.breakable q.pp @sets end end - - ## - # Replaces a failed APISet for the URI in +error+ with an IndexSet. - # - # If no matching APISet can be found the original +error+ is raised. - # - # The calling method must retry the exception to repeat the lookup. - - def replace_failed_api_set error # :nodoc: - uri = error.uri - uri = URI uri unless URI === uri - uri.query = nil - - raise error unless api_set = @sets.find { |set| - Gem::Resolver::APISet === set and set.dep_uri == uri - } - - index_set = Gem::Resolver::IndexSet.new api_set.source - - @sets.map! do |set| - next set unless set == api_set - index_set - end - end - end - diff --git a/lib/rubygems/resolver/composed_set.rb b/lib/rubygems/resolver/composed_set.rb index 0b65942dca..e67dd41754 100644 --- a/lib/rubygems/resolver/composed_set.rb +++ b/lib/rubygems/resolver/composed_set.rb @@ -1,4 +1,5 @@ # frozen_string_literal: true + ## # A ComposedSet allows multiple sets to be queried like a single set. # @@ -9,14 +10,13 @@ # This method will eliminate nesting of composed sets. class Gem::Resolver::ComposedSet < Gem::Resolver::Set - attr_reader :sets # :nodoc: ## # Creates a new ComposedSet containing +sets+. Use # Gem::Resolver::compose_sets instead. - def initialize *sets + def initialize(*sets) super() @sets = sets @@ -26,7 +26,7 @@ class Gem::Resolver::ComposedSet < Gem::Resolver::Set # When +allow_prerelease+ is set to +true+ prereleases gems are allowed to # match dependencies. - def prerelease= allow_prerelease + def prerelease=(allow_prerelease) super sets.each do |set| @@ -37,31 +37,29 @@ class Gem::Resolver::ComposedSet < Gem::Resolver::Set ## # Sets the remote network access for all composed sets. - def remote= remote + def remote=(remote) super - @sets.each { |set| set.remote = remote } + @sets.each {|set| set.remote = remote } end def errors - @errors + @sets.map { |set| set.errors }.flatten + @errors + @sets.flat_map(&:errors) end ## # Finds all specs matching +req+ in all sets. - def find_all req - @sets.map do |s| + def find_all(req) + @sets.flat_map do |s| s.find_all req - end.flatten + end end ## # Prefetches +reqs+ in all sets. - def prefetch reqs - @sets.each { |s| s.prefetch(reqs) } + def prefetch(reqs) + @sets.each {|s| s.prefetch(reqs) } end - end - diff --git a/lib/rubygems/resolver/conflict.rb b/lib/rubygems/resolver/conflict.rb deleted file mode 100644 index 7997f92950..0000000000 --- a/lib/rubygems/resolver/conflict.rb +++ /dev/null @@ -1,160 +0,0 @@ -# frozen_string_literal: true -## -# Used internally to indicate that a dependency conflicted -# with a spec that would be activated. - -class Gem::Resolver::Conflict - - ## - # The specification that was activated prior to the conflict - - attr_reader :activated - - ## - # The dependency that is in conflict with the activated gem. - - attr_reader :dependency - - attr_reader :failed_dep # :nodoc: - - ## - # Creates a new resolver conflict when +dependency+ is in conflict with an - # already +activated+ specification. - - def initialize(dependency, activated, failed_dep=dependency) - @dependency = dependency - @activated = activated - @failed_dep = failed_dep - end - - def == other # :nodoc: - self.class === other and - @dependency == other.dependency and - @activated == other.activated and - @failed_dep == other.failed_dep - end - - ## - # A string explanation of the conflict. - - def explain - "<Conflict wanted: #{@failed_dep}, had: #{activated.spec.full_name}>" - end - - ## - # Return the 2 dependency objects that conflicted - - def conflicting_dependencies - [@failed_dep.dependency, @activated.request.dependency] - end - - ## - # Explanation of the conflict used by exceptions to print useful messages - - def explanation - activated = @activated.spec.full_name - dependency = @failed_dep.dependency - requirement = dependency.requirement - alternates = dependency.matching_specs.map { |spec| spec.full_name } - - unless alternates.empty? then - matching = <<-MATCHING.chomp - - Gems matching %s: - %s - MATCHING - - matching = matching % [ - dependency, - alternates.join(', '), - ] - end - - explanation = <<-EXPLANATION - Activated %s - which does not match conflicting dependency (%s) - - Conflicting dependency chains: - %s - - versus: - %s -%s - EXPLANATION - - explanation % [ - activated, requirement, - request_path(@activated).reverse.join(", depends on\n "), - request_path(@failed_dep).reverse.join(", depends on\n "), - matching, - ] - end - - ## - # Returns true if the conflicting dependency's name matches +spec+. - - def for_spec?(spec) - @dependency.name == spec.name - end - - def pretty_print q # :nodoc: - q.group 2, '[Dependency conflict: ', ']' do - q.breakable - - q.text 'activated ' - q.pp @activated - - q.breakable - q.text ' dependency ' - q.pp @dependency - - q.breakable - if @dependency == @failed_dep then - q.text ' failed' - else - q.text ' failed dependency ' - q.pp @failed_dep - end - end - end - - ## - # Path of activations from the +current+ list. - - def request_path current - path = [] - - while current do - case current - when Gem::Resolver::ActivationRequest then - path << - "#{current.request.dependency}, #{current.spec.version} activated" - - current = current.parent - when Gem::Resolver::DependencyRequest then - path << "#{current.dependency}" - - current = current.requester - else - raise Gem::Exception, "[BUG] unknown request class #{current.class}" - end - end - - path = ['user request (gem command or Gemfile)'] if path.empty? - - path - end - - ## - # Return the Specification that listed the dependency - - def requester - @failed_dep.requester - end - -end - -## -# TODO: Remove in RubyGems 3 - -Gem::Resolver::DependencyConflict = Gem::Resolver::Conflict # :nodoc: diff --git a/lib/rubygems/resolver/current_set.rb b/lib/rubygems/resolver/current_set.rb index 265c639f15..370e445089 100644 --- a/lib/rubygems/resolver/current_set.rb +++ b/lib/rubygems/resolver/current_set.rb @@ -1,14 +1,12 @@ # frozen_string_literal: true + ## # A set which represents the installed gems. Respects # all the normal settings that control where to look # for installed gems. class Gem::Resolver::CurrentSet < Gem::Resolver::Set - - def find_all req + def find_all(req) req.dependency.matching_specs end - end - diff --git a/lib/rubygems/resolver/dependency_request.rb b/lib/rubygems/resolver/dependency_request.rb index c2918911cd..60b338277f 100644 --- a/lib/rubygems/resolver/dependency_request.rb +++ b/lib/rubygems/resolver/dependency_request.rb @@ -1,10 +1,10 @@ # frozen_string_literal: true + ## # Used Internally. Wraps a Dependency object to also track which spec # contained the Dependency. class Gem::Resolver::DependencyRequest - ## # The wrapped Gem::Dependency @@ -19,17 +19,17 @@ class Gem::Resolver::DependencyRequest # Creates a new DependencyRequest for +dependency+ from +requester+. # +requester may be nil if the request came from a user. - def initialize dependency, requester + def initialize(dependency, requester) @dependency = dependency @requester = requester end - def == other # :nodoc: + def ==(other) # :nodoc: case other when Gem::Dependency @dependency == other when Gem::Resolver::DependencyRequest - @dependency == other.dependency && @requester == other.requester + @dependency == other.dependency else false end @@ -48,7 +48,7 @@ class Gem::Resolver::DependencyRequest # NOTE: #match? only matches prerelease versions when #dependency is a # prerelease dependency. - def match? spec, allow_prerelease = false + def match?(spec, allow_prerelease = false) @dependency.match? spec, nil, allow_prerelease end @@ -95,13 +95,13 @@ class Gem::Resolver::DependencyRequest @requester ? @requester.request : "(unknown)" end - def pretty_print q # :nodoc: - q.group 2, '[Dependency request ', ']' do + def pretty_print(q) # :nodoc: + q.group 2, "[Dependency request ", "]" do q.breakable q.text @dependency.to_s q.breakable - q.text ' requested by ' + q.text " requested by " q.pp @requester end end @@ -116,5 +116,4 @@ class Gem::Resolver::DependencyRequest def to_s # :nodoc: @dependency.to_s end - end diff --git a/lib/rubygems/resolver/git_set.rb b/lib/rubygems/resolver/git_set.rb index 723a202d7a..2912378fe7 100644 --- a/lib/rubygems/resolver/git_set.rb +++ b/lib/rubygems/resolver/git_set.rb @@ -1,4 +1,5 @@ # frozen_string_literal: true + ## # A GitSet represents gems that are sourced from git repositories. # @@ -10,7 +11,6 @@ # set.add_git_gem 'rake', 'git://example/rake.git', tag: 'rake-10.1.0' class Gem::Resolver::GitSet < Gem::Resolver::Set - ## # The root directory for git gems in this set. This is usually Gem.dir, the # installation directory for regular gems. @@ -36,14 +36,13 @@ class Gem::Resolver::GitSet < Gem::Resolver::Set def initialize # :nodoc: super() - @git = ENV['git'] || 'git' @need_submodules = {} @repositories = {} @root_dir = Gem.dir @specs = {} end - def add_git_gem name, repository, reference, submodules # :nodoc: + def add_git_gem(name, repository, reference, submodules) # :nodoc: @repositories[name] = [repository, reference] @need_submodules[repository] = submodules end @@ -56,7 +55,7 @@ class Gem::Resolver::GitSet < Gem::Resolver::Set # This fills in the prefetch information as enough information about the gem # is present in the arguments. - def add_git_spec name, version, repository, reference, submodules # :nodoc: + def add_git_spec(name, version, repository, reference, submodules) # :nodoc: add_git_gem name, repository, reference, submodules source = Gem::Source::Git.new name, repository, reference @@ -77,7 +76,7 @@ class Gem::Resolver::GitSet < Gem::Resolver::Set ## # Finds all git gems matching +req+ - def find_all req + def find_all(req) prefetch nil specs.values.select do |spec| @@ -88,7 +87,7 @@ class Gem::Resolver::GitSet < Gem::Resolver::Set ## # Prefetches specifications from the git repositories in this set. - def prefetch reqs + def prefetch(reqs) return unless @specs.empty? @repositories.each do |name, (repository, reference)| @@ -104,8 +103,8 @@ class Gem::Resolver::GitSet < Gem::Resolver::Set end end - def pretty_print q # :nodoc: - q.group 2, '[GitSet', ']' do + def pretty_print(q) # :nodoc: + q.group 2, "[GitSet", "]" do next if @repositories.empty? q.breakable @@ -118,6 +117,4 @@ class Gem::Resolver::GitSet < Gem::Resolver::Set end end end - end - diff --git a/lib/rubygems/resolver/git_specification.rb b/lib/rubygems/resolver/git_specification.rb index 2448797d3f..e587c17d2a 100644 --- a/lib/rubygems/resolver/git_specification.rb +++ b/lib/rubygems/resolver/git_specification.rb @@ -1,19 +1,19 @@ # frozen_string_literal: true + ## # A GitSpecification represents a gem that is sourced from a git repository # and is being loaded through a gem dependencies file through the +git:+ # option. class Gem::Resolver::GitSpecification < Gem::Resolver::SpecSpecification - - def == other # :nodoc: - self.class === other and - @set == other.set and - @spec == other.spec and + def ==(other) # :nodoc: + self.class === other && + @set == other.set && + @spec == other.spec && @source == other.source end - def add_dependency dependency # :nodoc: + def add_dependency(dependency) # :nodoc: spec.dependencies << dependency end @@ -21,8 +21,8 @@ class Gem::Resolver::GitSpecification < Gem::Resolver::SpecSpecification # Installing a git gem only involves building the extensions and generating # the executables. - def install options = {} - require 'rubygems/installer' + def install(options = {}) + require_relative "../installer" installer = Gem::Installer.for_spec spec, options @@ -35,8 +35,8 @@ class Gem::Resolver::GitSpecification < Gem::Resolver::SpecSpecification installer.run_post_install_hooks end - def pretty_print q # :nodoc: - q.group 2, '[GitSpecification', ']' do + def pretty_print(q) # :nodoc: + q.group 2, "[GitSpecification", "]" do q.breakable q.text "name: #{name}" @@ -44,7 +44,7 @@ class Gem::Resolver::GitSpecification < Gem::Resolver::SpecSpecification q.text "version: #{version}" q.breakable - q.text 'dependencies:' + q.text "dependencies:" q.breakable q.pp dependencies @@ -54,6 +54,4 @@ class Gem::Resolver::GitSpecification < Gem::Resolver::SpecSpecification q.pp @source end end - end - diff --git a/lib/rubygems/resolver/incompatibility.rb b/lib/rubygems/resolver/incompatibility.rb new file mode 100644 index 0000000000..57a60affb4 --- /dev/null +++ b/lib/rubygems/resolver/incompatibility.rb @@ -0,0 +1,10 @@ +# frozen_string_literal: true + +class Gem::Resolver::Incompatibility < Gem::PubGrub::Incompatibility + attr_reader :extended_explanation + + def initialize(terms, cause:, custom_explanation: nil, extended_explanation: nil) + @extended_explanation = extended_explanation + super(terms, cause: cause, custom_explanation: custom_explanation) + end +end diff --git a/lib/rubygems/resolver/index_set.rb b/lib/rubygems/resolver/index_set.rb index 2450f14b4f..cddaf8773f 100644 --- a/lib/rubygems/resolver/index_set.rb +++ b/lib/rubygems/resolver/index_set.rb @@ -1,15 +1,15 @@ # frozen_string_literal: true + ## # The global rubygems pool represented via the traditional # source index. class Gem::Resolver::IndexSet < Gem::Resolver::Set - - def initialize source = nil # :nodoc: + def initialize(source = nil) # :nodoc: super() @f = - if source then + if source sources = Gem::SourceList.from [source] Gem::SpecFetcher.new sources @@ -17,7 +17,7 @@ class Gem::Resolver::IndexSet < Gem::Resolver::Set Gem::SpecFetcher.fetcher end - @all = Hash.new { |h,k| h[k] = [] } + @all = Hash.new {|h,k| h[k] = [] } list, errors = @f.available_specs :complete @@ -36,7 +36,7 @@ class Gem::Resolver::IndexSet < Gem::Resolver::Set # Return an array of IndexSpecification objects matching # DependencyRequest +req+. - def find_all req + def find_all(req) res = [] return res unless @remote @@ -44,38 +44,36 @@ class Gem::Resolver::IndexSet < Gem::Resolver::Set name = req.dependency.name @all[name].each do |uri, n| - if req.match? n, @prerelease then - res << Gem::Resolver::IndexSpecification.new( - self, n.name, n.version, uri, n.platform) - end + next unless req.match? n, @prerelease + res << Gem::Resolver::IndexSpecification.new( + self, n.name, n.version, uri, n.platform + ) end res end - def pretty_print q # :nodoc: - q.group 2, '[IndexSet', ']' do + def pretty_print(q) # :nodoc: + q.group 2, "[IndexSet", "]" do q.breakable - q.text 'sources:' + q.text "sources:" q.breakable q.pp @f.sources q.breakable - q.text 'specs:' + q.text "specs:" q.breakable - names = @all.values.map do |tuples| + names = @all.values.flat_map do |tuples| tuples.map do |_, tuple| tuple.full_name end - end.flatten + end q.seplist names do |name| q.text name end end end - end - diff --git a/lib/rubygems/resolver/index_specification.rb b/lib/rubygems/resolver/index_specification.rb index 4340f46943..7b95608071 100644 --- a/lib/rubygems/resolver/index_specification.rb +++ b/lib/rubygems/resolver/index_specification.rb @@ -1,11 +1,11 @@ # frozen_string_literal: true + ## # 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 Gem::Resolver::IndexSpecification < Gem::Resolver::Specification - ## # An IndexSpecification is created from the index format described in `gem # help generate_index`. @@ -15,14 +15,15 @@ class Gem::Resolver::IndexSpecification < Gem::Resolver::Specification # The +name+, +version+ and +platform+ are the name, version and platform of # the gem. - def initialize set, name, version, source, platform + def initialize(set, name, version, source, platform) super() @set = set @name = name @version = version @source = source - @platform = platform.to_s + @platform = Gem::Platform.new(platform.to_s) + @original_platform = platform.to_s @spec = nil end @@ -34,22 +35,54 @@ class Gem::Resolver::IndexSpecification < Gem::Resolver::Specification spec.dependencies end + ## + # The required_ruby_version constraint for this specification + # + # A fallback is included because when generated, some marshalled specs have it + # set to +nil+. + + def required_ruby_version + spec.required_ruby_version || Gem::Requirement.default + end + + ## + # The required_rubygems_version constraint for this specification + # + # A fallback is included because the original version of the specification + # API didn't include that field, so some marshalled specs in the index have it + # set to +nil+. + + def required_rubygems_version + spec.required_rubygems_version || Gem::Requirement.default + end + + def ==(other) + self.class === other && + @name == other.name && + @version == other.version && + @platform == other.platform + end + + def hash + @name.hash ^ @version.hash ^ @platform.hash + end + def inspect # :nodoc: - '#<%s %s source %s>' % [self.class, full_name, @source] + format("#<%s %s source %s>", self.class, full_name, @source) end - def pretty_print q # :nodoc: - q.group 2, '[Index specification', ']' do + def pretty_print(q) # :nodoc: + q.group 2, "[Index specification", "]" do q.breakable q.text full_name - unless Gem::Platform::RUBY == @platform then + unless @platform == Gem::Platform::RUBY q.breakable q.text @platform.to_s end q.breakable - q.text 'source ' + q.text "source " q.pp @source end end @@ -60,11 +93,9 @@ class Gem::Resolver::IndexSpecification < Gem::Resolver::Specification def spec # :nodoc: @spec ||= begin - tuple = Gem::NameTuple.new @name, @version, @platform + tuple = Gem::NameTuple.new @name, @version, @original_platform @source.fetch_spec tuple end end - end - diff --git a/lib/rubygems/resolver/installed_specification.rb b/lib/rubygems/resolver/installed_specification.rb index d9c6a5e5cf..8280ae4672 100644 --- a/lib/rubygems/resolver/installed_specification.rb +++ b/lib/rubygems/resolver/installed_specification.rb @@ -1,13 +1,13 @@ # frozen_string_literal: true + ## # An InstalledSpecification represents a gem that is already installed # locally. class Gem::Resolver::InstalledSpecification < Gem::Resolver::SpecSpecification - - def == other # :nodoc: - self.class === other and - @set == other.set and + def ==(other) # :nodoc: + self.class === other && + @set == other.set && @spec == other.spec end @@ -15,7 +15,7 @@ class Gem::Resolver::InstalledSpecification < Gem::Resolver::SpecSpecification # This is a null install as this specification is already installed. # +options+ are ignored. - def install options = {} + def install(options = {}) yield nil end @@ -25,13 +25,13 @@ class Gem::Resolver::InstalledSpecification < Gem::Resolver::SpecSpecification def installable_platform? # BACKCOMPAT If the file is coming out of a specified file, then we # ignore the platform. This code can be removed in RG 3.0. - return true if @source.kind_of? Gem::Source::SpecificFile + return true if @source.is_a? Gem::Source::SpecificFile super end - def pretty_print q # :nodoc: - q.group 2, '[InstalledSpecification', ']' do + def pretty_print(q) # :nodoc: + q.group 2, "[InstalledSpecification", "]" do q.breakable q.text "name: #{name}" @@ -42,7 +42,7 @@ class Gem::Resolver::InstalledSpecification < Gem::Resolver::SpecSpecification q.text "platform: #{platform}" q.breakable - q.text 'dependencies:' + q.text "dependencies:" q.breakable q.pp spec.dependencies end @@ -54,6 +54,4 @@ class Gem::Resolver::InstalledSpecification < Gem::Resolver::SpecSpecification def source @source ||= Gem::Source::Installed.new end - end - diff --git a/lib/rubygems/resolver/installer_set.rb b/lib/rubygems/resolver/installer_set.rb index f24293c0a0..42ce0890e2 100644 --- a/lib/rubygems/resolver/installer_set.rb +++ b/lib/rubygems/resolver/installer_set.rb @@ -1,10 +1,10 @@ # frozen_string_literal: true + ## # A set of gems for installation sourced from remote sources and local .gem # files class Gem::Resolver::InstallerSet < Gem::Resolver::Set - ## # List of Gem::Specification objects that must always be installed. @@ -27,13 +27,18 @@ class Gem::Resolver::InstallerSet < Gem::Resolver::Set attr_reader :remote_set # :nodoc: ## + # Ignore ruby & rubygems specification constraints. + # + + attr_accessor :force # :nodoc: + + ## # Creates a new InstallerSet that will look for gems in +domain+. - def initialize domain + def initialize(domain) super() @domain = domain - @remote = consider_remote? @f = Gem::SpecFetcher.fetcher @@ -43,6 +48,7 @@ class Gem::Resolver::InstallerSet < Gem::Resolver::Set @local = {} @local_source = Gem::Source::Local.new @remote_set = Gem::Resolver::BestSet.new + @force = false @specs = {} end @@ -50,30 +56,44 @@ class Gem::Resolver::InstallerSet < Gem::Resolver::Set # Looks up the latest specification for +dependency+ and adds it to the # always_install list. - def add_always_install dependency + def add_always_install(dependency) request = Gem::Resolver::DependencyRequest.new dependency, nil found = find_all request - found.delete_if { |s| - s.version.prerelease? and not s.local? - } unless dependency.prerelease? + found.delete_if do |s| + s.version.prerelease? && !s.local? + end unless dependency.prerelease? found = found.select do |s| - Gem::Source::SpecificFile === s.source or - Gem::Platform::RUBY == s.platform or - Gem::Platform.local === s.platform + Gem::Source::SpecificFile === s.source || + Gem::Platform.match_spec?(s) + end + + found = found.sort_by do |s| + [s.version, Gem::Platform.sort_priority(s.platform)] end - if found.empty? then + newest = found.last + + unless newest exc = Gem::UnsatisfiableDependencyError.new request exc.errors = errors raise exc end - newest = found.max_by do |s| - [s.version, s.platform == Gem::Platform::RUBY ? -1 : 1] + unless @force + found_matching_metadata = found.reverse.find do |spec| + metadata_satisfied?(spec) + end + + if found_matching_metadata.nil? + ensure_required_ruby_version_met(newest.spec) + ensure_required_rubygems_version_met(newest.spec) + else + newest = found_matching_metadata + end end @always_install << newest.spec @@ -83,7 +103,7 @@ class Gem::Resolver::InstallerSet < Gem::Resolver::Set # Adds a local gem requested using +dep_name+ with the given +spec+ that can # be loaded and installed using the +source+. - def add_local dep_name, spec, source + def add_local(dep_name, spec, source) @local[dep_name] = [spec, source] end @@ -91,14 +111,14 @@ class Gem::Resolver::InstallerSet < Gem::Resolver::Set # Should local gems should be considered? def consider_local? # :nodoc: - @domain == :both or @domain == :local + @domain == :both || @domain == :local end ## # Should remote gems should be considered? def consider_remote? # :nodoc: - @domain == :both or @domain == :remote + @domain == :both || @domain == :remote end ## @@ -112,23 +132,25 @@ class Gem::Resolver::InstallerSet < Gem::Resolver::Set # Returns an array of IndexSpecification objects matching DependencyRequest # +req+. - def find_all req + def find_all(req) res = [] - dep = req.dependency + dep = req.dependency - return res if @ignore_dependencies and - @always_install.none? { |spec| dep.match? spec } + return res if @ignore_dependencies && + @always_install.none? {|spec| dep.match? spec } name = dep.name dep.matching_specs.each do |gemspec| - next if @always_install.any? { |spec| spec.name == gemspec.name } + next if @always_install.any? {|spec| spec.name == gemspec.name } res << Gem::Resolver::InstalledSpecification.new(self, gemspec) end unless @ignore_installed - if consider_local? then + matching_local = [] + + if consider_local? matching_local = @local.values.select do |spec, _| req.match? spec end.map do |spec, source| @@ -138,21 +160,18 @@ class Gem::Resolver::InstallerSet < Gem::Resolver::Set res.concat matching_local begin - if local_spec = @local_source.find_gem(name, dep.requirement) then + @local_source.find_all_gems(name, dep.requirement).each do |local_spec| res << Gem::Resolver::IndexSpecification.new( self, local_spec.name, local_spec.version, - @local_source, local_spec.platform) + @local_source, local_spec.platform + ) end rescue Gem::Package::FormatError # ignore end end - res.delete_if do |spec| - spec.version.prerelease? and not dep.prerelease? - end - - res.concat @remote_set.find_all req if consider_remote? + res.concat @remote_set.find_all req if consider_remote? && matching_local.empty? res end @@ -161,25 +180,23 @@ class Gem::Resolver::InstallerSet < Gem::Resolver::Set @remote_set.prefetch(reqs) if consider_remote? end - def prerelease= allow_prerelease + def prerelease=(allow_prerelease) super @remote_set.prerelease = allow_prerelease end def inspect # :nodoc: - always_install = @always_install.map { |s| s.full_name } + always_install = @always_install.map(&:full_name) - '#<%s domain: %s specs: %p always install: %p>' % [ - self.class, @domain, @specs.keys, always_install, - ] + format("#<%s domain: %s specs: %p always install: %p>", self.class, @domain, @specs.keys, always_install) end ## # Called from IndexSpecification to get a true Specification # object. - def load_spec name, ver, platform, source # :nodoc: + def load_spec(name, ver, platform, source) # :nodoc: key = "#{name}-#{ver}-#{platform}" @specs.fetch key do @@ -192,28 +209,28 @@ class Gem::Resolver::InstallerSet < Gem::Resolver::Set ## # Has a local gem for +dep_name+ been added to this set? - def local? dep_name # :nodoc: + def local?(dep_name) # :nodoc: spec, _ = @local[dep_name] spec end - def pretty_print q # :nodoc: - q.group 2, '[InstallerSet', ']' do + def pretty_print(q) # :nodoc: + q.group 2, "[InstallerSet", "]" do q.breakable q.text "domain: #{@domain}" q.breakable - q.text 'specs: ' + q.text "specs: " q.pp @specs.keys q.breakable - q.text 'always install: ' + q.text "always install: " q.pp @always_install end end - def remote= remote # :nodoc: + def remote=(remote) # :nodoc: case @domain when :local then @domain = :both if remote @@ -224,4 +241,31 @@ class Gem::Resolver::InstallerSet < Gem::Resolver::Set end end + private + + def metadata_satisfied?(spec) + spec.required_ruby_version.satisfied_by?(Gem.ruby_version) && + spec.required_rubygems_version.satisfied_by?(Gem.rubygems_version) + end + + def ensure_required_ruby_version_met(spec) # :nodoc: + if rrv = spec.required_ruby_version + ruby_version = Gem.ruby_version + unless rrv.satisfied_by? ruby_version + raise Gem::RuntimeRequirementNotMetError, + "#{spec.full_name} requires Ruby version #{rrv}. The current ruby version is #{ruby_version}." + end + end + end + + def ensure_required_rubygems_version_met(spec) # :nodoc: + if rrgv = spec.required_rubygems_version + unless rrgv.satisfied_by? Gem.rubygems_version + rg_version = Gem::VERSION + raise Gem::RuntimeRequirementNotMetError, + "#{spec.full_name} requires RubyGems version #{rrgv}. The current RubyGems version is #{rg_version}. " \ + "Try 'gem update --system' to update RubyGems itself." + end + end + end end diff --git a/lib/rubygems/resolver/local_specification.rb b/lib/rubygems/resolver/local_specification.rb index 1d9d22f0ac..b57d40e795 100644 --- a/lib/rubygems/resolver/local_specification.rb +++ b/lib/rubygems/resolver/local_specification.rb @@ -1,14 +1,14 @@ # frozen_string_literal: true + ## # A LocalSpecification comes from a .gem file on the local filesystem. class Gem::Resolver::LocalSpecification < Gem::Resolver::SpecSpecification - ## # Returns +true+ if this gem is installable for the current platform. def installable_platform? - return true if @source.kind_of? Gem::Source::SpecificFile + return true if @source.is_a? Gem::Source::SpecificFile super end @@ -17,8 +17,8 @@ class Gem::Resolver::LocalSpecification < Gem::Resolver::SpecSpecification true end - def pretty_print q # :nodoc: - q.group 2, '[LocalSpecification', ']' do + def pretty_print(q) # :nodoc: + q.group 2, "[LocalSpecification", "]" do q.breakable q.text "name: #{name}" @@ -29,7 +29,7 @@ class Gem::Resolver::LocalSpecification < Gem::Resolver::SpecSpecification q.text "platform: #{platform}" q.breakable - q.text 'dependencies:' + q.text "dependencies:" q.breakable q.pp dependencies @@ -37,6 +37,4 @@ class Gem::Resolver::LocalSpecification < Gem::Resolver::SpecSpecification q.text "source: #{@source.path}" end end - end - diff --git a/lib/rubygems/resolver/lock_set.rb b/lib/rubygems/resolver/lock_set.rb index 7fddc93e1c..e5ee32a9a6 100644 --- a/lib/rubygems/resolver/lock_set.rb +++ b/lib/rubygems/resolver/lock_set.rb @@ -1,22 +1,22 @@ # frozen_string_literal: true + ## # A set of gems from a gem dependencies lockfile. class Gem::Resolver::LockSet < Gem::Resolver::Set - attr_reader :specs # :nodoc: ## # Creates a new LockSet from the given +sources+ - def initialize sources + def initialize(sources) super() @sources = sources.map do |source| Gem::Source::Lock.new source end - @specs = [] + @specs = [] end ## @@ -26,10 +26,10 @@ class Gem::Resolver::LockSet < Gem::Resolver::Set # The specification's set will be the current set, and the source will be # the current set's source. - def add name, version, platform # :nodoc: + def add(name, version, platform) # :nodoc: version = Gem::Version.new version specs = [ - Gem::Resolver::LockSpecification.new(self, name, version, @sources, platform) + Gem::Resolver::LockSpecification.new(self, name, version, @sources, platform), ] @specs.concat specs @@ -41,7 +41,7 @@ class Gem::Resolver::LockSet < Gem::Resolver::Set # Returns an Array of IndexSpecification objects matching the # DependencyRequest +req+. - def find_all req + def find_all(req) @specs.select do |spec| req.match? spec end @@ -51,11 +51,11 @@ class Gem::Resolver::LockSet < Gem::Resolver::Set # Loads a Gem::Specification with the given +name+, +version+ and # +platform+. +source+ is ignored. - def load_spec name, version, platform, source # :nodoc: + def load_spec(name, version, platform, source) # :nodoc: dep = Gem::Dependency.new name, version found = @specs.find do |spec| - dep.matches_spec? spec and spec.platform == platform + dep.matches_spec?(spec) && spec.platform == platform end tuple = Gem::NameTuple.new found.name, found.version, found.platform @@ -63,21 +63,19 @@ class Gem::Resolver::LockSet < Gem::Resolver::Set found.source.fetch_spec tuple end - def pretty_print q # :nodoc: - q.group 2, '[LockSet', ']' do + def pretty_print(q) # :nodoc: + q.group 2, "[LockSet", "]" do q.breakable - q.text 'source:' + q.text "source:" q.breakable q.pp @source q.breakable - q.text 'specs:' + q.text "specs:" q.breakable - q.pp @specs.map { |spec| spec.full_name } + q.pp @specs.map(&:full_name) end end - end - diff --git a/lib/rubygems/resolver/lock_specification.rb b/lib/rubygems/resolver/lock_specification.rb index f485675673..06f912dd85 100644 --- a/lib/rubygems/resolver/lock_specification.rb +++ b/lib/rubygems/resolver/lock_specification.rb @@ -1,4 +1,5 @@ # frozen_string_literal: true + ## # The LockSpecification comes from a lockfile (Gem::RequestSet::Lockfile). # @@ -6,10 +7,9 @@ # lockfile. class Gem::Resolver::LockSpecification < Gem::Resolver::Specification - attr_reader :sources - def initialize set, name, version, sources, platform + def initialize(set, name, version, sources, platform) super() @name = name @@ -27,10 +27,10 @@ class Gem::Resolver::LockSpecification < Gem::Resolver::Specification # This is a null install as a locked specification is considered installed. # +options+ are ignored. - def install options = {} + def install(options = {}) destination = options[:install_dir] || Gem.dir - if File.exist? File.join(destination, 'specifications', spec.spec_name) then + if File.exist? File.join(destination, "specifications", spec.spec_name) yield nil return end @@ -41,26 +41,26 @@ class Gem::Resolver::LockSpecification < Gem::Resolver::Specification ## # Adds +dependency+ from the lockfile to this specification - def add_dependency dependency # :nodoc: + def add_dependency(dependency) # :nodoc: @dependencies << dependency end - def pretty_print q # :nodoc: - q.group 2, '[LockSpecification', ']' do + def pretty_print(q) # :nodoc: + q.group 2, "[LockSpecification", "]" do q.breakable q.text "name: #{@name}" q.breakable q.text "version: #{@version}" - unless @platform == Gem::Platform::RUBY then + unless @platform == Gem::Platform::RUBY q.breakable q.text "platform: #{@platform}" end - unless @dependencies.empty? then + unless @dependencies.empty? q.breakable - q.text 'dependencies:' + q.text "dependencies:" q.breakable q.pp @dependencies end @@ -71,9 +71,9 @@ class Gem::Resolver::LockSpecification < Gem::Resolver::Specification # A specification constructed from the lockfile is returned def spec - @spec ||= Gem::Specification.find { |spec| - spec.name == @name and spec.version == @version - } + @spec ||= Gem::Specification.find do |spec| + spec.name == @name && spec.version == @version + end @spec ||= Gem::Specification.new do |s| s.name = @name @@ -83,6 +83,4 @@ class Gem::Resolver::LockSpecification < Gem::Resolver::Specification s.dependencies.concat @dependencies end end - end - diff --git a/lib/rubygems/resolver/molinillo.rb b/lib/rubygems/resolver/molinillo.rb deleted file mode 100644 index 2357f41bee..0000000000 --- a/lib/rubygems/resolver/molinillo.rb +++ /dev/null @@ -1,2 +0,0 @@ -# frozen_string_literal: true -require 'rubygems/resolver/molinillo/lib/molinillo' diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo.rb b/lib/rubygems/resolver/molinillo/lib/molinillo.rb deleted file mode 100644 index 0ae4b6a912..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo.rb +++ /dev/null @@ -1,10 +0,0 @@ -# frozen_string_literal: true -require 'rubygems/resolver/molinillo/lib/molinillo/gem_metadata' -require 'rubygems/resolver/molinillo/lib/molinillo/errors' -require 'rubygems/resolver/molinillo/lib/molinillo/resolver' -require 'rubygems/resolver/molinillo/lib/molinillo/modules/ui' -require 'rubygems/resolver/molinillo/lib/molinillo/modules/specification_provider' - -# Gem::Resolver::Molinillo is a generic dependency resolution algorithm. -module Gem::Resolver::Molinillo -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/delegates/resolution_state.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/delegates/resolution_state.rb deleted file mode 100644 index 1bbc72c1f6..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/delegates/resolution_state.rb +++ /dev/null @@ -1,50 +0,0 @@ -# frozen_string_literal: true -module Gem::Resolver::Molinillo - # @!visibility private - module Delegates - # Delegates all {Gem::Resolver::Molinillo::ResolutionState} methods to a `#state` property. - module ResolutionState - # (see Gem::Resolver::Molinillo::ResolutionState#name) - def name - current_state = state || Gem::Resolver::Molinillo::ResolutionState.empty - current_state.name - end - - # (see Gem::Resolver::Molinillo::ResolutionState#requirements) - def requirements - current_state = state || Gem::Resolver::Molinillo::ResolutionState.empty - current_state.requirements - end - - # (see Gem::Resolver::Molinillo::ResolutionState#activated) - def activated - current_state = state || Gem::Resolver::Molinillo::ResolutionState.empty - current_state.activated - end - - # (see Gem::Resolver::Molinillo::ResolutionState#requirement) - def requirement - current_state = state || Gem::Resolver::Molinillo::ResolutionState.empty - current_state.requirement - end - - # (see Gem::Resolver::Molinillo::ResolutionState#possibilities) - def possibilities - current_state = state || Gem::Resolver::Molinillo::ResolutionState.empty - current_state.possibilities - end - - # (see Gem::Resolver::Molinillo::ResolutionState#depth) - def depth - current_state = state || Gem::Resolver::Molinillo::ResolutionState.empty - current_state.depth - end - - # (see Gem::Resolver::Molinillo::ResolutionState#conflicts) - def conflicts - current_state = state || Gem::Resolver::Molinillo::ResolutionState.empty - current_state.conflicts - end - end - end -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/delegates/specification_provider.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/delegates/specification_provider.rb deleted file mode 100644 index 71903c7e86..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/delegates/specification_provider.rb +++ /dev/null @@ -1,80 +0,0 @@ -# frozen_string_literal: true -module Gem::Resolver::Molinillo - module Delegates - # Delegates all {Gem::Resolver::Molinillo::SpecificationProvider} methods to a - # `#specification_provider` property. - module SpecificationProvider - # (see Gem::Resolver::Molinillo::SpecificationProvider#search_for) - def search_for(dependency) - with_no_such_dependency_error_handling do - specification_provider.search_for(dependency) - end - end - - # (see Gem::Resolver::Molinillo::SpecificationProvider#dependencies_for) - def dependencies_for(specification) - with_no_such_dependency_error_handling do - specification_provider.dependencies_for(specification) - end - end - - # (see Gem::Resolver::Molinillo::SpecificationProvider#requirement_satisfied_by?) - def requirement_satisfied_by?(requirement, activated, spec) - with_no_such_dependency_error_handling do - specification_provider.requirement_satisfied_by?(requirement, activated, spec) - end - end - - # (see Gem::Resolver::Molinillo::SpecificationProvider#name_for) - def name_for(dependency) - with_no_such_dependency_error_handling do - specification_provider.name_for(dependency) - end - end - - # (see Gem::Resolver::Molinillo::SpecificationProvider#name_for_explicit_dependency_source) - def name_for_explicit_dependency_source - with_no_such_dependency_error_handling do - specification_provider.name_for_explicit_dependency_source - end - end - - # (see Gem::Resolver::Molinillo::SpecificationProvider#name_for_locking_dependency_source) - def name_for_locking_dependency_source - with_no_such_dependency_error_handling do - specification_provider.name_for_locking_dependency_source - end - end - - # (see Gem::Resolver::Molinillo::SpecificationProvider#sort_dependencies) - def sort_dependencies(dependencies, activated, conflicts) - with_no_such_dependency_error_handling do - specification_provider.sort_dependencies(dependencies, activated, conflicts) - end - end - - # (see Gem::Resolver::Molinillo::SpecificationProvider#allow_missing?) - def allow_missing?(dependency) - with_no_such_dependency_error_handling do - specification_provider.allow_missing?(dependency) - end - end - - private - - # Ensures any raised {NoSuchDependencyError} has its - # {NoSuchDependencyError#required_by} set. - # @yield - def with_no_such_dependency_error_handling - yield - rescue NoSuchDependencyError => error - if state - vertex = activated.vertex_named(name_for(error.dependency)) - error.required_by += vertex.incoming_edges.map { |e| e.origin.name } - error.required_by << name_for_explicit_dependency_source unless vertex.explicit_requirements.empty? - end - raise - end - end - end -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb deleted file mode 100644 index b413e3ab6a..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb +++ /dev/null @@ -1,222 +0,0 @@ -# frozen_string_literal: true -require 'set' -require 'tsort' - -require 'rubygems/resolver/molinillo/lib/molinillo/dependency_graph/log' -require 'rubygems/resolver/molinillo/lib/molinillo/dependency_graph/vertex' - -module Gem::Resolver::Molinillo - # A directed acyclic graph that is tuned to hold named dependencies - class DependencyGraph - include Enumerable - - # Enumerates through the vertices of the graph. - # @return [Array<Vertex>] The graph's vertices. - def each - return vertices.values.each unless block_given? - vertices.values.each { |v| yield v } - end - - include TSort - - # @!visibility private - alias tsort_each_node each - - # @!visibility private - def tsort_each_child(vertex, &block) - vertex.successors.each(&block) - end - - # Topologically sorts the given vertices. - # @param [Enumerable<Vertex>] vertices the vertices to be sorted, which must - # all belong to the same graph. - # @return [Array<Vertex>] The sorted vertices. - def self.tsort(vertices) - TSort.tsort( - lambda { |b| vertices.each(&b) }, - lambda { |v, &b| (v.successors & vertices).each(&b) } - ) - end - - # A directed edge of a {DependencyGraph} - # @attr [Vertex] origin The origin of the directed edge - # @attr [Vertex] destination The destination of the directed edge - # @attr [Object] requirement The requirement the directed edge represents - Edge = Struct.new(:origin, :destination, :requirement) - - # @return [{String => Vertex}] the vertices of the dependency graph, keyed - # by {Vertex#name} - attr_reader :vertices - - # @return [Log] the op log for this graph - attr_reader :log - - # Initializes an empty dependency graph - def initialize - @vertices = {} - @log = Log.new - end - - # Tags the current state of the dependency as the given tag - # @param [Object] tag an opaque tag for the current state of the graph - # @return [Void] - def tag(tag) - log.tag(self, tag) - end - - # Rewinds the graph to the state tagged as `tag` - # @param [Object] tag the tag to rewind to - # @return [Void] - def rewind_to(tag) - log.rewind_to(self, tag) - end - - # Initializes a copy of a {DependencyGraph}, ensuring that all {#vertices} - # are properly copied. - # @param [DependencyGraph] other the graph to copy. - def initialize_copy(other) - super - @vertices = {} - @log = other.log.dup - traverse = lambda do |new_v, old_v| - return if new_v.outgoing_edges.size == old_v.outgoing_edges.size - old_v.outgoing_edges.each do |edge| - destination = add_vertex(edge.destination.name, edge.destination.payload) - add_edge_no_circular(new_v, destination, edge.requirement) - traverse.call(destination, edge.destination) - end - end - other.vertices.each do |name, vertex| - new_vertex = add_vertex(name, vertex.payload, vertex.root?) - new_vertex.explicit_requirements.replace(vertex.explicit_requirements) - traverse.call(new_vertex, vertex) - end - end - - # @return [String] a string suitable for debugging - def inspect - "#{self.class}:#{vertices.values.inspect}" - end - - # @param [Hash] options options for dot output. - # @return [String] Returns a dot format representation of the graph - def to_dot(options = {}) - edge_label = options.delete(:edge_label) - raise ArgumentError, "Unknown options: #{options.keys}" unless options.empty? - - dot_vertices = [] - dot_edges = [] - vertices.each do |n, v| - dot_vertices << " #{n} [label=\"{#{n}|#{v.payload}}\"]" - v.outgoing_edges.each do |e| - label = edge_label ? edge_label.call(e) : e.requirement - dot_edges << " #{e.origin.name} -> #{e.destination.name} [label=#{label.to_s.dump}]" - end - end - - dot_vertices.uniq! - dot_vertices.sort! - dot_edges.uniq! - dot_edges.sort! - - dot = dot_vertices.unshift('digraph G {').push('') + dot_edges.push('}') - dot.join("\n") - end - - # @return [Boolean] whether the two dependency graphs are equal, determined - # by a recursive traversal of each {#root_vertices} and its - # {Vertex#successors} - def ==(other) - return false unless other - return true if equal?(other) - vertices.each do |name, vertex| - other_vertex = other.vertex_named(name) - return false unless other_vertex - return false unless vertex.payload == other_vertex.payload - return false unless other_vertex.successors.to_set == vertex.successors.to_set - end - end - - # @param [String] name - # @param [Object] payload - # @param [Array<String>] parent_names - # @param [Object] requirement the requirement that is requiring the child - # @return [void] - def add_child_vertex(name, payload, parent_names, requirement) - root = !parent_names.delete(nil) { true } - vertex = add_vertex(name, payload, root) - vertex.explicit_requirements << requirement if root - parent_names.each do |parent_name| - parent_node = vertex_named(parent_name) - add_edge(parent_node, vertex, requirement) - end - vertex - end - - # Adds a vertex with the given name, or updates the existing one. - # @param [String] name - # @param [Object] payload - # @return [Vertex] the vertex that was added to `self` - def add_vertex(name, payload, root = false) - log.add_vertex(self, name, payload, root) - end - - # Detaches the {#vertex_named} `name` {Vertex} from the graph, recursively - # removing any non-root vertices that were orphaned in the process - # @param [String] name - # @return [Array<Vertex>] the vertices which have been detached - def detach_vertex_named(name) - log.detach_vertex_named(self, name) - end - - # @param [String] name - # @return [Vertex,nil] the vertex with the given name - def vertex_named(name) - vertices[name] - end - - # @param [String] name - # @return [Vertex,nil] the root vertex with the given name - def root_vertex_named(name) - vertex = vertex_named(name) - vertex if vertex && vertex.root? - end - - # Adds a new {Edge} to the dependency graph - # @param [Vertex] origin - # @param [Vertex] destination - # @param [Object] requirement the requirement that this edge represents - # @return [Edge] the added edge - def add_edge(origin, destination, requirement) - if destination.path_to?(origin) - raise CircularDependencyError.new([origin, destination]) - end - add_edge_no_circular(origin, destination, requirement) - end - - # Deletes an {Edge} from the dependency graph - # @param [Edge] edge - # @return [Void] - def delete_edge(edge) - log.delete_edge(self, edge.origin.name, edge.destination.name, edge.requirement) - end - - # Sets the payload of the vertex with the given name - # @param [String] name the name of the vertex - # @param [Object] payload the payload - # @return [Void] - def set_payload(name, payload) - log.set_payload(self, name, payload) - end - - private - - # Adds a new {Edge} to the dependency graph without checking for - # circularity. - # @param (see #add_edge) - # @return (see #add_edge) - def add_edge_no_circular(origin, destination, requirement) - log.add_edge_no_circular(self, origin.name, destination.name, requirement) - end - end -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/action.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/action.rb deleted file mode 100644 index eeedabb069..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/action.rb +++ /dev/null @@ -1,35 +0,0 @@ -# frozen_string_literal: true -module Gem::Resolver::Molinillo - class DependencyGraph - # An action that modifies a {DependencyGraph} that is reversible. - # @abstract - class Action - # rubocop:disable Lint/UnusedMethodArgument - - # @return [Symbol] The name of the action. - def self.action_name - raise 'Abstract' - end - - # Performs the action on the given graph. - # @param [DependencyGraph] graph the graph to perform the action on. - # @return [Void] - def up(graph) - raise 'Abstract' - end - - # Reverses the action on the given graph. - # @param [DependencyGraph] graph the graph to reverse the action on. - # @return [Void] - def down(graph) - raise 'Abstract' - end - - # @return [Action,Nil] The previous action - attr_accessor :previous - - # @return [Action,Nil] The next action - attr_accessor :next - end - end -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb deleted file mode 100644 index e994e59d05..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb +++ /dev/null @@ -1,65 +0,0 @@ -# frozen_string_literal: true -require 'rubygems/resolver/molinillo/lib/molinillo/dependency_graph/action' -module Gem::Resolver::Molinillo - class DependencyGraph - # @!visibility private - # (see DependencyGraph#add_edge_no_circular) - class AddEdgeNoCircular < Action - # @!group Action - - # (see Action.action_name) - def self.action_name - :add_vertex - end - - # (see Action#up) - def up(graph) - edge = make_edge(graph) - edge.origin.outgoing_edges << edge - edge.destination.incoming_edges << edge - edge - end - - # (see Action#down) - def down(graph) - edge = make_edge(graph) - delete_first(edge.origin.outgoing_edges, edge) - delete_first(edge.destination.incoming_edges, edge) - end - - # @!group AddEdgeNoCircular - - # @return [String] the name of the origin of the edge - attr_reader :origin - - # @return [String] the name of the destination of the edge - attr_reader :destination - - # @return [Object] the requirement that the edge represents - attr_reader :requirement - - # @param [DependencyGraph] graph the graph to find vertices from - # @return [Edge] The edge this action adds - def make_edge(graph) - Edge.new(graph.vertex_named(origin), graph.vertex_named(destination), requirement) - end - - # Initialize an action to add an edge to a dependency graph - # @param [String] origin the name of the origin of the edge - # @param [String] destination the name of the destination of the edge - # @param [Object] requirement the requirement that the edge represents - def initialize(origin, destination, requirement) - @origin = origin - @destination = destination - @requirement = requirement - end - - private - - def delete_first(array, item) - return unless index = array.index(item) - array.delete_at(index) - end - end - end -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/add_vertex.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/add_vertex.rb deleted file mode 100644 index 6cde933080..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/add_vertex.rb +++ /dev/null @@ -1,61 +0,0 @@ -# frozen_string_literal: true -require 'rubygems/resolver/molinillo/lib/molinillo/dependency_graph/action' -module Gem::Resolver::Molinillo - class DependencyGraph - # @!visibility private - # (see DependencyGraph#add_vertex) - class AddVertex < Action # :nodoc: - # @!group Action - - # (see Action.action_name) - def self.action_name - :add_vertex - end - - # (see Action#up) - def up(graph) - if existing = graph.vertices[name] - @existing_payload = existing.payload - @existing_root = existing.root - end - vertex = existing || Vertex.new(name, payload) - graph.vertices[vertex.name] = vertex - vertex.payload ||= payload - vertex.root ||= root - vertex - end - - # (see Action#down) - def down(graph) - if defined?(@existing_payload) - vertex = graph.vertices[name] - vertex.payload = @existing_payload - vertex.root = @existing_root - else - graph.vertices.delete(name) - end - end - - # @!group AddVertex - - # @return [String] the name of the vertex - attr_reader :name - - # @return [Object] the payload for the vertex - attr_reader :payload - - # @return [Boolean] whether the vertex is root or not - attr_reader :root - - # Initialize an action to add a vertex to a dependency graph - # @param [String] name the name of the vertex - # @param [Object] payload the payload for the vertex - # @param [Boolean] root whether the vertex is root or not - def initialize(name, payload, root) - @name = name - @payload = payload - @root = root - end - end - end -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/delete_edge.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/delete_edge.rb deleted file mode 100644 index d44aaf1f06..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/delete_edge.rb +++ /dev/null @@ -1,62 +0,0 @@ -# frozen_string_literal: true -require 'rubygems/resolver/molinillo/lib/molinillo/dependency_graph/action' -module Gem::Resolver::Molinillo - class DependencyGraph - # @!visibility private - # (see DependencyGraph#delete_edge) - class DeleteEdge < Action - # @!group Action - - # (see Action.action_name) - def self.action_name - :delete_edge - end - - # (see Action#up) - def up(graph) - edge = make_edge(graph) - edge.origin.outgoing_edges.delete(edge) - edge.destination.incoming_edges.delete(edge) - end - - # (see Action#down) - def down(graph) - edge = make_edge(graph) - edge.origin.outgoing_edges << edge - edge.destination.incoming_edges << edge - edge - end - - # @!group DeleteEdge - - # @return [String] the name of the origin of the edge - attr_reader :origin_name - - # @return [String] the name of the destination of the edge - attr_reader :destination_name - - # @return [Object] the requirement that the edge represents - attr_reader :requirement - - # @param [DependencyGraph] graph the graph to find vertices from - # @return [Edge] The edge this action adds - def make_edge(graph) - Edge.new( - graph.vertex_named(origin_name), - graph.vertex_named(destination_name), - requirement - ) - end - - # Initialize an action to add an edge to a dependency graph - # @param [String] origin_name the name of the origin of the edge - # @param [String] destination_name the name of the destination of the edge - # @param [Object] requirement the requirement that the edge represents - def initialize(origin_name, destination_name, requirement) - @origin_name = origin_name - @destination_name = destination_name - @requirement = requirement - end - end - end -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/detach_vertex_named.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/detach_vertex_named.rb deleted file mode 100644 index fa03e2d365..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/detach_vertex_named.rb +++ /dev/null @@ -1,60 +0,0 @@ -# frozen_string_literal: true -require 'rubygems/resolver/molinillo/lib/molinillo/dependency_graph/action' -module Gem::Resolver::Molinillo - class DependencyGraph - # @!visibility private - # @see DependencyGraph#detach_vertex_named - class DetachVertexNamed < Action - # @!group Action - - # (see Action#name) - def self.action_name - :add_vertex - end - - # (see Action#up) - def up(graph) - return [] unless @vertex = graph.vertices.delete(name) - - removed_vertices = [@vertex] - @vertex.outgoing_edges.each do |e| - v = e.destination - v.incoming_edges.delete(e) - if !v.root? && v.incoming_edges.empty? - removed_vertices.concat graph.detach_vertex_named(v.name) - end - end - - @vertex.incoming_edges.each do |e| - v = e.origin - v.outgoing_edges.delete(e) - end - - removed_vertices - end - - # (see Action#down) - def down(graph) - return unless @vertex - graph.vertices[@vertex.name] = @vertex - @vertex.outgoing_edges.each do |e| - e.destination.incoming_edges << e - end - @vertex.incoming_edges.each do |e| - e.origin.outgoing_edges << e - end - end - - # @!group DetachVertexNamed - - # @return [String] the name of the vertex to detach - attr_reader :name - - # Initialize an action to detach a vertex from a dependency graph - # @param [String] name the name of the vertex to detach - def initialize(name) - @name = name - end - end - end -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/log.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/log.rb deleted file mode 100644 index 5cdd84b5c1..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/log.rb +++ /dev/null @@ -1,125 +0,0 @@ -# frozen_string_literal: true -require 'rubygems/resolver/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular' -require 'rubygems/resolver/molinillo/lib/molinillo/dependency_graph/add_vertex' -require 'rubygems/resolver/molinillo/lib/molinillo/dependency_graph/delete_edge' -require 'rubygems/resolver/molinillo/lib/molinillo/dependency_graph/detach_vertex_named' -require 'rubygems/resolver/molinillo/lib/molinillo/dependency_graph/set_payload' -require 'rubygems/resolver/molinillo/lib/molinillo/dependency_graph/tag' - -module Gem::Resolver::Molinillo - class DependencyGraph - # A log for dependency graph actions - class Log - # Initializes an empty log - def initialize - @current_action = @first_action = nil - end - - # @!macro [new] action - # {include:DependencyGraph#$0} - # @param [Graph] graph the graph to perform the action on - # @param (see DependencyGraph#$0) - # @return (see DependencyGraph#$0) - - # @macro action - def tag(graph, tag) - push_action(graph, Tag.new(tag)) - end - - # @macro action - def add_vertex(graph, name, payload, root) - push_action(graph, AddVertex.new(name, payload, root)) - end - - # @macro action - def detach_vertex_named(graph, name) - push_action(graph, DetachVertexNamed.new(name)) - end - - # @macro action - def add_edge_no_circular(graph, origin, destination, requirement) - push_action(graph, AddEdgeNoCircular.new(origin, destination, requirement)) - end - - # {include:DependencyGraph#delete_edge} - # @param [Graph] graph the graph to perform the action on - # @param [String] origin_name - # @param [String] destination_name - # @param [Object] requirement - # @return (see DependencyGraph#delete_edge) - def delete_edge(graph, origin_name, destination_name, requirement) - push_action(graph, DeleteEdge.new(origin_name, destination_name, requirement)) - end - - # @macro action - def set_payload(graph, name, payload) - push_action(graph, SetPayload.new(name, payload)) - end - - # Pops the most recent action from the log and undoes the action - # @param [DependencyGraph] graph - # @return [Action] the action that was popped off the log - def pop!(graph) - return unless action = @current_action - unless @current_action = action.previous - @first_action = nil - end - action.down(graph) - action - end - - extend Enumerable - - # @!visibility private - # Enumerates each action in the log - # @yield [Action] - def each - return enum_for unless block_given? - action = @first_action - loop do - break unless action - yield action - action = action.next - end - self - end - - # @!visibility private - # Enumerates each action in the log in reverse order - # @yield [Action] - def reverse_each - return enum_for(:reverse_each) unless block_given? - action = @current_action - loop do - break unless action - yield action - action = action.previous - end - self - end - - # @macro action - def rewind_to(graph, tag) - loop do - action = pop!(graph) - raise "No tag #{tag.inspect} found" unless action - break if action.class.action_name == :tag && action.tag == tag - end - end - - private - - # Adds the given action to the log, running the action - # @param [DependencyGraph] graph - # @param [Action] action - # @return The value returned by `action.up` - def push_action(graph, action) - action.previous = @current_action - @current_action.next = action if @current_action - @current_action = action - @first_action ||= action - action.up(graph) - end - end - end -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/set_payload.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/set_payload.rb deleted file mode 100644 index 02cfba64a7..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/set_payload.rb +++ /dev/null @@ -1,45 +0,0 @@ -# frozen_string_literal: true -require 'rubygems/resolver/molinillo/lib/molinillo/dependency_graph/action' -module Gem::Resolver::Molinillo - class DependencyGraph - # @!visibility private - # @see DependencyGraph#set_payload - class SetPayload < Action # :nodoc: - # @!group Action - - # (see Action.action_name) - def self.action_name - :set_payload - end - - # (see Action#up) - def up(graph) - vertex = graph.vertex_named(name) - @old_payload = vertex.payload - vertex.payload = payload - end - - # (see Action#down) - def down(graph) - graph.vertex_named(name).payload = @old_payload - end - - # @!group SetPayload - - # @return [String] the name of the vertex - attr_reader :name - - # @return [Object] the payload for the vertex - attr_reader :payload - - # Initialize an action to add set the payload for a vertex in a dependency - # graph - # @param [String] name the name of the vertex - # @param [Object] payload the payload for the vertex - def initialize(name, payload) - @name = name - @payload = payload - end - end - end -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/tag.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/tag.rb deleted file mode 100644 index 0cb08075ca..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/tag.rb +++ /dev/null @@ -1,35 +0,0 @@ -# frozen_string_literal: true -require 'rubygems/resolver/molinillo/lib/molinillo/dependency_graph/action' -module Gem::Resolver::Molinillo - class DependencyGraph - # @!visibility private - # @see DependencyGraph#tag - class Tag < Action - # @!group Action - - # (see Action.action_name) - def self.action_name - :tag - end - - # (see Action#up) - def up(_graph) - end - - # (see Action#down) - def down(_graph) - end - - # @!group Tag - - # @return [Object] An opaque tag - attr_reader :tag - - # Initialize an action to tag a state of a dependency graph - # @param [Object] tag an opaque tag - def initialize(tag) - @tag = tag - end - end - end -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/vertex.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/vertex.rb deleted file mode 100644 index cebd9cafdd..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/vertex.rb +++ /dev/null @@ -1,125 +0,0 @@ -# frozen_string_literal: true -module Gem::Resolver::Molinillo - class DependencyGraph - # A vertex in a {DependencyGraph} that encapsulates a {#name} and a - # {#payload} - class Vertex - # @return [String] the name of the vertex - attr_accessor :name - - # @return [Object] the payload the vertex holds - attr_accessor :payload - - # @return [Array<Object>] the explicit requirements that required - # this vertex - attr_reader :explicit_requirements - - # @return [Boolean] whether the vertex is considered a root vertex - attr_accessor :root - alias root? root - - # Initializes a vertex with the given name and payload. - # @param [String] name see {#name} - # @param [Object] payload see {#payload} - def initialize(name, payload) - @name = name.frozen? ? name : name.dup.freeze - @payload = payload - @explicit_requirements = [] - @outgoing_edges = [] - @incoming_edges = [] - end - - # @return [Array<Object>] all of the requirements that required - # this vertex - def requirements - incoming_edges.map(&:requirement) + explicit_requirements - end - - # @return [Array<Edge>] the edges of {#graph} that have `self` as their - # {Edge#origin} - attr_accessor :outgoing_edges - - # @return [Array<Edge>] the edges of {#graph} that have `self` as their - # {Edge#destination} - attr_accessor :incoming_edges - - # @return [Array<Vertex>] the vertices of {#graph} that have an edge with - # `self` as their {Edge#destination} - def predecessors - incoming_edges.map(&:origin) - end - - # @return [Array<Vertex>] the vertices of {#graph} where `self` is a - # {#descendent?} - def recursive_predecessors - vertices = predecessors - vertices += vertices.map(&:recursive_predecessors).flatten(1) - vertices.uniq! - vertices - end - - # @return [Array<Vertex>] the vertices of {#graph} that have an edge with - # `self` as their {Edge#origin} - def successors - outgoing_edges.map(&:destination) - end - - # @return [Array<Vertex>] the vertices of {#graph} where `self` is an - # {#ancestor?} - def recursive_successors - vertices = successors - vertices += vertices.map(&:recursive_successors).flatten(1) - vertices.uniq! - vertices - end - - # @return [String] a string suitable for debugging - def inspect - "#{self.class}:#{name}(#{payload.inspect})" - end - - # @return [Boolean] whether the two vertices are equal, determined - # by a recursive traversal of each {Vertex#successors} - def ==(other) - return true if equal?(other) - shallow_eql?(other) && - successors.to_set == other.successors.to_set - end - - # @param [Vertex] other the other vertex to compare to - # @return [Boolean] whether the two vertices are equal, determined - # solely by {#name} and {#payload} equality - def shallow_eql?(other) - return true if equal?(other) - other && - name == other.name && - payload == other.payload - end - - alias eql? == - - # @return [Fixnum] a hash for the vertex based upon its {#name} - def hash - name.hash - end - - # Is there a path from `self` to `other` following edges in the - # dependency graph? - # @return true iff there is a path following edges within this {#graph} - def path_to?(other) - equal?(other) || successors.any? { |v| v.path_to?(other) } - end - - alias descendent? path_to? - - # Is there a path from `other` to `self` following edges in the - # dependency graph? - # @return true iff there is a path following edges within this {#graph} - def ancestor?(other) - other.path_to?(self) - end - - alias is_reachable_from? ancestor? - end - end -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/errors.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/errors.rb deleted file mode 100644 index 129246bf4a..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/errors.rb +++ /dev/null @@ -1,75 +0,0 @@ -# frozen_string_literal: true -module Gem::Resolver::Molinillo - # An error that occurred during the resolution process - class ResolverError < StandardError; end - - # An error caused by searching for a dependency that is completely unknown, - # i.e. has no versions available whatsoever. - class NoSuchDependencyError < ResolverError - # @return [Object] the dependency that could not be found - attr_accessor :dependency - - # @return [Array<Object>] the specifications that depended upon {#dependency} - attr_accessor :required_by - - # Initializes a new error with the given missing dependency. - # @param [Object] dependency @see {#dependency} - # @param [Array<Object>] required_by @see {#required_by} - def initialize(dependency, required_by = []) - @dependency = dependency - @required_by = required_by - super() - end - - # The error message for the missing dependency, including the specifications - # that had this dependency. - def message - sources = required_by.map { |r| "`#{r}`" }.join(' and ') - message = "Unable to find a specification for `#{dependency}`" - message += " depended upon by #{sources}" unless sources.empty? - message - end - end - - # An error caused by attempting to fulfil a dependency that was circular - # - # @note This exception will be thrown iff a {Vertex} is added to a - # {DependencyGraph} that has a {DependencyGraph::Vertex#path_to?} an - # existing {DependencyGraph::Vertex} - class CircularDependencyError < ResolverError - # [Set<Object>] the dependencies responsible for causing the error - attr_reader :dependencies - - # Initializes a new error with the given circular vertices. - # @param [Array<DependencyGraph::Vertex>] nodes the nodes in the dependency - # that caused the error - def initialize(nodes) - super "There is a circular dependency between #{nodes.map(&:name).join(' and ')}" - @dependencies = nodes.map(&:payload).to_set - end - end - - # An error caused by conflicts in version - class VersionConflict < ResolverError - # @return [{String => Resolution::Conflict}] the conflicts that caused - # resolution to fail - attr_reader :conflicts - - # Initializes a new error with the given version conflicts. - # @param [{String => Resolution::Conflict}] conflicts see {#conflicts} - def initialize(conflicts) - pairs = [] - conflicts.values.flatten.map(&:requirements).flatten.each do |conflicting| - conflicting.each do |source, conflict_requirements| - conflict_requirements.each do |c| - pairs << [c, source] - end - end - end - - super "Unable to satisfy the following requirements:\n\n" \ - "#{pairs.map { |r, d| "- `#{r}` required by `#{d}`" }.join("\n")}" - @conflicts = conflicts - end - end -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/gem_metadata.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/gem_metadata.rb deleted file mode 100644 index c5b5bd729f..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/gem_metadata.rb +++ /dev/null @@ -1,5 +0,0 @@ -# frozen_string_literal: true -module Gem::Resolver::Molinillo - # The version of Gem::Resolver::Molinillo. - VERSION = '0.5.7'.freeze -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/modules/specification_provider.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/modules/specification_provider.rb deleted file mode 100644 index 916345b12a..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/modules/specification_provider.rb +++ /dev/null @@ -1,100 +0,0 @@ -# frozen_string_literal: true -module Gem::Resolver::Molinillo - # Provides information about specifcations and dependencies to the resolver, - # allowing the {Resolver} class to remain generic while still providing power - # and flexibility. - # - # This module contains the methods that users of Gem::Resolver::Molinillo must to implement, - # using knowledge of their own model classes. - module SpecificationProvider - # Search for the specifications that match the given dependency. - # The specifications in the returned array will be considered in reverse - # order, so the latest version ought to be last. - # @note This method should be 'pure', i.e. the return value should depend - # only on the `dependency` parameter. - # - # @param [Object] dependency - # @return [Array<Object>] the specifications that satisfy the given - # `dependency`. - def search_for(dependency) - [] - end - - # Returns the dependencies of `specification`. - # @note This method should be 'pure', i.e. the return value should depend - # only on the `specification` parameter. - # - # @param [Object] specification - # @return [Array<Object>] the dependencies that are required by the given - # `specification`. - def dependencies_for(specification) - [] - end - - # Determines whether the given `requirement` is satisfied by the given - # `spec`, in the context of the current `activated` dependency graph. - # - # @param [Object] requirement - # @param [DependencyGraph] activated the current dependency graph in the - # resolution process. - # @param [Object] spec - # @return [Boolean] whether `requirement` is satisfied by `spec` in the - # context of the current `activated` dependency graph. - def requirement_satisfied_by?(requirement, activated, spec) - true - end - - # Returns the name for the given `dependency`. - # @note This method should be 'pure', i.e. the return value should depend - # only on the `dependency` parameter. - # - # @param [Object] dependency - # @return [String] the name for the given `dependency`. - def name_for(dependency) - dependency.to_s - end - - # @return [String] the name of the source of explicit dependencies, i.e. - # those passed to {Resolver#resolve} directly. - def name_for_explicit_dependency_source - 'user-specified dependency' - end - - # @return [String] the name of the source of 'locked' dependencies, i.e. - # those passed to {Resolver#resolve} directly as the `base` - def name_for_locking_dependency_source - 'Lockfile' - end - - # Sort dependencies so that the ones that are easiest to resolve are first. - # Easiest to resolve is (usually) defined by: - # 1) Is this dependency already activated? - # 2) How relaxed are the requirements? - # 3) Are there any conflicts for this dependency? - # 4) How many possibilities are there to satisfy this dependency? - # - # @param [Array<Object>] dependencies - # @param [DependencyGraph] activated the current dependency graph in the - # resolution process. - # @param [{String => Array<Conflict>}] conflicts - # @return [Array<Object>] a sorted copy of `dependencies`. - def sort_dependencies(dependencies, activated, conflicts) - dependencies.sort_by do |dependency| - name = name_for(dependency) - [ - activated.vertex_named(name).payload ? 0 : 1, - conflicts[name] ? 0 : 1, - ] - end - end - - # Returns whether this dependency, which has no possible matching - # specifications, can safely be ignored. - # - # @param [Object] dependency - # @return [Boolean] whether this dependency can safely be skipped. - def allow_missing?(dependency) - false - end - end -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/modules/ui.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/modules/ui.rb deleted file mode 100644 index dbc4e000e4..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/modules/ui.rb +++ /dev/null @@ -1,65 +0,0 @@ -# frozen_string_literal: true -module Gem::Resolver::Molinillo - # Conveys information about the resolution process to a user. - module UI - # The {IO} object that should be used to print output. `STDOUT`, by default. - # - # @return [IO] - def output - STDOUT - end - - # Called roughly every {#progress_rate}, this method should convey progress - # to the user. - # - # @return [void] - def indicate_progress - output.print '.' unless debug? - end - - # How often progress should be conveyed to the user via - # {#indicate_progress}, in seconds. A third of a second, by default. - # - # @return [Float] - def progress_rate - 0.33 - end - - # Called before resolution begins. - # - # @return [void] - def before_resolution - output.print 'Resolving dependencies...' - end - - # Called after resolution ends (either successfully or with an error). - # By default, prints a newline. - # - # @return [void] - def after_resolution - output.puts - end - - # Conveys debug information to the user. - # - # @param [Integer] depth the current depth of the resolution process. - # @return [void] - def debug(depth = 0) - if debug? - debug_info = yield - debug_info = debug_info.inspect unless debug_info.is_a?(String) - output.puts debug_info.split("\n").map { |s| ' ' * depth + s } - end - end - - # Whether or not debug messages should be printed. - # By default, whether or not the `MOLINILLO_DEBUG` environment variable is - # set. - # - # @return [Boolean] - def debug? - return @debug_mode if defined?(@debug_mode) - @debug_mode = ENV['MOLINILLO_DEBUG'] - end - end -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb deleted file mode 100644 index 73a4242157..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb +++ /dev/null @@ -1,494 +0,0 @@ -# frozen_string_literal: true -module Gem::Resolver::Molinillo - class Resolver - # A specific resolution from a given {Resolver} - class Resolution - # A conflict that the resolution process encountered - # @attr [Object] requirement the requirement that immediately led to the conflict - # @attr [{String,Nil=>[Object]}] requirements the requirements that caused the conflict - # @attr [Object, nil] existing the existing spec that was in conflict with - # the {#possibility} - # @attr [Object] possibility the spec that was unable to be activated due - # to a conflict - # @attr [Object] locked_requirement the relevant locking requirement. - # @attr [Array<Array<Object>>] requirement_trees the different requirement - # trees that led to every requirement for the conflicting name. - # @attr [{String=>Object}] activated_by_name the already-activated specs. - Conflict = Struct.new( - :requirement, - :requirements, - :existing, - :possibility, - :locked_requirement, - :requirement_trees, - :activated_by_name - ) - - # @return [SpecificationProvider] the provider that knows about - # dependencies, requirements, specifications, versions, etc. - attr_reader :specification_provider - - # @return [UI] the UI that knows how to communicate feedback about the - # resolution process back to the user - attr_reader :resolver_ui - - # @return [DependencyGraph] the base dependency graph to which - # dependencies should be 'locked' - attr_reader :base - - # @return [Array] the dependencies that were explicitly required - attr_reader :original_requested - - # Initializes a new resolution. - # @param [SpecificationProvider] specification_provider - # see {#specification_provider} - # @param [UI] resolver_ui see {#resolver_ui} - # @param [Array] requested see {#original_requested} - # @param [DependencyGraph] base see {#base} - def initialize(specification_provider, resolver_ui, requested, base) - @specification_provider = specification_provider - @resolver_ui = resolver_ui - @original_requested = requested - @base = base - @states = [] - @iteration_counter = 0 - @parents_of = Hash.new { |h, k| h[k] = [] } - end - - # Resolves the {#original_requested} dependencies into a full dependency - # graph - # @raise [ResolverError] if successful resolution is impossible - # @return [DependencyGraph] the dependency graph of successfully resolved - # dependencies - def resolve - start_resolution - - while state - break unless state.requirements.any? || state.requirement - indicate_progress - if state.respond_to?(:pop_possibility_state) # DependencyState - debug(depth) { "Creating possibility state for #{requirement} (#{possibilities.count} remaining)" } - state.pop_possibility_state.tap do |s| - if s - states.push(s) - activated.tag(s) - end - end - end - process_topmost_state - end - - activated.freeze - ensure - end_resolution - end - - # @return [Integer] the number of resolver iterations in between calls to - # {#resolver_ui}'s {UI#indicate_progress} method - attr_accessor :iteration_rate - private :iteration_rate - - # @return [Time] the time at which resolution began - attr_accessor :started_at - private :started_at - - # @return [Array<ResolutionState>] the stack of states for the resolution - attr_accessor :states - private :states - - private - - # Sets up the resolution process - # @return [void] - def start_resolution - @started_at = Time.now - - handle_missing_or_push_dependency_state(initial_state) - - debug { "Starting resolution (#{@started_at})\nUser-requested dependencies: #{original_requested}" } - resolver_ui.before_resolution - end - - # Ends the resolution process - # @return [void] - def end_resolution - resolver_ui.after_resolution - debug do - "Finished resolution (#{@iteration_counter} steps) " \ - "(Took #{(ended_at = Time.now) - @started_at} seconds) (#{ended_at})" - end - debug { 'Unactivated: ' + Hash[activated.vertices.reject { |_n, v| v.payload }].keys.join(', ') } if state - debug { 'Activated: ' + Hash[activated.vertices.select { |_n, v| v.payload }].keys.join(', ') } if state - end - - require 'rubygems/resolver/molinillo/lib/molinillo/state' - require 'rubygems/resolver/molinillo/lib/molinillo/modules/specification_provider' - - require 'rubygems/resolver/molinillo/lib/molinillo/delegates/resolution_state' - require 'rubygems/resolver/molinillo/lib/molinillo/delegates/specification_provider' - - include Gem::Resolver::Molinillo::Delegates::ResolutionState - include Gem::Resolver::Molinillo::Delegates::SpecificationProvider - - # Processes the topmost available {RequirementState} on the stack - # @return [void] - def process_topmost_state - if possibility - attempt_to_activate - else - create_conflict if state.is_a? PossibilityState - unwind_for_conflict until possibility && state.is_a?(DependencyState) - end - end - - # @return [Object] the current possibility that the resolution is trying - # to activate - def possibility - possibilities.last - end - - # @return [RequirementState] the current state the resolution is - # operating upon - def state - states.last - end - - # Creates the initial state for the resolution, based upon the - # {#requested} dependencies - # @return [DependencyState] the initial state for the resolution - def initial_state - graph = DependencyGraph.new.tap do |dg| - original_requested.each { |r| dg.add_vertex(name_for(r), nil, true).tap { |v| v.explicit_requirements << r } } - dg.tag(:initial_state) - end - - requirements = sort_dependencies(original_requested, graph, {}) - initial_requirement = requirements.shift - DependencyState.new( - initial_requirement && name_for(initial_requirement), - requirements, - graph, - initial_requirement, - initial_requirement && search_for(initial_requirement), - 0, - {} - ) - end - - # Unwinds the states stack because a conflict has been encountered - # @return [void] - def unwind_for_conflict - debug(depth) { "Unwinding for conflict: #{requirement} to #{state_index_for_unwind / 2}" } - conflicts.tap do |c| - sliced_states = states.slice!((state_index_for_unwind + 1)..-1) - raise VersionConflict.new(c) unless state - activated.rewind_to(sliced_states.first || :initial_state) if sliced_states - state.conflicts = c - index = states.size - 1 - @parents_of.each { |_, a| a.reject! { |i| i >= index } } - end - end - - # @return [Integer] The index to which the resolution should unwind in the - # case of conflict. - def state_index_for_unwind - current_requirement = requirement - existing_requirement = requirement_for_existing_name(name) - index = -1 - [current_requirement, existing_requirement].each do |r| - until r.nil? - current_state = find_state_for(r) - if state_any?(current_state) - current_index = states.index(current_state) - index = current_index if current_index > index - break - end - r = parent_of(r) - end - end - - index - end - - # @return [Object] the requirement that led to `requirement` being added - # to the list of requirements. - def parent_of(requirement) - return unless requirement - return unless index = @parents_of[requirement].last - return unless parent_state = @states[index] - parent_state.requirement - end - - # @return [Object] the requirement that led to a version of a possibility - # with the given name being activated. - def requirement_for_existing_name(name) - return nil unless activated.vertex_named(name).payload - states.find { |s| s.name == name }.requirement - end - - # @return [ResolutionState] the state whose `requirement` is the given - # `requirement`. - def find_state_for(requirement) - return nil unless requirement - states.reverse_each.find { |i| requirement == i.requirement && i.is_a?(DependencyState) } - end - - # @return [Boolean] whether or not the given state has any possibilities - # left. - def state_any?(state) - state && state.possibilities.any? - end - - # @return [Conflict] a {Conflict} that reflects the failure to activate - # the {#possibility} in conjunction with the current {#state} - def create_conflict - vertex = activated.vertex_named(name) - locked_requirement = locked_requirement_named(name) - - requirements = {} - unless vertex.explicit_requirements.empty? - requirements[name_for_explicit_dependency_source] = vertex.explicit_requirements - end - requirements[name_for_locking_dependency_source] = [locked_requirement] if locked_requirement - vertex.incoming_edges.each { |edge| (requirements[edge.origin.payload] ||= []).unshift(edge.requirement) } - - activated_by_name = {} - activated.each { |v| activated_by_name[v.name] = v.payload if v.payload } - conflicts[name] = Conflict.new( - requirement, - requirements, - vertex.payload, - possibility, - locked_requirement, - requirement_trees, - activated_by_name - ) - end - - # @return [Array<Array<Object>>] The different requirement - # trees that led to every requirement for the current spec. - def requirement_trees - vertex = activated.vertex_named(name) - vertex.requirements.map { |r| requirement_tree_for(r) } - end - - # @return [Array<Object>] the list of requirements that led to - # `requirement` being required. - def requirement_tree_for(requirement) - tree = [] - while requirement - tree.unshift(requirement) - requirement = parent_of(requirement) - end - tree - end - - # Indicates progress roughly once every second - # @return [void] - def indicate_progress - @iteration_counter += 1 - @progress_rate ||= resolver_ui.progress_rate - if iteration_rate.nil? - if Time.now - started_at >= @progress_rate - self.iteration_rate = @iteration_counter - end - end - - if iteration_rate && (@iteration_counter % iteration_rate) == 0 - resolver_ui.indicate_progress - end - end - - # Calls the {#resolver_ui}'s {UI#debug} method - # @param [Integer] depth the depth of the {#states} stack - # @param [Proc] block a block that yields a {#to_s} - # @return [void] - def debug(depth = 0, &block) - resolver_ui.debug(depth, &block) - end - - # Attempts to activate the current {#possibility} - # @return [void] - def attempt_to_activate - debug(depth) { 'Attempting to activate ' + possibility.to_s } - existing_node = activated.vertex_named(name) - if existing_node.payload - debug(depth) { "Found existing spec (#{existing_node.payload})" } - attempt_to_activate_existing_spec(existing_node) - else - attempt_to_activate_new_spec - end - end - - # Attempts to activate the current {#possibility} (given that it has - # already been activated) - # @return [void] - def attempt_to_activate_existing_spec(existing_node) - existing_spec = existing_node.payload - if requirement_satisfied_by?(requirement, activated, existing_spec) - new_requirements = requirements.dup - push_state_for_requirements(new_requirements, false) - else - return if attempt_to_swap_possibility - create_conflict - debug(depth) { "Unsatisfied by existing spec (#{existing_node.payload})" } - unwind_for_conflict - end - end - - # Attempts to swp the current {#possibility} with the already-activated - # spec with the given name - # @return [Boolean] Whether the possibility was swapped into {#activated} - def attempt_to_swap_possibility - activated.tag(:swap) - vertex = activated.vertex_named(name) - activated.set_payload(name, possibility) - if !vertex.requirements. - all? { |r| requirement_satisfied_by?(r, activated, possibility) } || - !new_spec_satisfied? - activated.rewind_to(:swap) - return - end - fixup_swapped_children(vertex) - activate_spec - end - - # Ensures there are no orphaned successors to the given {vertex}. - # @param [DependencyGraph::Vertex] vertex the vertex to fix up. - # @return [void] - def fixup_swapped_children(vertex) # rubocop:disable Metrics/CyclomaticComplexity - payload = vertex.payload - deps = dependencies_for(payload).group_by(&method(:name_for)) - vertex.outgoing_edges.each do |outgoing_edge| - requirement = outgoing_edge.requirement - parent_index = @parents_of[requirement].last - succ = outgoing_edge.destination - matching_deps = Array(deps[succ.name]) - dep_matched = matching_deps.include?(requirement) - - # only push the current index when it was originally required by the - # same named spec - if parent_index && states[parent_index].name == name - @parents_of[requirement].push(states.size - 1) - end - - if matching_deps.empty? && !succ.root? && succ.predecessors.to_a == [vertex] - debug(depth) { "Removing orphaned spec #{succ.name} after swapping #{name}" } - succ.requirements.each { |r| @parents_of.delete(r) } - - removed_names = activated.detach_vertex_named(succ.name).map(&:name) - requirements.delete_if do |r| - # the only removed vertices are those with no other requirements, - # so it's safe to delete only based upon name here - removed_names.include?(name_for(r)) - end - elsif !dep_matched - debug(depth) { "Removing orphaned dependency #{requirement} after swapping #{name}" } - # also reset if we're removing the edge, but only if its parent has - # already been fixed up - @parents_of[requirement].push(states.size - 1) if @parents_of[requirement].empty? - - activated.delete_edge(outgoing_edge) - requirements.delete(requirement) - end - end - end - - # Attempts to activate the current {#possibility} (given that it hasn't - # already been activated) - # @return [void] - def attempt_to_activate_new_spec - if new_spec_satisfied? - activate_spec - else - create_conflict - unwind_for_conflict - end - end - - # @return [Boolean] whether the current spec is satisfied as a new - # possibility. - def new_spec_satisfied? - unless requirement_satisfied_by?(requirement, activated, possibility) - debug(depth) { 'Unsatisfied by requested spec' } - return false - end - - locked_requirement = locked_requirement_named(name) - - locked_spec_satisfied = !locked_requirement || - requirement_satisfied_by?(locked_requirement, activated, possibility) - debug(depth) { 'Unsatisfied by locked spec' } unless locked_spec_satisfied - - locked_spec_satisfied - end - - # @param [String] requirement_name the spec name to search for - # @return [Object] the locked spec named `requirement_name`, if one - # is found on {#base} - def locked_requirement_named(requirement_name) - vertex = base.vertex_named(requirement_name) - vertex && vertex.payload - end - - # Add the current {#possibility} to the dependency graph of the current - # {#state} - # @return [void] - def activate_spec - conflicts.delete(name) - debug(depth) { "Activated #{name} at #{possibility}" } - activated.set_payload(name, possibility) - require_nested_dependencies_for(possibility) - end - - # Requires the dependencies that the recently activated spec has - # @param [Object] activated_spec the specification that has just been - # activated - # @return [void] - def require_nested_dependencies_for(activated_spec) - nested_dependencies = dependencies_for(activated_spec) - debug(depth) { "Requiring nested dependencies (#{nested_dependencies.join(', ')})" } - nested_dependencies.each do |d| - activated.add_child_vertex(name_for(d), nil, [name_for(activated_spec)], d) - parent_index = states.size - 1 - parents = @parents_of[d] - parents << parent_index if parents.empty? - end - - push_state_for_requirements(requirements + nested_dependencies, !nested_dependencies.empty?) - end - - # Pushes a new {DependencyState} that encapsulates both existing and new - # requirements - # @param [Array] new_requirements - # @return [void] - def push_state_for_requirements(new_requirements, requires_sort = true, new_activated = activated) - new_requirements = sort_dependencies(new_requirements.uniq, new_activated, conflicts) if requires_sort - new_requirement = new_requirements.shift - new_name = new_requirement ? name_for(new_requirement) : ''.freeze - possibilities = new_requirement ? search_for(new_requirement) : [] - handle_missing_or_push_dependency_state DependencyState.new( - new_name, new_requirements, new_activated, - new_requirement, possibilities, depth, conflicts.dup - ) - end - - # Pushes a new {DependencyState}. - # If the {#specification_provider} says to - # {SpecificationProvider#allow_missing?} that particular requirement, and - # there are no possibilities for that requirement, then `state` is not - # pushed, and the node in {#activated} is removed, and we continue - # resolving the remaining requirements. - # @param [DependencyState] state - # @return [void] - def handle_missing_or_push_dependency_state(state) - if state.requirement && state.possibilities.empty? && allow_missing?(state.requirement) - state.activated.detach_vertex_named(state.name) - push_state_for_requirements(state.requirements.dup, false, state.activated) - else - states.push(state).tap { activated.tag(state) } - end - end - end - end -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/resolver.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/resolver.rb deleted file mode 100644 index 5c59a45c3d..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/resolver.rb +++ /dev/null @@ -1,45 +0,0 @@ -# frozen_string_literal: true -require 'rubygems/resolver/molinillo/lib/molinillo/dependency_graph' - -module Gem::Resolver::Molinillo - # This class encapsulates a dependency resolver. - # The resolver is responsible for determining which set of dependencies to - # activate, with feedback from the {#specification_provider} - # - # - class Resolver - require 'rubygems/resolver/molinillo/lib/molinillo/resolution' - - # @return [SpecificationProvider] the specification provider used - # in the resolution process - attr_reader :specification_provider - - # @return [UI] the UI module used to communicate back to the user - # during the resolution process - attr_reader :resolver_ui - - # Initializes a new resolver. - # @param [SpecificationProvider] specification_provider - # see {#specification_provider} - # @param [UI] resolver_ui - # see {#resolver_ui} - def initialize(specification_provider, resolver_ui) - @specification_provider = specification_provider - @resolver_ui = resolver_ui - end - - # Resolves the requested dependencies into a {DependencyGraph}, - # locking to the base dependency graph (if specified) - # @param [Array] requested an array of 'requested' dependencies that the - # {#specification_provider} can understand - # @param [DependencyGraph,nil] base the base dependency graph to which - # dependencies should be 'locked' - def resolve(requested, base = DependencyGraph.new) - Resolution.new(specification_provider, - resolver_ui, - requested, - base). - resolve - end - end -end diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo/state.rb b/lib/rubygems/resolver/molinillo/lib/molinillo/state.rb deleted file mode 100644 index c20de98854..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/state.rb +++ /dev/null @@ -1,54 +0,0 @@ -# frozen_string_literal: true -module Gem::Resolver::Molinillo - # A state that a {Resolution} can be in - # @attr [String] name the name of the current requirement - # @attr [Array<Object>] requirements currently unsatisfied requirements - # @attr [DependencyGraph] activated the graph of activated dependencies - # @attr [Object] requirement the current requirement - # @attr [Object] possibilities the possibilities to satisfy the current requirement - # @attr [Integer] depth the depth of the resolution - # @attr [Set<Object>] conflicts unresolved conflicts - ResolutionState = Struct.new( - :name, - :requirements, - :activated, - :requirement, - :possibilities, - :depth, - :conflicts - ) - - class ResolutionState - # Returns an empty resolution state - # @return [ResolutionState] an empty state - def self.empty - new(nil, [], DependencyGraph.new, nil, nil, 0, Set.new) - end - end - - # A state that encapsulates a set of {#requirements} with an {Array} of - # possibilities - class DependencyState < ResolutionState - # Removes a possibility from `self` - # @return [PossibilityState] a state with a single possibility, - # the possibility that was removed from `self` - def pop_possibility_state - PossibilityState.new( - name, - requirements.dup, - activated, - requirement, - [possibilities.pop], - depth + 1, - conflicts.dup - ).tap do |state| - state.activated.tag(state) - end - end - end - - # A state that encapsulates a single possibility to fulfill the given - # {#requirement} - class PossibilityState < ResolutionState - end -end diff --git a/lib/rubygems/resolver/requirement_list.rb b/lib/rubygems/resolver/requirement_list.rb index 2768c80170..6f86f0f412 100644 --- a/lib/rubygems/resolver/requirement_list.rb +++ b/lib/rubygems/resolver/requirement_list.rb @@ -1,4 +1,5 @@ # frozen_string_literal: true + ## # The RequirementList is used to hold the requirements being considered # while resolving a set of gems. @@ -7,7 +8,6 @@ # first. class Gem::Resolver::RequirementList - include Enumerable ## @@ -18,7 +18,7 @@ class Gem::Resolver::RequirementList @list = [] end - def initialize_copy other # :nodoc: + def initialize_copy(other) # :nodoc: @exact = @exact.dup @list = @list.dup end diff --git a/lib/rubygems/resolver/set.rb b/lib/rubygems/resolver/set.rb index 11704d5c4c..243fee5fd5 100644 --- a/lib/rubygems/resolver/set.rb +++ b/lib/rubygems/resolver/set.rb @@ -1,10 +1,10 @@ # frozen_string_literal: true + ## # Resolver sets are used to look up specifications (and their # dependencies) used in resolution. This set is abstract. class Gem::Resolver::Set - ## # Set to true to disable network access for this set @@ -21,7 +21,6 @@ class Gem::Resolver::Set attr_accessor :prerelease def initialize # :nodoc: - require 'uri' @prerelease = false @remote = true @errors = [] @@ -31,7 +30,7 @@ class Gem::Resolver::Set # The find_all method must be implemented. It returns all Resolver # Specification objects matching the given DependencyRequest +req+. - def find_all req + def find_all(req) raise NotImplementedError end @@ -43,7 +42,7 @@ class Gem::Resolver::Set # When overridden, the #prefetch method should look up specifications # matching +reqs+. - def prefetch reqs + def prefetch(reqs) end ## @@ -53,5 +52,4 @@ class Gem::Resolver::Set def remote? # :nodoc: @remote end - end diff --git a/lib/rubygems/resolver/source_set.rb b/lib/rubygems/resolver/source_set.rb index 66f5963e54..074b473edc 100644 --- a/lib/rubygems/resolver/source_set.rb +++ b/lib/rubygems/resolver/source_set.rb @@ -1,10 +1,11 @@ +# frozen_string_literal: true + ## # The SourceSet chooses the best available method to query a remote index. # # Kind off like BestSet but filters the sources for gems class Gem::Resolver::SourceSet < Gem::Resolver::Set - ## # Creates a SourceSet for the given +sources+ or Gem::sources if none are # specified. +sources+ must be a Gem::SourceList. @@ -16,7 +17,7 @@ class Gem::Resolver::SourceSet < Gem::Resolver::Set @sets = {} end - def find_all req # :nodoc: + def find_all(req) # :nodoc: if set = get_set(req.dependency.name) set.find_all req else @@ -25,7 +26,7 @@ class Gem::Resolver::SourceSet < Gem::Resolver::Set end # potentially no-op - def prefetch reqs # :nodoc: + def prefetch(reqs) # :nodoc: reqs.each do |req| if set = get_set(req.dependency.name) set.prefetch reqs @@ -33,16 +34,14 @@ class Gem::Resolver::SourceSet < Gem::Resolver::Set end end - def add_source_gem name, source + def add_source_gem(name, source) @links[name] = source end -private + private def get_set(name) link = @links[name] - @sets[link] ||= Gem::Source.new(link).dependency_resolver_set if link + @sets[link] ||= Gem::Source.new(link).dependency_resolver_set(@prerelease) if link end - end - diff --git a/lib/rubygems/resolver/spec_specification.rb b/lib/rubygems/resolver/spec_specification.rb index 35ee8cc247..00ef9fdba0 100644 --- a/lib/rubygems/resolver/spec_specification.rb +++ b/lib/rubygems/resolver/spec_specification.rb @@ -1,16 +1,16 @@ # frozen_string_literal: true + ## # The Resolver::SpecSpecification contains common functionality for # Resolver specifications that are backed by a Gem::Specification. class Gem::Resolver::SpecSpecification < Gem::Resolver::Specification - ## # A SpecSpecification is created for a +set+ for a Gem::Specification in # +spec+. The +source+ is either where the +spec+ came from, or should be # loaded from. - def initialize set, spec, source = nil + def initialize(set, spec, source = nil) @set = set @source = source @spec = spec @@ -24,6 +24,20 @@ class Gem::Resolver::SpecSpecification < Gem::Resolver::Specification end ## + # The required_ruby_version constraint for this specification + + def required_ruby_version + spec.required_ruby_version + end + + ## + # The required_rubygems_version constraint for this specification + + def required_rubygems_version + spec.required_rubygems_version + end + + ## # The name and version of the specification. # # Unlike Gem::Specification#full_name, the platform is not included. @@ -53,5 +67,10 @@ class Gem::Resolver::SpecSpecification < Gem::Resolver::Specification spec.version end -end + ## + # The hash value for this specification. + def hash + spec.hash + end +end diff --git a/lib/rubygems/resolver/specification.rb b/lib/rubygems/resolver/specification.rb index 44989d39ae..d2098ef0e2 100644 --- a/lib/rubygems/resolver/specification.rb +++ b/lib/rubygems/resolver/specification.rb @@ -1,11 +1,11 @@ # frozen_string_literal: true + ## # A Resolver::Specification contains a subset of the information # contained in a Gem::Specification. Only the information necessary for # dependency resolution in the resolver is included. class Gem::Resolver::Specification - ## # The dependencies of the gem for this specification @@ -45,6 +45,16 @@ class Gem::Resolver::Specification attr_reader :version ## + # The required_ruby_version constraint for this specification. + + attr_reader :required_ruby_version + + ## + # The required_ruby_version constraint for this specification. + + attr_reader :required_rubygems_version + + ## # Sets default instance variables for the specification. def initialize @@ -54,6 +64,8 @@ class Gem::Resolver::Specification @set = nil @source = nil @version = nil + @required_ruby_version = Gem::Requirement.default + @required_rubygems_version = Gem::Requirement.default end ## @@ -81,14 +93,10 @@ class Gem::Resolver::Specification # After installation #spec is updated to point to the just-installed # specification. - def install options = {} - require 'rubygems/installer' + def install(options = {}) + require_relative "../installer" - destination = options[:install_dir] || Gem.dir - - Gem.ensure_gem_subdirectories destination - - gem = source.download spec, destination + gem = download options installer = Gem::Installer.at gem, options @@ -97,15 +105,22 @@ class Gem::Resolver::Specification @spec = installer.install end + def download(options) + dir = options[:install_dir] || Gem.dir + + Gem.ensure_gem_subdirectories dir + + source.download spec, dir + end + ## # Returns true if this specification is installable on this platform. def installable_platform? - Gem::Platform.match spec.platform + Gem::Platform.match_spec? spec end def local? # :nodoc: false end end - diff --git a/lib/rubygems/resolver/stats.rb b/lib/rubygems/resolver/stats.rb deleted file mode 100644 index 3b95efebf7..0000000000 --- a/lib/rubygems/resolver/stats.rb +++ /dev/null @@ -1,45 +0,0 @@ -# frozen_string_literal: true -class Gem::Resolver::Stats - def initialize - @max_depth = 0 - @max_requirements = 0 - @requirements = 0 - @backtracking = 0 - @iterations = 0 - end - - def record_depth(stack) - if stack.size > @max_depth - @max_depth = stack.size - end - end - - def record_requirements(reqs) - if reqs.size > @max_requirements - @max_requirements = reqs.size - end - end - - def requirement! - @requirements += 1 - end - - def backtracking! - @backtracking += 1 - end - - def iteration! - @iterations += 1 - end - - PATTERN = "%20s: %d\n" - - def display - $stdout.puts "=== Resolver Statistics ===" - $stdout.printf PATTERN, "Max Depth", @max_depth - $stdout.printf PATTERN, "Total Requirements", @requirements - $stdout.printf PATTERN, "Max Requirements", @max_requirements - $stdout.printf PATTERN, "Backtracking #", @backtracking - $stdout.printf PATTERN, "Iteration #", @iterations - end -end diff --git a/lib/rubygems/resolver/strategy.rb b/lib/rubygems/resolver/strategy.rb new file mode 100644 index 0000000000..bf0dbb6adc --- /dev/null +++ b/lib/rubygems/resolver/strategy.rb @@ -0,0 +1,44 @@ +# frozen_string_literal: true + +# Custom PubGrub strategy with caching for version selection. +# Modeled after Bundler's strategy to avoid redundant versions_for +# calls during the solver's package selection loop. + +class Gem::Resolver::Strategy + def initialize(source) + @source = source + @package_priority_cache = Hash.new {|h, pkg| h[pkg] = {} } + + @version_indexes = Hash.new do |h, k| + if Gem::PubGrub::Package.root?(k) + h[k] = { Gem::PubGrub::Package.root_version => 0 } + else + h[k] = @source.all_versions_for(k).each.with_index.to_h + end + end + end + + def next_package_and_version(unsatisfied) + package, range = next_term_to_try_from(unsatisfied) + [package, most_preferred_version_of(package, range)] + end + + private + + def most_preferred_version_of(package, range) + versions = @source.versions_for(package, range) + indexes = @version_indexes[package] + versions.min_by {|version| indexes[version] || Float::INFINITY } + end + + def next_term_to_try_from(unsatisfied) + unsatisfied.min_by do |package, range| + @package_priority_cache[package][range] ||= begin + matching_versions = @source.versions_for(package, range) + higher_versions = @source.versions_for(package, range.upper_invert) + + [matching_versions.count <= 1 ? 0 : 1, higher_versions.count] + end + end + end +end diff --git a/lib/rubygems/resolver/vendor_set.rb b/lib/rubygems/resolver/vendor_set.rb index f30ce534af..293a1e3331 100644 --- a/lib/rubygems/resolver/vendor_set.rb +++ b/lib/rubygems/resolver/vendor_set.rb @@ -1,4 +1,5 @@ # frozen_string_literal: true + ## # A VendorSet represents gems that have been unpacked into a specific # directory that contains a gemspec. @@ -15,7 +16,6 @@ # rake.gemspec (watching the given name). class Gem::Resolver::VendorSet < Gem::Resolver::Set - ## # The specifications for this set. @@ -32,7 +32,7 @@ class Gem::Resolver::VendorSet < Gem::Resolver::Set # Adds a specification to the set with the given +name+ which has been # unpacked into the given +directory+. - def add_vendor_gem name, directory # :nodoc: + def add_vendor_gem(name, directory) # :nodoc: gemspec = File.join directory, "#{name}.gemspec" spec = Gem::Specification.load gemspec @@ -52,7 +52,7 @@ class Gem::Resolver::VendorSet < Gem::Resolver::Set # Returns an Array of VendorSpecification objects matching the # DependencyRequest +req+. - def find_all req + def find_all(req) @specs.values.select do |spec| req.match? spec end.map do |spec| @@ -65,12 +65,12 @@ class Gem::Resolver::VendorSet < Gem::Resolver::Set # Loads a spec with the given +name+. +version+, +platform+ and +source+ are # ignored. - def load_spec name, version, platform, source # :nodoc: + def load_spec(name, version, platform, source) # :nodoc: @specs.fetch name end - def pretty_print q # :nodoc: - q.group 2, '[VendorSet', ']' do + def pretty_print(q) # :nodoc: + q.group 2, "[VendorSet", "]" do next if @directories.empty? q.breakable @@ -83,6 +83,4 @@ class Gem::Resolver::VendorSet < Gem::Resolver::Set end end end - end - diff --git a/lib/rubygems/resolver/vendor_specification.rb b/lib/rubygems/resolver/vendor_specification.rb index c624f3e834..ac78f54558 100644 --- a/lib/rubygems/resolver/vendor_specification.rb +++ b/lib/rubygems/resolver/vendor_specification.rb @@ -1,15 +1,15 @@ # frozen_string_literal: true + ## # A VendorSpecification represents a gem that has been unpacked into a project # and is being loaded through a gem dependencies file through the +path:+ # option. class Gem::Resolver::VendorSpecification < Gem::Resolver::SpecSpecification - - def == other # :nodoc: - self.class === other and - @set == other.set and - @spec == other.spec and + def ==(other) # :nodoc: + self.class === other && + @set == other.set && + @spec == other.spec && @source == other.source end @@ -17,9 +17,7 @@ class Gem::Resolver::VendorSpecification < Gem::Resolver::SpecSpecification # This is a null install as this gem was unpacked into a directory. # +options+ are ignored. - def install options = {} + def install(options = {}) yield nil end - end - |