diff options
Diffstat (limited to 'lib/rubygems/resolver')
50 files changed, 214 insertions, 2709 deletions
diff --git a/lib/rubygems/resolver/activation_request.rb b/lib/rubygems/resolver/activation_request.rb index ae35681db9..5c722001b1 100644 --- a/lib/rubygems/resolver/activation_request.rb +++ b/lib/rubygems/resolver/activation_request.rb @@ -1,4 +1,5 @@ # frozen_string_literal: true + ## # Specifies a Specification object that should be activated. Also contains a # dependency that was used to introduce this activation. @@ -58,10 +59,8 @@ class Gem::Resolver::ActivationRequest if @spec.respond_to? :sources exception = nil path = @spec.sources.find do |source| - begin - source.download full_spec, path - rescue exception - end + source.download full_spec, path + rescue exception end return path if path raise exception if exception @@ -93,9 +92,7 @@ class Gem::Resolver::ActivationRequest end def inspect # :nodoc: - '#<%s for %p from %s>' % [ - self.class, @spec, @request - ] + format("#<%s for %p from %s>", self.class, @spec, @request) end ## @@ -109,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 @@ -130,12 +127,12 @@ class Gem::Resolver::ActivationRequest end def pretty_print(q) # :nodoc: - q.group 2, '[Activation request', ']' do + q.group 2, "[Activation request", "]" do q.breakable q.pp @spec q.breakable - q.text ' for ' + q.text " for " q.pp @request end end diff --git a/lib/rubygems/resolver/api_set.rb b/lib/rubygems/resolver/api_set.rb index 21c9b8920c..3f443519d8 100644 --- a/lib/rubygems/resolver/api_set.rb +++ b/lib/rubygems/resolver/api_set.rb @@ -1,13 +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: @@ -22,17 +23,17 @@ 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 - # https://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://index.rubygems.org/info/') + def initialize(dep_uri = "https://index.rubygems.org/info/") super() - dep_uri = URI dep_uri unless URI === dep_uri + 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] = [] } @source = Gem::Source.new @uri @@ -75,7 +76,8 @@ class Gem::Resolver::APISet < Gem::Resolver::Set end def prefetch_now # :nodoc: - needed, @to_fetch = @to_fetch, [] + needed = @to_fetch + @to_fetch = [] needed.sort.each do |name| versions(name) @@ -83,12 +85,12 @@ class Gem::Resolver::APISet < Gem::Resolver::Set end def pretty_print(q) # :nodoc: - q.group 2, '[APISet', ']' do + 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 @@ -102,16 +104,21 @@ class Gem::Resolver::APISet < Gem::Resolver::Set end uri = @dep_uri + name - str = Gem::RemoteFetcher.fetcher.fetch_path uri - lines(str).each do |ver| - number, platform, dependencies, requirements = parse_gem(ver) + 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) - 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 + 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 } + @data[name] << { name: name, number: number, platform: platform, dependencies: dependencies, requirements: requirements } + end end @data[name] diff --git a/lib/rubygems/resolver/api_set/gem_parser.rb b/lib/rubygems/resolver/api_set/gem_parser.rb index 685c39558d..4d827f4980 100644 --- a/lib/rubygems/resolver/api_set/gem_parser.rb +++ b/lib/rubygems/resolver/api_set/gem_parser.rb @@ -4,17 +4,18 @@ 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) } : [] + 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(":") + 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 b5aa0b71d4..ccfd6fe084 100644 --- a/lib/rubygems/resolver/api_specification.rb +++ b/lib/rubygems/resolver/api_specification.rb @@ -1,6 +1,7 @@ # 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. @@ -18,10 +19,10 @@ class Gem::Resolver::APISpecification < Gem::Resolver::Specification 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 https://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) @@ -40,10 +41,10 @@ class Gem::Resolver::APISpecification < Gem::Resolver::Specification end def ==(other) # :nodoc: - self.class === other and - @set == other.set and - @name == other.name and - @version == other.version and + self.class === other && + @set == other.set && + @name == other.name && + @version == other.version && @platform == other.platform end @@ -62,7 +63,7 @@ class Gem::Resolver::APISpecification < Gem::Resolver::Specification end def pretty_print(q) # :nodoc: - q.group 2, '[APISpecification', ']' do + q.group 2, "[APISpecification", "]" do q.breakable q.text "name: #{name}" @@ -73,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 diff --git a/lib/rubygems/resolver/best_set.rb b/lib/rubygems/resolver/best_set.rb index 300ea8015c..e647a2c11b 100644 --- a/lib/rubygems/resolver/best_set.rb +++ b/lib/rubygems/resolver/best_set.rb @@ -1,4 +1,5 @@ # frozen_string_literal: true + ## # The BestSet chooses the best available method to query a remote index. # @@ -20,57 +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? + 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? + pick_sets if @remote && @sets.empty? super end def pretty_print(q) # :nodoc: - q.group 2, '[BestSet', ']' do + 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.original_uri - uri = URI uri unless URI === uri - uri = uri + "." - - raise error unless api_set = @sets.find do |set| - Gem::Resolver::APISet === set and set.dep_uri == uri - end - - 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 226da1e1e0..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. # @@ -43,16 +44,16 @@ class Gem::Resolver::ComposedSet < Gem::Resolver::Set 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| + @sets.flat_map do |s| s.find_all req - end.flatten + end end ## diff --git a/lib/rubygems/resolver/conflict.rb b/lib/rubygems/resolver/conflict.rb deleted file mode 100644 index 4c4588d7e8..0000000000 --- a/lib/rubygems/resolver/conflict.rb +++ /dev/null @@ -1,153 +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? - 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 - 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 diff --git a/lib/rubygems/resolver/current_set.rb b/lib/rubygems/resolver/current_set.rb index c3aa3a2c37..370e445089 100644 --- a/lib/rubygems/resolver/current_set.rb +++ b/lib/rubygems/resolver/current_set.rb @@ -1,4 +1,5 @@ # frozen_string_literal: true + ## # A set which represents the installed gems. Respects # all the normal settings that control where to look diff --git a/lib/rubygems/resolver/dependency_request.rb b/lib/rubygems/resolver/dependency_request.rb index 356aadb3b2..60b338277f 100644 --- a/lib/rubygems/resolver/dependency_request.rb +++ b/lib/rubygems/resolver/dependency_request.rb @@ -1,4 +1,5 @@ # frozen_string_literal: true + ## # Used Internally. Wraps a Dependency object to also track which spec # contained the Dependency. @@ -95,12 +96,12 @@ class Gem::Resolver::DependencyRequest end def pretty_print(q) # :nodoc: - q.group 2, '[Dependency request ', ']' do + 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 diff --git a/lib/rubygems/resolver/git_set.rb b/lib/rubygems/resolver/git_set.rb index eac51f15ad..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. # @@ -35,7 +36,6 @@ class Gem::Resolver::GitSet < Gem::Resolver::Set def initialize # :nodoc: super() - @git = ENV['git'] || 'git' @need_submodules = {} @repositories = {} @root_dir = Gem.dir @@ -104,7 +104,7 @@ class Gem::Resolver::GitSet < Gem::Resolver::Set end def pretty_print(q) # :nodoc: - q.group 2, '[GitSet', ']' do + q.group 2, "[GitSet", "]" do next if @repositories.empty? q.breakable diff --git a/lib/rubygems/resolver/git_specification.rb b/lib/rubygems/resolver/git_specification.rb index ee47080ab4..e587c17d2a 100644 --- a/lib/rubygems/resolver/git_specification.rb +++ b/lib/rubygems/resolver/git_specification.rb @@ -1,4 +1,5 @@ # 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:+ @@ -6,9 +7,9 @@ class Gem::Resolver::GitSpecification < Gem::Resolver::SpecSpecification def ==(other) # :nodoc: - self.class === other and - @set == other.set and - @spec == other.spec and + self.class === other && + @set == other.set && + @spec == other.spec && @source == other.source end @@ -21,7 +22,7 @@ class Gem::Resolver::GitSpecification < Gem::Resolver::SpecSpecification # the executables. def install(options = {}) - require_relative '../installer' + require_relative "../installer" installer = Gem::Installer.for_spec spec, options @@ -35,7 +36,7 @@ class Gem::Resolver::GitSpecification < Gem::Resolver::SpecSpecification end def pretty_print(q) # :nodoc: - q.group 2, '[GitSpecification', ']' do + q.group 2, "[GitSpecification", "]" do q.breakable q.text "name: #{name}" @@ -43,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 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 9390e34255..cddaf8773f 100644 --- a/lib/rubygems/resolver/index_set.rb +++ b/lib/rubygems/resolver/index_set.rb @@ -1,4 +1,5 @@ # frozen_string_literal: true + ## # The global rubygems pool represented via the traditional # source index. @@ -43,32 +44,32 @@ class Gem::Resolver::IndexSet < Gem::Resolver::Set name = req.dependency.name @all[name].each do |uri, n| - if req.match? n, @prerelease - 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 + 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 diff --git a/lib/rubygems/resolver/index_specification.rb b/lib/rubygems/resolver/index_specification.rb index 9ea76f40ba..7b95608071 100644 --- a/lib/rubygems/resolver/index_specification.rb +++ b/lib/rubygems/resolver/index_specification.rb @@ -1,4 +1,5 @@ # 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+ @@ -21,7 +22,8 @@ class Gem::Resolver::IndexSpecification < Gem::Resolver::Specification @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 @@ -66,21 +68,21 @@ class Gem::Resolver::IndexSpecification < Gem::Resolver::Specification 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 + q.group 2, "[Index specification", "]" do q.breakable q.text full_name - unless Gem::Platform::RUBY == @platform + 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 @@ -91,7 +93,7 @@ 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 diff --git a/lib/rubygems/resolver/installed_specification.rb b/lib/rubygems/resolver/installed_specification.rb index 167ba1439e..8280ae4672 100644 --- a/lib/rubygems/resolver/installed_specification.rb +++ b/lib/rubygems/resolver/installed_specification.rb @@ -1,12 +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 + self.class === other && + @set == other.set && @spec == other.spec end @@ -24,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 + q.group 2, "[InstalledSpecification", "]" do q.breakable q.text "name: #{name}" @@ -41,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 diff --git a/lib/rubygems/resolver/installer_set.rb b/lib/rubygems/resolver/installer_set.rb index f4fee351a5..42ce0890e2 100644 --- a/lib/rubygems/resolver/installer_set.rb +++ b/lib/rubygems/resolver/installer_set.rb @@ -1,4 +1,5 @@ # frozen_string_literal: true + ## # A set of gems for installation sourced from remote sources and local .gem # files @@ -61,36 +62,35 @@ class Gem::Resolver::InstallerSet < Gem::Resolver::Set found = find_all request found.delete_if do |s| - s.version.prerelease? and not s.local? + 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, s.platform == Gem::Platform::RUBY ? -1 : 1] + [s.version, Gem::Platform.sort_priority(s.platform)] end newest = found.last + unless newest + exc = Gem::UnsatisfiableDependencyError.new request + exc.errors = errors + + raise exc + end + unless @force found_matching_metadata = found.reverse.find do |spec| metadata_satisfied?(spec) end if found_matching_metadata.nil? - if newest - ensure_required_ruby_version_met(newest.spec) - ensure_required_rubygems_version_met(newest.spec) - else - exc = Gem::UnsatisfiableDependencyError.new request - exc.errors = errors - - raise exc - end + ensure_required_ruby_version_met(newest.spec) + ensure_required_rubygems_version_met(newest.spec) else newest = found_matching_metadata end @@ -111,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 ## @@ -137,8 +137,8 @@ class Gem::Resolver::InstallerSet < Gem::Resolver::Set 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 @@ -148,6 +148,8 @@ class Gem::Resolver::InstallerSet < Gem::Resolver::Set res << Gem::Resolver::InstalledSpecification.new(self, gemspec) end unless @ignore_installed + matching_local = [] + if consider_local? matching_local = @local.values.select do |spec, _| req.match? spec @@ -158,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) + @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 @@ -188,11 +187,9 @@ class Gem::Resolver::InstallerSet < Gem::Resolver::Set 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 ## @@ -219,16 +216,16 @@ class Gem::Resolver::InstallerSet < Gem::Resolver::Set end def pretty_print(q) # :nodoc: - q.group 2, '[InstallerSet', ']' do + 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 @@ -266,7 +263,7 @@ class Gem::Resolver::InstallerSet < Gem::Resolver::Set 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}. " + + "#{spec.full_name} requires RubyGems version #{rrgv}. The current RubyGems version is #{rg_version}. " \ "Try 'gem update --system' to update RubyGems itself." end end diff --git a/lib/rubygems/resolver/local_specification.rb b/lib/rubygems/resolver/local_specification.rb index 9c69c4ab74..b57d40e795 100644 --- a/lib/rubygems/resolver/local_specification.rb +++ b/lib/rubygems/resolver/local_specification.rb @@ -1,4 +1,5 @@ # frozen_string_literal: true + ## # A LocalSpecification comes from a .gem file on the local filesystem. @@ -7,7 +8,7 @@ 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,7 +18,7 @@ class Gem::Resolver::LocalSpecification < Gem::Resolver::SpecSpecification end def pretty_print(q) # :nodoc: - q.group 2, '[LocalSpecification', ']' do + q.group 2, "[LocalSpecification", "]" do q.breakable q.text "name: #{name}" @@ -28,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 diff --git a/lib/rubygems/resolver/lock_set.rb b/lib/rubygems/resolver/lock_set.rb index eabf217aba..e5ee32a9a6 100644 --- a/lib/rubygems/resolver/lock_set.rb +++ b/lib/rubygems/resolver/lock_set.rb @@ -1,4 +1,5 @@ # frozen_string_literal: true + ## # A set of gems from a gem dependencies lockfile. @@ -54,7 +55,7 @@ class Gem::Resolver::LockSet < Gem::Resolver::Set 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,18 +64,18 @@ class Gem::Resolver::LockSet < Gem::Resolver::Set end def pretty_print(q) # :nodoc: - q.group 2, '[LockSet', ']' do + 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 cdb8e4e425..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). # @@ -29,7 +30,7 @@ class Gem::Resolver::LockSpecification < Gem::Resolver::Specification def install(options = {}) destination = options[:install_dir] || Gem.dir - if File.exist? File.join(destination, 'specifications', spec.spec_name) + if File.exist? File.join(destination, "specifications", spec.spec_name) yield nil return end @@ -45,7 +46,7 @@ class Gem::Resolver::LockSpecification < Gem::Resolver::Specification end def pretty_print(q) # :nodoc: - q.group 2, '[LockSpecification', ']' do + q.group 2, "[LockSpecification", "]" do q.breakable q.text "name: #{@name}" @@ -59,7 +60,7 @@ class Gem::Resolver::LockSpecification < Gem::Resolver::Specification unless @dependencies.empty? q.breakable - q.text 'dependencies:' + q.text "dependencies:" q.breakable q.pp @dependencies end @@ -71,7 +72,7 @@ class Gem::Resolver::LockSpecification < Gem::Resolver::Specification def spec @spec ||= Gem::Specification.find do |spec| - spec.name == @name and spec.version == @version + spec.name == @name && spec.version == @version end @spec ||= Gem::Specification.new do |s| diff --git a/lib/rubygems/resolver/molinillo.rb b/lib/rubygems/resolver/molinillo.rb deleted file mode 100644 index 12ca740e5a..0000000000 --- a/lib/rubygems/resolver/molinillo.rb +++ /dev/null @@ -1,2 +0,0 @@ -# frozen_string_literal: true -require_relative 'molinillo/lib/molinillo' diff --git a/lib/rubygems/resolver/molinillo/LICENSE b/lib/rubygems/resolver/molinillo/LICENSE deleted file mode 100644 index 01feffa088..0000000000 --- a/lib/rubygems/resolver/molinillo/LICENSE +++ /dev/null @@ -1,9 +0,0 @@ -This project is licensed under the MIT license. - -Copyright (c) 2014 Samuel E. Giddins segiddins@segiddins.me - -Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. diff --git a/lib/rubygems/resolver/molinillo/lib/molinillo.rb b/lib/rubygems/resolver/molinillo/lib/molinillo.rb deleted file mode 100644 index f67badbde7..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo.rb +++ /dev/null @@ -1,11 +0,0 @@ -# frozen_string_literal: true - -require_relative 'molinillo/gem_metadata' -require_relative 'molinillo/errors' -require_relative 'molinillo/resolver' -require_relative 'molinillo/modules/ui' -require_relative '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 d540d3baff..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/delegates/resolution_state.rb +++ /dev/null @@ -1,57 +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 - - # (see Gem::Resolver::Molinillo::ResolutionState#unused_unwind_options) - def unused_unwind_options - current_state = state || Gem::Resolver::Molinillo::ResolutionState.empty - current_state.unused_unwind_options - 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 b765226fb0..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/delegates/specification_provider.rb +++ /dev/null @@ -1,88 +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#dependencies_equal?) - def dependencies_equal?(dependencies, other_dependencies) - with_no_such_dependency_error_handling do - specification_provider.dependencies_equal?(dependencies, other_dependencies) - 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 95f8416b96..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb +++ /dev/null @@ -1,255 +0,0 @@ -# frozen_string_literal: true - -require_relative '../../../../tsort' - -require_relative 'dependency_graph/log' -require_relative '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 Gem::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 - - # @param [DependencyGraph] other - # @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_vertex = vertex_named(parent_name) - add_edge(parent_vertex, 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(path(destination, origin)) - 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 - - # Returns the path between two vertices - # @raise [ArgumentError] if there is no path between the vertices - # @param [Vertex] from - # @param [Vertex] to - # @return [Array<Vertex>] the shortest path from `from` to `to` - def path(from, to) - distances = Hash.new(vertices.size + 1) - distances[from.name] = 0 - predecessors = {} - each do |vertex| - vertex.successors.each do |successor| - if distances[successor.name] > distances[vertex.name] + 1 - distances[successor.name] = distances[vertex.name] + 1 - predecessors[successor] = vertex - end - end - end - - path = [to] - while before = predecessors[to] - path << before - to = before - break if to == from - end - - unless path.last.equal?(from) - raise ArgumentError, "There is no path from #{from.name} to #{to.name}" - end - - path.reverse - 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 cc140031b3..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/action.rb +++ /dev/null @@ -1,36 +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 5570483253..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb +++ /dev/null @@ -1,66 +0,0 @@ -# frozen_string_literal: true - -require_relative '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 f1411d5efa..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/add_vertex.rb +++ /dev/null @@ -1,62 +0,0 @@ -# frozen_string_literal: true - -require_relative '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 3b48d77a50..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/delete_edge.rb +++ /dev/null @@ -1,63 +0,0 @@ -# frozen_string_literal: true - -require_relative '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 92f60d5be8..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/detach_vertex_named.rb +++ /dev/null @@ -1,61 +0,0 @@ -# frozen_string_literal: true - -require_relative '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 7aeb8847ec..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/log.rb +++ /dev/null @@ -1,126 +0,0 @@ -# frozen_string_literal: true - -require_relative 'add_edge_no_circular' -require_relative 'add_vertex' -require_relative 'delete_edge' -require_relative 'detach_vertex_named' -require_relative 'set_payload' -require_relative '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 726292a2c3..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/set_payload.rb +++ /dev/null @@ -1,46 +0,0 @@ -# frozen_string_literal: true - -require_relative '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 bfe6fd31f8..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/tag.rb +++ /dev/null @@ -1,36 +0,0 @@ -# frozen_string_literal: true - -require_relative '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 77114951b2..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph/vertex.rb +++ /dev/null @@ -1,164 +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).uniq - 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 [Set<Vertex>] the vertices of {#graph} where `self` is a - # {#descendent?} - def recursive_predecessors - _recursive_predecessors - end - - # @param [Set<Vertex>] vertices the set to add the predecessors to - # @return [Set<Vertex>] the vertices of {#graph} where `self` is a - # {#descendent?} - def _recursive_predecessors(vertices = new_vertex_set) - incoming_edges.each do |edge| - vertex = edge.origin - next unless vertices.add?(vertex) - vertex._recursive_predecessors(vertices) - end - - vertices - end - protected :_recursive_predecessors - - # @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 [Set<Vertex>] the vertices of {#graph} where `self` is an - # {#ancestor?} - def recursive_successors - _recursive_successors - end - - # @param [Set<Vertex>] vertices the set to add the successors to - # @return [Set<Vertex>] the vertices of {#graph} where `self` is an - # {#ancestor?} - def _recursive_successors(vertices = new_vertex_set) - outgoing_edges.each do |edge| - vertex = edge.destination - next unless vertices.add?(vertex) - vertex._recursive_successors(vertices) - end - - vertices - end - protected :_recursive_successors - - # @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 whether there is a path following edges within this {#graph} - def path_to?(other) - _path_to?(other) - end - - alias descendent? path_to? - - # @param [Vertex] other the vertex to check if there's a path to - # @param [Set<Vertex>] visited the vertices of {#graph} that have been visited - # @return [Boolean] whether there is a path to `other` from `self` - def _path_to?(other, visited = new_vertex_set) - return false unless visited.add?(self) - return true if equal?(other) - successors.any? { |v| v._path_to?(other, visited) } - end - protected :_path_to? - - # Is there a path from `other` to `self` following edges in the - # dependency graph? - # @return whether there is a path following edges within this {#graph} - def ancestor?(other) - other.path_to?(self) - end - - alias is_reachable_from? ancestor? - - def new_vertex_set - require 'set' - Set.new - end - private :new_vertex_set - 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 ada03a901c..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/errors.rb +++ /dev/null @@ -1,143 +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.uniq - 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 if and only if 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>] vertices the vertices in the dependency - # that caused the error - def initialize(vertices) - super "There is a circular dependency between #{vertices.map(&:name).join(' and ')}" - @dependencies = vertices.map { |vertex| vertex.payload.possibilities.last }.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 - - # @return [SpecificationProvider] the specification provider used during - # resolution - attr_reader :specification_provider - - # Initializes a new error with the given version conflicts. - # @param [{String => Resolution::Conflict}] conflicts see {#conflicts} - # @param [SpecificationProvider] specification_provider see {#specification_provider} - def initialize(conflicts, specification_provider) - pairs = [] - conflicts.values.flat_map(&:requirements).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 - @specification_provider = specification_provider - end - - require_relative 'delegates/specification_provider' - include Delegates::SpecificationProvider - - # @return [String] An error message that includes requirement trees, - # which is much more detailed & customizable than the default message - # @param [Hash] opts the options to create a message with. - # @option opts [String] :solver_name The user-facing name of the solver - # @option opts [String] :possibility_type The generic name of a possibility - # @option opts [Proc] :reduce_trees A proc that reduced the list of requirement trees - # @option opts [Proc] :printable_requirement A proc that pretty-prints requirements - # @option opts [Proc] :additional_message_for_conflict A proc that appends additional - # messages for each conflict - # @option opts [Proc] :version_for_spec A proc that returns the version number for a - # possibility - def message_with_trees(opts = {}) - solver_name = opts.delete(:solver_name) { self.class.name.split('::').first } - possibility_type = opts.delete(:possibility_type) { 'possibility named' } - reduce_trees = opts.delete(:reduce_trees) { proc { |trees| trees.uniq.sort_by(&:to_s) } } - printable_requirement = opts.delete(:printable_requirement) { proc { |req| req.to_s } } - additional_message_for_conflict = opts.delete(:additional_message_for_conflict) { proc {} } - version_for_spec = opts.delete(:version_for_spec) { proc(&:to_s) } - incompatible_version_message_for_conflict = opts.delete(:incompatible_version_message_for_conflict) do - proc do |name, _conflict| - %(#{solver_name} could not find compatible versions for #{possibility_type} "#{name}":) - end - end - - conflicts.sort.reduce(''.dup) do |o, (name, conflict)| - o << "\n" << incompatible_version_message_for_conflict.call(name, conflict) << "\n" - if conflict.locked_requirement - o << %( In snapshot (#{name_for_locking_dependency_source}):\n) - o << %( #{printable_requirement.call(conflict.locked_requirement)}\n) - o << %(\n) - end - o << %( In #{name_for_explicit_dependency_source}:\n) - trees = reduce_trees.call(conflict.requirement_trees) - - o << trees.map do |tree| - t = ''.dup - depth = 2 - tree.each do |req| - t << ' ' * depth << printable_requirement.call(req) - unless tree.last == req - if spec = conflict.activated_by_name[name_for(req)] - t << %( was resolved to #{version_for_spec.call(spec)}, which) - end - t << %( depends on) - end - t << %(\n) - depth += 1 - end - t - end.join("\n") - - additional_message_for_conflict.call(o, name, conflict) - - o - end.strip - 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 6b5ada7ade..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/gem_metadata.rb +++ /dev/null @@ -1,6 +0,0 @@ -# frozen_string_literal: true - -module Gem::Resolver::Molinillo - # The version of Gem::Resolver::Molinillo. - VERSION = '0.7.0'.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 1067bf7439..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/modules/specification_provider.rb +++ /dev/null @@ -1,112 +0,0 @@ -# frozen_string_literal: true - -module Gem::Resolver::Molinillo - # Provides information about specifications 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 - - # Determines whether two arrays of dependencies are equal, and thus can be - # grouped. - # - # @param [Array<Object>] dependencies - # @param [Array<Object>] other_dependencies - # @return [Boolean] whether `dependencies` and `other_dependencies` should - # be considered equal. - def dependencies_equal?(dependencies, other_dependencies) - dependencies == other_dependencies - 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 a810fd519c..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/modules/ui.rb +++ /dev/null @@ -1,67 +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) - debug_info = debug_info.split("\n").map { |s| ":#{depth.to_s.rjust 4}: #{s}" } - output.puts debug_info - 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 8b40e59e42..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/resolution.rb +++ /dev/null @@ -1,839 +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_set the set of specs 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. - # @attr [Object] underlying_error an error that has occurred during resolution, and - # will be raised at the end of it if no resolution is found. - Conflict = Struct.new( - :requirement, - :requirements, - :existing, - :possibility_set, - :locked_requirement, - :requirement_trees, - :activated_by_name, - :underlying_error - ) - - class Conflict - # @return [Object] a spec that was unable to be activated due to a conflict - def possibility - possibility_set && possibility_set.latest_version - end - end - - # A collection of possibility states that share the same dependencies - # @attr [Array] dependencies the dependencies for this set of possibilities - # @attr [Array] possibilities the possibilities - PossibilitySet = Struct.new(:dependencies, :possibilities) - - class PossibilitySet - # String representation of the possibility set, for debugging - def to_s - "[#{possibilities.join(', ')}]" - end - - # @return [Object] most up-to-date dependency in the possibility set - def latest_version - possibilities.last - end - end - - # Details of the state to unwind to when a conflict occurs, and the cause of the unwind - # @attr [Integer] state_index the index of the state to unwind to - # @attr [Object] state_requirement the requirement of the state we're unwinding to - # @attr [Array] requirement_tree for the requirement we're relaxing - # @attr [Array] conflicting_requirements the requirements that combined to cause the conflict - # @attr [Array] requirement_trees for the conflict - # @attr [Array] requirements_unwound_to_instead array of unwind requirements that were chosen over this unwind - UnwindDetails = Struct.new( - :state_index, - :state_requirement, - :requirement_tree, - :conflicting_requirements, - :requirement_trees, - :requirements_unwound_to_instead - ) - - class UnwindDetails - include Comparable - - # We compare UnwindDetails when choosing which state to unwind to. If - # two options have the same state_index we prefer the one most - # removed from a requirement that caused the conflict. Both options - # would unwind to the same state, but a `grandparent` option will - # filter out fewer of its possibilities after doing so - where a state - # is both a `parent` and a `grandparent` to requirements that have - # caused a conflict this is the correct behaviour. - # @param [UnwindDetail] other UnwindDetail to be compared - # @return [Integer] integer specifying ordering - def <=>(other) - if state_index > other.state_index - 1 - elsif state_index == other.state_index - reversed_requirement_tree_index <=> other.reversed_requirement_tree_index - else - -1 - end - end - - # @return [Integer] index of state requirement in reversed requirement tree - # (the conflicting requirement itself will be at position 0) - def reversed_requirement_tree_index - @reversed_requirement_tree_index ||= - if state_requirement - requirement_tree.reverse.index(state_requirement) - else - 999_999 - end - end - - # @return [Boolean] where the requirement of the state we're unwinding - # to directly caused the conflict. Note: in this case, it is - # impossible for the state we're unwinding to to be a parent of - # any of the other conflicting requirements (or we would have - # circularity) - def unwinding_to_primary_requirement? - requirement_tree.last == state_requirement - end - - # @return [Array] array of sub-dependencies to avoid when choosing a - # new possibility for the state we've unwound to. Only relevant for - # non-primary unwinds - def sub_dependencies_to_avoid - @requirements_to_avoid ||= - requirement_trees.map do |tree| - index = tree.index(state_requirement) - tree[index + 1] if index - end.compact - end - - # @return [Array] array of all the requirements that led to the need for - # this unwind - def all_requirements - @all_requirements ||= requirement_trees.flatten(1) - end - end - - # @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 if !state.requirement && state.requirements.empty? - 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 - - resolve_activated_specs - 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 - - push_initial_state - - debug { "Starting resolution (#{@started_at})\nUser-requested dependencies: #{original_requested}" } - resolver_ui.before_resolution - end - - def resolve_activated_specs - activated.vertices.each do |_, vertex| - next unless vertex.payload - - latest_version = vertex.payload.possibilities.reverse_each.find do |possibility| - vertex.requirements.all? { |req| requirement_satisfied_by?(req, activated, possibility) } - end - - activated.set_payload(vertex.name, latest_version) - end - activated.freeze - 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_relative 'state' - require_relative 'modules/specification_provider' - - require_relative 'delegates/resolution_state' - require_relative '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 - unwind_for_conflict - end - rescue CircularDependencyError => underlying_error - create_conflict(underlying_error) - unwind_for_conflict - 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 and pushes the initial state for the resolution, based upon the - # {#requested} dependencies - # @return [void] - def push_initial_state - graph = DependencyGraph.new.tap do |dg| - original_requested.each do |requested| - vertex = dg.add_vertex(name_for(requested), nil, true) - vertex.explicit_requirements << requested - end - dg.tag(:initial_state) - end - - push_state_for_requirements(original_requested, true, graph) - end - - # Unwinds the states stack because a conflict has been encountered - # @return [void] - def unwind_for_conflict - details_for_unwind = build_details_for_unwind - unwind_options = unused_unwind_options - debug(depth) { "Unwinding for conflict: #{requirement} to #{details_for_unwind.state_index / 2}" } - conflicts.tap do |c| - sliced_states = states.slice!((details_for_unwind.state_index + 1)..-1) - raise_error_unless_state(c) - activated.rewind_to(sliced_states.first || :initial_state) if sliced_states - state.conflicts = c - state.unused_unwind_options = unwind_options - filter_possibilities_after_unwind(details_for_unwind) - index = states.size - 1 - @parents_of.each { |_, a| a.reject! { |i| i >= index } } - state.unused_unwind_options.reject! { |uw| uw.state_index >= index } - end - end - - # Raises a VersionConflict error, or any underlying error, if there is no - # current state - # @return [void] - def raise_error_unless_state(conflicts) - return if state - - error = conflicts.values.map(&:underlying_error).compact.first - raise error || VersionConflict.new(conflicts, specification_provider) - end - - # @return [UnwindDetails] Details of the nearest index to which we could unwind - def build_details_for_unwind - # Get the possible unwinds for the current conflict - current_conflict = conflicts[name] - binding_requirements = binding_requirements_for_conflict(current_conflict) - unwind_details = unwind_options_for_requirements(binding_requirements) - - last_detail_for_current_unwind = unwind_details.sort.last - current_detail = last_detail_for_current_unwind - - # Look for past conflicts that could be unwound to affect the - # requirement tree for the current conflict - all_reqs = last_detail_for_current_unwind.all_requirements - all_reqs_size = all_reqs.size - relevant_unused_unwinds = unused_unwind_options.select do |alternative| - diff_reqs = all_reqs - alternative.requirements_unwound_to_instead - next if diff_reqs.size == all_reqs_size - # Find the highest index unwind whilst looping through - current_detail = alternative if alternative > current_detail - alternative - end - - # Add the current unwind options to the `unused_unwind_options` array. - # The "used" option will be filtered out during `unwind_for_conflict`. - state.unused_unwind_options += unwind_details.reject { |detail| detail.state_index == -1 } - - # Update the requirements_unwound_to_instead on any relevant unused unwinds - relevant_unused_unwinds.each do |d| - (d.requirements_unwound_to_instead << current_detail.state_requirement).uniq! - end - unwind_details.each do |d| - (d.requirements_unwound_to_instead << current_detail.state_requirement).uniq! - end - - current_detail - end - - # @param [Array<Object>] binding_requirements array of requirements that combine to create a conflict - # @return [Array<UnwindDetails>] array of UnwindDetails that have a chance - # of resolving the passed requirements - def unwind_options_for_requirements(binding_requirements) - unwind_details = [] - - trees = [] - binding_requirements.reverse_each do |r| - partial_tree = [r] - trees << partial_tree - unwind_details << UnwindDetails.new(-1, nil, partial_tree, binding_requirements, trees, []) - - # If this requirement has alternative possibilities, check if any would - # satisfy the other requirements that created this conflict - requirement_state = find_state_for(r) - if conflict_fixing_possibilities?(requirement_state, binding_requirements) - unwind_details << UnwindDetails.new( - states.index(requirement_state), - r, - partial_tree, - binding_requirements, - trees, - [] - ) - end - - # Next, look at the parent of this requirement, and check if the requirement - # could have been avoided if an alternative PossibilitySet had been chosen - parent_r = parent_of(r) - next if parent_r.nil? - partial_tree.unshift(parent_r) - requirement_state = find_state_for(parent_r) - if requirement_state.possibilities.any? { |set| !set.dependencies.include?(r) } - unwind_details << UnwindDetails.new( - states.index(requirement_state), - parent_r, - partial_tree, - binding_requirements, - trees, - [] - ) - end - - # Finally, look at the grandparent and up of this requirement, looking - # for any possibilities that wouldn't create their parent requirement - grandparent_r = parent_of(parent_r) - until grandparent_r.nil? - partial_tree.unshift(grandparent_r) - requirement_state = find_state_for(grandparent_r) - if requirement_state.possibilities.any? { |set| !set.dependencies.include?(parent_r) } - unwind_details << UnwindDetails.new( - states.index(requirement_state), - grandparent_r, - partial_tree, - binding_requirements, - trees, - [] - ) - end - parent_r = grandparent_r - grandparent_r = parent_of(parent_r) - end - end - - unwind_details - end - - # @param [DependencyState] state - # @param [Array] binding_requirements array of requirements - # @return [Boolean] whether or not the given state has any possibilities - # that could satisfy the given requirements - def conflict_fixing_possibilities?(state, binding_requirements) - return false unless state - - state.possibilities.any? do |possibility_set| - possibility_set.possibilities.any? do |poss| - possibility_satisfies_requirements?(poss, binding_requirements) - end - end - end - - # Filter's a state's possibilities to remove any that would not fix the - # conflict we've just rewound from - # @param [UnwindDetails] unwind_details details of the conflict just - # unwound from - # @return [void] - def filter_possibilities_after_unwind(unwind_details) - return unless state && !state.possibilities.empty? - - if unwind_details.unwinding_to_primary_requirement? - filter_possibilities_for_primary_unwind(unwind_details) - else - filter_possibilities_for_parent_unwind(unwind_details) - end - end - - # Filter's a state's possibilities to remove any that would not satisfy - # the requirements in the conflict we've just rewound from - # @param [UnwindDetails] unwind_details details of the conflict just unwound from - # @return [void] - def filter_possibilities_for_primary_unwind(unwind_details) - unwinds_to_state = unused_unwind_options.select { |uw| uw.state_index == unwind_details.state_index } - unwinds_to_state << unwind_details - unwind_requirement_sets = unwinds_to_state.map(&:conflicting_requirements) - - state.possibilities.reject! do |possibility_set| - possibility_set.possibilities.none? do |poss| - unwind_requirement_sets.any? do |requirements| - possibility_satisfies_requirements?(poss, requirements) - end - end - end - end - - # @param [Object] possibility a single possibility - # @param [Array] requirements an array of requirements - # @return [Boolean] whether the possibility satisfies all of the - # given requirements - def possibility_satisfies_requirements?(possibility, requirements) - name = name_for(possibility) - - activated.tag(:swap) - activated.set_payload(name, possibility) if activated.vertex_named(name) - satisfied = requirements.all? { |r| requirement_satisfied_by?(r, activated, possibility) } - activated.rewind_to(:swap) - - satisfied - end - - # Filter's a state's possibilities to remove any that would (eventually) - # create a requirement in the conflict we've just rewound from - # @param [UnwindDetails] unwind_details details of the conflict just unwound from - # @return [void] - def filter_possibilities_for_parent_unwind(unwind_details) - unwinds_to_state = unused_unwind_options.select { |uw| uw.state_index == unwind_details.state_index } - unwinds_to_state << unwind_details - - primary_unwinds = unwinds_to_state.select(&:unwinding_to_primary_requirement?).uniq - parent_unwinds = unwinds_to_state.uniq - primary_unwinds - - allowed_possibility_sets = primary_unwinds.flat_map do |unwind| - states[unwind.state_index].possibilities.select do |possibility_set| - possibility_set.possibilities.any? do |poss| - possibility_satisfies_requirements?(poss, unwind.conflicting_requirements) - end - end - end - - requirements_to_avoid = parent_unwinds.flat_map(&:sub_dependencies_to_avoid) - - state.possibilities.reject! do |possibility_set| - !allowed_possibility_sets.include?(possibility_set) && - (requirements_to_avoid - possibility_set.dependencies).empty? - end - end - - # @param [Conflict] conflict - # @return [Array] minimal array of requirements that would cause the passed - # conflict to occur. - def binding_requirements_for_conflict(conflict) - return [conflict.requirement] if conflict.possibility.nil? - - possible_binding_requirements = conflict.requirements.values.flatten(1).uniq - - # When there's a `CircularDependency` error the conflicting requirement - # (the one causing the circular) won't be `conflict.requirement` - # (which won't be for the right state, because we won't have created it, - # because it's circular). - # We need to make sure we have that requirement in the conflict's list, - # otherwise we won't be able to unwind properly, so we just return all - # the requirements for the conflict. - return possible_binding_requirements if conflict.underlying_error - - possibilities = search_for(conflict.requirement) - - # If all the requirements together don't filter out all possibilities, - # then the only two requirements we need to consider are the initial one - # (where the dependency's version was first chosen) and the last - if binding_requirement_in_set?(nil, possible_binding_requirements, possibilities) - return [conflict.requirement, requirement_for_existing_name(name_for(conflict.requirement))].compact - end - - # Loop through the possible binding requirements, removing each one - # that doesn't bind. Use a `reverse_each` as we want the earliest set of - # binding requirements, and don't use `reject!` as we wish to refine the - # array *on each iteration*. - binding_requirements = possible_binding_requirements.dup - possible_binding_requirements.reverse_each do |req| - next if req == conflict.requirement - unless binding_requirement_in_set?(req, binding_requirements, possibilities) - binding_requirements -= [req] - end - end - - binding_requirements - end - - # @param [Object] requirement we wish to check - # @param [Array] possible_binding_requirements array of requirements - # @param [Array] possibilities array of possibilities the requirements will be used to filter - # @return [Boolean] whether or not the given requirement is required to filter - # out all elements of the array of possibilities. - def binding_requirement_in_set?(requirement, possible_binding_requirements, possibilities) - possibilities.any? do |poss| - possibility_satisfies_requirements?(poss, possible_binding_requirements - [requirement]) - end - end - - # @param [Object] requirement - # @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 - - # @param [String] name - # @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 vertex = activated.vertex_named(name) - return nil unless vertex.payload - states.find { |s| s.name == name }.requirement - end - - # @param [Object] requirement - # @return [ResolutionState] the state whose `requirement` is the given - # `requirement`. - def find_state_for(requirement) - return nil unless requirement - states.find { |i| requirement == i.requirement } - end - - # @param [Object] underlying_error - # @return [Conflict] a {Conflict} that reflects the failure to activate - # the {#possibility} in conjunction with the current {#state} - def create_conflict(underlying_error = nil) - 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 do |edge| - (requirements[edge.origin.payload.latest_version] ||= []).unshift(edge.requirement) - end - - activated_by_name = {} - activated.each { |v| activated_by_name[v.name] = v.payload.latest_version if v.payload } - conflicts[name] = Conflict.new( - requirement, - requirements, - vertex.payload && vertex.payload.latest_version, - possibility, - locked_requirement, - requirement_trees, - activated_by_name, - underlying_error - ) - 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 - - # @param [Object] requirement - # @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_vertex = activated.vertex_named(name) - if existing_vertex.payload - debug(depth) { "Found existing spec (#{existing_vertex.payload})" } - attempt_to_filter_existing_spec(existing_vertex) - else - latest = possibility.latest_version - possibility.possibilities.select! do |possibility| - requirement_satisfied_by?(requirement, activated, possibility) - end - if possibility.latest_version.nil? - # ensure there's a possibility for better error messages - possibility.possibilities << latest if latest - create_conflict - unwind_for_conflict - else - activate_new_spec - end - end - end - - # Attempts to update the existing vertex's `PossibilitySet` with a filtered version - # @return [void] - def attempt_to_filter_existing_spec(vertex) - filtered_set = filtered_possibility_set(vertex) - if !filtered_set.possibilities.empty? - activated.set_payload(name, filtered_set) - new_requirements = requirements.dup - push_state_for_requirements(new_requirements, false) - else - create_conflict - debug(depth) { "Unsatisfied by existing spec (#{vertex.payload})" } - unwind_for_conflict - end - end - - # Generates a filtered version of the existing vertex's `PossibilitySet` using the - # current state's `requirement` - # @param [Object] vertex existing vertex - # @return [PossibilitySet] filtered possibility set - def filtered_possibility_set(vertex) - PossibilitySet.new(vertex.payload.dependencies, vertex.payload.possibilities & possibility.possibilities) - 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_new_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] possibility_set the PossibilitySet that has just been - # activated - # @return [void] - def require_nested_dependencies_for(possibility_set) - nested_dependencies = dependencies_for(possibility_set.latest_version) - debug(depth) { "Requiring nested dependencies (#{nested_dependencies.join(', ')})" } - nested_dependencies.each do |d| - activated.add_child_vertex(name_for(d), nil, [name_for(possibility_set.latest_version)], 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 - # @param [Boolean] requires_sort - # @param [Object] new_activated - # @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 = nil - loop do - new_requirement = new_requirements.shift - break if new_requirement.nil? || states.none? { |s| s.requirement == new_requirement } - end - new_name = new_requirement ? name_for(new_requirement) : ''.freeze - possibilities = possibilities_for_requirement(new_requirement) - handle_missing_or_push_dependency_state DependencyState.new( - new_name, new_requirements, new_activated, - new_requirement, possibilities, depth, conflicts.dup, unused_unwind_options.dup - ) - end - - # Checks a proposed requirement with any existing locked requirement - # before generating an array of possibilities for it. - # @param [Object] requirement the proposed requirement - # @param [Object] activated - # @return [Array] possibilities - def possibilities_for_requirement(requirement, activated = self.activated) - return [] unless requirement - if locked_requirement_named(name_for(requirement)) - return locked_requirement_possibility_set(requirement, activated) - end - - group_possibilities(search_for(requirement)) - end - - # @param [Object] requirement the proposed requirement - # @param [Object] activated - # @return [Array] possibility set containing only the locked requirement, if any - def locked_requirement_possibility_set(requirement, activated = self.activated) - all_possibilities = search_for(requirement) - locked_requirement = locked_requirement_named(name_for(requirement)) - - # Longwinded way to build a possibilities array with either the locked - # requirement or nothing in it. Required, since the API for - # locked_requirement isn't guaranteed. - locked_possibilities = all_possibilities.select do |possibility| - requirement_satisfied_by?(locked_requirement, activated, possibility) - end - - group_possibilities(locked_possibilities) - end - - # Build an array of PossibilitySets, with each element representing a group of - # dependency versions that all have the same sub-dependency version constraints - # and are contiguous. - # @param [Array] possibilities an array of possibilities - # @return [Array<PossibilitySet>] an array of possibility sets - def group_possibilities(possibilities) - possibility_sets = [] - current_possibility_set = nil - - possibilities.reverse_each do |possibility| - dependencies = dependencies_for(possibility) - if current_possibility_set && dependencies_equal?(current_possibility_set.dependencies, dependencies) - current_possibility_set.possibilities.unshift(possibility) - else - possibility_sets.unshift(PossibilitySet.new(dependencies, [possibility])) - current_possibility_set = possibility_sets.first - end - end - - possibility_sets - 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 vertex 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 d43121f8ca..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/resolver.rb +++ /dev/null @@ -1,46 +0,0 @@ -# frozen_string_literal: true - -require_relative '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_relative '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 6e7c715fce..0000000000 --- a/lib/rubygems/resolver/molinillo/lib/molinillo/state.rb +++ /dev/null @@ -1,58 +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 [Hash] conflicts unresolved conflicts, indexed by dependency name - # @attr [Array<UnwindDetails>] unused_unwind_options unwinds for previous conflicts that weren't explored - ResolutionState = Struct.new( - :name, - :requirements, - :activated, - :requirement, - :possibilities, - :depth, - :conflicts, - :unused_unwind_options - ) - - class ResolutionState - # Returns an empty resolution state - # @return [ResolutionState] an empty state - def self.empty - new(nil, [], DependencyGraph.new, nil, nil, 0, {}, []) - 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, - unused_unwind_options.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 5b51493c9a..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. diff --git a/lib/rubygems/resolver/set.rb b/lib/rubygems/resolver/set.rb index 5d8dd51eaa..243fee5fd5 100644 --- a/lib/rubygems/resolver/set.rb +++ b/lib/rubygems/resolver/set.rb @@ -1,4 +1,5 @@ # frozen_string_literal: true + ## # Resolver sets are used to look up specifications (and their # dependencies) used in resolution. This set is abstract. diff --git a/lib/rubygems/resolver/source_set.rb b/lib/rubygems/resolver/source_set.rb index bf8c23184e..074b473edc 100644 --- a/lib/rubygems/resolver/source_set.rb +++ b/lib/rubygems/resolver/source_set.rb @@ -1,3 +1,5 @@ +# frozen_string_literal: true + ## # The SourceSet chooses the best available method to query a remote index. # @@ -40,6 +42,6 @@ class Gem::Resolver::SourceSet < Gem::Resolver::Set 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 7b665fe876..00ef9fdba0 100644 --- a/lib/rubygems/resolver/spec_specification.rb +++ b/lib/rubygems/resolver/spec_specification.rb @@ -1,4 +1,5 @@ # frozen_string_literal: true + ## # The Resolver::SpecSpecification contains common functionality for # Resolver specifications that are backed by a Gem::Specification. @@ -65,4 +66,11 @@ class Gem::Resolver::SpecSpecification < Gem::Resolver::Specification def version spec.version 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 dfcb7eb057..d2098ef0e2 100644 --- a/lib/rubygems/resolver/specification.rb +++ b/lib/rubygems/resolver/specification.rb @@ -1,4 +1,5 @@ # frozen_string_literal: true + ## # A Resolver::Specification contains a subset of the information # contained in a Gem::Specification. Only the information necessary for @@ -93,7 +94,7 @@ class Gem::Resolver::Specification # specification. def install(options = {}) - require_relative '../installer' + require_relative "../installer" gem = download options diff --git a/lib/rubygems/resolver/stats.rb b/lib/rubygems/resolver/stats.rb deleted file mode 100644 index 64b458f504..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".freeze - - 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 48c640d8c9..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. @@ -69,7 +70,7 @@ class Gem::Resolver::VendorSet < Gem::Resolver::Set end def pretty_print(q) # :nodoc: - q.group 2, '[VendorSet', ']' do + q.group 2, "[VendorSet", "]" do next if @directories.empty? q.breakable diff --git a/lib/rubygems/resolver/vendor_specification.rb b/lib/rubygems/resolver/vendor_specification.rb index 8dfe5940f2..ac78f54558 100644 --- a/lib/rubygems/resolver/vendor_specification.rb +++ b/lib/rubygems/resolver/vendor_specification.rb @@ -1,4 +1,5 @@ # 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:+ @@ -6,9 +7,9 @@ class Gem::Resolver::VendorSpecification < Gem::Resolver::SpecSpecification def ==(other) # :nodoc: - self.class === other and - @set == other.set and - @spec == other.spec and + self.class === other && + @set == other.set && + @spec == other.spec && @source == other.source end |